Notation for theoretic scheduling problems

A convenient notation for theoretic scheduling problems was introduced by Ronald Graham, Eugene Lawler, Jan Karel Lenstra and Alexander Rinnooy Kan. 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.

Machine environment

Single stage problems

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_ij for job i on machine j

The last two letters might be followed by a the number of machines which is then fixed, here m stands then for a fixed number.

Multi-stage problem

O 

open shop problem

F 

flow shop problem

J 

job shop problem

Job characteristics

The processing time may be equal for all jobs (p_i = p, or p_ij = p) or even of unit length (p_i = 1, or p_ij = 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 $\sum 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

size_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

Objective functions

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\le d_i$ and U_i = 1 otherwise. The common objective functions are $C_\max, L_\max, E_\max, T_\max, \sum C_i, \sum L_i, \sum E_i, \sum T_i$ or weighted version of these sums, where every job comes with a priority w_i.

References

• B. Chen, C.N. Potts and G.J. Woeginger. "A review of machine scheduling: Complexity, algorithms and approximability". Handbook of Combinatorial Optimization (Volume 3) (Editors: D.-Z. Du and P. Pardalos), 1998, Kluwer Academic Publishers. 21-169. ISBN 0-7923-5285-8 (HB) 0-7923-5019-7 (Set)
• Peter Brucker, Sigrid Knust. Complexity results for scheduling problems