Uniform-machines scheduling

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 machine scheduling, in which all machines have the same speed. This 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 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 average of the completion time, where each job has a different weight.

Algorithms

The SPT algorithm (Shortest Processing Time First), which runs in time O(n log n), minimizes the average completion time on identical machines.

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. They show that minimizing the weighted average completion time is NP-hard even on identical machines, by reduction from the knapsack problem.

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

The simple algorithm called greedy number partitioning, or the LPT algorithm (Longest Processing Time First), sorts the jobs by their length, longest first, and then assigns them to the processor with the earliest end time so far. While originally developed for identical machines, it has good asymptotic convergence properties even for uniform machines.

Horowitz and Sahni present several algorithms for both uniform machines and unrelated machines, with various objective functions:

• An exact algorithm for minimizing the maximum completion time on both uniform and unrelated machines, with exponential run-time (note that these problems are NP-hard).
• An exact algorithm for minimizing the average completion time on uniform machines, with run time O(n log m n).
• An exact algorithms for minimizing the weighted-average completion time on uniform machines, with exponential run-time (this problem is NP-hard).

Hochbaum and Shmoys, who developed a PTAS for identical processors, extended their PTAS to handle processors with different speeds.

Epstein and Sgall generalized this PTAS to handle more general objective functions. Let s_i (for i between 1 and k) be the makespan of processor i in a given schedule. Instead of minimizing the objective function max(s_i), one can minimize the objective function max(f(s_i)), where f is any fixed function. Similarly, one can minimize the objective function sum(f(s_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.