Algorithms for scheduling a single machine to minimize the weighted number of late jobs. (English) Zbl 0656.90048

The paper considers the following problem. Given are n jobs for a single machine with required time, due dates, and penalty weights. Minimize the weighted penalty for the late jobs. This problem is NP-hard. The authors give a reduction principle which helps in the reduction of job numbers. They obtain an algorithm for the problem using well-known methods, which seems to be quite impressive. Several numerical tests were performed proving the effectiveness of this heuristic.
Reviewer: A.P.Bosznay


90B35 Deterministic scheduling theory in operations research
65K05 Numerical mathematical programming methods
Full Text: DOI