lagrangian relaxation approach to minimize makespan for hybrid flow shop scheduling problem with unrelated parallel machines

This research addresses scheduling problem of n jobs on 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 nphard, a lagrangian relaxation (lr) algorithm is developed to handle the hfs scheduling problem. we design two approaches, 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 four 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 conclude that the simplification of subproblems shows slightly better solutions in comparison with dominance rules to solve the subproblems.