《2016 Column generation heuristics for multiple machine》.pdf

Ann Oper Res (2008) 159: 261–273 DOI 10.1007/s10479-007-0281-2 Column generation heuristics for multiple machine, multiple orders per job scheduling problems Jagadish Jampani · Scott J. Mason Published online: 1 December 2007 © Springer Science+Business Media, LLC 2007 Abstract Front opening unified pods (FOUPs) are used to store and transport silicon wafers in 300-mm semiconductor wafer fabs. To achieve production efficiencies, wafers are grouped together in FOUPs without regard to the originating customer placing the order. In the resulting multiple orders per job (moj) scheduling problem, scheduling is performed at the FOUP (i.e., aggregated order) level, while scheduling performance is assessed per in- dividual customer order. Column generation heuristics are presented for single and parallel machine moj scheduling problems to minimize total weighted order completion time. The proposed heuristics obtain near-optimal solutions very quickly, outperforming competing approaches in the literature. Keywords Semiconductor manufacturing · Column generation · Machine scheduling 1 Introduction The last decade has seen tremendous growth in the semiconductor manufacturing indus- try. With the increasing demand for semiconductor-based products, the industry is trying to meet ever tightening customer deadlines and simultaneously evolve into more efficient production units. The demand for on-time delivery of high quality products has motivated the manufacturers to implement technologies based on dispatching and scheduling to reduce the production time. Efficient scheduling of the available resources is an effective method to achieve the organizational goals of on-time deliveries of products at low production cost. Semiconductor manufacturing can be divided into four phases: wafer fabrication, wafer probe, assembly, and final testing (Uzsoy et al. 1992). Wafer fabrication is the most complex phase with a number of process