# Planning machine maintenance in two-machine shop scheduling

Kubzin, M.A. and Strusevich, V.A. (2006) *Planning machine maintenance in two-machine shop scheduling.* Operations Research, 54 (4 ). pp. 789-800. ISSN 0030-364X (Print), 1526-5463 (Online) (doi:10.1287/opre.1060.0301)

## 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.

Item Type: | Article |
---|---|

Uncontrolled Keywords: | production, scheduling, multiple machine, maintenance, replacement |

Subjects: | Q Science > QA Mathematics > QA75 Electronic computers. Computer science |

School / Department / Research Groups: | School of Computing & Mathematical Sciences Faculty of Architecture, Computing & Humanities > School of Computing & Mathematical Sciences School of Computing & Mathematical Sciences > Department of Mathematical Sciences Faculty of Architecture, Computing & Humanities > School of Computing & Mathematical Sciences > Department of Mathematical Sciences Faculty of Architecture, Computing & Humanities |

Related URLs: | |

Last Modified: | 19 Aug 2015 14:21 |

URI: | http://gala.gre.ac.uk/id/eprint/3676 |

### Actions (login required)

View Item |