The classical F2//Cmax problem is solved optimally by the famous Johnson's algorithm in O(n*log(n)) 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 close 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 stays linear. Once again, the F2//Cmax appears to be a peculiarity in a complex environment.
