Comparison of yard crane scheduling algorithms

• Main Author: Low, Yihang.
• Other Authors: Huang Shell Ying
• Format: Final Year Project
• Language: English
• Published: 2012
• Subjects: DRNTU::Engineering::Computer science and engineering::Theory of computation::Analysis of algorithms and problem complexity
• Online Access: http://hdl.handle.net/10356/48639
• Institution: Nanyang Technological University

Yard cranes (YCs) are integral parts of a container terminal system. It is desirable to find algorithms which can produce an optimal sequence for a set of jobs to be served by yard crane. This problem of yard crane scheduling has been widely studied and various algorithms have been developed. This project aimed to study six of these algorithms to compare the quality of solutions produced and the time taken for the algorithms to be executed. The algorithms were implemented in C#. Various measurement metrics, most importantly waiting time of the jobs and execution time of the algorithms, were collected. The results were processed in R and an analysis was made in order to quantify the quality differences and execution time differences of the algorithms. It was discovered that the heuristic algorithms (Nearest Neighbour, Shortest Completion-time Job First and Partial Sequence Search) produced solutions of only slightly worse quality than the optimal one found by A*, but at a far small execution time cost.