Uniform-machines scheduling: Difference between revisions

Revision as of 07:55, 5 September 2023

Revision as of 17:42, 30 January 2024

Line 1:

'''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''₁, ''J''₂, ..., ''J_n'' 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_i,j''. In the general case, the times ''p_i,j'' 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_i'', and the run-time of job ''j'' on machine ''i'' is ''p_i,j'' = ''p_j'' / ''s_i''.

In the standard [[Optimal job scheduling|three-field notation for optimal job scheduling problems]], the uniform-machine variant is denoted by '''Q''' in the first field. For example, the problem denoted by " '''Q||'''<math>C_\max</math>" is a uniform machine scheduling problem with no constraints, where the goal is to minimize the maximum completion time. 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.

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); it is denoted by '''Q||'''<math>\sum C_i</math>. 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 w_i C_i</math>.

== Algorithms ==

=== Minimizing the average completion time ===

Line 47:

== Extensions ==

'''Dependent jobs''': In some cases, the jobs may be dependent. For example, take the case of reading user credentials from console, then use it to authenticate, then if authentication is successful display some data on the console. Clearly one task is dependent upon another. This is a clear case of where some kind of [[Orderorder theory|ordering]] exists between the tasks. In fact it is clear that it can be modelled with [[partial ordering]]. Then, by definition, the set of tasks constitute a [[Latticelattice (order)|lattice structure]]. This adds further complication to the multiprocessor scheduling problem.

'''Static versus Dynamic''': Machine scheduling algorithms are static or dynamic. A scheduling algorithm is '''static''' if the scheduling decisions as to what computational tasks will be allocated to what processors are made before running the program. An algorithm is '''dynamic''' if it is taken at run time. For static scheduling algorithms, a typical approach is to rank the tasks according to their precedence relationships and use a list scheduling technique to schedule them onto the processors.<ref>{{Cite journal|last1=Kwok|first1=Yu-Kwong|last2=Ahmad|first2=Ishfaq|date=1999-12-01|title=Static scheduling algorithms for allocating directed task graphs to multiprocessors|journal=ACM Computing Surveys|volume=31|issue=4|pages=406–471|doi=10.1145/344588.344618|issn=0360-0300|citeseerx=10.1.1.322.2295|s2cid=207614150 }}</ref>

Line 54:

== External links ==

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

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

==References==