岸桥调度是集装箱港口的一项重要作业,直接决定了港口的运行效率和港口竞争力。已有文献通过运筹学方法研究带无交叉作业约束的岸桥调度问题,本文主要介绍岸桥调度问题中两个更加符合实际情景的约束:不同岸桥之间的安全距离约束以及部分无交叉约束。以极小化装/卸载离散分布的船舱中的集装箱总耗时为目标函数,本文设计了若干具有最坏情况保证的多项式时间近似算法。全文分为四章来阐述。第一章介绍调度与算法,以及岸桥调度模型,特别是对岸桥调度与经典平行机调度模型进行了对比,指出了两者的本质区别。第二章研究具有安全距离和无交叉作业约束的m台岸桥调度问题。文献中通常将安全距离定义为毗邻作业的岸桥之间应间隔的最少船舱数。本章对安全距离为1的情形设计了最坏情况界为(2-2/m+1)的近似算法,该算法可以推广到任意固定数目的安全距离情形。第三章,在m台无交叉作业的岸桥中替换一台为可以跨越岸桥作业的龙门起重机,本章证明此时基于“分割船舱”思想,存在最坏情况界为2-2/m的改进算法,从而表明松弛无交叉约束确实可以改进算法的性能。第四章总结全文并给出后续研究方向。