中，延遲時間（，或延遲）衡量某工作實際完成時間，與應完成時間（交期）相比，延誤多少。 同理提早時間（，或早交時間）衡量實際執行時間比交期提早多少。各項工作之間可能互相依賴，即某項工作的前提可能是另一工作已完成。工作亦受限於所需設備是否可用。
排程問題的例子包括製造業生產流程，以及資訊傳輸和處理的排程。
就製造業的而言，延遲與提早皆不理想。延遲導致工作積壓，並要因誤期違約賠償顧客，損失商譽。相反，提早則會佔用倉庫，提高成本，阻礙資本流動。
數碼訊號處理亦會考慮个别流延迟的時長，即输出信号滞后于输入信号的时间。其平均值稱為平均延遲，是表示开关速度的参数。
數學表述
設有多項工作，第i項限期為d_i，而完成時間C_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_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，其中w_i為各項工作的權重，代表工作的開銷、優先程度等。
此類函數的最優化問題常為NP困难。
亦可考慮延遲時間的平均值，稱為平均延遲（），公式為：
:\overline T = \frac{1}{n} \sum_{i = 1}^n T_i,
其中n為該批工作的數目。
參考文獻
评论 (0)