TY - JOUR ID - 20018 TI - Lagrangian relaxation approach to minimize makespan for hybrid flow shop scheduling problem with unrelated parallel machines JO - Scientia Iranica JA - SCI LA - en SN - 1026-3098 AU - Asadi-Gangraj, Ebrahim AD - Babol Noshirvani University of Technology; Babol; Iran Y1 - 2018 PY - 2018 VL - 25 IS - 6 SP - 3765 EP - 3775 KW - Hybrid Flow Shop KW - Makespan KW - Lagrangian relaxation KW - simplification of subproblems KW - dominance rules DO - 10.24200/sci.2017.20018 N2 - 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 NP-hard, 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. UR - https://scientiairanica.sharif.edu/article_20018.html L1 - https://scientiairanica.sharif.edu/article_20018_eddf7e7037f7b901ffed1b036de0899c.pdf ER -