Single machine weighted earliness-tardiness penalty problem with a common due date

In this paper, we have considered a class of single machine job scheduling problems where the objective is to minimize the weighted sum of earliness-t ardiness penalties of jobs. The weights are job-independent but they depend on whether a job is early or tardy. The restricted version of the problem where the common due date is smaller than a critical value, is known to be NP-complete, While dynamic programming formulation runs out of memory for l arge problem instances, depth-first and bound formulation runs slow for lar ge problems since it uses a tree search space. In this paper, we have sugge sted an algorithm to optimally solve large instances of the restricted vers ion of the problem. The algorithm uses a graph search space. Unlike dynamic programming, the algorithm can output optimal solutions even when availabl e memory is limited. It has been found to run faster than dynamic programmi ng and depth-first-and-bound formulations and can solve much larger instanc es of the problem in reasonable time. New upper and lower bounds have been proposed and used. Experimental findings are given in detail. (C) 2001 Publ ished by Elsevier Science Ltd. All rights reserved.