【文章內(nèi)容簡(jiǎn)介】 Y少了一個(gè)與 X不同的作業(yè)。 重復(fù)上述的轉(zhuǎn)換，可使 Y在 不減 效益值的情況下轉(zhuǎn)換成X。從而 X至少有和 Y一樣的效益值。所以 X也是最優(yōu)解。 證畢。 …….……….a…………… ……..………b…………… α ： β ： ta α =（ … x … z… ） α =（ … z … x … ） β =（ … y … x… ） β =（ … y … x … ） (a) x與 z交換前 (b) x與 z交換后 α =（ … y … x … ） α =（ … y … x … ） β =（ … x … z … ） β =（ … z … x … ） (c) x與 z交換前 (d) x與 z交換后 圖 61 使相同作業(yè)在相同時(shí)刻被調(diào)度 可行性判定 定理 6－ 3 X=（ x0,x1,…,x k）是 k個(gè)作業(yè)的集合， ?=（ ?0, ?1,…, ?k）是 X 的一種特定排列，它使得 d ?0≤ d?1≤…≤d ?k ，其中， d?j是作業(yè) ?j的時(shí)限。 X是一個(gè)可行解當(dāng)且僅當(dāng) X中的作業(yè)能夠按 ?次序調(diào)度而不會(huì)有作業(yè)超期。 方法一 ：枚舉法，檢驗(yàn) X中作業(yè)所有可能的排列，對(duì)于任一種次序排列的作業(yè)序列，判斷這些作業(yè)是否能夠在其期限前完成 ——若 X中有 k個(gè)作業(yè)，則將要檢查 k!個(gè)序列 判斷策略： 對(duì)于一個(gè)給定 作業(yè)處理序列 α＝ i1i2…i k,由于作業(yè) ij完成的最早時(shí)間 是 j，因此只要判斷出 α排列中的每個(gè)作業(yè)的期限有dij≥j ，就可得知 α是一個(gè)允許的調(diào)度序列，從而 X是一可行解。 反之，如果 α排列中有一個(gè)作業(yè)有 dij＜ j,則 α將是一個(gè)行不通的調(diào)度序列，因?yàn)橹辽僮鳂I(yè) ij不能在其期限之前完成。 方法二 ：檢查 X中作業(yè)的一個(gè) 特定序列 就可判斷 X的可行性：這一特定序列是按照 作業(yè)期限 的 非降次序 排列的作業(yè)序列 證明： ① 如果 X中的作業(yè)可以按照 α的次序而又不違反任何一個(gè)作業(yè)期限的情況來(lái)處理，則 X是一個(gè) 可行解 ② 現(xiàn)證 若 X是一個(gè)可行解， α是否代表一個(gè)可行的調(diào)度序列？ ∵ X是可行解 ∴ 必存在一可行的調(diào)度序列 β ＝ r1r2…r k，使得 drj≥ j, 1≤j≤k。 ★ 若 α ＝ β，則 α即是可行的調(diào)度序列。否則， ★ α ≠ β ，令 a是使得 ra≠ia的最小下標(biāo)（如下圖） α ＝ i1 i2 … ia … … ic … ik β ＝ r1 r2 … ra … rb … r k 設(shè) rb=ia。則有 ： b＞ a 且 dra≥drb 故，在 β中調(diào)換 ra與 rb，所得的新序列 γ＝ s1s2…sk的處理次序不違反任何一個(gè)期限，而 γ中位置 a及 a之前的作業(yè)均與 α相同。 重復(fù)上述過(guò)程，則可將 β轉(zhuǎn)換成 α且不違反任何一個(gè)期限，故 α是一個(gè)可行的調(diào)度序列 故定理得證。 作業(yè)排序貪心算法 定理 6－ 3提供了一種高效的可行解判定方法。使得在按最優(yōu)量度標(biāo)準(zhǔn)，即按作業(yè)收益的非增次序選擇下一個(gè)作業(yè)后，可以有效地判定是否可將該作業(yè)加入已生成的部分解向量 X。 【 程序 6－ 4】 帶時(shí)限的作業(yè)排序程序 int JS(int *d, int *x, int n) { //設(shè) p0?p1?? ?pn1 int k=0。 x[0]=0。 for (int j=1。jn。j++){ int r=k。 while (r=0 amp。amp。 d[x[r]]d[j] amp。amp。 d[x[r]]r+1)r。 if((r0||d[x[r]]=d[j]) amp。amp。 d[j]r+1){ for (int i=k。i=r+1。i) x[i+1]=x[i]。 x[r+1]=j。 k++。 } } return k。 } 一種改進(jìn)算法 本小節(jié)將介紹一種帶時(shí)限作業(yè)排序的快速算法 ，它采用不同于前者的可行解判定方法 ， 可使算法的時(shí)間從 ?(n2)減少到接近 O(n)。 例 6－ 3 設(shè) n=5個(gè)作業(yè) ， 作業(yè)的時(shí)限為 :(d0,d1,d2,d3,d4)=(2,2,1,3,3), 收益為 : (p0,p1,p2,p3,p4)=(20,15,10,5,1)。 【 程序 6－ 5】 使用并查集的帶時(shí)限作業(yè)排序 int FJS(int *d,int *x,int n) { UFSet s(n)。 int b,k=1,*f=new int[n+1]。 for (int i=0。i=n。i++) f[i]=i。 for (i=0。in。i++) { if(nd[i]) b=n。else b=d[i]。 int r=(b)。 if (f[r]) { x[++k]=i。 int t=(f[r]1)。 (t,r)。 f[r]=f[t]。 } } delete []f。 return k。 } 多機(jī)調(diào)度問(wèn)題 多機(jī)調(diào)度問(wèn)題 要求給出一種作業(yè)調(diào)度方案，使所給的 n個(gè)作業(yè)在盡可能短的時(shí)間內(nèi)由 m臺(tái)機(jī)器加工處理完成。 這個(gè)問(wèn)題是 NP完全問(wèn)題，到目前為止還沒(méi)有有效的解法。對(duì)于這一類問(wèn)題 ,用貪心選擇策略有時(shí)可以設(shè)計(jì)出較好的近似算法。 約定，每個(gè)作業(yè)均可在任何一臺(tái)機(jī)器上加工處理，但未完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。 采用 最長(zhǎng)處理時(shí)間作業(yè)優(yōu)先 的貪心選擇策略可以設(shè)計(jì)出解多機(jī)調(diào)度問(wèn)題的較好的近似算法。 按此策略，當(dāng) n≤m時(shí)，只要將機(jī)器 i的 [0, ti]時(shí)間區(qū)間分配給作業(yè) i即可，算法只需要 O(1)時(shí)間。 當(dāng) nm時(shí)，首先將 n個(gè)作業(yè)依其所需的處理時(shí)間從大到小排序。然后依此順序?qū)⒆鳂I(yè)分配給空閑的處理機(jī)。算法所需的計(jì)算時(shí)間為 O(nlogn)。 例如 ， 設(shè) 7個(gè)獨(dú)立作業(yè) {1,2,3,4,5,6,7}由3臺(tái)機(jī)器 M1， M2和 M3加工處理。各作業(yè)所需的處理時(shí)間分別為 {2,14,4,16,6,5,3}。按算法greedy產(chǎn)生的作業(yè)調(diào)度如下圖所示，所需的加工時(shí)間為 17。 問(wèn)題描述 兩路合并外排序算法通過(guò)反復(fù)執(zhí)行將兩個(gè)有序子文件合并成一個(gè)有序文件的操作 ， 最終將 n個(gè)長(zhǎng)度不等的有序子文件合并成一個(gè)有序文件 。 合并 n個(gè)有序子文件成為一個(gè)有序文件的合并過(guò)程可以有多種方式 ， 稱為 合并模式 。 在整個(gè)合并過(guò)程中 ， 需從外存讀寫的記錄數(shù)最少的合并方案稱為 最佳合并模式 （ optimal merge pattern） 。 最佳合并模式 例 6－ 4 設(shè)有 5個(gè)有序子文件 （ F1,F2,F3,F4,F5） ， 其長(zhǎng)度分別為 （ 20， 30， 30， 10， 5） 。 現(xiàn)通過(guò)兩兩合并將其合并成一個(gè)有序文件 。 帶權(quán)外路徑長(zhǎng)度 是針對(duì)擴(kuò)充二叉樹而言的 。 擴(kuò)充二叉樹 （ extended binary tree） 中除葉子結(jié)點(diǎn)外 ， 其余結(jié)點(diǎn)都必須有兩個(gè)孩子 。 擴(kuò)充二叉樹的帶權(quán)外路徑長(zhǎng)度 （ weighted external path length） 定義為： ???m1kkk lwW P L 貪心法求解 兩路合并最佳模式問(wèn)題的 最優(yōu)量度標(biāo)準(zhǔn) 為帶權(quán)外路徑長(zhǎng)度最小。 兩路合并最佳模式的貪心算法簡(jiǎn)述如下： 設(shè) W＝ {w0,w1 ,? ,wn－ 1}是 n個(gè)有序文件的長(zhǎng)度；以每個(gè)權(quán)值作為根結(jié)點(diǎn)值，構(gòu)造 n棵只有根的二叉樹； 選擇兩棵根結(jié)點(diǎn)權(quán)值最小的樹，作為左右子樹構(gòu)造一棵新二叉樹，新樹根的權(quán)值是兩棵子樹根的權(quán)值之和； 重