×

One-dimensional vehicle scheduling with a front-end depot and non-crossing constraints. (English) Zbl 1290.90038

Summary: This paper considers the scheduling problem of multiple vehicles executing a given set of jobs in parallel along a shared pathway. The job set consists of storage and retrieval tasks, transporting goods between a front-end depot and given storage locations on the line. Non-crossing constraints need to be applied to the vehicle movements. This problem setting is relevant when a train is loaded with containers by multiple straddle carriers on the landside of a container terminal. Other potential applications exist in multi-shuttle automated storage and retrieval systems and multi-stage production systems where items are transported by parallel hoists. We formalize the problem, analyze its computational complexity, and develop exact and heuristic solution procedures.

MSC:

90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Boysen N, Emde S, Fliedner M (2013) Scheduling train loading with straddle carriers in container yards. J Oper Res Soc (to appear)
[2] Boysen N, Fliedner M, Kellner M (2010) Determining fixed crane areas in rail-rail transshipment yards. Transp Res Part E Logist Transp Rev 46:1005-1016 · doi:10.1016/j.tre.2010.05.004
[3] Gellert TJ, König FG (2011) 1D vehicle scheduling with conflicts. In: Proceedings of the workshop on algorithm engineering and experiments, ALENEX 2011. Society for Industrial and, Applied Mathematics, pp 107-115 · Zbl 1430.90080
[4] Goldberg DE (1989) Genetic algorithms in search, optimization and machine learning. Addison-Wesley Publishing Company Inc, Reading · Zbl 0721.68056
[5] Goldberg DE, Deb K (1991) A comparison of selection schemes used in genetic algorithms. In: Rawlins GJE (ed) Foundations of genetic algorithms, pp 69-93
[6] Heinrichs U, Moll C (1997) On the scheduling of one-dimensional transport systems. Technical Report No. 97-277. Center for Parallel Computing, University of Cologne
[7] Holland JH (1975) Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. University of Michigan Press, Ann Arbor
[8] Hulett H, Will TG, Woeginger GJ (2008) Multigraph realizations of degree sequences: maximization is easy, minimization is hard. Oper Res Lett 36:594-596 · Zbl 1210.90140 · doi:10.1016/j.orl.2008.05.004
[9] Lei L, Wang T-J (1991) The minimum common cycle algorithm for cycle scheduling of two material handling hoists with time window constraints. Manag Sci 37:1629-1639 · Zbl 0741.90036 · doi:10.1287/mnsc.37.12.1629
[10] Leung JMY, Zhang G, Yang X, Mak R, Lam K (2004) Optimal cyclic multi-hoist scheduling: a mixed integer programming approach. Oper Res 52:965-976 · Zbl 1165.90460 · doi:10.1287/opre.1040.0144
[11] Lieberman RW, Turksen IB (1981) Crane scheduling problems. AIIE Trans 13:304-311 · doi:10.1080/05695558108974566
[12] Lieberman RW, Turksen IB (1982) Two-operation crane scheduling problems. AIIE Trans 14:147-155 · doi:10.1080/05695558208975054
[13] Liu J, Zhou Z (1998) A heuristic method for cyclic scheduling of two hoists without overlapping. In: Proceedings of the 3rd annual international conference of industrial engineering theories, applications and practice, Hong Kong, pp 250.1-250.6 · Zbl 1210.90140
[14] Malmborg CJ (2000) Interleaving models for the analysis of twin shuttle automated storage and retrieval systems. Int J Prod Res 38:4599-4610 · Zbl 1045.90504 · doi:10.1080/00207540050205532
[15] Meller RD, Mungwattana A (1997) Multi-shuttle automated storage/retrieval systems. IIE Trans 29: 925-938
[16] Reeves CR (1997) Genetic algorithms for the operations researcher. INFORMS J Comput 9:231-250 · Zbl 0893.90145 · doi:10.1287/ijoc.9.3.231
[17] Roodbergen KJ, Vis IFA (2009) A survey of literature on automated storage and retrieval systems. Eur J Oper Res 194:343-362 · Zbl 1154.90322 · doi:10.1016/j.ejor.2008.01.038
[18] Steenken D, Voß S, Stahlbock R (2004) Container terminal operation and operations research—a classification and literature review. OR Spectr 26:3-49 · Zbl 1160.90322 · doi:10.1007/s00291-003-0157-z
[19] van den Berg JP, Gademann AJRM (1999) Optimal routing in an automated storage/retrieval system with dedicated storage. IIE Trans 31:407-415 · doi:10.1023/A:1007545122755
[20] Zhou ZL, Li L (2003) Single hoist cyclic scheduling with multiple tanks: a material handling solution. Comput Oper Res 30:811-819 · Zbl 1026.90051
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.