延迟 (排程)

在调度中，迟到是对执行某些操作的延迟的度量，早到是对在规定时间之前完成操作的度量。 这些操作可能相互依赖，并取决于执行它们的设备的可用性。

典型的例子包括制造中的作业调度和数据处理网络中的数据交付调度。

在制造环境中，库存管理认为迟到和早到都是不可取的。 迟到涉及积压问题，例如客户对延误和商誉损失的赔偿。 提前会产生存储制成品的费用并占用资金。

在有多个作业的环境中，让截止日期为 d i {displaystyle d_{i}} ，完成时间为作业 i {displaystyle i} 的 C i {displaystyle C_{i}} 。 然后对于工作 i {displaystyle i}

• 迟到是 L i = C i − d i {displaystyle L_{i}=C_{i}-d_{i}} ,
• 早熟度是 E i = max ( 0 , d i − C i ) {displaystyle E_{i}=max(0,d_{i}-C_{i})} ,
• 迟到是 T i = max ( 0 , C i − d i ) {displaystyle T_{i}=max(0,C_{i}-d_{i})} 。

在调度中常见的目标函数是 C max , L max , E max , T max , ∑ C i , ∑ L i , ∑ E i , ∑ T i {displaystyle C_{max },L_{max } ,E_{max },T_{max },sum C_{i},sum L_{i},sum E_{i},sum T_{i}} 或加权版本 这些总和中， w i C max , w i L max , w i E max , w i T max , ∑ w i C i , ∑ w i L i , ∑ w i E i , ∑ w i 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}} ，其中每个作业都有一个权重 w i {displaystyle w_{ 一世}} 。 权重是作业成本、优先级等的表示。

在大量情况下，优化这些函数的问题是 NP 难的。