Abstract
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.
Original language | English |
---|---|
Pages (from-to) | 597-609 |
Number of pages | 13 |
Journal | Acta Mathematicae Applicatae Sinica |
Volume | 34 |
Issue number | 3 |
DOIs | |
Publication status | Published - Jul 2018 |
Bibliographical note
First Online: 09 August 2018Keywords
- 90B35
- 90C59
- approximation algorithm
- numerical simulation
- performance ratio
- scheduling