A new lower bound for the job-shop scheduling problem (Q2366077)

The best known exact algorithms for solving the general job-shop scheduling problem are branch-and-bound methods. A natural way to get lower bounds for branch-and-bound algorithms is to solve relaxations of the general job-shop problem. The classical method is based on one- machine relaxations. In the article a new lower bound is developed. This lower bound is based on a two-job relaxation which can be solved efficiently by using geometric methods. Computational experiments show that the new lower bound improves the one-machine relaxation bound if the ratio between the number of machines and the number of jobs is large.