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.
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 4 3 {\displaystyle {\frac {4}{3}}} times the optimal (minimum) largest sum. A more detailed analysis yields a factor of 4 m − 1 3 m = 4 3 − 1 3 m {\displaystyle {\frac {4m-1}{3m}}={\frac {4}{3}}-{\frac {1}{3m}}} times the optimal (minimum) largest sum. (for example, when m =2 this ratio is 7 / 6 ≈ 1.167 {\displaystyle 7/6\approx 1.167} ). The factor 4 m − 1 3 m {\displaystyle {\frac {4m-1}{3m}}} is tight. Suppose there are 2 m + 1 {\displaystyle 2m+1} inputs (where m is even): 2 m − 1 , 2 m − 1 , 2 m − 2 , 2 m − 2 , … , m + 1 , m + 1 , m , m , m {\displaystyle 2m-1,2m-1,2m-2,2m-2,\ldots ,m+1,m+1,m,m,m} . Then the greedy algorithm returns:
2 m − 1 , m , m {\displaystyle 2m-1,m,m}
2 m − 1 , m {\displaystyle 2m-1,m}
2 m − 2 , m + 1 {\displaystyle 2m-2,m+1}
2 m − 2 , m + 1 {\displaystyle 2m-2,m+1} , ...
3 m / 2 , 3 m / 2 − 1 {\displaystyle 3m/2,3m/2-1}
3 m / 2 , 3 m / 2 − 1 {\displaystyle 3m/2,3m/2-1}
with a maximum of 4 m − 1 {\displaystyle 4m-1} , but the optimal partition is:
m , m , m {\displaystyle m,m,m}
2 m − 1 , m + 1 {\displaystyle 2m-1,m+1}
2 m − 1 , m + 1 {\displaystyle 2m-1,m+1}
2 m − 2 , m + 2 {\displaystyle 2m-2,m+2}
2 m − 2 , m + 2 {\displaystyle 2m-2,m+2}
...
3 m / 2 , 3 m / 2 {\displaystyle 3m/2,3m/2}
with a maximum of 3 m {\displaystyle 3m} .
Input consideration An even more detailed analysis takes into account the number of inputs in the max-sum part.
… excerpt ends here. Continue reading the full article.
