Longest-processing-time-first scheduling


Longest-processing-time-first 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:
  1. Order the jobs by descending order of their processing-time, such that the job with the longest processing time is first.
  2. Schedule each job in this sequence into a machine in which the current load is smallest.
Step 2 of the algorithm is essentially the list-scheduling 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.

Examples

If the input set is S = and m = 2, then the resulting partition is,. If m = 3, then the resulting 3-way partition is,,.

Properties

LPT might not find the optimal partition. For example, in the above instance the optimal partition,, where both sums are equal to 15. However, its suboptimality is bounded both in the worst case and in the average case; see Performance guarantees below.
The running time of LPT is dominated by the sorting, which takes O time, where n is the number of inputs.
LPT is monotone in the sense that, if one of the input numbers increases, the objective function weakly increases. This is in contrast to Multifit algorithm.

Performance guarantees: identical machines

When used for identical-machines scheduling, LPT attains the following approximation ratios.

Worst-case maximum sum

In the worst case, the largest sum in the greedy partition is at most times the optimal largest sum.
A more detailed analysis yields a factor of times the optimal largest sum..
The factor is tight. Suppose there are inputs :. Then the greedy algorithm returns:
  • ,
  • ...
with a maximum of, but the optimal partition is:
  • ...
with a maximum of.

Input consideration

An even more detailed analysis takes into account the number of inputs in the max-sum part.
  1. In each part of the greedy partition, the j-th highest number is at most .
  2. Suppose that, in the greedy part P with the max-sum, there are L inputs. Then, the approximation ratio of the greedy algorithm is. It is tight for L≥3. Proof. Denote the numbers in P by x1,...,xL. Before xL was inserted into P, its sum was smallest. Therefore, the average sum per part is at least the sum x1+...+xL-1 + xL/m. The optimal max-sum must be at least the average sum. In contrast, the greedy sum is x1+...+xL-1+xL. So the difference is at most xL, which by is at most *OPT/L. So the ratio is at most.

    Worst-case minimum sum

In the worst case, the smallest sum in the returned partition is at least times the optimal smallest sum.

Proof

The proof is by contradiction. We consider a minimal counterexample, that is, a counterexample with a smallest m and fewest input numbers. Denote the greedy partition by P1,...,Pm, and the optimal partition by Q1,...,Qm. Some properties of a minimal counterexample are:
  • The min-sum in the optimal partition is 4, and the min-sum in the greedy partition is less than 3.
  • The max-sum in the greedy partition is more than 4.
  • If sum≥3 for some greedy bin Pi, then Pi is not dominated by any optimal bin Qj. Proof: if Pi is dominated by Qj, then we can construct a smaller counterexample by decreasing m to m-1 and removing the items in Pi. The min-sum in the greedy partition remains less than 3. In the optimal partition, the items in Pi can be replaced by their dominating items in Qj, so the min-sum remains at least 4.
  • If sum≥3 for some greedy bin Pi, then Pi contains at least two numbers. Proof: if Pi contains only one number x, then it is dominated by the optimal bin Qj which contains x.givese some input x is at least 3, and the greedy algorithm puts it in some Pi. Then, since there is a bundle with sum less than 3, the greedy algorithm will not put any other input in Pi, contradicting the previous lemma.
  • Every greedy bin Pi contains at most one input weakly-larger than 3/2. Proof: Let Pi be the first greedy bin which is assigned two such inputs. Since inputs are assigned in descending order, Pi 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, Pi is not assigned any other input. On the other hand, by the pigeonhole principle, there must be some optimal bin Qj that contains some two inputs from among the largest m+1 inputs; so Pi is dominated by Qj.
  • During the run of the greedy algorithm, the sum in every bin Pi becomes at least 8/3 before the sum of any bin exceeds 4. Proof: Let y be the first input added to some bin Pi, which made its sum larger than 4. Before y was added, Pi 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 Pi was smaller than 8/3, it contained exactly one item x from T. So now Pi contains exactly 2 items, 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. 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. Therefore, the number of items in T is at most 1*m + 2* = 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 +2* = 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. Once x is replaced with 1, it is still inserted into Pj, and its sum is still above 3. So the greedy min-sum does not change.
  • We can now partition the inputs into small and large. The set of small items in Pi is denoted by Si. 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 according to its size and greedy bundle Pi:
  • If x is a large item:
  • * If x is the single large item in Pi, then w=8/3.
  • * If Pi contains exactly two items and both of them are large, and x>y, and sum≥3, then w=8/3.
  • * Otherwise, w=4/3.
  • If x is a small item:
  • * if sum≥3, then w = 4x/; so w = 4/3.
  • * if sum<3, then w = 2x/; so w = 2/3.
This weighting scheme has the following properties:
  • If x≥2, then w=8/3. Proof: x is large. Suppose it is in Pi. If Pi contains another large item y, then x+y≥3 so there is no other item in Pi. Moreover, x>y since there is at most one item larger than 3/2. So w=8/3.
  • If x<1/3, then w > 2x. Proof: x is small. Suppose it is in Pi.
  • *If sum≥3 then, since sum 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 was at least 8/3. This means that sum < 2/3, so w = 4x/ > 2x.
  • *If sum<3 then sum < 3-8/3=1/3, so w = 2x/ > 2x.
  • The weight of every greedy bin Pi is at most 4, and the weight of at least one greedy bin is at most 10/3. Proof:
  • *If all inputs in Pi 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 Pi 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 or 10/3.
  • The weight of every optimal bin Qj is at least 4. Proof:
  • *If Qj contains only small items, then each of them satisfies w > 2x, so w > 2 sum ≥ 8.
  • *If Qj 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<2 and the weight of small items is at least 8-4=4, or x in and w=8/3 and the weight of small items is at least 8-6=2. In both cases the total weight is at least 4.
  • *If Qj 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 Pm. Let z be the second input added into Pm. If x+z≥3, then there are no more inputs in Pm, so w=8/3 and we are done. Otherwise, x+z<3. Let v be the smallest input in some greedy bin whose sum exceeds 4. Since x<8/3, z must have been processed before v, so z≥v. Consider now any small item t in Qj, and suppose it is in some greedy bin Pi.
  • **If sum<3, then the fact that v was not put in Pi implies that v > 4-sum > 1+sum. Therefore, 1+sum+x < v+x ≤ z+x < 3 and sum < 2-x. This means that 2*sum < 4-2x ≤ 4-x-y ≤ sum. So w = 2t/ > 4t/.
  • **If sum≥3, and sum≤1, then w=4/3 and we are done. Since sum was less than 3 before t was added into it, sum<3+sum/2. The fact that v was not put in Pi implies that v > 4-sum > 1+sum/2. Similariy to the previous paragraph, w > 4t/.
  • **Therefore, the total weight of all small items in Qj is at least 4/3, so the total weight of Qj is at least 4/3+10/3>4.
  • *If Qj 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.