Unrelated-machines scheduling

<h2 id="algorithms">Algorithms</h2>
<h3>Minimizing the maximum completion time (makespan)</h3>
Minimizing the maximum completion time is NP-hard even for identical machines, by reduction from the <a href="/facts/Partition_problem/LcSBAcmu">partition problem</a>.
Horowitz and Sahni<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a> presented:

<ul><li>Exact <a href="/facts/Dynamic_programming/CLcabtmk">dynamic programming</a> algorithms for minimizing the maximum completion time on both uniform and unrelated machines. These algorithms run in exponential time (recall that these problems are all NP-hard).</li>
<li><a href="/facts/Polynomial-time_approximation_scheme/52Chjx9y">Polynomial-time approximation schemes</a>, which for any ε>0, attain at most (1+ε)OPT. For minimizing the maximum completion time on two uniform machines, their algorithm runs in time 
 
 
 
 O
 (
 
 10
 
 2
 l
 
 
 n
 )
 
 
 {\displaystyle O(10^{2l}n)}
 
, where 
 
 
 
 l
 
 
 {\displaystyle l}
 
 is the smallest integer for which 
 
 
 
 ϵ
 ≥
 2
 ⋅
 
 10
 
 −
 l
 
 
 
 
 {\displaystyle \epsilon \geq 2\cdot 10^{-l}}
 
. Therefore, the run-time is in 
 
 
 
 O
 (
 n
 
 /
 
 
 ϵ
 
 2
 
 
 )
 
 
 {\displaystyle O(n/\epsilon ^{2})}
 
, so it is an <a href="/facts/FPTAS/52Chjx9y">FPTAS</a>. For minimizing the maximum completion time on two unrelated machines, the run-time is 
 
 
 
 O
 (
 
 10
 
 l
 
 
 
 n
 
 2
 
 
 )
 
 
 {\displaystyle O(10^{l}n^{2})}
 
 = 
 
 
 
 O
 (
 
 n
 
 2
 
 
 
 /
 
 ϵ
 )
 
 
 {\displaystyle O(n^{2}/\epsilon )}
 
. They claim that their algorithms can be easily extended for any number of uniform machines, but do not analyze the run-time in this case.</li></ul>
Lenstra, Shmoys and Tardos<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> presented a polytime 2-factor approximation algorithm, and proved that no polytime algorithm with approximation factor smaller than 3/2 is possible unless P=NP. Closing the gap between the 2 and the 3/2 is a long-standing open problem.
Verschae and Wiese<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> presented a different 2-factor approximation algorithm.
Glass, Potts and Shade<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> compare various <a href="/facts/Local_search_(optimization)/G1D2aHBz">local search</a> techniques for minimizing the makespan on unrelated machines. Using computerized simulations, they find that <a href="/facts/Tabu_search/olw8qTSl">tabu search</a> and <a href="/facts/Simulated_annealing/JCmHqd3t">simulated annealing</a> perform much better than <a href="/facts/Genetic_algorithm/WP2AFWuW">genetic algorithms</a>.

<h3>Minimizing the average completion time</h3>
Bruno, Coffman and Sethi<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> present an algorithm, running in time 
 
 
 
 O
 (
 max
 (
 m
 
 n
 
 2
 
 
 ,
 
 n
 
 3
 
 
 )
 )
 
 
 {\displaystyle O(\max(mn^{2},n^{3}))}
 
, for minimizing the average job completion time on unrelated machines, R||
 
 
 
 ∑
 
 C
 
 j
 
 
 
 
 {\displaystyle \sum C_{j}}
 
 (the average over all jobs, of the time it takes to complete the jobs). 
Minimizing the weighted average completion time, R||
 
 
 
 ∑
 
 w
 
 j
 
 
 
 C
 
 j
 
 
 
 
 {\displaystyle \sum w_{j}C_{j}}
 
 (where wj is the weight of job j), 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:6" href="#fn:6">6</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:7" href="#fn:7">7</a>
Schulz and Skutella<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> present a (3/2+ε)-approximation algorithm using <a href="/facts/Randomized_rounding/8e7sqFxk">randomized rounding</a>. Their algorithm is a (2+ε)-approximation for the problem with job release times, R|
 
 
 
 
 r
 
 j
 
 
 
 
 {\displaystyle r_{j}}
 
|
 
 
 
 ∑
 
 w
 
 j
 
 
 
 C
 
 j
 
 
 
 
 {\displaystyle \sum w_{j}C_{j}}
 
.

<h3>Maximizing the profit</h3>
Bar-Noy, Bar-Yehuda, Freund, Naor and Schieber<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> consider a setting in which, for each job and machine, there is a profit for running this job on that machine. They present a 1/2 approximation for discrete input and (1-ε)/2 approximation for continuous input.

<h3>Maximizing the minimum completion time</h3>
Main article: <a href="/facts/Egalitarian_item_allocation/LWq3LqBU">Egalitarian item allocation</a>
Suppose that, instead of "jobs" we have valuable items, and instead of "machines" we have people. Person i values item j at pi,j. We would like to allocate the items to the people, such that the least-happy person is as happy as possible. This problem is equivalent to unrelated-machines scheduling in which the goal is to maximize the minimum completion time. It is better known by the name egalitarian or <a href="/facts/Max-min_item_allocation/LWq3LqBU">max-min item allocation</a>.

<h2 id="linear-programming-formulation">Linear programming formulation</h2>
A natural way to formulate the problem as a linear program is called the Lenstra–Shmoys–Tardos<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a> linear program (LST LP). For each machine i and job j, define a variable 
 
 
 
 
 z
 
 i
 ,
 j
 
 
 
 
 {\displaystyle z_{i,j}}
 
, which equals 1 if machine i processes job j, and 0 otherwise. Then, the LP constraints are:

<ul><li>
 
 
 
 
 ∑
 
 i
 =
 1
 
 
 m
 
 
 
 z
 
 i
 ,
 j
 
 
 =
 1
 
 
 {\displaystyle \sum _{i=1}^{m}z_{i,j}=1}
 
 for every job j in 1,...,n;</li>
<li>
 
 
 
 
 ∑
 
 j
 =
 1
 
 
 n
 
 
 
 z
 
 i
 ,
 j
 
 
 ⋅
 
 p
 
 i
 ,
 j
 
 
 ≤
 T
 
 
 {\displaystyle \sum _{j=1}^{n}z_{i,j}\cdot p_{i,j}\leq T}
 
 for every machine i in 1,...,m;</li>
<li>
 
 
 
 
 z
 
 i
 ,
 j
 
 
 ∈
 {
 0
 ,
 1
 }
 
 
 {\displaystyle z_{i,j}\in \{0,1\}}
 
 for every i, j.</li></ul>
Relaxing the integer constraints gives a linear program with size polynomial in the input. Solving the relaxed problem can be rounded to obtain a 2-approximation to the problem.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>
Another LP formulation is the <a href="/facts/Configuration_linear_program/GzKDyIQ8">configuration linear program</a>. For each machine i, there are finitely many subsets of jobs that can be processed by machine i in time at most T. Each such subset is called a configuration for machine i. Denote by Ci(T) the set of all configurations for machine i. For each machine i and configuration c in Ci(T), define a variable 
 
 
 
 
 x
 
 i
 ,
 c
 
 
 
 
 {\displaystyle x_{i,c}}
 
 which equals 1 if the actual configuration used in machine i is c, and 0 otherwise. Then, the LP constraints are:

<ul><li>
 
 
 
 
 ∑
 
 c
 ∈
 
 C
 
 i
 
 
 (
 T
 )
 
 
 
 x
 
 i
 ,
 c
 
 
 =
 1
 
 
 {\displaystyle \sum _{c\in C_{i}(T)}x_{i,c}=1}
 
 for every machine i in 1,...,m;</li>
<li>
 
 
 
 
 ∑
 
 i
 =
 1
 
 
 m
 
 
 
 ∑
 
 c
 ∋
 j
 ,
 c
 ∈
 
 C
 
 i
 
 
 (
 T
 )
 
 
 
 x
 
 i
 ,
 c
 
 
 =
 1
 
 
 {\displaystyle \sum _{i=1}^{m}\sum _{c\ni j,c\in C_{i}(T)}x_{i,c}=1}
 
 for every job j in 1,...,n;</li>
<li>
 
 
 
 
 x
 
 i
 ,
 j
 
 
 ∈
 {
 0
 ,
 1
 }
 
 
 {\displaystyle x_{i,j}\in \{0,1\}}
 
 for every i, j.</li></ul>
Note that the number of configurations is usually exponential in the size of the problem, so the size of the configuration LP is exponential. However, in some cases it is possible to bound the number of possible configurations, and therefore find an approximate solution in polynomial time.

<h2 id="special-cases">Special cases</h2>
There is a special case in which pi,j is either 1 or infinity. In other words, each job can be processed on a subset of allowed machines, and its run-time in each of these machines is 1. This variant is sometimes denoted by " P|pj=1,Mj|
 
 
 
 
 C
 
 max
 
 
 
 
 {\displaystyle C_{\max }}
 
". It can be solved in polynomial time. <a class="footnote-ref" id="fnref:12" href="#fn:12">12</a>

<h2 id="extensions">Extensions</h2>
Kim, Kim, Jang and Chen<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a> extend the problem by allowing each job to have a setup time, which depends on the job but not on the machine. They present a solution using <a href="/facts/Simulated_annealing/JCmHqd3t">simulated annealing</a>. Vallada and Ruiz<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a> present a solution using a <a href="/facts/Genetic_algorithm/WP2AFWuW">genetic algorithm</a>.
Nisan and Ronen in their 1999 paper on <a href="/facts/Algorithmic_mechanism_design/Lc9Q7Fre">algorithmic mechanism design</a>.<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a> extend the problem in a different way, by assuming that the jobs are owned by selfish agents (see <a href="/facts/Truthful_job_scheduling/MDRHA0yF">Truthful job scheduling</a>).

<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">Lenstra, Jan Karel; Shmoys, David B.; Tardos, Éva (1990-01-01). "Approximation algorithms for scheduling unrelated parallel machines". Mathematical Programming. 46 (1): 259–271. doi:10.1007/BF01585745. ISSN 1436-4646. S2CID 52867171. <a href="https://doi.org/10.1007/BF01585745" target="_blank">https://doi.org/10.1007/BF01585745</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Verschae, José; Wiese, Andreas (2013-11-10). "On the configuration-LP for scheduling on unrelated machines". Journal of Scheduling. 17 (4): 371–383. arXiv:1011.4957. doi:10.1007/s10951-013-0359-4. ISSN 1094-6136. S2CID 254694965. <a href="https://link-springer-com.mgs.ariel.ac.il/article/10.1007/s10951-013-0359-4" target="_blank">https://link-springer-com.mgs.ariel.ac.il/article/10.1007/s10951-013-0359-4</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Glass, C.A.; Potts, C.N.; Shade, P. (1994-07-01). "Unrelated parallel machine scheduling using local search". Mathematical and Computer Modelling. 20 (2): 41–52. doi:10.1016/0895-7177(94)90205-4. ISSN 0895-7177. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Bruno, J.; Coffman, E. G.; Sethi, R. (1974-07-01). "Scheduling independent tasks to reduce mean finishing time". Communications of the ACM. 17 (7): 382–387. doi:10.1145/361011.361064. ISSN 0001-0782. S2CID 2507557. <a href="https://doi.org/10.1145%2F361011.361064" target="_blank">https://doi.org/10.1145%2F361011.361064</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">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:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">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:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Schulz, Andreas S.; Skutella, Martin (2002-01-01). "Scheduling Unrelated Machines by Randomized Rounding". SIAM Journal on Discrete Mathematics. 15 (4): 450–469. doi:10.1137/S0895480199357078. ISSN 0895-4801. <a href="https://epubs.siam.org/doi/abs/10.1137/S0895480199357078" target="_blank">https://epubs.siam.org/doi/abs/10.1137/S0895480199357078</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Bar-Noy, Amotz; Bar-Yehuda, Reuven; Freund, Ari; (Seffi) Naor, Joseph; Schieber, Baruch (2001-09-01). "A unified approach to approximating resource allocation and scheduling". Journal of the ACM. 48 (5): 1069–1090. doi:10.1145/502102.502107. ISSN 0004-5411. S2CID 12329294. <a href="/wiki/Baruch_Schieber" target="_blank">/wiki/Baruch_Schieber</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Lenstra, Jan Karel; Shmoys, David B.; Tardos, Éva (1990-01-01). "Approximation algorithms for scheduling unrelated parallel machines". Mathematical Programming. 46 (1): 259–271. doi:10.1007/BF01585745. ISSN 1436-4646. S2CID 206799898. <a href="https://doi.org/10.1007/BF01585745" target="_blank">https://doi.org/10.1007/BF01585745</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Lenstra, Jan Karel; Shmoys, David B.; Tardos, Éva (1990-01-01). "Approximation algorithms for scheduling unrelated parallel machines". Mathematical Programming. 46 (1): 259–271. doi:10.1007/BF01585745. ISSN 1436-4646. S2CID 206799898. <a href="https://doi.org/10.1007/BF01585745" target="_blank">https://doi.org/10.1007/BF01585745</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Lin, Yixun; Li, Wenhua (2004-07-01). "Parallel machine scheduling of machine-dependent jobs with unit-length". European Journal of Operational Research. EURO Excellence in Practice Award 2001. 156 (1): 261–266. doi:10.1016/S0377-2217(02)00914-1. ISSN 0377-2217. <a href="https://www.sciencedirect.com/science/article/pii/S0377221702009141" target="_blank">https://www.sciencedirect.com/science/article/pii/S0377221702009141</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Kim, Dong-Won; Kim, Kyong-Hee; Jang, Wooseung; Frank Chen, F. (2002-06-01). "Unrelated parallel machine scheduling with setup times using simulated annealing". Robotics and Computer-Integrated Manufacturing. 18 (3–4): 223–231. doi:10.1016/S0736-5845(02)00013-3. ISSN 0736-5845. <a href="https://www.sciencedirect.com/science/article/abs/pii/S0736584502000133" target="_blank">https://www.sciencedirect.com/science/article/abs/pii/S0736584502000133</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Vallada, Eva; Ruiz, Rubén (2011-06-16). "A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times". European Journal of Operational Research. 211 (3): 612–622. doi:10.1016/j.ejor.2011.01.011. hdl:10251/35412. ISSN 0377-2217. <a href="https://www.sciencedirect.com/science/article/abs/pii/S0377221711000142" target="_blank">https://www.sciencedirect.com/science/article/abs/pii/S0377221711000142</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Nisan, Noam; Ronen, Amir (2001). "Algorithmic Mechanism Design". Games and Economic Behavior. 35 (1–2): 166–196. CiteSeerX 10.1.1.16.7473. doi:10.1006/game.1999.0790. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
</ol>

Unrelated-machines scheduling open-in-new

Unrelated-machines scheduling