Tardiness (scheduling)

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]

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\}. The 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 otimizing these functions are NP-hard.[3]

References

  1. Minimizing tardiness in data aggregation scheduling with due date consideration for single-hop wireless sensor networks, Wireless Networks, Volume 21 Issue 4, May 2015 Pages 1259-1273
  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. "Complexity results for scheduling problems", University of Osnabrueck
This article is issued from Wikipedia - version of the Tuesday, April 05, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.