Notation for theoretic scheduling problems

From Wikipedia, the free encyclopedia

This article may need to be wikified to meet Wikipedia's quality standards.
Please help improve this article, especially its introduction, section layout, and relevant internal links. (help)

A convenient notation for theoretic scheduling problems was introduced by Graham, Lawler, Lenstra & Rinnoy Kan. It consists of three fields α|β|γ where 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 \sum C_i 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 C_i\le d_i and Ui = 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 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]
Retrieved from "http://en.wikipedia.org../../../n/o/t/Notation_for_theoretic_scheduling_problems.html"