Scheduling Position-Dependent Maintenance Operations

Maciej Drozdowski (), Florian Jaehn () and Radosław Paszkowski ()
Additional contact information
Maciej Drozdowski: Institute of Computing Science, Poznań University of Technology, 60-965 Poznań, Poland
Florian Jaehn: Institute for Management Science and Operations Research, Helmut Schmidt University–University of the Federal Armed Forces Hamburg, 22043 Hamburg, Germany
Radosław Paszkowski: Institute of Computing Science, Poznań University of Technology, 60-965 Poznań, Poland

Operations Research, 2017, vol. 65, issue 6, 1657-1677

Abstract: This paper addresses one-machine scheduling with maintenance restrictions. A maintenance operation is position dependent in a sequence of normal jobs if the maintenance has to be performed after at most some defined number of job changes on the machine. We show that several problems with objective functions C max and L max are still solvable in polynomial time if position-dependent maintenance is considered. We then consider the problem of preemptive scheduling with ready times and due dates on one machine with the L max criterion. We show that this problem is computationally hard and present the characteristics of this problem—for example, the fact that optimum schedules may be nonactive. After determining a set of dominance properties, branch-and-bound and local search algorithms are proposed. The performance of the algorithms is evaluated using a series of computational experiments.

Keywords: maintenance scheduling; position-dependent maintenance (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
https://doi.org/10.1287/opre.2017.1659 (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:65:y:2017:i:6:p:1657-1677

Access Statistics for this article

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