多机调度问题分析
问题描述
在多机调度问题中，我们有 n 个独立的作业和 m 个相同的机器。每个作业 i 需要处理时间 ti。我们的目标是找到一个调度方案，使得所有作业尽可能快地完成。
贪心策略
- 最长处理时间优先：优先分配处理时间最长的作业到最先可用的机器上。
情况分类
A: n < m
在这种情况下，每个作业可以独立地分配给一个机器，因为有足够的机器来处理所有作业。
B: n > m
当作业数超过机器数时，我们需要更智能的调度策略。以下是一个具体的例子：
示例
设有7个独立作业 {1, 2, 3, 4, 5, 6, 7} 由3台机器 {M1, M2, M3} 加工处理，各作业所需的处理时间分别为 {2, 14, 4, 16, 6, 5, 3}。
贪心算法步骤
-
作业排序：首先，将作业按处理时间降序排序。
-
初始分配：将排序后的前
m个作业分配给m台机器。 -
剩余作业分配：对于剩余的作业，将它们分配给当前完成时间最短的机器。
-
计算完成时间：最后，找出所有机器中完成时间最长的机器，该时间即为最短完成时间。
贪心策略
采用贪心策略，优先处理花费时间长的任务。具体步骤如下：
- 作业排序：将作业按处理时间降序排序，确保最长的作业最先被考虑。
- 分配作业：将排序后的作业依次分配给最先空闲的机器。
- 计算完成时间：通过比较各台机器的占用时间，找出最大值，即为最短完成时间。
步骤
-
作业排序：
-
作业分配：
- 机器 M1 分配作业 4，时间为16
- 机器 M2 分配作业 2，时间为14
- 机器 M3 分配作业 5，时间为6
- 在时间为6时，机器 M3 先结束，此时剩余任务里时间最长的是任务6，时间为5，选择任务6
- 在时间为11时，机器 M3 先结束，此时剩余任务里时间最长的是任务3，时间为4，选择任务6
- 在时间为14时，机器 M2 先结束，此时剩余任务里时间最长的是任务7，时间为3，选择任务7
- 在时间为15时，机器 M3 先结束，此时剩余任务里时间最长的是任务1，时间为2，选择任务1
-
计算完成时间：比较各台机器的占用时间，找出最大值为17。
代码：
#include<stdio.h> // 包含标准输入输出库，用于执行输入输出操作。
#define SIZE 100 // 定义一个宏SIZE，表示数组的最大大小。
// 函数声明，用于获取数组中的最小值。
int getmin(int a[], int n) {
int min=0, i; // 初始化最小值索引为0，声明循环变量i。
for(i = 0; i < n; i++) { // 遍历数组。
if(a[i] < a[min]) // 如果当前元素小于已知最小值。
min = i; // 更新最小值索引。
}
return min; // 返回最小值的索引。
}
// 函数声明，用于获取数组中的最大值。
int getmax(int a[], int n) {
int max, i; // 声明最大值索引max，初始化为第一个元素的索引。
a[max] = a[0]; // 将数组的第一个元素赋值给max。
for(i = 0; i < n; i++) { // 遍历数组。
if(a[i] > a[max]) // 如果当前元素大于已知最大值。
max = i; // 更新最大值索引。
}
return max; // 返回最大值的索引。
}
int main() {
int m, n, a[SIZE]; // 声明机器数m，作业数n，以及大小为SIZE的作业时间数组a。
printf("请输入有几台机器："); // 提示用户输入机器数。
scanf("%d", &m); // 读取用户输入的机器数。
printf("请输入有几个作业："); // 提示用户输入作业数。
scanf("%d", &n); // 读取用户输入的作业数。
printf("请分别写出："); // 提示用户输入每个作业的时间。
for(int i = 0; i < n; i++) { // 循环读取每个作业的时间。
scanf("%d", &a[i]); // 读取用户输入的作业时间。
}
// 冒泡排序，将作业时间从小到大排序。
for(int i=0; i<n; i++) {
for(int j=i; j<n; j++) { // 内层循环进行相邻元素的比较。
if(a[i] > a[j]) { // 如果前一个元素大于后一个元素。
int tmp = a[j]; // 临时变量存储后一个元素的值。
a[j] = a[i]; // 将前一个元素的值赋给后一个元素。
a[i] = tmp; // 将临时变量的值赋给前一个元素。
}
}
}
// 将排序后的数组最大值（即最长作业时间）分配给m台机器。
int w[SIZE]; // 声明一个数组w，用于存储每台机器的作业时间。
for(int i=0; i<m; i++) {
w[i] = a[n-i-1]; // 将排序后的数组的最后m个元素（最长的作业）分配给机器。
}
// 将剩余的作业时间分配给机器，使得完成时间最短。
for(int j=n-m-1; j>=0; j--) {
int t = getmin(w,m); // 找到当前机器中作业时间最短的机器。
w[t] += a[j]; // 将当前作业时间加到该机器上。
}
// 计算并输出最短完成时间。
int min = w[getmax(w,m)]; // 找到所有机器中作业时间最长的机器的时间。
printf("最短时间为:%d", min); // 输出最短完成时间。
return 0; // 程序结束。
}
运行截图：
