Variations on the theorem of Birkhoff-von Neumann and extensions. (English) Zbl 1412.05066

de Werra, D.

Rusu, Irena (ed.), Proceedings of the 6th international conference on graph theory, Marseille-Luminy, France, August 28–September 2, 2000. Amsterdam: Elsevier. Electron. Notes Discrete Math. 5, 97-99 (2000).

From the text: The theorem of Birkhoff-von Neumann (see [C. Berge, Graphes. 3rd ed. Paris: Gauthier-Villars, Bordas (1983; Zbl 0531.05031)]) on the decomposition of bistochastic matrices (i.e., matrix with nonnegative entries and all row sums and column sums equal to one) has found various applications in scheduling; it is in particular a basic tool in the two-phase method of the preemptive scheduling problem on various machines with different capacities (see [E. L. Lawler and J. Labetoulle, J. Assoc. Comput. Mach. 25, 612–619 (1978; Zbl 0388.68027); D. de Werra, SIAM J. Algebraic Discrete Methods 5, 11–20 (1984; Zbl 0532.90047); Eur. J. Oper. Res. 37, No. 2, 227–235 (1988; Zbl 0652.90064)]).
We shall consider here some simple variations of this result where we remove the sign restrictions; extensions of permutation matrices will be considered and we will use elementary graph-theoretical arguments to derive some of these variations.
For the entire collection see [Zbl 0974.00033].

MSC:

05C15	Coloring of graphs and hypergraphs
90B35	Deterministic scheduling theory in operations research
68M20	Performance evaluation, queueing, and scheduling in the context of computer systems

Keywords:

preemptive scheduling

Citations:

Zbl 0531.05031; Zbl 0388.68027; Zbl 0532.90047; Zbl 0652.90064