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

DOI10.1007/S10107-014-0814-9zbMATH Open1327.90267OpenAlexW2067598904WikidataQ59404568 ScholiaQ59404568MaRDI QIDQ747774FDOQ747774

Authors: Akiyoshi Shioura, N. V. Shakhlevich, V. A. Strusevich 

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

Recommendations

• Handling scheduling problems with controllable parameters by methods of submodular optimization
• A submodular optimization approach to bicriteria scheduling problems with controllable processing times on parallel machines
• Application of submodular optimization to single machine scheduling with controllable processing times subject to release dates and deadlines
• SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES BY SUBMODULAR OPTIMIZATION
• Scheduling problems with controllable processing times and a common deadline to minimize maximum compression cost

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)

Cites Work

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

Cited In (13)

• Handling scheduling problems with controllable parameters by methods of submodular optimization
• A Review for Submodular Optimization on Machine Scheduling Problems
• Min-max controllable risk problems
• Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: a review of solution approaches
• SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES BY SUBMODULAR OPTIMIZATION
• Machine speed scaling by adapting methods for convex optimization with submodular constraints
• Min‐sum controllable risk problems with concave risk functions of the same value range
• Application of submodular optimization to single machine scheduling with controllable processing times subject to release dates and deadlines
• Scheduling problems with controllable processing times and a common deadline to minimize maximum compression cost
• A submodular optimization approach to bicriteria scheduling problems with controllable processing times on parallel machines
• Preemptive scheduling of parallel jobs of two sizes with controllable processing times
• Single machine resource allocation scheduling problems with deterioration effect and general positional effect
• On Submodular Search and Machine Scheduling

This page was built for publication: Decomposition algorithms for submodular optimization with applications to parallel machine scheduling with controllable processing times

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