约束规划求解集装箱装卸系统集成调度问题  

Constraint programming for the integrated scheduling problem of container handling systems in container terminals

作　　者：秦天保[1] 葛浩[1] 沙梅[1] 

机构地区：[1]上海海事大学交通运输学院,上海201306

出　　处：《系统工程理论与实践》2015年第8期2127-2136,共10页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(71172076);交通部应用基础研究项目(2011-329-810-450);上海市科委地方院校专项(11510501800);上海市重点学科建设项目(S30601)

摘　　要：集装箱码头装卸系统中的岸桥、集卡和场桥的集成调度问题本质上是有阻塞、准备时间可分离并且依赖操作顺序的三阶段混合流水车间调度问题,现有文献多采用启发式算法求解该问题.本文先建立了一个紧凑的混合整数规划模型,然后从约束规划的角度建模求解该问题,提出了一个约束规划模型,以区间变量作为决策变量,并采用"扩展操作任务"的概念来定义区间决策变量以提升求解效率.为了展示约束规划的建模灵活性,还扩展了模型以考虑机器效率不同的因素.数值实验显示约束规划模型能够在很短的时间内对大规模算例求出高质量的解.Integrated scheduling of quay cranes, yard trucks and yard cranes in container terminals boils down to a 3-stage hybrid flowshop scheduling problem with blocking and separable, sequence-dependent setup times. Various heuristic algorithms were developed to tackle the problem in most literature. First, a concise mixed integer linear programming （MILP） model for the integrated scheduling problem is formu- lated. Then a novel constraint programming （CP） model is put forward to improve the solving efficiency, which employs so-called interval variables as decision variables and adopts the concept of ＂extended oper- ation task＂ to define the interval decision variables. To demonstrate the modeling flexibility of CP, the CP model is further extended to accommodate different efficiency of machines. Numerical experiments show that the CP model can be solved efficiently to obtain near-optimum solutions for large-scale problems.

关 键 词：集装箱码头 混合流水车间 约束规划 混合整数线性规划 启发式算法 

分 类 号：TP29[自动化与计算机技术—检测技术与自动化装置] U691[自动化与计算机技术—控制科学与工程]