Minimising makespan on a single batch processing machine with dynamic job arrivals and non-identical job sizes

Abstract

Batch scheduling is a prevalent policy in many industries such as burn-in operations in semiconductor manufacturing and heat treatment operations in metalworking. In this paper, we consider the problem of minimising makespan on a single batch processing machine in the presence of dynamic job arrivals and non-identical job sizes. The problem under study is NP-hard. Consequently, we develop a number of efficient construction heuristics. The performance of the proposed heuristics is evaluated by comparing their results to two lower bounds, and other solution approaches published in the literature, namely the first-fit longest processing time-earliest release time (FFLPT-ERT) heuristic, hybrid genetic algorithm (HGA), joint genetic algorithm and dynamic programming (GA+DP) approach and ant colony optimisation (ACO) algorithm. The computational experiments demonstrate the superiority of the proposed heuristics with respect to solution quality, especially for the problems with small size jobs. Moreover, the computational costs of the proposed heuristics are very low.

Keywords:

• scheduling
• batch processing machine
• makespan
• heuristics

Notes

This work was supported in part by the National Natural Science Foundation of China (No. 71171184/71201151), the Funds for Creative Research Group of China (No. 70821001), the NSFC major program (No. 71090401/71090400), the Cai Yuanpei Program of the French Ministries of Foreign and European Affairs and the Chinese Ministry of Education (No. 27927VE), the Postdoctoral Science Foundation of China (No. 2011M501067/2013T60628) and the Fundamental Research Funds for the Central Universities (No. WK0110000032). This research also received funding from the University of Tennessee Health Information Technology & Simulation (HITS) Laboratory.