最優(yōu)流水作業(yè)調(diào)度問題

1、最優(yōu)流水作業(yè)調(diào)度問題摘要本文給出了雙機(jī)流水作業(yè)調(diào)度的Johnson算法，并結(jié)合POJ上的一道題目詳述了該算法 的具體編程實(shí)現(xiàn)和應(yīng)用。關(guān)鍵詞：雙機(jī)流水作業(yè)調(diào)度Johnson算法正文流水作業(yè)是并行處理技術(shù)領(lǐng)域的一項(xiàng)關(guān)鍵技術(shù)，它是以專業(yè)化為基礎(chǔ)，將不同處理對(duì)彖的 同一施工工序交給專業(yè)處理部件執(zhí)行，各處理部件在統(tǒng)一計(jì)劃安排卜，依次在各個(gè)作業(yè)面上完 成指定的操作。流水作業(yè)調(diào)度問題是一個(gè)非常巫要的問題，其直接關(guān)系到計(jì)算機(jī)處理器的工 作效率。然而由于牽扯到數(shù)據(jù)相關(guān)、資源相關(guān)、控制用關(guān)等許多問題，最優(yōu)流水作業(yè)調(diào)度問 題處理起來非常復(fù)雜。已經(jīng)證明，當(dāng)機(jī)器數(shù)（或稱工序數(shù)）大于等于3時(shí)，流水作業(yè)調(diào)度問 題是一個(gè)NP

2、-hard問題（e.g分布式任務(wù)調(diào)度）。粗糙地說，即該問題至少在目前基本上沒有 可能找到多項(xiàng)式時(shí)間的算法。只刈當(dāng)機(jī)器數(shù)為2時(shí)，該問題町有多項(xiàng)式時(shí)間的算法（機(jī)器數(shù) 為1時(shí)該問題是平凡的）。我們先給出流水作業(yè)調(diào)度的定義：設(shè)有n個(gè)作業(yè)，每一個(gè)作業(yè)i均被分解為m項(xiàng)任務(wù)：TiDTi2,. ,1 （1 < i < n,故 共有n x m個(gè)任務(wù)），要把這些任務(wù)安排到m臺(tái)機(jī)器上進(jìn)行加工。如果任務(wù)的安排滿足卜列 3個(gè)條件，則稱該安排為流水作業(yè)調(diào)度：1. 毎個(gè)作業(yè)i的第j項(xiàng)任務(wù)舟（1< i<n,l < j< m）只能安排在機(jī)器耳上進(jìn)行加工；2. 作業(yè)i的第j項(xiàng)任務(wù)TM （1 &

3、lt; i < n, 2 < j < m）的開始加工時(shí)間均安排在第j - 1項(xiàng)任務(wù) Tij"加工完畢之后，任何一個(gè)作業(yè)的任務(wù)必須依次完成，前一項(xiàng)任務(wù)完成之后才能開 始著手下項(xiàng)任勢(shì)；3. 任何一臺(tái)機(jī)器在任何一個(gè)時(shí)刻最多只能承擔(dān)一項(xiàng)任務(wù)。最優(yōu)流水作業(yè)調(diào)度是指：設(shè)任務(wù)T”在機(jī)器耳上進(jìn)行加工需要的時(shí)間為可。如果所有的5 （l<i<n,l<j<m）均 己給岀，要找出一種安排任務(wù)的方法，使得完成這n個(gè)作業(yè)的加工時(shí)間為最少。這個(gè) 安排稱之為最優(yōu)流水作業(yè)調(diào)度。前面己經(jīng)說過，卅m > 3時(shí)該問題是NP問題，這里我們只給出m = 2時(shí)時(shí)間復(fù)雜度在多 項(xiàng)式以

4、內(nèi)的Johnson算法。求解流水作業(yè)調(diào)度問題的Johnson算法具體描述如下：1）設(shè)減i和bi （0 < i <町分別為作業(yè)i在兩臺(tái)設(shè)備上的處理時(shí)間。建立由三元組（作業(yè) 號(hào)，處理時(shí)間，設(shè)備號(hào)）組成的三元組表d°其中，處理時(shí)間是指每個(gè)作業(yè)所包含的兩 個(gè)任務(wù)中時(shí)間較少的處理時(shí)間。設(shè)n = 4. (a0,apa2,a3) = (3A8,10)>ftl(b0,bpb2lb3) = (6,2,9,15)的作業(yè) 0 的三元組為 (0,3,0),作業(yè)1的三元組為(1,2,1)。如圖(打所示。2) 對(duì)三元組表按處理時(shí)間排序，得到排序后的三元組表d。如圖(b)所示。3) 對(duì)1元組表的

5、每一項(xiàng)di(0 M i V n),從左右兩端生成最優(yōu)作業(yè)排列cj(0 < j < n), cj 是作業(yè)號(hào)。如果di設(shè)備號(hào)為1,則將作業(yè)i置于c的左端末尾，否則置于c的右端 末尾。如圖(c)所示，由兩端向中間存放。a)三元組表作業(yè)號(hào)處理時(shí)間設(shè)備號(hào)0301212803100b)按處理時(shí)間排序作業(yè)號(hào)處理時(shí)間設(shè)備號(hào)121002803100c)瑕優(yōu)作業(yè)排列(02 3,1) d)最優(yōu)調(diào)度方案pl38104P269152該算法是如此經(jīng)典以至于ACM界己經(jīng)有該算法的題目.卜面是北k PKU P0J第2751題 Saving Endeavour俄校的BOJ上也有，不過是從POJ上照搬過來的)：有2臺(tái)

6、機(jī)器，n件任務(wù)，必須先在S1上做，再在S2上做。任務(wù)之間先做后做任意。求 最早的完工時(shí)間。雙機(jī)調(diào)度問題Johnson算法簡析：1) 把作業(yè)按工序加工時(shí)間分成兩個(gè)子集，第一個(gè)集介中在S1上做的時(shí)間比在S2上少，其 它的作業(yè)放到第二個(gè)集合。先完成第一個(gè)集合里面的作業(yè)，再完成第二個(gè)集合里的作業(yè)。2) 對(duì)于第一個(gè)集合，其中的作業(yè)順序是按在SI I：的時(shí)間的不減排列：對(duì)于第二個(gè)集合， 其中的作業(yè)順序是按在S2上的時(shí)間的不增排列。Johnson算法的時(shí)間取決于對(duì)作業(yè)集合的排序,Wilt,在繪懷情況卜算法的時(shí)間復(fù)雜度 為O(nlogn),所需的空間復(fù)雜度為0(n)。c語言代碼如下：#include <

7、stdio. h>#include <memory. h>#includealgorithm using namespace std;const int MAXN=10005;struct TNodeint si, s2;wsMAXN;int topf, tops;int n;bool operator< (TNode x. TNode y)if (x. sl<x s2&&y sl>=y. s2) rrturn true;if (x. sl<x s2&&y sl<y s2) return x. sl<ysl; if (x. sl>=x s2&&y. sl>= y s2) ret urn x s2> y s2; return false;)int max(int x,int y)return x>y?x：y;void Work 0sort (ws. ws+n);int i, tl二0»t2二0;for (i=0;i<n;i+)11+=ws. si;t2 =max(tlt t2)+ws. s2;pr intf (/z%dnz t2);void ReadOint i;whi