A lower bound for the job insertion problem Original Research Article

This note deals with the job insertion problem in job-shop scheduling: Given a feasible schedule of n jobs and a new job which is not scheduled, the problem is to find a feasible insertion of the new job into the schedule which minimises the makespan. Since the problem is NP-hard, a relaxation method is proposed to compute a strong lower bound. Conditions under which the relaxation provides us with the makespan of the optimal insertion are derived. After the analysis of the polytope of feasible insertions, a polynomial time procedure is proposed to solve the relaxed problem. Our results are based on the theory of perfect graphs and elements of polyhedral theory.