Several problems in various industrial enviromnents are combinatorial problems. This is the case for numerous scheduling problems. Generally there do not exist efficient algorithms to solve these problems in their general form. Generally, the combinations of goals and resources have exponentially growing search space, described in computer science terms as NP-complele. Therefore, exact methods such as branch and bound methods, dynamic programming methods, etc..., take considerable computing time and/or require complex mathematical formulation. Recently stochastic search techniques such as genetic algorithms have been successfully applied to job -shop scheduling problems. Genetic algorithms present some advantages. They are robust in that they provide a good solution on a wide range of problems. In addition, they can easily be modified with respect to the objective function and constraints. Our objective in this article is to improve performance of the genetic algorithms based approach to job-shop scheduling problems by developing effective genetic operators, such as a parallel representation of the chromosome, on the one hand, and genetic operators associated with this original representation, on the other one. In this article we deal with the problem of flexible job-shop scheduling which presents two difficulties: the first one is the assignment of each operation to a machine, and the second one is scheduling this set of operations in order to minimize our criterion (e.g. the makespan).
Genetic Algorithms (GAs), Parallel Representation, Initial Population, Priority rules, Constraint Logic Programming
All articles published by Studies in Informatics and Control (SIC) are published in accordance with the terms and conditions of the Creative Commons Attribution License (CC BY-NC-SA 4.0).