Loading…
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.