多机调度问题（Multiprocessor Scheduling Problem）是一个经典的组合优化问题，通常涉及到将一系列任务分配给多个处理器，目标是找到一种分配方式，使得完成所有任务所需的总时间（通常称为“Makespan”）最小。
以下是一个简单的C语言程序示例，用于解决多机调度问题。我们将使用一种近似算法——贪心算法（Greedy Algorithm）来解决这个问题。贪心算法在每一步选择当前最优的分配方案，通常不能保证找到全局最优解，但在实践中表现良好。
### 代码示例
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_TASKS 100
#define MAX_MACHINES 10
int tasks[MAX_TASKS]; // 任务的执行时间
int n_tasks; // 任务数量
int n_machines; // 机器数量
// 找到当前负载最小的机器
int findMinLoadMachine(int load[]) {
int minLoad = INT_MAX;
int minIndex = -1;
for (int i = 0; i < n_machines; i++) {
if (load[i] < minLoad) {
minLoad = load[i];
minIndex = i;
}
}
return minIndex;
}
// 使用贪心算法进行任务分配
void scheduleTasks() {
int load[MAX_MACHINES] = {0}; // 每个机器的当前负载
for (int i = 0; i < n_tasks; i++) {
int minIndex = findMinLoadMachine(load);
load[minIndex] += tasks[i];
}
// 输出每个机器的负载
printf("机器负载分配情况:\n");
for (int i = 0; i < n_machines; i++) {
printf("机器 %d: 负载 %d\n", i + 1, load[i]);
}
// 计算并输出Makespan
int makespan = 0;
for (int i = 0; i < n_machines; i++) {
if (load[i] > makespan) {
makespan = load[i];
}
}
printf("最小Makespan: %d\n", makespan);
}
int main() {
// 输入任务数量和机器数量
printf("输入任务数量: ");
scanf("%d", &n_tasks);
printf("输入机器数量: ");
scanf("%d", &n_machines);
// 输入每个任务的执行时间
printf("输入每个任务的执行时间: ");
for (int i = 0; i < n_tasks; i++) {
scanf("%d", &tasks[i]);
}
// 调度任务
scheduleTasks();
return 0;
}
```
### 代码说明：
1. **任务和机器**：`tasks` 数组存储每个任务的执行时间，`n_tasks` 是任务数量，`n_machines` 是机器数量。
2. **负载数组**：`load` 数组记录每个机器的当前负载。
3. **贪心算法**：`scheduleTasks` 函数使用贪心算法进行任务分配。每次选择当前负载最小的机器来分配任务。
4. **Makespan**：最终输出每个机器的负载情况，并计算和输出Makespan。
### 运行示例：
假设有5个任务，3台机器，任务的执行时间分别为 [3, 5, 7, 2, 10]，程序输出如下：
```
输入任务数量: 5
输入机器数量: 3
输入每个任务的执行时间: 3 5 7 2 10
机器负载分配情况:
机器 1: 负载 10
机器 2: 负载 9
机器 3: 负载 8
最小Makespan: 10
```
### 注意事项：
- 贪心算法通常能提供较好的近似解，但不保证是最优解。对于更复杂的情况，可以考虑使用动态规划、分支定界等更复杂的算法。
- 该程序假设任务数量和机器数量相对较小，以确保在合理时间内完成计算。对于更大规模的问题，可能需要使用更高效的算法或优化技术来解决。