Generalizing Horn's conditions for preemptive scheduling on identical parallel machines via network flow techniques

DOI10.1002/net.22202OpenAlexW4390055875MaRDI QIDQ6196891

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

Publication date: 15 March 2024

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.22202

zbMATH Keywords

optimality conditionsscheduling with controllable processing timespreemptionparallel-machine schedulingmaximum-flow problemminimum-cut problemscheduling under resource constraints

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation of the parallel machine scheduling problem with additional unit resources
• Scheduling subject to resource constraints: Classification and complexity
• Scheduling preemptable tasks on parallel processors with limited availability
• Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: a review of solution approaches
• Parallel machine scheduling with additional resources: notation, classification, models and solution methods
• Parallel machine scheduling with machine availability and eligibility constraints
• Network flow approaches to pre-emptive open-shop scheduling problems with time-windows
• Scheduling with Deadlines and Loss Functions
• Preemptive Scheduling of Uniform Machines by Ordinary Network Flow Techniques
• Preemptive Scheduling with Due Dates
• Some simple scheduling algorithms
• General Multiprocessor Task Scheduling: Approximate Solutions in Linear Time
• Max flows in O(nm) time, or better
• Scheduling Jobs on Several Machines with the Job Splitting Property
• On PreemptiveResource Constrained Scheduling: Polynomial-Time Approximation Schemes
• Preemptive scheduling with dedicated processors: applications of fractional graph coloring
• Scheduling of parallel identical machines to maximize the weighted number of just-in-time jobs

This page was built for publication: Generalizing Horn's conditions for preemptive scheduling on identical parallel machines via network flow techniques