Optimal Algorithms and a PTAS for Cost-Aware Scheduling

DOI10.1007/978-3-662-48054-0_18zbMath1465.90027OpenAlexW2141097584WikidataQ57399732 ScholiaQ57399732MaRDI QIDQ2946391

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

Publication date: 16 September 2015

Published in: Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/hal-01249098/file/ChenMRSV-MFCS15.pdf

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Related Items (4)

Calibration scheduling with time slot cost ⋮ Single machine batch scheduling with non-increasing time slot costs ⋮ On scheduling with non-increasing time slot cost to minimize total weighted completion time ⋮ Optimal algorithms for scheduling under time-of-use tariffs

Cites Work

• Preemptive scheduling with availability constraints to minimize total weighted completion times
• Algorithms for Cost-Aware Scheduling
• On the Performance of Smith’s Rule in Single-Machine Scheduling with Nonlinear Cost
• Universal Sequencing on an Unreliable Machine
• On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming
• Scheduling with variable time slot costs
• Dual Techniques for Scheduling on a Machine with Varying Speed

This page was built for publication: Optimal Algorithms and a PTAS for Cost-Aware Scheduling