Minimizing the number of late jobs in single machine scheduling with nested execution intervals

This paper considers the problem of scheduling n jobs on a single machine. A fixed processing time and an execution interval are associated with each job. Job execution intervals are assumed to be nested each inside the other, like Russian dolls. The objective is to minimize the number of late jobs. For this problem, denoted as 1|r_i , nested| SigmaU_i, a new dominance condition and an optimal O(n³) solving procedure are proposed