(A) single machine scheduling problem with earliness and tardiness penalties under common due date

Abstract

This thesis considers a nonpreemptive single machine scheduling problem in which all jobs are partitioned into several job sets each having its corresponding common due date and are subject to penalties due to early or late completions. The objective of the problem is to minimize the weighted mean absolute deviation of job completion times about such common due dates under the assumption that each job has a different weight, and to exploit dominant solution properties based upon which three heuristic solution methods are derived. It is also shown that the problem of minimizing the mean squared deviation of job completion times about a common due date is equivalent to the problem of minimizing the completion time variance. The mean absolute deviation problem with a single common due date is first investigated and then extended to the case with two common due dates, and suggests a solution method. Numerical examples are presented.