文献类型：期刊文献

中文题名：Scheduling Reclaimer Operations in the Stockyard to Minimize Makespan

英文题名：Scheduling Reclaimer Operations in the Stockyard to Minimize Makespan

作者：Chao WANG[1];Xi-wen LU[1];René SITTERS[2]

机构：[1]East China University of Science and Technology, 200237, Shanghai, China;[2]VU University Amsterdam, De Boelelaan 1105, 1081 HV Amsterdam, The Netherlands

年份：2018

卷号：34

期号：3

起止页码：597

中文期刊名：Acta Mathematicae Applicatae Sinica

外文期刊名：应用数学学报（英文版）

收录：CSTPCD;;Scopus;CSCD:【CSCD2017_2018】；

基金：Supported by the National Natural Science Foundation of China(No.11371137 and No.71431004)

语种：英文

中文关键词：scheduling approximation;algorithm performance ratio;numerical simulation

外文关键词：scheduling approximation;algorithm performance ratio;numerical simulation

摘要：This paper considers a reclaimer scheduling problem in which one has to collect bulk material from stockpiles in the quay in such a way that the time used is minimized. When reclaimers are allowed to work on the same stockpile simultaneously, a fully polynomial time approximation scheme（FPTAS） is designed. Further,we present a 2-approximation algorithm in the case that any stockpile can be handled by only one reclaimer at a time. When the number of reclaimers is two, we give a 3/2-approximation algorithm. Numerical experiments show that the algorithms perform much better than our worst case analysis guarantees.
This paper considers a reclaimer scheduling problem in which one has to collect bulk material from stockpiles in the quay in such a way that the time used is minimized. When reclaimers are allowed to work on the same stockpile simultaneously, a fully polynomial time approximation scheme（FPTAS） is designed. Further,we present a 2-approximation algorithm in the case that any stockpile can be handled by only one reclaimer at a time. When the number of reclaimers is two, we give a 3/2-approximation algorithm. Numerical experiments show that the algorithms perform much better than our worst case analysis guarantees.