Uniform-machines scheduling explained

Uniform machine scheduling (also called uniformly-related machine scheduling or related machine scheduling) is an optimization problem in computer science and 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 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||

C _{max} " 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-machines 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||

\sum C _{i} . More generally, when some jobs are more important than others, it may be desired to minimize a weighted average of the completion time, where each job has a different weight. This is denoted by Q||\sum w _{i} C _{i} .

Algorithms

Minimizing the average completion time

Minimizing the average completion time can be done in polynomial time:

• The SPT algorithm (Shortest Processing Time First), sorts the jobs by their length, shortest first, and then assigns them to the processor with the earliest end time so far. It runs in time O(n log n), and minimizes the average completion time on identical machines, P||

\sum C _{i} .

• Horowitz and Sahni present an exact algorithm, with run time O(n log m n), for minimizing the average completion time on uniform machines, Q||

\sum C _{i} .

• Bruno, Coffman and Sethi^[1] present an algorithm, running in time

O( max (m n ^{2,n} ^{3))} , for minimizing the average completion time on unrelated machines, R||\sum C _{i} .

Minimizing the weighted-average completion time

Minimizing the weighted average completion time is NP-hard even on identical machines, by reduction from the knapsack problem. It is NP-hard even if the number of machines is fixed and at least 2, by reduction from the partition problem.^[2]

Sahni presents an exponential-time algorithm and a polynomial-time approximation algorithm for identical machines.

Horowitz and Sahni presented:

• Exact dynamic programming algorithms for minimizing the weighted-average completion time on uniform machines. These algorithms run in exponential time.
• Polynomial-time approximation schemes, which for any ε>0, attain at most (1+ε)OPT. For minimizing the weighted average completion time on two uniform machines, the run-time is

O( 10 ^{l} n ^{2)} = O( n ^{2} / \epsilon) , so it is an FPTAS. They claim that their algorithms can be easily extended for any number of uniform machines, but do not analyze the run-time in this case. They do not present an algorithm for weighted-average completion time on unrelated machines.

Minimizing the maximum completion time (makespan)

Minimizing the maximum completion time is NP-hard even for identical machines, by reduction from the partition problem.

A constant-factor approximation is attained by the Longest-processing-time-first algorithm (LPT).

Horowitz and Sahni^[3] presented:

• Exact dynamic programming algorithms for minimizing the maximum completion time on both uniform and unrelated machines. These algorithms run in exponential time (recall that these problems are all NP-hard).
• Polynomial-time approximation schemes, which for any ε>0, attain at most (1+ε)OPT. For minimizing the maximum completion time on two uniform machines, their algorithm runs in time

O( 10 ^{2l} n) , where l is the smallest integer for which \epsilon \geq 2 ⋅ 10 ^{-l} . Therefore, the run-time is in O( n / \epsilon ^{2)} , so it is an FPTAS. For minimizing the maximum completion time on two unrelated machines, the run-time is O( 10 ^{l} n ^{2)} = O( n ^{2} / \epsilon) . They claim that their algorithms can be easily extended for any number of uniform machines, but do not analyze the run-time in this case.

Hochbaum and Shmoys^[4] presented several approximation algorithms for any number of identical machines. Later,^[5] they developed a PTAS for uniform machines.

Epstein and Sgall^[6] generalized the PTAS for uniform machines to handle more general objective functions. Let C_i (for i between 1 and m) be the makespan of machine i in a given schedule. Instead of minimizing the objective function max(C_i), one can minimize the objective function max(f(C_i)), where f is any fixed function. Similarly, one can minimize the objective function sum(f(C_i)).

Monotonicity and Truthfulness

In some settings, the machine speed is the machine's private information, and we want to incentivize machines to reveal their true speed, that is, we want a truthful mechanism. An important consideration for attaining truthfulness is monotonicity.^[7] It means that, if a machine reports a higher speed, and all other inputs remain the same, then the total processing time allocated to the machine weakly increases. For this problem:

• Auletta, De Prisco, Penna and Persiano^[8] presented a 4-approximation monotone algorithm, which runs in polytime when the number of machines is fixed.
• Ambrosio and Auletta^[9] proved that the Longest Processing Time algorithm is monotone whenever the machine speeds are powers of some c ≥ 2, but not when c ≤ 1.78. In contrast, List scheduling is not monotone for c > 2.
• Andelman, Azar and Sorani^[10] presented a 5-approximation monotone algorithm, which runs in polytime even when the number of machines is variable.
• Kovacz^[11] presented a 3-approximation monotone algorithm.

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 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 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.^[12]

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, flow shop scheduling and job shop scheduling.

External links

• Summary of parallel machine problems without preemtion

References

1. Bruno. J.. Coffman. E. G.. Sethi. R.. 1974-07-01. Scheduling independent tasks to reduce mean finishing time. Communications of the ACM. 17. 7. 382–387. 10.1145/361011.361064. 0001-0782. free.
2. Sahni. Sartaj K.. 1976-01-01. Algorithms for Scheduling Independent Tasks. Journal of the ACM. 23. 1. 116–127. 10.1145/321921.321934. 0004-5411. free.
3. Horowitz. Ellis. Sahni. Sartaj. 1976-04-01. Exact and Approximate Algorithms for Scheduling Nonidentical Processors. Journal of the ACM. 23. 2. 317–327. 10.1145/321941.321951. 18693114 . 0004-5411. free.
4. Hochbaum. Dorit S.. Shmoys. David B.. 1987-01-01. Using dual approximation algorithms for scheduling problems theoretical and practical results. Journal of the ACM. 34. 1. 144–162. 10.1145/7531.7535. 0004-5411. 9739129. free.
5. Hochbaum. Dorit S.. Shmoys. David B.. 1988-06-01. A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach. SIAM Journal on Computing. 17. 3. 539–551. 10.1137/0217033. 0097-5397.
6. Epstein. Leah. Sgall. Jiri. 2004-05-01. Approximation Schemes for Schedulingon Uniformly Related and Identical Parallel Machines. Algorithmica. en. 39. 1. 43–57. 10.1007/s00453-003-1077-7. 12965369 . 1432-0541.
7. Book: Archer. A.. Tardos. E.. Proceedings 42nd IEEE Symposium on Foundations of Computer Science . Truthful mechanisms for one-parameter agents . 2001-10-01. https://ieeexplore.ieee.org/document/959924. 482–491. 10.1109/SFCS.2001.959924. 0-7695-1390-5 . 11377808 .
8. Book: Auletta. Vincenzo. De Prisco. Roberto. Penna. Paolo. Persiano. Giuseppe. Stacs 2004 . Deterministic Truthful Approximation Mechanisms for Scheduling Related Machines . 2004. Diekert. Volker. Habib. Michel. https://link.springer.com/chapter/10.1007/978-3-540-24749-4_53. Lecture Notes in Computer Science. 2996 . en. Berlin, Heidelberg. Springer. 608–619. 10.1007/978-3-540-24749-4_53. 978-3-540-24749-4.
9. Book: Ambrosio. Pasquale. Auletta. Vincenzo. Approximation and Online Algorithms . Deterministic Monotone Algorithms for Scheduling on Related Machines . 2005. Persiano. Giuseppe. Solis-Oba. Roberto. https://link.springer.com/chapter/10.1007/978-3-540-31833-0_22. Lecture Notes in Computer Science. 3351 . en. Berlin, Heidelberg. Springer. 267–280. 10.1007/978-3-540-31833-0_22. 978-3-540-31833-0.
10. Book: Andelman. Nir. Azar. Yossi. Sorani. Motti. Stacs 2005 . Truthful Approximation Mechanisms for Scheduling Selfish Related Machines . 2005. Diekert. Volker. Durand. Bruno. https://link.springer.com/chapter/10.1007/978-3-540-31856-9_6. Lecture Notes in Computer Science. 3404 . en. Berlin, Heidelberg. Springer. 69–82. 10.1007/978-3-540-31856-9_6. 978-3-540-31856-9.
11. Book: Kovács, Annamária. Algorithms – ESA 2005 . Fast Monotone 3-Approximation Algorithm for Scheduling Related Machines . 2005. Brodal. Gerth Stølting. Leonardi. Stefano . https://link.springer.com/chapter/10.1007/11561071_55 . Lecture Notes in Computer Science. 3669 . en. Berlin, Heidelberg. Springer. 616–627. 10.1007/11561071_55. 978-3-540-31951-1.
12. Kwok. Yu-Kwong. Ahmad. Ishfaq. 1999-12-01. Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Computing Surveys. 31. 4. 406–471. 10.1145/344588.344618. 0360-0300. 10.1.1.322.2295. 207614150 .