延遲 (排程)

排程理論中,工作比預定遲多少

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

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

就製造業的庫存管理英語inventory management而言,延遲與提早皆不理想。延遲導致工作積壓,並要因誤期違約賠償顧客,損失商譽。相反,提早則會佔用倉庫,提高成本[3],阻礙資本流動。

數位訊號處理亦會考慮個別流延遲的時長,即輸出信號滯後於輸入信號的時間。其平均值稱為平均延遲,是表示開關速度參數

數學表述

編輯

設有多項工作,第 項限期為 ,而完成時間 ,則對該工作而言,[4]

  • 差異時間(lateness)定義為 
  • 早交時間為 
  • 延遲時間為 

排程問題中,常以其最大值 或總和 作為最小化的目標,又或者採用其加權版本 ,其中 為各項工作的權重,代表工作的開銷、優先程度等。

此類函數的最優化問題常為NP困難[5]

亦可考慮延遲時間的平均值,稱為平均延遲(mean tardiness),公式為:

 

其中 為該批工作的數目。

參考文獻

編輯
  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. Multi-machine earliness and tardiness scheduling problem: an interconnected neural network approach. 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. ^ Complexity results for scheduling problems. University of Osnabrueck. [2022-02-07]. (原始內容存檔於2022-04-10).