（系統(tǒng)工程專業(yè)論文）VLSN在帶有模糊交貨期的單機(jī)調(diào)度問(wèn)題中的應(yīng)用.pdf

東北大學(xué)碩士論文摘要 摘要 本文討論了帶有模糊交貨期的單機(jī)調(diào)度問(wèn)題，目標(biāo)函數(shù)是總加權(quán)滿 意程度最大化。帶有模糊交貨期的單機(jī)調(diào)度問(wèn)題的條件假設(shè)如下：n 個(gè) 工件以，以，。要在一臺(tái)機(jī)器上加工，機(jī)器每次只能加工一個(gè)工件，工件 之間不具有優(yōu)先關(guān)系，在開(kāi)始階段所有的工件都可以加工，并且工件一 旦被加工，不允許中斷，工件的加工時(shí)問(wèn)依次為p 。，p ：，n ，交貨期依 次為( d l ，d 。+ q ) ，( 吐，畋+ p 2 ) ，( 以，以+ g 。) ，權(quán)值依次為嵋，k ，完成時(shí) 間為c l ，c 2 ，e ，對(duì)于每個(gè)工件根據(jù)它的完成時(shí)間定義一個(gè)滿意程度 ( c ，) ，目標(biāo)函數(shù)為m f l t x w ，蘆( c ，) ，這是一個(gè)n p - 難問(wèn)題，我們用啟發(fā)式 。 面。 算法尋找近優(yōu)解。本文對(duì)模糊集在帶有模糊交貨期調(diào)度中的應(yīng)用作了綜 述，在i s h i b u c h i1 9 】的基礎(chǔ)上討論了在一定條件下，總加權(quán)滿意程度最大 化與加權(quán)拖期最小化之間的關(guān)系。提出了在一定條件下，帶有模糊交貨 期單機(jī)調(diào)度問(wèn)題中的統(tǒng)治規(guī)則，兩個(gè)定理和三個(gè)推論。介紹了大規(guī)模鄰 域構(gòu)造的基本思想，并證明基于交換和單向插入所構(gòu)造的兩種鄰域是指 數(shù)鄰域，即大規(guī)模鄰域。討論了大規(guī)模鄰域?qū)τ诮獾馁|(zhì)量改進(jìn)的作用及 其基于動(dòng)態(tài)規(guī)劃思想的求解方法d y n a s e a r c h 。并舉例說(shuō)明大規(guī)模鄰域與 傳統(tǒng)鄰域之間的區(qū)別。也即是大規(guī)模鄰域的優(yōu)點(diǎn)。實(shí)現(xiàn)了兩種d y n a s e a r e h 算法。通過(guò)例題對(duì)大規(guī)模鄰域求解的算法d y n a s e a r c h 的步驟進(jìn)行了說(shuō)明。 為了得到更好的解。把d y n a s e a r c h 算法與迭代局域搜索算法相結(jié)合，即 是迭代d y n a s e a r c h 算法。對(duì)于迭代局域搜索算法中的擾動(dòng)策略即在k i c k 策略中引入了誤差限制，對(duì)k i c k 后的滿足限制條件的點(diǎn)進(jìn)行局域搜索， 否則重新進(jìn)行k i c k 的思想，實(shí)驗(yàn)表明這種思想還是有一定作用的。本文 還討論了把統(tǒng)治規(guī)則與局域搜索相結(jié)合的兩種方式：( 1 ) 對(duì)初始解應(yīng)用 統(tǒng)治規(guī)則，改善初始解的性能：( 2 ) 對(duì)k i c k 后的點(diǎn)應(yīng)用統(tǒng)治規(guī)則。 通過(guò)實(shí)驗(yàn)表明，統(tǒng)治規(guī)則與初始解的結(jié)合對(duì)解的質(zhì)量在不增加計(jì)算 時(shí)間的情況下有明顯的改善；嵌入統(tǒng)治規(guī)則的k i c k 迭代算法在不影響解 的質(zhì)量的情況下能夠減少程序的運(yùn)行時(shí)間；基于交換d y n a s e a r e h 鄰域的 l l 東北大學(xué)碩士學(xué)位論文摘要 i l s 算法比基于插入d y n a s e a r c h 鄰域的i l s 算法好，并優(yōu)于此問(wèn)題的以 交換為鄰域的多初始點(diǎn)改進(jìn)算法。 關(guān)鍵詞單機(jī)調(diào)度交換插入模糊交貨期加權(quán)滿意程度 統(tǒng)治規(guī)則大規(guī)模鄰域動(dòng)態(tài)規(guī)劃d y n a s e a r c h 迭代局域搜索接受準(zhǔn)則多點(diǎn)改進(jìn)算法 1 1 1 東北大學(xué)碩士論文a b s t r a c t a b s t r a c t t h ep a p e ri sar e s e a r c ho ns i n g l em a c h i n es c h e d u l i n gp r o b l e mw i t h f u z z yd u e - d a t e s t om a x i m i z et h et o t a l w e i g h t e d s a t i s f a c t i o nl e v e l w e c o n s i d e rt h e p r o b l e m o f s c h e d u l i n g 行j o b s f o r p r o c e s s i n g w i t h o u t i n t e r r u p t i o n ，o nas i n g l em a c h i n et h a tc a np r o c e s so n l yo n ej o ba tat i m e f o re a c hj o bj o i 。j ，2 ，玎) ，l e tp jb e t h e p r o c e s s i n gt i m e ，面b e t h e s a t i s f a c t o r yd u ed a t e ，e jb e t h eo p t i m i s md u ed a t e ，白b et h ec o m p l e t i o nt i m e a n d w jb et h eb e n e f i to c c u r r e df o re a c hu n i to f s a t i s f a c t i o nl e v e l e a c h j o b h a sa s a t i s f a c t o r y l e v e l p ( c jj f o ri t s c o m p l e t i o n t i m e t h eo b j e c t i v e + n f u n c t i o ni st om a x i m i z et h et o t a l w e i g h t e ds a t i s f a c t o r y l e v e l w j u ( c j ) ， j z l w h i c hi sn p - h a r d i nt h i sp a p e r ，t h er e l a t i o nb e t w e e nt h em a x i m i z a t i o no f t o t a lw e i g h t e ds a t i s f a c t i o na n dt h em i n i m i z a t i o no ft o t a lw e i g h t e dt a r d i n e s s u n d e rs o m ec o n d i t i o ni sd i s c u s s e db a s e do ni s h i b u c h i 【9 1 t h e r ei 。sa l s oa n a n a l y s i sa n ds u r v e yo nt h ea p p l i c a t i o no ff u z z ys e t si nf u z z yd u ed a t e si nt h e p a p e r i nt h i s p a p e r w ep r o p o s et w od o m i n a n c er u l e sf o rt h e s i n g l e m a c h i n ef u z z ys c h e d u l i n gp r o b l e ma sw e l l ，a n dg e tt h r e ed e d u c t i o n so ni t m o r e o v e r , t h ep a p e ri n t r o d u c e ss o m ef u n d a m e n t a lc o n c e p t so ft h em e t h o di n w h i c ht h ev e r yl a r g es c a l en e i g h b o r h o o d ( v l s n ) i sc o n s t r u c t e d ，a n dp r o v e s t h a tt h es i z eo ft h e n e i g h b o r h o o d i s e x p o n e n t i a l ，w h i c h m e a n st h e n e i g h b o r h o o d i s v e r yl a r g e f u r t h e r m o r e ，t h ep a p e rp r e s e n t s t h e d y n a s e a r c ha l g o r i t h mw h i c hi sb a s e d o nd y n a m i cp r o g r a m m i n gt os e a r c ht h e l o c a l o p t i m a l s o l u t i o no ft h e n e i g h b o r h o o d ，a n ds h o w st h ed i f f e r e n c e s b e t w e e nt h ev l s na n dt h et r a d i t i o n a ln e i g h b o r h o o db yan u m e r i ce x a m p l e ， w h i c hi st h ea d v a n t a g eo fv l s n i na d d i t i o n ，t h e r ei sa ni l l u s t r a t i o no ft h e d y n a s e a r c ha l g o r i t h mb ya ne x a m p l ei nt h ep a p e r t oi m p r o v et h eq u a l i t y o ft h e s o l u t i o n ，w e f i r s tc o m b i n et h e d y n a s e a r c ha l g o r i t h mw i t hi t e r a t e d l o c a ls e a r c hi nw h i c ht h ek i c k s t r a t e g y i s e m b e d d e d ，a n dt h i s k i n do f 東北大學(xué)碩士學(xué)位論文a b s t r a c t a l g o r i t h mh a s b e e nn a m e di t e r a t e d d y n a s e a r c hi n s o m ep a p e r s t h e nw e c o m b i n et h ed o m i n a n c er u l ew i t ht h ei t e r a t e dd y n a s e a r c ha l g o r i t h mt h r o u g h t h et h r e ef o l l o w i n gm e t h o d sa sw e l l ：1 ) a p p l y i n gd o m i n a n c er u l et ot h e i n i t i a ls o l u t i o n ；2 ) a p p l y i n gd o m i n a n c er u l et ot h es o l u t i o nk i c k e d t h er e s u l t so fe x p e r i m e n t ss h o wt h a tt h ef i r s tc o m b i n a t i o ni s v e r y u s e f u lt oi m p r o v et h eq u a l i t yo ft h ef i n a ls o l u t i o nw i t h o u ti n c r e a s i n gt h e o p e r a t i o nt i m e ，a n dt h es e c o n do n ec a nr e d u c et h et i m ec o n s u m e db yt h e p r o g r a m w i t h o u t d e c r e a s i n g t h e q u a l i t y o fs o l u t i o n s t h e r ei sa l s oa c o m p a r i s o n o ft h ei t e r a t e d d y n a s e a r c h a n dm u l t i - s t a r t i m p r o v e m e n t a l g o r i t h m ，a n di ts h o w s t h a tt h ef o r m e ri sp r i o rt ot h el a t t e r k e yw o r d s ：f u z z yd u ed a t e s ，d y n a s e a r c hs w a p ，i n s e r t ，d o m i n a c er u l e ， v e r yl a r g e s c a l en e i g h b o r h o o d ( v l s n ) ，d y n a s e a r c h ，i t e r a t e dl o c a ls e a r c h ， w e i g h t e d s a t i s f a c t i o n l e v e l ，a c c e p t a n c er u l e ，r a n d o m k i c k ，i t e r a t e d d y n a s e a r e h ，m u l t i s t a r ta l g o r i t h m v 東北大學(xué)碩士學(xué)位論文 聲明 聲明 本人聲明所呈交的學(xué)位論文是在導(dǎo)師的指導(dǎo)下完成的。論文中取 得的研究成果除加以標(biāo)注和致謝的地方外，不包含其他人已經(jīng)發(fā)表或 撰寫(xiě)過(guò)的研究成果，也不包括本人為獲得其他學(xué)位而使用過(guò)的材料。 與我一同工作的同志對(duì)本研究所做的任何貢獻(xiàn)均已在論文中作了明確 的說(shuō)明并表示謝意! 本人簽名：7 娶形浼 日期：壚中2 f 東北大學(xué)碩士學(xué)位論文第一章緒論 第一章緒論 自從z a d e h ! 】先生在1 9 6 5 年發(fā)表第一篇關(guān)于模糊集的論文以來(lái)， 模糊集合已經(jīng)被廣泛的應(yīng)用于各個(gè)領(lǐng)域，從那時(shí)起已經(jīng)有7 0 0 0 多篇關(guān)于 模糊集的論文、報(bào)告、?？蜁?shū)籍出版。旱些時(shí)候，人們關(guān)于模糊集的 研究還是屬于用模糊集來(lái)描述人們認(rèn)知過(guò)程中的不確定性?，F(xiàn)在，模糊 集已經(jīng)應(yīng)用到工程、商業(yè)、醫(yī)藥科學(xué)和自然科學(xué)等領(lǐng)域。過(guò)去幾年里， 模糊集已經(jīng)成功地應(yīng)用于生產(chǎn)管理領(lǐng)域。模糊集已經(jīng)被看作是一種建模、 求解問(wèn)題的很重要的技巧。有很多研究者把模糊集用于解決調(diào)度問(wèn)題。 1 1 問(wèn)題的來(lái)源及研究目的 本論文的研究課題來(lái)源于國(guó)家自然科學(xué)基金項(xiàng)目基于v l s n 的智 能i l s 優(yōu)化方法及其在調(diào)度中的應(yīng)用研究( 6 0 2 7 4 0 4 9 ) 。 本論文的目的是研究帶有模糊交貨期的單機(jī)調(diào)度問(wèn)題，目標(biāo)函數(shù)是 總加權(quán)滿意程度最大化。并把v l s n 應(yīng)用于該問(wèn)題。完成了兩種v l s n 的算法，并與統(tǒng)治規(guī)則相結(jié)合，改進(jìn)算法的性能。最后對(duì)算法進(jìn)行了分 析和比較。 1 2 單機(jī)調(diào)度問(wèn)題 調(diào)度問(wèn)題是運(yùn)籌學(xué)的一個(gè)分支。其主要目的是在滿足一定的技術(shù)與 資源約束的條件下對(duì)操作的排序，按照排序的次序給操作分配資源和時(shí) 間，使某個(gè)預(yù)定目標(biāo)達(dá)到最優(yōu)或近優(yōu)。調(diào)度問(wèn)題主要集中在車間的計(jì)劃 與調(diào)度方面，許多學(xué)者作了大量研究，出了不少的研究成果。制造系統(tǒng) 的生產(chǎn)調(diào)度是針對(duì)一項(xiàng)可分解的工作( 如產(chǎn)品制造) ，探討在盡可能滿足 約束條件( 如交貨期、工藝路線、資源情況) 的前提下，通過(guò)下達(dá)生產(chǎn)指 令，安排其組成部分( 操作) 使用哪些資源、其加工時(shí)間及加工的先后順 序，以獲得產(chǎn)品制造時(shí)間或成本的最優(yōu)化。在理論研究中，生產(chǎn)調(diào)度問(wèn) 題常被稱為排序問(wèn)題或資源分配問(wèn)題。自從2 0 世紀(jì)5 0 年代，j o h n s o n 1 東北大學(xué)碩士學(xué)位論文第一章緒論 第一次提出了求解流水車間兩臺(tái)機(jī)器下排序問(wèn)題最優(yōu)解的法則，計(jì)算機(jī) 和制造系統(tǒng)的調(diào)度問(wèn)題已經(jīng)成為廣泛研究的主題。但是根據(jù)具體應(yīng)用背 景的不同，調(diào)度理論的應(yīng)用范圍已經(jīng)超越了計(jì)算機(jī)和制造系統(tǒng)，而涉及 到農(nóng)業(yè)、醫(yī)療業(yè)、運(yùn)輸業(yè)和航天業(yè)等領(lǐng)域。調(diào)度的對(duì)象也由開(kāi)始的機(jī)器 上的加工工序拓展為交通中的運(yùn)輸工具、學(xué)校中的課程、醫(yī)院中的病床 或手術(shù)，及c p u 處理中的進(jìn)程。 調(diào)度問(wèn)題在各行各業(yè)的廣泛應(yīng)用引起了人們的濃厚若趣，在運(yùn)籌學(xué)、 應(yīng)用數(shù)學(xué)、計(jì)算機(jī)科學(xué)、生產(chǎn)管理科學(xué)、人工智能以及工程科學(xué)等領(lǐng)域， 大量新的文獻(xiàn)不斷涌現(xiàn)1 2 ，由此可見(jiàn)調(diào)度研究的重要性。隨著科學(xué)技術(shù) 日新月異的變化和社會(huì)經(jīng)濟(jì)的發(fā)展，在一定程度上決定生產(chǎn)經(jīng)營(yíng)過(guò)程能 否穩(wěn)定高效運(yùn)轉(zhuǎn)的調(diào)度問(wèn)題的復(fù)雜性和重要性不斷提高。 實(shí)際情況中經(jīng)常有這樣的情況：一些待完成的工作需要在唯一的加 工設(shè)備資源上完成。機(jī)器一次只能處理一項(xiàng)工作，各工作之間是相互獨(dú) 立的。在一臺(tái)機(jī)器上進(jìn)行工作的調(diào)度在理論和實(shí)際問(wèn)題中都具有重要意 義。研究單機(jī)問(wèn)題的理論是理解更大規(guī)模的多機(jī)調(diào)度問(wèn)題性質(zhì)的重要模 塊。研究單機(jī)問(wèn)題的排序方法對(duì)研究復(fù)雜問(wèn)題的有指導(dǎo)性作用，并且為 處理復(fù)雜的排序闖題提供了近似算法。 實(shí)際上，單臺(tái)機(jī)器的排序問(wèn)題也是存在的。例如，一組工人修理幾 臺(tái)損壞了的機(jī)器。幾艘輪船等待停靠一個(gè)碼如一個(gè)考生要做幾道考題， 幾個(gè)人等待一臺(tái)機(jī)器復(fù)印資料等，都可以歸結(jié)為單臺(tái)機(jī)器排序問(wèn)題。在 工業(yè)生產(chǎn)中，也存在類似的問(wèn)題。如，一臺(tái)進(jìn)行流程式生產(chǎn)的工廠，每 次只能生產(chǎn)一種產(chǎn)品。這種情況可以看作單臺(tái)機(jī)器的排序問(wèn)題。對(duì)于有 多臺(tái)機(jī)器的工廠或車間，往往有一臺(tái)關(guān)鍵車床。它的作用的發(fā)揮，會(huì)直 接影響到全廠產(chǎn)品的生產(chǎn)。這時(shí)，整個(gè)工廠或車間生產(chǎn)安排問(wèn)題的焦點(diǎn) 就在這臺(tái)關(guān)鍵車床上。這也是可以按單臺(tái)機(jī)器的排序問(wèn)題來(lái)考慮。 1 3 模糊模型的作用 在任何一門(mén)學(xué)科中，模糊模型的作用【2 6 1 究竟是什么呢? 貝爾曼 ( r e b e l l e m a n ) 在1 9 7 3 年作了一個(gè)極好的回答： 東北大學(xué)碩士學(xué)位論文第一章緒論 “要想確切地描繪任何現(xiàn)實(shí)的物理狀態(tài)，事實(shí)上是辦不到的。這是 個(gè)公認(rèn)的并經(jīng)過(guò)檢驗(yàn)的事實(shí)。因此，描述( 對(duì)于通訊，作決定，推而 廣之對(duì)于人的一切活動(dòng)都是不可少的) 的主要問(wèn)題是：減少必然會(huì)有的 不確切性，使它達(dá)到無(wú)關(guān)緊要的程度。為了把整個(gè)問(wèn)題描述得詳盡，我 們必須在準(zhǔn)確和簡(jiǎn)明之間取得平衡，既減少?gòu)?fù)雜性而又不過(guò)于簡(jiǎn)單化”。 哥根( j a g o g u e n ) 在1 9 7 4 年說(shuō)得更加準(zhǔn)確：“描述的不確切性并不是 壞事，相反，倒是件好事，它能用較少的代價(jià)傳送足夠的信息，并能對(duì) 復(fù)雜事物作出高效率的判斷和處理。也就是說(shuō)，不確切性有助于提高效 率?！?產(chǎn)生上述看法的原因，是由于系統(tǒng)日益復(fù)雜，不可能精確地描述它， 因此產(chǎn)生了所謂互克性原理。這里，我們從扎臺(tái)( l a z a d e h ) 1 9 7 3 年的一 篇論文中摘錄一段話來(lái)說(shuō)明。 “從本質(zhì)上說(shuō)，互克性原理的要旨是：當(dāng)系統(tǒng)日益復(fù)雜，人們對(duì)它 作精密而有意義的描述的能力將相應(yīng)地降低，以至達(dá)到精密性和有意義 ( 或適用性) 成為兩個(gè)幾乎互相排斥的特征的地步。在這種意義下，對(duì) 人文系統(tǒng)特性精密的數(shù)量化描繪，對(duì)現(xiàn)實(shí)世界中社會(huì)的、政治的、經(jīng)濟(jì) 的以及其他形式的問(wèn)題，都不會(huì)產(chǎn)生多大的適用性。這里說(shuō)的人或指?jìng)€(gè) 人或指一群人?！?模糊集之所以成為模擬和分析決策系統(tǒng)的一種方法，是由于模糊集 能夠在質(zhì)量和數(shù)量上模擬模型中的模糊性和不確定性，從而引起了生產(chǎn) 管理研究者的極大興趣。一些研究者指出了模糊集在以下領(lǐng)域具有極大 的潛力：新產(chǎn)品的開(kāi)發(fā)，設(shè)備的選址和布局，生產(chǎn)調(diào)度和管理，庫(kù)存管 理，質(zhì)量和費(fèi)用的效益分析。同時(shí)他們也指出模糊集應(yīng)用于生產(chǎn)管理的 三個(gè)主要原因：首先是決策者對(duì)于所研究問(wèn)題的認(rèn)識(shí)存在著模糊性和不 確定性；其次，在生產(chǎn)管理中，需要考慮的模型的目標(biāo)，決策變量，約 束和參數(shù)可能存在不確定性和無(wú)法準(zhǔn)確計(jì)算；第三，由于人們的偏見(jiàn)和 主觀意愿使得可用信息的質(zhì)量和數(shù)量變得模糊和不確定。所阻模糊集可 以成為生產(chǎn)管理研究中的描述性和說(shuō)明性的模型之間的橋梁。 那么，為什么用模糊集而不是概率來(lái)表示這種不確定性呢? 這是因 3 東她走學(xué)磺士學(xué)鎣謗文第一毒毖讖 為： 薹斃，囂予調(diào)凄審憋不磷定娃參數(shù)，熱粟其處避方法是剩燃嘏率摸 型即概率分布來(lái)攢述不確定的參數(shù)，在這種情況下，計(jì)算和優(yōu)化這些模 蘩燕菲鬻醒露魏，著羹簿手不礁定參數(shù)，炎有透避對(duì)囂受上靜穴爨豹數(shù) 據(jù)進(jìn)行分析觀察，才能得到它的概率分布。但是。對(duì)于萊些新產(chǎn)品，豉 禳多皇產(chǎn)戇產(chǎn)瑟，一黧不確定參數(shù)戇壤率努毒是籠法確囊靛。這鞋，哭 能用其他方法來(lái)處理這種模裂。 其次，模鞋集幫穰率是霹令不瓣黲禳念。摸顴幢蓮辮攀耱零龕是穰 糊的，而概率怒指事物的發(fā)生與否怒不確定的。如：日常生活中，經(jīng)常 翳瓣囂萊萊盤(pán)鏹瑟懿禽金量灸霉?fàn)? 9 ，藏霹浚理解凳該梅菇羼予縫金熬 稷度為9 9 9 9 ，即是一個(gè)模糊集；而如果換成該飾品怒純金的概率為 9 9 9 9 ，+ 這蓑怒囂今不弼鵑概念。 最舞，模糊集痘用于調(diào)度問(wèn)題已經(jīng)帶來(lái)很大的方便，并且為廣大研 究者接受。 1 4 模糊集在調(diào)度海燕睪豹庭用 m a r i al i t o i u ! 司提剃，模糊集在調(diào)度巾豹戲翅裔搿個(gè)方越： 1 ) 模型。盡管調(diào)度意味精確定住，但在調(diào)度中一般存在不確定耐。 模耬集溺寒整理互雩孛蠢馨模裁約寨條姊，模糊魏王對(duì)越，模糖交贊期等等。 2 ) 求解確定性模濺。基平模糊邏輯的讖似推驥用來(lái)建立專家系統(tǒng)。 m a r i nl i t o i u 6 】在德戇文章串髭模贛數(shù)建溺予實(shí)辯謖發(fā)鞫囂，撼述熬 一時(shí)間和交貨期等的不確定性，為了求解模型，引入了調(diào)度的滿意水平 稼必癸瓣添數(shù)寒簸毽工律翡攢贛交贊裳饔模耬燕王鼴溪，勞提出了尋我 最好優(yōu)先權(quán)分配的算法。 t a d a h i k om u r a t ae t e 淄討論了滾永車霾瓣繁畜摟贛交貸麓懿多套蠢 的調(diào)度閥題。禚該篇文章中，作者所討論的多目標(biāo)問(wèn)題怒部分工件考 慮捷蘺，攘鬻懲鑲，男舔分藩建藏鬻懲弱；律者月三囊形模贛數(shù)狂砉搽 彤模糊數(shù)分別襲示提前，拖期釉拖期問(wèn)題的模糊交貨期，漿用了一個(gè)參數(shù) p 來(lái)決定滿意永平靜隸屬函數(shù)靜形狀，彳乍者討論了模糊交貨精閎怒靜囂 東北大學(xué)碩士學(xué)位論文第一章緒論 個(gè)目標(biāo)函數(shù)，最小滿意程度最大化和總加權(quán)滿意程度最大化，并指出最 小滿意程度最大化問(wèn)題存在的問(wèn)題及其解決的方法。 i s h i ie t a l i s 研究了兩個(gè)帶有模糊交貨期的調(diào)度問(wèn)題。該文章中的模 糊交貨期采用右梯形模糊數(shù)來(lái)表示。模糊交貨期定義為線性函數(shù)表示工 件完成時(shí)間的滿意水平。其第一個(gè)模型是，個(gè)工件，2 臺(tái)機(jī)器的開(kāi)放車間 的調(diào)度問(wèn)題，目標(biāo)函數(shù)是對(duì)所有工件的滿意程度中的最小值和機(jī)器速度 所產(chǎn)生的費(fèi)用尋找每臺(tái)機(jī)器的最優(yōu)速度和工件的最優(yōu)調(diào)度。第二個(gè)問(wèn)題 是n 個(gè)工件，m 臺(tái)同構(gòu)機(jī)器的開(kāi)放車間的調(diào)度問(wèn)題，目標(biāo)函數(shù)是最小化最 大工件拖期。 i s h i b u c h ie ta 1 【9 】討論了流水車間帶有模糊交貨期的遺傳算法和鄰域 搜索算法，模糊調(diào)度問(wèn)題和一般調(diào)度問(wèn)題的關(guān)系，指出許多一般訶度闖 題可以用模糊調(diào)度的方法重新加以討論，并且指出最大化總滿意程度問(wèn) 題要比最大化最小滿意程度問(wèn)題復(fù)雜得多。i s h i b u c h ie t a l 還討論了用非 線性函數(shù)表示工件完成時(shí)間的滿意程度，目標(biāo)函數(shù)是最大化最小滿意程 度。 h a ne ta l 討論了一個(gè)工件的單機(jī)最大延期問(wèn)題。其中工件帶有模糊交 貨期并且機(jī)器速度是可控的。目標(biāo)函數(shù)是找到一個(gè)最優(yōu)調(diào)度和機(jī)器加工 工件時(shí)的速度使得由于所有工件的完成時(shí)間所造成的不滿意程度和機(jī)器 的速度的費(fèi)用之和達(dá)到最小。用線性函數(shù)表示工件完成時(shí)間的滿意程度。 機(jī)器速度的費(fèi)用定義為電力和，或勞動(dòng)。并用多項(xiàng)式算法求解。 對(duì)于具有模糊交貨期的單機(jī)調(diào)度問(wèn)題。主要有兩個(gè)目標(biāo)函數(shù)：一是 最小滿意程度最大化問(wèn)題，即 m a x m i n g c j j j 其中 c ) 表示工件完成時(shí)間的滿意程度。 另一個(gè)是總加權(quán)滿意程度最大化問(wèn)題，即在做決策的時(shí)候，決策者 需向不同的商家提供產(chǎn)品，根據(jù)不同商家酌定貨量、付款方式、顧客信 譽(yù)等可以把產(chǎn)品即待加工的工件賦以不同的權(quán)值為w ，w 2 c 。決策者 的目標(biāo)是使所有商家的加權(quán)滿意程度之和最大，即最大化總加權(quán)滿意程 度。用式子表示為 5 東北大學(xué)碩士學(xué)位論文第一章緒論 m a x w j # ( c ) j = l ， 在著作排序論【2 7 1 中，討論了單臺(tái)機(jī)器模糊交貨期的排序問(wèn)題的 兩個(gè)問(wèn)題：一是最小滿意度最大化的排序問(wèn)題；另一個(gè)是帶權(quán)總滿意度 的最大化問(wèn)題。對(duì)于最小滿意度最大化的排序問(wèn)題引用t a d a 的結(jié)果給出 了t a d a 算法，并指出用t a d a 算法所得到的工件的排序是最優(yōu)排序。同 時(shí)，他們也討論了最大不滿意度最小化問(wèn)題并引用t a n k a 和v l a c h 的結(jié) 果，給出了該問(wèn)題的l a w l a r 算法，他們指出在所有工件的交貨期都相同 時(shí)，即具有公共交貨期時(shí)最大不滿意度最小化問(wèn)題是n p 難的，在一般 情況下，該問(wèn)題是強(qiáng)n p 難的。對(duì)于帶權(quán)總滿意度的最大化問(wèn)題，他們 討論了特殊情況所有工件的交貨期相同、加工時(shí)間相同時(shí)的求最優(yōu)解的 分配規(guī)則，并指苧：帶權(quán)總不滿意度的最小化問(wèn)題當(dāng)所有工件的加工時(shí)間 不全相等時(shí)是n p 難的。他們還介紹了流水車間的排序問(wèn)題的i s h i b u c h i 和m u t a t e 的遺傳算法。一些研究者指出隨著在模糊集理論基礎(chǔ)上發(fā)展起 來(lái)的模糊推理和模糊控制等得到越來(lái)越廣泛的應(yīng)用，它們成為信息科學(xué) 和系統(tǒng)科學(xué)研究的熱點(diǎn)，模糊排序是值得引起關(guān)注的一種新型排序。 6 東北大學(xué)碩士學(xué)位論文第二章帶有模糊交貨期的單機(jī)調(diào)度問(wèn)題的數(shù)學(xué)模型 第二章帶有模糊交貨期的單機(jī)調(diào)度問(wèn)題 的數(shù)學(xué)模型 本章討論了帶有模糊交貨期的單機(jī)調(diào)度的數(shù)學(xué)模型，用右梯形模糊 數(shù)來(lái)表示模糊交貨期，討論了拖期懲罰和加權(quán)滿意程度之間的關(guān)系。 2 1 單機(jī)調(diào)度模型 單機(jī)調(diào)度問(wèn)題是調(diào)度問(wèn)題中相對(duì)簡(jiǎn)單的一類調(diào)度問(wèn)題，并且有很大 的實(shí)際意義，如在一個(gè)大的系統(tǒng)中存在一臺(tái)瓶頸機(jī)，它的運(yùn)行情況直援 影響到整個(gè)系統(tǒng)的運(yùn)行，從而可以把該系統(tǒng)看作是1 個(gè)單機(jī)調(diào)度問(wèn)題， 使問(wèn)題得到簡(jiǎn)化，減小了問(wèn)題的復(fù)雜性。 一般的單機(jī)調(diào)度問(wèn)題是指：n 個(gè)工件 ，以，j 。要在一臺(tái)機(jī)器上加 工，工件之間不具有優(yōu)先關(guān)系，在開(kāi)始階段所有的工件都可以加工，并 且工件一旦被加工，不允許中斷，工件的加工時(shí)間依次為p ，p 2 ，n ， 交貨期依次為d l , d 2 ，以，權(quán)值依次為w i ，w 2 ，w n ，完成時(shí)間為 c 。，c ：，c 。，機(jī)器每次只能加工一個(gè)工件。 對(duì)于非模糊調(diào)度問(wèn)題，如果工件的完成時(shí)間小于或等于工件的交貨 期，就認(rèn)為決策者滿意，就說(shuō)滿意程度是1 ，如果發(fā)生拖期，就不滿意， 滿意程度是0 。 這時(shí)我們可以定義滿意程度的隸屬函數(shù)來(lái)表示： ， f 1 ，c d 髟戶1 0 c d 但是，在實(shí)際問(wèn)題中，有許多時(shí)候并不是這樣，在未發(fā)生拖期時(shí)， 用滿意程度是1 表示滿意，當(dāng)發(fā)生拖期時(shí)，隨著完成時(shí)間的延長(zhǎng)，滿意 程度逐漸下降，直至最后滿意程度為0 。即是所謂的模糊交貨期問(wèn)題。 為了與這個(gè)實(shí)際情況相符合，我們引進(jìn)模糊集。 我們用模糊集來(lái)定義工件完成時(shí)間的滿意程度的隸屬函數(shù)，或稱為 滿意程度，或稱為滿意水平，圖形如2 1 所示 7 東北大學(xué)碩士學(xué)位論文第二章帶有模糊交貨期的單機(jī)調(diào)度問(wèn)題的數(shù)學(xué)模型 1 圖2 1 右梯形模糊數(shù) f i g 2 1r i g h tt r a p e z o i d a lf u z z yn u m b e r 圖2 1 所示的模糊數(shù)是右梯形模糊數(shù)( t - n u m b e r s ) ，這個(gè)模糊數(shù)最早 由z i m m e r m a n n 2 2 1 給出定義，記為0 ，j + e ) ，這里d 稱為滿意交貨期，d + e 稱為樂(lè)觀交貨期 2 5 1 ，完成時(shí)間的滿意程度的函數(shù)表達(dá)式為： 五= 乒( c ) = l ，c d p 0 c d d c s d + e d + p 0 ，所以定理成立。 3 ) 對(duì)于第五種情況，此時(shí)有第i 個(gè)工件的開(kāi)始加工時(shí)問(wèn)f 滿足 以o ) 一p 。o ) 一p 。c ，) t d o ( 0 一辦o ) 一兒，隱含著以“) - d o ( 0 ，此時(shí)式( 1 ) 左端 項(xiàng)小于0 ，( 1 ) 不成立，所以工件盯o ) 在盯( f ) 之前而從表中也可以直接 得到a 。 0 ，所以定理成立。 4 ) 對(duì)于第六種情況，此時(shí)工件盯c ，) 無(wú)論是否與工件盯( f ) 交換都發(fā)生 拖期，工件盯o ) 不發(fā)生拖期，即有第f 個(gè)工件的開(kāi)始加工時(shí)間，滿足 t d 一( 一) 一p 。( 一) 一p 一“) 且d 。( j ) 一p 口 t 這時(shí)定理中的( 3 1 ) 式的左端 。，wo。)。if，一!垡l必=贏(r+辦。，+po,-ao(o)(opp o o ) o ，即( 3 1 ) 式不成立，ip a o )je a o ) p o “ 此時(shí)，f ：一塹p 。) o ，所以工件仃( ，) 在盯o ) 之前； 所以t 件盯( ，) 在仃( f ) 之前；從而定理成立。 5 ) 對(duì)于第七種情況，此時(shí)有第f 個(gè)工件的開(kāi)始加工時(shí)間r 滿足 m a x p o o ) 一p ，o ) 一p ，“) ，d o 一p 。( i ) 一p ，( j ) 蔓f m i n d ，( 。) 一p 。( i ) ，d o ( j ) - p ，) j 此時(shí)( 4 ) 式 ，= 等( f + p c ( o + p o o ) - d 一( o ) 一等h 也曠，) 由定理?xiàng)l件，若( 1 ) 成立，即 墜f 1 一虹型竺叢 上址f l 一虹匹塵進(jìn)1 可得 p 一( f ) p 一( ，) i p o )j8 a “) p 一“) l p o ) 等h 礦m 咄，) 等( ，一圳j ) 所以a 。0 ，從而工件口( f ) 應(yīng)在盯o ) 之前，定理成立；反之，若( 1 ) 不成立， 同理可得a 。0 ，所以工件盯( ，) 在盯( f ) 之前，定理仍然成立。 6 1 對(duì)于第八種情況。此時(shí)有第f 個(gè)工件的開(kāi)始加t 時(shí)間f 滿足 m a x d ，o ) 一p ，( ，) 一p ，【，) ，d o o ) 一p o ( i ) 一p 。( ，) ，且， d o o ) 一p 。， 則 鏟等h 咖啊) 一等， 這時(shí)定理中( 1 ) 的條件 監(jiān)一f 1 一虹正蘭叢 上址f l 一亟癥衛(wèi)叢 p 一( 一) p 口o ) 【p 一( j )je o o ) p “j ) l p ?！? j 變?yōu)?東北大學(xué)碩士學(xué)位論文第三章單機(jī)模糊調(diào)度的統(tǒng)治規(guī)則 旦f 1 一鳋三幽 # 一o ) 兒( f ) l 島 k “) e a “) 幾f ， 即 等h ，噸，) 哿， 所以。0 ，從而工件盯( f ) 應(yīng)在盯( ，) 之前，定理成立。 7 ) 對(duì)于第十一種情況，此時(shí)工件盯( f ) 無(wú)論是否與工件仃【，) 交換都發(fā) 生拖期，工件盯o ) 不發(fā)生拖期，即有第f 個(gè)工件的開(kāi)始加q - 時(shí)間f 滿足 t 以( ，) 一p ，( ，) 一p 。( j ) 且d 。( 。) 一p 。( ，) o e ，( 。) p 。( 。) i p o )je 一( o p a ( t ) 而右端 蒜 t 一掣p _ 囂( f + p 州噸) ) o 。 。 p ，f f ) 所以工件盯( ) 在盯c ，) 之前；所以工件d o ) 在盯c ，) 之前；從而定理成立。 8 ) 對(duì)于第十五種情況，第f 個(gè)工件的開(kāi)始加工時(shí)間f 滿足 m a ) 【 d ，o ) 一p 。( 。) ，d ，( ) 一p ，( ，) 一p ?！? ) t d ：“) 一p 。o ) 此時(shí)，當(dāng)( 3 1 ) 成立時(shí) 一塑l f l 一虹業(yè) 上址f l 一虹衛(wèi)蘭進(jìn) e ，( ，) p ，( j ) l p 一“)j 。a ( ，) p a ( j ) ip o )j 1 4 東北大學(xué)碩士學(xué)位論文第三章單機(jī)模糊調(diào)度的統(tǒng)治規(guī)則 所以有 等等g 嘲。+ 脅一) 而 島2 老e 鋤+ 確一) 崠( f 咖嘞) 嵩9 蝴鋤一) 即 島2 等黝老?？? 脅一) 所以a g 0 所以工件盯( f ) 在盯( ，) 之前：當(dāng)定理的條件( 3 1 ) 不成立時(shí)，釓o ， 1 - 件盯c ，) 在工件盯o ) 之前；所以定理成立。 9 ) 對(duì)于第十六種情況，此時(shí)第f 個(gè)t 件的開(kāi)始加工對(duì)嗣r 滿足 m a x d ，o ) 一p ，o ) ，d ，“) 一凡“) ) ! ，l p t p i e j p j 由于e ，= e j ；e ，所以導(dǎo)蘭，從而，p o ， p p ， 所以，推論1 成立。 推論2 ：如果存在一個(gè)所有工件的滿意程度都小于1 的最優(yōu)調(diào)度， 則按2 l 的非增順序捧列工件，可得到這樣的最優(yōu)調(diào)度。 p i e i 證明：反復(fù)應(yīng)用推論l ，即可得到推論2 。 推論3 ：如果有一個(gè)工件的加工時(shí)間p ，滿足d 。s p ，s d ，+ e 且具有最 大的l 值，則至少有一個(gè)最優(yōu)調(diào)度使該工件捧在第一個(gè)位置。 p | e i 證明：假設(shè)工件盯( 七) 具有上述性質(zhì)。用反證法，假設(shè)所有的最優(yōu)調(diào) 度都沒(méi)有把工件盯( 七) 排在第一個(gè)位置，考慮這些最優(yōu)調(diào)度中盯( 七) 位置在 最前面的最優(yōu)調(diào)度，不妨設(shè)為盯。設(shè)盯中在盯o ) 之前的工件為口o ) 。 若工件盯o ) 的滿意程度小于1 ，則由推論2 和假設(shè)可知必有 塑：蘭d l ，這時(shí)交換仃( f ) 和叮 ) 的位置，設(shè)得到的工件次序?yàn)槭希?p a 0 ) p ，0 )p 一恥) p f t ) 則民和盯有相同的總加權(quán)滿意程度，證明如下： 這時(shí) 1 6 東北大學(xué)碩士學(xué)位論文 第三章單機(jī)模糊調(diào)度的統(tǒng)治規(guī)則 色2 等( f 嘲曠咄”) 嵩。嘲”+ 螄一) 嵩。撬嘞) 一等( f + 枷嗍”一) 即 2 等啪嵩腳 由于 鑒地：羔垡2 e ，o ) p 一( i )p 。恤) p ，恤) 所以a 。= 0 ，所以工件次序?yàn)樽顑?yōu)調(diào)度，且盯g ) 在盯( f ) 之前，這與 盯 ) 排在最前面的假設(shè)矛盾a 若工件盯( f ) 的滿意程度為1 ，即有t + p ，o ) 以o ) 考慮交換仃( 七) 和盯( f ) ， 則交換后仃( f ) 的滿意程度必小于1 ，否則，與盯是最優(yōu)調(diào)度矛盾，仍設(shè)得 到的t 件次序?yàn)閛 o 。這時(shí) 2 等( f 一) 嵩f + 啪一) 崠( f + 螄咖一) 即 氣2 等( f 蝴蝴一) 專螄 由于 羔盟s 鑒垡! ， 8 口( f ) p 一( r )e 一“) 兒( ) 所以 又由于 等肌，一等岍0 ， 掣( r + p 刑一以( j ) ) o e 口( r ) 。 所以a ms o ，由于盯是最優(yōu)調(diào)度，所以口= o ，從而，c r o 也是最優(yōu)調(diào) 東北大學(xué)碩士學(xué)位論文第三章單機(jī)模糊調(diào)度的統(tǒng)治規(guī)則 度，且盯 ) 在盯( f ) 之前，這與盯q ) 排在最前面的假設(shè)相矛盾。 所以，推論3 成立。 定理3 2 如果4 = d ，p = p ( f = 1 , 2 棚) ，當(dāng)相鄰兩個(gè)工件盯( f ) 和 盯o ) u = f + 1 ) 滿足( f + 1 ) p w _ l ，與定理l 的證明過(guò)程 1 e l e i 相似，僅僅考慮交換第i 個(gè)和第_ ，個(gè)位置工件，此時(shí)，對(duì)序列中其他工件 的完成時(shí)間沒(méi)有影響，所以，交換前后的工件次序的好與壞，完全取決 于( 3 4 ) 式中的。是大于0 還是小于0 。由于工件的加工時(shí)間與交貨期都 是相同的，所以無(wú)論哪個(gè)工件在前，第i 個(gè)和第，個(gè)工件的完成時(shí)間都是 相同的，第i 個(gè)位置工件的完成時(shí)間為咖，第，個(gè)位置工件的完成時(shí)間 為( i + 1 ) p ，此時(shí)在表3 1 中，只有第l 、6 、1 6 三種情況有可能，分別記 為a 1 ，a 2 ，a 3 ，其余情況是不可能的。下面針對(duì)于這三種情況分別作 討論。 在a 1 條件下，顯然有( 沖1 ) p d 又分為以 下三種情況： a 2 b 1 ：( f + 1 ) p d + p f ，且( f + 1 ) p d + 勺i a 2 8 2 ：d + e x ( f + 1 ) p d + 勺： a 2 8 3 ：d + 印 d + e j 分別討論如下： 在a 2 8 1 條件下，兩個(gè)工件無(wú)論怎樣的次序，前面的工件的完成時(shí) 間都小于滿意交貨期，而后面的工件的完成時(shí)間大于滿意交貨期并且小 于樂(lè)觀交貨期。這時(shí)， 東北大學(xué)碩士學(xué)位論文第三章單機(jī)模糊調(diào)度的統(tǒng)治規(guī)則 。= w 。+ 1 一盥i ! ：；型 一( 吩+ 坼1 一半 ) ：i 蘭一旦l ( ( f + l 掃一d ) 0 l qp 所以，i 在，前優(yōu)于，在i 前，此時(shí)定理成立。 在a 2 8 2 條件下，不滿足定理?xiàng)l件，去掉。 在a 2 8 3 條件下，排在前面的工件的完成時(shí)間小于滿意交貨期，工 件，在i 后面時(shí)，其完成時(shí)間大于樂(lè)觀交貨期，工件i 在_ ，后面時(shí)，其完 成時(shí)間，小于樂(lè)觀交貨期。這時(shí)， ，= w 。+ w j * 0 - ( 一+ 1 一掣 = 詈m + l b d ) 一葉 詈e i - 葉 o 所以，定理成立。 在a 2 8 4 條件下，不滿足定理?xiàng)l件，去掉。 在a 3 條件下，有咖 d ，又分為以下四種情況： a 3 8 1 ：i p d + e iai p d + e j ； a 3 8 2 ：d + e j 咖 d + p ，； a 3 8 3 ：d + e ， i p d + e j ；( 不滿足定理?xiàng)l件，去掉) a 3 8 4 ：d + e j i p ，且d + e l i p ，( 不滿足定理?xiàng)l件，去掉) 其中a 3 8 3 和a 3 8 4 這兩種情況不滿足定理?xiàng)l件，去掉，只考慮a 3 8 1 和a 3 8 2 兩種情況。 在a 3 8 1 條件下，又分為四種情況： a 3 8 1 c 1 ：( f + 1 ) p d + p f ，且( f + 1 ) p d + e j ； a 3 8 1 c 2 ：d + e j ( i + 1 ) p d + e j ，( 不滿足定理?xiàng)l件，去掉) 。 在a 3 8 1 c 1 條件下，此時(shí)兩個(gè)工件無(wú)論哪個(gè)在前，哪個(gè)在后，它們 的完成時(shí)間都大于滿意交貨期，小于樂(lè)觀交貨期。這時(shí) 1 9 東北大學(xué)碩士學(xué)位論文第三章單機(jī)模糊調(diào)度的統(tǒng)治規(guī)則 鏟( 一一等 + _ ( t 一半m 一等卜i ( - 一半 ：j 蘭一蘭i p 0 le fe j 所以，定理成立。 在a 3 8 2 條件下，這時(shí)，把其中矛盾和不符合定理?xiàng)l件的情況去掉， 只有一種情況：d + e j ( i + 1 ) p d + p j ；此時(shí)，工件，無(wú)論在哪個(gè)位置，其完 成時(shí)間都大于樂(lè)觀交貨期，而工件i 無(wú)論在哪個(gè)位置，其完成時(shí)間都大 于滿意交貨期，小于樂(lè)觀交貨期，所以，應(yīng)該有f 在，前，定理成立。 綜上所述，對(duì)于滿足定理?xiàng)l件的相鄰兩個(gè)工件，定理是成立的。 說(shuō)明：定理3 2 中的條件( f + 1 ) p d + q ( f = 1 , 2 ，萬(wàn)一1 ) 是非常重要的， 如果這個(gè)條件不滿足，則定理就不成立。 舉一個(gè)例子說(shuō)明。設(shè)有1 5 個(gè)工件，p = 1 0 0 。d = 1 0 0 0 ，令f - l l ，j = 1 2 ，