SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES BY SUBMODULAR OPTIMIZATION

DOI10.1142/S0129054109006541zbMath1170.90399OpenAlexW2015110010WikidataQ60500877 ScholiaQ60500877MaRDI QIDQ3634181

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

Publication date: 23 June 2009

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054109006541

zbMATH Keywords

polymatroidcontrollable processing timesSingle machine schedulingbase polyhedron

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items

In-house production and outsourcing under different discount schemes on the total outsourcing cost, Batch scheduling of identical jobs with controllable processing times, Machine Speed Scaling by Adapting Methods for Convex Optimization with Submodular Constraints, 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, Application of Submodular Optimization to Single Machine Scheduling with Controllable Processing Times Subject to Release Dates and Deadlines, Decomposition algorithms for submodular optimization with applications to parallel machine scheduling with controllable processing times

Cites Work

• 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
• Generalized polymatroids and submodular flows
• A bicriterion approach to time/cost trade-offs in sequencing
• Single machine scheduling subject to deadlines and resource dependent processing times
• Using geometric techniques to improve dynamic programming algorithms for the economic lot-sizing problem and extensions
• Some comments on sequencing with controllable processing times
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Scheduling imprecise computation tasks on uniform processors
• A survey of scheduling with controllable processing times
• Submodular functions and optimization.
• Algorithms for Reporting and Counting Geometric Intersections
• A bicriterion problem of the scheduling theory taking the variation of servicing time into account