Identical-machines scheduling is an optimization problem in computer science and operations research.
We are given n jobs J1, J2, ..., Jn 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.
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.
" 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 P||
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.
Minimizing the average completion time (P||
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.
Minimizing the weighted average completion time is NP-hard even on identical machines, by reduction from the knapsack problem.
[1] It is NP-hard even if the number of machines is fixed and at least 2, by reduction from the partition problem.
[2] Sahni[2] presents an exponential-time algorithm and a polynomial-time approximation scheme for solving both these NP-hard problems on identical machines: Minimizing the maximum completion time (P||
) is NP-hard even for identical machines, by reduction from the partition problem.
Graham proved that: Coffman, Garey and Johnson presented a different algorithm called multifit algorithm, using techniques from bin packing, which has an approximation factor of 13/11≈1.182.
Huang and Lu[5] presented a simple polynomial-time algorithm that attains an 11/9≈1.222 approximation in time O(m log m + n), through the more general problem of maximin-share allocation of chores.
Sahni[2] presented a PTAS that attains (1+ε)OPT in time
The algorithm uses a technique called interval partitioning.
Hochbaum and Shmoys[6] presented several approximation algorithms for any number of identical machines (even when the number of machines is not fixed): Leung[7] improved the run-time of this algorithm to
Maximizing the minimum completion time (P||
) is applicable when the "jobs" are actually spare parts that are required to keep the machines running, and they have different life-times.
The goal is to keep machines running for as long as possible.
Woeginger[9] presented a PTAS that attains an approximation factor of
a huge constant that is exponential in the required approximation factor ε.
Alon, Azar, Woeginger and Yadid[10] consider a more general objective function.
Given a positive real function f, which depends only on the completion times Ci, they consider the objectives of minimizing
They prove that, if f is non-negative, convex, and satisfies a strong continuity assumption that they call "F*", then both minimization problems have a PTAS.
Similarly, if f is non-negative, concave, and satisfies F*, then both maximization problems have a PTAS.
In both cases, the run-time of the PTAS is O(n), but with constants that are exponential in 1/ε.