An exact approach to the generalized serial-lock scheduling problem from a flexible job-shop scheduling perspective.

*(English)*Zbl 07350549Summary: In this paper, the general serial-lock scheduling problem (SLSP) is studied from a new methodological angle, aiming at optimizing the process of ships passing a series of consecutive locks. For the first time in this research topic, we propose a widely applicable model for the SLSP from a flexible job-shop scheduling (FJS) perspective, integrated with a two-dimensional bin-packing problem. The FJS-based perspective allows the formulation of a mixed integer linear programming model, which is capable of solving the SLSP to optimality. Wide-ranging instances with various lock configurations and traffic scenarios are performed to test the applicability and efficiency of the proposed FJS model, which demonstrates that the FJS can optimally solve most of the instances with up to four multi-chamber locks and 20 ships. The results obtained respectively with and without the first-come-first-served restriction show that imposing this restriction can accelerate the solution process for most instances. Meanwhile, experimental results also confirm the advantage of the FJS for solving single-lock scheduling problems, compared with other existing methods. Additionally, although the experiments on the simplified SLSP without multi-type chambers nor two-dimensional ship placement demonstrate a comparable performance between the FJS-based approach and other exact methods, the majority of experimental results infer that the FJS is a more suitable candidate model for dealing with the scenarios with high-density water traffic.

##### MSC:

90Bxx | Operations research and management science |

PDF
BibTeX
XML
Cite

\textit{B. Ji} et al., Comput. Oper. Res. 127, Article ID 105164, 17 p. (2021; Zbl 07350549)

Full Text:
DOI

##### References:

[1] | Bugarski, V.; BačKalić, T.; Kuzmanov, U., Fuzzy decision support system for ship lock control, Expert Systems with Applications, 40, 3953-3960 (2013) |

[2] | Dai, M. D.; Schonfeld, P., Metamodels for estimating waterway delays through series of queues, Transportation Research Part B: Methodological, 32, 1-19 (1998) |

[3] | Ji, B.; Yuan, X.; Yuan, Y., Orthogonal design-based NSGA-III for the optimal lockage co-problem, IEEE Transactions on Intelligent Transportation Systems, 18, 2085-2095 (2016) |

[4] | Ji, B.; Yuan, X.; Yuan, Y., A hybrid intelligent approach for co-scheduling of cascaded locks with multiple chambers, IEEE Transactions on Cybernetics, 49, 1236-1248 (2018) |

[5] | Ji, B.; Yuan, X.; Yuan, Y.; Lei, X.; Fernando, T.; Iu, H. H., Exact and heuristic methods for optimizing lock-quay system in inland waterway, European Journal of Operational Research, 277, 740-755 (2019) · Zbl 1430.90269 |

[6] | Ji, B.; Yuan, X.; Yuan, Y.; Lei, X.; Iu, H. H., An adaptive large neighborhood search for solving generalized lock scheduling problem: Comparative study with exact methods, IEEE Transactions on Intelligent Transportation Systems (2019) |

[7] | Verstichel, J., Berghe, G.V., 2016. Simulation and optimization for ship lock scheduling: a case study. In: 2016 7th International Conference on Information, Intelligence, Systems & Applications (IISA), IEEE, 2016, pp. 1-6. |

[8] | Lübbecke, E.; Lübbecke, M. E.; Möhring, R. H., Ship traffic optimization for the kiel canal, Operations Research, 67, 791-812 (2019) · Zbl 1444.90029 |

[9] | Martinelli, D.; Schonfeld, P., Approximating delays at interdependent locks, Journal of Waterway, Port, Coastal, and Ocean Engineering, 121, 300-307 (1995) |

[10] | Nauss, R. M., Optimal sequencing in the presence of setup times for tow/barge traffic through a river lock, European Journal of Operational Research, 187, 1268-1281 (2008) · Zbl 1137.90427 |

[11] | Passchyn, W.; Coene, S.; Briskorn, D.; Hurink, J. L.; Spieksma, F. C.; Berghe, G. V., The lockmaster’s problem, European Journal of Operational Research, 251, 432-441 (2016) · Zbl 1346.90597 |

[12] | Passchyn, W.; Briskorn, D.; Spieksma, F. C., Mathematical programming models for lock scheduling with an emission objective, European Journal of Operational Research, 248, 802-814 (2016) · Zbl 1346.90380 |

[13] | Petersen, E. R.; Taylor, A. J., An optimal scheduling system for the welland canal, Transportation Science, 22, 173-185 (1988) · Zbl 0645.90040 |

[14] | Prandtstetter, M.; Ritzinger, U.; Schmidt, P.; Ruthmair, M., A variable neighborhood search approach for the interdependent lock scheduling problem, (European Conference on Evolutionary Computation in Combinatorial Optimization (2015), Springer), 36-47 |

[15] | Smith, L. D.; Nauss, R. M., Investigating strategic alternatives for improving service in an inland waterway transportation system, International Journal of Strategic Decision Sciences, 1, 62-81 (2010) |

[16] | Smith, L. D.; Sweeney, D.; Campbell, J. F., Simulation of alternative approaches to relieving congestion at locks in a river transportion system, Journal of the Operational Research Society, 60, 519-533 (2009) · Zbl 1163.90411 |

[17] | Tan, Z.; Wang, Y.; Meng, Q.; Liu, Z., Joint ship schedule design and sailing speed optimization for a single inland shipping service with uncertain dam transit time, Transportation Science, 52, 1570-1588 (2018) |

[18] | Verstichel, J.; Berghe, G. V., A late acceptance algorithm for the lock scheduling problem, (Logistik Management (2009), Springer), 457-478 |

[19] | Verstichel, J.; Berghe, G. V., Scheduling serial locks: A green wave for waterbound logistics, (Sustainable Logistics and Supply Chains (2016), Springer), 91-109 |

[20] | Verstichel, J.; De Causmaecker, P.; Berghe, G. V., Scheduling algorithms for the lock scheduling problem, Procedia-Social and Behavioral Sciences, 20, 806-815 (2011) |

[21] | Verstichel, J.; De Causmaecker, P.; Spieksma, F. C.; Berghe, G. V., Exact and heuristic methods for placing ships in locks, European Journal of Operational Research, 235, 387-398 (2014) · Zbl 1305.90262 |

[22] | Verstichel, J.; De Causmaecker, P.; Spieksma, F.; Berghe, G. V., The generalized lock scheduling problem: An exact approach, Transportation Research Part E: Logistics and Transportation Review, 65, 16-34 (2014) |

[23] | Verstichel, J.; Kinable, J.; De Causmaecker, P.; Berghe, G. V., A combinatorial Benders’ decomposition for the lock scheduling problem, Computers & Operations Research, 54, 117-128 (2015) · Zbl 1348.90318 |

[24] | Wilson, H. G., On the applicability of queueing theory to lock capacity analysis, Transportation Research, 12, 175-180 (1978) |

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.