A NEW APPROACH FOR THE BEST-CASE SCHEDULE IN A GROUP SEQUENCE

Colloque avec actes et comité de lecture. internationale.International audience"The job-shop scheduling problem is an NP-hard optimization problem. It is generally solved using either predictive methods such as discrete optimization which try to find a solution that fits constraints and that optimizes one or more objectives or usingreactive methods such real-time control methods which try to build incrementally in real-time a solution of the problem. Predictive-reactive methods try to combine both advantages of predictive and reactive methods (i.e., good performances andreactivity). The group sequencing method is one of the most studied predictive-reactive methods. The goal of this method is to have a sequential flexibility during the execution of the schedule and to guarantee a minimal quality corresponding to theworst-case.The best-case quality has also been successfully addressed by [Pinot2008] using a branch and bound procedure. It has been established for every regular objective. In this paper we propose two new branching processes to compute the best-case for the makespan which is one of the most studied regular objective. The experiments made on very well-known instances of the job-shop problem show the benefits of these new branching procedures.}