Flexible Job-Shop Scheduling Problems: Formulation, Lower Bounds, Encoding and Controlled Evolutionary Approach
Imed Kacem (Laboratoire d’Automatique et Informatique de Lille, France), Slim Hammadi (Laboratoire d’Automatique et Informatique de Lille, France) and Pierre Borne (Laboratoire d’Automatique et Informatique de Lille, France)
Copyright: © 2003
The Job-shop Scheduling Problem (JSP) is one of hardest problems; it is classified NP-complete (Carlier & Chretienne, 1988; Garey & Johnson, 1979). In the most part of cases, the combination of goals and resources can exponentially increase the problem complexity, because we have a very large search space and precedence constraints between tasks. Exact methods such as dynamic programming and branch and bound take considerable computing time (Carlier, 1989; Djerid & Portmann, 1996). Front to this difficulty, meta-heuristic techniques such as evolutionary algorithms can be used to find a good solution. The literature shows that they could be successfully used for combinatorial optimization such as wire routing, transportation problems, scheduling problems, etc. (Banzhaf, Nordin, Keller & Francone, 1998; Dasgupta & Michalewicz, 1997).