Machine Speed Scaling by Adapting Methods for Convex Optimization with Submodular Constraints

DOI10.1287/ijoc.2017.0758zbMath1446.90084OpenAlexW2604670394WikidataQ59887103 ScholiaQ59887103MaRDI QIDQ5131701

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

Publication date: 9 November 2020

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/ijoc.2017.0758

zbMATH Keywords

computational complexitynonlinearanalysis of algorithmsprogrammingproduction-scheduling: multiple machinesproduction-scheduling: single machine

Mathematics Subject Classification ID

Convex programming (90C25) Deterministic scheduling theory in operations research (90B35)

Related Items

On a Reduction for a Class of Resource Allocation Problems, Unrelated parallel machine scheduling problem with special controllable processing times and setups, Approximation algorithms for energy-efficient scheduling of parallel jobs, A Review for Submodular Optimization on Machine Scheduling Problems, Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: a review of solution approaches

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Speed scaling on parallel processors
• Decomposition algorithms for submodular optimization with applications to parallel machine scheduling with controllable processing times
• Energy optimal schedules for jobs with multiple active intervals
• Pre-emptive scheduling problems with controllable processing times
• A survey of results for sequencing 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
• Two algorithms for maximizing a separable concave function over a polymatroid feasible region
• Energy-efficient scheduling and routing via randomized rounding
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• About strongly polynomial time algorithms for quadratic optimization over submodular constraints
• Equivalence of convex minimization problems over base polytopes
• Green scheduling, flows and matchings
• On multi-processor speed scaling with migration
• A survey of scheduling with controllable processing times
• Submodular functions and optimization.
• Scheduling with Deadlines and Loss Functions
• Scheduling on Power-Heterogeneous Processors
• Application of Submodular Optimization to Single Machine Scheduling with Controllable Processing Times Subject to Release Dates and Deadlines
• Speed Scaling Problems with Memory/Cache Consideration
• Algorithms for Scheduling Imprecise Computations with Timing Constraints
• Scalably Scheduling Power-Heterogeneous Processors
• SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES BY SUBMODULAR OPTIMIZATION
• A Generalized Uniform Processor System
• NOTE ON THE UNIVERSAL BASES OF A PAIR OF POLYMATROIDS
• Lexicographically Optimal Base of a Polymatroid with Respect to a Weight Vector
• Optimal flows in networks with multiple sources and sinks
• Some simple scheduling algorithms
• Speed Scaling on Parallel Processors with Migration
• A Fast Parametric Maximum Flow Algorithm and Applications
• Fast Algorithms for Parametric Scheduling Come From Extensions to Parametric Maximum Flow
• A Submodular Optimization Approach to Bicriteria Scheduling Problems with Controllable Processing Times on Parallel Machines