 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.
Contents
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.
Multistage 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 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
 sptree, 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 and U_{i} = 1 otherwise. The common objective functions are 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. 21169. ISBN 0792352858 (HB) 0792350197 (Set)
 Peter Brucker, Sigrid Knust. Complexity results for scheduling problems
Wikimedia Foundation. 2010.
Look at other dictionaries:
Scheduling — is the process of deciding how to commit resources between a variety of possible tasks. Time can be specified (scheduling a flight to leave at 8:00) or floating as part of a sequence of events.Scheduling may refer to: * I/O scheduling, the order… … Wikipedia
Mathematical economics — Economics … Wikipedia
List of algorithms — The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.If you intend to describe a new algorithm,… … Wikipedia
List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… … Wikipedia
combinatorics — /keuhm buy neuh tawr iks, tor , kom beuh /, n. (used with singular v.) See combinatorial analysis. * * * Branch of mathematics concerned with the selection, arrangement, and combination of objects chosen from a finite set. The number of possible… … Universalium
Time — This article is about the measurement. For the magazine, see Time (magazine). For other uses, see Time (disambiguation). The flow of sand in an hourglass can be used to keep track of elapsed time. It also concretely represents the present as… … Wikipedia