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

Approximation algorithms of quay crane scheduling with non-interference constraints

作　　者：张文帅[1] 张安[1] 陈光亭[1,2] 陈永[1] 

机构地区：[1]杭州电子科技大学理学院,浙江杭州310018 [2]台州学院数学与信息工程学院,浙江台州317000

出　　处：《高校应用数学学报（A辑）》2016年第3期351-356,共6页Applied Mathematics A Journal of Chinese Universities(Ser.A)

基　　金：国家自然科学基金(11571252;11201105;11401149);浙江省自然科学基金(LY16A010015)

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

关 键 词：码头起重机 调度 近似算法 最坏情况分析 

分 类 号：O221.7[理学—运筹学与控制论]