Planning Machine Maintenance in Two-Machine Shop Scheduling

M. A. Kubzin () and V. A. Strusevich ()
Additional contact information
M. A. Kubzin: Legion Limited, 22--26 Albert Embankment, London SE1 7TJ, United Kingdom
V. A. Strusevich: School of Computing and Mathematical Sciences, University of Greenwich, London SE10 9LS, United Kingdom

Operations Research, 2006, vol. 54, issue 4, 789-800

Abstract: We consider the two-machine open shop and two-machine flow shop scheduling problems in which each machine has to be maintained exactly once during the planning period, and the duration of each of these intervals depends on its start time. The objective is to minimize the maximum completion time of all activities to be scheduled. We resolve complexity and approximability issues of these problems. The open shop problem is shown to be polynomially solvable for quite general functions defining the length of the maintenance intervals. By contrast, the flow shop problem is proved binary NP-hard and pseudopolynomially solvable by dynamic programming. We also present a fully polynomial approximation scheme and a fast 3/2-approximation algorithm.

Keywords: production/scheduling: approximations/heuristic; multiple machine; inventory/production: maintenance/replacement (search for similar items in EconPapers)
Date: 2006
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (31)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1060.0301 (application/pdf)

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:inm:oropre:v:54:y:2006:i:4:p:789-800

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().