Scheduling Position-Dependent Maintenance Operations in Single Machine Layouts
摘要
In this paper, we consider the single machine scheduling problem of minimizing the number of late jobs taking into account ready times, due dates, and uniform processing times. Assuming limited machine availability, position-dependent maintenance operations of uniform length must be performed on the machine no later than a given number of scheduled jobs. This type of maintenance can be found in any real-world setting where the number of jobs, rather than their length, is the main cause of deterioration, such as aircraft landing gear. We discuss the characteristics of this scheduling problem and formulate an algorithm to solve the above single machine problem in polynomial time.