Branch less, cut more and minimize the number of late equal-length jobs on identical machines

A simple greedy-type solution for a discrete optimization problem does not guarantee the optimality if the problem is sufficiently complicated. Dynamic programming is then a commonly used method, and a direct combinatorial algorithm is its reasonable alternative. Here we propose such an algorithm with some specific features, called branch less and cut more, abbreviated blesscmore. A blesscmore algorithm, like a branch-and-bound algorithm uses a solution tree whereas the branching and cutting criteria are based on the analysis of the so-called behavior alternatives. Our O(n3logn) blesscmore algorithm solves an earlier open problem of scheduling n equal-length jobs with release times and due-dates on a group of identical machines to minimize the number of late jobs.