Zurück zu den Preprints des Jahres 2006


A Flow Formulation for the One-Machine Scheduling Problem with Chain Precedence Relations

by Servilio, M., Wagler, A., Weismantel, R..

Series: 2006-37, Preprints

90C27 Combinatorial optimization
90C90 Applications of mathematical programming

We consider a one-machine scheduling problem with chain precedence constraints in order to send data packets through a single channel in a UMT-system.
We propose a flow formulation that allows to solve the problem
in polynomial time, for a fixed number of users.

1-machine scheduling, flow formulation