Preemptive scheduling on uniform parallel machines with controllable job processing times

DOI10.1007/s00453-007-9091-9zbMath1147.90009OpenAlexW2104988268MaRDI QIDQ930610

Natalia V. Shakhlevich, Vitaly A. Strusevich

Publication date: 1 July 2008

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://eprints.whiterose.ac.uk/5412/1/Algorithmica2008.pdf

zbMATH Keywords

Maximum flowControllable processing timesGeneralized polymatroidUniform parallel machine scheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items

Scheduling imprecise computation tasks on uniform processors, Preemptive scheduling of two uniform parallel machines to minimize total tardiness, Machine Speed Scaling by Adapting Methods for Convex Optimization with Submodular Constraints, Fast Divide-and-Conquer Algorithms for Preemptive Scheduling Problems with Controllable Processing Times – A Polymatroid Optimization Approach, A Review for Submodular Optimization on Machine Scheduling Problems, An intelligent water drop algorithm to identical parallel machine scheduling with controllable processing times: a just-in-time approach, 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, SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES BY SUBMODULAR OPTIMIZATION

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimizing mean weighted execution time loss on identical and uniform processors
• Pre-emptive scheduling problems with controllable processing times
• A survey of results for sequencing problems with controllable processing times
• Generalized polymatroids and submodular flows
• Minimizing the weighted number of tardy task units
• Notes on max flow time minimization with controllable processing times
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• 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
• Algorithms for Scheduling Imprecise Computations with Timing Constraints
• Preemptive Scheduling of Uniform Machines by Ordinary Network Flow Techniques
• Scheduling Independent Tasks with Due Times on a Uniform Processor System
• Preemptive Scheduling with Release Times, Deadlines, and Due Times
• Preemptive Scheduling of Uniform Processor Systems
• Improved Algorithms for Bipartite Network Flow