research-article

Cooperative twin-crane scheduling

Authors:

Nils BoysenAuthors Info & Claims

Discrete Applied Mathematics, Volume 211, Issue C

Pages 40 - 57

https://doi.org/10.1016/j.dam.2016.04.006

Published: 01 October 2016 Publication History

Abstract

This paper treats the crane scheduling in a container port where two cooperative gantry cranes (denoted as twin cranes) jointly store import containers arriving from the seaside in a storage yard. We aim to minimize the makespan while non-crossing constraints among cranes need to be considered and preemptive container moves are allowed, i.e.,źthe seaside crane sets down a container in some intermediate position where the landside crane takes over and delivers the container to its final storage position in the yard. Elementary complexity proofs are provided and efficient heuristic solution procedures are introduced and tested.

References

[1]

A.J. Baird, Optimising the container transhipment hub location in northern Europe, J. Transp. Geogr., 14 (2006) 195-214.

[2]

J.J. Bartholdi, D.D. Eisenstein, A production line that balances itself, Oper. Res., 44 (1996) 21-34.

Digital Library

[3]

J.J. Bartholdi, D.D. Eisenstein, R.D. Foley, Performance of bucket brigades when work is stochastic, Oper. Res., 49 (2001) 710-719.

Digital Library

[4]

N. Boysen, S. Bock, Scheduling just-in-time part supply for mixed-model assembly lines, European J. Oper. Res., 211 (2011) 15-25.

[5]

N. Boysen, D. Briskorn, S. Emde, A decomposition heuristic for the twin robots scheduling problem, Nav. Res. Logist., 62 (2014) 16-22.

[6]

N. Boysen, D. Briskorn, F. Meisel, 2014. A Generalized Classification Scheme for Crane Scheduling with Interference, Working Paper Friedrich-Schiller University Jena.

[7]

N. Boysen, M. Fliedner, F. Jaehn, E. Pesch, A survey on container processing in railway yards, Transp. Sci., 47 (2013) 312-329.

Digital Library

[8]

D. Briskorn, P. Angeloudis, Scheduling co-operating stacking cranes with predetermined container sequences, Discrete Appl. Math., 201 (2016) 70-85.

Digital Library

[9]

R. Choe, T.S. Kim, T. Kim, K.R. Ryu, Crane scheduling for opportunistic remarshaling of containers in an automated stacking yard, Flexible Serv. Manuf. J., 27 (2013) 331-349.

[10]

R. Dekker, P. Voogd, E. van Asperen, Advanced methods for container stacking, OR Spectrum, 28 (2006) 563-586.

[11]

R. Edmonson, Calling a new tune, J. Commer., 8 (2007) 12-15.

[12]

G. Erdogan, M. Battarra, G. Laporte, Scheduling twin robots on a line, Nav. Res. Logist., 61 (2014) 119-130.

[13]

M.R. Garey, D.S. Johnson, Computers and intractability: A guide to the theory of NP-completeness, Freeman, New York, 1979.

Digital Library

[14]

A.H. Gharehgozli, G. Laporte, Y. Yu, R. de Koster, Scheduling twin yard cranes in a container block, Transp. Sci., 49 (2015) 686-705.

Digital Library

[15]

D.E. Goldberg, Genetic Algorithms in Search, Optimization & Machine Learning, Addison-Wesley Publishing Company Inc., Reading, MA, 1989.

Digital Library

[16]

D.E. Goldberg, K. Deb, A Comparison of Selection Schemes used in Genetic Algorithms, in: Foundations of Genetic Algorithms, 1991, pp. 69-93.

[17]

S. Hartmann, Generating scenarios for simulation and optimization of container terminal logistics, OR Spectrum, 26 (2004) 171-192.

[18]

J.H. Holland, Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence, University of Michigan Press, Ann Arbor, MI, 1975.

Digital Library

[19]

N. Kemme, RMG Crane Scheduling and Stacking, in: Handbook of Terminal Planning, Springer, New York, 2011, pp. 271-301.

[20]

N. Kemme, Effects of storage block layout and automated yard crane systems on the performance of seaport container terminals, OR spectrum, 34 (2012) 563-591.

Digital Library

[21]

S. Kirkpatrick, C.D. Gelatt, M.P. Vecchi, Optimization by simulated annealing, Science, 220 (1983) 671-680.

[22]

R. Namboothiri, A.L. Erera, Planning local container drayage operations given a port access appointment system, Transp. Res. E: Logist.Transp. Rev., 44 (2008) 185-202.

[23]

T. Park, R. Choe, S.M. Ok, K.R. Ryu, Real-time scheduling for twin RMGs in an automated container yard, OR Spectrum, 32 (2010) 593-615.

[24]

B. Peterson, I. Harjunkoski, S. Hoda, J.N. Hooker, Scheduling multiple factory cranes on a common track, Comput. Oper. Res., 48 (2014) 102-112.

[25]

C.R. Reeves, Genetic algorithms for the operations researcher, INFORMS J. Comput., 9 (1997) 231-250.

Digital Library

[26]

Y.A. Saanen, M.V. Valkengoed, 2005. Comparison of three automated stacking alternatives by means of simulation. In: Proceedings of the 37th Winter Simulation Conference, 1567-1576.

Digital Library

[27]

R. Stahlbock, S. Voß, Operations research at container terminals: a literature update, OR Spectrum, 30 (2008) 1-52.

[28]

D. Steenken, S. Voß, R. Stahlbock, Container terminal operation and operations research-a classification and literature review, OR Spectrum, 26 (2004) 3-49.

[29]

P.J. Van Laarhoven, E.H. Aarts, J.K. Lenstra, Job shop scheduling by simulated annealing, Oper. Res., 40 (1992) 113-125.

Digital Library

[30]

I.F. Vis, A comparative analysis of storage and retrieval equipment at a container terminal, Int. J. Prod. Econ., 103 (2006) 680-693.

[31]

Y. Wu, W. Li, M.E.H. Petering, M. Goh, R. de Souza, Scheduling multiple yard cranes with crane interference and safety distance requirement, Transp. Sci., 49 (2015) 990-1005.

Digital Library

[32]

W. Zhou, X. Wu, An efficient optimal solution of a two-crane scheduling problem, Asia-Pac. J. Oper. Res., 26 (2009) 31-58.

Cited By

Zhou PZhang QTang G(2023)A Double-Agent Neighbor-State Q-learning Algorithm for Dynamic Scheduling Twin-ASCs in ACTsProceedings of the 2023 15th International Conference on Computer Modeling and Simulation10.1145/3608251.3608274(1-7)Online publication date: 16-Jun-2023
https://dl.acm.org/doi/10.1145/3608251.3608274
Oladugba AGheith MEltawil A(2023)A new solution approach for the twin yard crane scheduling problem in automated container terminalsAdvanced Engineering Informatics10.1016/j.aei.2023.10201557:COnline publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1016/j.aei.2023.102015
Zey LBriskorn DBoysen N(2022)Twin-crane scheduling during seaside workload peaks with a dedicated handshake areaJournal of Scheduling10.1007/s10951-021-00710-w25:1(3-34)Online publication date: 1-Feb-2022
https://dl.acm.org/doi/10.1007/s10951-021-00710-w
Show More Cited By

Cooperative twin-crane scheduling
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
    2. Online algorithms
      1. Online learning algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

Twin-crane scheduling during seaside workload peaks with a dedicated handshake area
Abstract
To enable the efficient division of labor in container yards, many large ports apply twin cranes, two identical automated stacking cranes each dedicated to one of the transfer zones on the seaside and landside. The use of a handshake area, a bay ...
Scheduling Multiple Yard Cranes with Crane Interference and Safety Distance Requirement

Container terminals require robust scheduling algorithms for yard cranes to optimally determine the sequence of storage and retrieval operations in yard blocks for higher container terminal performance. This paper investigates the multiple yard crane ...
Solving the single crane scheduling problem at rail transshipment yards
Abstract
We consider single-crane scheduling at rail transshipment yards, in which gantry cranes move containers between trains, trucks and a storage area. The single-crane scheduling problem arises at single-crane transshipment terminals and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Discrete Applied Mathematics

Discrete Applied Mathematics Volume 211, Issue C

October 2016

223 pages

ISSN:0166-218X

Issue’s Table of Contents

Copyright © Elsevier B.V.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 October 2016

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhou PZhang QTang G(2023)A Double-Agent Neighbor-State Q-learning Algorithm for Dynamic Scheduling Twin-ASCs in ACTsProceedings of the 2023 15th International Conference on Computer Modeling and Simulation10.1145/3608251.3608274(1-7)Online publication date: 16-Jun-2023
https://dl.acm.org/doi/10.1145/3608251.3608274
Oladugba AGheith MEltawil A(2023)A new solution approach for the twin yard crane scheduling problem in automated container terminalsAdvanced Engineering Informatics10.1016/j.aei.2023.10201557:COnline publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1016/j.aei.2023.102015
Zey LBriskorn DBoysen N(2022)Twin-crane scheduling during seaside workload peaks with a dedicated handshake areaJournal of Scheduling10.1007/s10951-021-00710-w25:1(3-34)Online publication date: 1-Feb-2022
https://dl.acm.org/doi/10.1007/s10951-021-00710-w
Briskorn D(2021)Routing two stacking cranes with predetermined container sequencesJournal of Scheduling10.1007/s10951-021-00689-424:4(367-380)Online publication date: 1-Aug-2021
https://dl.acm.org/doi/10.1007/s10951-021-00689-4
Eilken A(2019)A decomposition-based approach to the scheduling of identical automated yard cranes at container terminals Journal of Scheduling10.1007/s10951-019-00611-z22:5(517-541)Online publication date: 1-Oct-2019
https://dl.acm.org/doi/10.1007/s10951-019-00611-z
Briskorn DJaehn FWiehl A(2019)A generator for test instances of scheduling problems concerning cranes in transshipment terminalsOR Spectrum10.1007/s00291-018-0529-z41:1(45-69)Online publication date: 1-Mar-2019
https://dl.acm.org/doi/10.1007/s00291-018-0529-z

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents