# Online Scheduling on a Single Machine with Grouped Processing Times

Authors: Qijia Liu; Long Wan; Lijun Wei
Journal: Discrete Dynamics in Nature and Society
 (2015)

---

## Abstract

We consider the online scheduling problem on a single machine with the assumption that all jobs have their processing times in[
p
,
(
1
+
α
)
p
], where p
>
0 and α
=
(
5
-
1
)
/
2. All jobs arrive over time, and each job and its processing time become known at its arrival time. The jobs should be first processed on a single machine and then delivered by a vehicle to some customer. When the capacity of the vehicle is infinite, we provide an online algorithm with the best competitive ratio of (
5
+
1
)
/
2. When the capacity of the vehicle is finite, that is, the vehicle can deliver at most c jobs at a time, we provide another best possible online algorithm with the competitive ratio of (
5
+
1
)
/
2.


---

## Body

## 1. Introduction and Problem Formulation

Production and distribution operations are two important segments in a supply chain; it is critical to integrate these two segments in a scheduling problem. In the last few years, scheduling problem with job delivery coordination is a very important topic. For the offline version, the earliest research of this topic is the one by Potts [1]. They considered the single machine scheduling problem to minimize the maximum delivery completion time and provided a heuristic algorithm with the worst-case performance ratio of 3
/
2. For more papers, the reader may refer to [2–6].For the online scheduling, there are three models which are commonly considered [7]. The first one assumes that there exists no release date and the jobs arrive in a list. The second one assumes that the processing time of each job is unknown until the job finishes. The third one assumes that each job arrives over time. When the machine is idle, an online algorithm decides which one of the available jobs is scheduled, if any. In this paper, we study the third model in which jobs arrive over time. For an online algorithm H, we use the competitive ratio (1)
ρ
H
=
sup
⁡
H
I
OPT
I
:
I
is
an
instance
with
OPT
I
>
0to measure the performance of H, where, for an instance I, H
(
I
) is used to denote the objective value of the schedule generated by the online algorithm H and OPT
(
I
) is the objective value of an offline optimal schedule.For the online version of scheduling problem with job delivery, Hoogeveen and Vestjens [8] considered the online single machine scheduling problem. They provided a best possible online algorithm with the competitive ratio of (
5
+
1
)
/
2. When restarts are allowed, van den Akker et al. [9] proposed a best possible online algorithm with the competitive ratio of 3
/
2. The online integrated production-distribution scheduling problems to minimize the sum of the total weighted flow time and the total delivery cost were considered by Averbakh [10]. For several cases of the problem, the author provided efficient online algorithms and used competitive analysis to study their worst-case performance ratio. Yuan et al. [11] studied a single batch machine online scheduling problem with restricted delivery times; that is, the delivery time of each job is less than or equal to its processing time. They provided a best possible online algorithm with competitive ratio of (
5
+
1
)
/
2. For the case in which the delivery time of each job is greater than or equal to its processing time, Tian et al. [12] proposed a best possible online algorithm with competitive ratio of (
5
+
1
)
/
2. Liu et al. [13] studied online scheduling problem on a single machine with bounded distribution. They proved a lower bound of competitive ratios for all online algorithms and proposed a best possible online algorithm with a competitive ratio of (
1
/
2
)
(
5
+
β
2
+
2
β
+
1
-
β
). Liu et al. [14] studied online scheduling problems on a single machine with deteriorating jobs. For each model, they presented an optimal online algorithm.Meanwhile, the scheduling problems in which the jobs have the equal length processing times are widely considered; the reader may refer to [15–17]. However, it is more reasonable to suppose that the jobs have their processing times being in a given interval. In semiconductor manufacturing integrated circuits are produced through the same technical processes. Therefore they have their processing times in a given interval. Fang et al. [18] studied online scheduling problems on a batch machine with the assumption that all jobs have their processing times in [
p
,
(
1
+
α
)
p
], where p
>
0 and α
=
(
5
-
1
)
/
2. For the two scheduling problems, they provided best possible online algorithms with the competitive ratio of (
5
+
1
)
/
2.In this paper, we study the single machine online scheduling problem with job delivery in which the jobs have their processing times in[
p
,
(
1
+
α
)
p
], where p
>
0 and α
=
(
5
-
1
)
/
2. The jobs should be first processed on a single machine and then delivered by a vehicle to some customer. When the capacity of the vehicle is infinite, we provide an online algorithm with the best competitive ratio of (
5
+
1
)
/
2. When the capacity of the vehicle is finite and fixed, that is, the vehicle can deliver at most c jobs to the customer at a time and c
≥
2, we provide another online algorithm with the best competitive ratio of (
5
+
1
)
/
2.


## 2. Problem Formulation and Preliminaries

In the online scheduling problem on a single machine to minimize the maximum delivery completion time, there aren jobs J
1
,
…
,
J
n which arrive over time. We do not know any information of these jobs in advance, including the number of the jobs and processing time p
j and arrival time r
j of each job J
j. The jobs are first processed on the single machine. Once the vehicle is available, the completed jobs can be delivered immediately in batches by the vehicle to some customer. Let T be the round-trip transportation between the machine and the customer. Since the customer is unknown in advance, we assume that T is known immediately once the first job arrives. The problem can be denoted by 1
→
D
∣
online
,
r
j
,
v
=
1
,
c
,
p
j
∈
[
p
,
(
1
+
α
)
p
]
∣
D
max
⁡. Here “1
→
D” means that jobs are first processed on a single machine and then the completed jobs must be delivered in batches to the customer; “v
=
1’’ means that there is one vehicle to deliver the jobs. “c’’ means the capacity of the vehicle; “p
j
∈
[
p
,
(
1
+
α
)
p
]’’ means that the jobs have their processing times in [
p
,
(
1
+
α
)
p
]. We use D
j to denote the time at which the vehicle transports J
j to the customer and returns to the machine. D
max
⁡
=
ma
x
j
=
1
n
{
D
j
} denotes the time when the vehicle finishes delivering the last delivery batch to the destination and returns to the machine.Indeed, whenc
=
1 and T is known in advance, Ng and Lu [19] provided an optimal online algorithm for the general case in which the processing time of each job is a nonnegative number. When c
≥
2 and T is known in advance, they provided an online algorithm which is not best possible. However, in this paper, we assume that c
≥
2 and T is unknown in advance. We deal with two variants of the online scheduling problem: 1
→
D
∣
online
,
r
j
,
v
=
1
,
c
=
∞
,
p
j
∈
[
p
,
(
1
+
α
)
p
]
∣
D
max
⁡ when the capacity of the vehicle is infinite and 1
→
D
∣
online
,
r
j
,
v
=
1
,
c
<
∞
,
p
j
∈
[
p
,
(
1
+
α
)
p
]
∣
D
max
⁡ when the capacity of the vehicle is finite and fixed.Letσ be a schedule generated by an online algorithm H. Let B
k be a delivery batch in σ. Then we define the following notation:(i)
s
j
(
σ
), the starting time of J
j on the machine in σ;
(ii)
c
j
(
σ
), the completion time of J
j on the machine in σ;
(iii)
s
(
B
k
)
=
min
⁡
{
s
j
(
σ
)
:
J
j
∈
B
k
};
(iv)
c
(
B
k
)
=
max
⁡
{
c
j
(
σ
)
:
J
j
∈
B
k
};
(v)
p
(
B
k
)
=
∑
J
j
∈
B
k
‍
p
j;
(vi)
U
(
t
), the set of the jobs which are available and unprocessed at time t;
(vii)
A
(
t
), the set of jobs which are completed on the machine and are waiting for the vehicle to be delivered at time t;
(viii)
ρ
(
B
k
), the ready time of delivery batch B
k, which is the maximum completion time of the jobs assigned to batch B
k; in fact ρ
(
B
k
)
=
c
(
B
k
);
(ix)
δ
(
B
k
), the departure time for the vehicle to delivery batch B
k from the machine to the customer; note that δ
(
B
k
)
≥
ρ
(
B
k
) in any feasible solution;
(x)
D
(
B
k
)
=
δ
(
B
k
)
+
T, the delivery completion time of the delivery batch B
k;
(xi)
we say that a set of delivery batchesB
=
{
B
1
,
…
,
B
k
} in this order is continuously delivered in a schedule if the time interval [
δ
(
B
1
)
,
D
(
B
k
)
] is totally occupied by the vehicle for delivering the batches in B; equivalently, we have δ
(
B
i
)
=
D
(
B
i
-
1
)
=
δ
(
B
i
-
1
)
+
T for 2
≤
i
≤
k;
(xii)
suppose thatB
′
=
{
B
1
′
,
…
,
B
k
′
} in this order is the set of delivery batches in a schedule; we say that there exists an idle time of the vehicle directly before δ
(
B
i
′
) in a schedule if D
(
B
i
-
1
′
)
<
δ
(
B
i
′
), for 2
≤
i
≤
k; similarly, we say that there exists no idle time of the vehicle directly before δ
(
B
i
′
) in a schedule if D
B
i
-
1
′
=
δ
(
B
i
′
), for 2
≤
i
≤
k.


## 3. A Lower Bound

We assume thatc
≥
2. Let ε be a sufficiently small positive number that tends to zero. Let N be a sufficiently large integer. For any online algorithm H, we consider the following job instance generated by the adversary. Let D
max
⁡
H and D
max
⁡
∗ be the objective values obtained by algorithm H and optimal offline algorithm, respectively. All jobs in the instance have a processing time p. Let T
=
N
p. At time 0, the adversary releases a job J
1. Assume that algorithm H starts processing J
1 at time t. If t
≥
α
(
p
+
T
), then no other jobs arrive. Clearly, we have D
max
⁡
H
≥
α
(
p
+
T
)
+
p
+
T. However, the optimal schedule is to process J
1 at time 0 and deliver it at time p. Then we have D
max
⁡
∗
=
p
+
T. Thus, (2)
D
max
⁡
H
D
max
⁡
∗
≥
α
(
p
+
T
)
+
p
+
T
p
+
T
=
1
+
α
.Suppose in the following that t
<
α
(
p
+
T
); we assume that the vehicle delivers J
1 at time s. If s
≥
α
(
p
+
T
), then no other jobs arrive. Then we have (3)
D
max
⁡
H
D
max
⁡
∗
≥
α
(
p
+
T
)
+
T
p
+
T
=
α
(
N
+
1
)
p
+
N
p
(
N
+
1
)
p
⟶
1
+
α
,when N
→
+
∞. If s
<
α
(
p
+
T
), then J
2 arrives at time s
+
ε. Clearly, we have D
max
⁡
H
≥
s
+
T
+
T. Note that s
≥
p. The optimal schedule is to process J
2 at time s
+
ɛ and then to deliver J
1 and J
2 together; that is, D
max
⁡
∗
=
s
+
ɛ
+
p
+
T. Thus, we have (4)
D
max
⁡
H
D
max
⁡
∗
≥
s
+
T
+
T
s
+
ɛ
+
p
+
T
⟶
s
+
T
+
T
s
+
p
+
T
=
1
+
T
-
p
s
+
p
+
T
>
1
+
(
N
-
1
)
p
(
α
+
1
)
(
N
+
1
)
p
⟶
1
+
1
1
+
α
=
1
+
α
,when ɛ
→
0 and N
→
+
∞.The above discussion implies the following two lemmas.Lemma 1.
For the problem1
→
D
∣
o
n
l
i
n
e
,
r
j
,
v
=
1
,
c
=
∞
,
p
j
∈
[
p
,
(
1
+
α
)
p
]
∣
D
max
⁡, there exists no online algorithm with a competitive ratio of less than 1
+
α.Lemma 2.
For the problem1
→
D
∣
o
n
l
i
n
e
,
r
j
,
v
=
1
,
c
<
∞
,
p
j
∈
[
p
,
(
1
+
α
)
p
]
∣
D
max
⁡, where c
≥
2, there exists no online algorithm with a competitive ratio of less than 1
+
α.


## 4. The Case ofc
=
∞

In this section, we consider the problem1
→
D
∣
online
,
r
j
,
v
=
1
,
c
=
∞
,
p
j
∈
[
p
,
(
1
+
α
)
p
]
∣
D
max
⁡, where the capacity of the vehicle is infinite; that is, all jobs can be delivered simultaneously in the same batch.Algorithm
D
∞Processing Stage. At time t, if the machine is available and U
(
t
)
≠
∅, we choose the job of U
(
t
) with the shortest processing time to process at time t. Otherwise, do nothing but wait.Delivery Stage. At time t with A
(
t
)
≠
∅, we consider A
(
t
) as a delivery batch. If the machine is available, t
≥
α
T, and U
(
t
)
=
∅, we deliver the delivery batch A
(
t
) at time t. Otherwise, do nothing but wait.Indeed, the algorithm of the processing stage ofD
∞ is optimal for the problem 1
∣
online
,
r
j
∣
C
max
⁡, because the algorithm cannot produce unnecessary idle time on the machine. For the delivery stage, the machine is available which means that there is not a job which is processing at this time and U
(
t
)
=
∅ means that there is not a job which is available and unprocessed at time t. That is, only if there is not an available job which is unprocessed or processing, the vehicle determines to deliver.Letσ and π be the schedules that are generated by algorithm D
∞ and optimal offline algorithm, respectively. Let D
max
⁡
(
σ
) and D
max
⁡
(
π
) be the objective values obtained from the schedule σ and the optimal offline schedule π, respectively. Let C
max
⁡
(
σ
) and C
max
⁡
(
π
) be the makespans of the schedule σ and the schedule π, respectively. For the problem 1
∣
online
,
r
j
∣
C
max
⁡, let C
max
⁡
∗ be the optimal offline makespan. Next, we get the following lemma.Lemma 3.
Consider the following(5)
C
max
⁡
∗
=
C
max
⁡
σ
.Proof.
Since the algorithm of processing stage ofD
∞ cannot produce an unnecessary idle time on the machine, that is, the machine is always busy as long as there are jobs which are available and unprocessed, we have C
max
⁡
∗
=
C
max
⁡
(
σ
).As the capacity of the vehicle is infinite, we have the following lemma.Lemma 4.
Consider the following(6)
D
max
⁡
π
≥
C
max
⁡
π
+
T
≥
C
max
⁡
∗
+
T
≥
r
l
+
T
.Theorem 5.
The competitive ratio of algorithmD
∞ is at most 1
+
α; that is, D
max
⁡
(
σ
)
/
D
max
⁡
(
π
)
≤
1
+
α.Proof.
LetB
1
,
…
,
B
k be the delivery batches in σ. Set n
B
=
|
{
B
1
,
…
,
B
k
}
|. Assume that the last arrival time of the jobs is r
l. If δ
(
B
k
)
=
α
T, then we have n
B
=
1. Thus D
max
⁡
(
σ
)
=
δ
(
B
k
)
+
T
≤
(
1
+
α
)
D
max
⁡
(
π
), as required. Suppose in the following that δ
(
B
k
)
>
α
T. If δ
(
B
k
)
=
C
max
⁡
(
σ
), from Lemmas 3 and 4, we have (7)
D
max
⁡
(
σ
)
=
C
max
⁡
(
σ
)
+
T
=
C
max
⁡
∗
+
T
≤
D
max
⁡
(
π
)
.If δ
(
B
k
)
≠
C
max
⁡
(
σ
), that is, the delivery batch B
k follows immediately behind the delivery batch B
k
-
1, then we have δ
(
B
k
)
=
δ
(
B
k
-
1
)
+
T. Thus, (8)
D
max
⁡
(
σ
)
=
δ
(
B
k
-
1
)
+
2
T
.As the capacity of the vehicle is infinite, by algorithm D
∞, we have r
l
>
δ
(
B
k
-
1
). According to the algorithm D
∞, we have δ
(
B
j
)
≥
α
T, for all 1
≤
j
≤
k. Then (9)
D
max
⁡
(
π
)
≥
r
l
+
T
>
δ
(
B
k
-
1
)
+
T
≥
α
T
+
T
.Thus, we have T
≤
α
D
max
⁡
(
π
). From Lemma 4, (8) can be rewritten as (10)
D
max
⁡
σ
=
δ
(
B
k
-
1
)
+
2
T
<
r
l
+
2
T
≤
D
max
⁡
(
π
)
+
α
D
max
⁡
(
π
)
.The result follows.Theorem5 and Lemma 1 imply that D
∞ is a best possible online algorithm for the problem 1
→
D
∣
online
,
r
j
,
v
=
1
,
c
=
∞
,
p
j
∈
[
p
,
(
1
+
α
)
p
]
∣
D
max
⁡. Indeed, according to the proof of Theorem 5, D
∞ is also a best possible online algorithm for the problem 1
→
D
∣
online
,
r
j
,
v
=
1
,
c
=
∞
∣
D
max
⁡.


## 5. The Case ofc
<
∞

In this section, we consider the problem1
→
D
∣
online
,
r
j
,
v
=
1
,
c
<
∞
,
p
j
∈
[
p
,
(
1
+
α
)
p
]
∣
D
max
⁡, where the capacity of the vehicle is finite and fixed; that is, the vehicle can deliver at most c jobs in the same batch to some customer at a time.Algorithm
D
cProcessing Stage. At time t, if the machine is available and U
(
t
)
≠
∅, we choose the job of U
(
t
) with the shortest processing time to process at time t. Otherwise, do nothing but wait.Delivery Stage
Step 0. If the vehicle is idle,t
≥
α
T, and A
(
t
)
≠
∅, determine |
A
(
t
)
| to be the number of the jobs of A
(
t
).
Step 1. If|
A
(
t
)
|
≥
c, select the earliest completed c jobs in A
(
t
) as a delivery batch and deliver this batch at time t.
Step 2. If0
<
|
A
(
t
)
|
<
c, then go to the following steps.
Step2
.
A. If the machine is available and U
(
t
)
=
∅, that is, there is not a job which is unprocessed or processing at time t, we consider jobs in A
(
t
) as a delivery batch and deliver this batch at time t.
Step2
.
B. If the machine is busy or U
(
t
)
≠
∅, that is, there exists a job which is unprocessed or processing at time t, wait until the machine is available and U
(
t
)
=
∅ or the next arrival.
Step 3. Go to Step 0.Similarly, the algorithm of the processing stage ofD
c is optimal for the problem 1
∣
online
,
r
j
∣
C
max
⁡, because the algorithm cannot produce unnecessary idle time. For the delivery stage, the machine is available which means that there is not a job which is processing at this time and U
(
t
)
=
∅ means that there is not a job which is available and unprocessed at time t. That is, only if there is not a job which is unprocessed or processing the vehicle determines to deliver. Meanwhile, the algorithm implies that the job with a smaller completion time is delivered no later than that with a larger completion time.Letμ and π be the schedules that are generated by algorithm D
c and optimal offline algorithm, respectively. Let D
max
⁡
(
μ
) and D
max
⁡
(
π
) be the objective values obtained from the schedule μ and the optimal offline schedule π, respectively. Let C
max
⁡
(
μ
) and C
max
⁡
(
π
) be the makespans of the schedule μ and the schedule π, respectively. For the problem 1
∣
online
,
r
j
∣
C
max
⁡, let C
max
⁡
∗ be the optimal offline makespan.As the algorithm of processing stage ofD
∞ is same as the algorithm of processing stage of D
c, we also have the following lemma.Lemma 6.
Consider the following(11)
C
max
⁡
∗
=
C
max
⁡
μ
.As the capacity of the vehicle is finite and fixed, there is at least one delivery batch. Letn be the number of the jobs in the schedule. Let k
∗
=
n
/
c. Then there are at least k
∗ delivery batches in any feasible schedule. Thus the following lemma can be observed.Lemma 7.
Consider the following(12)
D
max
⁡
(
π
)
≥
max
⁡
{
C
max
⁡
(
π
)
+
T
,
p
+
k
∗
T
}
.A delivery batch is calledfull if it contains exactly c jobs. Otherwise, it isnonfull. Let B
1
,
…
,
B
k be the delivery batches in μ. Assume that the last arrival time of the jobs is r
l.Lemma 8.
IfT
≤
p, then D
max
⁡
(
μ
)
/
D
max
⁡
(
π
)
≤
1
+
α.Proof.
AsT
≤
p, we have D
max
⁡
(
μ
)
=
C
max
⁡
(
μ
)
+
T. From Lemmas 6 and 7, we have (13)
D
max
⁡
μ
=
C
max
⁡
(
μ
)
+
T
=
C
max
⁡
∗
+
T
≤
C
max
⁡
(
π
)
+
T
≤
D
max
⁡
(
π
)
.The lemma follows.Lemma 9.
IfT
>
p and C
max
⁡
(
μ
)
≤
α
T, then D
max
⁡
(
μ
)
/
D
max
⁡
(
π
)
≤
1
+
α.Proof.
Note thatC
max
⁡
(
μ
)
≤
α
T. According to the algorithm of delivery stage of D
c, we have δ
(
B
1
)
=
α
T and δ
(
B
j
)
>
α
T for all 2
≤
j
≤
k. Then we get k
=
k
∗. Thus, (14)
D
max
⁡
(
μ
)
=
δ
(
B
1
)
+
k
T
=
α
T
+
k
∗
T
≤
(
1
+
α
)
D
max
⁡
(
π
)
.The lemma follows.Lemma 10.
IfT
>
p and C
max
⁡
(
μ
)
>
α
T, then D
max
⁡
(
μ
)
/
D
max
⁡
(
π
)
≤
1
+
α.Proof.
LetB
t be the earliest delivery batch such that B
t
,
…
,
B
k are continuous delivery batch in μ. If B
t
=
B
k, as C
max
⁡
(
μ
)
>
α
T, we have δ
(
B
k
)
=
C
max
⁡
(
μ
); then D
max
⁡
(
μ
)
=
C
max
⁡
(
μ
)
+
T
≤
D
max
⁡
(
π
), as required.
IfB
t
≠
B
k and δ
(
B
k
-
1
)
≤
C
max
⁡
(
μ
), as C
max
⁡
(
μ
)
>
α
T, we have C
max
⁡
(
π
)
≥
C
max
⁡
∗
=
C
max
⁡
(
μ
)
>
α
T. Then (15)
D
max
⁡
(
π
)
≥
C
max
⁡
(
π
)
+
T
≥
(
α
+
1
)
T
.Thus, we have D
max
⁡
(
μ
)
=
δ
(
B
k
-
1
)
+
2
T
≤
C
max
⁡
(
μ
)
+
2
T
≤
D
max
⁡
(
π
)
+
T
≤
(
1
+
α
)
D
max
⁡
(
π
), as required. Suppose in the following that B
t
≠
B
k and δ
(
B
k
-
1
)
>
C
max
⁡
(
μ
). Then B
k
-
1 follows immediately behind the delivery batch B
k
-
2, and so |
{
B
t
,
…
,
B
k
}
|
≥
3. Now, there are two possibilities to be discussed.
Case  1. There are some nonfull delivery batches in B
t
,
…
,
B
k
-
1. Denote the last nonfull delivery batch before B
k by B
s, where t
≤
s
≤
k
-
1. Obviously, we have δ
(
B
s
)
≥
α
T and D
max
⁡
(
μ
)
=
δ
(
B
s
)
+
(
k
-
s
+
1
)
T. As B
s is nonfull, by algorithm D
c, we have U
(
δ
(
B
s
)
)
=
∅ and there is not a job which is processing at time δ
(
B
s
). Then, for each s
+
1
≤
i
≤
k, the jobs of B
i arrive after δ
(
B
s
). Note that B
s
+
1
,
…
,
B
k
-
1 are full delivery batches. Thus, we have (16)
D
max
⁡
(
π
)
≥
δ
(
B
s
)
+
(
k
-
s
)
T
.From (15) and (16), we have (17)
D
max
⁡
μ
=
δ
(
B
s
)
+
(
k
-
s
+
1
)
T
≤
D
max
⁡
(
π
)
+
T
≤
(
1
+
α
)
D
max
⁡
(
π
)
,as required.
Case  2. In μ, all the delivery batches B
t
,
…
,
B
k
-
1 are full. As |
{
B
t
,
…
,
B
k
}
|
≥
3, we have k
∗
≥
3. From Lemma 7, we have T
≤
(
1
/
3
)
D
max
⁡
(
π
).
Case  2.1 (
δ
(
B
t
)
=
α
T
). Then B
t
=
B
1 and D
max
⁡
(
μ
)
=
δ
(
B
1
)
+
k
T. As all the delivery batches B
t
,
…
,
B
k
-
1 are full, we have k
=
k
∗. Then D
max
⁡
(
μ
)
=
δ
(
B
1
)
+
k
T
=
α
T
+
k
∗
T
≤
(
1
+
α
)
D
max
⁡
(
π
), as required.
Case  2.2 (
δ
(
B
t
)
>
α
T
). The jobs in B
t are processed on the machine in this interval [
s
(
B
t
)
,
c
(
B
t
)
]. Note that B
t is the earliest delivery batch such that B
t
,
…
,
B
k are continuous delivery batch in μ. Then there exists an idle time of the vehicle directly before δ
(
B
t
). Then δ
(
B
t
)
=
ρ
(
B
t
)
=
c
(
B
t
). By algorithm D
c, the job with a smaller completion time is delivered no later than that with a larger completion time; then s
(
B
t
+
1
)
≥
c
(
B
t
). Noting that B
t
,
…
,
B
k are continuous delivery batch, we have δ
(
B
t
+
1
)
=
δ
(
B
t
)
+
T. However, p
j
∈
[
p
,
(
1
+
α
)
p
], for all 1
≤
j
≤
n, and B
t
+
1 is full; we have (18)
δ
B
t
+
T
=
δ
(
B
t
+
1
)
≥
c
(
B
t
+
1
)
≥
s
(
B
t
+
1
)
+
c
p
≥
c
(
B
t
)
+
c
p
.Thus, we have (19)
p
≤
T
c
.
If there exists an idle time in[
s
(
B
t
)
,
c
(
B
t
)
] on the machine in μ, assume that s
i is the earliest time such that there exists no idle time in [
s
i
,
c
(
B
t
)
], where s
i
>
s
(
B
t
). Then s
i is the arrival time of some job. By algorithm D
c, all jobs of B
t
+
1
,
…
,
B
k arrive at or after s
i. Assume that there are m jobs which are processed in [
s
i
,
c
(
B
t
)
] on the machine, where m
<
c. Noting that B
t
+
1
,
…
,
B
k
-
1 are full, then there are at least m
+
(
k
-
t
-
1
)
c
+
1 jobs which arrive at or after s
i. In fact, these jobs need at least k
-
t delivery batches to be delivered. Thus, we have (20)
D
max
⁡
(
π
)
≥
s
i
+
m
p
+
(
k
-
t
)
T
.As p
j
∈
[
p
,
(
1
+
α
)
p
], for all 1
≤
j
≤
n, we have (21)
D
max
⁡
μ
=
δ
(
B
t
)
+
(
k
-
t
+
1
)
T
≤
s
i
+
m
(
1
+
α
)
p
+
(
k
-
t
+
1
)
T
.From (19), (20), and (21), we have (22)
D
max
⁡
μ
-
D
max
⁡
π
≤
m
α
p
+
T
≤
α
T
+
T
≤
1
+
α
3
D
max
⁡
(
π
)
<
α
D
max
⁡
(
π
)
,as required.
If there exists no idle time in[
s
(
B
t
)
,
c
(
B
t
)
] on the machine in μ, assume that s
0 is the earliest time such that there exists no idle time in [
s
0
,
c
(
B
t
)
]. Obviously, s
0
≤
s
(
B
t
) and s
0 is the arrival time of some job. By algorithm D
c, all jobs of B
t
+
1
,
…
,
B
k arrive at or after s
0. Assume that there are n
′ jobs which arrive at or after s
0 and there are z jobs which are processed on the machine in [
s
0
,
c
(
B
t
)
], where z
≥
c. Then there are n
′
-
z jobs which are processed on the machine in [
c
(
B
t
)
,
C
max
⁡
(
μ
)
]. As p
j
∈
[
p
,
(
1
+
α
)
p
], we have (23)
D
max
⁡
(
μ
)
≤
s
0
+
z
(
1
+
α
)
p
+
(
k
-
t
+
1
)
T
.Let n
′
=
k
′
c
+
ν, where n
′
≤
n and k
′
≤
k
∗
-
1. Then (24)
D
max
⁡
(
π
)
≥
s
0
+
ν
p
+
(
k
′
+
1
)
T
.In addition, n
′
-
z jobs which are processed in [
c
(
B
t
)
,
C
max
⁡
(
μ
)
] are delivered by k
-
t delivery batches, because these jobs are delivered in B
t
+
1
,
…
,
B
k. Then (
n
′
-
z
)
/
c
=
k
-
t; that is, k
-
t
-
1
<
(
n
′
-
z
)
/
c
≤
k
-
t. Hence, k
′
c
+
ν
-
z
=
n
′
-
z
>
c
(
k
-
t
-
1
); that is, (25)
c
(
k
-
t
-
1
)
-
(
k
′
c
+
ν
)
<
-
z
.On the other hand, as |
{
B
t
,
…
,
B
k
}
|
≥
3, we have |
{
B
t
+
1
,
…
,
B
k
}
|
≥
2; then c
+
1
≤
n
′
-
z
=
k
′
c
+
ν
-
z; that is, (26)
z
c
<
k
′
+
ν
c
-
1
.Now, from (23), (24), and (25), we have (27)
D
max
⁡
μ
-
D
max
⁡
π
=
z
(
1
+
α
)
p
-
ν
p
+
(
k
-
t
+
1
)
T
-
(
k
′
+
1
)
T
=
(
z
-
ν
)
p
+
α
z
p
+
(
k
-
t
)
T
-
k
′
T
≤
z
-
ν
c
T
+
α
z
c
T
+
c
k
-
t
-
1
-
c
k
′
+
ν
c
T
+
T
+
ν
c
T
≤
z
-
ν
c
T
+
α
z
c
T
-
z
c
T
+
ν
c
T
+
T
=
α
z
c
T
+
T
=
α
(
z
c
+
1
α
)
T
.If z
=
c, since T
≤
(
1
/
3
)
D
max
⁡
(
π
), we have D
max
⁡
(
μ
)
-
D
max
⁡
(
π
)
≤
(
1
+
α
)
T
≤
α
D
max
⁡
(
π
), as required. If z
>
c, then there exists no idle time immediately before s
(
B
t
) on the machine. As the job with a smaller completion time is delivered no later than that with a larger completion time, we have ρ
(
B
t
-
1
)
=
c
(
B
t
-
1
)
=
s
(
B
t
). Furthermore, there exists an idle time of the vehicle before δ
(
B
t
); then s
(
B
t
)
+
T
=
ρ
(
B
t
-
1
)
+
T
≤
δ
(
B
t
-
1
)
+
T
<
δ
(
B
t
)
=
c
(
B
t
)
≤
s
(
B
t
)
+
c
(
1
+
α
)
p, implying that (28)
p
>
α
c
T
.However, (29)
(
α
ν
c
+
1
)
-
(
ν
c
+
α
)
=
(
c
-
ν
)
(
1
-
α
)
c
>
0
.From (24), (26), (28), and (29), (27) can be rewritten as (30)
D
max
⁡
μ
-
D
max
⁡
π
≤
α
z
c
+
1
α
T
≤
α
(
k
′
+
ν
c
-
1
+
1
α
)
T
=
α
(
k
′
+
ν
c
+
α
)
T
≤
α
(
k
′
+
α
ν
c
+
1
)
T
≤
α
[
ν
p
+
(
k
′
+
1
)
T
]
≤
α
D
max
⁡
(
π
)
.This completes the proof.Theorem 11.
For the problem(31)
1
⟶
D
∣
o
n
l
i
n
e
,
r
j
,
v
=
1
,
c
<
∞
,
p
j
∈
p
,
1
+
α
p
∣
D
max
⁡
,where the capacity of the vehicle is finite and fixed, D
c is the best possible online algorithm with a competitive ratio of 1
+
α.Proof.
From Lemmas8, 9, and 10, the competitive ratio of online algorithm D
c is 1
+
α. The result follows from Lemma 2.



---

*Source: 805294-2015-04-12.xml*