Scheduling Problem

computation scheduling

Definition

Scheduling Problem

A scheduling problem asks for an assignment of jobs to machines and times that satisfies the constraints of the instance and optimises a given objective.

Formally, an instance consists of a finite job set $J$, a finite machine set $M$, a feasibility predicate $F$ on assignments, and an objective function $C$.
A schedule is a function

$$\sigma :J\to M\times {\mathbb{R}}_{\ge 0}$$

where $\sigma (j)=(m_j,t_j)$ means that job $j$ starts on machine $m_j$ at time $t_j$.
The problem is to find a feasible schedule $\sigma$ such that $C(\sigma )$ is optimal.

Components

Jobs

Each job $j\in J$ represents a unit of work. Depending on the model, it may have a processing time $p_j$, release time $r_j$, deadline $d_j$, weight $w_j$, or a fixed interval $[s_j,f_j)$.

Machines

Each machine $m\in M$ is a resource that can process jobs. In the basic single-machine model, $M=\{m\}$ and at most one job may run at any time.

Constraints

A feasibility predicate $F(\sigma )$ encodes the rules of the model. Typical constraints are:

• no machine processes two jobs at the same time;
• a job starts after its release time;
• a job completes before its deadline;
• precedence constraints are respected.

Objective

The objective function $C$ defines what counts as a good schedule. Common objectives include minimising maximum lateness, minimising total completion time, or maximising the number of compatible jobs.

Form

A scheduling problem is not one problem but a schema. A concrete problem is obtained by fixing:

1. the structure of jobs;
2. the machine model;
3. the feasibility predicate;
4. the objective.

For example, the interval scheduling problem fixes each job to an immutable interval and asks for the largest feasible subset of non-overlapping jobs.

Notation

Definition

Scheduling Notation

Scheduling notation is the three-field notation

$$\alpha \mid \beta \mid \gamma$$

for classifying a scheduling problem. The field $\alpha$ describes the machine environment, $\beta$ describes job characteristics and constraints, and $\gamma$ describes the objective function.

Link to original