Zurück zu den Preprints des Jahres 2006


2006-37

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

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


Series: 2006-37, Preprints

MSC:
90C27 Combinatorial optimization
90C90 Applications of mathematical programming

Abstract:
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.

Keywords:
1-machine scheduling, flow formulation