丁甜甜，慕運動，柴 幸

(河南工業(yè)大學 理學院，河南 鄭州 450001)

排序理論是運籌學組合最優(yōu)化領(lǐng)域中一個重要的研究分支，主要研究工件(或稱為任務(wù))在機器上進行加工處理，如何優(yōu)化不同的目標函數(shù)。例如盡可能快的加工完所有工件，實現(xiàn)時間表長的最小化。隨著現(xiàn)代化的不斷發(fā)展，越來越多的排序模型和相應(yīng)的目標函數(shù)得到廣泛的關(guān)注。近些年來計算機學家和運籌學家們對工件具有處理集限制或可拒絕的排序問題進行了深入的研究。首先，具有處理集限制的排序問題，是指由于工件屬性和機器性能的限制，工件只能在對應(yīng)的滿足其屬性的部分機器上加工?？杉庸つ彻ぜ臋C器的集合，稱之為該工件的處理集。其中包含關(guān)系、樹形關(guān)系、嵌套關(guān)系三類處理集限制的排序問題已經(jīng)得到了廣泛的研究[1]。其次，工件可拒絕排序是指工件可以不在機器上進行加工，即可以被拒絕(或者通過外包進行處理)，此時需要支付一定的拒絕費用。

排序理論中的經(jīng)典模型，m臺機器上最小化時間表長(即所有工件的最大完工時間)的問題是強NP-困難的，不存在多項式時間的最優(yōu)算法，因此此類問題的近似算法得到了廣泛研究。近似算法主要討論在合理有效的計算時間內(nèi)得到較為好的近似結(jié)果，其優(yōu)劣用最壞情形比來衡量。算法的最壞情形比，也稱為近似比，是指對最小化目標函數(shù)的排序問題，在所有實例下，由算法所生成的目標函數(shù)值與最優(yōu)的目標函數(shù)值的比值的上界。

工件具有處理集限制時最小化時間表長的排序問題已經(jīng)得到了一系列的近似算法。Lenstra等人[2]對于具有包含關(guān)系處理集限制的排序問題得到了最壞情形比為2的多項式時間算法。緊接著Hwang等人[3]提出了關(guān)于解決上述問題的一個LG-LPT算法，該算法在m=2時的最壞情形比是5/4;在m≥3時最壞情形比是2-1/m-1，并證明了當m≥2時這個界是緊的.簡單的來說這個算法就是把那些未排的工件中最長的放到可以加工它的等級最低的機器上。接著Glass和Kellerer[4]對于嵌套關(guān)系處理集限制的排序問題給出了最壞情形比為2-1/m的列表算法，并對包含關(guān)系處理集限制的排序問題給出了最壞情形比為3/2的算法。進一步Ou等人[5]對具有包含關(guān)系處理集限制的排序問題得到了最壞情形比為4/3+ε的近似算法，其中ε為任意小的正數(shù)。再有Huo和Leung[6]對嵌套關(guān)系處理集限制的排序問題給出了最壞情形比為7/4的改進算法，以及兩臺機器時最壞情形比為5/4的算法。

關(guān)于工件可拒絕排序問題也得到了若干近似算法。Bartal等人[7]對最小化時間表長加上總拒絕費用的排序問題給出了最壞情形比為2-1/m的近似算法。更多的相關(guān)研究可參見綜述文獻[8]。

1 問題描述

本文我們主要討論的是兩臺機器上工件具有嵌套關(guān)系的處理集，同時工件可拒絕的排序問題。關(guān)于這個問題的描述如下:有n個工件的集合={J1,J2,…,Jn}，和兩臺機器集合={M1,M2}。每個工件Jj都有加工時間pj和拒絕費用ej，以及它所對應(yīng)的處理集。依據(jù)工件和機器的屬性，每個工件只能在部分機器上加工，可加工工件Jj的處理集j?{M1,M2}。在本文中，我們討論具有嵌套關(guān)系處理集限制的排序問題，任意兩工件對應(yīng)的處理集是相互包含或者不交的。因此工件的處理集有以下三類:{M1}，{M2}，{M1,M2}。此外，每個工件Jj都要面對一個問題，加工還是拒絕: 如果拒絕，那么需要支付拒絕費用ej；如果加工，那么就需要將Jj放到相應(yīng)的機器上進行加工。我們的目標是使時間表長Cmax和總的拒絕費用RC之和最小。

2 算法及分析

我們把工件的拒絕費用ej與pj/2來進行比較(這里2對應(yīng)總的機器數(shù)目)，決定工件的拒絕與否，以及安排在哪臺機器進行加工。因為這里是2臺機器，而pj/2表示的是一個工件放到2臺機器上的每臺機器的平均加工時長，即對時間表長的最小貢獻是這么多。如果此時拒絕費用ej

算法

首先對工件做預先處理，把處理集為{M1}或{M2}的工件放在序列前邊，把處理集為{M1,M2}的工件放在序列后邊；其次對序列中工件逐個安排加工，步驟如下：

步驟1對工件Jj，判斷ej與pj/2的大小關(guān)系。

1)若ej

2)若ej≥pj/2，則轉(zhuǎn)至步驟2。

步驟2依據(jù)Jj的處理集選擇機器進行加工。

1)若Jj的處理集為{M1}，則把Jj分配給M1進行加工；

2)若Jj的處理集為{M2}，則把Jj分配給M2進行加工；

3)若Jj的處理集為{M1,M2}，則把Jj分配給當前負載較小的機器(即當前已被分配的工件總加工時長較小的機器)進行加工。

為了更好地理解算法，我們先給出兩個具體的實例，然后再給出算法的最壞情形比分析。

實例1 有3個工件，所滿足的情況如下表：

表1 實例1工件詳情

根據(jù)我們的算法，可以得出J1在M2加工；J3在M1上加工；J2拒絕。根據(jù)算法可得Cmax=8,RC=1。

而關(guān)于這個實例的最優(yōu)排序是J1,J2,J3全部拒絕，故而有C*=0,RC*=6。所以有

實例2 有5個工件，所滿足的情況如下表：

表2 實例2工件詳情

根據(jù)我們的算法可得J1拒絕；J3,J4,J5在M1上加工；J2拒絕。故而可得Cmax=18,RC=0。

為了方便我們下面的分析證明，我們定義如下符號：對任一排序?qū)嵗齀來說，記由算法生成的排序為σ。在σ中，接收的工件集合記為JA，拒絕的工件集合為JR。其中Cmax表示排序σ的時間表長，即最大完工時間；RC表示排序σ中總的拒絕費用。實例I的最優(yōu)排序記為π，在π中，接收的工件集合記為JA*，拒絕的工件集合記為JR*，其中C*表示排序π的時間表長；RC*表示排序π中總的拒絕費用。

為了我們分析的方便，我們做如下假設(shè)：

假設(shè)1由我們算法生成的排序σ的時間表長Cmax對應(yīng)于M1的完工時間，即σ的時間表長Cmax是在M1上實現(xiàn)的。(若是在M2上實現(xiàn)的，可以把如下分析中的M1與M2互換即可。)

定理1算法的最壞情形比為2。

證明由假設(shè)1，設(shè)M1上最后完工的一個工件為Jh，且CH(Mi)表示在排序σ中機器Mi上的完工時間(i=1,2)。而Jh無非對應(yīng)于以下兩種情形：Jh對應(yīng)的處理集為{M1,M2}；Jh對應(yīng)的處理集為{M1}，此時說明M1上加工的工件全部都是處理集為{M1}的工件。

情形1Jh對應(yīng)的處理集為{M1,M2}。由算法步驟2.3，Jh被分配給當前負載最小的機器，所以

下面分四種子情形分別討論。

情形1.1排序σ與π接收的工件完全一樣。即JA=JA*，JR=JR*。故RC=RC*，

情形1.2排序σ中接收的工件多于π中接收工件，即JA*?JA。此時π比σ多拒絕了一些工件，并且這些工件滿足ej≥pj/2。用JA-JA*表示σ比π多加工的工件集合，記為Eσ。故而可得JR*-JR=Eσ，JA-JA*=Eσ。

情形1.3排序σ中接收的工件少于π中接收工件，即有JA?JA*。此時σ比π多拒絕了一些工件，并且這些工件滿足ej

因此

情形1.4JA與JA*沒有相互包含的關(guān)系，即排序σ中接收的工件與π中接收的工件不相互包含。此時σ比π多加工一些工件，用JA-JA*表示這些工件集合，記為Eσ，則它們滿足ej≥pj/2；π比σ多加工了一些工件，用JA*-JA表示這些工件集合，記為Eπ，則它們滿足ej

情形2Jh對應(yīng)的處理集為{M1}，說明M1上加工的工件全部都是處理集為{M1}的工件。同樣此時也有以下4種子情形。

情形2.1排序σ與π接收的工件完全一樣。即JA=JA*，JR=JR*。則Cmax=C*，RC=RC*。

情形2.3排序σ中接收的工件少于π中接收工件，即有JA?JA*。此時σ比π多拒絕了一些工件，并且這些工件滿足ej

情形2.4JA與JA*沒有相互包含的關(guān)系，即排序σ中接收的工件與π中接收的工件不相互包含。此時σ比π多加工一些工件，用JA-JA*表示這些工件集合，記為Eσ，則它們滿足ej≥pj/2；π比σ多加工了一些工件，用JA*-JA表示這些工件集合，記為Eπ，則它們滿足ej

綜上所述，算法的最壞情形比為2，結(jié)合實例2可知所分析的這個近似比2是緊的。

3 結(jié)論

在本文中，我們對兩臺機器上具有嵌套關(guān)系處理集限制的可拒絕排序問題進行了探討。關(guān)于工件具有處理集限制或工件可拒絕的排序問題在以往得到了廣泛的研究，也取得了若干近似算法，而這兩者結(jié)合的排序問題在文獻中很少提及。該類問題的難點在于如何結(jié)合不同工件的處理集限制與拒絕費用這兩者的關(guān)系，合理的設(shè)計算法并盡可能取得較好的近似結(jié)果。本文中首次關(guān)于這類問題給出了最壞情形比為2的近似算法，通過實例可知該近似比的值是緊的。如何設(shè)計最壞情形比更小的近似算法，以及如何把兩臺機器上的相應(yīng)結(jié)論推廣到更為一般的模型上，會是非常有趣的挑戰(zhàn)。