IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v54y2007i2p115-127.html
   My bibliography  Save this article

A m‐parallel crane scheduling problem with a non‐crossing constraint

Author

Listed:
  • Andrew Lim
  • Brian Rodrigues
  • Zhou Xu

Abstract

In this paper, we study a m‐parallel machine scheduling problem with a non‐crossing constraint motivated by crane scheduling in ports. We decompose the problem to allow time allocations to be determined once crane assignments are known and construct a backtracking search scheme that manipulates domain reduction and pruning strategies. Simple approximation heuristics are developed, one of which guarantees solutions to be at most two times the optimum. For large‐scale problems, a simulated annealing heuristic that uses random neighborhood generation is provided. Computational experiments are conducted to test the algorithms. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007.

Suggested Citation

  • Andrew Lim & Brian Rodrigues & Zhou Xu, 2007. "A m‐parallel crane scheduling problem with a non‐crossing constraint," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(2), pages 115-127, March.
    • Handle: RePEc:wly:navres:v:54:y:2007:i:2:p:115-127
    DOI: 10.1002/nav.20189
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/nav.20189
    Download Restriction: no
    File URL: https://libkey.io/10.1002/nav.20189?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
    ---><---

    References listed on IDEAS

    as
    1. T. C. Hu, 1961. "Parallel Sequencing and Assembly Line Problems," Operations Research, INFORMS, vol. 9(6), pages 841-848, December.
    2. Lee, Young Hoon & Pinedo, Michael, 1997. "Scheduling jobs on parallel machines with sequence-dependent setup times," European Journal of Operational Research, Elsevier, vol. 100(3), pages 464-474, August.
    3. Zhang, Chuqian & Wan, Yat-wah & Liu, Jiyin & Linn, Richard J., 2002. "Dynamic crane deployment in container storage yards," Transportation Research Part B: Methodological, Elsevier, vol. 36(6), pages 537-555, July.
    4. Peterkofsky, Roy I. & Daganzo, Carlos F., 1990. "A branch and bound solution method for the crane scheduling problem," Transportation Research Part B: Methodological, Elsevier, vol. 24(3), pages 159-172, June.
    5. Ebru K. Bish & Thin‐Yin Leong & Chung‐Lun Li & Jonathan W. C. Ng & David Simchi‐Levi, 2001. "Analysis of a new vehicle scheduling and location problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 48(5), pages 363-385, August.
    6. Daganzo, Carlos F., 1989. "The crane scheduling problem," Transportation Research Part B: Methodological, Elsevier, vol. 23(3), pages 159-175, June.
    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. Cheng, T. C. E. & Sin, C. C. S., 1990. "A state-of-the-art review of parallel-machine scheduling research," European Journal of Operational Research, Elsevier, vol. 47(3), pages 271-292, August.
    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. Schulz, Arne & Fliedner, Malte & Fiedrich, Benedikt & Pfeiffer, Christian, 2021. "Levelling crane workload in multi-yard rail-road container terminals," European Journal of Operational Research, Elsevier, vol. 293(3), pages 941-954.
    2. Yongpei Guan & Kang-Hung Yang & Zhili Zhou, 2013. "The crane scheduling problem: models and solution approaches," Annals of Operations Research, Springer, vol. 203(1), pages 119-139, March.
    3. Qin, Tianbao & Du, Yuquan & Chen, Jiang Hang & Sha, Mei, 2020. "Combining mixed integer programming and constraint programming to solve the integrated scheduling problem of container handling operations of a single vessel," European Journal of Operational Research, Elsevier, vol. 285(3), pages 884-901.
    4. 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.
    5. Sun, Defeng & Tang, Lixin & Baldacci, Roberto, 2019. "A Benders decomposition-based framework for solving quay crane scheduling problems," European Journal of Operational Research, Elsevier, vol. 273(2), pages 504-515.
    6. Dirk Briskorn & Florian Jaehn & Andreas Wiehl, 2019. "A generator for test instances of scheduling problems concerning cranes in transshipment terminals," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 41(1), pages 45-69, March.
    7. J Blazewicz & T C E Cheng & M Machowiak & C Oguz, 2011. "Berth and quay crane allocation: a moldable task scheduling model," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(7), pages 1189-1197, July.
    8. Shucheng Yu & Shuaian Wang & Lu Zhen, 2017. "Quay crane scheduling problem with considering tidal impact and fuel consumption," Flexible Services and Manufacturing Journal, Springer, vol. 29(3), pages 345-368, December.
    9. Guvenc Dik & Erhan Kozan, 2017. "A flexible crane scheduling methodology for container terminals," Flexible Services and Manufacturing Journal, Springer, vol. 29(1), pages 64-96, March.
    10. 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.

    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. Shawn Choo & Diego Klabjan & David Simchi-Levi, 2010. "Multiship Crane Sequencing with Yard Congestion Constraints," Transportation Science, INFORMS, vol. 44(1), pages 98-115, February.
    2. 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.
    3. Zeng, Qingcheng & Yang, Zhongzhen & Lai, Luyuan, 2009. "Models and algorithms for multi-crane oriented scheduling method in container terminals," Transport Policy, Elsevier, vol. 16(5), pages 271-278, September.
    4. Nabil Nehme & Bacel Maddah & Isam A. Kaysi, 2021. "An integrated multi-ship crane allocation in Beirut Port container terminal," Operational Research, Springer, vol. 21(3), pages 1743-1761, September.
    5. Andrew Lim & Brian Rodrigues & Fei Xiao & Yi Zhu, 2004. "Crane scheduling with spatial constraints," Naval Research Logistics (NRL), John Wiley & Sons, vol. 51(3), pages 386-406, April.
    6. 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.
    7. 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.
    8. 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.
    9. Branislav Dragović & Nam Kyu Park & Zoran Radmilović, 2006. "Ship-berth link performance evaluation: simulation and analytical approaches," Maritime Policy & Management, Taylor & Francis Journals, vol. 33(3), pages 281-299, July.
    10. Dirk Briskorn & Florian Jaehn & Andreas Wiehl, 2019. "A generator for test instances of scheduling problems concerning cranes in transshipment terminals," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 41(1), pages 45-69, March.
    11. Henry Lau & Ying Zhao, 2008. "Integrated scheduling of handling equipment at automated container terminals," Annals of Operations Research, Springer, vol. 159(1), pages 373-394, March.
    12. 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.
    13. Frank Meisel & Christian Bierwirth, 2013. "A Framework for Integrated Berth Allocation and Crane Operations Planning in Seaport Container Terminals," Transportation Science, INFORMS, vol. 47(2), pages 131-147, May.
    14. Tang, Lixin & Zhao, Jiao & Liu, Jiyin, 2014. "Modeling and solution of the joint quay crane and truck scheduling problem," European Journal of Operational Research, Elsevier, vol. 236(3), pages 978-990.
    15. Yongpei Guan & Kang-Hung Yang & Zhili Zhou, 2013. "The crane scheduling problem: models and solution approaches," Annals of Operations Research, Springer, vol. 203(1), pages 119-139, March.
    16. Shucheng Yu & Shuaian Wang & Lu Zhen, 2017. "Quay crane scheduling problem with considering tidal impact and fuel consumption," Flexible Services and Manufacturing Journal, Springer, vol. 29(3), pages 345-368, December.
    17. Vibhuti Dhingra & Debjit Roy & René B. M. Koster, 2017. "A cooperative quay crane-based stochastic model to estimate vessel handling time," Flexible Services and Manufacturing Journal, Springer, vol. 29(1), pages 97-124, March.
    18. Abdellah Salhi & Ghazwan Alsoufi & Xinan Yang, 2019. "An evolutionary approach to a combined mixed integer programming model of seaside operations as arise in container ports," Annals of Operations Research, Springer, vol. 272(1), pages 69-98, January.
    19. 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.
    20. 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.

    More about this item

    Statistics

    Access and download statistics

    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:wly:navres:v:54:y:2007:i:2:p:115-127. 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: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    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.