Scheduling Position-Dependent Maintenance Operations
Maciej Drozdowski, Florian Jaehn, Radosław Paszkowski
Operations Research · 2017 · Volume 65 · Issue 6
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
Enable JavaScript for citation tools and additional paper interactions.