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

霍满臣，陈忠菊

(1.沈阳工程学院 基础部，辽宁 沈阳 110136；

2.辽宁公安司法管理干部学院 公共安全系，辽宁 沈阳 110161)



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

霍满臣1，陈忠菊2

(1.沈阳工程学院 基础部，辽宁 沈阳 110136；

2.辽宁公安司法管理干部学院 公共安全系，辽宁 沈阳 110161)

摘要：研究两台同构并行机上的批在线调度问题，工件以批方式到达且每个批中有m个工件，每个工件的处理时间限定在一个区间上，只有当前批中工件全部加工完成后才可以加工其后面的工件，目标函数是使最大完成时间最小。针对这一问题，给出了1个批在线启发式调度算法，在同一批中的工件按LPT规则调度。对算法的最坏情况进行了分析并给出了算法的最坏情况比与批中工件数有关，并由计算机程序进行了验证。

关键词：批在线列表调度；最坏情况比；同构并行机；最大完成时间；加工时间

在流程工业中存在大量的在线批调度问题。对生产工序进行优化,使生产资源配置的变化降到最低是重要的问题。在生产调度中，要充分考虑过程的不确定性，根据生产实绩实时调整调度安排,产生新的调度信息[1,2]。

古典的调度问题中，假设在调度前已经给出了工件的全部信息，而在实际问题中，在调度前许多工件的信息是未知的，针对这一情况，提出了在线调度理论[3-8]。Graham于1966年提出了算法最坏情况为2-1/m的列表在线调度理论[5]，但他没考虑批形式调度的情况。而实际中存在大量的在线批调度的情况，利用在线批调度比一次调度一个工件更经济实用[9-11]。

1批在线调度问题及算法

1.1两台同构并行机上的批在线调度问题

有2台同构并行机和1个批工件序列，即工件以批方式按列表到达，将第i批工件记为bi(i=1,2,…,n)，每个工件加工时间在某个实数区间[a,b]上。这里假定每个批中都有m个工件，每批一个接一个地到达，形成1个批工件序列表，且当每批工件到达时，在不知其后面批工件列信息的情况下，对该批中工件立即进行调度。当该批工件全部加工完时，才调度其后面批中的工件。目标函数是使调度的最大完成时间(makespan)最小。

1.2批在线调度算法A

当1批工件bi(i=1,2,…,n-1)到达时，将该批中的工件进行编号，使它们加工时间满足pi1≥pi2≥…≥pim，其中Pij(i=1，2，…，n-1；j=1，2，…，m)表示第i个批中第j个工件的处理时间，且所有加工时间pij∈[a,b]。然后根据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的最大完成时间(makespan),OPT(BL)表示离线最优调度对BL的最大完成时间。

2.1实例

现有3批工件，每批有5个工件要调度到两台并行机上，如表1所示，其中pij∈[3,6]。

算法A产生的调度算法A如图1所示。

图1　算法A产生的调度算法

从而有CA=39

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

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

从而有COPT=36

2.2理论分析

对区间[a,b]长度 b-a作如下限定：

设 Cij(j=1,2)为第i批工件在第j台机器上的完成时间。

证明

证明

证：由引理1，2

证明

证：

证：由引理1，2可得

3实验与数值计算结果

对于近似算法A的目标函数值A(BL)及相应离线最优算法的最优值OPT(BL)，利用C语言编程。在数值计算中，对于n∈{10，30， 60，70，80，90，100，110，120，140，150}、m∈{5，6，8，10，20，30，40，50，60，80，100}的每种组合，算法A随机产生A(BL)的5个算例，n表示每个算例中批的数量，每种情况作50次随机模拟，工件的基本处理时间分别在[10,100]、[20,100]、[20,80]、[10,50]、[1,5]服从均匀分布。表1给出算法相应最坏情况比值在各个比值区间上模拟出现的次数，其中比值区间被分成[1.0，1.1)、[1.1，1.2)、[1.2，1.3)、[1.3，1.4)、[1.4，1.5]。

由表1可得如下的分析结果：

1)程序计算结果表明：当批中含有较多工件时，算法A的最坏情况比较理想，比值基本上分布在区间[1.0，1.1)中，说明算法性能较好。

2)启发式算法对于批内工件较多问题的改进比那些批内工件少的改进更大，从而减小的最大完成时间更明显。

表1　算法相应最坏情况比值在各个比值

4结论

参考文献

[1]TangLX,LiuJY,RongAY,etal.Areviewofplanningandschedulingsystemsandmethodsforintegratedsteelproduction[J].EuropeanJournalofOperationalResearch,2001,133:1-20.

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

[3]ChenB,VestjensA.P.A.Schedulingonidenticalmachines:HowgoodisLPTinanon-linesetting?[J].OperationsResearchLetters,1998,21(15):165-169.

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

[5]GrahamR.Boundsforcertainmultiprocessinganomalies[J].TheBellSystemTechnicalJournal,1966,45:1563-1581.

[6]EpsteinL.Anoteonon-lineschedulingwithprecedenceconstraintsonidenticalmachines[J].InformationProcessingLetters,2000,76:149-153.

[7]EpsteinL,SgallJ.Alowerboundforon-lineschedulingonuniformlyrelatedmachines[J].OperationsResearchLetters,2000,26(1):17-22.

[8]LuX,SittersRA,StougieL.Aclassofon-lineschedulingalgorithmstominimizetotalcompletiontime[J].OperationsResearchLetters,2003,31:232-236.

[9]PottsCN,KovalyovMY.Schedulingwithbatching:Areview[J].EuropeanJournalofOperationalResearch,2000,120:228-249.

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

[11]霍满臣，陈忠菊.机器无等待工件具有区间限制的两台同构并行机上批在线调度[J].沈阳工程学院学报：自然科学版，2015，11(1)：90-92.

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

On-line Batch Scheduling with Constraint on Processing Time in Interval and Machine Waiting

HUO Man-chen1,CHEN Zhong-jiu2

(1.Foundation Department,Shenyang Engineering Institute,Shenyang 110136;2.Public Security Department,Liaoning Administrators College of Police and Justice,Shenyang 110161,Liaoning Province)

Abstract：It was studied with the problem of scheduling jobs in batches on-line on 2 identical parallel machines with objective to minimize the maximum completion time (the completion time of the last job: makespan),where batches arrived over list and every batch had exactly m jobs,and the processing timeswere constrained in some interval.When a batch arrivedthe jobswere scheduled in this batch immediately and irrevocably without the knowledge of later batches.The pre-emptionwas not allowed.An algorithm with scheduling jobs in every batch by LPT rule was proposed.When all the jobs in pre-batch were scheduledthe jobswere schedule in the following batch.The worst case was analyzed and the worst case ratio dependent with number of jobs in batch was given,and the conclusion was proved by program.

Key words：batch on-line list schedule;competitive ratio;identical parallel machines;batch list;maximum completion time;processing time

中图分类号：TP301.6

文献标识码：A

文章编号：1673-1603(2016)01-0092-05

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

作者简介：霍满臣(1963-)，男，辽宁海城人，教授，博士，主要从事系统工程与应用数学方面的研究。

收稿日期：2015-10-14