延遲 (排程)

排程理論（義大利語：Teoria della schedulazione）中，延遲時間（tardiness，或延遲）衡量某工作實際完成時間，與應完成時間（交期）相比，延誤多少。^[1] 同理提早時間（earliness，或早交時間）衡量實際執行時間比交期提早多少。各項工作之間可能互相依賴，即某項工作的前提可能是另一工作已完成。工作亦受限於所需設備是否可用。

排程問題的例子包括製造業生產流程，以及資訊傳輸和處理的排程。^[2]

就製造業的庫存管理（英语：inventory management）而言，延遲與提早皆不理想。延遲導致工作積壓，並要因誤期違約賠償顧客，損失商譽。相反，提早則會佔用倉庫，提高成本^[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}$ 為該批工作的數目。

參考文獻

1. 曾心珮; 林俊逸. 工件大小不一致單一批次機器之排程問題. 第15屆科技整合管理研討會: 1–13. 2012. 
2. Su, Sheng; Yu, Haijie. Minimizing tardiness in data aggregation scheduling with due date consideration for single-hop wireless sensor networks. Wireless Networks. 2015-05, 21 (4): 1259–1273. doi:10.1007/s11276-014-0853-4. 
3. Eren Akyol, Derya; Bayhan, G. Mirac. . The International Journal of Advanced Manufacturing Technology. 2008-05, 37 (5): 576–588 [2022-02-07]. （原始内容存档于2022-02-07）. 
4. 黃祥熙. (PDF). 國立屏東科技大學. [2022-02-07]. （原始内容 (PDF)存档于2022-02-07）. 
5. . University of Osnabrueck. [2022-02-07]. （原始内容存档于2022-04-10）.