Decomposition algorithms for submodular optimization with applications to parallel machine scheduling with controllable processing times

DOI10.1007/s10107-014-0814-9zbMath1327.90267OpenAlexW2067598904WikidataQ59404568 ScholiaQ59404568MaRDI QIDQ747774

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

Publication date: 19 October 2015

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-014-0814-9

zbMATH Keywords

decompositionparallel machine schedulingcontrollable processing timessubmodular optimization

Mathematics Subject Classification ID

Linear programming (90C05) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Related Items

Scheduling problems with controllable processing times and a common deadline to minimize maximum compression cost, Min‐sum controllable risk problems with concave risk functions of the same value range, Machine Speed Scaling by Adapting Methods for Convex Optimization with Submodular Constraints, A Review for Submodular Optimization on Machine Scheduling Problems, Single machine resource allocation scheduling problems with deterioration effect and general positional effect, Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: a review of solution approaches, Min-max controllable risk problems, Application of Submodular Optimization to Single Machine Scheduling with Controllable Processing Times Subject to Release Dates and Deadlines

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pre-emptive scheduling problems with controllable processing times
• A survey of results for sequencing problems with controllable processing times
• Preemptive scheduling on uniform parallel machines with controllable job processing times
• Two algorithms for maximizing a separable concave function over a polymatroid feasible region
• Single machine scheduling subject to deadlines and resource dependent processing times
• Scheduling jobs to minimize total cost
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Approximation schemes for parallel machine scheduling problems with controllable processing times
• A bicriterion approach to preemptive scheduling of parallel machines with controllable job processing times
• A survey of scheduling with controllable processing times
• Submodular functions and optimization.
• Scheduling with Deadlines and Loss Functions
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• Fast Divide-and-Conquer Algorithms for Preemptive Scheduling Problems with Controllable Processing Times – A Polymatroid Optimization Approach
• SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES BY SUBMODULAR OPTIMIZATION
• Preemptive Scheduling with Due Dates
• Lexicographically Optimal Base of a Polymatroid with Respect to a Weight Vector
• Scheduling Independent Tasks with Due Times on a Uniform Processor System
• Preemptive Scheduling of Uniform Processor Systems
• 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