On the NP-hardness of scheduling with time restrictions

作者：Zhang, An; Chen, Yong; Chen, Lin; Chen, Guangting^*

来源：Discrete Optimization, 2018, 28: 54-62.

DOI：10.1016/j.disopt.2017.12.001

• Single-processor scheduling
• Time restrictions
• NP-hardness

In a recent paper, Braun et al. (2014) have addressed a single-processor scheduling problem with time restrictions. Given a fixed integer B >= 2, there is a set of jobs to be processed by a single processor subject to the following B-constraint. For any real x, no unit time interval [x, x + 1) is allowed to intersect more than B jobs. The makespan minimization problem has been shown to be NP-hard when B is a part of input and left as an open question whether it remains NP-hard or not if B is fixed (Braun et al., 2014; 2016; Zhang, 2017). This paper contributes to answering this question that we prove the problem is NP-hard even when B = 2. A PTAS is also presented for any constant B >= 2.

• 出版日期2018-5
• 单位杭州电子科技大学; 台州学院