Fast Divide-and-Conquer Algorithms for Preemptive Scheduling Problems with Controllable Processing Times – A Polymatroid Optimization Approach

DOI10.1007/978-3-540-87744-8_63zbMath1158.90355OpenAlexW1581923154MaRDI QIDQ3541133

Akiyoshi Shioura, Natalia V. Shakhlevich, Vitaly A. Strusevich

Publication date: 25 November 2008

Published in: Algorithms - ESA 2008 (Search for Journal in Brave)

Full work available at URL: http://eprints.whiterose.ac.uk/5397/1/shakhlevitchn1.pdf

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Related Items

Application of Submodular Optimization to Single Machine Scheduling with Controllable Processing Times Subject to Release Dates and Deadlines, Decomposition algorithms for submodular optimization with applications to parallel machine scheduling with controllable processing times

Cites Work

• Pre-emptive scheduling problems with controllable processing times
• Minimizing the number of tardy job units under release time constraints
• Preemptive scheduling on uniform parallel machines with controllable job processing times
• Single machine scheduling subject to deadlines and resource dependent processing times
• Minimizing the weighted number of tardy task units
• A bicriterion approach to preemptive scheduling of parallel machines with controllable job processing times
• Submodular functions and optimization.
• Scheduling with Deadlines and Loss Functions
• Algorithms for Scheduling Imprecise Computations with Timing Constraints
• Preemptive Scheduling of Uniform Machines by Ordinary Network Flow Techniques
• Preemptive Scheduling with Due Dates
• Scheduling Independent Tasks with Due Times on a Uniform Processor System
• Preemptive Scheduling of Uniform Processor Systems
• Improved Algorithms for Bipartite Network Flow
• Some simple scheduling algorithms
• A Fast Parametric Maximum Flow Algorithm and Applications
• Fast Algorithms for Parametric Scheduling Come From Extensions to Parametric Maximum Flow