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

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

作　　者：霍满臣[1] 陈忠菊[2] 

机构地区：[1]沈阳工程学院基础部,辽宁沈阳110136 [2]辽宁公安司法管理干部学院公共安全系,辽宁沈阳110161

出　　处：《沈阳工程学院学报（自然科学版）》2016年第1期92-96,共5页Journal of Shenyang Institute of Engineering:Natural Science

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

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]