Scheduling Reclaimer Operations in the Stockyard to Minimize Makespan

Chao Wang, Xi wen Lu*, René Sitters

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

102 Downloads (Pure)

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 languageEnglish
Pages (from-to)597-609
Number of pages13
JournalActa Mathematicae Applicatae Sinica
Volume34
Issue number3
DOIs
Publication statusPublished - Jul 2018

Bibliographical note

First Online: 09 August 2018

Keywords

  • 90B35
  • 90C59
  • approximation algorithm
  • numerical simulation
  • performance ratio
  • scheduling

Fingerprint

Dive into the research topics of 'Scheduling Reclaimer Operations in the Stockyard to Minimize Makespan'. Together they form a unique fingerprint.

Cite this