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 has completion time and due date , then its lateness is

Interpretation

If , then job is late. If , it completes exactly at its due date. If , it completes early.

For an interval instance with fixed interval , the completion time is , so

Maximum lateness

Maximum lateness objective

The maximum lateness of a schedule is

The scheduling objective asks for a feasible schedule with minimum maximum lateness.

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