This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Kubzin, M. A. Articles by Strusevich, V. A. Search for Related Content

Planning Machine Maintenance in Two-Machine Shop Scheduling

Legion Limited, 22–26 Albert Embankment, London SE1 7TJ, United Kingdom
School of Computing and Mathematical Sciences, University of Greenwich, London SE10 9LS, United Kingdom
mikhail.kubzin{at}legion.biz
v.strusevich{at}gre.ac.uk

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.

Subject classifications: production/scheduling: approximations/heuristic; multiple machine; inventory/production: maintenance/replacement.
History: Received February 2004; revision received June 2005; accepted August 2005.