Identical-machines scheduling

<h2 id="algorithms">Algorithms</h2>
<h3>Minimizing average and weighted-average completion time</h3>
Minimizing the average completion time (P||
 
 
 
 ∑
 
 C
 
 i
 
 
 
 
 {\displaystyle \sum C_{i}}
 
) can be done in polynomial time. The SPT algorithm (Shortest Processing Time First), sorts the jobs by their length, shortest first, and then assigns them to the processor with the earliest end time so far. It runs in time O(n log n), and minimizes the average completion time on identical machines,<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a> P||
 
 
 
 ∑
 
 C
 
 i
 
 
 
 
 {\displaystyle \sum C_{i}}
 
.

<ul><li>There can be many SPT schedules; finding the SPT schedule with the smallest finish time (also called OMFT – optimal mean finish time) is NP-hard.</li></ul>
Minimizing the weighted average completion time is NP-hard even on identical machines, by reduction from the <a href="/facts/Knapsack_problem/HMIdVJH5">knapsack problem</a>.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> It is NP-hard even if the number of machines is fixed and at least 2, by reduction from the <a href="/facts/Partition_problem/LcSBAcmu">partition problem</a>.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>
Sahni<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> presents an exponential-time algorithm and a polynomial-time approximation scheme for solving both these NP-hard problems on identical machines:

<ul><li>Optimal average-completion-time;</li>
<li>Weighted-average-completion-time.</li></ul>
<h3>Minimizing the maximum completion time (makespan)</h3>
Minimizing the maximum completion time (P||
 
 
 
 
 C
 
 max
 
 
 
 
 {\displaystyle C_{\max }}
 
) is NP-hard even for identical machines, by reduction from the <a href="/facts/Partition_problem/LcSBAcmu">partition problem</a>. Many exact and approximation algorithms are known.
Graham proved that:

<ul><li>Any <a href="/facts/List_scheduling/qUscTqbx">list scheduling</a> algorithm (an algorithm that processes the jobs in an arbitrary fixed order, and schedules each job to the first available machine) is a 
 
 
 
 2
 −
 1
 
 /
 
 m
 
 
 {\displaystyle 2-1/m}
 
 approximation for identical machines.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> The bound is tight for any m. This algorithm runs in time O(n).</li>
<li>The specific list-scheduling algorithm called <a href="/facts/Longest-processing-time-first_scheduling/EcPS5uh3">Longest Processing Time First</a> (LPT), which sorts the jobs by descending length, is a 
 
 
 
 4
 
 /
 
 3
 −
 1
 
 /
 
 3
 m
 
 
 {\displaystyle 4/3-1/3m}
 
 approximation for identical machines.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>: sec.5  It is also called <a href="/facts/Greedy_number_partitioning/EuDV9gm8">greedy number partitioning</a>.</li></ul>
Coffman, Garey and Johnson presented a different algorithm called <a href="/facts/Multifit_algorithm/41TkvqaW">multifit algorithm</a>, using techniques from <a href="/facts/Bin_packing_problem/T67Qe934">bin packing</a>, which has an approximation factor of 13/11≈1.182.
Huang and Lu<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> presented a simple polynomial-time algorithm that attains an 11/9≈1.222 approximation in time O(m log m + n), through the more general problem of <a href="/facts/Maximin-share/pdUnoMuY">maximin-share</a> allocation of chores.
Sahni<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> presented a PTAS that attains (1+ε)OPT in time 
 
 
 
 O
 (
 n
 ⋅
 (
 
 n
 
 2
 
 
 
 /
 
 ϵ
 
 )
 
 m
 −
 1
 
 
 )
 
 
 {\displaystyle O(n\cdot (n^{2}/\epsilon )^{m-1})}
 
. It is an FPTAS if m is fixed. For m=2, the run-time improves to 
 
 
 
 O
 (
 
 n
 
 2
 
 
 
 /
 
 ϵ
 )
 
 
 {\displaystyle O(n^{2}/\epsilon )}
 
. The algorithm uses a technique called interval partitioning.
Hochbaum and Shmoys<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> presented several approximation algorithms for any number of identical machines (even when the number of machines is not fixed):

<ul><li>For any r >0, an algorithm with approximation ratio at most (6/5+2−r ) in time 
 
 
 
 O
 (
 n
 (
 r
 +
 log
 ⁡
 
 n
 
 )
 )
 
 
 {\displaystyle O(n(r+\log {n}))}
 
.</li>
<li>For any r >0, an algorithm with approximation ratio at most (7/6+2−r ) in time 
 
 
 
 O
 (
 n
 (
 r
 
 m
 
 4
 
 
 +
 log
 ⁡
 
 n
 
 )
 )
 
 
 {\displaystyle O(n(rm^{4}+\log {n}))}
 
.</li>
<li>For any ε>0, an algorithm with approximation ratio at most (1+ε) in time 
 
 
 
 O
 (
 (
 n
 
 /
 
 ε
 
 )
 
 (
 1
 
 /
 
 
 ε
 
 2
 
 
 )
 
 
 )
 
 
 {\displaystyle O((n/\varepsilon )^{(1/\varepsilon ^{2})})}
 
 . This is a <a href="/facts/Polynomial-time_approximation_scheme/52Chjx9y">PTAS</a>. Note that, when the number of machines is a part of the input, the problem is <a href="/facts/Strong_NP-completeness/rqFp8pxx">strongly NP-hard</a>, so no FPTAS is possible.</li></ul>
Leung<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a> improved the run-time of this algorithm to 
 
 
 
 O
 
 (
 
 (
 n
 
 /
 
 ε
 
 )
 
 (
 1
 
 /
 
 ε
 )
 log
 ⁡
 
 (
 1
 
 /
 
 ε
 )
 
 
 
 
 )
 
 
 
 {\displaystyle O\left((n/\varepsilon )^{(1/\varepsilon )\log {(1/\varepsilon )}}\right)}
 
.

<h3>Maximizing the minimum completion time</h3>
Maximizing the minimum completion time (P||
 
 
 
 
 C
 
 min
 
 
 
 
 {\displaystyle C_{\min }}
 
) is applicable when the "jobs" are actually spare parts that are required to keep the machines running, and they have different life-times. The goal is to keep machines running for as long as possible.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a> The <a href="/facts/LPT_algorithm/EcPS5uh3">LPT algorithm</a> attains at least 
 
 
 
 
 
 
 3
 m
 −
 1
 
 
 4
 m
 −
 2
 
 
 
 
 
 {\displaystyle {\frac {3m-1}{4m-2}}}
 
 of the optimum. 
Woeginger<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a> presented a PTAS that attains an approximation factor of 
 
 
 
 1
 −
 
 ε
 
 
 
 {\displaystyle 1-{\varepsilon }}
 
 in time 
 
 
 
 O
 (
 
 c
 
 ε
 
 
 n
 log
 ⁡
 
 k
 
 )
 
 
 {\displaystyle O(c_{\varepsilon }n\log {k})}
 
, where 
 
 
 
 
 c
 
 ε
 
 
 
 
 {\displaystyle c_{\varepsilon }}
 
 a huge constant that is exponential in the required approximation factor ε. The algorithm uses Lenstra's algorithm for <a href="/facts/Integer_linear_programming/MDaaadoA">integer linear programming</a>.

<h3>General objective functions</h3>
Alon, Azar, Woeginger and Yadid<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a> consider a more general objective function. Given a positive real function f, which depends only on the completion times Ci, they consider the objectives of minimizing 
 
 
 
 
 ∑
 
 i
 =
 1
 
 
 m
 
 
 f
 (
 
 C
 
 i
 
 
 )
 
 
 {\displaystyle \sum _{i=1}^{m}f(C_{i})}
 
, minimizing 
 
 
 
 
 max
 
 i
 =
 1
 
 
 m
 
 
 f
 (
 
 C
 
 i
 
 
 )
 
 
 {\displaystyle \max _{i=1}^{m}f(C_{i})}
 
, maximizing 
 
 
 
 
 ∑
 
 i
 =
 1
 
 
 m
 
 
 f
 (
 
 C
 
 i
 
 
 )
 
 
 {\displaystyle \sum _{i=1}^{m}f(C_{i})}
 
, and maximizing 
 
 
 
 
 min
 
 i
 =
 1
 
 
 m
 
 
 f
 (
 
 C
 
 i
 
 
 )
 
 
 {\displaystyle \min _{i=1}^{m}f(C_{i})}
 
. They prove that, if f is non-negative, <a href="/facts/Convex_function/IbzG5SLF">convex</a>, and satisfies a strong continuity assumption that they call "F*", then both minimization problems have a PTAS. Similarly, if f is non-negative, <a href="/facts/Convex_function/IbzG5SLF">concave</a>, and satisfies F*, then both maximization problems have a PTAS. In both cases, the run-time of the PTAS is O(n), but with constants that are exponential in 1/ε.

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Fernandez%2527s_method/bWJ5QmPc">Fernandez's method</a></li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="http://www2.informatik.uni-osnabrueck.de/knust/class/dateien/classes/pqr_nop/pqr_nop/">Summary of parallel machine problems without preemtion</a></li></ul>

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

<ol>
<li id="fn:1">Horowitz, Ellis; Sahni, Sartaj (1976-04-01). "Exact and Approximate Algorithms for Scheduling Nonidentical Processors". Journal of the ACM. 23 (2): 317–327. doi:10.1145/321941.321951. ISSN 0004-5411. S2CID 18693114. <a href="https://doi.org/10.1145%2F321941.321951" target="_blank">https://doi.org/10.1145%2F321941.321951</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Horowitz, Ellis; Sahni, Sartaj (1976-04-01). "Exact and Approximate Algorithms for Scheduling Nonidentical Processors". Journal of the ACM. 23 (2): 317–327. doi:10.1145/321941.321951. ISSN 0004-5411. S2CID 18693114. <a href="https://doi.org/10.1145%2F321941.321951" target="_blank">https://doi.org/10.1145%2F321941.321951</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Sahni, Sartaj K. (1976-01-01). "Algorithms for Scheduling Independent Tasks". Journal of the ACM. 23 (1): 116–127. doi:10.1145/321921.321934. ISSN 0004-5411. S2CID 10956951. <a href="https://doi.org/10.1145%2F321921.321934" target="_blank">https://doi.org/10.1145%2F321921.321934</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Sahni, Sartaj K. (1976-01-01). "Algorithms for Scheduling Independent Tasks". Journal of the ACM. 23 (1): 116–127. doi:10.1145/321921.321934. ISSN 0004-5411. S2CID 10956951. <a href="https://doi.org/10.1145%2F321921.321934" target="_blank">https://doi.org/10.1145%2F321921.321934</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Graham, Ron L. (1966). "Bounds for Certain Multiprocessing Anomalies". Bell System Technical Journal. 45 (9): 1563–1581. doi:10.1002/j.1538-7305.1966.tb01709.x. ISSN 1538-7305. <a href="/wiki/Ronald_Graham" target="_blank">/wiki/Ronald_Graham</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Graham, Ron L. (1969-03-01). "Bounds on Multiprocessing Timing Anomalies". SIAM Journal on Applied Mathematics. 17 (2): 416–429. doi:10.1137/0117039. ISSN 0036-1399. <a href="/wiki/Ronald_Graham" target="_blank">/wiki/Ronald_Graham</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Huang, Xin; Lu, Pinyan (2021-07-18). "An Algorithmic Framework for Approximating Maximin Share Allocation of Chores". Proceedings of the 22nd ACM Conference on Economics and Computation. EC '21. Budapest, Hungary: Association for Computing Machinery. pp. 630–631. arXiv:1907.04505. doi:10.1145/3465456.3467555. ISBN 978-1-4503-8554-1. S2CID 195874333. <a href="978-1-4503-8554-1" target="_blank">978-1-4503-8554-1</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Sahni, Sartaj K. (1976-01-01). "Algorithms for Scheduling Independent Tasks". Journal of the ACM. 23 (1): 116–127. doi:10.1145/321921.321934. ISSN 0004-5411. S2CID 10956951. <a href="https://doi.org/10.1145%2F321921.321934" target="_blank">https://doi.org/10.1145%2F321921.321934</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Hochbaum, Dorit S.; Shmoys, David B. (1987-01-01). "Using dual approximation algorithms for scheduling problems theoretical and practical results". Journal of the ACM. 34 (1): 144–162. doi:10.1145/7531.7535. ISSN 0004-5411. S2CID 9739129. <a href="https://doi.org/10.1145%2F7531.7535" target="_blank">https://doi.org/10.1145%2F7531.7535</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Leung, Joseph Y-T. (1989-05-08). "Bin packing with restricted piece sizes". Information Processing Letters. 31 (3): 145–149. doi:10.1016/0020-0190(89)90223-8. ISSN 0020-0190. <a href="https://www.sciencedirect.com/science/article/abs/pii/0020019089902238" target="_blank">https://www.sciencedirect.com/science/article/abs/pii/0020019089902238</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Friesen, D. K.; Deuermeyer, B. L. (1981-02-01). "Analysis of Greedy Solutions for a Replacement Part Sequencing Problem". Mathematics of Operations Research. 6 (1): 74–87. doi:10.1287/moor.6.1.74. ISSN 0364-765X. <a href="https://pubsonline.informs.org/doi/abs/10.1287/moor.6.1.74" target="_blank">https://pubsonline.informs.org/doi/abs/10.1287/moor.6.1.74</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Woeginger, Gerhard J. (1997-05-01). "A polynomial-time approximation scheme for maximizing the minimum machine completion time". Operations Research Letters. 20 (4): 149–154. doi:10.1016/S0167-6377(96)00055-7. ISSN 0167-6377. <a href="http://www.sciencedirect.com/science/article/pii/S0167637796000557" target="_blank">http://www.sciencedirect.com/science/article/pii/S0167637796000557</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">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:13" class="footnote-back-ref">↩</a></li>
</ol>

Identical-machines scheduling open-in-new

Identical-machines scheduling