Optimal single-machine scheduling about a common due window with earliness/tardiness and additional penalties

This paper is concerned with the optimal due dates and the optimal sequence to a set of jobs on a single-machine. The common due date assignment method is used, in which all jobs are assigned a common flow allowance. The objective is to find the optimal common due date and the optimal sequence to minimize an objective function of the sum of the Earliness/Tardiness (E/T) penalties and the additional penalties (including two dimensions, namely due date penalties and completion times penalties). It is assumed the E/T penalties will not occur if a job is completed within the due window. However, E/T penalties will occur if a job is completed outside the due window. Five lemmas and a polynomial-time algorithm are presented to determine the optimal common due date and the optimal sequence, a numerical example is provided to illustrate our algorithm.