散装物料堆场是连接内陆运输和海上运输的中转站,在出口业务中扮演着重要角色,尤其是场区的可连续作业、散料可同时堆取等优势,更凸显其重要性。本文主要研究源自煤炭码头堆场管理中的一类抽象调度问题,目的是确定散料在堆场上的堆放位置以及各储料堆的回收次序(与堆放次序一致),以极小化一批储料堆的回收耗时。对该问题,本文给出了一个简单的NP-困难性证明并设计了多项式时间的近似算法。为便于叙述,全文共分为四章。第一章,首先简要介绍调度、算法以及计算复杂性的基本概念,接着给出堆取料机调度问题模型的定义,以及若干全文通用的符号与术语。第二章,首先证明了堆取料机允许在工作区的任意位置终止的情形是多项式时间可解的,而其仅允许回到起始端或者回到工作区任意一端的情形是NP-难的。接着,对后两种情形分别设计了最坏情况界不超过1+1/3s的近似算法,其中s(≥1)为堆取料机空机运行与载料运行的速度之比。第三章,进一步研究上一章所提的NP-难问题。利用该问题与平行机排序问题的联系,设计了改进的近似算法,证明了其最坏情况界为1+1/4s。第四章,总结全文并给出结论。