具有特殊工件的平行機在線排序問題.pdf

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

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

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