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.
No takes yet. Share an insight, caveat, or question.
Florian Jaehn (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: