多机调度问题 贪心算法解决 C++

问题：设有n个独立的作业{1, 2, …, n}, 由m台相同的机器进行加工处理。作业i所需时间为Ti. 约定:任何作业可以在任何一台机器上加工处理, 但未完工前不允许中断处理,任何作业不能拆分成更小的子作业。要求给出一种作业执行次序，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。

要求：随机生成n个作业相关信息，并计算由m台机器处理的最短时间。

分析思路：daidai贪心法求解多机调度问题的贪心策略是最长处理时间作业优先，即把处理时间最长的作业分配给最先空闲的机器，这样可以保证处理时间长的作业优先处理，从而在整体上获得尽可能短的处理时间。按照最长处理时间作业优先的贪心策略，当m≥n时，只要将机器i的[0，ti)时间区间分配给作业i即可;当m<n时，首先将n个作业依其所需的处理时间从大到小排序，然后依此顺序将作业分配给空闲的处理机。

使用贪心法，将n个作业所用时间存放到数组里t[i]，对耗费时间进行降序排序，用另外一个数组f记录每一台机器的当前机器累加作业时间，将当前机器累加作业时间进行升序排序，将排出来当前机器累加作业时间的最小值（最先空闲的机器）与作业时间最大值相加，存入数组中f[0] =t[i]，再将f升序排序，for循环重复操作，最终将所有机器累加的时间进行排序，输出最大值。

代码如下：

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;

int n,m;                        //n为作业数，m为机器数
bool compare(int a,int b)
{
return a>b;
}
int main(){
        
     printf("请输入n,m ");
    scanf("%d%d",&n,&m);
    
    int t[n];                    //存放n个作业完成时间 
    for(int i=0;i<n;i ){
    
         t[i]=rand()0;          //随机生成一组数据存放在t数组里 
         printf("作业%d所用%dh\n",i,t[i]);
    
    }
    sort(t,t n,compare);        //对耗费时间进行降序排序 ，从大到小排 
    int f[m]={0};                //用来记录每一台机器的时间
    
    for(int i=0;i<n;i ){
        sort(f,f m);          //将机器当前累加作业时间进行升序排序 ，从小到大排 
        f[0] =t[i];      //将排出来的机器数最小值与作业时间最大值相加，for循环重复操作 
    }
    sort(f,f m);          //最终将所有机器累加的时间进行排序 
    printf("贪心法近似最优解为%dh\n",f[m-1]);
} 

但是多机调用问题使用贪心算法，最大的问题是：贪心算法只能求得近似解或者最优解，并不能将所有解求得最优，具有一定的局限性。

最好使用回溯法或分支限界法。

这篇好文章是转载于：学新通技术网