工时依赖于开工时间的单台机排序问题

此文考察工时依赖于开工时间的排序问题．文章证明：（１）即使准备时间完全相同，判断工时与开工时间相关的单台机排序问题是否有可行解也是ＮＰ完全的．（２）即使只存在两个不同的截止期，判断工时与开工时间相关的单台机排序问题是否有可行解仍然是ＮＰ完全的．（３）当所有工件有相同截止期时，问题是否有可行解可在多项式时间内判定．