# A Competitive Online Algorithm for Minimizing Total Weighted Completion Time on Uniform Machines

Authors: Xuyang Chu; Jiping Tao
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

We consider the classic online scheduling problem onm uniform machines in the online setting where jobs arrive over time. Preemption is not allowed. The objective is to minimize total weighted completion time. An online algorithm based on the directly waiting strategy is proposed. Its competitive performance is proved to be max2smax1−1/2∑si,2smax/1+smax2.5−1/2m by the idea of instance reduction, where sm is the fastest machine speed after being normalized by the slowest machine speed.


---

## Body

## 1. Introduction

Scheduling is a commonly used term in several different contexts including production management, service operations, and computer systems. In a general sense, scheduling is a process of allocating some scarce resources to different activities. It aims to improve the effectiveness and/or efficiency to implement these activities. It is for this fact that scheduling has attracted numerous interests of both practitioners and researchers. In academia, thousands of papers have been published with scheduling as topics. These works can be roughly classified into two categories, namely, application-oriented research and theoretical research.From a perspective of applications, researchers try to provide a solution method for a given scheduling problem by utilizing mathematical or computation techniques. The effectiveness and efficiency of the proposed approach are often judged by its performance on randomly generated or benchmark instances or some case data. Along this line, a rich variety of scheduling problems have been investigated, motivated by different applications from real-world situations. Among these problems, a great many are focused on scheduling arising in industries of production and manufacturing. In this field, most of the work can be divided into four types in terms of solution methodology, which are analytical approaches (e.g., branch and bound [1], Lagrangian relaxation [2], and column generation [3]), heuristic dispatch rules [4], metaheuristics (e.g., simulated annealing [5] and genetic algorithms [6]), and machine learning methods (e.g., neural network [7], decision tree [8], and ensemble methods [9]). The detailed discussion of these methods is beyond the scope of this paper. The abovementioned references are just some of the landmark or representative papers in each field. Interested readers can further refer to some classical books (e.g., Brucker [10] and Pinedo [11]). In addition to the abovementioned work about shop-level scheduling methods, some attention has been paid on scheduling-related problems from the perspective of planning and management. For example, Sastoque Pinilla et al. [12] conducted a case study about technology readiness level (TRL) 5C7 project management in the aircraft industry. In addition, with the new requirements and challenges occurring in the context of Industry 4.0, some new technologies and ideas such as Internet of things, cyber-physical systems, and big data analysis have been introduced into the scheduling research [13–15].In contrast, from a theoretical perspective, researchers first try to understand the computational complexity of a given scheduling problem. If the problem is computationally tractable, they then develop a polynomial algorithm that can give optimal solutions in polynomial time for any instance of the problem. If the problem is computationally intractable, they design an algorithm and evaluate it by its theoretically guaranteed performance rather than its performance in numeric simulations. The theoretically guaranteed performance often refers to the worst-case performance. Along this line, most of the work is focused on some classical and simplified scheduling models that are abstracted from similar applications, which can be often denoted by the widely used three-field classification scheme [16]. These models can be further divided into two categories in terms of whether the full information about jobs is known at the outset or not, namely, off-line models and online models. For the former category, some pioneering works can be found in [17] and [18]. For the online category, some representative works include Hoogeveen and Vestjens [19], Anderson and Potts [20], and Correa and Wagner [21]. Interested readers can further refer to a review by Potts and Strusevich [22]. Following this line of theoretical research, we consider a classical online scheduling problem in this work.


### 1.1. Problem Formulation

Formally, there is a sequence of jobs denoted byJ1,J2,…,Jn, which must be scheduled on one of m uniform machines without interruption. Here, uniform means that each machine has a job-independent speed. Each job Jj is characterized by a release time rj, a processing requirement pj, and a positive weight wj. When a job is assigned on a machine, the processing time is its processing requirement divided by the machine speed. Without loss of the generality, we assume that the machines are ordered by a nondecreasing speed 1=s1≤s2≤⋯≤sm. The objective is to minimize the total weighted completion time of all the jobs. We focus our attention on the online setting, which means that all the characteristics about one job is not revealed to the scheduling algorithm until it is released at its release time. The problem can be denoted by Qmrj,online∑wjCj.


### 1.2. Related Work

In the online setting, parallel machine scheduling problem has obtained much attention. For the case of identical machines, many efficient online algorithms were presented [21, 23, 24]. When it comes to the setting of uniform machines, i.e., each machine has a different and job-independent speed, most of the work was focused on the objective of minimizing the makespan [25–27]. For the objective of minimizing the total completion time, to the best of our knowledge, the only constant competitive algorithm was the one presented by Hall et al. [18]. They designed a 8+ε-competitive algorithm. The result had remained unchanged for more than ten years until Liu et al. [28] extended the result about a two-machine scheduling problem [29] and proposed an online algorithm with a competitive performance of 4m−3+3/2 . It performs better than the 8-competitive algorithm when the machine number is not too larger. However, the competitive ratio tends to infinity with m increasing. As mentioned by Hoogeveen and Vestjens [19], for the single-machine case, any online algorithm that schedules a job as soon as the machine is available has an unbounded worst-case performance. The conclusion also holds up for the case of uniform machines. In other words, a waiting strategy is necessary in order to guarantee bounded competitive performance. Two kinds of techniques are commonly used to design waiting strategies. The first one is to shift releasing times forward. The revised releasing times are derived either by a heuristic method [23, 30, 31] or from a preemptive schedule by solving a related relaxation problem [21, 32, 33]. The other technique is to apply a directly waiting strategy, which makes the decision to insert appropriate waiting time or to immediately schedule a job by directly comparing processing time with the current time [19, 20, 34]. Hoogeveen and Vestjens [19] first developed the technique and proposed the delayed shortest processing rule (D-SPT) for the single-machine scheduling to minimize the total completion time. They proved that the D-SPT rule is the best online algorithm for 1rj,online∑Cj. The idea behind the D-SPT rule and its competitive analysis was generalized to the weighted case by Anderson and Potts [20]. They proposed the delayed shortest weighted processing time (D-SWPT) rule and proved it is optimal for 1rj,online∑wjCj. The idea of the directly waiting strategy was further extended to design online algorithms for Pmrj,online∑wjCj by Tao [24], Tao et al. [35], and Ma and Tao [36]. The authors designed several waiting strategies and proved their competitive performance.


### 1.3. Our Contribution

ForQmrj,online∑wjCj, we construct a deterministic online algorithm and prove that it has a competitive ratio of no more than max2smax1−1/2∑si,2smax/1+smax2.5−1/2m. To the best of our knowledge, this is the first online algorithm where the approximation ratio depends on the machine speeds. If the fastest machine is not too fast, say less than 4, the algorithm beats the 8+ε-competitive algorithm [18], which is the best constant competitive algorithm so far. In addition, the performance ratio for our algorithm decreases as the machine number increases. It is contrary to the result in [28], where the competitive ratio increases as the machine number increases. Thus, our algorithm also outperforms the one in [28] in the case with a larger number of machines.The remaining sections are organized as follows. In Section2, the online algorithm is presented. The competitive analysis is detailed in Section 3. Conclusions are given in Section 4.


## 1.1. Problem Formulation

Formally, there is a sequence of jobs denoted byJ1,J2,…,Jn, which must be scheduled on one of m uniform machines without interruption. Here, uniform means that each machine has a job-independent speed. Each job Jj is characterized by a release time rj, a processing requirement pj, and a positive weight wj. When a job is assigned on a machine, the processing time is its processing requirement divided by the machine speed. Without loss of the generality, we assume that the machines are ordered by a nondecreasing speed 1=s1≤s2≤⋯≤sm. The objective is to minimize the total weighted completion time of all the jobs. We focus our attention on the online setting, which means that all the characteristics about one job is not revealed to the scheduling algorithm until it is released at its release time. The problem can be denoted by Qmrj,online∑wjCj.


## 1.2. Related Work

In the online setting, parallel machine scheduling problem has obtained much attention. For the case of identical machines, many efficient online algorithms were presented [21, 23, 24]. When it comes to the setting of uniform machines, i.e., each machine has a different and job-independent speed, most of the work was focused on the objective of minimizing the makespan [25–27]. For the objective of minimizing the total completion time, to the best of our knowledge, the only constant competitive algorithm was the one presented by Hall et al. [18]. They designed a 8+ε-competitive algorithm. The result had remained unchanged for more than ten years until Liu et al. [28] extended the result about a two-machine scheduling problem [29] and proposed an online algorithm with a competitive performance of 4m−3+3/2 . It performs better than the 8-competitive algorithm when the machine number is not too larger. However, the competitive ratio tends to infinity with m increasing. As mentioned by Hoogeveen and Vestjens [19], for the single-machine case, any online algorithm that schedules a job as soon as the machine is available has an unbounded worst-case performance. The conclusion also holds up for the case of uniform machines. In other words, a waiting strategy is necessary in order to guarantee bounded competitive performance. Two kinds of techniques are commonly used to design waiting strategies. The first one is to shift releasing times forward. The revised releasing times are derived either by a heuristic method [23, 30, 31] or from a preemptive schedule by solving a related relaxation problem [21, 32, 33]. The other technique is to apply a directly waiting strategy, which makes the decision to insert appropriate waiting time or to immediately schedule a job by directly comparing processing time with the current time [19, 20, 34]. Hoogeveen and Vestjens [19] first developed the technique and proposed the delayed shortest processing rule (D-SPT) for the single-machine scheduling to minimize the total completion time. They proved that the D-SPT rule is the best online algorithm for 1rj,online∑Cj. The idea behind the D-SPT rule and its competitive analysis was generalized to the weighted case by Anderson and Potts [20]. They proposed the delayed shortest weighted processing time (D-SWPT) rule and proved it is optimal for 1rj,online∑wjCj. The idea of the directly waiting strategy was further extended to design online algorithms for Pmrj,online∑wjCj by Tao [24], Tao et al. [35], and Ma and Tao [36]. The authors designed several waiting strategies and proved their competitive performance.


## 1.3. Our Contribution

ForQmrj,online∑wjCj, we construct a deterministic online algorithm and prove that it has a competitive ratio of no more than max2smax1−1/2∑si,2smax/1+smax2.5−1/2m. To the best of our knowledge, this is the first online algorithm where the approximation ratio depends on the machine speeds. If the fastest machine is not too fast, say less than 4, the algorithm beats the 8+ε-competitive algorithm [18], which is the best constant competitive algorithm so far. In addition, the performance ratio for our algorithm decreases as the machine number increases. It is contrary to the result in [28], where the competitive ratio increases as the machine number increases. Thus, our algorithm also outperforms the one in [28] in the case with a larger number of machines.The remaining sections are organized as follows. In Section2, the online algorithm is presented. The competitive analysis is detailed in Section 3. Conclusions are given in Section 4.


## 2. The LW-SWPR Rule

Inspired by the same idea of the directly waiting strategy mentioned above in the subsection of related work, we construct an online algorithm forQmrj,online∑wjCj. We call the proposed algorithm the limited waiting shortest weighted processing requirement rule. It is therefore abbreviated to LW-SWPR, which can be described as follows with some notations listed in Table 1:Table 1
Symbol/notation description.
Notation
Description
t
The current decision time
σ
⋅
The schedule constructed by the LW-SWPR rule for a given instance. It also refers to the objective value of the schedule when no confusion arises
S
j
The starting time of jobJj in the online schedule σ⋅
C
j
The completion time of jobJj in the online schedule σ⋅
π
⋅
The optimal schedule for a given instance. It also refers to the objective value of the schedule when no confusion arises


### 2.1. The LW-SWPR Rule

Whenever some idle machines and some jobs are available at timet, choose the machine with the highest speed and choose a job with the smallest value of the ratio pj/wj among all the arrived and unscheduled jobs. If ties occur, choose the smallest index. Say that Mi and Jj are chosen. Calculate the total processing requirement at all the busy machines at time t, which can be written as ∑Si≤t,Ci>tpi. Then, if(1)pj+∑Si≤t,Ci>tpi∑i=1msi≤t,schedule Jj on the machine Mi; otherwise, wait until a new job is released or the above inequality is satisfied.We note that the LW-SWPR rule can be reduced to the AD-SWPT rule in Tao [24] when all the machines have the same speed, i.e., the model is reduced to the identical-machine model. Next, we will show that the LW-SWPR rule has a machine number independent performance guarantee.Theorem 1.
For the online scheduling problem ofQmrj,online∑wjCj, the LW-SWPR rule is max2sm1−1/2∑si,2sm/1+sm2.5−1/2mcompetitive, where sm is the fastest machine speed after being normalized by the slowest machine speed.


## 2.1. The LW-SWPR Rule

Whenever some idle machines and some jobs are available at timet, choose the machine with the highest speed and choose a job with the smallest value of the ratio pj/wj among all the arrived and unscheduled jobs. If ties occur, choose the smallest index. Say that Mi and Jj are chosen. Calculate the total processing requirement at all the busy machines at time t, which can be written as ∑Si≤t,Ci>tpi. Then, if(1)pj+∑Si≤t,Ci>tpi∑i=1msi≤t,schedule Jj on the machine Mi; otherwise, wait until a new job is released or the above inequality is satisfied.We note that the LW-SWPR rule can be reduced to the AD-SWPT rule in Tao [24] when all the machines have the same speed, i.e., the model is reduced to the identical-machine model. Next, we will show that the LW-SWPR rule has a machine number independent performance guarantee.Theorem 1.
For the online scheduling problem ofQmrj,online∑wjCj, the LW-SWPR rule is max2sm1−1/2∑si,2sm/1+sm2.5−1/2mcompetitive, where sm is the fastest machine speed after being normalized by the slowest machine speed.


## 3. The Competitive Analysis of the LW-SWPR Algorithm

### 3.1. Instance Reduction

Since it is very difficult to directly analyze the performance for an arbitrary instance, we wish to reduce the searching space for the worst-case instances. This is just the intuition behind the instance reduction method commonly used by Tao et al. [37, 38] and Tao [24]. The basic idea is to modify an arbitrary instance to a new instance such that it has a worse performance ratio as well as a more special structure of which we can take advantage to analyze the performance ratio. To simplify the presentation, we list some instances with specified structure in Table 2. We also use these notations to refer to the instance set with the specified structure when no confusion arises. For ease of presentation, we denote that one machine is “idle”/“busy” at the time t if the machine remains idle/busy during the interval of t−ε,t+ε, where ε is an infinitely small positive value. In order to differentiate the switching time points between the busy and idle states, we further state that the time t is a “starting point of busy time”(abbreviated to SPoint) if the machine remains idle in t−ε,t and busy in t,t+ε and that the time t is an “ending point of busy time”(EPoint) if the machine is busy in t−ε,t and idle in t,t+ε.Table 2
Three types of instances with specified structure.
I
1:
Any instance for which there does not exist a timet between the earliest SPoint and the latest EPoint in the online schedule by the LW-SWPR rule, such that all the machines remain idle at t
I
2:
An instance which not only possesses the same structure asI1 but also satisfies that each job has the same weighted processing time
I
3:
An instance which not only possesses the same structure asI1 but also satisfies that jobs in the last subqueue in the online schedule have the same weighted processing time with weights tending to positive infinityFirst, we note that the worst-case instances can be obtained among the set ofI1. The reason follows. For any instance I which does not belong to the set of I1, there exists a time t between the earliest SPoint and the latest EPoint when all the machines are idle. Thus, we can split the instance I into two smaller instances that consist of jobs scheduled, respectively, before and after t. Denote the two instances by I′ and I″, respectively. According to the LW-SWPR rule, we can readily discover that σI′ and σI″ maintain the starting times of all the jobs same as in σI, i.e.,(2)σI=σI′+σI″.Given any feasible schedule ofI, we can construct two feasible schedules for I′ and I″, respectively, by keeping the starting times unchanged. Because the optimal schedule is the one with the minimum objective value among all the feasible schedules, it follows that(3)πI≥πI′+πI″.Combining (2) with (3), we can obtain(4)σIπI≤σI′+σI″πI′+πI″≤maxσI′πI′,σI″πI″,i.e., at least one of the two smaller instances can achieve a performance ratio not less than that of the original instance I. Therefore, from the perspective of worst-case instances, we need to focus only on the set of I1.Next, we show in Lemma1 that I1 can be further reduced to one of the two new instances I2 or I3 with the performance ratio not decreasing. Here, we only give some intuitive explanation while referring readers to [24] for the detailed proof. As mentioned above, jobs within each subqueue are ordered according to the WSPR rule. For I1, we can multiply the weights of some jobs by a parameter δ with not changing the mutual relations of the weighted processing requirements among jobs. The result is that jobs are scheduled in the same time intervals as in σI1 after this modification. The fact means that the objective value of the online schedule for the modified instance is a monotonously increasing linear function with respect to δ. At the same time, the optimal objective value is a concave function with respect to δ because any feasible schedule remains feasible after modification and the optimal schedule is the one with the minimum objective value among all the feasible schedules. Combining the above observations with Lemma 3.1 in [37] which states that the ratio of a convex function to a concave function is maximized at one endpoint of the supported interval, we can modify I1 to an intermediate instance with a worse performance ratio by setting δ to a specified value. By repeatedly applying the modification, we can reduce I1 to I2 or I3.Lemma 1 (see [24]).
For any instanceI1, a new instance I2 or I3 can be constructed by modifying the weights in I1, such that(5)σI1πI1≤maxσI2πI2,σI3πI3.


### 3.2. Performance Analysis ofI2 and I3

Based on the special structure thatI2 and I3 possess and the LP lower bound, we can analyze the performance ratio of I2 and I3. First, an appropriate lower bound on the optimal schedule has to be established in order to further analyze the performance ratios of I2 and I3. Because the instances I2 and I3 are associated with the special structure, we can only consider the lower bound on these special instances. This can be readily obtained from related results provided by Gu and Lu [39] and Chou et al. [40].Lemma 2 (see [39, 40]).
For theQmrj,online∑wjCj with pj=wj for each job, the optimal schedule satisfies an inequality of(6)μI≥rmin∑j=1npj+12∑si∑j=1npj2+12sm∑j=1npj2,where rmin is the earliest release time.Next, we analyze the performance ratios ofI2 and I3 by two lemmas.Lemma 3.
For any instanceI2, the online scheduling by the LW-SWPR rule satisfies(7)σI2πI2≤max2sm1−12∑si,2sm1+sm2.5−12m.Proof.
It does not change the performance ratio to multiply the weights of all the jobs by a positive constant. All the jobs inI2 have the same weighted processing time and we can normalize the ratio of pj/wj to 1, i.e., wj equals pj.
Consider the latest SPoint inσI2, and denote it as rL. The “latest” implies that jobs are continuously processed after rL at each machine without idle time between jobs. Now, we analyze the performance ratio by two cases.Case 1: there does not exist a job which is released beforerL and is scheduled at, or after, rL in σI2. Consider these jobs that start at or after rL. According to the increasing order of their starting times, denote these jobs by J1,J2,…,Jn. The assumption in this case implies that these jobs must be released at, or after, rL. Furthermore, these jobs have no effect on jobs starting before rL. Construct an intermediate instance I2′ which includes all the other jobs in I2 except J1,J2,…,Jn. Then, we have(8)σI2≤σI2′+∑j=1nSj+pjwj.Jobs are continuously processed afterrL at each machine. So, we can limit the starting time of the jth job in J1,J2,…,Jn as(9)Sj≤rL+∑Sj≤rL,Cj>rLpj+∑1≤i<jpi∑i=1msi,i=1,2,…,m,j=1,2,…,n,where the second term is to average the total processing time that have to be finished betweenrL and Sj over all the machines and ∑Sj≤rL,Cj>rLpj represents the total remaining processing time at all the machines at time rL. Let ∑Sj≤rL,Cj>rLpj:=A and ∑j=1npj:=B. Along with (7), we can limit σI2 by an upper bound as(10)σI2≤σI2′+∑j=1nSj+pjwj≤σI2′+∑j=1nrL+A+∑i=1j−1pi∑si+pjpj=σI2′+∑j=1nrL+A∑si+∑i=1jpi∑sipj+1−1∑si∑j=1npj2=σI2′+rL+A∑siB+B22∑si+1−12∑si∑j=1npj2.The second term in (10) can be regarded as the total weighted completion time of the jobs of J1,J2,…,Jn, which are continuously processed starting from the time rL+A/∑si on a single machine, with the processing time of each job multiplied by a constant of 1/∑si. Consider the set of J1,J2,…,Jn as a separate instance and further relax the release times of all the jobs to rL; then, we can develop a lower bound of the optimal schedule πI2 according to Lemma 2.(11)πI2≥πI2′+πJ1,J2,…,Jn≥πI2′+LBmJ1,J2,…,Jn=πI2′+rmin∑j∈Ipj+12∑si∑j∈Ipj2+12sm∑j∈Ipj2.According to the LW-SWPR rule, we have∑Sj≤rL,Cj>rLpj/∑si≤rL, i.e., A/∑si≤rL. Combining (9) and (10), we have(12)σI2πI2≤maxσI2′πI2′,rL+A/∑siB+B2/2∑si+1−1/2∑si∑j=1npj2rLB+B2/2∑si+1/2sm∑j=1npj2≤maxσI2′πI2′,2,2sm1−12∑si≤maxσI2′πI2′,2sm1−12∑si.Case 2: there exists at least a jobJk which is released before rL and is scheduled at, or after, rL in σI2. According to the LW-SWPR rule, Jk must satisfy(13)pk+∑Sj≤rL,Cj>rLpj∑si≥rL.
Otherwise,Jk would be scheduled before rL.
Consider the jobs that are completed afterrL. According to the increasing order of their starting times, denote these jobs by J1,J2,…,Jn. Construct an intermediate instance I2′ which includes all the other jobs in I2 except J1,J2,…,Jn. Divide the set of J1,J2,…,Jn into two subsets as follows:(14)Q1=JjSj<rL,Cj>rL∪Jk,Q2=JjSj≥rL\Jk.
Let∑Jj∈Q1pj:=A and ∑Jj∈Q2pj:=B.
Then, similar to the derivation of (9), we can limit σI2 as(15)σI2≤σI2′+rLA+B+A+B22∑si+1−12∑si∑Jj∈Q1∪Q2pj2.
By relaxing the releasing times of jobs inJ1,J2,…,Jn to 0, similar to the analysis of (10), we can limit πI2 as(16)πI2≥πI2′+A+B22∑si+12sm∑Jj∈Q1∪Q2pj2.
We can deriveA/∑si≥rL from (12). Furthermore, we can obtain ∑Jj∈Q1pj2≥A2/m because there are at most m jobs in Q1. In addition, we have the inequality of ∑i=1msi≥m. Combining these relations with (13) and (15), we can limit the performance ratio of I2 as(17)σI2πI2≤maxσI2′πI2′,rLA+B+A+B2/2∑si+1−1/2∑si∑Jj∈Q1∪Q2pj2A+B2/2∑si+1/2sm∑Jj∈Q1∪Q2pj2≤maxσI2′πI2′,AA+B/∑si+A+B2/2∑si+1−1/2∑si∑Jj∈Q1∪Q2pj2A2/2∑si+1/2sm∑Jj∈Q1∪Q2pj2≤maxσI2′πI2′,2sm+3/2−sm/∑siA2−1/2∑si∑Jj∈Q1∪Q2pj2A2/2∑si+1/2sm∑Jj∈Q1∪Q2pj2≤maxσI2′πI2′,2sm+3/2−sm/∑siA2−1/2∑siA2/mA2/2∑si+1/2smA2/∑si=maxσI2′πI2′,2smsm+12.5−12m.
The above two cases show that we can bound the performance ratio ofI2 from above equation by 2sm1−1/2∑si or 2sm/sm+12.5−1/2m or the performance ratio of an intermediate instance I2′. Furthermore, in σI2′, rL is not the latest SPoint anymore. Rewrite I2′ as I2 and repeat the above analysis until I2′ becomes an empty set. Ultimately the performance ratio of I2 can be bounded from the above equation by the larger value in 2sm1−1/2∑si and 2sm/sm+12.5−1/2m.Lemma 4.
For any instanceI3, the online schedule by the LW-SWPR rule satisfies(18)σI3πI3≤max2sm1−12∑si,2sm1+sm2.5−12m.Proof.
Jobs in the last subqueue ofI3 have the same weighted processing time with weights tending to infinity. Without loss of generality, let wj=δpj for these jobs with δ tending to infinity. In the following calculation of performance ratios, they are all carried out in the sense of limit when δ tends to infinity, with the sign of limit omitted.
Denote byQ∞ the set including all the jobs in the last subqueue of I3. Denote by rf the earliest releasing time of jobs in Q∞, and by rL the latest SPoint in I3. Next, we analyze the performance ratio of I3 by the following three cases:Case 1:rL≤rf. Considering the time rf, according to the LW-SWPR rule, we have(19)∑Sj≤rf,Cj>rfpj∑si≤rf.After the jobs which start beforerf are completed, the jobs in Q∞ are continuously processed. Assume that the jobs in Q∞ start being processed in the order of J1,J2,…,Jn. Let ∑Jj∈Q∞pj:=B. Similar to the analysis in Case 1 in the proof of Lemma 3.5, along with (19), we can derive an upper bound of σI3 as(20)σI3=σI3′+∑j=1nSj+pjwj≤σI3′+∑j=1nrf+∑Sj≤rf,Cj>rfpj+∑i=1j−1pi∑si+pjδpj≤σI3′+δ2rfB+B22∑si+1−12∑si∑j=1npj2,whereπI3′ indicates a limited value. By relaxing the releasing times of jobs in Q∞ to rf, we can similarly derive a lower bound of πI3 as(21)πI3≥πI3′+δrfB+B22m+12sm∑j=1npj2.Whenδ tends to infinity, the relations above immediately imply(22)σI3πI3≤maxσI3′πI3′,2sm1−12∑si.Case 2:rL>rf. Furthermore, jobs being processed at rL in σI3 all belong to Q∞. Similar to the proof of Lemma 3, we can construct an intermediate instance I3′ by deleting some jobs from I3 such that rL is not the latest SPoint in σI3′ anymore. Furthermore, it holds that(23)σI3πI3≤maxσI3′πI3′,2smsm+12.5−12m.Case 3:rL>rf. Furthermore, there are one or more jobs which do not belong to Q∞ and are being processed at rL in σI3. According to the improved AD-SWPT rule, these jobs must start before rf. We further analyze the performance ratio in terms of two subcases.Case 3.1: there does not exist a job inQ∞ which is released before rL and is scheduled at, or after, rL in σI3. This case implies that jobs starting at, or after, rL are all released at, or after, rL. Except these jobs, we can construct an intermediate instance I3′, which includes all the other jobs in I3. Let ∑Sj≥rLpj=B. Similar to the analysis in Case 1 in the proof of Lemma 3, we can derive(24)σI3πI3≤σI3′+δrL+∑Sj<rLpj/∑siB+B2/2∑si+1−1/2∑si∑Sj≥rLpj2πI3′+δrLB+B2/2∑si+1/2sm∑Sj≥rLpj2≤maxσI3′πI3′,2sm1−12∑si.Case 3.2: there exists at least a jobJk in Q∞ which is released before rL and is scheduled at, or after, rL in σI3. First, consider these jobs which do not belong to Q∞ and are being processed at rL in σI3. Denote the set including these jobs by Q′. Let ∑j∈Q′,Sj≤rL,Cj>rLpj:=A′. According to the LW-SWPR rule, these jobs must start being processed before rf. It follows that(25)A′∑si≤rf.
BecauseJk is released before rL and is scheduled at, or after, rL in σI3, we have(26)pk+∑Sj≤rL,Cj>rLpj∑si≥rL.
Consider the jobs inQ∞ which are completed after rL. Define two sets as follows:(27)Q1=Jj∈Q∞Sj<rL,Cj>rL∪Jk,Q2=Jj∈Q∞Sj≥rL\Jk.
Construct an intermediate instanceI3′, which includes all the jobs in I3 except jobs in Q1 and Q2. Let ∑Jj∈Q1:=A and ∑Jj∈Q2:=B. Similar to the analysis in Case 2 in the proof of Lemma 3, considering that jobs in Q1 and Q2 can be continuously processed after jobs in Q′ are completed, we can derive an upper bound on σI3 as(28)σI3≤σI3′+δrL+A′∑siA+B+A+B22∑si+1−12∑si∑Jj∈Q1∪Q2pj2.
By relaxing the releasing times of jobs inQ1 and Q2 to rf, we can also derive a lower bound on πI3 as(29)πI3≥πI3′+δrfA+B+A+B22∑si+∑Jj∈Q1∪Q2pj22.
Equation (26) implies that A+A′/∑si≥rL. Furthermore, ∑Jj∈Q1pj2≥A2/∑si because there are at most m jobs in Q1. Combining these relations with (24), (26), and (28), we have(30)σI3πI3≤maxσI3′πI3′,2,A/∑siA+B+A+B2/2∑si+1−1/2∑si∑Jj∈Q1∪Q2pj2A+B2/2∑si+1/2sm∑Jj∈Q1∪Q2pj2≤maxσI3′πI3′,2,2sm+3/2−sm/∑siA2−1/2∑si∑Jj∈Q1∪Q2pj2A2/2∑si+1/2sm∑Jj∈Q1∪Q2pj2≤maxσI3′πI3′,2,2sm+3/2−sm/∑siA2−1/2∑siA2/mA2/2∑si+1/2smA2/∑si≤maxσI3′πI3′,2smsm+12.5−12m.
The first inequality is derived by applyingA+A′/∑si≥rL and A′/∑si≤rf. The second inequality is obtained by relaxing Q2 to an empty set and then applying ∑Jj∈Q1pj2≥A2/m.
The above three cases show that we can bound the performance ratio from the above equation by the maximal value among2sm1/1−2∑si and 2sm/sm+12.5−1/2m and the performance ratio of the intermediate instance I3′. Furthermore, in σI3′, rL is not the latest SPoint anymore. Rewrite I3′ as I3 and repeat the above analysis. Ultimately the performance ratio of I3 can be bounded from the above equation by max2sm1−1/2∑si,2sm/1+sm2.5−1/2m.
Following Lemmas1, 3, and 4, we can readily obtain that LW-SWPR is max2sm1−1/2∑si,2sm/1+sm2.5−1/2m-competitive. Thus, Theorem 1 is proved.


## 3.1. Instance Reduction

Since it is very difficult to directly analyze the performance for an arbitrary instance, we wish to reduce the searching space for the worst-case instances. This is just the intuition behind the instance reduction method commonly used by Tao et al. [37, 38] and Tao [24]. The basic idea is to modify an arbitrary instance to a new instance such that it has a worse performance ratio as well as a more special structure of which we can take advantage to analyze the performance ratio. To simplify the presentation, we list some instances with specified structure in Table 2. We also use these notations to refer to the instance set with the specified structure when no confusion arises. For ease of presentation, we denote that one machine is “idle”/“busy” at the time t if the machine remains idle/busy during the interval of t−ε,t+ε, where ε is an infinitely small positive value. In order to differentiate the switching time points between the busy and idle states, we further state that the time t is a “starting point of busy time”(abbreviated to SPoint) if the machine remains idle in t−ε,t and busy in t,t+ε and that the time t is an “ending point of busy time”(EPoint) if the machine is busy in t−ε,t and idle in t,t+ε.Table 2
Three types of instances with specified structure.
I
1:
Any instance for which there does not exist a timet between the earliest SPoint and the latest EPoint in the online schedule by the LW-SWPR rule, such that all the machines remain idle at t
I
2:
An instance which not only possesses the same structure asI1 but also satisfies that each job has the same weighted processing time
I
3:
An instance which not only possesses the same structure asI1 but also satisfies that jobs in the last subqueue in the online schedule have the same weighted processing time with weights tending to positive infinityFirst, we note that the worst-case instances can be obtained among the set ofI1. The reason follows. For any instance I which does not belong to the set of I1, there exists a time t between the earliest SPoint and the latest EPoint when all the machines are idle. Thus, we can split the instance I into two smaller instances that consist of jobs scheduled, respectively, before and after t. Denote the two instances by I′ and I″, respectively. According to the LW-SWPR rule, we can readily discover that σI′ and σI″ maintain the starting times of all the jobs same as in σI, i.e.,(2)σI=σI′+σI″.Given any feasible schedule ofI, we can construct two feasible schedules for I′ and I″, respectively, by keeping the starting times unchanged. Because the optimal schedule is the one with the minimum objective value among all the feasible schedules, it follows that(3)πI≥πI′+πI″.Combining (2) with (3), we can obtain(4)σIπI≤σI′+σI″πI′+πI″≤maxσI′πI′,σI″πI″,i.e., at least one of the two smaller instances can achieve a performance ratio not less than that of the original instance I. Therefore, from the perspective of worst-case instances, we need to focus only on the set of I1.Next, we show in Lemma1 that I1 can be further reduced to one of the two new instances I2 or I3 with the performance ratio not decreasing. Here, we only give some intuitive explanation while referring readers to [24] for the detailed proof. As mentioned above, jobs within each subqueue are ordered according to the WSPR rule. For I1, we can multiply the weights of some jobs by a parameter δ with not changing the mutual relations of the weighted processing requirements among jobs. The result is that jobs are scheduled in the same time intervals as in σI1 after this modification. The fact means that the objective value of the online schedule for the modified instance is a monotonously increasing linear function with respect to δ. At the same time, the optimal objective value is a concave function with respect to δ because any feasible schedule remains feasible after modification and the optimal schedule is the one with the minimum objective value among all the feasible schedules. Combining the above observations with Lemma 3.1 in [37] which states that the ratio of a convex function to a concave function is maximized at one endpoint of the supported interval, we can modify I1 to an intermediate instance with a worse performance ratio by setting δ to a specified value. By repeatedly applying the modification, we can reduce I1 to I2 or I3.Lemma 1 (see [24]).
For any instanceI1, a new instance I2 or I3 can be constructed by modifying the weights in I1, such that(5)σI1πI1≤maxσI2πI2,σI3πI3.


## 3.2. Performance Analysis ofI2 and I3

Based on the special structure thatI2 and I3 possess and the LP lower bound, we can analyze the performance ratio of I2 and I3. First, an appropriate lower bound on the optimal schedule has to be established in order to further analyze the performance ratios of I2 and I3. Because the instances I2 and I3 are associated with the special structure, we can only consider the lower bound on these special instances. This can be readily obtained from related results provided by Gu and Lu [39] and Chou et al. [40].Lemma 2 (see [39, 40]).
For theQmrj,online∑wjCj with pj=wj for each job, the optimal schedule satisfies an inequality of(6)μI≥rmin∑j=1npj+12∑si∑j=1npj2+12sm∑j=1npj2,where rmin is the earliest release time.Next, we analyze the performance ratios ofI2 and I3 by two lemmas.Lemma 3.
For any instanceI2, the online scheduling by the LW-SWPR rule satisfies(7)σI2πI2≤max2sm1−12∑si,2sm1+sm2.5−12m.Proof.
It does not change the performance ratio to multiply the weights of all the jobs by a positive constant. All the jobs inI2 have the same weighted processing time and we can normalize the ratio of pj/wj to 1, i.e., wj equals pj.
Consider the latest SPoint inσI2, and denote it as rL. The “latest” implies that jobs are continuously processed after rL at each machine without idle time between jobs. Now, we analyze the performance ratio by two cases.Case 1: there does not exist a job which is released beforerL and is scheduled at, or after, rL in σI2. Consider these jobs that start at or after rL. According to the increasing order of their starting times, denote these jobs by J1,J2,…,Jn. The assumption in this case implies that these jobs must be released at, or after, rL. Furthermore, these jobs have no effect on jobs starting before rL. Construct an intermediate instance I2′ which includes all the other jobs in I2 except J1,J2,…,Jn. Then, we have(8)σI2≤σI2′+∑j=1nSj+pjwj.Jobs are continuously processed afterrL at each machine. So, we can limit the starting time of the jth job in J1,J2,…,Jn as(9)Sj≤rL+∑Sj≤rL,Cj>rLpj+∑1≤i<jpi∑i=1msi,i=1,2,…,m,j=1,2,…,n,where the second term is to average the total processing time that have to be finished betweenrL and Sj over all the machines and ∑Sj≤rL,Cj>rLpj represents the total remaining processing time at all the machines at time rL. Let ∑Sj≤rL,Cj>rLpj:=A and ∑j=1npj:=B. Along with (7), we can limit σI2 by an upper bound as(10)σI2≤σI2′+∑j=1nSj+pjwj≤σI2′+∑j=1nrL+A+∑i=1j−1pi∑si+pjpj=σI2′+∑j=1nrL+A∑si+∑i=1jpi∑sipj+1−1∑si∑j=1npj2=σI2′+rL+A∑siB+B22∑si+1−12∑si∑j=1npj2.The second term in (10) can be regarded as the total weighted completion time of the jobs of J1,J2,…,Jn, which are continuously processed starting from the time rL+A/∑si on a single machine, with the processing time of each job multiplied by a constant of 1/∑si. Consider the set of J1,J2,…,Jn as a separate instance and further relax the release times of all the jobs to rL; then, we can develop a lower bound of the optimal schedule πI2 according to Lemma 2.(11)πI2≥πI2′+πJ1,J2,…,Jn≥πI2′+LBmJ1,J2,…,Jn=πI2′+rmin∑j∈Ipj+12∑si∑j∈Ipj2+12sm∑j∈Ipj2.According to the LW-SWPR rule, we have∑Sj≤rL,Cj>rLpj/∑si≤rL, i.e., A/∑si≤rL. Combining (9) and (10), we have(12)σI2πI2≤maxσI2′πI2′,rL+A/∑siB+B2/2∑si+1−1/2∑si∑j=1npj2rLB+B2/2∑si+1/2sm∑j=1npj2≤maxσI2′πI2′,2,2sm1−12∑si≤maxσI2′πI2′,2sm1−12∑si.Case 2: there exists at least a jobJk which is released before rL and is scheduled at, or after, rL in σI2. According to the LW-SWPR rule, Jk must satisfy(13)pk+∑Sj≤rL,Cj>rLpj∑si≥rL.
Otherwise,Jk would be scheduled before rL.
Consider the jobs that are completed afterrL. According to the increasing order of their starting times, denote these jobs by J1,J2,…,Jn. Construct an intermediate instance I2′ which includes all the other jobs in I2 except J1,J2,…,Jn. Divide the set of J1,J2,…,Jn into two subsets as follows:(14)Q1=JjSj<rL,Cj>rL∪Jk,Q2=JjSj≥rL\Jk.
Let∑Jj∈Q1pj:=A and ∑Jj∈Q2pj:=B.
Then, similar to the derivation of (9), we can limit σI2 as(15)σI2≤σI2′+rLA+B+A+B22∑si+1−12∑si∑Jj∈Q1∪Q2pj2.
By relaxing the releasing times of jobs inJ1,J2,…,Jn to 0, similar to the analysis of (10), we can limit πI2 as(16)πI2≥πI2′+A+B22∑si+12sm∑Jj∈Q1∪Q2pj2.
We can deriveA/∑si≥rL from (12). Furthermore, we can obtain ∑Jj∈Q1pj2≥A2/m because there are at most m jobs in Q1. In addition, we have the inequality of ∑i=1msi≥m. Combining these relations with (13) and (15), we can limit the performance ratio of I2 as(17)σI2πI2≤maxσI2′πI2′,rLA+B+A+B2/2∑si+1−1/2∑si∑Jj∈Q1∪Q2pj2A+B2/2∑si+1/2sm∑Jj∈Q1∪Q2pj2≤maxσI2′πI2′,AA+B/∑si+A+B2/2∑si+1−1/2∑si∑Jj∈Q1∪Q2pj2A2/2∑si+1/2sm∑Jj∈Q1∪Q2pj2≤maxσI2′πI2′,2sm+3/2−sm/∑siA2−1/2∑si∑Jj∈Q1∪Q2pj2A2/2∑si+1/2sm∑Jj∈Q1∪Q2pj2≤maxσI2′πI2′,2sm+3/2−sm/∑siA2−1/2∑siA2/mA2/2∑si+1/2smA2/∑si=maxσI2′πI2′,2smsm+12.5−12m.
The above two cases show that we can bound the performance ratio ofI2 from above equation by 2sm1−1/2∑si or 2sm/sm+12.5−1/2m or the performance ratio of an intermediate instance I2′. Furthermore, in σI2′, rL is not the latest SPoint anymore. Rewrite I2′ as I2 and repeat the above analysis until I2′ becomes an empty set. Ultimately the performance ratio of I2 can be bounded from the above equation by the larger value in 2sm1−1/2∑si and 2sm/sm+12.5−1/2m.Lemma 4.
For any instanceI3, the online schedule by the LW-SWPR rule satisfies(18)σI3πI3≤max2sm1−12∑si,2sm1+sm2.5−12m.Proof.
Jobs in the last subqueue ofI3 have the same weighted processing time with weights tending to infinity. Without loss of generality, let wj=δpj for these jobs with δ tending to infinity. In the following calculation of performance ratios, they are all carried out in the sense of limit when δ tends to infinity, with the sign of limit omitted.
Denote byQ∞ the set including all the jobs in the last subqueue of I3. Denote by rf the earliest releasing time of jobs in Q∞, and by rL the latest SPoint in I3. Next, we analyze the performance ratio of I3 by the following three cases:Case 1:rL≤rf. Considering the time rf, according to the LW-SWPR rule, we have(19)∑Sj≤rf,Cj>rfpj∑si≤rf.After the jobs which start beforerf are completed, the jobs in Q∞ are continuously processed. Assume that the jobs in Q∞ start being processed in the order of J1,J2,…,Jn. Let ∑Jj∈Q∞pj:=B. Similar to the analysis in Case 1 in the proof of Lemma 3.5, along with (19), we can derive an upper bound of σI3 as(20)σI3=σI3′+∑j=1nSj+pjwj≤σI3′+∑j=1nrf+∑Sj≤rf,Cj>rfpj+∑i=1j−1pi∑si+pjδpj≤σI3′+δ2rfB+B22∑si+1−12∑si∑j=1npj2,whereπI3′ indicates a limited value. By relaxing the releasing times of jobs in Q∞ to rf, we can similarly derive a lower bound of πI3 as(21)πI3≥πI3′+δrfB+B22m+12sm∑j=1npj2.Whenδ tends to infinity, the relations above immediately imply(22)σI3πI3≤maxσI3′πI3′,2sm1−12∑si.Case 2:rL>rf. Furthermore, jobs being processed at rL in σI3 all belong to Q∞. Similar to the proof of Lemma 3, we can construct an intermediate instance I3′ by deleting some jobs from I3 such that rL is not the latest SPoint in σI3′ anymore. Furthermore, it holds that(23)σI3πI3≤maxσI3′πI3′,2smsm+12.5−12m.Case 3:rL>rf. Furthermore, there are one or more jobs which do not belong to Q∞ and are being processed at rL in σI3. According to the improved AD-SWPT rule, these jobs must start before rf. We further analyze the performance ratio in terms of two subcases.Case 3.1: there does not exist a job inQ∞ which is released before rL and is scheduled at, or after, rL in σI3. This case implies that jobs starting at, or after, rL are all released at, or after, rL. Except these jobs, we can construct an intermediate instance I3′, which includes all the other jobs in I3. Let ∑Sj≥rLpj=B. Similar to the analysis in Case 1 in the proof of Lemma 3, we can derive(24)σI3πI3≤σI3′+δrL+∑Sj<rLpj/∑siB+B2/2∑si+1−1/2∑si∑Sj≥rLpj2πI3′+δrLB+B2/2∑si+1/2sm∑Sj≥rLpj2≤maxσI3′πI3′,2sm1−12∑si.Case 3.2: there exists at least a jobJk in Q∞ which is released before rL and is scheduled at, or after, rL in σI3. First, consider these jobs which do not belong to Q∞ and are being processed at rL in σI3. Denote the set including these jobs by Q′. Let ∑j∈Q′,Sj≤rL,Cj>rLpj:=A′. According to the LW-SWPR rule, these jobs must start being processed before rf. It follows that(25)A′∑si≤rf.
BecauseJk is released before rL and is scheduled at, or after, rL in σI3, we have(26)pk+∑Sj≤rL,Cj>rLpj∑si≥rL.
Consider the jobs inQ∞ which are completed after rL. Define two sets as follows:(27)Q1=Jj∈Q∞Sj<rL,Cj>rL∪Jk,Q2=Jj∈Q∞Sj≥rL\Jk.
Construct an intermediate instanceI3′, which includes all the jobs in I3 except jobs in Q1 and Q2. Let ∑Jj∈Q1:=A and ∑Jj∈Q2:=B. Similar to the analysis in Case 2 in the proof of Lemma 3, considering that jobs in Q1 and Q2 can be continuously processed after jobs in Q′ are completed, we can derive an upper bound on σI3 as(28)σI3≤σI3′+δrL+A′∑siA+B+A+B22∑si+1−12∑si∑Jj∈Q1∪Q2pj2.
By relaxing the releasing times of jobs inQ1 and Q2 to rf, we can also derive a lower bound on πI3 as(29)πI3≥πI3′+δrfA+B+A+B22∑si+∑Jj∈Q1∪Q2pj22.
Equation (26) implies that A+A′/∑si≥rL. Furthermore, ∑Jj∈Q1pj2≥A2/∑si because there are at most m jobs in Q1. Combining these relations with (24), (26), and (28), we have(30)σI3πI3≤maxσI3′πI3′,2,A/∑siA+B+A+B2/2∑si+1−1/2∑si∑Jj∈Q1∪Q2pj2A+B2/2∑si+1/2sm∑Jj∈Q1∪Q2pj2≤maxσI3′πI3′,2,2sm+3/2−sm/∑siA2−1/2∑si∑Jj∈Q1∪Q2pj2A2/2∑si+1/2sm∑Jj∈Q1∪Q2pj2≤maxσI3′πI3′,2,2sm+3/2−sm/∑siA2−1/2∑siA2/mA2/2∑si+1/2smA2/∑si≤maxσI3′πI3′,2smsm+12.5−12m.
The first inequality is derived by applyingA+A′/∑si≥rL and A′/∑si≤rf. The second inequality is obtained by relaxing Q2 to an empty set and then applying ∑Jj∈Q1pj2≥A2/m.
The above three cases show that we can bound the performance ratio from the above equation by the maximal value among2sm1/1−2∑si and 2sm/sm+12.5−1/2m and the performance ratio of the intermediate instance I3′. Furthermore, in σI3′, rL is not the latest SPoint anymore. Rewrite I3′ as I3 and repeat the above analysis. Ultimately the performance ratio of I3 can be bounded from the above equation by max2sm1−1/2∑si,2sm/1+sm2.5−1/2m.
Following Lemmas1, 3, and 4, we can readily obtain that LW-SWPR is max2sm1−1/2∑si,2sm/1+sm2.5−1/2m-competitive. Thus, Theorem 1 is proved.


## 4. Conclusions

In this work, we design an online algorithm forQmrj,online∑wjCj and prove that it is max2sm1−1/2∑si,2sm/1+sm2.5−1/2m-competitive. The result is a generalization from the identical-machine scheduling considered in [24]. Although the competitive performance is not a constant because it tends to infinity when the fastest machine speed sm tends to infinity, it still makes improvements on the existed results in some extents. The first one is that it improves the result provided by Hall et al. [18] when the fastest machine is not too fast, say less than 4. The second one is that it tends to an sm-related constant when the machine number tends to infinity. In this sense, it also improves the result provided by Liu et al. [28]. Furthermore, it is very hopeful to improve the performance guarantee to an sm-independent value if all the machines are considered besides the idle ones in the scheduling rule. The same analysis method can be employed. It deserves to be further investigated in our future work.



---

*Source: 7527862-2020-04-14.xml*