NP-completeness of the Active Time Scheduling Problem
NP-completeness of the Active Time Scheduling Problem
复制标题
活动时间调度问题的 NP 完备性
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Manish Purohit
中科院分区：
文献类型：
--
作者：
Sagnika Saha;Manish Purohit
In this paper, we study the active time scheduling problem. We are given n jobs with integral processing times each of which has an integral release time and deadline. The goal is to schedule all the jobs on a machine that can work on b jobs simultaneously, and the objective is to minimize the number of time slots for which the machine is active. The active time scheduling model was introduced by Chang et al. in the context of energy-efficient scheduling. Surprisingly, despite the development of a number of constant factor approximation algorithms for the problem, the complexity of this fundamental problem had remained open. In this paper, we resolve this open problem and show that the active time scheduling problem is indeed NP-complete.
