Optimal Energy-Aware Scheduling of Heterogeneous Jobs with Monotonically Increasing Slot Costs

Lin Zhao, Hao Fu, Mu SuSymmetry 2025 · DOI

TL;DR

This paper tackles the challenge of efficiently scheduling diverse jobs on multiple machines where the cost of using later slots increases over time. They introduce a novel "monotonic machine assignment" framework that simplifies the problem by focusing only on "heavy" jobs, leading to a provably optimal and highly scalable O(nm²) algorithm. This work is crucial for optimizing energy consumption in systems like cloud data centers and embedded devices where such cost structures are common.

What Problem Does This Paper Address?

Modern computing and manufacturing systems are increasingly concerned with energy efficiency. A significant factor contributing to energy consumption is job scheduling, especially when jobs have different energy demands ("heterogeneous") and the cost of processing them increases with their position in the schedule ("monotonically increasing slot costs"). This latter phenomenon can arise from factors like hardware degradation, thermal effects, or increasing resource contention over time.

The core challenge is to assign a fixed sequence of jobs (meaning they can't be reordered arbitrarily) to multiple identical machines to minimize total energy cost. This is complicated by:

  • Heterogeneous Jobs: Some jobs are "heavy" (high energy cost) and others are "light" (low energy cost).
  • Monotonically Increasing Slot Costs: The cost of using the 1st slot on a machine is lower than the 2nd, which is lower than the 3rd, and so on.
  • Fixed Job Order: Jobs arrive and must be processed in a specific sequence, preventing simple reordering to optimize costs.

Existing scheduling models often assume homogeneous jobs, allow reordering, or don't account for this specific type of increasing slot cost, making them unsuitable for many real-world scenarios like streaming data processing or embedded real-time systems.

Methods

The authors propose a multi-pronged approach:

  1. Problem Formulation and Normalization: They first formalize the problem as an Integer Linear Program (ILP). A key insight is that the energy cost of light jobs is invariant across all feasible assignments. This allows them to simplify the objective function to solely focus on minimizing the cost associated with placing heavy jobs. This normalization is crucial for algorithmic development.
  2. Monotonic Machine Assignment: This is the core structural contribution. They define a "monotonic machine assignment" characterized by three properties:
  3. Job Number Monotonicity: Machines with lower indices should have at least as many jobs assigned as machines with higher indices at any point in the job sequence.
  4. Light Job Monotonicity: Light jobs are assigned to the earliest available machine.
  5. Heavy Job Monotonicity: Heavy jobs are assigned to machines in a non-decreasing order of machine indices.

    Crucially, they prove that any feasible assignment can be transformed into a monotonic one without increasing the total energy cost. This significantly reduces the search space for the optimal solution.

  6. Dynamic Programming (DP) Algorithm: Based on the monotonic assignment structure, they develop a DP algorithm. The state DP[i][h] represents the minimum cost of assigning the first i machines with a total of h heavy jobs. This algorithm achieves a time complexity of O(n²m²), where n is the number of slots per machine and m is the number of machines.

  7. Misalignment Elimination Algorithm: Recognizing the O(n²m²) complexity of DP might be too slow for large instances, they propose a more efficient iterative refinement algorithm. This algorithm identifies "misaligned assignments" (where a heavy job on machine i is placed after a light job on machine i+1, violating the monotonic structure) and resolves them by swapping jobs between adjacent machines. This process guarantees feasibility and non-increasing cost. This algorithm achieves a much better time complexity of O(nm²), making it highly scalable.

Datasets

Not discussed in the paper. The paper focuses on a theoretical model and algorithmic development, with experimental evaluation using randomly generated instances.

Key Insights and Ideas

  • Focusing on Heavy Jobs is Sufficient: The most significant insight is that by normalizing the problem, the optimization objective can be reduced to solely considering the placement of heavy jobs. This dramatically simplifies the problem without losing optimality.
  • Monotonicity as a Structural Constraint: The concept of "monotonic machine assignment" is a powerful way to impose structure on the problem. By proving that any optimal solution can be represented this way, they create a constrained search space that is amenable to efficient algorithms.
  • Local Refinement for Global Optimality: The misalignment elimination algorithm demonstrates that local adjustments (swapping jobs between adjacent machines) can iteratively lead to a globally optimal solution. This is a common theme in optimization, but its application here to energy-aware scheduling with specific constraints is novel.
  • Scalability through Structure: The O(nm²) algorithm is a significant improvement over the O(n²m²) DP, highlighting how understanding the underlying structure of a problem can lead to much more efficient solutions, especially for large-scale systems.

Key Results

  • Provable Optimality: Both the DP and the misalignment elimination algorithms are proven to find the globally optimal energy-aware schedule.
  • Improved Time Complexity: The misalignment elimination algorithm achieves a time complexity of O(nm²), which is significantly better than the O(n²m²) of the dynamic programming approach. This makes it practical for larger problem instances.
  • Experimental Validation: The experimental evaluation shows that the misalignment elimination algorithm is substantially faster and scales much better than the dynamic programming approach, especially as the number of machines (m) increases. For instance, with n=5 and H/N=0.3, the runtime for the misalignment elimination algorithm was orders of magnitude lower than DP for larger m.

Limitations and Future Work

  • Fixed Job Sequence: The current model assumes jobs arrive in a fixed, predetermined order. Real-world systems might have dynamic job arrivals.
  • Deterministic Slot Costs: The slot costs are assumed to be fixed and known. In reality, these costs might be stochastic or influenced by dynamic system conditions.
  • Identical Machines: The model assumes identical machines. Heterogeneous machines with different processing capabilities and energy profiles would add further complexity.

Future research directions suggested by the authors include:

  • Online Extensions: Developing algorithms for dynamically arriving jobs.
  • Hybrid Models: Integrating structure-aware optimization with adaptive learning mechanisms.
  • Heterogeneous Machines: Extending the model to handle machines with varying characteristics.
  • Multi-Objective Optimization: Balancing energy efficiency with other objectives like latency and fairness.
  • Stochastic Models: Incorporating uncertainty in job characteristics and energy estimations.

Summary updated

BibTeX
@article{zhao2025optimal,
  author = {Lin Zhao and Hao Fu and Mu Su},
  title = {{Optimal Energy-Aware Scheduling of Heterogeneous Jobs with Monotonically Increasing Slot Costs}},
  journal = {Symmetry},
  year = {2025},
  doi = {10.3390/sym17070980},
}
Figure