Опоздание (по расписанию)

В планировании опоздание — это мера задержки выполнения определенных операций, а преждевременность — мера завершения операций досрочно. Операции могут зависеть друг от друга и от наличия оборудования для их выполнения.

Типичные примеры включают планирование заданий на производстве и планирование доставки данных в сетях обработки данных.

В производственной среде управление запасами считает нежелательными как опоздания, так и ранние сроки. Опоздание связано с такими проблемами, как компенсация клиентам за задержки и потеря репутации. Своевременность влечет за собой расходы на хранение изготовленной продукции. и связывает капитал.

Математические формулировки

В среде с несколькими заданиями пусть крайний срок будет $d_{i}$ и время завершения будет $C_{i}$ работы $i$. Тогда на работу $i$

• опоздание это $L_{i}=C_{i}-d_{i}$,
• скороспелость это $E_{i}=\max(0,d_{i}-C_{i})$,
• опоздание это $T_{i}=\max(0,C_{i}-d_{i})$.

При планировании общими целевыми функциями являются $C_{\max },L_{\max },E_{\max },T_{\max },\sum C_{i},\sum L_{i},\sum E_{i},\sum T_{i}$ или взвешенная версия этих сумм, $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}$, где каждая работа имеет вес $w_{i}$. Вес представляет собой стоимость работы, приоритет и т. д.

В большом числе случаев задачи оптимизации этих функций являются NP-трудными .