Title :
Assignment and Scheduling in Flexible Job-Shops by Hierarchical Optimization
Author :
Zribi, Nozha ; Kacem, Imed ; El Kamel, Abdelkader ; Borne, Pierre
Author_Institution :
Ecole Centrale de Lille, Villeneuve d´´ Ascq
fDate :
7/1/2007 12:00:00 AM
Abstract :
In this paper, we propose a new hierarchical method for the flexible job-shop scheduling problem (FJSP). This approach is mainly adapted to a job-shop problem (JSP) with high flexibility and is based on the decomposition of the problem in an assignment subproblem and a sequencing subproblem. For the first subproblem, we propose two methods: the first one is based successively on a heuristic approach and a local search; the second one, however, is based on a branch-and-bound algorithm. The quality of the assignment is evaluated by a lower bound. For the second subproblem we apply a hybrid genetic algorithm to deal with the sequencing problem. Computational tests are finally presented.
Keywords :
genetic algorithms; job shop scheduling; tree searching; branch-and-bound algorithm; flexible job-shops assignment; flexible job-shops scheduling; heuristic approach; hierarchical optimization; hybrid genetic algorithm; local search; sequencing subproblem; Dispatching; Evolutionary computation; Genetic algorithms; Helium; NP-hard problem; Optimization methods; Processor scheduling; Routing; Single machine scheduling; Testing; Assignment problem; branch-and-bound; genetic algorithms (GAs); job-shop scheduling problem; local search; lower bounds;
Journal_Title :
Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on
DOI :
10.1109/TSMCC.2007.897494