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 i i th completed job receives the i i th 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.
unary np-hard assignable due dates single machine scheduling generalized due dates