Scheduling position-dependent maintenance operations
Publication date
2017-10-23
Document type
Forschungsartikel
Author
Organisational unit
Scopus ID
Publisher
INFORMS
Series or journal
Operations Research
ISSN
Periodical volume
65
Periodical issue
6
First page
1657
Last page
1677
Peer-reviewed
✅
Part of the university bibliography
✅
Language
English
Keyword
Maintenance scheduling
Position-dependent maintenance
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.
Version
Published version
Access right on openHSU
Metadata only access