当前位置：首页 > article >正文

博客打卡-求解流水线调度

article 2025/9/17 21:21:18

题目如下：

有n个作业（编号为1～n）要在由两台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi（1≤i≤n）。
流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。可以假定任何作业一旦开始加工，就不允许被中断，直到该作业被完成，即非优先调度。

输入格式:

第一行输入作业数n，接着的n行分别为在M1和M2加工各作业所需的时间。

输出格式:

先输出所需加工时间，再输入最优调度方案。

输入样例1:

输出样例1:

33
3 1 4 2

解题思路如下：

本题涉及的是两台机器流水作业调度问题，目的是找到一种作业加工顺序，使得从第一个作业在M1机器上开始加工到最后一个作业在M2机器上加工完成的总时间最短。为了解决这个问题，采用了回溯法（深度优先搜索DFS结合剪枝策略）来枚举所有可能的作业排列顺序，并计算每种顺序下的总加工时间以寻找最优解。

具体来说，算法首先读取每个作业在M1和M2上的加工时间，然后通过递归方式交换作业顺序模拟所有可能的排列情况。在搜索过程中，对于每一个作业排列，模拟其在两台机器上的加工过程：先计算该排列下M1机器的累计加工时间，再根据M1的完成时间确定M2机器的开始时间并累加相应的加工时间。如果当前排列下的总完成时间小于已知的最佳时间，则更新最佳时间和对应的作业顺序作为最优解。此外，采用剪枝技术，即一旦发现当前路径的累计完成时间已经超过目前最优解的时间，立即停止进一步搜索该分支，从而提高搜索效率。最终输出总最短完成时间和对应的最优作业调度方案。

具体代码如下：

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;const int MAX = 1000;
int n;                      // 作业数
int a[MAX];                 // M1加工时间
int b[MAX];                 // M2加工时间
int best_time = INT_MAX;    // 最优调度时间
int current_order[MAX];     // 当前调度顺序
int best_order[MAX];        // 最优调度顺序void dfs(int level, int time_m1, int time_m2) {if (level > n) {if (time_m2 < best_time) {best_time = time_m2;for (int i = 1; i <= n; i++) {best_order[i] = current_order[i];}}return;}for (int i = level; i <= n; i++) {swap(current_order[level], current_order[i]);int new_time_m1 = time_m1 + a[current_order[level]];int new_time_m2 = max(time_m2, new_time_m1) + b[current_order[level]];if (new_time_m2 < best_time) {dfs(level + 1, new_time_m1, new_time_m2);}swap(current_order[level], current_order[i]);}
}int main() {// 输入处理cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i] >> b[i];current_order[i] = i;}// 回溯搜索dfs(1, 0, 0);// 输出结果cout << best_time << endl;for (int i = 1; i <= n; i++) {cout << best_order[i] << " ";}cout << endl;return 0;
}

提交结果如下：