HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Master Theses  >

Please use this identifier to cite or link to this item:
Title: An efficient local search algorithm for crane scheduling problem
Authors: Ngan, Sai-fong
Issue Date: 1997
Abstract: 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.
Description: Thesis (M.Phil.)--Hong Kong University of Science and Technology, 1997
xi, 81 leaves : ill. ; 30 cm
HKUST Call Number: Thesis COMP 1997 Ngan
Appears in Collections:CSE Master Theses

Files in This Item:

File Description SizeFormat

All items in this Repository are protected by copyright, with all rights reserved.