In the scheduling problem addressed in this note we have to determine: (i) the job sequence, (ii) the (common) due-date, and (iii) the location of a rate modifying (maintenance) activity. Jobs scheduled before (after) the due-date are penalized according to their earliness (tardiness) value. The processing time of a job scheduled after the maintenance activity decreases by a job-dependent factor. The objective is minimum total earliness, tardiness and due-date cost. We introduce a polynomial (O(n4))(O(n4)) solution for the problem.
Lee and Leon [1] introduced a new class of scheduling problems. In these problems, in addition to the traditional (job scheduling) decisions, a decision has to be made regarding a rate modifying activity. This activity affects the performance of the machine, i.e., it affects the production time of the following jobs. Both positive and negative effects may occur. However, quite often the rate modification is due to maintenance, implying that the machine will only improve, i.e., the production rate will increase. It is obvious that during the maintenance period, the machine is idle and no production takes place. Thus, when scheduling a maintenance activity, one has to consider the tradeoff between the temporary machine shutdown, and the improvement in the production rate. Lee and Leon [1] studied several single machine scheduling problems in this class: minimizing makespan, flow-time, weighted flow-time and maximum lateness. Mosheiov and Sidney [2] addressed the problems of minimizing makespan with precedence relations, minimizing makespan with learning effect, and minimizing the number of tardy jobs.
In this note we study a classical due-date assignment problem with the option of scheduling a maintenance activity. Panwalker, Smith and Seidmann [3] addressed the following single machine scheduling and common due-date assignment problem: “…All jobs have a common (but unknown) due-date. The objective is to find an optimal value of the due-date and optimal sequence which minimizes the total penalty based on the due-date value and the earliness or tardiness of each job”. Panwalker et al. consider a set of nn jobs available at time zero. The common due-date dd is a decision variable. The processing time of job jj is denoted by pjpj, j=1,…,nj=1,…,n. For a given schedule, the completion time of job jj is denoted by CjCj. The earliness and tardiness of job jj are defined as Ej=max{d−Cj,0}Ej=max{d−Cj,0} and Tj=max{Cj−d,0}Tj=max{Cj−d,0}, j=1,…,nj=1,…,n, respectively. Three cost components are assumed: for earliness, for tardiness and for (delaying the) due-date. The unit penalties for earliness, tardiness and due-date are denoted by αα, ββ and γγ, respectively.
The objective is to minimize the total cost, i.e.,
Panwalker et al. [3] presented an O(nlogn)O(nlogn) solution for the problem.
When considering the option of performing a rate modifying activity, both the optimal job sequence and the complexity of the solution algorithm may change significantly. Both issues are investigated in this note. The rate modifying activity is denoted by rmrm, and (as in Lee and Leon [1]) the length of rmrm is denoted by tt. The processing of job jj if scheduled after rmrm is δjpjδjpj, j=1,…,nj=1,…,n, where δj>0δj>0 is the modifying rate. (Although the solution presented in this note is valid for any positive δδ-value, as mentioned above, in most applications, namely when scheduling a maintenance activity, δj<1δj<1.) A solution of the problem consists of finding: (i) the optimal job sequence, (ii) the optimal due-date, and (iii) the optimal timing of the rate modifying activity. Using the conventional notation, the problem studied in this note is View the MathML source1/rm/∑j=1n(αEj+βTj+γd). We show that the problem is solvable in polynomial (O(n4))(O(n4)) time.
This note is a first attempt to study maintenance activity scheduling and due-date assignment simultaneously. We show that the problem (an extended version of the classical problem of Panwalker et al. [3]) remains solvable in polynomial time.
Future research may focus on a similar problem with job-dependent earliness and tardiness costs. This more general version is known to be NP-hard (see Hall and Posner [4]) even with no rate modifying activity, no due-date cost, and symmetric earliness–tardiness cost. Thus, either accurate approximation techniques or efficient (pseudo-polynomial) exact algorithms are needed. The same rate modifying scheduling problem can also be solved with other machine settings, e.g. parallel identical machines or a two-machine flow-shop.
