Stochastic programming approach for unidirectional quay crane scheduling problem with uncertainty

作     者：Ma, Shoufeng Li, Hongming Zhu, Ning Fu, Chenyi 

作者机构：Tianjin Univ Inst Syst Engn Coll Management & Econ Tianjin 300072 Peoples R China 

出 版 物：《JOURNAL OF SCHEDULING》 (调度杂志)

年 卷 期：2021年第24卷第2期

页      面：137-174页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0802[工学-机械工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Natural Science Foundation of China [71971154, 71671123, 71771167] MOE (Ministry of Education in China) Project of Humanities and Social Sciences [17YJC630239] 

主　　题：Unidirectional quay crane scheduling Uncertainty Two-stage stochastic programming Integer L-shaped method Simulated annealing algorithm 

摘      要：Quay crane scheduling is a key aspect of container terminal operation, which can be regarded as a decision-making process with uncertainty. Each task involves stochastic loading and unloading operation times owing to the existence of uncertainty. In this study, we investigate the unidirectional quay crane scheduling problem for a stochastic processing time, which requires that all the quay cranes move in the same direction either from bow to stern, or vice versa, throughout the planning horizon. The problem is formulated as a two-stage stochastic mixed-integer programming model, where the binary first-stage decision variables correspond to the assignment of tasks to quay cranes, and the mixed-integer second-stage decision variables are related to the generation of detailed schedules. To make the model solvable, we develop an alternative equivalent reformulation with a special structure that involves binary variables in the first stage and continuous variables in the second stage. To solve this reformulated model, an integer L-shaped method is presented for small-size instances, and a simulated annealing algorithm is presented for large-size instances to obtain near-optimal solutions. Numerical experiments show that the integer L-shaped method and simulated annealing algorithm could efficiently solve the unidirectional quay crane scheduling problem with uncertainty. The results also indicate that the stochastic model has distinct advantages in terms of shortening the completion time of vessels and improving the service level of container terminals compared with the expected value problem solutions.