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

DOI10.1002/NET.22202MaRDI QIDQ6196891zbMATH OpenOpenAlexFDO

Authors Akiyoshi Shioura, V. A. Strusevich, N. V. Shakhlevich

Publication date 15 March 2024

Published in Networks (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

maximum-flow problemminimum-cut problemoptimality conditionsparallel-machine schedulingpreemptionscheduling under resource constraintsscheduling with controllable processing times

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Recommendations

• Preemptive Scheduling of Uniform Machines by Ordinary Network Flow Techniques
• Preemptive scheduling on identical parallel machines subject to deadlines.
• Preemptive scheduling on uniform machines to minimize mean flow time
• Preemptive scheduling with deadlines on parallel machines
• Preemptive Scheduling, Linear Programming and Network Flows

Cites work

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6196891)