Tardiness (scheduling)

In an environment with multiple jobs, let the deadline be ${\displaystyle d_{i}}$ and the completion time be ${\displaystyle C_{i}}$ of job ${\displaystyle i}$. Then for job ${\displaystyle i}$

• lateness is ${\displaystyle L_{i}=C_{i}-d_{i}}$,
• earliness is ${\displaystyle E_{i}=\max(0,d_{i}-C_{i})}$,
• tardiness is ${\displaystyle T_{i}=\max(0,C_{i}-d_{i})}$.

In scheduling common objective functions are ${\displaystyle C_{\max },L_{\max },E_{\max },T_{\max },\sum C_{i},\sum L_{i},\sum E_{i},\sum T_{i}}$ or weighted version of these sums, ${\displaystyle w_{i}C_{\max },w_{i}L_{\max },w_{i}E_{\max },w_{i}T_{\max },\sum w_{i}C_{i},\sum w_{i}L_{i},\sum w_{i}E_{i},\sum w_{i}T_{i}}$, where every job comes with a weight ${\displaystyle w_{i}}$. The weight is a representation of job cost, priority, etc.

In a large number of cases the problems of optimizing these functions are NP-hard.[3]