Hybrid approach to decision-making for job-shop scheduling

Abstract

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 space, and the generation of consistent and satisfying schedules is more and more difficult. This article shows the coupling of three approaches in order 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 mechanics 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 population which is considered an important parameter of GAs. CLP is a concept based on operation research (OR) and artificial intelligence (AI). It tends to rid itself of their drawbacks and to regroup their advantages. It aims at providing a set of solutions to a problem expressed in term of constraints. A MCDM approach aims at providing an analysis of a set of possible alternatives 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 population. Second it describes the application of GAs to provide a set of job-shop scheduling minimizing the global makespan. Among the set of job-shop scheduling minimizing the global makespan, it is then possible for the decision-maker to select the most satisfying scheduling according to other criteria, e.g. balance of workload or makespan of each manufacturing order. A large-sized example illustrates clearly the advantages of our hybrid method.