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