A tabu search and a genetic algorithm for solving a bicriteria general job shop scheduling problem
| Autor: | Jean-Charles Billaut, Geoffrey Vilcot |
|---|---|
| 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) |
| Rok vydání: | 2008 |
| Předmět: |
0209 industrial biotechnology
Mathematical optimization Information Systems and Management General Computer Science Job shop Population 02 engineering and technology Management Science and Operations Research Tabu search Industrial and Manufacturing Engineering Scheduling (computing) 020901 industrial engineering & automation Search algorithm 0202 electrical engineering electronic engineering information engineering Bicriteria [INFO]Computer Science [cs] education Mathematics education.field_of_study Job shop scheduling Scheduling Pareto principle [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] Flow shop scheduling General job shop Genetic algorithm Modeling and Simulation 020201 artificial intelligence & image processing |
| Zdroj: | European Journal of Operational Research European Journal of Operational Research, Elsevier, 2007, 190, pp.398-411 |
| ISSN: | 0377-2217 |
| DOI: | 10.1016/j.ejor.2007.06.039 |
| 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