Diseño de métodos de solución para el problema de orientación y problemas de planificaciónanálisis de técnicas híbridas (búsqueda tabú-VNS)

Zusammenfassung

El trabajo desarrollado en la presente tesis doctoral propone un nuevo método híbrido que combina la búsqueda en entornos variables con la búsqueda tabú. Este nuevo método será aplicado al problema de orientación conocido como “Orienteering Problem” (Tsiligirides 1984) y el problema de planificación de la producción con mantenimiento preventivo (Angel Bello Acosta, Martínez Salazar et al. 2009). El problema de orientación surge de la práctica deportiva de la orientación (Chao, Golden et al. 1996) en el cual una serie de competidores individuales comienzan en un punto específico y tratan de visitar tantos puntos de control como les sea posible y regresar al punto de inicio en un tiempo preestablecido. Por tanto el problema de orientación consiste en determinar un camino o ruta, desde el punto de origen al punto de destino que visite un subconjunto de puntos del conjunto de puntos disponible, de forma que la suma de la puntuación de los puntos visitados sea la máxima posible y el tiempo total de viaje no exceda un valor pre-establecido El problema de planificación de la producción con mantenimiento preventivo está motivado porque en la actualidad las máquinas adquieren un papel cada vez más importante dentro de las empresas y que los costos de mantenimiento pueden llegar a formar un gran porcentaje del presupuesto total de operación (Garg y Deshmukh 2006) resulta deseable obtener una programación de la producción que tome en consideración de manera simultánea tanto las tareas u órdenes a procesar, como las actividades de mantenimiento que reducirán la tasa de paros (Chen y Liao 2005). El tiempo que se invierte en la preparación de las máquinas depende de la tarea que se concluye y de la que se va a procesar. Por tanto la importancia del mantenimiento en la programación de la producción en muchas situaciones reales esto resulta crítico. Por tanto se puede considerar el problema de planificación de la producción con mantenimiento preventivo como un problema combinado de secuenciación de tareas con tiempos de preparación dependientes de la secuencia y restricciones de disponibilidad, el cual puede ser modelado matemáticamente. El problema consiste en determinar el orden en que deben procesarse las tareas en una máquina con costos de preparación dependientes de la secuencia y actividades programadas de mantenimientos preventivos con el objetivo de minimizar el tiempo de finalización de la última tarea que se procese. Además, el procesamiento de las tareas no puede ser interrumpido y el mantenimiento es considerado como una tarea más con costo de preparación dependiente de la secuencia. Dentro de la presente tesis ha realizado un estudio de las técnicas metaheurísticas, de carácter general, tanto clásicas como de reciente aparición. Seguidamente se ha elaborado un análisis y descripción de los dos problemas que se han descrito anteriormente, presentando una descripción de problema y sus variantes, así como sus aplicaciones prácticas y las técnicas propuestas en la literatura para su resolución. Como aportación novedosa en esta tesis se aporta un nuevo método metaheurístico hibrido el cual se quiere aplicar a ambos problemas. Para ello se han elaborado y comparado diversos métodos constructivos, se han realizado análisis de parámetros para determinar cuáles son los valores que mejor se ajustan a estos problemas en concreto. Para analizar el rendimiento de él método hÍbrido propuesto se han utilizado las instancias disponibles en la literatura, se ha decidido hacer de esta manera para así poder posteriormente comparar los resultados obtenidos con otras técnicas. El método propuesto se compara con otras técnicas como búsqueda local, búsqueda tabú, y búsqueda en entornos variables para ver el funcionamiento de las distintas técnicas sobre las mismas instancias. La aportación más reseñable es añadir una estructura basada en memoria en base a las frecuencias para mejorar los resultados frente a los métodos clásicos. Angel Bello Acosta, F. R., I. A. Martínez Salazar, et al. (2009). Incluyendo mantenimiento preventivo en la programación de la producción: un enfoque metaheurístico. VI CONGRESO DE METAHEURÍSTICOS, ALGORITMOS EVOLUTIVOS Y BIOINSPIRADOS: 207-213. Chao, I. M., B. L. Golden, et al. (1996). "The team orienteering problem." European Journal of Operational Research 88(3): 464-474. Chen, W.-J. and C. J. Liao (2005). "Scheduling with different maintenance policies ina textile company." Journal of Quality in Maintenance Engineering 11: 43-53. Garg, A. and S. Deshmukh (2006). "Maintenance management: literature review and directions." Journal of Quality in Maintenance Engineering 12(3): 205-238. Tsiligirides, T. (1984). "HEURISTIC METHODS APPLIED TO ORIENTEERING." Journal of the Operational Research Society 35(9): 797-809.