Discrete time model and algorithms for container yard crane scheduling.

*(English)*Zbl 1163.90496Summary: Container terminal (CT) operations are often bottlenecked by slow YC (yard crane) movements. PM (prime mover) queues in front of the YCs are common. Hence, efficient YC scheduling to reduce the PM waiting time is critical in increasing a CT’s throughput. We develop an efficient model for YC scheduling by taking into account realistic operational constraints such as inter-crane interference, fixed YC separation distances and simultaneous container storage/retrievals. Among them, only inter-crane interference has ever been considered in the literature. The model requires far fewer integer variables than the literature by using bi-index decision variables. We show how the model can be solved quickly using heuristics and rolling-horizon algorithm, yielding close to optimal solutions in seconds. The solution quality and solution time are both better than the literature even with additional constraints considered. The proposed formulations and algorithms can be extended to other problems with time windows and space constraints.

##### MSC:

90B35 | Deterministic scheduling theory in operations research |

90B36 | Stochastic scheduling theory in operations research |

PDF
BibTeX
XML
Cite

\textit{W. Li} et al., Eur. J. Oper. Res. 198, No. 1, 165--172 (2009; Zbl 1163.90496)

Full Text:
DOI

##### References:

[1] | Bish, E.K., A multiple-crane-constrained scheduling problem in a container terminal, European journal of operational research, 144, 83-107, (2003) · Zbl 1037.90023 |

[2] | Chen, L.; Bostel, N.; Dejax, P.; Cai, J.; Xi, L., A tabu search algorithm for the integrated scheduling problem of container handling systems in a maritime terminal, European journal of operational research, 181, 40-58, (2007) · Zbl 1121.90054 |

[3] | Cheung, R.K.; Li, C.; Lin, W., Interblock crane deployment in container terminals, Transportation science, 36, 79-93, (2002) · Zbl 1065.90514 |

[4] | Froyland, G.; Koch, T.; Megow, N.; Duane, E.; Wren, H., Optimizing the landside operation of a container terminal, OR spectrum, 30, 53-75, (2008) · Zbl 1133.90308 |

[5] | Henwood R., 2006. The practitioner’s definitive guide: Seafreight forwarding, SNP Reference. |

[6] | Hopp, W.J.; Spearman, M.L., Factory physics: foundations of manufacturing management, (2000), Irwin/McGraw-Hill |

[7] | Kim, K.H.; Kim, K.Y., An optimal routing algorithm for a transfer crane in port container terminals, Transportation science, 33, 17-33, (1999) · Zbl 1002.90508 |

[8] | Kim, K.Y.; Kim, K.H., Heuristic algorithms for routing yard-side equipment for minimizing loading times in container terminals, Naval research logistics, 50, 498-514, (2003) · Zbl 1043.90045 |

[9] | Kim, K.H.; Park, Y., A crane scheduling method for port container terminals, European journal of operational research, 156, 752-768, (2004) · Zbl 1062.90027 |

[10] | Li, J.; Leung, S.; Wu, Y.; Liu, K., Allocation of empty containers between multi-ports, European journal of operational research, 182, 400-412, (2007) · Zbl 1128.90004 |

[11] | Lim, A.; Rodrigues, B.; Xu, Z., A m-parallel crane scheduling problem with a non-crossing constraint, Naval research logistics, 54, 115-127, (2007) · Zbl 1126.90025 |

[12] | Narasimhan, A.; Palekar, U.S., Analysis and algorithms for the transtainer routing problem in container port operations, Transportation science, 36, 63-78, (2002) · Zbl 1065.90511 |

[13] | Ng, W.C., Crane scheduling in container yards with inter-crane interference, European journal of operational research, 164, 64-78, (2005) · Zbl 1132.90331 |

[14] | Ng, W.C.; Mak, K.L., Yard crane scheduling in port container terminals, Applied mathematical modelling, 29, 263-275, (2005) · Zbl 1077.90029 |

[15] | Ng, W.C., Tsang, W.S., 2005. Scheduling yard crane in a port container terminal using genetic algorithm. In: The First International Conference on Transportation Logistics (T-Log 2005) 27-29 July, Singapore. |

[16] | Stahlbock, R.; Voß, S., Operations research at container terminals: A literature update, OR spectrum, 30, 1-52, (2008) · Zbl 1133.90313 |

[17] | Steenken, D.; Voß, S.; Stahlbock, R., Container terminal operation and operations research – a classification and literature review, OR spectrum, 26, 3-49, (2004) · Zbl 1160.90322 |

[18] | Vis, I.F.A.; Koster, R.D., Transshipment of containers at a container terminal: an overview, European journal of operational research, 147, 1-16, (2003) · Zbl 1011.90005 |

[19] | Wang, F.; Lim, A., A stochastic beam search for the berth allocation problem, Decision support systems, 42, 2186-2196, (2007) |

[20] | Zhang, C.; Wan, Y.; Liu, J.; Linn, R.J., Dynamic crane deployment in container storage yards, Transportation research B, 36, 537-555, (2002) |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.