Bidirectional Flow Shop Scheduling with Multi-Machine Capacity and Critical Operations Sequencing

• Main Authors: ZHAO, ZhengYi, LEONG, Thin Yin, Ge, Shuzhi Sam, LAU, Hoong Chuin
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2007
• Subjects: Flow shop; Job shop; Machine capacity; Critical operation sequencing; Artificial Intelligence and Robotics; Business; Operations Research, Systems Engineering and Industrial Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/398
• Institution: Singapore Management University

We study a special bidirectional flow shop problem with multi-machine capacity and sequencing constraints on critical operations. A formulation is proposed in continuous time domain and compared with a mixed integer programming (MIP) formulation in discrete time domain. Of particular interest to us is the formulation of the machine utilization function - both in continuous time and in discrete time domain. Fast heuristics are proposed with the relaxation of the machine capacity. A Lagrangian-based heuristics procedure is used to further reduce the duality gap. The performance of the heuristic and Lagrangian relaxation is compared with optimal solutions experimentally.