ASSESSING THE EFFECTS OF MACHINE BREAKDOWNS IN STOCHASTIC SCHEDULING John R. Birge Department of Industrial and Operations Engineering University of Michigan Kevin D. Glazebrook Department of Statistics University of Newcastle upon Tyne. Technical Report 88-1 January 1988

1 Assessing the effects of machine breakdowns in stochastic scheduling by John R. Birge, Department of Industrial and Operations Engineering, University of Michigan, and Kevin D. Glazebrook, Department of Statistics, University of Newcastle upon Tyne. ABSTRACT In most scheduling problems discussed in the literature it is assumed that the machine (i.e. key resource) is continuously available. Plainly, this is often unrealistic. Here we suggest assessing the effects of machine breakdowns by evaluating the strategy which is optimal when the machine is always available as a strategy for the breakdowns case. The results extend earlier ones of the authors and co-workers. ALTERNATING RENEWAL PROCESS, GITTINS INDEX, RENEWAL FUNCTION, STOCHASTIC SCHEDULING.

2 1. Introduction Let J = {1,2,...,N} be a set of jobs to be processed on a single machine th which is subject to breakdown. For k = 1,2,... the k breakdown of the machine is associated with two random variables Uk and Dk, both taking values th in the positive integers. Uk is the k uptime for the machine, i.e. the length of the period between the (k - 1)t and the kth breakdown. is the kth machine downtime, i.e. th breakdown. All of these random variables are independent of each other, and further the uptimes and downtimes are (separately) identically distributed. This process of breakdowns constitutes an alternating renewal process (see Ross (1970)). We further assume that the uptimes have finite first and second moments, i1 and 2', that the downtimes have finite first moment MD and that the machine is up from time 0 until U1. The processing requirement of Job j is a random variable Xj, taking values in the positive integers, 1 < J g N. The X.'s are independent of each J other and of the uptimes and downtimes. For each non-negative integer point in time t at which the machine is functioning, one of the jobs in J which has not yet been completed must be chosen for processing during [t,t + 1). Processing stops when all of the jobs have been finished. A policy I is any rule for deciding how to process the jobs in J. Under i, job j is completed at time F Tr). The objective is to choose a policy which minimizes expected weighted flow time C() = E{ jFj()} (1) j=1 where the wj's are given positive constants. For a machine which is continuously available (i.e. downtimes are zero), any optimal policy is known to be determined by a collection of Gittins' indices (see Gittins (1979) and Glazebrook (1984)). If job j has received x

3 units of processing and has still to complete, its Gittins index is defined to be r t-2 w 2 pj(x+t-1)[ It {l-p (x+s)}] ~=1 s-nTr(x) = sup r-l t-l, x = 0,,2,... (2) r- 2 [ IT {l-p (x+s)}] t=O s=0 J where p(t) = p(Xj = t + 1IXj > t), t = 0,1,2,... is the completion rate function for job j. Hence in the absence of breakdowns, an optimal policy always allocates the machine to any uncompleted job with maximal Gittins index. Glazebrook (1987) pointed out that this remains optimal for a problem with breakdowns when the uptimes are geometrically distributed. Our objective is to-evaluate the simple "no breakdowns" optimal policy determined by the Gittins' indices in (2) as a policy for our general problem with breakdowns. For convenience denote by Xr a policy which, whenever the machine is up, processes the uncompleted job with the largest Gittins index. Denote by vr an optimal policy. We shall seek to evaluate Tr by putting upper bounds on the quantities C(^) - C(r") (3) or {C(r) - C(.r)}{C(r )}. (4) Following on from the last remark in the previous paragraph, a natural approach is to bound the quantities in (3) or (4) by a quantity which measures the extent to which the uptimes fail to be geometric. This work is reported in Section 2 and extends results due to Glazebrook (1987). A more general result in Section 3 extends previous work by Birge, Frenk, Mittenthal and Rinnooy Kan (1987) which was restricted to the case of deterministic processing times.

4 2. Bounds based on stochastic orderings We shall need some preliminary remarks and definitions relating to the renewal process NU(t) determined by the up-times, i.e. Nu(t) sup{k 0: U1 + U2 +... + Uk t}. The renewal function mU(t) is defined as usual to be E{NU(t)}. We shall use the notation Nv(t), Nw(t), mV(t), mW(t) to represent renewal processes and functions defined with respect to i.i.d. random variables {V1,V2,...} and {W1,W2,...} respectively. Throughout, all random variables are assumed to be positive integer-valued with finite mean. We make use of the following ideas from reliability theory (see Barlow and Proschan (1975)). DEFINITION 1. Positive integer-valued random variable V is new better than used in expectation (N.B.U.E.) if E(V) > E(V - vV v + 1), v = 0,1,2,... DEFINITION 2. Positive integer-valued random variable V is new worse than used in expectation (N.W.U.E.) if E(V) ~ E(V - v|V > v + 1), v = 0,1,2,.... The following result follows fairly simply from Theorem 3.14 in Chapter 6 of Barlow and Proschan (1975). In Lemma 1 "< sT" denotes stochastic ordering. LEMMA 1. Suppose that there exists a N.B.U.E. random variable V1 and a N.W.U.E. random variable W1 such that V1 ~ ST U1 i ST W1 then t/E(Vl) 2 mV(t) 2 mU(t) 1 mU(t) > t/E(W1), t > 0. Geometric random variables are both N.B.U.E. and N.W.U.E. and hence Lemma 1 relates to the situation where the uptimes are stochastically bounded above and below by such variates. The following definitions relate to the "closest" such bounding variables obtainable.

5 DEFINITION 3. The upper geometric rate Tr of uptime U1 is defined as T7 = inf{ T > 0; V < Sr U1 where V1 is geometric with probability }. DEFINITION 4. The lower geometric rate r] of uptime U1 is defined as 7 = sup{T7 > 0; U1 < S W1 where W1 is geometric with probability 77} - Ti It is not difficult to show algebraically that if Tl(T) is the completion rate function of uptime U1 then J -1 sup 7T(j) 2 77 = sup[l - ( 1 1 - 7(k)})) ] > sup{ ri(k)-j } j j k=l j k=l (5) > inf{ 2 tr(k)-j } > infl[ - ( 1 1 - 7(k)))] = Ti 2 infT7(j). j k=l j k=l - j We are now in a position to use the above bounds on the uptimes and the related bounds on renewal functions to give the evaluation of the "no breakdowns" optimal strategy r we seek. Let - be a strategy for our stochastic scheduling problem with breakdowns, which is stationary with regard to the values of past downtimes. Optimal v plainly has this property. Under vr job j is completed at time F (r). Denote by F0j() the implied completion time of j under policy v when there are no breakdowns (i.e. U1 is infinite). The assumptions concerning independence and finiteness of moments imply via a simple conditioning argument that = jI w(Fj(") + mu{ ( )}) ] (6) j=l Theorem 1 embodies an evaluation of w in terms of a measure of the extent to which the uptimes fal to be geometric. which the uptimes fail to be geometric.

6 THEOREX 1 - N 0 (a) C(r) - C(w ) < (. - n)E[ 2 wF()] j=l j j(I -- (b) {C(7r ) - C(r)}(Gr)} {( -1 }{1 + } < {(7(T1)} - 1 Proof From Lemma 1, Definition 3 and (6) it follows that N C(r) = E[ wj(Fj (r) + mu{Fj(7r)}D)] J=1 N (1 + TuID)E[ 2 wjF( )]. J=* Similarly we have that N C(T ) > (1 + _p)E[ 2 wj Fj()] j=l J J N ~ (1 + _ )E[ Z w F() the latter inequality following from the optimality of IT for the no-breakdowns case. Inequalities (a) and (b) now follow simply. Note that since (j - rl) and {(n(n) } - 1 are both natural measures of the extent to which uptimes fail to be geometric then in Theorem 1 we have achieved our stated objective - namely the evaluation of v in terms of such measures. It follows fairly simply from Lemma 1 that we can do rather better than Theowi 1 in the case of N.B.U.E. and N.W.U.E. uptime distributions. This is of considerable practical importance since all of the standard discrete distributions have monotonic completion rate functions and hence are either N.B.U.E. or N.W.U.E. Theorem 2 has a proof which is a simple elaboration of that of Theorem 1 and hence it will not be given.

7 THEOREM 2 (i) If uptime U1 is N.B.U.E. then (a) C(i) - C( ) - (H )E[ w F(T )] - -1 (b) (C() - C(T)){C(*)} 1 {(1 - )D}{1 + _p} 1 g (_rl)' - I. (ii) If uptime U1 is N.W.U.E. then (c) C( ) - C() A ( - N1i 2 o ( j=1 originate from Lorden's inequality for the renewal function which, under the conditions assumed here, states that 1 M (t) 1, t 11. (7) THEIREl Al -2 N C(T) - C(T ) -2iL1 1 ( 2 w,=,, 1=1 Proof From the right-hand side of (7), together with (6), it follows that C(t) = E[ I wj(Fj(T ) + mu{F( T)}D)] J i=1 N F0(r ) ~ E[lI w (Fj( ) + D( 1 + 2 )] j=l N N1 N N -1. j__ _

8 Similarly, from the left-hand side of (7), we have that N N C(ir) > (1 + IL )EC Z w.F )] - ( 2 wj) j=l J J j=l -l N N -1 N 0 N > (1 + )[ l1 )EC Z w.F ( - ) ( j w ) j=l j j j=l J the latter inequality following from the optimality of r for the no-breakdowns case. The result now follows. REFERENCES BARLOW, R.E. and PROSCHAN, F., (1975), Statistical theory of reliability and life testing, Holt, Rinehart and Winston, New York. BIRGE, J.R., FRENK, J.B.G., MITTENTHAL, J. and RINNOOY KAN, A.H.G., (1987), Single machine scheduling subject to stochastic breakdowns (unpublished m.s.). GITTINS, J.C., (1979), Bandit processes and dynamic allocation indices (with discussion), J. Roy. Statist. Soc. B41, 148-177. GLAZEBROOK, K.D., (1984), Scheduling stochastic jobs on a single machine subject to breakdowns, Naval Res. Logist. Quart. 31, 251-264. GLAZEBROOK, K.D., (1987), Evaluating the effects of machine breakdowns in stochastic scheduling problems, Naval Res. Logist. 34, 319-335. ROSS, S.M., (1970), Applied probability models with optimization applications. Holden-Day, San Francisco.