丁甜甜，慕運(yùn)動(dòng)，柴 幸

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

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

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

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

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

1 問題描述

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

2 算法及分析

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

算法

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

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

1)若ej

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

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

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

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

3)若Jj的處理集為{M1,M2}，則把Jj分配給當(dāng)前負(fù)載較小的機(jī)器(即當(dāng)前已被分配的工件總加工時(shí)長較小的機(jī)器)進(jìn)行加工。

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

實(shí)例1 有3個(gè)工件，所滿足的情況如下表：

表1 實(shí)例1工件詳情

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

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

實(shí)例2 有5個(gè)工件，所滿足的情況如下表：

表2 實(shí)例2工件詳情

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

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

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

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

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

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

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

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

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

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

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

因此

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

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

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

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

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

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

3 結(jié)論

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