摘要
研究了煤炭码头堆取料机的调度问题。以极小化最大堆取料完成时间为目标,给出了堆取料机可在工作区任意位置结束工作的情形的多项式时间最优算法。当堆取料机在工作区任一端或起始端结束时,证明了该问题是NP-hard的,同时对两种情形分别设计了最坏情况界是1+13 s的近似算法。
This paper studies the problem of scheduling a reclaimer on a single stock pad at a coal terminal.The goal is to minimize the overall time for reclaiming a set of stockpiles.If the reclaimer is allowed to terminate at any position of the stock pad,a polynomial time optimal algorithm is proposed;if the reclaimer has to end at one side of the pad or return to its starting side,we show that the problem becomes NP-hard and present an approximation algorithm with worst case ratio 1+13s for two cases respectively.
作者
王翼展
张安
陈永
陈光亭
WANG Yizhan;ZHANG An;CHEN Yong;CHEN Guangting(School of Sciences,Hangzhou Dianzi University.,Hangzhou Zhejiang 310018,China)
出处
《杭州电子科技大学学报(自然科学版)》
2019年第6期88-93,共6页
Journal of Hangzhou Dianzi University:Natural Sciences
基金
国家自然科学基金资助项目(11571252,11771114)