Lagrangian relaxation approach to minimizing makespan in hybrid flow shop scheduling problem with unrelated parallel machines

This research addresses scheduling problem of n jobs in a Hybrid Flow Shop (HFS) with unrelated parallel machines in each stage. A monolithic Mixed Integer Linear Programming (MILP) model is presented to minimize the maximum completion time (makespan). As the research problem is shown to be strongly NP-hard, a Lagrangian Relaxation (LR) algorithm is developed to handle the HFS scheduling problem. We design two approaches, namely, simplification of subproblems and dominance rules, to solve the subproblems which are generated in each iteration. For evaluation purposes, numerical experiments with small-and large-size problems are randomly generated with up to 50 jobs and 4 stages. The experimental results show that the Lagrangian relaxation approaches outperform the MILP model with respect to CPU time. Furthermore, from the results, it can be concluded that the simplification of subproblems shows slightly better solutions than dominance rules do in solving the subproblems.