An improved approach for quay crane scheduling with non-crossing constraints

Common deficiencies found in previous studies that modelled quay crane scheduling with non-crossing constraints (QCSNC) in port container terminals are identified. Remedies for the problems are proposed to prevent the occurrence of unrealistic optimal solutions for QCSNC. Additionally, two approxima...

Full description

Saved in:
Bibliographic Details
Published in:Engineering optimization 2010-01, Vol.42 (1), p.1-15
Main Authors: Lee, Der-Horng, Chen, Jiang Hang
Format: Article
Language:English
Subjects:
Algorithms
Approximation
approximation algorithms
Back propagation
Cranes
Engineering
Mathematical analysis
Mathematical models
non-crossing constraints
Optimization
Partitions
quay crane scheduling
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Common deficiencies found in previous studies that modelled quay crane scheduling with non-crossing constraints (QCSNC) in port container terminals are identified. Remedies for the problems are proposed to prevent the occurrence of unrealistic optimal solutions for QCSNC. Additionally, two approximation schemes for QCSNC are studied. The first one is called the best partition (BP) method, which can be solved by dynamic programming (DP) with time complexity of (mn 2 ). A more efficient algorithm is designed to improve the original DP by adopting binary search. Next, based on BP and an exact algorithm for QCSNC (with pseudo-polynomial computational time), the second approximation scheme, called the enhanced best partition (EBP) method, is proposed to achieve a better estimation of the optimal makespan for QCSNC. The results of numerical experiments show that EBP is an effective approximation scheme for the problem of QCSNC.
ISSN:0305-215X
1029-0273
DOI:10.1080/03052150902943020