A convenient notation for theoretic scheduling problems was introduced by Ronald Graham, Eugene Lawler, Jan Karel Lenstra and Alexander Rinnooy Kan in. It consists of three fields: α, β and γ.
Each field may be a comma separated list of words. The α field describes the machine environment, β the job characteristics, and γ the objective function.
Each job comes with a given processing time.
1
there is a single machine
P
there are
m
parallel identical machines
Q
there are
m
parallel machines with different given speeds, length of job
i
on machine
j
is the processing time
p
i
divided by speed
s
j
R
there are
m
parallel unrelated machines, there are given processing times
p
i
j
for job
i
on machine
j
The last three letters might be followed by the number of machines which is then fixed, here
m
stands then for a fixed number.
O
open shop problem
F
flow shop problem
J
job shop problem
The processing time may be equal for all jobs (
p
i
=
p
, or
p
i
j
=
p
) or even of unit length (
p
i
=
1
, or
p
i
j
=
1
). This makes a difference because all release times, deadlines are assumed to be integer.
r
i
for each job a release time is given before which it cannot be scheduled, default is 0.
d
i
for each job a deadline is given after which it cannot be scheduled. If the objective is
∑
U
i
for example, then this field is implicitly assumed.
pmtn
the jobs may be preempted and execution resumed later, possibly on a different machine
s
i
z
e
i
Each job comes with a number of machines on which it must be scheduled at the same time, default is 1.
Precedence relations might be given for the jobs, in form of a partial order, meaning that if i is a predecessor of i' in that order, i' can start only when i is completed.
prec
an arbitrary precedence relation is given
sp-tree, tree, intree, outtree, chain
specific partial orders
Most objective functions depend on the deadline
d
i
and the completion time
C
i
of job
i
. We define lateness
L
i
=
C
i
−
d
i
, earliness
E
i
=
max
{
0
,
d
i
−
C
i
}
, tardiness
T
i
=
max
{
0
,
C
i
−
d
i
}
, unit penalty
U
i
=
0
if
C
i
≤
d
i
and
U
i
=
1
otherwise. The common objective functions are
C
max
,
L
max
,
E
max
,
T
max
,
∑
C
i
,
∑
L
i
,
∑
E
i
,
∑
T
i
or weighted version of these sums, where every job comes with a priority
w
i
.
Adapted from
1|prec|
L
max
a single machine, general precedence constraint, minimizing maximum lateness.
R|pmtn|
∑
C
i
variable number of unrelated parallel machines, allowing preemption, minimizing total completion time.
J3|
p
i
j
|
C
max
3-machines job shop with unit processing times, minimizing maximum completion time.
