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

Abstract

Energy-aware scheduling plays a critical role in modern computing and manufacturing systems, where energy consumption often increases with job execution order or resource usage intensity. This study investigates a scheduling problem in which a sequence of heterogeneous jobs—classified as either heavy or light—must be assigned to multiple identical machines with monotonically increasing slot costs. While the machines are structurally symmetric, the fixed job order and cost asymmetry introduce significant challenges for optimal job allocation. We formulate the problem as an integer linear program and simplify the objective by isolating the cumulative cost of heavy jobs, thereby reducing the search for optimality to a position-based assignment problem. To address this challenge, we propose a structured assignment model termed monotonic machine assignment, which enforces index-based job distribution rules and restores a form of functional symmetry across machines. We prove that any feasible assignment can be transformed into a monotonic one without increasing the total energy cost, ensuring that the global optimum lies within this reduced search space. Building on this framework, we first present a general dynamic programming algorithm with complexity $O\left(n^2{m}^2\right)$. More importantly, by introducing a structural correction scheme based on misaligned assignments, we design an iterative refinement algorithm that achieves global optimality in only $O\left(n{m}^2\right)$ time, offering significant scalability for large instances. Our results contribute both structural insight and practical methods for optimal, position-sensitive, energy-aware scheduling, with potential applications in embedded systems, pipelined computation, and real-time operations.