A bounded two-level dynamic programming algorithm for quay crane scheduling in container terminals
One of the optimization problems in terminal operations is the quay crane scheduling problem. The quay crane scheduling algorithm plays a critical role because it directly affects the length of the vessel loading and unloading process, which means vessel turnaround time. We propose a bounded two-lev...
| Główni autorzy: | , |
|---|---|
| Kolejni autorzy: | |
| Format: | Journal Article |
| Język: | English |
| Wydane: |
2018
|
| Hasła przedmiotowe: | |
| Dostęp online: | https://hdl.handle.net/10356/89771 http://hdl.handle.net/10220/46732 |
| _version_ | 1826112308704706560 |
|---|---|
| author | Huang, Shell Ying Li, Ya |
| author2 | School of Computer Science and Engineering |
| author_facet | School of Computer Science and Engineering Huang, Shell Ying Li, Ya |
| author_sort | Huang, Shell Ying |
| collection | NTU |
| description | One of the optimization problems in terminal operations is the quay crane scheduling problem. The quay crane scheduling algorithm plays a critical role because it directly affects the length of the vessel loading and unloading process, which means vessel turnaround time. We propose a bounded two-level dynamic programming (DP) algorithm which keeps the simplicity of the bay-based approach but overcomes its shortcomings. We also propose a method to estimate the lower bound to quay crane scheduling given the lists of unloading and loading containers and the number of quay cranes assigned to the vessel. This lower bound is used both to reduce computational time of the 2-level DP algorithm and to evaluate our crane scheduling method. Our experiments with real vessel unloading and loading lists for 80 vessels show that the vessel makespan is close to the lower
bound. The computational times for the 80 vessels with up to 6600 container moves by cranes in loading and unloading a vessel are all under two minutes. |
| first_indexed | 2024-10-01T03:04:53Z |
| format | Journal Article |
| id | ntu-10356/89771 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T03:04:53Z |
| publishDate | 2018 |
| record_format | dspace |
| spelling | ntu-10356/897712020-03-07T11:48:57Z A bounded two-level dynamic programming algorithm for quay crane scheduling in container terminals Huang, Shell Ying Li, Ya School of Computer Science and Engineering Quay Crane Scheduling Container Terminals DRNTU::Engineering::Computer science and engineering One of the optimization problems in terminal operations is the quay crane scheduling problem. The quay crane scheduling algorithm plays a critical role because it directly affects the length of the vessel loading and unloading process, which means vessel turnaround time. We propose a bounded two-level dynamic programming (DP) algorithm which keeps the simplicity of the bay-based approach but overcomes its shortcomings. We also propose a method to estimate the lower bound to quay crane scheduling given the lists of unloading and loading containers and the number of quay cranes assigned to the vessel. This lower bound is used both to reduce computational time of the 2-level DP algorithm and to evaluate our crane scheduling method. Our experiments with real vessel unloading and loading lists for 80 vessels show that the vessel makespan is close to the lower bound. The computational times for the 80 vessels with up to 6600 container moves by cranes in loading and unloading a vessel are all under two minutes. MOE (Min. of Education, S’pore) Accepted version 2018-11-29T03:15:04Z 2019-12-06T17:33:06Z 2018-11-29T03:15:04Z 2019-12-06T17:33:06Z 2018 2018 Journal Article Huang, S. Y., & Li, Y. (2018). A bounded two-level dynamic programming algorithm for quay crane scheduling in container terminals. Computers & Industrial Engineering, 123303-313. doi:10.1016/j.cie.2018.06.010 0360-8352 https://hdl.handle.net/10356/89771 http://hdl.handle.net/10220/46732 10.1016/j.cie.2018.06.010 rims:208363 208363 en Computers and Industrial Engineering © 2018 Elsevier. This is the author created version of a work that has been peer reviewed and accepted for publication by Computers & Industrial Engineering,, Elsevier. It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document. The published version is available at: [http://doi.org/10.1016/j.cie.2018.06.010] 18 p. application/pdf |
| spellingShingle | Quay Crane Scheduling Container Terminals DRNTU::Engineering::Computer science and engineering Huang, Shell Ying Li, Ya A bounded two-level dynamic programming algorithm for quay crane scheduling in container terminals |
| title | A bounded two-level dynamic programming algorithm for quay crane scheduling in container terminals |
| title_full | A bounded two-level dynamic programming algorithm for quay crane scheduling in container terminals |
| title_fullStr | A bounded two-level dynamic programming algorithm for quay crane scheduling in container terminals |
| title_full_unstemmed | A bounded two-level dynamic programming algorithm for quay crane scheduling in container terminals |
| title_short | A bounded two-level dynamic programming algorithm for quay crane scheduling in container terminals |
| title_sort | bounded two level dynamic programming algorithm for quay crane scheduling in container terminals |
| topic | Quay Crane Scheduling Container Terminals DRNTU::Engineering::Computer science and engineering |
| url | https://hdl.handle.net/10356/89771 http://hdl.handle.net/10220/46732 |
| work_keys_str_mv | AT huangshellying aboundedtwoleveldynamicprogrammingalgorithmforquaycraneschedulingincontainerterminals AT liya aboundedtwoleveldynamicprogrammingalgorithmforquaycraneschedulingincontainerterminals AT huangshellying boundedtwoleveldynamicprogrammingalgorithmforquaycraneschedulingincontainerterminals AT liya boundedtwoleveldynamicprogrammingalgorithmforquaycraneschedulingincontainerterminals |