Processing Time (Interval Scheduling)

Definition

Processing Time

The processing time $p_j$ of job $j$ is the amount of machine time required to complete the job.

On one machine, if job $j$ starts at time $S_j$ and is not preempted, then its completion time is

$$C_j=S_j+p_j.$$

Fixed intervals

In the basic interval scheduling problem, each job already has a fixed interval

$$I_j=[s_j,f_j).$$

The processing time is therefore the interval length:

$$p_j=f_j-s_j.$$

Equivalently, if the interval is described by a release time and strict deadline, then the fixed-interval case has

$$p_j={\bar{d}}_j-r_j.$$

Flexible windows

If $p_j<{\bar{d}}_j-r_j$, then the interval $[r_j,{\bar{d}}_j)$ is not the job itself but a feasible window in which the job may be placed. The schedule must then choose a start time $S_j$ satisfying

$$r_j\le S_j\text{and}{S}_j+p_j\le {\bar{d}}_j.$$

This extra freedom changes the problem. Feasibility on one machine is already hard in this setting; see a deadline gap can hide subset sum.