Flexible Job-Shop Scheduling Problems: Formulation, Lower Bounds, Encoding and Controlled Evolutionary Approach

Abstract

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).