Paper Info
Title
A complete and an incomplete algorithm for automated guided vehicle scheduling in container terminals
Abstract
In this paper, a scheduling problem for automated guided vehicles in container terminals is defined and formulated as a Minimum Cost Flow model. This problem is then solved by a novel algorithm, NSA+, which extended the standard Network Simplex Algorithm (NSA). Like NSA, NSA+ is a complete algorithm, which means that it guarantees optimality of the solution if it finds one within the time available. To complement NSA+, an incomplete algorithm Greedy Vehicle Search (GVS) is designed and implemented. The NSA+ and GVS are compared and contrasted to evaluate their relative strength and weakness. With polynomial time complexity, NSA+ can be used to solve very large problems, as verified in our experiments. Should the problem be too large for NSA+, or the time available for computation is too short (as it would be in dynamic scheduling), GVS complements NSA+.
Year
DOI
Venue
2011
10.1016/j.camwa.2010.12.009
Computers & Mathematics with Applications
Keywords
Field
DocType
dynamic scheduling,minimum cost,flow model,network simplex algorithm,container terminals,container terminal,scheduling problem,polynomial time complexity,vehicle scheduling,search methods,scheduling problems,complete algorithm,novel algorithm,large problem,greedy vehicle search,optimization,incomplete algorithm,simplex algorithm,polynomial time
Network simplex algorithm,Mathematical optimization,Automated guided vehicle,Job shop scheduling,Scheduling (computing),Computer science,Algorithm,Dynamic priority scheduling,Relative strength,Minimum-cost flow problem,Computation
Journal
Volume
Issue
ISSN
61
3
Computers and Mathematics with Applications
Citations 
PageRank 
References 
10
0.57
9
Authors
2
Name
Order
Citations
PageRank
Hassan Rashidi1526.10
Edward P. K. Tsang289987.77