Scheduling with jobs at fixed positions
研究了单机调度中部分作业必须安排在特定位置的约束，分析了多种经典目标函数，发现某些情况仍可多项式求解，并针对最小化延迟作业数给出了一个多项式算法。
In this paper, we study classical single machine scheduling problems with the additional constraint that a set of special jobs must be scheduled at certain positions in the job sequence. In other words, a special job must start when a certain number of jobs have finished on the machine. We analyze several classical objective functions for this more general setting with the additional constraint of fixed positioned jobs. We show that for some of them they are still polynomially solvable. Then, we focus on the objective of minimizing the number of tardy jobs. Considering the case of just one special job, this allows for a polynomial-time algorithm.