Title: Minimising makespan for single burn-in oven scheduling problems using ACO+DP approach

Authors: Hao Shao, Hua-ping Chen

Addresses: School of Management, University of Science and Technology of China, Hefei, Anhui, 230026, China. ' School of Management, University of Science and Technology of China, Hefei, Anhui, 230026, China

Abstract: This paper considers minimising makespan on a single batch processing machine where jobs have dynamic release time and non-identical sizes in burn-in operation of semiconductor final testing. The machine can process one batch at a time as long as its capacity is not exceeded. The processing time of a batch equals to the longest processing time of all jobs in that batch. The problem is proven to be NP-hard and hence a hybrid Ant Colony Optimisation (ACO) method was proposed combined with Dynamic Programming (DP) technique. Computational results show that the joint ACO+DP approach performs considerably well on all instances. [Received 9 April 2009; Revised 27 June 2009; Accepted 13 October 2009]

Keywords: manufacturing research; batch scheduling; ACO; ant colony optimisation; dynamic programming; single burn-in ovens; makespan; semiconductor testing; final testing; semiconductor manufacturing.

DOI: 10.1504/IJMR.2010.033467

International Journal of Manufacturing Research, 2010 Vol.5 No.3, pp.271 - 285

Published online: 02 Jun 2010 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article