The simple with forbidden tasks in first or last position: A problem more complex that it seems
The classical F2//Cmax problem is solved optimally by the famous Johnson's algorithm in where n is the number of jobs. For solving the F/no-idle/Cmax with a branch and bound algorithm, it is necessary to solve problem closed to the F2//Cmax. The only difference is an additive constraint: a set of jobs that cannot be placed in the first (or the last) position. This problem is linear and can be solved by testing systematically all allowed jobs in first position, the other one being scheduled according to Johnson's rule. But this exhaustive procedure (in O(n2)) is not satisfying. While it seems natural to think that a single rule (like Johnson's one) can be applied, all intuitive rules can be refuted by counterexamples. Surprisingly, this F2//Cmax with this additive constraint appears to be more complicated than the initial problem, even if it stay linear. Once again, the F2//Cmax appears to be a peculiarity in a complex environment.
no-idle scheduling flow-shop makespan