Tardiness (scheduling) explained

In scheduling, tardiness is a measure of a delay in executing certain operations and earliness is a measure of finishing operations before due time. The operations may depend on each other and on the availability of equipment to perform them.

Typical examples include job scheduling in manufacturing and data delivery scheduling in data processing networks.^[1]

In manufacturing environment, inventory management considers both tardiness and earliness undesirable. Tardiness involves backlog issues such as customer compensation for delays and loss of goodwill. Earliness incurs expenses for storage of the manufactured items^[2] and ties up capital.

Mathematical formulations

In an environment with multiple jobs, let the deadline be

d _{i} and the completion time be C _{i} of job i . Then for job i

• lateness is

L _{i=C} _{i-d} _{i} ,

• earliness is

E _{i} = max ( 0 , d _{i-C} _{i)} ,

• tardiness is

T _{i} = max ( 0 , C _{i-d} _{i)} .

In scheduling common objective functions are

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, w _{iC} _{max,} w _{iL} _{max,} w _{iE} _{max,} w _{iT} _{max,} \sum w _{iC} _{i,} \sum w _{iL} _{i,} \sum w _{iE} _{i,} \sum w _{iT} _{i} , where every job comes with a weight 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]

Notes and References

1. http://dl.acm.org/citation.cfm?id=2767221 Minimizing tardiness in data aggregation scheduling with due date consideration for single-hop wireless sensor networks
2. Derya Eren Akyol, G. Mirac Bayhan, Multi-machine earliness and tardiness scheduling problem: an interconnected neural network approach, The International Journal of Advanced Manufacturing Technology May 2008, Volume 37, Issue 5, pp 576-588.
3. http://www2.informatik.uni-osnabrueck.de/knust/class/ "Complexity results for scheduling problems"