一：題目

n個作業{1，2，…，n}要在由2臺機器M1和M2組成的流水線上完成加工。每個作業加工的順序都是先在M1上加工，然后在M2上加工。M1和M2加工作業i所需的時間分別為ai和bi。流水作業調度問題要求確定這n個作業的最優加工順序，使得從第一個作業在機器M1上開始加工，到最后一個作業在機器M2上加工完成所需的時間最少。

輸入格式:
第一行給出作業個數n(0<n<100)

第二行起的n行，每行兩個數ai和bi

輸出格式:
兩個數字，以空格分隔，分別表示M1機器運行結束的時間和M2機器運行結束的時間。

輸入樣例:

6 30 80 120 100 50 90 20 60 90 30 110 10

結尾無空行
輸出樣例:

420 430

二：思路

1.判斷動態規劃：
首先m1的加工結束時間就是所有的時間和，但m2的加工時間和最小值，
求解過程是跳躍性的 所以判定為動態規劃
2.這道題用到了johnson算法，我是拿個例子來理解的，
比如：假設再m1上的加工時間為a,在m2上的加工時間為b
如果作業i和作業j滿足min(aj,bi) > min (ai,bj) 則稱作業i和j
滿足johnson法則

i在m1和m2上的加工時間為 3,4
j在m1和m2上的加工時間為 6,7
min(4,6) > min(3,7)
則作業i和j滿足johnson法則

若先加工i
m2的結束時間 = 3+4+2+7 = 16
若先加工j
m2的結束時間 = 6+7+4 = 17

所以說johnson確定了加工的順序

3.那么在處理數據的時候我們看到了一對一的摸樣，但不能用map容器
因為數據當中有重復的部分，這時候我們完全可以用結構體數組來實現
同一個下標，但其可以含有多個值，java當中也可以創建一個對象來實現
但擔心java 的虛擬機可能會超時。。。

4.本題中的johnson的算法的舉例：



上面的例子是我理解時候看別人的例子，分享給大家

下面的例子：是本題的例子

三：上碼

前言注釋一下：1.這個題用完 Johnson的算法后，就基本上做完了，和前幾道動態規劃的題思路都不一樣

這個當中的排序 用的是重寫sort方法 利用結構體數組來處理數據（自認為本題唯一有成就感的地方）

/**思路：1.判斷動態規劃：首先m1的加工結束時間就是所有的時間和，但m2的加工時間和最小值，求解過程是跳躍性的 所以判定為動態規劃2.這道題用到了johnson算法，我是拿個例子來理解的，比如：假設再m1上的加工時間為a,在m2上的加工時間為b如果作業i和作業j滿足min(aj,bi) > min (ai,bj) 則稱作業i和j滿足johnson法則i在m1和m2上的加工時間為 3,4j在m1和m2上的加工時間為 6,7min(4,6) > min(3,7) 則作業i和j滿足johnson法則 若先加工im2的結束時間 = 3+4+2+7 = 16若先加工jm2的結束時間 = 6+7+4 = 17所以說johnson確定了加工的順序3.那么在處理數據的時候我們看到了一對一的摸樣，但不能用map容器因為數據當中有重復的部分，這時候我們完全可以用結構體數組來實現同一個下標，但其可以含有多個值，java當中也可以創建一個對象來實現但擔心java 的虛擬機可能會超時。。。 */ #include<bits/stdc++.h> using namespace std;struct Node{int number1; // 在m1上的加工時間int number2;// 在m2上的加工時間 };//N1集合當中ai的遞增排序 bool sort_N1(Node a,Node b){return a.number1 < b.number1; } //N2中按bi的降序排序 bool sort_N2(Node a,Node b){return a.number2 > b.number2; } int main(){int N;int a[101];int b[101];Node *stu1 = new Node[101];Node *stu2 = new Node[101]; Node *stu3 = new Node[101]; cin >> N; for(int i = 0; i < N; i++){cin >> a[i] >> b[i];}// for(int i = 0; i < N; i++){ // cout << b[i] << ' '; // }//開始處理數據在N1的集合當中是作業ai < bi(即在m2上的加工時間大于在m1上的加工時間)//N2上的集合是作業的(ai > bi) //還要注意的是在N1上是按照ai的遞增排序，在N2上是按照bi的遞減排序int k1 = 0,k2 = 0;for(int i = 0; i < N; i++){//集合N1上 if(a[i] < b[i]){stu1[k1].number1 = a[i];stu1[k1].number2 = b[i];k1++;}else{//集合N2上 stu2[k2].number1 = a[i];stu2[k2].number2 = b[i];k2++;}}// for(int i = 0; i < k1; i++){ // cout << stu1[i].number1 << ' ' << stu1[i].number2 << endl; // } //對N1集合進行排序（按ai的遞增排序） sort(stu1,stu1+k1,sort_N1);//對N2集合進行排序（按bi的遞減順序進行排序）sort(stu2,stu2+k2,sort_N2); //將N1和N2集合合并（N1在前，N2在后）int k3 = 0;for(int i = 0; i < k1; i++){stu3[k3].number1 = stu1[i].number1;stu3[k3].number2 = stu1[i].number2;k3++;} for(int i = 0; i < k2; i++){stu3[k3].number1 = stu2[i].number1;stu3[k3].number2 = stu2[i].number2;k3++; }//驗證數據 // for(int i = 0; i < k3; i++){ // cout << stu3[i].number1 << ' '; // }//計算時間m1,m2的結束時間int m1,m2;m1 = stu3[0].number1;//第一個工作在m1執行完的時間m2 = stu3[0].number2 + m1;//第一個工作的總體執行時間for(int i = 1; i < N; i++){m1 = m1 + stu3[i].number1;//第i個工作在m1上的執行時間if(m1 < m2){//說明m2上的工作還沒有完成 m2 = m2 + stu3[i].number2;//工作累積 }else if(m1 > m2){//說明m2需要等待，因為m1上的工作還未完成 m2 = m1 + stu3[i].number2; } } cout << m1 << ' ' << m2; } //20 30 50 120 90 110 //60 80 90 100 30 10

加油boy!! 睡覺了寶貝哈哈哈哈哈哈哈哈哈哈哈！

總結

以上是生活随笔為你收集整理的7-5 流水作业调度 (10 分)(思路+详解+johnson解析)Come Baby!!!!!!!!!!的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。