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

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

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

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

4、即。則由動(dòng)態(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ī)器的等待時(shí)間為t時(shí)的調(diào)度a中，交換作業(yè)i和作業(yè)j的加工次序，得到的作業(yè)集S的另一個(gè)調(diào)度a，它所需要的加工時(shí)間為 。其中， 當(dāng)作業(yè)i和j滿足Johnson不等式時(shí)，我們有從而，由此可得，因此任意t有從而，。由此可見(jiàn)。 換句話說(shuō)，當(dāng)作業(yè)i和作業(yè)j不滿足Johnson不等式時(shí)，交換它們的加工順序后，作業(yè)i和作業(yè)j就滿足Johnson不等式了，且不增加加工時(shí)間。由此可得，對(duì)于流水

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

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

7、個(gè)數(shù)int numberB; / 記錄N1的個(gè)數(shù)int numberC; / 記錄N1的個(gè)數(shù)int *a; / 存儲(chǔ)流水作業(yè)時(shí)間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)度所用的時(shí)間;#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個(gè)作業(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的時(shí)間事件 在機(jī)器M1上的工作時(shí)間 小于M2上的工作時(shí)間 存儲(chǔ)在數(shù)組b

12、中bnumberB0=ai0;bnumberB1=ai1;numberB+;else / 提取滿足ai>=bi的時(shí)間事件 在機(jī)器M1上的工作時(shí)間 小于M2上的工作時(shí)間 存儲(chǔ)在數(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) / 判斷是否一對(duì)數(shù)組b 排好序if (sortC(c,0,numberC-1,1) / 判斷是否一對(duì)數(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) / 從左邊尋找第一個(gè)大于 pivot 的數(shù) 不適用等號(hào)if (b+iX<piv

15、ot)continue;break;while(j>i) / 從右邊尋找第一個(gè)小于 pivot 的數(shù) 不適用等號(hào) 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) / 從左邊尋找第一個(gè)小于 pivot 的數(shù) 不適用等號(hào) if (c+iX>pivot)continue;break;while(j>i) / 從右邊尋找第一個(gè)大于 pivot 的數(shù) 不適用等號(hào) 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<<