A crane scheduling method for port container terminals. (English) Zbl 1062.90027

Kim, Kap Hwan; Park, Young-Man

Eur. J. Oper. Res. 156, No. 3, 752-768 (2004).

Summary: This paper discusses the problem of scheduling Quay Cranes (QCs), the most important equipment in port terminals. A mixed-integer programming model, which considers various constraints related to the operation of QCs, was formulated. This study proposes a branch and bound (B \(\and\) B) method to obtain the optimal solution of the QC scheduling problem and a heuristic search algorithm, called greedy randomized adaptive search procedure (GRASP), to overcome the computational difficulty of the B \(\and\) B method. The performance of GRASP is compared with that of the B \(\and\) B method.

MSC:

90B35	Deterministic scheduling theory in operations research
90C57	Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C27	Combinatorial optimization

Keywords:

Scheduling; Branch and bound; Transportation; Container; terminal; Combinatorial optimization

References:

[1]	Brown, G. G.; Lawphongpanich, S.; Thurman, K. P., Optimizing ship berthing, Naval Research Logistics, 41, 1-15 (1995) · Zbl 0800.90579
[2]	Cheung, R. K.; Li, C.-L.; Lin, W., Interblock crane deployment in container terminals, Transportation Science, 36, 1, 79-93 (2002) · Zbl 1065.90514
[4]	Cojeen, H. P.; Dyke, P. V., The automatic planning and sequencing of containers for containership loading and unloading, (Pitkin; Roche; Williams, Ship Operation Automation (1976), North-Holland Publishing Co)
[5]	Daganzo, C. F., The crane scheduling problem, Transportation Research Part B, 23B, 3, 159-175 (1989)
[6]	Feo, T. A.; Resende, M. G.C., Greedy randomized adaptive search procedures, Journal of Global Optimization, 6, 109-133 (1995) · Zbl 0822.90110
[8]	Guinet, A., Scheduling sequence-dependent jobs on identical parallel machines to minimize completion time criteria, International Journal of Production Research, 31, 7, 1579-1594 (1993)
[9]	Kim, K. H.; Kim, K. Y., An optimal routing algorithm for a transfer crane in port container terminals, Transportation Science, 33, 1, 17-33 (1999) · Zbl 1002.90508
[10]	Lee, Y. H.; Pinedo, M., Scheduling jobs on parallel machines with sequence-dependent setup times, European Journal of Operational Research, 100, 3, 464-474 (1997) · Zbl 0917.90193
[11]	Lim, A., The berth planning problem, Operations Research Letters, 22, 105-110 (1998) · Zbl 0911.90283
[12]	Narasimhan, A.; Palekar, U. S., Analysis and algorithms for the transtainer routing problem in container port operations, Transportation Science, 36, 1, 63-78 (2002) · Zbl 1065.90511
[13]	Peterkofsky, R. I.; Daganzo, C. F., A branch and bound solution method for the crane scheduling problem, Transportation Research Part B, 24, 3, 159-172 (1990)
[14]	Zhang, C.; Wan, Y.-W.; Liu, J.; Linn, R. J., Dynamic crane deployment in container storage yards, Transportation Research Part B, 36, 537-555 (2002)