機器有使用限制的三臺同類機排序問題

榮建華 張玲玲 王瑞霞

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

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

中圖分類號：G64 文獻標識碼：A 文章編號：1674-098X（2015）07（a）-0052-02

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

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

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

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

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

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

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

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

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

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

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

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

情形1.1：在機器上完工。此時。

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

因為

所以

=

。

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

因為

所以

=。

因而有。

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

情形1.3：在機器上完工。此時。

因為

所以

=。

因而有。

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

情形2.1：在機器上完工。此時。

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

因為

又因為時刻之前三臺機器上的可用加工時間之和為

所以

從而得到。

情形2.1.2：。此時且。

因為，

又因為時刻之前三臺機器上的可用加工時間之和為，所以

從而得到。

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

情形2.3：在機器上完工。此時。且。

因為

又因為時刻之前三臺機器上的可用加工時間之和為，

所以。

從而得到。

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

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

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

又因為

所以

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

又因為

所以

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

又因為

所以。

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

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

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

因為

所以

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

情形2.1：此時有

。

注意以下兩個不等式成立

（1）。

（2）。

故

情形2.1.1：。此時有。

情形2.1.2：此時有

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

下面分三種情況討論：

情形2.2.1：由于我們有

情形2.2.2：。由于我們有

情形2.2.3：因為

所以

綜上可知：對任意實例總有。

3 結(jié)語

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

參考文獻

[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.