帶有強(qiáng)制工件的單機(jī)在線分批排序問題

金世國(guó)，張巧利

（1.鄭州信息科技職業(yè)學(xué)院，河南 鄭州 450046；2.河南廣播電視大學(xué)，河南 鄭州 450008）

帶有強(qiáng)制工件的單機(jī)在線分批排序問題

金世國(guó)1，張巧利2

（1.鄭州信息科技職業(yè)學(xué)院，河南 鄭州 450046；2.河南廣播電視大學(xué)，河南 鄭州 450008）

本文研究了帶有強(qiáng)制工件的單機(jī)在線分批排序問題, 目標(biāo)函數(shù)為最小化最大完工時(shí)間?？紤]了和強(qiáng)制工件沖突的批可以中斷(pmtn )和需要重啟(restart)兩種情形。對(duì)于每一種情形，給出了問題的下界及相應(yīng)的近似算法或最好可能的近似算法。

強(qiáng)制工件；單機(jī)；在線；平行分批

在經(jīng)典排序論中，一般假定實(shí)例的所有相關(guān)信息在開始排序前是事先知道的，如工件的個(gè)數(shù)、到達(dá)時(shí)間及加工時(shí)間等，這樣的情況稱為是離線的。但是現(xiàn)實(shí)生活中很多情況不是這樣，有時(shí)工件的信息是逐個(gè)釋放的，在任一時(shí)刻只知道已經(jīng)到達(dá)的工件信息，這種情況稱為在線(on-line)。在分批排序中，機(jī)器可以同時(shí)加工多個(gè)工件，構(gòu)成一批，并且批的加工時(shí)間是該批所有工件加工時(shí)間中的最大者。如何來分批是問題的關(guān)鍵，批確定后，可將其看做一工件來尋求最優(yōu)算法或近似算法。這里考慮帶有強(qiáng)制工件，目標(biāo)函數(shù)為最小化最大完工時(shí)間的在線分批排序，所有工件都是在線的，但有1一| p些 ?特ba殊工件要求單獨(dú)成批，且一旦到達(dá)了就要立刻加工，這類工件稱為強(qiáng)制工件(master job)，其余稱為自由工件。在這里強(qiáng)制工件間不相互沖突。1此|m 模ast型er記jo為b(： pmtn) ; p ?ba

1|m asterjob; p ?batch,b; on ?line,rj|Cmax，

考慮僅和強(qiáng)制工件沖突的批可中斷(pmtn)與需要重啟(restart)等情形。批允許重啟指可打斷正在加工的批，其已加工部分作廢，該批中的工件重新被釋放，變?yōu)槲醇庸すぜ?，可與其它已達(dá)未加工工件重新組合成新批，再被加工。

用競(jìng)爭(zhēng)比來衡量一個(gè)在線算法的優(yōu)良程度。記CH(L)，C*(L)表示對(duì)任意的工件序列L，在線算法H對(duì)應(yīng)的最大完工時(shí)間值及離線狀況下最優(yōu)值。算法H的競(jìng)爭(zhēng)比定義為R =sup{CH(L)/C*(L )}，競(jìng)爭(zhēng)比越小，對(duì)H?L應(yīng)算法越好。這里，我們把CH(L)和C*(L)簡(jiǎn)記為CH和C*。1|m asterjob(p mtn) ; p ? b Zhang G．C．等人對(duì)問題1|o n ?line,rj;p ?batch,b| |Cmax進(jìn)行了系列研究，也證明了該模型在線算法的下界為1+α，這里α= (5 ?1)/2，且批容量無界時(shí)，給出了與這一下界相吻合的最好可能算法H∞；當(dāng)批容量有界（b ＜n）時(shí)，又給出了一競(jìng)爭(zhēng)比不超過2的算法HB，猜想HB為最好可能。

算法FBLPT：

Step1：按加工時(shí)間不增的順序?qū)ぜ匦聵?biāo)號(hào)使p1≥ p2≥…pn。

Step2：第ib+1個(gè)工件至第(i + 1)b個(gè)工件構(gòu)成一批，這里i = 0,… ,[n/b]，[x] 表示小于x的最大整數(shù)。

Step 3：這些批按任意的序來排列。

1 可中斷（pmtn）情形

1.1 批容量無界情形

算法MH∞：

Step 0：當(dāng)強(qiáng)制工件到來時(shí)，立即對(duì)其加工，同時(shí)把加工區(qū)間收縮為一點(diǎn)，修改一下時(shí)間軸。當(dāng)強(qiáng)制工件完工時(shí)，繼續(xù)原來中斷的批。

Step 1：執(zhí)行算法H∞。強(qiáng)制工件到來時(shí)就返回Step 0。

定理3：對(duì)于問題1|m asterjob( pmtn) ; p ? batch,b =∞; o n ?line,rj|Cmax，算法MH∞競(jìng)爭(zhēng)比不超過1+α。證明：對(duì)任意的實(shí)例L，H∞在修改時(shí)間軸下目標(biāo)值和最優(yōu)值用C1和C1*表示，MH∞對(duì)應(yīng)目標(biāo)值和最優(yōu)值用C和C*表示，記強(qiáng)制工件總長(zhǎng)度為 ?L。 有C*= C1*+?L ；C= C1+?L 。 對(duì) 于C1和C1*， 由 Zhang G．C． [1]知，C1/C1*≤1+α， 故C/C*= (C1+?L )/(C1*+?L ) ≤ C1/C1*≤1+α。由定理2和定理3可知，算法MH∞是最好可能。

1.2 批容量有界情形

1|m asterjob(p mtn) ; p ? batch,b ＜n;o n ?line,rj|Cmax

算法MHB：

Step 0：當(dāng)強(qiáng)制工件來到時(shí)，立即對(duì)其加工，同時(shí)把加工區(qū)間收縮為一點(diǎn)，修改一下時(shí)間軸。當(dāng)強(qiáng)制工件完工時(shí)，繼續(xù)原來中斷的批。

Step 1：執(zhí)行算法HB。強(qiáng)制工件來到時(shí)就 返回Step 0。

定理4：對(duì)于問題1|m as1te|mr ajosbte(r pmjotbn() r;e ps t?a rbta)t;cph ?,b b ＜atnc;h n;o n ?line,rj|Cmax，算法MHB競(jìng)爭(zhēng)比不超過2。

證明：對(duì)于任意的實(shí)例L，算法HB在修改時(shí)間軸下目標(biāo)值和最優(yōu)值用C1和C1*表示，MHB對(duì)應(yīng)目標(biāo)值和最優(yōu)值用C和C*表示，記強(qiáng)制工件總長(zhǎng)度為?L。有

2 重啟(restart )情形1

證明：構(gòu)造實(shí)例，J1是第一個(gè)工件同時(shí)也是自由工件于零時(shí)刻到達(dá)，長(zhǎng)度是1。對(duì)任一算法H，

Case 1：若算法在時(shí)刻1前還未加工J1，則就不來工件。此時(shí)有CH≥2；C*=1．故CH/C*≥2．

Case 2：若算法在時(shí)刻0已經(jīng)開始加工J1，則于ε時(shí)刻來到另一自由工件J2，長(zhǎng)度也為1。此時(shí)CH≥2；C*=1+ε，于是CH/C*≥ 2/(1 +ε) → 2(ε →0)。

Case 3：若算法在l 時(shí)刻開始加工J1，這里0 ＜ l＜1，則一強(qiáng)制工件J2于1時(shí)刻到來，長(zhǎng)度為 ε。 此 時(shí)CH≥1 + ε+ 1= 2+ε；C*=1+ε， 故CH/C*≥(2 + ε) /(1 +ε) → 2(ε →0)．

綜上可知，RH≥2。

2.1 批容量無界情形

算法H：

Step 0：當(dāng)機(jī)器可用時(shí)，一旦有可用的自由工件，就把其放在同一批立即加工。

Step 1：當(dāng)有強(qiáng)制工件到來時(shí)，對(duì)其立即加工。返回Step 0。

定理6：?jiǎn)栴}1|m asterjob(r estart); p ? batch,b =∞;o o n ?line,rj|Cmax的算法H競(jìng)爭(zhēng)比不會(huì)超過2。

證明：對(duì)任一實(shí)例L，L中最大工件的長(zhǎng)度我們記為pmax。根據(jù)算法知，CH和C*至多相差了某批的長(zhǎng)度，從而即。

由定理5和6知，算法H 是最好可能的。

2.2 批容量有界情形

算法HH：

Step 0：每當(dāng)機(jī)器可用時(shí)，若有可用的自由工件，則對(duì)當(dāng)前所有自有工件按FBLPT 進(jìn)行分批，按批的LPT 進(jìn)行加工。

Step 1：強(qiáng)制工件到來時(shí)，對(duì)其立即進(jìn)行加工。同時(shí)返回Step 0。

以下僅考慮最后到達(dá)工件集中不含強(qiáng)制工件的情形，記它是在批B0加工過程中到達(dá)的。在B0加工的過程到達(dá)的新工件中最早到達(dá)時(shí)間記為r′．按照下面方法來處理：B0加工過程中所有到達(dá)的新工件都看成是時(shí)刻到達(dá)的，如果批B0是強(qiáng)制工件，仿上可以證明。不是強(qiáng)制工件，把其加工區(qū)間記為[s,t]，N表示s 時(shí)刻可用工件集，N′表示r′時(shí)刻到達(dá)的新工件集，算法中t 后加工的批我們記為

用F(D)來表示對(duì)工件集D運(yùn)用FBLPT得到批的加工時(shí)間之和。處理后的實(shí)例的目標(biāo)值和最優(yōu)值分別用Cmax與C*′表示。我們有

而C*′ ≥max{F(N),r ′+F(N ′)}，因此C /C*′≤2．

max容易得知，處理過的實(shí)例與原來的相比較，目標(biāo)值不變，最優(yōu)值也不會(huì)增加，所以對(duì)原實(shí)例也有CHH/C*≤2．綜上，定理成立。 由定理5和定理7可知，在線算法HH 是最好可能的。

3 結(jié)語(yǔ)

本文研究的帶強(qiáng)制工件的單機(jī)在線分批排序問題,對(duì)可中斷(pmtn )與需重啟(restart)兩種情形，均給出了問題的下界及近似算法或最好可能的近似算法。

[1]Zhang G．C．,Cai X．Q． and Wong C．K． On-Line Algorithms for Minimizing Makespan on Batch Processing Machines[J] ．Naval Research Logistics, 2001, 48: 241-258．

[2]Poon C．K． and Zhang P．Minimizing makespan in batch machine scheduling[J]． Algorithms, 2004, 39:155-174．

[3]Poon C．K． and Yu W．C．On-Line Scheduling Algorithms for a Batch Machine with Finite

O223

A

1671-0711（2017）08（下）-0216-02

河南省教育廳科學(xué)技術(shù)研究重點(diǎn)項(xiàng)目(15A110003)。