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 constant-factor 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 were hardest empirically for previous traditional approximation algorithms, a large fraction of the set of jobs can be scheduled using these techniques, with good performance. Our results are based on the existence of approximation algorithms for the nonpreemptive scheduling of jobs with release dates and due dates on one machine so as to maximize the (weighted) number of on-time jobs. As an additional contribution, we generalize the state of the art for such problems, giving the first constant-factor approximation algorithms for the problem of scheduling jobs with resource requirements and release and due dates so as to optimize the weighted number of on-time jobs. In turn, this result further broadens the class of problems to which we can apply our relaxed-approximation result.
