Lateness (Interval Scheduling)

computation scheduling

Definition

Lateness

The lateness of a job is the amount by which its completion time exceeds its due date, allowing negative values for early jobs.
If job $j$ has completion time $C_j$ and due date $d_j$, then its lateness is

$$L_j=C_j-d_j.$$

Interpretation

If $L_j>0$, then job $j$ is late. If $L_j=0$, it completes exactly at its due date. If $L_j<0$, it completes early.

For an interval instance with fixed interval $I_j=[s_j,f_j)$, the completion time is $C_j=f_j$, so

$$L_j=f_j-d_j.$$

Maximum lateness

Maximum lateness objective

The maximum lateness of a schedule is

$$L_{\max }=\underset{j\in J}{\max }{L}_j.$$

The scheduling objective $\gamma =L_{\max }$ asks for a feasible schedule with minimum maximum lateness.

Maximum lateness measures the worst due-date violation. It differs from the unit penalty $U_j$, which records only whether a job is late and not how late it is.