机器无等待工件具有区间限制的两台同构并行机上批在线调度

霍满臣,陈忠菊

(1.沈阳工程学院 基础部，辽宁 沈阳 110136； 2.辽宁公安司法管理干部学院 公共安全系，辽宁 沈阳 110161)



机器无等待工件具有区间限制的两台同构并行机上批在线调度

霍满臣1,陈忠菊2

(1.沈阳工程学院 基础部，辽宁 沈阳 110136； 2.辽宁公安司法管理干部学院 公共安全系，辽宁 沈阳 110161)

摘要：针对两台同构并行机上的在线批调度问题，提出了使工件加工的最大完成时间最小的一个批在线列表调度算法。即工件组成不同的批，每个批中有m个工件，当每批到达等待加工时，其内部的工件加工时间才已知，且每个工件加工时间限定在某个实区间[a,b]上。在对当前批后批中工件的信息不了解的情况下，立即将其中的工件按LPT规则调度进行调度，调度过程中不允许中断。 解决了算法的可使用性的度量问题，对其最坏情况进行了分析，给出了算法的最坏情况比。

关键词：最坏情况比；两台同构并行机；批工件列；最大完成时间；加工时间

现代流程工业中存在大量批在线调度问题。在生产调度过程中，存在大量的不确定性，需要根据生产实际实时调整调度安排,产生动态的调度算法[1,2]。批在线调度理论适用于解决这一类问题。

离线调度理论假设在调度前已经掌握了工件的全部信息，而在实际生产应用中，工件的许多信息在调度前是不确定的，考虑这种动态不确定性，产生了在线调度问题[3~8]。Graham于1966年给出了在线列表调度算法并证明了其最好情况比为2-1/m[5]，但他没有考虑工件按批方式到达的情况。实际上存在大量批加工问题，而批调度比一次调度一个工件实用[9,10]。因此，以每次来m个工件的批到达情况为例，将批调度与在线调度相结合，针对一个批在线调度问题，给出了一个在线批调度算法，分析了其最坏情况并给出了其最坏情况比。

1批在线调度问题及算法

两台同构并行机上批在线调度问题可以描述如下：有两台用于加工工件的同构并行机，工件组成一个批工件表列，工件以批形式按列表到达，将第i批工件记为bi (i=1,2,…,n)。其中每个工件的加工时间随其批的到达便已知，且每个工件加工时间在某个实数区间[a,b]上。这里每个批中都有m个工件，每批一个接一个地到达形成一个批工件序列，且每批工件到达时，在不依赖其后面批的信息情况下，立即对该批中工件进行调度，调度过程不允许被打断。问题的目标是使调度的最大完成时间最小。

批在线调度算法记为A：当一批工件bi (i=1,2,…,n-1)到达时，将该批中的工件进行编号使它们满足pi1≥pi2≥…≥pim，再根据LPT规则将该批中的工件调度到两台同构并行机上，当bi+1(i=1,2,…,n)中最后一个工件加工完成时，立即再调度bi(i=2,3,…,n)中所有工件，机器不允许空闲。

2批在线调度算法A的最坏情况分析

批在线算法A的最坏情况可用调度算法A对批工件列产生的最大完成时间与离线最优算法产生的最大完成时间的比来度量。这个比定义为：R=sup{A(BL)/OPT(BL)}，其中BL为批工件列，A(BL)表示算法A对BL的最大完成时间,OPT(BL)表示离线最优调度对BL的最大完成时间。

例如，现有3批工件，每批有5个工件要调度到两台并行机上如下表。

表1　不同批次不同工件的处理时间Pij

Pij(i=1，2，…，n-1；j=1，2，…，m)表示第i个批中第j个工件的处理时间，且所有加工时间pij∈[a,b]，此处pij∈[3,6]。

图1　批在线算法A对批工件列产生的调度

其中，CA=40。

图2　离线算法对批工件列产生的最优调度

其中，COPT=39。

引理2设算法A产生的在线调度中，批工件列BL最后到达的批最后完成。

1)当最后完成的工件的开始加工时间不大于前n-1批中工件的加工时间和的一半，则

2)当工件Jnk的开始加工时间t超过前n-1批中全部工件的加工时间和的一半，则

证明首先，离线最优调度下的最大完成时间满足

设最后一批，即第n批中最后完成加工的工件为Jnk，其开始加工时间是t，则由算法A产生调度的最大完成时间为CA(BL)=t+Pnk。

1)当工件Jnk的开始加工时间t不超过前n-1个批中全部工件的加工时间和的一半，即

2)当工件Jnk的开始加工时间t超过前n-1批中全部工件的加工时间和的一半，即

这样算法A产生的调度的最大完成时间

根据以上的(1)与(2)，得出引理2的结论。

引理3pij∈[a,b]

证明

3结论

通过对一个在线批列表调度问题的研究，将以往工件的到达推广为工件以批的方式到达，讨论了在限定每一批中恰有m个工件且工件加工时间在一定区间上的情况，最终提出了一个批在线调度算法，即每一批中的工件按LPT规则进行调度，并证明了算法A的最坏情况比不超过3/2，从理论上证明了以批形式组织生产更能提高生产效率。

参考文献

[1]Tang L X,Liu J Y,Rong A Y,et al.A review of planning and scheduling systems and methods for integrated steel production[J].European Journal of Operational Research,2001,133:1-20.

[2]唐立新.轧钢厂的精轧工序轧制批量调度的优化模型[J].东北大学学报：自然科学版,1998,19(6):624-626.

[3]Chen B,Vestjens A.P.A.Scheduling on identical machines:How good is LPT in an on-line setting?[J].Operations Research Letters,1998,21(15):165-169.

[4]霍满臣，唐立新.面向流程工业的批在线调度问题[J].控制工程，2005,12(6):511-514.

[5]Pinedo.调度：原理、算法和系统[M].第2版.北京：清华大学出版社,2005.

[6]Xiuli Wang,1,2 T.C.Edwin Cheng.Machine Scheduling with an Availability Constraint and Job Delivery Coordination.Naval Research Logistics,2007，54：11-21.

[7]Epstein L,Sgall J.A lower bound for on-line scheduling on uniformly related machines[J].Operations Research Letters,2000,26(1):17-22.

[8]Lu X,Sitters R A,Stougie L.A class of on-line scheduling algorithms to minimize total completion time[J].Operations Research Letters,2003,31:232-236.

[9]Potts C N,Kovalyov M Y.Scheduling with batching:A review[J].European Journal of Operational Research,2000,120:228-249.

[10]霍满臣，唐立新.基于到达时间两台并行机上在线批调度[J].控制与决策，2009,12(12):1826-1830.

(责任编辑张凯校对佟金锴)

Batch On-line Scheduling of Workpieces on Two Parallel

Machines with Time Interval Restriction

HUO Man-chen1,CHEN Zhong-ju2

(1.Basic Courses Department,Shenyang Institute of Engineering,Shenyang 110136;

2.Public Security Department,Liaoning Administrators College of Police and Justice,Shenyang 110161,Liaoning Province)

Abstract：An algorithm was put forward to satisfy the batch on-line scheduling on two identical parallel machines with the objective to minimize the maximum completion time.In the algorithm,all workpieces were divided into different batches,and each batch has m workpieces.The processing times of workpieces in every batch were given only when the batch containing them arrived and they were constrained in some interval[a,b].When a batch arrived,the workpieces in this batch were scheduled immediately and irrevocably with the unknown following batches.An algorithm with scheduling workpieces in every batch by LPT rule was proposed.The measurement of the algorithm application was solved,the worst case was analyzed and the worst case ratio was given.

Key words：Worst case ratio;Two identical parallel machines;Batch list;Maximum completion time;Processing time

DOI：10.13888/j.cnki.jsie(ns).2015.01.021

作者简介：马国强(1960-)，男，辽宁沈阳人，助理实验师。

收稿日期：2014-09-14

中图分类号：TP273

文献标识码：A

文章编号：1673-1603(2015)01-0090-03