Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) No edit summary |
||
Line 5:
A special case of uniform machine scheduling is '''identical machine scheduling''', in which all machines have the same speed. This variant is denoted by '''P''' in the first field. For example, " '''P||'''<math>C_\max</math>" is an identical machine scheduling problem with no constraints, where the goal is to minimize the maximum completion time. This problem is also a special case of the [[multiway number partitioning]] problem. In both problems, the goal is to partition numbers into subsets with nearly-equal sum; identical machine scheduling is a special case in which the objective is to minimize the largest sum. Many algorithms for multiway number partitioning, both exact and approximate, can be used to attain this objective.
In some variants of the problem, instead of minimizing the ''maximum'' completion time, it is desired to minimize the ''average'' completion time (averaged over all ''n'' jobs). More generally, when some jobs are more important than others, it may be desired to minimize a ''[[Weighted arithmetic mean|weighted average]]'' of the completion time, where each job has a different weight. This is denoted by " '''Q||'''<math>\sum_i w_i C_i</math>"
==Algorithms==
| |||