A tabu search heuristic for the quay crane scheduling problem
A tabu search heuristic for the quay crane scheduling problem
复制标题
DOI：
10.1007/s10951-007-0029-5
复制
发表时间：
2007-10
影响因子：
2
通讯作者：
Marcello Sammarra;J. Cordeau;G. Laporte;M. F. Monaco
中科院分区：
文献类型：
--
作者：
Marcello Sammarra;J. Cordeau;G. Laporte;M. F. Monaco
本文提出了一种禁忌搜索启发式算法来求解码头起重机调度问题（QCSP），即调度固定数量的码头起重机来装卸集装箱的问题。考虑的最优性准则是最小完工时间。考虑了任务之间的优先性和非优先性约束。前者源于每个起重机必须执行的不同类型的操作;后者是为了避免起重机之间的干扰而需要的。将QCSP问题分解为路由问题和调度问题。路由问题是解决了禁忌搜索启发式，而本地搜索技术是用来生成的调度问题的解决方案。这是通过最小化析取图中的最长路径长度来完成的。我们的算法的有效性进行评估，通过比较它的分支和切割算法和贪婪的随机自适应搜索过程（GRASP）。
This paper proposes a tabu search heuristic for theQuay Crane Scheduling Problem(QCSP), the problem of scheduling a fixed number of quay cranes in order to load and unload containers into and from a ship. The optimality criterion considered is the minimum completion time. Precedence and non-simultaneity constraints between tasks are taken into account. The former originate from the different kind of operations that each crane has to perform; the latter are needed in order to avoid interferences between the cranes. The QCSP is decomposed into a routing problem and a scheduling problem. The routing problem is solved by a tabu search heuristic, while a local search technique is used to generate the solution of the scheduling problem. This is done by minimizing the longest path length in a disjunctive graph. The effectiveness of our algorithm is assessed by comparing it to a branch-and-cut algorithm and to a Greedy Randomized Adaptive Search Procedure (GRASP).