Recursive Decomposition for Energy Efficient Scheduling

This direction is no longer present in the current build. Its last version stays readable and citable here.

Version 1 of 116 papers22 conceptsfrozen 2026-10-04

In modern computing, from mobile devices to massive data centers, the goal is rarely just to finish a task as fast as possible. Instead, the challenge is to finish a set of tasks by their respective deadlines while consuming the minimum amount of energy. This "speed scaling" problem is difficult because every decision—how fast to run a processor at time $t$—is coupled with every other decision across the entire timeline.

However, a recurring insight across several decades of research is that these complex, global optimization problems possess a hidden recursive structure. By identifying specific "anchor" jobs or "busy periods," researchers have shown that we can decompose a continuous scheduling horizon into independent sub-problems, leading to efficient polynomial-time algorithms.

The Least Urgent Job as a Structural Anchor

The most influential breakthrough in this area involves identifying the "least urgent" task—the job with the latest possible deadline. In Polynomial Time Algorithms for Minimum Energy Scheduling, Philippe Baptiste, Christoph Dürr, and Marek Chrobák demonstrated that this job acts as a natural divider.

The intuition is as follows: if you know exactly when the least urgent job is executed, that execution window splits all other jobs into two sets—those that must be completed before it and those that must be completed after it. Because the anchor job is the least urgent, it doesn't "squeeze" the other jobs in a way that creates new dependencies between the "before" and "after" sets.

This "inversion trick" allows a complex scheduling problem to be solved via dynamic programming. By iterating through all possible execution windows for this anchor job, the algorithm recursively solves the resulting independent sub-problems. This approach turned a long-standing open problem into a solvable $O(n^4)$ or $O(n^5)$ algorithm, as detailed in their later work, Polynomial-time algorithms for minimum energy scheduling.

Partitioning via Busy Periods

A complementary perspective focuses not on a single job, but on "busy periods"—intervals where the processor is active without any idle gaps. In Preemptive Scheduling of Equal-Length Jobs to Maximize Weighted Throughput, Wojciech Jawor and Nodari Vakhania joined the previous authors to show that optimal schedules naturally cluster into these blocks.

The boundary of a busy period is a moment where the machine has completely cleared its current workload. These "structural split points" are powerful because they represent a total reset of the system state. Nicole Megow and Leen Stougie applied this to Scheduling under Time-of-Use Tariffs, using potential functions to detect these points and decompose the scheduling horizon into segments that can be optimized independently.

This concept is particularly useful in networking. Lei Miao and Jianfeng Mao showed in Optimal Energy-Efficient Downlink Transmission Scheduling that wireless transmissions can be partitioned into these contiguous active blocks. By solving each busy period as a standalone optimization, they reduced the computational complexity of maintaining real-time deadlines in battery-operated nodes.

Identifying Critical Bottlenecks

In parallel processing environments, the decomposition is often driven by "critical jobs"—the tasks most constrained by their deadlines. Eric Angel and Dimitrios Letsios developed the BAL algorithm in Speed Scaling on Parallel Processors with Migration.

Instead of looking for a temporal split, they look for a "bottleneck" speed. They identify the jobs that must run at a certain minimum speed to meet their deadlines. Once these critical jobs are assigned their optimal speeds, the remaining "slack" in the schedule can be distributed among less constrained tasks. This iterative process reduces a complex convex optimization problem to a series of simpler maximum flow computations.

Handling Dependencies and Non-Preemption

The strategy of recursive decomposition even extends to more rigid constraints, such as precedence (where one job must finish before another starts) or non-preemption (where a job cannot be interrupted).

Across all these facets, the core intuition remains the same: the global complexity of energy-efficient scheduling is an illusion created by overlapping constraints. By finding the right structural "seam"—whether it is the least urgent job, a busy period boundary, or a critical bottleneck—we can rip the problem into smaller pieces and solve it optimally.

Papers in this version

History & citationVersion 1 · 2026-10-04

No longer present in the current build · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_recursive_decomposition_for_energy_effic_843684a1,
  title = {Recursive Decomposition for Energy Efficient Scheduling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/recursive-decomposition-for-energy-efficient-scheduling/rdr_843684a1d41f49e3a0a211e520bc5f74},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_recursive_decomposition_for_energy_effic_843684a1_v1,
  title = {Recursive Decomposition for Energy Efficient Scheduling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/recursive-decomposition-for-energy-efficient-scheduling/rdr_843684a1d41f49e3a0a211e520bc5f74/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}