Exact algorithms for energy-constrained scheduling on identical parallel machines
Abstract
We address the problem of scheduling non-preemptive jobs on identical parallel machines under a single renewable resource constraint, with the objective of minimizing the makespan. This setting captures relevant applications in energy-aware production planning, where energy usage must not exceed a fixed limit at any time. We introduce two mathematical formulations and propose an exact algorithm that integrates a branch-and-bound, advanced bounding techniques, and a constraint programming model. Extensive computational experiments on two benchmark sets from the literature show that the proposed approach outperforms existing exact methods, solving more instances to optimality and achieving consistently smaller optimality gaps within limited computation time.
Fields of Study & Subjects
Scheduling and Optimization Algorithms
Distributed and Parallel Computing Systems
Optimization and Search Problems
Publication details
- Journal / source
- Computers & Operations Research
- Publisher
- Elsevier BV
- Volume
- 191
- Pages
- 107440–107440
- Publication date
- 26 February 2026
- Language
- EN