Identical-machines scheduling

Identical machine scheduling is an optimization problem in computer science and operations research. We are given n jobs J₁, J₂, ..., J_n of varying processing times, which need to be scheduled on m identical machines, such that a certain objective function is optimized, for example, the makespan is minimized.

Identical machine scheduling is a special case of uniform machine scheduling, which is itself a special case of optimal job scheduling. In the general case, the processing time of each job may be different on different machines; in the case of identical machine scheduling, the processing time of each job is the same on each machine. Therefore, identical machine scheduling is equivalent to multiway number partitioning.

In the standard three-field notation for optimal job scheduling problems, the identical-machines variant is denoted by P in the first field. For example, " P||$C_{\max }$" 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 the standard three-field notation for optimal job scheduling problems, the identical-machines variant is denoted by P in the first field. For example, " P||☃☃" is an identical machine scheduling problem with no constraints, where the goal is to minimize the maximum completion time. 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}$.
  • There can be many SPT schedules; finding the SPT schedule with the smallest finish time (also called OMFT - optimal mean finish time) is NP-hard. Sahni presents an exponential-time algorithm and a polynomial-time approximation algorithm for identical machines.
• 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 present an algorithm, running in time $O(\max(mn^{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.

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. Many exact and approximation algorithms are known.

For identical machines, the problem is equivalent to multiway number partitioning, where the job lengths are the numbers, the number of machines (denoted here by m) is the number of parts (denoted there by k), and the goal is to minimize the maximum sum. See multiway number partitioning#minmax for details about exact and approximate algorithms.

Graham proved that:

• Any list scheduling algorithm (an algorithm that processes the jobs in an arbitrary fixed order, and schedules each job to the first available machine) is a $2-1/m$ approximation for identical machines. The bound is tight for any m. This algorithm runs in time O(n).
• The specific list-scheduling algorithm called Longest Processing Time First (LPT), which sorts the jobs by descending length, is a $4/3-1/3m$ approximation for identical machines. It has good asymptotic convergence properties even for uniform machines. It is also called greedy number partitioning.

Sahni presented several algorithms for identical machines. In particular:

• A PTAS that attains (1+ε)OPT in time $O(n\cdot (n^{2}/\epsilon )^{m-1})$. It is an FPTAS if m is fixed. For m=2, the run-time improves to $O(n^{2}/\epsilon )$. The algorithm uses a technique called interval partitioning.

Horowitz and Sahni 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\cdot 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 presented several approximation algorithms for any number of identical machines (even when the number of machines is not fixed):

• For any r >0, an algorithm with approximation ratio at most (6/5+2^−r ) in time $O(n(r+\log {n}))$.
• For any r >0, an algorithm with approximation ratio at most (7/6+2^−r ) in time $O(n(rm^{4}+\log {n}))$.
• For any ε>0, an algorithm with approximation ratio at most (1+ε) in time $O((n/\varepsilon )^{(1/\varepsilon ^{2})})$ . This is a PTAS. Note that, when the number of machines is a part of the input, the problem is strongly NP-hard, so no FPTAS is possible.
  • The run-time of this algorithm was later improved to $O\left((n/\varepsilon )^{(1/\varepsilon )\log {(1/\varepsilon )}}\right)$.

Later, they developed a PTAS for uniform machines.

Epstein and Sgall 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)).

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.

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