Preemptive Scheduling, Linear Programming and Network Flows

DOI10.1137/0605003MaRDI QIDQ3315254zbMATH OpenOpenAlexFDO

Authors Dominique De Werra

Publication date 1984

Published in SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0605003

zbMATH Keywords

Birkhoff-von Neumann theorembistochastic matricesnetwork flowpreemptive schedulingunrelated processors

Mathematics Subject Classification ID

Random matrices (algebraic aspects) (15B52) Deterministic network models in operations research (90B10) Deterministic scheduling theory in operations research (90B35) Linear programming (90C05)

Recommendations

• Variations on the theorem of Birkhoff-von Neumann and extensions
• Preemptive Scheduling of Uniform Machines by Ordinary Network Flow Techniques
• Preemptive scheduling with staircase and piecewise linear resource availability
• On the two-phase method for preemptive scheduling
• Preemptive scheduling and antichain polyhedra

Cites work

• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 3661359 (Why is no real title available?)
• scientific article; zbMATH DE number 3722085 (Why is no real title available?)
• scientific article; zbMATH DE number 3400923 (Why is no real title available?)
• On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming

Cited in

(20)

• Scheduling tasks on two processors with deadlines and additional resources
• Minimizing mean flow time with parallel processors and resource constraints
• New trends in machine scheduling
• On the two-phase method for preemptive scheduling
• Some preemptive open shop scheduling problems with a renewable or a nonrenewable resource
• On the complexity of preemptive openshop scheduling problems
• On an optimization problem occurring in FMSs: A hypergraph-theoretical formulation
• Normal-form preemption sequences for an open problem in scheduling theory
• Algorithms for minimizing maximum lateness with unit length tasks and resource constraints
• Scheduling two-machine preemptive open shops to minimize total completion time
• On preemptive scheduling: A general setting for the two-phase method
• A preemptive open shop scheduling problem with one resource
• Variations on the theorem of Birkhoff-von Neumann and extensions
• Preemptive scheduling with staircase and piecewise linear resource availability
• scientific article; zbMATH DE number 15416 (Why is no real title available?)
• Nonpreemptive open shop with restricted processing times
• Generalizing Horn's conditions for preemptive scheduling on identical parallel machines via network flow techniques
• Mathematical programming formulations for machine scheduling: A survey
• Linear programming based algorithms for preemptive and non-preemptive RCPSP
• A note on SS/TDMA satellite communication

This page was built for publication: Preemptive Scheduling, Linear Programming and Network Flows

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