有区间约束单机延误排序问题

Single Machine Tardy Scheduling Problem for Intervalsconstrained

研究一类推广的从准备时间ｒｉ到交工期ｄｉ的多重ｒ／ｄ区间排序问题——有区间约束单机延误排序问题。就该问题的一般情形而言证明了它是ＮＰ—困难的，对问题的特殊情形证明了它是多项式时间可解的。

his paper studies generated single machine tardy scheduling problem with mutiple release time/deadline intervals(r/d),namely,from ready time to due date.Generally speaking,the problem is proved to be NPhard in the strong scene,and particular problem is solvable with polynomial time.