Scheduling Position-Dependent Maintenance Operations
研究单机调度中位置相关的维护操作，证明部分问题多项式可解，并针对带就绪时间和截止日期的抢占调度提出分支定界和局部搜索算法。
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.