Green Scheduling with Time-of-Use Tariffs and Machine States: Optimizing Energy Cost via Branch-and-Bound and Bin Packing Strategies

2025/06/12 by Benedikt, Ondřej, Módos, István, Novak, Antonin +1
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2506.10405

Abstract

This paper presents a branch-and-bound algorithm, enhanced with bin packing strategies, for scheduling under variable energy pricing and power-saving states. The proposed algorithm addresses the 1,TOU|states|TEC problem, which involves scheduling jobs to minimize total energy cost (TEC) while considering time-of-use (TOU) electricity prices and different machine states (e.g., processing, idle, off). Key innovations include instance pre-processing for rapid lower bound calculations, a novel branching scheme combined with initializations, a block-finding primal heuristic, and a tighter lower bound for jobs with non-coprime processing times. These enhancements result in an efficient algorithm capable of solving benchmark instances with real energy prices with 200 jobs more than 100 times faster than existing state-of-the-art methods.

Citations

• Job scheduling under Time-of-Use energy tariffs for sustainable manufacturing: a survey
• Optimal Algorithms for Scheduling under Time-of-Use Tariffs
• The Easiest Hard Problem: Number Partitioning

Related

• Exact and Heuristic Algorithms for Energy-Efficient Scheduling
• On incorporating variable consumption functions within energy-efficient parallel machine scheduling
• On Time-Sensitive Revenue Management and Energy Scheduling in Green Data Centers
• Optimal Scheduling of Flexible Power-to-X Technologies in the Day-ahead Electricity Market
• Multi-mode resource-constrained project scheduling problem with multiple shifts and dynamic energy prices