现代物流行业中,海洋运输是国际物流行业的主要运输方式,海运已成为国际贸易的支柱和推动贸易全球化的关键动力。来自中国产业信息网消息,国际贸易总运输量的2/3、中国贸易货运量的约90%均来自海运。随着中国经济的不断快速发展及影响力不断扩大,中国海港的集装箱吞吐量已经位居世界第一。港口之间为了增强自身竞争力,就如何提高港口运行效率,尤其是如何减少码头起重机的装载或卸载耗时,就显得至关重要。本文主要研究一类具有无交叉约束的码头起重机调度问题,即通过对集装箱港口的码头起重机调度,使其装载或卸载一艘集装箱货轮的时间尽可能小。对此问题,本文给出了近似算法和相应的最坏情况分析。全文将分成四章进行阐述。第一章,首先给出调度问题的定义,接着介绍近似算法、时间复杂度,最坏情况界等概念,最后介绍了本文所研究的码头起重机调度问题及其数学规划模型。第二章,本章主要研究了具有无交叉约束的m台码头起重机调度问题。对此问题,我们不仅给出了关于最优解的一个新的下界,而且给出了求解该问题的一种最坏情况界为2 - 2/m-1的”分割”调度算法,此最坏情况界是应用”分割”思想的最好可能界。最后,我们从时间复杂度和最坏情况界角度比较了几种应用”分割”思想的近似算法,并通过数值实验验证已有算法的平均性能。第三章,主要研究了两台不同速率的码头起重机调度问题。首先对文献中的已有算法进行了改进的分析,得到最坏情况紧界为min{s+1/s,(s+1)2/2s+1},其中s(≥ 1)是两台起重机的速率之比;接着设计了改进算法,并证明其最坏情况界为(1+s)2/1+s+s2。第四章,总结全文,归纳本文主要研究结论并且展望未来研究方向。