带有单服务器的并行机调度问题

谢 谢，李彦平

（沈阳大学辽宁省装备制造综合自动化重点实验室，辽宁沈阳 110044）

带有单服务器的并行机调度问题

谢 谢，李彦平

（沈阳大学辽宁省装备制造综合自动化重点实验室，辽宁沈阳 110044）

研究了一类具有准备时间和移出时间约束的单服务器并行机调度问题.这个问题概括了工件仅需要准备操作的经典单服务器并行机调度问题.在该问题中，服务器不仅需要在每个工件加工之前将其装载到一台机器上，而且在工件加工结束后，将其从机器上卸载下来，装载和卸载操作需要一定的时间.目标函数为最小化最大完工时间.主要研究指定机器加工的情况，针对这种情况，构建了多项式时间内可解的启发式算法.该启发式的值与最优值的比值为2，且证明了该界为紧界.

调度；并行机；单服务器；NP-难；启发式

本文以钢铁企业罩式退火实际过程［1］为背景，提炼出带有单服务器的并行机调度问题.罩式退火过程是钢铁企业改进钢卷质量的一个重要轧制过程.该过程由加热和冷却两个关键步骤组成，加热和冷却的流程基本相同.以加热过程为例，由三四个钢卷组成的一个钢卷垛（可看做一个工件）在加热罩（可看做加工机器）中改变温度以增强钢卷的弹性和硬度.这个过程需要额外使用一台吊机，每个工件需要进行3道工序.首先，加工机器由吊机装载到工件上，加热立刻开始.当加热结束时，吊机再将该机器进行卸载.这个调度的过程就是吊机将数目有限的加热罩分配到给定的工件上，以最小化最后一垛钢卷的完工时间（最大完工时间）.由于冷却过程和加热过程的工序一样，只是用冷却罩代替了加热罩，因此，主要考虑加热过程.

基于这个过程可知，每个工件需要进行3道工序：准备（装载），加工（加热），移出（卸载）.将吊机看做一个服务器，对准备工序和移出工序进行操作.因此，问题可以归结为具有准备工序和移出工序约束的一个单服务器（吊机）的平行机（加热罩）调度.当不考虑移出工序时，问题可以简化为仅考虑由单服务器准备操作的平行机调度问题.

目前已有的研究几乎不考虑移出工序，这些模型太理想化，现存的结论很难应用到带有多种实际约束的问题中.本文的单服务器不仅需要操作准备工序，还需要操作移出工序，而移出工序的操作增加了问题的难度，因此需用新方法来解决这个问题.问题的特点就在于同时考虑机器和服务器.本文考虑并行机中的每一台机器指定加工预先分好的工件集，提出了一个多项式时间内可解的近似算法，这个算法的最坏性能最多是最优值的2倍，并且为紧界.它概括了Glass等人［2］的一个结论.

给定n个工件的一个集合N＝｛J1，J2，…，Jn｝，每个工件必须在m个并行机M1，M2，…，Mm的一台上进行加工.每个工件Jj的加工时间为pj.在加工工序之前，服务器需要sj≥0个时间单位进行一个准备工序Sj.类似地，加工结束之后，服务器需要rj≥0个时间单位进行一个移出工序Rj.准备工序和移出工序需要同时使用服务器和工具.准备一旦结束，机器必须立刻开始加工.服务器可以自由地进行其他准备工序.加工结束后，需要进行移出工序，或许由于服务器繁忙，因此这个操作在一定的空闲时间后才开始.任意的准备、加工和移出工序不可中断，也就是说，一旦一道工序开始，它的前道工序必须结束.每个工件的加工时间不依赖于机器.一个工件一次最多被分配到一台机器上加工，机器一次仅可以加工一个工件.准备和移出工序都由服务器完成.服务器一次最多处理一个工件.所有的工件、机器和服务器在零时刻可获得.如果一个工件Jj被预先分配到一台机器Mi上，Jj在机器Mi上的工序Oij的时间为pij≥0，工序Oij开始之前的准备工序Sij的时间为sij≥0，它的移出工序Rij的时间为rij≥0.如果一个工件Jj在机器Mi的第k个位置（1≤i≤m）加工，相应的准备工序、加工工序P和移出工序R的时间分别为s，和.所有的数据是预先已知并且确定的.本文考虑的所有问题的目标函数为最小化所有工件在机器上加工的最大完工时间.

问题用三元组α｜β｜γ（Garey和Johnson［3］）方法表示为PD，S1｜sij，rij｜Cmax.α-域P表示并行机的机器环境.本文研究的加工机器是相同的，工件在哪台机器上加工也是预先指定的，这意味着将N个工件的集合预先划分成m个子集N1，N2，…，Nm，每个集合Ni中的工件在机器Mi（1≤i≤m）上加工，写做PD.如果机器的数目m是固定的（也就是不作为输入的一部分），表示为PDm，S1｜sij，rij｜Cmax.此外，用S1表示单服务器的存在.β-域将不同的任意准备时间sj或sij以及常数时间sj＝s或sij＝si＝s写在其中.移出时间rj或rij类似.在仅考虑准备时间的相关文献中，忽略了在该域中表示准备时间.不同于它们的表示，即使准备时间和移出时间是任意的，也将sj或sij以及rj或rij都表示出来.在γ-域，将最大完工时间表示为Cmax.对任意一个可行调度σ，最大完工时间表示为Cmax（σ）.Cmax（σ＊）为最优调度σ＊对应的调度值.通常，近似算法的质量是由它们的最坏性能度量的.如果对问题的任意一个例子都有不等式Cmax（σ）／Cmax（σ＊）≤ρ成立，那么算法H产生的调度σ提供了一个性能保证ρ.如果存在问题的一个例子满足Cmax（σ）／Cmax（σ＊）＝ρ，或当工件的加工时间趋近于0或无穷时至少有Cmax（σ）／Cmax（σ＊）→ρ成立，则这个性能保证为紧的.问题的一个例子或许包含非常小加工时间、准备时间或移出时间.这样短的操作时间对目标函数的影响不大.这些小的趋近于0的时间通常可以近似认为是0.

1 文献综述

目前，关于单服务器的并行机调度文献的研究主要集中在理论分析，或者证明问题特殊情况的复杂性或者分析可以在多项式时间内获得最优解的性质.进一步地，提出有效的启发式算法来解决问题的一般情况.Glass等人［2］考虑了单服务器、工件指定机器的最小化最大完工时间的问题.他们证明了即使所有的准备时间都相等或者所有工件的加工时间都相等的两台并行机问题也是强NP-难的.Hall等人［4］补充了Glass等人［2］所考虑问题的一些结果.他们证明了一个最坏性能比为紧的、值为3／2的一个启发式算法.对于工件指定机器的m个并行机问题，他们也提出了一个启发式算法，该算法的目标值与最优值的比不超过2.

另一方面，研究者主要考虑近似算法.Abdekhodaee等人［5］应用遗传算法和Gilmore-Gomory算法解决了单服务器两台并行机的调度问题.尽管Yip等人［6］考虑了准备和移出工序，但他们忽略了单服务器的约束.Cheng和Kovalyov［7］、Brucker等人［8］、Iravani和Teo［9］、Su和Lee［10］研究了服务器调度问题，但都是在流水车间环境中考虑的.

2 启发式算法

Glass等人［2］已经证明了问题PD，S1｜sij，rij｜Cmax的特殊情况为NP-难的.通过多项式时间的归结，这个问题也是NP-难的.本节提出一个修改的贪婪算法.这个算法概括了可以应用到问题仅有准备时间存在的情况（rij＝0），证明了这个多项式时间算法得到的解值最多是最优值的2倍，同时证明了这个界是紧的.

令σ＊表示问题PD，S1｜sij，rij｜Cmax的最优调度，则有

由于服务器一次只能进行一个准备或移出工序，对于任意机器Mi（1≤i≤m），则有

对于PD，S1｜sij，rij｜Cmax问题，下面的贪婪算法可以按任意顺序扫描工件.

第1步 对每台机器Mi，产生工件的任一顺序的一个列表Li（i＝1，2，…，m），转第2步.

第2步 通过将工件Ji分配给最先可利用的机器Mi，构建一个活动调度J1，J2，…，Jn.如果服务器空闲，那么

第2.1步 当机器Mi完成之前的加工工序后，服务器对工件Jj进行准备工序；

第2.2步 当机器Mi完成它的加工工序后，服务器对工件Jj进行移出工序.否则，转第3步.

第3步 直到服务器可利用时，准备和移出工序可以进行.当机器Mi和服务器可以利用时，将工件列表Li中的下一个工件分配到机器Mi上加工.当两台机器同时可利用时，任选其一.已分配的工件从列表中排除.当列表为空时，停止.

因此，算法需要o（mn2）时间.

下面，将完成对算法的分析并证明这个界是紧的.考虑问题PD，S1｜sij，rij｜Cmax的一个例子.有n＝m＋2个工件，对m的任一值如下：

图1 算法的紧界：调度σ＊Fig.1 Tightness of algorithm：scheduleσ＊

另一方面，由算法得到的排序σ将工件的准备和移出按如下顺序分配给服务器：

服务器从工序S35到R12一直繁忙，R12和R24之间的唯一空闲是使用机器M2进行加工工序，则有Cmax（σ）＝2＋11ε.如图2所示.

图2 算法的紧界：调度σFig.2 Tightness of algorithm：scheduleσ

3 结 语

本文研究了一种具有准备和移出工序约束的单服务器并行机调度问题.提出了一个启发式算法并证明了其最坏性能比为2，该界为紧界.本研究概括了经典的、工件仅需要准备工序的单服务器并行机调度问题.适合解决具有单服务器并行机调度问题特点的问题.在考虑具体的实施过程中，可以扩展到炼钢、炼铁以及精炼等过程.对于这类问题，考虑其他目标函数并设计有效的启发式算法是未来进一步研究的方向.

［1］谢谢，李彦平.罩式退火过程中的多吊机调度问题［J］.沈阳大学学报：自然科学版，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年辽宁省教育厅科学研究一般项目（L2011207）.

谢 谢（1981-），女，辽宁沈阳人，沈阳大学讲师，博士；李彦平（1958-），男，辽宁沈阳人，沈阳大学教授，博士.

李 艳】