Journal of the Operational Research Society (2010) 61, 882 --887

© 2010

Operational Research Society Ltd. All rights reserved. 0160-5682/10 www.palgrave-journals.com/jors/

Scheduling a deteriorating maintenance activity on a single machine G Mosheiov1∗ and JB Sidney2 1 The

Hebrew University, Jerusalem, Israel; and 2 The University of Ottawa, Ottawa, Ontario, Canada

We study a problem of scheduling a maintenance activity on a single machine. Following several recent papers, the maintenance is assumed to be deteriorating, that is, delaying the maintenance increases the time required to perform it. The following objective functions are considered: makespan, flowtime, maximum lateness, total earliness, tardiness and due-date cost, and number of tardy jobs. We introduce polynomial time solutions for all these problems. Journal of the Operational Research Society (2010) 61, 882 – 887. doi:10.1057/jors.2009.5 Published online 22 April 2009 Keywords: scheduling; single-machine; maintenance activity; polynomial-time solution

1. Introduction Scheduling a maintenance activity in a manufacturing system has attracted several researchers in the last years. In most cases, during the maintenance time, the production process is stopped, leading to an increase of the completion times of the following jobs. In some models, performing the maintenance activity within a given period of time is crucial (see eg Lee and Chen, 2000), whereas in others, maintenance is optional (Lee and Leon, 2001). In the latter case, the motivation to perform the maintenance is the fact that it improves the efficiency of the processor, and the processing times of jobs processed after the maintenance become shorter. Hence, the questions (i) whether to schedule the maintenance activity (in the latter model), and (ii) when to do it, (in both models), are challenging. In a recent paper, Kubzin and Strusevich (2006) considered a setting where the maintenance activity is deteriorating, that is delaying the maintenance activity increases the time required to perform it. The longer the maintenance activity is delayed, the worse the system conditions become, so that the maintenance requires more effort and time. Kubzin and Strusevich (2006) study makespan minimization on a twomachine flowshop and a two-machine openshop. Following Kubzin and Strusevich (2006), in this paper we study scheduling problems with a deteriorating maintenance activity. The underlying assumptions are those of Lee and Leon (2001): the maintenance activity is optional, it may be performed once during the production process, and it improves the production rate of the processor (which is reflected in smaller processing times of jobs scheduled after the maintenance activity). As in Kubzin and Strusevich, we assume that the maintenance time increases with the starting ∗ Correspondence: G Mosheiov, School of Business Administration, The Hebrew University, Jerusalem 91905, Israel. E-mail: [email protected]

time of the maintenance activity. Similar to many scheduling models with deteriorating jobs (see the recent survey paper on scheduling with position-dependent processing times, Cheng et al, 2004), we assume here that the maintenance time deteriorates linearly. We study this setting for several classical objective functions. All problems are shown to be solved in polynomial time.

2. Formulation Consider a single machine setting and n independent jobs. All jobs are available for processing at time zero. The (basic) processing time of job j is denoted by a j , j = 1, 2, . . . , n. The scheduler has an option to perform a maintenance activity denoted by MA. As mentioned, the impact of performing this activity is reflected in a reduction of the job processing times: if job j is scheduled after the maintenance activity (called by Lee and Leon (2001), the rate modifying activity), then its processing time becomes b j (b j  a j ), j = 1, . . . , n. The basic and shorter processing times of the jth job in the sequence are denoted by a( j) and b( j) , respectively. The length of time required to perform the maintenance activity TMA increases linearly with its starting time: TMA = T0 + t, (where T0 and  are positive constants, and t is the MA’s starting time). It should be noted that in the context of scheduling a maintenance activity (or, in general, when machine nonavailability periods are assumed), the scheduling literature (see eg Lee, 2004) considers two important settings: (i) the non-resumable case: if a job is interrupted by the maintenance, it needs to be restarted from the beginning when the machine becomes available again, and (ii), the resumable case: when such a job does not need to restart and will complete its processing after the maintenance. For a given schedule, C j denotes the completion time of job j, j = 1, . . . , n. If d j is the due-date of job j, then its

G Mosheiov and JB Sidney—Scheduling a deteriorating maintenance activity

lateness is L j = C j − d j , j = 1, . . . , n. The earliness and tardiness of job j are defined by E j = max{d j − C j , 0} and T j =max{C j −d j , 0}, respectively. The earliness and tardiness costs per unit of time are denoted by  and , respectively. In the case of a common due date (d j = d), we denote the cost per unit of time for (delaying) the due-date by . Finally, we define the standard indicator for tardiness: U j = 1 if C j > d j (a tardy job), and U j =0 if C j  d j (on-time job), j =1, . . . , n. Most classical objectives are considered: makespan, flowtime, maximum lateness, total earliness, tardiness and duedate cost, and minimum number of tardy jobs. Formally, if TMA =T0 + t denotes the (linearly deteriorating) maintenance time, and p j = (a j , b j ) reflects the normal and the shortened processing times, the problems studied here are: (i) (ii) (iii) (iv) (v)

1/TMA = T0 + t, p j = (a j , b j )/C max 1/TMA = T0 + t, p j = (a j , b j )/ C j 1/TMA = T0 + t, p j = (a j , b j )/L max 1/TMA =T0 +t, p j =(a j , b j ), d j =d/ ( E j +T j +d) 1/TMA = T0 + t, p j = (a j , b j ), d j = d/ U j

In all these cases we look for the optimal schedule of both the jobs and the maintenance activity. An obvious property of an optimal schedule in all these problems is Lemma 1 The maintenance activity (if performed) is scheduled between two consecutive jobs. Proof Assume that the maintenance activity is scheduled  units of time after the starting time of the kth job processed ( < p(k) ). If a job has to restart after the maintenance activity (the non-resumable case), then obviously it is better to start the maintenance  time units earlier (prior to job (k)) even in the case of non-deteriorating maintenance. In the resumable case, again, it is better to start the maintenance  time units earlier, since both the maintenance time and the processing time of job (k) are reduced, as well as the completion times of job (k) and all the jobs that follow job (k). 

3. Minimum makespan In this trivial case there are two candidates for optimality: either the maintenance activity is performed at time zero (when its processing TMA is minimized and all the job processing times are shortened), or the maintenance is not performed at all. In both cases the order of the jobs is immaterial. The better of these two options is optimal. Hence, makespan minimization is solved in O(n), the time required   to compute ai and T0 + bi .

4. Minimum flowtime Lee and Leon (2001) showed that minimizing flow time on a single machine with the option of scheduling a maintenance activity of fixed duration has a polynomial time solu-

883

tion. Given that an optimal schedule exists in which the maintenance activity is performed at the completion time of a job, there are n + 1 options that need to be considered: either schedule the maintenance activity prior to each of the n jobs, or do not schedule it at all. The latter case is solved by the SPT (Shortest Processing Time first) schedule using the basic processing times ai , whereas for each one of the other n options, a standard assignment problem (of jobs to positions) needs to be solved. The assignment problem is known to be solvable in O(n 3 ) (see Kuhn, 1955), implying that the total running time required is O(n 4 ). We show that a similar procedure is valid for the more general case of a deteriorating maintenance activity. Assuming that the maintenance activity is performed immediately prior to the starting time of the kth job, the total flowtime is given by: g(k)≡



C j (k)=

k−1  j=1

⎛ + ⎝T0 +

k−1 

(n− j+1)a( j) ⎞

a( j) ⎠ (n−k+1)+

k−1 

(n− j+1)b( j)

j=k

j=1

=

n 

[(n− j+1)+(n−k+1)]a( j) +T0 (n−k+1)

j=1 n 

+

(n− j+1)b( j) .

j=k

In order to formulate this problem as an assignment problem, we define the following standard binary variables:  1 if job i is assigned to position j, xi j = (1) 0 otherwise. Let ci j denote the cost associated with assigning job i to position j:  [(n− j+1)+(n−k+1)]ai for 1  j  k−1, (2) ci j = (n− j+1)bi for k  j  n. The assignment problem is Minimize g(k) =

n n  

ci j xi j + T0 (n − k + 1)

(3)

i=1 j=1

subject to n  xi j = 1, j=1 n 

xi j = 1,

1i n 1 j n

(4)

i=1

xi j  0. Thus, g(k) denotes the minimum flowtime in the case that the maintenance is performed prior to job k, k =1, . . . , n. g(n +1) denotes the flowtime in the case that the maintenance is not performed at all. Note that g(n + 1) is solved by an SPT order of the a j values, whereas g(1) is solved by an SPT order of the

884

Journal of the Operational Research Society Vol. 61, No. 5

b j values. Each of the remaining cases is reduced to the above assignment problem. The optimal solution is clearly the one with the lowest cost. The optimal position of the maintenance activity (k ∗ ) is given by k ∗ = argmin{g(k)|1  k  n + 1}. The complexity remains O(n 4 ) (follows from the requirement to solve n assignment problems, each of which has complexity O(n 3 )). We summarize: Theorem 1 1/TMA = T0 + t, p j = (a j , b j )/ in O(n 4 ) time.



C j is solved

5. Minimum maximum lateness Two properties of an optimal solution are: (i) the maintenance activity is scheduled to finish at the start time of one of the jobs, or not scheduled at all (proved above); (ii) an optimal schedule exists in which the set of jobs scheduled prior to the maintenance activity and the set of jobs scheduled after the maintenance activity are scheduled according to EDD (Earliest Due-Date first). (ii) is easily proved by a standard pair-wise interchange argument. It remains to examine jobs i and j, where job i is the last job scheduled prior to the maintenance activity and job j is scheduled immediately after it. We claim that these two jobs are scheduled according to EDD as well. Let q1 denote a schedule with jobs i and j scheduled just prior to and just after the maintenance, respectively, and assume that di > d j . If S denotes the starting time of job i in q1 , then L i (q1 ) = S + ai − di , L j (q1 ) = S + ai + T0 + (S + ai ) + b j − d j . We create a new schedule (q2 ) by scheduling job i immediately after job j, while keeping the remaining jobs and the maintenance activity in their positions. We obtain L j (q2 ) = S + T0 + (S) + b j − d j , L i (q2 ) = S + T0 + (S) + b j + bi − di . It is easily verified that L j (q2 ) < L j (q1 ) and L i (q2 ) < L j (q1 ), implying that the maximum lateness of q2 is less than or equal to that of q1 . We conclude that there exists an optimal sequence in which (i) the set of jobs which precede the maintenance activity and the set of jobs which follow it are each in EDD order, and (ii) the due date of the last job which precedes the maintenance activity does not exceed that of the first job which follows it. Such a sequence is an EDD sequence for the whole job set. We conclude that an optimal schedule can be found by sequencing the jobs in EDD and then computing L max for the n +1 schedules that are obtained by setting k =1, 2, . . . , n +1. The initial sorting requires O(n log n), while the computation of L max (for the given EDD sequence and a given position of the maintenance activity) requires O(n). The latter is repeated n times; hence the total running time is O(n 2 ). Thus we have proved Theorem 2 1/TMA = T0 + t, p j = (a j , b j )/L max is solved in O(n 2 ) time.

6. Due-date assignment In this section we study the effect of scheduling a deteriorating maintenance activity on the classical due-date assignment problem introduced by Panwalkar et al (1982). In this setting, the (common) due-date is a decision variable, in addition to the traditional job sequencing decisions. Delaying the due-date by one unit of time increases the total cost by , whereas the earliness and tardiness unit costs are  and , respectively. Our objective is to find the optimal schedule of the jobs,  the due-date and the maintenance activity that minimize ( E j + T j + d). Two properties of an optimal schedule in the classical setting of Panwalkar et al (1982) continue to hold when a deteriorating maintenance activity is considered: (i) An optimal schedule exists with no idle time between consecutive jobs; (ii) The optimal due-date is the completion time of the job in position m, where m = (n( − ))/( + ), regardless of the position of the maintenance activity. This result is obtained by small perturbations of the due-date to both sides as in Panwalkar et al (1982). While the position of the due-date is given by the above expression, the position of the maintenance activity is found by search. (As mentioned, it may be scheduled prior to any one of the jobs or not performed at all.) It is easily verified that there are problem instances for which the maintenance activity is optimally scheduled to start at time zero (eg when T0 is sufficiently small), or not performed at all (eg when T0 is sufficiently large). Lemma 2 In an optimal schedule, either the maintenance will be scheduled at time 0, or it will be scheduled after the due date. Proof Suppose that the maintenance activity takes place over the interval (u, v) where 0 < u < v  d just prior to the start of job h, and that the due date is equal to the completion time of job j. Moving the maintenance activity to time 0 and setting the due date to the new completion time of job j will reduce the total cost as follows: (i) the processing time of the maintenance activity is smaller as it starts earlier; (ii) the processing time of job h − 1 and its predecessors is reduced; and (iii) the due date cost is reduced. (i), (ii) and (iii) above imply that the total earliness cost of job h − 1 and its predecessors is reduced. We conclude that the maintenance activity may be (optimally) scheduled either at time zero, or prior to any of the jobs processed after the due-date, or not performed at all.  Recall that the due date is the completion time of job m. If the maintenance activity is not performed at all, then the problem is reduced to that of Panwalkar et al (1982), and the optimal schedule is obtained by appropriately matching the magnitudes of the a j ’s to the magnitudes of the

G Mosheiov and JB Sidney—Scheduling a deteriorating maintenance activity

following positional weights W j : ( j − 1) + n, j = 1, . . . , m, Wj = (n − j + 1), j = m + 1, . . . , n.

+

The ith smallest a j is matched with the ith largest W j , which means that the a j ’s and the W j ’s must be sorted by magnitude, requiring a total effort of O(n log n). If the maintenance activity is performed at time zero, the total cost is given by: a

n 

E j +

n 

j=1 m 

=

T j +nd

j=1

(d−C j )+

j=1

=

n 

m 

⎛ (C j −d)+n ⎝T0 +

j=m+1

⎞ b( j) ⎠

j=1

n   ( j−1)+n  b( j) + (n− j+1)b( j) +nT 0

j=1

=

m 

j=m+1

n 

W j b( j) +nT 0 ,

j=1

where

Wj=

( j−1)+n ,

j=1, . . . , m,

(n− j+1),

j=m+1, . . . , n.

Hence, the optimal schedule is obtained by matching the shorter job processing times (bi ) to the (same) positional weights (W j ). As in the previous case, this case is solved in O(n log n). If the maintenance activity is performed prior to the kth job (k > m), then the total cost is given by a

n 

E j +

n 

j=1

=

T j +nd

j=1

m 

(d−C j )+

j=1

=

m 

n 

⎛ (C j −d)+n ⎝T0 +

j=m+1

( j−1)a( j) +

j=1

k−1 

j=1

(n− j+1)a( j)

j=m+1

⎛ + ⎝T0 +

k−1 

⎞ a( j) ⎠ (n−k+1)

j=1

+

n  j=k

=

m  j=1

m 

(n− j+1)b( j) +n

m 

a( j)

j=1

[( j−1)+(n−k+1)+n]a( j)

⎞ a( j) ⎠

+

k−1 

885

[(n − j + 1) + (n − k + 1)]a( j)

j=m+1 n 

(n − j + 1)b( j) + T0 (n − k + 1).

j=k

In a manner similar to that in Section 4, we define binary variables (see (1)), and the cost associated with assigning job i to position j is given by: ⎧ [( j−1)+(n−k+1)+n]ai for 1  j  m, ⎪ ⎪ ⎨ ci j = [(n− j+1)+(n−k+1)]ai for m+1  j  k−1, ⎪ ⎪ ⎩ for k  j  n. (n+1− j)bi The appropriate assignment problem in this case is identical to the one introduced in Section 4: Minimize (3), subject to (4). In this case, g(n + 1) denotes the total cost in the case that the maintenance activity is not performed, g(1) denotes the cost in the case that the maintenance is performed prior to the first job, and g( j) ( j = m + 1, m + 2, . . . , n) denotes the cost when the maintenance is performed prior to job j. The lowest cost provides the optimal solution. The total running time is O(n 4 ) (due to a solution of no more than n assignment problems). We conclude: Theorem 3 1/TMA =T0 + t, p j =(a j , b j ), d j =d/ T j + d) is solved in O(n 4 ) time.



( E j +

7. Minimum number of tardy jobs The problem of minimizing the number of tardy jobs on a single machine with a common given due-date with the option of performing a maintenance activity was shown to have a polynomial time solution by Mosheiov and Sidney (2003). In this section, we extend this result to the case of a deteriorating maintenance activity. The solution procedure consists of a search over the (exact) number of on-time jobs. For a given d value, we try to answer the question: is it possible to schedule h jobs on time? This problem is basically makespan minimization of h out of n jobs. Although optimality is not required, we seek a schedule whose makespan is no more than d. If the resulting makespan does not exceed d, we try to increase h. Otherwise, we have to check a smaller h value. As in the previous models, it may be optimal to perform the maintenance activity at time zero (for sufficiently small T0 value), or not to perform it at all (for sufficiently large T0 value). The other option is to perform the maintenance activity immediately preceding the processing of one of the jobs. It is obvious that performing the maintenance activity after the due-date is not useful. When trying to schedule exactly h jobs on time, we need only consider placing the maintenance activity before job k (k = 1, . . . , h) or not doing it at all, which we denote by k = h + 1.

886

Journal of the Operational Research Society Vol. 61, No. 5

If k > h the problem is solved in O(n log n) time by Moore’s algorithm (1968). Suppose that k  h. The makespan value for a given job sequence and given h and k (ie the completion time of the hth job given maintenance prior to the kth job) is C(h, k) =

k−1 

a( j) + T0 + 

j=1

= T0 +

k−1 

a( j) +

b( j)

j=k

j=1 k−1 

h 

(1 + )a( j) +

h 

b( j) .

j=k

j=1

In order to find the minimum value of C(h, k), we formulate this problem as an assignment problem. As previously (see (1)), we define binary variables. We denote the cost associated with assigning job i to position j by ci j : ⎧ (1 + )ai for 1  j  k − 1, ⎪ ⎪ ⎨ ci j = bi for k  j  h, ⎪ ⎪ ⎩ 0 for h < j. Let g(h, k) be the shortest time for completion of h jobs where the maintenance activity precedes job k (k = 1, . . . , h + 1). g(h, h + 1) refers to the case of no maintenance activity. For k  h, the assignment problem to be solved is: Minimize g(h, k) =

n n  

ci j xi j + T0

i=1 j=1

subject to (4). For k = h + 1 we solve the above problem after dropping T0 from the objective function. We use a standard binary search on the number of jobs (h) to find the maximum number of on-time jobs. The detailed Max-on-Time algorithm is provided in the appendix. Theorem 4 Algorithm Max-On-Time finds the maximum number of on-time jobsfor the problem 1/TMA = T0 + t, p j = (a j , b j ), d j = d/ Ui in O(n 4 log n). Proof The algorithm does a binary search on the number of on-time jobs, and a complete search on the position of the maintenance activity for the case of a given number of on-time jobs. Hence, the algorithm will find the maximum number of on-time jobs. For complexity, there are O(log n) iterations of Step 2. In each iteration, O(n) assignment problems are solved, each requiring O(n 3 ) steps. Thus, the complexity is O(log n)O(n)O(n 3 ) = O(n 4 log n) as claimed. 

8. Conclusions and directions for further research We studied single machine scheduling problems with an option to perform a maintenance activity. The maintenance is assumed to be deteriorating, that is, any delay implies more maintenance effort and time. The efficiency of the

machine is improved after performing the maintenance, and consequently job processing times are reduced. All the problems studied here are proved to have polynomial time solutions. A slightly different, interesting and realistic setting has been studied in the literature: the maintenance must be completed prior to a given deadline (see eg Lee and Chen, 2000). The inclusion of this constraint in our models, that is, with deteriorating maintenance (as in the Model of Kubzin and Strusevich, 2006), may lead to a challenging topic in future research. Other standard potential extensions of the models studied in this paper include multi-machine settings, other objective functions (eg the sum of weighted completion times), and a more general (not necessarily linear) maintenance deterioration. Acknowledgements — This work was supported in part by the Recanati Fund of the School of Business, The Hebrew University, Jerusalem, and in part by the Natural Sciences and Engineering Research Council of Canada (NSERC) grant number OGP0002507.

References Cheng TCE, Ding Q and Lin BMT (2004). A concise survey of scheduling with time-dependent processing times. Eur J Opl Res 152: 1–13. Kubzin MA and Strusevich VA (2006). Planning machine maintenance in two-machine shop scheduling. Opns Res 54: 789–800. Kuhn HW (1955). The Hungarian method for the assignment problem. Nav Res Logist Quart 2: 83–97. Lee C-Y (2004). Machine scheduling with availability constraints. In: Leung JY-L (ed). Handbook of Scheduling. Chapman and Hall/CRC: Boca Raton, FL, pp 22.1–22.13. Lee C-Y and Chen Z-L (2000). Scheduling jobs and maintenance activities on parallel machines. Nav Res Logist 47: 145–165. Lee C-L and Leon VJ (2001). Machine scheduling with a ratemodifying activity. Eur J Opl Res 129: 119–128. Moore JM (1968). An n job, one machine sequencing algorithm for minimizing the number of late jobs. Mngt Sci 15: 102–109. Mosheiov G and Sidney J (2003). New results on sequencing with rate modification. INFOR 41: 155–163. Panwalkar SS, Smith ML and Seidmann A (1982). Common duedate assignment to minimize total penalty for the one machine scheduling problem. Opns Res 30: 391–399.

Appendix Algorithm Max-on-Time The following algorithm finds the maximum number of on-time jobs. The algorithm executes a binary search on h = number of jobs (0  h  n). Additional notation to describe the solution include: OT:

 = (1 , 2 , . . . ,  O T ): k:

The cardinality of the largest on-time set found so far the set of on-time jobs listed in the order which yields OT the position of the maintenance activity within  as defined above

G Mosheiov and JB Sidney—Scheduling a deteriorating maintenance activity

Algorithm Max-on-Time (1) Initialization (a) Set initial bounds of binary search on h: Low = 0, High = n. (b) Set initial value for solution variables: O T = 0, k = 0,  = . (2) Binary search on number of jobs (a) Choose new value of h: h = h + (High-Low)/2. (b) For u = 1 to h + 1 (i) if g(h, u)  d [found h on-time jobs] (1) O T ← h, k ← u,  = (1 , 2 , . . . , h ) = list of on-time jobs in the order found by assignment algorithm. (2) if Low = High [finished binary search], output OT, k and 

887

(3) otherwise, Low ← h + 1 [continue binary search] (4) return to Step 2 (ii) Otherwise (if g(h, u) > d) (1) if u = h + 1 [Failed to get solution with h on-time jobs] (a) if Low = High [finished binary search], output OT, k and  (b) otherwise, High ← h − 1 [continue binary search] (c) return to Step 2 (2) if u < h + 1, continue with next value of u in Step 2(b). Received July 2008; accepted December 2008 after one revision