具有非交叉維修時(shí)間的平行機(jī)在線排序.pdf

1、本文主要研究的是具有非交叉維修時(shí)間的平行機(jī)在線排序問題。在排序問題中，平行機(jī)排序是其中最活躍的分支之一。無論是對離線的還是在線的，數(shù)十年來人們進(jìn)行了大量的研究。關(guān)于平行機(jī)排序問題的文獻(xiàn)大都是假設(shè)所有機(jī)器自始至終都是可使用的，然而這種假設(shè)在實(shí)踐中可能不現(xiàn)實(shí)。在生產(chǎn)過程中，由于對機(jī)器的預(yù)防性維修或機(jī)器突然出現(xiàn)故障都會(huì)導(dǎo)致機(jī)器在某一段時(shí)間內(nèi)不能使用，有時(shí)候我們也把機(jī)器不能使用的這一段時(shí)間叫做這臺機(jī)器的禁用區(qū)間，所以我們有必要把這些因素考慮到排

2、序問題中去，再做出合理的決策非交叉維修時(shí)間指的是對于m臺平行機(jī)(Parallel identical machines)的集合M={M<,i>|i=1，2，…m)來說，每一臺機(jī)器M<,i>上有一個(gè)維修時(shí)間段[a<,i>,b<,i>)，且0≤a<,i>，i=1，2，…m，并且這m個(gè)維修時(shí)間段滿足或者完全重合或者完全分離，也就是說；或者滿足a<,i>=a，b<,i>=b，a，b是常數(shù)，i：1，2，…m；或者滿足a<,i+1>≥b

3、<,i>，i=1，2，…m-1．在本文的討論中，對于前者我們還假定b-a≤P<,max>，對于后者我們假定a<,i+1>-b<,i>≥Pmax，i=1，2，…m-1，其中p<,max>默是工件集中工件的最大加工時(shí)間。前者所述我們用D1=_{[a<,i>b<,i>)| 0≤a<,i>，a<,i>，b<,i>=b,b-a≤p<,max>，i=1，2，…m)來表示，后者所述用D2={[a<,i>b<,i>)| 0≤a<,i>

4、,i>，a<,i+1>-b<,i>≥p<,max>，i=1，2，…m-1)來表示。 所謂在線指的是工件集是按照某個(gè)順序到達(dá)的，是什么順序我們事先不知道，工件的所有性質(zhì)在它到來之前是未知的，工件在到來之前不能被安排加工。只有當(dāng)工件J<,j->已經(jīng)被安排好之后工件J<,j>才到達(dá)，否則，工件J<,j>不出現(xiàn)，并且工件J<,j>一出現(xiàn)就要立即被安排到某臺機(jī)器上加工，一旦被安排就不能再改變。 在這種類型的排序問題中，又可分為兩種

5、情形來考慮：一種是中斷后可繼續(xù)加工的情形，比如說在某個(gè)時(shí)刻某臺機(jī)器上有某個(gè)工件正在加工還沒有完工，而這臺機(jī)器在這個(gè)時(shí)刻需要進(jìn)行維修，那么在這一時(shí)刻可以中斷正在加工的這個(gè)工件，等到這臺機(jī)器維修完之后，再接著加工被中斷的工件剩余的部分。一種是中斷后不可繼續(xù)加工的情形，也就是說；對于上面的情形而言，被中斷的工件在機(jī)器維修完之后必須被重新開始加工，相當(dāng)于前面被加工的部分作廢．這兩種情形在排序模型中我們分別用符號r-a(Resumable ava

6、ilability)和nr-a(Nonresumable availability)來表示，這是借文獻(xiàn)[1]的用法。在上述情況下，我們的任務(wù)是找一個(gè)把所有工件安排到機(jī)器集上之后使得我們所要的某個(gè)目標(biāo)函數(shù)值達(dá)到盡可能優(yōu)的方案，用排序論的語言來說也就是找一個(gè)盡可能好的算法。 在這篇文章里，我們主要對m=2和3的情形進(jìn)行了討論，我們研究的問題的模型用三參數(shù)可表示為P2｜on-line-list；r-a；D<,1>｜C<,max>P2｜

7、on-line-list；nr-a；D<,1>｜C<,max>P2｜on-line-list；nr-a；D<,2>｜C<,max>P3｜on-line-list；nr-a；D<,1>｜C<,max>本文的主要結(jié)果是對問題P2｜on-line-list；r-a；D<,1>｜C<,max>，找到了一個(gè)競爭比是2的最好的算法并給出了證明．對問題P2｜on-line-list；nr-a；D<,1>｜C<,max>，我們將證明此排序問題的任意在線