Un algoritmo genético híbrido y un enfriamiento simulado para solucionar el problema de programación de pedidos Job Shop

La programación de pedidos para el problema de producción Job Shop (JSP), catalogado como NP-Hard, ha constituido un reto para la comunidad científica, debido a que alcanzar una solución óptima a este problema se dificulta en la medida que crece en número de máquinas y trabajos. Numerosas técnicas,...

Full description

Autores:
Meisel-Donoso, José David
Prado, L. K. (Liliana Katherine)
Tipo de recurso:
Article of journal
Fecha de publicación:
2010
Institución:
Universidad EIA .
Repositorio:
Repositorio EIA .
Idioma:
spa
OAI Identifier:
oai:repository.eia.edu.co:11190/216
Acceso en línea:
https://repository.eia.edu.co/handle/11190/216
Palabra clave:
REI00122
ORGANIZACIÓN E INDUSTRIA
ORGANIZATION AND INDUSTRY
PRODUCCIÓN INDUSTRIAL
INDUSTRIAL PRODUCTION
PLANIFICACIÓN DE LA PRODUCCIÓN
PRODUCTION PLANNING
JOB SHOP
ALGORITMO GENÉTICO
ENFRIAMIENTO SIMULADO
ADMINISTRACIÓN
GENETIC ALGORITHM
SIMULATED ANNEALING
OPERATIONS MANAGEMENT
COMBINATORIAL OPTIMIZATION
Rights
openAccess
License
Derechos Reservados - Universidad EIA, 2020
id REIA2_327e68dacefc86e51d2a8bf89c7991da
oai_identifier_str oai:repository.eia.edu.co:11190/216
network_acronym_str REIA2
network_name_str Repositorio EIA .
repository_id_str
dc.title.spa.fl_str_mv Un algoritmo genético híbrido y un enfriamiento simulado para solucionar el problema de programación de pedidos Job Shop
dc.title.alternative.spa.fl_str_mv Um algoritmo genético híbrido e um esfriamento simulado para solucionar o problema de programação de pedidos Job Shop
A hybrid genetic algorithm and a simulated annealing for solving the Job Shop scheduling problem
title Un algoritmo genético híbrido y un enfriamiento simulado para solucionar el problema de programación de pedidos Job Shop
spellingShingle Un algoritmo genético híbrido y un enfriamiento simulado para solucionar el problema de programación de pedidos Job Shop
REI00122
ORGANIZACIÓN E INDUSTRIA
ORGANIZATION AND INDUSTRY
PRODUCCIÓN INDUSTRIAL
INDUSTRIAL PRODUCTION
PLANIFICACIÓN DE LA PRODUCCIÓN
PRODUCTION PLANNING
JOB SHOP
ALGORITMO GENÉTICO
ENFRIAMIENTO SIMULADO
ADMINISTRACIÓN
GENETIC ALGORITHM
SIMULATED ANNEALING
OPERATIONS MANAGEMENT
COMBINATORIAL OPTIMIZATION
title_short Un algoritmo genético híbrido y un enfriamiento simulado para solucionar el problema de programación de pedidos Job Shop
title_full Un algoritmo genético híbrido y un enfriamiento simulado para solucionar el problema de programación de pedidos Job Shop
title_fullStr Un algoritmo genético híbrido y un enfriamiento simulado para solucionar el problema de programación de pedidos Job Shop
title_full_unstemmed Un algoritmo genético híbrido y un enfriamiento simulado para solucionar el problema de programación de pedidos Job Shop
title_sort Un algoritmo genético híbrido y un enfriamiento simulado para solucionar el problema de programación de pedidos Job Shop
dc.creator.fl_str_mv Meisel-Donoso, José David
Prado, L. K. (Liliana Katherine)
dc.contributor.author.spa.fl_str_mv Meisel-Donoso, José David
Prado, L. K. (Liliana Katherine)
dc.subject.lcsh.spa.fl_str_mv REI00122
topic REI00122
ORGANIZACIÓN E INDUSTRIA
ORGANIZATION AND INDUSTRY
PRODUCCIÓN INDUSTRIAL
INDUSTRIAL PRODUCTION
PLANIFICACIÓN DE LA PRODUCCIÓN
PRODUCTION PLANNING
JOB SHOP
ALGORITMO GENÉTICO
ENFRIAMIENTO SIMULADO
ADMINISTRACIÓN
GENETIC ALGORITHM
SIMULATED ANNEALING
OPERATIONS MANAGEMENT
COMBINATORIAL OPTIMIZATION
dc.subject.eia.spa.fl_str_mv ORGANIZACIÓN E INDUSTRIA
ORGANIZATION AND INDUSTRY
dc.subject.eurovoc.spa.fl_str_mv PRODUCCIÓN INDUSTRIAL
INDUSTRIAL PRODUCTION
PLANIFICACIÓN DE LA PRODUCCIÓN
PRODUCTION PLANNING
dc.subject.keywords.spa.fl_str_mv JOB SHOP
ALGORITMO GENÉTICO
ENFRIAMIENTO SIMULADO
ADMINISTRACIÓN
GENETIC ALGORITHM
SIMULATED ANNEALING
OPERATIONS MANAGEMENT
COMBINATORIAL OPTIMIZATION
description La programación de pedidos para el problema de producción Job Shop (JSP), catalogado como NP-Hard, ha constituido un reto para la comunidad científica, debido a que alcanzar una solución óptima a este problema se dificulta en la medida que crece en número de máquinas y trabajos. Numerosas técnicas, entre ellas las metaheurísticas, se han empleado para su solución, sin embargo, su eficiencia, en cuanto a tiempo computacional, no ha sido muy satisfactoria. Por lo anterior y para contribuir a la solución de este problema, se planteó el uso de un enfriamiento simulado propuesto (ESP) y de un algoritmo genético mejorado (AGM). Para el AGM se implementó una estrategia de enfriamiento simulado en la fase de mutación, que permite al algoritmo intensificar y diversificar las soluciones al mismo tiempo, con el fin de que no converja prematuramente a un óptimo local. Los resultados mostraron que los algoritmos propuestos arrojan buenos resultados, con desviaciones alrededor de los mejores valores encontrados que no superan el 5 % para los problemas más complejos
publishDate 2010
dc.date.created.spa.fl_str_mv 2010-07
dc.date.submitted.spa.fl_str_mv 2010-03-07
dc.date.accepted.spa.fl_str_mv 2010-05-26
dc.date.accessioned.spa.fl_str_mv 2013-12-17T16:05:46Z
dc.date.available.spa.fl_str_mv 2013-12-17T16:05:46Z
dc.date.issued.spa.fl_str_mv 2013-12-17
dc.type.spa.fl_str_mv Artículo de revista
dc.type.coar.fl_str_mv http://purl.org/coar/resource_type/c_2df8fbb1
dc.type.coar.spa.fl_str_mv http://purl.org/coar/resource_type/c_6501
dc.type.driver.spa.fl_str_mv info:eu-repo/semantics/article
dc.type.version.spa.fl_str_mv info:eu-repo/semantics/publishedVersion
dc.type.content.spa.fl_str_mv Text
dc.type.redcol.spa.fl_str_mv https://purl.org/redcol/resource_type/ART
dc.type.coarversion.spa.fl_str_mv http://purl.org/coar/version/c_970fb48d4fbd8a85
format http://purl.org/coar/resource_type/c_6501
status_str publishedVersion
dc.identifier.issn.spa.fl_str_mv ISSN 17941237
dc.identifier.uri.spa.fl_str_mv https://repository.eia.edu.co/handle/11190/216
dc.identifier.bibliographiccitation.spa.fl_str_mv Meisel, J. D., y Prado, L. K. (2010). Un algoritmo genético híbrido y un enfriamiento simulado para solucionar el problema de programación de pedidos Job Shop, Revista EIA, 7 (13), 39-51. doi: http://hdl.handle.net/11190/216
identifier_str_mv ISSN 17941237
Meisel, J. D., y Prado, L. K. (2010). Un algoritmo genético híbrido y un enfriamiento simulado para solucionar el problema de programación de pedidos Job Shop, Revista EIA, 7 (13), 39-51. doi: http://hdl.handle.net/11190/216
url https://repository.eia.edu.co/handle/11190/216
dc.language.iso.spa.fl_str_mv spa
language spa
dc.relation.ispartof.spa.fl_str_mv Revista EIA
dc.relation.references.spa.fl_str_mv Aiex, R. M.; Binato, S. and Resende M. G. C. (2003). “Parallel GRASP with path-relinking for job shop scheduling”. Parallel Computing 29, pp. 393-430.
Azizi, Nader and Zolfaghari, Saeed (2004). “Adaptive temperature control for simulated annealing: a comparative study”. Computers & Operations Research, vol. 31, pp. 2439-2451.
Bierwirth, C.; Mattfeld D. and Kopfer H. (1996). “Proceedings of parallel problem solving from Nature IV”. Springer, pp. 310-318.
Binato, S.; Hery, W. J.; Loewenstern, D. M. and Resende, M. G. C. A GRASP for job shop scheduling. In: Ribeiro, C. C., Hansen, P. (eds.). Essays and Surveys in Metaheuristics. Kluwer Academic Publishers, 2002.
Della Croce, Federico; Tadei, Roberto and Volta, Giuseppe (1995). “A genetic algorithm for the job shop problem”. Computers & Operations Research, vol. 22, No. 1, pp. 15-24.
dc.rights.spa.fl_str_mv Derechos Reservados - Universidad EIA, 2020
dc.rights.uri.spa.fl_str_mv https://creativecommons.org/licenses/by-nc/4.0/
dc.rights.accessrights.spa.fl_str_mv info:eu-repo/semantics/openAccess
dc.rights.creativecommons.spa.fl_str_mv Atribución-NoComercial
dc.rights.coar.spa.fl_str_mv http://purl.org/coar/access_right/c_abf2
rights_invalid_str_mv Derechos Reservados - Universidad EIA, 2020
https://creativecommons.org/licenses/by-nc/4.0/
Atribución-NoComercial
http://purl.org/coar/access_right/c_abf2
eu_rights_str_mv openAccess
dc.format.extent.spa.fl_str_mv 13 p.
dc.format.mimetype.spa.fl_str_mv application/pdf
dc.publisher.editor.spa.fl_str_mv Fondo Editorial EIA
institution Universidad EIA .
bitstream.url.fl_str_mv https://repository.eia.edu.co/bitstreams/285c4e23-f16f-426e-b10a-3361becd8f76/download
https://repository.eia.edu.co/bitstreams/1b04d0c5-d8c2-4b3c-838d-d1aa3523a249/download
https://repository.eia.edu.co/bitstreams/ec531bb9-7996-4450-ac80-218d19e94a02/download
https://repository.eia.edu.co/bitstreams/4ed36494-8379-40aa-a9d0-7b3ca55cab0c/download
https://repository.eia.edu.co/bitstreams/92596cb5-e4b5-4e83-8c3f-4006027a87ac/download
https://repository.eia.edu.co/bitstreams/a263d22e-e5cc-49ed-acf7-6054a1fe0981/download
https://repository.eia.edu.co/bitstreams/d1e525bc-6671-4c50-8233-3a2396014626/download
bitstream.checksum.fl_str_mv 489911257442fdaec564e37309a4b3da
e398f72b52bb3e44c94c3eb468e2d948
66874b0b9366b748c60895d2fb6339f8
4afdbb8c545fd630ea7db775da747b2f
35f5a4dbb73331730901b4be803cf6b5
cd76e7886171c964e259dcf5e912e299
75fc223f9bf81f3c2145f2cf9d6a2df6
bitstream.checksumAlgorithm.fl_str_mv MD5
MD5
MD5
MD5
MD5
MD5
MD5
repository.name.fl_str_mv Repositorio Institucional Universidad EIA
repository.mail.fl_str_mv bdigital@metabiblioteca.com
_version_ 1814100897595129856
spelling Meisel-Donoso, José David1f81cb4a3d8ddf426c4411dd28c8007c-1Prado, L. K. (Liliana Katherine)19be9e7f8442d6c70475e626a38faa78-1jose.meisel@unibague.edu.coliloprado@hotmail.com2013-12-17T16:05:46Z2013-12-17T16:05:46Z2010-072013-12-172010-03-072010-05-26ISSN 17941237https://repository.eia.edu.co/handle/11190/216Meisel, J. D., y Prado, L. K. (2010). Un algoritmo genético híbrido y un enfriamiento simulado para solucionar el problema de programación de pedidos Job Shop, Revista EIA, 7 (13), 39-51. doi: http://hdl.handle.net/11190/216La programación de pedidos para el problema de producción Job Shop (JSP), catalogado como NP-Hard, ha constituido un reto para la comunidad científica, debido a que alcanzar una solución óptima a este problema se dificulta en la medida que crece en número de máquinas y trabajos. Numerosas técnicas, entre ellas las metaheurísticas, se han empleado para su solución, sin embargo, su eficiencia, en cuanto a tiempo computacional, no ha sido muy satisfactoria. Por lo anterior y para contribuir a la solución de este problema, se planteó el uso de un enfriamiento simulado propuesto (ESP) y de un algoritmo genético mejorado (AGM). Para el AGM se implementó una estrategia de enfriamiento simulado en la fase de mutación, que permite al algoritmo intensificar y diversificar las soluciones al mismo tiempo, con el fin de que no converja prematuramente a un óptimo local. Los resultados mostraron que los algoritmos propuestos arrojan buenos resultados, con desviaciones alrededor de los mejores valores encontrados que no superan el 5 % para los problemas más complejosJob Shop Scheduling Problem (JSP), classified as NP-Hard, has been a challenge for the scientific community because achieving an optimal solution to this problem is complicated as it grows in number of machines and jobs. Numerous techniques, including metaheuristics, have been used for its solution; however, the efficiency of the techniques, in terms of computational time, has not been very satisfactory. Because of this and for contributing to the solution of this problem, a simulated annealing (SA) and an improved genetic algorithm (IGA) have been proposed. The latter, by implementing a strategy of simulated annealing in the mutation phase, allows the algorithm to enhance and diversify the solutions at the same time, in order not to converge prematurely to a local optimum. The results showed that the proposed algorithms yield good results with deviations around the best values found not exceeding 5 % for more complex problems.13 p.application/pdfspaRevista EIAAiex, R. M.; Binato, S. and Resende M. G. C. (2003). “Parallel GRASP with path-relinking for job shop scheduling”. Parallel Computing 29, pp. 393-430.Azizi, Nader and Zolfaghari, Saeed (2004). “Adaptive temperature control for simulated annealing: a comparative study”. Computers & Operations Research, vol. 31, pp. 2439-2451.Bierwirth, C.; Mattfeld D. and Kopfer H. (1996). “Proceedings of parallel problem solving from Nature IV”. Springer, pp. 310-318.Binato, S.; Hery, W. J.; Loewenstern, D. M. and Resende, M. G. C. A GRASP for job shop scheduling. In: Ribeiro, C. C., Hansen, P. (eds.). Essays and Surveys in Metaheuristics. Kluwer Academic Publishers, 2002.Della Croce, Federico; Tadei, Roberto and Volta, Giuseppe (1995). “A genetic algorithm for the job shop problem”. Computers & Operations Research, vol. 22, No. 1, pp. 15-24.Derechos Reservados - Universidad EIA, 2020https://creativecommons.org/licenses/by-nc/4.0/El autor de la obra, actuando en nombre propio, hace entrega del ejemplar respectivo y de sus anexos en formato digital o electrónico y autoriza a la ESCUELA DE INGENIERIA DE ANTIOQUIA, para que en los términos establecidos en la Ley 23 de 1982, Ley 44 de 1993, Decisión andina 351 de 1993, Decreto 460 de 1995, y demás normas generales sobre la materia, utilice y use por cualquier medio conocido o por conocer, los derechos patrimoniales de reproducción, comunicación pública, transformación y distribución de la obra objeto del presente documento. PARÁGRAFO: La presente autorización se hace extensiva no sólo a las dependencias y derechos de uso sobre la obra en formato o soporte material, sino también para formato virtual, electrónico, digital, y en red, internet, extranet, intranet, etc., y en general en cualquier formato conocido o por conocer. EL AUTOR, manifiesta que la obra objeto de la presente autorización es original y la realiza sin violar o usurpar derechos de autor de terceros, por lo tanto la obra es de exclusiva autoría y tiene la titularidad sobre la misma. PARÁGRAFO: En caso de presentarse cualquier reclamación o acción por parte de un tercero en cuanto a los derechos de autor sobre la obra en cuestión, EL AUTOR, asumirá toda la responsabilidad, y saldrá en defensa de los derechos aquí autorizados; para todos los efectos la ESCUELA DE INGENIERÍA DE ANTIOQUIA actúa como un tercero de buena fe.info:eu-repo/semantics/openAccessAtribución-NoComercialhttp://purl.org/coar/access_right/c_abf2REI00122ORGANIZACIÓN E INDUSTRIAORGANIZATION AND INDUSTRYPRODUCCIÓN INDUSTRIALINDUSTRIAL PRODUCTIONPLANIFICACIÓN DE LA PRODUCCIÓNPRODUCTION PLANNINGJOB SHOPALGORITMO GENÉTICOENFRIAMIENTO SIMULADOADMINISTRACIÓNGENETIC ALGORITHMSIMULATED ANNEALINGOPERATIONS MANAGEMENTCOMBINATORIAL OPTIMIZATIONUn algoritmo genético híbrido y un enfriamiento simulado para solucionar el problema de programación de pedidos Job ShopUm algoritmo genético híbrido e um esfriamento simulado para solucionar o problema de programação de pedidos Job ShopA hybrid genetic algorithm and a simulated annealing for solving the Job Shop scheduling problemArtículo de revistahttp://purl.org/coar/resource_type/c_6501http://purl.org/coar/resource_type/c_2df8fbb1info:eu-repo/semantics/articleinfo:eu-repo/semantics/publishedVersionTexthttps://purl.org/redcol/resource_type/ARThttp://purl.org/coar/version/c_970fb48d4fbd8a85Fondo Editorial EIAPublicationTHUMBNAILREI00122.pdf.jpgREI00122.pdf.jpgGenerated Thumbnailimage/jpeg12226https://repository.eia.edu.co/bitstreams/285c4e23-f16f-426e-b10a-3361becd8f76/download489911257442fdaec564e37309a4b3daMD57ORIGINALREI00122.pdfREI00122.pdfapplication/pdf1047519https://repository.eia.edu.co/bitstreams/1b04d0c5-d8c2-4b3c-838d-d1aa3523a249/downloade398f72b52bb3e44c94c3eb468e2d948MD51LICENSElicense.txtlicense.txttext/plain; charset=utf-81494https://repository.eia.edu.co/bitstreams/ec531bb9-7996-4450-ac80-218d19e94a02/download66874b0b9366b748c60895d2fb6339f8MD52CC-LICENSElicense_urllicense_urltext/plain; charset=utf-849https://repository.eia.edu.co/bitstreams/4ed36494-8379-40aa-a9d0-7b3ca55cab0c/download4afdbb8c545fd630ea7db775da747b2fMD53license_textlicense_texttext/html; charset=utf-820149https://repository.eia.edu.co/bitstreams/92596cb5-e4b5-4e83-8c3f-4006027a87ac/download35f5a4dbb73331730901b4be803cf6b5MD54license_rdflicense_rdfapplication/rdf+xml; charset=utf-823253https://repository.eia.edu.co/bitstreams/a263d22e-e5cc-49ed-acf7-6054a1fe0981/downloadcd76e7886171c964e259dcf5e912e299MD55TEXTREI00122.pdf.txtREI00122.pdf.txtExtracted texttext/plain44346https://repository.eia.edu.co/bitstreams/d1e525bc-6671-4c50-8233-3a2396014626/download75fc223f9bf81f3c2145f2cf9d6a2df6MD5611190/216oai:repository.eia.edu.co:11190/2162023-07-25 17:06:39.892https://creativecommons.org/licenses/by-nc/4.0/Derechos Reservados - Universidad EIA, 2020open.accesshttps://repository.eia.edu.coRepositorio Institucional Universidad EIAbdigital@metabiblioteca.comRWwgYXV0b3IgZGUgbGEgb2JyYSwgYWN0dWFuZG8gZW4gbm9tYnJlIHByb3BpbywgSGFjZSBlbnRyZWdhIGRlbCBlamVtcGxhciByZXNwZWN0aXZvIHkgZGUgc3VzIGFuZXhvcyBlbiBmb3JtYXRvIGRpZ2l0YWwgbyBlbGVjdHLDs25pY28uIAoKWSBhdXRvcml6YSBhIGxhIEVTQ1VFTEEgREUgSU5HRU5JRVJJQSBERSBBTlRJT1FVSUEsIHBhcmEgcXVlIGVuIGxvcyB0w6lybWlub3MgZXN0YWJsZWNpZG9zIGVuOgoKIC0gbGEgTGV5IDIzIGRlIDE5ODIKIC0gTGV5IDQ0IGRlIDE5OTMKLSBEZWNpc2nDs24gYW5kaW5hIDM1MSBkZSAxOTkzCiAtIERlY3JldG8gNDYwIGRlIDE5OTUKCiB5IGRlbcOhcyBub3JtYXMgZ2VuZXJhbGVzIHNvYnJlIGxhIG1hdGVyaWEsIHV0aWxpY2UgeSB1c2UgcG9yIGN1YWxxdWllciBtZWRpbyBjb25vY2lkbyBvIHBvciBjb25vY2VyLCBsb3MgZGVyZWNob3MgcGF0cmltb25pYWxlcyBkZSByZXByb2R1Y2Npw7NuLAogY29tdW5pY2FjacOzbiBww7pibGljYSwgdHJhbnNmb3JtYWNpw7NuIHkgZGlzdHJpYnVjacOzbiBkZSBsYSBvYnJhIG9iamV0byBkZWwgcHJlc2VudGUgZG9jdW1lbnRvLiAKCiBQQVJHUkFGTzogTGEgcHJlc2VudGUgYXV0b3JpemFjacOzbiBzZSBoYWNlIGV4dGVuc2l2YSBubyBzb2xvIGEgbGFzIGRlcGVuZGVuY2lhcyB5IGRlcmVjaG9zIGRlIHVzbyBzb2JyZSBsYSBvYnJhIGVuIGZvcm1hdG8gbyBzb3BvcnRlIG1hdGVyaWFsLCAKIHNpbm8gdGFtYmnDqW4gcGFyYSBmb3JtYXRvIHZpcnR1YWwsIGVsZWN0csOzbmljbywgZGlnaXRhbCwgeSBjdXlvIHVzbyBzZSBkZSBlbiByZWQsIGludGVybmV0LCBleHRyYW5ldCwgaW50cmFuZXQsIGV0Yy4sIHkgZW4gZ2VuZXJhbCBlbiBjdWFscXVpZXIKIGZvcm1hdG8gY29ub2NpZG8gbyBwb3IgY29ub2Nlci4gCgogRUwgQVVUT1IsIG1hbmlmaWVzdGEgcXVlIGxhIG9icmEgb2JqZXRvIGRlIGxhIHByZXNlbnRlIGF1dG9yaXphY2nDs24gZXMgb3JpZ2luYWwgeSBsYSByZWFsaXphIHNpbiB2aW9sYXIgbyB1c3VycGFyIGRlcmVjaG9zIGRlIGF1dG9yIGRlIHRlcmNlcm9zLAogcG9yIGxvIHRhbnRvIGxhIG9icmEgZXMgZGUgZXhjbHVzaXZhIGF1dG9yw61hIHkgdGllbmUgbGEgdGl0dWxhcmlkYWQgc29icmUgbGEgbWlzbWEuClBBUkFHUkFGTzogRW4gY2FzbyBkZSBwcmVzZW50YXJzZSBjdWFscXVpZXIgcmVjbGFtYWNpw7NuIG8gYWNjacOzbiBwb3IgcGFydGUgZGUgdW4gdGVyY2VybyBlbiBjdWFudG8gYSBsb3MgZGVyZWNob3MgZGUgYXV0b3Igc29icmUgbGEgb2JyYSBlbiAKY3Vlc3Rpw7NuLCBFTCBBVVRPUiwgYXN1bWlyw6HCoSB0b2RhIGxhIHJlc3BvbnNhYmlsaWRhZCwgeSBzYWxkcsOhwqEgZW4gZGVmZW5zYSBkZSBsb3MgZGVyZWNob3MgYXF1w60gYXV0b3JpemFkb3M7IHBhcmEgdG9kb3MgbG9zIGVmZWN0b3MgTGEgRVNDVUVMQSAKREUgSU5HRU5JRVJJQSBERSBBTlRJT1FVSUEgYWN0w7phIGNvbW8gdW4gdGVyY2VybyBkZSBidWVuYSBmZS4K