A lower bound for the job insertion problem

✍ Scribed by Tamás Kis; Alain Hertz

• Book ID: 104294105
• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 490 KB
• Volume: 128
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(02)00502-4

✦ Synopsis

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 ÿnd 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.