In this section we consider scheduling problems in which more than one machine is available for processing the jobs. It does not matter which machine a job is assigned to, but it cannot be processed on more than one machine at the same time. Such machines are known as parallel processors.
tj,k is the time required of machine k by job j. If tj,k1 = tj,k2 = tj for all machines k1 and k2, then they are said to be identical processors. If there exists a constant 0 < Rk ≤ 1 associated with each machine k such that tj,k = tj / Rk for all jobs j, then the machines are known as uniform processors. If no such processing rate can be associated with each machine, the machines are known as independent processors. The rest of this section will consider the special case of parallel identical processors, in which all Rk = 1.
Makespan is the total time required to process a set of jobs. In the single machine model, this was simply the sum of all processing and idle time, while in the multiple machine model it is the maximum value of this quantity over all machines.
As a job can be processed on at most one machine at a time, we have that
M ≥ M1 = max{tj : ∀ jobs j},
M ≥ M2 = ∑{tj/m : ∀ jobs j}.
If preempt-resume is allowed, the following, known as
McNaughton's Algorithm
[McNaughton, R. Scheduling with deadlines and loss functions
.
Management Science 6.1(1959)]
constructs a schedule which achieves one of these bounds and thus is optimal.
Determine M = max{M1 , M2}.
Arrange the jobs in any arbitrary order.
Assign the first M units of time to machine 1, the next M units to machine 2, and so on until all jobs are scheduled.
Note that if the division occurs part of the way through a job, then that job is assigned to two machines, its time being preempted on the larger numbered machine and resumed on the other.
The algorithm may be proven by showing that the resulting schedule is feasible (i.e. no job is scheduled on two machines at the same time, which is guaranteed by M1) and that its makespan is no greater than the larger of M1 and M2 (which is guaranteed by M2).
If jobs may not be preempted, no simple algorithm to find an optimal schedule is known. However, the following heuristic LPT dispatching rule may be used to find a reasonable but not necessarily optimal schedule.
Whenever a machine is available, schedule a job requiring the greatest amount of time.
Let nk be the number of jobs assigned to machine k, and let tj,k be the time required of machine k by job j. Assuming all jobs are initially available, the mean flowtime of the schedule is ∑∑{tj,k (nk+1−j)/n : ∀ jobs j, ∀ machines k},
The following algorithm may be used to schedule a set of n jobs on m parallel identical processors, minimizing the mean flowtime.
If n ≤ m, schedule all jobs on different machines. Otherwise schedule the smallest n−m jobs optimally followed by the largest m jobs all on different machines.
By section 1.2.1 (Adjacent Interchange Proof Example) we know that in an optimal schedule the jobs on each machine must be in SPT order, a condition clearly satisfied by this algorithm. Now suppose some schedule does not have the largest m jobs on different machines. Then one machine, say m1, has none of the largest m jobs, while another machine, say m2, has at least two of them, say j1 and j2. If i is the last job scheduled on m1, then ti < tj1 ≤ tj2. If we interchange the scheduled positions of i and j1, then the total flowtime on m1 is increased by tj1 − ti, while the total flowtime on m2 is decreased by 2 (tj1 − ti) as both i and j2 finish that much earlier. Thus there is a net decrease in the total flowtime and the original schedule must not be optimal, thus proving that any optimal schedule must have the largest m jobs on different machines. Now suppose the last job on each of two different machines are interchanged. The change in total flowtime on one machine will be equal and opposite to that on the other machine, and so it does not matter in which order the largest m jobs are assigned to different machines.
As there is no restriction as to which machines the jobs must be placed on, this algorithm can be used to generate many (in fact all) optimal schedules. The following SPT dispatching rule may also be used to find some, but not all, optimal schedules.
Whenever a machine is available, schedule a job requiring the smallest amount of time.
Notice that this is the exact opposite of the heuristic for minimizing makespan.
No efficient algorithm is known for the general problem of minimizing makespan with precedence constraints, although some are known for special cases.
If all processing times are constant, say 1,
and the precedence constraints form an assembly forest,
then the following, known as
Hu's algorithm
[Hu, T.C. Parallel sequencing and assembly line problems
.
Operations Research 9.6(1961)]
will produce an optimal schedule.
Assign a label Xj to each node j such that
Xj = 1 if j is a terminal job, or
Xj = 1 + Xi where i is the direct successor of j.
Until all jobs are scheduled, if there are fewer than m jobs with no unscheduled predecessors then schedule the remaining machines with one unit of idle time each, otherwise schedule the m jobs with largest labels and no unscheduled predecessors to different machines.
If preemption is allowed, the following,
known as the
Muntz-Coffman algorithm
[Muntz, R.R.; Coffman, E. Optimal preemptive scheduling on two-processor systems
.
IEEE Transactions on Computers 18.11(1969)]
may be used with arbitrary precedence constraints,
although the solution may be suboptimal for the case of more than two machines.
Assign a label Xj to each job j such that
Xj = 1 if j has no successors, and
Xj = 1 + max{ Xi : i ← j }.
Let K = max{ Xj }.
Let Sk = { Xj : Xj = k }.
For k = K, K−1, K−2, ... ,1 if |Sk| <m, try to complete Sk by adding jobs without unscheduled predecessors, choosing those with largest labels first.
Schedule Sk using McNaughton's algorithm.
The previous two algorithms may also be used to schedule jobs with unequal processing times if preemption is allowed and if the processing times are commensurable, by simply subdividing each job j into a string of tj jobs each with unit processing time. The resulting set of jobs may be quite large however.
If processor sharing is allowed, and the precedence constraints form an assembly tree,
then the following modified version of the
Muntz-Coffman algorithm
[Muntz, R.R.; Coffman, E. Preemptive scheduling of real-time tasks on multiprocessor systems
.
JACM 17.2(1970)]
may be used to minimize makespan of a set of jobs with arbitrary processing
times on any number of machines.
Assign a label Xj to each job j such that
Xj = tj if j has no successors, and
Xj = tj + max{ Xi : i ← j }.
Until all jobs are completed, use the following dispatching rule, the first decision point being the availability of all m machines.
Set all Rj = 0.
Set m' = m, the number of available machines.
While m' > 0,
Let S = { j : Xj ≥ Xi ∀ jobs i }.
Set Rj = min{ 1, m'/|S| } ∀ j ∈ S.
Reduce m' by |S|.
Update the labels on each job by reducing Xj by Rj for each unit of scheduled time, until either some job is completed in which case it is removed from further consideration, or until there are two jobs i and j such that Ri < Rj and Xi ≥ Xj.
The resulting schedule may be converted into a schedule with identical makespan but without processor sharing by applying McNaughton's algorithm to each time interval delimited by changes in the set of jobs with positive R.