Solution strategies for multi-stage wafer probing scheduling problem with reentry

W.l. Pearn, S. H. Chung, M. H. Yang, K. P. Shiao

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


The multi-stage wafer probing scheduling problem (M-WPSP) with reentry is a practical variation of the parallel-machine scheduling problem. Since the M-WPSP involves multiple product families, to be processed on multiple stages, with various job due dates, ready times, reentry, serial and batch operations, sequential-dependent setup time, it is more difficult to solve than the classical parallel-machine scheduling problems. In this paper, we consider two strategies to solve the M-WPSP with reentry, where the total machine workload must be minimized. These two strategies incorporate a global planning mechanism, in advance, to determine the required stage due date of job at each process stage to prevent the due date problems occurring at the final stage. The sequential strategy schedules the jobs at the required stages according to the sequence of manufacturing process. The parallel strategy is designed specifically for the reentrant characteristic. To evaluate the efficiency of the proposed strategies, a set of test problems involving four critical factors, the product family ratio, the temperature-change consideration, the tightness of due dates, and the ready time, are designed to test the quality of solutions under two levels of workload.

Original languageEnglish
Pages (from-to)637-651
Number of pages15
JournalJournal of the Operational Research Society
Issue number5
StatePublished - 13 May 2008


  • Identical parallel machine
  • Multi-stage
  • Reentry
  • Sequential dependent setup time
  • Wafer probing

Fingerprint Dive into the research topics of 'Solution strategies for multi-stage wafer probing scheduling problem with reentry'. Together they form a unique fingerprint.

Cite this