We study a single machine scheduling problem. The processor needs to go through a maintenance activity, which has to be completed prior to a given deadline. The objective function is minimum total weighted completion time. The problem is proved to be NP-hard, and an introduction of a pseudo-polynomial dynamic programming algorithm indicates that it is NP-hard in the ordinary sense. We also present an efficient heuristic, which is shown numerically to perform well.
Lee and Chen [1] studied the problem of scheduling a maintenance activity on parallel identical machines with the objective of minimum total weighted completion time. There are two underlying assumptions in their model: (i) the maintenance activity requires a given period during which no production is possible, and (ii) the maintenance must be completed prior to (not after) a pre-specified deadline (since any delay increases significantly the risk of system failure). Clearly, both assumptions reflect most real-life systems which need maintenance.
Due to the many applications, scheduling a maintenance activity became a popular topic among researchers in recent years. There are studies assuming an optional maintenance which improves the processor’s performance, see e.g. Lee and Leon [2]. Other models consider maintenance scheduling in a flow-shop environment [3], on parallel identical machines [4], a flexible maintenance [5], and a periodic maintenance (see e.g. [6], [7] and [8]). A slightly different paper [9] focuses on scheduling a deteriorating maintenance in flow-shops and open-shops.
In this note we focus on the single machine version of the problem studied by Lee and Chen [1]. We assume that all nn jobs are available for processing at time zero, and preemption is not allowed. The processing time of job jj is denoted by Pj,j=1,…,nPj,j=1,…,n. The weight of job jj is denoted by Wj,j=1,…,nWj,j=1,…,n. For a given job schedule, the completion time of job jj is denoted by Cj,j=1,…,nCj,j=1,…,n. We denote by tt the duration of the maintenance activity, which must be performed and completed not after (the deadline) TT. In order to guarantee a feasible solution, we assume that t≤Tt≤T. Thus, the maintenance activity can start at any time during the interval [0,T,−t][0,T,−t]. Pj,j=1,…,nPj,j=1,…,n, where tt and TT are assumed to be integers.
The objective function is the classical minimum total weighted completion time: View the MathML source∑j=1nWjCj. Let MA denotes the maintenance activity. Then, the problem studied here is 1/MA/∑WjCj1/MA/∑WjCj.
First we prove that the problem is NP-hard. Then we introduce a pseudo-polynomial dynamic programming algorithm, implying that the problem is NP-hard in the ordinary sense. We also suggest an efficient heuristic and a tight lower bound on the optimal weighted completion time value. In the last section we present the results of our numerical tests.
We studied the classical single machine scheduling problem to minimize job weighted completion times with the additional constraint that a maintenance activity must be performed prior to a given deadline. The problem is shown to be NP-hard in the ordinary sense. A heuristic and a lower bound are introduced, and our numerical study verifies that the heuristic performs well in all tested settings.
Future research may address the setting of parallel identical machines: an extension of the WSPT-based heuristic to this setting seems to be promising. Considering the maintenance as a “rate modifying activity” (i.e. the machine becomes more efficient after the maintenance, see Lee and Leon [2]) is also a challenging open problem. [Lee and Leon studied this case only under “agreeability” of processing times and weights.] Minimum total weighted completion time with maintenance on other machine settings are also interesting options for future research.
