机器有使用限制的混合恶化排序问题的复杂性

doi:10.12341/jssms12589

系统科学与数学 ›› 2015, Vol. 35 ›› Issue (6): 685-694.DOI: 10.12341/jssms12589

机器有使用限制的混合恶化排序问题的复杂性

张玉忠¹，苗翠霞²

1.曲阜师范大学管理学院, 日照 276826; 2.曲阜师范大学数学科学学院, 曲阜 273165

出版日期:2015-06-25 发布日期:2015-07-14

PDF ( 317 ) 引用

张玉忠，苗翠霞. 机器有使用限制的混合恶化排序问题的复杂性[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.

THE COMPLEXITY OF SCHEDULING WITH MIXED DETERIORATION AND AVAILABILITY CONSTRAINTS

ZHANG Yuzhong¹ , MIAO Cuixia²

1.School of Management, Qufu Normal University, Rizhao 276826; 2.School of Mathematical Sciences, Qufu Normal University, Qufu 273165

Online:2015-06-25 Published:2015-07-14

考虑了机器具有使用限制的混合恶化排序问题. 其中部分工件的加工时间是固定常数, 另一部分的是其开工时间的简单线性函数, 工件是不可中断的. 文章目标是极小化最大完工时间. 对于单机问题, 证明了问题是一般意义下的NP-难的, 给出了一个$\frac{4}{3}$-近似算法, 并证明了算法界是紧的. 对于平行机问题, 证明了问题是强NP- 难的.

关键词： 混合恶化, 使用限制, NP-难, 近似算法.

In this paper, we consider the scheduling problem in which the machines have availability constraints and the processing times of some jobs are constant, while others are simple linear increasing functions of their starting times. The objective is to minimize the makespan for non-resumable jobs. For the single-machine issue, we show that this problem is NP-hard in the ordinary sense, provide a $\frac{4}{3}$-approximation algorithm and show that the bound is tight. For the parallel-machine issue, we show that this problem is NP-hard in the strong sense.

MR(2010)主题分类:

90B35

分享此文:

[1]	姜春艳，李改弟. 软容量约束的动态设施选址问题的近似算法[J]. 系统科学与数学, 2012, 32(4): 476-484.
[2]	陈荣军，唐国春. 同类机下的供应链排序及转包策略*[J]. 系统科学与数学, 2012, 32(1): 53-61.
[3]	陈荣军;唐国春. 平行机的供应链排序[J]. 系统科学与数学, 2010, 30(2): 274-282.

阅读次数

全文

摘要