Application of Submodular Optimization to Single Machine Scheduling with Controllable Processing Times Subject to Release Dates and Deadlines

DOI10.1287/ijoc.2015.0660zbMath1338.90182OpenAlexW2270422555WikidataQ57950404 ScholiaQ57950404MaRDI QIDQ2806872

Akiyoshi Shioura, Natalia V. Shakhlevich, Vitaly 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 complexityproduction schedulingsingle machineanalysis of algorithmslineardeterministicprogramming

Mathematics Subject Classification ID

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

Related Items

Maximizing a monotone non-submodular function under a knapsack constraint, Multiproduct Newsvendor Problem with Customer-Driven Demand Substitution: A Stochastic Integer Program Perspective, Scheduling problems with controllable processing times and a common deadline to minimize maximum compression cost, Approximation algorithm of maximizing non-monotone non-submodular functions under knapsack constraint, Machine Speed Scaling by Adapting Methods for Convex Optimization with Submodular Constraints, A Review for Submodular Optimization on Machine Scheduling Problems, Integrated optimization of material supplying, manufacturing, and product distribution: models and fast algorithms, Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: a review of solution approaches

Cites Work

• Decomposition algorithms for submodular optimization with applications to parallel machine scheduling with controllable processing times
• 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
• Power-aware scheduling for makespan and flow
• Minimizing the weighted number of tardy task units
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A survey of scheduling with controllable processing times
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• Algorithms for Scheduling Imprecise Computations with Timing Constraints
• Fast Divide-and-Conquer Algorithms for Preemptive Scheduling Problems with Controllable Processing Times – A Polymatroid Optimization Approach
• Speed Scaling for Weighted Flow Time
• SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES BY SUBMODULAR OPTIMIZATION
• Preemptive Scheduling of Uniform Machines by Ordinary Network Flow Techniques
• Improved Algorithms for Bipartite Network Flow
• Some simple scheduling algorithms
• 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