×

A multiple-crane-constrained scheduling problem in a container terminal. (English) Zbl 1037.90023

Summary: We consider a container terminal loading and unloading containers to and from a set of ships, and storing the containers in the terminal yard. Each ship is served by multiple quay cranes, which load and unload containers to and from ships. Containers are moved between the ships and the yard using a fleet of vehicles, each with unit capacity. The problem is (i) to determine a storage location for each unloaded container, (ii) to dispatch vehicles to containers, and (iii) to schedule the loading and unloading operations on the cranes, so as to minimize the maximum time it takes to serve a given set of ships. This problem is NP-hard, and therefore we develop a heuristic algorithm based on formulating the problem as a transshipment problem. The effectiveness of the heuristic is analyzed from both worst-case and computational points of view.

MSC:

90B35 Deterministic scheduling theory in operations research
90B06 Transportation, logistics and supply chain management
90C59 Approximation methods and heuristics in mathematical programming
90C90 Applications of mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bilge, U.; Ulusoy, G., A time window approach to simultaneous scheduling of machines and material handling system in an FMS, Operations Research, 43, 6, 1058-1070 (1995) · Zbl 0852.90083
[2] E.K. Bish, Theoretical analysis and practical algorithms for problems in a mega container terminal, Ph.D. Dissertation, Northwestern University, Evanston, IL, 1999; E.K. Bish, Theoretical analysis and practical algorithms for problems in a mega container terminal, Ph.D. Dissertation, Northwestern University, Evanston, IL, 1999
[3] Bish, E. K.; Leong, T.; Li, C.; Ng, J. W.C.; Simchi-Levi, D., Analysis of a new vehicle scheduling and location problem, Naval Research Logistics, 48, 5, 363-385 (2001) · Zbl 1005.90032
[4] Bramel, J.; Simchi-Levi, D., The Logic of Logistics: Theory, Algorithms, and Applications for Logistics Management (1997), Springer: Springer New York · Zbl 0931.90002
[5] Y. Chen, T. Leong, J.W.C. Ng, E.K. Bish, B.L. Nelson, D. Simchi-Levi, Dispatching vehicles in a mega container terminal, Working Paper, Northwestern University, Evanston, IL, 1998; Y. Chen, T. Leong, J.W.C. Ng, E.K. Bish, B.L. Nelson, D. Simchi-Levi, Dispatching vehicles in a mega container terminal, Working Paper, Northwestern University, Evanston, IL, 1998 · Zbl 1091.90008
[6] Co, C. G.; Tanchoco, J. M.A., A review of research on AGVS vehicle management, Engineering Costs and Production Economics, 21, 35-42 (1991)
[7] Cordeau, J.; Toth, P.; Vigo, D., A survey of optimization models for train routing and scheduling, Transportation Science, 32, 4, 380-404 (1998) · Zbl 0987.90507
[8] Daganzo, C. F., The crane scheduling problem, Transportation Research B, 23, 159-175 (1989)
[9] Daganzo, C. F., Crane productivity and ship delay in ports, Transportation Research Record, 1251, 1-9 (1990)
[10] S.M. Easa, Analysis of traffic operations in harbor terminals, Ph.D. Dissertation, University of California at Berkeley, CA, 1981; S.M. Easa, Analysis of traffic operations in harbor terminals, Ph.D. Dissertation, University of California at Berkeley, CA, 1981
[11] Edmond, E., Operation capacity of container berths for scheduled service by queuing theory, Dock and Harbor Authority, 56, 230-234 (1975)
[12] Hall, N. G.; Potts, C. N.; Sriskandarajah, C., Parallel machine scheduling with a common server, Discrete Applied Mathematics, 102, 223-243 (2000) · Zbl 0972.90031
[13] Hammesfahr, R. D.J.; Clayton, E. R., A computer simulation to assist intermodal terminal managers in operations analysis, Transportation Journal, 22, 55-68 (1983)
[14] M.K. Kiesling, M. Walton, Loading/unloading operations and vehicle queuing processes at container ports, Working Paper, Texas A&M University, 1995; M.K. Kiesling, M. Walton, Loading/unloading operations and vehicle queuing processes at container ports, Working Paper, Texas A&M University, 1995
[15] King, R. E.; Wilson, C. M., A review of AGV system design and scheduling, Production Planning and Control, 2, 44-51 (1991)
[16] Law, A. M.; Kelton, W. D., Simulation Modeling and Analysis (1991), McGraw-Hill: McGraw-Hill New York
[17] McKinsey and Company, Inc., Containerization: The key to low transport. A Report by McKinsey and Company, Inc. for the British Transport Docks Board, 1967; McKinsey and Company, Inc., Containerization: The key to low transport. A Report by McKinsey and Company, Inc. for the British Transport Docks Board, 1967
[18] Mettam, J. D., Forecasting delays to ships in port, Dock and Harbor Authority, 47, 380-382 (1967)
[19] Peterkofsky, R. I.; Daganzo, C. F., A branch and bound solution method for the crane scheduling problem, Transportation Research B, 24, 159-172 (1990)
[20] Stecke, K. E.; Aronson, J. E., Review of operator/machine interference models, International Journal of Production Research, 23, 129-151 (1985)
[21] I.F.A. Vis, R. Koster, K.J. Roodbergen, Determination of the number of AGVs in a semi-automated container terminal, Working Paper, Erasmus University, 1999; I.F.A. Vis, R. Koster, K.J. Roodbergen, Determination of the number of AGVs in a semi-automated container terminal, Working Paper, Erasmus University, 1999 · Zbl 1131.90313
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.