Bi-objective scheduling for the re-entrant hybrid flow shop with learning effect and setup times

Document Type : Article


1 Department of Industrial Engineering, Mazandaran University of Science and Technology, Babol, Iran

2 Department of Industrial Management, Management and Accounting Faculty, Shahid Beheshti University, G. C., Tehran, Iran


The production scheduling problem in hybrid flow shops is a complex combinatorial optimization problem observed in many real-world applications. The standard hybrid flow shop problem involves often unrealistic assumptions. In order to address the realistic assumptions, four additional traits were added to the proposed problem. These include re-entrant line, setup times, position-dependent learning effects, and the consideration of maximum completion time together with total tardiness as objective function. Since the proposed problem is non-deterministic polynomial-time (NP)-hard, a meta-heuristic algorithm is proposed as the solution procedure. The solution procedure is categorized as an a priori approach. To show the efficiency and effectiveness of the proposed algorithm, computational experiments were done on various test problems. Computational results show that the proposed algorithm can obtain an effective and appropriate solution quality for our investigated problem


Main Subjects

1. Allahverdi, A., Ng, C.T., Cheng, T.C.E., and Kovalyov,
M.Y. A survey of scheduling problems with
setup times or costs", European J. Oper. Res., 187(3),
pp. 985-1032 (2008).
2. Lin, D. and Lee, C.K.M. A review of the research
methodology for the re-entrant scheduling problem",
Int. J. Prod. Res., 49(8), pp. 2221-2242 (2011).
3. Biskup, D.A. Single machine scheduling with learning
considerations", European J. Oper. Res., 115(1), pp.
173-178 (1999).
4. Biskup, D.A. A state-of-the-art review on scheduling
with learning e ects", European J. Oper. Res., 188(2),
pp. 315-329 (2008).
5. Gupta, J.N.D. Two-stage, hybrid
ow shop scheduling
problem", J. Oper. Res. Soc., 39(4), pp. 359-364
6. Jungwattanakit, J., Reodecha, M., Chaovalitwongse,
P., and Werner, F. Algorithms for
shop problems with unrelated parallel machines, setup
times, and dual criteria", Int. J. Adv. Manuf. Technol.,
37(3), pp. 354-370 (2008).
7. Behnamian, J., Fatemi Ghomi, S.M.T., and Zandieh,
M. A multi-phase covering Pareto-optimal front
method to multi-objective scheduling in a realistic
owshop using a hybrid metaheuristic", Expert
Syst. Appl., 36(8), pp. 11057-11069 (2009).
8. Naderi, B., Zandieh, M., Khaleghi Ghoshe Balagh, A.,
and Roshanaei, V. An improved simulated annealing
for hybrid
owshops with sequence-dependent setup
and transportation times to minimize total completion
time and total tardiness", Expert Syst. Appl., 36(6),
pp. 9625-9633 (2009).
9. Rashidi, E., Jahandar, M., and Zandieh, M. An
improved hybrid multi-objective parallel genetic algorithm
for hybrid
ow shop scheduling with unrelated
parallel machines", Int. J. Adv. Manuf. Technol.,
49(9), pp. 1129-1139 (2010).
10. Dugardin, F., Yalaoui, F., and Amodeo., L. New
multi-objective method to solve reentrant hybrid
shop scheduling problem", European J. Oper. Res.,
203(1), pp. 22-31 (2010).
11. Cho, H-M., Bae, S-J., Kim, J., and Jeong, I-J. Biobjective
scheduling for reentrant hybrid
ow shop
using Pareto genetic algorithm", Comput. Ind. Eng.,
61(3), pp. 529-541 (2011).
12. Mousavi, S.M., Zandieh, M., and Yazdani, M. A simulated
annealing/local search to minimize the makespan
and total tardiness on a hybrid
owshop", Int. J. Adv.
Manuf. Technol., 64(1), pp. 369-388 (2012).
13. Mousavi, S.M., Mousakhani, M., and Zandieh, M. Biobjective
ow shop scheduling: a new local
search", Int. J. Adv. Manuf. Technol., 64(5), pp. 933-
950 (2012).
14. Hakimzadeh Abyaneh, S. and Zandieh, M. Biobjective
ow shop scheduling with sequencedependent
setup times and limited bu ers", Int. J.
Adv. Manuf. Technol., 58(1), pp. 309-325 (2012).
15. Pargar, F. and Zandieh, M. Bi-criteria SDST hybrid

ow shop scheduling with learning e ect of setup times:
ow-like algorithm approach", Int. J. Prod. Res.,
50(10), pp. 2609-2623 (2012).
16. Sheikh, S. Multi-objective
ow lines with due
window, time lag, and job rejection", Int. J. Adv.
Manuf. Technol., 64(9), pp. 1423-1433 (2013).
17. Tadayon, B. and Salmasi, N. A two-criteria objective
owshop scheduling problem with
machine eligibility constraint", Int. J. Adv. Manuf.
Technol., 64(5), pp. 1001-1015 (2013).
18. Behnamian, J. and Zandieh, M. Earliness and tardiness
minimizing on a realistic hybrid
owshop scheduling
with learning e ect by advanced metaheuristic",
Arab. J. Sci. Eng., 38(5), pp. 1229-1242 (2013).
19. Fadaei, M. and Zandieh, M. Scheduling a bi-objective
ow shop with sequence-dependent family setup
times using metaheuristics", Arab. J. Sci. Eng., 38(8),
pp. 2233-2244 (2013).
S.M. Mousavi et al./Scientia Iranica, Transactions E: Industrial Engineering 25 (2018) 2233{2253 2253
20. Jolai, F., Ase , H., Rabiee, M., and Ramezani, P. Biobjective
simulated annealing approaches for no-wait
ow shop scheduling problem", Sci.
Iran., 20(3), pp. 861-872 (2013).
21. Luo, H., Du, B., Huang, G.Q., Chen, H., and Li,
X. Hybrid
ow shop scheduling considering machine
electricity consumption cost", Int. J. Prod. Econ,
146(2), pp. 423-439 (2013).
22. Tran., T.H. and Ng, K.M. A Hybrid water
ow algorithm
for multi-objective
ow shop scheduling
problem", Eng. Optim., 45(4), pp. 483-502 (2013).
23. Su, S., Yu, H., Wu, Z., and Tian, W. A distributed
coevolutionary algorithm for multiobjective hybrid

owshop scheduling problems", Int. J. Adv. Manuf.
Technol., 70(1), pp. 477-494 (2014).
24. Attar, S.F., Mohammadi, M., Tavakkoli-Moghaddam,
R., and Yaghoubi, S. Solving a new multi-objective
owshop problem with limited waiting
times and machine-sequence-dependent set-up time
constraints", Int. J. Comput. Integr. Manuf., 27(5),
pp. 450-469 (2014).
25. Wang, S. and Liu, M. Two-stage hybrid
ow shop
scheduling with preventive maintenance using multiobjective
tabu search method", Int. J. Prod. Res.,
52(5), pp. 1495-1508 (2014).
26. Ying, K.C., Lin, S.W., and Wan, S.Y. Bi-objective
reentrant hybrid
owshop scheduling: an iterated
Pareto greedy algorithm", Int. J. Prod. Res., 52(19),
pp. 5735-5747 (2014).
27. Mousavi, S.M. and Zandieh, M. An ecient hybrid
algorithm for a bi-objectives hybrid
ow shop
scheduling", Intell Autom Soft Co (2016). DOI:
10.1080/10798587.2016.1261956 (2016).