Computer Science

Computer Science ›› 2021, Vol. 48 ›› Issue (11A): 22-29.doi: 10.11896/jsjkx.201200167

• Intelligent Computing • Previous Articles     Next Articles

Theoretical Research and Efficient Algorithm of Container Terminal Quay Crane Optimal Scheduling

GAO Xi, SUN Wei-wei   

  1. School of Computer Science,Fudan University,Shanghai 201203,China
    Shanghai Key Laboratory of Data Science,Fudan University,Shanghai 201203,China
    Shanghai Institute of Intelligent Electronics and Systems,Shanghai 200433,China
  • Online:2021-11-10 Published:2021-11-12
  • About author:GAO Xi,born in 1996,postgraduate.His main research interests include intelligent transport and so on.
    SUN Wei-wei,born in 1973,Ph.D,professor,is senior member of China Computer Federation.His main research interests include intelligent transport and big spatial-temporal data.
  • Supported by:
    National Natural Science Foundation of China(61772138).

PDF (PC)

1040

Abstract: Quay crane scheduling problem is one of the most important scheduling problems in container terminals.The existing research results can not calculate the optimal scheduling of large-scale business in the feasible time,so the existing quay crane scheduling algorithms generally adopt heuristic strategies to ensure that scheduling can be calculated in the feasible time.In this paper,firstly,the correctness of the lower bound of completion time is proved theoretically,an optimal scheduling construction method is designed and the theoretical system of quay crane scheduling problem is completed.Secondly,based on the theoretical work,an algorithm of linear time complexity is designed to find the optimal scheduling.Finally,experiments show that the proposed method is significantly better than the existing methods in terms of solution quality and efficiency.

Key words: Linear algorithm, Lower bound of completion time, Optimal solution, Quay crane scheduling

CLC Number: 

  • TP399
[1]ZHANG S,LV M Q,DAI J H,et al.Research on Quay Crane Scheduling Optimization Based on the Uncertainty of Operation Time[J].Industrial Engineering and Management,2020,25(5):54-62.
[2]Statistics of Container Terminal Throughput for Main Ports in China (Jul.,2020)[J].Containerization,2020,31(8):34-35.
[3]ZHAO C.The Way to Improve the Port[J].Industry City,2020(10):54-55.
[4]LU S X,LV C H,QING T.An Algorithm Based on Make Span Lower Bound for Quay Crane Schedule Problem in Container Terminals[J].Operations Research Transactions,2020,24(3):67-76.
[5]LIU J,WAN Y W,WANG L.Quay crane Scheduling at Container Terminals to Minimize the Maximum Relative Tardiness of Vessel Departures[J].Naval Research Logs,2006,53(1):60-74.
[6]MIAO W L.Quay Crane Scheduling with Non-Interference Constraints in Port Container Terminals[J]. Transportation Research Part E Logistics & Transportation Review,2008,44(1):124-135.
[7]KAVESHGAR N,NUYNH N,RAHIMIAN S K.An Efficient Genetic Algorithm for Solving the Quay Crane Scheduling Problem[J].Expert Systems With Applications,2012,39(18):13108-13117.
[8]CHUNG S H,FELIX T,CHAN S.A Workload Balancing Genetic Algorithm for the Quay Crane Scheduling Problem[J].International Journal of Production Research,2013,51(16):4820-4834.
[9] SU N Y,ZHANG M J,JOHNSTON M,et al.Hybrid Evolutionary Computation Methods for Quay Crane Scheduling Problems[J].Computers and Operations Research,2013,40(8):2083-2093.
[10]LEE D H,WANG H Q,MIAO L X.Quay Crane Schedulingwith Handling Priority in Port Container Terminals.Engineering Optimization,2008,40(2):179-189.
[11]KIM K H,PARK Y M.A Crane Scheduling Method for Port Container Terminals [J].European Journal of Operational Research,2004,156(3):752-768.
[12]ZHU Y,LIM A.Crane Scheduling with Non-Crossing Con-straint.Journal of the Operational Research Society,2006,57(12):1464-1471.
[13]PETERKOFSKY R I,DAGANZO C F.A Branch and Bound Solution Method for the Crane Scheduling Problem[J]. Transportation Research Part B Methodological,1990,24(3):159-172.
[14]MOCCIA L,CORDEAU J F,GAUDIOSO M,et al.A Branch-and-Cut Algorithm for the Quay Crane Scheduling Problem in a Container Terminal[J].Naval Research Logistics,2006,53(1):45-59.
[15]BIERWIRTH C,MEISEL F.A Fast Heuristic for Quay Crane Scheduling with Interference Constraints[J].Journal of Scheduling,2009,12(4):345-360.
[16]SONG Y T,WANG N,WU N.Optimization of Berth and Quay Crane Collaborative Scheduling Considering Both the Cost and Time Guarantee Rate[J].Operations Research and Management Science,2020,29(4):130-137.
[17]LE M L,ZHAO Y Y,LIU X L.Shore-Mounted Gantry Crane Scheduling for Single Vessel Under Time Window-Using Mathematical Programming and Rule Heuristic Algorithm[J].Computer Engineering and Applications,2014,50(9):242-248.
[1] YU Xin, LIN Zhi-liang. Novel Neural Network for Dealing with a Kind of Non-smooth Pseudoconvex Optimization Problems [J]. Computer Science, 2022, 49(5): 227-234.
[2] HUANG Guang-qiu, LU Qiu-qin. Vertical Structure Community System Optimization Algorithm [J]. Computer Science, 2020, 47(4): 194-203.
[3] YANG Ting, LUO Fei, DING Wei-chao, LU Hai-feng. Bin Packing Algorithm Based on Adaptive Optimization of Slack [J]. Computer Science, 2020, 47(4): 211-216.
[4] CAO Fang and ZHU Yong-kang. 3D Reconstruction Based on SFS Method and Accuracy Analysis [J]. Computer Science, 2017, 44(Z6): 244-247.
[5] MEI Hai-tao, HUA Ji-xue and WANG Yi. Improved Intuitionistic Fuzzy Genetic Algorithm for Nonlinear Programming Problems [J]. Computer Science, 2016, 43(9): 250-254.
[6] MAO Li, ZHOU Chang-xi and WU Bin. Artificial Bee Colony Algorithm Based on Strategy of Segmental-search with Current Optimal Solution [J]. Computer Science, 2015, 42(12): 263-267.
[7] CAO Jian-wei,CHEN Qing-kui and ZHUANG Song-lin. UPSO (Uniform Particle Swarm Optimization):An Algorithm of Dynamic Overlay Optimization for WSN [J]. Computer Science, 2014, 41(Z6): 255-257.
[8] WEN Chuan-jun,WANG Qing-miao and ZHAN Yong-zhao. Equalization Fuzzy C-means Clustering Algorithm [J]. Computer Science, 2014, 41(8): 250-253.
[9] HAN Li-xia. Novel Genetic Algorithm for Multi-objective Optimization Problem [J]. Computer Science, 2013, 40(Z6): 64-66.
[10] . [J]. Computer Science, 2009, 36(4): 235-238.
[11] ZHENG Jin-hua, LUO Biao, LI Jing ,WEN Shi-hua ,LI Wang-yi （Institute of Information Engineering,Xiangtan University, Xiangtan 411105, China）. [J]. Computer Science, 2009, 36(2): 30-34.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.