Exact algorithms for energy-constrained scheduling on identical parallel machines

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. • We develop advanced bounds via column generation and metaheuristic based methods. • We introduce a new B&B with dynamic programming cuts and timetabling based pruning. • We present an exact algorithm using binary search with B&B, CP, and known methods. • We compare MILP and CP models for parallel machines with a single renewable resource. • We report superior computational results on two benchmark sets from the literature.