Scheduling Position-Dependent Maintenance Operations

• 成果类型: Article
• 署名作者: Drozdowski, Maciej; Jaehn, Florian; Paszkowski, Radoslaw
• 署名单位: Poznan University of Technology; Helmut Schmidt University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2017.1659
• 发表日期: 2017
• 页码: 1657-1677
• 关键词: single-machine; processing times; jobs; availability; SUBJECT; models

摘要

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.