Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/5640

An efficient local search algorithm for crane scheduling problem

Authors Ngan, Sai-fong
Issue Date 1997
Summary Hong Kong has the world's busiest container port. Everyday thousands of con-tainers need to be removed from container ships onto container yards and from the yards onto container trunks. In this thesis, a Crane Scheduling Problem is defined to model operations in the container yards. We have developed a scheduling algorithm for Crane Scheduling Problem. Our algorithm solves the problem by minimizing the time needed to remove containers from the yard, shortening the waiting time in queues for container trucks, and thus reducing traffic congestion on the port docks and around the port area. In the scheduling algorithm, an efficient local search technique is designed to sequence the delivery requests to be removed out of the yard by crane. Such a scheduling problem is NP-hard and the search space grows exponentially as the number of requests increases. The proposed algorithm makes use of problem specific knowledge in order to reduce the search space as well as the cost of partial schedule calculation. Under different experiments, the algorithm has shown promising results and is able to produce near-optimal results in a reasonable time.
Note Thesis (M.Phil.)--Hong Kong University of Science and Technology, 1997
Subjects
Language English
Format Thesis
Access
Files in this item:
File Description Size Format
th_redirect.html 341 B HTML