×

zbMATH — the first resource for mathematics

A hybrid Lagrangian metaheuristic for the cross-docking flow shop scheduling problem. (English) Zbl 1430.90261
Summary: Cross-docking is a logistics strategy that minimizes the storage and picking functions of conventional warehouses. The objective is to unload the cargo from inbound trucks and directly load it into outbound trucks, with little or no storage. The success of the strategy depends on an efficient transshipment operation. This work undertakes a study of truck scheduling in a parallel dock cross-docking center. The problem is first modeled as a two-machine flow shop scheduling problem with precedence constraints, with the objective of minimizing the makespan, and later, we generalize it to the parallel-dock case. We propose a hybrid method based on a Lagrangian relaxation technique through the volume algorithm. Using information from the Lagrangian multipliers, constructive heuristics with local search procedures generates good feasible solutions. With a series of cuts, the methodology finds tight bounds for small and large instance sizes, outperforming current results.

MSC:
90B35 Deterministic scheduling theory in operations research
90B06 Transportation, logistics and supply chain management
90C10 Integer programming
90C59 Approximation methods and heuristics in mathematical programming
Software:
SPOT
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alba, E., Parallel metaheuristics: A new class of algorithms, 47, (2005), Wiley · Zbl 1094.90052
[2] Alpan, G.; Bauchau, S.; Larbi, R.; Penz, B., Optimal operations scheduling in a crossdock with multi strip and multi stack doors, Proceedings of the thirty-eight international conference on computers and industrial engineering (CIE38), 2, 1168-1176, (2008)
[3] Alpan, G.; Larbi, R.; Penz, B., A bounded dynamic programming approach to schedule operations in a cross docking platform, Computers & Industrial Engineering, 60, (3), 385-396, (2011)
[4] Arabani, A. B.; Ghomi, S. F.; Zandieh, M., Meta-heuristics implementation for scheduling of trucks in a cross-docking system with temporary storage, Expert Systems with Applications, 38, 3, 1964-1979, (2011)
[5] Araújo, D. P. M., & Melo, B. M. R. (2010). Heurísticas construtivas para o sequenciamento de caminhões em centros de cross-docking Master’s thesisUniversidade Federal de Minas Gerais.
[6] Arroyo, J., Nunes, G., & Kamke, E. (2009). Iterative local search heuristic for the single machine scheduling problem with sequence dependent setup times and due datesIn Proceedings of the ninth international conference on hybrid intelligent systems, 1, 505-510.
[7] Bahiense, L.; Maculan, N.; Sagastizabal, C., The volume algorithm revised: Relation with bundle methods, Mathematical Programming, 94, 41-69, (2002) · Zbl 1023.90038
[8] Barahona, F.; Anbil, R., The volume algorithm: Producing primal solutions with a subgradient method, Mathematical Programming, 87, 3, 385-399, (2000) · Zbl 0961.90058
[9] Barahona, F.; Ladányi, L., Branch and cut based on the volume algorithm: Steiner trees in graphs and max-cut, RAIRO Operations Research, 40, 53-73, (2006) · Zbl 1146.90090
[10] Bartholdi, J.; Gue, K., Reducing labor costs in an LTL crossdocking terminal, Operations Research, 48, 6, 823-832, (2002)
[11] Bartz-Beielstein, T. (2010). SPOT: An R package for automatic and interactive tuning of optimization algorithms by sequential parameter optimization. arXiv:1006.4645v1.
[12] Bartz-Beielstein, T.; Zaefferer, M., A gentle introduction to sequential parameter optimization, Technical Report 2, (2012), Bibliothek der Fachhochschule Koeln
[13] Belle, J. V.; Valckenaers, P.; Cattrysse, D., Cross-docking: State of the art, Omega, 40, 827-846, (2012)
[14] Blum, C.; Puchinger, J.; Raidl, G.; Roli, A., Hybrid metaheuristics in combinatorial optimization: A survey, Applied Soft Computing, 11, 6, 4135-4151, (2011)
[15] Boschetti, M.; Maniezzo, V., Benders decomposition, Lagrangean relaxation and metaheuristic design, Journal of Heuristics, 15, 3, 283-312, (2009) · Zbl 1176.90485
[16] Boysen, N., Truck scheduling at zero-inventory cross docking terminals, Computers & Operations Research, 37, 1, 32-41, (2010) · Zbl 1171.90391
[17] Boysen, N.; Fliedner, M., Cross dock scheduling: Classification, literature review and research agenda, Omega, 38, 6, 413-422, (2010)
[18] Boysen, N.; Fliedner, M.; Scholl, A., Scheduling inbound and outbound trucks at crossdocking terminals, OR Spectrum, 32, 1, 135-161, (2010) · Zbl 1181.90111
[19] Bozer, Y.; Carlo, H., Optimizing inbound and outbound door assignments in less-than-truckload crossdocks, IIE Transactions, 40, 1007-1018, (2008)
[20] Campbell, J., A survey of network hub location, Studies in Locational Analysis, 6, 31-49, (1994)
[21] Chen, F.; Lee, C.-Y., Minimizing the makespan in a two-machine cross-docking flow shop problem, European Journal of Operational Research, 193, 1, 59-72, (2009) · Zbl 1152.90433
[22] Chen, F.; Song, K., Minimizing makespan in two-stage hybrid cross docking scheduling problem, Computers & Operations Research, 36, 6, 2066-2073, (2009) · Zbl 1179.90032
[23] Chen, J., A hybrid heuristic for the uncapacited single allocation hub location problem, Omega, 35, 211-220, (2007)
[24] Chen, P.; Guo, Y.; Lim, A.; Rodrigues, B., Multiple crossdocks with inventory and time windows, Computers and Operations Research, 33, 43-46, (2006) · Zbl 1089.90007
[25] Clausen, J.; Cordeau, J.; Laporte, G.; Wen, M.; J., L., Vehicle routing scheduling with cross-docking, Journal of the Operational Research Society, 60, 1708-1718, (2009) · Zbl 1196.90027
[26] Cota, P. M.; Gimenez, B. M.; Araújo, D. P.; Nogueira, T. H.; de Souza, M. C.; Ravetti, M. G., Time-indexed formulation and polynomial time heuristic for a multi-dock truck scheduling problem in a cross-docking centre, Computers & Industrial Engineering, 95, 135-143, (2016)
[27] Forger, G., Ups starts worlds premiere cross-docking operation, Modern material handling, 36, 8, 36-38, (1995)
[28] Fukuda, E. H. (2007). Algoritmo de volume e otimização não diferenciável Master’s thesis. USP.
[29] Gue, K. R., The effects of trailer scheduling on the layout of freight terminals, Transportation Science, 33, (4), 419-428, (1999) · Zbl 0961.90503
[30] Kim, C.; Yang, K. H.; Kim, J., A strategy for third-party logistics systems: a case analysis using the blue ocean strategy, Omega, 36, 4, 522-534, (2008)
[31] Klose, A.; Drexl, A., Facility location models for distribution system design, European Journal of Operational Research, 162, 4-29, (2005) · Zbl 1132.90345
[32] Ladier, A.-L.; Alpan, G., Cross-docking operations: Current research versus industry practice, Omega, 62, 145-162, (2016)
[33] Larbi, R.; Alpan, G.; Baptiste, P.; Penz, B., Scheduling cross docking operations under full, partial and no information on inbound arrivals, Computers & Operations Research, 38, 6, 889-900, (2011) · Zbl 1205.90127
[34] Larbi, R.; Alpan, G.; Penz, B., Scheduling transshipment operations in a multiple inbound and outbound door crossdock, Proceedings of the thirty-ninth international conference on computers and industrial engineering (CIE39), (2009), Troyes, France
[35] Lee, K.; Lee, Y.; Jung, J., Positioning of goods in a cross-docking environment, Computers & Industrial Engineering, 54, 3, 677-689, (2008)
[36] Lemaréchal, C., An extension of Davidon methods to non differentiable problems, Nondifferentiable optimization, 95-109, (1975), Springer · Zbl 0358.90051
[37] Lemaréchal, C., Lagrangean relaxation, (Jünger, M.; Naddef, D., Computational combinatorial optimization. Lecture notes in computer science, 2241, (2001), Springer: Springer Berlin, Heidelberg)
[38] Lemaréchal, C., Chapter VII Nondifferentiable optimization, Handbooks in Operations Research and Management Science, 1, 529-572, (1989)
[39] Lima, M. F. (2014). O problema de sequenciamento de caminhões numa estação de cross-docking com duas máquinas: Formulação indexada no tempo, relaxação lagrangeana e geração de colunas Master’s thesis. Universidade Federal de Minas Gerais.
[40] McWilliams, D. L., Iterative improvement to solve the parcel hub scheduling problem, Computers & Operations Research, 59, 1, 136-144, (2010)
[41] Miao, Z.; Lim, A.; Ma, H., Truck dock assignment problem with operational time constraint within crossdocks, European Journal of Operational Research, 192, 1, 105-115, (2009) · Zbl 1181.90122
[42] Nawaz, M.; Enscore, J.; Ham, I., A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem, Omega, 11, 1, 91-95, (1983)
[43] Nogueira, T. H. (2014). Single machine scheduling problems with sequence-dependent setup times Ph.D. thesis. Universidade Federal de Minas Gerais.
[44] Oh, Y.; Hwang, H.; Chab, C.; Lee, S., A dock-door assignment problem for the Korean mail distribution center, Computers & Industrial Engineering, 51, 2, 288-296, (2006)
[45] Paula, M.; Mateus, G.; Ravetti, M., A non-delayed relax-and-cut algorithm for scheduling problems with parallel machines, due dates and sequence-dependent setup times, Computers & Operations Research, 37, 5, 938-949, (2010) · Zbl 1177.90196
[46] Pinedo, M. L., Scheduling: theory, algorithms, and systems, (2008), Springer · Zbl 1155.90008
[47] Pirkwieser, S.; Raidl, G.; Puchinger, J., Combining Lagrangian decomposition with an evolutionary algorithm for the knapsack constrained maximum spanning tree problem, Evolutionary computation in combinatorial optimization, 176-187, (2007), Springer
[48] Puchinger, J.; Raidl, G., Combining metaheuristics and exact algorithms in combinatorial optimization: A survey and classification, Artificial intelligence and knowledge engineering applications: A bioinspired approach, 41-53, (2005), Springer
[49] Smith, W. E., Various optimizers for single-stage production, Naval Research Logistics, 3, 59-66, (1956)
[50] Stalk, G.; Evans, P.; Shulman, L. E., Competing on capabilities: The new rules of corporate strategy, Harvard Business Review, 70, 2, 57-69, (1991)
[51] Stutzle, T., Local search algorithms for combinatorial problems, (1998), Darmstadt University of Technology, Ph.D. thesis
[52] Tsui, L.; Chang, C., A microcomputer based decision support tool for assigning dock doors in freight yards, Computers & Industrial Engineering, 19, 309-312, (1990)
[53] Tsui, L.; Chang, C., An optimal solution to a dock door assignment problem, Computers & Industrial Engineering, 23, 283-286, (1992)
[54] Vahdani, B.; Zandieh, M., Scheduling trucks in cross-docking systems: Robust metaheuristics, Computers & Operations Research, 58, 1, 12-24, (2010)
[55] Witt, C. E., Crossdocking: Concepts demand choice, Material Handling Engineering, 53, 7, 44-49, (1998)
[56] Wolfe, P., A method of conjugate subgradients for minimizing nondifferentiable functions, Nondifferentiable optimization, 145-173, (1975), Springer
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.