Cette thèse se situe à l’intersection de deux domaines de recherche scientifique la Reconnaissance d’Objets Structurels (ROS) et la Recherche Opérationnelle (RO). Le premier consiste à rendre la machine plus intelligente et à reconnaître les objets, en particulier ceux basés sur les graphes. Alors que le second se focalise sur la résolution de problèmes d’optimisation combinatoire difficiles. L’idée principale de cette thèse est de combiner les connaissances de ces deux domaines. Parmi les problèmes difficiles existants en ROS, le problème de la distance d’édition entre graphes (DEG) a été sélectionné comme le cœur de ce travail. Les contributions portent sur la conception de méthodes adoptées du domaine RO pour la résolution du problème de DEG. Explicitement, des nouveaux modèles linéaires en nombre entiers et des matheuristiques ont été développé à cet effet et de très bons résultats ont été obtenus par rapport à des approches existantes. / This thesis is focused on Graph Matching (GM) problems and in particular the Graph Edit Distance (GED) problems. There is a growing interest in these problems due to their numerous applications in different research domains, e.g. biology, chemistry, computer vision, etc. However, these problems are known to be complex and hard to solve, as the GED is a NP-hard problem. The main objectives sought in this thesis, are to develop methods for solving GED problems to optimality and/or heuristically. Operations Research (OR) field offers a wide range of exact and heuristic algorithms that have accomplished very good results when solving optimization problems. So, basically all the contributions presented in thesis are methods inspired from OR field. The exact methods are designed based on deep analysis and understanding of the problem, and are presented as Mixed Integer Linear Program (MILP) formulations. The proposed heuristic approaches are adapted versions of existing MILP-based heuristics (also known as matheuristics), by considering problem-dependent information to improve their performances and accuracy.

Die schichtenübergreifende Steuerung von Multi-Layer Netzen ermöglicht die Realisierung fortgeschrittener Netzarchitekturen sowie neuartiger Konzepte zur Steigerung der Ausfallsicherheit. Gegenstand dieser Arbeit ist ein neues ressourcensparendes Konzept zur Kompensation von Core-Router-Ausfallen in IP-Netzen. Core-Router-Ausfälle führen zur Abkopplung der an Ihnen angeschlossenen Zugangsrouter vom Netz. Daher werden die Zugangsrouter üblicherweise mit jeweils zwei oder mehreren verschiedenen Core-Routern verbunden (engl.: dual homing) was jedoch eine Verdoppelung der Anschlusskapazität im IP Netz bedingt. Bei dem neuen Verfahren - Dual Homing mit gemeinsam genutzten Router-Ersatzressourcen (engl.: dual homing with shared backup router resources, DH-SBRR) - erfolgt die Zugangsrouter-Anbindung zum einen zu einem Core-Router des IP-Netzes und zum anderen zu einem Netzelement der darunterliegenden Transportschicht. Damit lassen sich Router-Ersatzressourcen, die im IP-Netz an beliebigen Stellen vorgehalten werden können, uber das Transportnetz an die Stelle eines ausgefallenen Core-Routers schalten. Die Steuerung dieser Ersatzschaltung geschieht über eine schichten übergreifende, d.h. das Transportnetz- und IP-Netz umfassende Control-Plane - beispielsweise auf Basis von GMPLS. Da beim Umschalten der Routerressourcen auch aktuelle Zustände (bspw. Routing-Tabellen) auf die Router-Ersatzressourcen mit übertragen werden müssen, beinhaltet das neue Verfahren auch Konzepte zur Router-Virtualisierung. Zum Vergleich und zur Bewertung der Leistungsfähigkeit des neuen DH-SBRR Verfahrens werden in der Arbeit verschiedene Zugangsrouter-Homing-Varianten hinsichtlich Netz-Kosten, Netz-Verfügbarkeit, Recovery-Zeit und Netz-Energieverbrauch gegenübergestellt. Als Multi-Layer Netzszenarien werden zum einen IP über WDM und zum anderen IP über OTN (ODU) betrachtet. Zur Bestimmung der minimalen Netz-Kosten ist ein generisches Multi-Layer Netzoptimierungsmodell entwickelt worden, welches bei unterschiedlichen Homing-Architekturen angewendet werden kann. Neben dem Optimierungsmodell zur Netzkostenminimierung wird auch eine Modellvariante zur Minimierung des Energieverbrauchs vorgestellt. Um die Rechenzeit für die Lösung der Optimierungsprobleme zu verringern und damit auch größere Netzszenarien untersuchen zu können bedarf es heuristischer Lösungsverfahren. Im Rahmen der Arbeit ist daher eine neue speziell auf die Multilayer-Optimierungsprobleme zugeschnittene Lösungsheuristik entwickelt worden. Aus der Netzkosten-Optimierung ergibt sich, dass durch den Einsatz von DH-SBBR signifikante Kosteneinsparungen im Vergleich zu herkömmlichen Homing-Architekturen realisiert werden können. Änderungen der Verkehrslast, der Kosten der IP-Netzelemente oder der Netztopologie haben keinen signifikanten Einfluss auf dieses Ergebnis. Neben dem Kosten- und Energieeinsparungspotential sind auch die Auswirkungen auf die Netz-Verfügbarkeit und die Recovery-Zeit untersucht worden. Für die Ende-zu-Ende Verfügbarkeit bei Anwendung der verschiedenen Homing-Architekturen Können untere Grenzwerte angegeben werden. Zur Bestimmung der Recovery-Zeit bei Einsatz von DH-SBRR ist ein eigenes analytisches Berechnungsmodell entwickelt und evaluiert worden. Damit kann das DH-SBRR Verfahren zur Einhaltung vorgegebener Recovery-Zeiten (wie sie für bspw. Für bestimmte Dienste gefordert werden) entsprechend parametriert werden. / The emergence of multi-layer networking capabilities opens the path for the development of advanced network architectures and resilience concepts. In this dissertation we propose a novel resource-efficient homing scheme: dual homing with shared backup router resources. The proposed scheme realizes shared router-level redundancy, enabled by the emergence of control plane architectures such as generalized multi-protocol label switching. Additionally, virtualization schemes complement the proposed architecture. Different homing architectures are examined and compared under the prism of cost, availability, recovery time and energy efficiency. Multiple network layers are considered in Internet protocol over wavelength division multiplexing as well as Internet protocol over optical data unit settings - leading to the development of multi-layer optimization techniques. A generic multi-layer network design mathematical model, which can be applied to different homing architecture considerations, is developed. The optimization objective can be adapted to either minimizing the cost for network equipment or the power consumption of the network. In order to address potential issues with regard to computational complexity, we develop a novel heuristic approach specifically targeting the proposed architecture. It is shown that significant cost savings can be achieved - even under extreme changes in the traffic demand volume, in the cost for different types of network equipment, as well as in the network topology characteristics. In order to evaluate occurring tradeoffs in terms of performance, we study the effects on availability and recovery time. We proceed to derive lower bounds on end-to-end availability for the different homing architectures. Additionally, an analytical recovery time model is developed and evaluated. We investigate how service-imposed maximum outage requirements have a direct effect on the setting of the proposed architecture.

<p>Minimum cycle mean (MCM) is an important concept in directed graphs. From clock period optimization, timing analysis to layout optimization, minimum cycle mean algorithms have found widespread use in VLSI system design optimization. With transistor size scaling to 10nm and below, complexities and size of the systems have grown rapidly over the last decade. Scalability of the algorithms both in terms of their runtime and memory usage is therefore important. </p> <p><br></p> <p>Among the few classical MCM algorithms, the algorithm by Young, Tarjan, and Orlin (YTO), has been particularly popular. When implemented with a binary heap, the YTO algorithm has the best runtime performance although it has higher asymptotic time complexity than Karp's algorithm. However, as an efficient implementation of YTO relies on data redundancy, its memory usage is higher and could be a prohibitive factor in large size problems. On the other hand, a typical implementation of Karp's algorithm can also be memory hungry. An early termination technique from Hartmann and Orlin (HO) can be directly applied to Karp's algorithm to improve its runtime performance and memory usage. Although not as efficient as YTO in runtime, HO algorithm has much less memory usage than YTO. We propose several improvements to HO algorithm. The proposed algorithm has comparable runtime performance to YTO for circuit graphs and dense random graphs while being better than HO algorithm in memory usage. </p> <p><br></p> <p>Minimum balancing of a directed graph is an application of the minimum cycle mean algorithm. Minimum balance algorithms have been used to optimally distribute slack for mitigating process variation induced timing violation issues in clock network. In a conventional minimum balance algorithm, the principal subroutine is that of finding MCM in a graph. In particular, the minimum balance algorithm iteratively finds the minimum cycle mean and the corresponding minimum-mean cycle, and uses the mean and cycle to update the graph by changing edge weights and reducing the graph size. The iterations terminate when the updated graph is a single node. Studies have shown that the bottleneck of the iterative process is the graph update operation as previous approaches involved updating the entire graph. We propose an improvement to the minimum balance algorithm by performing fewer changes to the edge weights in each iteration, resulting in better efficiency.</p> <p><br></p> <p>We also apply the minimum cycle mean algorithm in latency insensitive system design. Timing violations can occur in high performance communication links in system-on-chips (SoCs) in the late stages of the physical design process. To address the issues, latency insensitive systems (LISs) employ pipelining in the communication channels through insertion of the relay stations. Although the functionality of a LIS is robust with respect to the communication latencies, such insertion can degrade system throughput performance. Earlier studies have shown that the proper sizing of buffer queues after relay station insertion could eliminate such performance loss. However, solving the problem of maximum performance buffer queue sizing requires use of mixed integer linear programming (MILP) of which runtime is not scalable. We formulate the problem as a parameterized graph optimization problem where for every communication channel there is a parameterized edge with buffer counts as the edge weight. We then use minimum cycle mean algorithm to determine from which edges buffers can be removed safely without creating negative cycles. This is done iteratively in the similar style as the minimum balance algorithm. Experimental results suggest that the proposed approach is scalable. Moreover, quality of the solution is observed to be as good as that of the MILP based approach.</p><p><br></p>

<p>Online retail sales and grocery/food orders have been breaking records every year. As a result, third-party delivery companies have found an opportunity to get their share from the growing transportation network. Electric vehicles (EVs) are becoming a preferable choice for such large delivery systems due to their environmental benefits. However, EVs have limited-service ranges; therefore, intra-route facilities are needed for EVs to stay operational. These facilities offer charging stations for EVs and storage areas for requests, e.g., food and packages. In this dissertation, we propose a novel <em>Pickup and Delivery Problem</em> (PDP) with EVs and transfers. There are requests to be picked up and delivered. EVs leave their origin depot, serve requests, and return to their destination depot. Unlike the generic PDP, intra-route facilities allow EVs to exchange requests. Thus, a request can be transported by more than one vehicle. In this dissertation, three new problems are introduced, and the following research questions are investigated: 1) "How valuable is to include intra-route facilities and allow transfers in a pickup and delivery network with EVs?", 2) "What is the cost of locating intra-route facilities randomly rather than finding the best locations while creating the routes for EVs?", and 3) "How much can drones improve the delivery speed in a pickup and delivery network with EVs and transfers?". A <em>Mixed-integer Linear Programming</em> (MILP) model and a <em>Simulated Annealing</em> (SA) algorithm are developed and compared with each other to answer the first question. For the second question, a MILP model is formulated; however, due to unreasonable computational runtimes, a SA algorithm and an <em>Adaptive Large Neighborhood Search</em> (ALNS) algorithm are proposed. Finally, a MILP model is developed for the hybrid-fleet problem. The overall results highlight that intra-route facilities shorten the total traveled distance in the PDP network by allowing exchanges and recharging.</p>

[pt] No Brasil, existem muitos projetos em sistemas fotovoltaicos, e a projeção para os próximos anos é de crescimento devido incentivos governamentais e os elevados preços das tarifas de energia. Associado a isso, o mercado de armazenamento de energia com baterias de íons de lítio tem se mostrado promissor devido a uma considerável queda nos preços dessas baterias nos últimos anos. Isso pode representar uma oportunidade para o mercado de sistemas fotovoltaicos quando os incentivos acabarem. Este trabalho propõe um modelo PLIM (Programação Linear Inteira Mista) estocástico para dimensionar um sistema fotovoltaico integrado com armazenamento de energia em baterias para grandes consumidores de energia, usando cenários de geração e consumo, podendo considerar diferentes modalidades tarifárias. As variáveis de decisão são o número de painéis, inversores, baterias, a operação diária do sistema de armazenamento e a demanda contratada do consumidor. A função objetivo busca minimizar o custo de investimento no sistema fotovoltaico, baterias e fatura de energia. A abordagem proposta será analisada sob diferentes premissas, uma com incentivos governamentais sobre a anergia injetada na rede e outra na qual a injeção de energia na rede não é permitida, a fim de avaliar a importância das baterias para manter a atratividade econômica do sistema fotovoltaico. Os resultados indicaram que o efeito sinérgico do sistema fotovoltaico com baterias potencializa a arbitragem, que está relacionada com a diferença entre as tarifas de energia de ponta e fora ponta. Isso ocorre principalmente com operação zero exportação porque somente assim o consumidor é livre para escolher a capacidade do seu sistema fotovoltaico, que hoje é limitado no Brasil quando o sistema é conectado na rede de distribuição. / [en] In Brazil, there are many projects in photovoltaic systems, and the projection for the coming years is positive due to the government incentives and the expensive energy tariffs. Associated with this, the Lithium-ion battery storage systems market has been promising due to a significant drop in battery prices in the last few years. This may represent an opportunity for the photovoltaic system market when the incentives run-out. This work proposes a stochastic mixed integer linear programming (MILP) model to design a photovoltaic system integrated with battery energy storage for big electricity consumers, using generation and consumption scenarios, being able to consider different Time-of-Use tariffs. The decision variables are the number of panels, inverters and batteries, its daily operation and the power demand contracted. The objective function aims to minimize the cost of investment, in the photovoltaic system, batteries and electricity bill. The proposed approach will be analyzed under different assumptions, one with the government incentive about injected surplus and another in which the injection into the network is not possible, in order to assess the importance of a storage system to keep the economic attraction of the photovoltaic system. Results indicated that the synergic effect of the photovoltaic system and battery potentialize the arbitrage, which is related to the difference between peak and off-peak energy tariff. This occurs, mainly with Zero Export operation because only this way the consumer is free to choose the capacity of the photovoltaic system, which is limited in Brazil when the system is allowed to inject energy into the network.

Tesis por compendio / [ES] Los sistemas tradicionales de planificación y control de la producción (PPC) se centran en producir lo que demanda el mercado, con la calidad, el calendario y los volúmenes previstos al mínimo coste, ajustándose al mismo tiempo a las disrupciones de la cadena de suministro. La exploración e implementación de nuevos avances tecnológicos en el marco de la industria 4.0 (I4.0), como sistemas ciberfísicos (CPS), fabricación en la nube (CMfg), fabricación aditiva (AM), big data, inteligencia artificial y la Internet de las cosas (IoT), podrían cambiar aspectos organizativos tales como las responsabilidades de PPC. En este contexto, no se identificaron estudios sobre un sistema para la toma de decisiones, arquitecturas y marcos conceptuales para los nuevos sistemas inteligentes de PPC e I4.0. En este contexto de nuevos cambios tecnológicos y organizativos a los que tienen que hacer frente las pequeñas y medianas empresas (PYMEs), surge el problema de diseñar herramientas de PPC que permitan la integración y colaboración de las operaciones de producción. Así, basándose en las nuevas tecnologías de producción digital y en las herramientas organizativas que darán soporte a las fábricas inteligentes conectadas del futuro, se identificó la falta de un sistema integrado de PPC e I4.0. Esta tesis doctoral es un compendio de artículos que abordan una amplia revisión bibliográfica sobre la PPC en un entorno de I4.0. También, se propone un marco conceptual y el diseño de modelos y algoritmos para la toma de decisiones y dar soporte a las funciones de PPC en un contexto digital I4.0 basado en las nuevas tecnologías de producción digital y herramientas organizativas que darán soporte a las fábricas inteligentes colaborativas y conectadas del futuro. Los modelos matemáticos y algoritmos propuestos se centran en resolver el problema del diseño y planificación de una cadena de suministro sostenible y resiliente en la que las decisiones estratégicas y tácticas se toman de forma integrada. Los modelos, algoritmos y método de resolución se han programado en Python. Los modelos han sido validados mediante un software que genera instancias de datos sintéticos y permite evaluar la complejidad computacional de los mismos. El desarrollo de este tipo de modelos y algoritmos supone una contribución al ámbito académico e investigador y, concretamente, en el área de PPC. / [CA] En l'actualitat, els sistemes tradicionals de planificació i control de la producció (PPC) se centren en produir el que demanda el mercat, amb la qualitat, el calendari i els volums previstos al mínim cost, ajustant-se al mateix temps a les pertorbacions. L'exploració i implementació de nous avanços tecnològics, com CPS, fabricació en el núvol (CMfg), fabricació additiva (AM), big data, intelligència artificial i el IoT, podrien canviar aspectes organitzatius, com les responsabilitats de PPC. En aquest context, no es van identificar estudis sobre un sistema per a la presa de decisions, arquitectures i marcs conceptuals per als nous sistemes intelligents de PPC i I4.0. En aquest context de nous canvis tecnològics i organitzatius als quals han de fer front les petites i mitjanes empreses (PIME), sorgeix el problema de dissenyar eines de PPC que permeten la integració i collaboració de les operacions de producció. Així, basant-se en les noves tecnologies de producció digital i en les eines organitzatives que donaran suport a les fàbriques intelligents connectades del futur, es va identificar la falta d'un sistema integrat de la PPC i I4.0. Aquesta investigació és un compendi d'articles que aborden una àmplia revisió bibliogràfica sobre la PPC en un entorn I4.0. També proposa un marc conceptual i el disseny de models i algorismes per a la presa de decisions i per a donar suport a les funcions de PPC en un context digital I4.0 basat en les noves tecnologies de producció digital i eines organitzatives que donaran suport a les fàbriques intelligents col·laboratives i connectades del futur. Els models matemàtics i algorismes proposats se centren en resoldre el problema del disseny d'una cadena de subministrament sostenible i resistent en la qual les decisions estratègiques i tàctiques es prenen de forma integrada. Els models, algorismes i mètode de resolució s'han programat en Python. Els models han sigut validats mitjançant un programari que genera instàncies de dades sintètiques i permet avaluar la complexitat computacional dels models. El desenvolupament d'aquesta mena de models i algorismes suposa una important contribució a l'àmbit acadèmic. / [EN] Currently, traditional production planning and control (PPC) systems focus on producing what the market demands with the expected quality, schedule and volumes at a minimum cost, while adjusting for disruption. The exploration and implementation of new technological advances, such as CPS, cloud manufacturing (CMfg), additive manufacturing (AM), big data, artificial intelligence and the Internet of Things (IoT), could change organisational aspects like PPC responsibilities. In this context, no studies on a system for decision making, architectures and conceptual frameworks for the new intelligent systems of PPC and industry 4.0 (I4.0) have been identified. In this context of new technological and organisational changes that small-and medium-sized enterprises (SMEs) have to face, the problem of designing PPC tools that enable the integration and collaboration of production operations arises. Thus, based on the new digital production technologies and organisational tools that will support the connected smart factories of the future, lack of an integrated PPC and I4.0 system was identified. The present doctoral thesis is a compendium of articles addressing a comprehensive literature review on PPC in an I4.0 environment. It also proposes a conceptual framework and the design of models and algorithms for decision making and to support PPC functions in a digital I4.0 context based on the new digital production technologies and organisational tools that will support the collaborative and connected smart factories of the future. The proposed mathematical models and algorithms focus on solving the problem of designing a sustainable and resilient supply chain where strategic and tactical decisions are made in an integrated way. The models, algorithms and resolution method have been programmed in Python. The models have been validated by means of software that generates synthetic data instances and allows the models' computational complexity to be evaluated. The development of this type of models and algorithms is a significant contribution to the academic field. / I would like to thank the following projects and universities for having financed the publications included in this doctoral thesis: • European Commission Horizon 2020 project entitled "Crop diversification and low-input farming cross Europe: From practitioners' engagement and ecosystems services to increased revenues and value chain organisation' (Diverfarming), grant agreement 728003. • Spanish Ministry of Science, Innovation and Universities project entitled 'Optimization of zero-defect production technologies enabling supply chains 4.0 (CADS4.0)' (RTI2018-101344-B-I00). • European Union H2020 program with grant agreement no. 958205 "Industrial Data Services for Quality Control in Smart Manufacturing (i4Q)". • European Union H2020 Program with grant agreement nº 825631 "Zero- Defect Manufacturing Platform (ZDMP)". / Cañas Sánchez, HE. (2023). Models, Algorithms and Digital Technologies for the Automation and Collaboration of Connected Smart Factories in an Industry 4.0 Environment [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/202312 / Compendio

Tesis por compendio / [ES] La optimización en las empresas manufactureras es especialmente importante, debido a las grandes inversiones que realizan, ya que a veces estas inversiones no obtienen el rendimiento esperado porque los márgenes de beneficio de los productos son muy ajustados. Por ello, las empresas tratan de maximizar el uso de los recursos productivos y financieros minimizando el tiempo perdido y, al mismo tiempo, mejorando los flujos de los procesos y satisfaciendo las necesidades del mercado. El proceso de planificación es una actividad crítica para las empresas. Esta tarea implica grandes retos debido a los cambios del mercado, las alteraciones en los procesos de producción dentro de la empresa y en la cadena de suministro, y los cambios en la legislación, entre otros. La planificación del aprovisionamiento, la producción y la distribución desempeña un papel fundamental en el rendimiento de las empresas manufactureras, ya que una planificación ineficaz de los proveedores, los procesos de producción y los sistemas de distribución contribuye a aumentar los costes de los productos, a alargar los plazos de entrega y a reducir los beneficios. La planificación eficaz es un proceso complejo que abarca una amplia gama de actividades para garantizar que los equipos, los materiales y los recursos humanos estén disponibles en el momento y el lugar adecuados. Motivados por la complejidad de la planificación en las empresas manufactureras, esta tesis estudia y desarrolla herramientas cuantitativas para ayudar a los planificadores en los procesos de la planificación del aprovisionamiento, producción y distribución. Desde esta perspectiva, se proponen modelos realistas y métodos eficientes para apoyar la toma de decisiones en las empresas industriales, principalmente en las pequeñas y medianas empresas (PYMES). Las aportaciones de esta tesis suponen un avance científico basado en una exhaustiva revisión bibliográfica sobre la planificación del aprovisionamiento, la producción y la distribución que ayuda a comprender los principales modelos y algoritmos utilizados para resolver estos planes, y pone en relieve las tendencias y las futuras direcciones de investigación. También proporciona un marco holístico para caracterizar los modelos y algoritmos centrándose en la planificación de la producción, la programación y la secuenciación. Esta tesis también propone una herramienta de apoyo a la decisión para seleccionar un algoritmo o método de solución para resolver problemas concretos de la planificación del aprovisionamiento, producción y distribución en función de su complejidad, lo que permite a los planificadores no duplicar esfuerzos de modelización o programación de técnicas de solución. Por último, se desarrollan nuevos modelos matemáticos y enfoques de solución de última generación, como los algoritmos matheurísticos, que combinan la programación matemática y las técnicas metaheurísticas. Los nuevos modelos y algoritmos comprenden mejoras en términos de rendimiento computacional, e incluyen características realistas de los problemas del mundo real a los que se enfrentan las empresas de fabricación. Los modelos matemáticos han sido validados con un caso de una importante empresa del sector de la automoción en España, lo que ha permitido evaluar la relevancia práctica de estos novedosos modelos utilizando instancias de gran tamaño, similares a las existentes en la empresa objeto de estudio. Además, los algoritmos matheurísticos han sido probados utilizando herramientas libres y de código abierto. Esto también contribuye a la práctica de la investigación operativa, y proporciona una visión de cómo desplegar estos métodos de solución y el tiempo de cálculo y rendimiento de la brecha que se puede obtener mediante el uso de software libre o de código abierto. / [CA] L'optimització a les empreses manufactureres és especialment important, a causa de les grans inversions que realitzen, ja que de vegades aquestes inversions no obtenen el rendiment esperat perquè els marges de benefici dels productes són molt ajustats. Per això, les empreses intenten maximitzar l'ús dels recursos productius i financers minimitzant el temps perdut i, alhora, millorant els fluxos dels processos i satisfent les necessitats del mercat. El procés de planificació és una activitat crítica per a les empreses. Aquesta tasca implica grans reptes a causa dels canvis del mercat, les alteracions en els processos de producció dins de l'empresa i la cadena de subministrament, i els canvis en la legislació, entre altres. La planificació de l'aprovisionament, la producció i la distribució té un paper fonamental en el rendiment de les empreses manufactureres, ja que una planificació ineficaç dels proveïdors, els processos de producció i els sistemes de distribució contribueix a augmentar els costos dels productes, allargar els terminis de lliurament i reduir els beneficis. La planificació eficaç és un procés complex que abasta una àmplia gamma d'activitats per garantir que els equips, els materials i els recursos humans estiguen disponibles al moment i al lloc adequats. Motivats per la complexitat de la planificació a les empreses manufactureres, aquesta tesi estudia i desenvolupa eines quantitatives per ajudar als planificadors en els processos de la planificació de l'aprovisionament, producció i distribució. Des d'aquesta perspectiva, es proposen models realistes i mètodes eficients per donar suport a la presa de decisions a les empreses industrials, principalment a les petites i mitjanes empreses (PIMES). Les aportacions d'aquesta tesi suposen un avenç científic basat en una exhaustiva revisió bibliogràfica sobre la planificació de l'aprovisionament, la producció i la distribució que ajuda a comprendre els principals models i algorismes utilitzats per resoldre aquests plans, i posa de relleu les tendències i les futures direccions de recerca. També proporciona un marc holístic per caracteritzar els models i algorismes centrant-se en la planificació de la producció, la programació i la seqüenciació. Aquesta tesi també proposa una eina de suport a la decisió per seleccionar un algorisme o mètode de solució per resoldre problemes concrets de la planificació de l'aprovisionament, producció i distribució en funció de la seua complexitat, cosa que permet als planificadors no duplicar esforços de modelització o programació de tècniques de solució. Finalment, es desenvolupen nous models matemàtics i enfocaments de solució d'última generació, com ara els algoritmes matheurístics, que combinen la programació matemàtica i les tècniques metaheurístiques. Els nous models i algoritmes comprenen millores en termes de rendiment computacional, i inclouen característiques realistes dels problemes del món real a què s'enfronten les empreses de fabricació. Els models matemàtics han estat validats amb un cas d'una important empresa del sector de l'automoció a Espanya, cosa que ha permés avaluar la rellevància pràctica d'aquests nous models utilitzant instàncies grans, similars a les existents a l'empresa objecte d'estudi. A més, els algorismes matheurístics han estat provats utilitzant eines lliures i de codi obert. Això també contribueix a la pràctica de la investigació operativa, i proporciona una visió de com desplegar aquests mètodes de solució i el temps de càlcul i rendiment de la bretxa que es pot obtindre mitjançant l'ús de programari lliure o de codi obert. / [EN] Optimisation in manufacturing companies is especially important, due to the large investments they make, as sometimes these investments do not obtain the expected return because the profit margins of products are very tight. Therefore, companies seek to maximise the use of productive and financial resources by minimising lost time and, at the same time, improving process flows while meeting market needs. The planning process is a critical activity for companies. This task involves great challenges due to market changes, alterations in production processes within the company and in the supply chain, and changes in legislation, among others. Planning of replenishment, production and distribution plays a critical role in the performance of manufacturing companies because ineffective planning of suppliers, production processes and distribution systems contributes to higher product costs, longer lead times and less profits. Effective planning is a complex process that encompasses a wide range of activities to ensure that equipment, materials and human resources are available in the right time and the right place. Motivated by the complexity of planning in manufacturing companies, this thesis studies and develops quantitative tools to help planners in the replenishment, production and delivery planning processes. From this perspective, realistic models and efficient methods are proposed to support decision making in industrial companies, mainly in small- and medium-sized enterprises (SMEs). The contributions of this thesis represent a scientific breakthrough based on a comprehensive literature review about replenishment, production and distribution planning that helps to understand the main models and algorithms used to solve these plans, and highlights trends and future research directions. It also provides a holistic framework to characterise models and algorithms by focusing on production planning, scheduling and sequencing. This thesis also proposes a decision support tool for selecting an algorithm or solution method to solve concrete replenishment, production and distribution planning problems according to their complexity, which allows planners to not duplicate efforts modelling or programming solution techniques. Finally, new state-of-the-art mathematical models and solution approaches are developed, such as matheuristic algorithms, which combine mathematical programming and metaheuristic techniques. The new models and algorithms comprise improvements in computational performance terms, and include realistic features of real-world problems faced by manufacturing companies. The mathematical models have been validated with a case of an important company in the automotive sector in Spain, which allowed to evaluate the practical relevance of these novel models using large instances, similarly to those existing in the company under study. In addition, the matheuristic algorithms have been tested using free and open-source tools. This also helps to contribute to the practice of operations research, and provides insight into how to deploy these solution methods and the computational time and gap performance that can be obtained by using free or open-source software. / This work would not have been possible without the following funding sources: Conselleria de Educación, Investigación, Cultura y Deporte, Generalitat Valenciana for hiring predoctoral research staff with Grant (ACIF/2018/170) and the European Social Fund with the Grant Operational Programme of FSE 2014-2020. Conselleria de Educación, Investigación, Cultura y Deporte, Generalitat Valenciana for predoctoral contract students to stay in research centers outside the research centers outside the Valencian Community (BEFPI/2021/040) and the European Social Fund. / Guzmán Ortiz, BE. (2022). Models and Algorithms for the Optimisation of Replenishment, Production and Distribution Plans in Industrial Enterprises [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/187461 / TESIS / Compendio

The purpose of this paper is to increase the routing efficiency of two previously separate commodity transports. By combining them in a common, multi-commodity network flow (MCNF). A Mixed Integer Linear Programming (MILP) model is used to minimize the mileage that is needed to fulfill demand in the different destinations of the transport network. Input needed for the model was mileage between destinations, which was obtained from open data. And the demand of respective commodity was received from documents and an estimation. To solve the stated problem approximations and simplifications was needed because it showed a NP-complete problem. The aim is to produce a result that shows a lower mileage than a reference measure from the present situation with separate transports. The result showed an optimized solution of 1939 km. Which was a difference of 1941 km from the reference measures, that summarized to 3880 km. Despite this the result from the model shows an effective optimization. Which makes the use of MILP for minimizing mileage inside a MCNF problem, a useful approach for solving the stated problem. / Syftet med arbetet var att effektivisera körsträckor för två tidigare separata transporter av olika produkter. Genom att kombinera dem till en gemensam transport i ett multi-commodity network flow (MCNF). Med en Mixed Integer Linear Programming (MILP) modell minimeras de körsträckor som krävs för att fylla efterfrågan i transportnätverkets adresser. In-data som krävdes för att en modell skulle kunna utföras var körsträckor mellan olika adresser, vilket hämtades från öppen data. Samt efterfrågan på produkter som erhölls från dokument och estimering.  Då problemet som skulle lösas visade på hög beräkningskomplexitet behövde ett antal approximationer och förenklingar verkställas. Målet var att visa på ett resultat där körsträckor hade förminskats relativt till ett referensmått från nuläget. Där resultatet visade på en optimerad lösning på 1939 km. Vilket var en differens på 1941 km från de referensmåttet som summerades till 3880 km. Modellens resultat visar trots det en effektiv optimering. Vilket gör att användningen av MILP för att minimera körsträckor inom MCNF problem, är ett effektivt tillvägagångssätt att lösa det motiverade problemet.

This paper presents the development and mathematical implementation of a production scheduling model utilizing mixed-integer linear programming (MILP). A simplified model of a real-world multi-product batch plant constitutes the basis. The paper shows practical extensions to the model, resulting in a digital twin of the plant. Apart from sequential arrangement, the final model contains maintenance periods, campaign planning and storage constraints to a limited extend. To tackle weak computational performance and missing model features, a condensed mathematical formulation is introduced at first. After stating that these measures do not suffice for applicability in a restrained time period, a novel solution strategy is proposed. The overall non-iterative algorithm comprises a multi-step decomposition approach, which starts with a reduced scope and incrementally complements the schedule in multiple subproblem stages. Each of those optimizations holds less decision variables and makes use of warmstart information obtained from the predecessor model. That way, a first feasible solution accelerates the subsequent improvement process. Furthermore, the optimization focus can be shifted beneficially leveraging the Gurobi solver parameters. Findings suggest that correlation may exist between certain characteristics of the scheduling scope and ideal parameter settings, which yield potential for further investigation. Another promising area for future research addresses the concurrent multi-processing of independent MILPs on a single machine. First observations indicate that significant performance gains can be achieved in some cases, though sound dependencies were not discovered yet.

[ES] En esta tesis doctoral se desarrollan modelos de programación matemática para el diseño estratégico-táctico de una red de transporte intermodal que combina dos tipos de problemas de decisiones: la localización de instalaciones y el diseño de la red de transporte. Esta combinación se reconoce en la literatura como problemas combinados LI-DR. El problema combinado se estudia para una situación real y se analizan el comportamiento de la solución óptima, a partir de distintos aspectos como: la disponibilidad del presupuesto de inversión, capacidad de las instalaciones intermodales, múltiples periodos de decisiones, interdependencia en la priorización de las decisiones, múltiples fuentes de financiación y criterios de optimización para las tres dimensiones de sostenibilidad. Para la situación real se referencian las condiciones de acceso y conectividad de la Zona de Desarrollo Económico y Social (ZODES) Magdalena Medio del departamento de Bolívar en Colombia, y el potencial de la industria agroalimentaria para esta subregión. Con el propósito de identificar factores clave que perfilen la formulación respecto a la composición y funcionamiento de los sistemas intermodales y en los problemas combinados LI-DR se analiza la literatura desde estas dos perspectivas. El análisis de la literatura ha permitido aportar dos clasificaciones novedosas e identificar retos para la investigación futura. Para la formulación de los modelos se lleva a cabo la sistemática de pasos definidos para la aplicación de las técnicas de programación matemática. Con estos pasos se logra transformar el problema del mundo real a un problema manejable con estas técnicas. La transformación favorece la interpretación matemática del problema combinado LI-DR intermodal, la modelación de los datos y la definición de una estructura de red de entrada para indexar las decisiones estratégicas y tácticas. Los modelos de programación matemática se construyen de manera gradual. En concreto, se proponen 2 versiones que se representan en 5 variantes. Se comienza formulando un modelo de programación lineal entero-mixto (MPLEM) mono-periodo para analizar, desde un enfoque económico, la sensibilidad de las capacidades del sistema intermodal, la capacidad financiera de los tomadores de decisiones y la variación de la demanda. A continuación, sobre la base de este modelo se propone un MPLEM multi-periodo y dos variantes para validar las condiciones de interdependencia en la toma de decisiones estratégica y la participación de múltiples actores en la financiación de los proyectos de inversión. Finalmente, se formula un MPLEM multi-objetivo para optimizar simultáneamente las tres dimensiones de sostenibilidad. Para resolver y validar los modelos se implementaron dos esquemas de resolución. En los esquemas se utilizan los lenguajes de programación R y Python con el software de optimización matemática Gurobi Optimizer. Se realizan experimentos numéricos para distintos escenarios y se analiza el comportamiento de las soluciones considerando distintos valores a los parámetros. Los resultados obtenidos permiten comprobar la utilidad de los modelos matemáticos e identificar las principales limitaciones y futuras líneas de trabajo. / [CA] En aquesta tesi doctoral es desenvolupen models de programació matemàtica per al disseny estratègic-tàctic d'una xarxa de transport intermodal que combina dos tipus de problemes de decisions: la localització d'instal·lacions i el disseny de la xarxa de transport. Aquesta combinació es reconeix en la literatura com problemes combinats LI-DR. El problema combinat s'estudia per a una situació real i s'analitzen el comportament de la solució òptima, a partir de diferents aspectes com: la disponibilitat de l'pressupost d'inversió, capacitat de les instal·lacions intermodals, múltiples períodes de decisions, interdependència en la priorització de les decisions, múltiples fonts de finançament i criteris d'optimització per a les tres dimensions de sostenibilitat. Per a la situació real es referencien les condicions d'accés i connectivitat de la Zona de Desenvolupament Econòmic i Social (ZODES) Magdalena Medio de el departament de Bolívar a Colòmbia, i el potencial de la indústria agroalimentària per a aquesta subregió. Amb el propòsit d'identificar factors clau que perfilin la formulació respecte a la composició i funcionament dels sistemes intermodals i en els problemes combinats LI-DR s'analitza la literatura des d'aquestes dues perspectives. L'anàlisi de la literatura ha permès aportar dues classificacions noves i identificar reptes per a la investigació futura. Per a la formulació dels models es porta a terme la sistemàtica de passos definits per l'aplicació de les tècniques de programació matemàtica. Amb aquests passos s'aconsegueix transformar el problema de l'món real a un problema manejable amb aquestes tècniques. La transformació afavoreix la interpretació matemàtica de el problema combinat LI-DR intermodal, la modelació de les dades i la definició d'una estructura de xarxa d'entrada per indexar les decisions estratègiques i tàctiques. Els models de programació matemàtica es construeixen de manera gradual. En concret, es proposen 2 versions que es representen en 5 variants. Es comença formulant un model de programació lineal sencer-mixt (MPLEM) mono-període per analitzar, des d'un enfocament econòmic, la sensibilitat de les capacitats de sistema intermodal, la capacitat financera dels prenedors de decisions i la variació de la demanda. A continuació, sobre la base d'aquest model es proposa un MPLEM multi-període i dues variants per validar les condicions d'interdependència en la presa de decisions estratègica i la participació de múltiples actors en el finançament dels projectes d'inversió. Finalment, es formula un MPLEM multi-objectiu per optimitzar simultàniament les tres dimensions de sostenibilitat. Per resoldre i validar els models es van implementar dos esquemes de resolució. En els esquemes s'utilitzen els llenguatges de programació R i Python amb el programari d'optimització matemàtica Gurobi Optimizer. Es realitzen experiments numèrics per a diferents escenaris i s'analitza el comportament de les solucions considerant diferents valors als paràmetres. Els resultats obtinguts permeten comprovar la utilitat dels models matemàtics i identificar les principals limitacions i futures línies de treball. / [EN] In this doctoral thesis, mathematical programming models are developed aiming at the strategic-tactical design of an intermodal transport network that combines two types of decision problems: the location of facilities and the transport network design. In the literature, this combination is recognized as combined LI-DR problems. The combined problem is studied for a real situation and the performance of the optimal solution is analyzed in relation to different aspects such as the investment budget availability, the intermodal facilities capacity, multiple decision periods, interdependence in the prioritization of the decisions, multiple sources of funding and optimization criteria for the three dimensions of sustainability. In what concern to the real situation, the access and connectivity conditions of the Magdalena Medio Economic and Social Development Zone (ZODES, for its acronym in Spanish) of the Bolívar department in Colombia, and the potential of the agri-food industry for this subregion, are considered. Aiming the identification of key factors that outlines the formulation regarding the composition and operation of intermodal systems and, in combined LI-DR problems, the literature is reviewed from these two perspectives. The literature analysis has made it possible to provide two novel classifications and to identify challenges for future research. The formulation of models follows the systematic steps already defined for the application of mathematical programming techniques. Following these steps, it is possible to transform the problem from a real-world problem to a manageable one. The transformation promotes the mathematical interpretation of the intermodal LI-DR combined problem, the data modeling, and the definition of an input network structure to index strategic and tactical decisions. Mathematical programming models are built gradually. Specifically, 2 versions are proposed, which are represented by 5 variants. Firstly, it is formulated a single-period mixed-integer linear programming model (MILPM) in order to analyze, from an economic perspective, the sensitivity of the intermodal system capacities, the financial capacity of the decision-makers, and the demand changes. Based on the aforementioned model, a multi-period MILPM and two variants are proposed aiming to validate the conditions of interdependence in strategic decision-making and the participation of multiple actors in the investment projects financing. Finally, a multi-objective MILPM is formulated to simultaneously optimize all three dimensions of sustainability. To solve and validate the models, two resolution schemes were implemented. The schematics use the R and Python programming languages with the mathematical optimization software Gurobi Optimizer. Numerical tests are carried out for different scenarios and the performance of the solutions is analyzed considering different values for the parameters. The results obtained allow us to verify the usefulness of the models proposed and identify the main limitations and future lines of work. / Agamez Arias, ADM. (2021). Modelos de optimización para el diseño estratégico-táctico de una red de transporte intermodal [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/177015 / TESIS