堆取料机调度问题的一个近似算法

研究源自煤炭港口料场管理的堆取料机调度问题.该问题中,堆取料机从长为L的料场作业区最左端开始空机或载料运行,两者的速度之比为s:1(s≥1).决策者需确定储料堆在作业区的分布以及堆取料机处理它们的先后次序,目的是极小化一批煤料运输船的在港服务时间.考虑堆取料机处理完毕需要回到料场终端的作业模型,证明了存在最坏情况界不超过1+1/4s的近似算法.

煤炭码头堆取料机的调度问题

研究了煤炭码头堆取料机的调度问题。以极小化最大堆取料完成时间为目标,给出了堆取料机可在工作区任意位置结束工作的情形的多项式时间最优算法。当堆取料机在工作区任一端或起始端结束时,证明了该问题是NP-hard的,同时对两种情形分别设计了最坏情况界是1+13 s的近似算法。