允許重啟的平行分批在線排序問(wèn)題.pdf

1、本文我們主要研究的是一類在線平行分批排序問(wèn)題，并且批工件是允許重啟(重新啟動(dòng))的。用三參數(shù)法表示我們的模型即是： 1|on-line,rj；p-batch,b=∞；restarts|Cmax。所謂在線，這里我們指的是工件集是隨時(shí)到達(dá)的，工件的所有性質(zhì)(包括到達(dá)時(shí)間)在它到來(lái)之前都是未知的，工件在到來(lái)之前不能被安排作業(yè)，工件到達(dá)了也沒(méi)有必要立即安排，一旦被安排就不能再改變。模型中平行分批是同時(shí)加工排序的一種情形，指的是若干工件可以

2、放在一起作為一批在一臺(tái)機(jī)器上同時(shí)加工，批中所有工件的開(kāi)工時(shí)間相等，完工時(shí)間也認(rèn)為相等，批的加工長(zhǎng)度等于批中所有工件中最長(zhǎng)的加工長(zhǎng)度，批的完工時(shí)間也就等于工件中最大的完工時(shí)間。平行分批排序又可分為批容量無(wú)界和批容量有界兩種類型，本文研究的是批容量無(wú)限制的情形，即一臺(tái)機(jī)器可以同時(shí)加工任意多個(gè)工件。 下面我們對(duì)“重新啟動(dòng)”(簡(jiǎn)稱重啟)給出定義。所謂工件允許重啟是指工件在加工過(guò)程中可以被打斷讓機(jī)器加工其他的工件，稍后再?gòu)念^開(kāi)始加工被打斷

3、的工件。也就說(shuō)該工件中斷前所消耗的時(shí)間都浪費(fèi)了。而一批允許重啟又與單個(gè)工件的重啟有所不同，一批允許重啟是指，我們可以打斷當(dāng)前正在加工的批，已經(jīng)加工的部分全部作廢，批中工件被釋放出來(lái)，各自成為獨(dú)立的未加工工件，它們可以與其它已經(jīng)到達(dá)的未加工的工件重新組合成一批，再被加工。排序中允許重啟可以降低錯(cuò)誤的決策造成的損失。在實(shí)踐中，操作需要重啟的事情經(jīng)常見(jiàn)到。比如冶金、集成電路產(chǎn)品的耐溫性檢測(cè)、程序的運(yùn)行、網(wǎng)上下載文件等都是一次性完成的，如果被打

4、斷，必須從頭開(kāi)始操作。在一些排序模型中，重啟起著很大的作用。例如在文獻(xiàn)[13]中，重啟對(duì)單機(jī)在線最小化最大運(yùn)輸時(shí)間的排序問(wèn)題是有幫助的，M.V.D.Akker等作者給出一個(gè)競(jìng)爭(zhēng)比是3/2的在線算法并且證明此算法是最具競(jìng)爭(zhēng)性的，而相應(yīng)的不允許工件重啟的單機(jī)在線最小化最大運(yùn)輸時(shí)間的排序問(wèn)題，最好的在線算法的競(jìng)爭(zhēng)比是(√5+1)/2。文獻(xiàn)[8]中，G.Zhang等人對(duì)問(wèn)題1|on-line,rj；p-batch,b=∞|Cmax給出性能比為(