Scheduling a batch processing machine with non-identical job sizes: a clustering perspective

Abstract

Batch processing machines that process a group of jobs simultaneously are often encountered in semiconductor manufacturing and metal heat treatment. This paper considered the problem of scheduling a batch processing machine from a clustering perspective. We first demonstrated that minimising makespan on a single batching machine with non-identical job sizes can be regarded as a special clustering problem, providing a novel insight into scheduling with batching. The definition of WRB (waste ratio of batch) was then presented, and the objective function of minimising makespan was transformed into minimising weighted WRB so as to define the distance measure between batches in a more understandable way. The equivalence of the two objective functions was also proved. In addition, a clustering algorithm CACB (constrained agglomerative clustering of batches) was proposed based on the definition of WRB. To test the effectiveness of the proposed algorithm, the results obtained from CACB were compared with those from the previous methods, including BFLPT (best-fit longest processing time) heuristic and GA (genetic algorithm). CACB outperforms BFLPT and GA especially for large-scale problems.

Keywords:

• scheduling
• batch processing machine
• clustering
• makespan

Acknowledgements

The authors would like to thank Xiaolin Li, Qi Tan, Song Zhang for technical assistance. This work was supported by the National Natural Science Foundation of China (70821001), the Research Fund for the Doctoral Program of Higher Education 03580024), HKSAR ITF (GHP/042/07LP) and HKSAR RGC GRF (HKU 712508E).