Heuristic algorithms for a practical-size dynamic parallel-machine scheduling problem: integrated-circuit wire bonding

Abstract

The parallel-machine scheduling problem has been an active research field over the past decades because of its practical applications. The present study proposes job-driven scheduling heuristic (JDSH) and machine-driven scheduling heuristic (MDSH) to solve a practical-size dynamic parallel-machine scheduling problem with stochastic failures. The proposed methodology is applicable for solving an identical, uniform or an unrelated parallel-machine scheduling problem. In addition, it is sufficiently robust to accommodate product mix or demand changes. A practical-size wire-bonding workstation from an integrated-circuit packaging plant is adopted for the empirical application. The empirical results are promising, and lead to the use of MDSH as the scheduler a priori. The proposed heuristics are suitable for practical application due to their efficiency and effectiveness. When an automatic shop-floor control system is available, the proposed heuristics are seen to be superior schedulers for providing a real-time scheduling decision.

Keywords:

• integrated-circuit packaging
• parallel-machine
• scheduling
• simulation
• wire bonding

Acknowledgements

The authors thank the anonymous company for providing the case study. The reviewers provided helpful comments that greatly improved the study. This study was supported, in part, by the National Science Council of Taiwan, Republic of China, under grant no. NSC98-2221-E006-100-MY3.