%0 Journal Article
%T Scheduling Equal-length Jobs with Release Times and Deadlines on a Batch Macine
%A LIU Zhao-hui
%J Journal of Chongqing Normal University
%D 2009
%I Chongqing Normal University
%X A batch machine can process a number of jobs simultaneously as a batch, where alll 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(n8)algorithm for the problem.Comparatively, Garey and others have given an O (n2) algorithm for the corresponding classical single machine scheduling problem. In this paper, we generalize Garey and others' algorithm to obtain an O(n2)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.
%K scheduling
%K batch machine
%K equal-length job
%K polynomial time algorithm
%U http://journal.cqnu.edu.cn/0903/pdf/090301.pdf