Acta Informatica 26, 679~i96 (1989)

9 Springer-Verlag 1989

Single Machine Flow-Time Scheduling With a Single Breakdown Igal Adiri ~, John Bruno z, ,, Esther Frostig 3, and A.H.G. Rinnooy Kan 4 1 Faculty of Industrial Engineering and Management, Technion, Haifa, Israel 2 Department of Computer Science, University of California, Santa Barbara, CA 93106, USA 3 Department of Statistics, Haifa University, Haifa, Israel 4 Econometric Institute, Erasmus University, Rotterdam, The Netherlands

Summary. We consider the problem of scheduling tasks on a single machine to minimize the flowtime. The machine is subject to breakdowns during the processing of the tasks. The breakdowns occur at a random times and the machine is unavailable until it is repaired. The times for repair are random and independent of each other and of the breakdown process. A task that is preempted due to a breakdown must be restarted and otherwise preemptions are not allowed. We show in the case of a single breakdown that if the distribution function of the time to breakdown is concave then Shortest Processing Time (SPT) first scheduling stochastically minimizes the flowtime. For the case of multiple breakdowns we show that SPT minimizes the expected flowtime when the times to breakdown are exponentially distributed. If the time for a single breakdown is known before scheduling begins, and the processing times of the tasks are also known, then we show that the problem of deciding whether there is a schedule with flowtime less than or equal to a given value is NP-complete. Finally, we bound the performance of SPT scheduling in the deterministic case when there is a single breakdown. 1. Introduction and Results

It has been twenty years since the publication of the classic book by Conway et al. 1-3] on the Theory of Scheduling and over thirty years since Smith 1-6] published his work containing results on flowtime scheduling. Since that time much work has been done in the area of both stochastic and deterministic scheduling problems [4]. This includes obtaining efficient algorithms for finding optimal schedules, inventing heuristics with reasonable and provable worst-case performance, and settling the complexity of certain classes of scheduling problems. During this period the notion of NP-completeness !-5] was discovered '~ The work of this author was partially supported by The Lady Davis Fellowship Trust through a Lady Davis Visiting Professorship at the Technion, Haifa, Israel Offprint requests to: I. Adiri

680

I. Adiri et al.

and has shed much light on the difficulty of many deterministic scheduling problems. We consider a variation of a well-known scheduling problem, namely, we are given a single machine and n tasks with known processing times zl < . . . < zn. The objective is to schedule the n tasks on the single machine so as to minimize the sum of the finishing times of all the tasks (usually called the flowtime). It is well-known that scheduling the tasks according to the Shortest Processing Time first (SPT) minimizes the flowtime [6]. The SPT scheduling policy has found many applications in both deterministic and stochastic scheduling [2, Chap. 3]. In this paper we consider n tasks, one machine and, as above, the processing times of the tasks are known. The variation we consider admits the possibility that the machine might suffer breakdowns during the processing of the tasks. The breakdowns occur at random points in time where the times to breakdown are independent, identically distributed random variables. The times for repair are given by independent, identically distributed random variables. If there is a breakdown during the processing of a task, then the task is interrupted and restarted (from the beginning) at a later time. Unless there is a breakdown during the processing of a task, tasks must be processed without interruption. The objective is to minimize the sum of completion times of the tasks. Clearly, it is not necessary to consider schedules which incorporate inserted idle time and therefore the decision epochs are taken to be time zero, the completion times of the tasks, and the moments that repairs are completed. Let C~ denote the flowtime (sum of finishing times) when scheduling according to policy 7z. Let SPT denote the policy which schedules the shortest unfinished task at every decision epoch. For most of this paper we treat the case of a single breakdown. The breakdown occurs at a random time tbrk with distribution function G. When the machine breaks down it is repaired and the repair time is a random variable R with distribution function H, independent of tbrk. Unless we state otherwise, we shall be considering the version of the problem in which there is a single breakdown. As we mentioned above, if the breakdown occurs during the processing of a task, processing is interrupted and the task is restarted at some time after the machine is repaired and unless the breakdown occurs during the processing of a task, all tasks must be processed without interruptions. Although our ultimate objective is to determine a policy n* which is optimal in some sense, we have not been able to solve this problem in general. Rather, we have focused on three different aspects of the problem. Since the SPT policy is so pervasive in flowtime scheduling, it is natural to seek to determine the conditions under which the SPT policy is optimal. We have been able to show that if the distribution function is concave then SPT stochastically minimizes the flowtime-Theorem 1 summarizes what we have been able to show. Secondly, we considered the case in which the breakdown time is deterministic and known before scheduling begins. This assumption turns our problem into a strictly combinatorial optimization problem and in this case we have been able to show that it is unlikely that there exists a polynomial time algorithm which

Single Machine Flow-Time Scheduling With a Single Breakdown

681

constructs an optimal policy (Theorem 2). Finally, we considered the performance of the SPT policy in the case of a single deterministic breakdown. In this case we found a tight bound on the relative error in the SPT schedule compared to the optimal schedule (Theorem 3). The remainer of this paper is organized as follows: we have put most of the technical details of the proofs of three of our results in the Appendix. The main text discusses the assuptions of the theorems and interpretations of their significance. Part of the proof of Theorem 2 is quite lengthy and technical and is not included here. In the next section we provide some additional discussion of the case of multiple breakdowns and give some concluding observations. We need a couple of definitions before we can state our first result. A policy rr* is said to stochastically minimize the flowtime if for all policies ~z and for each t >=O,Pr{C~,<=t} > Pr{C~
G(x + s ) - G(x) >=G(y + s ) - G(y)

(1)

for each x, y, s such that O < x < y , s > 0 , and G(x)--0 for x < 0 . A consequence of this definition is that any chord lies below the function. Our first result provides a sufficient condition for SPT scheduling to remain optimal even when the machine may suffer a breakdown. Theorem 1. Assume there is a single breakdown and that the time to the breakdown is distributed according to the distribution function G. If the distribution function G is concave then SPT stochastically minimizes the flowtime. Distribution functions that are concave include: all the D F R (Decreasing Failure Rate) distributions, the exponential distribution, the gamma distribution with 0t< 1, and the uniform distribution on (0, 0). Also included are distribution functions with a positive probability that the breakdown occurs at time 0. The condition that preemptions are not allowed except at a breakdown is significant in the sense that if the processing of a task could be resumed without any time losses, rather than restarted after breakdown, then SPT is optimal for any distribution function G. The continuity condition in Theorem 1 can be omitted. Theorem 1 will hold also if G is a step function, having a jump every time interval A, satisfies (1), and the zls are multiples of A. Another criterion that can be considered is the makespan - Cmax, the maximal finishing time. We say that the distribution function G is convex up to a > 0 if the function G is continuous, G ( a ) = l , G ( x ) < l for x 0 , and y + s < a . It can be shown that if G is concave then SPT stochastically minimizes the makespan and if G is convex up to ~ zi then LPT (schedule the unfinished task with the longest i=1

682

I. Adiriet al.

processing time first) stochastically minimizes the makespan. The proof is the same as the proof of Theorem 1. Next we consider the deterministic version of our problem. In this case the processing times, the breakdown time, and the time for repair are all known before scheduling begins. This problem is of interest since it is an extreme example of a nonconcave distribution function. In showing that this problem is NPcomplete, we are providing compelling evidence that there is no polynomially computable policy for producing the optimal schedule in this case. The technical background for Theorem 2 is represented next. An instance of the single-machine flowtime problem with a single breakdown is specified by: GIVEN: n + 3 positive numbers z l < z 2 < . . . < z , , tbrk, tfix, and C, where the zis are the processing times of n tasks and 0 < tbrk < tfix. Scheduling begins at time 0 and the machine is unavailable in the interval (tbrk, tfix). No preemptions are allowed. (Note that when tbrk = tfix the interval (tbrk, tfix) is empty. In this case we require that either no processing occurs at tbrk, tbrk is the finishing time of some task, or tbrk is the starting time of some task.) QUESTION: Does there exist a schedule rc such that C, satisfies C~ < C? We show that this problem is a difficult one in the following sense. Theorem 2. The single machine flowtime problem with a single breakdown is NPcomplete. The proof of Theorem 2 shows that the single-machine flowtime problem with a single breakdown is at least as difficult as another problem which is known to be NP-complete. Since all NP-complete problems are polynomially reducible to each other it is unlikely that there is a polynomial time algorithm to solve any one of them since the existence of a polynomial time algorithm for one NP-complete problem implies the existence of a polynomial time algorithm for every NP-complete problem. Theorem 2, in demonstrating that the deterministic version of the problem is NP-complete, supplies compelling evidence that simple optimal policies such as SPT do not exist when the distribution function is not concave. If we consider C. . . . the makespan, then the problem of minimizing the makespan is NP-complete. This is easy to see since the objective is essentially to minimize the idle time prior to the breakdown. It is worth mentioning, however, that, in a manner similar to 2-partition, the deterministic problem is solvable by a pseudopolynomial-time algorithm [5]. This means that the NP-completeness of our problem depends strongly on the fact that extremely large input numbers are allowed. If any upper bound were imposed in advance on these numbers a polynomial time algorithm could be found for the restricted problem. Finally, a natural question to ask is how SPT behaves when the distribution function is non concave. We have obtained a bound on the performance of the SPT policy in the deterministic case. Let I be a problem instance and let Cser(I) and CoeT(I) denote the flowtimes of the SPT and optimum schedules, respectively, for the instance I.

Single Machine Flow-TimeSchedulingWith a SingleBreakdown

683

Theorem 3. Let I be an instance of the single-machine flowtime problem with a single breakdown. Then the relative error for the SPT schedule is RSPT(I) =

CSPT(I) -- COPT(I) < 1 COPT(I) = 4

and for each ct > 0 there exists an instance I such that RSPT(I) --

CspT(I) - COPT(I) 1 >-COpT(I) 4 + ~"

Although, Theorem 3 applies to a distribution function which is a step function, it does suggest that SPT might be a reasonable policy even when the distribution function is non concave.

2. Conclusions In this paper we have shown that the SPT policy minimizes the flowtime in the case where the machine is subject to a single breakdown, and the distribution function for the time until breakdown is concave. We conjecture that the SPT policy is still optimal for the more general case of multiple breakdowns where the times until breakdown are independent random variables with concave distribution function and the repair times are independent identically distributed random variables, i.e., the breakdown and repair is an alternating renewal process. In support of our conjecture we supply the result for the case where the times until breakdowns are exponentially distributed with parameter 2 and the repair time is a random variable R with expectation E(R). The processing times of the n tasks satisfy Z I ~ Z 2 ~ . . . ~ Z n. When a breakdown occurs during the processing of a task, the processing time that has already been delivered to the preempted task is lost and at some time later the task is restarted. If a task is not preempted by a breakdown it continues until completion. The objective is to minimize the expected flowtime. For this model we can prove the following: Theorem 4. SPT minimizes the expected flowtime.

Proof Decision epochs are time zero, task and repair completions. Let C, denote the expected flowtime under policy n. To prove the optimality of the SPT policy it is enough to show that Csvr < C,j,

(2)

where rcj is a policy that schedules task j first and from the next decision epoch onwards it is identical to SPT. Let S be the set of all n tasks. Due to the memoryless property of the exponential distribution we have: zj

C~j = n S (x + E (R)) 2 e- ax d x + (1 - e - zz~) CsPr + e - z's (n zj + CSPT(S -- {j})). (3) 0

684

I. Adiriet al.

Consider the SPT policy. In this policy when a task starts it stays on the machine until completion. Let z be the processing time of the task and z* the expected time it stays on the machine from the moment it starts. Z

z * = z + ~ e-~=(1-e-~9"n ~ ( x + E ( R ) ) 2 e - ~ dx n=l

i (x + E(R)) he -z:' =Zq-

-2z 0

1 -e

0

-'~z

dx.

e

Because of the memoryless property of the exponential distribution, z* is the expected time a task with processing time z occupies the machine no matter when the last breakdown before it started occurred. It is easy to see that: j-1

Csex- Cspx(S- {j}) = ~ z* + ( n - j + 1) z*. /=1

Since z, < z2 <... < zj <... < z,, ~ (x + E (R)) ~ e- ax -.zj o

and, consequently, (3) and (4) imply (2).

dx

(4)

e

[]

Notice that the exponential distribution function is concave. We conjecture that the optimality of the SPT policy is still valid for the more general case where the time until breakdown has a general concave distribution. For the nonconcave distribution function, the SPT policy is not optimal as exemplified by the case of a single deterministic breakdown. Moreover, the fact that the problem of deterministic time until a single breakdown is NPcomplete provides evidence that the computation of optimal schedule for the nonconcave case is extremely difficult. However, for the case of deterministic time until a single breakdown we have demonstrated that the relative error of the SPT policy is not greater than 0.25 of the optimal. Bounds for the relative error for other distribution functions and for multiple breakdowns might be evaluated by simulation.

References 1. Adiri, I., Bruno, J., Frostig, E., Rinnooy Kan, A.H.G.: Single Machine Flow-time Scheduling With a Single Breakdown. TRCS892, January 1989, Department of Computer Science, University of California, Santa Barbara, CA, 93106, USA 2. Coffman, E.G.: Computer and Job-Shop Scheduling Theory. New York: John Wiley 1976 3. Conway, R.W., Maxwell, W.L., Miller, L.W.: Theory of Scheduling. Reading, MA: Addison-Wesley 1967 4. Dempster, M.A.H., Lenstra, J.K., Rinnooy Kan, A.H.G.: Deterministic and Stochastic Scheduling. In: Proceedings of the NATO Advanced Study and Research Institute on Theoretical Approaches to Scheduling Problems. Dordrecht: Reidel 1982

Single Machine Flow-Time Scheduling With a Single Breakdown

685

5. Garey, M.R., Johnson, D.S.: Computers and Intractability, A Guide to the Theory of NP-Completeness. San Francisco: Freeman 1979 6. Smith, W.E.: Various Optimizers for Single-Stage Production. Nav. Res. Logist. Q. 3, 59~6 (1956) 7. Strauch, R.: Negative Dynamic Programming. Ann. Math. Stat., 37, 871-890 (1966) Received June 28, 1988 / March 21, 1989

Appendix Proof of Theorem 1. Let ~1 be a policy which schedules task j (j # 1) first until it completes or breakdown occurs (whichever one comes first), and from that point onwards is identical to SPT. Let rhj be the following policy: task 1 is scheduled first. If breakdown occurs during the processing of task 1 then after the repair schedule all tasks according to SPT. If task 1 finishes before the breakdown then schedule taskj. If breakdown occurs during the processing of task j or task j finishes, then schedule all tasks according to SPT. We point out that it is always best to schedule the tasks according to SPT after the breakdown occurs. The real issue is to determine which tasks are to be scheduled prior to the breakdown. Let X be an indicator random variable. For example,

~{a
if a
We define the following random variables:

("

A~= ~ (n-i+l)z

,)

x{O
\i= 1

-]-nzjq-~(n--i)zi-[\

i=1

~ (n--i+l)z

z{tbrk>zj}

i=j+l

Bjl = n(tbrk + R) Z {0 < tbrk < z~} + ( n - 1) (tbrk- zj + R) Z {zj < tbrk < z l + zj}

D = i-, ~, (n -- i)(tbrk- z, - zj - '-~ ~, Zk+ R) ~ {z , + zj + i-'zk
+

i=j+l

k=2

k=2

-

~', Zk
Similarly define:

A~J=(i~=l(n-i + l) zi) x {O< tbrk < z~ + z~} +(nzl+(n--1)zi+ ~ (n-i)zi+ i=2

)

( n - i + l ) z i x{tbrk>zl+zj} i=j+l

B lj = n (tbrk + R) Z {0 < tbrk < z l} + ( n - 1) (tbrk- z x + R) Z {zx < tbrk < z~ + z j}

I. Adiri et al.

686

The following relations hold:

C~j1= A jl + Bjl + D C=11=A1jk- B1j-k D

(5)

Let ~ and ~' be two policies. We write C~O Pr{C~
>Pr{C~,
Cltl.c~sTC~t.il.

Proof. An examination of three ranges for the possible realizations of tbrk (less than zj, greater than or equal to zj and less than z~+zj, and greater than or equal to z~ + zj) shows that

Alj< Ajl

(6)

with probability 1. Therefore

C~j, = Ajx + Bjl + D>=Alj+ Bjl + D with probability 1. Hence it is enough to show that

A~j+ BIj+ D
(7)

Demonstrating (7) we have to show that for t > 0,

Pr{A~j+ Blj+ Dz~ +zj} > Pr{A~j+ Bjl + D< t ltbrk>zx +zj}

(8)

Pr{A~j+ B~j+ D Pr{A~j+ Bjx + D
(9)

and

Equation (8) is true since if tbrk>zl +zj then Bli=Bj~ = 0 . n TO prove (9) notice that if tbrk < z~ + zj, then D = 0 and A l j = ~, (n + i + 1)zi = constant. Thus it remains to show that ~=

Pr{B~j Pr{Bj~
[]

Lemma 2

Pr{B~jPr{Bj~ <=tlR=r, tbrk
(10)

Proof Zl=Zj implies B~j=Bjl and we are done, otherwise z~ ( n - 1 ) r (r < t/(n-1)), for which six subcases are analyzed. (i) r > t / n - z 1 and r > t/(n- 1 ) - z l .

687

Single Machine Flow-Time Scheduling With a Single Breakdown

Calculation shows that

Pr{Blj
G(n~-r+zl)-G(z,)

-

G(zl + z j)

G(zl + zj)

and

Pr{B)I <=tlR=r, tbrk
- G(z~ + z j )

Since

za
(ii) r >

+ z j}

~

C,(z~ + z j )

Eq. (10) follows from (1), where s =

t/n- z x and t/(n-

1)-

zj < r < t/(n-

t

n-1

-r, x=zl,

1 ) - z 1.

Calculation reveals that

Pr{Bli
+ z j}

G(n~-r G (z i + zj)

+ zl)-G(zl)

G(Zl+Zj)

and

Pr {Bjl < t l R = r, tbrk < z I + zi} G(~--r) - G ( zl + z j)

G(zx+zj)-G(zj) ~ G ( z I + z j)

Since G is concave, we have that

Since G is monotone increasing we also have that

a (ZJ+ n - ~ - r ) - G ( z j ) > G(zj+ zl)-G(zA. Thus Eq. (10) holds for this case. (iii) r >

t/n- Zl

and r <

t/(n-

1)-

zj.

and

y=zj.

I. Adiri et al.

688 Calculating we find that

Pr{Blj
G(Zl_FZj)_G(zl )

- G(Zl + z j ) §

G(z 1 + z j )

and

Pr{BjI ~ t lR =r, tbrk
G(zO < G(zj).

i.e.,

(iv)

t/n-zj
and

t/(n- 1)-zj
1)-Za

Pr{Bxj
and

Pr {Bjl ~ t[R = r, tbrk < 2' 1 -'[- Zj} G ( t - r ) G(Zl+Zj)-G(zj) + G(zl +z i) G(zl +zj) In order to demonstrate Eq. (10) we need to show that

t

t

We have that n - r < ~ 1 - - 1 - r < zj and that G is a monotone increasing function satisfying Eq. (1). Therefore

-Zl) o(:'1 > G(z~+ z l ) - 6(zj)

Single Machine Flow-TimeSchedulingWith a Single Breakdown

689

(v) t/n - zj < r < t/n - z 1 and r < t/(n - 1) - z~

Pr { B l j < t l R = r ,

tbrk < z l + zj}

G(zl) -4 G(zl + z j ) - G ( z l ) G (z 1 + z j) G (z 1 + z j) and

tbrk
Pr{BjI < t l R = r , G(t-r)

G(Zl+Zj)-G(zj)

G(zl + zj)

G(zl + zj)

In order to demonstrate Eq. (10)we have to show that G ( t - r I - G ( z j ) < O . V" / t But this is true since G is monotone nondecreasing and - - r < zj. n (vi) r < t / n - zj and r < t/(n - 1 ) - zj

Pr {Blj < t I R = r, tbrk < z 1 + zi} G(Zl) G(zl+zj)-G(zl) -G(z~+zj) + G(z~+zj)

G(zj) G(zl+zj)-G(zj) + G(z~+zj) G(z~+zj) =Pr{Bjl
tbrk < z , + zj}.

Since (i)-(vi) exhaust all possibilities for r < t / ( n - 1), Eq. (10) follows and this completes the proof of Lemma 2. [] We now complete the proof of Theorem 1 by induction on n, the number of tasks. For n = 2 the theorem is true as a result of Lemma 1 (substituting j=2). Assume that the theorem is true for n - 1 tasks or less and consider a problem with n tasks with processing times zl < z2 < . . . < z,. To prove the theorem it is enough to show that the SPT policy is preferable to rcjl I-7]. Formally, we have to show that CSPT< C~ 1. We first show that

CSPT~ST C=,j.

(11)

If preemption occurs during the processing of task 1, then from that point onward both policies are identical (to SPT). If a breakdown does not occur during the processing of task 1 then at time z l , n - 1 tasks have to be scheduled and the distribution of the time until breakdown, given a breakdown has not occurred by time Zx, is concave, i.e.,

6(zl + x ) - 6(zl) 1 - G(Zl)

690

I. Adiri et al.

is concave in x. Thus Eq. (11) follows from the induction hypothesis. Combining (11) with Lemma 1 we have CSPT

~ST Clxlj ~ ST C1tj1 9

[]

Proof of Theorem 2. An instance of the single machine flow-time problem with a single breakdown is specified by: GIVEN: n + 3 positive numbers Zl
The traditional manner in which one shows that a problem is NP-complete is to reduce a known NP-complete problem to the problem in question. The 2-partition problem is known to be NP-complete [-5] and in what follows we describe a way of reducing (in polynomial time) instances of the 2-partition problem to instances of our scheduling problem such that an instance of the 2-partition has a solution if and only if the corresponding instance of our scheduling problem has a solution (Theorem 5).

Reduction Assume we are given an instance, say I, of the 2-partition problem, i.e., we n

~ x1 i . are given n positive numbers xl, x2, ..., x,. Denote b = ~1 i= Let A be a sufficiently large constant, namely A > 2 n b . Define X i = x l + x z + . . . + xi and Ai= A + Xi for 0 < i < n, X o = 0. Note that X~< X~+ 1 and thus Ai
QUESTION: Does there exist a schedule rc such that C~ __
691

Single Machine Flow-TimeSchedulingWith a SingleBreakdown

Theorem 5. Let I be an instance of the 2-Partition problem and Q(I) the corresponding instance of the single machine flow-time problem with a single breakdown. Then there exists a subset P of {1, 2, ..., n} such that ~" x~=b if and only if there exists a schedule rc such that C~ <=Co + b. i~P Proof of Theorem 2. Clearly the single machine flow-time problem with a single breakdown is in NP. Consequently, Theorem 2 follows from Theorem 5. [] Proof of Theorem 5: Only I f This is the easy direction of the Theorem in which we assume a solution to an instance of the 2-partition problem and show how it provides a solution to the corresponding instance of our scheduling problem. In what follows we shall consider I to be the instance of the 2-partition problem and Q (I) the corresponding instance of our scheduling problem. Observation 1. No more than n + 1 tasks can finish before tbrk. Proof A consequence of A being sufficiently large.

[]

Let ~ be a schedule. Define A~(i) to be equal to the number of tasks whose finishing times are affected by the processing time of task i. There are two cases to consider. If task i is scheduled before tbrk then the number A~(i) is 1 plus the number of tasks that follow task i and finish before tbrk. If task i is scheduled after tfix, then A~(i) is 1 plus the number of tasks which follow task i. Observation 2. Let n be a schedule and suppose n schedules k tasks before tbrk. Then we can write C~, the flow time of schedule n, as: 2n+2

C~=(2n+2-k)tfix+

~ A~(i)A~i), i=1

where A~i) is the processing time of task i corresponding to A~(i). Proof The delay tfix contributes to the finishing time of each task which is scheduled after tfix. Therefore ( 2 n + 2 - k ) t f i x is the total contribution of tfix to the flow time. The inclusion of this term justifies the value of A=(i) for tasks which are scheduled before tbrk. Generally, all the tasks which follow a given task i have their finishing times delayed by an amount Ar So the contribution of A(i) to the flow time is A~(i)A,~. [] Let tbrko = tbrk + b. Clearly, tbrko = t f i x - 1. Observation 3. I f the breakdown time is tbrk o and the fixtime is tfix (as defined above) then one obtains a schedule with the minimum possible flow time by placing n + 1 tasks with processing times A o, A x. . . . . A, before the breakdown and placing the remaining n + 1 tasks after the fixtime. There is no inserted idle time and the tasks are scheduled in increasing order of their processing times. Call this schedule 7to .

692

I. A d i r i e t al.

Proof. By Observation 2 we can write the total flow-time as C,,o = (n + 1) tfix+2(A.+2A._ 1 + 3A,-2 +-.. +nA1 +(n+ 1) Ao). By Observation 1 the quantity (n+l)tfix cannot be reduced. The 2 n + 2 coefficients A~o which are available are: 1, 1,2,2 . . . . . n , n , n + l , n + l . The schedule no pairs the tasks with the largest processing times with the smallest coefficients, and the tasks with the smallest processing times with the largest coefficients, namely,

A n1FAi n 1"-XnA -21 "A~ -2n -

1 "'"

ATA. ~n1A nn+oI A ~ ) + I "

It is well-known that this pairing of terms leads to a sum-of-products which is as small as possible. Schedules where fewer than n + 1 tasks are scheduled before tbrko have flow times which are necessarily greater than C~o. [] From here on no denotes the optimal schedule when the breakdown time is given by tbrko. By Observation 3, C~o = Co. Observation 4. If we exchange the ith task (processing time Ai) occurring before

the breakdown with the i-1st task (processing time Ai-l) occurring after the repair, then L, the length of the schedule apearing before the breakdown, decreases by xi, and the flow-time cost increases by xi. Proof. Exchange the tasks and calculate the difference in the costs.

[]

Lemma 3. Let P be a subset of {1, 2, ..., n} such that ~ xi= b. Then there is

a schedule for the flow-time problem, Q (I), where the flow-time equals Co + b. Proof. Start with schedule no. For each i~P, exchange the ith task occurring before the breakdown with the i - 1 s t task occurring after the fixtime. From Observation 4 we conclude that the schedule obtained is feasible (the n + 1 tasks occurring before the breakdown finish at tbrk= tbrko-b) and the flow-time is Co + b. []

Proof of Theorem 5: If. In this direction, we assume that there exists a schedule n for the instance Q(I) of our scheduling problem and show how this implies that there is a solution to the instance I of the 2-partition problem. In the proof we give a very careful analysis of the change in the flow-time and the corresponding change in the length of the schedule prior to the breakdown when a task occurring before the breakdown is exchanged with one occurring after the breakdown. The instance Q (I) has breakdown time tbrko-b and flowtime bound Co + b. Schedule no is feasible for breakdown tbrko and flow-time Co. Starting with the schedule no we examine all possible ways to achieve the schedule n using exchanges. It turns out that certain exchanges are not allowed since they cannot lead to the schedule n because either the flow-time increases

Single Machine Flow-Time Scheduling With a Single Breakdown

693

too quickly or the length of the schedule prior to the breakdown is too large. The feasible exchanges have the property that they reveal the identity of a set of tasks which solves the 2-partition problem. This proof is quite long and for the sake of brevity we have chosen not to include it in the appendix. The reader interested in the details is referred to the report [1] which is available upon request. Proof of Theorem 3. The machine is unavailable in the time interval (tbrk, tfix). Let z o = t f i x - tbrk. We assume without loss of generality that z~
u = t b r k - ~ zi. i=1

Remarks. (1) Jo is the maximum number of tasks that can be completed before tbrk. (2) Consider the SPT schedule, for 1 < i < j o and Jo+ 1 < k < n we have (i) Zk > Zi and (ii) Zk > U. (3) For any schedule, the tasks before tbrk and after tfix are scheduled according to SPT. Let A and B denote the set of tasks in the SPT schedule that are scheduled before tbrk and after tfix, respectively, i.e., A={1, 2 . . . . . Jo} and B = { j o +1, ..., n}. Let re be a schedule, re#SPT. Assume that re schedules tasks ix, i2 . . . . . ik~A after tfix and tasks i'l i'2. . . . , i'hr before tbrk. According to Remark 3, we assume that all tasks in re which are scheduled before tbrk and after tfix are scheduled according to SPT.

(A)-CspT(A)>=k( C z,r+U+Zo ).

Lemma 9.

Proof Let re' be a schedule in which all the tasks in A are scheduled before tbrk, the tasks in A - { i l , ..., ik} occurring first and are ordered according to SPT, the tasks in {i, . . . . . ik} next and are ordered according to SPT. Clearly, C~, (A) -

C s p T (A) >

0

(12)

In schedule n, the tasks in A are scheduled in the same order as in 7z' but k

each of the tasks ir starts ~ zir + u + z o time units later in r~ than in n'. Thus,

694

I. Adiri et al.

Summing Eq. (12) and (13) yields Lemma 9.

[]

k

Lemma 10. C s P T ( B ) - C n ( B ) < = h Q ~ = l z i + u + z o ) + ( n - j o - h ) u .

Proof It is easy to calculate that each task i't (where 1 < l<_h) starts dz time units earlier in n than in SPT, where Q=~I

at=

\

i~-1

ih-1

i~-i

j=jo+ 1

j=i]+l

j=i~-l+l

z,+u+zo)+ Z zj+ E

Z

zj.

Since zj < zit for each Jo + 1 < j < i'l, we get

dr<=

zi,+U+Zo + [ ( i ' l - - j o - - l ) + ( i ' 2 - i ' l - - 1 ) + . . . + ( i ' l - - i i - 1 - - 1 ) ] z i l r

All tasks which are scheduled after i't, not including tasks in {i'~+~, ..., i~}, start processing zit time units earlier in n than in SPT. Additionally, all the ( n - j o - h) k tasks in B-{i'~, ..., i~} have a delay of ~ zir time units in n with respect to SPT. r=1 Summing up all of the above we get:

CSPT(B)-C~(B)
zi,+U+Zo)+ ~ (i'l--jo--l)zii l

1=1 h

k

+ ~ (n -- i'z-- h + I) zig - ( n - j o - h) ~ zir /=1

r=l

= h ~ z i + u + Zo) + ( n - j o - h) \i= 1

zi t -

.

(14)

l

Clearly, for the schedule n to be feasible we must have h

E 1=1

k

X z,r<=u.

(15)

r=l

Equations (14) and (15) yield Lemma 10.

[]

Corollary 1. For a schedule ~ v~SPT where tasks before tbrk and after tfix are processed in SPT order, we have that CSPT-- C~ < (n--jo -- 1) u.

Proof Since k > h, it follows immediately from Lemmas 9 and 10. Lemma 11. I f in the SPT schedule n - 1

SPT is an optimal schedule.

[]

tasks are scheduled before tbrk then

695

Single Machine Flow-TimeSchedulingWith a Single Breakdown

Proof Follows directly from Corollary 1. [] Lemma

12 u.

(16)

Proof Remark 1 implies that for any schedule there are at least n - j o tasks which are scheduled after tfix. Remark 2 yields that there are at least n - j o tasks whose processing times are larger than u. Thus the flow time is at least (n -Jo) tfix plus the flow time of n - j o tasks in B. Let n be a schedule such that h tasks in B are processed before tbrk and n - j o - h tasks are processed after tfix. For such a schedule,

C~ > (n -Jo) tfix -~ h(h + 1) u -

(n - J o - h) (n - J o - h + 1) u

2

+

(17)

2

The minimum value of the RHS of (17) is as per (16).

[]

Corollary 2. The relative error of the SPT schedule is Csp T -- Cop T < 1 Rsp T Cop T

=

4

Proof Corollary 1 and Lemma 12 yield (n-jo-

Rsp T <

1) u

(n--jo)tfix+~--~9-~~

.

(18)

u

The RHS of (18) is a monotone decreasing function of n-jo. Lemma 11 implies that n - j o > 2 , and we also have tfix>u. The Corollary follows from (18) by substituting n - j o = 2 and tfix = u. [] Finally, we show that for ~ > 0 there exists an instance I of the problem, such that RsPT(I)>l/(4+~); in other words, for a given tolerance 6 > 0 there exists an instance of the problem where RSPT(I) is within 6 of 1/4. Consider the problem where there are n + 2 tasks with processing times:

zi=~

for i = 1 , 2 , . . . , n

and n-1 Zn+l = Z n + 2 = m - - ~ "

The repair time is zero and tbrk = tfix = m.

n -

696

I. A d i r i et al.

Constructing the SPT schedule, the n tasks with processing time ~- are n-1 scheduled before tbrk and the two tasks with processing time m - - - n 2 e are schedule after tfix. Thus

n(n+ i) e CSPT --

2

//2

3n--1 n ~ e + 5 m.

However, the optimal schedule is obtained by scheduling n - 1 tasks with proe n--1 cessing time ~-~ and one task with processing time m nT--e before tbrk. We have n ( n - 1)e n - 3 CovT=4mq 2n 2 n ~ e. Elementary algebraic manipulations yield 1 - e/m n Rsp T --

n-1 4+mn2m e

n-3 -n -2em

Clearly for a given ~ >0 and n__>1 there exists a constant value m such that Rsvx > 1/(4 + e). This completes the proof of Theorem 3. []