Developing a Lagrangian Relaxation Method for Flexible Flowshop Scheduling Problem

Flexible flow shop scheduling problem (FFS) with unrelated parallel machines contains sequencing in flow shop where, at any stage, there exists one or more unrelated parallel machines. The objective consists of minimizing the maximum completion time. A new Lagrangian relaxation (LR) method is developed to solve the candidate problem. To solve the sub-problems in LR, we use two approaches such as, simplicity of sub-problems and dominance rules. The results show that the both approaches can achieve the near-optimal solution in reasonable time; but there is no significant difference between them. On the other side, simplicity of sub-problems can achieve the solution in reasonable time.