We consider the following fundamental scheduling problem. The input consists of $n$ jobs to be scheduled on a set of machines of bounded capacities. Each job is associated with a release time, a due date, a processing time and demand for machine capacity. The goal is to schedule all of the jobs non-preemptively in their release-time-deadline windows, subject to machine capacity constraints, such that the total busy time of the machines is minimized. Our problem has important applications in power-aware scheduling, optical network design and unit commitment in power systems. Scheduling to minimize busy times is APX-hard already in the special case where all jobs have the same (unit) processing times and can be scheduled in a fixed time interval.Our main result is a $5$-approximation algorithm for general instances. We extend this result to obtain an algorithm with the same approximation ratio for the problem of scheduling moldable jobs, that requires also to determine, for each job, one of several processing-time vs. demand configurations. Better bounds and exact algorithms are derived for several special cases, including proper interval graphs, intervals forming a clique and laminar families of intervals.
展开▼
机译：我们考虑以下基本调度问题。输入包括要在一组有限容量的计算机上调度的$ n $个作业。每个作业都与发布时间，截止日期，处理时间和机器容量需求相关联。目标是根据机器容量限制，在其释放时间-截止日期窗口中非抢占地安排所有作业，以使机器的总繁忙时间最小化。我们的问题在电力感知调度，光网络设计和电力系统中的单元承诺中具有重要的应用。在所有情况下，所有工作都具有相同的（单位）处理时间并且可以在固定的时间间隔内进行调度的特殊情况下，计划将繁忙时间最小化已经很困难，我们的主要结果是在一般情况下采用$ 5 $的近似算法。我们扩展此结果以获得具有相同近似比率的算法，以解决可模制作业的调度问题，该算法还需要针对每个作业确定几种处理时间与需求配置中的一种。对于几种特殊情况，可以得出更好的边界和精确的算法，包括适当的间隔图，形成集团的间隔和层状间隔族。
展开▼
