具有特殊工件的平行機(jī)在線(xiàn)排序問(wèn)題.pdf

1、本文研究一類(lèi)具有特殊工件的平行機(jī)在線(xiàn)排序問(wèn)題，目標(biāo)是最小化最大完工時(shí)間。用Graham等人[12]提出的三參數(shù)法，我們的問(wèn)題可以表示為：Pm｜on-line-list；special．jobs(M<,1>)｜C<,max>，其中M<,1>表示特殊工件要在第一臺(tái)機(jī)器上加工．當(dāng)工件集中沒(méi)有特殊工件時(shí)，問(wèn)題就退化成了經(jīng)典的平行機(jī)在線(xiàn)排序Pm｜on-line-lis｜C<,max>． 所謂在線(xiàn)，本文指的是列表在線(xiàn)：工件被排成一個(gè)隊(duì)列，然

2、后逐個(gè)釋放。一旦某個(gè)工件被釋放，必須馬上決定在哪臺(tái)機(jī)器上加工它．工件被釋放之前，我們不知道它的任何信息．只有當(dāng)前面一個(gè)工件被安排之后，后一個(gè)工件的信息才知道．一旦工件被安排到機(jī)器上，我們不允許再移動(dòng)它到另一臺(tái)機(jī)器上． 在本文考慮的排序問(wèn)題中，有兩種類(lèi)型的工件：正常工件和特殊工件。正常工件能夠在平行機(jī)的任何一臺(tái)機(jī)器上加工，而特殊工件僅僅能夠在它被指定的機(jī)器上加工，并且每個(gè)特殊工件的指定機(jī)器是唯一的。在本文討論的模型中，所有的特殊工

3、件都被指定到機(jī)器M<,1>上去加工。 在生產(chǎn)實(shí)踐中，特殊工件是普遍存在的。它們有一些特殊的性能使得它們必須到指定的機(jī)器上去處理。這樣，就使得我們的生產(chǎn)安排變得復(fù)雜化。 本文的主要結(jié)果如下： (1)兩臺(tái)機(jī)器的情形：P2｜on-line-list；special．jobs(M<,1>)｜C<,max>．證明了任意在線(xiàn)算法的競(jìng)爭(zhēng)比不小于5/3，并提供了一個(gè)最好可能的在線(xiàn)算法。 (2)三臺(tái)機(jī)器的情形： P3｜on