具有截止时间和误时惩罚的任务安排问题可描述如下。 (1) 给定 n 个任务的集合 S={1,2,...,n}; (2) 完成任务i需要ti 时间,1≤i≤n; (3) 任务 i 的截止时间 di ,1≤i≤n,即要求任务 i 在时间 di 之前结束; (4) 任务 i 的误时惩罚 wi ,1≤i≤n,即任务 i 未在时间di 之前结束将招致 wi 的惩罚; 若按时完成则无惩罚。 任务安排问题要求确定 S 的一个时间表(最优时间表)使得总误时惩罚达到最小。 对于给定的 n 个任务,编程计算总误时惩罚最小的最优时间表。
