Scheduling a maintenance activity on parallel identical machines

Asaf Levin, Gur Mosheiov and Assaf Sarig

Naval Research Logistics (NRL), 2009, vol. 56, issue 1, 33-41

Abstract: We study a problem of scheduling a maintenance activity on parallel identical machines, under the assumption that all the machines must be maintained simultaneously. One example for this setting is a situation where the entire system must be stopped for maintenance because of a required electricity shut‐down. The objective is minimum flow‐time. The problem is shown to be NP‐hard, and moreover impossible to approximate unless P = NP. We introduce a pseudo‐polynomial dynamic programming algorithm, and show how to convert it into a bicriteria FPTAS for this problem. We also present an efficient heuristic and a lower bound. Our numerical tests indicate that the heuristic provides in most cases very close‐to‐optimal schedules. © 2008 Wiley Periodicals, Inc. Naval Research Logistics 2009

Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/nav.20324

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:56:y:2009:i:1:p:33-41

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().