Scheduling jobs with general linear deterioration to minimize total weighted number of late jobs

This paper deals with a single-machine scheduling problem with a general linear deterioration effect. The goal is to determine the job schedule such that the total weighted number of late jobs is minimized. We present three properties, one heuristic algorithm and a lower bound to speed up the search process of the branch-and-bound algorithm. In addition, some complex heuristics (including tabu search and simulated annealing algorithms) are proposed as solutions to this problem. The computational results show that the proposed algorithms are effective and efficient.