Unary NP-hardness of minimizing the total deviation with generalized or assignable due dates

In this paper, we study the single machine scheduling to minimize the total earliness and tardiness (i.e., the total deviation) with generalized or assignable due dates. Under the assumption of assignable due dates, the due dates are treated as variables and must be assigned to the individual jobs in a schedule. The assumption of generalized due dates is a special version of assignable due dates, in which the due dates are sequenced in the EDD order and assigned to the jobs by the increasing order of their completion times so that the iith completed job receives the iith due date. The exact complexity of the two problems has been reported open in the literature. We show in this paper that the two problems are unary NP-hard.