Green Scheduling with Time-of-Use Tariffs and Machine States: Optimizing Energy Cost via Branch-and-Bound and Bin Packing Strategies
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908460102189056 |
|---|---|
| author | Benedikt, Ondřej Módos, István Novak, Antonin Hanzálek, Zdeněk |
| author_facet | Benedikt, Ondřej Módos, István Novak, Antonin Hanzálek, Zdeněk |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_10405 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Green Scheduling with Time-of-Use Tariffs and Machine States: Optimizing Energy Cost via Branch-and-Bound and Bin Packing Strategies Benedikt, Ondřej Módos, István Novak, Antonin Hanzálek, Zdeněk Optimization and Control 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. |
| title | Green Scheduling with Time-of-Use Tariffs and Machine States: Optimizing Energy Cost via Branch-and-Bound and Bin Packing Strategies |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2506.10405 |