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

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. The performance of the heuristic and Lagrangian relaxation are compared with optimal solutions experimentally.