We study the problem of unrelated parallel-machine scheduling with deteriorating maintenance activities. Each machine has at most one maintenance activity, which can be performed at any time throughout the planning horizon. The length of the maintenance activity increases linearly with its starting time. The objective is to minimize the total completion time or the total machine load. We show that both versions of the problem can be optimally solved in polynomial time.
Production scheduling and preventive maintenance planning are fundamental operational problems in the manufacturing industry. The simultaneous consideration of these two problems has received increasing attention from the scheduling research community and the corresponding scheduling problem is commonly known as “machine scheduling with availability constraints”. Most of the studies on this problem assume that the maintenance time is constant and known in advance. However, some studies assume that the maintenance time is constant while the starting time of the maintenance activity is a decision variable, which can take place within a known time interval. On the other hand, Lee and Leon (2001) consider single-machine scheduling with a rate-modifying activity. The rate-modifying activity is optional, which, if performed, changes the production rate of the machine. For more information, the reader may refer to the surveys on this subject by Schmidt, 2000, Ma et al., 2010 and Lee, 2004.
It is noted that all of the above studies assume that the length of the maintenance activity is a constant regardless of the machine conditions. However, in real production, the length of the maintenance activity performed on a machine may depend on the state (e.g., running time) of the machine. For example, in the timber industry, log band mills are one of the main machines in a sawmill. Generally, the saw of a log band mill is maintained by an auto band saw sharpener to sustain the sharpness of its teeth. Specifically, the earlier a log band mill undergoes the teeth sharpening maintenance activity, the less blunt are its teeth, so the less time is needed to sharpen them. The motivation for this study stems from a sawmill that cuts various sizes and shapes of wood. Each log band mill is operated by a skilled worker. Typically, several log band mills are simultaneously available and a job (log) can be processed by any one of them. The conditions of the log band mills and workers are different. Therefore, the jobs have different processing times depending on the log band mills selected to process them.
Kubzin and Strusevich (2005) study a two-machine flow shop scheduling problem with no-wait in process to minimize the makespan with a maintenance period on one of the machines. They assume that the length of the maintenance activity depends on its starting time and provide a polynomial time approximation scheme for the problem. Kubzin and Strusevich (2006) consider the two-machine open shop and flow shop scheduling problems to minimize the makespan. They assume that each machine has to be maintained exactly once during the planning horizon and the length of each of maintenance activity depends on its starting time. They show that the open shop problem is polynomially solvable and the flow shop problem NP-hard, for which they present a fully polynomial approximation scheme and a fast 3/2-approximation algorithm. Mosheiov and Sidney (2010) study a single-machine scheduling problem with an option to perform a deteriorating maintenance activity. The objectives are to minimize the makespan, total completion time, maximum lateness, number of tardy jobs, and total earliness, tardiness, and due-date cost. They introduce polynomial time solutions for all these problems. Yang and Yang (2010) consider a single-machine scheduling problem with a position-dependent aging effect described by a power function and maintenance activities that have variable maintenance durations. The objective is to find jointly the optimal maintenance frequency, the optimal maintenance positions, and the optimal job sequence to minimize the makespan. They show that the problem can be optimally solved in polynomial time.
We extend the model proposed by Mosheiov and Sidney (2010) to the unrelated parallel-machine setting. The objectives are to minimize the total completion time and the total machine load. We show that both versions of the problem can be optimally solved in polynomial time.
In this paper we study the problem concerning unrelated parallel-machine scheduling with deteriorating maintenance activities. We show that both versions of the problem are solvable in polynomial time. Future research may focus on similar problems with several maintenance activities throughout the planning horizon. It would also be interesting to investigate an extension of the problems to other shop settings or involving other performance measures.
