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 -