张玉忠1,苗翠霞2
张玉忠,苗翠霞. 机器有使用限制的混合恶化排序问题的复杂性[J]. 系统科学与数学, 2015, 35(6): 685-694.
ZHANG Yuzhong,MIAO Cuixia. THE COMPLEXITY OF SCHEDULING WITH MIXED DETERIORATION AND AVAILABILITY CONSTRAINTS[J]. Journal of Systems Science and Mathematical Sciences, 2015, 35(6): 685-694.
ZHANG Yuzhong1 , MIAO Cuixia2
考虑了机器具有使用限制的混合恶化排序问题. 其中部分工件的加工时间是固定常数, 另一部分的是其开工时间的简单线性函数, 工件是不可中断的. 文章目标是极小化最大完工时间. 对于单机问题, 证明了问题是一般意义下的NP-难的, 给出了一个$\frac{4}{3}$-近似算法, 并证明了算法界是紧的. 对于平行机问题, 证明了问题是强NP- 难的.
MR(2010)主题分类:
分享此文:
[1] | 姜春艳,李改弟. 软容量约束的动态设施选址问题的近似算法[J]. 系统科学与数学, 2012, 32(4): 476-484. |
[2] | 陈荣军,唐国春. 同类机下的供应链排序及转包策略*[J]. 系统科学与数学, 2012, 32(1): 53-61. |
[3] | 陈荣军;唐国春. 平行机的供应链排序[J]. 系统科学与数学, 2010, 30(2): 274-282. |
阅读次数 | ||||||
全文 |
|
|||||
摘要 |
|
|||||