Algorithm for minimizing weighted earliness penalty in single-machine problem

In this paper, the problem of minimizing the weighted earliness penalty in a single-machine scheduling problem is addressed. For this problem, every job is assumed to be available at time zero and must be completed before or on its deadline. No tardy job is allowed. Each job has its own earliness penalty and deadline. The paper identifies several local optimality conditions for sequencing of adjacent jobs. A heuristic algorithm is developed based on these local optimality conditions. Sample problems are solved and the solutions obtained from the heuristic are compared to solutions obtained from the heuristics developed by Chand and Schneeberger. Also, comparisons are performed between the solutions obtained from the heuristic and the optimal solutions obtained from a mathematical modeling approach for problems involving 10 and 15 jobs. The results show that the developed heuristic produces solutions close to optimal in small size problems, and it also outperforms the Chand and Schneeberger's method. (C) 2003 Elsevier B.V. All rights reserved.