（運(yùn)籌學(xué)與控制論專業(yè)論文）帶周期性維護(hù)時間的平行機(jī)排序問題研究.pdf

摘要 摘要 本文研究了帶有維護(hù)時問( 單個或j 時期性) 的平行機(jī)排序問題。該問題可議描 述為：給頂一個相互獨(dú)立的工件序列j = f j 。，j 。j j ，每個工件的加工時間( 長 度) 是p ；，i = l ，n ，且需要把它們分配到一臺( 或多臺) 平行機(jī)上進(jìn)行不可中斷 地加工。在加工過程中，需要對機(jī)器迸行維護(hù)，而工件在維護(hù)時段內(nèi)不能加工。 工件和機(jī)器在零時刻都處于就緒狀態(tài)。全文共分為三章。 第一章是緒論部分，主要介紹排序問題相關(guān)的一些概念和預(yù)備知識。 第二章介紹了帶單個維護(hù)時段的單機(jī)排序問題，分兩種情況：維護(hù)時段固定 維護(hù)時段可選擇。 第三章討論了帶周期性維護(hù)時間的平行機(jī)排序問題。本章證明了l s 算法是 p ，ip e r i o d i c i n a i n t e na n t e i c m a x 在線情況的最優(yōu)算法，算法競爭比為2 。證明 了兩臺機(jī)p z lp e r i o d i c - i l i a i n t e n a n c e f c m a x 情況下，不存在常數(shù)界多項式時間算 法。此外，給出了一個離線算法的參數(shù)界。 關(guān)鍵詞：排序，計算復(fù)雜性，工件不可中斷，維護(hù)時問，近似算法 t h i sp a p e rm a i n l yc o n s i d e r sm a c h i n es c h e d u li n gp r o b l e mw i t h ( s i n g l e o rp e r i o d i c ) m a i n t e n a n c ea c t i v i t i e s g i v e nas e q u e n c ej = ( j l ，j 2 ，j 。) o f i n d e p e n d e n tj o b s ，e a c hw i t hap u s i t i r ep r o c e s s i n gt i m e ( s i z e ) p i ，i = l ，n ， a 1 1j o b sm u s tb en o n p r e e m p t i v e l ys c h e d u l i n go no n eo rs e v e r a li d e n t i c a l m a c h i n e s t h ep a p e rc o n s i s tso ft h r e ec h a p t e r s c h a p t e r1g i v e ss o m ei n t r o d u c t i o na n dp r e l i m i n a r i e sf o rs c h e d u l i n g p r o b l e m s c h a p t e r2i n t r o d u c e ss i n g l e - - m a c h i n es c h e d u l i n gp r o b l e mw i t ho n e m a i n t e n a n c e t h e r ea r et w os o r ts ：f i x e dm a i n t e n a n c e 、o p t i o n a lm a i n t e n a n c e c h a p t e r 3d is c h ss e sm a c h i n e s c h e d u l i n gp r o b l e m w i t h p e r i o d i c m e i n t e n a n c e t h isc h a p t e rp r o v et h a tl sist h eo p t i m a lo n l i n ea l g o r i t h m o fp 】j p e r i o d i c - - m a i n t e na n c e f c m a x t h ec o m p e t i t i v er a t i oo fl sa l g o r i t n m i s2 t h ea l g o r i t h mw i t hc o n s t a n tb o u n do fp 2j p e r i o d i c - - m i n t e na n c e l c m a x d o e s n te x is t b e s i d e s ，w eg i v eao f f l i n ep o l y n o m i a la l g o r i t l mw i t h p a r a m e t e rb o u n d k e yw o r d s ：s c h e d u l i n g ，c o m p u t a t i o n a lc o m p l e x i t y ，n o n r e s u m a b l ej o b s ， m a i n t e n a n c e ，a p p r o x i m a t i o na l g o r i t h m 玎 第一章緒論 * 第一章緒論 1 1 平行機(jī)排序問題 排序( s c h e d u l i n g ) 是一類重要的組合優(yōu)化問題，它廣泛地應(yīng)用于計算機(jī)科 學(xué)，管理科學(xué)和工程技術(shù)等很多領(lǐng)域，同時也是運(yùn)籌學(xué)一個非常活躍的分支。排 序問題產(chǎn)生的背景是機(jī)器制造。后來普通的生產(chǎn)部門的人員調(diào)度，學(xué)校的課程安 排等等都需要用道排序的理論和算法。排序問題 1 】簡單得說就是利用一些處理 機(jī)( p r o c e s s o r ) ，機(jī)器( m a c h i n e ) 或資源( r e s o t l f e e ) ，最優(yōu)地完成一批給定的 任務(wù)( t a s k ) 或工作( j o b ) 。在執(zhí)行這些任務(wù)或作業(yè)時需要滿足某些限制條件， 如任務(wù)的到達(dá)時間、完工的限定時間、任務(wù)的加工順序、資源對加工時問的影響 等。 一般的平行機(jī)排序問題可以描述成：給定一個工件序列j = j 1 ，j 。j j ， 每個工件的加工時間( 長度) 是p 。i = 1 ，n ( 在不混淆的情況下將工件序列表示 為j = p 。，p ：，p 。) ) ，需要把它們分配到m 臺機(jī)器m 1 ，m 2 ，m m 上去加工。機(jī)器 m i 的速度為s i 1 。機(jī)器的負(fù)載是指所有在這臺機(jī)器上加工的工件的總長度。在 算法s 下機(jī)器負(fù)載記為l i ( j ，s ) ( 在不會引起歧異的情況下，可筒記為1 1 ) ， i = 1 ，2 ，m 。 目前文獻(xiàn)普遍采用一矛 三參數(shù)表示法ajply 來為排序閘題命名三個參數(shù) o 【，口和v 分別刻畫了機(jī)器的狀況，工件的狀況和目標(biāo)函數(shù)。下面我們分別對每 個參數(shù)所代表的含義作具體說明。 o 【主要描述了機(jī)器的類型和加工規(guī)則。常見的有單臺機(jī)，同型機(jī)( i d e n t i c a l m a c h i n e s ) ，同類機(jī)( u n i f o r mm a c h i n e s ) ，不同類機(jī)( u n r e l a t e dm a c h i n e s ) ， 流水作業(yè)( f l o w s h o w ) ，有序作業(yè)( j o bs h o p ) ，自由作業(yè)( o p e ns h o p ) 等等。 本文考慮同型機(jī)，即完全相同的平行機(jī)器，機(jī)器速度s ；均相同。 d 主要表示工件的性質(zhì)，加工要求和限制( 如果不寫，表示無限制) 。它可 以同時包含多項。如工件是在線還是半在線，加工是否可以中斷，工件是否需要 準(zhǔn)備時閥，工件之間是否存在加工順序約束等等。在實際生活中，機(jī)器運(yùn)行一段 時間之后需要停止并維護(hù)，在這樣的背景下我們可以加入帶維護(hù)時間這個條件來 考慮這一類問題。第二章列舉了帶單個維護(hù)時間的排序問題模型、計算復(fù)雜性和 第一章緒論 相應(yīng)算法；第三章集中討論了帶周期性維護(hù)時間的排序問題，主要是單臺機(jī)和兩 臺機(jī)的情況 v 主要描述了要優(yōu)化的目標(biāo)函數(shù)。類似于所有的組合優(yōu)化問題，任何一個給 定的排序問題都有有限個可行解，目標(biāo)函數(shù)給出了這個含有限個解的解空間的一 個度量，并在這個度量意義下定義了最優(yōu)解。對于某個給定的排序問題，定義某 臺機(jī)器的完工時問為安排好所有的工件后，這臺機(jī)器上的最后一個完工工件的完 工時間。排序問題中最經(jīng)典的目標(biāo)函數(shù)是c m x ( m a k e s p a n ) ，即極小化最大的機(jī) 器完工時聞。事實上，最優(yōu)化問題特別是排序問題的一個主要缺陷是對于目標(biāo)函 數(shù)每個不同的度量都有不同的最優(yōu)解。通常，不同算法用于不用度量，也都給出 自己的解。關(guān)于各種目標(biāo)函數(shù)，如總完工時間，最大誤工時間等等，請參考一些 排序方面的專著 1 】。 第一章緒論 1 2 離線，在線、半在線悶意和算法性能分析 根據(jù)我們在排序時掌握工件信息的多少把排序問題分為離線( o f f l i n e ) 和 在線( o n l i n e ) 兩類。 在離線問題中，全部工件的所有信息在排序時都是已知的，我們可以充分利 用這些信息對工件進(jìn)行安排。 而對在線問題，是指工件的信息逐個釋放，即工件p i * l 的信息只有在對工件 p 1 ，p i 進(jìn)行安排后才會被釋放，并且工件一個個到達(dá)，一旦到達(dá)，就必須安 排它在某臺機(jī)器上加工，且在以后不可改變。 半在線( s e m i o n l i n e ) 排序問題是介于離線問題和在線問題之間的排序問 題，也就是說我們除了知道當(dāng)前到達(dá)的工件及之前的工件信息，同時還預(yù)先知道 工件的部分信息，但仍不允許對任何已安排的工件迸行重排 4 ；5 。常見的信息 有預(yù)先知道所有工件的總長度( s u m ) 6 ，最大工件的加工時間( m a x ) 7 】，工 件從大到小來( d e c r ) 【8 9 】，工件的加工時間在一個區(qū)問內(nèi)( g r o u p ) 【7 】，工 件的相對大小( o r d i n a l ) 10 】，以及預(yù)先知道離線最優(yōu)值( o p t ) 1 i 等等。 半在線排序問題的研究主要體現(xiàn)在如何有效地利用這些已知的部分信息來 設(shè)計出更好的算法，即要求該算法的性能要比已知的最好可能的在線算法的性能 要好。在半在線排序的研究出現(xiàn)之前，幾乎沒有人知道這些信息對于設(shè)計近似算 法的有用程度，也幾乎沒有人知道如何利用這些信息來設(shè)計更好性能的近似算 法。因此，與經(jīng)典的平行機(jī)排序問題一樣，半在線排序問題也是同樣有趣和有意 義的。 對離線問題，我們將求解離線問題的算法稱為離線算法。離線算法的性能用 最壞情況界( w o r s t - e a s er a t i o ) 來衡量。對一個工件序列j 和算法s ，記s ( j ) 代表算法s 的目標(biāo)值，o p t ( j ) 代表最優(yōu)值。對于極小化目標(biāo)，算法s 的最壞情況 界定義為c ( s ) = s u p ， s ( j ) o p t ( j ) ) 。對于極大化目標(biāo)，算法s 的最壞情況界定義 為c ( s ) = s u p ，f o p t ( j ) s ( j ) ) 。 對于一個( 半) 在線問題，求解該問題的算法就稱為( 半) 在線算法。( 半) 在線算法的性能是可以通過它的競爭比( c o m p e t i t i v er a t i o ) 來衡量的。其定 義與離線算法的最壞情況界類似，其中o p t ( j ) 為相應(yīng)離線問題的最優(yōu)目標(biāo)值。 第一章緒論 我們希望設(shè)計出競爭比盡可能小的算法。如果沒有任何( 半) 在線算法的競爭小 于p ，則稱這個( 半) 在線問題的上界為p 當(dāng)這個問題的某個( 半) 在線算法 的競爭比小于p ，則稱這個( 半) 在線問題的下界為p 。當(dāng)這個問題的某個( 半) 在線算法的競爭比等于問題的下界時，我們就稱這個算法是最優(yōu)的。 第一章緒論 1 3 論文概述 本文主要討論了帶維護(hù)時聞的平行機(jī)排序問題。 第二章討論了帶單個維護(hù)時段的單機(jī)排序問題，分兩種情況：維護(hù)時段固定、 維護(hù)時段可選擇。對前一種情況，證明了1 ，啊“c j 的n p 困難性，介紹了s p t 算法和i d s p t 算法，以及兩個算法的最壞情況界；對后一種情況，介紹了近期相 關(guān)文章的研究成果。 第三章討論了帶周期性維護(hù)時間的平行機(jī)排序問題。目前研究這類問題的文 章較少，本章的內(nèi)容主要是接著m j i ，y h e ，t c e c h e n g 的文章 2 0 】做了些工 作。文章f 2 0 】證明了l p t 算法是p 。l p e r i o d i c - - m a i n t e n a n c e i c m a x 離線情況的最 優(yōu)算法，算法最壞情況界為2 。本章證明了l s 算法是p ，ip e r i o d i c - - m a i n t e n a n t e l c m a x 在線情況的最優(yōu)算法，算法競爭比也為2 。證明了兩臺機(jī)p ：ip e r i o d i c 一 眥i n t e n a n c e l c m a x 情況下，不存在常數(shù)界多項式時問算法。此外，給出了一個 離線算法及其參數(shù)界。 第二章帶維護(hù)時問的平行機(jī)排序問題研究 第二章帶單個維護(hù)時段的單機(jī)排序同邀研究 2 1 引言 現(xiàn)有的關(guān)于排序理論的文章大多數(shù)是基于機(jī)器連續(xù)可獲得的假設(shè)。但在實際 生產(chǎn)過程中，由于確定的機(jī)器維護(hù)和不可預(yù)見的死機(jī)( 損壞) 現(xiàn)象，往往使得這 種假設(shè)不成立。在實踐中，有工件等待加工而機(jī)器卻停止運(yùn)轉(zhuǎn)進(jìn)行維護(hù)的現(xiàn)象并 非罕見，我們要將機(jī)器維護(hù)計劃和工件加工計劃很好得協(xié)調(diào)起來。不確定的死機(jī) ( 損壞) 現(xiàn)象將會打亂工件加工計劃，并大大降低生產(chǎn)系統(tǒng)的效率。機(jī)器維護(hù)可 以通過較小的損失降低死機(jī)的概率，決策者越來越注意到制訂機(jī)器維護(hù)計劃的重 要性。 如果一臺機(jī)器在加工過程中可以安排一次或者若干次的機(jī)器維護(hù)，這些維護(hù) 可能需要花費(fèi)一些時間，但卻可以使加工某些工件的速度變快，那么作為一個精 明的決策者，是否安排這些維護(hù)，何時安排它們以及對某個具體的工件是否有必 要等到維護(hù)之后再加工等等這些問題就應(yīng)當(dāng)排入考慮之列。這就是我們要介紹的 一一帶有速率改變行為的單機(jī)排序問題，我們用并不準(zhǔn)確的“速率改變行為”代 表的不只是上面提到的機(jī)器維護(hù)，還可能是機(jī)器中斷，機(jī)器磨損以及加工過程的 學(xué)習(xí)效應(yīng)等所有可利用的限制( 機(jī)器限制的可利用性見文獻(xiàn)【i3 】) 。正是由于有 著廣泛的應(yīng)用背景，這個問題一直以來為很多人考慮和研究。 我們可以將問題簡單地分為兩類：速率改變行為固定和速率改變行為不定。 到目前為止，對于只有一個速率改變行為的情形，這樣兩類分別都有了一些比較 好的結(jié)果。比如，對于前者，已經(jīng)給出了目標(biāo)為最大完工時間或者完工時間總和 的近似算法，而對于后者，很多目標(biāo)都已經(jīng)有了獲得最優(yōu)解的多項式算法。 帶有速率改變行為的單機(jī)排序問題的各個目標(biāo)都已經(jīng)有了較好的結(jié)果，對于 速率改變行為時間固定的情形，主要是復(fù)雜性的證明和近似算法的尋找，而對于 速率改變行為時間可選擇的情形，主要是分辨其中哪些不是p 問題，而對其中的 p 問題如何給出多項式時間算法等。我們也可以將速率改變行為的次數(shù)加入考慮 因素中，一些問題仍然值得我們探討。 第二章帶維護(hù)時問的平行機(jī)排序問題研究 2 2 維護(hù)時段圈定的情況 為方便陳述，我們下面給出相關(guān)的記號：”個工件的集合j 2 “，以，以) ， 機(jī)器有一次速率改變行為，它的起始時間是r ，進(jìn)行需要的時間是上。所有工件 都在零時刻釋放，工件加工時不允許中斷，l x 4 牛j , 的正常加工時間是只，而在 速率改變行為之后的加工時間為q 只，其中o 5 4 ) 的s p t 近似算法( s h o r t e s tp r o c e s s i n g t i m e ) ，其n p 困難性的證明相對復(fù)雜，而s p t 近似算法是指將工件按照從小到大 順序加工，并盡可能地排在中斷之前。 這個算法最壞情況界是在1 9 9 2 年被c y l e e 等在文獻(xiàn)【3 中證明的，他們還 提供了一個最壞情況緊的例子，同時給了一個較為簡單的困難性證明。 定理2 1 1 ， | i c 是n p 困難的 證明：將奇一偶劃分問題多項式時間歸約到l i j y c , 對于給定的奇一偶劃分問題的實例，x 2 而，屯，x 2 一 ，其中對于所有的 皓1 ，2 ”，o t 2 l ( n - i + 1 ) ( x n l + x 2 ，) + 2 h + l 】m + 柏 + 2 ( n m + z ) + m 】 的l ，島ij g 的實例。 由這個構(gòu)造可以得到1 ，啊l i c 問題的n p 困難性( 具體見文獻(xiàn)【3 】) 。 定理2 2s p t 算法的最壞情況界不超過9 7 。 證明：對于s p t 最壞情況界的估計，還用c y l e e 等文中的記號，記s p t 算法得 到的排在機(jī)器中斷前的工件集為b ，之后加工的_ t - 件集為a ，s p t 排序s 中s - 件z 的完工時問為c ，相應(yīng)的最優(yōu)解中前面j b l 個工件的集合是x ，而其余工件 的集合是y ，最優(yōu)排序s 中工件z 的完工時間為c 。考慮到?jīng)]有機(jī)器中斷時的 完工時間總和以s p t 排序最優(yōu)，他們得出s 在中斷前的空閑時間j 不會超過s 的 空閑時間j ，并由此給出最優(yōu)解和s p t 解的完s - 時間總和的一個比較， q c + ( r l l x 占一j + ) 以及最優(yōu)解的一個估計c 2 ( 掣+ l 艫一萬“，這 樣相對誤差界就有 e = 連乒s 齋器 2 即s p t 算法的最壞情況界不超過9 7 。 另一3 - 面，c y l e e 等人的工作還包括給出一個緊實例：n = 4 ，a 。l ， 島2 馬5 只2 m 21 ，r = m ，上= l ，這個實例按照s p t 排序的完工時間總和 是9 m + 4 ，而最優(yōu)解是7 m + 6 ，這樣當(dāng)m 呻。o 時，該實例的最壞情況界斗9 7 ， 所以s p t 算法最壞情況界就是9 7 。 可以看到，c y l e e 等對最優(yōu)解和算法所得解都是用占一這個數(shù)來估計的， 這個方法在2 0 0 3 年c s a d f i 等人的文章( 文獻(xiàn)【2 ) 中也得到體現(xiàn)，c s a d f i 等人在這篇文章中對于s p t 算法進(jìn)行改進(jìn)得到m s p t 算法，即首先將工件按照s p t 排好，然后通過交換一次機(jī)器中斷前的一個工件和中斷后的一個工件選擇對目標(biāo) 8 第= 章帶維護(hù)時問的平行機(jī)排序問題研究 值最好的情況。 定理2 3m s p t 算法的最壞情況界是2o 17 。 證明：如果記這個算法得到的排序是s ，工件，的完工時間為c ，那么得到的 兩個主要估計就是 q ( l 蘭掣+ 2 ) ( 巧一d ) ，c - z c , + ( j r l 2 ) ( 占一占) 。 由此得到相對誤差界為 s = 避乒崠篙專 另一方面，有實例：”= 7 ，對于i 1 ，2 ) ，口= 1 ；而對于i 3 4 ，5 ，6 ，7 ，a = m ； 并且r = m ，l = 1 。此實例最壞情況界恰是2 0 1 7 ，這樣m s p t 算法的最壞情況 界就是2o 1 7 。 也就是說m s p t 算法改進(jìn)了s p t 的結(jié)果。20 0 5 年y h e ，w y z h o n g ，h k g u 在 文章 2 1 中給出了l ，趣h y , c , 的p t a s ( 這個p t a s 是文章12 3 中算法的拓展) 。 s + 和s 分別表示由最優(yōu)算法和s p t 算法得到的序列。b 表示序列s 中在維護(hù) 時段之前的工件集合；a 表示s 中所有在維護(hù)時段之后的工件集合。x 表示序列 s + 中前f b f 個工件集合，y 表示后f a f 個工件集合。6 和6 分別表示序列s + 和s 中維護(hù)時段前的空閑時段。 定義2 2 1 令a a “k ，k - 交換”程序是指：對序列s ，將a 中的a 個工件與b 中的b 個工件交換，且 b 中的b 個工件總長與6 之和不小于h 中的a 個工件長度之和。經(jīng)過這樣的交換， 維護(hù)時段前后的工件按非遞減的順序重新排列。 算法s p t e ： 1 將所有工件按s p t 規(guī)則排序 2 對任一給定正整數(shù)k ，用“k ，k - 交換”生成新序列 3 在1 和2 步中的兩個序列中選取最好的作為結(jié)果輸出 第二章帶維護(hù)時問的平行機(jī)排序問題研究 當(dāng)令k = l 時，上述算法就是m s p t 算法【23 】因此s i t e 是m s p t 算法的一般 形式。s a d i fe ta 1 f 2 3 】已經(jīng)證明m s p t 算法的最壞情況界為2 0 1 7 。y h e w y z h o n g ，h k g u 【23 給出結(jié)果： 定理2 4 對任意給定的整數(shù)k 2 ，算法s p t e 的最壞情況界至多為1 +! ， 5 + 2 、2 k + 8 時間復(fù)雜性為o ( d ”) 。 由此可知s p t e 是問題1 ，啊h y c , 的一個p t a s 。 第- i 帶維護(hù)時問的平行機(jī)排序問題研究 2 2 2 維護(hù)時段前后機(jī)器加工速率改交 再來看帶有機(jī)器磨損或者學(xué)習(xí)效應(yīng)的情形，此時月也是一個固定的時刻。與 上面不同的是，以上在進(jìn)行“速率改變行為”時工件都不允許加工，而這類情形 下，上：o ，并且工件在速率改變時可以加工，也可以空閑直到速率改變進(jìn)行之 后。 在帶有機(jī)器磨損的情形，有口，2 1 。在2 0 0 1 年t c e c h e n g 等的文章( 文 獻(xiàn)【1 5 1 ) 證明了有機(jī)器磨損的最大完工時間問題是n p 困難的，同時指出了一些 特殊多項式可解的情形。 在有學(xué)習(xí)效應(yīng)耐，o r + a k p k ，那么機(jī)器空f , - j 至, j 時刻r 才開始加工以以及后來 到達(dá)的工件；否則，在以一，之后直接加工以和其余工件。 離線算法 i ： ( 1 ) 將工件重新標(biāo)號，使得啦哆2 c t 。，t = m i n ( j i ：，只 胄) 。 ( 2x 將工件以，以一。加工，執(zhí)行算法a o 的第2 步。 y h e 等在文章中證明了算法a o 的競爭比是2 ，兩算法a i 的最壞情況界是5 4 。 第= 章帶維護(hù)時問的平行機(jī)排序問題研究 2 3 維護(hù)時段可選擇的情況 速率改交時問可選擇，印指r 不再是一個固定的時刻。 此時，分兩種情況：必須有維護(hù)時段，但開始時刻r 可選擇；是否有維護(hù)時 段，可選擇。 c 一y l e e 和v j l e o n 首先在2 0 0 1 年的論文 12 】中分別給了1 l l , m ic ， 1 f l , m i c j ，1 i r m i w j c j 的多項式時間算法，主要利用的是動態(tài)規(guī)劃方法；此外 對于1 lr m i l m a x 還證明是n p 困難的，并且給了一個偽多項式時間算法。 c 一y l e e 和c s l i n 在2 0 0 1 年的文章【1 6 】中假定工件加工時間在維護(hù)發(fā)生 前后保持不變，研究了工件可中斷情況中的1 i i m ，r a i e 【c m a x 】，1 i i m ，r a f e c i 】，1 1 1 7 1 1 1 ，r a i m a x e l i 】，1 l l , m ，r - a i e 【m a x l i 四種情況；對于工件不可中斷的 情況研究了1 ir i b ，i l l 一a i e 【c m a x ，1 lr m ，n 1 一a i e 【c - 】，1 ir m ，n r - a i m a x e 【l i ， 1 l l - m ，i l l - 一a l e 【m a x l i 。文章研究上述各種情況所具有的特殊性質(zhì)，并得到了一些 有益的結(jié)論： ( i ) 目標(biāo)為最小化期望最大完工時問的情況，若r 的分布函數(shù)f ( x ) 是凹函 數(shù)，按s p t 規(guī)則得到的工件序列是最優(yōu)的；若r 的分布函數(shù)f ( x ) 相對于工件加 工時間總和是凸函數(shù)時，按l p t 規(guī)則得到的工件序列是最優(yōu)的。 ( i i ) 目標(biāo)為最小化總期望完工時間的情況，若r 的分布函數(shù)f ( x ) 是凹函數(shù)， 按s p t 規(guī)則得到的工件序列是最優(yōu)的。 ( i i i ) 目標(biāo)為最小化最大期望誤工時間的情況，當(dāng)工件序列滿足“l(fā) , e v e l , s e - a g r e e a b l e ”假設(shè)時，若r 的分布函數(shù)f ( x ) 是凹函數(shù)( 或凸函數(shù)) ，按e d d 規(guī)則得 到的工件序列是最優(yōu)的。 y h e ，m j i 和t c e c h e n g 在2 0 0 5 年的文章【17 中，分析了目標(biāo)為最小化 最大完工時間和總完工時間的情況下的問題復(fù)雜性： 第二章帶維護(hù)時間的平行機(jī)排序問題研究 t s b l e1 s u m m a r yo f n p - h a r d n e s sr e s u l t s i 蔭l s l = 0s 1 o 夠f 2a 加s i - 0 t a b l e l 中的妒； s 1 ，s 2 ，s m ) 表示r 可以選擇的時刻集合。 文章對目標(biāo)為最小化最大完工時問的情況，給出了偽多項式時間算法和完全 多項式近似方案；對目標(biāo)為完工時間總和的情況，給出了一個特殊情況的偽多項 式時聞算法。 t a b l e2 s u m m a r yo f t h ea l g o r i t h m s 第三章帶周期性維護(hù)時間的平行機(jī)排序問題研究 第三章帶周期性維護(hù)時同的平行機(jī)排序問題研究 3 1 引言 周期性維護(hù)計劃包括定期檢查、定期修理和預(yù)防性維護(hù)。合理的周期性維護(hù) 計劃可以提高生產(chǎn)效率和安全性，從而促進(jìn)產(chǎn)量的提高和對安全的重視。 隨著加工系統(tǒng)越來越多地安排周期性維護(hù)，我們有必要研究在帶有周期性維 護(hù)的系統(tǒng)中如何來安排工件加工順序。l i a o 和c h e n 】1 就曾研究過目標(biāo)為最小 化最大延誤時間的此類問題，他們給出了一個分支定界算法和針對大規(guī)模實例的 啟發(fā)式算法，并通過測試驗證該啟發(fā)式算法有較好的性能。 在m i n 兒，y o n gh e ，t c e c h e n g 的文章 2 0 中，討論了目標(biāo)為最小化 m a k e s p a n 的周期性單機(jī)排序問題。文章證明了經(jīng)典l p t 算法的最壞情況界為2 ， 且該問題不存在最壞情況界小于2 的多項式時問近似算法，即l p t 算法是最優(yōu)離 線算法。 本章中所用的符號于文章 2 0 】統(tǒng)一，t 表示連續(xù)加工時問，t 表示單次維護(hù) 時間，b 表示最優(yōu)解中所用加工時段數(shù)，b 表示l s 算法中所用加工時段數(shù)。 第三章帶周期性維護(hù)時問的平行機(jī)排序問題研究 3 2 單臺機(jī)的曩佳在線算法 在文章m i nj i ，y o n gh e ，t c e c h e n g ，s i n g l e m a c h i n es c h e d u l i n gw i t h p e r i o d i cm a i n t e n a n c et om i n i m i z em a k e s p a n 【2 0 】中證明了單臺機(jī)帶周期性維 護(hù)時問離線情況下，”t 算法是最優(yōu)的。接下來，我們將證嘆在線情況下，l s 算法是最優(yōu)的。 3 2 1 復(fù)雜性證明 c y l e e 在他的一篇文章中提過該問題的復(fù)雜性，但未做證明，在此重新證 明作為補(bǔ)充。 定理3 2 1 ：p 1 i p e r i o d i c m a i n t e n a n c e i c m a x 是強(qiáng)n p 難的。 證明：我們將該問題多項式時間歸約到“三元劃分問題”。 對任一“三元劃分問題”的實例i ： 有3 m 個元素的有窮集合a ， _ a l ，a 2 ，a 0 ：，a i = m t ，且對任意i = l ，2 ，3 m 有t 2 a i t 4 問：a 是否能分成m 個不相交的集合s ，s ：，s 一 使得1 j m ，e a ies ja i = t ? 構(gòu)造上述問題的一個實例i ： 機(jī)器連續(xù)加工時間為t ，每次維護(hù)時間為t 有工件p - ，p 2 ，p h ( 滿足p i = a i ，對任意1 i t 4 ，所以每個加工時段內(nèi)恰好有三個工件( 工件長度之和 為t ) 。于是，得知實例i 中a 必存分成m 個不相交的集合s l ，s 坼s 一，使 得使得1 j m ，a i es ja i f t 。 充分性：如果 是能分成m 個不相交的集合s t ，s ：，s ，使得1 j ：c j + ：，a j = ：，( c j + a j ) t b + 矛盾，說明引理3 2 2 成立 一 定理3 2 2 ：對于p l l p e r i o d i c m a a i n t e n a n c e l c m a x 問題，r l s = c l s c o p t 2 。 證明：1 ，b t 1 時，必有b = l ，此時c l s c o p t = i 2 時，由引理3 2 2 可得，b _ b b 一1 ( 1 ) 若b - b * b * - i c l s ( b - 1 ) ( t + t ) + y c o p t( b 一1 ) ( t + t ) + x 其中y 表示l s 算法中最后一個加工時段內(nèi)所有工件總長；x 表示最優(yōu)解 中最后一個加工時段內(nèi)所有工件總長。 由b - b * b * 一1 得b - 1 2 ( b 一1 ) ，又因為b 、b 是整數(shù)，所以b 2 ( b 一1 ) 。 c l s ( b - 1 ) t 2 f f i ( b 一1 ) t 。最優(yōu)解中酋b * - i 個 加工時段內(nèi)的工件總長”。再聯(lián)合假設(shè)y x ，得最優(yōu)解中工件總長小于 l s 算法中工件總長，這與實際矛盾，說明假設(shè)y x 不成立，印y 2 ) 內(nèi)加工，則之后沒有新工件， 有c d c o r r = ( n - i ) ( t + t ) + 5 】一o o ( 一0 ) ，其中n 2 。 2 ，算法a 將工件p l = 6 放在第一個加工時段內(nèi)，當(dāng)工件p 2 = t 到達(dá)時只能 放在第二個及以后的加工時段內(nèi)，設(shè)其放在第n 個時間段( n 2 ) 內(nèi)加 工，此時 有c c o p r 一 t + ( n 一1 ) ( t + t ) ( t + t + ) 一n ( t 一* ) ，其中n 2 。 3 、綜合1 ，2 得在線情況問題下界為2 。 一 小結(jié)：由定理3 2 。2 和定理3 2 3 的結(jié)論可知l s 算法是 p 1i p e r i o d i c - m a i n t e f l a n c ei c m a x 問題在線情況下的最優(yōu)算法。 第三章帶周期性維護(hù)時聞的平行機(jī)排序問題研究 3 3 兩臺機(jī)問題討論 3 3 1 復(fù)雜性證明 兩臺機(jī)器復(fù)雜性證明與單臺機(jī)器的情況是類似的。 定理3 3 1 ：p 2 i p e r i o d i c 一眥i n t e n a n c e i c m a x 是強(qiáng)n p 難的。 證明：我們將該問題多項式時間9 3 約到“三元劃分問題”。 對任一“三元劃分問題”的實例i ： 有3 m 個元素的有窮集合a ，a f f i a ，a 2 ，a 0 ：，a l - - - m t ，且對任意i l l ，2 ，3 m 有t 2 a i t 4 問：a 是否能分成m 個不相交的集合sz ，s ：，s 。 使得1 j m ，ea jes ja i f f i t ? 構(gòu)造上述問題的一個實例i ： 機(jī)器連續(xù)加工時間為t ，每次維護(hù)時間為t 有工件p 1 p 2 p 4 ( 滿足p i f f i a i ，對任意1 i t 4 ，1 i 3 m ，所以每個加工時段內(nèi)恰好有三個 工件( 工件長度之和為t ) 。進(jìn)而得：實例i 中a 能分成m 個不相交的集合 s l ，s 2 ，s ，使得1 j m ，a es ja i f t 。 充分性：若實例i 中a 能分成m 個不相交的集合s ，s z ，s ，使得1 j m ，a ies ja i = t 。可得實例i 中工件p - ，p 2 p n 能恰好放入m 個加工時 段，而工件p z ，p * ：p i 也恰好使用了m 個加工時段，于是c m a x f f i a l t + ( m _ 1 ) t ，即實例i 中問題的回答是肯定的。 又因為“三元劃分問題”是強(qiáng)n p 難的，所以到p 2 i p e r i o d i c - m a i n t e n a n c e l c m a x 問題也是強(qiáng)n p 難的。 第三章帶周期性維護(hù)時間的平行機(jī)排序問題研究 3 3 2 一般情況下不存在常數(shù)界多項式時問算法 上節(jié)已經(jīng)證明該類問題單臺機(jī)情況下有競爭比為2 的最優(yōu)近似算法，而兩臺機(jī)器 時情況卻大不一樣，不存在常數(shù)界近似算法。 定理3 3 2 ：p 2 fp e r i o d i c - m a i n t e n a n c e l c m a x 問題不存在常數(shù)界算法。 證明- 反證法，假設(shè)存在該問題一般情況下的常數(shù)界( c ) 多項式時問算法 ， 即“( i ) c o r r ( i ) c ，對任意實例i 。 對任一。劃分問題”的實例i ： 有2 m 個元素的有窮集合b ，b = ( a ，a ：，a 。) a i z + ，1 i c a c ( t + t + 1 ) c t ，即“二 元劃分問題”無解。 于是算法a 可在多項式時間內(nèi)求解“二元劃分問題”，這與“二元劃分 問題”為n p 難，矛盾，說明不存在這樣的算法 。 即p 2 ip e r i o d i c - m a i n t e n a n c ej c m a x 問題不存在常數(shù)界多項式時間算法。 第三章帶周期性維護(hù)時問的平行機(jī)排序問題研究 3 3 3 離線算法及其參數(shù)界 由于一般情況下p , 1 p e r i o d i c - m a i n t e n a n c e c m a x 問題不存在常數(shù)界算法 自然想到考慮該問題的參數(shù)界。這里我們令c 【= t t 算法 ：( 1 ) 將維護(hù)時段按圖示編號，工件加工對按編號順序放入維護(hù)時段 - - i：i： 二：i( 二： 二： 1 2 l1 4 12 k ) m i一 ( 2 ) 用f f d 算法將工件排序 定理3 3 3 算法a 的參數(shù)界為r - - m a x ( 2 ，8 5 + 6o 【5 ) 證明：令符號( i ) 表示b = 2 k ，k + 1 ；( i i ) 表示b = 2 k 。- 1 ，k 1 ； ( i ) 表示b f f i 2 k ，k 1 ；( i i ) 表示b = 2 k - i ，k 1 將排好順序的加工時段看做箱子，則b 表示用f f d 算法排序時使用的箱子數(shù)，b 表示最優(yōu)算法排序時使用的箱子數(shù)。 接下來分四種情況討論算法a 的參數(shù)界： ( i ) ( i ) ：此時c = ( k - 1 ) ( t + t ) + x ，c z ( k - i ) ( t + t ) + y ，其中x t 2 ，y t + t + x 3 t 2 + t ，于是c t 2 ，y c t 因為b 3 b 2 ，于是k 3 k 2 + 1 2 = 2 + 3 ( c 一x ) ( 2 t + 2 t ) c t + t + 3 c 2 - 3 x 2 + y 2 t t 3 = 5 t 3 ，得 c c ( 4 t 3 + t ) ( 5 t 1 6 ) = 8 5 + 6a 5 2 2 第三章帶周期性維護(hù)時間的平行機(jī)排序問題研究 k = 2 ，k = 3 時，c = t + t + x ，c = 2 ( t + t ) + y ，因為x t 2 ，y t ，于是c 2 c k 3 時，c 2 t + 2 t + x s t 2 + 2 t ，于是c o ，y t 因為b 3 b 。2 ，于是k t + t + x 3 t 2 一t 2 ，于是c 2 c ( i i ) ( i i ) ：此時c = ( k - 1 ) ( t + t ) + x ，c ；( k - 1 ) ( t + t ) + y ，其中x o ，y t 因為b 3 b 2 ，于是k 3 k 2 - 1 4 = 3 【1 + ( c 一x ) ( t + t ) 】2 1 4 c 3 c 2 + 5 ( t + t ) 4 - 3 x 2 + y 3 c 2 + 9 t 4 + 5 t 4 k 5 t + 5 t + x 9 t 2 + 5 t 2 ，于是c 2 c 2 3 參考文獻(xiàn) 參考文獻(xiàn) 【1 】m p i n e d o s c h e d u l in g ：t h e o r y a ig o r i t h m sa n ds y s t e m s p r e n i c eh a l l , 19 9 5 【2 】c s a d f i ，e p e n z ，c r a p i n e ，j b l a z e w i c z ，p f o r m n o w i c z ，a ni m p r o v e da p p r o x i m a t i o n a l g o r i t h mf o r t h es i n g l em a c h i n et o t a lc o m p le t i o nt i m es c h e d u l i n gp r o b l e mq i t h a v a i l a b l i t yc o n s tr a i n ts ，e u r o p e a n j o u n a lo f o p e r a t l o n a l r e s e a r c h , 20 0 5 ，1 6 1 ：3 - 1 0 【3 c y l e e ，s d l i m n s i n g l em a c h i n ef l o w - ti m es c h e d u li n gw it hs c h e d u l e dm a i n t e n a n c e ，a c t si n ，o r m a t j