8 The M/G/1 priority system
Usually not all jobs have the same urgency. Some jobs are supposed to be ready within a
day or a we ek, while other jobs have a delivery date of 4 to 6 weeks from now. Further some
customers are regular ones with contracts specifying short throughput times, others are
occasional and receive a delivery date according to the present amount of work in process.
This makes it quite natural to study a simplified production system in which arriving
jobs belong to different job classes and these job classes have different throughput time
requirements. To further simplify this we say that the job classes have different priorities.
If we number the priority classes from 1 upto r, then class 1 is top priority, class 2 has
the second highest priority, etc. Further the job classes may have different proc essing time
characteristics. We denote the processing time of class i by B
i
, with mean E(B
i
) and mean
residual processing time E(R
i
) with E(R
i
) = E(B
2
i
)/2E(B
i
). Class i jobs arrive according
to a Poisson process with rate λ
i
.
We will consider two variants of the priority rule. In the first one a job that has started
cannot be interrupted; in the second one the processing of a job can be interrupted by
newly arrived jobs of higher priority classes. If all higher priority jobs are served, the
servicing of the job is resumed where it was preempted, i.e., no work is lost. The first
type of priority is called non-preemptive, the second type is called preemptive-resume. If
we think of the situation in which all production is done on one machine, non-preemptive
priorities are far more natural, since an interrupt might lead to extra setup time or even
to destruction of the product. If however the production capacity is mainly labour, then
switching from one job to another might be fairly easy.
8.1 The non-preemptive pr iority system
The analysis is again based on the mean value approach, and it is a more or less straight-
forward extension of what we have seen for the M/G/1 system in chapter 7. For class i
jobs, the quantities of interest are the mean waiting time E(W
i
), the mean number of jobs
waiting in the queue E(L
q
i
), the mean throughput time E(S
i
) and the mean number of
jobs in the system E(L
i
). Let us denote by ρ
i
= λ
i
E(B
i
) the utilization by class i jobs.
Then, according to the PASTA property, an arriving job finds with probability ρ
i
a class
i job in service. Further, upon arrival the job finds on the average E(L
q
i
) jobs of class i in
the queue.
Let us first look at a job of class 1. This job has to wait for jobs of its own class that
arrived before, and also for the job (if any) on the machine. So,
E(W
1
) = E(L
q
1
)E(B
1
) +
r
X
i=1
ρ
i
E(R
i
).
Defining,
ρ =
r
X
i=1
ρ
i
1
