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(n(3) log n) 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. (c) 2012 Elsevier B.V. All rights reserved.
solution tree polynomial-time algorithm scheduling identical machines