多机调度问题(贪心算法)

心已赠人 2022-12-28 01:39 147阅读 0赞

某工厂有n个独立的作业，由m台相同的机器进行加工处理。作业i所需的加工时间为ti，任何作业在被处理时不能中 断，也不能进行拆分处理。现厂长请你给他写一个程序：算出n个作业由m台机器加工处理的最短时间

解题思路：

当n<=m时，只要将作业分给每一个机器即可；当n>m时，首先将n个作业从大到小排序，然后依此顺序将作业分配给空闲 的处理机。也就是说从剩下的作业中，选择需要处理时间最长的，然后依次选择处理时间次长的，直到所有的作业全部处 理完毕，或者机器不能再处理其他作业为止。如果我们每次是将需要处理时间最短的作业分配给空闲的机器，那么可能就 会出现其它所有作业都处理完了只剩所需时间最长的作业在处理的情况，这样势必效率较低。

代码如下：

#include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
    int mintime(vector<int>time, int m)
    {
    	vector<int>machine(m, 0);
    	sort(time.begin(), time.end());
    	int n = time.size();
    	if (n <= m){
    		return time[n - 1];
    	}
    	else{
    		for (int i = n - 1; i >= 0; --i){
    			int min = 0;
    			int machinetime = machine[min];
    			for (int j = 1; j < m; j++){
    				if (machinetime>machine[j]){
    					min = j;
    					machinetime = machine[j];
    				}
    			}
    			machine[min] += time[i];
    		}
    	}
    	n = machine[0];
    	for (int i = 1; i < m; i++){
    		n = n<machine[i] ? machine[i] : n;
    	}
    	return n;
    }
    int main()
    {
    	vector<int>time{ 2 ,5 ,13 ,15 ,16 ,20};
    	int m;
    	cin >> m;
    	cout << "最小的时间：" << mintime(time,m) <<endl;
    }