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

doi:10.1007/s40305-019-00277-6

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

CLC Number:

90B35

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.

TrendMD

References

[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)