Content deleted Content added
Fix link to identical-machine scheduling |
Added short description Tags: Mobile edit Mobile app edit Android app edit |
||
Line 1:
{{Short description|Optimization prpblem}}
'''Uniform machine scheduling''' (also called '''uniformly-related machine scheduling''' or '''related machine scheduling''') is an [[optimization problem]] in [[computer science]] and [[Operations Research|operations research]]. It is a variant of [[optimal job scheduling]]. We are given ''n'' jobs ''J''<sub>1</sub>, ''J''<sub>2</sub>, ..., ''J<sub>n</sub>'' of varying processing times, which need to be scheduled on ''m'' different machines. The goal is to minimize the [[makespan]] - the total time required to execute the schedule. The time that machine ''i'' needs in order to process job j is denoted by ''p<sub>i,j</sub>''. In the general case, the times ''p<sub>i,j</sub>'' are unrelated, and any matrix of positive processing times is possible. In the specific variant called ''uniform machine scheduling'', some machines are ''uniformly'' faster than others. This means that, for each machine ''i'', there is a speed factor ''s<sub>i</sub>'', and the run-time of job ''j'' on machine ''i'' is ''p<sub>i,j</sub>'' = ''p<sub>j</sub>'' / ''s<sub>i</sub>''.
| |||