本文研究集装箱堆场作业中两个组合优化问题,其一是并行堆装载问题,其二是集装箱转运问题。重点讨论上述两个问题的计算复杂性(多项式可解或NP-困难性),整数规划模型的建立,近似算法的设计及算法近似比的理论分析,以及为满足实际需求而设计的启发式算法,并通过计算机编程加以实现。全文共分为四章,每一章的具体内容如下。第一章,首先给出了组合优化问题的有关定义,接着介绍计算复杂性与近似算法及算法性能比等概念,最后对本文所研究的堆场作业中的两个优化问题进行了详细描述。第二章,主要研究并行堆装载问题,即给定一组带有优先级的到达顺序已定的集装箱,需要暂时贮存在若干平行堆中,已知集装箱i的优先级为P_i,集装箱j的优先级为P_j,不妨假设i<j,P_i<P_j,即集装箱i先于集装箱j到达。若在某种装载方案下,集装箱i和j恰好被分派到同一个堆栈中,且集装箱j刚好位于集装箱i的上方,则此时集装箱i和j产生一个堵塞,我们的目标是寻求一个堵塞数最少的装载方案。针对这个问题,我们首先给出了它的数学规划模型。当平行堆数s=2且堆栈高度不限定时,设计了求解该问题的多项式时间最优算法。当平行堆数s=2且堆栈高度限定时,利用划分问题进行规约,证明了该问题是NP-困难的。最后,通过计算机编程进行了数值实验以评估求解该问题所提出的启发式算法的性能。第三章,主要研究了集装箱转运问题,货运列车上的集装箱需要通过起重机转运到卡车上,集装箱从货运列车到卡车有一定的转运时间,目标是寻求总转运时间最少的转运方案。该问题可转为为二部图中最小完美匹配子集权问题,针对子集个数为2的情形,我们首先建立了其整数规划模型接着利用奇偶划分问题进行规约,证明了该问题是NP-困难的,接着设计了最坏情况界为3/2的多项式时间最小权重优先算法,最后提出了最坏情况界为4/3的改进近似算法。第四章,对前三章所完成的工作,进行简单概括并且展望未来研究方向。