《2016 A column generation heuristic for complex job shop multiple orders per job scheduling 》.pdf

Computers Industrial Engineering 58 (2010) 108–118 Contents lists available at ScienceDirect Computers Industrial Engineering journal homepage: /locate/caie A column generation heuristic for complex job shop multiple orders per job scheduling q Jagadish Jampani, Scott J. Mason * University of Arkansas, 4207 Bell Engineering Center, Fayetteville, AR 72701, USA a r t i c l e i n f o a b s t r a c t Article history: Scheduling in semiconductor manufacturing is a challenging task due to inherent complexities like Received 10 September 2008 assignment of multiple customer orders to front opening unified pods (FOUPs), batch processing in multi- Received in revised form 29 July 2009 ple toolgroups with parallel machines, and re-entrant flow. A disjunctive–network-flow mixed integer Accepted 21 September 2009 program (DNF) and a column generation heuristic are presented to minimize the sum of weighted cus- Available online 24 September 2009 tomer order completion times in a complex job shop environment. In addition, a lower bound estimation approach for the complex job shop problem is presented. The column generation heuristic obtains solu- Keywords: tions that are very close to that of the time constrained DNF formulation for problem instances with zero Optimization order ready times. However, column generation’s performance differs conside