文献类型：期刊文献

中文题名：批处理机上有就绪和截止时间的等长度工件排序

英文题名：Scheduling Equal-length Jobs with Release Times and Deadlines on a Batch Machine

作者：刘朝晖[1]

机构：[1]华东理工大学数学系,上海200237

年份：2009

卷号：26

期号：3

起止页码：1

中文期刊名：重庆师范大学学报（自然科学版）

外文期刊名：Journal of Chongqing Normal University:Natural Science

收录：CSTPCD

基金：国家自然科学基金资助项目(No.10771067)

语种：中文

中文关键词：排序;批处理机;等长度工件;多项式时间算法

外文关键词：scheduling; batch machine; equal-length job; polynomial time algorithm

摘要：一台批处理机一次可以同时加工多个工件(称为一批),每批工件有相同的开工和完工时间,加工时间等于其中最长工件的加工时间。本文研究单台批处理机上有就绪时间和截止时间约束的n个等长度工件的排序问题,目标是求一个可行时间表。就该问题,B aptiste已经提出了一个复杂性为O(n8)的算法,在此基础上,本文推广G arey等人关于对应的经典排序问题的算法,得到了一个复杂性为O(n2)的算法。算法分两个阶段执行:在阶级I,算法找出所谓的禁止开工区间,在这些区间中将不允许有工件开工;在阶段II,算法从时刻零开始,每当机器有空闲且不属于禁止开工区间的时候,就按照最早截止时间优先规则从已就绪的未加工工件中选择尽可能多的工件作为一批进行加工,若当前的机器空闲时刻属于某个禁止开工区间,则首先更新其到该禁止开工区间的右端点再进行决策。
A batch machine can process a number of jobs simultaneously as a batch, where all the jobs processed in a batch have the same start time and the same completion time, and the processing time of a batch is given by the longest processing time of the jobs assigned to it. This paper studies the problem of scheduling n equal-length jobs with release times and deadlines on a batch machine, so as to obtain a feasible schedule. Baptiste has presented an O （ n^8 ） algorithm for the problem. Comparatively, Garey and others have given an O（ n^2 ） algorithm for the corresponding classical single machine scheduling problem. In this paper, we generalize Garey and others＇ algorithm to obtain an O（ n^2） algorithm for the above batch machine scheduling problem, which improves greatly on Baptiste＇s algorithm. Our algorithm is divided into two phases. In the first phase, we declare the so-called forbidden regions in which no jobs can start if the schedule is to be feasible. In the second phase, we schedule the jobs forward from time zero by using the earliest deadline scheduling rule. If the machine is idle and some unscheduled jobs are available at some time which is not in any forbidden region, we schedule the available unscheduled jobs with earlier deadlines as many as possible as a batch. If the idle time of the machine falls in some forbidden region, we first update the time to the right end of the forbidden region, and then make decision.