Diseño de meta-metamodelos para el modelado de entornos de smart manufacturing mediante técnicas de optimización

Equation Chapter 1 Section 1 Proyecto Fin de Carrera Ingeniería en Tecnologías Industriales Diseño de meta-metamodelos para el modelado de entornos de smart manufacturing mediante técnicas de optimización Dpto. Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Autor: Álvaro Garrido Rodríguez-Córdoba Tutor: Jesús Racero Moreno Sevilla, 2022 12 Proyecto Fin de Carrera Ingeniería en Tecnologías Industriales Diseño de meta-metamodelos para el modelado de entornos de smart manufacturing mediante técnicas de optimización Autor: Álvaro Garrido Rodríguez-Córdoba Tutor: Jesús Racero Moreno Dpto. de Organización Industrial y Gestión de empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2022 14 Proyecto Fin de Carrera: Diseño de meta-metamodelos para el modelado de entornos de smart manufacturing mediante técnicas de optimización Autor: Álvaro Garrido Rdríguez-Córdoba Tutor: Jesús Racero Moreno El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros: Presidente: Vocales: Secretario: Acuerdan otorgarle la calificación de: 16 Sevilla, 2022 El Secretario del Tribunal A mi familia A mis amigos 18 Índice Resumen ..................................................................................................................................................... 11 Abstract ...................................................................................................................................................... 11 Índice de figuras .......................................................................................................................................... 11 Índice de códigos ......................................................................................................................................... 11 1 Introducción y objetivos ........................................................................................................................ 1 1.1 Introducción ................................................................................................................................................. 1 1.2 Objetivos ....................................................................................................................................................... 2 2 Revisión de la literatura ......................................................................................................................... 3 2.1 La programación de operaciones en el ámbito de fabricación ................................................................ 3 2.1.1 Introducción al problema de scheduling 4 2.1.2 Tipos de problemas de programación de operaciones (Schedulling) 5 2.1.3 Representación 7 2.2 Resolución del problema de scheduling ..................................................................................................... 9 2.2.1 Métodos exactos 11 2.2.2 Métodos heurísticos 11 2.3 Smart scheduling ....................................................................................................................................... 13 2.3.1 Algoritmos predictivos-reactivos 14 2.3.2 Machine learning y simulación en problemas de scheduling 15 2.4 Gestión del conocimiento en sistemas de fabricación ............................................................................ 16 2.4.1 Introducción a la gestión del conocimiento 16 2.4.2 Análisis semántico para la gestión del conocimiento 17 2.4.3 Ontologías aplicadas al scheduling y smart scheduling 18 3 Diseño de un sistema de conocimiento interoperable para smart scheduling ..................................... 21 3.1 Introducción a las técnicas de diseño de ontologías ............................................................................... 21 3.2 Software de diseño de ontologías ............................................................................................................ 23 3.3 Diseño de la ontología. Algoritmo de resolución, elegir uno .................................................................. 34 3.4 Interoperabilidad entre implementación de sistemas smart scheduling .............................................. 39 4 Pruebas ................................................................................................................................................ 41 4.1 Validación del proceso ............................................................................................................................... 41 4.2 Resolución de problema de mantenimiento ............................................................................................ 45 5 Conclusiones y extensiones ................................................................................................................. 61 5.1 Conclusiones ............................................................................................................................................... 61 5.2 Extensiones ................................................................................................................................................. 62 Bibliografía .................................................................................................................................................. 63 1 1 INTRODUCCIÓN Y OBJETIVOS 1.1 Introducción Actualmente la industria y el mercado exigen el desarrollo de numerosos productos que combinen, por un lado, novedad, y por otro, un proceso productivo eficiente y rápido, todo ello intentando minimizar los recursos empleados. Durante los últimos cuarenta años, las industrias han dedicado grandes esfuerzos a la mejora del proceso de producción como una vía prácticamente de supervivencia, sin embargo, en los últimos diez, los avances en este sentido han sido notablemente mayores. Estos avances se deben a que, apoyados en las tecnologías de información (IT), que a su vez han evolucionado exponencialmente, es posible generar y tratar inmensas cantidades de datos de forma muy eficaz, algo que era imposible con anterioridad. En este sentido, muchos han sido los avances realizados en diferentes ámbitos relacionados con el proceso productivo, como la logística, la automatización, el diseño y muchos otros, pero en este trabajo se tratará concretamente el avance en el campo de la secuenciación de operaciones. Este campo es crucial para el buen funcionamiento del proceso ya que está íntimamente relacionado con algunos de los recién mencionados. La fatiga y el deterioro de los equipos de trabajo provocan paradas en los sistemas de producción donde el tiempo de recuperación o puesta de nuevo en marcha no es siempre determinista. La recuperación de los sistemas puede en muchos casos emplear recursos no necesarios y aumentar los costes de producción innecesariamente. El tiempo de respuesta ante caídas o fallos del sistema de producción son aspectos a considerar y reducir sin descuidar el coste de la puesta en marcha o reestructuración del sistema o los tiempos de entrega del pedido al cliente. La planificación de tareas o secuenciación de operaciones forma parte del proceso de producción, normalmente se planifica la secuencia de tareas, el orden en que deben ejecutándose prevaleciendo las relaciones de precedencias, recursos disponibles o tiempo máximo de ejecución. Este tipo de problema ha sido trabajado detalladamente en la literatura convirtiéndose en un problema clásico de resolución. Una vez resuelto este problema la realidad del proceso productivo se centra en evitar paradas, es decir que las tareas no se detengan por fatiga, deterioro o paradas no planificadas. Este tipo de problema se enmarca en el ámbito del mantenimiento, diferenciando el mantenimiento preventivo vs mantenimiento correctivo. Las empresas emplean muchos recursos en el mantenimiento con el objetivo de evitar paradas no planificadas. Finalmente, el mantenimiento no implica que las paradas no previstas desaparezcan, por lo que es necesario que el sistema productivo se reconfigure siguiendo determinados criterios basado en diferentes objetivos. Este tipo de problema se le denomina Smart Ma unfacturing y en los últimos años está cobrando gran importancia con la integración de los conceptos de la industria 4.0. La literatura asociada a Smart Manufacturing describe diferentes procedimientos y métodos para resolver los problemas secuenciación ante paradas no esperadas. Los métodos de resolución describen algoritmos (mediante pseudocodigo) de reordenación de tareas donde se recoge el conocimiento de los métodos. Esta metodología de descripción de los métodos de resolución de problemas impide en muchos casos la posibilidad de comparar métodos de resolución ya que la implementación basada en pseudocódigo no permite una implementación común. El problema reside en disponer de las herramientas que describan dichos métodos de resolución de forma que la herramienta para su implementación sea independiente del método de descripción de los algoritmos. En los últimos años ha cobrado una gran importancia el uso de ontologías para describir el conocimiento y la interoperabilidad entre sistemas. Las ontologías permiten describir de forma general cualquier conocimiento. El siguiente trabajo aborda el problema de la secuenciación de operaciones inteligente, capaz de adaptarse de manera autónoma a las diferentes situaciones de la planta y los contratiempos en su correcto desarrollo. Hasta Diseño de meta-metamodelos para el modelado de entornos de Smart Manufacturing mediante técnicas de optimización 2 no hace mucho este problema se resolvía de manera estática, con un plan de producción maestro poco flexible que para nada se adapta a la situación real de todos los recursos necesarios. Este sistema ha quedado claramente obsoleto, por lo que es necesario facilitar la distribución y utilización de sistemas de secuenciación inteligente para continuar el desarrollo de la producción en aras de una mejor gestión de los recursos disponibles. Además en este trabajo se aborda la integración e interoperabilidad del conocimiento en el ámbito del problema de secuenciación inteligente para analizar las posibilidades de la estandarización, inteoperabilidad y gestión del conocimiento. 1.2 Objetivos Cuando se habla de sistemas de secuenciación inteligente, se habla de algoritmos de resolución de problemas de secuenciación. Existen una gran variedad de método de resolución considerando diferentes situaciones, cada uno de ellos con unas características concretas. La diversidad de métodos no se describe mediante una notación estándar que en muchos casos comparar diferentes métodos para el mismo problema depende de la interpretación de la solución como las estructuras de datos o procedimientos auxiliares que son descritos con poca precisión. El objetivo de este trabajo es la definición de un estándar para la definición y gestión que permita recoger el conocimiento que hay detrás de estos algoritmos, de manera que su comprensión y desarrollo sea más fácil. Un sistema que permita desglosar los procesos internos de cualquier algoritmo y que pueda reflejar las similitudes y diferencias entre ellos. El sistema desarrollado está basado en una ontología, sobre la que se sientan las bases de cómo representar cualquier algoritmo, esta ontología se implementa mediante el software Protégé. De esta forma se potencia la extensibilidad e interoperabilidad entre las diferentes formas de implementar los algoritmos, permitiendo trabajar conjuntamente a profesionales especializados en diferentes campos. El desarrollo del objetivo principal está compaginado con la aplicación a un problema clásico sobre Smart Manufacturing que permita analizar la viabilidad y estudiar la potencialidad de usar la gestión de conocimiento en la estandarización de problemas. El trabajo sigue la siguiente estructura: la sección 2 trata de la revisión de la literatura analizando el desarrollo histórico del problema de la secuenciación de operaciones, sus métodos de resolución y el estado actual de los sistemas de gestión de conocimiento en relación a dichos problemas, en la sección 3 se describen las técnicas y su aplicación para la creación de una ontología capaz de representar algoritmos inteligentes, aplicando esto a un algoritmo concreto, que es sometido a diferentes pruebas en la sección 4. Por último, en la sección 5 se analiza el resultado del trabajo y se explican las posibles extensiones que puede tener. 3 2 REVISIÓN DE LA LITERATURA ara la realización de este trabajo se estima oportuna una revisión de la literatura relacionada con ciertos conceptos clave a la hora de comprender y contextualizar el desarrollo del mismo. En la actualidad, es necesario que las empresas caminen en la dirección de optimizar sus procesos con el objetivo de convertirse en competitivas, no simplemente para la reducción de costes. Son muchos los agentes que intervienen, por ejemplo, en el ámbito productivo, por ello, es necesario dar soluciones que se basen en la fácil transmisión de información para resolver problemas de la mejor manera posible a nivel global de cada proyecto, es decir, en todas sus etapas. 2.1 La programación de operaciones en el ámbito de fabricación El ser humano siempre ha tenido la necesidad de fabricar objetos para facilitar las tareas de su vida. La historia de la manufactura comienza con el descubrimiento y la invención de los materiales y los procesos necesarios para fabricar objetos. Se tiene constancia del empleo de algunos procesos de fabricación, como la fundición, trabajo con martillo y rectificado, desde hace más de 6000 años. A lo largo de la historia estos procesos han evolucionado, y se han definido los sistemas de manufactura, formas de organizar a las personas y los equipos, para llevar a cabo las tareas de fabricación de manera más eficiente. Uno de los grandes avances en este campo fue la división del trabajo, asignar a cada trabajador o cada estación de trabajo una tarea concreta para agilizar y distribuir los centros de fabricación de una manera más eficiente. Este principio, aunque usado muchas veces con anterioridad, se le atribuye al economista Adam Smith (1723- 1790)[1] Posteriormente tuvieron lugar dos revoluciones industriales, la primera, aquella en la que la potencia de vapor reemplaza a la animal o la natural y la economía pasa de basarse en la agricultura y el oficio manual a hacerlo en la industria y la manufactura, y una segunda, que se caracteriza por pasar a producir en masa, un movimiento de la administración científica y la aparición de líneas de ensamblado, que introduce Henry Ford (1863-1947) en 1913, en su planta de Highland Park. Son muchos los problemas que han surgido para llevar a cabo todo este desarrollo, como pueden ser: el estudio de los movimientos, para intentar reducirlos, el estudio de tiempos, para establecer tiempos de trabajo para determinadas operaciones, el uso de estándares, para unificar un poco más la forma de trabajar de cada sistema o el uso de conjuntos de datos, para registrarlos y utilizarlos con el objetivo de mejorar la productividad. Entre todos los problemas surgidos en el desarrollo de los sistemas de fabricación hay que resaltar uno en especial para el desarrollo de este trabajo: el scheduling. La palabra scheduling puede traducirse a nuestro idioma como programación, planificación u organización. En el campo de la fabricación, la planificación de procesos es el término más común para referirse al scheduling, que puede definirse como la secuenciación de operaciones necesarias para la consecución de un objetivo, limitada por los recursos disponibles y sujeta a una serie de restricciones determinadas por numerosos factores. El problema del scheduling no es algo nuevo[2]; las pirámides se construyeron hace más de 3000 años, y ya entonces Sun Tzu ya hablaba de organización y estrategia hace unos 2500 años desde un punto de vista militar. Las rutas de comercio transoceánicas llevan existiendo más de 300 años. Ninguna de estas actividades podría haber sido realizada sin alguna programación o planificación previa. P Diseño de meta-metamodelos para el modelado de entornos de Smart Manufacturing mediante técnicas de optimización 4 Figura 1. Línea temporal de la historia del scheduling [3] En la figura anterior puede observarse una línea temporal con los grandes hitos en el campo de la secuenciación de operaciones. Pueden verse algunos avances que aún tienen cabida hoy en día como los diagramas de Gantt, los diagramas PERT o la gestión de proyectos por cadena crítica. El scheduling surge de la necesidad de organizar las operaciones de un proceso productivo para transformar unas materias primas en un producto final, basándose en un diseño previo que ha de satisfacer. En este caso los procesos estarán limitados, no solo por las materias primas disponibles, sino por las características de la fábrica, como el estado actual de la misma o la capacidad de la mano de obra que en ella opera. 2.1.1 Introducción al problema de scheduling En el ámbito de la fabricación[4], el plan de procesos permite transformar unas materias primas en un producto final, basándose en un diseño previo que debe satisfacer. En este caso los procesos estarán limitados, no solo por las materias primas disponibles, sino por las características de la fábrica, como el estado actual de la misma o la capacidad de la mano de obra o maquinaria que en ella opera. Una serie de propiedades del problema de planificación de procesos impondrán unas restricciones que servirán, posteriormente, para modelarlo y tratar de resolverlo con la máxima eficiencia posible[5]. Cada uno de los siguientes componentes tendrá asociados una serie de valores y atributos que los definirán por completo. Un problema de este tipo suele tener los mismos objetivos, atendiendo a cuestiones lógicas, y suponiendo el funcionamiento normal de un sistema: minimizar los recursos utilizados para completar las tareas necesarias para llevar a cabo la producción en marcha. Estos recursos incluyen tanto capacidad, como materias primas y tiempo. Algunos de los objetivos que persiguen son: fabricar todos los productos con la mínima cantidad de retrasos posible, minimizar el tiempo entre operaciones o llevar al mínimo la cantidad de mano de obra necesaria. Por otro lado, las características del trabajo u operación a realizar determinan qué procesos, y en qué orden, hay que utilizar las materias primas para la confección del producto final. Un ejemplo de estas peculiaridades puede ser su fecha de entrega, así como su prioridad o la capacidad del producto para agruparse por lotes. Otro factor para tener en cuenta a la hora de modelar y tratar de resolver cualquier problema de planificación será la gestión de recursos, que pueden definirse como la materia prima, infraestructura y mano de obra necesarias para la confección de un producto. La disponibilidad de estos recursos condicionará de manera dinámica el estado de nuestro problema. El producto final es el resultado del proceso de manufactura, requiere una serie de recursos para su fabricación, y de su estado, en todo momento, depende la orientación del proceso productivo. La precedencia impuesta por las características del proceso productivo, más en concreto entre las actividades que lo componen, para la realización de este, jugará también un papel clave a la hora de la resolución. 2. Revisión de la literatura 5 Figura 2. Componentes de un problema de scheduling [6] En este problema se consideran dos subfunciones de la programación de operaciones: la secuenciación y la temporización. Generalmente se considera el problema del taller (job-shop) como el prototipo de esta clase de problemas y su enunciado es el siguiente[7]: “n piezas (lotes de piezas, pedidos u órdenes de trabajo) deben realizarse en m máquinas (recursos, secciones, puestos de trabajo). La realización de cada pieza implica la ejecución, en cierto orden establecido, de una serie de operaciones prefijadas donde cada operación está asignada a una de las m máquinas y tiene una duración (tiempo de proceso) determinada y conocida; debe establecerse un programa, es decir, la secuencia de operaciones en cada máquina y el intervalo temporal de ejecución de las operaciones, con el objetivo de optimizar un índice determinado que mide la eficiencia del programa.” Para simplificar la nomenclatura de todos estos términos se hablará indistintamente de máquinas, estaciones o células de producción como aquellos recursos que tienen la capacidad de realizar una serie de trabajos sobre el producto, aunque podrá variar qué trabajos y a qué velocidad pueden completarlos. Se dejarán aparte, por tanto, los detalles técnicos de cada estación, así como el factor de si necesitan mano de obra o no. 2.1.2 Tipos de problemas de programación de operaciones (Schedulling) Estas son las principales configuraciones productivas en las que se pueden simplificar la gran mayoría de problemas de programación de operaciones: • Una máquina (single machine) Se trata de la configuración más sencilla, está conformada por una única máquina o estación que realiza solo una operación. De esta manera, esta máquina realizará todos los trabajos que haya que secuenciar. Dado un problema con n trabajos habrá 𝑛! posibles soluciones. La solución de un problema de este tipo será la secuencia de trabajos según el orden en que deben ser procesados. Pese a ser una configuración simple, podría parecer que Diseño de meta-metamodelos para el modelado de entornos de Smart Manufacturing mediante técnicas de optimización 6 la resolución de este tipo de problemas no supone un gran problema. Sin embargo, la incorporación y combinación de ciertas restricciones y ciertos objetivos pueden suponer una gran dificultad. Por ejemplo, Biskup[8] demuestra que puede resolverse el problema de single machine, incluyendo la capacidad de aprendizaje de una estación de trabajo, de manera polinomial y atendiendo a dos objetivos al mismo tiempo: minimizando la desviación de las fechas de vencimiento de los pedidos y, a la vez, minimizando la suma del tiempo que los trabajos se encuentran en la estación. • Máquinas en paralelo (parallel machine) En este caso se dispone de m máquinas que trabajan al mismo tiempo, pero el proceso productivo se reduce a una única operación que puede ser realizada en cualquier estación. Según la eficiencia relativa de las máquinas existen diferentes variantes: - Máquinas idénticas: todas las máquinas tardan lo mismo en realizar las mismas tareas. - Máquinas uniformes: cada estación lleva asociado un factor de velocidad que define lo rápido que trabaja respecto a otras. - Máquinas diferentes: los tiempos de procesado de cada máquina pueden ser completamente arbitrarios. Una máquina puede ser muy rápida para una tarea, pero lenta para otra. Figura 3. Esquema de un problema con m máquinas en paralelo [9] Para m máquinas y n trabajos existirán (𝑛+𝑚−1 𝑛)𝑛! soluciones, que estarán formadas por una secuencia de trabajos ordenados para cada máquina. • Flowshop Este es uno de los problemas más estudiados en el campo del scheduling. En este caso hay que procesar un conjunto de n piezas que han de pasar por m estaciones, cada una de las cuales estará formada por una sola máquina. Existirá una única ruta de producción recorriendo las m estaciones que cada pieza deberá seguir, no pudiendo ser procesada más de una vez por estación. La duración de cada operación quedará definida por 𝑝𝑖𝑗, donde i hará referencia a la pieza y j indicará la máquina, por lo tanto, podrá variar el tiempo de realización de cada operación dependiendo de cada pieza y la máquina en que se realiza. 2. Revisión de la literatura 7 Figura 4. Representación de un problema de tipo flowshop [10] El número de posibles soluciones sería (𝑛!)𝑚 en caso de dar una secuencia para cada máquina. La cantidad de soluciones quedará reducida a 𝑛! imponiendo una misma secuencia para todas las máquinas, que sería la solución del problema. • Taller (job shop) Partiendo del caso anterior, es un entorno de tipo job shop cuando se elimina la restricción de una única secuencia para todas las máquinas. Ahora cada pieza seguirá su propia ruta recorriendo las máquinas, pero no tendrán que pasar por todas ellas de manera obligatoria. Figura 5. Representación de un problema de job shop En este caso si existirán (𝑛!)𝑚 posibles soluciones y, en este caso, para obtener un programa que solucione el problema, será necesaria una secuencia de trabajos para cada máquina. En la práctica muchas veces se simplifica dando una sola secuencia S de n x m elementos en el que cada trabajo aparece m veces, se seleccionan los elementos de la secuencia S y se van asignando a la máquina que está indicada en su ruta. 2.1.3 Representación Para describir los problemas de scheduling se suele utilizar la nomenclatura de Lawler [11] que recoge el enunciado o la situación propuesta mediante tres factores: 𝜶|𝜷|𝜸 • 𝜶 hace referencia al entorno en el que se desarrolla el problema, estará formado por un elemento, por ejemplo: Diseño de meta-metamodelos para el modelado de entornos de Smart Manufacturing mediante técnicas de optimización 8 o 1, single machine o P, parallel machine o F, flow-shop • 𝜷: define las características del problema en sí, puede contener una o varias inscripciones. Algunos ejemplos: o Sij, tiempo de preparación de la máquina i antes de procesar el trabajo j o Batch(b), las máquinas pueden procesar a la vez, como mucho, b trabajos o Pij=p, tiempo de procesamiento constante de p unidades temporales o Prec, existen relaciones de precedencia entre los trabajos, es decir, algunos trabajos no podrán comenzarse hasta que no se terminen otros. Esta condición debe acompañarse de las relaciones de precedencia que hay que cumplir. • 𝜸: este último campo indica cuál es la función objetivo, esto es, cómo se medirá la eficiencia de cada solución. Los valores para medir la eficiencia de manera clásica son: o ∑𝐶𝑗 tiempo total de finalización de los trabajos o ∑𝐹 𝑗 tiempo total que los trabajos están en proceso o ∑𝑈𝑗 total de trabajos que finalizan fuera de su plazo de entrega Una forma de priorizar aquellos trabajos que sean más importantes que otros es añadiendo un factor de peso, wj. Al introducir este factor en el objetivo del problema, se conseguirá priorizar trabajos atendiendo a los objetivos del sistema productivo. Estas son sólo algunas de las opciones para cada uno de los campos, pero, como se puede ver, se pueden combinar entre ellas dando lugar a numerosos problemas de scheduling que pueden adaptar un problema real a una notación breve y simple. Un ejemplo de un problema completo para una sola máquina con fechas de llegada de los pedidos en el que se intenta minimizar el momento de finalización del último trabajo sería: 1 | rj | Cmax Los grafos han sido otra de las técnicas empleadas para la representación de problemas de Schedulling, un grafo está compuesto por un conjunto de vértices y arcos dirigidos, los vértices representan trabajo y los arcos las relaciones de precedencias. Esta representación casa con el campo 𝜷, normalmente, en entornos reales, existen relaciones de precedencia entre los trabajos. Por ello es habitual representar la distribución del proceso productivo mediante grafos de precedencia. Un grafo de precedencia puede ser definido como un grafo acíclico y dirigido donde cada nodo representará una máquina y las aristas indican la precedencia. Para que un trabajo esté completo tendrá que recorrer este grafo según indique su ruta. 2. Revisión de la literatura 9 Figura 6. [12]Red de tareas para un lote de n productos [12] De esta manera puede verse, muy gráficamente, la ruta que los trabajos deberán seguir. Como puede observarse en la figura anterior [12], en la que cada nodo representa una tarea asociada a la producción de alguno de los productos y cada flecha que las une indica la tarea que puede ser realizada a continuación. Esta representación es especialmente útil para analizar el proceso productivo de un vistazo y poder evitar posibles cuellos de botella o plantear alguna redistribución de la planta para optimizar el proceso. 2.2 Resolución del problema de scheduling Una vez planteado el problema y sus características será necesario buscar la mejor solución posible que se ajuste a los requisitos planteados. Esta no será más que un programa que indique la actividad de cada máquina en un horizonte temporal indicando qué tareas de qué trabajo se realizarán en cada momento, definiendo así el funcionamiento del sistema de fabricación. Una forma sencilla de representar esta planificación son los diagramas de Gantt, una herramienta propuesta a comienzos del siglo XX, que revoluciona la gestión de proyectos, y puede ser utilizada en muchos ámbitos, pero en nuestro caso estará compuesto por dos ejes, el horizontal para indicar unidades de tiempo y el vertical para indicar trabajos o máquinas, de lo cual dependerá la orientación del diagrama. En la siguiente figura [13] puede observarse el ejemplo de un diagrama de Gantt con ambas orientacionesHaga clic o pulse aquí para escribir texto., en el primer caso (a) orientado a máquinas y en el segundo (b) orientado a trabajos: Figura 7. Diagramas de Gant con diferentes orientaciones [13] El número de programas que se pueden crear para un problema de scheduling es muy elevado, por ello, se clasifican en tres tipos: semi-activos, activos y sin retrasos. Para definir cada tipo de programa, se parte de la base de que todos ellos son factibles, que se pueden llevar a cabo físicamente. Diseño de meta-metamodelos para el modelado de entornos de Smart Manufacturing mediante técnicas de optimización 16 Figura 14. Modelo conceptual de un algoritmo predictivo-reactivo basado en maching learning y modelos de simulación [28] 2.4 Gestión del conocimiento en sistemas de fabricación La manera tradicional de enfocar los flujos de información en un proceso productivo se basa en la utilización de un solo esquema común, normalmente muy rígido, y centrado en el producto. Está demostrado que esta manera de compartir la información necesaria a lo largo del ciclo de vida del producto, formado por muchas etapas muy diferenciadas, da lugar a problemas [29], ya que los diferentes ingenieros que trabajen en el diseño y la implementación de este sistema pueden estar interesados en aspectos concretos de toda esta información, que es difícil de transmitir y decodificar. A esto se le suma la capacidad actual de cualquier fábrica para generar datos de cualquier producción que lleve a cabo, lo cual desborda cualquier modo tradicional de gestionar toda esta información. Con los avances tecnológicos aumenta el tamaño de la información que se recoge, y con ello, debe adaptarse también la manera en que se gestiona: desde su generación hasta la manera en que se interpreta para tomar decisiones. Desde comienzo de los 90s se habla de gestión del conocimiento, que es el conjunto de actividades que permiten la creación, almacenamiento, distribución y aplicación del conocimiento generado por una organización y las personas que la forman [30]. Pero es en los últimos tiempos, con la evolución de la llamada industria 4.0, cuando la gestión del conocimiento se convierte en un factor que puede suponer una ventaja competitiva en el mercado. Por ejemplo, Yan Lu [31], presenta un método de gestión del conocimiento aplicado a la fabricación aditiva, que abarca prácticamente toda la información necesaria para el desarrollar productos de esta manera, como el proceso de selección de materia, el control in-situ del proceso, diseño de la estructura… En base a esto se propone un entorno de trabajo de cuatro rangos, en el que el conocimiento fluye del nivel inferior al superior y los objetivos se definen automáticamente de manera inversa para mejorar el rendimiento del proceso con la información que se va generando. Este es un ejemplo de implementación de gestión del conocimiento a un proceso productivo muy concreto, pero en ingeniería son muchas las líneas de investigación que hay abiertas en campos como diseño de procesos, diseño de productos, producción, diseño de sistemas y muchos otros. Para este trabajo el foco estará puesto en el campo de la secuenciación inteligente de operaciones en el contexto antes indicado, es decir, el smart scheduling. 2.4.1 Introducción a la gestión del conocimiento Como ya se ha comentado, la revolución tecnológica que se ha venido mencionando, ha dado lugar a un cambio de paradigma en la sociedad. Se dice que se ha pasado de la era de la información a la era del conocimiento. Hasta ahora se encontraba valor en el volumen, cantidad y calidad de datos, sin embargo, de un tiempo a esta parte no solo basta con acumular esta información, si no de qué manera se genera, almacena e interactúa con ella, esto es, la gestión que se realiza de ese conocimiento. 2. Revisión de la literatura 17 De esta manera, el conocimiento adquirido permite solucionar problemas basándose en la experiencia acumulada por una fábrica, una empresa o cualquier tipo de organización. Es por ello por lo que el conocimiento se convierte en una posesión valiosísima que puede tornarse en un elemento estratégico para generar valor diferencial respecto al resto de competidores. La gestión del conocimiento recoge cuatro actividades principales: • Reunir el conocimiento: la adquisición y recolección del conocimiento generado para su posterior utilización. • Estructurar y organizar el conocimiento: es necesario imponer una división y estructura en el conocimiento recogido, más aún cuando el volumen que se maneja es grande. • Refinar el conocimiento: corregir, actualizar, añadir o eliminar conocimiento son tareas que deben realizarse de manera sistemática para que la gestión del conocimiento sea efectiva a lo largo del tiempo. • Distribuir el conocimiento: llevar a cada profesional la información precisa que necesita es el fin último de la gestión del conocimiento. Para entender mejor esta tarea se parte de una definición de G. Probst [32] de qué es el conocimiento: El conocimiento que es todo el conjunto de cogniciones y habilidades con los cuales los individuos suelen solucionar problemas, comprende tanto la teoría como la práctica, las reglas cotidianas al igual que las instrucciones para la acción, el conocimiento se basa en datos e información, pero a diferencia de éstos siempre está ligado a las personas; forma parte integral de los individuos y representa las creencias de éstos acerca de las relaciones causales. En base a esta definición rápidamente se infiere que el conocimiento no es un producto en sí mismo, ni algo que las empresas puedan comprar. El conocimiento se encuentra en el interior de las personas que forman parte del proceso, que puede abarcar tanto aspectos técnicos o de funcionamiento, como aspectos sociales para su funcionamiento. Cuando se intenta poner el conocimiento acumulado por una persona en algún tipo de base de datos, lo que se intenta realmente es dejarlo reflejado para que, en cualquier otro lugar, pueda ser recogido por cualquier persona y, de esa manera, transmitirlo en el tiempo. [33] 2.4.2 Análisis semántico para la gestión del conocimiento Llega la hora de decidir de qué manera se va a reflejar el conocimiento en una base de datos, qué métodos se usarán para unificar todos los campos que intervienen en la actividad de la cual se quiere recoger el conocimiento que la empresa posee. Aparece entonces el concepto de gestión semántica del conocimiento, que puede definirse como: “un conjunto de prácticas que busca clasificar el contenido, para que el conocimiento que contiene sea accesible y transformado de manera inmediata para su entrega a la audiencia deseada, en el formato requerido.” [34] Como puede observarse esta definición encaja perfectamente con los requerimientos que se exponían, en las secciones anteriores, para un sistema de gestión del conocimiento. Numerosos artículos relacionados con la gestión semántica del conocimiento muestran una tendencia general del uso del concepto de ontología, a través del Web Ontology Language (OWL). Este lenguaje de construye sobre RDF (Resource Description Framework), un modelo de datos para metadatos que sirve para la descripción conceptual y el modelado de la información implementado en recursos web. El OWL se codifica en XML (eXtensivle Markup Language), un lenguaje que permite definir lenguajes de marcas que da soporte a bases de datos, y todo esto bajo el amparo del World Wide Web Consortium (W3C). El concepto de ontología nace en el ámbito de la filosofía, y trata de explorar la existencia de las cosas mediante sus propiedades y relaciones, creando así relaciones entre conceptos particulares y universales. Desde mediados de los setenta comienza la investigación en el campo de la inteligencia artificial, lo que impulsa la investigación en el campo de las ontologías como modelos computacionales que permiten cierto grado de razonamiento automático. No sería hasta la siguiente década, cuando el término ontología comenzaría a ser acogido, por la comunidad investigadora, como un componente de los sistemas de gestión del conocimiento. Posteriormente, este concepto es relacionado con la ciencia computacional en el marco de las redes semánticas. En el campo de la fabricación se encuentran numerosas aportaciones en esta materia. Felic A. [35], propone una semántica orientada a procesos para la gestión del conocimiento a lo largo de todo el ciclo de vida del producto Diseño de meta-metamodelos para el modelado de entornos de Smart Manufacturing mediante técnicas de optimización 18 con el objetivo de mejorar la transmisión de información entre modelos de subproductos o diferentes procesos dentro de la fabricación. De esta manera se utiliza una semántica centrada en los procesos, que permite a los expertos de cada punto del ciclo de vida del producto acceder a la información que necesitan para reducir costes y tiempos en todo el proceso. En la misma línea, Szejka [36] propone una reconciliación mediante la semántica de los flujos de información entre los campos de diseño y fabricación del producto, explicando todo el proceso de intercambio de información desde unas ontologías de base, formando relaciones entre los dominios de cada una para crear vínculos a nivel semántico que mejoren la transmisión de información, es decir, la interoperabilidad. 2.4.3 Ontologías aplicadas al scheduling y smart scheduling Llegado el momento de buscar alguna ontología relacionada con la secuenciación, y más en concreto con la secuenciación de operaciones en el ámbito de la fabricación, encontramos algunos ejemplos de ontologías genéricas para representar sistemas de este tipo, cada una de las cuales haciendo énfasis en algún aspecto concreto. Stephen [5], en 1997, crea su ontología denominada OZONE, una herramienta para configurar sistemas de secuenciación basados en restricciones y crear modelos útiles en diferentes campos como el de la fabricación o el transporte. Figura 15. Simplificación del dominio de la ontología OZONE En la figura 15, la ontología se centra en cuatro conceptos básicos: las actividades, los productos, los recursos y la demanda, todos ellos conectados por las restricciones, eje central de esta ontología ya que condiciona y determina la secuenciación de las operaciones de fabricación. Posteriormente, Stephen, amplía pormenorizado cada uno de estos conceptos definiéndolos y explicando sus propiedades y relaciones. Rajpathak [37], por su parte, plantea otro ejemplo de ontología genérica para aplicaciones de secuenciación de operaciones para la fabricación, sin embargo, el eje central de esta son las secuencias. 2. Revisión de la literatura 19 Figura 16. Modelo de la estructura de la ontología propuesta por Rajpathak Como se ve en la figura 16, ya se incluyen algunos conceptos mencionados en las secciones 2.1 y 2.2 como son: la función de coste o función objetivo, la preferencia. Por otro lado, las restricciones, en este caso, se dividen en fuertes y débiles, algo muy útil a la hora de aplicar ciertos algoritmos. Figura 17. Diagrama de relaciones de clases en la ontología propuesta por Rajpathak Las relaciones definidas por Rajpathak (figura 17) conectan las clases que conforman la ontología. En este esquema es mucho más visible cómo la secuencia está en el centro de toda la ontología, todas las demás clases se relacionan de alguna manera con ella para ir conformándola. Esta ontología se aproxima algo más al objetivo del trabajo, ya que incluye conceptos y relaciones clave a la hora de representar ciertos algoritmos de resolución, por ejemplo, los trabajos ya asignados y sin asignar o la optimalidad y viabilidad de una secuencia ya dada. Como se ha visto, existen ontologías dedicadas a la creación de aplicaciones para la resolución de problemas de Diseño de meta-metamodelos para el modelado de entornos de Smart Manufacturing mediante técnicas de optimización 20 secuenciación, sin embargo, no existen aquellas que recojan los conceptos necesarios para la representación de algoritmos inteligentes o de smart Scheduling. Se observa en todas las ontologías revisadas, una falta de clases que expresen el estado actual de la fabricación y puedan representar la capacidad de la solución de adaptarse a dichas condiciones. Por otro lado, ninguna de estas ontologías ofrece una representación estandarizada de los métodos de resolución empleados para establecer una comparación entre ellos. De igual manera, no se descomponen en la ontología dichos métodos para poder compararlos entre ellos, comparar partes de ellos o relacionarlos con otros para su implementación posterior. 21 3 DISEÑO DE UN SISTEMA DE CONOCIMIENTO INTEROPERABLE PARA SMART SCHEDULING na vez introducidas las ontologías como el método escogido para la representación del conocimiento en el ámbito que se quiere abarcar, es decir, los algoritmos inteligentes para la resolución de problemas de secuenciación de operaciones en un entorno real, es necesaria una explicación de cómo es una ontología y cómo se crea. Se utilizará un ejemplo sencillo para introducir el programa escogido y, posteriormente, se modelará un algoritmo concreto similar a los anteriormente expuestos. 3.1 Introducción a las técnicas de diseño de ontologías No existe una única y correcta metodología para la creación y el desarrollo de metodologías, por ello se opta por basarse en ciertos principios fundamentales. El primero ya ha sido mencionado: no existe una manera correcta o absoluta de modelar un problema, dependerá de muchos factores como el área de conocimiento que se quiere representar o de la cantidad de información de la que se dispone. Otra idea fundamental en la que apoyarse es que el proceso de desarrollo de una ontología es iterativo, no se crea una ontología en su forma final, sino que va mutando a medida que se va ampliando, extendiendo y corrigiendo. Un primer paso fundamental es definir el dominio y el alcance de la ontología, qué abarcará y con qué profundidad, ya que de ello depende el enfoque que se le dará a posteriores pasos. Es común clasificar las ontologías según su nivel de profundización en el tema, dando lugar a distintos tipos, como son: • Ontologías de dominio. Abarcan conocimiento de un campo concreto, por ejemplo, electrónica, mecánica o aerodinámica. Dentro de este tipo de ontologías pueden encontrarse distintos grados de profundización, siendo algunas de ellas muy especializadas. • Ontologías basadas en metadatos. Ofrecen un vocabulario para describir el contenido de las fuentes basadas en la World Wide Web. • Ontologías representacionales. Están basadas en entidades representacionales que no establecen qué debe ser representado. Definen un marco para la representación del conocimiento orientado a objetos. El editor Protégé, que posteriormente será tratado, utiliza este modelo. • Ontologías genéricas o de nivel alto. Capturan conocimientos generales que pueden ser aplicados en diferentes dominios o ámbitos del conocimiento. • Ontologías metodológicas. Representan técnicas de resolución de ciertos problemas o procedimientos para la realización de determinadas tareas concretas. Para determinar el dominio y el alcance es muy útil realizar una lista de preguntas a las que la ontología sea capaz de dar respuesta. Otra consideración importante será la búsqueda de ontologías existentes que puedan ampliarse o adaptarse para dar cobertura al conocimiento que se quiere representar. Existen numerosas librerías reutilizables como la DAML ontology o Ontolingua ontology. Para continuar con este desarrollo es necesario conocer los elementos que forman parte de una ontología. Los principales son: • Clases. Elementos principales de la ontología. Representan conceptos, tipos o conjuntos de objetos. Existen subclases, que estarán recogidas dentro de una clase padre. U Diseño de meta-metamodelos para el modelado de entornos de Smart Manufacturing mediante técnicas de optimización • Individuos. También conocidos como instancias, son la unidad básica de una ontología, modelan objetos concretos pertenecientes a una clase. Se puede crear una ontología sin ningún individuo, pero normalmente la clasificación y estudio de relaciones entre estos es el objetivo de la creación de un modelo de este tipo. • Relaciones. Son enlaces entre clases o individuos, forman la estructura de la ontología. Normalmente pueden definirse tipos de relaciones. • Atributos. Propiedades, características o parámetros que definen un individuo, aunque no siempre es así, ya que los atributos deben responder a un tipo de atributo y un formato, por ejemplo, un individuo de la clase persona puede tener un atributo de tipo nombre, que será una cadena de caracteres. • Axiomas o restricciones. Son las reglas lógicas que deben cumplir todas las relaciones que existen entre los elementos de la ontología. Darán sentido y forma al conocimiento que se recoge. Una vez conocidos los principales elementos que forman una ontología un siguiente paso lleva a realizar una lista de elementos, conceptos o ideas que ésta debe recoger o representar. Esto puede ayudar a la hora de definir las clases y su jerarquía (clases madre y clases hija). Para esta jerarquización existen varios enfoques: de abajo hacia arriba (se comienza definiendo las clases más específicas y se avanza hacia las más generales) de arriba hacia abajo (sentido inverso al anterior) o por último, una combinación de ambos enfoques para cubrir todo el conocimiento que se quiera recoger. Posteriormente habría que especificar los tipos de atributos con su formato siempre que sean necesarios para definir algún aspecto de los individuos para, finalmente, instanciar la ontología, añadir todos los individuos de cada clase que se quiera y así, se puedan incluir para ir rellenando el modelo. Para entender todos estos procedimientos mejor, se observa el ejemplo de la figura 18, una pequeña jerarquía de clases instanciada, aunque en la realidad las ontologías son mucho más extensas y complejas. Figura 18. Ejemplo de jerarquía de clases para libros En el ejemplo se observa una clase superior, “libros”, de la que penden dos subclases: “libros para niños” y “novelas”. Dentro de cada subclase existen dos instancias, cuyo nombre se corresponde con el título de la obra que representan. Hay dos tipos de atributos: “género” y “autor”, cuyo formato será una cadena de caracteres. Se puede suponer un escenario en el que se quiere utilizar una ontología para recoger las obras de un listado, en este caso de cuatro títulos. Para la creación de clases se podría primero agrupar por pares en libros para niños y novelas, para posteriormente crear una clase superior llamada “libros” que recoja a todas (enfoque de abajo hacia arriba). Otra opción sería partir de la clase “libros”, que recogerá todos los títulos y de ahí se ramifica hasta obtener el mismo resultado (enfoque de arriba hacia abajo). El último paso sería rellenar todos los datos correspondientes a los atributos, que pueden ser tantos como sean necesarios para cada instancia, en este caso son solo dos, pero podrían incluirse otros muchos como el número de ediciones, el año de publicación o incluso el número de páginas. 3. Diseño de un sistema de conocimiento interoperable para Smart schedulling 3.2 Software de diseño de ontologías Son varios los programas centrados o que pueden usarse para el diseño de ontologías, aportando cada uno de ellos características particulares respecto al resto. Algunos de los más utilizados son SWOOP, NeOn Toolkit o Enterprise Architect, pero para la realización de este trabajo se ha decidido escoger Protégé, programa desarrollado por el Stanford Center for Biomedical Informatics Research en la Stanford University School of Medicine. Este programa presenta un entorno colaborativo con una comunidad bastante activa que ayuda al desarrollo de ontologías, trabajando con el OWL (Web Onology Language) en el marco de los protocolos W3 (World Wide Web) para compartir el conocimiento acumulado. Protégé es un programa bastante intuitivo a la hora de diseñar y trabajar con ontologías. En este apartado se presenta un ejemplo de la creación de una ontología que, posteriormente servirá para acoger el objetivo principal del trabajo. En el caso de uso que se presenta a continuación se tratará de representar el algoritmo SPT (shortest processing time) para la secuenciación de un listado de tareas en un entorno de single machine, un algoritmo sencillo para priorizar aquellas tareas con un tiempo de procesamiento menor. Los trabajos van llegando y, si la máquina está ocupada, quedan en cola. Cuando la máquina queda libre realiza el trabajo con un tiempo de procesamiento mas corto de los que haya en la cola. Este algoritmo ofrece soluciones óptimas para minimizar el tiempo de procesamiento total siempre que no esté ponderado. Para la creación de un nuevo proyecto en Protégé se comienza pulsando el botón File>New… para posteriormente encontrar lo siguiente: Figura 19. Creación de una ontología en Protégé Como se observa en la figura anterior, al abrir un nuevo proyecto de una ontología, el programa crea un enlace (Ontology IRI) que permite a otros usuarios acceder a la ontología para ampliarla y compartirla. El primer paso, como se indicaba en el anterior punto, es determinar el alcance y el dominio de la ontología, que en este caso se centrará en los algoritmos de resolución, basándose en qué problemas debe resolver y de qué manera. El pseudocódigo seguido para el ejemplo es el siguiente, pero para comprenderlo es necesario aclarar que todos los trabajos estarán incluidos en una lista de tareas, aunque también existirá otra lista destinada a las tareas en espera, inicialmente vacia. Cada uno de estos trabajos contarán con una serie de valores asociados como su instante de llegada o su tiempo de procesamiento entre otros. Diseño de meta-metamodelos para el modelado de entornos de Smart Manufacturing mediante técnicas de optimización tiempo=0; Lista_tareas_espera=Lista_tareas_primer_elemento <-Elimina de la lista de tareas el elemento que saca. i<-0 While (Lista_tareas_espera!= Vacio) do { Trabajo=Lista_tareas_espera.Primer_elemento() trabajo.Inicio=t trabajo.Fin=Trabajo.Inicio+trabajo.Duración Orden_ejecucion=i If (t<Trabajo.Instante_llegada) { t=Trabajo.Instante_llegada trabajo.Restraso=0 { If not {trabajo.Restraso=t-Trabajo.instante_llegada} End if } t=trabajo.Fin Añadir_lista_tareas_espera (t,Lista_tareas) i= i+1 Fin Mientras Pseudocódigo de Shortest Path problem Definición de clases Como se ve, son varios los elementos que intervienen a la hora de definir un algoritmo de este tipo. En la siguiente lista se recogen las diferentes clases padre que se han definido: • Algoritmos. Una clase que recoge los distintos algoritmos que se incluyan en la ontología. • Funciones. Serán los elementos que conformen los algortimos, una misma clase puede servir de igual manera para dos algoritmos, describiéndose por tanto en la ontología de manera aislada, aunque se relacionen con otros elementos (funciones, variables…) • Condiciones. Se utilizarán en todo momento que sea necesario comprobar el estado del sistema o de una variable en concreto comparándola con otro valor. • Listas. Estarán compuestas por trabajos y son equivalentes a vectores. • Operaciones básicas. En ellas se incluirán todas las operaciones básicas que pueden desarrollarse dentro de una función, en ellas se encuentran suma, resta o asignación. Pertenecen a un nivel inferior a las funciones. • Trabajos. Elemento básico común a todos los algoritmos. De manera genérica son elementos comunes a todos los problemas, sin embargo, la ontología será capaz e discernir cuáles pertenecen a cada 3. Diseño de un sistema de conocimiento interoperable para Smart schedulling problema concreto. • Variables. Serán utilizadas como recursos para el correcto desarrollo de las funciones , operaciones básicas, condiciones o funciones. Para añadirlas a la ontología que se está creando el siguiente paso es clickar en la pestaña Entities>Classes. Se puede observar que al crear una nueva ontología ya existe una clase que el propio programa crea de manera automática y de la que penderán todas las que se añadan, esta clase se llama “Thing”. Figura 20. Adición de clases en Protégé A partir de esta clase “Thing”, que será la más alta en la jerarquía se irán añadiendo nuevas clases utilizando los botones señalados en la figura anterior. El primero por la izquierda añadirá la nueva clase en un nivel inferior a la marcada, el otro la añadirá al mismo nivel. Al pulsar cualquiera de estos, una ventana pedirá nombrar la nueva clase y a la derecha aparecerán los menús de la siguiente figura. Figura 21. Propiedades de una clase en Protégé Como se puede ver en el recuadro “Annotations”, es posible añadir una pequeña descripción mediante texto para la clase creada. En el inferior, “Description”, se encuentran diferentes opciones para añadir distintas propiedades o axiomas para definir aún más las clases siempre que sea necesario. Por ejemplo “SubClass Of” permite enlazar dos clases creando una relación madre-hija entre ellas. Una vez creadas esta clases principales o superiores, a continuación, se va a analizar el caso concreto del ejemplo para determinar que subclases serán necesarias crear. • Algoritmos: parece claro que se necesitará una subclase para el algoritmo concreto del ejemplo, a la que se llamará “Algoritmo SPT”. • Funciones: principalmente tres funciones son las usadas en este algoritmo “IF”, “WHILE” y una concreta llamada “Añadir lista tareas espera”, a la que se le pasan dos variables, el tiempo y una lista de Diseño de meta-metamodelos para el modelado de entornos de Smart Manufacturing mediante técnicas de optimización Figura 29. Creación de una instancia en Protégé Pulsando en el botón señalado en la imagen anterior se abrirá una ventana que pide el nombre del nuevo individuo, como en el resto de los elementos. Figura 30. Propiedades de una instancia en Protégé A continuación, como se puede ver vuelven a aparecer tres apartados: - “Annotations” igual al de las entidades, atributos y relaciones - “Description” que contiene tres opciones: “Types” para indicar a que clase pertenece el individuo, puede ser una o varias, “Same Individual As” y “Different Individuals” que, como su propio nombre indica, sirven para expresar que dos individuos son iguales o diferentes entre sí. - “Property assertions” ofrece cuatro botones que permitirán hacer efectivas las relaciones existentes en la ontología y dotar de atributos al individuo seleccionado. Al pulsar en Object property assertions una ventana pedirá qué object property (relación) se quiere hacer efectiva y con qué individuo Figura 31. Unión de dos individuos mediante una relación en Protégé De la misma manera al pulsar en Data property assertions se hará posible dotar de atributos al indiviuo, para ello será necesario seleccionar el tipo de atributo que se le quiere dar y qué valor tomará dicho atributo. 3. Diseño de un sistema de conocimiento interoperable para Smart schedulling Figura 32. Adición de un atributo a un individuo en Protégé Es preciso aclarar que para la instanciación del ejemplo se pretende representar el algoritmo de resolución, no la resolución de un problema concreto, por ello cada acción que se ejecute en el algoritmo tendrá su propia instancia. Por ejemplo, cada bucle WHILE tendrá una instancia que se relacionará mediante “Analiza” con una instancia de tipo condición, que a su vez se relacionará con dos variables comparándolas mediante “Compara”. Figura 33. Instancia para una función de tipo “WHILE” del ejemplo Figura 34. Instancia para una condición del ejemplo Esta condición puede cumplirse o no cumplirse, lo que se modela mediante dos instancias con el nombre de la Diseño de meta-metamodelos para el modelado de entornos de Smart Manufacturing mediante técnicas de optimización condición seguido de “true” o “false”, que a su vez se conectan con la condición mediante las object properties “TRUE” o “FALSE”. Figura 35. Instancia para una condición cumplida del ejemplo En este caso el cumplimiento de la condición derivará en la ejecución de una serie de acciones, ya sean llamada a funciones, operaciones básicas, inicialización de una variable u otras, cada una de ellas con sus correspondientes instancias. El orden de ejecución de las acciones en el algoritmo podría suponer un problema, por eso aquellas acciones que lo requieren pueden conectarse mediante “Precede a”, que será una relación transitiva, por lo que las acciones que son predecesoras de otras también lo serán de las siguientes, sin necesidad de conectar todas y cada una de las acciones del algoritmo a mano. Con este ejemplo se muestra la capacidad de esta ontología para extenderse tanto como sea necesario. Llegado el caso, podría no conocerse el código correspondiente a una función en concreto, pero aun así quedaría modelada para que otra persona que sí lo conozca lo pudiera añadir, haciendo posible la extensión de la ontología tanto como lo requieran los nuevos factores. 3.3 Diseño de la ontología. Algoritmo de resolución, elegir uno Como primera ampliación a la ontología descrita en el apartado anterior, entrando en el campo del smart scheduling, se decide realizar una ampliación de esta incorporando el algoritmo reactivo presentado por Minzu [26]. Las premisas sobre las que se desarrolla el algoritmo son las siguientes. Se trabaja sobre una línea de ensamblaje formada por un conjunto de tareas numeradas. Las tareas se agrupan en estaciones de trabajo, cada una de las cuales está atendida por un único operario. Además, existe una relación de precedencia que determina que tareas deben ser realizadas antes que otras, lo que se puede representar mediante un grafo de precedencia como el de la siguiente figura, donde cada nodo representa una tarea o trabajo y cada recuadro representa una estación de trabajo denominada Wi. 3. Diseño de un sistema de conocimiento interoperable para Smart schedulling Figura 36. Ejemplo de un grafo de precedencia dividido en estaciones de trabajo Hay que señalar que cada operario tendrá la capacidad de realizar un listado de tareas, representado por Fi que será una lista o vector compuesto por todas las tareas que puede realizar el operario i. En el artículo se describe la siguiente casuística: uno de los operarios al cargo de una estación de trabajo falla, por lo que hay que volver a definir las estaciones de trabajo con los operarios disponibles restantes, bajo la premisa de que cualquier tarea puede ser asignada a cualquier operario capaz de realizarla, este será el objetivo principal del algoritmo reactivo. Dadas estas premisas el funcionamiento del algoritmo puede dividirse en cuatro pasos principalmente: 1. Verificar que cada tarea que realizaba el operario fallido puede ser realizada por algún otro operario. 2. Establecer para cada operador Pi la lista de tareas Fi que puede realizar. 3. Construir los conjuntos Ωi que se explica a continuación. 4. Generar las particiones Wi` que se corresponden con las nuevas estaciones de trabajo. Tanto el primer como el segundo paso son sencillos, dado que las listas Fi se toman como dato del problema, es fácil comprobar que todas las tareas de la línea pueden ser cubiertas por algún operario. Para construir los conjuntos Ωi, en el tercer paso, hay que definir Ti, una serie de listas compuestas por aquellos trabajos que sólo pueden ser realizados por el operario i. Dada esta aclaración y atendiendo a la definición propuesta en el artículo: Ωi = {W/W ∈ Ω, W ⊂ Fi , Ti ⊂ W}, i ∈ I Tal y como se indica, cada uno de estos conjuntos estará formado por una serie de listas que responderán a todas las combinaciones de los trabajos que forman Fi siempre incluyendo los de Ti. Dará todas las posibilidades de formar una estación de trabajo del operario i, por lo que siempre habrá que incluir las tareas que sólo él puede realizar, ya que, si no, no quedarían cubiertas. Cabe destacar que cualquier estación de trabajo o grupo de tareas candidato a serlo ha de estar formado por trabajos sucesivos al menos dos a dos, las precedencias deben ser tomadas en cuenta. Para el cuarto paso se plantea el siguiente pseudocódigo: {i=0; i=successor(i); X=0; while i∈I do { -Determinar los segmentos de X -Construir S con los sucesores de los nodos finales -Construir Ωi'={Wi'/Wi'∈Ωi, Wi'∩X=0, S⊂Wi'} -Elegir Wi'∈Ωi' -Actualizar X -i=succesor(i); } Diseño de meta-metamodelos para el modelado de entornos de Smart Manufacturing mediante técnicas de optimización -Verificar X=Q; } Pseudocódigo para el cuarto paso del algoritmo reactivo Aparecen varios elementos hasta ahora desconocidos que deben ser descritos para entender su funcionamiento: • X: lista o vector que se actualiza con cada pasada del bucle “while” añadiendo los trabajos que ya han sido asignados a una nueva estación de trabajo • S: lista o vector formado por las tareas sucesoras a los nodos finales de X según el grafo de precedencia. • Successor(i): Función que recibe como dato el índice de un operario y devuelve el índice del siguiente saltándose el operario fallido. • Q: lista de todas las tareas que forman la línea de ensamblaje. • Segmento: lista formada por uno o varios nodos (tareas) que ocupan posiciones contiguas en el grafo de precedencias. Como se ve en el código anterior se inicializa un índice mediante la función succesor(i) y se establece X como una lista vacía. Tras esto, se entra en un bucle “while” que dará tantas pasadas como operarios funcionales haya. En cada uno de estos ciclos, se determinan los segmentos que forman el conjunto X y se construye S con los sucesores de los nodos finales de X. Ahora se construirá un nuevo conjunto Ωi’ que por definición: Ωi' = {Wi'/Wi' ∈ Ωi , Wi'∩X=0, S ⊂ Wi'} Lo que indica que los conjuntos Ωi’ se formarán a partir de Ωi , pero solo se tomarán aquellos subconjuntos que incluyan los elementos de S, los sucesores de las anteriores nuevas estaciones de trabajo propuestas. A continuación, se elige que subconjunto de Ωi’, será el escogido para formar la nueva Wi'. Como no se establece ningún criterio claro, se escogerá el primer elemento de Ωi’. Por último, se actualiza X añadiendo los elementos de la nueva Wi', se ejecuta succesor(i) para pasar al siguiente operario disponible. Una vez se sale del bucle, porque ya se han hecho tantos ciclos como operarios no fallidos hay, se verifica que X equivale a Q lo que significa que todas las tareas de la línea están cubiertas por algún operario. Todas estas nuevas variables y procesos deben verse reflejados en la ontología. Partiendo de la ontología creada en el apartado 3.2 se realiza una ampliación para que el algoritmo quede totalmente recogido en ella. Primeramente, se detallan las nuevas entidades y posteriormente como se relacionan entre ellas. Como se observa en las figuras a continuación habrá una nueva clase padre para los conjuntos Ωi y Ωi’. También se añade una subclase dentro de “Listas” para Fi , Q, S, X, Ti , Wi', Wi , Ωij’, Ωij , grafo de precedencia y Io , que estará compuesta por los operarios disponibles tras el fallo. En el apartado de las funciones se añade una subclase para la función encargada del paso 1 del algoritmo, comprobar que todas las tareas están cubiertas, una para construir el conjunto Ωi y una más para generar las nuevas estaciones Wi'. De esta última subclase penden todas aquellas funciones que intervienen en su ejecución y que se han explicado en el pseudocódigo del paso 4. 3. Diseño de un sistema de conocimiento interoperable para Smart schedulling La lista de entidades queda como se muestra en la siguiente figura: Figura 37. Lista de entidades en Protégé tras la ampliación con el algoritmo reactivo Diseño de meta-metamodelos para el modelado de entornos de Smart Manufacturing mediante técnicas de optimización En el caso de las relaciones serán menores los nuevos elementos a incorporar, se muestran en la siguiente tabla: Relación Dominio Rango Compuesto por Conjunto Listas Genera Funciones Variables Conjunto Listas Se realiza antes de Trabajos Trabajos Tabla 3. Nuevas relaciones a incluir en la ontología La lista total actualizada de las relaciones se muestra a continuación: Figura 38. Lista de relaciones en Protégé con el algoritmo reactivo El siguiente paso es la instanciación de la ontología, para ello se parte de un caso teórico y general del algoritmo como el que se ha usado en la explicación. No se describirá en este punto ningún caso real con un número de trabajos y estaciones determinado. La gran mayoría de instancias en este punto llevarán el mismo nombre que la subclase a la que pertenecen, este es el caso de todas las pertenecientes a las clases de “Listas”, “Conjuntos” y las funciones que no pertenecen a “WHILE”. A continuación, se detallan sólo aquellas que son de especial interés: • Algoritmos: se creará una instancia para el algoritmo reactivo. • Condiciones: 3 nuevas instancias se crearán con sus correspondientes instancias para la condición cumplida y no cumplida. “Lista tareas operario fallido=cubiertas” para el primer paso del algoritmo. “X=Q” para la comprobación de que todas las tareas quedan cubiertas por las nuevas estaciones de trabajo. “i ∈ I” para ejecutar el bucle WHILE mientras haya operarios disponibles sin tareas asignadas. • WHILE: para el bucle del paso 4 se añade “While i ∈ I”, como su correspondiente End while. La manera de relacionarse estas instancias es muy similar a la del ejemplo puesto en el punto 3.2, pero posteriormente se detallará en el apartado de pruebas mediante una serie de ejemplo. De esta manera queda reflejado en la ontología el algoritmo reactivo escogido con todos los procesos y elementos que en él intervienen. 3. Diseño de un sistema de conocimiento interoperable para Smart schedulling 3.4 Interoperabilidad entre implementación de sistemas smart scheduling Una de las principales características que presentan las ontologías es la capacidad de compartir el conocimiento que contienen. El enfoque tradicional presenta un único sistema de información para todo el proceso de producción del producto, normalmente de manera rígida, lo que dificulta su transmisión entre diferentes equipos involucrados en dicho proceso. Las ontologías se presentan como una oportunidad de aumentar la interoperabilidad del conocimiento para mejorar los flujos de información. representación del flujo de información en un proceso productivo Para el caso que ocupa este trabajo el eje central se encuentra en los algoritmos, por lo que será necesario impulsar la fácil comprensión de su funcionamiento para cualquier profesional que decida implementarlo o que quiera participar en la ampliación de la ontología. En este sentido y al ser un algoritmo, son muchos los posibles lenguajes de programación en los que se puede implementar, pero todos responderán a los mismos procesos. Con este objetivo se trabaja en la posibilidad de incluir cualquier parte del algoritmo en cualquier lenguaje de programación, dejando constancia también de la equivalencia de códigos en caso de existir. Para llevar a cabo esto en Protégé se opta por crear un atributo (data property) llamado “Código”. El dominio de este atributo se extiende entre las clases de “Funciones” y “Algoritmos”, cuyas instancias son aquellas que pueden ser ejecutadas mediante un código. El tipo de dato escogido es “string” que se compone de uno o más caracteres alfanuméricos. Estos caracteres se tratarán solamente como texto. Figura 39. Atributo “Código” creado en Prótegé. Hay que aclarar que la disponibilidad de añadir un atributo de este tipo en una instancia no obliga al usuario que Diseño de meta-metamodelos para el modelado de entornos de Smart Manufacturing mediante técnicas de optimización quiere ampliar la ontología a hacerlo, ya que el desarrollo de un algoritmo o función puede quedar reflejado también mediante las relaciones existentes. De esta manera la ontología gana más posibilidades en la descripción de partes concretas del algoritmo. En la siguiente imagen se puede ver un ejemplo con la función que verifica al final del algoritmo que todos los trabajos están cubiertos por alguna de las nuevas estaciones de trabajo. Se han creado tres instancias nuevas (además de la genérica que ya existía) para los lenguajes C++, Python y R. Cada una de ellas tendrá un atributo de tipo código donde se incluirá la sintaxis de la función en cada uno de los lenguajes correspondientes. Figura 40. Instancias para una misma función en diferentes lenguajes de programación en Protégé Protégé facilita añadir este tipo de instancias ya que no será necesario relacionar de nuevo cada una de ellas con el algoritmo, ya que en la ventana derecha existe, como ya se conoce, la opción de “Same individual as”, lo que permitirá marcar la equivalencia de las nuevas instancias con la que ya existía, quedando así integradas en la ontología. 41 4 PRUEBAS DE VALIDACIÓN n este apartado se muestran varios casos de uso del algoritmo reactivo escogido así como su implementación en la ontología. Mediante estas pruebas se demostrará la trazabilidad del algoritmo y sus soluciones tanto intermedias como final. 4.1 Validación del proceso Para la primera aplicación de la ontología en un caso concreto se decide representar el presentado por Minzu [26] en el mismo artículo en el que se define el algoritmo. Los datos de los que se disponen son los siguientes: • Grafo de precedencia (figura 36) 𝑄 = {1,2,3,4,5,6,7,8,9,10} • Estaciones de trabajo: 𝑊1={1,2,3,4}, 𝑊2={6,7}, 𝑊3={5,8}, 𝑊4={9,10} • Tareas realizables por cada operario: 𝐹1={1,2,3,4,5}, 𝐹2={5,6,7,8}, 𝐹3={1,2,5,8,10}, 𝐹4={1,2,6,9,10} Estos datos se reflejan en la ontología mediante instancias, primero se incluirán cada uno de los trabajos, que se relacionarán entre ellos mediante “Se realiza antes de” para dejar constancia de las precedencias, y posteriormente las listas, cuya composición se indica mediante la relación “Formada por”. Para el caso que se propone se marcará cada una de las instancias con la palabra “ejemplo” al final de su nombre, como se ve en las siguientes figuras. Figura 41. Representación de los trabajos en Protégé para el ejemplo E Diseño de meta-metamodelos para el modelado de entornos de Smart Manufacturing mediante técnicas de optimización ontology-24#Trabajo_0_mant"/> <Formada_por rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Trabajo_1_mant"/> <Formada_por rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Trabajo_3_mant"/> <Formada_por rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Trabajo_5_mant"/> <Formada_por rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Trabajo_6_mant"/> </owl:NamedIndividual> • F2 <!-- http://www.semanticweb.org/alvar/ontologies/2022/5/untitled-ontology-24#F2_mant --> <owl:NamedIndividual rdf:about="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#F2_mant"> <rdf:type rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Fi"/> <Formada_por rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Trabajo_1_mant"/> <Formada_por rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Trabajo_3_mant"/> <Formada_por rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Trabajo_6_mant"/> <Formada_por rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Trabajo_7_mant"/> </owl:NamedIndividual> • F3 <!-- http://www.semanticweb.org/alvar/ontologies/2022/5/untitled-ontology-24#F3_mant --> <owl:NamedIndividual rdf:about="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#F3_mant"> <rdf:type rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Fi"/> <Formada_por rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Trabajo_2_mant"/> <Formada_por rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Trabajo_4_mant"/> <Formada_por rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Trabajo_5_mant"/> <Formada_por rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Trabajo_8_mant"/> </owl:NamedIndividual> • F4 <!-- http://www.semanticweb.org/alvar/ontologies/2022/5/untitled-ontology-24#F4_mant --> <owl:NamedIndividual rdf:about="http://www.semanticweb.org/alvar/ontologies/2022/5/untitled- 4. Pruebas de validación ontology-24#F4_mant"> <rdf:type rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Fi"/> <Formada_por rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Trabajo_1_mant"/> <Formada_por rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Trabajo_3_mant"/> <Formada_por rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Trabajo_6_mant"/> <Formada_por rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Trabajo_7_mant"/> <Formada_por rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Trabajo_8_mant"/> </owl:NamedIndividual> Se decide añadir una función que indique las tareas exclusivas de cada operario. Para ello se creará una subclase de tipo “función” llamada “Generar Ti”. Como se ha venido haciendo se crea una instancia genérica para la función y otra para este caso concreto. Se quiere dejar reflejado el código de Python utilizado, por ello se creará un tercer individuo “Generar Ti Python” con su atributo “Código” correspondiente en el que se incluirá lo siguiente: def Tareas_exclusivas(N,F): aux=F.copy( aux.remove(F[N]); W=[] for i in aux: for j in i: W.append(j) exclusiva=[] for i in F[N]: if i not in W: exclusiva.append(i) return exclusiva; Código en Python para encontrar las tareas exclusivas Esta función recibirá mediante N el operario del que se desean conocer las tareas y F como una lista compuesta por cada Fi. Todo esto queda detallado en la instancia, no solo mediante el atributo si no con un pequeño comentario. Las instancias correspondientes son: • Función genérica <!-- http://www.semanticweb.org/alvar/ontologies/2022/5/untitled-ontology-24#Generar_Ti --> Diseño de meta-metamodelos para el modelado de entornos de Smart Manufacturing mediante técnicas de optimización <owl:Class rdf:about="http://www.semanticweb.org/alvar/ontologies/2022/5/untitled-ontology- 24#Generar_Ti"> <rdfs:subClassOf rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Funciones"/> </owl:Class> • Función para el problema concreto <!-- http://www.semanticweb.org/alvar/ontologies/2022/5/untitled-ontology-24#Generar_Ti_mant -- > <owl:NamedIndividual rdf:about="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Generar_Ti_mant"> <rdf:type rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Generar_Ti"/> <Genera rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#T1_mant"/> <Genera rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#T3_mant"/> <Genera rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#T4_mant"/> </owl:NamedIndividual> • Función para su implementación en Python <owl:NamedIndividual rdf:about="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Generar_Ti_python"> <rdf:type rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Generar_Ti"/> <Código>def Tareas_exclusivas(N,F): aux=F.copy(); aux.remove(F[N]); W=[]; for i in aux: for j in i: W.append(j); exclusiva=[] for i in F[N]: if i not in W: exclusiva.append(i); return exclusiva;</Código> <rdfs:comment>Definición de la función en Python para generar las tareas exclusivas de cada operario. Recibe el operario y un conjunto con todas las F a modod de lista y devuelve las tareas exclusivas de ese operario</rdfs:comment> <rdfs:comment>Podría combinarse con un bucle para generar la lista para cada operario.</rdfs:comment> </owl:NamedIndividual> El resultado para cada uno de los operarios disponibles será: 4. Pruebas de validación 𝑇1={0}, 𝐹3={2,4}, 𝐹4={7} Con sus instancias: • T1 <!-- http://www.semanticweb.org/alvar/ontologies/2022/5/untitled-ontology-24#T1_mant --> <owl:NamedIndividual rdf:about="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#T1_mant"> <rdf:type rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Ti"/> <Formada_por rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Trabajo_0_mant"/> </owl:NamedIndividual> • T3 <!-- http://www.semanticweb.org/alvar/ontologies/2022/5/untitled-ontology-24#T3_mant --> <owl:NamedIndividual rdf:about="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#T3_mant"> <rdf:type rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Ti"/> <Formada_por rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Trabajo_2_mant"/> <Formada_por rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Trabajo_4_mant"/> </owl:NamedIndividual> • T4 <!-- http://www.semanticweb.org/alvar/ontologies/2022/5/untitled-ontology-24#T4_mant --> <owl:NamedIndividual rdf:about="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#T4_mant"> <rdf:type rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Ti"/> <Formada_por rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Trabajo_7_mant"/> </owl:NamedIndividual> El siguiente paso es conformar el conjunto Ωi para lo que se crea la siguiente función: def generar_omegai(F,T,G): # compute all the possible combinations of the elements in F up to the length of F combinations = [] Diseño de meta-metamodelos para el modelado de entornos de Smart Manufacturing mediante técnicas de optimización for i in range(1, len(F)+1): combinations += list(itertools.combinations(F, i)) # transform into list combinations = [list(i) for i in combinations] print("combinations =", str(combinations)) # now create a copy of the combinations list combinations_filtered = combinations.copy() # first remove all the elements that do not contain T elements_removed = 0 for i in combinations: if T not in i: combinations_filtered.remove(i) elements_removed += 1 print("Removed", elements_removed, "elements that do not contain T") print("First filtered list =", str(combinations_filtered)) # then evaluate each element in the combination according to different criteria print("Second filtered list =", str(combinations_filtered)) combinations_filtered_2 = [] for i in combinations_filtered: print("---") print("Evaluating", i) # if there is only one element in the combination, keep it if len(i) == 1: print("Only one element in the combination, keep it") print("----> Keeping", i) combinations_filtered_2.append(i) continue # create a list with nodes that are not connected to any other element in the combination isolated_nodes = [] for j in i: for k in i: if G[j][k] == 1 or G[k][j] == 1: break 4. Pruebas de validación else: isolated_nodes.append(j) print("Isolated nodes =", isolated_nodes) # iterate over not isolated nodes has_antecesor = [] for j in isolated_nodes: print("Evaluating antecesor for", j) # walk over all nodes in the graph for k in range(len(G)): # if k is pointing to j and to any other node in the combination i if G[k][j] == 1: ("Found node pointing to j:", k) # iterate over other nodes for which k is pointing to for l in i: if G[k][l] == 1 and l != j: print("Removing", j, "because", k, "points to", j, "and", l) has_antecesor.append(j) isolated_filtered = [n for n in isolated_nodes if n not in has_antecesor] print("Isolated nodes after checking connections =", isolated_filtered) # if after filtering there is more than one element in the combination, remove it if len(isolated_filtered) > 0: print("!!!!! Removing", i) else: combinations_filtered_2.append(i) print("----> Keeping", i) print("---") print("Final combinations =", str(combinations_filtered_2)) return combinations_filtered_2 Código en Python para la formación de los conjuntos Ωi Diseño de meta-metamodelos para el modelado de entornos de Smart Manufacturing mediante técnicas de optimización Este código resuelve mediante lista la problemática de definir el conjunto Ωi , lo cual no es trivial. Para ello se comienza creando todas las posibles combinaciones de los elementos de F. Mediante un primer filtrado se eliminan todos aquellos elementos que no contengan la lista T. Posteriormente, se aplican una serie de filtros: -Se mantienen aquellos elementos que estén formados por un solo trabajo, para los casos en que T solo contiene un trabajo. -Se itera entre todos los subconjuntos de la siguiente manera, se detecta aquellos nodos aislados dentro del subconjunto y se estudia si poseen algún predecesor común. Si estos elementos desconectados entre sí tienen un predecesor común se tendrán en cuanta, pero si existiera algún otro elemento asilado y a su vez no conectado con ninguno de ellos, dicho subconjunto se eliminaría de los conjuntos aspirantes a estación de trabajo. El código se incluye en la siguiente instancia: <!-- http://www.semanticweb.org/alvar/ontologies/2022/5/untitled-ontology- 24#Construir_Ωi_python --> <owl:NamedIndividual rdf:about="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Construir_Ωi_python"> <rdf:type rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Construir_Ωi"/> <Código>def generar_omegai(F,T,G): # compute all the possible combinations of the elements in F up to the length of F combinations = [] for i in range(1, len(F)+1): combinations += list(itertools.combinations(F, i)) # transform into list combinations = [list(i) for i in combinations] print("combinations =", str(combinations)) # now create a copy of the combinations list combinations_filtered = combinations.copy() # first remove all the elements that do not contain T elements_removed = 0 for i in combinations: if T not in i: combinations_filtered.remove(i) elements_removed += 1 print("Removed", elements_removed, "elements that do not contain T") print("First filtered list =", str(combinations_filtered)) # then evaluate each element in the combination according to different criteria print("Second filtered list =", str(combinations_filtered)) combinations_filtered_2 = [] for i in combinations_filtered: print("---") print("Evaluating", i) 4. Pruebas de validación # if there is only one element in the combination, keep it if len(i) == 1: print("Only one element in the combination, keep it") print("----> Keeping", i) combinations_filtered_2.append(i) continue # create a list with nodes that are not connected to any other element in the combination isolated_nodes = [] for j in i: for k in i: if G[j][k] == 1 or G[k][j] == 1: break else: isolated_nodes.append(j) print("Isolated nodes =", isolated_nodes) # iterate over not isolated nodes has_antecesor = [] for j in isolated_nodes: print("Evaluating antecesor for", j) # walk over all nodes in the graph for k in range(len(G)): # if k is pointing to j and to any other node in the combination i if G[k][j] == 1: ("Found node pointing to j:", k) # iterate over other nodes for which k is pointing to for l in i: if G[k][l] == 1 and l != j: print("Removing", j, "because", k, "points to", j, "and", l) has_antecesor.append(j) isolated_filtered = [n for n in isolated_nodes if n not in has_antecesor] print("Isolated nodes after checking connections =", isolated_filtered) # if after filtering there is more than one element in the combination, remove it if len(isolated_filtered) > 0: print("!!!!! Removing", i) else: combinations_filtered_2.append(i) print("----> Keeping", i) print("---") print("Final combinations =", str(combinations_filtered_2)) return combinations_filtered_2</Código> </owl:NamedIndividual> Que corresponde a la siguiente, la función genérica: <!-- http://www.semanticweb.org/alvar/ontologies/2022/5/untitled-ontology- Diseño de meta-metamodelos para el modelado de entornos de Smart Manufacturing mediante técnicas de optimización 24#Construir_Ωi' --> <owl:NamedIndividual rdf:about="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Construir_Ωi'"> <rdf:type rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Construir_Ωi'"/> <owl:sameAs rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Construir_Ωi'_ejemplo"/> <Genera rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Ωi'"/> <Precede_a rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Elegir_Wi'_1"/> </owl:NamedIndividual> La función recibirá el conjunto F, T y el grafo de precedencias expresado como una matriz mediante G. El resultado de aplicar esta función a cada estación de trabajo es el siguiente: Ω1={{0},{0,1} ,{0,1,3} ,{0,1,3,6}}, Ω3={{2,4},{4,5},{4,8},{2,4,5},{2,4,8},{4,5,8},{2,4,5,8}}, Ω4={{7},{3,7},{6,7},{7,8},{1,3,7},{3,6,7},{3,7,8},{6,7,8},{1,3,6,7},{1,3,7,8},{3,6,7,8},{1,3,6,7,8}} En la ontología queda: • Función para construir los conjuntos <!-- http://www.semanticweb.org/alvar/ontologies/2022/5/untitled-ontology- 24#Construir_Ωi_mant --> <owl:NamedIndividual rdf:about="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Construir_Ωi_mant"> <rdf:type rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Construir_Ωi"/> <Genera rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Ω1_mant"/> <Genera rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Ω3_mant"/> <Genera rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Ω4_mant"/> </owl:NamedIndividual> • Ω1 <!-- http://www.semanticweb.org/alvar/ontologies/2022/5/untitled-ontology-24#Ω1_mant --> <owl:NamedIndividual rdf:about="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Ω1_mant"> <rdf:type rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Ωi"/> <Compuesto_por rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Ω11_mant"/> <Compuesto_por rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Ω12_mant"/> 4. Pruebas de validación <Compuesto_por rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Ω13_mant"/> <Compuesto_por rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Ω14_mant"/> </owl:NamedIndividual> • Ω3 <!-- http://www.semanticweb.org/alvar/ontologies/2022/5/untitled-ontology-24#Ω3_mant --> <owl:NamedIndividual rdf:about="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Ω3_mant"> <rdf:type rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Ωi"/> <Compuesto_por rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Ω31_mant"/> <Compuesto_por rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Ω32_mant"/> <Compuesto_por rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Ω33_mant"/> <Compuesto_por rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Ω34_mant"/> <Compuesto_por rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Ω35_mant"/> <Compuesto_por rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Ω36_mant"/> <Compuesto_por rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Ω37_mant"/> </owl:NamedIndividual> • Ω4 <!-- http://www.semanticweb.org/alvar/ontologies/2022/5/untitled-ontology-24#Ω4_mant --> <owl:NamedIndividual rdf:about="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Ω4_mant"> <rdf:type rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Ωi"/> <Compuesto_por rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Ω410_mant"/> <Compuesto_por rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Ω411_mant"/> <Compuesto_por rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Ω412_mant"/> <Compuesto_por rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Ω41_mant"/> <Compuesto_por rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitledontology-24#Ω42_mant"/> <Compuesto_por rdf:resource="http://www.semanticweb.org/alvar/ontologies/2022/5/untitled- Diseño de meta-metamodelos para el modelado de entornos de Smart Manufacturing mediante técnicas de optimización 10.1007/s10845-013-0771-9. [18] P. Brucker, B. Jurisch, and B. Sievers, “A branch and bound algorithm for the job-shop scheduling problem,” Discrete Appl Math (1979), vol. 49, no. 1–3, pp. 107–127, Mar. 1994, doi: 10.1016/0166- 218X(94)90204-6. [19] R. Zhang, “Environment-Aware Production Scheduling for Paint Shops in Automobile Manufacturing: A Multi-Objective Optimization Approach” Enviromental Research and Public Health, 2017. [20] I. M. Ovacik and R. Uzsoy, “Decomposition Methods for Complex Factory Scheduling Problems”. [21] K. Bouleimen and H. Lecocq, “A new efficient simulated annealing algorithm for the resourceconstrained project scheduling problem and its multiple mode version” in European Journal of Operational Research, Sep. 2003, vol. 149, no. 2, pp. 268–281. doi: 10.1016/S0377-2217(02)00761-0. [22] L. Egri and T. R. Shultz, “Constraint-Satisfaction Models” International Encyclopedia of the Social & Behavioral Sciences: Second Edition, pp. 716–723, Mar. 2015, doi: 10.1016/B978-0-08-097086- 8.43023-0. [23] M. A. Aloulou, M.-C. Portmann, and A. Vignier, “Predictive-Reactive Scheduling for the Single Machine Problem” 2002. [Online]. Available: https://www.researchgate.net/publication/228570005 [24] H. Jopek, H. Jopek, and J. A. Kołodziej, “Application of genetic algorithms for optimal positions of source points in method of fundamental solutions Thermomechanical properties of auxetic composites View project Materials-Special Issue View project Application of genetic algorithms for optimal positions of source points in method of fundamental solutions” 2008. [Online]. Available: https://www.researchgate.net/publication/255531663 [25] J. Davis et al., “Smart Manufacturing” Annu Rev Chem Biomol Eng, vol. 6, pp. 141–160, Jul. 2015, doi: 10.1146/annurev-chembioeng-061114-123255. [26] V. Minzu and J.-M. Henrioud, “Algorithm for Reactive Scheduling in Flexible Assembly Systems” IFAC Proceedings Volumes, vol. 28, no. 24, pp. 305–309, Oct. 1995, doi: 10.1016/s1474- 6670(17)46567-0. [27] S. J. Russell and P. Norvig, “Artificial intelligence: a modern approach” Pearson Education Limited, 2016. [28] S. L. Takeda Berger, R. M. Zanella, and E. M. Frazzon, “Towards a data-driven predictive-reactive production scheduling approach based on inventory availability” in IFAC-PapersOnLine, Sep. 2019, vol. 52, no. 13, pp. 1343–1348. doi: 10.1016/j.ifacol.2019.11.385. [29] P. Kugathasan and C. A. McMahon, “Multiple viewpoint design models for automotive body-in-white design” Int J Prod Res, vol. 39, 2001. [30] H. K. H. Chow, K. L. Choy, W. B. Lee, and F. T. S. Chan, “Design of a knowledge-based logistics strategy system” Expert Syst. Applic., vol. 29, 2005. [31] Y. Lu, Z. Yang, D. Eddy, and S. Krishnamurty, “Self-Improving Additive Manufacturing Knowledge Management” Aug. 2018. doi: 10.1115/DETC2018-85996. [32] G. Probst, S. Raub, and K. Romhardt, Wissen managen, Prentice Hall. Wiesbaden: Gabler, 2006. doi: 10.1007/978-3-8349-9343-4. [33] A. Canals (2003). "La gestión del conocimiento". En: Acto de presentación del libro Gestión del conocimiento (2003: Barcelona) [en línea]. UOC. [34] J. Davies, M. Grobelnik, and D. Mladenic, Semantic Knowledge Management: Integrating Ontology Management, Knowledge Discovery, and Human Language Technologies. 2008. [35] A. Felic, B. König-Ries, and M. Klein, “Process-oriented semantic knowledge management in Product Lifecycle Management” in Procedia CIRP, 2014, vol. 25, no. C, pp. 361–368. doi: 10.1016/j.procir.2014.10.050. [36] A. L. Szejka, O. C. Junior, H. Panetto, A. Aubry, and E. F. R. Loures, “A semantic reconciliation view to support the interoperable information relationships in product design and manufacturing” Jul. 2017, vol. 50, no. 1, pp. 15896–15903. doi: 10.1016/j.ifacol.2017.08.2357. [37] D. Rajpathak, E. Motta, and R. Roy, “A generic task ontology for scheduling applications,” 2001. [Online]. Available: http://kmi.open.ac.uk/projects/akt/publication-pdf/generictaskontology.pdf