一类无干涉作业的码头起重机调度问题的近似算法研究

Approximation algorithms of quay crane scheduling with non-interference constraints

集装箱港口上的大型货轮通常是由从船头到船尾纵向分布的集装箱船舱构成,而码头起重机主要负责装载或卸载集装箱.如何调度码头起重机在很大程度上影响着集装箱货轮的运输效率.该文主要研究一类无干涉作业的起重机调度问题,目标是极小化装(卸)载总耗时.对三台,四台起重机情形设计了新型调度算法,并给出了最坏情况分析,改进了文献中的已有结果.

In port container terminals, a vessel is usually divided longitudinally between head and tail into many holds to store containers, which must be loaded or unloaded by several quay cranes. The scheduling of quay cranes significantly influences the turn-around time of a container vessel. This paper studies a problem of scheduling small number of quay cranes with non-interference constraint. The objective is to minimize the overall time of loading or unloading the containers. New scheduling algorithms are designed and analyzed for three and four quay cranes, which improve previous results on this problem.