查看“︁延遲 (排程)”︁的源代码

{{Refimprove|time=2022-02-08T04:57:10+00:00}}
{{link-it|排程理論|Teoria della schedulazione}}中，'''延遲時間'''（{{lang|en|tardiness}}，或'''延遲'''）衡量某工作實際完成時間，與應完成時間（交期）相比，延誤多少。<ref>{{cite conference|author1 = 曾心珮|author2 = 林俊逸|title = 工件大小不一致單一批次機器之排程問題|conference = 第15屆科技整合管理研討會|year = 2012|pages = 1–13}}</ref> 同理'''提早時間'''（{{lang|en|earliness}}，或'''早交時間'''）衡量實際執行時間比交期提早多少。各項工作之間可能互相依賴，即某項工作的前提可能是另一工作已完成。工作亦受限於所需設備是否可用。

排程問題的例子包括製造業生產流程，以及資訊傳輸和處理的[[排程]]。<ref>{{cite journal |first1 = Sheng|last1 = Su|first2 = Haijie|last2 = Yu |url = http://dl.acm.org/citation.cfm?id=2767221|title =  Minimizing tardiness in data aggregation scheduling with due date consideration for single-hop wireless sensor networks| journal = Wireless Networks| volume = 21| issue= 4|date = 2015-05|pages =  1259–1273|doi = 10.1007/s11276-014-0853-4}}</ref>

就製造業的{{link-en|庫存管理|inventory management}}而言，延遲與提早皆不理想。延遲導致工作積壓，並要因誤期違約賠償顧客，損失商譽。相反，提早則會佔用倉庫，提高成本<ref>{{cite journal|first1 = Derya|last1 = Eren Akyol|first2 = G. Mirac|last2 = Bayhan|url = https://link.springer.com/article/10.1007%2Fs00170-007-0993-0|title = Multi-machine earliness and tardiness scheduling problem: an interconnected neural network approach|journal = The International Journal of Advanced Manufacturing Technology|date = 2008-05|volume = 37|issue = 5|pages = 576–588|access-date = 2022-02-07|archive-date = 2022-02-07|archive-url = https://web.archive.org/web/20220207152412/https://link.springer.com/article/10.1007%2Fs00170-007-0993-0}}</ref>，阻礙資本流動。

[[數碼訊號處理]]亦會考慮[[个别流]]延迟的時長，即[[输出信号]]滞后于[[输入信号]]的时间。其平均值稱為平均延遲，是表示[[开关速度]]的[[參數 (數學)|参数]]。
== 數學表述 ==

設有多項工作，第<math>i</math>項限期為<math>d_i</math>，而完成時間<math>C_i</math>，則對該工作而言，<ref>{{cite web|title = 排程理論 概述|url = http://hhuang.npust.edu.tw/ezfiles/146/1146/img/1544/943497907.pdf|author = 黃祥熙|website = 國立屏東科技大學|access-date = 2022-02-07|archive-date = 2022-02-07|archive-url = https://web.archive.org/web/20220207152120/http://hhuang.npust.edu.tw/ezfiles/146/1146/img/1544/943497907.pdf}}</ref>

* 差異時間（{{lang|en|lateness}}）定義為<math>L_i=C_i-d_i,</math>
* 早交時間為<math>E_i = \max(0, d_i-C_i),</math>
* 延遲時間為<math>T_i = \max(0, C_i-d_i).</math>

排程問題中，常以其最大值<math>C_\max, L_\max, E_\max, T_\max</math>或總和<math> \sum C_i, \sum L_i, \sum E_i, \sum T_i</math>作為最小化的[[损失函数|目標]]，又或者採用其加權版本<math>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</math>，其中<math>w_i</math>為各項工作的權重，代表工作的開銷、優先程度等。

此類函數的[[最優化問題]]常為[[NP困难]]。<ref>{{cite web|url = http://www2.informatik.uni-osnabrueck.de/knust/class/|title = Complexity results for scheduling problems|website = [[奥斯纳布吕克大学|University of Osnabrueck]]|access-date = 2022-02-07|archive-date = 2022-04-10|archive-url = https://web.archive.org/web/20220410003005/http://www2.informatik.uni-osnabrueck.de/knust/class/}}</ref>

亦可考慮延遲時間的[[平均值]]，稱為平均延遲（{{lang|en|mean tardiness}}），公式為：
:<math>\overline T = \frac{1}{n} \sum_{i = 1}^n T_i,</math>
其中<math>n</math>為該批工作的數目。

== 參考文獻 ==
{{reflist}}
{{调度问题}}
[[Category:时间管理]]
[[Category:排程]]
[[Category:理论计算机科学]]