Application of submodular optimization to single machine scheduling with controllable processing times subject to release dates and deadlines

DOI10.1287/IJOC.2015.0660zbMATH Open1338.90182DBLPjournals/informs/ShiouraSS16OpenAlexW2270422555WikidataQ57950404 ScholiaQ57950404MaRDI QIDQ2806872FDOQ2806872

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

Publication date: 19 May 2016

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

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

Recommendations

• Handling scheduling problems with controllable parameters by methods of submodular optimization
• SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES BY SUBMODULAR OPTIMIZATION
• Decomposition algorithms for submodular optimization with applications to parallel machine scheduling with controllable processing times
• A Review for Submodular Optimization on Machine Scheduling Problems
• A submodular optimization approach to bicriteria scheduling problems with controllable processing times on parallel machines

zbMATH Keywords

computational complexityanalysis of algorithmssingle machinelineardeterministicproduction schedulingprogramming

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Integer programming (90C10)

Cites Work

• Power-aware scheduling for makespan and flow
• A survey of scheduling with controllable processing times
• Speed Scaling for Weighted Flow Time
• A survey of results for sequencing problems with controllable processing times
• A Fast Parametric Maximum Flow Algorithm and Applications
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• Preemptive Scheduling of Uniform Machines by Ordinary Network Flow Techniques
• Some simple scheduling algorithms
• 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 WITH CONTROLLABLE PROCESSING TIMES BY SUBMODULAR OPTIMIZATION
• Pre-emptive scheduling problems with controllable processing times
• Improved Algorithms for Bipartite Network Flow
• Fast Algorithms for Parametric Scheduling Come From Extensions to Parametric Maximum Flow
• 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
• Decomposition algorithms for submodular optimization with applications to parallel machine scheduling with controllable processing times
• Algorithms for Scheduling Imprecise Computations with Timing Constraints
• Minimizing the weighted number of tardy task units

Cited In (13)

• 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
• SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES BY SUBMODULAR OPTIMIZATION
• Multiproduct Newsvendor Problem with Customer-Driven Demand Substitution: A Stochastic Integer Program Perspective
• Maximizing a monotone non-submodular function under a knapsack constraint
• Integrated optimization of material supplying, manufacturing, and product distribution: models and fast algorithms
• Approximation algorithm of maximizing non-monotone non-submodular functions under knapsack constraint
• Scheduling problems with controllable processing times and a common deadline to minimize maximum compression cost
• Algorithms for single machine scheduling problem with release dates and submodular penalties
• Approximation algorithm of maximizing non-submodular functions under non-submodular constraint
• Preemptive scheduling of parallel jobs of two sizes with controllable processing times
• Machine Speed Scaling by Adapting Methods for Convex Optimization with Submodular Constraints
• On Submodular Search and Machine Scheduling

This page was built for publication: Application of submodular optimization to single machine scheduling with controllable processing times subject to release dates and deadlines

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