# WSPT's Competitive Performance for Minimizing the Total Weighted Flow Time: From Single to Parallel Machines

Authors: Jiping Tao; Tundong Liu
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

We consider the classical online scheduling problem over single and parallel machines with the objective of minimizing total weighted flow time. We employ an intuitive and systematic analysis method and show that the weighted shortest processing time (WSPT) is an optimal online algorithm with the competitive ratio ofP+1 for the case of single machine, and it is (P+(3/2)−(1/2m))-competitive for the case of parallel machines (m>1), where P is the ratio of the longest to the shortest processing time.


---

## Body

## 1. Introduction

In the context of scheduling problems, the flow time of a job is the total time it stays in the system. Sometimes it is also called response time. It is equal to the delay of waiting for service plus the actual service time. The total (weighted) flow time captures the overall quality of service of the system, which is a natural and important measure in many applications such as networks and parallel computing [1, 2]. From the prespective of optimal solutions, the objective of minimizing the total (weighted) flow time is equivalent to minimizing the total (weighted) completion time. However, online algorithms and approximation results are largely different between the two objectives.In this work, we consider the online scheduling over parallel machines with the objective of minimizing the total weighted flow time. Formally, there is a set ofn jobs and m identical machines. Each job Jj is associated with processing time pj, release date rj, and a positive weight wj. All the information about one job is not revealed until it is released. Also, the total number n of jobs is unknown a priori. An online algorithm determines which machine to be chosen and what time to start for processing each job without interruption. Denote the completion time and flow time of Jj by Cj and Fj, respectively. Then, Fj=Cj-rj holds. The problem can be denoted by Pm|rj|∑‍wjFj in terms of the standard three field notations for scheduling problems [3].When the objective is to minimize the total (weighted) completion time, it is well known that optimal deterministic online algorithms with the competitive ratio of2 have been presented for 1|rj|∑‍Cj [4, 5] and 1|rj|∑‍wjCj, respectively [6, 7]. As for the parallel machine scheduling P|rj|∑‍wjCj, the current best online algorithm is given by Correa and Wagner [8]; they design a 2.618-competitive algorithm based on linear programming techniques and the concept of α-point. However, no online algorithm with bounded competitive ratio exists for the case of total (weighted) flow time scheduling. Even for offline approximate algorithms, the lower bound on worst-case performance guarantee is still at least Ω(n1/2-ε) for the single machine case [9] and Ω(n1/3-ε) for the multiple machines case [2].Since the lower bound is so strong, an intuitive idea is to impose some additional assumptions on the original problem. A widely used assumption is that the ratio of the longest to the shortest processing time is not greater than a constant, sayP. With this assumption, Bunde [10] proves that the shorting processing time (SPT) rule is optimal with the competitive ratio of (P+1)/2 for 1|rj|∑‍Fj. Most of other previous works focus on the preemptive setting. Chekuri et al. [11] consider the problem 1|rj, pmtn|∑‍wjFj. They present a O(log2P)-competitive online algorithm when the weights are also bounded. Leonardi and Raz [2] prove that the shortest remaining processing time (SRPT) algorithm has a competitive ratio of O(log(min((n/m),P))) for Pm|rj, pmtn|∑‍wjFj. The same authors also provide a Ω(log(min((n/m),P))) lower bound on the competitive ratio of any randomized algorithm for this problem. Bansal and Dhamdhere [12] make another kind of assumption. They assume that the job weights belong to at most k different arbitrary weight classes. Under this assumption, they construct an online algorithm for 1|rj,pmtn|∑‍wjFj and prove that it is k-competitive. Combining this conclusion and the assumption that the ratio of the maximum to the minimum job weight is W, the authors further obtain a O(logW)-competitive algorithm, since weights can be rounded up to a power of 2.To the best of our knowledge, no positive results exist when nontrivial weights are considered and preemption is not allowed. In this work, we show that the weighted shortest processing time (WSPT) rule is optimal with the competitive ratio ofP+1 for 1|rj|∑‍wjFj, and it is (P+(3/2)-(1/2m))-competitive for Pm|rj, pmtn|∑‍wjFj (m>1). The competitive analysis method is based on the idea of instance transformation, which is first introduced by us in [13] and is further developed in [14, 15]. The method tries to search for the worst-case instance in the instance space. It starts from an arbitrary instance and modifies the instance towards the possible structure of the worst-case instance with respect to the given online algorithm. The modification guarantees that the performance ratio of the modified instance does not decrease. Eventually, the modification ends up with an instance with a relatively simple and special structure, whose performance ratio can be much easily evaluated.The paper is organized as follows. In Section2 we show that the worst-case instance with respect to the WSPT rule is characterized by two kinds of special structures. Then, we analyze the performance ratio of these two kinds of instances for the single machine and parallel machines in Sections 3 and 4, respectively. Concluding remarks are given in Section 5.


## 2. Block Structure of the Schedule and Instance Transformation

For any instanceI, denote the schedule obtained by WSPT by σ(I), the optimal offline schedule by σ*(I), and the objective values of the two schedules by ALG(I) and OPT(I), respectively. For any job Jj in I, denote its flow time in σ(I) and σ*(I) by Fj and Fj*.It can be easily shown that the worst-case instance can be obtained among such instances for which the schedules by WSPT rule are composed of a single block. A block means a time interval in which jobs are processed contiguously without keeping all the machines idle at the same time. Denote any one of these instances byI1. Without loss of generality, assume that the first job is released at time 0; that is, the single block begins at time 0. According to the nondecreasing order of starting times of jobs in σ(I1), we further partition jobs into subblocks, such that the jobs within each subblock are ordered according to the WSPT rule and the last job of a subblock has a greater ratio of processing time to weight (hereafter, we use weighted processing time to refer to the ratio) than the first job of the succeeding subblock if it exists.We will further show that a new instance with a more simple and special structure can be obtained by modifying the weights of jobs inI1. First we introduce an important lemma without proof since it can be derived from basic mathematics. The following lemma will be repeatedly used in the competitive analysis.Lemma 1.
Letf(x) and g(x) be two positive functions defined in the interval [u,v]; moreover, f(x) is convex and g(x) is concave. Then, f(x)/g(x) reaches its maximum at one endpoint of the interval; that is, f(x)/g(x)≤max{f(u)/g(u),f(v)/g(v)} for all x∈[u,v].It can be easily shown that the above lemma still holds when the interval is open at some endpoint in the condition that the limitation off(x)/g(x) exists at the corresponding endpoint.Lemma 2.
For an arbitrary instanceI1, a new instance can be constructed by modifying the weights of jobs in I1, such that all the jobs in the new instance have the same weighted processing time or there are jobs which not only have the same weighted processing time but also have positive infinite weights in the last subblock of the schedule for the new instance; denote the former new instance by I2 and the latter one by I3; then
(1)ALG(I1)OPT(I1)≤max{ALG(I2)OPT(I2),ALG(I3)OPT(I3)}.Proof.
Assume thatσ(I1) is composed of K subblock. We first consider the case of K>1. Next, we will show that an intermediate instance I′ can be obtained by modifying I1, such that either σ(I′) is composed of K-1 subblocks or there are jobs with positive infinite weights in the last subblock of σ(I′) with K subblocks.
Denote the last job of the next-to-last subblock inσ(I1) by Jk. Denote the set of all the jobs of the last subblock by Q′. Divide Q′ into two subsets in terms of the relations between their weighted processing times and Jk’s:
(2)Q1′={Jj∣Jj∈Q′,0<pjwj<pkwk},Q2′={Jj∣Jj∈Q′,pjwj≥pkwk}.
Modify the weightwj of each job Jj in Q1′ to δwj, where δ is a parameter to be chosen later. Let
(3)δ_=max{(pj/wj)∣Jj∈Q1′}pk/wk.
Denote the intermediate instance after this adjustment byI′. Since this adjustment does not change the mutual relationships of the weighted processing time among jobs in the last subblock, jobs are processed in σ(I′) in the same order as in σ(I1) for any δ∈[δ_,+∞).
ALG
(
I
′
) is composed of the linear combination of all jobs’ weights, where the coefficient of each weight is the corresponding job’s flow time. Since the schedule does not change after adjustment and each job’s flow time does not change, ALG(I′) is a monotonously increasing linear function with respect to δ. Consider how OPT(I′) changes with respect to δ. If jobs keep the same processing order as in σ*(I1), the objective value of the obtained schedule is also a monotonously increasing linear function with respect to δ. Since the optimal schedule σ*(I′) is the one with the minimal objective value among all the feasible schedules, OPT(I′) is a piecewise linear function with respect to δ; moreover, its slope does not increase with δ increasing. It means that OPT(I′) is a concave function with respect to δ. According to Lemma 1, we can obtain an instance with a worse performance ratio by choosing δ as either δ_ or +∞. There are two cases. (i)
Ifδ is chosen as δ_, there is at least one job belonging to Q1′ whose weighted processing time is modified to pk/wk according to (3). Then, update Q1′ and Q2′ according to (2). If there remain jobs in Q1′, modify their weights by repeating the above procedure; otherwise all the jobs in Q1′ have been removed into Q2′. Since all the jobs in Q2′ have greater weighted processing time than Jk’s, the last two subblocks in the original schedule σ(I1) can be combined into a single subblock in the new instance according to the description of “subblock” in Section 2; that is, σ(I′) is composed of K-1 subblocks.(ii)
Ifδ tends to infinity, all the jobs in Q1′ have weights +∞. This intermediate instance is just the instance which we want to obtain at the beginning of the proof.
By repeatedly applying the above transformation procedure, we can eventually obtain a new instance, such that the schedule by WSPT for the new instance is composed of a single subblock, or there are jobs with positive infinite weights in the last subblock of the schedule for the new instance. For the former one, for ease of exposition, we still useI′ to denote it. Next we will show that I′ can be modified such that all the jobs have the same weighted processing time.
Denote the first job in the single subblock ofσ(I′) by J1. Divide all the jobs into other two sets in terms of the relations between their weighted processing time and J1’s:
(4)Q1′′={Jj∣Jj∈Q2′,+∞>pjwj>p1w1},Q2′′={Jj∣Jj∈Q2′,pjwj=p1w1}.
Similar to the previous adjustment, modify the weightwj of each job Jj in Q1′′ to δwj, where δ is a parameter to be chosen later. Let
(5)δ-=min{(pj/wj)∣Jj∈Q1′′}p1/w1.
We useI~′ to denote the intermediate instance after this adjustment. Completely similar to the previous analysis, when δ lies in (0,δ-], ALG(I~′) is a monotonously increasing linear function with respect to δ. OPT(I~′) is a concave function with respect to δ. According to Lemma 1, we can obtain an instance with a worse performance ratio by choosing δ as either δ- or an infinitely small value ε. If δ is chosen as δ-, there is at least one job belonging to Q1′′ whose weighted processing time is modified to p1/w1 according to (5). Then, update Q1′′ and Q2′′ according to (4). If there remain jobs in Q1′′, modify their weights by repeating the above adjustment procedure. If δ is chosen as an infinitely small value, all the jobs in Q1′′ have weights tending to 0. These jobs are processed at last both in σ(I~′) and σ*(I~′). Thus, we can directly delete these jobs, since they contribute nothing to the objective value.
After finite steps, all the jobs lie inQ2′′; that is, all the jobs have the same weighted processing time as J1’s. It is just the instance I2 which we want to obtain in the theorem. For the intermediate instance, where there are jobs with positive infinite weights in the last subblock, we can apply the same above modification and modify these jobs such that they have the same weighted processing time. The resulted instance is I3 which we want to obtain in the theorem.


## 3. WSPT’s Optimality for1|rj|∑‍wjFj

In this section, we show that WSPT is optimal with the competitive ratio ofP+1 for 1|rj|∑‍wjFj. We obtain the result by proving that P+1 is both an upper bound on the competitive ratio of WSPT and a lower bound on the competitive ratio of any online algorithm.We know that the worst-case instance can be achieved among such instances, for which the schedules by WSPT are composed of a single block. From Lemma2, we show that any such instance can be modified to a new instance with a worse performance ratio. Next, we can directly analyze the performance ratio of the new instance obtained in Lemma 2 and get the competitive performance of WSPT algorithm.Theorem 3.
The WSPT algorithm is optimal with the competitive ratio ofP+1 for 1|rj|∑‍wjFj.Proof.
For the new instanceI2 described in Lemma 2, where all the jobs have the same weighted processing time, it is obvious that the schedule obtained by WSPT is just the optimal one for 1|rj|∑‍wjFj.
As for another new instanceI3, there are jobs which not only have the same weighted processing time but also have positive infinite weights in the last subblock. Denote the last job of the next-to-last subblock by Jk. Denote the set of all these jobs with positive infinite weights in the last subblock by Q∞. We can directly analyze the performance ratio of the instance by only considering these jobs in Q∞ since other jobs’ weighted flow times can be omitted in the sense of limitation. All these jobs in Q∞ are released after Jk starts being processed in σ(I3); otherwise they would be processed before Jk. These jobs are continuously processed immediately after Jk is finished in σ(I3). They are processed in the optimal schedule σ*(I3) in the same order as in σ(I3); moreover, they start being processed not earlier than the time when Jk starts in σ(I3). Figure 1 illustrates the schedules σ(I3) and σ*(I3). Thus, we have
(6)ALG(I3)OPT(I3)=∑j∈Q∞wjFj∑j∈Q∞wjFj*≤maxj∈Q∞FjFj*≤maxj∈Q∞Fj*+pkFj*≤1+maxpkpj≤1+P.
So, we get an upper bound on the competitive ratio of WSPT algorithm, i.e.,
(7)ρ≤1+P.
Next, we show that1+P is also a lower bound on the competitive ratio of any deterministic online algorithm for 1|rj|∑‍wjFj.
Consider the following instance. The first jobJ1 arrives at time 0 with p1=1 and w1=1. The online algorithm decides to schedule J1 at time S. The second job J2 is released job at time S+ε with p2=1/P and w2, where ε is an infinitely small value. The optimal schedule performs no worse than the one which first schedules J2 at time S+ε, then, followed by J1. So we have
(8)ALG(I)OPT(I)≥S+1+w2(1+1/P-ε)S+ε+1/P+1+w2(1/P).
Whenε tends to 0 and w2 tends to infinity, the above ratio tends to (P+1). Since a competitive ratio of an online algorithm is the maximal performance ratio over all the instances, we can directly obtain that the competitive ratio of any deterministic online algorithm is no less than (P+1).
According to the above analysis, we can immediately obtain that the WSPT algorithm is optimal with the competitive ratio ofP+1.Figure 1
The WSPT schedule and optimal schedule forI3 in the case of single machine.


## 4. Competitive Analysis of WSPT Algorithm forPm|rj|∑‍wjFj

Next, we will extend the result for the single machine in Section3 to the case of parallel machines. Similar to the proof for Theorem 3, we can analyze the performance ratio of the new instances I2 and I3 obtained in Lemma 2. First, an appropriate lower bound on the optimal schedule has to be established in order to further analyze the performance ratio of I2 and I3. Chou et al. [16] show a lower bound on the corresponding weighted completion time problem of Pm|rj|∑‍wjCj by introducing a virtual m-times faster single machine problem and the concept of LP schedule [17]. We can readily extend this result to the weighted flow time problem due to the equivalence between optimal schedules for Pm|rj|∑‍wjCj and Pm|rj|∑‍wjFj.Corollary 4.
For an instanceI of P|rj|∑‍wjFj, construct a virtual m-times faster single machine instance I′={rj,pj/m,wj}. For the corresponding LP schedule of I′, denote the mean-busy-time and flow time of job Jj by MjLP and FjLP, respectively, and then,
(9)OPT(I)≥∑j∈I‍wjMjLP+12∑j∈I‍wjpj-∑j∈I‍wjrj.
Moreover, if theLP schedule is nonpreemptive, then,
(10)OPT(I)≥∑j∈I‍wjFjLP+12(1-1m)∑‍wjpj.Hereafter, we refer to the lower bound in Corollary4 as LP lower bound and denote it by LBm(·).


### 4.1. Performance Analysis ofI2 and I3

For simplicity, we give the result via three Lemmas.Lemma 5.
For any instanceI for Pm|rj|∑‍wjFj, if all the jobs have the same weighted processing time and there is no idle time on each machine before it completes its processing in the corresponding schedule σ(I), then,
(11)ALG(I)OPT(I)≤32-12m.Proof.
All the jobs in the instanceI have the same weighted processing time. Moreover, there is no idle time on each machine before it completes its processing in the corresponding schedule in σ(I). We can find out that for the corresponding virtual m-times faster single machine problem, the schedule which processes jobs without preemption and delay in the same starting order as in σ(I) is just a LP schedule. Without loss of generality, we can assume that wj=pj in order to simplify the analysis. Thus, the LP lower bound in (10) can be rewritten as
(12)OPT(I)≥∑‍pjFjLP+12(1-1m)∑‍pj2.
Another trivial lower bound on OPT(I) is
(13)OPT(I)≥∑‍wjpj=∑‍pj2.
Taking how the LP schedule is constructed, we can bound the flow timeFj in the WSPT schedule as
(14)Fj≤FjLP+(1-1m)pj.
So
(15)ALG(I)≤∑‍pjFjLP+(1-1m)∑‍pj2.
Denote the two bounds in (12) and (13) by LB1 and LB2 respectively,. Next, we analyze the performance ratio by two cases. (i)
IfLB1≤LB2, that is, ∑‍pjFjLP+(1/2)(1-(1/m))∑‍pj2≤∑‍pj2, then
(16)ALG(I)OPT(I)≤∑‍pjFjLP+(1-(1/m))∑‍pj2∑‍pj2≤∑‍pj2+(1/2)(1-(1/m))∑‍pj2∑‍pj2=32-12m.(ii)
IfLB1≥LB2, that is, ∑‍pjFjLP+(1/2)(1-(1/m))∑‍pj2≥∑‍pj2,
(17)ALG(I)OPT(I)≤∑‍pjFjLP+(1-(1/m))∑‍pj2∑‍pjFjLP+(1/2)(1-(1/m))∑‍pj2=1+(1/2)(1-(1/m))∑‍pj2∑‍pjFjLP+(1/2)(1-(1/m))∑‍pj2≤1+(1/2)(1-(1/m))∑‍pj2∑‍pj2=32-12m.Lemma 6.
In the case of parallel machines, for the instanceI2 obtained in Lemma 2, one has
(18)ALG(I2)OPT(I2)≤P+32-12m.Proof.
When there is no idle time on each machine before it completes its processing inσ(I2), this result can be directly obtained from Lemma 5. Suppose that there are totally L (L>1) periods of idle time in σ(I2). Next, we will show that an intermediate instance I2′ can be obtained such that there are L-1 periods of idle time in σ(I2′); moreover,
(19)ALG(I2)OPT(I2)≤max{ALG(I2′)OPT(I2′),P+32-12m}.
For the sake of exposition, we take an instance with three machines; for example, see Figure2. t is the ending time of the last (with respect to the ending point of the idle time) period of idle time. It means that all the jobs are continuously processed without idle time on each machine after t. Since WSPT is a no-waiting strategy, we know that all the arrived jobs have been finished or are being processed at t. t′ is the latest completion time of jobs which start before t. Denote the maximal processing time among all the jobs by pmax; then, t′-t≤pmax.
Construct an intermediate instance denoted byI2′, which is composed of all the jobs released before t. In addition, we construct an auxiliary instance I~2. It includes all the jobs released at and after t. We have
(20)ALG(I2)OPT(I2)≤ALG(I2′)+∑j∈I~2wjFjOPT(I2′)+OPT(I~2)≤max{ALG(I2′)OPT(I2′),∑j∈I~2wjFjOPT(I~2)}.
In order to bound the later term in the above expression, similar to the proof of Lemma5, consider the virtual m-times faster single machine problem for I~2. Assume that jobs are continuously processed on the virtual m-times faster single machine from time t in the same starting order as in σ(I2) without considering the release time constrain. Denote the corresponding flow time of Jj by Fj′. Then, we can bound the flow time in the WSPT schedule as
(21)Fj≤Fj′+(1-1m)pj+t′-t,j∈I~2.
Without loss of generality, let wj=pj; we have
(22)∑j∈I~2‍wjFj≤∑j∈I~2‍wiFj′+(1-1m)∑j∈I~2‍pj2+(t′-t)∑j∈I~2‍pj.
In addition, for the virtualm-times faster single machine problem for I~2, consider its LP schedule. Denote by FjLP the flow time in the LP schedule. We can get a lower bound on OPT(I~2) as
(23)OPT(I~2)≥∑j∈I~2‍wjFjLP+12(1-1m)∑j∈I~2‍wjpj≥∑j∈I~2‍pjFj′+12(1-1m)∑j∈I~2‍pj2.
Another trivial lower bound onOPT(I~2) is
(24)OPT(I~2)≥∑j∈I~2‍wjpj=∑j∈I~2‍pj2.
Combining (22),(23), and (24), we have
(25)∑j∈I~2wjFjOPT(I~2)≤∑j∈I~2pjFj′+(1-(1/m))∑j∈I~2pj2+(t′-t)∑j∈I~2pimax{∑j∈I~2pj2,∑j∈I~2pjFj′+(1/2)(1-(1/m))∑j∈I~2pj2}.
Similar to the analysis of the two cases in the proof of Lemma5, we can obtain
(26)∑j∈I~2pjFj′+(1-(1/m))∑j∈I~2pj2max{∑j∈I~2pj2,∑j∈I~2pjFj′+(1/2)(1-(1/m))∑j∈I~2pj2}≤32-12m.
In addition, it can be obtained fromt′-t≤pmax that
(27)(t′-t)∑j∈I~2pj∑j∈I~2pj2≤maxj∈I~2pmaxpj≤P.
According to the above analysis, we can obtain(28)∑j∈I~2wjFjOPT(I~2)≤P+32-12m
and prove relation (19).
By repeating the above transformation, we can get a sequence of intermediate instances with (19) satisfied and finish the proof.Figure 2
The schedule obtained by WSPT forI2 in the case of parallel machines.Lemma 7.
In the case of parallel machines, for the instanceI3 obtained in Lemma 2, one has
(29)ALG(I3)OPT(I3)≤P+32-12m.Proof.
For ease of presentation, we still take an instance with three machines; for example, see Figure3. Assume that these jobs with positive infinite weights start being processed at the time t. t′ is the latest starting time of jobs among all the machines before t. t′′ is the latest completion time of jobs which start before t. Denote the maximal processing time among all the jobs by pmax; then, t′′-t′≤pmax. We only need to consider these jobs with positive infinite weights in the last subblock. Then, the proof is similar to the one for Lemma 6 and the detailed procedure is omitted.Figure 3
The schedule obtained by WSPT forI3 in the case of parallel machines.Following Lemmas2, 6, and 7, we can immediately get the competitive performance of WSPT for the case of parallel machines.Theorem 8.
The WSPT algorithm is(P+(3/2)-(1/2m))-competitive for Pm|rj|∑‍wjFj(m>1).


## 4.1. Performance Analysis ofI2 and I3

For simplicity, we give the result via three Lemmas.Lemma 5.
For any instanceI for Pm|rj|∑‍wjFj, if all the jobs have the same weighted processing time and there is no idle time on each machine before it completes its processing in the corresponding schedule σ(I), then,
(11)ALG(I)OPT(I)≤32-12m.Proof.
All the jobs in the instanceI have the same weighted processing time. Moreover, there is no idle time on each machine before it completes its processing in the corresponding schedule in σ(I). We can find out that for the corresponding virtual m-times faster single machine problem, the schedule which processes jobs without preemption and delay in the same starting order as in σ(I) is just a LP schedule. Without loss of generality, we can assume that wj=pj in order to simplify the analysis. Thus, the LP lower bound in (10) can be rewritten as
(12)OPT(I)≥∑‍pjFjLP+12(1-1m)∑‍pj2.
Another trivial lower bound on OPT(I) is
(13)OPT(I)≥∑‍wjpj=∑‍pj2.
Taking how the LP schedule is constructed, we can bound the flow timeFj in the WSPT schedule as
(14)Fj≤FjLP+(1-1m)pj.
So
(15)ALG(I)≤∑‍pjFjLP+(1-1m)∑‍pj2.
Denote the two bounds in (12) and (13) by LB1 and LB2 respectively,. Next, we analyze the performance ratio by two cases. (i)
IfLB1≤LB2, that is, ∑‍pjFjLP+(1/2)(1-(1/m))∑‍pj2≤∑‍pj2, then
(16)ALG(I)OPT(I)≤∑‍pjFjLP+(1-(1/m))∑‍pj2∑‍pj2≤∑‍pj2+(1/2)(1-(1/m))∑‍pj2∑‍pj2=32-12m.(ii)
IfLB1≥LB2, that is, ∑‍pjFjLP+(1/2)(1-(1/m))∑‍pj2≥∑‍pj2,
(17)ALG(I)OPT(I)≤∑‍pjFjLP+(1-(1/m))∑‍pj2∑‍pjFjLP+(1/2)(1-(1/m))∑‍pj2=1+(1/2)(1-(1/m))∑‍pj2∑‍pjFjLP+(1/2)(1-(1/m))∑‍pj2≤1+(1/2)(1-(1/m))∑‍pj2∑‍pj2=32-12m.Lemma 6.
In the case of parallel machines, for the instanceI2 obtained in Lemma 2, one has
(18)ALG(I2)OPT(I2)≤P+32-12m.Proof.
When there is no idle time on each machine before it completes its processing inσ(I2), this result can be directly obtained from Lemma 5. Suppose that there are totally L (L>1) periods of idle time in σ(I2). Next, we will show that an intermediate instance I2′ can be obtained such that there are L-1 periods of idle time in σ(I2′); moreover,
(19)ALG(I2)OPT(I2)≤max{ALG(I2′)OPT(I2′),P+32-12m}.
For the sake of exposition, we take an instance with three machines; for example, see Figure2. t is the ending time of the last (with respect to the ending point of the idle time) period of idle time. It means that all the jobs are continuously processed without idle time on each machine after t. Since WSPT is a no-waiting strategy, we know that all the arrived jobs have been finished or are being processed at t. t′ is the latest completion time of jobs which start before t. Denote the maximal processing time among all the jobs by pmax; then, t′-t≤pmax.
Construct an intermediate instance denoted byI2′, which is composed of all the jobs released before t. In addition, we construct an auxiliary instance I~2. It includes all the jobs released at and after t. We have
(20)ALG(I2)OPT(I2)≤ALG(I2′)+∑j∈I~2wjFjOPT(I2′)+OPT(I~2)≤max{ALG(I2′)OPT(I2′),∑j∈I~2wjFjOPT(I~2)}.
In order to bound the later term in the above expression, similar to the proof of Lemma5, consider the virtual m-times faster single machine problem for I~2. Assume that jobs are continuously processed on the virtual m-times faster single machine from time t in the same starting order as in σ(I2) without considering the release time constrain. Denote the corresponding flow time of Jj by Fj′. Then, we can bound the flow time in the WSPT schedule as
(21)Fj≤Fj′+(1-1m)pj+t′-t,j∈I~2.
Without loss of generality, let wj=pj; we have
(22)∑j∈I~2‍wjFj≤∑j∈I~2‍wiFj′+(1-1m)∑j∈I~2‍pj2+(t′-t)∑j∈I~2‍pj.
In addition, for the virtualm-times faster single machine problem for I~2, consider its LP schedule. Denote by FjLP the flow time in the LP schedule. We can get a lower bound on OPT(I~2) as
(23)OPT(I~2)≥∑j∈I~2‍wjFjLP+12(1-1m)∑j∈I~2‍wjpj≥∑j∈I~2‍pjFj′+12(1-1m)∑j∈I~2‍pj2.
Another trivial lower bound onOPT(I~2) is
(24)OPT(I~2)≥∑j∈I~2‍wjpj=∑j∈I~2‍pj2.
Combining (22),(23), and (24), we have
(25)∑j∈I~2wjFjOPT(I~2)≤∑j∈I~2pjFj′+(1-(1/m))∑j∈I~2pj2+(t′-t)∑j∈I~2pimax{∑j∈I~2pj2,∑j∈I~2pjFj′+(1/2)(1-(1/m))∑j∈I~2pj2}.
Similar to the analysis of the two cases in the proof of Lemma5, we can obtain
(26)∑j∈I~2pjFj′+(1-(1/m))∑j∈I~2pj2max{∑j∈I~2pj2,∑j∈I~2pjFj′+(1/2)(1-(1/m))∑j∈I~2pj2}≤32-12m.
In addition, it can be obtained fromt′-t≤pmax that
(27)(t′-t)∑j∈I~2pj∑j∈I~2pj2≤maxj∈I~2pmaxpj≤P.
According to the above analysis, we can obtain(28)∑j∈I~2wjFjOPT(I~2)≤P+32-12m
and prove relation (19).
By repeating the above transformation, we can get a sequence of intermediate instances with (19) satisfied and finish the proof.Figure 2
The schedule obtained by WSPT forI2 in the case of parallel machines.Lemma 7.
In the case of parallel machines, for the instanceI3 obtained in Lemma 2, one has
(29)ALG(I3)OPT(I3)≤P+32-12m.Proof.
For ease of presentation, we still take an instance with three machines; for example, see Figure3. Assume that these jobs with positive infinite weights start being processed at the time t. t′ is the latest starting time of jobs among all the machines before t. t′′ is the latest completion time of jobs which start before t. Denote the maximal processing time among all the jobs by pmax; then, t′′-t′≤pmax. We only need to consider these jobs with positive infinite weights in the last subblock. Then, the proof is similar to the one for Lemma 6 and the detailed procedure is omitted.Figure 3
The schedule obtained by WSPT forI3 in the case of parallel machines.Following Lemmas2, 6, and 7, we can immediately get the competitive performance of WSPT for the case of parallel machines.Theorem 8.
The WSPT algorithm is(P+(3/2)-(1/2m))-competitive for Pm|rj|∑‍wjFj(m>1).


## 5. Concluding Remarks

In this work, we consider the single and parallel machines online scheduling problem of minimizing the total weighted flow time. We show that WSPT rule is optimal with the competitive ratio ofP+1 for the single machine problem, where P is the ratio of the longest to the shortest processing time. We further prove that the WSPT rule is (P+(3/2)-(1/2m))-competitive for the case of parallel machines (m>1), which is consistent with the case of single machine problem.In the competitive analysis, we introduce an intuitive and systematic method. The method is aiming to derive an upper bound on the competitive ratio of the online algorithm. The analysis method exploits the possible structure of the worst-case instance with respect to the given online algorithm. The basic idea behind it is to begin with an arbitrary instance and transform it by modifying the instance, such that the modified instance shows a more special structure of which we can take advantage to analyze the performance ratio. The analysis method deserves to be extended to other online algorithms in our further work.



---

*Source: 343287-2013-10-07.xml*