×

A tabu search algorithm for the integrated scheduling problem of container handling systems in a maritime terminal. (English) Zbl 1121.90054

Summary: The scheduling problem in a container terminal is characterized by the coordination of different types of equipment. In this paper, we present an integrated model to schedule the equipment. The objective is to minimize the makespan, or the time it takes to serve a given set of ships. The problem is formulated as a hybrid flow shop scheduling problem with precedence and Blocking constraints (HFSS-B). A tabu search algorithm is proposed to solve this problem. Certain mechanisms are developed and introduced into the algorithm to assure its quality and efficiency. The performance of the tabu search algorithm is analyzed from the computational point of view.

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming

Software:

VRP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ben-Daya, M.; Al-Fawzan, M., A tabu search approach for the flow shop scheduling problem, European Journal of Operational Research, 109, 88-95 (1998) · Zbl 0949.90037
[2] 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
[3] Bose, J., Reiners, T., Steenken, D., 2000. Vehicle dispatching at seaport container terminal using evolutionary algorithm. In: Proceedings of the 33rd Hawaii International Conference on System Science.; Bose, J., Reiners, T., Steenken, D., 2000. Vehicle dispatching at seaport container terminal using evolutionary algorithm. In: Proceedings of the 33rd Hawaii International Conference on System Science.
[4] Carlier, J.; Rebaï, I., Two branch and bound algorithms for the permutation flow shop scheduling problem, European Journal of Operational Research, 90, 238-251 (1996) · Zbl 0913.90162
[5] Daganzo, C. F., Crane productivity and ship delay in ports, Transportation Research Record, 1251, 1-9 (1989)
[6] Dell’Amico, M.; Trubian, M., Applying tabu search to the job-shop scheduling problem, Annals of Operations Research, 41, 231-252 (1993) · Zbl 0771.90056
[7] Elmaghraby, S. E.; Kamoub, R. E., Production control in hybrid flowshops: An example from textile manufacturing, (Artiba, A.; Elmaghraby, S. E., The Planning and Scheduling of Production Systems (1997), Chapman & Hall: Chapman & Hall UK), (Chapter 6)
[8] Glover, F., Tabu search, part I, ORSA Journal of Computing, 1, 190-206 (1989) · Zbl 0753.90054
[9] Glover, F., Tabu search, part II, ORSA Journal of Computing, 2, 4-32 (1990) · Zbl 0771.90084
[10] Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics, 5, 287-326 (1979) · Zbl 0411.90044
[11] James, A.P., Howard, J.M., Basilotto, J.P., et al., 1997. Megaports and load centers of the future with the port of Houston as the baseline port. Research Report, Texas A&M University.; James, A.P., Howard, J.M., Basilotto, J.P., et al., 1997. Megaports and load centers of the future with the port of Houston as the baseline port. Research Report, Texas A&M University.
[12] Kim, K. H.; Kim, K. Y., Routing straddle carriers for the loading operation of containers using a beam search algorithm, Computer & Industrial Engineering, 36, 109-136 (1999)
[13] Kim, K. H.; Kim, K. Y., A routing algorithm for a single straddle carrier to load export containers onto a containership, International Journal of Production Economics, 59, 425-433 (1999)
[14] 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
[15] Kim, K. H.; Kim, H. B., The optimal sizing of the storage space and handling facilities for import containers, Transportation Research Part B, 36, 821-835 (2002)
[16] Kim, K. H.; Park, Y., A crane scheduling method for port container terminals, European Journal of Operational Research, 156, 3, 752-768 (2004) · Zbl 1062.90027
[17] Kurz, M. E.; Askin, R. G., Comparing scheduling rules for flexible flow lines, International Journal of Production Economics, 85, 371-388 (2003)
[18] Lee, C.-Y.; Vairaktarakis, G. L., Minimizing makespan in hybrid flowshops, Operations Research Letters, 16, 149-158 (1994) · Zbl 0812.90066
[19] Linn, R.; Zhang, W., Hybrid flow shop scheduling: A survey, Computers & Industrial Engineering, 37, 57-61 (1999)
[20] Low, C., Simulated annealing heuristic for flow shop scheduling problems with unrelated parallel machines, Computers & Operations Research, 32, 8, 2013-2025 (2005) · Zbl 1068.90060
[21] Mati, Y.; Rezg, N.; Xie, X., A taboo search approach for deadlock-free scheduling of automated manufacturing systems, Journal of Intelligent Manufacturing, 12, 535-552 (2001)
[22] Matsuo, H., Suh, F.J., Sullivan, R.S., 1988. A controlled search simulated annealing method for the general jobshop scheduling problem. Working paper 03-44-88, Graduate School of Business, University of Texas, Austin, TX.; Matsuo, H., Suh, F.J., Sullivan, R.S., 1988. A controlled search simulated annealing method for the general jobshop scheduling problem. Working paper 03-44-88, Graduate School of Business, University of Texas, Austin, TX.
[23] Meersmans, P.l.M., 2002. Optimization of container handling systems. Ph.D. thesis, Tinbergen Institute 271, Erasmus University Rotterdam.; Meersmans, P.l.M., 2002. Optimization of container handling systems. Ph.D. thesis, Tinbergen Institute 271, Erasmus University Rotterdam.
[24] Negenman, E. G., Local search algorithms for the multiprocessor flow shop scheduling problem, European Journal of Operational Research, 128, 147-158 (2001) · Zbl 0984.90017
[25] Nowicki, E., The permutation flow shop with buffers: A tabu search approach, European Journal of Operational Research, 116, 205-219 (1999) · Zbl 1009.90039
[26] Nowicki, E.; Smutnicki, C., A fast tabu search algorithm for the permutation flow-shop problem, European Journal of Operational Research, 91, 160-175 (1996) · Zbl 0947.90590
[27] Nowicki, E.; Smutnicki, C., The flow shop with parallel machines: A tabu search approach, European Journal of Operational Research, 106, 226-253 (1998) · Zbl 0991.90059
[28] Pinedo, M., Scheduling Theory, Algorithms, and Systems (2002), Prentice Hall: Prentice Hall New Jersey · Zbl 1145.90394
[29] Riane, F.; Artiba, A.; Elmaghraby, S. E., A hybrid three-stage flowshop problem: Efficient heuristics to minimize makespan, European Journal of Operational Research, 109, 321-329 (1998) · Zbl 0937.90035
[30] Santos, D. L.; Hunsucker, J. L.; Deal, D. E., Global lower bounds for flow shops with multiple processors, European Journal of Operational Research, 80, 112-120 (1995) · Zbl 0927.90052
[31] Taillard, E. D., Parallel taboo search techniques for the job-shop scheduling problem, ORSA Journal on Computing, 6, 2, 108-117 (1994) · Zbl 0807.90066
[32] Van Laarhoven, P. J.M.; Aarts, E. H.L.; Lenstra, J. K., Job shop scheduling by simulated annealing, Operations Research, 40, 1, 113-125 (1992) · Zbl 0751.90039
[33] Vigo, D., Toth, P. 2002. The Vehicle Routing Problem. Philadelphia, USA.; Vigo, D., Toth, P. 2002. The Vehicle Routing Problem. Philadelphia, USA. · Zbl 0979.00026
[34] Vis, I. F.A.; De Koster, R., Transshipment of containers at a container terminal: An overview, European Journal of Operational Research, 147, 1-16 (2003) · Zbl 1011.90005
[35] 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)
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.