LIN Ling, TAN Zhi-yi, HE Yong. Deterministic and randomized scheduling problems under the lp norm on two identical machines[J]. Journal of Zhejiang University Science A, 2005, 6(1): 20-26.
@article{title="Deterministic and randomized scheduling problems under the lp norm on two identical machines", author="LIN Ling, TAN Zhi-yi, HE Yong", journal="Journal of Zhejiang University Science A", volume="6", number="1", pages="20-26", year="2005", publisher="Zhejiang University Press & Springer", doi="10.1631/jzus.2005.A0020" }
%0 Journal Article %T Deterministic and randomized scheduling problems under the lp norm on two identical machines %A LIN Ling %A TAN Zhi-yi %A HE Yong %J Journal of Zhejiang University SCIENCE A %V 6 %N 1 %P 20-26 %@ 1673-565X %D 2005 %I Zhejiang University Press & Springer %DOI 10.1631/jzus.2005.A0020
TY - JOUR T1 - Deterministic and randomized scheduling problems under the lp norm on two identical machines A1 - LIN Ling A1 - TAN Zhi-yi A1 - HE Yong J0 - Journal of Zhejiang University Science A VL - 6 IS - 1 SP - 20 EP - 26 %@ 1673-565X Y1 - 2005 PB - Zhejiang University Press & Springer ER - DOI - 10.1631/jzus.2005.A0020
Abstract: Parallel machine scheduling problems, which are important discrete optimization problems, may occur in many applications. For example, load balancing in network communication channel assignment, parallel processing in large-size computing, task arrangement in flexible manufacturing systems, etc., are multiprocessor scheduling problem. In the traditional parallel machine scheduling problems, it is assumed that the problems are considered in offline or online environment. But in practice, problems are often not really offline or online but somehow in-between. This means that, with respect to the online problem, some further information about the tasks is available, which allows the improvement of the performance of the best possible algorithms. Problems of this class are called semi-online ones. In this paper, the semi-online problem P2|decr|lp (p>1) is considered where jobs come in non-increasing order of their processing times and the objective is to minimize the sum of the lp norm of every machine’s load. It is shown that LS algorithm is optimal for any lp norm, which extends the results known in the literature. Furthermore, randomized lower bounds for the problems P2|online|lp and P2|decr|lp are presented.
Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article
Article Content
. INTRODUCTION
In this work, we study online and semi-online scheduling problems under the lp norm (p>1). We are given a sequence J={p1, p2, …, pn} of independent jobs, each with a positive processing time (size) pi, i=1, …, n, that must be non-preemptively scheduled on one of m identical machines. The load of a machine is the sum of the size of the jobs assigned to it. The load of ith machine related to an algorithm S is denoted by ti(J,S), i=1, 2, …, m, respectively. The objective is to minimize the sum of the lp norm of every machine’s load, i.e. Lp(J,S)≡[t1(J,S)p+t2(J,S)p +… +tm(J,S)p]1/p, where p>1 (Note that for p=1, the problem is trivial and any algorithm yields an optimal solution).
A scheduling problem is called online if jobs come one by one and it is required to schedule jobs irrevocably onto machines as soon as they are given, without any knowledge about jobs that follow later on. If some partially additional information about jobs is available in advance, and we cannot rearrange any job which has been assigned to machines, then it is called semi-online. Different partial information results in different semi-online problem. In the semi-online version with non-increasing job sizes (Graham, 1969; Seiden et al., 2000), we know in advance that jobs come in non-increasing order of their sizes, i.e. pi≥pi+1, i=1, …, n−1. If we have full information on the job data before constructing a scheduling, it is called offline. Algorithms for online and semi-online problems are called online and semi-online algorithms, respectively. Naturally, one wishes to achieve improvement of the performance of the optimal semi-online algorithm with respect to the online version by exploiting additional information. Though it is a relatively new area, more and more results of semi-online algorithms for scheduling problems appeared in the last decade. The readers may refer to recent survey papers (He et al., 2003a; 2003b). This paper will also consider such a problem.
We measure the performance of an algorithm for online and semi-online problems by its competitive ratio. For any fixed p>1, the competitive ratio of an algorithm S is defined as where J is an arbitrary job sequence, and OPT is an optimal offline algorithm. For randomized algorithm, we use E(Lp(J,S)) instead of Lp(J,S) in the above definition. If no deterministic (randomized) algorithm for an online (semi-online) scheduling problem has a competitive ratio smaller than c, then c is called the deterministic (randomized) lower bound for the corresponding problem. A deterministic or randomized algorithm is called optimal if its competitive ratio matches the corresponding lower bound.
The prime motivation of this study is as follows: So far most researches have been done in various scheduling models for the makespan measure, i.e. the l∞ norm, but in some applications other norms may be suitable such as the l2 norm (Azar et al., 2002). Consider for example a case where the processing time of a job corresponds to its machine disk access frequency. Then each job may see a delay that is proportional to the load on the machine it is assigned to. Thus the average delay is proportional to the sum of squares of the machines loads (i.e. l2 norm of machine loads), whereas the maximum delay is proportional to the maximum load (Chandra and Wong, 1975). Besides the real applications of the scheduling under lp norm, study for this kind of problems has also theoretical significance. In fact, a major drawback in optimization problems and in particular in scheduling problems is that for every measure there may be a different optimal solution. Usually, different algorithms are used for diverse measures, each providing its own solution. Therefore, one may ask what is the “correct” solution for a given scheduling problem In many cases there is no right answer to this question. In this paper, we show a case for which we can provide an appropriate answer, especially when the measures are different lp norms. Here “appropriate answer” means that the algorithm is optimal for every lp norm.
For the classical parallel machine scheduling problem Pm|online|Cmax, which can be viewed as the l∞ norm, Graham (1966) showed that the competitive ratio of LS algorithm is 2−1/m. Here LS algorithm always puts the first unassigned job on the machine with minimum current load. Faigle et al.(1989) further proved that LS is an optimal algorithm when m=2, 3. For the problem Pm|online|l2, Avidor et al.(2001) showed that the competitive ratio of LS is 4/3 for any number of machines divisible by 3 but strictly less than 4/3 in all other cases; and that LS is optimal. For the general problem Pm|online|lp, the exact competitive ratio of LS turns out to be 2−Θ(lnp/p) (Avidor et al., 2001). Specially, the competitive ratio of LS for m=2 is Moreover, for P2|online|l∞, an optimal randomized algorithm with competitive ratio 4/3 was proposed by Bartal et al.(1995). But to the authors’ knowledge, there is few literature considering randomized algorithm in the lp norm, where p>1. In this paper, we will propose a randomized lower bound of the problem P2|online|lp.
For the semi-online problem with decreasing job size Pm|decr|l∞, Graham (1969) proved that the competitive ratio of LS algorithm (i.e. LPT algorithm) is 4/3−1/(3m). Seiden et al.(2000) proved LS is optimal for m=2. Furthermore, an optimal randomized algorithm with competitive ratio 8/7 was also proposed for m=2 in the same paper. However the general problem P2|decr|lp is relatively unexplored. In this paper, we will consider this problem by proving that LS is an optimal algorithm for any lp norm. The competitive ratio is ((2Δ)p Thus LS algorithm is an all-norm optimal algorithm (Azar et al., 2002) for this semi-online scheduling problem, supplying one solution guaranteeing simultaneously optimal approximation with respect to the optimal solutions for all norms. This result extends the one obtained by Seiden et al.(2000). Moreover, we will also give a randomized lower bound of P2|decr|lp.
A closely related problem is the off-line problem P||lp. Chandra and Wong (1975) proved that the worst-case ratio of LPT lies in the interval [1.03, 1.04] for p=2. In 1995, tighter bounds of this algorithm was given by Leung and Wei (1995), which is a piecewise function depending on m. Alon et al.(1998) provided a polynomial time approximation scheme of P||lp, for any p>1.
. OPTIMAL SEMI-ONLINE DETERMINISTIC ALGORITHM
In this section, we are devoted to proving LS algorithm is an optimal algorithm of the problem P2|decr|lp for any p>1. We assume p1≥p2≥…≥pn in this section. We first present several technical lemmas.
Lemma 1 Define H(r)≡rp+(c−r)p over 0≤r≤c, where c is a positive constant. We have: (1) H(r) monotonically increases when r≥c/2; (2) cp/2p−1≤H(r) ≤cp; (3) H(r) monotonically increases in terms of |c−2r|.
Proof Clearly H′(r)=prp−1−p(c−r)p−1. The equation H′(r)=0 has a unique solution r=c/2, and H′(r)≥0 if and only if r∈[c/2,c] for the considered interval of r. We can conclude that H(r) monotonically increases when r∈[c/2,c], and decreases when r∈[0,c/2]. Thus Since |c−2r| also monotonically increases when r∈[c/2,c] and decreases when r∈[0,c/2], we conclude that H(r) monotonically increases in terms of |c−2r|.
Lemma 2 Algorithm LS always yields an optimal solution for any sequence J of the problem P2|decr|lp, where |J|≤4.
Proof The cases of |J|≤3 are trivial. Hence we focus on the case |J|=4. For the sake of simplicity, we assume that the sum of all job sizes in J is 1. Let B(C) denote the algorithm that assigns two jobs (three jobs) to one machine, and the remaining jobs to another machine. Then OPT must be one of B and C. Then it suffices to show that Lp(J,LS)≤Lp(J,B) and Lp(J,LS)≤Lp(J,C) to get the desired result. Let i, j, k∈{2,3,4} with i≠j≠k. Note that if an algorithm A assigns jobs to one machine with load r, then its objective value is Lp(J,A)=(rp+(1−r)p)1/p. Since max{r,1−r}≥1/2 is true for any r∈[0,1], by Lemma 1(1), (Lp(J,A))p monotonically increases in terms of max{r,1−r}.
If p1≥p2+p3, then Lp(J,LS)=( +(p2+ p3+p4)p)1/p. Since max{p1+pi, pj+pk}=p1+pi≥max{p1, p2+p3+p4}, we get Lp(J,LS)≤Lp(J,B). Similarly, we can get Lp(J,LS)≤Lp(J,C). If p1<p2+p3, then Lp(J,LS)= ((p1+p4)p+(p2+p3)p)1/p, and Lp(J,B)=((p1+pi)p+(pj+ pk)p)1/p. Since i, j, k∈{2,3,4} with i≠j≠k, and p1≥p2≥p3≥p4, we have max{p1+pi, pj+pk}≥p1+p4 and max{p1+pi, pj+pk}≥p2+p3. It follows that Lp(J,LS)≤Lp(J,B). Similarly, Lp(J,LS)≤Lp(J,C) holds. Thus LS is optimal for any sequence with 4 jobs.
Lemma 3Cp(LS) is achieved by the job sequence J0={y, y, z, z, z}, where y/2<z≤y.
Proof By normalization, we can assume that the sum of all job sizes in J is 1. Furthermore, we assume that we are considering the job sequence with the fewest jobs. In order to get a sequence J such that the ratio Lp(J,LS)/Lp(J,OPT) achieves the supremum, we show that we only need to consider such J satisfying
(i) pn≥|t1(J,LS)−t2(J,LS)|,
(ii) J only has 5 jobs.
To prove (i), we suppose there exists a job sequence J such that pn<|t1(J,LS)−t2(J,LS)|. Assume that t1(J,LS)>t2(J,LS) (the case t2(J,LS)>t1(J,LS) is similar). Then pn must be assigned to the second machine. In fact, if not, denote by s the starting time of pn on the first machine. Since we are considering the instance with fewest number of jobs, we have t1(J,LS)=s+pn. According to LS rule, s≤t2(J,LS). Then t1(J,LS)−t2(J,LS)≤pn, a contradiction.
Let J′={p1, p2, …, pn−1}, we have t1(J′,LS)=t1(J,LS), t2(J′,LS)=t2(J,LS)−pn. W.l.o.g., let pn be on the second machine of OPT. Let P be the algorithm for J′ that agrees with OPT for J. Set u=t2(J,LS), v=t2(J,OPT). We claim that
i.e. . To see it, sinceLp(J′,P)=((1−v)p+(v−pn)p)1/p, we have Denote C1(x)=(1−u)p+(u−x)p, C2(x)=(1−v)p+(v−x)p, and w(x)=C1(x)/C2(x), then we know Since v≥u≥x and C1(x)≥C2(x), we have ≥0, and thus w(pn)>w(0). It leads to Hence Eq.(1) holds. Since the sum of the jobs in sequence J′ is less than 1, we can make the sum equal to 1 by scaling up all sizes by the same number (i.e. by re-normalization). So we claim that for any J violating (i) we can remove the last job from J until (i) is satisfied (Note that for the job sequence with one job, (i) is valid trivially).
Next we prove (ii). Consider the sequence J={1/4,1/4,1/6,1/6,1/6}. Note that the gap between two machine loads is h(A)≡|t1(J,A)−t2(J,A)| =|1−2t2(J,A)| for any algorithm A. We have h(LS)=1/6 and h(OPT)=0. By Lemma 1(3), Lp(J,LS) is a monotonically increasing function of h(LS) for any J with five jobs. If J={1/4,1/4,1/6,1/6,1/6} achieves the supremum, we are done since this instance satisfies the result of the lemma. Thus we must select the sequence J satisfying h(LS)>1/6 in order to increase Lp(J,LS)/Lp(J,OPT). By the condition (i) we have pn>1/6. However since the total size of all jobs is 1 and p1≥p2≥…≥pn, we know pn≤1/n, which implies n≤5. Combining it with Lemma 2, we know that |J|=5. Hence we obtain (ii).
Now we return to the proof of the lemma. Given a non-increasing sequence of jobs J={p1, p2, …, p5} with p5>1/6, since 1−p1−p5=p2+p3+p4≥3p5, we have p1<1/3. Obviously the sum of any three jobs is greater than 1/2. It follows that the sum of any three jobs is greater than that of the remaining. The optimal algorithm OPT must assign p1, p2 to one machine and p3, p4, p5 to anther machine, while LS assigns p1, p4 to one machine, and p2, p3 to anther machine, since p1<1/3<p2+p3. Two cases are considered with respect to the assignment of p5 in LS schedule.
Case 1p1+p4>p2+p3. Then p2, p3 and p5 are on the same machine in LS schedule, and p2+p3+p5>1/2. We get the desired sequence by implementing the following three steps:
(a) Let ε=((p1+p4)−(p2+p3))/2. Replacing p1 by p1′=p1−ε, p2 by p2′=p2+ε, results in increasing h(LS) but keeping h(OPT) unchanged. Thus Lp(J,LS)/Lp(J,OPT) becomes larger. And we have p1′+p4=p2′+p3.
(b) Let ε′=(p1′−p2′)/2. By replacing p1′ by p1′′=p1′−ε′, p2′ by p2′′=p2′+ε′, p3 by p3′=p3−ε′, and p4 by p4′=p4+ε′, we have p1′′=p2′′, p3′=p4′, and both h(LS) and h(OPT) remain unchanged.
(c) Finally, let ε′′=(p3′−p5)/3, p3′′=p3′−ε′′, and p4′′=p4′−ε′′, p5′=p5+2ε′′, then p3′′=p4′′=p5′. It increases h(LS) and has no effect on h(OPT), and thus yields a larger Lp(J,LS)/Lp(J,OPT). Now we get a sequence J′′={p1′′, p2′′, p3′′, p4′′, p5′} satisfying p1′′=p2′′, p3′′=p4′′=p5′, and p1′′/2<p3′′≤p1′′.
Case 2p1+p4≤p2+p3. Then p1, p4 and p5 are on the same machine in LS schedule. Let ε=((p2+p3)−(p1+p4))/2, p3′=p3−ε, p4′=p4+ε. It increases h(LS) and remains h(OPT) unchanged, and thus increases Lp(J,LS)/Lp(J,OPT). Furthermore p1+p4′=p2+p3′, which is similar to the situation in Case 1(a). Therefore the result can be obtained by similar arguments as those in Case 1(b) and 1(c).
Thus is achieved by the job sequence J0={y, y, z, z, z}, y/2<z≤y.
DefineLemma 4 For any fixed p>1, Cp(LS)≤ Proof According to Lemma 3, we have Cp(LS)≤ Since Lp(J0,LS)=[(y+2z)p+ (y+z)p]1/p and Lp(J0,OPT)=[(2y)p+(3z)p]1/p, we have Set Δ=y/z, then 1≤Δ<2, we have = We next show that is achieved at a point Δ*∈[1, 2] for any fixed p>1, which implies = . In fact, since Cp(LS)≥1, we have (Δ*+2)p+(Δ*+1)p≥(2Δ*)p+3p. Combining it with Lemma 1(1), we have max{Δ*+2,Δ*+1}=Δ*+2≥ max(2Δ*,3)≥(2Δ*+3)/2. Δ*+2≥max{2Δ*,3} implies that Δ*∈[1,2]. By setting fp′(Δ)=0, we know is achieved at the solution of the following equation in x:
[(x+2)p−1+(x+1)p−1][(2x)p+3p]
=2(2x)p−1[(x+2)p+(x+1)p].
Since p>1, x=2 is not the solution of the above equation. So Δ*≠2 and the desired conclusion follows.
Lemma 5 For any p>1, any deterministic algorithm for P2|decr|lp has competitive ratio at least Proof We show the result by adversary method. First, two jobs with size Δ* come, where Δ* is defined above. If an algorithm A assigns them to the same machine, then no new job comes, and we have and Hence By Lemma 1(2), we have and These two inequalities imply that i.e. ≥ If algorithm A assigns the first two jobs to distinct machines, then the last three jobs with size 1 come. Denote J={Δ*, Δ*, 1, 1, 1}. We have So we conclude that any semi-online algorithm has a competitive ratio at least By Lemmas 4 and 5, we obtain the main result of this section:
Theorem 1 For the problem P2|decr|lp, where p>1, LS is an optimal deterministic semi-online algorithm with competitive ratio This section discusses randomized lower bounds of P2|online|lp and P2|decr|lp, for every p>1. To the authors’ best knowledge, no papers ever presented any lower bound for these problems so far.
Define Recall that the optimal deterministic algorithm of P2|online|lp is LS with competitive ratio , and is achieved at the unique solution Δ∈[0,∞] of the following equation in x: xp−1((1+x)1−p+1)=2p. Similar to that in the proof of Lemma 4, it can be shown that is achieved at a point for every fixed p>1, i.e., = . Furthermore it can also be shown that is achieved at the same Theorem 2 For any fixed p>1, any randomized algorithm for P2|online|lp has a competitive ratio at least Proof Let Obviously 0≤q1≤1. First, two jobs with size 1 come. If an algorithm A assigns the first two jobs to distinct machines with probability q<q1, then no new job comes. We have and It follows that > and we are done. If algorithm A assigns with probability q≥q1 to the first two jobs to distinct machines, then the last and third job with size Δ** comes, where Δ** is defined above. The optimal solution assigns the first two jobs together to a machine, and the last job to another machine, having objective value , while We have Hence ≥ and the proof is complete.
Define we then know is achieved at Δ*∈[1, 2), where Δ* is defined before.
Theorem 3 For any fixed p>1, any randomized algorithm for P2|decr|lp has a competitive ratio at least Proof Let . Obviously 0≤q2≤1. If an algorithm A assigns the first two jobs to distinct machines with probability q<q2, then no new job comes. We have, and It follows that = If algorithm A assigns the first two jobs to distinct machines with probability q≥q2, then the last three jobs with same size 1 come. Denote to J={Δ*, Δ*, 1, 1, 1}. The optimal solution assigns the first two jobs together to a machine, and the last three together to another machine with objective value [(2Δ*)p+3p]1/p, while We have ≥ Hence ≥ , and the proof is complete.
Table 1 shows the value of bounds for different p>1. We can see from Table 1 that the values of these functions monotonically increase in terms of p, and matches exactly the known results of the makespan problem when p→∞
In this paper we proved that LS algorithm is an optimal algorithm of P2|decr|lp for any p>1. We further presented randomized lower bounds of the problems P2|online|lp and P2|decr|lp. It will be interesting to propose optimal randomized algorithms under the lp norm for the above problems.
[4] Bartal, Y., Fiat, A., Karloff, H., 1995. New algorithms for an ancient scheduling problem. , J of Computer and System Science, 359-366. :359-366.
[5] Chandra, A.K., Wong, C.K., 1975. Worst-case analysis of a placement algorithm related to storage allocation. , SIAM J on Computing, 249-263. :249-263.
[6] Faigle, U., Kern, W., Turan, G., 1989. On the performance of online algorithms for partition problems. , Acta Cybernetica, 107-119. :107-119.
[7] Graham, R.L., 1966. Bounds for certain multiprocessor anomalies. , Bell Systems Technical J, 1563-1581. :1563-1581.
[8] Graham, R.L., 1969. Bounds on multiprocessing timing anomalies. , SIAM J on Applied Mathematics, 416-429. :416-429.
Open peer comments: Debate/Discuss/Question/Opinion
<1>