Hybrid approach to decision-making for job-shop scheduling

The job-shop scheduling problem is one of the hardest problems (NP-complete problem) [Garey and Johnson 1979, Computer and Intractability: A Guide to the Theory of NP-completeness (San Francisco: Freeman)]. In lots of cases, the combination of goals and resources exponentially increases the search s pace, and the generation of consistent and satisfying schedules is more and more difficult. This article shows the coupling of three approaches in ord er to contribute to the solving of the job-shop scheduling problem: genetic algorithms. (GAs); constraint logic programming (CLP); and multi-criteria decision-making (MCDM). The GAs are searching algorithms based on the mecha nics of natural. selection. They employ a probabilistic search for locating the globally optimal solution. They start with an initial population often randomly generated. The difficulty holds in the creation of this initial p opulation which is considered an important parameter of GAs. CLP is a conce pt based on operation research (OR) and artificial intelligence (AI). It te nds to rid itself of their drawbacks and to regroup their advantages. It ai ms at providing a set of solutions to a problem expressed in term of constr aints. A MCDM approach aims at providing an analysis of a set of possible a lternatives according to a set of conflicting criteria in order to help the user. This article explains first how to use the CLP to generate a first p opulation. Second it describes the application of GAs to provide a set of j ob-shop scheduling minimizing the global makespan. Among the set of job-sho p scheduling minimizing the global makespan, it is then possible for the de cision-maker to select the most satisfying scheduling according to other cr iteria, e.g. balance of workload or makespan of each manufacturing order. A large-sized example illustrates clearly the advantages of our hybrid metho d.