View article

We consider a single-machine scheduling problem such that the due dates are assigned not to the jobs but to the position at which the job is processed. We focus on the case with identical due date intervals. The objective is to minimize the weighted number of early and tardy jobs. First, we show that the problem is strongly NP-hard and has no -approximation algorithm for any fixed value . Then, we investigate polynomially solvable cases. Finally, we show that the preemption version is weakly NP-hard through its equivalence to the problem of minimizing the weighted number of tardy jobs.