|
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, |
