Minimizing the weighted number of tardy jobs on a general single machine

This paper considers the problem of minimizing the weighted number of tardy jobs, each job having a release time, a processing time, a due date and a weight on a single machine. A mathematical programming model with (n²+2n) variables and (6n-1) constraints is formulated. A heuristic is then presented. The average solution quality of the heuristic algorithm is above 98.66%. A 100-job case requires only 0.0165 s, on average, to obtain an optimal or a near optimal solution. To the best of our knowledge, this is the first heuristic approach to attempt to solve this problem.