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.

`t _{j,k}` is the time required of machine

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 ≥ M _{1} = max{t_{j} : ∀ 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{M}._{1}, M_{2}

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 `M _{1}`)
and that its makespan is no greater than the larger of

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 `n _{k}` be the number of jobs assigned
to machine

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 smallestn−mjobs optimally followed by the largestmjobs 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 `m _{1}`, has none of the largest

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

Xto each node_{j}jsuch that

Xif_{j}= 1jis a terminal job, or

Xwhere_{j}= 1 + X_{i}iis the direct successor ofj.

Until all jobs are scheduled, if there are fewer thanmjobs 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

Xto each job_{j}jsuch that

Xif_{j}= 1jhas no successors, and

X._{j}= 1 + max{ X_{i}: i ← j }

LetK = max{ X._{j}}

LetS}._{k}= { X_{j}: X_{j}= k

Fork = K, K−1, K−2, ... ,1if|S, try to complete_{k}| <mSby adding jobs without unscheduled predecessors, choosing those with largest labels first._{k}

ScheduleSusing McNaughton's algorithm._{k}

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 `t _{j}` 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

Xto each job_{j}jsuch that

Xif_{j}= t_{j}jhas no successors, and

X._{j}= t_{j}+ max{ X_{i}: i ← j }

Until all jobs are completed, use the following dispatching rule, the first decision point being the availability of allmmachines.

Set allR._{j}= 0

Setm' = m, the number of available machines.

Whilem' > 0,

LetS = { j : X._{j}≥ X_{i}∀ jobs i }

SetR._{j}= min{ 1, m'/|S| } ∀ j ∈ S

Reducem'by|S|.

Update the labels on each job by reducingXby_{j}Rfor 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_{j}iandjsuch thatRand_{i}< R_{j}X._{i}≥ X_{j}

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`.