6.3 最佳調(diào)度問題.doc

6.3 最佳調(diào)度問題算法設(shè)計思想：(1) 分支限界法求解假設(shè)有n個任務(wù)和k個機器，首先將問題轉(zhuǎn)化為一顆解空間樹：樹高為n，每一層對應(yīng)一個任務(wù)；每個節(jié)點代表一個調(diào)度狀態(tài)，記錄了每個機器完成任務(wù)的時間；每個節(jié)點有k個孩子，代表下一個任務(wù)可以由k個機器來完成。這樣，問題所求的最佳調(diào)度方案就是找所有機器完成時間最大值的最小值葉子節(jié)點。分支限界法的本質(zhì)是對解空間樹的BFS（廣度優(yōu)先）搜索，即將下一個任務(wù)由每個機器完成的調(diào)度狀態(tài)入隊，而后再依次將出隊的每一個狀態(tài)的子狀態(tài)入隊。為了實現(xiàn)剪枝，我們需要定義一個處理時間上界up，其含義為：當前剩下的任務(wù)全部由完成時間最早的機器處理之后，所有機器完成任務(wù)的最晚時間。這樣，在搜索過程中不斷縮小up，并判斷當前狀態(tài)的最晚完成時間，一旦大于up，說明該支路沒有發(fā)展前景，進行剪枝。另外，為了使up正確地指示上界，需要首先對任務(wù)按照完成時間降序排序，并且預(yù)處理得到剩下的后m項任務(wù)的完成時間，避免在搜索過程中重復(fù)計算。(2) 采用優(yōu)先隊列容器在進行BFS搜索時，需要用隊列來存儲解空間樹的各個節(jié)點，即當前的調(diào)度狀態(tài)。該算法采用函數(shù)庫提供的特殊容器：優(yōu)先隊列容器priority_queue（包含在庫queue中），并且自己定義了優(yōu)先隊列容器所需的對象比較優(yōu)先權(quán)bool operator()const為調(diào)度狀態(tài)中最大機器完成時間，使隊列每次出隊的元素為最大完成時間最小的調(diào)度方案，實現(xiàn)了優(yōu)先隊列式的分支限界法。(3) 搜索過程中動態(tài)申請釋放數(shù)組在BFS搜索過程中，解空間樹的每個狀態(tài)節(jié)點所記錄的各機器完成時間都采用動態(tài)數(shù)組記錄。這就要求我們不能僅靠構(gòu)造函數(shù)中那一次動態(tài)數(shù)組申請，而是需要對每個新的狀態(tài)申請一個動態(tài)數(shù)組。同樣，我們也不能只靠類對象的析構(gòu)函數(shù)來釋放一個動態(tài)數(shù)組，而需要在算法每次剪枝時釋放懸空的動態(tài)數(shù)組。我們用全局變量NUMBER（初始為0）對動態(tài)數(shù)組的申請（+）和釋放（-）進行了監(jiān)視，結(jié)果顯示（NUMBER=0）所有申請的動態(tài)數(shù)組都得到了釋放。（相應(yīng)代碼已刪去）算法的重點是處理時間上界up的定義，優(yōu)先隊列容器的使用，以及對動態(tài)數(shù)組的動態(tài)申請和釋放。除了上述三點之外，程序?qū)︳敯粜宰隽嗽鰪姡瑢Ψ欠ㄝ斎牒臀募e誤進行了檢測。程序設(shè)計代碼： /*頭文件 最佳調(diào)度問題.h*/#ifndef KNAP_H#define KNAP_H#include #include #include /包含優(yōu)先隊列容器using namespace std;class state/記錄調(diào)度狀態(tài)public:state(int k);/構(gòu)造函數(shù)，k是機器數(shù)state();/析構(gòu)函數(shù)int x;/任務(wù)序號int *time;/記錄各機器當前時間bool operator(const state &y)const; /定義優(yōu)先隊列所需的關(guān)系state& operator=(const state &y); /定義狀態(tài)賦值運算符=private:int n;/任務(wù)數(shù);class Task/任務(wù)類public:Task(char *in, char *out);/構(gòu)造函數(shù)Task();/析構(gòu)函數(shù)void Solve();/輸出結(jié)果到文件protected:void Sort();/將工作時間從大到小排序void Schedule();/分枝限界法采用優(yōu)先隊列求解void PreProcess(int *last);/預(yù)處理，后幾個工作的時間和int MinMachine(int* time);/當前狀態(tài)下處理最小時間機器int *Fresh(int* old);/更新狀態(tài)中的時間int Max(int* time);/返回最大時間void Print();/輸出結(jié)果private:int n, k;/任務(wù)數(shù)和機器數(shù)int *t;/完成任務(wù)的時間int *time;/記錄各機器工作時間int min;/最小工作時間ofstream fout;/輸出結(jié)果文件;#endif/*函數(shù)實現(xiàn)文件 最佳調(diào)度問題.cpp*/#include 最佳調(diào)度問題.hstate:state(int k)/構(gòu)造函數(shù)，k是機器數(shù)n = k;x = 0;/表示從選0個任務(wù)開始time = new intn+1;/需要記錄n個機器的當前時間for(int i = 1; i (const state &y)const/定義優(yōu)先隊列所需的關(guān)系int this_max = 0;int y_max = 0;for(int i = 1; i = n; i+)/找到該狀態(tài)機器最大處理時間if(this_max timei)this_max = timei;if(y_max y_max)/機器最大處理時間大于yreturn true;elsereturn false;state& state:operator=(const state &y) /定義狀態(tài)賦值運算符=x = y.x;n = y.n;time = y.time;return *this;Task:Task(char *in, char *out) : fout(out)ifstream fin(in);if( !fin )cerr 文件 in 無法打開! n k;/初始化任務(wù)數(shù)n和機器數(shù)kt = new intn+1;for(int i = 1; i ti;/初始化各任務(wù)所需處理時間fin.close();time = new intk+1;for(int i = 1; i = k; i+)timei = 0;/初始化各機器處理時間min = INT_MAX;/最小時間開始初始化為最大值if( !fout )cerr 文件 out 無法打開! endl;exit(1);Task:Task()if(fout)fout.close();if(t)delete t;if(time)delete time;void Task:Solve()Sort();/將工作時間從大到小排序Schedule();/分枝限界法采用優(yōu)先隊列求解Print();/輸出函數(shù)void Task:Sort()int temp;for(int i = 1; i n; i+)for(int j = i+1; j = n; j+)if(ti tj)temp = ti;ti = tj;tj = temp;void Task:Schedule()int *last;/存儲剩下工作時間的數(shù)組last = new intk;/元素為之后剩余工作時間和PreProcess(last);/預(yù)處理int up = last0;/處理時間上界，初始為總時間state temp(k);/輔助狀態(tài)，構(gòu)造k個機器/存儲狀態(tài)的優(yōu)先隊列容器，按照當前狀態(tài)機器最大完成時間升序排列priority_queuestate, vector, greater Queue;Queue.push(temp);int num;/任務(wù)序號int min_machine;/當前狀態(tài)處理時間最少的機器while(1)temp = Queue.top();/取隊頭元素if(temp.x = n)/處理結(jié)束break;Queue.pop();num = temp.x;for(int i = 1;i 1 & temp.timei = temp.timei-1)if(i = k)/需要釋放數(shù)組time內(nèi)存delete temp.time;continue;/同等剪枝if(Max(temp.time) up)if(i = k)/需要釋放數(shù)組time內(nèi)存delete temp.time;continue;/限界剪枝temp.timei += tnum+1;/加上下一個任務(wù)的時間min_machine = MinMachine(temp.time);temp.timemin_machine += lastnum+1;if(Max(temp.time) max)min = max;/找到最優(yōu)方案delete temp.time;void Task:PreProcess(int *last)for(int i = 0; i n; i+)/預(yù)處理last數(shù)組lasti = 0;for(int j = i+1; j = n; j+)lasti += tj;int Task:MinMachine(int* time)int min = INT_MAX;int min_machine;for(int i = 1; i = k; i+)if(timei min)min = timei;min_machine = i;return min_machine;int* Task:Fresh(int* old)int *temp;temp = new intk+1;for(int i = 1; i = k; i+)tempi = oldi;return temp;int Task:Max(int* time)int max = 0;for(int i = 1; i = k; i+)if(max timei)max = timei;return ma