Similar articles

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|l_p (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 l_p norm of every machine’s load. It is shown that LS algorithm is optimal for any l_p norm, which extends the results known in the literature. Furthermore, randomized lower bounds for the problems P2|online|l_p and P2|decr|l_p are presented.

.  INTRODUCTION

 In this work, we study online and semi-online scheduling problems under the l_p norm (p>1). We are given a sequence J={p₁, p₂, …, p_n} of independent jobs, each with a positive processing time (size) p_i, 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 t_i(J,S), i=1, 2, …, m, respectively. The objective is to minimize the sum of the l_p norm of every machine’s load, i.e. L_p(J,S)≡[t₁(J,S)^p+t₂(J,S)^p +… +t_m(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. p_i≥p_i+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(L_p(J,S)) instead of L_p(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 l₂ 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. l₂ 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 l_p 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 l_p norms. Here “appropriate answer” means that the algorithm is optimal for every l_p norm.

 For the classical parallel machine scheduling problem Pm|online|C_max, 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|l₂, 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|l_p, 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 l_p norm, where p>1. In this paper, we will propose a randomized lower bound of the problem P2|online|l_p.

 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|l_p is relatively unexplored. In this paper, we will consider this problem by proving that LS is an optimal algorithm for any l_p 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|l_p.

 A closely related problem is the off-line problem P||l_p. 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||l_p, 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|l_p for any p>1. We assume p₁≥p₂≥…≥p_n in this section. We first present several technical lemmas.

 Lemma 1 Define H(r)≡r^p+(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) c^p/2^p−1≤H(r) ≤c^p; (3) H(r) monotonically increases in terms of |c−2r|.

 Proof Clearly H′(r)=pr^p−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|l_p, 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 L_p(J,LS)≤L_p(J,B) and L_p(J,LS)≤L_p(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 L_p(J,A)=(r^p+(1−r)^p)^1/p. Since max{r,1−r}≥1/2 is true for any r∈[0,1], by Lemma 1(1), (L_p(J,A))^p monotonically increases in terms of max{r,1−r}.

 If p₁≥p₂+p₃, then L_p(J,LS)=( +(p₂+ p₃+p₄)^p)^1/p. Since max{p₁+p_i, p_j+p_k}=p₁+p_i≥max{p₁, p₂+p₃+p₄}, we get L_p(J,LS)≤L_p(J,B). Similarly, we can get L_p(J,LS)≤L_p(J,C). If p₁<p₂+p₃, then L_p(J,LS)= ((p₁+p₄)^p+(p₂+p₃)^p)^1/p, and L_p(J,B)=((p₁+p_i)^p+(p_j+ p_k)^p)^1/p. Since i, j, k∈{2,3,4} with i≠j≠k, and p₁≥p₂≥p₃≥p₄, we have max{p₁+p_i, p_j+p_k}≥p₁+p₄ and max{p₁+p_i, p_j+p_k}≥p₂+p₃. It follows that L_p(J,LS)≤L_p(J,B). Similarly, L_p(J,LS)≤L_p(J,C) holds. Thus LS is optimal for any sequence with 4 jobs.

 Lemma 3 C_p(LS) is achieved by the job sequence J₀={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 L_p(J,LS)/L_p(J,OPT) achieves the supremum, we show that we only need to consider such J satisfying

 (i) p_n≥|t₁(J,LS)−t₂(J,LS)|,

 (ii) J only has 5 jobs.

 To prove (i), we suppose there exists a job sequence J such that p_n<|t₁(J,LS)−t₂(J,LS)|. Assume that t₁(J,LS)>t₂(J,LS) (the case t₂(J,LS)>t₁(J,LS) is similar). Then p_n must be assigned to the second machine. In fact, if not, denote by s the starting time of p_n on the first machine. Since we are considering the instance with fewest number of jobs, we have t₁(J,LS)=s+p_n. According to LS rule, s≤t₂(J,LS). Then t₁(J,LS)−t₂(J,LS)≤p_n, a contradiction.

 Let J′={p₁, p₂, …, p_n−1}, we have t₁(J′,LS)=t₁(J,LS), t₂(J′,LS)=t₂(J,LS)−p_n. W.l.o.g., let p_n be on the second machine of OPT. Let P be the algorithm for J′ that agrees with OPT for J. Set u=t₂(J,LS), v=t₂(J,OPT). We claim that (1)

 i.e. . To see it, since L_p(J′,P)=((1−v)^p+(v−p_n)^p)^1/p, we have Denote C₁(x)=(1−u)^p+(u−x)^p, C₂(x)=(1−v)^p+(v−x)^p, and w(x)=C₁(x)/C₂(x), then we know Since v≥u≥x and C₁(x)≥C₂(x), we have ≥0, and thus w(p_n)>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)≡|t₁(J,A)−t₂(J,A)| =|1−2t₂(J,A)| for any algorithm A. We have h(LS)=1/6 and h(OPT)=0. By Lemma 1(3), L_p(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 L_p(J,LS)/L_p(J,OPT). By the condition (i) we have p_n>1/6. However since the total size of all jobs is 1 and p₁≥p₂≥…≥p_n, we know p_n≤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={p₁, p₂, …, p₅} with p₅>1/6, since 1−p₁−p₅=p₂+p₃+p₄≥3p₅, we have p₁<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 p₁, p₂ to one machine and p₃, p₄, p₅ to anther machine, while LS assigns p₁, p₄ to one machine, and p₂, p₃ to anther machine, since p₁<1/3<p₂+p₃. Two cases are considered with respect to the assignment of p₅ in LS schedule.

 Case 1 p₁+p₄>p₂+p₃. Then p₂, p₃ and p₅ are on the same machine in LS schedule, and p₂+p₃+p₅>1/2. We get the desired sequence by implementing the following three steps:

 (a) Let ε=((p₁+p₄)−(p₂+p₃))/2. Replacing p₁ by p₁′=p₁−ε, p₂ by p₂′=p₂+ε, results in increasing h(LS) but keeping h(OPT) unchanged. Thus L_p(J,LS)/L_p(J,OPT) becomes larger. And we have p₁′+p₄=p₂′+p₃.

 (b) Let ε′=(p₁′−p₂′)/2. By replacing p₁′ by p₁′′=p₁′−ε′, p₂′ by p₂′′=p₂′+ε′, p₃ by p₃′=p₃−ε′, and p₄ by p₄′=p₄+ε′, we have p₁′′=p₂′′, p₃′=p₄′, and both h(LS) and h(OPT) remain unchanged.

 (c) Finally, let ε′′=(p₃′−p₅)/3, p₃′′=p₃′−ε′′, and p₄′′=p₄′−ε′′, p₅′=p₅+2ε′′, then p₃′′=p₄′′=p₅′. It increases h(LS) and has no effect on h(OPT), and thus yields a larger L_p(J,LS)/L_p(J,OPT). Now we get a sequence J′′={p₁′′, p₂′′, p₃′′, p₄′′, p₅′} satisfying p₁′′=p₂′′, p₃′′=p₄′′=p₅′, and p₁′′/2<p₃′′≤p₁′′.

 Case 2 p₁+p₄≤p₂+p₃. Then p₁, p₄ and p₅ are on the same machine in LS schedule. Let ε=((p₂+p₃)−(p₁+p₄))/2, p₃′=p₃−ε, p₄′=p₄+ε. It increases h(LS) and remains h(OPT) unchanged, and thus increases L_p(J,LS)/L_p(J,OPT). Furthermore p₁+p₄′=p₂+p₃′, 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 J₀={y, y, z, z, z}, y/2<z≤y.

 Define Lemma 4 For any fixed p>1, C_p(LS)≤ Proof According to Lemma 3, we have C_p(LS)≤ Since L_p(J₀,LS)=[(y+2z)^p+ (y+z)^p]^1/p and L_p(J₀,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 C_p(LS)≥1, we have (Δ^*+2)^p+(Δ^*+1)^p≥(2Δ^*)^p+3^p. 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+3^p]

 =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|l_p 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|l_p, where p>1, LS is an optimal deterministic semi-online algorithm with competitive ratio This section discusses randomized lower bounds of P2|online|l_p and P2|decr|l_p, 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|l_p is LS with competitive ratio , and is achieved at the unique solution Δ∈[0,∞] of the following equation in x: x^p−1((1+x)^1−p+1)=2^p. 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|l_p has a competitive ratio at least Proof Let Obviously 0≤q₁≤1. First, two jobs with size 1 come. If an algorithm A assigns the first two jobs to distinct machines with probability q<q₁, then no new job comes. We have and It follows that > and we are done. If algorithm A assigns with probability q≥q₁ 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|l_p has a competitive ratio at least Proof Let . Obviously 0≤q₂≤1. If an algorithm A assigns the first two jobs to distinct machines with probability q<q₂, 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≥q₂, 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+3^p]^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→∞

.  CONCLUSION

 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.

---

* Project supported by the National Natural Science Foundation of China (Nos. 10271110, 10301028) and the Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions of MOE, China