Algorithms for the wafer probing scheduling problem with sequence-dependent set-up time and due date restrictions

Abstract

In this paper, we consider the wafer probing scheduling problem (WPSP) to sequence families of jobs on identical parallel machines with due date restrictions. The machine set-up time is sequentially dependent on the product types of the jobs processed on the machine. The objective is to minimize the total machine workload without violating the machine capacity and job due date restrictions. The WPSP is a variation of the classical parallel-machine scheduling problem, that can be transformed into the vehicle-routing problem with time windows (VRPTW). One can therefore solve the WPSP efficiently using existing VRPTW algorithms. We apply four existing savings algorithms presented in the literature including sequential, parallel, generalized, and matching based savings, and develop three modifications called the modified sequential, the compound matching based, and the modified compound matching-based savings algorithms, to solve the WPSP. Based on the characteristics of the wafer probing process, a set of test problems is generated for testing purposes. Computational results show that the three proposed modified algorithms perform remarkably well.

Keywords:

• parallel-machine scheduling problem
• wafer probing
• sequence-dependent set-up time
• savings algorithm
• vehicle-routing problem with time windows

Acknowledgements

This paper was supported in part by the National Science Council, Taiwan, ROC, under the contract NSC 90-2218-E-239-004. We thank the anonymous referees for their helpful comments, which improved the paper.