遅刻（スケジュール）

スケジュールでは、遅刻は特定の操作の実行が遅れる度合いを表し、早刻は予定時間より前に操作を終了する度合いを表します。操作は相互に依存し、操作を実行するための機器の可用性にも依存する場合があります。

典型的な例としては、製造業におけるジョブスケジューリングやデータ処理ネットワークにおけるデータ配信スケジューリングなどが挙げられます。^[1]

製造業の環境では、在庫管理では遅れと早さの両方が望ましくないと見なされます。遅れは、遅延に対する顧客への補償や信用の喪失などのバックログの問題を伴います。早さは、製造品目の保管費用^[2]を招き、資本を拘束します。

複数のジョブがある環境では、締め切りを、完了時間を とします。すると、ジョブ について${\displaystyle d_{i}}$${\displaystyle C_{i}}$${\displaystyle i}$${\displaystyle i}$

• 遅刻は、${\displaystyle L_{i}=C_{i}-d_{i}}$
• 早さは、${\displaystyle E_{i}=\max(0,d_{i}-C_{i})}$
• 遅刻は です。${\displaystyle T_{i}=\max(0,C_{i}-d_{i})}$

スケジューリングでは、一般的な目的関数はまたはこれらの合計の加重バージョンであり、すべてのジョブには重み が伴います。重みはジョブのコスト、優先度などを表します。 ${\displaystyle C_{\max},L_{\max},E_{\max},T_{\max},\sum C_{i},\sum L_{i},\sum E_{i},\sum 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}}$${\displaystyle w_{i}}$

多くの場合、これらの関数を最適化する問題はNP困難である。^[3]