謝 謝，李彥平

（沈陽大學(xué)遼寧省裝備制造綜合自動化重點實驗室，遼寧沈陽 110044）

帶有單服務(wù)器的并行機調(diào)度問題

謝 謝，李彥平

（沈陽大學(xué)遼寧省裝備制造綜合自動化重點實驗室，遼寧沈陽 110044）

研究了一類具有準備時間和移出時間約束的單服務(wù)器并行機調(diào)度問題.這個問題概括了工件僅需要準備操作的經(jīng)典單服務(wù)器并行機調(diào)度問題.在該問題中，服務(wù)器不僅需要在每個工件加工之前將其裝載到一臺機器上，而且在工件加工結(jié)束后，將其從機器上卸載下來，裝載和卸載操作需要一定的時間.目標(biāo)函數(shù)為最小化最大完工時間.主要研究指定機器加工的情況，針對這種情況，構(gòu)建了多項式時間內(nèi)可解的啟發(fā)式算法.該啟發(fā)式的值與最優(yōu)值的比值為2，且證明了該界為緊界.

調(diào)度；并行機；單服務(wù)器；NP-難；啟發(fā)式

本文以鋼鐵企業(yè)罩式退火實際過程［1］為背景，提煉出帶有單服務(wù)器的并行機調(diào)度問題.罩式退火過程是鋼鐵企業(yè)改進鋼卷質(zhì)量的一個重要軋制過程.該過程由加熱和冷卻兩個關(guān)鍵步驟組成，加熱和冷卻的流程基本相同.以加熱過程為例，由三四個鋼卷組成的一個鋼卷垛（可看做一個工件）在加熱罩（可看做加工機器）中改變溫度以增強鋼卷的彈性和硬度.這個過程需要額外使用一臺吊機，每個工件需要進行3道工序.首先，加工機器由吊機裝載到工件上，加熱立刻開始.當(dāng)加熱結(jié)束時，吊機再將該機器進行卸載.這個調(diào)度的過程就是吊機將數(shù)目有限的加熱罩分配到給定的工件上，以最小化最后一垛鋼卷的完工時間（最大完工時間）.由于冷卻過程和加熱過程的工序一樣，只是用冷卻罩代替了加熱罩，因此，主要考慮加熱過程.

基于這個過程可知，每個工件需要進行3道工序：準備（裝載），加工（加熱），移出（卸載）.將吊機看做一個服務(wù)器，對準備工序和移出工序進行操作.因此，問題可以歸結(jié)為具有準備工序和移出工序約束的一個單服務(wù)器（吊機）的平行機（加熱罩）調(diào)度.當(dāng)不考慮移出工序時，問題可以簡化為僅考慮由單服務(wù)器準備操作的平行機調(diào)度問題.

目前已有的研究幾乎不考慮移出工序，這些模型太理想化，現(xiàn)存的結(jié)論很難應(yīng)用到帶有多種實際約束的問題中.本文的單服務(wù)器不僅需要操作準備工序，還需要操作移出工序，而移出工序的操作增加了問題的難度，因此需用新方法來解決這個問題.問題的特點就在于同時考慮機器和服務(wù)器.本文考慮并行機中的每一臺機器指定加工預(yù)先分好的工件集，提出了一個多項式時間內(nèi)可解的近似算法，這個算法的最壞性能最多是最優(yōu)值的2倍，并且為緊界.它概括了Glass等人［2］的一個結(jié)論.

給定n個工件的一個集合N＝｛J1，J2，…，Jn｝，每個工件必須在m個并行機M1，M2，…，Mm的一臺上進行加工.每個工件Jj的加工時間為pj.在加工工序之前，服務(wù)器需要sj≥0個時間單位進行一個準備工序Sj.類似地，加工結(jié)束之后，服務(wù)器需要rj≥0個時間單位進行一個移出工序Rj.準備工序和移出工序需要同時使用服務(wù)器和工具.準備一旦結(jié)束，機器必須立刻開始加工.服務(wù)器可以自由地進行其他準備工序.加工結(jié)束后，需要進行移出工序，或許由于服務(wù)器繁忙，因此這個操作在一定的空閑時間后才開始.任意的準備、加工和移出工序不可中斷，也就是說，一旦一道工序開始，它的前道工序必須結(jié)束.每個工件的加工時間不依賴于機器.一個工件一次最多被分配到一臺機器上加工，機器一次僅可以加工一個工件.準備和移出工序都由服務(wù)器完成.服務(wù)器一次最多處理一個工件.所有的工件、機器和服務(wù)器在零時刻可獲得.如果一個工件Jj被預(yù)先分配到一臺機器Mi上，Jj在機器Mi上的工序Oij的時間為pij≥0，工序Oij開始之前的準備工序Sij的時間為sij≥0，它的移出工序Rij的時間為rij≥0.如果一個工件Jj在機器Mi的第k個位置（1≤i≤m）加工，相應(yīng)的準備工序、加工工序P和移出工序R的時間分別為s，和.所有的數(shù)據(jù)是預(yù)先已知并且確定的.本文考慮的所有問題的目標(biāo)函數(shù)為最小化所有工件在機器上加工的最大完工時間.

問題用三元組α｜β｜γ（Garey和Johnson［3］）方法表示為PD，S1｜sij，rij｜Cmax.α-域P表示并行機的機器環(huán)境.本文研究的加工機器是相同的，工件在哪臺機器上加工也是預(yù)先指定的，這意味著將N個工件的集合預(yù)先劃分成m個子集N1，N2，…，Nm，每個集合Ni中的工件在機器Mi（1≤i≤m）上加工，寫做PD.如果機器的數(shù)目m是固定的（也就是不作為輸入的一部分），表示為PDm，S1｜sij，rij｜Cmax.此外，用S1表示單服務(wù)器的存在.β-域?qū)⒉煌娜我鉁蕚鋾r間sj或sij以及常數(shù)時間sj＝s或sij＝si＝s寫在其中.移出時間rj或rij類似.在僅考慮準備時間的相關(guān)文獻中，忽略了在該域中表示準備時間.不同于它們的表示，即使準備時間和移出時間是任意的，也將sj或sij以及rj或rij都表示出來.在γ-域，將最大完工時間表示為Cmax.對任意一個可行調(diào)度σ，最大完工時間表示為Cmax（σ）.Cmax（σ＊）為最優(yōu)調(diào)度σ＊對應(yīng)的調(diào)度值.通常，近似算法的質(zhì)量是由它們的最壞性能度量的.如果對問題的任意一個例子都有不等式Cmax（σ）／Cmax（σ＊）≤ρ成立，那么算法H產(chǎn)生的調(diào)度σ提供了一個性能保證ρ.如果存在問題的一個例子滿足Cmax（σ）／Cmax（σ＊）＝ρ，或當(dāng)工件的加工時間趨近于0或無窮時至少有Cmax（σ）／Cmax（σ＊）→ρ成立，則這個性能保證為緊的.問題的一個例子或許包含非常小加工時間、準備時間或移出時間.這樣短的操作時間對目標(biāo)函數(shù)的影響不大.這些小的趨近于0的時間通?？梢越普J為是0.

1 文獻綜述

目前，關(guān)于單服務(wù)器的并行機調(diào)度文獻的研究主要集中在理論分析，或者證明問題特殊情況的復(fù)雜性或者分析可以在多項式時間內(nèi)獲得最優(yōu)解的性質(zhì).進一步地，提出有效的啟發(fā)式算法來解決問題的一般情況.Glass等人［2］考慮了單服務(wù)器、工件指定機器的最小化最大完工時間的問題.他們證明了即使所有的準備時間都相等或者所有工件的加工時間都相等的兩臺并行機問題也是強NP-難的.Hall等人［4］補充了Glass等人［2］所考慮問題的一些結(jié)果.他們證明了一個最壞性能比為緊的、值為3／2的一個啟發(fā)式算法.對于工件指定機器的m個并行機問題，他們也提出了一個啟發(fā)式算法，該算法的目標(biāo)值與最優(yōu)值的比不超過2.

另一方面，研究者主要考慮近似算法.Abdekhodaee等人［5］應(yīng)用遺傳算法和Gilmore-Gomory算法解決了單服務(wù)器兩臺并行機的調(diào)度問題.盡管Yip等人［6］考慮了準備和移出工序，但他們忽略了單服務(wù)器的約束.Cheng和Kovalyov［7］、Brucker等人［8］、Iravani和Teo［9］、Su和Lee［10］研究了服務(wù)器調(diào)度問題，但都是在流水車間環(huán)境中考慮的.

2 啟發(fā)式算法

Glass等人［2］已經(jīng)證明了問題PD，S1｜sij，rij｜Cmax的特殊情況為NP-難的.通過多項式時間的歸結(jié)，這個問題也是NP-難的.本節(jié)提出一個修改的貪婪算法.這個算法概括了可以應(yīng)用到問題僅有準備時間存在的情況（rij＝0），證明了這個多項式時間算法得到的解值最多是最優(yōu)值的2倍，同時證明了這個界是緊的.

令σ＊表示問題PD，S1｜sij，rij｜Cmax的最優(yōu)調(diào)度，則有

由于服務(wù)器一次只能進行一個準備或移出工序，對于任意機器Mi（1≤i≤m），則有

對于PD，S1｜sij，rij｜Cmax問題，下面的貪婪算法可以按任意順序掃描工件.

第1步 對每臺機器Mi，產(chǎn)生工件的任一順序的一個列表Li（i＝1，2，…，m），轉(zhuǎn)第2步.

第2步 通過將工件Ji分配給最先可利用的機器Mi，構(gòu)建一個活動調(diào)度J1，J2，…，Jn.如果服務(wù)器空閑，那么

第2.1步 當(dāng)機器Mi完成之前的加工工序后，服務(wù)器對工件Jj進行準備工序；

第2.2步 當(dāng)機器Mi完成它的加工工序后，服務(wù)器對工件Jj進行移出工序.否則，轉(zhuǎn)第3步.

第3步 直到服務(wù)器可利用時，準備和移出工序可以進行.當(dāng)機器Mi和服務(wù)器可以利用時，將工件列表Li中的下一個工件分配到機器Mi上加工.當(dāng)兩臺機器同時可利用時，任選其一.已分配的工件從列表中排除.當(dāng)列表為空時，停止.

因此，算法需要o（mn2）時間.

下面，將完成對算法的分析并證明這個界是緊的.考慮問題PD，S1｜sij，rij｜Cmax的一個例子.有n＝m＋2個工件，對m的任一值如下：

圖1 算法的緊界：調(diào)度σ＊Fig.1 Tightness of algorithm：scheduleσ＊

另一方面，由算法得到的排序σ將工件的準備和移出按如下順序分配給服務(wù)器：

服務(wù)器從工序S35到R12一直繁忙，R12和R24之間的唯一空閑是使用機器M2進行加工工序，則有Cmax（σ）＝2＋11ε.如圖2所示.

圖2 算法的緊界：調(diào)度σFig.2 Tightness of algorithm：scheduleσ

3 結(jié) 語

本文研究了一種具有準備和移出工序約束的單服務(wù)器并行機調(diào)度問題.提出了一個啟發(fā)式算法并證明了其最壞性能比為2，該界為緊界.本研究概括了經(jīng)典的、工件僅需要準備工序的單服務(wù)器并行機調(diào)度問題.適合解決具有單服務(wù)器并行機調(diào)度問題特點的問題.在考慮具體的實施過程中，可以擴展到煉鋼、煉鐵以及精煉等過程.對于這類問題，考慮其他目標(biāo)函數(shù)并設(shè)計有效的啟發(fā)式算法是未來進一步研究的方向.

［1］謝謝，李彥平.罩式退火過程中的多吊機調(diào)度問題［J］.沈陽大學(xué)學(xué)報：自然科學(xué)版，2012，24（1）：12-19.

［2］Glass C A，Shafransky Y M，Strusevich V A.Scheduling for parallel dedicated machines with a single server［J］.Naval Research Logistics，2000，47（4）：304-328.

［3］Garey M R，Johnson D S.Computers and Intractability：a guide to the theory of NP-Completeness［M］.San Francisco：Freeman，1979.

［4］Hall N G，Potts C N，Sriskandarajah C.Parallel machine scheduling with a common server［J］.Discrete Applied Mathematics，2000，102（3）：223-243.

［5］Abdekhodaee A H，Wirth A，Gan H S.Scheduling two parallel machines with a single server：the general case［J］.Computers ＆Operations Research，2006，33（4）：994-1009.

［6］Yip Y，Cheng C Y，Low C.Sequencing of an M machine flow shop with setup，processing and removal times separated［J］.International Journal of Advanced Manufacturing Technology，2006，30（3／4）：286-296.

［7］Cheng T C E，Kovalyov M Y.Scheduling a single server in a two-machine flow shop［J］.Computing，2003，70（2）：167-180.

［8］Brucker P，Knust S，Wang G Q.Complexity results for flow-shop problems with a single server［J］.European Journal of Operational Research，2005，165（2）：398-407.

［9］Iravani S M R，Teo C P.Asymptotically optimal schedules for single-server flow shop problems with setup costs and times［J］.Operations Research Letters，2005，33（4）：421-430.

［10］Su L H，Lee Y Y.The two-machine flowshop no-wait scheduling problem with a single server to minimize the total completion time［J］.Computers ＆Operations Research，2008，35（9）：2952-2963.

Scheduling Parallel Machines with a Single Server

XIE Xie，LI Yanping

（Key Laboratory of Manufacturing Industrial and Integrated Automation，Shenyang University，Shenyang 110044，China）

The scheduling parallel machines with a single sever is investigated，as well as additional constraints on setups and removals.It generalizes classical parallel machine scheduling problem with a single server which needs to perform setup operation of each job only.The single server in this problem does not only load a job on a machine which takes a certain setup time immediately before processing but also unloads a job from the machine which takes a certain removal time after processing.The objective is to minimize makespan.A heuristic algorithm is constructed for the problem concerning the situations：with dedicated machine.A polynomial time approximate algorithm is proposed with a tight worst-case bound at most twice as large as the optimal value.

scheduling；parallel machines；single server；NP-hard problem；heuristics

TP 301.5

A

1008-9225（2012）04-0066-04

2012-01-04

2011年遼寧省教育廳科學(xué)研究一般項目（L2011207）.

謝 謝（1981-），女，遼寧沈陽人，沈陽大學(xué)講師，博士；李彥平（1958-），男，遼寧沈陽人，沈陽大學(xué)教授，博士.

李 艷】