Algorithm Design for an Online Berth Allocation Problem
In this paper, we investigate an online berth allocation problem, where vessels arrive one by one and their information is revealed upon arrival. Our objective is to design online algorithms to minimize the maximum load of all berths (makespan). We first demonstrate that the widely used Greedy algor...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2024-09-01
|
| Series: | Journal of Marine Science and Engineering |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2077-1312/12/10/1722 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850205802018635776 |
|---|---|
| author | Cong Chen Fanxin Wang Jiayin Pan Lang Xu Hongming Gao |
| author_facet | Cong Chen Fanxin Wang Jiayin Pan Lang Xu Hongming Gao |
| author_sort | Cong Chen |
| collection | DOAJ |
| description | In this paper, we investigate an online berth allocation problem, where vessels arrive one by one and their information is revealed upon arrival. Our objective is to design online algorithms to minimize the maximum load of all berths (makespan). We first demonstrate that the widely used Greedy algorithm has a very poor theoretical guarantee; specifically, the competitive ratio of the Greedy algorithm for this problem is lower bounded by <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mrow><mrow><mi mathvariant="sans-serif">Ω</mi><mo>(</mo><mi mathvariant="normal">log</mi></mrow><mo></mo><mrow><mi>m</mi></mrow></mrow><mo>/</mo><mrow><mrow><mi mathvariant="normal">log</mi></mrow><mo></mo><mrow><mrow><mrow><mi mathvariant="normal">log</mi></mrow><mo></mo><mrow><mi>m</mi></mrow></mrow></mrow></mrow><mo>)</mo></mrow></semantics></math></inline-formula>, which increases with the number of berths <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>m</mi></mrow></semantics></math></inline-formula>. On account of this, we borrow an idea from algorithms for the online strip packing problem and provide a comprehensive theoretical analysis of the Revised Shelf (RS) algorithm as applied to our berth allocation problem. We prove that the competitive ratio of RS for our problem is 5, improving on the original competitive ratio of 6.66 for the online strip packing problem. Through numerical studies, we examine the RS algorithm and Greedy algorithm in an average case. The numerical simulation of competitive ratios reveals distinct advantages for different algorithms depending on job size. For smaller job sizes, the Greedy algorithm emerges as the most efficient, while for medium-sized jobs, the RS algorithm proves to be the most effective. |
| format | Article |
| id | doaj-art-63c8fe83df7d4b04891058d894ac98c5 |
| institution | OA Journals |
| issn | 2077-1312 |
| language | English |
| publishDate | 2024-09-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Journal of Marine Science and Engineering |
| spelling | doaj-art-63c8fe83df7d4b04891058d894ac98c52025-08-20T02:11:00ZengMDPI AGJournal of Marine Science and Engineering2077-13122024-09-011210172210.3390/jmse12101722Algorithm Design for an Online Berth Allocation ProblemCong Chen0Fanxin Wang1Jiayin Pan2Lang Xu3Hongming Gao4School of Management, Guangzhou University, Guangzhou 510006, ChinaSchool of Management, Guangzhou University, Guangzhou 510006, ChinaSchool of Management, Xi’an Jiaotong University, Xi’an 710049, ChinaCollege of Transport and Communications, Shanghai Maritime University, Shanghai 200135, ChinaSchool of Management, Guangzhou University, Guangzhou 510006, ChinaIn this paper, we investigate an online berth allocation problem, where vessels arrive one by one and their information is revealed upon arrival. Our objective is to design online algorithms to minimize the maximum load of all berths (makespan). We first demonstrate that the widely used Greedy algorithm has a very poor theoretical guarantee; specifically, the competitive ratio of the Greedy algorithm for this problem is lower bounded by <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mrow><mrow><mi mathvariant="sans-serif">Ω</mi><mo>(</mo><mi mathvariant="normal">log</mi></mrow><mo></mo><mrow><mi>m</mi></mrow></mrow><mo>/</mo><mrow><mrow><mi mathvariant="normal">log</mi></mrow><mo></mo><mrow><mrow><mrow><mi mathvariant="normal">log</mi></mrow><mo></mo><mrow><mi>m</mi></mrow></mrow></mrow></mrow><mo>)</mo></mrow></semantics></math></inline-formula>, which increases with the number of berths <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>m</mi></mrow></semantics></math></inline-formula>. On account of this, we borrow an idea from algorithms for the online strip packing problem and provide a comprehensive theoretical analysis of the Revised Shelf (RS) algorithm as applied to our berth allocation problem. We prove that the competitive ratio of RS for our problem is 5, improving on the original competitive ratio of 6.66 for the online strip packing problem. Through numerical studies, we examine the RS algorithm and Greedy algorithm in an average case. The numerical simulation of competitive ratios reveals distinct advantages for different algorithms depending on job size. For smaller job sizes, the Greedy algorithm emerges as the most efficient, while for medium-sized jobs, the RS algorithm proves to be the most effective.https://www.mdpi.com/2077-1312/12/10/1722online algorithmberth allocation problemmultiprocessor task scheduling |
| spellingShingle | Cong Chen Fanxin Wang Jiayin Pan Lang Xu Hongming Gao Algorithm Design for an Online Berth Allocation Problem Journal of Marine Science and Engineering online algorithm berth allocation problem multiprocessor task scheduling |
| title | Algorithm Design for an Online Berth Allocation Problem |
| title_full | Algorithm Design for an Online Berth Allocation Problem |
| title_fullStr | Algorithm Design for an Online Berth Allocation Problem |
| title_full_unstemmed | Algorithm Design for an Online Berth Allocation Problem |
| title_short | Algorithm Design for an Online Berth Allocation Problem |
| title_sort | algorithm design for an online berth allocation problem |
| topic | online algorithm berth allocation problem multiprocessor task scheduling |
| url | https://www.mdpi.com/2077-1312/12/10/1722 |
| work_keys_str_mv | AT congchen algorithmdesignforanonlineberthallocationproblem AT fanxinwang algorithmdesignforanonlineberthallocationproblem AT jiayinpan algorithmdesignforanonlineberthallocationproblem AT langxu algorithmdesignforanonlineberthallocationproblem AT hongminggao algorithmdesignforanonlineberthallocationproblem |