Content deleted Content added
m iff means "if and only if" so not a typo |
Adding short description: "Optimization problem in computer science and operations research" |
||
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''<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).
| |||