Multirecombining random and seed immigrants in evolutionary algorithms to face the shop scheduling problem
In an m-machines n-jobs flow-shop sequencing problem each job consists of m operations and each operation requires a different machine, so n jobs have to be processed in the same sequence on m machines. The processing time of each job on each machine is given. Frequently, the main objective is to fi...
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Objeto de conferencia |
| Lenguaje: | Inglés |
| Publicado: |
2002
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/22071 |
| Aporte de: |
| id |
I19-R120-10915-22071 |
|---|---|
| record_format |
dspace |
| institution |
Universidad Nacional de La Plata |
| institution_str |
I-19 |
| repository_str |
R-120 |
| collection |
SEDICI (UNLP) |
| language |
Inglés |
| topic |
Ciencias Informáticas evolutionary algorithms multiple crossovers multiple parents flow shop scheduling problem Algorithms Scheduling |
| spellingShingle |
Ciencias Informáticas evolutionary algorithms multiple crossovers multiple parents flow shop scheduling problem Algorithms Scheduling Vilanova, Gabriela Villagra, Andrea Pandolfi, Daniel San Pedro, María Eugenia de Gallard, Raúl Hector Multirecombining random and seed immigrants in evolutionary algorithms to face the shop scheduling problem |
| topic_facet |
Ciencias Informáticas evolutionary algorithms multiple crossovers multiple parents flow shop scheduling problem Algorithms Scheduling |
| description |
In an m-machines n-jobs flow-shop sequencing problem each job consists of m operations and each operation requires a different machine, so n jobs have to be processed in the same sequence on m machines. The processing time of each job on each machine is given. Frequently, the main objective is to find the sequence of jobs minimizing the maximum flow time, which is called the makespan. The flow-shop problem has been proved to be NP-complete.
Evolutionary algorithms (EAs) have been successfully applied to solve scheduling problems. Improvements in evolutionary algorithms consider multirecombination, allowing multiple crossover operations on a pair of parents (MCPC, multiple crossovers per couple) or on a set of multiple parents (MCMP. Multiple crossovers on multiple parents). MCMP-STUD and MCMP-SRI are novel MCMP variants, which considers the inclusion of a stud-breeding individual as a seed in a pool of random immigrant parents. Random immigrants provide genetic diversity while seed-immigrants afford the knowledge of some conventional robust heuristics. Members of the mating pool subsequently undergo multiple crossover operations.
Another question in a multirecombined EA is the setting of parameters n1 (number of crossovers) and n2 (number of parents). In the experiments conducted they were empirically determined, by a deterministic rule or by self adaptation of parameters n1 and n2. In the last case the idea is to code the parameters within the chromosome and undergo genetic operations. Hence it is expected that better parameter values be more intensively propagated. |
| format |
Objeto de conferencia Objeto de conferencia |
| author |
Vilanova, Gabriela Villagra, Andrea Pandolfi, Daniel San Pedro, María Eugenia de Gallard, Raúl Hector |
| author_facet |
Vilanova, Gabriela Villagra, Andrea Pandolfi, Daniel San Pedro, María Eugenia de Gallard, Raúl Hector |
| author_sort |
Vilanova, Gabriela |
| title |
Multirecombining random and seed immigrants in evolutionary algorithms to face the shop scheduling problem |
| title_short |
Multirecombining random and seed immigrants in evolutionary algorithms to face the shop scheduling problem |
| title_full |
Multirecombining random and seed immigrants in evolutionary algorithms to face the shop scheduling problem |
| title_fullStr |
Multirecombining random and seed immigrants in evolutionary algorithms to face the shop scheduling problem |
| title_full_unstemmed |
Multirecombining random and seed immigrants in evolutionary algorithms to face the shop scheduling problem |
| title_sort |
multirecombining random and seed immigrants in evolutionary algorithms to face the shop scheduling problem |
| publishDate |
2002 |
| url |
http://sedici.unlp.edu.ar/handle/10915/22071 |
| work_keys_str_mv |
AT vilanovagabriela multirecombiningrandomandseedimmigrantsinevolutionaryalgorithmstofacetheshopschedulingproblem AT villagraandrea multirecombiningrandomandseedimmigrantsinevolutionaryalgorithmstofacetheshopschedulingproblem AT pandolfidaniel multirecombiningrandomandseedimmigrantsinevolutionaryalgorithmstofacetheshopschedulingproblem AT sanpedromariaeugeniade multirecombiningrandomandseedimmigrantsinevolutionaryalgorithmstofacetheshopschedulingproblem AT gallardraulhector multirecombiningrandomandseedimmigrantsinevolutionaryalgorithmstofacetheshopschedulingproblem |
| bdutipo_str |
Repositorios |
| _version_ |
1764820465466998785 |