Registro:
| Documento: | Tesis de Grado |
| Título: | Algoritmos para el problema de job-shop scheduling basados en programación dinámica |
| Autor: | Nogueira, Agustín Alejandro |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Publicación en la web: | 2026-04-09 |
| Fecha de defensa: | 2015-09-30 |
| Fecha en portada: | 28 de agosto de 2015 |
| Grado Obtenido: | Grado |
| Título Obtenido: | Licenciado en Ciencias Matemáticas |
| Departamento Docente: | Departamento de Matemáticas |
| Director: | Ojea, Ignacio |
| Jurado: | Perrucci, Daniel Roberto; Etcheverry, Javier Ignacio |
| Idioma: | Español |
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/seminario_nMAT000925_Nogueira |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nMAT000925_Nogueira.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/seminario/document/seminario_nMAT000925_Nogueira |
| Ubicación: | Dep.MAT 000925 |
| Derechos de Acceso: | Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Nogueira, Agustín Alejandro. (2015). Algoritmos para el problema de job-shop scheduling basados en programación dinámica. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/seminario_nMAT000925_Nogueira |
Resumen:
El objetivo principal de esta tesis es estudiar un algoritmo exacto para el problema de job-shop scheduling, basado en programación dinámica, que fue propuesto en [6]. El algoritmo es de complejidad exponencial, lo cual resulta natural dado que el problema de job-shop scheduling es NP-Hard [3]. Sin embargo, es también exponencialmente mejor que la fuerza bruta. De este modo, representa un pequeño avance en un sentido poco frecuente, dado que la mayor parte de la literatura dedicada a la resolución de problemas NP-Hard apunta al desarrollo de nuevas heurísticas. El algoritmo construye soluciones iterativamente y por etapas. En cada etapa se cuenta con un conjunto de soluciones parciales, cada una de las cuales es expandida en la etapa siguiente a través del agregado de una nueva operación. La naturaleza exponencial del algoritmo radica en el crecimiento exponencial de estos conjuntos. Al seguir la línea de un planteo por programación dinámica, la formulación del problema propuesta en [6] permite comparar soluciones parciales con el objetivo de descartar algunas de ellas. Esto contribuye a mejorar la eficiencia práctica del algoritmo. Nuestra implementación mejora la original, dado que incorpora nuevos criterios de comparación que permiten reducir considerable el número de soluciones parciales construidas por el algoritmo. Al tratarse de un algoritmo exacto, este permite resolver en tiempos aceptables instancias relativamente pequeñas del problema, pero no instancias medianas o grandes. Para estos casos, implementamos una variante heurística que consiste esencialmente en acotar arbitrariamente el número de soluciones parciales generadas en cada etapa. Si bien esta heurística permite encontrar soluciones cercanas al óptimo en instancias que resultaban inabordables con el algoritmo exacto, su eficiencia dista de la de otras técnicas heurísticas estudiadas en la literatura. El primer capítulo está dedicado a la introducción de nociones básicas de problemas de optimización combinatoria, mientras que el segundo presenta los rudimentos de la programación dinámica. En el Capítulo 3 se plantea el problema de job-shop scheduling. El cuarto capítulo representa el corazón de la tesis: allí se realiza la formulación del problema, siguiendo la línea de [6], se presenta el esquema del algoritmo y se demuestra que efectivamente encuentra una solución óptima. La demostración de este hecho dada en el artículo original contenía errores que aquí son salvados. En el Apéndice se muestra, con un contraejemplo, la falsedad de alguna de las afirmaciones de [6]. En el Capítulo 5 se detalla nuestra implementación y se estima su complejidad. La técnica heurística es presentada en el sexto capítulo, mientras que el séptimo está dedicado a la exposición de los resultados obtenidos.
Citación:
---------- APA ----------
Nogueira, Agustín Alejandro. (2015). Algoritmos para el problema de job-shop scheduling basados en programación dinámica. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nMAT000925_Nogueira
---------- CHICAGO ----------
Nogueira, Agustín Alejandro. "Algoritmos para el problema de job-shop scheduling basados en programación dinámica". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2015.https://hdl.handle.net/20.500.12110/seminario_nMAT000925_Nogueira
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nMAT000925_Nogueira.pdf
Distrubución geográfica
