榮建華 張玲玲 王瑞霞

摘 要：該文對兩種機(jī)器有使用限制的三臺同類機(jī)排序問題進(jìn)行了研究，已知有三臺機(jī)器和，其中的加工速度為1，的加工速度為s（0

關(guān)鍵詞：排序 同類機(jī) 使用限制 在線算法 競爭比

中圖分類號：G64 文獻(xiàn)標(biāo)識碼：A 文章編號：1674-098X（2015）07（a）-0052-02

在經(jīng)典排序問題的研究文獻(xiàn)中大都給出了如下假設(shè)條件：機(jī)器在任何時間都可以加工工件。但是這種假設(shè)條件在實(shí)際情況中并不總是存在。例如，在機(jī)器損壞或維修的一段時間內(nèi)，機(jī)器不能加工工件。因此，關(guān)于機(jī)器有使用限制的排序問題的研究得到了越來越多的關(guān)注。在此條件下，研究人員進(jìn)一步考慮了以下兩類問題。一類是工件可以中斷的情況，另一類是工件不可以中斷的情況。在考慮上述假設(shè)條件的前提下，研究人員對平行機(jī)和流水作業(yè)等相關(guān)問題作了研究。

在考慮機(jī)器有使用限制的條件下，研究人員主要對同型機(jī)的平行機(jī)排序問題進(jìn)行了研究。假定有一臺機(jī)器始終可用，而其它機(jī)器上都只有一個時間段不可用的條件下，證明了對于可中斷的平行機(jī)排序問題，LPT算法的性能比為，其中為機(jī)器數(shù)，且界是緊的；而對于不可中斷的平行機(jī)排序問題，LS算法和LPT算法的性能比分別為和。而和證明了在最大的同時不可用機(jī)器數(shù)不超過的條件下，LPT算法的性能比為2。

1 相關(guān)定義及符號

三臺同類機(jī)排序問題可以描述如下：

給定三臺機(jī)器和，其中的加工速度為1，的加工速度為）。給定待加工的工件集，的加工時間為，每個工件只需在一臺機(jī)器上加工，工件在機(jī)器上加工需要的實(shí)際時間為）。該文主要研究了兩種機(jī)器有使用限制的三臺同類機(jī)排序問題。第一種是機(jī)器在時段不可用，而機(jī)器始終可用，目標(biāo)函數(shù)為工件的最大完工時間，將此問題用三參數(shù)法表示為，其中表示機(jī)器上有使用限制；第二種情況是機(jī)器在時段不可用而機(jī)器始終可用。此類問題可以表示為。對于上有使用限制的情形和第一種情況完全一樣。

該文分析了和問題的LS算法。LS算法描述如下：

將當(dāng)前待加工的工件安排在可以最早完成加工的機(jī)器上。如果出現(xiàn)兩臺或三臺機(jī)器同時加工的情況，則優(yōu)先安排在速度快的機(jī)器上加工。

2 主要結(jié)論及證明

在對LS算法的性能比進(jìn)行分析以前，我們先給出由LS算法的排序所得到的對問題。最優(yōu)排序的最大完工時間的一個估計。

引理2.1：設(shè)對問題，由LS算法所得到的排序?yàn)樵O(shè)中最后完工的工件為，其開始加工時刻為。令的最優(yōu)排序的最大完工時間為，則必有。

證明：設(shè)實(shí)例共有個工件。記排序中機(jī)器上工件的最后完工時間分別為。以下分情況討論：

情形1：此時，時刻前三臺機(jī)器上的可用加工時間之和為。

情形1.1：在機(jī)器上完工。此時。

情形1.1.1：即機(jī)器在時刻前已完工。由算法可知：機(jī)器在時刻B前剩余的時間不能完成工件的加工，即。所以故。

因?yàn)?/p>

所以

=

。

情形1.1.2：由算法可知：不會大于時刻，即。

因?yàn)?/p>

所以

=。

因而有。

情形1.2：在機(jī)器上完工。仿情形1.1，同理可證。

情形1.3：在機(jī)器上完工。此時。

因?yàn)?/p>

所以

=。

因而有。

情形2：令表示時刻以前機(jī)器上空閑時間段。

情形2.1：在機(jī)器上完工。此時。

情形2.1.1：。由算法可知故。

因?yàn)?/p>

又因?yàn)闀r刻之前三臺機(jī)器上的可用加工時間之和為

所以

從而得到。

情形2.1.2：。此時且。

因?yàn)椋?/p>

又因?yàn)闀r刻之前三臺機(jī)器上的可用加工時間之和為，所以

從而得到。

情形2.2：在機(jī)器上完工。仿情形2.1，同理可證。

情形2.3：在機(jī)器上完工。此時。且。

因?yàn)?/p>

又因?yàn)闀r刻之前三臺機(jī)器上的可用加工時間之和為，

所以。

從而得到。

定理2.1：問題的算法的競爭比為。

證明：設(shè)在中最后一個完工工件為，開工時間為，進(jìn)一步設(shè)中的完工時間為。

情形1：在上完工。此時，且。

又因?yàn)?/p>

所以

情形2：在上完工。則且。

又因?yàn)?/p>

所以

情形3：在上完工。此時且。

又因?yàn)?/p>

所以。

定理2.1：問題的算法的競爭比為。

證明：設(shè)在中最后一個完工工件為，其開工時間為，又設(shè)在中的完工時間為。

情形1：工件在或上加工。由和的對稱性，不妨設(shè)在上加工。此時，且。

因?yàn)?/p>

所以

情形2：如果工件在上加工。則。

情形2.1：此時有

。

注意以下兩個不等式成立

（1）。

（2）。

故

情形2.1.1：。此時有。

情形2.1.2：此時有

情形2.2：令表示時刻以前機(jī)器上的空閑時間段，則。且。由引理2.1可知：

下面分三種情況討論：

情形2.2.1：由于我們有

情形2.2.2：。由于我們有

情形2.2.3：因?yàn)?/p>

所以

綜上可知：對任意實(shí)例總有。

3 結(jié)語

該文討論了機(jī)器有使用限制的三臺同類機(jī)排序問題，證明了LS算法的競爭比分別為和。下一步將致力于研究以下兩個問題：（1）討論該問題的下界；（2）將機(jī)器臺數(shù)推廣到m，設(shè)計在線算法并分析算法的競爭比。

參考文獻(xiàn)

[1] C.Y.Lee，Machine scheduling with an availability constraint[J].Journal of Global Optimization，1996，9（3）：395-416.

[2] H.C.Hwang and S.C.Chang，Parallel machines machines scheduling with machine shutdowns[J].Computers and Mathematics With Applications，1998，36（3）：21-31.