IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v258y2017i3p820-828.html
   My bibliography  Save this article

Approximate the scheduling of quay cranes with non-crossing constraints

Author

Listed:
  • Zhang, An
  • Zhang, Wenshuai
  • Chen, Yong
  • Chen, Guangting
  • Chen, Xufeng

Abstract

In port container terminals, the scheduling of quay cranes (QCs) for a container vessel is one of the most critical operations. This paper investigates the problem of scheduling quay cranes with non-crossing constraints, wherein QCs cannot cross over each other because they are on the same track. The objective is to minimise the makespan of a container vessel, which is the latest completion time among all handling tasks of the vessel. Compared with several 2-approximation algorithms in the literature, this paper presents an approximation algorithm with a worst case ratio 2−2m+1<2 for any m QCs. This ratio is demonstrated to be the best possible among all partition-based algorithms in the literature. Besides, we study the scheduling of two quay cranes with different processing speeds. For an arbitrary speed ratio s ≥ 1, an approximation algorithm with worst case ratio (1+s)21+s+s2 is provided.

Suggested Citation

  • Zhang, An & Zhang, Wenshuai & Chen, Yong & Chen, Guangting & Chen, Xufeng, 2017. "Approximate the scheduling of quay cranes with non-crossing constraints," European Journal of Operational Research, Elsevier, vol. 258(3), pages 820-828.
    • Handle: RePEc:eee:ejores:v:258:y:2017:i:3:p:820-828
    DOI: 10.1016/j.ejor.2016.10.021
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221716308542
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2016.10.021?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Anne V. Goodchild & Carlos F. Daganzo, 2006. "Double-Cycling Strategies for Container Ships and Their Effect on Ship Loading and Unloading Operations," Transportation Science, INFORMS, vol. 40(4), pages 473-483, November.
    2. Bierwirth, Christian & Meisel, Frank, 2015. "A follow-up survey of berth allocation and quay crane scheduling problems in container terminals," European Journal of Operational Research, Elsevier, vol. 244(3), pages 675-689.
    3. Ng, W. C., 2005. "Crane scheduling in container yards with inter-crane interference," European Journal of Operational Research, Elsevier, vol. 164(1), pages 64-78, July.
    4. Lehnfeld, Jana & Knust, Sigrid, 2014. "Loading, unloading and premarshalling of stacks in storage areas: Survey and classification," European Journal of Operational Research, Elsevier, vol. 239(2), pages 297-312.
    5. Bierwirth, Christian & Meisel, Frank, 2010. "A survey of berth allocation and quay crane scheduling problems in container terminals," European Journal of Operational Research, Elsevier, vol. 202(3), pages 615-627, May.
    6. Shang, Xiao Ting & Cao, Jin Xin & Ren, Jie, 2016. "A robust optimization approach to the integrated berth allocation and quay crane assignment problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 94(C), pages 44-65.
    7. Kim, Kap Hwan & Park, Young-Man, 2004. "A crane scheduling method for port container terminals," European Journal of Operational Research, Elsevier, vol. 156(3), pages 752-768, August.
    8. Türkoğulları, Yavuz B. & Taşkın, Z. Caner & Aras, Necati & Altınel, İ. Kuban, 2016. "Optimal berth allocation, time-variant quay crane assignment and scheduling with crane setups in container terminals," European Journal of Operational Research, Elsevier, vol. 254(3), pages 985-1001.
    9. Goodchild, A.V. & Daganzo, C.F., 2007. "Crane double cycling in container ports: Planning methods and evaluation," Transportation Research Part B: Methodological, Elsevier, vol. 41(8), pages 875-891, October.
    10. Chung-Yee Lee & Ming Liu & Chengbin Chu, 2015. "Optimal Algorithm for the General Quay Crane Double-Cycling Problem," Transportation Science, INFORMS, vol. 49(4), pages 957-967, November.
    11. Vis, Iris F. A. & de Koster, Rene, 2003. "Transshipment of containers at a container terminal: An overview," European Journal of Operational Research, Elsevier, vol. 147(1), pages 1-16, May.
    12. Y Zhu & A Lim, 2006. "Crane scheduling with non-crossing constraint," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(12), pages 1464-1471, December.
    13. Lee, Der-Horng & Wang, Hui Qiu & Miao, Lixin, 2008. "Quay crane scheduling with non-interference constraints in port container terminals," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 44(1), pages 124-135, January.
    14. Meersmans, P.J.M. & Dekker, R., 2001. "Operations research supports container handling," Econometric Institute Research Papers EI 2001-22, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Shoufeng Ma & Hongming Li & Ning Zhu & Chenyi Fu, 2021. "Stochastic programming approach for unidirectional quay crane scheduling problem with uncertainty," Journal of Scheduling, Springer, vol. 24(2), pages 137-174, April.
    2. Damla Kizilay & Deniz Türsel Eliiyi, 2021. "A comprehensive review of quay crane scheduling, yard operations and integrations thereof in container terminals," Flexible Services and Manufacturing Journal, Springer, vol. 33(1), pages 1-42, March.
    3. Gharehgozli, Amir & Zaerpour, Nima, 2018. "Stacking outbound barge containers in an automated deep-sea terminal," European Journal of Operational Research, Elsevier, vol. 267(3), pages 977-995.
    4. Kong, Lingrui & Ji, Mingjun & Gao, Zhendi, 2022. "An exact algorithm for scheduling tandem quay crane operations in container terminals," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 168(C).
    5. Abou Kasm, Omar & Diabat, Ali & Chow, Joseph Y.J., 2023. "Simultaneous operation of next-generation and traditional quay cranes at container terminals," European Journal of Operational Research, Elsevier, vol. 308(3), pages 1110-1125.
    6. Raeesi, Ramin & Sahebjamnia, Navid & Mansouri, S. Afshin, 2023. "The synergistic effect of operational research and big data analytics in greening container terminal operations: A review and future directions," European Journal of Operational Research, Elsevier, vol. 310(3), pages 943-973.
    7. Feifeng Zheng & Yaxin Pang & Ming Liu & Yinfeng Xu, 2020. "Dynamic programming algorithms for the general quay crane double-cycling problem with internal-reshuffles," Journal of Combinatorial Optimization, Springer, vol. 39(3), pages 708-724, April.
    8. Fan Bu & Heather Nachtmann, 2023. "Literature review and comparative analysis of inland waterways transport: “Container on Barge”," Maritime Economics & Logistics, Palgrave Macmillan;International Association of Maritime Economists (IAME), vol. 25(1), pages 140-173, March.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Gharehgozli, Amir & Zaerpour, Nima, 2018. "Stacking outbound barge containers in an automated deep-sea terminal," European Journal of Operational Research, Elsevier, vol. 267(3), pages 977-995.
    2. Bierwirth, Christian & Meisel, Frank, 2010. "A survey of berth allocation and quay crane scheduling problems in container terminals," European Journal of Operational Research, Elsevier, vol. 202(3), pages 615-627, May.
    3. Damla Kizilay & Deniz Türsel Eliiyi, 2021. "A comprehensive review of quay crane scheduling, yard operations and integrations thereof in container terminals," Flexible Services and Manufacturing Journal, Springer, vol. 33(1), pages 1-42, March.
    4. Boysen, Nils & Briskorn, Dirk & Meisel, Frank, 2017. "A generalized classification scheme for crane scheduling with interference," European Journal of Operational Research, Elsevier, vol. 258(1), pages 343-357.
    5. Shoufeng Ma & Hongming Li & Ning Zhu & Chenyi Fu, 2021. "Stochastic programming approach for unidirectional quay crane scheduling problem with uncertainty," Journal of Scheduling, Springer, vol. 24(2), pages 137-174, April.
    6. Bierwirth, Christian & Meisel, Frank, 2015. "A follow-up survey of berth allocation and quay crane scheduling problems in container terminals," European Journal of Operational Research, Elsevier, vol. 244(3), pages 675-689.
    7. Evrim Ursavas, 2017. "Crane allocation with stability considerations," Maritime Economics & Logistics, Palgrave Macmillan;International Association of Maritime Economists (IAME), vol. 19(2), pages 379-401, June.
    8. Nils Boysen & Malte Fliedner & Florian Jaehn & Erwin Pesch, 2013. "A Survey on Container Processing in Railway Yards," Transportation Science, INFORMS, vol. 47(3), pages 312-329, August.
    9. Chen, Lu & Langevin, André & Lu, Zhiqiang, 2013. "Integrated scheduling of crane handling and truck transportation in a maritime container terminal," European Journal of Operational Research, Elsevier, vol. 225(1), pages 142-152.
    10. Gharehgozli, Amir & Yu, Yugang & de Koster, René & Du, Shaofu, 2019. "Sequencing storage and retrieval requests in a container block with multiple open locations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 125(C), pages 261-284.
    11. Gharehgozli, Amir Hossein & Vernooij, Floris Gerardus & Zaerpour, Nima, 2017. "A simulation study of the performance of twin automated stacking cranes at a seaport container terminal," European Journal of Operational Research, Elsevier, vol. 261(1), pages 108-128.
    12. Feifeng Zheng & Yaxin Pang & Ming Liu & Yinfeng Xu, 2020. "Dynamic programming algorithms for the general quay crane double-cycling problem with internal-reshuffles," Journal of Combinatorial Optimization, Springer, vol. 39(3), pages 708-724, April.
    13. Türkoğulları, Yavuz B. & Taşkın, Z. Caner & Aras, Necati & Altınel, İ. Kuban, 2016. "Optimal berth allocation, time-variant quay crane assignment and scheduling with crane setups in container terminals," European Journal of Operational Research, Elsevier, vol. 254(3), pages 985-1001.
    14. Chung-Yee Lee & Ming Liu & Chengbin Chu, 2015. "Optimal Algorithm for the General Quay Crane Double-Cycling Problem," Transportation Science, INFORMS, vol. 49(4), pages 957-967, November.
    15. Gabriela N. Maschietto & Yassine Ouazene & Martín G. Ravetti & Maurício C. de Souza & Farouk Yalaoui, 2017. "Crane scheduling problem with non-interference constraints in a steel coil distribution centre," International Journal of Production Research, Taylor & Francis Journals, vol. 55(6), pages 1607-1622, March.
    16. Zhen, Lu & Zhuge, Dan & Wang, Shuaian & Wang, Kai, 2022. "Integrated berth and yard space allocation under uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 162(C), pages 1-27.
    17. Wu, Lingxiao & Ma, Weimin, 2017. "Quay crane scheduling with draft and trim constraints," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 97(C), pages 38-68.
    18. Liu, Ming & Chu, Feng & Zhang, Zizhen & Chu, Chengbin, 2015. "A polynomial-time heuristic for the quay crane double-cycling problem with internal-reshuffling operations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 81(C), pages 52-74.
    19. Sun, Defeng & Tang, Lixin & Baldacci, Roberto & Lim, Andrew, 2021. "An exact algorithm for the unidirectional quay crane scheduling problem with vessel stability," European Journal of Operational Research, Elsevier, vol. 291(1), pages 271-283.
    20. Zhang, Xiaoju & Zeng, Qingcheng & Yang, Zhongzhen, 2016. "Modeling the mixed storage strategy for quay crane double cycling in container terminals," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 94(C), pages 171-187.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:258:y:2017:i:3:p:820-828. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.