Acta Informatica 41, 315–340 (2005) Digital Object Identifier (DOI) 10.1007/s00236-004-0156-9

Preemptive online algorithms for scheduling with machine cost
Yiwei Jiang, Yong He Department of Mathematics, State Key Lab of CAD & CG, Zhejiang University, Hangzhou 310027, People’s Republic of China (e-mail: [email protected]) Received: 7 June 2004 / 28 September 2004 c Springer-Verlag 2004 Published online: 11 November 2004 –


Abstract. For most scheduling problems the set of machines is fixed initially and remains unchanged. Recently Imreh and Noga proposed adding the concept of machine cost to scheduling problems and considered the so-called List Model problem. For this problem, we are given a sequence of independent jobs with positive sizes, which must be processed non-preemptively on a machine. No machines are initially provided, and when a job is revealed the algorithm has the option to purchase new machines. The objective is to minimize the sum of the makespan and cost of machines. In this paper, a modified model of List Model is presented where preemption is allowed. For this model, it is shown that better performance is √ possible. We present an online algorithm with a competitive ratio of (2 6 + 2)/5 ≈ 1.3798 while the lower bound is 4/3. For the semi-online problem with decreasing sizes, we design an optimal algorithm with a competitive ratio of 4/3, which improves the known upper bound of 3/2. The algorithm does not introduce any preemption, and hence is also an optimal semi-online algorithm for the non-preemptive semi-online problem. For the semi-online problem with known largest size, we present an optimal algorithm with a competitive ratio of 4/3. 1 Introduction In this paper we consider the following parallel machine scheduling problem with machine cost. We are given a sequence J of independent jobs with


This research is supported by the Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions of MOE, China, and National Natural Science Foundation of China (10271110, 60021201).

316

Y. Jiang, Y. He

positive processing times (sizes) p1 , p2 , . . . , pn , which must be scheduled on machines. Jobs come one by one (online over list), and it requires one to schedule jobs irrevocably to machines as soon as they are given, without any knowledge about jobs that follow later on. The machines are identical, but their number is not fixed. Instead the scheduler must purchase machines, each at a cost 1. (As the machines are identical, the cost for purchasing machines are the same. Moreover, by normalizing all job sizes and machine cost, we can assume that the cost for purchasing a machine is 1 without loss of generality). Initially there are no machines. If preemption is permitted, we are allowed to split a job and spread its processing over machines, in nonoverlapping time slots. On the other hand, non-preemptive algorithms are not allowed to cut the job and have to assign it continuously to one machine. The load of a machine is the sum of the sizes of the jobs (or portions of jobs) scheduled on it. The makespan is the maximum load over machines after all jobs are completed. The goal is to minimize the sum of the makespan and the cost for purchasing machines. This problem, called List Model, was first studied by Imreh and Noga [10]. This problem is quite different from the classical scheduling problem P m||Cmax , where we typically have a fixed number m of machines, the algorithm (scheduler) makes no decision regarding the machine number nor it is allowed to change the machine number later, and the provided machines can be utilized without cost. Imreh and Noga [10] proposed adding the concept of machine cost to scheduling problem due to the following main motivation: First, real machines have cost. Second, the performance of an algorithm on a given input can be highly dependent on the number of machines. This seems particularly true when considering worst-case measures (such as competitive analysis). Last, by considering such a variant we may find other interesting problems and/or gain insight into the original. Besides [10], Panwalker and Liman [12] recently also proposed a similar scheduling problem. For their problem, a number of identical machines can be activated to process the jobs, and each machine that is activated incurs a fixed machine activation cost. The objective of minimizing the sum of machine activation cost, weighted earliness cost and weighted tardiness cost was considered. Following [10], He and Cai [7, 1] considered a variant of the List Model problem. They studied the problem in semi-online environment. Here semionline means that we have partial knowledge on jobs before constructing a schedule and we still cannot rearrange any job which has been assigned to machines. Naturally, one seeks to improve on an online algorithm by deploying a semi-online algorithm that exploits partial information about the jobs. If the problem is semi-online with known largest size, we know the size of the largest job as a priori. If the problem is semi-online with known

Preemptive online algorithms for scheduling with machine cost

317

total size, we know the sum of sizes of all jobs in advance. If the problem is semi-online with decreasing sizes, we know that jobs come in an order of non-increasing sizes. Note that the semi-online problem with known largest size can be viewed as a relaxation of the problem with decreasing sizes. These semi-online versions were first proposed by different authors when the basic scheduling problem P m||Cmax was studied [6, 9, 11]. Research on semi-online scheduling problems involves studying how to benefit from such partial information, and how to design semi-online algorithms with better competitive ratios than those of the best possible or known online algorithms. The results of semi-online research mainly focused on the classical makespan scheduling problems P m||Cmax and Qm||Cmax (see [4, 5,8] and references therein). They have shed light on the relations between the extent of the known information and the approximability of the scheduling problems under an environment of partial information, and on the value of different types of partial information for the design of approximation algorithms. Prior to the release of studies on semi-online scheduling, the usefulness of different types of partial information for the design of approximation algorithms was almost unknown, and there was little knowledge about how to use the available partial information to construct approximation algorithms that yield a better performance guarantee. Hence it would be interesting to study semi-online algorithms for scheduling problems other than the classical makespan scheduling problems on parallel machines. The quality of an online or semi-online algorithm A is measured by its competitive ratio. For any job sequence I, let z A denote the objective value produced by A, and z ∗ denote the optimal value. Then the competitive ratio of A is defined as the smallest number c such that z A ≤ cz ∗ for all sequences. An online (semi-online) scheduling problem has a lower bound ρ if no online (semi-online) algorithm has a competitive ratio of smaller than ρ. An online (semi-online) algorithm is called optimal if its competitive ratio matches the lower bound of the problem. Previous work. For the non-preemptive List Model problem, Imreh and Noga [10] presented an online algorithm with a competitive ratio of 1.618, and showed the lower bound of the problem was 4/3. D´osa and He [3] made an improvement √ by presenting an online algorithm with a competitive ratio of at most (2 6 + 3)/5 ≈ 1.5798. If randomization is allowed, Seiden [13] provided a lower bound of 6e/(6e − 1) > 1.06532. For the semi-online problem with known largest size, He and Cai [7] presented an algorithm with a competitive ratio of at most 1.5309 while the lower bound was 4/3. Further, D´osa and He [3] presented an improved algorithm with a competitive ratio of at most 3/2. For the semi-online problem with known total size, He and Cai [7] presented an algorithm with a competitive ratio of at most 1.414 while the lower bound was 1.161. For the semi-online problem with decreasing

318

Y. Jiang, Y. He

sizes, Cai and He [1] presented an algorithm with a competitive ratio of 3/2 while the lower bound was still 4/3. But unfortunately, no optimal algorithm has been obtained for the online and semi-online problems. Our results. In this paper, we focus on the preemptive List Model problem. First, √ we present a preemptive online algorithm with a competitive ratio of (2 6 + 2)/5 ≈ 1.3798 while the lower bound is 4/3. Second, we present an optimal algorithm for the semi-online problem with decreasing sizes. The competitive ratio is 4/3. This algorithm does not introduce any preemption, hence it is indeed an optimal semi-online algorithm for non-preemptive problem with decreasing sizes. It improves the known upper bound 3/2. Third, we present an optimal preemptive semi-online algorithm for the semionline problem with known largest size. The competitive ratio is still 4/3. Hence it can be also viewed as an optimal semi-online algorithm for the semi-online problem with decreasing sizes, but it really uses preemptions. For the considered List Model problem, it is crucial to design a strategy for deciding when to purchase machines. In [10], the decision simply depends on the total size of all arrived jobs. In [3], a new strategy was proposed, in which the decision depends on the current makespan, and upon the current objective value with respect to the lower bounds of the current optimal value. In this paper, we further develop this idea for the preemptive problems. In fact, our decision will be made by comparing the current makespan with the number of currently purchased machines and the largest job size (if it is known). To get tight competitive analysis, we will develop approaches to estimate the lower bound of total size of all jobs, i.e., the optimal value, by carefully analyzing online algorithms. Furthermore we will provide two new lower bound formulas of the optimal value (see Lemma 2.2), which may be useful even for other preemptive/non-preemptive List Model problems. We note that when preemptions are allowed with no machine cost, the List Model problem becomes the online preemptive scheduling problem P m|pmpt|Cmax which has been solved by Chen et al. [2]. The paper is organized as follows. Section 2 presents preliminary results. Section 3 considers the online problem. Section 4 considers the semi-online problem with decreasing sizes. Section 5 considers the semi-online problem with known largest size. Finally Sect. 6 contains some remarks. 2 Preliminaries We use the following notation in the remainder of the paper. Denote by pmax j the largest job in the first j jobs, and by L the largest size of all jobs. Then L = pmax n . Denote by P =

n


i=1

pi the total size of all jobs. Let m0 be the

Preemptive online algorithms for scheduling with machine cost

319

positive integer satisfying (m0 −1)m0 < P ≤ m0 (m0 +1). Let C A and C ∗ be the makespan yielded by algorithm A and an optimal (offline) algorithm respectively, and let m and m∗ be the number of machines purchased by A and the optimal (offline) algorithm, after all jobs are completed, respectively. Then z A = C A + m and z ∗ = C ∗ + m∗ . √ √ Lemma 2.1 ([10]) z ∗ ≥ 2 P . Further, if L ≥ √P , then z ∗ ≥ L + P/L; or, equivalently, if there is a job pi such that pi ≥ P , then z ∗ ≥ pi + P/pi . Next lemma provides two new lower bounds of the optimal value, which are quite useful in Sect. 4. Lemma 2.2 (1) z ∗ ≥

P m0

+ m0 . (2) Further, if L >

P m0 ,

then z ∗ ≥ L +

P L.

Proof. (1) It is clear that z ∗ ≥ min{ Pi +i : i ∈ Z + } by averaging argument. Define the function f0 (x) = Px + x over all positive integers. Then we know that it is increasing in terms of x when x ≥ m0 , and decreasing when x < m0 . Hence min{ Pi + i : i ∈ Z + } = mP0 + m0 . (2) Since L > mP0 , we have L > m0 − 1 due to the definition of m0 . If the number of machines in an optimal solution satisfies m∗ > m0 − 1, i.e., m∗ ≥ m0 , then the optimal value is z ∗ = C ∗ + m∗ ≥ L + m0 > L + PL by the assumption of L > mP0 . Hence we assume m∗ ≤ m0 − 1. Two cases are considered as follows with respect to the value of L. Case 1. m0 − 1 < L < m0 . Since m∗ ≤ m0 − 1, and the function f0 (x) is decreasing when x < m0 , we have z ∗ ≥ mP∗ + m∗ ≥ m0P−1 + m0 − 1. Hence we only need to prove m0P−1 + m0 − 1 ≥ L + PL to get the result. To see it, due to the definition of m0 , we have m0 (m0 − 1) < P , and thus L+

P (L − (m0 − 1))(L(m0 − 1) − P ) P −( + m0 − 1) = L m0 − 1 L(m0 − 1) (L − (m0 − 1))(m0 (m0 − 1) − P ) < < 0. L(m0 − 1)

Case 2. L ≥ m0 . If m∗ >  PL , i.e. m∗ ≥  PL , then we have z ∗ ≥ L +  PL ≥ L + PL . Therefore we assume m∗ ≤  PL . Obviously  PL  < m0 by the assumption of L > mP0 . Since again f0 (x) is decreasing when x < m0 , we have z ∗ ≥ mP∗ + m∗ >  PP  +  PL . Hence we only need to show P

P  L

L>

+  PL  ≥ L + P m0

P L.

Let

P L

L

=  PL  + x, where 0 ≤ x < 1. Then by

and L ≥ m0 , we have 







P P P  L + −   + =L+x− P L L L

  P L



+x L

  P L





L = x 1 −    P L

320

Y. Jiang, Y. He

=

x

  P L



−L

  P L

≤

x



P L

−

P m0



  P L

≤ 0.



Lemma 2.3 ([10, 1]) Any preemptive online algorithm for the problem, any preemptive semi-online algorithm for the problem with decreasing sizes, and any preemptive semi-online algorithm for the problem with known largest size have a competitive ratio at least 4/3. Proof. We show the result by adversary method. Let the largest size be L = 1/N where N is a sufficiently large positive integer. Consider a long sequence of jobs, each with size L. If an algorithm A never purchases a A 8N/N +1 3 second machine, then 8N jobs come. It follows that zz ∗ ≥ 8N/(2N )+2 = 2 . So we assume that A purchases a second machine when job pi arrives. Then no new job comes. If all arrived jobs have a total size Pi ≤ 2, then A in the optimal solution all jobs are processed on one machine and zz ∗ ≥ Pi −1/N +2 ≥ 4−1/N . If Pi > 2, then in the optimal solution all jobs can be Pi +1 3 +2 split nearly evenly between two machines and zz ∗ ≥ PiP−1/N ≥ i /2+2 Since we choose N to be arbitrarily large, we obtain the result. A

Lemma 2.4 (1) If x ≤ 1, then √

1+x 1+ 12 x2

3)m > 2, then √ (3) If 2 ≤ x < (2 − 3)m, then

(2) If x ≥ (2 −

4−1/N 3+1/N .



√

2 6+2 . 5

<

m2 +m+x2 −3x 2

√ > ( 3 − 1)2 m2 .

2m

2 2 −3x m−x+ m +m+x 2(m−x)

<

√ 2 6+2 . 5

1+x . It is 1+ 12 x2 √ √ 1+ 3 < 2 56+2 2

Proof. (1) Let f1 (x) =

not hard to obtain that f1 (x) achieves √ the maximum value when t = 3 − 1. √ 2 2 −3x . Since x ≥ (2− 3)m > 2, we can conclude (2) Let f2 (x) = m +m+x 2 that f2 (x) is increasing in terms of x by an easy calculation. Thus we have

f2 (x) ≥ f



=



√ 



m2 + m + 2 −



2− 3 m =

√  √  8−4 3 m2 + 3 3−5 m

√ 2 2 √  3 m −3 2− 3 m

2

√ 

> 4−2 3 m2 =

√

2 √ (3) Since 2 ≤ x < (2 − 3)m implies m − 3x > 0, we have 2m m−x+

m2 +m+x2 −3x 2(m−x)

<

2m m−x+

m2 +x2

2(m−x)

=

2

3−1

m2 .

4m2 − 4mx . 3m2 + 3x2 − 4mx

Preemptive online algorithms for scheduling with machine cost

321

√ 2 −4mx x 4−4t Let m = t with some 0 < t < 2 − 3, then 3m4m 2 +3x2 −4mx = 3+3t2 −4t , to obtain that f3 (t) achieves the maximum denoted√by f3 (t). It is not difficult √ 2 6+2 3− 6 

value 5 when t = 3 . Lemma 2.5 (1) If 23 m ≤ x ≤ m + 1 and m ≥ 3, then 2

(2) If 32 m ≤ x ≤ m and m ≥ 3, then 2

(3) If x ≥

m−1 m

and m ≥ 3, then

x+m 2m2 −3m +x 3

xm+1+m 1 1 xm+ m+1 + 2x − 2xm 2

x+m 2m2 −2m +x 3

≤ 43 .

≤ 43 . ≤ 43 .

. Proof. (1) The desired inequality is equivalent to f4 (x) = (3(x + m))2 −



8

2m2 −2m 3

2

+x

≤ 0. By simplifying f4 (x), we have f4 (x) = 9(x + 2

128m 2m 2 2 m − 32 − 101m − 9(m − 32 9 ) + 3 3 9 ) . Since m ≥ 3, we have 3 > 32 −m + 9 , from which it follows that f4 (x) is increasing in terms of x when 2 20m2 44m 3 m ≤ x ≤ m + 1. Hence f4 (x) ≤ f4 (m + 1) = − 3 + 3 − 55 < 0 due to m ≥ 3.



(2) and (3) The results can be obtained by the same method as above. Lemma 2.6 Assume that t ≥ 2 and m ≥ 3. We have

(1)

 2m − 1 4   ≤ ,  2 +t2 )−(m+t)  (m 3 2

for m ≤ 2t,

2

2m − 1 4   ≤ ,    3 2m2 +t2 −2mt+3t−4m+2 2

for m > 2t.

2

(2)

 2m 4   ≤ ,  2 2  3  2 (m +t )+(m−t−2)

for m ≤ 2t,

2

4 2m   ≤ ,   2 2  3 2 2m +t −2mt+3t−2m

for m > 2t.

2

Proof. We only show the first inequality of (1), and other can be proved by similar arguments. In fact, the first inequality of (1) is equivalent to 9(m − 1/2)2 − 8(m2 + t2 − m − t) ≤ 0. Since m ≤ 2t and t ≥ 2, we have

1 9 m− 2

2

− 8(m2 + t2 − m − t) = m2 − m − 8t2 + 8t +

≤ 4t2 − 2t − 8t2 + 8t + and we are done.

9 4

9 9 9 = −4t2 + 6t + ≤ −16 + 12 + < 0, 4 4 4 

322

Y. Jiang, Y. He

Before going to the main content, we further define some notation. When analyzing an online or semi-online algorithm in the later sections, we use the following: Denote by k the current number of purchased machines. Denote by pji the first job (maybe a part of which) processed on the i-th purchased machine, and pl the job determining the makespan after all jobs are completed. Let Cji denote the current load of the i-th machine at time j ≥ 0, where time j will be defined later. 3 Preemptive online problem In this section we define time j as the moment right after the j-th job has been scheduled and the machines have been re-indexed in non-decreasing order of their current loads. Algorithm H1 1. Purchase the first machine to process job p1 . Set k = 1, j = 2 and C1max = max{k + 1, C11 }, where C11 = p1 . 2. For pj (j ≥ 2): max − C 1 , schedule p completely onto the machine with 2.1. If pj ≤ Cj−1 j j−1 minimum current load, go to 3. max − C 1 max 2.2. If Cj−1 j−1 < pj ≤ Cj−1 , purchase a new machine, and schedmax 1 ule Cj−1 − Cj−1 portion of pj onto the machine with minimum current load and the rest of pj onto the new machine. Set k = k + 1, go to 3. max , purchase a new machine and schedule p completely 2.3. If pj > Cj−1 j onto it. Set k = k + 1, go to 3. 3. Re-index the machines with respect to their current loads such that Cj1 ≤ Cj2 ≤ · · · ≤ Cjk . Let Cjmax = max{k + 1, Cjk }, and go to 4. 4. Set j = j + 1. If no new job comes, stop. Otherwise, go to 2. Remark 1 At time j, if the current number of machines is k, then the maximum current load Cjk satisfies: max if p is scheduled by Step 2.1; (1) Cjk ≤ Cj−1 j max if p is scheduled by Step 2.2; (2) Cjk = Cj−1 j max if p is scheduled by Step 2.3. (3) Cjk = pj > Cj−1 j

Lemma 3.1 Algorithm H1 is well-defined, that is, the time slots assigned to any job pj never overlap. Proof. If pj is scheduled according to Step 2.1 or 2.3, it is clear that the time slots assigned to pj do not overlap. If pj is scheduled onto two machines by

Preemptive online algorithms for scheduling with machine cost

323

max − C 1 ) ≤ C 1 Step 2.2, then by pj − (Cj−1 j−1 j−1 we know that its completion time on one machine (newly-purchased one) is not greater than its starting time on the other machine, that is to say, its time slots do not overlap, too. 

 >  machines have been purchased at time j. If Cjm Lemma 3.2 Suppose m  = pmax .  + 1 or Cjmax > m  + 1, we have Cjmax = Cjm m j

,m  >  + 1}, and by the assumption that Cjm Proof. Since Cjmax = max{Cjm

 . We next show C m  max ,   m+1 or Cjmax > m+1, we obtain Cjmax = Cjm j = pj that is, the maximum current load at time j is achieved by a single job with largest size. Suppose that at time q (q ≤ j), the maximum current load achieves  for the first time, and the numbers of machines are k and k  the value Cjm  = Ck > Ck . (k ≤ k  ) at time q −1 and q, respectively. Then we have Cjm q q−1 

 >m  + 1 (note that we have shown In addition, by the assumption that Cjm

 ), we have C k = C m   + 1 ≥ k  + 1 ≥ k + 1. Therefore Cjmax = Cjm q j >m  k } = C max . If job p is scheduled by we obtain Cqk > max{k + 1, Cq−1 q q−1  max due to Remarks 1(1) and Step 2.1 or 2.2, it is clear that Cqk ≤ Cq−1 (2), a contradiction. Thus pq must be scheduled by Step 2.3, that is, pq   is scheduled completely onto one machine, and Cqk = pq . As Cqk is the maximum machine load, we get pq = pmax . 

j 

Lemma 3.3 (1) C H1 ≥ m. (2) At least one of the following two conclusions holds: (i) C H1 = L; (ii) If C H1 > L, then m ≤ C H1 ≤ m + 1. Proof. (1) Consider time jm , i.e., the moment when job pjm comes. As we need to purchase the m-th machine for processing it (or its portion), by Remarks 1(2) and (3) we have C H1 ≥ Cjmm ≥ Cjmax ≥ (m − 1) + 1 = m. m −1 (2) Noting that C H1 ≥ L holds trivially, we only need to show that C H1 = L  = m, must hold if C H1 > m + 1. Applying Lemma 3.2 with j = n and m H1 m max we obtain C = Cn = pn = L. 

Lemma √ 3.4 If m ≤ 2, the competitive ratio of algorithm H1 is at most 2 6+2 4 . 3 < 5 Proof. If m = 1, algorithm H1 schedules all jobs onto one machine by Step 2.1. We have P < 2. Thus the optimal value z ∗ ≥ min{P + 1, P/2 + 2} = P + 1 = z H1 . Now we consider the case of m = 2. If C H1 = L, L ≥ 2 by H1 4 Lemma 3.3(1). Since z ∗ ≥ L+1 holds trivially, we obtain zz ∗ ≤ L+2 L+1 ≤ 3 .

324

Y. Jiang, Y. He

Hence we suppose C H1 > L. We then have 2 ≤ C H1 ≤ 3 by Lemma 3.3(2). Since m = 2, C H1 < P < 2C H1 is obviously true. It follows that 2 < P < 6, and thus 



P P z ≥ min i + : i is a positive integer = 2 + . i 2 ∗

If further C H1 = 2, we get C H1

z H1 z∗

≤

2+C H1 2+P/2

<

2+C H1 2+C H1 /2

=

4 3.

Hence we

suppose 2 < ≤ 3. To get the desired ratio, we need to estimate a lower bound of P . In fact, we next show that P ≥ C H1 + 2 by distinguishing two cases. Case 1. Cj12 −1 ≤ 2. Then Cjmax = max{2, Cj12 −1 } = 2. If pj2 < 2, then 2 −1 pj2 < Cjmax . Since a new machine is purchased to process pj2 , we know 2 −1 that pj2 is scheduled by Step 2.2, and Cj22 = 2 after re-indexing the machine 2 order. Since C H1 > 2, we get l > j2 and thus Cl−1 ≥ Cj22 = 2. Since pl is assigned completely onto the machine with minimum current load such that 1 + p + C2 H1 + 2. If p ≥ 2, its new load is C H1 , we have P ≥ Cl−1 j2 l l−1 ≥ C pj2 is assigned completely onto a new machine such that Cj22 = pj2 ≥ 2. 2 C H1 > L implies l > j2 , and thus Cl−1 ≥ Cj22 = 2. Hence we can obtain H1 P ≥ C + 2 similarly. Case 2. Cj12 −1 > 2. Clearly according to the definition of j2 , algorithm H1 purchases only one machine at time j2 − 1. Hence all
arrived jobs at time j2 − 1 have a total size at least 2. Let x = min{j : ji=1 pi > 2}, then 1 max , x ≤ j2 − 1. On the other hand, if x > 1, then from px + Cx−1 > 2 = Cx−1 we conclude that the second machine must be purchased at time x, i.e. x = j2 , a contradiction. Hence we conclude x = 1. It also follows that j2 = 2 since p1 = Cj12 −1 > 2. Noting that two machine loads are p1 and p2 respectively at time j2 = 2 no matter that p2 is assigned by Step 2.2 or 2.3, and that C H1 > L ≥ max{p1 , p2 }, we have l > j2 and thus 2 1 Cl−1 ≥ Cj22 > 2. By the definition of pl , we obtain pl + Cl−1 = C H1 , 1 2 H1 which implies P ≥ pl + Cl−1 + Cl−1 ≥ C + 2. Now we are easy to complete the proof. In fact, by P ≥ 2 + C H1 and H1 H1 +2 C H1 +2 10 H1 C ≤ 3, we have zz ∗ ≤ C2+P/2 ≤ 3+C 

H1 /2 < 9 . We assume m ≥ 3 in the remainder of this section. To get the desired competitive ratio, we need to better estimate the optimal value. This will be done by presenting lower bounds of the total job size P through carefully analyzing the online algorithm. Next Lemma 3.5 estimates the machine loads, and Lemma 3.6 provides lower bounds of P accordingly. Lemma 3.5 Cjim ≥ i, for i = 2, 3 · · · , m.

Preemptive online algorithms for scheduling with machine cost

325

Proof. We prove it by induction on k (k ≤ m), the current number of purchased machines by algorithm H1. Recall that machines are always purchased at Steps 2.2 and 2.3. We first consider the case k = 2, for which we need to show Cj22 ≥ 2. In fact, if pj2 is scheduled by Step 2.2, we have Cj22 = Cjmax ≥ (2−1)+1 = 2 2 −1 due to Remark 1(2). If pj2 is scheduled by Step 2.3, we also have Cj22 −1 = pj2 > Cjmax ≥ 2 due to Remark 1(3). Hence Cj22 ≥ 2. 2 −1 Assume that the result is true for k −1, that is, we have Cjik−1 ≥ i for 2 ≤ i ≤ k − 1, where 2 < k ≤ m. Since jk − 1 ≥ jk−1 , we have Cjik −1 ≥ i for max −C 1 2 ≤ i ≤ k−1. If pjk is scheduled by Step 2.2, that is, the portion Cj−1 j−1 of pj is scheduled onto the machine with minimum current load, we then know that its new load becomes Cjmax ≥ k (this machine becomes the most k −1 loaded and the k-th one after the machine order is re-indexed). As the loads of the remaining original k −2 machines are not changed when scheduling pjk , their loads are at least 2, · · · , k −1 respectively by the induction assumption. Hence by re-indexing the machine order according to their loads, we have Cjik ≥ i for 2 ≤ i ≤ k. If pjk is scheduled by Step 2.3, then the load of the new machine is Cjkk = pjk > Cjmax ≥ k due to Remark 1(3), and the k −1 loads of other k − 1 machines are not changed. Thus we have Cjik ≥ i for 2 ≤ i ≤ k, too. We thus conclude that the result is true for k, and the proof is complete. 

2 in this section. Denote x = Cj2m and y = Cl−1

Lemma 3.6 (1) P >

m2 +m+x2 −3x 2

(2) If C H1 = L, we have P > L +

+ Cj1m . m2 −m−2 . 2

(3) If C H1 > L and m < C H1 ≤ m + 1, we have P >

m2 +3m+y 2 −3y . 2

Proof. (1) As Cj1m ≤ Cj2m ≤ · · · ≤ Cjmm , and Cjim ≥ i for i = 2, 3, · · · , m according to Lemma 3.5, we get Cjim ≥ max{i, x}, for i = 2, 3, · · · , m. Denote x the largest integer no greater than x. We obtain P ≥

m  i=1

Cjim ≥ Cj1m +

x  i=2

= Cj1m

m 

i

i=x+1

(m + x + 1)(m − x) 2 2xx − 2x + m2 + m − x2 − x + 2 m2 + m − (x − x)2 + (x − x) + x2 − 3x + 2

= Cj1m + (x − 1)x + = Cj1m

x+

326

Y. Jiang, Y. He

≥ Cj1m

(since 0 ≤ x − x < 1) m2 + m + x2 − 3x . + 2

(2) We have Cni ≥ Cjim ≥ i, for i = 2, 3, · · · , m according to Lemma 3.5, and Cnm = C H1 = L by the assumption. Thus P > 2 + ··· + m − 1 + L = L +

m2 − m − 2 . 2

(3) From Lemma 3.5, we have Cjmm ≥ m. If Cjmm = m, from C H1 > m we have l > jm . If Cjmm > m, we show as follows that l > jm still holds. Recalling that a new machine is purchased for processing pjm , by Remarks 1(2) and (3), we know Cjmm = Cjmax or pjm . We distinguish two cases m −1 accordingly. Case 1. Cjmm = Cjmax . Hence Cjmax > m. From Lemma 3.2, we have m −1 m −1 m−1 max max  = m − 1. In Cjm −1 = Cjm −1 = pjm −1 by setting j = jm − 1 and m m max addition, we have Cjm ≥ pjm trivially, which implies pjm −1 = Cjm−1 = m −1 max . It states that the maximum current Cjmm ≥ pjm , i.e., Cjmm = pmax = p jm −1 jm load is equal to the largest size of all arrived jobs at time jm . As C H1 > L ≥ pmax jm , we obtain l > jm . m max Case 2. Cjmm = pjm . We obtain Cjmm = pjm = pmax jm since Cjm ≥ pjm trivially holds. By the assumption that C H1 > L ≥ pmax jm , we conclude that some jobs coming later than pjm must exist, i.e., l > jm . Now we are ready to obtain the result. As l − 1 ≥ jm , by the same argument as above we have that the total sizes of all arrived jobs at time 2 2 −3y 1 . Since again l > j , we conclude l − 1 is at least m +m+y + Cl−1 m 2 that pl must be scheduled by Step 2.1. Otherwise we would purchase a new 1 machine, a contradiction. Thus we have pl + Cl−1 = C H1 ∈ (m, m + 1] by the definition of pl . Hence

m2 + m + y 2 − 3y m2 + m + y 2 − 3y 1 + Cl−1 +m + pl > 2 2 m2 + 3m + y 2 − 3y . = 

2

P ≥

Lemma 3.7 If C H1 = L, the competitive ratio of algorithm H1 is at most √ 2 6+2 . 5 Proof. By Lemma 3.3(1),√we have L ≥ m, from which it follows that P < mL ≤ L2 , i.e., L > P . It is clear that z ∗ ≥ L+ PL due to Lemma 2.1,

Preemptive online algorithms for scheduling with machine cost

327

while z H1 = C H1 + m = L + m. According to Lemma 3.6(2), we have P > L + (m−2)(m+1) , and thus 2 √ 1+ m L+m L+m L+m 2 6+2 z H1 L , ≤ ≤ ≤ < 2 2 = 2 z∗ 5 L+ PL L+ 2L+m2L−m−2 L+ mL 1+ 12 ( m L) where the last inequality is due to

m L

≤ 1 and Lemma 2.4(1).



Lemma 3.8 If C H1 = m, the competitive ratio of algorithm H1 is at most √ 2 6+2 . 5 √ √ √ Proof. If P ≥ ( 3 − 1)2 m2 , we have z ∗ ≥ 2 P ≥ 2( 3 − 1)m by H1 Lemma 2.1. Combining it with z H1 = C H1 + m = 2m, we get zz ∗ ≤ √2m 2( 3−1)m

=

√ 1+ 3 2

<

√ 2 6+2 . 5

Hence we suppose

√ P < ( 3 − 1)2 m2 .

(1) 2

On the other hand, by Lemma 3.6(1) we have P > m +m+x 2 2 . Hence ing it with x = Cj2m ≥ 2, we have P > m +3m−2 2 √ m2 + 3m − 2 < ( 3 − 1)2 m2 . 2

2 −3x

. Combin-

(2)

It is clear that the integer solution of Inequality (2) is {m|m ≥ 12 or m ≤ 2, m is an integer}, thus we only need to consider √ the case of m ≥ 12 because of Lemma 3.4. We first prove 2 ≤√x < (2 − 3)m. In fact, x ≥ √ 2 is trivially true, and (2 − 3)m > 2 holds due to m ≥ 12. If x ≥ (2 − 3)m > 2, by Lemmas 3.6(1) and 2.4(2), we conclude that √ 2 2 −3x P > m +m+x > ( 3 − 1)2 m2 , which contradicts Inequality (1). 2 √ Hence we have obtained 2 ≤ x < (2 − 3)m. We return to prove the lemma. Since Cj1m −1 ≤ x and Cj1m −1 + pjm > max Cjm −1 ≥ (m − 1) + 1 = m, we have pjm > m − x, and thus pjm > √ √ √ √ m − (2 − 3)m = ( 3 − 1)m > P (because of x < (2 − 3)m and Inequality (1)). It implies that z ∗ ≥ pjm + pPj due to Lemma 2.1. Thus we m obtain √ 2m 2m 2m 2 6+2 z H1 , ≤ ≤ ≤ 2 2 −3x < P z ∗ pjm + pP 5 m−x+ m−x m−x+ m +m+x 2(m−x) jm

where the last inequality is directly from Lemma 2.4(3).



H1 ≤ m + 1, the competitive ratio of Lemma 3.9 If C H1 > L and √ m
328

Y. Jiang, Y. He

Proof. We show the result by an argument similar to what we have used H1 in the proof of Lemma 3.8. Let m = m+C . Then the objective value of 2 H1 H1  algorithm H is z = m + C = 2m , which is parallel to the objective value z H1 = 2m in that proof. By the assumption, we have C H1 ≤ m + 1, 2 which implies m ≤ 2m+1 2 . By a simple calculation, we have m + 3m > 2 2 −3y > m 2 + m . Combining it with Lemma 3.6(3), we get P > m +3m+y 2 2 2 −3x m 2 +m +y 2 −3y , which is parallel to P > m +m+x in that proof. Further, 2 2 C H1 +m H1  − y = m − y, which is parallel to we have pl > C − y > 2 pjm > m − x in that proof, too. Hence we can obtain the result similarly.



Theorem 3.10 Algorithm H1 has a competitive ratio of at most

√

2 6+2 . 5

Proof. The competitive ratio is obtained directly from Lemmas 3.4, 3.7–3.9. 

Through Lemma 2.3 and Theorem 3.10, we conclude that for preemptive List Model problem, the gap between the competitive ratio of H1 and the lower bound is about 0.0465. Hence algorithm H1 is almost optimal. 4 (Non-) Preemptive semi-online problem with decreasing sizes In this section, we assume that jobs come in an order of their non-increasing sizes, which implies L = p1 . We present an optimal algorithm H2 with a competitive ratio of 4/3. The algorithm does not introduce any preemption, hence it is even optimal for non-preemptive problem. In this section, we define time j as the moment right after the j-th job has been scheduled, and denote by Cjmin the minimum current load over all purchased machines at time j. Algorithm H2 1. Purchase the first machine to process job p1 . Let j = 2 and k = 1. min + p ≤ max{p , k} + 1, then assign job p to the machine with 2. If Cj−1 j 1 j minimum current load, and go to 4; Else go to 3. 3. Purchase a new machine and assign pj to it. Set k = k + 1, and go to 4. 4. Set j = j + 1, if no new job comes, stop. Otherwise, go to 2. Lemma 4.1 If m ≤ 2, the competitive ratio of algorithm H2 is at most 4/3. Proof. For m = 1, it is clear that z H2 = P + 1. By the algorithm rule, we have P ≤ max{p1 , m} + 1 = max{p1 + 1, 2}. (3)

Preemptive online algorithms for scheduling with machine cost

329

It implies m∗ ≤ 2 (otherwise z ∗ ≥ z H2 ). We thus obtain z ∗ ≥ min{P + 1, max{p1 + 2, P/2 + 2}}. If P ≤ p1 + 1, i.e., P + 1 ≤ p1 + 2, then z ∗ ≥ min{P + 1, p1 + 2} = P + 1 = z H2 . Otherwise, by Inequality (3), we have P ≤ 2, i.e., P + 1 ≤ P/2 + 2. Thus we obtain z ∗ ≥ min{P + 1, P/2 + 2} = P + 1 = z H2 , which means that algorithm H1 yields an optimal solution when m = 1. For m = 2, we have C H2 ≤ max{p1 + 1, 3}. By the algorithm rule of purchasing the second machine, we have P > 2. Three cases are considered by distinguishing the value of p1 . Case 1. p1 ≥ 2. If m∗ = 1, z ∗ = P + 1 > C H2 + 1. We obtain p1 + 2 z H2 C H2 + 2 C H2 + 2 4 ≤ = < ≤ . ∗ H2 z P +1 C +1 p1 + 1 3 If m∗ ≥ 2, we have z ∗ ≥ p1 + 2, while z H2 = C H2 + 2 ≤ p1 + 3. It follows H2 5 that zz ∗ ≤ pp11 +3 +2 ≤ 4 due to p1 ≥ 2. Case 2. 1 ≤ p1 < 2. Clearly C H2 ≤ 3. If C H2 ≤ 2, then z H2 = C H2 + 2 ≤ 4 while z ∗ ≥ min{P + 1, min{p1 + i : i ≥ 2}} ≥ 3. It follows H2 that zz ∗ ≤ 43 . Hence we assume 2 < C H2 ≤ 3. (I) If m∗ ≥ 3, we have C H2 +2 5 z H2 ∗ ∗ H2 + 1 holds trivially. z ∗ ≤ p1 +3 ≤ 4 . (II) If m = 1, z = P + 1 ≥ C H2

H2

+2 It follows that zz ∗ ≤ C < 43 due to C H2 > 2. (III) Last, we assume C H2 +1 ∗ m = 2. Recall that pl determines the makespan of algorithm H2. If pl is 2 1 assigned to the first machine, then Cl−1 ≥ Cl−1 ≥ p1 , which follows that 1 2 H2 2 P ≥ Cl + Cl ≥ C + p1 . Otherwise, P ≥ Cl + Cl1 ≥ C H2 + p1 holds obviously. Therefore,

z H2 C H2 + 2 ≤ = P z∗ 2 +2

C H2 + 2 C H2 2

+

p1 2

+2

<

C H2 + 2 C H2 2

+

5 2

4 < . 3

Case 3. 0 < p1 < 1. Then C H2 ≤ 3 and thus P ≤ 6. If m∗ ≥ 4, then C H2 +2 5 z H2 ∗ ∗ z ∗ ≤ C ∗ +4 < 4 . If m ≤ 3, then z ≥ min{P/i + i : i = 1, 2, 3} = P/2 + 2. Since pl determines the makespan of H2 and pl < p1 < 1, we get P > C H2 + (C H2 − pl ) > 2C H2 − 1. Therefore, we have z ∗ > C H2 + 3/2 H2 H2 +2 and thus zz ∗ < CCH2 +3/2 < 43 . 

In the remainder of this section, we assume m ≥ 3. Similarly to Sect. 3, we first present lower bounds of P in next two lemmas by analyzing algorithm H2. Lemma 4.2 (1) If m < p1 +1, we have Cjim > and P > p1 +

(p1 +1)(m−1) . 2

(2) If m ≥ p1 + 1, we have Cjim >

m 2

p1 +1 2

for i = 1, 2, · · · , m−1,

for i = 1, 2, · · · , m − 1, and P >

m2 2 .

330

Y. Jiang, Y. He

Proof. Since only m − 1 machines have been purchased at time jm − 1, we have pjm +Cjim −1 > max{p1 , m−1}+1. Moreover, Cjim −1 ≥ pjm for i = 1, 2, · · · , m − 1, since jobs come in order of non-increasing sizes. It follows that 2Cjim = 2Cjim −1 > max{p1 + 1, m}, that is, Cjim > max{ p12+1 , m 2} for i = 1, 2, · · · , m − 1. Therefore, we obtain ) + (Cjm−1 + Cjmm ) P ≥ Cj1m + (Cj2m + · · · + Cjm−2 m m (m − 3)(p1 + 1) + p1 + 1 2 (p1 + 1)(m − 1) , = p1 + 2

> p1 +

and P ≥ (Cj1m + · · · + Cjm−2 ) + (Cjm−1 + Cjmm ) > m m

m2 (m − 2)m +m= . 2 2 

Lemma 4.3 If Cjim >

2m 3

for i = 1, 2, · · · , m − 1, we have:

(1) when C H2 > m and l > jm , P > (2) when C H2 ≤ m, P >

2m2 −3m 3

2m2 −2m 3

+ C H2 holds;

+ C H2 holds.

Proof. (1) If C H2 is achieved on one of the first m − 1 machines, then from m ≥ C i > 2m for l > jm and the rule of assigning pl , we conclude that Cl−1 jm 3 2

H2 = 2m −2m + C H2 . If i = 1, 2, · · · , m − 1. Thus, P ≥ (m − 1) 2m 3 +C 3 H2 = C H2 is achieved on the last machine, it is clear that P ≥ (m−1) 2m 3 +C 2 2m −2m + C H2 . 3

(2) If C H2 is achieved on one of the first m − 1 machines, according to pjm + Cjim −1 > max{p1 , m − 1} + 1 ≥ m for i = 1, · · · , m − 1, we 2

H2 = 2m −3m + C H2 . Otherwise, we have have P > (m − 3) 2m 3 +m+C 3 H2 = 2m2 −2m + C H2 > 2m2 −3m + C H2 . + C 

P ≥ (m − 1) 2m 3 3 3

Lemma 4.4 If m ≥ p1 + 1, the competitive ratio of H2 is at most 4/3. Proof. Clearly C H2 ≤ m + 1 and z H2 ≤ 2m + 1. We distinguish two cases according to the value of pjm . i Case 1. pjm ≤ m 3 . Since Cjm −1 + pjm > m for i = 1, 2, · · · , m − 1, H2 > m, we must have we have Cjim = Cjim −1 > m − pjm ≥ 2m 3 . If C l > jm . Otherwise, we have C H2 ≤ max{p1 + 1, (m − 1) + 1} = m,

Preemptive online algorithms for scheduling with machine cost

a contradiction. Then by Lemma 4.3(1), we have P > Combining it with Lemmas 2.1 and 2.6(1), we obtain

331 2m2 −2m 3

+ C H2 .

z H2 C H2 + m 4 C H2 + m √ ≤ ≤ . ≤ ∗ 2 z 3 2 P 2 2m 3−2m + C H2 2

If C H2 ≤ m, similarly we know P > 2m 3−3m + C H2 from Lemma 4.3(2). Thus we obtain C H2 + m 4 z H2 ≤ ≤ 2 z∗ 3 2 2m −3m + C H2 3

by Lemmas 2.1 and 2.6(2). H2 ≤ m + 1, we have P ≤ m(m + 1). If Case 2. pjm > m 3 . Since C 2 2 P ≥ m , i.e., m ≤ P ≤ m(m + 1), then m = m0 due to the definition of m0 . According to Lemma 2.2(1), we have z ∗ ≥ mP0 + m0 ≥ m + m = 2m, H2

4 2 and thus zz ∗ ≤ 2m+1 2m < 3 . Hence we assume P < m in the following. Since pjm > m 3 , and each of the first m − 1 machines has a load no greater than max{p1 + 1, (m − 1) + 1} = m at time jm , we conclude that each of these machines has at most two jobs in algorithm H2. Therefore we assume that at time jm , there are m1 machines (and must be the first m1 machines, according to the rule of H2 and the non-increasing job sizes), each of which has processed only one job, and m2 = m − 1 − m1 machines (i.e., the last m2 machines of the first m − 1 machines), each of which has processed just two jobs. Let

S1 = {pi : pi is processed on the first m1 machines at time jm − 1} and S2 = {pi : pi is processed on the last m2 machines of the first m − 1 machines at time jm − 1 }. It is clear that pi > max{p1 + 1, m} − pjm ≥ max{p1 + 1, m} − pi , i.e., pi > 12 max{p1 + 1, m} = m 2 for pi ∈ S1 ; and similarly pj ≥ pjm > 1 m m 3 max{p1 + 1, m} = 3 for pj ∈ S2 . It also implies that p1 ≥ 2 . If S1 = ∅, i.e., every of the first m − 1 machines has just two jobs at time jm − 1, then we have Cjim ≥ 2pjm > 2m 3 for i = 1, · · · , m − 1, which implies the desired competitive ratio by the same argument as that in Case 1. Therefore we assume S1 = ∅ in the remainder of the proof. Now we have the following proposition: Proposition 4.1 If pjm > 13 m and m∗ < m, we have C ∗ > m and z ∗ ≥ P m + m.

332

Y. Jiang, Y. He

Proof. We show C ∗ > m by contradiction. Suppose C ∗ ≤ m, and consider   the assignment for the jobs of S1 S2 {pjm } in the optimal solution. Since S1 = ∅, it is clear that for any two jobs pi , pj ∈ S1 , we have pi + pj > m/2 + m/2 = m, and for any pi ∈ S1 and pj ∈ S2 , we have pi + pj ≥ pi + pjm > max{p1 + 1, m} ≥ m by the definition of pjm . Thus we conclude that any job pi ∈ S1 cannot share a machine with any other job   of S1 S2 {pjm } in the optimal solution, which follows that there is at least m1 machines to process the jobs inset S1 . It is clear that no machine can process more than two jobs in S2 {pjm } to avoid C ∗ > m. Since there are 2m2 + 1 jobs in S2 {pjm }, we conclude that at least m2 + 1 other machines are required to process those jobs in the optimal solution. Thus we have m∗ ≥ m1 + (m2 + 1) = m, a contradiction. We thus obtain C ∗ > m. Since the makespan of the optimal solution is C ∗ , we know that the number of machines purchased in the optimal solution is at least  CP∗ , which √ P +m (since C ∗ > m > P ). follows that z ∗ ≥ C ∗ + CP∗ ≥ C ∗ + CP∗ ≥ m 

Now we return to the proof of Case 2. It is clear that C ∗ > L = p1 > m 2. z H2 C H2 +m m+m 4 H2 ∗ (I) If C ≤ m and m ≥ m, we have z ∗ ≤ C ∗ +m∗ ≤ m/2+m = 3 . (II)

P + m. If C H2 ≤ m and m∗ < m, from Proposition 4.1 we have z ∗ ≥ m m2 z H2 C H2 +m Meanwhile, by Lemma 4.2(2), we have P > 2 . Thus z ∗ ≤ P/m+m ≤ m+m 4 H2 > m. We can conclude l > j m m/2+m = 3 . (III) Last, we assume that C in the same way as that in Case 1. Since algorithm H2 schedules job pl on i the machine with the minimum current load, we have Cl−1 + pl ≥ C H2 , H2 i i . Thus for i = 1, · · · , m. It follows that Cl−1 ≥ C 2 due to pl ≤ Cl−1 H2 H2 . If m∗ ≥ m + 1, we have z H2 ≤ P > C H2 + (m − 1) C 2 = m+1 2 C z∗ z H2 2m+1 4 ∗ = m, z ∗ ≥ P + m trivially. If m∗ < m, ≤ < . If m C ∗ +m∗ 3 m m/2+m+1

we get z ∗ ≥ obtain

P m

+ m by Proposition 4.1, too. Then for m∗ ≤ m, we always

z H2 C H2 + m ≤ ≤ P z∗ m +m ≤

C H2 C H2 2

+

C H2 + m (m+1)C H2 2m

+m 1 2

+m

<

+m

4 m+1+m < , 1 3 + 2 +m

m+1 2

H2 , the third one is from where the second inequality is from P > m+1 2 C H2 H2 > m, and the fourth one is due to C ≤ m + 1. We thus complete C the proof of Lemma 4.4. 

Lemma 4.5 If m < p1 + 1, the competitive ratio of H2 is at most 4/3.

Preemptive online algorithms for scheduling with machine cost

333

Proof. Clearly C H2 ≤ max{m + 1, p1 + 1}. Case 1. C H2 > p1 + 1. Then we have m < p1 + 1 < C H2 ≤ m + 1, from which it follows that l > jm (otherwise, C H2 ≤ max{p1 + 1, (m − 1) + 1)} = p1 +1, a contradiction). (I) If pjm ≤ p13+1 , then from Cjim −1 +pjm > p1 + 1 for i = 1, 2, · · · , m − 1, we have 2(p1 + 1) 2m ≥ , i = 1, 2, · · · , m − 1. 3 3 Hence the conditions of Lemma 4.3(1) are satisfied. It follows that P > √ 2m2 −2m H2 . Noting that the optimal value z ∗ ≥ 2 P according to + C 3 Lemma 2.1, we have Cjim = Cjim −1 > p1 + 1 − pjm ≥

z H2 C H2 + m 4 C H2 + m √ ≤ ≤ ≤ 2 −2m z∗ 3 2m 2 P 2 + C H2 3 by Lemma 2.6(1). (II) If pjm > p13+1 , by the similar argument as that of Case 2 in Lemma 4.4, we can assume that P < m2 . pjm > p13+1 implies that none of the first m − 1 machines has at least 3 jobs at time jm in H2. Then we define similarly the sets S1 and S2 . It follows that pi > m 2 for m m pi ∈ S1 , pj ≥ pjm > 3 for pj ∈ S2 , and p1 ≥ 2 . Moreover, we can assume S1 = ∅, too. Parallel to Proposition 4.1, we have Proposition 4.2 If pjm > P z∗ ≥ m + m.

p1 +1 3

and m∗ < m, we have C ∗ > m and

By the same arguments as what we have used in the last paragraph of the proof of Lemma 4.4 (i.e., Case 2(III) in that proof), we can obtain the desired competitive ratio with the help of Propositionï 4.2 (Note that only C H2 ≥ m is needed to consider at this time). P ∗ m0 , we have z ≥ (p +1)(m−1) P 1 , p1 +p1 by Lemma 2.2(2). By Lemma 4.2(1), we have P > p1 + 2 P m+1 m−1 m−1 i.e., p1 > 2 + 2p1 . Let p1 = xm with some x ≥ m . We have

Case 2. C H2 ≤ p1 + 1. Then z H2 ≤ p1 + m + 1. If p1 >

z H2 C H2 + m < ≤ P z∗ p1 + p1

p1 + 1 + m m+1 m−1 2 + 2p1 + p1

=

xm + 1 + m 1 xm + m+1 2 + 2x −

1 2xm

4 ≤ , 3

where the last inequality is from Lemma 2.5(3). Hence we suppose p1 ≤ mP0 . Since p1 ≤ mP0 , and mP0 ≤ m0 + 1 (according to the definition of m0 ), we have m0 + 1 ≥ p1 > m − 1, i.e., m0 ≥ m − 1. Lemma 2.2(1) states that z ∗ ≥ mP0 + m0 . Thus if m ≥ 4, we have 4 z H2 C H2 + m p1 + 1 + m 2 2 ≤ . ≤ P ≤ =1+ <1+ ∗ z p1 + m − 1 p1 + m − 1 2(m − 1) 3 m + m0 0

334

Y. Jiang, Y. He

Hence we only need to consider Case 2 when m = 3. We first show P ≥ 2C H2 to reach the conclusion. (I) If C H2 is achieved on the first machine, we have P ≥ Cl1 +(Cj2m −1 +pjm ) > C H2 + max{p1 , m−1}+1 = C H2 +p1 + 1 ≥ 2C H2 due to the assignment rule of pjm . (II) If C H2 is achieved on the second machine, similarly we have P ≥ Cl2 + (Cj1m −1 + pjm ) > C H2 + max{p1 , m − 1} + 1 ≥ 2C H2 . (III) If C H2 is achieved on the third machine, we must have l ≥ jm . Moreover, we have that Cjim −1 ≥ pjm and Cjim + pjm > C H2 for i = 1, 2. It follows that P > Cj1m + Cj2m + Cl3 ≥ Cj1m + pjm + Cl3 > 2C H2 , too. Hence we obtain P ≥ 2C H2 . Now we are ready to get the result for Case 2 when m = 3. m = 3 implies m0 ≥ m − 1 = 2. If m0 = 2, mP0 + m0 = P2 + 2 ≥ C H2 + 2. By p1 > m − 1 = 2, we have C H2 + m C H2 + 3 z H2 1 ≤ ≤ = 1 + H2 P ∗ H2 z C +2 C +2 m0 + m0 4 1 1 < . <1+ ≤1+ p1 + 2 2+2 3 If m0 ≥ m = 3, we also have z H2 1 4 C H2 + m p1 + 1 + 3 =1+ < , ≤ ≤ P ∗ z p1 + 3 p1 + 3 3 m0 + m0 where the first inequality holds because of p1 ≤ mP0 and the case’s assump

tion of C H2 ≤ p1 + 1. We thus complete the proof of Lemma 4.5. Theorem 4.6 Algorithm H2 has a competitive ratio of 4/3, and thus optimal. Proof. The competitive ratio is directly from Lemmas 4.1, 4.4 and 4.5, and the optimality follows from Lemma 2.3. 

5 Preemptive semi-online problem with known largest size In this section, we assume that the largest job size is known in advance. We are devoted to presenting an optimal preemptive semi-online algorithm with a competitive ratio of 4/3. Noting that the problem with known largest

Preemptive online algorithms for scheduling with machine cost

335

size can be viewed as a relaxation of the problem with decreasing sizes, we know that the algorithm is also optimal for the preemptive problem with decreasing sizes. Considering that D´osa and He [3] presented an optimal non-preemptive online algorithm with a competitive ratio of 4/3 for the case where each job has a size no greater than 1. Hence in the following we assume L > 1. Denote by t = L the smallest integer no less than L. Then t ≥ 2. The definition of time j is the same as that in Sect. 3. Algorithm H3 1. Purchase the first machine to process job p1 . Let j = 2 and k = 1. 2. For pj (j ≥ 2): 1 + p ≤ max{t, k}, schedule p completely onto the machine 2.1. If Cj−1 j j with minimum current load, and go to 3. 1 1 2.2. If Cj−1 + pj > max{t, k}, schedule max{t, k} − Cj−1 portion of pj onto the machine with minimum current load, and the remainder of pj onto a new machine. Set m = m + 1, and go to 3. 3. Re-index the machines with respect to their current loads such that Cj1 ≤ Cj2 ≤ · · · ≤ Cjk , and go to 4. 4. Set j = j + 1, if no new job comes, stop. Otherwise, go to 2. It is clear that the makespan of H3 is at most max{t, m} after all jobs are completed. Analogous to the proof of Lemma 3.1, we get Lemma 5.1 Algorithm H3 is well-defined, that is, the time slots assigned to any job pj never overlap. Lemma 5.2 If m ≤ 2, the competitive ratio of algorithm H3 is at most 4/3. Proof. If m = 1, it is obvious that P = Cn1 ≤ max{t, m} = t ≤ L + 1 by the algorithm rule. It follows that z ∗ ≥ min{P + 1, L + 2} = P + 1 = z H3 . If m = 2, i.e., t ≥ m, we then obtain z H3 = max{t, m} + 2 = t + 2. On the other hand, the optimal value is at least min{P + 1, L + 2} ≥ min{t + 1, L + 2}. Because 1 4 t+2 t−L 1 4 t+2 =1+ ≤ and =1+ ≤1+ = , t+1 t+1 3 L+2 L+2 3 3 we obtain

z H3 z∗

≤ 34 .



From now on, we assume m ≥ 3. Lemma 5.3 If m ≤ t, the competitive ratio of algorithm H3 is at most 4/3. Proof. We have z H3 = max{t, m} + m = t + m due to m ≤ t. We next give a lower bound of P .

336

Y. Jiang, Y. He

Since max{t, m} = t, according to the algorithm rule of H3 we can observe that: the algorithm always schedules an incoming job onto the machine with minimum current load until its new load achieves t, and then it schedules the leftover of the job (if any) onto a new machine. Because totally m machines are purchased, we can conclude that there are at least m − 1 machines having a load t. It follows that P > t(m − 1). To obtain the desired competitive ratio, two cases are considered according to the value of P . √ Case 1. P > L2 . If L > 3, we have z ∗ ≥ 2 P ≥ 2L by Lemma 2.1. We thus obtain 4 t+m z H3 2t t−L ≤ . ≤ √ ≤ =1+ z∗ 2L L 3 2 P If L ≤ 3, i.e., t ≤ 3, we have t = 3 due to the assumption that √m =  √ t ≥ m ≥ 3. It follows that z ∗ ≥ 2 P ≥ 2 t(m − 1) = 2 6. Because H3 6 < 43 . z H3 = t + m = 6, we get zz ∗ ≤ 2√ 6 √ √ Case 2. P ≤ L2 . If m ≥ 4, we have L ≥ P > 3t > 3 since P > t(m − 1) ≥ 3t and t ≥ m. Then according to Lemma 2.1 we have z ∗ ≥ L + PL > L + t(m−1) ≥ L + m − 1. Hence L t−L+1 t−L+1 2 4 z H3 t+m =1+ <1+ ≤1+ = . ≤ ∗ z L+m−1 L+m−1 L+3 6 3 If m = 3, P > t(m − 1) = 2t. Hence P + 2, min{L + i}} i≥3 2 ≥ min{2t + 1, t + 2, min{L + i}} = min{t + 2, L + 3}.

z ∗ ≥ min{P + 1,

i≥3

Because z H3 = t + 3, and 4 t+3 t−L 4 t+3 1 < , ≤1+ < , =1+ t+2 t+2 3 L+3 L+3 3 we get

z H3 z∗

< 43 .



Next Lemmas 5.4–5.5 give lower bounds of P for the case of m > t. Noting that the maximum current load is max{t, m−1} at time jm according to Step 2.2, we have C H3 ≥ max{t, m − 1} ≥ m − 1 if m > t (i.e., m − 1 ≥ t). Lemma 5.4 Assume t < m ≤ 2t. Then we have: (m2 +t2 )−(m+t) ; 2 (m2 +t2 )+(m−t−2) . 2

(1) P >

(2) If further C H3 > m − 1, then P >

Preemptive online algorithms for scheduling with machine cost

337

Proof. (1) By a similar argument as that in the proof of Lemma 5.3 (for proving P > t(m − 1)), we obtain that, when purchasing t-th machine, the current load of each purchased machine is t except for the machine with minimum current load. Further, right after we purchase the k-th (k > t) machine to process a job, the minimum machine load over the k − 1 earlypurchased machine is increased to k −1. Thus at time l, we know that Cli ≥ t for 2 ≤ i ≤ t + 1, and Cli ≥ i − 1 for t + 2 ≤ i ≤ m, which imply P =

m  i=1

Cni

>

m  i=2

Cli

t+1 

≥

i=2

Cli

+

m  i=l+2

Cli

(t + m)(m − t − 1) (m2 + t2 ) − (m + t) ≥ t2 + = . 2 2

(4)

(2) Since the maximum current load is max{t, m − 1} = m − 1 at time jm and C H3 > m − 1, we know that there must exist some jobs arriving later than pjm , i.e., l > jm . By the same argument as above, we have that at time l − 1, m machines have been purchased and the sum of current machine 2



2

1 loads except Cl−1 is at least (m +t )−(m+t) = P1 . Furthermore, since no 2 more machine is purchase after time jm , pl must be scheduled by Step 2.1. That is to say, pl is scheduled completely onto the machine with minimum current load. Therefore we have

(m2 + t2 ) − (m + t) +m−1 2 (m2 + t2 ) + (m − t − 2) . = 

2 Lemma 5.5 Assume m > 2t. Then we have: 1 P > P1 + Cl−1 + pl = P1 + C H3 >

2m2 +t2 −2mt+3t−4m+2 . 2 2m2 +t2 −2mt+3t−2m . 2

(1) P >

(2) If further C H3 > m − 1, then P >

Proof. (1) It is clear that the difference between the largest and smallest loads over the k − 1 early-purchased machines is less than L when we need to purchase the k-th machine (otherwise we do not need to purchase a new machine). Then after scheduling all jobs, except for the machine with minimum current load, each machine has a load satisfying Cni ≥ max{i − 1, m − 1 − L}, i.e., Cni ≥ m − 1 − L for 2 ≤ i ≤ m − t, and Cni ≥ i − 1 for m − t + 1 ≤ i ≤ m. Hence P >

m  i=2

Cni ≥

m−t  i=2

Cni +

m  i=m−t+1

≥ (m − 1 − L)(m − t − 1) +

Cni

t(2m − t − 1) 2

338

Y. Jiang, Y. He

≥

2m2 + t2 − 2mt + 3t − 4m + 2 . 2

(2) Analogous to the proof of Lemma 5.4(2), we obtain P >

2m2 +t2 −2mt+3t−2m 2m2 +t2 −2mt+3t−4m+2 +m−1 = . 2 2



Lemma 5.6 If m > t, the competitive ratio of algorithm H3 is at most 4/3. Proof. Recall that C H3 ≥ m − 1 and C H3 ≤ max{m, t} = m, since m > t. Two cases are considered according to the value of C H3 . Case 1. C H3 = m − 1. We have z H3 = 2m − 1. According to Lemmas 2.1, 5.4(1) and 5.5(1), we have     (m2 + t2 ) − (m + t)   , 2   √ 2 z∗ ≥ 2 P >     2m2 + t2 − 2mt + 3t − 4m + 2   , 2

2

for m ≤ 2t, for m > 2t.

Then by Lemma 2.6(1), we have

 2m − 1 4   ≤ ,  2 +t2 )−(m+t)  (m 3 2

z H3 2 < 2m − 1 4  z∗  ≤ ,    3 2m2 +t2 −2mt+3t−4m+2 2 2

for m ≤ 2t, for m > 2t.

Case 2. m − 1 < C H3 ≤ m. We have z H3 ≤ 2m. Similarly according to Lemmas 2.1, 5.4(2) and 5.5(2), we have     (m2 + t2 ) + (m − t − 2)   , 2   √ 2 ∗ z ≥2 P >     2m2 + t2 − 2mt + 3t − 2m   , 2

2

for m ≤ 2t, for m > 2t,

Then by Lemma 2.6(2), we have  2m 4   ≤ ,  2 2  3  2 (m +t )+(m−t−2)

for m ≤ 2t, z H3 2 < 4 2m  z∗  ≤ , for m > 2t.   2 2  3 2 2m +t −2mt+3t−2m 2 

Preemptive online algorithms for scheduling with machine cost

339

Theorem 5.1 Algorithm H3 has a competitive ratio of 4/3 and thus optimal. Proof. The competitive ratio is directly from Lemmas 5.2, 5.3 and 5.6, and the optimality follows from Lemma 2.3. 

6 Conclusion In this paper, we considered the preemptive List Model problem. We√presented a preemptive online algorithm with a competitive ratio of (2 6 + 2)/5 ≈ 1.3798 while the lower bound is 4/3. Compared with the gap (≈ 0.2465) between upper and lower bounds for the non-preemptive List Model problem, our gap (≈ 0.0465) is much smaller. To further shed light on the relations between algorithm performance and partial available information on jobs, we considered the problem in different semi-online environments. For the semi-online problem with decreasing sizes, we designed an optimal algorithm with a competitive ratio of 4/3. The algorithm does not introduce any preemption, and hence is also optimal semi-online algorithm for non-preemptive semi-online problem. It improves the known upper bound of 3/2. For the semi-online problem with known largest size, we presented an optimal preemptive algorithm with a competitive ratio of 4/3. To the author’s best knowledge, no optimal preemptive and non-preemptive algorithm was ever appeared in literature for the List Model problem so far. The algorithms for the considered problems consist of two parts, a purchasing strategy, which decides when to purchase new machines, and a scheduling algorithm, which assigns jobs to machines. To get near-optimal online algorithm and optimal semi-online algorithms, we designed new purchasing strategies, which depended on the current makespan, the number of currently purchased machines and the largest job size (if it is known). Although the scheduling algorithms are simple greedy-like procedures (something like LS algorithm with or without preemption), it is strong enough to get near optimal and even optimal algorithms. This is quite different from the classical online scheduling problems P m||Cmax and P m|pmpt|Cmax where greedy-like procedures are not optimal. It may conclude that for the List Model problem, purchasing strategy is more crucial than scheduling algorithm. Note that for the online problem P m|pmpt|Cmax , Chen et al. [2] proposed an optimal online algorithm which has a competitive ratio of e/(e √ − 1) ≈ 1.5820. Comparing it with the obtained upper bound of (2 6 + 2)/5 ≈ 1.3798 for the preemptive List Model problem, we conclude that adding machine cost greatly decreases the competitive ratio (i.e., improves the performance guarantee).

340

Y. Jiang, Y. He

The results of this paper suggest a number of problems deserving further study. An important and natural open question is to design an optimal preemptive online algorithm. On the other hand, as Seiden [13] presented a randomized lower bound of 1.06532 for the non-preemptive List Model problem, which is strictly smaller than the lower bound of the preemptive List Model problem, it is interesting to know whether randomization is really helpful for the preemptive List Model problem. References 1. Cai, S.Y., He, Y. (2003) Semi-online algorithms for scheduling non-increasing processing jobs with processor cost. Acta Automatica Sinica 29: 917–921 (in Chinese) 2. Chen, B., van Vliet, A., Woeginger, G. (1995) An optimal algorithm for preemptive on-line scheduling. Operations Research Letters 18: 127–131 3. D´osa, G., He, Y. (2004) Better on-line algorithms for scheduling with machine cost. SIAM Journal on Computing 33: 1035–1051 4. D´osa, G., He, Y. (2004) Semi-online algorithms for parallel machine scheduling problems. Computing 72: 355–363 5. Epstein, L. (2003) Bin stretching revisited. Acta Informatica 39: 97–117 6. Graham, R.L. (1969) Bounds on multiprocessing finishing anomalies. SIAM Journal on Applied Mathematics 17: 416–429 7. He,Y., Cai, S.Y. (2002) Semi-online scheduling with machine cost. Journal of Computer Science and Technology 17: 781–787 8. He, Y., Jiang, Y.W. (2004) Optimal algorithms for semi-online preemptive scheduling problems on two uniform machines. Acta Informatica 40: 367–383 9. He,Y., Zhang, G. (1999) Semi-online scheduling on two identical machines. Computing 62: 179–187 10. Imreh, C., Noga, J. (1999) Scheduling with machine cost. In: Proc. of RANDOMAPPROX’99 (Lecture Notes in Computer Science 1671). Springer, Berlin Heidelberg New York 1999, pp. 168–176 11. Kellerer, H., Kotov, V., Speranza, M.R., Tuza, Z. (1997) Semi on-line algorithms for the partition problem. Operations Research Letters 21: 235–242 12. Panwalker, S., Liman, S.D. (2002) Single operation earliness-tardiness scheduling with machine activation costs. IIE Transactions 34: 509–513 13. Seiden, S. (2000) A guessing game and randomized online algorithms. In: Proceedings of the 32nd Annual ACM Symposium on the Theory of Computing, ACM, New York 2000, pp. 592–601