A Tabu Search algorithm and a genetic algorithm for solving a bicriteria general jobshop scheduling problem
| Autor: | Vilcot, Geoffrey, Billaut, Jean-Charles |
|---|---|
| Přispěvatelé: | 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), Maurel, Denis |
| Jazyk: | angličtina |
| Rok vydání: | 2008 |
| Předmět: |
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]
[INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO] Scheduling Genetic algorithm General job shop [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC] [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] Tabu search Bicriteria |
| Zdroj: | European Journal of Operational Research European Journal of Operational Research, Elsevier, 2008, 190 (2), pp.398-411 |
| ISSN: | 0377-2217 |
| 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: |
|
Full Text from ScienceDirect