C++程序-流水作業(yè)調(diào)度

1、一、 問題描述給定n個作業(yè)，每個作業(yè)有兩道工序，分別在兩臺機(jī)器上處理。一臺機(jī)器一次只能處理一道工序，并且一道工序一旦開始就必須進(jìn)行下去直到完成。一個作業(yè)只有在機(jī)器1上的處理完成以后才能由機(jī)器2處理。假設(shè)已知作業(yè)i在機(jī)器j上需要的處理時間為ti,j。流水作業(yè)調(diào)度問題就是要求確定一個作業(yè)的處理順序使得盡快完成這n個作業(yè)。二、 算法分析n個作業(yè)1,2,n要在由2臺機(jī)器和組成的流水線上完成加工。每個作業(yè)加工的順序都是先在上加工，然后在上加工。和加工作業(yè)所需要的時間分別為ti,1和ti,2, .流水作業(yè)調(diào)度問題要求確定這n個作業(yè)的最優(yōu)加工順序，使得從第一個作業(yè)在機(jī)器上開始加工，到最后一個作業(yè)在機(jī)器上加工

2、完成所需的時間最少。從直觀上我們可以看到，一個最優(yōu)調(diào)度應(yīng)使機(jī)器沒有空閑時間，且機(jī)器的空閑時間是最少。在一般情況下，機(jī)器上會有機(jī)器空閑和作業(yè)積壓兩種情況。設(shè)全部作業(yè)的集合為。是的作業(yè)子集。在一般情況下，機(jī)器開始加工中作業(yè)時，機(jī)器還在加工其他作業(yè)，要等時間t后才能利用。將這種情況下完成中作業(yè)所需的最短時間計(jì)為。流水作業(yè)調(diào)度問題的最優(yōu)解為。1. 證明流水作業(yè)調(diào)度問題具有最優(yōu)子結(jié)構(gòu)設(shè)a是所給n個流水作業(yè)的一個最優(yōu)調(diào)度，它所需要的加工時間為。其中，是在機(jī)器的等待時間為時，安排作業(yè)所需的時間。記，則我們可以得到。事實(shí)上，有T的定義可知.若，設(shè)是作業(yè)集在機(jī)器的等待時間為情況下的一個最優(yōu)調(diào)度。則是的一個調(diào)度且

3、該調(diào)度所需的時間。這與a是N的一個最優(yōu)調(diào)度矛盾，所以。從而。這就是證明了流水作業(yè)調(diào)度問題具有最優(yōu)子結(jié)構(gòu)的性質(zhì)。2. 建立遞歸式計(jì)算最優(yōu)解由流水作業(yè)調(diào)度問題的最優(yōu)子結(jié)構(gòu)的性質(zhì)我們可以得到，。推廣到更一般的情形，我們便有：。其中，這一項(xiàng)是由于機(jī)器上，作業(yè)需在時間之后才能開工。因此，在機(jī)器上完成作業(yè)之后，在機(jī)器上還需時間才能完成對作業(yè)的加工。按照上面所敘述的遞歸式，可以設(shè)計(jì)出解決流水作業(yè)調(diào)度問題的動態(tài)規(guī)劃算法。通過對遞歸式的分析，算法可以得到進(jìn)一步的改進(jìn)。3. 流水調(diào)度問題的Johnson法則 設(shè)a是作業(yè)集S在機(jī)器的等待時間為t時的任意一個最優(yōu)調(diào)度。如果在調(diào)度中，安排在最前面的兩個作業(yè)分別為i和j，

4、即。則由動態(tài)規(guī)劃的遞歸式可以得到：其中， 如果作業(yè)i和j滿足，則稱作業(yè)i和j滿足Johnson不等式。如果作業(yè)i和j不滿足Johnson不等式，則交換作業(yè)i和j的加工次序后，作業(yè)i和j滿足Johnson不等式。 在作業(yè)集S當(dāng)機(jī)器的等待時間為t時的調(diào)度a中，交換作業(yè)i和作業(yè)j的加工次序，得到的作業(yè)集S的另一個調(diào)度a，它所需要的加工時間為 。其中， 當(dāng)作業(yè)i和j滿足Johnson不等式時，我們有從而，由此可得，因此任意t有從而，。由此可見。 換句話說，當(dāng)作業(yè)i和作業(yè)j不滿足Johnson不等式時，交換它們的加工順序后，作業(yè)i和作業(yè)j就滿足Johnson不等式了，且不增加加工時間。由此可得，對于流水

5、作業(yè)調(diào)度問題，必存在一個最優(yōu)的調(diào)度a，使得作業(yè)和滿足Johnson不等式：，稱這樣的調(diào)度a為滿足Johnson法則的調(diào)度。 進(jìn)一步可以證明，調(diào)度a滿足Johnson法則當(dāng)且僅當(dāng)對任意的i和j都有i<j時有。由此可知，任意兩個滿足Johnson法則的調(diào)度均為最優(yōu)調(diào)度。至此，我們將流水調(diào)度問題轉(zhuǎn)化為求滿足Johnson法則的調(diào)度問題。4. 算法的描述從上面的分析可知，流水作業(yè)調(diào)度問題一定存在滿足Johnson法則的最優(yōu)調(diào)度，且容易由下面的算法確定。流水作業(yè)調(diào)度問題的Johnson算法：（1） 令；（2） 將中作業(yè)依的非減序排列；將中作業(yè)依的非增序排列；（3） 作業(yè)接種作業(yè)構(gòu)成滿足Johnso

6、n法則的最優(yōu)調(diào)度。具體的代碼在文件夾流水作業(yè)調(diào)度動態(tài)規(guī)劃法文件夾中。三、 時空效率分析 算法FlowJob的主要計(jì)算時間花在對作業(yè)集的排序上。在這里，我們使用冒泡排序法(BubbleSort)，因此，在最壞情況下算法FlowJob所需要的計(jì)算時間為。所需要的空閑顯然是。/ FlowOperation.h#ifndef FLOWOPERATION_H#define FLOWOPERATION_Hclass FlowOperationpublic:FlowOperation();FlowOperation();void run(); / 運(yùn)行接口private:int number; / 流水作業(yè)

7、個數(shù)int numberB; / 記錄N1的個數(shù)int numberC; / 記錄N1的個數(shù)int *a; / 存儲流水作業(yè)時間int *b; / N1（Ai<Bi）int *c; / N2（Ai>=Bi）bool input(); / 輸入接口bool sort(); / X=0 or X=1 快速排序 目的是滿足Johnson 不等式 min(Bi,Aj)min(Bj,Ai) 任意 jibool sortB(int *b,int i,int j,int X); / X=0;bool sortC(int *c,int i,int j,int X); / X=1;void outp

8、ut(); / 輸出計(jì)算的最優(yōu)調(diào)度所用的時間;#endif/ FlowOperation.cpp#include <iostream>using std:endl;using std:ios;using std:cout;#include <fstream>using std:fstream;using std:ifstream;using std:ofstream;#include <cstdlib>/using std:exit;#include "FlowOperation.h"#define N 50 / 預(yù)定義有50個作業(yè) 根據(jù)

9、實(shí)際情況可作調(diào)整ifstream inputFile("input.txt",ios:in);ofstream outputFile("output.txt",ios:out);FlowOperation:FlowOperation() / 構(gòu)造函數(shù)number=0;numberB=0;numberC=0;a=new int *N;b=new int *N;c=new int *N;for (int i=0;i<N;i+)ai=new int 2;bi=new int 2;ci=new int 2;FlowOperation:FlowOperati

10、on() / 析構(gòu)函數(shù)for (int i=0;i<2;i+)delete ai;delete bi;delete ci;delete a;delete b;delete c;bool FlowOperation:input() / 輸入inputFile>>number;outputFile<<number<<endl;cout<<number<<endl;for (int j=0;j<2;j+) / 讀取數(shù)據(jù) 并導(dǎo)入到output.txt文件中for (int i=0;i<number;i+)inputFile&

11、gt;>aij;outputFile<<aij<<" "cout<<aij<<" "outputFile<<endl;cout<<endl;outputFile<<endl;cout<<endl;for (int i=0;i<number;i+) / 分類 判斷 ai 與 bi 的關(guān)系 即 ai0 與 ai1的大小關(guān)系 if (ai0<ai1) / 提取滿足ai<bi的時間事件 在機(jī)器M1上的工作時間 小于M2上的工作時間 存儲在數(shù)組b

12、中bnumberB0=ai0;bnumberB1=ai1;numberB+;else / 提取滿足ai>=bi的時間事件 在機(jī)器M1上的工作時間 小于M2上的工作時間 存儲在數(shù)組c中cnumberC0=ai0;cnumberC1=ai1;numberC+;cout<<"numberB="<<numberB<<endl;for (int k=0;k<2;k+)for (int i=0;i<numberB;i+)cout<<bik<<" "cout<<endl;cout

13、<<endl;cout<<"numberC="<<numberC<<endl;for ( k=0;k<2;k+)for (int i=0;i<numberC;i+)cout<<cik<<" "cout<<endl;cout<<endl;if (a!=NULL)if (b!=NULL) | (c!=NULL)return true;return false;return false;bool FlowOperation:sort()if (sortB

14、(b,0,numberB-1,0) / 判斷是否一對數(shù)組b 排好序if (sortC(c,0,numberC-1,1) / 判斷是否一對數(shù)組c 排好序return true;return false;return true;bool FlowOperation:sortB(int *b,int i,int j,int X) / 升序排序if (i<j)int left=i;int right=j;j+;/ 目的是使用 -jint pivot=biX;while (i<j)while(i<j) / 從左邊尋找第一個大于 pivot 的數(shù) 不適用等號if (b+iX<piv

15、ot)continue;break;while(j>i) / 從右邊尋找第一個小于 pivot 的數(shù) 不適用等號 if (b-jX>pivot)continue;break;if (i<j)int t;t=biX;biX=bjX;bjX=t;int Y=(X+1)%2;t=biY;biY=bjY;bjY=t;int t;t=bleftX;bleftX=bjX;bjX=t;int Y=(X+1)%2;t=bleftY;bleftY=bjY;bjY=t;sortB(b,left,j-1,X);sortB(b,j+1,right,X);return true;bool FlowOp

16、eration:sortC(int *c,int i,int j,int X) / 降序排序if (i<j)int left=i;int right=j;j+;/ 目的是使用 -jint pivot=ciX;while (i<j)while(i<j) / 從左邊尋找第一個小于 pivot 的數(shù) 不適用等號 if (c+iX>pivot)continue;break;while(j>i) / 從右邊尋找第一個大于 pivot 的數(shù) 不適用等號 if (c-jX<pivot)continue;break;if (i<j)int t;t=ciX;ciX=cj

17、X;cjX=t;int Y=(X+1)%2;t=ciY;ciY=cjY;cjY=t;int t;t=cleftX;cleftX=cjX;cjX=t;int Y=(X+1)%2;t=cleftY;cleftY=cjY;cjY=t;sortC(c,left,j-1,X);sortC(c,j+1,right,X);return true;void FlowOperation:run() / 運(yùn)行接口if (input() / 調(diào)用并判斷 是否完成輸入、和劃分if (sort() / 判斷是否已排好序output(); / 調(diào)用outpu()函數(shù) 實(shí)現(xiàn)導(dǎo)入、輸出void FlowOperation:o

18、utput() / 結(jié)果輸出for (int k=0;k<2;k+) / 把排序好的數(shù)據(jù)導(dǎo)入到output.txt文件中 以備查看 for (int i=0;i<numberB;i+)cout<<bik<<" "outputFile<<bik<<" "cout<<endl;outputFile<<endl;cout<<endl;outputFile<<endl;for ( k=0;k<2;k+) / 把排序好的數(shù)據(jù)導(dǎo)入到output.txt文件中 以備查看for (int i=0;i<numberC;i+)cout<<cik<<" "outputFile<<