| 工时依赖于开工时间的单台机排序问题 |
| |
| 引用本文： | 杨启帆.工时依赖于开工时间的单台机排序问题[J].高校应用数学学报(A辑),1998,13(2):193-196. |
| |
| 作者姓名： | 杨启帆 |
| |
| 作者单位： | 浙江大学应用数学系 |
| |
| 摘 要： | 此文考察工时依赖于开工时间的排序问题．文章证明：(1)即使准奋时间完全相同，判断工时与开工时间相关的单台机排序问题是否有可行解也是NP完全的．(2)即使只存在两个不同的截止期，判断工时与开工时间相关的单台机排序问题是否有可行解仍然是NP完全的．(3)当所有工件有相同截止期时，问题是否有可行解可在多项式时间内判定．
|
| 关 键 词： | NP完全 准备时间 截止期 可行排序 |
SINGLE MACHINE SCHEDULING WITH TIME DEPENDENT EXECUTION TIMES |
| |
| Yang Qifan.SINGLE MACHINE SCHEDULING WITH TIME DEPENDENT EXECUTION TIMES[J].Applied Mathematics A Journal of Chinese Universities,1998,13(2):193-196. |
| |
| Authors: | Yang Qifan |
| |
| Abstract: | A new scheduling model is considered.In this paper,the execution time of a task depends on its starting time.The paper shows that (1) Even for a set of tasks with the same release time,the feasibility problem is NP complete.(2) Even the tasks have two distinct deadlines,the feasibility problem is NP complete.(3) When all tasks have the same release time and same deadline the feasibility problem is polynomially solvable. |
| |
| Keywords: | NP Complete Release Time Deadline Feasible Schedule |
| 本文献已被 CNKI 维普 等数据库收录！ |
