PDF Imprimeix Correu electrònic

SMPA - Secuenciación Multiobjetivo Paralela Avanzada

SMPA logoLa secuenciación multiobjetivo

La secuenciación o programación de la producción, en Inglés, “scheduling” consiste en la asignación de órdenes de producción a los distintos recursos productivos (normalmente máquinas, aunque se puede hablar de servicios con algunas generalizaciones) y la obtención de un programa de producción. Es un campo muy activo de investigación desde mediados de los años 50.

No obstante, la formidable complejidad y variedad de los problemas de optimización combinatoria en esta área ha dado como resultado una investigación excesivamente teórica donde se tratan, de manera general, problemas con un número reducido de restricciones y con una limitada aplicación práctica. De hecho, muchos investigadores denuncian una brecha o “gap” entre la teoría y el uso real por parte de las empresas de las soluciones desarrolladas.

Para resultar útil en la práctica, una programación de la producción debe ser realizable. Para ello es necesario que todas las restricciones se contemplen en el programa. Asimismo, las máquinas o recursos productivos no son la única limitación, ya que hay que considerar materias primas, materiales auxiliares, producto en curso y mano de obra para poder operar los recursos productivos. De igual manera, la práctica totalidad de la inmensa literatura existente se centra en un único objetivo de optimización, cuando bien es sabido que en la práctica es necesario considerar múltiples objetivos, muchas veces conflictivos entre sí.


Objetivos del proyecto

La finalidad del proyecto SMPA es, como las propias siglas del mismo indican, la de desarrollar algoritmos y técnicas que sean capaces de cubrir cuatro grandes aspectos que hoy por hoy no se encuentran cubiertos.

plant layoutObtención de modelos y algoritmos para la programación de la producción en entornos más complejos y realistas de utilidad para las empresas. Aunque muchos autores afirman resolver problemas “realistas” esto no es así en la práctica. La mayoría de las empresas sigue sin utilizar técnicas de optimización para la programación de la producción. Concretamente se consideran características que ocurren frecuentemente en entornos productivos reales como: Problemas sin esperas o “no-wait” y/o sin máquinas paradas o “no-idle”. Cantidad máxima de cambios de partida en planta (“setups”). Almacenamiento de producto en curso limitado y flexible. Problemas en los cuales no es necesario ni procesar todos los trabajos y/o utilizar todas las máquinas. Todos estos aspectos no se han estudiado para problemas complejos. Adicionalmente, se llevará a cabo una primera aproximación a la integración de decisiones de mantenimiento preventivo y de decisiones de re-secuenciación de tareas y/o consideración de imprevistos en la programación de la producción en entornos complejos.


Desarrollo de modelos y algoritmos para la programación de la producción atendiendo a varios recursos productivos. Estos recursos serán limitados, con carácter tanto de renovables como de no renovables. También se estudiarán problemas donde los recursos son asignables y es necesario programar la producción así como decidir cuántos recursos asignar. Además, los recursos pueden estar sometidos a calendarios, algo que también se tratará en este objetivo.


paretoProgramación de la producción realista multiobjetivo. Se desarrollarán principalmente algoritmos evolutivos basados en NSGA, NSGA-II e Iterated Pareto Greedy que puedan programar la producción en todos los entornos complejos de los dos objetivos anteriores con respecto a varios objetivos. Las aproximaciones serán a partir de combinaciones lineales de objetivos ponderados y problemas multiobjetivo con frontera de Pareto y conjunto de soluciones no dominadas. También se extenderán los resultados a problemas con más de dos objetivos.


Desarrollo de paradigmas y algoritmos para la programación realista de la producción mediante técnicas paralelas y/o cooperativas. Aunque las arquitecturas paralelas dedicadas son sumamente eficaces, resultan ser no estándar, caras y pocas empresas disponen de estas plataformas. Se persigue entonces ampliar los algoritmos y métodos desarrollados en todos los puntos anteriores a las plataformas paralelas estándar: programación multi-hilo, clústers y GRIDS.


Difusión y potenciación de transferencia de los resultados obtenidos hacia las empresas. Por último, y durante toda la duración del proyecto se validarán y probarán los métodos desarrollados y se llevarán a cabo tareas de difusión como otro objetivo principal en la investigación.

Las técnicas

genetic algorithmsLas modernas técnicas metaheurísticas permiten resolver complejos problemas de optimización a través del uso de abstracciones. De forma general, una metaheurística trabajará con una representación abstracta de un problema de producción y realizará operaciones sobre esta representación. Las restricciones se pueden considerar separadamente, así como los distintos objetivos de optimización. Adicionalmente, mediante el uso de técnicas de búsqueda local y otros operadores avanzados, una solución obtenida con una metaheurística se puede mejorar sensiblemente en una segunda fase de optimización. El proyecto SMPA hará uso intensivo de estas técnicas para proporcionar un marco algorítmico avanzado de resolución de problemas de producción para distintos sectores productivos, sin necesidad de proponer algoritmos nuevos y/o distintos para cada problema. Es importante destacar que uno de los principales motivos por los cuales los problemas de producción en la práctica no tienen a día de hoy una solución satisfactoria es por el mero hecho de pretender resolver cada problema con un algoritmo específico. En la realidad existen cientos de problemas diferentes. Simplemente no resulta adecuado ni económicamente viable proponer un algoritmo distinto para cada problema.

Con todo ello, disponer de algoritmos que permitan programar la producción a capacidad finita, considerando un elevado número de restricciones relevantes, así como todos los recursos productivos, con avanzados algoritmos de optimización, y además teniendo en cuenta varios objetivos de manera simultánea, y todo ello en una plataforma hardware paralela, puede llegar a tener un tremendo impacto en la literatura y, eventualmente, entre las empresas. La finalidad última es la de incorporar todos estos algoritmos en un prototipo software y con ello potenciar una posible transferencia de los resultados hacia las empresas en el marco de proyectos futuros de transferencia.


Participantes

El proyecto contará con la participación de 19 investigadores (miembros del SOA, y de otros grupos de investigación nacionales e internacionales), así como de 5 EPOs.

Financiación
El proyecto ha sido financiado por el Ministerio de Ciencia e Innovación

MICINN logo