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

DOI10.1287/IJOC.2015.0660MaRDI QIDQ2806872zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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

zbMATH Keywords

computational complexityanalysis of algorithmssingle machinelineardeterministicproduction schedulingprogramming

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(17)

• On Submodular Search and Machine Scheduling
• Handling scheduling problems with controllable parameters by methods of submodular optimization
• A Review for Submodular Optimization on Machine Scheduling Problems
• Scheduling a single machine with compressible jobs to minimize maximum lateness
• 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
• Machine speed scaling by adapting methods for convex optimization with submodular constraints
• Maximizing a monotone non-submodular function under a knapsack constraint
• Integrated optimization of material supplying, manufacturing, and product distribution: models and fast algorithms
• Decomposition algorithms for submodular optimization with applications to parallel machine scheduling with controllable processing times
• 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
• A submodular optimization approach to bicriteria scheduling problems with controllable processing times on parallel machines
• Approximation algorithm of maximizing non-submodular functions under non-submodular constraint
• Preemptive scheduling of parallel jobs of two sizes with controllable processing times

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)