Longest-processing-time-first scheduling

<h2 id="examples">Examples</h2>
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}.

<h2 id="properties">Properties</h2>
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.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> This is in contrast to <a href="/facts/Multifit_algorithm/41TkvqaW">Multifit algorithm</a>.

<h2 id="performance-guarantees-identical-machines">Performance guarantees: identical machines</h2>
When used for <a href="/facts/Identical-machines_scheduling/lwNSXMs6">identical-machines scheduling</a>, LPT attains the following approximation ratios.

<h3>Worst-case maximum sum</h3>
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 class="footnote-ref" id="fnref:3" href="#fn:3">3</a><a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>
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.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a><a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> (for example, when m =2 this ratio is 
 
 
 
 7
 
 /
 
 6
 ≈
 1.167
 
 
 {\displaystyle 7/6\approx 1.167}
 
).<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>
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:

<ul><li>
 
 
 
 2
 m
 −
 1
 ,
 m
 ,
 m
 
 
 {\displaystyle 2m-1,m,m}
 
</li>
<li>
 
 
 
 2
 m
 −
 1
 ,
 m
 
 
 {\displaystyle 2m-1,m}
 
</li>
<li>
 
 
 
 2
 m
 −
 2
 ,
 m
 +
 1
 
 
 {\displaystyle 2m-2,m+1}
 
</li>
<li>
 
 
 
 2
 m
 −
 2
 ,
 m
 +
 1
 
 
 {\displaystyle 2m-2,m+1}
 
,</li>
<li>...</li>
<li>
 
 
 
 3
 m
 
 /
 
 2
 ,
 3
 m
 
 /
 
 2
 −
 1
 
 
 {\displaystyle 3m/2,3m/2-1}
 
</li>
<li>
 
 
 
 3
 m
 
 /
 
 2
 ,
 3
 m
 
 /
 
 2
 −
 1
 
 
 {\displaystyle 3m/2,3m/2-1}
 
</li></ul>
with a maximum of 
 
 
 
 4
 m
 −
 1
 
 
 {\displaystyle 4m-1}
 
, but the optimal partition is:

<ul><li>
 
 
 
 m
 ,
 m
 ,
 m
 
 
 {\displaystyle m,m,m}
 
</li>
<li>
 
 
 
 2
 m
 −
 1
 ,
 m
 +
 1
 
 
 {\displaystyle 2m-1,m+1}
 
</li>
<li>
 
 
 
 2
 m
 −
 1
 ,
 m
 +
 1
 
 
 {\displaystyle 2m-1,m+1}
 
</li>
<li>
 
 
 
 2
 m
 −
 2
 ,
 m
 +
 2
 
 
 {\displaystyle 2m-2,m+2}
 
</li>
<li>
 
 
 
 2
 m
 −
 2
 ,
 m
 +
 2
 
 
 {\displaystyle 2m-2,m+2}
 
</li>
<li>...</li>
<li>
 
 
 
 3
 m
 
 /
 
 2
 ,
 3
 m
 
 /
 
 2
 
 
 {\displaystyle 3m/2,3m/2}
 
</li></ul>
with a maximum of 
 
 
 
 3
 m
 
 
 {\displaystyle 3m}
 
.

<h4>Input consideration</h4>
An even more detailed analysis takes into account the number of inputs in the max-sum part.

<ol><li>In each part of the greedy partition, the j-th highest number is at most 
 
 
 
 O
 P
 T
 
 /
 
 j
 
 
 {\displaystyle OPT/j}
 
.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a></li>
<li>Suppose that, in the greedy part P with the max-sum, there are L inputs. Then, the approximation ratio of the greedy algorithm is 
 
 
 
 
 
 
 L
 +
 1
 
 L
 
 
 −
 
 
 1
 
 L
 m
 
 
 
 =
 1
 +
 
 
 1
 L
 
 
 −
 
 
 1
 
 L
 m
 
 
 
 
 
 {\displaystyle {\frac {L+1}{L}}-{\frac {1}{Lm}}=1+{\frac {1}{L}}-{\frac {1}{Lm}}}
 
.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> It is tight for L≥3 (For L=3, we get the general factor 
 
 
 
 
 
 4
 3
 
 
 −
 
 
 1
 
 3
 m
 
 
 
 
 
 {\displaystyle {\frac {4}{3}}-{\frac {1}{3m}}}
 
). Proof.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a> 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 (1-1/m)xL, which by (1) is at most (1-1/m)*OPT/L. So the ratio is at most (1 + 1/L - 1/Lm).</li></ol>
<h3>Worst-case minimum sum</h3>
In the worst case, the smallest sum in the returned partition is at least 
 
 
 
 
 
 3
 4
 
 
 
 
 {\displaystyle {\frac {3}{4}}}
 
 times the optimal (maximum) smallest sum.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>

<h4>Proof</h4>
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:

<ul><li>The min-sum in the optimal partition is 4, and the min-sum in the greedy partition is less than 3 (this is just normalization - it is without loss of generality).</li>
<li>The max-sum in the greedy partition is more than 4 (since the total sum in both partitions is the same, and it is at least 4m).</li>
<li>If sum(Pi)≥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.</li>
<li>If sum(Pi)≥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.</li>
<li>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 <a href="/facts/Pigeonhole_principle/hDks9p4n">pigeonhole principle</a>, 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.</li>
<li>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 {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.
<ul><li>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.</li>
<li>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.</li>
<li></li></ul></li>
<li>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 Pi has a final sum larger than 4. Before the last input was added into Pi, its sum was smaller than 3; so Pi 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 Pj, the sum of Pj becomes at least 8/3+1/3=3, so no more items are added into Pj. So Pj contains only one input with size in [1/3,1). 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.</li>
<li>We can now partition the inputs into small (less than 1/3) and large (at least 1). 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.</li></ul>
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:

<ul><li>If x is a large item:
<ul><li>If x is the single large item in Pi, then w(x)=8/3.</li>
<li>If Pi contains exactly two items {x,y} and both of them are large, and x>y, and sum(Pi)≥3, then w(x)=8/3.</li>
<li>Otherwise, w(x)=4/3.</li></ul></li>
<li>If x is a small item:
<ul><li>if sum(Pi)≥3, then w(x) = 4x/(3 sum(Si)); so w(Si) = 4/3.</li>
<li>if sum(Pi)<3, then w(x) = 2x/(3 sum(Si)); so w(Si) = 2/3.</li></ul></li></ul>
This weighting scheme has the following properties:

<ul><li>If x≥2, then w(x)=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(x)=8/3.</li>
<li>If x<1/3, then w(x) > 2x. Proof: x is small. Suppose it is in Pi.
<ul><li>If sum(Pi)≥3 then, since sum(Pi) 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(Pi) was at least 8/3. This means that sum(Si) < 2/3, so w(x) = 4x/(3 sum(Si)) > 2x.</li>
<li>If sum(Pi)<3 then sum(Si) < 3-8/3=1/3, so w(x) = 2x/(3 sum(Si)) > 2x.</li></ul></li>
<li>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:
<ul><li>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.</li>
<li>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.</li>
<li>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).</li></ul></li>
<li>The weight of every optimal bin Qj is at least 4. Proof:
<ul><li>If Qj contains only small items, then each of them satisfies w(x) > 2x, so w(Qj) > 2 sum(Qj) ≥ 8.</li>
<li>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 (2,3) and w(x)=8/3 and the weight of small items is at least 8-6=2. In both cases the total weight is at least 4.</li>
<li>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(x)=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.
<ul><li>If sum(Pi)<3, then the fact that v was not put in Pi implies that v > 4-sum(large-items-in-Pi) > 1+sum(small-items-in-Pi). Therefore, 1+sum(Si)+x < v+x ≤ z+x < 3 and sum(Si) < 2-x. This means that 2*sum(Si) < 4-2x ≤ 4-x-y ≤ sum(small-items-in-Qj). So w(t) = 2t/(3sum(Si)) > 4t/(3sum(small-items-in-Qj)).</li>
<li>If sum(Pi)≥3, and sum(Si)≤1, then w(t)=4/3 and we are done. Since sum(Pi) was less than 3 before t was added into it, sum(Pi)<3+sum(Si)/2. The fact that v was not put in Pi implies that v > 4-sum(large-items-in-Pi) > 1+sum(small-items-in-Pi)/2. Similariy to the previous paragraph, w(t) > 4t/(3sum(small-items-in-Qj)).</li>
<li>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.</li></ul></li>
<li>If Qj contains exactly three or more large items, then its total weight is at least 4/3+4/3+4/3=4.</li></ul></li>
<li>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.</li></ul>
<h4>Upper bound on the ratio</h4>
A more sophisticated analysis shows that the ratio is at most 
 
 
 
 
 
 
 3
 m
 −
 1
 
 
 4
 m
 −
 2
 
 
 
 
 
 {\displaystyle {\frac {3m-1}{4m-2}}}
 
 (for example, when m=2 the ratio is 5/6).<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a><a class="footnote-ref" id="fnref:13" href="#fn:13">13</a>

<h4>Tightness and example</h4>
The above ratio is tight.<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a>
Suppose there are 3m-1 inputs (where m is even). The first 2m inputs are: 2m-1, 2m-1, 2m-2, 2m-2, ..., m, m. The last m-1 inputs are all m. Then the greedy algorithm returns:

<ul><li>2m-1, m, m</li>
<li>2m-1, m, m</li>
<li>2m-2, m+1, m</li>
<li>2m-2, m+1, m</li>
<li>...</li>
<li>3 m/2, 3 m/2-1, m</li>
<li>3 m/2, 3 m/2-1</li></ul>
with a minimum of 3m-1. But the optimal partition is:

<ul><li>2m-1, 2m-1</li>
<li>2m-2, m, m</li>
<li>2m-2, m, m</li>
<li>2m-3, m+1, m</li>
<li>2m-3, m+1, m</li>
<li>...</li>
<li>3 m/2, 3 m/2-2, m</li>
<li>3 m/2, 3 m/2-2, m</li>
<li>3 m/2-1, 3 m/2-1, m</li></ul>
with a minimum of 4m-2.

<h4>Restricted LPT</h4>
There is a variant of LPT, called Restricted-LPT or RLPT,<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a> 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.

<h3>Average-case maximum sum</h3>
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:

<ul><li>The expected largest sum for m=2 machines is at least 
 
 
 
 
 
 n
 4
 
 
 +
 
 
 1
 
 4
 n
 +
 4
 
 
 
 
 
 {\displaystyle {\frac {n}{4}}+{\frac {1}{4n+4}}}
 
 and at most 
 
 
 
 
 
 n
 4
 
 
 +
 
 
 e
 
 2
 n
 +
 2
 
 
 
 
 
 {\displaystyle {\frac {n}{4}}+{\frac {e}{2n+2}}}
 
, where n is the number of inputs.<a class="footnote-ref" id="fnref:16" href="#fn:16">16</a></li>
<li>The largest sum is at most 
 
 
 
 1
 +
 O
 (
 log
 ⁡
 
 log
 ⁡
 
 n
 
 
 
 /
 
 n
 )
 
 
 {\displaystyle 1+O(\log {\log {n}}/n)}
 
 times the optimum <a href="/facts/Almost_surely/fWaxzpBA">almost surely</a>, and 
 
 
 
 1
 +
 O
 (
 1
 
 /
 
 n
 )
 
 
 {\displaystyle 1+O(1/n)}
 
 in expectation, where 
 
 
 
 n
 
 
 {\displaystyle n}
 
 is the number of inputs.<a class="footnote-ref" id="fnref:17" href="#fn:17">17</a></li>
<li>The difference between the LPT largest sum and the optimal largest sum is at most 
 
 
 
 O
 (
 log
 ⁡
 
 n
 
 
 /
 
 n
 )
 
 
 {\displaystyle O(\log {n}/n)}
 
 almost surely (for uniform or <a href="/facts/Negative_exponential_distribution/yY3EdV0u">negative exponential</a> distributions), and at most 
 
 
 
 O
 (
 
 m
 
 2
 
 
 
 /
 
 n
 )
 
 
 {\displaystyle O(m^{2}/n)}
 
 in expectation (for uniform distribution). These results hold also for <a href="/facts/Uniform-machines_scheduling/LFDtRUfD">machines with different speeds</a>.<a class="footnote-ref" id="fnref:18" href="#fn:18">18</a></li></ul>
<h3>General objectives</h3>
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<a class="footnote-ref" id="fnref:19" href="#fn:19">19</a> prove that, if f satisfies the following two conditions:

<ol><li>A strong continuity condition called Condition F*: for every ε>0 there exists δ>0 such that, if |y-x|<δx, then |f(y)-f(x)|<εf(x).</li>
<li><a href="/facts/Convex_function/IbzG5SLF">Convexity</a>.</li></ol>
Then the LPT rule has a finite approximation ratio for minimizing sum(f(Ci)).

<h3>Performance with divisible item sizes</h3>
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,<a class="footnote-ref" id="fnref:20" href="#fn:20">20</a>: Thm.4  and maximizes the minimum size.<a class="footnote-ref" id="fnref:21" href="#fn:21">21</a>: Thm.5  

<h2 id="adaptations-to-other-settings">Adaptations to other settings</h2>
Besides the simple case of identical-machines scheduling, LPT has been adapted to more general settings.

<h3>Uniform machines</h3>
In <a href="/facts/Uniform-machines_scheduling/LFDtRUfD">uniform-machines scheduling</a>, 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).<a class="footnote-ref" id="fnref:22" href="#fn:22">22</a>

<ul><li>Gonzalez, Ibarra and Sahni<a class="footnote-ref" id="fnref:23" href="#fn:23">23</a> show that the approximation ratio of LPT with m uniform machines is at most 
 
 
 
 2
 m
 
 /
 
 (
 m
 +
 1
 )
 
 
 {\displaystyle 2m/(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
 +
 
 
 17
 
 
 )
 
 /
 
 4
 ≈
 1.281
 
 
 {\displaystyle (1+{\sqrt {17}})/4\approx 1.281}
 
 and it is tight.</li>
<li>Mireault, Orlin and Vohra<a class="footnote-ref" id="fnref:24" href="#fn:24">24</a> 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.</li>
<li>Koulamas and Kyparisis<a class="footnote-ref" id="fnref:25" href="#fn:25">25</a> 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 
 
 
 
 
 
 1.5
 
 
 ≈
 1.2247
 
 
 {\displaystyle {\sqrt {1.5}}\approx 1.2247}
 
 and it is tight.</li></ul>
<h3>Cardinality constraints</h3>
In the <a href="/facts/Balanced_partition_problem/zWSTmzc5">balanced partition problem</a>, 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.

<ul><li>Kellerer and Woeginger<a class="footnote-ref" id="fnref:26" href="#fn:26">26</a> study a variant in which there are at most 3*m jobs, and each machine must contain at most 3 jobs (this can be seen as a generalization of <a href="/facts/3-partition_problem/X4uW5f57">3-partition problem</a>). They show that MLPT attains at most 
 
 
 
 (
 4
 m
 −
 1
 )
 
 /
 
 (
 3
 m
 )
 
 
 {\displaystyle (4m-1)/(3m)}
 
 of the minimum largest sum, which the same approximation ratio that LPT attains for the unconstrained problem. The bound is tight for MLPT. It is conjectured<a class="footnote-ref" id="fnref:27" href="#fn:27">27</a> that MLPT has the same approximation ratio for more general cardinality constraints (c>3). Currently, it is known that the approximation ratio of MLPT for general c>3 is at most 2.<a class="footnote-ref" id="fnref:28" href="#fn:28">28</a></li>
<li>Chen, He and Lin<a class="footnote-ref" id="fnref:29" href="#fn:29">29</a> show that, for the same problem, MLPT attains at least 
 
 
 
 (
 3
 m
 −
 1
 )
 
 /
 
 (
 4
 m
 −
 2
 )
 
 
 {\displaystyle (3m-1)/(4m-2)}
 
 of the maximum smallest sum, which is again the same ratio that LPT attains for the unconstrained problem.</li></ul>
Another constraint is that the number of jobs on all machines should be 
 
 
 
 n
 
 /
 
 m
 
 
 {\displaystyle 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).<a class="footnote-ref" id="fnref:30" href="#fn:30">30</a> The resulting partition is balanced by design.

<ul><li>Coffman, Frederickson and Lueker<a class="footnote-ref" id="fnref:31" href="#fn:31">31</a> show that the expected largest sum of RLPT when inputs are uniformly-distributed random variables is exactly 
 
 
 
 
 
 n
 4
 
 
 +
 
 
 1
 
 2
 n
 +
 2
 
 
 
 
 
 {\displaystyle {\frac {n}{4}}+{\frac {1}{2n+2}}}
 
. The expected difference between the largest and smallest sum is 
 
 
 
 Θ
 (
 1
 
 /
 
 n
 )
 
 
 {\displaystyle \Theta (1/n)}
 
.<a class="footnote-ref" id="fnref:32" href="#fn:32">32</a></li></ul>
<h3>Kernel constraints - non-simultaneous availability</h3>
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,<a class="footnote-ref" id="fnref:33" href="#fn:33">33</a> assigns each kernel to a different subset, and then runs the <a href="/facts/LPT_algorithm/EcPS5uh3">LPT algorithm</a>.

<ul><li>Lee<a class="footnote-ref" id="fnref:34" href="#fn:34">34</a> proves that this heuristic has a tight approximation ratio 
 
 
 
 
 
 
 3
 m
 −
 1
 
 
 2
 m
 
 
 
 
 
 {\displaystyle {\frac {3m-1}{2m}}}
 
 for the minimum largest sum. He then suggests running, in the second step, a modified version of LPT, and proves that it attains an approximation ratio 
 
 
 
 
 
 4
 3
 
 
 
 
 {\displaystyle {\frac {4}{3}}}
 
 .</li>
<li>Lin, Yao and He<a class="footnote-ref" id="fnref:35" href="#fn:35">35</a> prove that this heuristic has a tight approximation ratio 
 
 
 
 
 
 
 2
 m
 −
 1
 
 
 3
 m
 −
 2
 
 
 
 
 
 {\displaystyle {\frac {2m-1}{3m-2}}}
 
 for the maximum smallest sum.</li>
<li>Shen, Wang and Wang<a class="footnote-ref" id="fnref:36" href="#fn:36">36</a> study different objective functions for this setting, and present polynomial-time algorithms.</li></ul>
<h3>Online settings</h3>
Often, the inputs come <a href="/facts/Online_algorithm/64TsU7Yz">online</a>, and their sizes becomes known only when they arrive. In this case, it is not possible to sort them in advance. <a href="/facts/List_scheduling/qUscTqbx">List scheduling</a> is a similar algorithm that takes a list in any order, not necessarily sorted. Its approximation ratio is 
 
 
 
 
 
 
 2
 m
 −
 1
 
 m
 
 
 =
 2
 −
 
 
 1
 m
 
 
 
 
 {\displaystyle {\frac {2m-1}{m}}=2-{\frac {1}{m}}}
 
.
A more sophisticated adaptation of LPT to an online setting attains an approximation ratio of 3/2.<a class="footnote-ref" id="fnref:37" href="#fn:37">37</a>

<h2 id="implementations">Implementations</h2>
<ul><li>Python: there is an implementation of LPT ("greedy") <a href="https://github.com/fuglede/numberpartitioning/blob/master/src/numberpartitioning/greedy.py">in the numberpartitioning package</a>, as well as <a href="https://github.com/erelsgl/prtpy/blob/main/prtpy/partitioning/greedy.py">in the prtpy package</a>.</li></ul>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Greedy_number_partitioning/EuDV9gm8">Greedy number partitioning</a> - generalizations and extensions of LPT for the problem of multiway number partitioning.</li></ul>
<h2 id="notes">Notes</h2>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Graham, R. L. (March 1969). "Bounds on Multiprocessing Timing Anomalies". SIAM Journal on Applied Mathematics. 17 (2): 416–429. CiteSeerX 10.1.1.90.8131. doi:10.1137/0117039. JSTOR 2099572. NAID 30006801878 ProQuest 917998761. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Segal-Halevi, Erel (2021-10-17), On Monotonicity of Number-Partitioning Algorithms, arXiv:2110.08886, retrieved 2024-02-22 <a href="http://arxiv.org/abs/2110.08886" target="_blank">http://arxiv.org/abs/2110.08886</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Xiao, Xin (2017-04-01). "A Direct Proof of the 4/3 Bound of LPT Scheduling Rule". Proceedings of the 2017 5th International Conference on Frontiers of Manufacturing Science and Measuring Technology (FMSMT 2017). Atlantis Press. pp. 486–489. doi:10.2991/fmsmt-17.2017.102. ISBN 978-94-6252-331-9. <a href="978-94-6252-331-9" target="_blank">978-94-6252-331-9</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Proof. Normalize the input items such that OPT=1. This implies that the sum of all items is at most m.

Partition the items into large (more than 2/3), medium (between 1/3 and 2/3), and small (less than 1/3). Let their numbers be nL, nM and nS. In each optimal partition, each part contains at most one large item, so nL ≤ m. Moreover, each optimal part cannot contain both a large and a medium item, or three medium items; so nM ≤ 2(m-nL).

The operation of the greedy algorithm can be partitioned into three phases:

1. Allocating the large items - each of which is put in a different bin. Since nL ≤ m, when this phase completes, each bin contains at most one item, so the max-sum is at most 1.
2. Allocating the medium items. The first m-nL ones are put in empty bins, and the next m-nL ones (if any) are added into the same bins. Since nM ≤ 2(m-nL), when this phase completes, each bin contains either one large item - with sum at most 1, or at most two medium items - with sum at most 4/3.
3. Allocating the small items. Each item is added into the bin with the smallest sum. The smallest sum is at most the average sum, which is at most 1. Hence, once a small item is added, the new sum becomes at most 4/3. <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Graham, R. L. (March 1969). "Bounds on Multiprocessing Timing Anomalies". SIAM Journal on Applied Mathematics. 17 (2): 416–429. CiteSeerX 10.1.1.90.8131. doi:10.1137/0117039. JSTOR 2099572. NAID 30006801878 ProQuest 917998761. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Coffman, E. G.; Sethi, Ravi (1976-03-29). "A generalized bound on LPT sequencing". Proceedings of the 1976 ACM SIGMETRICS conference on Computer performance modeling measurement and evaluation - SIGMETRICS '76. New York, NY, USA: Association for Computing Machinery. pp. 306–310. doi:10.1145/800200.806205. ISBN 978-1-4503-7497-2. S2CID 16980306. <a href="978-1-4503-7497-2" target="_blank">978-1-4503-7497-2</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Proof. The previous proof can be refined in two ways.

First, one can prove that, once all large and medium items are allocated, the sum in each bin is at most 1.

If there are at most m-nL medium items, then each large and medium item is placed in a separate bin, so the sum is clearly at most 1.
Otherwise, denote the first m-nL medium items by top-medium items, and the others (at most m-nL) by bottom-medium items.
Assume first that item #m is larger than 1/2. This means that the items #1,...,#m are all larger than 1/2, so each must be in a different optimal part. Each of the bottom-medium items (items #m+1,...#nM) must fit into an optimal part with exactly one of the items #1,...,#m . Let us call two items matchable if their sum is at most 1, so that they can fit into the same optimal part. By Hall's theorem, each subset of k bottom-medium items must be matchable to at least k of the items #1,...,#m. In particular, the item #m+1 must be matchable to item #m; items #m+1 and #m+2 must be matchable to item #m-1; and in general, item #m+k must be matchable to item #'m-k+1. LPT indeed puts item #m+k in the same bin as #'m-k+1, so the sum of each bin is at most 1.

Second, one can prove that, when allocating the small inputs, the sum of every new bin is at most 4/3-1/(3m). There are two cases:

1. If the current smallest sum is at most 1-1/(3m), then the new sum - after adding one small input - is at most 1-1/(3m)+1/3 = 4/3-1/(3m).

2. Otherwise, all sums are larger than 1-1/(3m), so the sum of the m-1 largest bins is larger than m-1-1/3+1/(3m) = m-(4/3-1/(3m)). Since the total sum of all inputs is at most m, the new sum must be less than 4/3-1/(3m). <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Chen, Bo (1993-10-01). "A note on LPT scheduling". Operations Research Letters. 14 (3): 139–142. doi:10.1016/0167-6377(93)90024-B. ISSN 0167-6377. <a href="https://dx.doi.org/10.1016/0167-6377%2893%2990024-B" target="_blank">https://dx.doi.org/10.1016/0167-6377%2893%2990024-B</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Coffman, E. G.; Sethi, Ravi (1976-03-29). "A generalized bound on LPT sequencing". Proceedings of the 1976 ACM SIGMETRICS conference on Computer performance modeling measurement and evaluation - SIGMETRICS '76. New York, NY, USA: Association for Computing Machinery. pp. 306–310. doi:10.1145/800200.806205. ISBN 978-1-4503-7497-2. S2CID 16980306. <a href="978-1-4503-7497-2" target="_blank">978-1-4503-7497-2</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Chen, Bo (1993-10-01). "A note on LPT scheduling". Operations Research Letters. 14 (3): 139–142. doi:10.1016/0167-6377(93)90024-B. ISSN 0167-6377. <a href="https://dx.doi.org/10.1016/0167-6377%2893%2990024-B" target="_blank">https://dx.doi.org/10.1016/0167-6377%2893%2990024-B</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Deuermeyer, Bryan L.; Friesen, Donald K.; Langston, Michael A. (June 1982). "Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System". SIAM Journal on Algebraic and Discrete Methods. 3 (2): 190–196. doi:10.1137/0603019. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Csirik, János; Kellerer, Hans; Woeginger, Gerhard (June 1992). "The exact LPT-bound for maximizing the minimum completion time". Operations Research Letters. 11 (5): 281–287. doi:10.1016/0167-6377(92)90004-M. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Wu, Bang Ye (December 2005). "An analysis of the LPT algorithm for the max–min and the min–ratio partition problems". Theoretical Computer Science. 349 (3): 407–419. doi:10.1016/j.tcs.2005.08.032. <a href="https://doi.org/10.1016%2Fj.tcs.2005.08.032" target="_blank">https://doi.org/10.1016%2Fj.tcs.2005.08.032</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Deuermeyer, Bryan L.; Friesen, Donald K.; Langston, Michael A. (June 1982). "Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System". SIAM Journal on Algebraic and Discrete Methods. 3 (2): 190–196. doi:10.1137/0603019. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Walter, Rico (2013-01-01). "Comparing the minimum completion times of two longest-first scheduling-heuristics". Central European Journal of Operations Research. 21 (1): 125–139. doi:10.1007/s10100-011-0217-4. ISSN 1613-9178. S2CID 254144745. <a href="https://doi.org/10.1007/s10100-011-0217-4" target="_blank">https://doi.org/10.1007/s10100-011-0217-4</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">Coffman, E. G.; Frederickson, G. N.; Lueker, G. S. (1984-05-01). "A Note on Expected Makespans for Largest-First Sequences of Independent Tasks on Two Processors". Mathematics of Operations Research. 9 (2): 260–266. doi:10.1287/moor.9.2.260. ISSN 0364-765X. <a href="https://pubsonline.informs.org/doi/abs/10.1287/moor.9.2.260" target="_blank">https://pubsonline.informs.org/doi/abs/10.1287/moor.9.2.260</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Frenk, J.B.G.; Kan, A.H.G.Rinnooy (June 1986). "The rate of convergence to optimality of the LPT rule". Discrete Applied Mathematics. 14 (2): 187–197. doi:10.1016/0166-218X(86)90060-0. hdl:1765/11698. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">Frenk, J. B. G.; Rinnooy Kan, A. H. G. (1987-05-01). "The Asymptotic Optimality of the LPT Rule". Mathematics of Operations Research. 12 (2): 241–254. doi:10.1287/moor.12.2.241. ISSN 0364-765X. S2CID 31770203. <a href="https://pubsonline.informs.org/doi/abs/10.1287/moor.12.2.241" target="_blank">https://pubsonline.informs.org/doi/abs/10.1287/moor.12.2.241</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">Alon, Noga; Azar, Yossi; Woeginger, Gerhard J.; Yadid, Tal (1998). "Approximation schemes for scheduling on parallel machines". Journal of Scheduling. 1 (1): 55–66. doi:10.1002/(SICI)1099-1425(199806)1:1<55::AID-JOS2>3.0.CO;2-J. ISSN 1099-1425. <a href="https://onlinelibrary.wiley.com/doi/abs/10.1002/%28SICI%291099-1425%28199806%291%3A1%3C55%3A%3AAID-JOS2%3E3.0.CO%3B2-J" target="_blank">https://onlinelibrary.wiley.com/doi/abs/10.1002/%28SICI%291099-1425%28199806%291%3A1%3C55%3A%3AAID-JOS2%3E3.0.CO%3B2-J</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
<li id="fn:20">Coffman, E. G; Garey, M. R; Johnson, D. S (1987-12-01). "Bin packing with divisible item sizes". Journal of Complexity. 3 (4): 406–428. doi:10.1016/0885-064X(87)90009-4. ISSN 0885-064X. <a href="https://dx.doi.org/10.1016/0885-064X%2887%2990009-4" target="_blank">https://dx.doi.org/10.1016/0885-064X%2887%2990009-4</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></li>
<li id="fn:21">Coffman, E. G; Garey, M. R; Johnson, D. S (1987-12-01). "Bin packing with divisible item sizes". Journal of Complexity. 3 (4): 406–428. doi:10.1016/0885-064X(87)90009-4. ISSN 0885-064X. <a href="https://dx.doi.org/10.1016/0885-064X%2887%2990009-4" target="_blank">https://dx.doi.org/10.1016/0885-064X%2887%2990009-4</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></li>
<li id="fn:22">Gonzalez, Teofilo; Ibarra, Oscar H.; Sahni, Sartaj (1977-03-01). "Bounds for LPT Schedules on Uniform Processors". SIAM Journal on Computing. 6 (1): 155–166. doi:10.1137/0206013. ISSN 0097-5397. <a href="https://epubs.siam.org/doi/abs/10.1137/0206013" target="_blank">https://epubs.siam.org/doi/abs/10.1137/0206013</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></li>
<li id="fn:23">Gonzalez, Teofilo; Ibarra, Oscar H.; Sahni, Sartaj (1977-03-01). "Bounds for LPT Schedules on Uniform Processors". SIAM Journal on Computing. 6 (1): 155–166. doi:10.1137/0206013. ISSN 0097-5397. <a href="https://epubs.siam.org/doi/abs/10.1137/0206013" target="_blank">https://epubs.siam.org/doi/abs/10.1137/0206013</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></li>
<li id="fn:24">Mireault, Paul; Orlin, James B.; Vohra, Rakesh V. (1997-02-01). "A Parametric Worst Case Analysis of the LPT Heuristic for Two Uniform Machines". Operations Research. 45 (1): 116–125. doi:10.1287/opre.45.1.116. ISSN 0030-364X. <a href="https://pubsonline.informs.org/doi/abs/10.1287/opre.45.1.116" target="_blank">https://pubsonline.informs.org/doi/abs/10.1287/opre.45.1.116</a> <a href="#fnref:24" class="footnote-back-ref">↩</a></li>
<li id="fn:25">Koulamas, Christos; Kyparisis, George J. (2009-07-01). "A modified LPT algorithm for the two uniform parallel machine makespan minimization problem". European Journal of Operational Research. 196 (1): 61–68. doi:10.1016/j.ejor.2008.02.008. ISSN 0377-2217. <a href="https://www.sciencedirect.com/science/article/pii/S0377221708001938" target="_blank">https://www.sciencedirect.com/science/article/pii/S0377221708001938</a> <a href="#fnref:25" class="footnote-back-ref">↩</a></li>
<li id="fn:26">Kellerer, Hans; Woeginger, Gerhard (1993-09-07). "A tight bound for 3-partitioning". Discrete Applied Mathematics. 45 (3): 249–259. doi:10.1016/0166-218X(93)90013-E. ISSN 0166-218X. <a href="https://doi.org/10.1016%2F0166-218X%2893%2990013-E" target="_blank">https://doi.org/10.1016%2F0166-218X%2893%2990013-E</a> <a href="#fnref:26" class="footnote-back-ref">↩</a></li>
<li id="fn:27">Babel, Luitpold; Kellerer, Hans; Kotov, Vladimir (1998-02-01). "The m-partitioning problem". Mathematical Methods of Operations Research. 47 (1): 59–82. doi:10.1007/BF01193837. ISSN 1432-5217. S2CID 5594197. <a href="https://doi.org/10.1007/BF01193837" target="_blank">https://doi.org/10.1007/BF01193837</a> <a href="#fnref:27" class="footnote-back-ref">↩</a></li>
<li id="fn:28">Dell'Amico, Mauro; Martello, Silvano (2001). "Bounds for the cardinality constrained P∥Cmax problem". Journal of Scheduling. 4 (3): 123–138. doi:10.1002/jos.68. ISSN 1099-1425. <a href="https://onlinelibrary.wiley.com/doi/abs/10.1002/jos.68" target="_blank">https://onlinelibrary.wiley.com/doi/abs/10.1002/jos.68</a> <a href="#fnref:28" class="footnote-back-ref">↩</a></li>
<li id="fn:29">Chen, Shi Ping; He, Yong; Lin, Guohui (2002-03-01). "3-Partitioning Problems for Maximizing the Minimum Load". Journal of Combinatorial Optimization. 6 (1): 67–80. doi:10.1023/A:1013370208101. ISSN 1573-2886. S2CID 9053629. <a href="https://doi.org/10.1023/A:1013370208101" target="_blank">https://doi.org/10.1023/A:1013370208101</a> <a href="#fnref:29" class="footnote-back-ref">↩</a></li>
<li id="fn:30">Coffman, E. G.; Frederickson, G. N.; Lueker, G. S. (1984-05-01). "A Note on Expected Makespans for Largest-First Sequences of Independent Tasks on Two Processors". Mathematics of Operations Research. 9 (2): 260–266. doi:10.1287/moor.9.2.260. ISSN 0364-765X. <a href="https://pubsonline.informs.org/doi/abs/10.1287/moor.9.2.260" target="_blank">https://pubsonline.informs.org/doi/abs/10.1287/moor.9.2.260</a> <a href="#fnref:30" class="footnote-back-ref">↩</a></li>
<li id="fn:31">Coffman, E. G.; Frederickson, G. N.; Lueker, G. S. (1984-05-01). "A Note on Expected Makespans for Largest-First Sequences of Independent Tasks on Two Processors". Mathematics of Operations Research. 9 (2): 260–266. doi:10.1287/moor.9.2.260. ISSN 0364-765X. <a href="https://pubsonline.informs.org/doi/abs/10.1287/moor.9.2.260" target="_blank">https://pubsonline.informs.org/doi/abs/10.1287/moor.9.2.260</a> <a href="#fnref:31" class="footnote-back-ref">↩</a></li>
<li id="fn:32">Tsai, Li-Hui (1992-02-01). "Asymptotic Analysis of an Algorithm for Balanced Parallel Processor Scheduling". SIAM Journal on Computing. 21 (1): 59–64. doi:10.1137/0221007. ISSN 0097-5397. <a href="https://epubs.siam.org/doi/abs/10.1137/0221007" target="_blank">https://epubs.siam.org/doi/abs/10.1137/0221007</a> <a href="#fnref:32" class="footnote-back-ref">↩</a></li>
<li id="fn:33">Chen, S. -P.; He, Y.; Yao, E. -Y. (1996-09-01). "Three-partitioning containing kernels: Complexity and heuristic". Computing. 57 (3): 255–271. doi:10.1007/BF02247409. ISSN 1436-5057. S2CID 21935917. <a href="https://doi.org/10.1007/BF02247409" target="_blank">https://doi.org/10.1007/BF02247409</a> <a href="#fnref:33" class="footnote-back-ref">↩</a></li>
<li id="fn:34">Lee, Chung-Yee (1991-01-07). "Parallel machines scheduling with nonsimultaneous machine available time". Discrete Applied Mathematics. 30 (1): 53–61. doi:10.1016/0166-218X(91)90013-M. ISSN 0166-218X. <a href="https://doi.org/10.1016%2F0166-218X%2891%2990013-M" target="_blank">https://doi.org/10.1016%2F0166-218X%2891%2990013-M</a> <a href="#fnref:34" class="footnote-back-ref">↩</a></li>
<li id="fn:35">Lin, Guo-Hui; Yao, En-Yu; He, Yong (1998-03-01). "Parallel machine scheduling to maximize the minimum load with nonsimultaneous machine available times". Operations Research Letters. 22 (2): 75–81. doi:10.1016/S0167-6377(97)00053-9. ISSN 0167-6377. <a href="https://www.sciencedirect.com/science/article/pii/S0167637797000539" target="_blank">https://www.sciencedirect.com/science/article/pii/S0167637797000539</a> <a href="#fnref:35" class="footnote-back-ref">↩</a></li>
<li id="fn:36">Shen, Lixin; Wang, Dan; Wang, Xiao-Yuan (2013-04-01). "Parallel-machine scheduling with non-simultaneous machine available time". Applied Mathematical Modelling. 37 (7): 5227–5232. doi:10.1016/j.apm.2012.09.053. ISSN 0307-904X. <a href="https://www.sciencedirect.com/science/article/pii/S0307904X12005847" target="_blank">https://www.sciencedirect.com/science/article/pii/S0307904X12005847</a> <a href="#fnref:36" class="footnote-back-ref">↩</a></li>
<li id="fn:37">Chen, Bo; Vestjens, Arjen P. A. (1 November 1997). "Scheduling on identical machines: How good is LPT in an on-line setting?" (PDF). Operations Research Letters. 21 (4): 165–169. doi:10.1016/S0167-6377(97)00040-0. <a href="https://pure.tue.nl/ws/files/1556464/459560.pdf" target="_blank">https://pure.tue.nl/ws/files/1556464/459560.pdf</a> <a href="#fnref:37" class="footnote-back-ref">↩</a></li>
</ol>

Longest-processing-time-first scheduling open-in-new

Longest-processing-time-first scheduling