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.
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.
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 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.
When used for identical-machines scheduling, LPT attains the following approximation ratios.
In the worst case, the largest sum in the greedy partition is at most
An even more detailed analysis takes into account the number of inputs in the max-sum part.
In the worst case, the smallest sum in the returned partition is at least
times the optimal (maximum) smallest sum.
Each input x is assigned a weight w(x) according to its size and greedy bundle Pi: This weighting scheme has the following properties: A more sophisticated analysis shows that the ratio is at most
The approximation ratio of RLPT for maximizing the minimum sum is at most m. 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: Let Ci (for i between 1 and m) be the sum of subset i in a given partition.
Similarly, one can minimize the objective function sum(f(Ci)).
Alon, Azar, Woeginger and Yadid[13] prove that, if f satisfies the following two conditions: Then the LPT rule has a finite approximation ratio for minimizing sum(f(Ci)).
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.
[14]: Thm.5 Besides the simple case of identical-machines scheduling, LPT has been adapted to more general settings.
[15] 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.
This rule is called modified LPT or MLPT.
A more sophisticated adaptation of LPT to an online setting attains an approximation ratio of 3/2.