Thumbnail Image

Random-Based Scheduling: New Approximations and LP Lower Bounds

Schulz, Andreas S.; Skutella, Martin

Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin

Three characteristics encountered frequently in real-world machine scheduling are jobs released over time, precedence constraints between jobs, and average performance optimization. The general constrained one-machine scheduling problem to minimize the average weighted completion time not only captures these features, but also is an important building block for more complex problems involving multiple machines.