La programación de talleres es un problema desafiante para la programación matemática. Sin embargo, cuando corresponde, el impacto operativo puede ser grande. En la publicación de blog de hoy, contribuiré a este tema con un ejemplo técnico que cubre la programación de tareas genéticas.
Un problema simple de programación de tareas de máquinas de taller
El ejemplo que sugiero comprende 3 máquinas (M1, M2 y M3) y 5 tareas (T1, T2, T3, T4 y T5). Los trabajos deben procesarse en un taller de trabajo. Cada tarea se puede procesar en cualquier máquina, pero existen ciertas restricciones que limitan la posible secuencia de tareas en cada máquina.
Por ejemplo, las restricciones podrían ser las siguientes:
- T1 debe procesarse antes que T2 en M1
- T4 debe procesarse antes que T5 en M2
- T2 y T3 no se pueden procesar en la misma máquina
Ahora quiero encontrar un programa de tareas en cada máquina que minimice el tiempo de procesamiento total para todas las tareas.
Programación de tareas de taller con algoritmos genéticos
Para resolver este problema utilizando un algoritmo genético, represento un programa como una secuencia de números enteros. Cada entero representa la tarea que se procesará a continuación. Por ejemplo, un programa [1, 2, 3, 4, 5] significa que procesamos la tarea 1 en la máquina 1, seguida de la tarea 2 en la máquina 2, seguida de la tarea 3 en la máquina 3, y así sucesivamente.
Podemos usar una función de aptitud simple que calcula el tiempo total de procesamiento para un cronograma dado, teniendo en cuenta las restricciones. Por ejemplo, podríamos calcular el tiempo de procesamiento de la siguiente manera:
- Para cada máquina, calcule el tiempo de procesamiento como la suma de los tiempos de procesamiento de todas las tareas asignadas a esa máquina.
- Si hay violaciones de restricciones (p. ej., si T2 y T3 están asignados a la misma máquina), agregue una penalización al tiempo de procesamiento.
- La idoneidad de un programa es el negativo del tiempo de procesamiento.
Luego podemos usar un algoritmo genético para generar y desarrollar horarios hasta que encontremos uno bueno.
Ejemplo de algoritmo de programación genética
Aquí hay un ejemplo de cómo podría funcionar el algoritmo:
- Genere una población inicial de programaciones, cada una de las cuales consiste en una secuencia aleatoria de tareas asignadas a las máquinas.
- Calcule la aptitud de cada horario utilizando la función de aptitud.
- Seleccione un subconjunto de la población para criar la próxima generación de cronogramas, utilizando un método de selección como la selección de torneos.
- Genere nuevos horarios utilizando operadores de cruce y mutación.
- Reemplace la población anterior con la población nueva y repita los pasos 2 a 4 para un cierto número de generaciones.
- El mejor programa encontrado es el que tiene el valor de condición física más alto.
Se sabe que los problemas de programación del taller de trabajo son NP-difíciles, lo que significa que encontrar la solución óptima es computacionalmente intratable para instancias de problemas grandes. Como resultado, los algoritmos genéticos pueden tardar mucho en converger o pueden no ser capaces de encontrar la solución óptima en absoluto.
Observaciones finales y contenido relacionado con la programación del taller
La programación del taller de trabajo es un tema desafiante. La programación matemática, y en este caso los algoritmos genéticos, pueden ser efectivos en algunos casos. En otros casos, los problemas pueden ser demasiado complejos para resolverlos analíticamente con un esfuerzo razonable. Si este fuera el caso, la simulación de eventos discretos puede ayudar a superar algunos de los desafíos de la aplicación de programación matemática. La siguiente publicación de blog de SCDA describe los desafíos de la programación de talleres:
Puede leer más sobre la simulación, especialmente la simulación de eventos discretos, en las siguientes publicaciones de SCDA. El modelado de simulación puede implementar soluciones de programación que pueden superar los desafíos de la programación matemática que la hacen inadecuada para su aplicación en problemas del mundo real.
- Enlace : Simulación de taller con salabim en Python
- Enlace : Simulación de taller de trabajo en SimPy
- Enlace : Visualización de la simulación del taller de trabajo de SimPy
La programación de restricciones es otro enfoque para la programación del taller de trabajo que puede tomar. Aquí hay un ejemplo que puede ayudarlo a comenzar:
Ingeniero industrial especializado en optimización y simulación (R, Python, SQL, VBA)
Leave a Reply