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

Potts, C. N.; van Wassenhove, L. N.

Manage. Sci. 34, No. 7, 843-858 (1988).

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

MSC:

90B35	Deterministic scheduling theory in operations research
65K05	Numerical mathematical programming methods

Keywords:

branch and bound; single machine; due dates; penalty weights; reduction principle; heuristic