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 constraints, and γ the objective function. Since its introduction in the late 1970s the notation has been constantly extended, sometimes inconsistently. As a result, today there are some problems that appear with distinct notations in several papers.
Each job comes with a given processing time. ; 1 ; P ; Q ; R These letters might be followed by the number of machines which is then fixed, here stands then for a fixed number. For example, is the problem of assigning each of the given jobs to one of the 2 given machines so to minimize the maximum total processing time over the machines.
Multi-stage problem
; O ; F : Flow shop problem. Every job consists of operations for, to be scheduled in that order. Operation must be processed for units on machine. ; J : Job shop problem. Every job consists of operations for, to be scheduled in that order. Operation must be processed for units on a dedicated machine with for.
Job characteristics
The processing time may be equal for all jobs or even of unit length. All processing times are assumed to be integers. In some older research papers however they are assumed to be rationals. ; ; ; ; ; pmtn ;
Precedence relations
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 ; chains ; tree ; intree ; outtree ; opposing forest ; sp-graph ; bounded height ; level order ; interval order ; quasi-interval order ; over-interval order ; Am-order ; DC-graph ; 2-dim partial order ; k-dim partial order In the presence of a precedence relation one might in addition assume time lags. Let denote the start time of a job and its completion time. Then the precedence relation implies the constraint. If no time lag is specified then it is assumed to be zero. Time lags can be positive or negative numbers. ; l ;
Transportation delays
; ; ; ; ;
Various constraints
; rcrc ; no-wait ; no-idle ; ; ;
Objective functions
Usually the goal is to minimize some objective value. One difference is the notation where the goal is to maximize the number of jobs that complete before their deadline. This is also called the throughput. The objective value can be sum, possibly weighted by some given priority weights per job. ; - ; ; ; ; ; ;
Examples
Adapted from ; 1|prec|: a single machine, general precedence constraint, minimizing maximum lateness. ; R|pmtn|: variable number of unrelated parallel machines, allowing preemption, minimizing total completion time. ; J3||: 3-machines job shop with unit processing times, minimizing maximum completion time. ; P||: parallel identical machines, each job comes with a number of machines on which it must be scheduled at the same time, minimizing maximum completion time.
