Optimization Algorithms for a Class of Single Machine Scheduling Problems Using Due Date determination Methods


N.I. Karacapilidis, C.P. Pappis




The problem of determining optimal schedules for the static, single machine scheduling problem with the aid of CON and SLK due date determination methods is considered. The objective is to minimize the total weighted earliness and tardiness penalty in the case when weights are proportional to the processing times of the respective jobs. For each method, an optimization algorithm has been developed, by means of which the set of all optimal sequences is provided. The numerical example, presented after the theoretical foundation . confirms considerations about the structural similarity of the two methods.