標題: Algorithms for the wafer probing scheduling problem with sequence-dependent set-up time and due date restrictions
作者: Pearn, WL
Chung, SH
Yang, MH
Chen, YH
交大名義發表
National Chiao Tung University
關鍵字: parallel-machine scheduling problem;wafer probing;sequence-dependent set-up time;savings algorithm;vehicle-routing;problem with time windows
公開日期: 1-十一月-2004
摘要: 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.
URI: http://dx.doi.org/10.1057/palgrave.jors.2601795
http://hdl.handle.net/11536/25671
ISSN: 0160-5682
DOI: 10.1057/palgrave.jors.2601795
期刊: JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY
Volume: 55
Issue: 11
起始頁: 1194
結束頁: 1207
顯示於類別:期刊論文