College of Computer Science and Technology, Shandong Institute of Business and Technology, Yantai, China

---

Abstract—This paper investigates the scheduling problem of minimizing makespan on parallel batch processing machines encountered in different manufacturing environments, such as the burn-in operation in the manufacture of semiconductors and the aging test operation in the manufacture of thin film transistor-liquid crystal displays (TFT-LCDs). Each job is characterized by a processing time, a release time and a job size. Each machine can process multiple jobs simultaneously in a batch, as long as the total size of all jobs in the batch does not exceed machine capacity. The processing time of a batch is represented by the longest time among the jobs in the batch. An approximation algorithm with worst-case ratio 2 +Ë is presented, where Ë> 0 can be made arbitrarily small.

Index Terms—scheduling, parallel batch processing machines, makespan, release times, job sizes, worst-case analysis

[PDF]

Cite: Shuguang Li, "Makespan Minimization on Parallel Batch Processing Machines with Release Times and Job Sizes," Journal of Software vol. 7, no. 6, pp. 1203-1210, 2012.