n個作業{1, 2, …, n}要在兩台機器上處理，每個作業必須先由機器1處理，然後再由機器2處理，機器1處理作業i所需時間為ai，機器2處理作業i所需時間為bi（1≤i≤n），批處理作業調度問題（batch-job scheduling problem）要求確定這n個作業的最優處理順序，使得從第1個作業在機器1上處理開始，到最後一個作業在機器2上處理結束所需時間最少。（備註：這個定義應該是“流水作業調度問題”的描述，“批處理作業調度問題”的一般關鍵字是“時間和”，不是“時間”，所以這項目應該是更改詞條名比較合適，改成“流水作業調度問題”。）
基本介紹
- 中文名：20ml、60ml和110ml三種為主
- 內容一：問題
- 內容二：想法
- 內容三：算法
想法,算法,算法分析,算法實現,
想法
顯然，批處理作業的一個最優調度應使機器1沒有空閒時間，且機器2的空閒時間最小。可以證明，存在一個最優作業調度使得在機器1和機器2上作業以相同次序完成。例如，有三個作業{1, 2, 3}，這三個作業在機器1上所需的處理時間為(2, 5, 4)，在機器2上所需的處理時間為(3, 2, 1)，則這三個作業存在6種可能的調度方案：{(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)}，相應的完成時間為{12, 13, 12, 14, 13, 16}，如圖8.8所示。顯然，最佳調度方案是(1, 2, 3)和(2, 1, 3)，最短完成時間為12。
設數組x[n]表示n個作業批處理的一種調度方案，其中x[k]表示第k個作業的編號，sum1[n]和sum2[n]保存在調度過程中機器1和機器2的當前完成時間，其中sum1[k]表示在安排第k個作業後機器1的當前完成時間，sum2[k]表示在安排第k個作業後機器2的當前完成時間，且根據下式進行更新：
sum1[k] = sum1[k-1] +作業x[k]在機器1的處理時間
sum2[k] = max(sum1[k], sum2[k-1] )+作業x[k]在機器2的處理時間
算法
設數組a[n]存儲n個作業在機器1上的處理時間，b[n]存儲n個作業在機器2上的處理時間，回溯法求解批處理調度問題的算法用偽代碼描述如下：
算法分析
對於批處理作業調度問題，由於要從n個作業的所有排列中找出具有最早完成時間的作業調度，所以，批處理作業調度問題的解空間是一棵排列樹，並且要搜尋整個解空間樹才能確定最優解，因此，其時間性能是O(n!)。相對於蠻力法求解批處理調度問題，由於在搜尋過程中利用了已得到的最短完成時間進行剪枝，所以，能夠提高搜尋速度。
算法實現
設數組a[n]存儲n個作業在機器1上的處理時間，數組b[n]存儲n個作業在機器2上的處理時間。數組x[n]存儲具體的作業調度，初始疊代時x[0]表示未安排作業，x[k]表示第k個作業的編號。數組sum1[n]存儲機器1的完成時間，sum2[n]存儲機器2的完成時間，初始疊代時sum1[0]和sum2[0]均為0，表示完成時間均為0，sum1[k]表示在安排第k個作業後機器1的當前完成時間，sum2[k]表示在安排第k個作業後機器2的當前完成時間。回溯法求解批處理作業調度問題的算法用C++語言描述如下：
int BatchJob(int a[ ], int b[ ], int n)
{
int i, k;
int x[10], sum1[10], sum2[10]; //假設最多9個作業
int bestTime = 1000; //假定最後完成時間不超過1000
for (i = 1; i <= n; i++) //初始化調度方案
{
x[i] = -1;
sum1[i] = 0; sum2[i] = 0;
}
sum1[0] = 0; sum2[0] = 0; //開始調度（初始疊代）時使用
k = 1; //調度第1個作業
while (k >= 1)
{
x[k] = x[k] + 1; //安排第k個作業，x[k]為作業編號
while (x[k] < n)
{
for (i = 1; i < k; i++) //檢測作業x[k]是否重複處理
if (x[i] == x[k]) break;
if (i == k) { //作業x[k]尚未處理
sum1[k] = sum1[k-1] + a[x[k]];
if (sum1[k] > sum2[k-1]) sum2[k] = sum1[k] + b[x[k]];
else sum2[k] = sum2[k-1] + b[x[k]];
if (sum2[k] < bestTime) break; //已超過目前最短時間，剪枝
else x[k] = x[k] + 1;
}
else x[k] = x[k] + 1; //作業x[k]已處理，嘗試下一個作業
}
if (x[k] < n && k < n)
k = k + 1; //安排下一個作業
else {
if (x[k] < n && k == n) //得到一個作業安排
if (bestTime > sum2[k]) {
bestTime = sum2[k];
cout<<"目前的最短作業安排是：";
for (int j = 1; j <= n; j++)
cout<<x[j] + 1<<" "; //下標從0開始，列印作業編號從1開始
cout<<"最短時間是："<<bestTime<<endl;
}
x[k] = -1; k = k - 1; //重置x[k]，回溯
}
}
return bestTime;
}
