• 论文 • 上一篇    下一篇

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

张玉忠1,苗翠霞2   

  1. 1.曲阜师范大学管理学院, 日照 276826; 2.曲阜师范大学数学科学学院, 曲阜 273165
  • 出版日期:2015-06-25 发布日期:2015-07-14

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

  1. 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- 难的.

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)主题分类: 

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


摘要