Scheduling a maintenance activity on parallel identical machines |
| |
Authors: | Asaf Levin Gur Mosheiov Assaf Sarig |
| |
Affiliation: | 1. Department of Statistics, The Hebrew University, Jerusalem 91905, Israel;2. School of Business Administration, The Hebrew University, Jerusalem 91905, Israel |
| |
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 |
| |
Keywords: | scheduling parallel machines flow‐time maintenance activity |
|
|