作业车间调度问题C++

作业车间调度问题是一个经典的组合优化问题，主要是解决在多个作业需要在多个机器上进行处理时，如何安排作业的顺序和分配机器的问题，以最小化完成所有作业的时间。

在C++中，可以使用贪心算法、动态规划等算法来解决作业车间调度问题。以下是一个使用贪心算法的C++示例代码：

#include <iostream>
#include <algorithm>
using namespace std;

// 定义作业结构体
struct Job {
    int id; // 作业编号
    int machine; // 机器编号
    int time; // 作业处理时间
};

// 按照作业处理时间从小到大排序
bool cmp(Job a, Job b) {
    return a.time < b.time;
}

// 计算作业完成时间
int calcFinishTime(Job jobs[], int n) {
    int finishTime[n];
    int maxTime = 0;
    for (int i = 0; i < n; i++) {
        int machine = jobs[i].machine;
        int time = jobs[i].time;
        if (i == 0) {
            finishTime[i] = time;
        } else {
            finishTime[i] = finishTime[i-1] + time;
        }
        maxTime = max(maxTime, finishTime[i]);
    }
    return maxTime;
}

// 贪心算法解决作业车间调度问题
int scheduleJobs(Job jobs[], int n, int m) {
    sort(jobs, jobs+n, cmp); // 按照作业处理时间排序
    int machineTime[m] = {0}; // 记录每个机器的可用时间
    for (int i = 0; i < n; i++) {
        int machine = jobs[i].machine;
        int time = jobs[i].time;
        jobs[i].id = i + 1; // 给作业编号
        machineTime[machine] += time; // 更新机器可用时间
    }
    sort(jobs, jobs+n, cmp); // 按照作业处理时间排序
    return calcFinishTime(jobs, n); // 计算作业完成时间
}

int main() {
    int n = 5; // 作业数量
    int m = 3; // 机器数量
    Job jobs[] = {{0, 0, 2}, {0, 1, 4}, {0, 2, 3}, {0, 1, 1}, {0, 2, 4}}; // 作业列表
    int finishTime = scheduleJobs(jobs, n, m); // 计算作业完成时间
    cout << "最短完成时间：" << finishTime << endl;
    return 0;
}

该示例代码中，先按照作业处理时间从小到大排序，然后根据贪心算法，将作业分配到可用时间最短的机器上处理。最后计算所有作业完成时间，输出最短完成时间。