Algorithm for job scheduling
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:
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.
Examples.
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}.
Properties.
LPT might not find the optimal partition. For example, in the above instance the optimal partition {8,7}, {6,5,4}, 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("n" log "n") 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 (the largest sum or the smallest sum of a subset in the output) 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 formula_1 times the optimal (minimum) largest sum.
A more detailed analysis yields a factor of formula_2 times the optimal (minimum) largest sum. (for example, when "m" =2 this ratio is formula_3).
The factor formula_4 is tight. Suppose there are formula_5 inputs (where "m" is even): formula_6. Then the greedy algorithm returns:
with a maximum of formula_13, but the optimal partition is:
with a maximum of formula_20.
Input consideration.
An even more detailed analysis takes into account the number of inputs in the max-sum part.
Worst-case minimum sum.
In the worst case, the "smallest" sum in the returned partition is at least formula_24 times the optimal (maximum) 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...,P"m", and the optimal partition by Q1...,Q"m". Some properties of a minimal counterexample are:
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 Pi:
This weighting scheme has the following properties:
Upper bound on the ratio.
A more sophisticated analysis shows that the ratio is at most formula_25 (for example, when "m"=2 the ratio is 5/6).
Tightness and example.
The above ratio is tight.
Suppose there are 3"m"-1 inputs (where "m" is even). The first 2"m" inputs are: 2"m"-1, 2"m"-1, 2"m"-2, 2"m"-2, ..., "m", "m". The last "m"-1 inputs are all "m". Then the greedy algorithm returns:
with a minimum of 3"m"-1. But the optimal partition is:
with a minimum of 4"m"-2.
Restricted LPT.
There is a variant of LPT, called Restricted-LPT or RLPT, in which the inputs are partitioned into subsets of size "m" called "ranks" (rank 1 contains the largest "m" inputs, rank 2 the next-largest "m" inputs, etc.). The inputs in each rank must be assigned to "m" different bins: rank 1 first, then rank 2, etc. The minimum sum in RLPT is at most the minimum sum at LPT. The approximation ratio of RLPT for maximizing the minimum sum is at most "m".
Average-case maximum sum.
In the average case, if the input numbers are distributed uniformly in [0,1], then the largest sum in an LPT schedule satisfies the following properties:
General objectives.
Let "Ci" (for "i" between 1 and "m") be the sum of subset "i" in a given partition. Instead of minimizing the objective function max("Ci"), one can minimize the objective function max("f"("Ci")), where "f" is any fixed function. Similarly, one can minimize the objective function sum("f"("Ci")). Alon, Azar, Woeginger and Yadid prove that, if "f" satisfies the following two conditions:
Then the LPT rule has a finite approximation ratio for minimizing sum("f"("Ci")).
Performance with divisible item sizes.
An important special case is that the item sizes form a "divisible sequence" (also called "factored"). A special case of divisible item sizes occurs in memory allocation in computer systems, where the item sizes are all powers of 2. If the item sizes are divisible, and in addition, the largest item sizes divides the bin size, then LPT always finds a scheduling that minimizes the maximum size,Thm.4 and maximizes the minimum size.Thm.5 
Adaptations to other settings.
Besides the simple case of identical-machines scheduling, LPT has been adapted to more general settings.
Uniform machines.
In uniform-machines scheduling, different machines may have different speeds. The LPT rule assigns each job to the machine on which its "completion time" will be earliest (that is, LPT may assign a job to a machine with a "larger" current load, if this machine is so fast that it would finish that job "earlier" than all other machines).
Cardinality constraints.
In the balanced partition problem, there are constraints on the "number" of jobs that can be assigned to each machine. A simple constraint is that each machine can process at most "c" jobs. The LPT rule assigns each job to the machine with the smallest load from among those with fewer than "c" jobs. This rule is called "modified LPT" or "MLPT".
Another constraint is that the number of jobs on all machines should be formula_38 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.
Kernel constraints - non-simultaneous availability.
In the "kernel partitioning problem", there are some "m" pre-specified jobs called kernels, and each kernel must be scheduled to a unique machine. An equivalent problem is scheduling when machines are available in different times: each machine "i" becomes available at some time "ti ≥" 0 (the time "ti" can be thought of as the length of the kernel job).
A simple heuristic algorithm, called SLPT, assigns each kernel to a different subset, and then runs the LPT algorithm.
Online settings.
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 formula_44.
A more sophisticated adaptation of LPT to an online setting attains an approximation ratio of 3/2.
References.
 ;templatestyles src="Reflist/styles.css" / ;