# Optimal Rules for Single Machine Scheduling with Stochastic Breakdowns

Authors: Jinwei Gu; Manzhan Gu; Xingsheng Gu
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

This paper studies the problem of scheduling a set of jobs on a single machine subject to stochastic breakdowns, where jobs have to be restarted if preemptions occur because of breakdowns. The breakdown process of the machine is independent of the jobs processed on the machine. The processing times required to complete the jobs are constants if no breakdown occurs. The machine uptimes are independently and identically distributed (i.i.d.) and are subject to a uniform distribution. It is proved that theLongest Processing Time first (LPT) rule minimizes the expected makespan. For the large-scale problem, it is also showed that the Shortest Processing Time first (SPT) rule is optimal to minimize the expected total completion times of all jobs.


---

## Body

## 1. Introduction

Machine scheduling problems belong to the classic combinational optimization problems. These problems deal with the model where decision maker needs to arrange jobs to process on a limited number of machines or processors. Machine scheduling problems play an important role in manufacturing, parallel computing, or compiler optimization. These problems have been studied since the 1950s and a lot of results have been achieved until now. We refer to the books by Brucker [1] and Pinedo [2] for a general overview of literature in scheduling problems.In the environment of classical scheduling problems, the machine is assumed to be workable continuously until the completion of all jobs. Nevertheless, some unexpected events during production (e.g., equipment damaged, error operation, and instrument breakdown) often occur in manufacturing environment. Therefore, it is very common that a machine breakdown happens during the processing of a job. Moreover, the information about the breakdowns may be uncertain. In the realistic situation, the decision maker has to consider how to utilize the available information to give a more effective scheduling plan in order to increase the output and reduce the cost. In this way, it is necessary and valuable to research the stochastic scheduling problems with random machine breakdowns.According to the impact a machine breakdown exerts to the job being processed, the machine breakdowns could be categorized into two models: preemptive-resume model and preemptive-repeat. In the preemptive-resume model, if a breakdown happens during the processing of a job, the work done prior to the breakdown is not lost, and the job could be resumed when the machine becomes available again. In the preemptive-repeat model, the job has to be reprocessed in its entirety if the machine breakdown occurs before the job is completed.The main purpose of this paper is to study the problem with machine breakdowns of preemptive-repeat model. There are many results on preemptive-resume model. Such as Glazebrook [3], Birge et al. [4], Mittenthal and Raghavachari [5], Cai and Zhou [6, 7], and Qi et al. [8]. Regarding the preemptive-repeat model, many authors have contributed remarkable achievements. Adiri et al. [9, 10] studied the problems with single breakdown; Cai et al. [11–13] studied the problems in which the realizations of processing times for a job between breakdowns are the same. They referred to this model as the case ofwithout resampling. Frostig [14] considered theresampling mechanism in which the repeated processing times of a job are i.i.d. between breakdowns. Khalil and Dimitrov [15] studied the flow time of a job under the preemptive-repeat and preemptive-resume models. Lee and Lin [16] considered the problem where the decision maker can decide whether to activate a maintenance or to leave the machine to run at a slower speed. Kasap et al. [17] studied the uptime distributions to ensure that the LPT rule minimizes the expected makespan. Tang and Zhao [18] designed an optimal algorithm for the problem with early and tardy penalties. Lee and Yu [19] gave algorithms to the problem with the objective to minimize the expected weighted completion times and expected maximum tardiness.However, all the papers reviewed above (except Kasap et al. [17]) carry the implicit assumption that the breakdown process of the machine is dependent on the job it is processing. With this assumption, the problem with machine breakdowns could be converted to the traditional scheduling problem without breakdowns; see papers [11, 12, 18].In this paper, the machine breakdowns are subject to preemptive-repeat model and are independent of job it is processing. The objective is to minimize the expected makespan or expected total completion times of all jobs. For this problem, Adiri et al. [9] firstly studied a special case of a single machine scheduling with only one breakdown, and the machine is assumed to be continuous workable after the breakdown. Subject to this restriction, Adiri et al. concluded that the LPT (SPT) rule minimizes the expected makespan when the distribution function of the uptime is convex (concave). This paper considers the general problem where the downtimes (repairing time) are i.i.d., and the uptimes are independently subject to a common uniform distribution. Under the assumptions above, it is proved that LPT rule is optimal to achieve the minimal expected makespan, and SPT rule minimizes the expected total completion times for large-scale problem, where the number of jobs is large enough.The remainder of the paper is organized as follows. In Section2, the model with stochastic preemptive-repeat breakdowns is formulated. Then, for a given processing order, we present a formulation of the expected completion time of a job. In Section 3, we show that the LPT rule minimizes the expected makespan. Section 4 demonstrates that SPT rule minimizes the expected total completion times for large-scale problems. Finally, some concluding remarks are made in Section 5.


## 2. Formulation of Problem

Suppose there aren jobs J
1
,
J
2
,
…
,
J
n available at time 0 and these jobs are to be processed on a single machine. Denote by a constant p
j the time needed to process job J
j if no breakdown occurs during its processing. Due to the breakdowns, the actual time needed to process job J
j may be more than p
j, and the time may vary in different processing orders. It is assumed that the machine could process one and only one job at a time, and once a job begins to be processed on the machine, it could not be preempted by other jobs (except by machine breakdowns) until its completion.The machine is subject to stochastic breakdowns, and, after each maintenance, the machine will start anew. The breakdown process is characterized by a sequence of positive random vectors{
U
k
,
D
k
}
k
=
1
∞, where U
k
,
D
k are, respectively, the durations of the kth uptime and downtime of the machine. The uptimes and downtimes are defined to be independent of the jobs. If the machine breaks down during the processing of job J
j, the work done on the job will be lost and the job has to be restarted. U
k
(
k
=
1,2
,
…
) are defined to be i.i.d. and follow the uniform distribution with the distribution function F
(
x
) with the support in [
0
,
C
]
(
0
≤
C
≥
∑
i
=
1
n
‍
p
j
). Hence, F
(
x
)
=
x
/
C
,
(
x
≤
C
). D
k
(
k
=
1,2
,
…
) are also i.i.d. with an arbitrary distribution with E
[
D
k
]
=
d
0. The objective functions in this paper are the expected makespan and the expected total completion times. Our work focuses on the scheduling order of all jobs so as to minimize the objective functions.Define a jobs processing orderλ
=
(
J
1
,
J
2
,
…
,
J
n
), and s
j
=
∑
k
=
1
j
‍
p
k
,
(
s
0
=
0
). Given a processing order λ, assume the machine begins to process only the jth, (
j
+
1
)th,
…
,
kth jobs at time zero; then define that C
λ
(
j
,
k
)
(
k
≥
j
) denotes the time to complete the k
-
j
+
1 jobs. So the makespan C
max
⁡
λ
=
C
λ
(
1
,
n
), and the completion time of jth job is C
λ
(
1
,
j
). Let I
A be an indicator variable such that I
A
=
1 if event A occurs; otherwise I
A
=
0. Based on the notations defined above, the expected completion time of job J
j could be expressed as
(1)
E
[
C
λ
(
1
,
j
)
]
=
E
[
∑
k
=
1
j
‍
C
λ
(
1
,
j
)
I
{
s
k
-
1
≤
U
1
<
s
k
}
+
C
λ
(
1
,
j
)
I
{
U
1
≥
s
j
}
]
=
∑
k
=
1
j
‍
E
[
C
λ
(
1
,
j
)
I
{
s
k
-
1
≤
U
1
<
s
k
}
]
+
E
[
C
λ
(
1
,
j
)
I
{
U
1
≥
s
j
}
]
=
∑
k
=
1
j
‍
Pr
⁡
(
s
k
-
1
≤
U
1
<
s
k
)
iiiiiii
×
E
[
C
λ
(
1
,
j
)
∣
s
k
-
1
≤
U
1
<
s
k
]
+
Pr
⁡
(
U
1
≥
s
j
)
E
[
C
λ
(
1
,
j
)
∣
U
1
≥
s
j
]
=
∑
k
=
1
j
‍
Pr
⁡
(
s
k
-
1
≤
U
1
<
s
k
)
i
i
i
i
i
i
i
i
i
×
{
+
d
0
+
E
[
C
λ
(
k
,
j
)
]
E
[
U
1
∣
s
k
-
1
≤
U
1
<
s
k
]
iiiiiiiiiiiiiii
+
d
0
+
E
[
C
λ
(
k
,
j
)
]
}
+
Pr
⁡
(
U
1
≥
s
j
)
s
j
=
∑
k
=
1
j
‍
p
k
C
[
(
s
k
-
1
+
p
k
2
)
+
d
0
+
E
[
C
λ
(
k
,
j
)
]
]
iiiiiiiii
+
C
-
s
j
C
s
j
,
which implies
(2)
E
[
C
λ
(
1
,
j
)
]
=
1
C
-
p
1
{
∑
k
=
2
j
‍
p
k
[
s
k
-
1
+
p
k
2
+
d
0
+
E
[
C
λ
(
k
,
j
)
]
]
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
+
(
C
-
s
j
)
s
j
+
p
1
2
2
+
d
0
p
1
∑
k
=
2
j
‍
p
k
}
.
Therefore, we obtain the expected makespan
(3)
E
[
C
max
⁡
λ
]
=
E
[
C
λ
(
1
,
n
)
]
=
1
C
-
p
1
{
∑
k
=
2
n
‍
p
k
[
s
k
-
1
+
p
k
2
+
d
0
+
E
[
C
λ
(
k
,
n
)
]
]
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
+
(
C
-
s
n
)
s
n
+
p
1
2
2
+
d
0
p
1
∑
k
=
2
n
‍
}
.


## 3. LPT Minimizes Expected Makespan

In this section, we will prove the optimality of LPT to minimize the expected value of makespan. Define the processing orderλ
k
=
(
J
1
,
…
J
k
-
1
,
J
k
+
1
,
J
k
,
J
k
+
2
…
,
J
n
)  (
1
≤
k
≤
n
-
1
), which is obtained by interchanging the processing order of the two jobs J
k
,
J
k
+
1 in λ. The following lemma shows that the processing of first two jobs is subject to LPT rule.Lemma 1.
Consider the processing orderλ
=
(
J
1
,
J
2
,
…
,
J
n
). If the uptimes are i.i.d and uniformly distributed and p
1
<
p
2, then the expected makespan can be reduced by interchanging the first two jobs J
1
,
J
2; that is,
(4)
E
[
C
λ
1
(
1
,
n
)
]
-
E
[
C
λ
(
1
,
n
)
]
<
0
.Proof.
According to the definition ofC
λ
(
j
,
k
) and by (3), it is obtained that
(5)
E
[
C
λ
(
2
,
n
)
]
=
1
C
-
p
2
{
∑
k
=
3
n
‍
p
k
[
(
s
k
-
1
-
p
1
)
+
p
k
2
+
d
0
+
E
[
C
λ
(
k
,
n
)
]
]
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
+
[
C
-
(
s
n
-
p
1
)
]
(
s
n
-
p
1
)
+
p
2
2
2
+
d
0
p
2
∑
k
=
3
n
‍
}
.
By replacing (5) in (3),
(6)
E
[
C
λ
(
1
,
n
)
]
=
1
C
-
p
1
∑
k
=
3
n
‍
p
k
(
s
k
-
1
+
p
k
2
+
d
0
+
E
[
C
λ
(
k
,
n
)
]
)
+
1
C
-
p
1
[
(
C
-
s
n
)
s
n
+
p
1
2
2
+
d
0
p
1
]
+
p
2
C
-
p
1
(
s
1
+
p
2
2
+
d
0
)
+
p
2
(
C
-
p
2
)
(
C
-
p
1
)
×
[
∑
k
=
3
n
‍
p
k
(
(
s
k
-
1
-
p
1
)
+
p
k
2
+
d
0
+
E
[
C
λ
(
k
,
n
)
]
)
IIIIIIII
+
(
C
-
(
s
n
-
p
1
)
)
(
s
n
-
p
1
)
+
p
2
2
2
+
d
0
p
2
∑
k
=
3
n
‍
]
.
That is,
(7)
E
[
C
λ
(
1
,
n
)
]
=
C
(
C
-
p
1
)
(
C
-
p
2
)
×
∑
k
=
3
n
‍
p
k
(
s
k
-
1
+
p
k
2
+
d
0
+
E
[
C
λ
(
k
,
n
)
]
)
-
p
1
p
2
(
C
-
p
1
)
(
C
-
p
2
)
∑
k
=
3
n
‍
p
k
+
1
(
C
-
p
1
)
(
C
-
p
2
)
×
(
+
2
p
1
p
2
s
n
+
C
2
s
n
-
C
s
n
2
+
C
p
1
2
2
+
C
p
2
2
2
+
C
d
0
p
1
+
C
d
0
p
2
-
d
0
p
1
p
2
-
p
1
p
2
2
-
3
p
1
2
p
2
2
)
.
By the same method, we could get the expression of E
[
C
λ
1
(
1
,
n
)
]. Since
(8)
E
[
C
λ
1
(
k
,
n
)
]
=
E
[
C
λ
(
k
,
n
)
]
,
for
k
=
3,4
,
…
,
n
,
we obtain
(9)
E
[
C
λ
1
(
1
,
n
)
]
-
E
[
C
λ
(
1
,
n
)
]
=
1
(
C
-
p
1
)
(
C
-
p
2
)
×
[
(
-
p
2
p
1
2
-
3
p
2
2
p
1
2
)
-
(
-
p
1
p
2
2
-
3
p
1
2
p
2
2
)
]
=
p
1
p
2
2
(
C
-
p
1
)
(
C
-
p
2
)
(
p
1
-
p
2
)
.
The conclusion follows by p
1
<
p
2.Corollary 2.
Assume the uptimes are i.i.d and uniformly distributed. Ifp
k
<
p
k
+
1, then
(10)
E
[
C
λ
k
(
k
,
n
)
]
-
E
[
C
λ
(
k
,
n
)
]
<
0
,
f
o
r
1
≤
k
≤
n
-
1
.Proof.
The proof is the same as that in Lemma1.Next we will give another expression forE
[
C
λ
k
(
k
,
n
)
]
-
E
[
C
λ
(
k
,
n
)
]. Assume the machine begins to process jobs J
k
,
J
k
+
1
,
…
,
J
n at time zero and p
k
<
p
k
+
1. Let k
1
=
min
⁡
{
i
∣
U
i
≥
p
k
}; then we consider the following three cases.Case  1 (
p
k
≤
U
k
1
<
p
k
+
1
). With the possibility (
F
(
p
k
+
1
)
-
F
(
p
k
)
)
/
(
1
-
F
(
p
k
)
), in this case, we have
(11)
E
[
C
λ
k
(
k
,
n
)
]
-
E
[
C
λ
(
k
,
n
)
]
=
E
[
C
λ
k
(
k
,
n
)
]
-
E
[
C
λ
(
k
+
1
,
n
)
]
≐
Δ
1
>
0
.
Case  2 (
p
k
+
1
≤
U
k
1
<
p
k
+
p
k
+
1
). With the possibility (
F
(
p
k
+
1
+
p
k
)
-
F
(
p
k
+
1
)
)
/
(
1
-
F
(
p
k
)
), we have
(12)
E
[
C
λ
k
(
k
,
n
)
]
-
E
[
C
λ
(
k
,
n
)
]
=
E
[
C
λ
k
(
k
+
1
,
n
)
]
-
E
[
C
λ
(
k
+
1
,
n
)
]
≐
Δ
2
<
0
.
Case  3 (
U
k
1
≥
p
k
+
p
k
+
1
). We have
(13)
E
[
C
λ
k
(
k
,
n
)
]
-
E
[
C
λ
(
k
,
n
)
]
=
0
.
From the three cases above, we get
(14)
E
[
C
λ
k
(
k
,
n
)
]
-
E
[
C
λ
(
k
,
n
)
]
=
F
(
p
k
+
1
)
-
F
(
p
k
)
1
-
F
(
p
k
)
Δ
1
+
F
(
p
k
+
p
k
+
1
)
-
F
(
p
k
+
1
)
1
-
F
(
p
k
)
Δ
2
.
Known from Corollary 2, we know E
[
C
λ
k
(
k
,
n
)
]
-
E
[
C
λ
(
k
,
n
)
]
<
0. Hence
(15)
F
(
p
k
+
1
)
-
F
(
p
k
)
1
-
F
(
p
k
)
Δ
1
+
F
(
p
k
+
p
k
+
1
)
-
F
(
p
k
+
1
)
1
-
F
(
p
k
)
Δ
2
<
0
.
That is,
(16)
Δ
1
Δ
2
>
p
k
p
k
-
p
k
+
1
.
The following lemma shows that the processing of any two consecutive jobs is subject to LPT rule.Lemma 3.
Assume the uptimes are i.i.d and uniformly distributed. Ifp
k
<
p
k
+
1, then
(17)
E
[
C
λ
k
(
1
,
n
)
]
-
E
[
C
λ
(
1
,
n
)
]
<
0
,
f
o
r
1
<
k
≤
n
-
1
.Proof.
LetU
* be the uptime where the job J
k
-
1 is completed, and assume the machine has been continuously processing jobs for t
* time units when J
k
-
1 is finished at time t
0; that is, we have U
*
>
t
*. Let X
=
U
*
-
t
*, and let G
(
x
) be the distribution function of X. We have
(18)
G
(
x
)
=
Pr
⁡
(
X
≤
x
)
=
Pr
⁡
(
U
*
-
t
*
≤
x
∣
U
*
>
t
*
)
=
x
C
-
t
*
,
x
∈
(
0
,
C
-
t
*
]
,
which implies that X is uniformly distributed for any given t
*. According to the definition of C, we know C
-
t
*
≥
∑
l
=
k
n
p
l. We now consider four possibilities depending on the value X obtains.
Case  1 (
X
<
p
k
). We have
(19)
E
[
C
λ
k
(
1
,
n
)
]
-
E
[
C
λ
(
1
,
n
)
]
=
E
[
C
λ
k
(
k
,
n
)
]
-
E
[
C
λ
(
k
,
n
)
]
.
Case  2 (
p
k
≤
X
<
p
k
+
1
). We have
(20)
E
[
C
λ
k
(
1
,
n
)
]
-
E
[
C
λ
(
1
,
n
)
]
=
E
[
C
λ
k
(
k
,
n
)
]
-
E
[
C
λ
(
k
+
1
,
n
)
]
.
Case  3 (
p
k
+
1
≤
X
<
p
k
+
p
k
+
1
). We have
(21)
E
[
C
λ
k
(
1
,
n
)
]
-
E
[
C
λ
(
1
,
n
)
]
=
E
[
C
λ
k
(
k
+
1
,
n
)
]
-
E
[
C
λ
(
k
+
1
,
n
)
]
.
Case  4 (
X
≥
p
k
+
p
k
+
1
). We have
(22)
E
[
C
λ
k
(
1
,
n
)
]
-
E
[
C
λ
(
1
,
n
)
]
=
0
.
Hence,
(23)
E
[
C
λ
k
(
1
,
n
)
]
-
E
[
C
λ
(
1
,
n
)
]
=
G
(
p
k
)
[
E
[
C
λ
k
(
k
,
n
)
]
-
E
[
C
λ
(
k
,
n
)
]
]
+
[
G
(
p
k
+
1
)
-
G
(
p
k
)
]
[
E
[
C
λ
k
(
k
,
n
)
]
-
E
[
C
λ
(
k
+
1
,
n
)
]
]
+
[
G
(
p
k
+
p
k
+
1
)
-
G
(
p
k
+
1
)
]
×
[
E
[
C
λ
k
(
k
+
1
,
n
)
]
-
E
[
C
λ
(
k
+
1
,
n
)
]
]
.
Because
(24)
E
[
C
λ
k
(
k
,
n
)
]
-
E
[
C
λ
(
k
+
1
,
n
)
]
=
Δ
1
>
0
,
E
[
C
λ
k
(
k
+
1
,
n
)
]
-
E
[
C
λ
(
k
+
1
,
n
)
]
=
Δ
2
<
0
,
E
[
C
λ
k
(
k
,
n
)
]
-
E
[
C
λ
(
k
,
n
)
]
=
F
(
p
k
+
1
)
-
F
(
p
k
)
1
-
F
(
p
k
)
Δ
1
+
F
(
p
k
+
p
k
+
1
)
-
F
(
p
k
+
1
)
1
-
F
(
p
k
)
Δ
2
.
By replacing (24) in (23), we obtain
(25)
E
[
C
λ
k
(
1
,
n
)
]
-
E
[
C
λ
(
1
,
n
)
]
=
p
k
C
-
t
*
[
F
(
p
k
+
1
)
-
F
(
p
k
)
F
¯
(
p
k
)
Δ
1
ii
+
F
(
p
k
+
p
k
+
1
)
-
F
(
p
k
+
1
)
F
¯
(
p
k
)
Δ
2
]
+
p
k
+
1
-
p
k
C
-
t
*
Δ
1
+
p
k
C
-
t
*
Δ
2
=
C
(
p
k
+
1
-
p
k
)
Δ
2
(
C
-
t
*
)
(
C
-
p
k
)
[
Δ
1
Δ
2
-
p
k
p
k
-
p
k
+
1
]
.
By (16) and Δ
2
<
0, the conclusion in this lemma holds.Based on Lemmas1 and 3, the following theorem is immediate.Theorem 4.
Assume the uptimes are i.i.d and uniformly distributed with support in[
0
,
C
], where C
≥
∑
j
=
1
n
p
j; then the LPT rule is optimal to minimize the expected makespan.


## 4. SPT Minimizes Expected Total Completion Times

This section considers the single machine problem to minimize the expected value of total completion times, that is,E
[
∑
j
=
1
n
C
λ
(
1
,
j
)
]. Assume there exist two constants p
_
,
p
¯ such that p
_
≤
p
j
≤
p
¯ for j
=
1,2
,
…
,
n; that is, the processing times of all jobs are uniformly bounded. For a given processing order λ, if machine begins to process the jth, (
j
+
1
)th,
…
,
kth jobs at time zero, define that π
λ
(
j
,
k
) denotes the sum of the completion times of the k
-
j
+
1 jobs. So we have
(26)
E
[
∑
j
=
1
n
‍
C
λ
(
1
,
j
)
]
=
E
[
π
λ
(
1
,
n
)
]
.
In this section, we focus on the large-scale scheduling problems; that is, the number of jobs n is large enough. With the assumption, the SPT rule will be proved to be optimal.Lemma 5.
Assume the uptimes are i.i.d and uniformly distributed. Ifp
1
>
p
2, then
(27)
E
[
π
λ
1
(
1
,
n
)
]
-
E
[
π
λ
(
1
,
n
)
]
<
0
,
for large number n.Proof.
Firstly we have(28)
E
[
π
λ
1
(
1
,
n
)
]
-
E
[
π
λ
(
1
,
n
)
]
=
∑
k
=
1
n
‍
[
E
[
C
λ
1
(
1
,
k
)
]
-
E
[
C
λ
(
1
,
k
)
]
]
=
E
[
C
λ
1
(
1,1
)
]
-
E
[
C
λ
(
1,1
)
]
+
∑
k
=
2
n
‍
[
E
[
C
λ
1
(
1
,
k
)
]
-
E
[
C
λ
(
1
,
k
)
]
]
.
By (3), we could get the expressions for E
[
C
λ
1
(
1,1
)
] and E
[
C
λ
(
1,1
)
]. Hence we obtain
(29)
E
[
C
λ
1
(
1,1
)
]
-
E
[
C
λ
(
1,1
)
]
=
[
p
2
+
1
C
-
p
2
(
p
2
2
2
+
d
0
p
2
)
]
-
[
p
1
+
1
C
-
p
1
(
p
1
2
2
+
d
0
p
1
)
]
=
(
p
2
-
p
1
)
(
C
-
p
1
)
(
C
-
p
2
)
[
C
2
-
C
2
(
p
1
+
p
2
)
+
p
1
p
2
2
+
d
0
C
]
.
Known from (9), we have
(30)
E
[
C
λ
1
(
1
,
k
)
]
-
E
[
C
λ
(
1
,
k
)
]
=
(
p
2
-
p
1
)
p
1
p
2
2
(
C
-
p
2
)
(
C
-
p
1
)
,
for
k
=
2,3
,
…
,
n
.
Therefore, we have
(31)
E
[
π
λ
1
(
1
,
n
)
]
-
E
[
π
λ
(
1
,
n
)
]
=
(
p
2
-
p
1
)
(
C
-
p
1
)
(
C
-
p
2
)
[
C
2
-
C
2
(
p
1
+
p
2
)
+
p
1
p
2
2
+
d
0
C
]
+
(
n
-
1
)
(
p
2
-
p
1
)
p
1
p
2
2
(
C
-
p
2
)
(
C
-
p
1
)
=
(
p
2
-
p
1
)
2
(
C
-
p
2
)
(
C
-
p
1
)
[
2
C
2
-
C
(
p
1
+
p
2
-
2
d
0
)
-
(
n
-
2
)
p
1
p
2
2
C
2
-
C
(
p
1
+
p
2
-
2
d
0
)
]
.
Note C
≥
∑
j
=
1
n
p
j
≥
p
_
n, so we have C
2
=
Ω
(
n
2
) and
(32)
E
[
π
λ
1
(
1
,
n
)
-
π
λ
(
1
,
n
)
]
⟶
p
2
-
p
1
,
(
n
⟶
∞
)
.
Since p
1
>
p
2, we obtain
(33)
E
[
π
λ
1
(
1
,
n
)
]
-
E
[
π
λ
(
1
,
n
)
]
<
0
as long as n is large enough.By Lemma5, the corollary below follows immediately.Corollary 6.
Assume the uptimes are i.i.d and uniformly distributed. Ifp
k
>
p
k
+
1, then
(34)
E
[
π
λ
k
(
k
,
n
)
]
-
E
[
π
λ
(
k
,
n
)
]
<
0
,
f
o
r
1
≤
k
≤
n
-
1
,
as long as n is large enough. Also, we have
(35)
E
[
π
λ
k
(
k
,
n
)
]
-
E
[
π
λ
(
k
,
n
)
]
=
(
p
k
+
1
-
p
k
)
2
(
C
-
p
k
+
1
)
(
C
-
p
k
)
×
[
2
C
2
-
C
(
p
k
+
p
k
+
1
-
2
d
0
)
i
i
-
(
n
-
k
-
1
)
p
k
p
k
+
1
2
C
2
-
C
(
p
k
+
p
k
+
1
-
2
d
0
)
]
⟶
p
k
+
1
-
p
k
,
(
n
⟶
∞
)
.Proof.
The proof is the same as that in Lemma5.In order to prove the main conclusion in this section, we will give another expression forE
[
π
λ
k
(
k
,
n
)
]
-
E
[
π
λ
(
k
,
n
)
]. Assume the machine begins to process jobs J
k
,
J
k
+
1
,
…
,
J
n at time zero and p
k
>
p
k
+
1. Let k
2
=
min
⁡
{
i
∣
U
i
≥
p
k
+
1
}, and ρ
=
∑
l
=
1
k
2
-
1
(
U
l
+
D
l
) (ρ
=
0 for k
2
=
1). We consider the following three cases.Case  1 (
p
k
+
1
≤
U
k
2
<
p
k
). In this case, we have
(36)
E
[
C
λ
k
(
k
,
k
)
∣
p
k
+
1
≤
U
k
2
<
p
k
]
=
ρ
+
p
k
+
1
,
E
[
C
λ
k
(
k
,
l
)
∣
p
k
+
1
≤
U
k
2
<
p
k
]
=
ρ
+
E
[
U
k
2
∣
p
k
+
1
≤
U
k
2
<
p
k
]
111
+
d
0
+
E
[
C
λ
k
(
k
,
l
)
]
,
l
=
k
+
1
,
…
,
n
,
E
[
C
λ
(
k
,
l
)
∣
p
k
+
1
≤
U
k
2
<
p
k
]
=
ρ
+
E
[
U
k
2
∣
p
k
+
1
≤
U
k
2
<
p
k
]
111
+
d
0
+
E
[
C
λ
(
k
,
l
)
]
,
l
=
k
,
…
,
n
.
We obtain
(37)
E
[
π
λ
k
(
k
,
n
)
-
π
λ
(
k
,
n
)
∣
p
k
+
1
≤
U
k
2
<
p
k
]
=
p
k
+
1
-
p
k
2
-
d
0
+
E
[
π
λ
k
(
k
+
1
,
n
)
]
-
E
[
π
λ
(
k
,
n
)
]
≐
δ
1
.
Case  2 (
p
k
≤
U
k
2
<
p
k
+
p
k
+
1
). In this case, we have
(38)
E
[
C
λ
k
(
k
,
k
)
∣
p
k
≤
U
k
2
<
p
k
+
p
k
+
1
]
=
ρ
+
p
k
+
1
,
E
[
C
λ
k
(
k
,
l
)
∣
p
k
≤
U
k
2
<
p
k
+
p
k
+
1
]
=
ρ
+
E
[
U
k
2
∣
p
k
≤
U
k
2
<
p
k
+
p
k
+
1
]
+
d
0
+
E
[
C
λ
k
(
k
,
l
)
]
,
l
=
k
+
1
,
…
,
n
,
E
[
C
λ
(
k
,
k
)
∣
p
k
≤
U
k
2
<
p
k
+
p
k
+
1
]
=
ρ
+
p
k
,
E
[
C
λ
(
k
,
l
)
∣
p
k
≤
U
k
2
<
p
k
+
p
k
+
1
]
=
ρ
+
E
[
U
k
2
∣
p
k
+
1
≤
U
k
2
<
p
k
]
+
d
0
+
E
[
C
λ
(
k
,
l
)
]
,
l
=
k
+
1
,
…
,
n
.
Therefore, we get
(39)
E
[
π
λ
k
(
k
,
n
)
-
π
λ
(
k
,
n
)
∣
p
k
≤
U
k
2
<
p
k
+
p
k
+
1
]
=
p
k
+
1
-
p
k
+
E
[
π
λ
k
(
k
+
1
,
n
)
]
-
E
[
π
λ
(
k
+
1
,
n
)
]
≐
δ
2
.
Case  3 (
U
k
2
≥
p
k
+
p
k
+
1
). We have
(40)
E
[
C
λ
k
(
k
,
k
)
∣
U
k
2
≥
p
k
+
p
k
+
1
]
=
ρ
+
p
k
+
1
,
E
[
C
λ
(
k
,
k
)
∣
U
k
2
≥
p
k
+
p
k
+
1
]
=
ρ
+
p
k
,
E
[
C
λ
k
(
k
,
l
)
∣
U
k
2
≥
p
k
+
p
k
+
1
]
=
E
[
C
λ
(
k
,
l
)
∣
U
k
2
≥
p
k
+
p
k
+
1
]
,
l
=
k
+
1
,
…
,
n
.
And we obtain
(41)
E
[
π
λ
k
(
k
,
n
)
-
π
λ
(
k
,
n
)
∣
U
k
2
≥
p
k
+
p
k
+
1
]
=
p
k
+
1
-
p
k
≐
δ
3
<
0
.
Based on the three cases above, we have
(42)
E
[
π
λ
k
(
k
,
n
)
-
π
λ
(
k
,
n
)
]
=
Pr
⁡
(
p
k
+
1
≤
U
k
2
<
p
k
∣
U
k
2
≥
p
k
+
1
)
δ
1
+
Pr
⁡
(
p
k
≤
U
k
2
<
p
k
+
p
k
+
1
∣
U
k
2
≥
p
k
+
1
)
δ
2
+
Pr
⁡
(
U
k
2
>
p
k
+
p
k
+
1
∣
U
k
2
≥
p
k
+
1
)
δ
3
=
1
C
-
p
k
+
1
[
(
p
k
-
p
k
+
1
)
δ
1
+
p
k
+
1
δ
2
i
i
i
i
i
i
i
i
i
i
i
i
i
i
+
(
C
-
p
k
-
p
k
+
1
)
δ
3
]
<
0
,
for large number n. The inequality holds by the conclusion in Corollary 6.Lemma 7.
Assume the uptimes are i.i.d and uniformly distributed. Ifp
k
>
p
k
+
1 (1
<
k
<
n), then one has
(43)
E
[
π
λ
k
(
1
,
n
)
]
-
E
[
π
λ
(
1
,
n
)
]
<
0
,
for large number n.Proof.
We letU
* be the uptime where the job J
k
-
1 is completed and let D
* be the downtime after U
*. Assume the machine has been continuously processing for t
* time units when J
k
-
1 is finished at time t
0; that is, we have U
*
>
t
*. Let X
=
U
*
-
t
*, and let G
(
x
) be the distribution function of X. Here, we have
(44)
π
λ
k
(
1
,
n
)
-
π
λ
(
1
,
n
)
=
∑
l
=
k
n
‍
C
λ
k
(
1
,
l
)
-
∑
l
=
k
n
‍
C
λ
(
1
,
l
)
.
Case  1 (
X
<
p
k
+
1
). In this case, we have
(45)
E
[
C
λ
k
(
1
,
l
)
∣
X
<
p
k
+
1
]
=
t
0
+
E
[
X
∣
X
<
p
k
+
1
]
+
d
0
+
E
[
C
λ
k
(
k
,
l
)
]
,
E
[
C
λ
(
1
,
l
)
∣
X
<
p
k
+
1
]
h
=
t
0
+
E
[
X
∣
X
<
p
k
+
1
]
+
d
0
+
E
[
C
λ
(
k
,
l
)
]
,
g
g
g
g
g
g
g
g
i
g
g
g
g
g
g
g
j
k
g
g
g
g
g
g
g
g
l
=
k
,
…
,
n
.
Therefore, we obtain
(46)
E
[
π
λ
k
(
1
,
n
)
-
π
λ
(
1
,
n
)
∣
X
<
p
k
+
1
]
=
E
[
π
λ
k
(
k
,
n
)
]
-
E
[
π
λ
(
k
,
n
)
]
.
Case  2 (
p
k
+
1
≤
X
<
p
k
). The case is similar to the case p
k
+
1
≤
U
k
2
<
p
k. So we get
(47)
E
[
π
λ
k
(
1
,
n
)
-
π
λ
(
1
,
n
)
∣
p
k
+
1
≤
X
<
p
k
]
=
p
k
+
1
-
p
k
2
-
d
0
+
E
[
π
λ
k
(
k
+
1
,
n
)
]
-
E
[
π
λ
(
k
,
n
)
]
=
δ
1
.
Case  3 (
p
k
≤
X
<
p
k
+
p
k
+
1
). The case is similar to the case p
k
≤
U
k
2
<
p
k
+
p
k
+
1. We have
(48)
E
[
π
λ
k
(
1
,
n
)
-
π
λ
(
1
,
n
)
∣
p
k
≤
X
<
p
k
+
p
k
+
1
]
=
p
k
+
1
-
p
k
+
E
[
π
λ
k
(
k
+
1
,
n
)
]
-
E
[
π
λ
(
k
+
1
,
n
)
]
=
δ
2
.
Case  4 (
X
≥
p
k
+
p
k
+
1
). The case is similar to the case U
k
2
≥
p
k
+
p
k
+
1. We obtain
(49)
E
[
π
λ
k
(
1
,
n
)
-
π
λ
(
1
,
n
)
∣
X
≥
p
k
+
p
k
+
1
]
=
p
k
+
1
-
p
k
=
δ
3
.
Based on the four cases above, we have
(50)
E
[
π
λ
k
(
1
,
n
)
-
π
λ
(
1
,
n
)
∣
t
*
]
=
Pr
⁡
(
X
<
p
k
+
1
)
E
[
π
λ
k
(
1
,
n
)
-
π
λ
(
1
,
n
)
∣
X
<
p
k
+
1
,
t
*
]
+
Pr
⁡
(
p
k
+
1
≤
X
<
p
k
)
×
E
[
π
λ
k
(
1
,
n
)
-
π
λ
(
1
,
n
)
∣
p
k
+
1
≤
X
<
p
k
,
t
*
]
+
Pr
⁡
(
p
k
≤
X
<
p
k
+
p
k
+
1
)
×
E
[
π
λ
k
(
1
,
n
)
-
π
λ
(
1
,
n
)
∣
p
k
≤
X
<
p
k
+
p
k
+
1
,
t
*
]
+
Pr
⁡
(
X
>
p
k
+
p
k
+
1
)
×
E
[
π
λ
k
(
1
,
n
)
-
π
λ
(
1
,
n
)
∣
X
>
p
k
+
p
k
+
1
,
t
*
]
=
p
k
+
1
C
-
t
*
1
C
-
p
k
+
1
×
[
(
p
k
-
p
k
+
1
)
δ
1
+
p
k
+
1
δ
2
+
(
C
-
p
k
-
p
k
+
1
)
δ
3
]
+
p
k
-
p
k
+
1
C
-
t
*
δ
1
+
p
k
+
1
C
-
t
*
δ
2
+
C
-
t
*
-
p
k
-
p
k
+
1
C
-
t
*
δ
3
=
C
C
-
t
*
1
C
-
p
k
+
1
×
[
(
p
k
-
p
k
+
1
)
δ
1
+
p
k
+
1
δ
2
+
(
C
-
p
k
-
p
k
+
1
)
δ
3
]
+
-
t
*
δ
3
(
C
-
t
*
)
=
C
C
-
t
*
E
[
π
λ
k
(
k
,
n
)
-
π
λ
(
k
,
n
)
]
+
-
t
*
δ
3
(
C
-
t
*
)
=
C
C
-
t
*
[
E
[
π
λ
k
(
k
,
n
)
-
π
λ
(
k
,
n
)
]
-
δ
3
]
+
δ
3
.
By (35), we have
(51)
E
[
π
λ
k
(
1
,
n
)
-
π
λ
(
1
,
n
)
∣
t
*
]
=
C
C
-
t
*
[
1
2
(
C
-
p
k
+
1
)
(
C
-
p
k
)
11111111
i
i
×
(
2
C
2
-
C
(
p
k
+
p
k
+
1
-
2
d
0
)
11111111
iiiiiii
-
(
n
-
k
-
1
)
p
k
p
k
+
1
2
C
2
-
C
(
p
k
+
p
k
+
1
-
2
d
0
)
)
-
1
1
2
(
C
-
p
k
+
1
)
(
C
-
p
k
)
]
·
δ
3
+
δ
3
=
C
C
-
t
*
×
C
(
p
k
+
p
k
+
1
)
+
2
C
d
0
-
(
n
-
k
+
1
)
p
k
p
k
+
1
2
(
C
-
p
k
+
1
)
(
C
-
p
k
)
·
δ
3
+
δ
3
.
We discuss the following cases..
Case  1 (
(
p
¯
)
2
-
2
(
p
_
)
2
≤
0
). Because k
>
1, we have
(52)
k
>
(
p
¯
)
2
-
2
(
p
_
)
2
(
p
¯
)
2
·
n
+
1
.
That is,
(53)
2
(
p
_
)
2
n
-
(
p
¯
)
2
n
+
k
(
p
¯
)
2
-
(
p
¯
)
2
>
0
.
So we obtain
(54)
C
(
p
k
+
p
k
+
1
)
+
2
C
d
0
-
(
n
-
k
+
1
)
p
k
p
k
+
1
≥
2
(
p
_
)
2
·
n
-
(
p
¯
)
2
·
n
+
k
(
p
¯
)
2
-
(
p
¯
)
2
>
0
.
Therefore, in this case we obtain
(55)
E
[
π
λ
k
(
1
,
n
)
-
π
λ
(
1
,
n
)
∣
t
*
]
≤
δ
3
<
0
.
That is,
(56)
E
[
π
λ
k
(
1
,
n
)
-
π
λ
(
1
,
n
)
]
=
E
[
E
[
π
λ
k
(
1
,
n
)
-
π
λ
(
1
,
n
)
∣
t
*
]
]
≤
δ
3
<
0
.
Case  2 (
(
p
¯
)
2
-
2
(
p
_
)
2
>
0
). In this case, we define a
≐
(
(
p
¯
)
2
-
2
(
p
_
)
2
)
/
(
p
¯
)
2, and 0
<
a
<
1. Next two cases are discussed for the value k obtains.
Case  2.1 (
k
>
a
·
n
+
1
). In this case, we have
(57)
k
(
p
¯
)
2
>
(
p
¯
)
2
+
[
(
p
¯
)
2
-
2
(
p
_
)
2
]
·
n
.
That is,
(58)
2
(
p
_
)
2
·
n
-
(
p
¯
)
2
·
n
+
k
(
p
¯
)
2
-
(
p
¯
)
2
>
0
.
Known from Case 1 above, we obtain
(59)
E
[
π
λ
k
(
1
,
n
)
-
π
λ
(
1
,
n
)
]
≤
δ
3
<
0
.
Case  2.2 (
k
≤
a
·
n
+
1
). According to the definition of t
*, we have t
*
≤
s
k
-
1, so
(60)
0
<
C
C
-
t
*
≤
C
C
-
s
k
-
1
=
1
+
s
k
-
1
C
-
s
k
-
1
<
1
+
k
·
p
¯
p
k
+
p
k
+
1
+
⋯
+
p
n
<
1
+
k
n
-
k
·
p
¯
p
_
≤
1
+
a
n
+
1
n
-
a
n
-
1
·
p
¯
p
_
=
1
+
a
+
1
/
n
1
-
a
-
1
/
n
·
p
¯
p
_
.
Note that there exists a number N such that 1
/
n
≤
(
1
-
a
)
/
2
,
∀
n
>
N, so we get
(61)
C
C
-
t
*
<
1
+
1
+
a
1
-
a
·
p
¯
p
_
for all n
>
N. Therefore,
(62)
E
[
π
λ
k
(
1
,
n
)
-
π
λ
(
1
,
n
)
∣
t
*
]
=
C
C
-
t
*
[
E
[
π
λ
k
(
k
,
n
)
-
π
λ
(
k
,
n
)
]
-
δ
3
]
+
δ
3
≤
[
1
+
1
+
a
1
-
a
·
p
¯
p
_
]
[
E
[
π
λ
k
(
k
,
n
)
-
π
λ
(
k
,
n
)
]
-
δ
3
]
+
δ
3
for all n
>
N. So we obtain
(63)
E
[
π
λ
k
(
1
,
n
)
-
π
λ
(
1
,
n
)
]
=
E
[
E
[
π
λ
k
(
1
,
n
)
-
π
λ
(
1
,
n
)
∣
t
*
]
]
≤
[
1
+
1
+
a
1
-
a
·
p
¯
p
_
]
{
E
[
π
λ
k
(
k
,
n
)
-
π
λ
(
k
,
n
)
]
-
δ
3
}
+
δ
3
⟶
δ
3
<
0
,
(
n
⟶
∞
)
.
Either (
p
¯
)
2
-
2
(
p
_
)
2
>
0 or not, we always have
(64)
E
[
π
λ
k
(
1
,
n
)
-
π
λ
(
1
,
n
)
]
<
0
for large number n.
Based on Lemmas5 and 7, the following theorem is immediate.Theorem 8.
Assume the uptimes are i.i.d. and uniformly distributed with support[
0
,
C
], where C
≥
∑
i
=
1
n
‍
p
i; then the SPT rule is optimal to minimize the expected value of total completion times if the number of jobs n is large enough.


## 5. Concluding Remarks

The stochastic scheduling problem on a single machine with random breakdowns has been investigated in this paper. We consider the situation where the uptimes are uniformly distributed and i.i.d; the downtimes are also assumed to be i.i.d and follow an arbitrary distribution. The machine breakdowns are defined to be independent of the job it is processing. Under the assumptions above, we prove that(
1
) the LPT rule could achieve the minimal expected makespan; (
2
) the SPT rule is optimal to minimize the expected value of total completion times for large scale problems. For the scheduling with stochastic breakdowns independent of job it is processing, the result obtained in this paper is the foundation in this area.Some problems may be considered for the future research: (a) whether optimal rule exists when the uptimes are subject to other probability distributions; (b) problems with other objective functions are worth investigation; (c) the multimachine version will also be an interesting but difficult problem in the future.



---

*Source: 260415-2014-09-29.xml*