Off-line admission control for general scheduling problems

Cynthia A. Phillips, R. Uma, Joel Wein

2000 · 50 citations · 9 references

Concepts

Abstract

We consider a class of scheduling problems which includes a variety of problems that are exceedingly difficult to approximate (unless P=NP). In the face of very strong hardness results, we consider a relaxed notion of approximability and show that under this notion the problems yield constantfactor approximation algorithms (of a kind). Specifically we give a pseudopolynomial-time algorithm that, given an n-job instance whose optimal schedule has optimality criterion of value OPT , schedules a constant fraction of the n jobs within a constant factor times OPT . In many cases this can be converted to a fully polynomial-time algorithm. We then study the experimental performance of this algorithm and some additional heuristics. Specifically, we consider a set of instances of a one-machine scheduling problem that we have studied previously in the context of traditional approximation algorithms, where the goal is to optimize average weighted flow time. We show that for the instances that we...

References

9