TY - JOUR

T1 - On the NP-hardness of scheduling with time restrictions

AU - Zhang, An

AU - Chen, Yong

AU - Chen, Lin

AU - Chen, Guangting

N1 - Funding Information:
The first author is supported by the National Natural Science Foundation of China ( 11771114 ) and the Zhejiang Provincial Natural Science Foundation of China ( LY16A010015 ). The second author is supported by the National Natural Science Foundation of China ( 11401149 ). The fourth author is supported by the National Natural Science Foundation of China ( 11571252 ). We are grateful to two anonymous referees for their careful reading of the manuscript and constructive comments.
Publisher Copyright:
© 2017 Elsevier B.V.

PY - 2018/5

Y1 - 2018/5

N2 - 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.

AB - 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.

KW - NP-hardness

KW - Single-processor scheduling

KW - Time restrictions

UR - http://www.scopus.com/inward/record.url?scp=85039841287&partnerID=8YFLogxK

U2 - 10.1016/j.disopt.2017.12.001

DO - 10.1016/j.disopt.2017.12.001

M3 - Article

AN - SCOPUS:85039841287

VL - 28

SP - 54

EP - 62

JO - Discrete Optimization

JF - Discrete Optimization

SN - 1572-5286

ER -