Complexity of Scheduling Problems With Generalized Due Dates

We consider the problem of scheduling \(n\) independent tasks
on a single processor with generalized due dates. The due dates
are given according to positions at which jobs are completed,
rather than specified by the jobs.
We show that the following problems are NP-Complete,
\(1|\text{prec}, p_j = 1|\sum w_jU_j\),
\(1|\text{chain}, p_j = 1|\sum w_jU_j\),
\(1|\text{prec}, p_j = 1|\sum w_jT_j\), and
\(1|\text{chain}, p_j = 1|\sum w_j T_j\).
With the removal of precedence constraints, we prove that
the two problems,
\(1|p_j = 1|\sum w_jU_j\) and
\(1|p_j = 1|\sum w_j T_j\),
are polynomially solvable.