A TABU SEARCH ALGORITHM FOR SOLVING A BICRITERIA FLEXIBLE JOB SHOP SCHEDULING PROBLEM
| Autor: | Carl Esswein, Geoffrey Vilcot, Jean-Charles Billaut |
|---|---|
| Přispěvatelé: | Maurel, Denis, Laboratoire d'Informatique Fondamentale et Appliquée de Tours (LIFAT), Université de Tours (UT)-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS) |
| Rok vydání: | 2006 |
| Předmět: |
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]
050210 logistics & transportation Mathematical optimization 021103 operations research [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO] Job shop scheduling Computer science 05 social sciences 0211 other engineering and technologies [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] 02 engineering and technology Flow shop scheduling Job shop scheduling problem Tabu search Scheduling (computing) Nurse scheduling problem 0502 economics and business [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC] Algorithm |
| Zdroj: | INCOM 12th IFAC Symposium on Information Control Problems in Manufacturing 12th IFAC Symposium on Information Control Problems in Manufacturing, May 2006, Saint-Etienne, France. pp.57-62 |
| ISSN: | 1474-6670 |
| DOI: | 10.3182/20060517-3-fr-2903.00038 |
| Popis: | International audience; This paper deals with a general job shop scheduling problem with multiple constraints, coming from printing and boarding industry. The objective is the minimization of two criteria, the makespan and the maximum lateness, and we are interested in finding an approximation of the Pareto frontier. We propose a fast and elitist genetic algorithm based on NSGA-II for solving the problem. The initial population of this algorithm is either randomly generated or partially generated by using a tabu search algorithm, that minimizes a linear combination of the two criteria. Both the genetic and the tabu search algorithms are tested on benchmark instances from flexible job shop literature and computational results show the interest of both methods to obtain an efficient and effective resolution method. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|