延迟 (排程)

排程理论（意大利语：Teoria della schedulazione）中，延迟时间（tardiness，或延迟）衡量某工作实际完成时间，与应完成时间（交期）相比，延误多少。^[1] 同理提早时间（earliness，或早交时间）衡量实际执行时间比交期提早多少。各项工作之间可能互相依赖，即某项工作的前提可能是另一工作已完成。工作亦受限于所需设备是否可用。

排程问题的例子包括制造业生产流程，以及资讯传输和处理的排程。^[2]

就制造业的库存管理而言，延迟与提早皆不理想。延迟导致工作积压，并要因误期违约赔偿顾客，损失商誉。相反，提早则会占用仓库，提高成本^[3]，阻碍资本流动。

数码信号处理亦会考虑个别流延迟的时长，即输出信号滞后于输入信号的时间。其平均值称为平均延迟，是表示开关速度的参数。

数学表述

设有多项工作，第${\displaystyle i}$项限期为${\displaystyle d_{i}}$，而完成时间${\displaystyle C_{i}}$，则对该工作而言，^[4]

• 差异时间（lateness）定义为${\displaystyle L_{i}=C_{i}-d_{i},}$
• 早交时间为${\displaystyle E_{i}=\max(0,d_{i}-C_{i}),}$
• 延迟时间为${\displaystyle T_{i}=\max(0,C_{i}-d_{i}).}$

排程问题中，常以其最大值${\displaystyle C_{\max },L_{\max },E_{\max },T_{\max }}$或总和${\displaystyle \sum C_{i},\sum L_{i},\sum E_{i},\sum T_{i}}$作为最小化的目标，又或者采用其加权版本${\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}}$，其中${\displaystyle w_{i}}$为各项工作的权重，代表工作的开销、优先程度等。

此类函数的最优化问题常为NP困难。^[5]

亦可考虑延迟时间的平均值，称为平均延迟（mean tardiness），公式为：

${\displaystyle {\overline {T}}={\frac {1}{n}}\sum _{i=1}^{n}T_{i},}$

其中${\displaystyle n}$为该批工作的数目。