Preemptive scheduling, linear programming and network flows. (English) Zbl 0532.90047

de Werra, Dominique

SIAM J. Algebraic Discrete Methods 5, 11-20 (1984).

Summary: A refinement of the Birkhoff-von Neumann theorem on bistochastic matrices is derived by a simple argument based on network flow theory; this result is then used for solving a problem of preemptive scheduling on unrelated processors with constraints involving subsets of processors and subsets of jobs. A simple construction procedure is given; it generalizes a two- stage method (linear programming \(+\) network flow) developed by E. L. Lawler and J. Labetoulle [J. Assoc. Comput. Mach. 25, 612-619 (1978; Zbl 0388.68027)] and extended by R. Slowinski [RAIRO, Inf. 15, 155-166 (1981; Zbl 0461.68035); Przegl. Stat. 24, 409-416 (1977; Zbl 0374.90076)].

MSC:

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

Keywords:

Birkhoff-von Neumann theorem; bistochastic matrices; network flow; preemptive scheduling; unrelated processors

Citations:

Zbl 0388.68027; Zbl 0461.68035; Zbl 0374.90076

References:

[1]	Berge, Claude, Graphs and hypergraphs, (1973) · Zbl 0254.05101
[2]	Ford, L. R.; Fulkerson, J., Flows in networks, (1962) · Zbl 0106.34802
[3]	Lawler, E. L.; Labetoulle, J., On preemptive scheduling of unrelated parallel processors by linear programming, J. Assoc. Comput. Mach., 25, 612, (1978) · Zbl 0388.68027
[4]	Slowinski, R., L’ordonnancement des tâches préemptives sur LES processeurs indépendants en présence de ressources supplémentaires, RAIRO Inform., 15, 155, (1981) · Zbl 0461.68035
[5]	Slowinski, R.; Weglarz, J., Minimalno-czasowy model sieciowy z roznymi sposobami wykonywania czynnosci, Przeglad Statyst, 24, 409, (1977)
[6]	de Werra, D., On a class of hypergraphs occurring in chromatic scheduling, Cahiers Centre Études Rech. Opér., 21, 239, (1979) · Zbl 0425.05042