Notation for theoretic scheduling problems
From Wikipedia, the free encyclopedia
A convenient notation for theoretic scheduling problems was introduced by Ronald Graham, Eugene Lawler, Jan Karel Lenstra & 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.
Contents |
[edit] Machine environment
[edit] 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 is processing time pi divided by speed sj
- R
- there are m parallel unrelated machines, there are given processing times pij 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.
[edit] Multi-stage problem
- O
- open shop problem
- F
- flow shop problem
- J
- job shop problem
[edit] Job characteristics
The processing time may be equal for all jobs (pi = p, or pij = p) or event of unit length (pi = 1, or pij = 1). This makes a difference because all release times, deadlines are assumed to be integer.
- ri
- for each job a release time is given before which it cannot be scheduled, default is 0.
- Di
- for each job a deadline is given after which it cannot be scheduled. If the objective is
for example, then this field is implicitly assumed. - pmtn
- the jobs may be preempted and execution resumed later, possibly on a different machine
- sizei
- Each job comes with a number of machines on which it must be scheduled at the same time, default is 1.
Precendence 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
[edit] Objective functions
Most objective functions depend on the deadline di and the completion time Ci of job i. We define lateness Li = Ci − di, earliness Ei = max{0,di − Ci}, tardiness Ti = max{0,Ci − di}, unit penalty Ui = 0 if 
and Ui = 1 otherwise. The common objective functions are 
or weighted version of these sums, where every job comes with a priority wi.
[edit] 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). [1]
- Peter Brucker, Sigrid Knust. Complexity results for scheduling problems. [2]
