Single-machine scheduling with positional due indices and positional deadlines

In this paper, we study single-machine scheduling problems with due dates, positional due indices, deadlines and positional deadlines. The scheduling criteria studied in this paper include the number of position-violated tasks, the weighted number of position-violated tasks, and the maximum positional lateness of tasks, by also combining with other traditional scheduling criteria. For each problem, we either provide a polynomial-time algorithm or present an NP-hardness proof.