3-11任务时间表问题 算法分析

给定一个单位时间任务的有限集S。关于S的一个时间表用于描述S中单位时间任务的执行次序。时间表中第1个任务从时间0开始执行直至时间1结束，第2个任务从时间1开始执行至时间2结束，…，第n个任务从时间n-1开始执行直至时间n结束。 具有截止时间和误时惩罚的单位时间任务时间表问题可描述如下。 (1) n个单位时间任务的集合S={1,2,…,n}； (2) 任务i的截止时间di ,1≤i≤n,1≤di≤n，即要求任务i在时间di之前结束； (3) 任务i的误时惩罚wi,1≤i≤n,即任务i未在时间di之前结束将招致的wi惩罚；若按时完成则无惩罚。 任务时间表问题要求确定S的一个时间表（最优时间表）使得总误时惩罚达到最小。 输入 具有截止时间和误时惩罚的单位时间任务时间表