A single machine scheduling problem with earliness/tardiness and starting time penalties under a common due date

This paper considers a single machine non-preemptive sequencing problem with a common due date. For the problem, the optimal job sequence is sought to minimize the sum of earliness/tardiness and starting-time penalities in the situation where all jobs are not required to be available at time 0. A set of dominant solution properties are characterized to derive both an optimal job starting time search procedure for an arbitrary sequence and a sequence improvement procedure. These are then put together to construct a heuristic solution algorithm whose effectiveness is rated at the mean relative errror of about 5% from its test on randomly generated numerical problems.