Optimal algorithms and a PTAS for cost-aware scheduling

DOI10.1007/978-3-662-48054-0_18MaRDI QIDQ2946391zbMATH OpenOpenAlexWikidataFDO

Authors Lin Chen, Nicole Megow, Roman Rischke, José Verschae, L. 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

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

Recommendations

• Optimal algorithms for scheduling under time-of-use tariffs
• Dual techniques for scheduling on a machine with varying speed
• On scheduling with non-increasing time slot cost to minimize total weighted completion time
• Dual techniques for scheduling on a machine with varying speed
• scientific article; zbMATH DE number 437570

Cites work

• Algorithms for cost-aware scheduling
• Dual techniques for scheduling on a machine with varying speed
• On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming
• On the Performance of Smith’s Rule in Single-Machine Scheduling with Nonlinear Cost
• Preemptive scheduling with availability constraints to minimize total weighted completion times
• Scheduling with variable time slot costs
• Universal sequencing on an unreliable machine

Cited in

(16)

• On scheduling with non-increasing time slot cost to minimize total weighted completion time
• Resource cost aware scheduling
• How unsplittable-flow-covering helps scheduling with job-dependent cost functions
• Calibration scheduling with time slot cost
• Optimal algorithms for scheduling under time-of-use tariffs
• Designing PTASs for MIN-SUM scheduling problems
• Single machine batch scheduling with non-increasing time slot costs
• Algorithms for cost-aware scheduling
• Universal sequencing on an unreliable machine
• A primal-dual approximation algorithm for min-sum single-machine scheduling problems
• scientific article; zbMATH DE number 437570 (Why is no real title available?)
• Dual techniques for scheduling on a machine with varying speed
• scientific article; zbMATH DE number 7204483 (Why is no real title available?)
• Dual techniques for scheduling on a machine with varying speed
• A primal-dual approximation algorithm for Min-sum single-machine scheduling problems
• Real time scheduling with a budget: parametric-search is better than binary search

This page was built for publication: Optimal algorithms and a PTAS for cost-aware scheduling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946391)