兩臺(tái)機(jī)器上具有嵌套關(guān)系處理集限制的可拒絕排序

丁甜甜，慕運(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í)間表長(zhǎng)的最小化。隨著現(xiàn)代化的不斷發(fā)展，越來(lái)越多的排序模型和相應(yīng)的目標(biāo)函數(shù)得到廣泛的關(guān)注。近些年來(lái)計(jì)算機(jī)學(xué)家和運(yùn)籌學(xué)家們對(duì)工件具有處理集限制或可拒絕的排序問(wèn)題進(jìn)行了深入的研究。首先，具有處理集限制的排序問(wèn)題，是指由于工件屬性和機(jī)器性能的限制，工件只能在對(duì)應(yīng)的滿足其屬性的部分機(jī)器上加工。可加工某工件的機(jī)器的集合，稱之為該工件的處理集。其中包含關(guān)系、樹(shù)形關(guān)系、嵌套關(guān)系三類處理集限制的排序問(wèn)題已經(jīng)得到了廣泛的研究[1]。其次，工件可拒絕排序是指工件可以不在機(jī)器上進(jìn)行加工，即可以被拒絕(或者通過(guò)外包進(jìn)行處理)，此時(shí)需要支付一定的拒絕費(fèi)用。

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

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

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

1 問(wèn)題描述

本文我們主要討論的是兩臺(tái)機(jī)器上工件具有嵌套關(guān)系的處理集，同時(shí)工件可拒絕的排序問(wèn)題。關(guān)于這個(gè)問(wèn)題的描述如下:有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)系處理集限制的排序問(wèn)題，任意兩工件對(duì)應(yīng)的處理集是相互包含或者不交的。因此工件的處理集有以下三類:{M1}，{M2}，{M1,M2}。此外，每個(gè)工件Jj都要面對(duì)一個(gè)問(wèn)題，加工還是拒絕: 如果拒絕，那么需要支付拒絕費(fèi)用ej；如果加工，那么就需要將Jj放到相應(yīng)的機(jī)器上進(jìn)行加工。我們的目標(biāo)是使時(shí)間表長(zhǎng)Cmax和總的拒絕費(fèi)用RC之和最小。

2 算法及分析

我們把工件的拒絕費(fèi)用ej與pj/2來(lái)進(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í)長(zhǎng)，即對(duì)時(shí)間表長(zhǎng)的最小貢獻(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í)長(zhǎng)較小的機(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ū)嵗齀來(lái)說(shuō)，記由算法生成的排序?yàn)棣?。在σ中，接收的工件集合記為JA，拒絕的工件集合為JR。其中Cmax表示排序σ的時(shí)間表長(zhǎng)，即最大完工時(shí)間；RC表示排序σ中總的拒絕費(fèi)用。實(shí)例I的最優(yōu)排序記為π，在π中，接收的工件集合記為JA*，拒絕的工件集合記為JR*，其中C*表示排序π的時(shí)間表長(zhǎng)；RC*表示排序π中總的拒絕費(fèi)用。

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

假設(shè)1由我們算法生成的排序σ的時(shí)間表長(zhǎng)Cmax對(duì)應(yīng)于M1的完工時(shí)間，即σ的時(shí)間表長(zhǎng)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無(wú)非對(duì)應(yīng)于以下兩種情形：Jh對(duì)應(yīng)的處理集為{M1,M2}；Jh對(duì)應(yīng)的處理集為{M1}，此時(shí)說(shuō)明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*沒(méi)有相互包含的關(guān)系，即排序σ中接收的工件與π中接收的工件不相互包含。此時(shí)σ比π多加工一些工件，用JA-JA*表示這些工件集合，記為Eσ，則它們滿足ej≥pj/2；π比σ多加工了一些工件，用JA*-JA表示這些工件集合，記為Eπ，則它們滿足ej

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

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

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

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