𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Scheduling a maintenance activity on parallel identical machines

✍ Scribed by Asaf Levin; Gur Mosheiov; Assaf Sarig

Publisher
John Wiley and Sons
Year
2009
Tongue
English
Weight
113 KB
Volume
56
Category
Article
ISSN
0894-069X

No coin nor oath required. For personal study only.

✦ Synopsis

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 = N____P. 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

πŸ“œ SIMILAR VOLUMES

Scheduling jobs and maintenance activiti
Scheduling jobs and maintenance activities on parallel machines
✍ Chung-Yee Lee; Zhi-Long Chen πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 147 KB πŸ‘ 1 views

Most machine scheduling models assume that the machines are available all of the time. However, in most realistic situations, machines need to be maintained and hence may become unavailable during certain periods. In this paper, we study the problem of processing a set of n jobs on m parallel machin

Approximation schemes for scheduling on
Approximation schemes for scheduling on parallel machines
✍ Noga Alon; Yossi Azar; Gerhard J. Woeginger; Tal Yadid πŸ“‚ Article πŸ“… 1998 πŸ› Springer US 🌐 English βš– 124 KB πŸ‘ 1 views

We discuss scheduling problems with m identical machines and n jobs where each job has to be assigned to some machine. The goal is to optimize objective functions that solely depend on the machine completion times. As a main result, we identify some conditions on the objective function, under which

Scheduling maintenance and semiresumable
Scheduling maintenance and semiresumable jobs on a single machine
✍ Gregory H. Graves; Chung-Yee Lee πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 349 KB πŸ‘ 1 views

The majority of scheduling literature assumes that the machines are available at all times. In this paper, we study single machine scheduling problems where the machine maintenance must be performed within certain intervals and hence the machine is not available during the maintenance periods. We al