Unrelated-machines scheduling: Difference between revisions

Revision as of 07:25, 15 May 2022

Latest revision as of 11:49, 24 June 2025

(17 intermediate revisions by 11 users not shown)

Line 1:

{{Short description|Optimization problem in computer science and operations research}}

'''Unrelated-machines scheduling''' is an [[optimization problem]] in [[computer science]] and [[Operations Research|operations research]]. It is a variant of [[optimal job scheduling]]. We need to schedule ''n'' jobs ''J''₁, ''J''₂, ..., ''J_n'' on ''m'' different machines, such that a certain objective function is optimized (usually, the [[makespan]] should be minimized). The time that machine ''i'' needs in order to process job j is denoted by ''p_i,j''. The term ''unrelated'' emphasizes that there is no relation between values of ''p_i,j'' for different ''i'' and ''j''. This is in contrast to two special cases of this problem: [[uniform-machines scheduling]] - in which ''p_i,j'' = ''p_i'' / ''s_j'' (where ''s_j'' is the speed of machine ''j''), and [[identical-machines scheduling]] - in which ''p_i,j'' = ''p_i'' (the same run-time on all machines).

Line 12 ⟶ 13:

Minimizing the ''maximum'' completion time is NP-hard even for ''identical'' machines, by reduction from the [[partition problem]].

Horowitz and Sahni'''<ref name=":0">{{Cite journal|lastlast1=Horowitz|firstfirst1=Ellis|last2=Sahni|first2=Sartaj|date=1976-04-01|title=Exact and Approximate Algorithms for Scheduling Nonidentical Processors|url=https://doi.org/10.1145/321941.321951|journal=Journal of the ACM|volume=23|issue=2|pages=317–327|doi=10.1145/321941.321951|s2cid=18693114 |issn=0004-5411|doi-access=free}}</ref>''' presented:

* Exact [[dynamic programming]] 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).

* [[Polynomial-time approximation scheme|Polynomial-time approximation schemes]], which for any ''ε''>0, attain at most (1+ε)OPT. For minimizing the ''maximum'' completion time on two ''uniform'' machines, their algorithm runs in time <math>O(10^{2l} n)</math>, where <math>l</math> is the smallest integer for which <math>\epsilon \geq 2\cdot 10^{-l}</math>. Therefore, the run-time is in <math>O( n / \epsilon^2)</math>, so it is an [[FPTAS]]. For minimizing the ''maximum'' completion time on two ''unrelated'' machines, the run-time is <math>O(10^{l} n^2)</math> = <math>O( n^2 / \epsilon)</math>. 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.

Lenstra, Shmoys and Tardos<ref>{{Cite journal|lastlast1=Lenstra|firstfirst1=Jan Karel|last2=Shmoys|first2=David B.|last3=Tardos|first3=Éva|date=1990-01-01|title=Approximation algorithms for scheduling unrelated parallel machines|url=https://doi.org/10.1007/BF01585745|journal=Mathematical Programming|language=en|volume=46|issue=1|pages=259–271|doi=10.1007/BF01585745|s2cid=52867171 |issn=1436-4646|url-access=subscription}}</ref> 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.

VersacheVerschae and Wiese<ref>{{Cite journal|lastlast1=Verschae|firstfirst1=José|last2=Wiese|first2=Andreas|date=2013-11-10|title=On the configuration-LP for scheduling on unrelated machines|url=https://link-springer-com.mgs.ariel.ac.il/article/10.1007/s10951-013-0359-4|journal=Journal of Scheduling|volume=17|issue=4|pages=371–383|doi=10.1007/s10951-013-0359-4|s2cid=254694965 |issn=1094-6136|arxiv=1011.4957}}</ref> presented a different 2-factor approximation algorithm.

Glass, Potts and Shade<ref>{{Cite journal|date=1994-07-01|title=Unrelated parallel machine scheduling using local search|url=https://www.sciencedirect.com/science/article/pii/0895717794902054|journal=Mathematical and Computer Modelling|language=en|volume=20|issue=2|pages=41–52|doi=10.1016/0895-7177(94)90205-4|issn=0895-7177|doi-access=free|last1=Glass |first1=C.A. |last2=Potts |first2=C.N. |last3=Shade |first3=P. }}</ref> compare various [[Local search (optimization)|local search]] techniques for minimizing the makespan on unrelated machines. Using computerized simulations, they find that [[tabu search]] and [[simulated annealing]] perform much better than [[Genetic algorithm|genetic algorithms]].

=== Minimizing the average completion time ===

Bruno, Coffman and Sethi<ref>{{Cite journal|lastlast1=Bruno|firstfirst1=J.|last2=Coffman|first2=E. G.|last3=Sethi|first3=R.|date=1974-07-01|title=Scheduling independent tasks to reduce mean finishing time|url=https://doi.org/10.1145/361011.361064|journal=Communications of the ACM|volume=17|issue=7|pages=382–387|doi=10.1145/361011.361064|s2cid=2507557 |issn=0001-0782|doi-access=free}}</ref> present an algorithm, running in time <math>O(\max(m n^2,n^3))</math>, for minimizing the average job completion time on ''unrelated'' machines, '''R||'''<math>\sum_{\text{job}\insum \text{Jobs}} \text{FinishTime}(\text{job})C_j</math>, on(the average over all ''unrelatedjobs'', machinesof the time it takes to complete the jobs).

Minimizing the ''weighted average'' completion time, '''R||'''<math>\sum w_j C_j</math> (where ''w_j'' is the weight of job ''j''), is NP-hard even on ''identical'' machines, by reduction from the [[knapsack problem]].'''<ref name=":0" />''' It is NP-hard even if the number of machines is fixed and at least 2, by reduction from the [[partition problem]].<ref name=":3">{{Cite journal|last=Sahni|first=Sartaj K.|date=1976-01-01|title=Algorithms for Scheduling Independent Tasks|url=https://doi.org/10.1145/321921.321934|journal=Journal of the ACM|volume=23|issue=1|pages=116–127|doi=10.1145/321921.321934|s2cid=10956951 |issn=0004-5411|doi-access=free}}</ref>

Schulz and Skutella<ref>{{Cite journal |lastlast1=Schulz |firstfirst1=Andreas S. |last2=Skutella |first2=Martin |date=2002-01-01 |title=Scheduling Unrelated Machines by Randomized Rounding |url=https://epubs.siam.org/doi/abs/10.1137/S0895480199357078 |journal=SIAM Journal on Discrete Mathematics |volume=15 |issue=4 |pages=450–469 |doi=10.1137/S0895480199357078 |issn=0895-4801|url-access=subscription }}</ref> present a (3/2+ε)-approximation algorithm using [[randomized rounding]]. Their algorithm is a (2+ε)-approximation for the problem with job release times, '''R|<math>r_j</math>|'''<math>\sum w_j C_j</math>.

=== Maximizing the profit ===

Bar-Noy, Bar-Yehuda, Freund, Naor and Schieber<ref>{{Cite journal|lastlast1=Bar-Noy|firstfirst1=Amotz|last2=Bar-Yehuda|first2=Reuven|last3=Freund|first3=Ari|last4=(Seffi) Naor|first4=Joseph|last5=Schieber|first5=Baruch|author5-link=Baruch Schieber|date=2001-09-01|title=A unified approach to approximating resource allocation and scheduling|url=https://doi.org/10.1145/502102.502107|journal=Journal of the ACM|volume=48|issue=5|pages=1069–1090|doi=10.1145/502102.502107|s2cid=12329294 |issn=0004-5411|url-access=subscription}}</ref> 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.

=== Maximizing the minimum completion time ===

{{Main|Egalitarian item allocation}}

Suppose that, instead of "jobs" we have valuable items, and instead of "machines" we have people. Person ''i'' values item j at ''p_i,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 ''[[Max-min item allocation|''max-min item allocation]]'']].

== Linear programming formulation ==

A natural way to formulate the problem as a linear program is called the ''Lenstra–Shmoys–Tardos<ref name=":2">{{Cite journal|last1=Lenstra|first1=Jan Karel|last2=Shmoys|first2=David B.|last3=Tardos|first3=Éva|date=1990-01-01|title=Approximation algorithms for scheduling unrelated parallel machines|url=https://doi.org/10.1007/BF01585745|journal=Mathematical Programming|language=en|volume=46|issue=1|pages=259–271|doi=10.1007/BF01585745|issn=1436-4646|s2cid=206799898|url-access=subscription}}</ref> linear program (LST LP)''. For each machine ''i'' and job ''j_,'' define a variable <math>z_{i,j}</math>, which equals 1 iffif machine ''i'' processes job ''j'', and 0 otherwise. Then, the LP constraints are:

* <math>\sum_{i=1}^m z_{i,j} = 1</math> for every job ''j'' in 1,...,''n;''

* <math>\sum_{ij=1}^mn z_{i,j}\cdot p_{i,j} \leq T</math> for every machine ''i'' in 1,...,''m;''

* <math>z_{i,j} \in \{0,1\}</math> for every ''i'', ''j''.

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.''<ref name=":2" />''

Another LP formulation is the [[configuration linear program]]. 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 ''C_i''(''T'') the set of all configurations for machine ''i''. For each machine ''i'' and configuration ''c'' in ''C_i''(''T''), define a variable <math>x_{i,c}</math> which equals 1 iffif the actual configuration used in machine ''i'' is ''c'', and 0 otherwise. Then, the LP constraints are:

* <math>\sum_{c\in C_i(T)}x_{i,c} = 1</math> for every machine ''i'' in 1,...,''m;''

Line 54 ⟶ 55:

== Special cases ==

There is a special case in which ''p_i,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|p_j=1,M_j|'''<math>C_\max</math>". It can be solved in polynomial time. <ref>{{Cite journal|lastlast1=Lin|firstfirst1=Yixun|last2=Li|first2=Wenhua|date=2004-07-01|title=Parallel machine scheduling of machine-dependent jobs with unit-length|url=https://www.sciencedirect.com/science/article/pii/S0377221702009141|journal=European Journal of Operational Research|series=EURO Excellence in Practice Award 2001|language=en|volume=156|issue=1|pages=261–266|doi=10.1016/S0377-2217(02)00914-1|issn=0377-2217|url-access=subscription}}</ref>

== Extensions ==

Kim, Kim, Jang and Chen<ref>{{Cite journal|date=2002-06-01|title=Unrelated parallel machine scheduling with setup times using simulated annealing|url=https://www.sciencedirect.com/science/article/abs/pii/S0736584502000133|journal=Robotics and Computer-Integrated Manufacturing|language=en|volume=18|issue=3-43–4|pages=223–231|doi=10.1016/S0736-5845(02)00013-3|issn=0736-5845|last1=Kim |first1=Dong-Won |last2=Kim |first2=Kyong-Hee |last3=Jang |first3=Wooseung |last4=Frank Chen |first4=F. |url-access=subscription}}</ref> 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 [[simulated annealing]]. Vallada and Ruiz<ref>{{Cite journal|date=2011-06-16|title=A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times|url=https://www.sciencedirect.com/science/article/abs/pii/S0377221711000142|journal=European Journal of Operational Research|language=en|volume=211|issue=3|pages=612–622|doi=10.1016/j.ejor.2011.01.011|issn=0377-2217|hdl-access=free|hdl=10251/35412|last1=Vallada |first1=Eva |last2=Ruiz |first2=Rubén }}</ref> present a solution using a [[genetic algorithm]].

Caragiannis<ref>{{CiteNisan journal|date=2011-06-16|title=Aand geneticRonen algorithmin fortheir the1999 unrelatedpaper parallelon machine[[algorithmic schedulingmechanism problemdesign]].<ref withname=NisanRonen01>{{Cite sequence dependent setup timesjournal|urldoi=https:10.1006//wwwgame.sciencedirect1999.com/science/article/abs/pii/S03772217110001420790|title=Algorithmic Mechanism Design|journal=EuropeanGames Journaland ofEconomic Operational Research|language=enBehavior|volume=21135|issue=31–2|pages=612–622166–196|doiyear=10.1016/j.ejor.2011.01.0112001|issnlast1=0377-2217Nisan|hdlfirst1=10251/35412Noam|last2=Ronen|hdl-accessfirst2=freeAmir|citeseerx=10.1.1.16.7473}}</ref> extendsextend the problem in a different way, by assuming that the jobs are owned by selfish agents (see [[Truthful job scheduling]]).

== External links ==