Academic
Publications
Optimal Semi-online Algorithm for Scheduling on a Batch Processing Machine

Optimal Semi-online Algorithm for Scheduling on a Batch Processing Machine,10.1007/978-3-642-02026-1_32,Ming Liu,Yinfeng Xu,Chengbin Chu,Lu Wang

Optimal Semi-online Algorithm for Scheduling on a Batch Processing Machine  
BibTex | RIS | RefWorks Download
We consider two semi-online scheduling problems on a single batch (processing) machine with jobs’ nondecreasing processing times and jobs’ nonincreasing processing times, respectively. Our objective is to minimize the makespan. A batch processing machine can handle up to B jobs simultaneously. We study an unbounded model where B = ∞. The jobs that are processed together construct a batch, and all jobs in a batch start and complete at the same time. The processing time of a batch is given by the longest processing time of any job in the batch. Jobs arrive over time. Let p j denote the processing time of job J j . Given job J j and its following job J j + 1, we assume that p j + 1 ≥ αp j , where α ≥ 1 is a constant number, for the first problem with jobs’ nondecreasing processing times. For the second problem, we assume that p j + 1 ≤ αp j , where 0 α \fracÖ{a</font >2+4}-</font >a</font >2+1\frac{\sqrt{\alpha^2+4}-\alpha}{2}+1 for the first problem and \fracÖ{4a</font >+1}+12\frac{\sqrt{4\alpha+1}+1}{2} for the second problem.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.