 A note on "scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan"Dehua Xu, Yunqiang Yin and Hongxing Li European Journal of Operational Research, 2009, vol. 197, issue 2, 825-827 Abstract: In a recent paper, Chen [J.S. Chen, Scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan, European Journal of Operational Research 190 (2008) 90-102] proposes a heuristic algorithm to deal with the problem Scheduling of Nonresumable Jobs and Flexible Maintenance Activities on A Single Machine to Minimize Makespan. Chen also provides computational results to demonstrate its effectiveness. In this note, we first show that the worst-case performance bound of this heuristic algorithm is 2. Then we show that there is no polynomial time approximation algorithm with a worst-case performance bound less than 2 unless P=NP, which implies that Chen's heuristic algorithm is the best possible polynomial time approximation algorithm for the considered scheduling problem. Keywords: Scheduling; Single; machine; Maintenance; Heuristic; algorithm; Worst-case; analysis (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:197:y:2009:i:2:p:825-827 Access Statistics for this article European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati More articles in European Journal of Operational Research from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.