帶有強制工件的單機在線分批排序問題

金世國，張巧利

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

帶有強制工件的單機在線分批排序問題

金世國1，張巧利2

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

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

強制工件；單機；在線；平行分批

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

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

考慮僅和強制工件沖突的批可中斷(pmtn)與需要重啟(restart)等情形。批允許重啟指可打斷正在加工的批，其已加工部分作廢，該批中的工件重新被釋放，變為未加工工件，可與其它已達未加工工件重新組合成新批，再被加工。

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

算法FBLPT：

Step1：按加工時間不增的順序對工件重新標號使p1≥ p2≥…pn。

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

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

1 可中斷（pmtn）情形

1.1 批容量無界情形

算法MH∞：

Step 0：當強制工件到來時，立即對其加工，同時把加工區間收縮為一點，修改一下時間軸。當強制工件完工時，繼續原來中斷的批。

Step 1：執行算法H∞。強制工件到來時就返回Step 0。

定理3：對于問題1|m asterjob( pmtn) ; p ? batch,b =∞; o n ?line,rj|Cmax，算法MH∞競爭比不超過1+α。證明：對任意的實例L，H∞在修改時間軸下目標值和最優值用C1和C1*表示，MH∞對應目標值和最優值用C和C*表示，記強制工件總長度為 ?L。 有C*= C1*+?L ；C= C1+?L 。 對 于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：當強制工件來到時，立即對其加工，同時把加工區間收縮為一點，修改一下時間軸。當強制工件完工時，繼續原來中斷的批。

Step 1：執行算法HB。強制工件來到時就 返回Step 0。

定理4：對于問題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競爭比不超過2。

證明：對于任意的實例L，算法HB在修改時間軸下目標值和最優值用C1和C1*表示，MHB對應目標值和最優值用C和C*表示，記強制工件總長度為?L。有

2 重啟(restart )情形1

證明：構造實例，J1是第一個工件同時也是自由工件于零時刻到達，長度是1。對任一算法H，

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

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

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

綜上可知，RH≥2。

2.1 批容量無界情形

算法H：

Step 0：當機器可用時，一旦有可用的自由工件，就把其放在同一批立即加工。

Step 1：當有強制工件到來時，對其立即加工。返回Step 0。

定理6：問題1|m asterjob(r estart); p ? batch,b =∞;o o n ?line,rj|Cmax的算法H競爭比不會超過2。

證明：對任一實例L，L中最大工件的長度我們記為pmax。根據算法知，CH和C*至多相差了某批的長度，從而即。

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

2.2 批容量有界情形

算法HH：

Step 0：每當機器可用時，若有可用的自由工件，則對當前所有自有工件按FBLPT 進行分批，按批的LPT 進行加工。

Step 1：強制工件到來時，對其立即進行加工。同時返回Step 0。

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

用F(D)來表示對工件集D運用FBLPT得到批的加工時間之和。處理后的實例的目標值和最優值分別用Cmax與C*′表示。我們有

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

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

3 結語

本文研究的帶強制工件的單機在線分批排序問題,對可中斷(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

河南省教育廳科學技術研究重點項目(15A110003)。