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

Document Type : Article


Babol Noshirvani University of Technology; Babol; Iran


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.


Main Subjects

1. Liao, C.J., Tjandradjaja, E., and Chung, T.P. An
approach using particle swarm optimization and bottleneck
heuristic to solve hybrid
ow shop scheduling
problem", Appl. Soft Comput., 12, pp. 1755-1764
2. Agnetis, L., Paci ci, A., Rossi, F., Lucertini, M.,
Nicoletti, S., and Nicolo, F. Scheduling of
shop in an automobile assembly plant", Eur. J. Oper.
Res., 97(2), pp. 348- 362 (1997).
3. Adler, L., Fraiman, N., Kobacker, E., Pinedo, M.,
Plotnico , J.C., and Wu, T.P. BPSS: a scheduling
support system for the packaging industry", Oper. Res,
41, pp. 641-648 (1993).
4. Shahvari, O., Salmasi, N., Logendran, L., and Abbasi,
B. An ecient tabu search algorithm for
shop sequence dependent group scheduling problems",
Int. J. Prod. Res., 50, 15, pp. 4237-4254 (2012).
5. Moursli, O. and Pochet, Y. A branch and- bound
algorithm for the hybrid
owshop", Int. J. Prod. Econ.,
64, pp. 113-25 (2000).
6. Liu, C.Y. and Chang, S.C. Scheduling
shops with sequence-dependent setup e ects", IEEE
Transaction on Robotics and Automation, 16(4), pp.
408-419 (2000).
7. Fattahi, P., Hosseini, S.M.H., Jolai, F., and Tavakkoli-
Moghaddam, R.A. Branch and bound algorithm for
ow shop scheduling problem with setup time
and assembly operations", Appl. Math. Model, 38, pp.
119-134 (2014).
8. Riane, F., Artibas, A., and Elmaghraby, S.E. A hybrid
three stage
ow shop problem: ecient heuristics
to minimize makespan", Eur. J. Oper. Res., 109, pp.
321-329 (1998).
E. Asadi-Gangraj/Scientia Iranica, Transactions E: Industrial Engineering 25 (2018) 3765{3775 3775
9. Linn, R. and Zhang, W. Hybrid
ow shop scheduling:
a survey", Comput. Ind. Eng., 37, pp. 57-61 (1999).
10. Marichelvam, M.K., Prabaharan, T., Yang, X., and
Geetha, M. Solving hybrid
ow shop scheduling
problems using bat algorithm", Int. J. Logist Econ
Glob, 5(1), pp. 15-29 (2013).
11. Jolai, F., Ase , H., Rabiee, M., and Ramezani, P.
Bi-objective simulated annealing approaches for nowait
ow shop scheduling problem",
Scientia Iranica, 20(3), pp. 861-872 (2013).
12. Marichelvam, M.K., Prabaharanb, T., and Yang, X.S.
Improved cuckoo search algorithm for hybrid
shop scheduling problems to minimize makespan",
Appl. Soft Comput., 19, pp. 93-101 (2014).
13. Jolai, F., Tavakkoli-Moghaddam, R., Rabiee, M., and
Gheisariha, E. An enhanced invasive weed optimization
for makespan minimization in a
exible fowshop
scheduling problem", Scientia Iranica, 21(3), pp. 1007-
1020 (2014).
14. Tang, L., Xuan, H., and Liu, J. A new Lagrangian
relaxation algorithm for hybrid
owshop scheduling to
minimize total weighted completion time", Comput.
Oper. Res., 33, pp. 3344-3359 (2006).
15. Liu, G.D. and Luh, P.B. Scheduling permutation

ow shops using the Lagrangian relaxation technique",
Ann. Oper. Res., 70, pp. 171-89 (1997).
16. Luh, P.B. and Hoitomt, D.J. Scheduling of manufacturing
systems using the Lagrangian relaxation
technique", IEEE Transaction on Automatic Control,
38(7), pp. 1066-1079 (1993).
17. Chang, S.C., Liao, D.Y., and Hsieh, F.S. Scheduling

ow shops of no setup cost by a Lagrangian
relaxation and network
ow approach", Interactional
Conference on Robotics and Automation (1991).
18. Irohara, T. Lagrangian relaxation algorithms for
ow-shop scheduling problems with limited
bu ers", Biomed. Fuzzy Hum. Sci., 15(1), pp. 21-28
19. Sun, X. and Noble, J.S. An approach to job
shop scheduling with sequence- dependent setups", J.
Manuf. Syst., 18(6), 416-430 (1999).
20. Emami, S., Sabbagh, M., and Moslehi, Gh. A Lagrangian
relaxation algorithm for order acceptance and
scheduling problem: a globalized robust optimisation
approach", Int. J. Comput. Integ. Manuf., 29(5), pp.
535-560 (2016). DOI: 10.1080/0951192X.2015.1068452.
21. Shishebori, D., Youse Babadi, A., and Noormohammadzadeh,
Z. A Lagrangian relaxation approach to
fuzzy robust multi-objective facility location network
design problem", Scientia Iranica, 25(3), pp. 1750-
1767 (2018).
22. Nahavandi, N. and Asadi Gangraj, E. A new lower
bound foe
ow shop scheduling problem with
unrelated parallel machines", Int. J. Ind. Eng. Prod.
Res., 25(1), pp. 65-70 (2014).
23. Augusto, V., Xie, X., and Perdomo, V. Operating
theatre scheduling using Lagrangian relaxation", Eur.
J. Ind. Eng., 2(2), pp. 172-189 (2008).
24. Smith, J.C. and Sonuc, S.B. An introduction to
integer and large-scale linear optimization, wireless
network design", Int. Ser. in Oper. Res. Manag. Sci.,
158, pp. 65-97 (2011).
25. Lenstra, J.K., Rinnooy Kan, A.H.G., and Bruker, P.
Complexity of machine scheduling problems", Annals
of Discrete Mathematics, 1, pp. 343-62 (1977).
26. Salmasi N., Logendran, R., and Skandari, M.R. Total

FLow time minimization in a
ow shop sequencedependent
group scheduling problem", Computers &
Operations Research, 37, pp. 199-212 (2010).
27. Polyak, B.T. Introduction to optimization", Optimization
Software, Inc., New York (1987).