摘要 摘要 本文考慮了帶容量限制的平行機(jī)排序問題：給定m 個(gè)同型平行機(jī)( i d e n t i c a l m a c h i n e s ) ，限定每臺(tái)機(jī)器上最大的加工個(gè)數(shù)為給定m 個(gè)工件，每個(gè)工 件的加工時(shí)間記為如0 ，找出一個(gè)排序使其時(shí)間跨度( m a k e s p a n ) 最小而且滿足問 題所要求的容量限制 當(dāng)機(jī)器臺(tái)數(shù)為2 且容量限制不同時(shí)，則離線情況下我們提出了算法m l p t , 且證 明了該算法具有緊界5 3 更進(jìn)一步，在算法m l p t 的基礎(chǔ)上，我們將其稍加修改，記 為r l p t , 我們證明該改進(jìn)算法的界為3 2 在線情況下，我們證明若兩臺(tái)機(jī)器的容量 限制之差大于等于2 時(shí)，則任何合理的在線算法都不具有比2 更好的界然而若它們 的容量限制之差為0 或1 時(shí)，我們提出了一個(gè)在線算法( 記為b s ) ，并證明這種情況 下該算法具有界1 + 0 1 ，其中q = 聳 ，且該算法是最好算法 當(dāng)機(jī)器臺(tái)數(shù)為m 時(shí)，我們首先證明了當(dāng)容量限制不同時(shí)，任何在線算法的界至 少是_ m + 廣1 另外，當(dāng)機(jī)器的容量限制相同時(shí)，我們分析了l s 算法，并證明l s 算法的 界為_ = 2 m = - 8 r - 1 ，其中6 為_ t - 件安排完成后達(dá)到了容量限制的機(jī)器個(gè)數(shù) 關(guān)鍵詞：平行機(jī)排序容量限制在線算法 摘要 a b s t r a c t t h i sp a p e rc o n s i d e r sp a r a l l e lm a c h i n es c h e d u l i n gw i t hc a p a c i t yc o n s t r a i n t s ：t h e r e a r emi d e n t i c a lm a c h i n e s ，e a c ho fw h i c hc a np r o c e s sa tm o s t j o b s w ea r ea l s og i v e n m 0 ，o p t ( i ) n ，r a ( i ) nv ，) 為簡(jiǎn)便起見，我們也常常將a ( i ) 和o p t ( i ) 記為a 和o p t 這里，我們不得不提及計(jì)算復(fù)雜性，即哪些問題是簡(jiǎn)單的，又有哪些問題是困難 的很顯然，計(jì)算復(fù)雜性是近似算法領(lǐng)域的基石而為了解決一個(gè)實(shí)際問題，我們或者 試圖去尋找關(guān)于該問題的一個(gè)多項(xiàng)式時(shí)間算法去求解其最優(yōu)值，或者嘗試去證明該 問題的尸一困難性，在此基礎(chǔ)上去尋找一個(gè)有效的近似算法 我們稱問題p 為在線問題，如果它的輸入以在線方式到達(dá)同時(shí)其輸出也以在線 方式產(chǎn)生，這意味著在線輸入所產(chǎn)生的輸出會(huì)影響到最終解的值由此產(chǎn)生一個(gè)自然 的想法，也就是將優(yōu)化問題分類為在線問題與離線問題許多優(yōu)化問題內(nèi)在地屬于離 線情況，例如大部分的線性規(guī)劃都假設(shè)它們的輸入是離線給出的但是也存在許多 優(yōu)化問題，考慮它們的在線與離線情況都具有重要的實(shí)際應(yīng)用背景，例如裝箱問題 ( b i np a c k i n g ) 與平行機(jī)排序問題( s c h e d u l i n g ) 此外，還有許多優(yōu)化問題屬于在線問題， 但是即使對(duì)于這樣的問題，我們?nèi)匀豢梢约僭O(shè)存在一個(gè)絕對(duì)聰明的對(duì)手使其所給予 的算法達(dá)到離線情況的最優(yōu)值 1 2 排序問題簡(jiǎn)介 我們先引入最基本的排序問題( p a r a l l e lm a c h i n es c h e d u l i n g ) ：假設(shè)有m 臺(tái) 機(jī)器壇( i = 1 ，2 ，m ) 以及n 個(gè)相互獨(dú)立的_ t - 件j j ( j = 1 ，2 ，n ) 現(xiàn)需將 每個(gè)工件安排到任一臺(tái)機(jī)器上不中斷地加工一次，記每個(gè)工件的加工時(shí)間為 p j o ( j = l ，2 ，扎) ，且每個(gè)工件在零時(shí)刻到達(dá)假設(shè)已給定一個(gè)排序，我們稱g 為工件乃的完工時(shí)間，記n 。= i i i & xa 我們的目標(biāo)是找到一個(gè)安排這些工件的 加工方案，使得所有工件在最短時(shí)間內(nèi)完工，即m i n n z 該問題稱為使時(shí)間跨度 ( m a k e s p a n ) 最小的平行機(jī)排序問題 自從1 9 6 6 年r g r a h a m 4 】提出關(guān)于上述問題的第一個(gè)近似算法以來，迄今人們 已廣泛地從不同的背景和觀點(diǎn)研究排序問題特別地，受到理論計(jì)算機(jī)科學(xué)發(fā)展所 緒論 需，排序問題持續(xù)地成為組合優(yōu)化領(lǐng)域中極具活力的包含有大量有趣結(jié)論的一個(gè)研 究方向?qū)τ谂判騿栴}，我們現(xiàn)實(shí)中常常需要對(duì)其進(jìn)行在線情況分析，即工件的信息 并非在零時(shí)刻完全釋放，我們需要根據(jù)現(xiàn)有的局部信息對(duì)工件進(jìn)行安排 排序問題可根據(jù)工件，機(jī)器或目標(biāo)值的特征分為各種不同的類型，關(guān)于它們的詳 細(xì)介紹請(qǐng)參見j s g a l l 所撰寫的綜述性文章 7 1 我們將在本節(jié)簡(jiǎn)單介紹一下排序問題 的基本類型： 1 2 1 關(guān)于工件的相關(guān)標(biāo)記 設(shè)工件以包含禮；個(gè)操作步驟0 m ，0 加每個(gè)步驟0 t f 需要的加工時(shí)間為 p 泓若工件以只包含一個(gè)步驟( 吼= 1 ) ，則記它的加工時(shí)間為p i 更進(jìn)一步地，將工 件以第一個(gè)步驟可執(zhí)行的時(shí)刻稱為它的釋放時(shí)間n 與0 ；f 相應(yīng)的加工機(jī)器記為 冬 尬，) 一般情況下，l i j 所屬的集合或者是單臺(tái)機(jī)，或者是所有機(jī)器的 集合第一種情況意味著相應(yīng)工件必須由特定的機(jī)器加工，后一種情況下我們則稱 這些機(jī)器為平行機(jī)本文主要研究的是平行機(jī)排序問題此外，當(dāng)每個(gè)工件以加工完 成時(shí)，對(duì)應(yīng)產(chǎn)生一個(gè)成本函數(shù)值 ( ) ，這里針對(duì)不同的目標(biāo)成本函數(shù)，我們可以選擇 完工時(shí)間也或權(quán)重齜來定義五 一般情況下，我們假設(shè)排序問題中的所有數(shù)據(jù)p i , p 巧，n ，d ，都是整數(shù)，并稱一 個(gè)排序是可行的如果任意兩個(gè)工件加工區(qū)間在同一臺(tái)機(jī)器上沒有重疊，任意工件的 單個(gè)步驟沒有在兩臺(tái)機(jī)器上同時(shí)加工，以及符合與排序問題各種類型相關(guān)的其它特 定限制我們稱一個(gè)排序是最優(yōu)排序，如果它對(duì)于相應(yīng)的目標(biāo)優(yōu)化準(zhǔn)則取得最小值 有時(shí)我們也將工件以簡(jiǎn)單地記為指標(biāo)值i ，這將在本文的論述和證明中加以使用 更進(jìn)一步地，人們傾向于使用約定俗成的“三參數(shù)表示法”( t h r e e f i e l dr e p r e s e n t a t i o n ) 將各種不同類型的排序問題表示為q 蚓7 的形式這里o t 表示機(jī)器環(huán)境，p 表示 工件特征，1 表示優(yōu)化目標(biāo)準(zhǔn)則 3 1 1 2 2 機(jī)器環(huán)境 機(jī)器環(huán)境由兩個(gè)參數(shù)組成的字符串q = q 1 乜2 表示我們?cè)谘芯窟^程中常常遇 到的關(guān)于參數(shù)。的取值可能性主要有。，p ，q ，r ，g ，0 ，zf 等下面主要介紹一下 。，p ，q ，r 的含義，其它記號(hào)請(qǐng)參考文獻(xiàn)【3 1 緒論 若q 1 = o ，9 2 0 表示每個(gè)工件必須被安排到某一特定的機(jī)器上進(jìn)行加工，這時(shí)相應(yīng) 的q 表示為a = 2 若q 1 p ，q ，r ) ，則表明這些機(jī)器是平行機(jī)更進(jìn)一步地，若o l 。= p ，則表示機(jī) 器為同型平行機(jī)( i d e n t i c a lp a r a l l e lm a c h i n e s ) ，也就是說若工件五被安排到機(jī)器尬上 時(shí)，其對(duì)應(yīng)的加工時(shí)間為p 巧= p t ，則當(dāng)其被安排到其它機(jī)器時(shí)上述加工時(shí)間維持不 變?nèi)魆 1 = q ，則表示機(jī)器為同類平行機(jī)( u n i f o r mp a r a l l e lm a c h i n e s ) ，即p i j = p i s j ， 其中s j 為機(jī)器m f 的加工速度若o l l = r ，則表示機(jī)器為無關(guān)聯(lián)平行機(jī)( u n r e l a t e d p a r a l l e lm a c h i n e s ) ，即p i j = 仇s 巧，其中s 巧為機(jī)器塢對(duì)每個(gè)工件五的加工速度 參數(shù)q 2 則表示機(jī)器的數(shù)量，若0 1 2 = k ，表示機(jī)器數(shù)為一個(gè)固定的常數(shù)值k 若機(jī) 器數(shù)是任意值，則記o l 2 = o 1 2 3 工件特征 我們將工件特征用參數(shù)表示，它主要包括六種不同類型，分別記之為 p t ，仍，風(fēng)，風(fēng)，阮，風(fēng)下面將簡(jiǎn)要介紹上述參數(shù)各自的含義和特點(diǎn) 參數(shù)阮表示工件是否允許中斷( p r e e m p t i o n ) 一個(gè)工件或其加工步驟可中斷是 指工件加工中途可停止并在稍后在同一臺(tái)機(jī)器( 或者在其它機(jī)器) 上繼續(xù)加工若工 件可中斷被允許，則記p 1 = p r n t n ，否則盧1 不出現(xiàn)在p 中 參數(shù)仍表示工件之間的順序關(guān)系( p r e c e d e n c er e l a t i o n s ) 它們的先后順序可以通 過一個(gè)有向無圈圖g = ( va ) 表示，其中v = 1 ，竹) 對(duì)應(yīng)工件集，( i ，k ) a 當(dāng) 且僅當(dāng)工件五必須在以開始加工之前完工，并將其記為五_ 以若g 是任意一種 有向無圈圖，我們記尻= p r e c 有時(shí)當(dāng)g 具有特殊的結(jié)構(gòu)，例如鏈( c h a i n ) ，樹( i n t r e e ， o u t t r e e ) 等，我們將仍進(jìn)一步標(biāo)記，例如當(dāng)g 為i n t r e e 時(shí)，則記阮= i n t r e e 參數(shù)島= n 表示工件的釋放時(shí)刻若對(duì)所有工件n = o ，則島不出現(xiàn)在p 中 參數(shù)風(fēng)表示工件加工時(shí)間或加工步驟的限制若屈表示為p t = 1 ( p 巧= 1 ) ， 則每個(gè)工件( 步驟) 具有同一加工長(zhǎng)度類似地，我們可根據(jù)實(shí)際問題將其表示為 p i = p ( p 訂= p ) 甚至如p i 1 ，2 ) 的形式以說明工件加工時(shí)間或加工步驟的情況 參數(shù)風(fēng)= d t 表示工件的具體截止時(shí)間，即每個(gè)工件必須在時(shí)刻d t 前完成 在有些排序問題中，我們限制一些工件的集合必須同批次( b a t c h ) 處理一個(gè)批 次是指這組工件的集合在同一臺(tái)機(jī)器上整體加工，我們假設(shè)同批次的工件它們的釋 4 緒論 放時(shí)間相同，且這些工件兩兩獨(dú)立批次排序問題包含兩種類型：p 一批次排序問題與 8 一批次排序問題p 一( s 一) 批次排序問題表示該批次的加工長(zhǎng)度為這些工件集合中 加工時(shí)間的最大值( 總和) ，并分別記為風(fēng)= p b a t c h 和風(fēng)= 8 一b a t c h ，否則風(fēng)不 出現(xiàn)在口中 1 2 4 優(yōu)化準(zhǔn)則 如前所述，我們記a 為工件z 的完工時(shí)間，相應(yīng)的成本記為 ( g ) 成本函數(shù)主 要有以下兩種基本類型： 厶凹( c ) ：= m a x f i ( c i ) i = 1 ，n ) 以及 ( c ) ：= 五( q ) = 1 分別稱為瓶頸目標(biāo)與總和目標(biāo)排序問題要求我們找到一個(gè)可行排序使其成本函數(shù) 總和最小一般情況下，我們主要研究時(shí)間跨度( m a k e s p a n ) c m 。z ( 瓶頸目標(biāo)) ，加權(quán)完 工時(shí)問和( s u mo f w e i g h t e dc o m p l e t i o nt i m e ) g ( 總和目標(biāo)) 等成本函數(shù) 1 3 在線排序問題簡(jiǎn)介 對(duì)于不同的在線排序問題，它們最重要的分類準(zhǔn)則取決于排序過程中哪一部分 的信息是在線給出的我們常遇到的類型有下面幾種： 1 3 1 工件逐次到達(dá)的情況 這種情況下工件按某一次序逐個(gè)給出在符合其它限制條件的基礎(chǔ)上，我們要求 在知道下一工件的信息前必須將前一個(gè)工件安排到某一機(jī)器上的某一確定時(shí)刻而 一旦工件給出，我t f 立即知道關(guān)于該工件的所有信息，包括它的加工時(shí)間我們可以 允許延遲工件的加工，即我們可以安排當(dāng)前工件晚于序列中下一個(gè)工件開始加工的 時(shí)間，但是一旦我們得知下一工件的所有信息，則不再允許修改前一工件的安排 1 3 2 加工時(shí)間未知的情況 這種情況- f z n 件的加工時(shí)間未知在該工件加工完成之前一直是未知信息對(duì)于 緒論 在線算法我們唯一可以確定的就是該工件仍在加工或未加工與上一情況不同，所有 可執(zhí)行的工件都可以是在線算法的執(zhí)行對(duì)象，任何工件都可以被算法選擇在某臺(tái)機(jī) 器上加工或稍后加工此外，如果允許工件可中斷或重啟，則算法可任意決定將某一 正在加工的工件中斷或重啟除了工件的j j 口7 - _ 時(shí)間之外，一旦某一工件變得可執(zhí)行， 則該工件的其它所有信息立即獲知 1 3 3 工件實(shí)時(shí)到達(dá)的情況 這種情況下，算法具有與加工時(shí)間未知的情況具有相同的可選擇范圍，與上面情 況不同的是一旦工件變得可執(zhí)行，則該工件的加工時(shí)間同時(shí)獲知此時(shí)唯一在線的 信息是我們不知道該工件后面到達(dá)的工件所具有的信息 我們有時(shí)也把那種一旦工件到達(dá)立即得知其加工時(shí)間的算法稱為可洞察的，而 將那種不知道加工時(shí)間的算法稱為不可洞察的 1 3 4 工件加工時(shí)間受限于某一區(qū)間的情況 上面介紹的三種在線情況都允許我們我們將工件延遲7 j 口：y - 但在這種情況下，我 們假設(shè)每個(gè)工件必須在某一時(shí)間區(qū)間內(nèi)加工，否則將該工件拒絕在這種情況下，我 們一般不考慮使時(shí)間跨度最小的目標(biāo)函數(shù)，而是考慮那些選擇被加工工件的權(quán)重和 等目標(biāo)函數(shù) 6 帶容量限制的平行機(jī)排序問題 2 帶容量限制的平行機(jī)排序問題 2 1問題簡(jiǎn)介 我們考慮這樣的一個(gè)平行機(jī)排序問題：給定m 個(gè)同型平行機(jī)( i d e n t i c a lm a c h i n e s ) ，限定每臺(tái)機(jī)器上最大的加工個(gè)數(shù)為砘給定m 莖個(gè)工件，每個(gè)工件 的加工時(shí)間記為島0 ，我們的目標(biāo)是找出一個(gè)排序使其時(shí)間跨度( m a k e s p a n ) 最小 而且滿足問題所要求的容量限制 該問題具有重要的實(shí)際應(yīng)用背景，在許多制造系統(tǒng)里，例如v l s i 芯片制造領(lǐng)域， 我們需要將工件安排到不同生產(chǎn)設(shè)備上，要求每臺(tái)設(shè)備上的工件個(gè)數(shù)盡量平均，具 體例子可參見l h t s a i 的論文 8 1 他首先提出了帶相同容量限制的兩臺(tái)機(jī)平行機(jī)排 序問題，并給出一個(gè)啟發(fā)式算法同時(shí)證明當(dāng)工件的加工時(shí)間互相獨(dú)立且均勻分布時(shí) 所給算法具有漸進(jìn)最優(yōu)性質(zhì) 上述問題是p 困難問題，離線情況下，j b r a m e l 等人 2 用l p t ( l a r g e s tp r o c e s s i n gt i m e ) 算法對(duì)兩臺(tái)機(jī)容量限制相同的特殊情況進(jìn)行了分析，并證明l p t 算法 在該情況下的界仍是7 6 ，與一般情況下兩臺(tái)機(jī)的l p t 算法所達(dá)到的緊界【5 】相同 此外，h y a n g 等人的文章 1 0 】考慮了兩臺(tái)機(jī)帶相同容量限制問題的另一類目標(biāo)函數(shù) g ，并給出了一個(gè)基于半正定規(guī)劃的多項(xiàng)式時(shí)間算法，其上界為1 1 6 2 6 此外， g j w o e g i n g e r 在他的文章 9 】中對(duì)于上述兩類目標(biāo)函數(shù)的兩臺(tái)機(jī)帶相同容量限制問 題分別給出了f p t a s ( f u l l yp o l y n o m i a lt i m ea p p r o x i m a t i o ns c h e m e ) ，即存在一系列近 似算法a 使得對(duì)所有的e 0 ，算法的界為1 + e ，其運(yùn)行時(shí)間由輸入規(guī)模由1 e 的多 項(xiàng)式所界定；最近c(diǎn) z h a n g 等人在他們的文章【1 1 】中用“i t e r a t i v er o u n d i n gm e t h o d ” 證明了該問題具有上界為3 的算法 我們?cè)诒疚闹兄饕芯恳韵聨追N情況： ( 1 ) 機(jī)器臺(tái)數(shù)為2 ，則離線情況下，我們對(duì)機(jī)器容量限制不同的情況利用文獻(xiàn)【2 】 所提的l p t 算法進(jìn)行分析，證明該算法存在下界為2 的實(shí)例然而對(duì)于一類特殊的 l p t 算法( 記為算法m l p t ) ，則可以證明該算法具有上界5 3 ，且該界是緊的進(jìn)一 帶容量限制的平行機(jī)排序問題 步的，在上述算法的基礎(chǔ)上我們可加以改進(jìn)從而得到界為3 2 的另一個(gè)算法( 記為 r l p t ) ； ( 2 ) 機(jī)器臺(tái)數(shù)為2 ，則在線情況下，我們首先對(duì)容量限制不同的情況進(jìn)行了分析， 證明若兩臺(tái)機(jī)器的容量限制之差大于等于2 時(shí)，任何在線算法都不具有比2 更好的 界然而若它們的容量限制之差為0 或1 時(shí)，我們提出了一個(gè)在線算法( 記為b s ) ，并 證明這種情況下該算法具有界1 + o ，其中口= 造，且該算法是最好算法 ( 3 ) - 3 機(jī)器臺(tái)數(shù)為m 時(shí)，則在線情況下，我們對(duì)于各機(jī)器容量限制不同的情況證 明任何在線算法的界至少是_ m + 廣l ，o 此外，若機(jī)器的容量限制相同時(shí)，我們證明l s ( l i s t s c h e d u l i n g ) 算法在該情況下其界為1 2 m 若- 5 r - 1 ，其中6 為工件安排完成后達(dá)到了容量限 制的機(jī)器個(gè)數(shù)我們將在下面幾節(jié)分別予以論述 2 2 兩臺(tái)機(jī)離線情況分析 在兩臺(tái)機(jī)容量限制相同的情況下，b r a m e l 等人【2 】采用了l p t 算法證明其界為 7 6 該算法描述如下： 算法l p t ：將各個(gè)工件按加工時(shí)間從大到小進(jìn)行排列，然后將工件按序放入到機(jī)器 中，每當(dāng)機(jī)器出現(xiàn)空閑時(shí)則將剩下未放的具有最大加工時(shí)間的工件放入該機(jī)器一旦 當(dāng)某一臺(tái)機(jī)器達(dá)到容量限制后，將剩余工件全部放入另一臺(tái)機(jī)器 對(duì)于兩臺(tái)機(jī)不同容量限制的情況，我們假設(shè)兩臺(tái)機(jī)器的容量限制分別為七。，乃2 ，分 別記為機(jī)器1 與機(jī)器2 不失一般性，假設(shè)k 1 k 2 我們注意到若對(duì)于該問題仍 采用上面的l p t 算法時(shí)，其界為2 下面是一個(gè)實(shí)例：取k 1 = 佗，k 2 = 1 ，考慮工件 集 ，厶+ 1 ) ，它們的加工時(shí)間分別為d 1 = l ，p 2 = p 3 = = + 1 = 1 n 用l p t 進(jìn)行加工時(shí)若將山放入機(jī)器1 ，則m l p t = 1 + 譬，而o p t = 1 ，故 r m l p t22 由此，我們提出了一個(gè)自然的想法，即將算法作如下改進(jìn)： 算法m l p t ( m o d i f i e dl p t ) ：將各個(gè)工件按加工時(shí)間從大到小進(jìn)行排列，然后先將第 一個(gè)工件安排到機(jī)器2 上，剩下的工件則使用上面所描述的l p t 算法進(jìn)行加工 在本文中我們將證明上述m l p t 算法具有如下的性質(zhì)： 帶容量限制的平行機(jī)排序問題 定理2 1 ：m l p t 的上界為5 3 ，且該界是緊的 記z 。為沒有容量限制兩臺(tái)機(jī)所需時(shí)間跨度的最優(yōu)解類似地，定義z 5 為帶容 量限制兩臺(tái)機(jī)所需時(shí)間跨度的最優(yōu)解此外，記z l p t 和z m l p t 分別為與上述最優(yōu) 解對(duì)應(yīng)的算法得到的值不失一般性，我們將工件以簡(jiǎn)單地記為i ，并假設(shè)這些工件 已經(jīng)按加工時(shí)1 4 從大到小排列，即t 1 t 2 t n 令f ：表示被m l p t 算法安排在 機(jī)器 上的第j 個(gè)工件所對(duì)應(yīng)的工件的序號(hào)考慮工件的子集 1 ，2 ，尼) ，記z 知為 m l p t 算法安排上述工件到機(jī)器后，機(jī)器2 的加工時(shí)間總和減去機(jī)器1 的加工時(shí)間 總和特別地，z 0 蘭0 k ， 引理2 1 ：若踏l p ? = o 礙，則硌卯t ；彩 j = l 。 證明：當(dāng)加工時(shí)間由容量限制較小的那臺(tái)機(jī)器確定時(shí)，這是b r a m e l 等人【2 】文章中 的特殊情況，因此上述命題成立 這里我們記機(jī)器i 是第一個(gè)被關(guān)閉的機(jī)器，若它首先由算法m l p t 達(dá)到它的容量限 制k ；通過上面的命題我們只需考慮總加工時(shí)間由機(jī)器1 決定的情況，印機(jī)器2 首 先達(dá)到容量限制記n 1 表示當(dāng)機(jī)器2 達(dá)到容量限制時(shí)m l p t 安排到機(jī)器1 上的工件 個(gè)數(shù)令n 2 三一仡1 ，即n 2 是m l p t 在安排第個(gè)工件前被安排在機(jī)器2 上的最 后一個(gè)_ t - 件顯然我們有n 2 k 2 1 記x i = e 屯j ，m =島j ( i = 1 ，2 ) 不難看出，對(duì)所有的實(shí)例，我們有下面的性質(zhì)： z y l 刀= x 1 + m z + 去( x z + m + 恐+ 蠔) k l + k 2 z + m = 巧 j - - k 2 + n l + l k x + k 2 z + t l + 島 j = k l + 2 ( 2 1 ) ( 2 2 ) ( 2 3 ) ( 2 4 ) z + t 2 + t 3 + e 巧 ( 2 5 ) j = k l + 3 x 1 一魄 3 ( x 2 + k ) 條件下m l p t 所具有的性質(zhì) 引理2 3 ： 當(dāng)k 2 2 時(shí)，z 拶l 尸t 2 彩 證明：當(dāng)七2 = 1 時(shí)，顯然這時(shí)m l p t 所得到的值就是最優(yōu)值；當(dāng)后2 = 2 時(shí)，由 于算法m l p t 將工件2 安排在機(jī)器1 上，這時(shí)我們有x 1 + m 一磁一蠔 2 ( 局十蠔) 2 t 2 ，故將工件2 與工件磋交換后，機(jī)器1 所有工件的加工 時(shí)間總和大于機(jī)器2 的加工時(shí)間總和，為最優(yōu)值此時(shí)搿l p r = x 1 + h ，而 彩= x 1 + m 一亡2 + 亡f ；，從而有踏l p r ；彩，否則由警= 石再x f l - _ y 函1 石 3 2 ， 我們得到x 1 + m 一3 t 2 + 3 t 朦 0 ，從而2 2 + x 2 + k 一3 2 + 3 t z 2 t 2 矛盾，命題得證 由上，我們只需考慮k 2 3 的情況 引理2 4 ： 當(dāng)k 2 3 ，且n 2 2 時(shí)，z 伊l p r 2 彩 證明：我們將由m l p t 安排在兩臺(tái)機(jī)器上的工件按照這樣的順序重新進(jìn)行排列：將 機(jī)器l 上的工件f ；( 加工時(shí)間由大到小) 與機(jī)器2 上的工件2 2 ( 加工時(shí)間由小到 大) 進(jìn)行交換，直到2 2 2 ；或者j = 佗1 時(shí)終止但由于n 2 2 ，故而必存在某 一k 和j 扎1 使上面的終止條件滿足假設(shè)共交換了s 個(gè)工件，這時(shí)有f 2 。一。 o f l 成立由此得 j = l 。 乃 易，故彩= t x 警 帶容量限制的平行機(jī)排序問題 下面的實(shí)例說明算法m l p t 在上述情況下的界達(dá)到3 2 ：設(shè)尼2 = 3 ，給定工件 集 ，如，以蚪6 ) ，其加工時(shí)間分別為：婦1 = 1 + ，p 2 = 1 ，p 3 = = p 6 = 擊+ e ，p 7 = = p 2 n + 6 = 擊 ，則有z 籮l p t = 3 + 石2 + 2 e ，彩= 2 + 魯- 4 - 3 e ，當(dāng)禮充分 大時(shí)界為3 2 現(xiàn)在我們來考慮忌2 3 ，且n 2 = 1 時(shí)的情況，我們將證明此時(shí)算法m l p t 的界為5 3 在這種情況下，由于n 2 = 1 ，我們恒有f ； ( j 2 ) ，因此這時(shí)條 件局+ 蠔 屯! 不一定成立我們簡(jiǎn)單地記t = x 2 + k ，由于我們已假設(shè) j = l 。 x 1 + m 3 ( x 2 + ) ，故記x 1 + m = 3 t + a 引理2 5 ： 若k 2 3 ，且n 2 = 1 時(shí)，則算法m l p t 具有上界； 證明：由上面，我們有硭1 = 3 t + 我們用反證法證明上述命題 若硌l p ? i 彩，即彩 f 2 。，從而 彩 t + a 成立 由于彩 z ( x 1 + m + x 2 - 4 - 蠔) = 堡筍，從而有1 8 t + 6 a 2 0 t 4 - 5 a ， 即a 2 t 成立由上，我們記a = 2 t - 4 - y ，則此時(shí)我們有z b 3 t + y 比較的上下界，我們得到3 t - 4 - y 5 y 這與 y 0 矛盾，故該不等式無解由此我們證明了算法m l p t 的上界為； 下面是界為i 的一個(gè)實(shí)例：庇2 = 3 ，_ t - 件集為 以，如，j 3 k 2 + 6 ) ，其加工時(shí)間 分別為d 1 = p 2 = 七一罷，p 3 = 墜，p 4 = = p 3 七。+ 6 = 丟) 顯然當(dāng)k 2 時(shí) 有p 2 p 3 ，滿足m l p t 性質(zhì)這時(shí)踏凹丁= 5 k 一2 ，而彩= 3 k - 4 - ；，當(dāng)k 充分 大時(shí)其界為5 3 ，結(jié)論得證 由引理2 1 ，2 2 ，2 3 ，2 4 ，2 5 ，定理2 1 得證 我們知道只有在x 1 + m 3 ( x 2 + k ) 且k 2 3 ，n 2 = 1 時(shí)的情況下m l p t 算 法的界為5 3 ，其它情況時(shí)m l p t 的界為3 2 因此我們考慮k 2 3 時(shí)的情況我們 通過將m l p t 作如下改進(jìn)來證明修改后的算法具有緊界3 2 ： 算法r l p t ( r e f i n e d l p t ) ：我們首先將加工時(shí)間最長(zhǎng)的工件先安排到容量限制較小 的機(jī)器2 上，接著按照m l p t 安排工件設(shè)m l p t 算法在機(jī)器1 上已經(jīng)安排了h 個(gè) 帶容量限制的平行機(jī)排序問題 工件，此時(shí)機(jī)器l 上的加工時(shí)間長(zhǎng)度為正= t t ! t 1 對(duì)于接下來的一個(gè)工件 h + 2 ，設(shè)它的加工時(shí)間為p 若丑+ p t 1 仍然成立，則將該工件繼續(xù)安排到機(jī)器1 否則我們得到正+ p t 1 ，記z = 正+ p t 1 若接下來剩下的工件個(gè)數(shù)大于忌2 1 個(gè)( 否則兩臺(tái)機(jī)器都不會(huì)達(dá)到容量限制，此時(shí)界為7 6 ) ，且它們當(dāng)中的前k 2 2 個(gè)工 件的加工時(shí)間總長(zhǎng)度滿足 t 1 成立，則此時(shí)加工時(shí)間由機(jī) 器2 確定，屬于引理2 1 的情況，結(jié)論成立；若存在新工件使乃+ p t 1 滿足， 但是 z 7 ，這時(shí)意味著n 2 2 ，屬于引理2 4 的情況，結(jié)論成立；若新工件 h + 2 h + k ，一1 使乃+ p t 1 滿足，且 q ，即修改后算法的完工時(shí)間為c 1 若 這時(shí)有q 1 的工件，此時(shí)算法a 只能將它們安排到機(jī)器2 上，這種情況下r a = 蠡，當(dāng)z 充分大時(shí)其競(jìng)爭(zhēng)比至少為2 ( 2 ) 算法a 將工件以安排到機(jī)器2 上，且將工件以安排到機(jī)器1 ，此時(shí)機(jī)器l 容量已滿不能繼續(xù)加工工件則對(duì)手令t 1 = t 2 = 1 ，且接著給出兩個(gè)加工時(shí)間 長(zhǎng)度為t 3 = t 4 = 秒 2 的工件，這種情況下r a = 等，當(dāng)可充分大時(shí)其競(jìng)爭(zhēng) 比至少為2 ( 3 ) 算法a 將工件 和如都安排到了機(jī)器2 上，則對(duì)手令上述兩個(gè)工件的加 工時(shí)間都為1 ，則這種情況下立即得r a = 2 綜上所述，當(dāng)兩臺(tái)機(jī)器的容量限制之差大于等于2 ，則任何合理的在線算法其 界為2 命題得證 由上，對(duì)于帶容量限制兩臺(tái)機(jī)排序問題的在線情況，我們只需考慮機(jī)器容量限制之 差為0 或1 的情況首先我們注意到安排過程中若兩臺(tái)機(jī)器上的工件加工時(shí)間總和 分別為c 1 ，c 2 不失一般性，設(shè)c l c 2 且接下來的工件為s ，其加工時(shí)間為t 。則對(duì)于 目前為止所有工件，其相應(yīng)的最優(yōu)解具有下界： s l b 。= m a x t t 2 ，m a x t t ) ( 江1 ，2 ，s ) ) 帶容量限制的平行機(jī)排序問題 對(duì)于容量限制之差為0 或1 的情況，我們采用如下的算法對(duì)工件進(jìn)行安排與加工，稱 為b s ( b a l a n c e ds c h e d u l i n g ) 其描述如下： 算法b s ：設(shè)機(jī)器1 和機(jī)器2 剩余的容量分別為k i 與憊：若k ：尼i ，則將接下來的工 件s 安排到剩余容量較大的那臺(tái)機(jī)器上否則，若c l + 。( 1 + a ) l b 。，則將該工件 放到機(jī)器i 上，否則將其放入機(jī)器2 上這里a = 叢2 土 定理2 4 ：若兩臺(tái)機(jī)器的容量限制之差為0 或i 時(shí)，則算法b s 的界為i + q ，且該算 法是最好算法 證明：先考慮七1 = k 2 的情況，我們用反證法證明r b s l + q 假設(shè)上述結(jié)論不成 立，則存在一個(gè)實(shí)例i 使得r b s i + a ，考慮這其中具有最小工件數(shù)的那個(gè)最 小反例我們對(duì)最小反例i 進(jìn)行分析，并通過推導(dǎo)出矛盾來證明該最小反例不 存在，從而結(jié)論得證 算法在最小反例中已經(jīng)安排了相同個(gè)數(shù)的工件到兩臺(tái)機(jī)器上，設(shè)它們的加工 時(shí)間之和分別為c l ，c 2 且c 1 c 2 ，對(duì)于接下來的工件以，設(shè)其加工時(shí)間為z 若 c l + z ( 1 + a ) l b ，仍然滿足算法所假設(shè)的界，不予考慮故假設(shè)在該反例中 算法b s 把該工件安排到了機(jī)器2 上，此時(shí)滿足c 1 + z ( 1 + ) c l ，即z q c l 注意到要使算法b s 的界大于1 + q ，只需考慮以下幾種情況： ( 1 ) 以是最小反例中的最后一個(gè)工件我們通過對(duì)其加工時(shí)間z 可能出現(xiàn)的不 同取值情況進(jìn)行分析，證明該情況下我們所假設(shè)的最小反例不存在： z c l + c 2 此時(shí)工件以被安排到了機(jī)器2 上，我們有b s = z + c 2 ，而在最 優(yōu)解中有o p t z ，故r b s = 游學(xué)若學(xué)1 + q ，則顯然這種情況下 該實(shí)例不是反例故此時(shí)必有華 1 + o t ，即c 2 q z 這意味著c l c 2 q z ， 從而得到z c 1 + c 2 2 a x ，這與我們假設(shè)中所取的a 值矛盾 口c l z c 1 + c 2 此時(shí)b s = z + c 2 或者b s = c 1 對(duì)于前一種情況，我們有 z + c 2 c 1 + c 2 + c 2 3 c 1 ；對(duì)于后一種情況我們有c 1 3 q c l 3 x q 可；石i 2 c i 2 + 西2 y 巧 1 + q ，即( 1 一q ) ( c 2 + 可) ( 1 十q ) ( c 1 + z ) 由上我們得( 1 一) ( 警) c 1 ( 1 一) ( 警) c 2 ( 1 + c e ) ( c l - + - z ) ( 1 + a ) c l ，從 而得到q c 2 + z 的情況由算法，此時(shí)我們有旦1 警 l + a ，即z a c l ； 旦d y 迎 1 + q ，即c 1 乜可；石干2 c i l + 阿2 1 葡 1 + q ，即( 1 一q ) ( c 1 + y ) ( 1 + a ) ( c 2 + z ) 由上我們得( 1 一q ) ( 警) 羞 ( 1 一q ) ( 警) c 1 ( 1 - a ) ( c l + y ) ( 1 + a ) ( c 2 + x ) ( 1 + q ) z ，從而得到a 2 + q 一1 0 ，這與我們假設(shè)中所取的q 值矛盾 由于算法在安排工件時(shí)必須使機(jī)器上的個(gè)數(shù)差至多為l ，故我們假設(shè)工件以是 最后一個(gè)或倒數(shù)第二個(gè)工件即已分析了可能出現(xiàn)的所有情況綜合( 1 ) ( 2 ) ，我們 得到當(dāng)k 1 = k 2 時(shí)，算法b s 具有上界1 + q 對(duì)于k 1 = 奶+ 1 的情況，我們按照算法先將第一個(gè)工件安排到機(jī)器1 若工件 只有一個(gè)，則即是o p t 值否則按照b s 算法對(duì)第二個(gè)工件進(jìn)行安排，從而即可 利用上面相同的分析證明該情況下算法b s 仍具有相同的上界 下面我們說明對(duì)于任意在線算法a 其下界至少是1 + q ，從而證明本文所給出 的b s 算法是該情況下的最優(yōu)算法由定理2 3 ，若在線算法a 在安排工件的過 程中出現(xiàn)了兩臺(tái)機(jī)剩余容量限制之差大于等于2 的情況時(shí)此時(shí)其下界至少為 2 若k 1 = k 2 時(shí)，且在線算法a 在兩臺(tái)機(jī)器上安排了相同個(gè)數(shù)的工件，且設(shè)每 臺(tái)機(jī)器上剩余的容量限制皆為2 則其對(duì)手令兩臺(tái)機(jī)器前面的加工時(shí)間總和相 等皆為e 并給出加工時(shí)間分別為e 和1 的兩個(gè)工件顯然由定理2 3 算法a 只 能將這兩個(gè)工件分別安排到兩臺(tái)機(jī)器上，設(shè)算法a 將加工時(shí)間為1 的工件安 帶容量限制的平行機(jī)排序問題 排在機(jī)器2 上此時(shí)對(duì)手繼續(xù)給出一個(gè)加工時(shí)間為0 的工件，若算法a 將其安 排在機(jī)器2 上，則此時(shí)算法a 的競(jìng)爭(zhēng)比為r a = 峙警，當(dāng)充分小時(shí)其競(jìng)爭(zhēng) 比至少為l + o l ；若算法a 將其安排在機(jī)器1 上，則對(duì)手繼續(xù)給出一個(gè)vt - 時(shí) 間為