Uniform-machines scheduling: Difference between revisions

Revision as of 19:18, 19 June 2021

Revision as of 19:39, 19 June 2021

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_isum w_i C_i</math>"

==Algorithms==

Line 44:

'''Multi-stage jobs''': In various settings, each job might have several operations that must be executed in parallel. Some such settings are handled by [[Open-shop scheduling|open shop scheduling]], [[flow shop scheduling]] and [[job shop scheduling]].

== External links ==

* [http://www2.informatik.uni-osnabrueck.de/knust/class/dateien/classes/pqr_nop/pqr_nop/ Summary of parallel machine problems without preemtion]

==References==