A Genetic Algorithm to Minimize the Makespan in a Two-Machine Cross-Docking Flow Shop Problem

doi:10.1007/s40305-019-00277-6

Journal of the Operations Research Society of China ›› 2020, Vol. 8 ›› Issue (3): 457-476.doi: 10.1007/s40305-019-00277-6

所属专题： Stochastic optimization； Scheduling

• Special Issue: Operations Research Models and Algorithms in Transportation • 上一篇下一篇

收稿日期:2018-10-26 修回日期:2019-05-15 出版日期:2020-09-30 发布日期:2020-09-10
通讯作者: Imen Hamdi, Mohamed Fadhel Tekaya E-mail:imen.hamdi2007@yahoo.fr;fadhel.tekaya@gmail.com

A Genetic Algorithm to Minimize the Makespan in a Two-Machine Cross-Docking Flow Shop Problem

Imen Hamdi^1,2, Mohamed Fadhel Tekaya¹

1 High Institute of Transport and Logistics, University of Sousse, Sousse, Tunisia;
2 MODILS lab, Faculty of Economics and Management, University of Sfax, Sfax, Tunisia

Received:2018-10-26 Revised:2019-05-15 Online:2020-09-30 Published:2020-09-10
Contact: Imen Hamdi, Mohamed Fadhel Tekaya E-mail:imen.hamdi2007@yahoo.fr;fadhel.tekaya@gmail.com

摘要/Abstract

Abstract: We consider the problem of two-machine cross-docking flow shop scheduling where each job on the second machine cannot be processed unless a job or a set of jobs have been completed on the first machine. The aim is to find a feasible schedule that minimizes the makespan. As the problem is shown to be strongly NP-hard, we propose a genetic algorithm to solve small and large size problems. We test different types for each genetic operator where new ideas are introduced, which leads to propose six versions of the genetic algorithm. We then evaluate their effectiveness through an extensive computational experiments by using many instances generated randomly and by determining the percentage deviation from a lower bound from the literature.

Key words: Cross-docking, Flow shop, Scheduling, Makespan, Genetic algorithm

中图分类号:

90B35

. [J]. Journal of the Operations Research Society of China, 2020, 8(3): 457-476.

Imen Hamdi, Mohamed Fadhel Tekaya. A Genetic Algorithm to Minimize the Makespan in a Two-Machine Cross-Docking Flow Shop Problem[J]. Journal of the Operations Research Society of China, 2020, 8(3): 457-476.

[1] Bartholdi Ⅲ, J.J., Gue, K.R.:The best shape for a crossdock. Transp. Sci. 38, 235-44(2004)
[2] Li, Y., Lim, A., Rodrigues, B.:Crossdocking-JIT scheduling with time windows. J. Oper. Res. Soc. 55, 1342-51(2004)
[3] Vahdani, B., Zandieh, M.:Scheduling trucks in cross-docking systems:robust meta-heuristics. Comput. Ind. Eng. 58, 12-24(2010)
[4] Kinnear, E.:Is there any magic in cross-docking? Supply Chain Manag. Int. J. 2, 49-52(1997)
[5] Sheikholeslam, M.N., Emamian, S.:A review and classification of cross-docking concept. Int. J. Learn. Manag. Syst. 4, 25-33(2016)
[6] VanBelle,J.,Valckenaers,P.,Cattrysse,D.:Cross-docking:stateoftheart.Omega 40,827-846(2012)
[7] Stalk, G., Evans, P., Shulman, L.E.:Competing on capabilities:the new rules of corporate strategy. Harv. Bus. Rev. 70, 57-69(1992)
[8] Witt, C.E.:Crossdocking:concepts demand choice. Mater. Handl. Eng. 53, 44-9(1998)
[9] Forger, G.:UPS starts world's premiere cross-docking operation. Mod. Mater. Handl. 50, 36-38(1995)
[10] Cook, R.L., Gibson, B., MacCurdy, D.:A lean approach to crossdocking. Supply Chain Manag. Rev. 9, 54-9(2005)
[11] Yazdani, M., Naderi, B., Rahmani, S., Rahmani, S.:Truck routing and scheduling for cross-docking in the supply chain:model and solution method. RAIRO Oper. Res. 51, 833-856(2017)
[12] Fonseca, G.B., Nogueira, T.H., Ravetti, M.G.:A hybrid Lagrangean metaheuristic for the twomachine cross-docking flow shop scheduling problem. Cornell University Library, arXiv. org -math - arXiv:1702.05603, (2017)
[13] Ladier, A.L., Alpen, G.:Robust cross-dock scheduling with time windows. Comput. Ind. Eng. 99, 16-28(2016)
[14] Zhao, H., Chen, L.:Hybrid particle swarm optimization for two-stage cross docking scheduling. Int. J. Hybrid Inf. Technol. 8, 249-266(2015)
[15] Graham, R., Lawler, E., Lenstra, J.K., Rinnooy, Kan A.H.G.:Optimization and approximation in deterministic sequencing and scheduling:a survey. Ann. Discret. Math. 5, 287-326(1997)
[16] Chen, F., Lee, C.Y.:Minimizing the makespan in a two-machine cross-docking flow shop problem. Eur. J. Oper. Res. 193, 59-72(2009)
[17] Chen, F., Song, K.L.:Crossdocking logistics scheduling problem and its approximation and exact algorithms. Ind. Eng. Manag. 6, 53-58(2006)
[18] Ma, D.Y., Chen, F.:Dynamic programming algorithm on two machines cross docking scheduling. J. Shanghai Jiao Tong Univ. 41, 852-856(2007)
[19] Prot, D., Rapine, C.:Approximations for the two-machine cross-docking flow shop problem. Discrete Appl. Math. 161, 2107-2119(2013)
[20] Romanova, A.:Algorithms for minimizing the makespan in a two-machine cross-docking flow shop problem. J. Appl. Ind. Math. 9, 570-579(2015)
[21] Ruiz, R., Maroto, C., Alcaraz, J.:Two new robust genetic algorithms for the flowshop scheduling problem. Omega 34, 461-476(2006)

相关文章 15

[1]	. [J]. Journal of the Operations Research Society of China, 2026, 14(2): 489-501.
[2]	. [J]. Journal of the Operations Research Society of China, 2026, 14(2): 547-564.
[3]	. [J]. Journal of the Operations Research Society of China, 2026, 14(2): 653-670.
[4]	. [J]. Journal of the Operations Research Society of China, 2026, 14(1): 129-148.
[5]	. [J]. Journal of the Operations Research Society of China, 2025, 13(4): 1157-1180.
[6]	. [J]. Journal of the Operations Research Society of China, 2025, 13(2): 590-602.
[7]	. [J]. Journal of the Operations Research Society of China, 2025, 13(2): 603-615.
[8]	. [J]. Journal of the Operations Research Society of China, 2024, 12(4): 1088-1102.
[9]	. [J]. Journal of the Operations Research Society of China, 2024, 12(4): 1126-1138.
[10]	. [J]. Journal of the Operations Research Society of China, 2024, 12(3): 681-693.
[11]	. [J]. Journal of the Operations Research Society of China, 2024, 12(2): 341-350.
[12]	. [J]. Journal of the Operations Research Society of China, 2023, 11(3): 693-706.
[13]	. [J]. Journal of the Operations Research Society of China, 2022, 10(1): 113-131.
[14]	. [J]. Journal of the Operations Research Society of China, 2021, 9(4): 909-914.
[15]	. [J]. Journal of the Operations Research Society of China, 2021, 9(2): 359-373.

A Genetic Algorithm to Minimize the Makespan in a Two-Machine Cross-Docking Flow Shop Problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

相关文章 15

编辑推荐

Metrics

本文评价