Steelmaking industry, one of the most electricity-intensive industrial processes, is seeking for new approaches to improve its competitiveness in terms of energy savings by taking advantage of the volatile electricity prices. This fluctuation in the price is mainly caused by the increasing share of renewable energy sources, the liberalization of energy markets and the growing demand of the energy. Therefore, making the production scheduling of steelmaking processes with knowledge about the cost of the energy may lead to significant cost savings in the electricity bills. With this aim in mind, different models are developed in this project in order to improve the existing monolithic models (continuous-time based scheduling) to find an efficient formulation of accounting for electricity consumption and also to expand them with more detailed scheduling of Electric Arc Furnace stage in the production process. The optimization of the energy cost with multiple electricity sources and contracts and the production planning are usually done as stand-alone optimizers due to their complexity, therefore as a new approach in addition to the monolithic model an iterative framework is developed in this work. The idea to integrate the two models in an iterative manner has potential to be useful in the industry due to low effort for reformulation of existing models. The implemented framework uses multiparametric programming together with bilevel programming in order to direct the schedule to find a compromise between the production constraints and goals, and the energy cost. To ensure applicability heuristic approaches are also examined whenever full sized models are not meeting computational performance requirements. The results show that the monolithic model implemented has a considerable advantage in terms of computational time compared to the models in the literature and in some cases, the solution can be obtained in a few minutes instead of hours. In the contrary, the iterative framework shows a bad performance in terms of computational time when dealing with real world instances. For that matter a heuristic approach, which is easy to implement, is investigated based on coordination theory and the results show that it has a potential since it provides solutions close to the optimal solutions in a reasonable amount of time. Multiparametric programming is the main core of the iterative framework developed in this internship and it is not able to give the solutions for real world instances due to computational time limitations. This computational problem is related to the nature of the algorithm behind mixed integer multiparametric programming and its ability to handle the binary variables. Therefore, further work to this project is to develop new approaches to approximate multiparametric technique or develop some heuristics to approximate the mp-MILP solutions.

Dans cette thèse, nous étudions des Hoist Scheduling Problems (HSP) qui se posent fréquemment dans des lignes automatiques de traitement de surface. Dans ces lignes, des ponts roulants sont utilisés pour transporter les pièces entre les bains. Ainsi, les ponts roulants jouent un rôle essentiel dans la performance de ces lignes ; et un ordonnancement optimal de leurs mouvements est un facteur déterminant pour garantir la qualité des produits et maximiser la productivité. Les lignes que nous étudions comportent un seul pont roulant mais peuvent être des lignes de base ou des lignes étendues (où des bains sont à fonctions et/ou capacités multiples). Nous examinons trois Hoist Scheduling Problems : l’optimisation robuste d’un HSP cyclique, l’ordonnancement dynamique d’une ligne étendue de type job shop et l’ordonnancement cyclique d’une telle ligne.Pour l’optimisation robuste d’un HSP cyclique, nous définissons la robustesse comme la marge dans le temps de déplacement du pont roulant. Nous formulons le problème en programmation linéaire en nombres mixtes à deux objectifs pour optimiser simultanément le temps de cycle et la robustesse. Nous démontrons que le temps de cycle minimal augmente avec la robustesse, et que par conséquent la frontière Pareto est constituée d’une infinité de solutions. Les valeurs minimales et maximales des deux objectifs sont établies. Les résultats expérimentaux à partir de benchmarks et d’instances générées aléatoirement montrent l’efficacité de l’approche proposée.Nous étudions ensuite un problème d’ordonnancement dynamique dans une ligne étendue de type job shop. Nous mettons en évidence une erreur de formulation dans une un modèle existant pour un problème similaire mais sans bains multi-fonctions. Cette erreur peut rendre l’ordonnancement obtenu sous-optimal voire irréalisable. Nous construisons un nouveau modèle qui corrige cette erreur. De plus il est plus compact et s’applique au cas avec des bains à la fois à capacités et à fonctions multiples. Les résultats expérimentaux menés sur des instances avec ou sans bains multi-fonctions montrent que le modèle proposé conduit toujours à une solution optimale et plus efficace que le modèle existant.Nous nous focalisons enfin sur l’ordonnancement cyclique d’une ligne étendue de type job shop avec des bains à fonctions et capacités multiples. Nous construisons un modèle mathématique en formulant les contraintes de capacité du pont roulant, les intervalles des durées opératoires, et les contraintes de capacité des bains. Nous établissons également des contraintes valides. Les expériences réalisées sur des instances générées aléatoirement montrent l’efficacité du modèle proposé. / This thesis studies hoist scheduling problems (HSPs) arising in automated electroplating lines. In such lines, hoists are often used for material handing between tanks. These hoists play a crucial role in the performance of the lines and an optimal schedule of the hoist operations is a key factor in guaranteeing product quality and maximizing productivity. We focus on extended lines (i.e. with multi-function and/or multi-capacity tanks) with a single hoist. This research investigates three hoist scheduling problems: robust optimization for cyclic HSP, dynamic jobshop HSP in extended lines and cyclic jobshop HSP in extended lines.We first study the robust optimization for a cyclic HSP. The robustness of a cyclic hoist schedule is defined in terms of the free slacks in hoist traveling times. A bi-objective mixed-integer linear programming (MILP) model is developed to optimize the cycle time and the robustness simultaneously. It is proved that the optimal cycle time strictly increases with the robustness, thus there is an infinite number of Pareto optimal solutions. We established lower and upper bounds of these two objectives. Computational results on several benchmark instances and randomly generated instances indicate that the proposed approach can effectively solve the problem.We then examine a dynamic jobshop HSP with multifunction and multi-capacity tanks. We demonstrate that an existing model for a similar problem can lead to suboptimality. To deal with this issue, a new MILP model is developed to generate an optimal reschedule. It can handle the case where a multi-function tank is also multi-capacity. Computational results on instances with and without multifunction tanks indicate that the proposed model always yields optimal solutions, and is more compact and effective than the existing one.Finally, we investigate a cyclic jobshop HSP with multifunction and multi-capacity tanks. An MILP model is developed for the problem. The key issue is to formulate the time-window constraints and the tank capacity constraints. We adapt the formulation of time-window constraints for a simpler cyclic HSP to the jobshop case. The tank capacity constraints are handled by dealing with the relationships between hoist moves so that there is always an empty processing slot for new parts. Computational experiments on numerical examples and randomly generated instances indicate that the proposed model can effectively solve the problem.

Das Ziel dieses Projektes ist, die bestehende tägliche Produktionsablaufplanung in der Handgalvanik bei dem Lohngalvanikbetrieb C. Jentner GmbH mit Hilfe eines mathematischen Modells zu optimie-ren. Hierfür wurde das Flexible-Job-Shop-Modell von Ziaee ([1], S. 91-95) ausgewählt und auf die Gegebenheiten vor Ort angepasst. Es gehört zu den MILP-Problemen (mixed integer linear programming- gemischt ganzzahlige Programmierung). Bei der Verwendung des Modells für die Praxis stellt die Modellgröße, die benötigt wird, um die Vorgänge in der Produktion ausreichend abbilden zu können, ein Problem dar. Diese führt zu langen Lösungszeiten, die für den täglichen Einsatz in der Produktionsablaufplanung ungeeignet sind. Zur Lösung dieses Problems wurde ein problemspezifisches Verfahren basierend auf Aggregations- und Dekompositionstechniken entwickelt. Durch Anwendung dieses Verfahrens kann die Problemgröße für den Solver klein und so die Lösungszeit in einem für die tägliche Produktionsablaufplanung annehmbaren Rahmen gehalten werden.

In telecommunications, there is currently a lot of work being done to migrate to the cloud, and a lot of specialized hardware is being exchanged for virtualized solutions. One important part of telecommunication networks that is yet to be moved to the cloud is known as the base-band unit, which sits between the antennas and the core network. The base-band unit has very strict latency requirements, making it unsuitable for out-of-the-box cloud solutions. Ericsson is therefore investigating if cloud solutions can be customized in such a way that base-band unit functionality can be virtualized as well. One such customization is to describe the functionality of a base-band unit using a directed acyclic graph (DAG), and deploy it to a cloud environment using Kubernetes. This thesis sets out to take applications represented using a DAG and deploy it using Kubernetes in such a way that the network latency is reduced when compared to the deployment generated by the default Kubernetes scheduler. The problem of placing the applications onto the available hardware resources was formulated as an integer linear programming problem. The problem was then implemented using Pyomo and solved with the open-source solver GLPK to obtain an optimized placement. This placement was then used to generate a configuration file that could be used to deploy the applications using Kubernetes. A mock application was developed in order to evaluate the optimized placement. The evaluation carried out in this thesis shows that the optimized placement obtained from the solution could improve the average round-trip latency of applications represented using a DAG by up to 30% when compared to the default Kubernetes scheduler.

With a fast-growing electricity demand and a larger proportion of intermittent energy sources follows a greater need for flexible and balancing sources of electricity, such as hydropower. Planning of hydropower production is considered to be a difficult problem to solve due to several nonlinearities, combinatorial properties and the fact that it is a large scale system with spatial-temporal coupling. Optimization approaches are used for solving such problems and a common simplification is to disregard the effect of head variation on the power output. This thesis presents two methods for modeling the head dependency in optimization models for hydropower river systems, the Triangulation method and the Bilinear method. The Triangulation method implements a three-dimensional interpolation technique called triangulation, using a MILP formulation. This is a commonly used method found in the literature. The Bilinear method is a novel approach that applies a piecewise bilinear approximation of the power production function, resulting in a BLP problem. Also, a strategy for selecting which hydropower stations to include head dependence for is provided. The performance of the methods was evaluated on authentic test cases from Lule River and compared to results obtained by Vattenfall's current model without head dependency. The Triangulation method and the Bilinear method give higher accuracy, and are therefore considered more realistic, than the current model. Further, the results indicate that it is sufficient to include head dependence for a subset of stations since the error is significantly reduced. Mid- to long-term scenarios were solved with high accuracy when a subset of the stations was modeled as head dependent. Overall, the Bilinear method had a significantly shorter computational time than the Triangulation method.

PLAS is a cloud-based software used for planning and scheduling fleets of vehicles for material transport. PLAS consists of two components; the Logistic Flow Solver (LFS) and the Material Transport Scheduler (MTS). Based on transportation requests, the LFS generates a set of logistic flows. The MTS then transforms the logistic flows into tasks that are assigned to the vehicles. The LFS is implemented with Mixed Integer Linear Programming (MILP). Currently, the LFS and the MTS are decoupled from each other and there is information that is not considered in the LFS. Thus, the choice of logistic flows generated with the current formulation may negatively impact the final transport plan. The objective of this thesis is to investigate how the generation of logistic flows can be improved. Two alternative mathematical models for the LFS were developed using MILP formulation. Compared to the current model, more information is taken into account in the two new models. Three different objective functions were considered. Scheduling of the vehicles were modelled as pickup and delivery problems, where pickup and delivery pairs correspond to the generated logistic flows. The models were implemented using Google OR-Tools, an open-source software suite for optimization. The different mathematical formulations were evaluated based on their performance for test problems with different fleet compositions. The results show that problem characteristics influence the performance of the models and that there is no model that gives the best result for every type of problem. Therefore, it is necessary to analyse problem characteristics in order to choose a suitable model for generation of logistic flows. / PLAS är en molnbaserad mjukvara som används för planering och schemaläggning av fordonsflottor för materialtransport. PLAS består av två komponenter; Logistic Flow Solver (LFS) and Material Transport Scheduler (MTS). Baserat på transportbehov genererar LFS ett antal logistikflöden. MTS omvandlar sedan logistikflödena till uppdrag som är tilldelade till fordonen. LFS är implementerad med blandad heltalsprogrammering. För närvarande är LFS och MTS frikopplade från varandra och det finns information som inte tas hänsyn till i LFS. Därför kan valet av logistikflöden genererade med den nuvarande formuleringen negativt påverka den slutliga transportplanen. Målet med detta examensarbete är att undersöka hur genereringen av logistikflöden kan förbättras. Två alternativa matematiska modeller utvecklades med MILP-formulering. Jämfört med den nuvarande modellen, tar de två nya modellerna hänsyn till mer information. Tre olika målfunktioner beaktades. Modellerna implementerades med Google OR-Tools, en öppen programvara för optimering. De matematiska formuleringarna utvärderades baserat på deras prestation på testproblem med olika kompositioner av fordonsflottor. Resultaten visar att problemegenskaper påverkar modellernas prestationer och att det inte finns någon modell som ger bäst resultat för varje problemtyp. Därför är det nödvändigt att analysera problemegenskaper för att kunna välja en lämplig modell för generering av logistikflöden.

Throughout United States and world history, disasters have caused not only significant loss of life, property but also enormous financial loss. The tsunami that occurred on December 26, 2004 is a telling example of the devastation that can occur unexpectedly. This unexpected natural event never happened before in this area. In addition, there was a lack of an emergency response plan for events of that magnitude. Therefore, this event resulted not only in a natural catastrophe for the people of South and Southeast Asia, but it is also considered one of the greatest natural disasters in world history. After the giant wave dissipated, there were more than 230,000 people dead and more than US$10 billion in property damage and loss. Another significant event was the terrorist incident on September 11, 2001 (commonly referred to as 9/11) in United States. This event was unexpected and an unnatural, i.e., man-made event. It resulted in approximately 3,000 lives lost and about US$21 billion in property damage. These and other unexpected (or unanticipated) events give emergency management officials short- or no-notice to prevent or respond to the situation. These and other facts motivate the need for better emergency evacuation route planning (EERP) approaches in order to minimize the loss of human lives and property in short- or no-notice emergency situations. This research considers aspects of evacuation routing that have received little attention in research and, more importantly, in practice. Previous EERP models only either consider unidirectional evacuee flow from the source of a hazard to destinations of safety or unidirectional emergency first responder flow to the hazard source. However, in real-life emergency situations, these heterogeneous, incompatible flows occur simultaneously over a bi-directional capacitated lane-based travel network, especially in short- and no-notice emergencies. After presenting a review of the work related to the multiple flow EERP problem, mathematical formulations are presented for the EERP problem where the objective for each problem is to identify an evacuation routing plan (i.e., a traffic flow schedule) that maximizes evacuee and responder flow and minimizes network clearance time of both types of flow. In addition, we integrate the general human response behavior flow pattern, where the cumulative flow behavior follows different degrees of an S-shaped curve depending upon the level of the evacuation order. We extend the analysis to consider potential traffic flow conflicts between the two types of flow under these conditions. A conflict occurs when flow of different types occupy a roadway segment at the same time. Further, with different degrees of flow movement flow for both evacuee and responder flow, the identification of points of flow congestion on the roadway segments that occur within the transportation network is investigated.

Downstream vehicles detect an emergency response vehicle (ERV) through sirens and/or strobe lights. These traditional warning systems do not give any recommendation about how to react, leaving the drivers confused and often adopting unsafe behavior while trying to open a passage for the ERV. In this research, an advanced intra-link emergency assistance system, that leverages the emerging technologies of the connected vehicle environment, is proposed. The proposed system assumes the presence of a centralized system that gathers/disseminates information from/to connected vehicles via vehicle-to-infrastructure (V2I) communications. The major contribution of this dissertation is the intra-link level support provided to ERV as well as non-ERVs. The proposed system provides network-wide assistance as it also considers the routing of ERVs. The core of the system is a mathematical program - a set of equations and inequalities - that generates, based on location and speed data from connected vehicles that are downstream of the ERV, the fastest intra-link ERV movement. It specifies for each connected non-ERV a final assigned position that the vehicle can reach comfortably along the link. The system accommodates partial market penetration levels and is applicable on large transportation link segments with signalized intersections. The system consists of three modules (1) an ERV route generation module, (2) a criticality analysis module and (2) the sequential optimization module. The first module determines the ERV's route (set of links) from the ERV's origin to the desired destination in the network. Based on this selected route, the criticality analysis module scans/filters the connected vehicles of interest and determines whether any of them should be provided with a warning/instruction message. As the ERV is moving towards its destination, new non-ERVs should be notified. When a group of non-ERVs is identified by the criticality analysis module, a sequential optimization module is activated. The proposed system is evaluated using simulation under different combinations of market penetration and congestion levels. Benefits in terms of ERV travel time with an average reduction of 9.09% and in terms of vehicular interactions with an average reduction of 35.46% and 81.38% for ERV/non-ERV and non-ERV/non-ERV interactions respectively are observed at 100% market penetration, when compared to the current practice where vehicles moving to the nearest edge. / Doctor of Philosophy / Downstream vehicles detect an emergency response vehicle (ERV) through sirens and/or strobe lights. These traditional warning systems do not give any recommendations about how to react, leaving the drivers confused and often adopting unsafe behavior while trying to open a passage for the ERV. In this research, an advanced intra-link emergency assistance system, that leverages the emerging technologies of the connected vehicle environment, is proposed. The proposed system assumes the presence of a centralized system that gathers/disseminates information from/to connected vehicles via vehicle-to-infrastructure (V2I) communications. The major contribution of this dissertation is the intra-link level support provided to ERV as well as non-ERVs. The proposed system provides network-wide assistance as it also considers the routing of ERVs. The core of the system is a mathematical program - a set of equations and inequalities - that generates, based on location and speed data from connected vehicles that are downstream of the ERV, the fastest intra-link ERV movement. It specifies for each connected non-ERV a final assigned position that the vehicle can reach comfortably along the link. The system accommodates partial market penetration levels and is applicable on large transportation link segments with signalized intersections. The system consists of three modules (1) an ERV route generation module, (2) a criticality analysis module and (2) the sequential optimization module. The first module determines the ERV’s route (set of links) from the ERV’s origin to the desired destination in the network. Based on this selected route, the criticality analysis module scans/filters the connected vehicles of interest and determines whether any of them should be provided with a warning/instruction message. As the ERV is moving towards its destination, new non-ERVs should be notified. When a group of non-ERVs is identified by the criticality analysis module, a sequential optimization module is activated. The proposed system is evaluated using simulation under different combinations of market penetration and congestion levels. Benefits in terms of ERV travel time with an average reduction of 9.09% and in terms of vehicular interactions with an average reduction of 35.46% and 81.38% for ERV/non-ERV and non-ERV/non-ERV interactions respectively are observed at 100% market penetration, when compared to the current practice where vehicles moving to the nearest edge.

京都大学 / 新制・課程博士 / 博士(情報学) / 甲第24938号 / 情博第849号 / 新制||情||142(附属図書館) / 京都大学大学院情報学研究科数理工学専攻 / (主査)准教授 原口 和也, 教授 山下 信雄, 教授 阿久津 達也 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

No description available.