A constrained single machine scheduling model with earliness/tardiness and flow time measures

This paper considers a single machine nonpreemptive scheduling problem with a given common due date. In the problem, the optimal job sequence is sought to minimize the sum of earliness/tardiness and flow time measures in the situation where all jobs are available at time zero, and weights per unit length of earliness/tardiness and flow time are V and W, respectively. Some dominant solution properties are characterized to derive both an optimal starting time for an arbitrary sequence and sequence improvement rules. The optimal schedule is found for the case W≥V. By the way, it is difficult to find the optimal schedule for the case W<V. Therefore, the derived properties are put on together to construct a heuristic solution algorithm for the case W<V, and its effectiveness is rated at the mean relative error of about 3% on randomly generated numerical problems.