延迟 (排程)

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

排程理论意大利语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).