Scheduling Notation

Definition

Scheduling Notation

Scheduling notation is the three-field notation

for classifying a scheduling problem. The field describes the machine environment, describes job characteristics and constraints, and describes the objective function.

Machine environment

The field describes the machines and the operational structure of each job.

For single-stage jobs, each job has one operation.

Except for the special case , a single-stage machine environment has the form

where is the machine type and is the number of machines.

Notation	Meaning
	one machine
	identical parallel machines
	uniform parallel machines with different speeds
	unrelated parallel machines

If is omitted, the number of machines is part of the input. For example, denotes an arbitrary number of identical parallel machines.

Thus is not an additional fourth field. It is the first part of in environments such as , , and .

For identical machines, job has the same processing time on every machine. For uniform machines, machine has speed , so job takes time

on machine . For unrelated machines, the processing time depends directly on the pair and is written .

Shop environments

For multi-stage jobs, each job consists of several operations. Usually, only one operation of the same job may be processed at a time.

Shop environments use the same pattern , but now describes the order structure of operations rather than only the speed relation between machines.

Notation	Name	Structure
	open shop	operations may be scheduled in any order
	flow shop	operations follow the same fixed machine order for every job
	job shop	each job has its own fixed operation order

As before, may be omitted when the number of machines is variable or clear from context.

In an open-shop or flow-shop instance, job has operations for . Operation must be processed on machine and takes time .

In a job-shop instance, job has operations for . Operation must be processed on machine and takes time . The machines for different operations of the same job are usually distinct:

Job constraints

The field lists additional job characteristics and constraints.

Notation	Meaning
	release time; job cannot be processed before time
	due date; lateness may be allowed but penalised
	strict deadline; job must complete by
	preemption is allowed
	precedence constraints are present

Preemption means that a job may be stopped and resumed later, possibly on another machine. A precedence constraint is a partial order on jobs. If , then job may start only after job has completed.

Objectives

The field names the quantity to optimise; it does not prescribe an approximation or a threshold. Unless stated otherwise, the task is to find a feasible schedule minimising that quantity. For a fixed instance , write

Thus is an objective function, is the value of one schedule, and is the minimum value. The notation ordinarily describes an optimisation problem. A decision version adds a target and asks whether some feasible satisfies . An approximation algorithm still addresses the optimisation problem, but may return a value above within a specified guarantee.

For a schedule, define for each job :

Here is the completion time, is the lateness, and is the unit penalty for missing the due date.

Objective	Meaning
absent	find any feasible schedule
	minimise the number of late jobs, equivalently maximise on-time throughput
	minimise maximum lateness
	minimise makespan
	minimise total completion time, equivalently average completion time

Conventions

Variants

Scheduling notation is not completely uniform in the literature. Some authors omit from when the objective already contains or , since those objectives require due dates. Some authors also write instead of when strict deadlines are clear from context.

Most scheduling models use integer input parameters unless another domain is stated explicitly.

Scheduling Zoo

Definition

Scheduling Zoo

The scheduling zoo

Link to original

Examples

Writing notation

One machine with no additional constraints and objective of minimising makespan is written as

Three identical machines with precedence constraints and deadlines, where the task is to check whether every job can meet its deadline, can be written as

Two uniform machines with release times and objective of minimising average completion time can be written as

Since is fixed for an instance, this is equivalent to minimising .

Reading notation

The notation

means a single-machine problem where each job has a release time and a strict deadline. The objective is to minimise the number of jobs completed after their deadlines, or equivalently to maximise the number completed on time.

The notation

means a single-machine problem where each job has a release time. The objective is to minimise the total completion time, equivalently the average completion time.

The notation

means an unrelated-parallel-machine problem with a variable number of machines. Jobs have release times and may be preempted. The objective is to minimise the maximum lateness.

Room booking

A room can host at most one event at a time. Each event has a fixed interval and processing time

The problem of booking the maximum number of compatible events can be written as

This is the interval scheduling problem when each selected job must occupy its given interval.
If is not forced to equal , then even feasibility on one machine becomes hard; see a deadline gap can hide subset sum.

Two-machine factory scheduling

Suppose there are two identical machines and each job has release time , due date , and processing time . The decision version asks whether all jobs can be completed by their due dates. One notation is

The equality expresses the decision requirement that no job is late.