Longest-processing-time-first scheduling

Longest-processing-time-first (LPT) is a greedy algorithm for job scheduling.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 15 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

Longest-processing-time-first (LPT) is a greedy algorithm for job scheduling. The input to the algorithm is a set of jobs, each of which has a specific processing-time. There is also a number m specifying the number of machines that can process the jobs.

The LPT algorithm works as follows: # Order the jobs by descending order of their processing-time, such that the job with the longest processing time is first. # Schedule each job in this sequence into a machine in which the current load (= total processing-time of scheduled jobs) is smallest. Step 2 of the algorithm is essentially the list-scheduling (LS) algorithm.

The difference is that LS loops over the jobs in an arbitrary order, while LPT pre-orders them by descending processing time. LPT was first analyzed by Ronald Graham in the 1960s in the context of the identical-machines scheduling problem. Later, it was applied to many other variants of the problem.

LPT can also be described in a more abstract way, as an algorithm for multiway number partitioning. The input is a set S of numbers, and a positive integer m; the output is a partition of S into m subsets. LPT orders the input from largest to smallest, and puts each input in turn into the part with the smallest sum so far.

Longest-processing-time-first (LPT) is a greedy algorithm for job scheduling. The input to the algorithm is a set of jobs, each of which has a specific processing-time. There is also a number m specifying the number of machines that can process the jobs.

The LPT algorithm works as follows: Order the jobs by descending order of their processing-time, such that the job with the longest processing time is first. Schedule each job in this sequence into a machine in which the current load (= total processing-time of scheduled jobs) is smallest. Step 2 of the algorithm is essentially the list-scheduling (LS) algorithm.

The difference is that LS loops over the jobs in an arbitrary order, while LPT pre-orders them by descending processing time. LPT was first analyzed by Ronald Graham in the 1960s in the context of the identical-machines scheduling problem. Later, it was applied to many other variants of the problem.

LPT can also be described in a more abstract way, as an algorithm for multiway number partitioning. The input is a set S of numbers, and a positive integer m; the output is a partition of S into m subsets. LPT orders the input from largest to smallest, and puts each input in turn into the part with the smallest sum so far.

If the input set is S = {4, 5, 6, 7, 8} and m = 2, then the resulting partition is {8, 5, 4}, {7, 6}. If m = 3, then the resulting 3-way partition is {8}, {7, 4}, {6, 5}. A more detailed analysis yields a factor of \frac{4m-1}{3m} = \frac{4}{3}-\frac{1}{3 m} times the optimal (minimum) largest sum.

(for example, when m =2 this ratio is 7/6\approx 1.167 ). The factor \frac{4m-1}{3m} is tight. Suppose there are 2 m+1 inputs (where m is even): 2 m-1,2 m-1, 2 m-2,2 m-2, \ldots, m+1,m+1, m,m, m . Then the greedy algorithm returns: 2 m-1,m,m 2 m-1,m 2 m-2,m+1 2 m-2,m+1 , ...

3 m/2,3 m/2-1 3 m/2,3 m/2-1 with a maximum of 4 m-1 , but the optimal partition is: m,m,m 2 m-1,m+1 2 m-1,m+1 2 m-2,m+2 2 m-2,m+2 ... 3 m/2,3 m/2 with a maximum of 3 m . Suppose that, in the greedy part P with the max-sum, there are L inputs. Then, the approximation ratio of the greedy algorithm is \frac{L+1}{L}-\frac{1}{L m} = 1 + \frac{1}{L} - \frac{1}{L m} .

It is tight for L≥3 (For L=3, we get the general factor \frac{4}{3}-\frac{1}{3 m} ). Proof. Denote the numbers in P by x 1 ,...,x L . Before x L was inserted into P, its sum was smallest.

Therefore, the average sum per part is at least the sum x 1 +...+x L-1 + x L /m. The optimal max-sum must be at least the average sum. In contrast, the greedy sum is x 1 +...+x L-1 +x L. So the difference is at most (1-1/m)x L , which by (1) is at most (1-1/m)*OPT/L. So the ratio is at most (1 + 1/L - 1/Lm). Every greedy bin P i contains at most one input weakly-larger than 3/2.

Proof: Let P i be the first greedy bin which is assigned two such inputs. Since inputs are assigned in descending order, P i is the first greedy bin assigned two inputs. This means that it must contain the smallest two inputs from among the largest m+1 inputs.

Moreover, since the sum of these two items is at least 3/2+3/2=3, P i is not assigned any other input. On the other hand, by the pigeonhole principle, there must be some optimal bin Q j that contains some two inputs from among the largest m+1 inputs; so P i is dominated by Q j . During the run of the greedy algorithm, the sum in every bin P i becomes at least 8/3 before the sum of any bin exceeds 4.

Proof: Let y be the first input added to some bin P i , which made its sum larger than 4. Before y was added, P i had the smallest sum, which by assumption was smaller than 8/3; this means that y>4/3. Let T denote the set of all inputs from the first one down to y; all these inputs are larger than 4/3 too.

Since P i was smaller than 8/3, it contained exactly one item x from T. So now P i contains exactly 2 items {x,y}, and remains with these 2 items until the algorithm ends. Let m be the number of items from the first one down to x. We now show a contradiction by counting the items in T in two ways. First, consider the n optimal bins.

If any such bin contains an item at least as large as x, then it cannot contain any other item of T, since otherwise it dominates {x,y}. Moreover, any such bin cannot contain three items from T, since the sum of any two of them is larger than 8/3, which is larger than x; and the third one is at least y, so it dominates {x,y}.

Therefore, the number of items in T is at most 1*m + 2*(n-m) = 2n-m. Now, consider the n greedy bins. When y is added to the bundle containing x, it is the bundle with the smallest sum.

Therefore, all elements of T that are smaller than x, must be in a greedy bin with at least one other item of T. The same is true for x and y. Therefore, the number of items in T is at least (m-1)+2*(n-m+1) = 2n-m+1 - contradiction. We can assume, without loss of generality, that all inputs are either smaller than 1/3, or at least 1. Proof: Suppose some input x is in (1/3,1).

We replace x with 1. This obviously does not decrease the optimal min-sum. We show that it does not change the greedy min-sum.

We know that some greedy bundle P i has a final sum larger than 4. Before the last input was added into P i , its sum was smaller than 3; so P i became larger than 4 when some input larger than 1 was added to it. By the previous lemma, at that point the sum of all other greedy bundles was at least 8/3.

The algorithm arrives at x afterwards. Once the algorithm adds x to some bin P j , the sum of P j becomes at least 8/3+1/3=3, so no more items are added into P j . So P j contains only one input with size in [1/3,1). Once x is replaced with 1, it is still inserted into P j , and its sum is still above 3.

So the greedy min-sum does not change. We can now partition the inputs into small (less than 1/3) and large (at least 1). The set of small items in P i is denoted by S i . Note that, when the algorithm starts processing small items, the sum in all bundles is at least 8/3.

The proof that a minimal counterexample does not exist uses a weighting scheme. Each input x is assigned a weight w(x) according to its size and greedy bundle P i : If x is a large item: If x is the single large item in P i , then w(x)=8/3. If P i contains exactly two items {x,y} and both of them are large, and x>y, and sum(P i )≥3, then w(x)=8/3.

Otherwise, w(x)=4/3. If x is a small item: if sum(P i )≥3, then w(x) = 4x/(3 sum(S i )); so w(S i ) = 4/3. if sum(P i ) i )); so w(S i ) = 2/3. This weighting scheme has the following properties: If x≥2, then w(x)=8/3.

Proof: x is large. Suppose it is in P i . If P i contains another large item y, then x+y≥3 so there is no other item in P i . Moreover, x>y since there is at most one item larger than 3/2. So w(x)=8/3.

If x 2x. Proof: x is small. Suppose it is in P i . If sum(P i )≥3 then, since sum(P i ) was smaller than 3 before x was added to it, it is now smaller than 10/3. But when the algorithm started processing small items, sum(P i ) was at least 8/3.

This means that sum(S i ) i )) > 2x. If sum(P i ) i ) i )) > 2x. The weight of every greedy bin P i is at most 4, and the weight of at least one greedy bin is at most 10/3. Proof: If all inputs in P i are large, then it contains either a single input with weight 8/3, two inputs with weights 8/3+4/3, or three inputs with weights 4/3+4/3+4/3.

If some inputs in P i are small, then their total weight is at most 4/3. There are at most two large inputs, and their weights are either 8/3 or 4/3+4/3. Finally, the weight of the greedy bin with sum smaller than 3 is at most 8/3 (if it has only large inputs) or 10/3 (if it has some small inputs).

The weight of every optimal bin Q j is at least 4. Proof: If Q j contains only small items, then each of them satisfies w(x) > 2x, so w(Q j ) > 2 sum(Q j ) ≥ 8. If Q j contains exactly one large item x, then it must contain some small items whose sum is at least 4-x and weight at least 8-2x. Then, either x j contains exactly two large items x>y, and x≥2, then there is at least 8/3+4/3=4.

If x+y≤10/3, then the sum of small items must be at least 2/3, so the total weight is at least 4/3+4/3+2*2/3=4. Otherwise, x>5/3. So x was the first input in some greedy bin P m . Let z be the second input added into P m . If x+z≥3, then there are no more inputs in P m , so w(x)=8/3 and we are done.

Otherwise, x+z j , and suppose it is in some greedy bin P i . If sum(P i ) i implies that v > 4-sum(large-items-in-P i ) > 1+sum(small-items-in-P i ). Therefore, 1+sum(S i )+x i ) i ) j ). So w(t) = 2t/(3sum(S i )) > 4t/(3sum(small-items-in-Q j )). If sum(P i )≥3, and sum(S i )≤1, then w(t)=4/3 and we are done. Since sum(P i ) was less than 3 before t was added into it, sum(P i ) i )/2.

The fact that v was not put in P i implies that v > 4-sum(large-items-in-P i ) > 1+sum(small-items-in-P i )/2. Similariy to the previous paragraph, w(t) > 4t/(3sum(small-items-in-Q j )). Therefore, the total weight of all small items in Q j is at least 4/3, so the total weight of Q j is at least 4/3+10/3>4.

If Q j contains exactly three or more large items, then its total weight is at least 4/3+4/3+4/3=4. The last two claims are contradictory, since the former implies that the weight of all inputs is at most 4m-2/3, and the latter implies that the weight of all inputs is at least 4m. Therefore, a counterexample does not exist.

A more sophisticated analysis shows that the ratio is at most \frac{3 m-1}{4 m-2} (for example, when m=2 the ratio is 5/6). The expected largest sum for m=2 machines is at least \frac{n}{4}+\frac{1}{4n+4} and at most \frac{n}{4}+\frac{e}{2n+2} , where n is the number of inputs.

The largest sum is at most 1 + O(\log{\log{n}}/n) times the optimum almost surely, and 1 + O(1/n) in expectation, where n is the number of inputs. The difference between the LPT largest sum and the optimal largest sum is at most O(\log{n}/n) almost surely (for uniform or negative exponential distributions), and at most O(m^2/n) in expectation (for uniform distribution).

These results hold also for machines with different speeds. Gonzalez, Ibarra and Sahni show that the approximation ratio of LPT with m uniform machines is at most 2 m/(m+1) . It is not tight, but there is an asymptotic lower bound of 1.5 when m approaches infinity.

For the special case of m=2 machines, the approximation ratio is at most (1+\sqrt{17})/4\approx 1.281 and it is tight. Mireault, Orlin and Vohra study a setting with two machines, in which one machine is q times faster than the other. They compute the approximation ratio of LPT as a function of q. When q=1, their result coincides with the 7/6 factor known for identical machines.

Koulamas and Kyparisis present a modification of LPT in which the three longest jobs are scheduled optimally, and the remaining jobs are scheduled based on the LPT rule. The approximation ratio for two machines is \sqrt{1.5}\approx 1.2247 and it is tight. Another constraint is that the number of jobs on all machines should be n/m rounded either up or down.

In an adaptation of LPT called restricted LPT or RLPT, inputs are assigned in pairs - one to each machine (for m=2 machines). The resulting partition is balanced by design. Coffman, Frederickson and Lueker show that the expected largest sum of RLPT when inputs are uniformly-distributed random variables is exactly \frac{n}{4}+\frac{1}{2n+2} .

The expected difference between the largest and smallest sum is \Theta(1/n) . Often, the inputs come online, and their sizes becomes known only when they arrive. In this case, it is not possible to sort them in advance. List scheduling is a similar algorithm that takes a list in any order, not necessarily sorted.

Its approximation ratio is \frac{2 m-1}{m} = 2-\frac{1}{m} . A more sophisticated adaptation of LPT to an online setting attains an approximation ratio of 3/2.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1360436379 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001360436379 · captured 1782042667.0 · version history

Cite this page as: encyclopegia.org, “Longest-processing-time-first scheduling”, snapshot enwiki-001360436379. https://encyclopegia.org/a/longest-processing-time-first-scheduling

Sources cited in this revision

19 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.