Optimal algorithms for scheduling under time-of-use tariffs

DOI10.1007/s10479-021-04059-3zbMath1476.90110arXiv1811.12657OpenAlexW3153094519MaRDI QIDQ2241552

José Verschae, Roman Rischke, Nicole Megow, Lin Chen, Leen Stougie

Publication date: 9 November 2021

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1811.12657

zbMATH Keywords

schedulingdynamic programmingmakespantotal weighted completion timepolynomial-time approximation scheme (PTAS)time-of-use tariffs

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39) Approximation algorithms (68W25)

Related Items (4)

Exact and heuristic solution approaches for energy-efficient identical parallel machine scheduling with time-of-use costs ⋮ Time-of-use scheduling problem with equal-length jobs ⋮ Job scheduling under time-of-use energy tariffs for sustainable manufacturing: a survey ⋮ Speed-robust scheduling: sand, bricks, and rocks

Cites Work

• Scheduling on a single machine under time-of-use electricity tariffs
• Approximability of single machine scheduling with fixed jobs to minimize total completion time
• How unsplittable-flow-covering helps scheduling with job-dependent cost functions
• Scheduling with time-of-use costs
• Preemptive scheduling with availability constraints to minimize total weighted completion times
• Algorithms for Cost-Aware Scheduling
• Universal Sequencing on an Unreliable Machine
• Optimal Algorithms and a PTAS for Cost-Aware Scheduling
• A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems
• Dual Techniques for Scheduling on a Machine with Varying Speed
• On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler
• On the Performance of Smith’s Rule in Single-Machine Scheduling with Nonlinear Cost
• The Geometry of Scheduling
• Scheduling with variable time slot costs
• A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems

This page was built for publication: Optimal algorithms for scheduling under time-of-use tariffs