O ambiente produtivo denominado job shop representa empresas manufatureiras com características como: alta variedade de produtos, volume baixo de produção e uma fábrica dividida em áreas funcionais. O problema abordado neste trabalho trata da determinação do programa de produção (scheduling) de cada lote de produtos no ambiente job shop, com a premissa de que cada produto a ser elaborado surge através de um pedido realizado pelo cliente com especificações e particularidades próprias. O objetivo do trabalho é apresentar e examinar de forma detalhada as formulações matemáticas do tipo linear inteira mista (PLIM), encontradas na literatura para o ambiente que consideram a função objetivo do makespan. Além disso, se estabelece uma nova formulação matemática que auxilia a simulação do ambiente. Todas as formulações foram comparadas através de suas dimensões e testes computacionais. Adicionalmente são apresentadas três diferentes estratégias de resolução que permitem a exploração de soluções obtidas através de diferentes metodologias. A primeira estratégia estabelece para cada instância uma solução inicial que promove uma redução do número de combinações a serem avaliadas pelo software, a segunda estratégia combina duas formulações tornando uma formulação unificada, e a terceira estratégia, estabelece um processo que utiliza duas formulações de forma consecutiva compondo um procedimento sistemático. Experimentos computacionais indicam que a formulação com melhor desempenho para o problema de job shop é a formulação de Manne (1960) por obter o melhor limitante superior (upper bound). A formulação proposta apresenta o melhor limitante inferior (lower bound). Todas as formulações melhoram seus resultados através do uso das estratégias propostas. / The operational job shop environment, represents manufacturing companies with high product variety, low volume production and an organization divided into functional areas. The problem addressed in this work determines the production schedule of each batch production, with the premise that each product results from a request made by the client with specifications and its own particularities. The main objective here is to present and to examine in detail the mathematical integer - linear program formulations (MILP) from the literature for the job shop classic environment, which considers the makespan objective. Furthermore, a new mathematical formulation is provided to help with the simulation of the environment. All the formulations were compared by mathematical dimensions and computational tests. In addition, three different strategies are presented to promote the exploration of solutions obtained from new methodologies. The first strategy defines an initial solution for each problem and promotes a reduction of the combination number to be evaluated by the software. The second strategy considers the combination of two mathematical formulations under one objective function. The third strategy establishes a procedure in which two mathematical formulations are used consecutively, creating a systematic procedure. Computational experiments demonstrate that the best formulation for the job shop problem is the Manne (1960) formulation, since it obtains the best upper bound. The proposal formulation obtains the best lower bound. All of the formulations improve their results through the use of the proposed strategies.

Diversas pesquisas e estudos científicos mostram que uma grande porcentagem das pessoas com deficiência é excluída do mercado de trabalho, sobretudo em países em desenvolvimento. Com o intuito de alterar essa realidade, destacam-se, entre outras medidas, a criação de Centros de Trabalho para Deficientes (CTDs). Tais organizações empregam trabalhadores com deficiência em vários setores empresariais, dando-lhes oportunidades iniciais e preparando-os para que possam, mais tarde, ser inseridos no mercado de trabalho convencional. Vários destes centros operam linhas de produção, principal objeto de estudo desta tese. Nosso estudo é situado em uma etapa idealmente posterior aos CTDs, referente à inserção de trabalhadores com deficiência em linhas de produção convencionais. A demanda por estudos neste contexto tem crescido nos últimos anos, devido sobretudo a políticas corporativas de responsabilidade social e exigências legislativas, como a \"Lei das Cotas\", presentes em diversos países. O planejamento da operação de linhas de produção na presença de trabalhadores com deficiência envolve uma série de desafios, devido à heterogeneidade entre trabalhadores, que faz com que o tempo de execução das tarefas seja dependente de cada indivíduo. Nos deparamos, assim, com um problema de dupla alocação, em que as variáveis de decisão determinam as tarefas a serem inseridas em estações e a alocação de trabalhadores para as mesmas, de modo a otimizar alguma medida de eficiência. O balanceamento de linhas de produção convencionais com uma parcela de trabalhadores com deficiência é denominado problema de balanceamento de linhas de produção e integração de trabalhadores (ALWIBP, do inglês: assembly line worker integration and balancing problem), sendo um caso particular do problema de balanceamento de linhas de produção e designação de trabalhadores (ALWABP, do inglês: assembly line worker assignment and balancing problem), cuja ocorrência é mais comum em linhas de CTDs. Nosso objetivo consiste em estudar formas eficientes de proporcionar a integração de trabalhadores com deficiência em linhas convencionais. Para tanto, abordamos variações do ALWIBP que consideram: (i) minimização de diferentes funções objetivo (número de estações ou tempo de ciclo); (ii) linha de produção com leiautes distintos (simples ou em U); (iii) incertezas quanto ao tempo de execução de cada tarefa (abordagem robusta); (iv) estratégias de rotação de tarefas ou alocação de trabalhadores com deficiência na linha com espaçamento regular. Para cada uma destas extensões, foram desenvolvidos formulações matemáticas, métodos de resolução e novos conjuntos de instâncias teste. Experimentos computacionais indicam possibilidades de adaptação de linhas de produção convencionais à inserção de trabalhadores com deficiência, a custos adicionais baixos ou quase nulos. Portanto, este trabalho oferece alternativas para uma maior flexibilidade na integração de pessoas com deficiência, tornando-os tão eficientes quanto qualquer outro trabalhador denominado \"convencional\". / A number of studies show that a large percentage of disabled people are excluded from the labor market, in particular in developing countries. In order to deal with this problem, one can highlight the importance of Sheltered Work Centers for Disabled (SWDs). These organizations employ disabled workers in various corporate sectors, giving them initial opportunities and preparing them so that they can be later integrated into the conventional labor market. Many of these centers operate assembly lines, the main object of study of this thesis. Our study considers an ideally later stage of SWDs, related with the insertion of disabled workers in conventional assembly lines. The demand for studies in this field has grown over the years, due to corporate social responsibility policies and legal requirements such as \"quotas legislations\", present in many countries. Planning the operation of assembly lines with disabled workers involves a series of challenges due to the heterogeneity among workers, which are reflected in task times being worker dependent. This results in a double allocation problem, where decisions must determine both the tasks and the workers to be assigned to the stations, in order to optimize some efficiency measure. The conventional assembly line balancing with a parcel of disabled workers is known as the assembly line worker integration and balancing problem (ALWIBP), being a particular case of the assembly line worker assignment and balancing problem (ALWABP), which occurance is more common in SWDs. Our goal consists in studying efficient ways to promote the integration of people with disabilities in conventional assembly lines. For that, we address ALWIBP variants that consider: (i) minimization of different objective functions (number of stations or cycle time); (ii) different assembly line layouts (simple or U-shaped); (iii) uncertainties on task execution times (robust approach); (iv) job rotation strategies or allocation of disabled workers in the line with regular spacing. For each of these extensions, we develop mathematical formulations, solution methods and new sets of benchmark instances. Computational experiments indicate possibilities for adapting conventional assembly lines to the insertion of disabled workers, at low or close to null additional costs. Therefore, this study offers alternatives ways of increasing exibility in the integration of people with disabilities, making them as efficient as any other conventional worker.

Mixed-Integer Programming has been a vital tool for the chemical engineer in the recent decades and is employed extensively in process design and control. This dissertation presents some new Mixed-Integer Programming formulations developed for two well-studied problems, one with a central role in the area of Optimisation, the other of great interest to the chemical industry. These are the Travelling Salesman Problem and the problem of scheduling cleaning actions for heat exchanger networks subject to fouling. The Travelling Salesman Problem finds a plethora of applications in many scientific disciplines, Chemical Engineering included. None of the mathematical programming formulations proposed for solving the problem considers fewer than O(n^2) binary degrees of freedom. The first part of this dissertation introduces a novel mathematical description of the Travelling Salesman Problem that succeeds in reducing the binary degrees of freedom to O(nlog2(n)). Three Mixed-Integer Linear Programming formulations are developed and the computational performance of these is tested through computational studies. Sophisticated methods are now available for scheduling the cleaning actions for networks of heat exchangers subject to fouling. In the majority of these, only one form of cleaning is used, which restores the performance of the exchanger back to its clean level. A recent study revised the scheduling problem for the case where there are several cleaning methods available. The second part of this dissertation extends their approach, developed for individual units, to heat exchanger networks and explores the concept of selection of cleaning techniques further. Mixed-Integer Programming formulations are proposed for the scheduling task, for two fouling scenarios: (i) chemical reaction fouling and (ii) biological fouling. A series of results are presented for the implementation of the scheduling formulations to networks of different sizes.

This master's thesis describes modified Chinese Postman Problems. These Problems are solved by (mixed) integer linear programming. The modified problems and also used approach (integer programming) belong at least to the NP complexity class. The thesis analyzes, compares and estimates computational complexity of each model. Based on this analysis, usability of described models for solving real-life problems is deduced. The models are focused on problems in urban environment. Therefore, it is possible to apply these models on problems like optimization of a waste collection or road maintenance. Graph and problem generator is programmed for purposes of this thesis.

abstract: In this work, the stacked values of battery energy storage systems (BESSs) of various power and energy capacities are evaluated as they provide multiple services such as peak shaving, frequency regulation, and reserve support in an ‘Arizona-based test system’ - a simplified, representative model of Salt River Project’s (SRP) system developed using the resource stack information shared by SRP. This has been achieved by developing a mixed-integer linear programming (MILP) based optimization model that captures the operation of BESS in the Arizona-based test system. The model formulation does not include any BESS cost as the objective is to estimate the net savings in total system operation cost after a BESS is deployed in the system. The optimization model has been formulated in such a way that the savings due to the provision of a single service, either peak shaving or frequency regulation or spinning reserve support, by the BESS, can be determined independently. The model also allows calculation of combined savings due to all the services rendered by the BESS. The results of this research suggest that the savings obtained with a BESS providing multiple services are significantly higher than the same capacity BESS delivering a single service in isolation. It is also observed that the marginal contribution of BESS reduces with increasing BESS energy capacity, a result consistent with the law of diminishing returns. Further, small changes in the simulation environment, such as factoring in generator forced outage rates or projection of future solar penetration, can lead to changes as high as 10% in the calculated stacked value. / Dissertation/Thesis / Masters Thesis Electrical Engineering 2020

This thesis introduces a Large Neighborhood Search (LNS) method to solve a multi-processor avionics scheduling problem. In a typical scheduling problem, tasks are scheduled with exact starting times. In this thesis however, tasks will instead be assigned to disjoint time segments, called buckets. For an assignment to be feasible, precedence relations and capacity constraints related to network and computing resources need to be fulfilled. The introduced LNS method relies on solving Mixed-Integer Programming (MIP)-models. To make progress in the search for a feasible assignment, we construct a MIP-model that allows violation of the problem constraints at a cost of increased objective value. The LNS method uses two operators, a destroy operator that chooses a set of tasks that are allowed to change buckets, and a repair operator that through solving the MIP-model creates a new schedule. This thesis develops 11 types of destroy operators and 30 (concrete) variants of them. The MIP-based LNS is evaluated on a set of 60 instances with up to 84 000 tasks and 21 processors. The instances belongs to six categories of varying difficulty. The MIP-based LNS solves 50 instances within our time limit, and the largest instance solved has 77 757 tasks. This is significantly better than solving the complete MIP-model in a single step. With this approach only 36 instances can be solved within our time limit and the largest instance solved has 48554 tasks.

This thesis presents a case study of mathematical production scheduling optimization applied on Arla Foods AB’s production of dairy products. The scheduling was performed as a possible remedy for problems caused by overcrowded finished goods warehouse. Based on the scheduling, conclusions were made on whether the existing two-shift production is sufficient or if an additional night shift should be introduced. In parallel, an empirical and theoretical analysis on the perceived effects of night shift work on employees was conducted. For the optimization, mixed integer programming was used to model the production context through a discrete time scheduling lot-sizing model developed in this thesis. The model developed and implemented on Arla Foods AB contributes to the research field through its feature of relatively low complexity enabling scheduling of extensive production systems when applied in industrial contexts where products may be categorized. The thesis concludes that mathematical production scheduling can solve Arla Foods AB’s production problematics and suggests reallocation of the existing shifts for the purpose of reduced costs and acceptable warehouse levels. This reallocation would incur production during inconvenient hours whereas management remedies reducing negative effects of night shift work are identified. / Denna avhandling innefattar en studie av matematisk optimering av produktionsscheman applicerad på Arla Foods ABs produktion av mejeriprodukter. Schemaläggningen utfördes som en möjlig lösning på produktionsproblematik orsakad av överfyllda färdigvarulager. Utifrån de optimerade produktionsschemana drogs slutsatser kring om dagens produktionsstruktur på två skift är tillräcklig eller om introduktion av ett andra nattskift skulle vara fördelaktig. Parallellt med detta presenteras en empirisk och teoretisk studie kring de produktionsanställdas uppfattning kring effekter av att arbeta nattskift. För optimeringen har heltalsoptimering (eng: mixed integer programming) använts för modellering av produktionen genom en produktionsplaneringsmodell med diskret tidsrepresentation (eng: discrete time scheduling lot-sizing model ) som utvecklas i denna avhandling. Denna model, som även appliceras på Arla Foods ABs produktion, presenteras i detalj och karaktäriseras av låg komplexitet vilket möjliggör schemaoptimering av omfattande produktionssystem givet att produktportföljen kan kategoriseras i produktgrupper med liknande egenskaper ur ett produktionsperspektiv. Avhandlingen fastslår att matematisk optimering av produktionsscheman har potential att lösa produktionsproblematiken på Arla Foods AB och föreslår en reallokering av den nuvarande produktionen för minskade kostnader och utjämnade nivåer i färdigvarulager. Produktionsomläggningen skulle innebära produktion under obekväm arbetstid vilket föranleder en analys av initiativ som har potential att minska de negativa effekterna av nattskiftarbete för de produktionsanställda.

The ambition of this project is to contribute to the development of optimisation techniques for underground mining. This resulted in a mathematical model to optimise a type of underground transportation system called the ramp. The ramp is a tunnel from the underground mining areas which trucks use to transport material up to the surface. We consider the case where the ramp only fits one truck at a time and it therefore needs passing bays where trucks can meet. We were inspired by an article which optimised the positions of the passing bays and the schedule for the trucks, during a certain time period. We extended that work by proposing a new mathematical model that can handle a more general and complex mine. The result from optimally solving the model gives the positioning of the passing bays and a schedule which completes a number of trips down and up the ramp as quickly as possible. The model can be used both for long-term and short-term planning. The long-term planning regards the positions of the passing bays. The model can therefore be used before the passing bays are constructed to gain insights about where to place them. The short-term planning is about finding an optimal trip schedule given the placement of the passing bays. The model can therefore also be used to provide a haulage schedule for an upcoming time period.

Under the envisioned smart city paradigm, there is an increasing demand for the coordinated operation of our infrastructure networks. In this context, this thesis puts forth a comprehensive toolbox for the optimization of electric power and water distribution networks. On the analytical front, the toolbox consists of novel mixed-integer (non)-linear program (MINLP) formulations; convex relaxations with optimality guarantees; and the powerful technique of McCormick linearization. On the application side, the developed tools support the operation of each of the infrastructure networks independently, but also towards their joint operation. Starting with water distribution networks, the main difficulty in solving any (optimal-) water flow problem stems from a piecewise quadratic pressure drop law. To efficiently handle these constraints, we have first formulated a novel MINLP, and then proposed a relaxation of the pressure drop constraints to yield a mixed-integer second-order cone program. Further, a novel penalty term is appended to the cost that guarantees optimality and exactness under pre-defined network conditions. This contribution can be used to solve the WF problem; the OWF task of minimizing the pumping cost satisfying operational constraints; and the task of scheduling the operation of tanks to maximize the water service time in an area experiencing electric power outage. Regarding electric power systems, a novel MILP formulation for distribution restoration using binary indicator vectors on graph properties alongside exact McCormick linearization is proposed. This can be used to minimize the restoration time of an electric system under critical operational constraints, and to enable a coordinated response with the water utilities during outages. / Master of Science / The advent of smart cities has promoted research towards interdependent operation of utilities such as water and power systems. While power system analysis is significantly developed due to decades of focused research, water networks have been relying on relatively less sophisticated tools. In this context, this thesis develops Advanced efficient computational tools for the analysis and optimization for water distribution networks. Given the consumer demands, an optimal water flow (OWF) problem for minimizing the pump operation cost is formulated. Developing a rigorous analytical framework, the proposed formulation provides significant computational improvements without compromising on the accuracy. Explicit network conditions are provided that guarantee the optimality and feasibility of the obtained OWF solution. The developed formulation is next used to solve two practical problems: the water flow problem, that solves the complex physical equations yielding nodal pressures and pipeline flows given the demands/injections; and an OWF problem that finds the best operational strategy for water utilities during power outages. The latter helps the water utility to maximize their service time during power outages, and helps power utilities better plan their restoration strategy. While the increased instrumentation and automation has enabled power utilities to better manage restoration during outages, finding an optimal strategy remains a difficult problem. The operational and coordination requirements for the upcoming distributed resources and microgrids further complicate the problem. This thesis develops a computationally fast and reasonably accurate power distribution restoration scheme enabling optimal coordination of different generators with optimal islanding. Numerical tests are conducted on benchmark water and power networks to corroborate the claims of the developed formulations.

This research presents a bi-level stochastic network interdiction model on an attack graph to enable a risk-averse resource constrained cyber network defender to optimally deploy security countermeasures to protect against attackers having an uncertain budget. This risk-averse conditional-value-at-risk model minimizes a weighted sum of the expected maximum loss over all scenarios and the expected maximum loss from the most damaging attack scenarios. We develop an exact algorithm to solve our model as well as several acceleration techniques to improve the computational efficiency. Computational experiments demonstrate that the application of all the acceleration techniques reduces the average computation time of the basic algorithm by 71% for 100-node graphs. Using metrics called mean-risk value of stochastic solution and value of risk-aversion, numerical results suggest that our stochastic risk-averse model significantly outperforms deterministic and risk-neutral models when 1) the distribution of attacker budget is heavy-right-tailed and 2) the defender is highly risk-averse.