Johnson算法实现流水作业最优调度

1. 算法描述

令$N_1=\{i|a_i<b_i\}$, $N_2=\{i|a_i\ge b_i\}$;将$N_1$中的作业按照$a_i$的非降序排列，将$N_2$中的作业按照$b_i$的非升序排列；$N_1$中的作业拼接$N_2$中的作业构成$Johnson$算法的最优作业调度。

2. C/C++代码实现

/************************************************** *Johnson算法实现流水作业最优调度 ***************************************************/ #include<iostream> #include<algorithm> using namespace std; const int maxn = 1000; class JobType { public: int key; int index; bool job; bool operator < (const JobType& j)const { return key < j.key;//重载运算符<,以键值key为关键字排序 } }; int FlowShop(int n, int a[], int b[], int c[]) { JobType* d = new JobType[n]; for (int i = 0; i < n; i++) { d[i].key = a[i] < b[i] ? a[i] : b[i];//记录ai bi中最小值为key d[i].job = a[i] < b[i]; //ai < bi N1 = {i | ai < bi} N2 = {i | ai >= bi} d[i].index = i; } sort(d, d + n);//并不是简单的快速排序 可能还有堆排序等排序算法 根据数据的规模进行选择 int j = 0; int k = n - 1; for (int i = 0; i < n; i++) //因为最后的调度序列是 排序之后的{N1,N2} //前面排序之后N1是非降序 N2也是非降序 //因此在排序之后序列中遍历时 遇到job == 0的下标 主要从c[]最后下标开始 依次递减 if (d[i].job) // N1 i按照ai的非降序排列 c[j++] = d[i].index; else //N2 i按照bi的非升序排列 c[k--] = d[i].index; //输出调度序列 cout << "流水作业调度序列为:"; for (int i = 0; i < n; i++) cout << c[i] << " "; cout << endl; //计算最短的流水作业调度时间 j = a[c[0]]; //j记录工序ai完成的时间 k = j + b[c[0]]; //k记录工序bi完成的时间 for (int i = 1; i < n; i++) { j += a[c[i]]; //工序a进行到目前用的时间 k = j < k ? k + b[c[i]] : j + b[c[i]]; //工序a进行到i用的时间j 和 工序b进行到i-1用的时间k 作比较 /*若j > k, i-1作业的b工序已经结束了 但是i作业的a工序还没结束 此时b需要等待其结束 那么i作业的b工序完成时间为 k = j + bi*/ /*否则j <= k, i-1作业的b工序还没结束 i作业的a工序就已经结束 此时i作业的b工序则不需要等待直接进行即可 那么i作业的b工序完成时间为k = k + bi*/ } delete[]d; return k; } int main() { int n; cin >> n; int a[maxn], b[maxn], c[maxn]; for (int i = 0; i < n; i++) cin >> a[i] >> b[i]; int t = FlowShop(n, a, b, c); cout << "流水作业调度最短完成时间是:" << t << endl; return 0; } /* 5 2 5 4 2 3 3 6 1 1 7 */

3. 运行结果

5 2 5 4 2 3 3 6 1 1 7 流水作业调度序列为:4 0 2 1 3 流水作业调度最短完成时间是:19

4. 具体动态规划推导过程

具体推导过程