问题描述
下面用一道2013上半年软件设计师的软考题来说明这个问题。
设有 M 台完全相同的机器运行 N 个独立的任务（任务不可分割)，运行任务 i 所需要的时间为，要求确定一个调度方案，使得完成所有任务所需要的时间最短，任务运行时独占机器。
这里要求定义的变量如下，所有数组的下标皆从0开始：
设m是机器数，n 是任务数，t[ ] 的长度为 n，其中每个元素表示各个任务的运行时间。
s[ ][ ]长度为 mn，下标从0开始，其中 s[ i ][ j ] 表示机器 i 运行的任务 j 。
d[ ]长度为 m，其中 d[ i ]表示机器i运行的时间。
count[ ]长度为 m，其中元素 count[ i ] 表示机器i运行 的任务数。
max 为完成所有任务的时间。min，i，j，k 为临时定义变量，无意义。
输入样例
机器数：5
任务数：7
每个任务的运行时间（从大到小）：16 14 6 5 4 3 2
输出样例
完成所有任务需要的时间为：16
各个机器执行的耗时一览：
机器0: 16
机器1: 14
机器2: 6
机器3: 5 2
机器4: 4 3
运行截图
#include <iostream>
using namespace std;
void schedule(int m, int n, int t[]) {
int i, j, k, max = 0;//i表示机器编号，j表示任务，max表示机器最大运行时间
int d[100], s[100][100], count[100];
for (i = 0; i < m; i++) {//循环设置s数组和d数组
d[i] = 0;
for (j = 0; j < n; j++) {
s[i][j] = -1;//-1代表不执行任何任务，不与0号任务混淆
}
}
/*机器数大于任务数*/
if (m > n) {
cout << "完成所有任务需要的时间：" << t[0] << endl;
for (i = 0; i < m; i++) { // 循环输出机器执行的耗时
s[i][0] = i;// 判断是否有任务运行
d[i] += t[i];//运行时间
}
cout << "各个机器执行的耗时一览：" << endl;
for (i = 0; i < m; i++) {
if (i + 1 > n) {
cout << "机器" << i << ":没有任务运行！" << endl;
}
else {
cout << "机器" << i << ":" << t[i] << endl;
}
}
}
/*任务数大于机器数*/
else {//分配前m个任务，必然是每个机器先分别接受1个任务
for (i = 0; i < m; i++) {
s[i][0] = i;
d[i] += t[i];//累计运行时间
count[i] = 1;//计数
}
/*判断哪个机器任务耗时最少，让其接受任务，尽可能地并行、平均分配任务，使得每台机器最后的运行时间接近*/
for (i = m; i < n; i++) {
int min = d[0];
k = 0;
for (j = 1; j < m; j++) {//确定空闲机器，实质是在求当期任务总时间最少的机器
if (min > d[j]) {
min = d[j];
k = j;//机器k空闲
}
}
s[k][count[k]] = i;//在机器k的执行队列添加第i号任务
count[k] += 1;//机器k的任务数+1
d[k] += t[i];//机器k的任务执行时间+t[i]，也就是+第i号任务的耗时
}
for (i = 0; i < m; i++) {//确定完成所有任务需要的时间，实质是求分配完所有任务之后耗时最多的机器的运行时间
if (max < d[i]) {
max = d[i];
}
}
cout << "完成所有任务需要的时间：" << max << endl;
cout << "各个机器执行的耗时一览：" << endl;
for (i = 0; i < m; i++) {
cout << "机器" << i << ":";
for (j = 0; j < n; j++) {
if (s[i][j] == -1) {
break;
}
cout << t[s[i][j]] << "\t";
}
cout << endl;
}
}
}
int main() {
int num_t, num_mach;//任务数，机器数
cout << "请输入机器数num_mach：";
cin >> num_mach;
cout << "请输入任务数num_t：";
cin >> num_t;
int* time = new int[num_t];//使用动态内存分配声明时间数组来表示各个任务的执行所需时间
cout << "请输入任务所需执行时间（从大到小）：";
for (int i = 0; i < num_t; i++) {
cin >> time[i];
}
schedule(num_mach, num_t, time);
delete[] time; // 释放动态分配的内存
return 0;
}