Estrategias mmas para minimización del makespan en la programación de una máquina con setup
En este trabajo se aplica un algoritmo de optimización de colonia de hormigas con límites de feromona superior e inferior denominado Max–Min Ant System, para resolver problemas de programación de una máquina con tiempos de preparación dependientes de la secuencia y minimización de makespan. El estud...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | Spanish |
| Published: |
Universidad del Bío-Bío
2011-07-01
|
| Series: | Ingenieria Industrial |
| Subjects: | |
| Online Access: | http://revistas.ubiobio.cl/index.php/RI/article/view/40 |
| _version_ | 1818369337625411584 |
|---|---|
| author | Eduardo Salazar Hornig Oscar Sánchez Pinto |
| author_facet | Eduardo Salazar Hornig Oscar Sánchez Pinto |
| author_sort | Eduardo Salazar Hornig |
| collection | DOAJ |
| description | En este trabajo se aplica un algoritmo de optimización de colonia de hormigas con límites de feromona superior e inferior denominado Max–Min Ant System, para resolver problemas de programación de una máquina con tiempos de preparación dependientes de la secuencia y minimización de makespan. El estudio presenta y compara tres variantes del Max–Min Ant System, en base a la forma de actualización de feromona aplicadas a un conjunto de pro-blemas de prueba de 100 trabajos. Las variantes de los algoritmos se comparan para deter-minar la mejor de ellas y, también, con una heurística constructiva greedy del Mejor Vecino. Se concluye que adecuadas modificaciones a la estrategia de actualización de feromona mejoran significativamente la calidad de las soluciones, obteniéndose soluciones cercanas al óptimo, dado que las diferencias promedio con respecto de una cota inferior del makespan son menores al 1%.
This paper studied an ant colony optimization algorithm with upper and lower pheromone limits called the Max–Min Ant System is applied to solve the single machine scheduling pro-blem with sequence dependent setup times and makespan minimization. The study presents and compares three variants of the algorithm based on the pheromone update applied to a set of problems of size 100 jobs. The algorithms variants are compared between them and with a constructive greedy heuristic of the best neighbor. We conclude that adequate modifications to the pheromone actualization strategy improve significantly the solution quality, obtaining solution near the optimum due to the average differences less than 1% with respect to a lower bound of the makespan. |
| first_indexed | 2024-12-13T23:22:15Z |
| format | Article |
| id | doaj.art-cc64973ef81a41ebb5827f1f8f5a7357 |
| institution | Directory Open Access Journal |
| issn | 0717-9103 0718-8307 |
| language | Spanish |
| last_indexed | 2024-12-13T23:22:15Z |
| publishDate | 2011-07-01 |
| publisher | Universidad del Bío-Bío |
| record_format | Article |
| series | Ingenieria Industrial |
| spelling | doaj.art-cc64973ef81a41ebb5827f1f8f5a73572022-12-21T23:27:41ZspaUniversidad del Bío-BíoIngenieria Industrial0717-91030718-83072011-07-01102Estrategias mmas para minimización del makespan en la programación de una máquina con setupEduardo Salazar Hornig0Oscar Sánchez Pinto1Departamento de Ingeniería Industrial, Universidad de Concepción, Concepción. ChileDepartamento de Ingeniería Industrial, Universidad de Concepción, Concepción. ChileEn este trabajo se aplica un algoritmo de optimización de colonia de hormigas con límites de feromona superior e inferior denominado Max–Min Ant System, para resolver problemas de programación de una máquina con tiempos de preparación dependientes de la secuencia y minimización de makespan. El estudio presenta y compara tres variantes del Max–Min Ant System, en base a la forma de actualización de feromona aplicadas a un conjunto de pro-blemas de prueba de 100 trabajos. Las variantes de los algoritmos se comparan para deter-minar la mejor de ellas y, también, con una heurística constructiva greedy del Mejor Vecino. Se concluye que adecuadas modificaciones a la estrategia de actualización de feromona mejoran significativamente la calidad de las soluciones, obteniéndose soluciones cercanas al óptimo, dado que las diferencias promedio con respecto de una cota inferior del makespan son menores al 1%. This paper studied an ant colony optimization algorithm with upper and lower pheromone limits called the Max–Min Ant System is applied to solve the single machine scheduling pro-blem with sequence dependent setup times and makespan minimization. The study presents and compares three variants of the algorithm based on the pheromone update applied to a set of problems of size 100 jobs. The algorithms variants are compared between them and with a constructive greedy heuristic of the best neighbor. We conclude that adequate modifications to the pheromone actualization strategy improve significantly the solution quality, obtaining solution near the optimum due to the average differences less than 1% with respect to a lower bound of the makespan.http://revistas.ubiobio.cl/index.php/RI/article/view/40Colonia de hormigasMMASuna máquinamakespansetupsmejor ve-cino. |
| spellingShingle | Eduardo Salazar Hornig Oscar Sánchez Pinto Estrategias mmas para minimización del makespan en la programación de una máquina con setup Ingenieria Industrial Colonia de hormigas MMAS una máquina makespan setups mejor ve-cino. |
| title | Estrategias mmas para minimización del makespan en la programación de una máquina con setup |
| title_full | Estrategias mmas para minimización del makespan en la programación de una máquina con setup |
| title_fullStr | Estrategias mmas para minimización del makespan en la programación de una máquina con setup |
| title_full_unstemmed | Estrategias mmas para minimización del makespan en la programación de una máquina con setup |
| title_short | Estrategias mmas para minimización del makespan en la programación de una máquina con setup |
| title_sort | estrategias mmas para minimizacion del makespan en la programacion de una maquina con setup |
| topic | Colonia de hormigas MMAS una máquina makespan setups mejor ve-cino. |
| url | http://revistas.ubiobio.cl/index.php/RI/article/view/40 |
| work_keys_str_mv | AT eduardosalazarhornig estrategiasmmasparaminimizaciondelmakespanenlaprogramaciondeunamaquinaconsetup AT oscarsanchezpinto estrategiasmmasparaminimizaciondelmakespanenlaprogramaciondeunamaquinaconsetup |