Content deleted Content added
Erel Segal (talk | contribs) ←Created page with ''''Unrelated-machines scheduling''' is an optimization problem in computer science and operations research. It is a variant of ...' |
Lazy Maniik (talk | contribs) m Added {{Orphan}} tag |
||
Line 1:
{{Orphan|date=June 2021}}
'''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''<sub>1</sub>, ''J''<sub>2</sub>, ..., ''J<sub>n</sub>'' 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<sub>i,j</sub>''. The term ''unrelated'' emphasizes that there is no relation between values of ''p<sub>i,j</sub>'' for different ''i'' and ''j''. This is in contrast to two special cases of this problem: [[uniform-machines scheduling]] - in which ''p<sub>i,j</sub>'' = ''p<sub>i</sub>'' / ''s<sub>j</sub>'' (where ''s<sub>j</sub>'' is the speed of machine ''j''), and [[identical-machines scheduling]] - in which ''p<sub>i,j</sub>'' = ''p<sub>i</sub>'' (the same run-time on all machines).
| |||