• 论文 •

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

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

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

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.