Mario Costa

M Agostinho Agra

Simone De Lima Martins

M Igor

Machado Coelho

M Me

Ayse Nur Arslan

M David

Sotelo Pinheiro

M Yuri

Abitbol De Menezes Frota

Rosa Figueiredo

M Serigne Gueye

Scheduling optimization applied to the electricity, oil and gas industries Optimisation de l

Keywords: Scheduling optimization applied to the electricity, oil and gas industries. Other [ Scheduling optimization applied to the electricity, oil and gas industries Robust Optimization. Smart grid. Energy. Scheduling. Permutation Flow Shop

Scheduling optimization applied to the electricity, oil and gas industries

Mario Costa Levorato Junior

Titre : Optimisation de l'ordonnancement appliquée à l'industrie du pétrole Mot clés : optimisation robuste, micro-réseaux, engagements flexibles, planification énergétique, ordonnancement, flow shop.

Résumé : Ce travail de recherche propose de nouvelles approches de solutions pour deux problèmes importants dans les domaines de l'énergie, du pétrole et du gaz, qui impliquent des paramètres d'entrée incertains.

Dans le contexte des réseaux d'énergie intelligents, le premier problème concerne la réalité des micro-réseaux qui échangent de l'énergie avec le réseau principal pour vendre leur surplus de production (provenant de sources d'énergie renouvelables) ou acheter un montant supplémentaire pour soutenir la demande des consommateurs locaux. Dans ce scénario, les dispositifs de contrôle intelligents sont des éléments importants, exécutant la planification énergétique en temps réel en fonction des fluctuations de la production et de la consommation. Comme on pouvait s'y attendre, la production et l'approvisionnement en électricité du réseau principal deviennent plus imprévus et risqués à mesure que les quantités d'énergie échangées oscillent au fil du temps. La première partie de la thèse étudie un framework de souscription des contrats énergétiques flexibles et bilatéraux, établis entre des fournisseurs d'électricité et un client. La souscription est liée à une stratégie de commande en temps réel (RTCS), adaptée à la planification énergétique des micro-réseaux avec des incertitudes dans la production et la consommation d'électricité.

Les principaux produits développés sont un modèle d'optimisation robuste multipériode embarqué, capable de fournir des solutions pour l'échange d'énergie sur plusieurs périodes, minimisant le coût par le client dans le pire des cas, ainsi qu'un ensemble de stratégies de contrôle pour la planification énergétique en temps réel. Au cours de la recherche, le modèle d'optimisation robuste initial a été amélioré pour représenter l'incertitude budgétisée, permettant des solutions moins conservatrices qui sont, en même temps, plus flexibles et moins chères, tout en assurant une protection contre les pires scénarios. La solution proposée a été testée à l'aide de données de consommation et de production collectées auprès d'un micro-réseau énergétique réel dans un centre de recherche à Tsukuba, au Japon.

S'appuyant sur un ensemble de contrats d'achat d'énergie inspirés du monde réel, les résultats de simulation ont confirmé l'efficacité de différentes stratégies de contrôle robustes, selon les types de scénarios d'incertitude. Pour des niveaux de protection spécifiques, les stratégies de contrôle robustes ont dominé les stratégies déterministes (naïves) dans toutes les mesures de coût opérationnel et de fiabilité du système.

Les résultats obtenus avec une étude de cas montrent que l'efficacité de chaque solution robuste dépendra du profil de charge du microréseau et de la production renouvelable, qui varient selon la saison de l'année. D'où l'importance de l'ensemble d'incertitudes budgétées, qui fournit un ensemble de solutions robustes, avec différents niveaux de protection, parmi lesquelles le décideur peut choisir. Le deuxième front de recherche est lié à la planification de la production sous incertitude, en particulier le problème d'ordonnancement connu sous le nom de Robust Permutation Flow Shop Scheduling. Nous utilisons l'approche de l'incertitude budgétaire, où les temps de traitement des opérations varient dans un intervalle donné. Le scénario le plus défavorable est borné par un paramètre de budget Γ, qui limite le nombre maximum d'opérations dont les temps de traitement peuvent osciller à leurs valeurs les plus défavorables. Le grand avantage de cette variante du problème consiste à ajuster le niveau de conservatisme de la solution, obtenant ainsi un équilibre entre le coût de la solution et la robustesse dans le pire des cas. Nous avons développé des méthodes de résolution pour deux fonctions objectifs différentes : makespan et somme pondérée des temps d'exécution des tâches. A notre connaissance, il s'agit du premier travail permettant d'obtenir des solutions robustes optimales aux deux objectifs.

Concernant la fonction objectif makespan, nous avons étendu deux formulations MILP classiques pour le cas déterministe et les avons combinées avec un cadre de génération de colonnes et de contraintes (Column-and-Constraint Generation -C&CG). A cet effet, un algorithme de programmation dynamique a également été développé, permettant l'identification des pires scé-narios en temps polynomial. De nombreux résultats expérimentaux ont démontré que l'algorithme proposé était efficace pour obtenir des ordonnancements robustes optimaux pour des problèmes de petite et moyenne taille (y compris des instances de 50 × 2, 100 × 2 et 10 × 5, 15 × 5). De plus, sur la base d'une étude de cas avec deux instances représentatives, nous avons évalué le compromis entre la qualité de la solution et le coût, en comparant des solutions robustes à des solutions déterministes et stochastiques. De plus, selon des simulations basées sur trois distributions de probabilités, ces calendriers robustes ne présentaient qu'un faible surcoût dans le coût de solution attendu.

Nous avons également développé une métaheuristique de recherche adaptative randomisée gloutonne (GRASP) pour obtenir des solutions efficaces pour les instances de problèmes volumineux (jusqu'à 100 × 50). L'évaluation des performances de GRASP a nécessité l'adaptation d'instances de la littérature, telles que les instances bien connues de Taillard. Les résultats expérimentaux ont démontré que l'algorithme GRASP est efficace pour obtenir des ordonnancements robustes optimaux pour des problèmes de petite et moyenne taille, par rapport à la méthode de résolution exacte C&CG. L'évaluation était basée sur 4 ensembles de problèmes de test et il a été démontré que GRASP produisait des solutions optimales ou quasi optimales sur toutes ces instances.

Enfin, nous avons exploré le flow shop robuste avec l'objectif somme pondérée des temps de réalisation des tâches (weighted sum of job completion times, en anglais), où les temps de traitement des opérations sont sujets à l'incertitude. Dans le contexte de l'industrie pétrolière et gazière, cette variante du flow shop est associée au planning de maintenance des plates-formes pétrolières. Lorsque chaque équipement fait l'objet d'une maintenance, certaines opérations d'assistance doivent voir leur ordre d'exécution respecté. Et pour terminer cet ensemble défini de tâches, les puits de pétrole doivent être fermés uniquement pour rouvrir à la production à la fin du calendrier. L'objectif, dans ce cas, est de trouver un calendrier qui minimise la perte de production de pétrole causée par le temps pendant lequel chaque puits de pétrole est resté fermé pour maintenance. Sur la base du cadre de génération de colonnes et de contraintes, nous avons pu obtenir des solutions exactes pour des instances d'une taille allant jusqu'à 15 × 5. En plus, nous avons proposé une étude de cas appliquée à l'industrie pétrolière et gazière, en utilisant des données réelles, obtenues à partir de l'historique des plates-formes pétrolières brésiliennes. proaches for two important problems in the areas of energy, oil and gas, which involve uncertain input parameters.

In the context of smart grids, the first problem addresses the reality of microgrids which trade energy with the main grid to either sell its production surplus (from renewable energy sources) or buy an additional amount to support local consumers' demand. In this scenario, smart control devices are important elements, executing realtime energy scheduling according to fluctuations in production and consumption. As we might expect, the main grid's power generation and supply becomes more unscheduled and risky as energy trading quantities oscillate over time. The first part of the work studies a flexible bilateral energy contract subscription framework, established between electricity suppliers and a client. The framework is coupled with a real-time command strategy (RTCS), suited for energy scheduling of microgrids with uncertainty in both production and consumption.

The main products are an embedded Robust Optimization model, capable of providing solutions for multi-period-ahead trading of energy, while minimizing the microgrid's worst-case cost, as well as a set of control strategies for real-time energy scheduling. During the research, the initial robust optimization model was improved to represent budgeted uncertainty, allowing for less conservative solutions that are, at the same time, more flexible and less expensive, while providing protection against worst-case scenarios. The proposed solution was tested using consumption and production data collected from a real microgrid in a research lab in Tsukuba, Japan.

Relying on a set of real-world-inspired energy purchase contracts, simulation experiments have confirmed the efficacy of different robust-based RTCS strategies, according to scenario types. For specific protection levels, the robust RTCS was able to dominate the naïve deterministic RTCS in all operational cost and system reliability metrics. Results obtained with a case study show that the effectiveness of each robust solution will depend on the microgrid's load profile and renewable production, which vary according to the season of the year. Hence the importance of the budgeted uncertainty set, which provides a pool of robust solutions, with different protection levels, the decisionmaker can choose from.

The second research avenue is related to production planning under uncertainty, in particular the scheduling problem known as Robust Permutation Flow Shop Scheduling. We adopt the budgeted uncertainty approach, where operation processing times are expected to vary within a given interval. Moreover the worst-case scenario is bounded by a budget parameter Γ, which limits the maximum number of operations whose processing times may oscillate to their worst-case values. The great advantage of this variant of the problem consists in adjusting the level of conservatism of the solution, thus obtaining a balance between solution cost and robustness in the worst case. We developed solution methods for two different objective functions: makespan and weighted sum of job completion times. To our knowledge, this is the first work to obtain optimal robust solutions to both objectives.

Regarding the makespan objective function, we extended two classical MILP formulations for the deterministic case and combined them with a Column-and-Constraint Generation (C&CG) framework. For this purpose, a dynamic programming algorithm was also developed, allowing the identification of worst-case scenarios in polynomial time. Extensive experimental results demonstrated that the proposed algorithm was effective in obtaining optimal robust schedules for small and medium-sized problems (including 50 × 2, 100 × 2 and 10 × 5, 15 × 5 instances). Additionally, based on a case study with two representative instances, we have assessed the trade-off between solution quality and cost, comparing robust solutions to deterministic and stochastic ones. Also, according to simulations based on three probability distributions, such robust schedules presented only a small overhead in the expected solution cost.

We also developed a greedy randomized adaptive search (GRASP) metaheuristic to obtain efficient solutions for large problem instances (up to 100 × 50). The evaluation of GRASP performance required the adaptation of literature instances, such as the well-known Taillard instances. Experimental results have demonstrated that the GRASP algorithm is efficient in obtaining optimal robust schedules for small and mediumsized problems, when compared to the C&CG exact solution method. The evaluation was based on 4 sets of test problems and GRASP has been shown to produce optimal or near-optimal solutions on all of these instances.

Finally, we explored the robust flow shop with the weighted sum of job completion times objective, where the processing times of operations are subject to uncertainty. In the context of the oil and gas industry, this variant of the flow shop is associated with the maintenance schedule for oil rigs.

When each piece of equipment is subject to maintenance, certain assistance operations must have their order of execution respected. Additionally, to complete this defined set of tasks, oil wells must be shut down only to reopen to production at the end of the schedule. The objective, in this case, is to find a schedule that minimizes the loss of oil production caused by the time that each oil well has remained closed for maintenance. Based on the Column-and-Constraint Generation framework, we were able to obtain exact solutions to instances of size up to 15 × 5. In addition, we proposed a case study applied to the oil and gas industry, using real data, obtained from the history of Brazilian oil platforms.

Título: Otimização de agendamento aplicada às indústrias de eletricidade, petróleo e gás Palavras-chave: Otimização Robusta. Smart grid. Energia. Agendamento. Programação. Permutation Flow Shop.

Resumo: Esta tese propõe novas abordagens de solução para dois problemas importantes nas áreas de energia, petróleo e gás, que envolvem parâmetros de entrada incertos.

No contexto das redes elétricas inteligentes (smart grids), o primeiro problema aborda a realidade das micro-redes (microgrids) que comercializam energia com a rede principal para vender seu excedente de produção (oriundo de fontes renováveis de energia) ou comprar um volume adicional para atender à demanda dos consumidores locais. Nesse cenário, dispositivos de controle inteligentes são elementos importantes, executando a programação de energia em tempo real de acordo com as oscilações de produção e consumo. Como poderíamos esperar, a geração e o fornecimento de energia da rede principal apresentam mais incerteza e risco, pois as quantidades de energia comercializadas oscilam ao longo do tempo. A primeira parte do trabalho estuda uma estrutura flexível de assinatura de contratos bilaterais de energia, estabelecida entre fornecedores de energia elétrica e um cliente. A estrutura de contratação é acoplada a uma estratégia de comando em tempo real (RTCS), adaptada à programação de energia de microredes com incerteza tanto na produção quanto no consumo de eletricidade.

Os principais produtos são um modelo de Otimização Robusta multi-período embarcado, capaz de fornecer soluções para comercialização de energia em vários períodos, minimizando o custo pago pelo cliente no pior caso, bem como um conjunto de estratégias de controle para programação de energia em tempo real. Durante a pesquisa, o modelo inicial de Otimização Robusta foi aprimorado para representar a incerteza orçamentária (budgeted uncertainty ), permitindo soluções menos conservadoras, mas ao mesmo tempo mais flexíveis e menos dispendiosas, sem abrir mão da proteção contra os piores cenários. A solução proposta foi testada usando dados de consumo e produção coletados de uma microrede instalada em um laboratório de pesquisa em Tsukuba, no Japão.

Baseando-se em um conjunto de contratos de compra de energia inspirados no mundo real, experimentos de simulação confirmaram a eficácia de diferentes estratégias de controle robustas, de acordo com os tipos de cenário de incerteza. Para níveis de proteção específicos, as estratégias de controle robustas foram capazes de dominar as estratégias determinísticas (ingênuas) em todas as métricas de custo operacional e confiabilidade do sistema. Os resultados obtidos com um estudo de caso mostram que a eficácia de cada solução robusta dependerá do perfil de carga da micro-rede e da produção renovável, que variam de acordo com a estação do ano. Daí a importância da utilização da incerteza orçamentária, que fornece um conjunto de soluções robustas, com diferentes níveis de proteção, entre as quais o decisor pode escolher a mais apropriada.

O segundo estudo envolve o planejamento da produção sob incerteza, em particular o problema de programação conhecido como Robust Permutation Flow Shop Scheduling. Adotamos a abordagem de Otimização Robusta conhecida como budgeted uncertainty, onde se espera que os tempos de processamento das operações variem dentro de um determinado intervalo. Além disso, o cenário de pior caso é limitado por um parâmetro de orçamento Γ, que limita o número máximo de operações cujos tempos de processamento podem oscilar para seus valores de pior caso. A grande vantagem desta variante do problema consiste em ajustar o nível de conservadorismo da solução, obtendo assim um equilíbrio entre custo da solução e robustez no pior caso. Métodos de solução foram então desenvolvidos para duas funções objetivo diferentes: makespan e soma ponderada dos tempos de término dos jobs. Até onde sabemos, este é o primeiro trabalho que conseguiu obter soluções ótimas robustas para ambas as funções objetivo.

Em relação à função objetivo makespan, estendemos duas formulações clássicas de MILP para o caso determinístico e as combinamos com uma estrutura de geração de colunas e restrições (Column-and-Constraint Generation -C&CG). Para tanto, também foi desenvolvido um algoritmo de programação dinâmica, que permite a identificação dos cenários de pior caso em tempo polinomial. Extensos resultados experimentais demonstraram que o algoritmo proposto foi eficaz na obtenção de soluções robustas ótimas para instâncias de pequeno e médio porte (incluindo 50 × 2, 100 × 2 e 10 × 5, 15 × 5). Adicionalmente, com base em um estudo de caso com duas instâncias representativas, avaliamos o trade-off entre qualidade e custo da solução, comparando soluções robustas com determinísticas e estocásticas. Além disso, de acordo com simulações baseadas em três distribuições de probabilidade, os cronogramas robustos obtidos apresentaram apenas uma pequena elevação no custo esperado da solução.

Também foi desenvolvida uma metaheurística de busca adaptativa randomizada gulosa (GRASP) para obter soluções eficientes para instâncias grandes do problema (até 100 × 50). A avaliação de desempenho do GRASP exigiu a adaptação de instâncias da literatura, como as conhecidas instâncias Taillard. Resultados experimentais demonstraram que o algoritmo GRASP foi eficiente na obtenção de soluções ótimas robustas para instâncias de pequeno e médio porte, quando comparado ao método exato de solução C&CG. A avaliação foi baseada em 4 conjuntos de problemas de teste e o GRASP foi capaz de obter soluções ótimas ou quase ótimas em todas essas instâncias.

Por fim, exploramos o flow shop robusto com o objetivo soma ponderada dos tempos de término dos jobs, onde os tempos de processamento das operações estão sujeitos à incerteza. No contexto da indústria de óleo e gás, esta variante do flow shop está associada ao cronograma de manutenção das plataformas de petróleo. Quando cada equipamento é submetido à manutenção, determinadas operações devem ter sua ordem de execução respeitada. Além disso, para concluir esse conjunto definido de tarefas, os poços de petróleo devem ser fechados, podendo ser reabertos apenas no final do cronograma. O objetivo, neste caso, é encontrar um cronograma que minimize a perda de produção de petróleo causada pelo tempo que cada poço de petróleo permaneceu fechado para manutenção. Com base no framework de Column-and-Constraint Generation, conseguimos obter soluções exatas para instâncias de tamanho até 15 × 5. Além disso, propusemos um estudo de caso aplicado à indústria de óleo e gás, utilizando dados reais, obtidos a partir do histórico das plataformas de petróleo brasileiras.

INTRODUCTION

Context

This research proposes new robust solution approaches for two crucial problems in the energy, oil, and gas industries, involving uncertain input parameters. The first one concerns the operation of microgrids with uncertain production and consumption, including electricity trading and real-time energy scheduling. The robustness of the energy grid, i.e., the capacity to be resilient to demand fluctuations, has always been a topic of extreme importance. More recently, with the advent of hybrid energy systems, new issues related to renewable energy production (e.g., wind, biomass, sun) and consumption (i.e., electric cars, batteries) have become apparent. Optimization problems appear in the operation of these systems, and uncertainty ought to be considered.

The second problem concerns the Oil and Gas industry, particularly oil-well maintenance scheduling. Among several exploration and production problems, planning and scheduling of oil platforms are of main interest. A frequent objective in these problems is to determine the optimum values of decision variables to maximize profits, increase production rates and reduce production costs. Nonetheless, considering uncertainty in such optimization problems is extremely important, given the risky nature of the industry.

It is worth noting that the classic paradigm for decision making in Mathematical Programming consists in developing a model which assumes that the input data is accurate and equal to nominal values. In other words, the influence of data uncertainties on the quality and feasibility of the model are not considered. Therefore, if data can assume different values than the nominal ones, several restrictions of the problem under analysis can be violated. The optimal solution obtained from nominal data may not be appropriate or even possible. This context evidences the need to develop "robust" models, as flexible as possible to data uncertainty.

When optimal decisions are calculated based on uncertain data, naïve solution approaches include applying a margin of error to the decision or considering a set of cases to obtain a balanced judgment. Although useful, the success of these approaches depends on decision makers' abilities and the completeness of available data. Moreover, if business complexity increases, it may be impossible to adopt these strategies. A common solution approach that has been used in Operational Research for a long time is Stochastic Optimization (SO) [START_REF] Daniel | Stochastic models in operations research: stochastic optimization[END_REF], whose fundamental premise states that the uncertainty can be described by using probabilities.

Part , Chapter 1 -Introduction

On the other hand, Robust Optimization (RO) [START_REF] Ben | Robust optimization-methodology and applications[END_REF] provides a different approach for optimizing problems under uncertain conditions. According to it, the objective and constraint functions are only assumed to belong to certain sets in function space. Uncertain problem parameters are modeled as belonging to a set of uncertainties, which contrasts with the more traditional modeling approach which uses probability distributions. The intention is to make a feasible decision no matter what the constraints turn out to be, and optimal for the worst-case objective function.

RO is a suitable modeling approach when the uncertainty interval is known, but not necessarily the probability distribution. Input data will assume an uncertain value in a specified fixed range. This way, calculated solutions will be available, considering all constraints, when model parameters vary within the ranges of uncertainty. If this is too restrictive, it is also possible to define with which probability the solution will satisfy restrictions. The robustness of decisions is measured in terms of better performance considering all input values. While Stochastic Optimization can originate large models if several scenarios have to be analyzed (thus making it important to limit the number of scenarios considered, and unfortunately making the results less robust), Robust Optimization models in general grow only slightly when uncertainty is added and, therefore, can be solved efficiently.

RO is currently becoming a popular approach, applied in several areas of Mathematical Programming, ranging from Mixed Integer Linear Programming (MILP) to non-linear optimization. Moreover, its solution methods have already been applied to several problems in the energy, and oil and gas industries, including:

-Refinery operational planning [START_REF] Leiras | Petroleum refinery operational planning using robust optimization[END_REF] and scheduling of crude oil operations, an important part of overall refinery operations [START_REF] Wang | Robust optimization model for crude oil scheduling under uncertainty[END_REF][START_REF] Li | Scheduling of crude oil operations under demand uncertainty: A robust optimization framework coupled with global optimization[END_REF].

-In Field Appraisal and Development, optimization of oil production under uncertainty (including the Recovery Factor (RF) of an oil field) can benefit from Robust Optimization [START_REF] Gijs Van Essen | Robust waterflooding optimization of multiple geological scenarios[END_REF][START_REF] Yasari | Application of multi-criterion robust optimization in water-flooding of oil reservoir[END_REF]. In particular, many RO models are focused on the recovery phases of a petroleum reservoir [START_REF] Gijs Van Essen | Robust waterflooding optimization of multiple geological scenarios[END_REF][START_REF] Yang | Robust optimization of SAGD operations under geological uncertainties[END_REF][START_REF] Yasari | Application of multi-criterion robust optimization in water-flooding of oil reservoir[END_REF].

-Maritime transportation [START_REF] Agra | The robust vehicle routing problem with time windows[END_REF] is a common problem in the oil and gas industry, where routing problems are known to include many types of uncertainty related to unforeseen events (e.g., bad weather, mechanical breakdowns, and port congestion).

-Planning the transition to hybrid electric vehicules [START_REF] Amir H Hajimiragha | A robust optimization approach for planning the transition to plug-in hybrid electric vehicles[END_REF].

-Sustainable energy planning [START_REF] Babonneau | Robust optimization for environmental and energy planning[END_REF][START_REF] Koo | Integration of CCS, emissions trading and volatilities of fuel prices into sustainable energy planning, and its robust optimization[END_REF][START_REF] Figueiredo | Robust Control Command Strategies in a Contract-Based Collaboration Framework[END_REF].

A robust contract collaboration framework for smart grids

In the context of smart grids, the first problem studied in this thesis is related to the collaboration established between a partner (energy suppliers) and its clients (individuals, households or 1.3. Robust Scheduling applied to Oil and Gas industry businesses, also known as end consumers) through the engagement on one or more day-ahead energy contracts. For a client's microgrid, the optimization framework allows for the two-way flow of electricity, with periodic energy market transactions (buying or selling energy), alternative energy sources (e.g., solar panels, wind turbines), electric cars, and energy storage systems (batteries). To our knowledge, this work is the first one to consider multiple energy contracts in microgrid energy management.

Undoubtedly, the proposed model's most significant feature involves mitigating the effects of uncertainty in energy production and consumption through Robust Optimization techniques. The final product is a real-time control algorithm embedded in smart control devices, providing a costeffective strategy for buying and selling energy at each period of the day. Such strategy benefits not only the clients, which can make considerable savings, but also the partner, since the amount of energy bought out of engaged contracts tends to be minimized, thus reducing unexpected peaks in energy consumption (increasing predictability in consumer demands).

Robust Scheduling applied to Oil and Gas industry

Exploration and production of hydrocarbons 1 constitute a high-risk endeavor. While geologists deal with uncertainties related to structure, reservoir seal, and hydrocarbon charge, on the other side, economic evaluations also have to consider risk when analyzing costs, the economic viability of reservoirs, technology, and oil price. Indeed, even at the production stage, engineering parameters include a high level of uncertainties concerning critical variables, such as infrastructure, production schedule, quality of oil, and operational costs. All these uncertainties involve high-risk decision scenarios, which present no guarantee that hydrocarbon resources will be discovered and developed.

In fact, the need for decision-making under conditions of risk and uncertainty has always been common in the oil industry. However, only in 1956 the economics and risk of exploration were analyzed using probability theory and explicit modeling of oil and gas exploration stages [4]. Making important decisions in the petroleum industry requires the incorporation of significant uncertainties, long time horizons, multiple alternatives, and complex value issues into the decision model.

In this thesis, we focus on the maintenance scheduling of oil wells. When the pieces of equipment of each well go through maintenance, certain support operations must have their order of execution respected. The objective is to find a suitable sequence of maintenance tasks that minimizes the loss of oil production caused by the time each oil well remains closed for maintenance. The moment and the order in which the wells are closed and subsequently reopened impact the oil platform's production. Therefore, minimizing the time a set of wells stays closed for maintenance generates 1. Includes all the necessary tasks to obtain oil and gas products, such as basin and plan analysis, leads, prospect evaluation, development stages, facilities, logistics, and management.

Part , Chapter 1 -Introduction financial gains (more oil will be produced), in the order of thousands and even millions of dollars.

In particular, we investigate a variation of the problem known as Permutation Flow Shop. Solving such scheduling problem taking real-world characteristics into account is a challenging task. First, there is the need to solve the problem quickly and efficiently. Additionally, in oil and gas companies, the data used as input to scheduling problems are actually forecasted, i.e., uncertainty is neglected in most cases. The solution methods proposed in this thesis will then focus on developing Robust Optimization models, and new solution approaches. Operation processing times are subject to uncertainty, and the lower and upper bounds of processing times are the only information available.

Challenges

As mentioned before, Robust Optimization provides a different approach to optimization problems under uncertain conditions. According to it, the unknown parameters are modeled as belonging to an uncertainty set, making it a more suitable modeling approach when the uncertainty set is known, but not necessarily the probability distribution. Unlike other robust optimization models, which generate only one conservative solution, the budgeted approach, applied in this thesis, allows the adjustment of the level of conservatism of the solution (protection level), enabling the incorporation of different attitudes toward risk (e.g., risk-averse, risk-neutral, or risk-seeking). As a result, the decision-maker can select the solution that achieves the best balance between robustness and optimality.

Besides the development of the solution method itself, when applying Robust Optimization, one major challenge concerns the quality evaluation of the obtained solutions, i.e., how it compares to deterministic (nominal) and stochastic solutions. Existing works from the literature have provided tools to accomplish this task. In particular, [START_REF] Bertsimas | The Price of Robustness[END_REF] proposed sensitivity analysis, which can be used to assess the price of increasing or decreasing the protection level. Measures such as the price of robustness and hedge value can be used to determine the trade-off between solution quality and cost, comparing robust solutions to deterministic ones.

Additionally, in the RO literature, it is well-known that such a hedge against worst-case costs might come at the price of higher expected costs in the long run. With this in mind, the Monte-Carlo simulation can be applied to compare robust, deterministic, and stochastic solutions, by obtaining a series of measures based on statistical data acquired from a vast number of simulation runs.

Even so, the proposal of comprehensive solution evaluation frameworks remains a challenge. In this thesis, we apply a mixture of the aforementioned techniques, which can be used to evaluate the quality of the obtained solutions and guide the decision-making process.

Contributions

Contributions

In the first part of the thesis, concerning microgrid energy management, we propose the Contract Collaboration Problem (CCP) and its underlying multi-contract microgrid energy subscription framework, based on flexible commitments. We develop a Robust Optimization model under budgeted uncertainty to hedge against worst-case energy costs, coupled with Real-Time Command Strategies (RTCS) for microgrid energy trading and scheduling. An extensive case study is presented, including simulations on real microgrid data to evaluate the robust model performance. The results demonstrate the effectiveness of the proposed energy contract framework, which could be applied in the near future, along with the introduction of forward, short-term energy trading at the microgrid / local consumer level.

The second part of the thesis explores two robust scheduling problems derived from the classical Permutation Flow Shop Problem. We start with the robust version of the classical makespan objective, which is then used as a research path for the subsequent development of solution approaches to a second problem, based on the total weighted completion time objective.

Concerning the first scheduling problem, we propose an exact solution method, based on Column-and-Constraint Generation, and a GRASP metaheuristic to provide efficient solutions to problems of arbitrary size. In the solution process, we develop two robust counterpart formulations, along with a polynomial-time dynamic programming algorithm to enumerate the worst-case scenarios. The performance of the solution methods is evaluated, as well as the trade-off of robustness price and hedge value, according to different selections of the budget parameter value Γ. Solution quality assessment makes use of some techniques mentioned in Section 1.4.

We then solve the second robust flow shop problem, also under budgeted uncertainty, which now minimizes the worst-case total weighted completion time. The final intent is to provide cost-effective solutions to the real case of the oil-well maintenance scheduling problem, where the objective is to minimize the worst-case value associated with loss of oil production. Similarly to the previous problem, we use a Column-and-Constraint Generation algorithm to obtain exact solutions, based on seven proposed Robust Counterpart (RC) models. Good quality results and low average solution gaps are obtained on both synthetic and real-world problem instances, allowing the application of this solution method to day-to-day maintenance scheduling.

We propose a set of benchmark instances for both variations of the flow shop problem, along with a comprehensive case study to compare the obtained robust solutions to deterministic and stochastic ones, in terms of worst-case and expected solution values. According to simulations based on three probability distributions, it turns out that the cost overhead of the robust solutions is, in fact, negligible, i.e., when analyzing the empirical estimation of the expected solution cost of robust and stochastic solutions (as well as other statistical measures), there are no remarkable differences between them. Even though we cannot generalize it, the behavior observed in the case study does not In summary, the experimental results indicate the feasibility of applying robust solution methods to real-world problem instances, such as the ones from the oil and gas industry, whose current solutions are obtained through methods that disregard either uncertainty or the impact of worstcase scenarios. Based on their risk preferences, decision-makers can then choose an appropriate schedule from a pool of robust solutions with different levels of exposure to uncertainty.

Besides the obtained experimental results and observations about how robust solutions can be competitive in the long run, this thesis also contributes to data and code availability, since we publicly made available all datasets, source code, and results used throughout this thesis, as indicated in each chapter.

Personal Bibliography

All the contributions listed in Section 1.5 allowed us to make the following publications and sub-

Organization

The thesis comprises two different research problems. It is organized into four additional chapters, which we summarize as follows.

In the microgrid context, Chapter 2 presents the Robust Contract Collaboration Problem, the proposed robust framework and details an application to smart energy grids, including a realistic case study based on a research center microgrid in Japan.

Chapter 3 proposes exact and approximate solution approaches for the Robust Permutation

Flow Shop Problem with the makespan objective, where operation processing times are uncertain and vary in a given interval. Based on the concept of budgeted uncertainty, the objective is to obtain a robust scheduling that minimizes the makespan of the restricted worst-case scenario, where only a subset of job processing times will oscillate to their worst-case values.

In its turn, Chapter 4 presents the Robust Permutation Flow Shop scheduling problem that minimizes the worst-case total weighted completion time objective under budgeted uncertainty. Experiments on real instances show that the obtained solution improvement is of great interest to the oil and gas industry.

Finally, Chapter 5 summarizes the research work and proposes some leads to solve the existing limitations. Some major perspectives are also identified.

Chapter 2

THE ROBUST CONTRACT COLLABORATION PROBLEM (RCCP)

Given the advent of smart grids, we have witnessed several technological developments, and new electricity market rules and regulation mechanisms. The use of sensors, online connections, computational resources, and control strategies now plays a crucial role in ensuring reliability, reducing costs, and improving the efficiency of energy networks. Powered by renewable energy sources, microgrids can trade energy with the main grid to either sell its production surplus or buy an additional amount to support local consumers' demand, including flexible loads, such as smart appliances and electric vehicles. In this scenario, smart control devices are important elements, executing real-time energy scheduling according to fluctuations in production and consumption.

As we might expect, the main grid's power generation and supply become more unscheduled and risky as energy trading quantities oscillate over time. In this chapter, based on a flexible energy contract subscription framework, we propose real-time command strategies to be used by smart control devices, and suited for energy scheduling of microgrids with uncertainty in both production and consumption. The main contributions are a Robust Optimization model for contract subscription under budgeted uncertainty, and a set of heuristic control strategies for real-time energy scheduling.

The robust model can provide solutions for multi-period-ahead trading of energy, while minimizing the restricted worst-case cost. An extensive computational case study, conducted on a real microgrid instance, has then confirmed the efficacy of the proposed solution approach.

Introduction to the problem

A microgrid consists of a small-scale integrated energy system that can manage its own generation and storage resources to dynamically supply local consumers' electricity demands [START_REF] Lasseter | Microgrid: a conceptual solution[END_REF]. Since a microgrid can integrate various sources of distributed generation, especially Renewable Energy Sources (RES), an increasing participation of microgrids can help relieve the supply tension of conventional generators in the main grid. However, the high fluctuation of RES production makes energy management more complex and uncertain. Consider, for example, a microgrid powered by a photo-voltaic system. Even if energy consumption follows a regular pattern, it is difficult to predict its renewable generation accurately as it is subject to sudden weather changes. Consequently, the microgrid will present a volatile production profile and sometimes its energy storage capacity may not be able to cope with the instant demand for energy. Therefore the subsequent decision, how much electricity to buy, will inherit a considerable level of uncertainty, which is also undesirable for the main grid, since it introduces risk and higher operational costs.

Other relevant issues concerning microgrids have arised with the introduction of free energy markets. Consumers became able to produce energy (thus being called prosumers) and, in parallel, contract types, market models and pricing schemes have evolved [START_REF] Mitter | Dynamic Pricing and Stabilization of Supply and Demand in Modern Power Grids[END_REF][START_REF] Joe-Wong | Optimized day-ahead pricing for smart grids with device-specific scheduling flexibility[END_REF][START_REF] Morstyn | Bilateral contract networks for peer-to-peer energy trading[END_REF][START_REF] Aussel | A trilevel model for best response in energy demand-side management[END_REF]. In liberalized markets, large-scale generators, suppliers, industrial consumers and other financial intermediaries trade energy in wholesale markets, including day-ahead auctions, where agents submit their bids and offers for delivery of electricity for each hour of the following day, before market closing time.

On the other hand, small-scale prosumers are currently serviced by large suppliers in the retail market. Nonetheless, forward energy trading is expected to happen at the local level, with microgrids and actively managed distribution networks becoming more widespread [START_REF] Cazalet | Transactive energy models[END_REF]. As new challenges related to local purchasing fluctuations of prosumers arise, the main grid must regulate and stabilize the microgrids' energy purchasing behaviors. One way to accomplish this objective is to introduce flexible commitments contracts [START_REF] Ben Tal | Supplier-Retailer Flexible Commitments Contracts: A Robust Optimization Approach[END_REF].

This study addresses a new framework for microgrid energy trading, with the novel introduction of flexible commitments in a multiple contract setting. The impacts of this contract-based framework are also investigated from the viewpoint of microgrid energy management. Consider a time horizon divided into discrete time periods. For each period, one or more contracts are offered, defining either selling or purchasing commitments, and providing the flexibility to trade energy between minimum and maximum amounts. Bearing in mind the uncertain nature of the renewable resources, the prosumer must choose the contracts for the whole time horizon, to minimize the worst-case cost, while guaranteeing that each commitment will be honored. In a second level of decision, in each time period, following the list of engaged contracts and minimum/maximum commitment constraints, a real-time scheduler coordinates the microgrid's systems, making energy trading and transfer operations, according to current storage units' status and instantaneous information regarding local electricity production and demand.

Although microgrid energy dispatch has been well studied in the literature, existing methods do not investigate the subscription to multiple and flexible electricity contracts, or even commit to future energy usage, according to forward markets. The same holds for works focused on dynamic electricity pricing [START_REF] Mitter | Dynamic Pricing and Stabilization of Supply and Demand in Modern Power Grids[END_REF][START_REF] Joe-Wong | Optimized day-ahead pricing for smart grids with device-specific scheduling flexibility[END_REF]. The closest work is by [START_REF] Duan | Dynamic contract to regulate energy management in microgrids[END_REF], which, based on Stochastic Optimization, proposed a dynamic contract mechanism to smooth out fluctuations of microgrids' purchasing from the main grid with time-specific commitments. Their research, however, assumes a single dynamic contract for the whole time horizon, in which the microgrid buys electricity from the energy company.

Among the benefits of flexible contracts, it enables small customers to engage in a set of short-

Introduction to the problem

term contracts and spread energy purchasing decisions over a period of time. Besides avoiding the risk of relying on a single energy contract, the client also has the option to sell the contracted energy back to the grid and start over, which could be used to hedge against risk.

Flexible contract engagement may have drawbacks as well. Intelligent energy scheduling strategies are needed, a smart meter is essential to take accurate readings, and purchasing decisions are often more complex, with the client more exposed to risk, as market prices can go up or down.

Moreover, if the client needs to buy out of any engaged contract, the energy price will be higher than the existing contract prices. For these reasons, the choice of energy contracts should be robust enough to protect the consumer even in the worst-case scenario, given its operational constraints.

Traditional modeling approaches for handling uncertainty include Robust Optimization (RO) and Stochastic Optimization (SO). In this work, RO was chosen for two main reasons. First, probability distributions for energy production/consumption are generally unknown for recently-installed microgrid energy systems. Second, SO methods typically rely on scenario trees for modeling uncertainty, which makes them computationally expensive [START_REF] Narayan | Risk-averse stochastic programming approach for microgrid planning under uncertainty[END_REF]. When applying a RO approach, the obtained models have improved tractability with less computational effort.

In a conference work [START_REF] Levorato | Realtime command strategies for smart grids based on the Robust Contract-based Collaboration Problem[END_REF], we introduced the first robust microgrid energy management model based on an electricity contract subscription framework with flexible commitments. In that previous work, we assumed a conservative box-shaped uncertainty set and obtained preliminary computational results on a single realistic case-study instance. In the present work, we extend both model and real-time command strategies: a budgeted uncertainty robust counterpart, which controls the level of solution conservatism, is described [START_REF] Bertsimas | The Price of Robustness[END_REF] and used in a look-ahead strategy for the real-time energy scheduling. We also present extensive computational experiments on a set of multiyear and seasonal case-studies based on data from a Japanese research center microgrid recently described in the literature [START_REF] Vink | Multiyear microgrid data from a research building in Tsukuba, Japan[END_REF].

The main features of this work are summarized as follows. Section 2.2 introduces the Contract Collaboration Problem and the underlying framework. Once the problem has been formally defined, Section 2.3 presents the state of the art on microgrid energy trading and management literature, and related works on Robust Optimization. In the context of the forward electricity market for microgrids, we describe in Section 2.4.2 a mathematical model for multi-contract energy trading with flexible commitments. A robust version of this model is then presented in Section 2.5, minimizing the costs and protecting against the worst-case realization of local production and consumption of electricity under budgeted uncertainty. Then, in Section 2.6, we describe real-time command strategies for energy scheduling within the microgrid, considering the contracts previously selected by our model.

Finally, we present a case study, based on a real microgrid, detailing the results of these scheduling strategies, when coupled with the robust model solution (list of engaged contracts), in contrast with a deterministic approach to solving the problem. In a second level of decision, inside each time period, a Real-time Command Strategy (RTCS) is responsible for performing on-line energy scheduling (item 2 in Figure 2.1). As explained in Section 2.2.2, the RTCS follows a predefined strategy to balance energy demand and supply at each instant of time, considering renewable energy sources, storage devices, drivable systems and deciding how much energy will be traded via each engaged contract.

CONTRACTS

The Contract Collaboration Problem (CCP)

The contract collaboration is established between two entities, both producers and consumers of a same kind of energy resource. One entity is called the client (individuals, households or businesses) and the other one the partner (energy supplier). These two entities have to collaborate in order to balance their consumption and production over a given time horizon. We consider a set {T 0 , T 1 , . . . , T t} of time points dividing the given time horizon into a set I = {I 0 , . . . , I t-1 } of t time periods where

I t = [T t , T t+1 ), for each t ∈ {0, 1, 2, . . . , t -1}.
The collaboration between the entities is established by the use of a set C of contracts of consumption or production, both offered by the partner. Let C t ⊆ C be the subset of contracts offered by the partner at time period I t . Each contract c ∈ C t has its own functional constraints and its own gain/cost functions. The partner determines the set C t and sets a price to engage each contract c ∈ C t . On each time period I t ∈ I, the client is free to enter into a commitment with the partner through any subset of C t . However, these commitments have to be taken by the client at the beginning of the time horizon and must be honored. At any time period, the client also has the option to buy energy out of any engaged contract, but at a higher cost which can vary with the time period.

The client's microgrid is composed by a set of systems S that produce/consume energy, each one with its own functional constraints and a cost/gain of consuming/producing over the time periods. In particular, the consumption/production can be driven for a subset of these systems (drivable systems) while the consumption/production is already planned for the other ones (non-drivable systems). Drivable systems are devices that allow being turned on/off or that must be loaded/unloaded from time to time (e.g., batteries, electric car), whereas non-drivable systems must be permanently turned on. Additionally, some of the drivable systems can store the energy resource under a capacity constraint and provide it when it is needed, thus being called storage systems. The uncertainty considered in the problem lies in a subset of the non-drivable systems, for which only uncertain previsions of the consumption/production are known. The so-called uncertain non-drivable systems include, for example, renewable generation and variable energy consumption.

The Contract Collaboration Problem (CCP) consists in determining a cost-minimizing contract subscription from the client to the partner that satisfies all client-side consumer demands over the time horizon, and also guarantees that each commitment taken by the client with the partner is honored. For a detailed description of the CCP models, we refer the reader to Sections 2.4 and 2.5.

The Real-Time Command Strategy (RTCS)

In the first level of decision, the list of engaged contracts (i.e., the solution of the CCP problem) is set. The second level of the framework is in charge of defining a Real-Time Command Strategy (RTCS) that guarantees these contracts will be honored. The RTCS operates on smart control devices, being in charge of making scheduling decisions according to instantaneous energy supply and demand fluctuations observed on customers' premises. Thanks to the development of advanced metering and communication infrastructure, these control devices have the ability to regulate energy consumption by directly communicating to the energy supplier and to other devices in the microgrid so as to prevent system overloads. Interesting examples would be the load reduction of a set of electric vehicle charging stations and the automatic activation of a group of electric generators.

The RTCS consists of a heuristic strategy that schedules, in real-time, the set of actions to be taken in order to properly manage the client's microgrid. From a real-time point of view, inside each time period I t ∈ I, the instantaneous production/consumption of each microgrid system is measured every ∆ time units. It is also at this time scale that drivable systems are driven, i.e, every ∆ time units a scheduling decision has to be taken by the control device, embedded in the client's microgrid, considering its state. For example, according to energy load and in real time, a group of generators (a type of drivable system) may be switched on during a period of higher demand and, analogously, a set of storage systems such as batteries can store energy during off-peak times in order to ease high demand supply in peak periods.

Regarding the energy contracts, the RTCS is in charge of deciding how much energy will be bought or sold, given each engaged contract and its minimum and maximum commitments. For instance, given a time period, if the client engages contract c, energy quotas (for buying or selling electricity) are established for each time period and, analogously, for each time slot.

The main objective of the RTCS is to reduce power consumption costs and promote load balance, while dealing with the effects of uncertainty in both production and consumption of energy.

As we can expect, the RTCS operates subject to the CCP constraints, guaranteeing both contract commitments and energy balance at each moment. A full description of the real-time command strategies developed in this work is available in Section 2.6.

Literature review

In this section, we highlight existing works involving the two subjects addressed in the paper: microgrid energy scheduling (RTCS) and electricity trading models (such as the CCP). Also, we review works presenting robust approaches to related problems.

Microgrid energy scheduling and electricity trading models

Various approaches have been proposed to optimize microgrid operational schedules, with distinct objectives, constraints, and methods for handling uncertainty. As a consequence, different terms have been used to refer to similar real-time control mechanisms: microgrid energy scheduling [START_REF] Ottesen | Demand side operational flexibility -A holistic stochastic optimization model for flexible consumers and prosumers[END_REF][START_REF] Zhang | Robust energy management for microgrids with high-penetration renewables[END_REF][START_REF] Su | Stochastic energy scheduling in microgrids with intermittent renewable energy resources[END_REF][START_REF] Zachar | Microgrid/Macrogrid Energy Exchange: A Novel Market Structure and Stochastic Scheduling[END_REF], real-time scheduling [START_REF] Hu | Toward optimal energy management of microgrids via robust two-stage optimization[END_REF], real-time control system [START_REF] Wu | Stochastic control of smart home energy management with plug-in electric vehicle battery energy storage and photovoltaic array[END_REF][START_REF] Wu | Stochastic Optimal Energy Management of Smart Home With PEV Energy Storage[END_REF], real-time power management and control [START_REF] Colson | Comprehensive Real-Time Microgrid Power Management and Control With Distributed Agents[END_REF], energy management policies [START_REF] Nguyen | Stochastic Optimization of Renewable-Based Microgrid Operation Incorporating Battery Operating Cost[END_REF], energy dispatching poli-cies [START_REF] Wu | Coordinated energy dispatching in microgrid with wind power generation and plug-in electric vehicles[END_REF], microgrid energy management [START_REF] Zhang | Robust distributed energy management for microgrids with renewables[END_REF][START_REF] Van Ackooij | Optimizing power generation in the presence of micro-grids[END_REF] and microgrid operation [START_REF] Hussain | Optimal operation of tri-generation microgrids considering demand uncertainties[END_REF][START_REF] Luis | Operations of a microgrid with renewable energy integration and line switching[END_REF]. Some authors have also studied the islanded-mode operation of microgrids [START_REF] Hooshmand | Stochastic model predictive control method for microgrid management[END_REF][START_REF] Hussain | Robust optimization-based scheduling of multi-microgrids considering uncertainties[END_REF].

In this review, we will focus on grid-connected microgrids, since energy trading with the main grid is a main premise of our work. As far as grid-connected microgrids are concerned, many works have applied risk-averse optimization methods to energy scheduling, dealing with uncertainties in several model parameters: energy prices, solar power production, wind power generation, Plug-in Electric Vehicle (PEV) consumption and availability, and load demand. An extensive, but not exhaustive, list of papers on microgrid energy scheduling is presented in Table 2.1, including the approach used to deal with uncertain data (SO or RO), which microgrid elements are assumed to be uncertain and the type of contract with the main grid.

The common point of existing works is how the microgrid interacts with the external energy market: energy transactions are modeled through a single contract (often with the utility grid/retail market), via purchase and sale prices that may vary in time, sometimes including a minimum/maximum tradable energy amount. One exception is the work of [START_REF] Ottesen | Demand side operational flexibility -A holistic stochastic optimization model for flexible consumers and prosumers[END_REF], where the prosumer can have at most two active contracts: one with a retailer and one with the grid company. In other words, flexible contract frameworks are not investigated. Such type of contract allows buying/selling from/to the main grid not only at different prices (even in the same time period), but also from/to different energy companies at the same time.

Ref SO RO Uncertainty

Solution Method Contract [START_REF] Colson | Comprehensive Real-Time Microgrid Power Management and Control With Distributed Agents[END_REF] x PV, spot price Decentralized multi-agents Single (Spot market) [START_REF] Duan | Dynamic contract to regulate energy management in microgrids[END_REF] x REN, load demands Stochastic Dynamic Programming Single dynamic contract [START_REF] Ottesen | Demand side operational flexibility -A holistic stochastic optimization model for flexible consumers and prosumers[END_REF] x Energy loads, energy prices General stochastic MILP model 1 contract with Utility grid + 1 dynamic price contract [START_REF] Wu | Coordinated energy dispatching in microgrid with wind power generation and plug-in electric vehicles[END_REF] x Wind, PEV Scenario generation and reduction Single (Utility grid) [START_REF] Su | Stochastic energy scheduling in microgrids with intermittent renewable energy resources[END_REF] x Wind, PV Two-stage stochastic model (with scenarios) Single (Utility grid) [START_REF] Huang | Adaptive electricity scheduling in microgrids[END_REF] x REN, energy prices, energy consumption Constrained stochastic programming; Lyapunov optimization Single (Utility grid) [START_REF] Nguyen | Stochastic Optimization of Renewable-Based Microgrid Operation Incorporating Battery Operating Cost[END_REF] x REN, load demands

Stochastic dynamic programming

Single (Utility grid) [START_REF] Wu | Stochastic control of smart home energy management with plug-in electric vehicle battery energy storage and photovoltaic array[END_REF] x PEV, PV, home load demand

Stochastic Dynamic Programming

Single (Utility grid) [START_REF] Mohammadi | Optimally operating microgrids in the presence of electric vehicles and renewable energy resources[END_REF] x Wind, PEV, energy prices Multi-objective ILP and scenario analysis Single (Utility grid) [START_REF] Zachar | Microgrid/Macrogrid Energy Exchange: A Novel Market Structure and Stochastic Scheduling[END_REF] x Residual load Chance-constrained optimization Day-ahead commitments [START_REF] Van Ackooij | Optimizing power generation in the presence of micro-grids[END_REF] x PV, Wind Bilevel stochastic MIP Multiple contracts, but can only subscribe to one [START_REF] Wu | Stochastic Optimal Energy Management of Smart Home With PEV Energy Storage[END_REF] x PEV Stochastic Dynamic Programming Single (Utility grid) [START_REF] Zhang | Robust distributed energy management for microgrids with renewables[END_REF] x REN Dual decomposition and distributed subgradient Single (Spot market) [START_REF] Zhang | Robust energy management for microgrids with high-penetration renewables[END_REF] x REN Dual decomposition and distributed subgradient methods Single (Spot market) [START_REF] Wang | A robust optimization approach for energy generation scheduling in microgrids[END_REF] x Net demand, heat demand, and electricity price

Chance constraint approximation and RO (budget-constrained & distribution uncertainty)

Single (Utility grid) [START_REF] Hussain | Optimal operation of tri-generation microgrids considering demand uncertainties[END_REF] x CHP, electrical loads Budget-constrained min-max robust counterpart Single (Utility grid) [START_REF] Craparo | A robust optimization approach to hybrid microgrid operation using ensemble weather forecasts[END_REF] x Wind Scenario-robust MILP based on realistic weather forecast scenarios Single (Utility grid) [START_REF] Hu | Toward optimal energy management of microgrids via robust two-stage optimization[END_REF] x REN, load demand Day-ahead scheduling with twostage RO Single (Utility grid) [START_REF] Luis | Operations of a microgrid with renewable energy integration and line switching[END_REF] x PV Two-stage RO with budget constraints 1 firm contract and 1 non-firm contract The novelty in our work is the incorporation of a multi-contract subscription framework for microgrids, based on flexible commitments. Even though such contract model is not present in existing low-voltage energy markets, it can be applied as an extension to the forward market (via an aggregator or similar energy service provider), or in local microgrid markets, following market structures depicted in [START_REF] Olivella-Rosell | Optimization problem for meeting distribution system operator requests in local flexibility markets with distributed energy resources[END_REF][START_REF] Khorasany | Microgrids and Local Markets[END_REF].

To our knowledge, only two authors present research directions similar to ours. From the viewpoint of multiple energy contracts, in [START_REF] Van Ackooij | Optimizing power generation in the presence of micro-grids[END_REF] different Generation Companies can offer buy/sell contracts to the microgrid. However, although the microgrid can receive contract offers from different competing companies, it can select at most one contract for the whole time horizon. As far as contract flexibility is concerned, [START_REF] Zachar | Microgrid/Macrogrid Energy Exchange: A Novel Market Structure and Stochastic Scheduling[END_REF] explored the stochastic scheduling of microgrids where energy exchange must be made with day-ahead commitments. In the proposed market structure, the microgrid may be either rewarded for respecting existing commitments, or penalized for deviating too much from them. Despite this flexibility, their work assumes a single long-term contract with the utility company.

Related works on Robust Optimization

The retailer-supplier problem is a NP-hard supply chain problem in which decisions are normally taken in a finite horizon of time periods. The retailer must order some products from a supplier for each period, being sometimes allowed to change these orders according to customer's demand.

Ordering, holding and shortage costs are involved. Demand uncertainty is frequent in this scenario and should be taken into account. Flexible commitments [START_REF] Bassok | Design of Component-supply Contract with Commitment Revision Flexibility[END_REF] is a coordination mechanism that aims to assist both retailers and suppliers in handling the uncertainty in customer's demand in a cooperative way. In this model, the retailer-supplier relation is established by contracts through which the retailer may have some flexibility to purchase quantities that actually deviate from his original commitments. Some variants of this mechanism were proposed in the literature, including orders that can be changed along the time horizon, sometimes incurring in penalty costs. The retailersupplier problem with flexible commitments (RSFC problem) is a NP-hard problem.

[12] applied the Affinely Adjustable Robust Counterpart methodology (AARC) to the RSFC problem with uncertain demand, based on the box uncertainty set. First, the retailer places his commitments for each time period. Then, at the beginning of each time period, the retailer is allowed to order a quantity not necessarily respecting his commitment, but subject to certain lower and upper bounds. Cumulative bounds are also imposed, and the supplier specifies a penalty that must be paid due to any deviation between committed and actual orders. The cost function involved is minimized against the worst-case demand occurrence (min-max criterion). In the present work, the applied solution approach presented in Section 2.5 is similar to the one used by [START_REF] Ben-Tal | Retailer-Supplier Flexible Commitments Contracts: A Robust Optimization Approach[END_REF].

Besides the RO works listed in Table 2.1, which directly involve microgrids, we also refer the reader to additional RO works on related problems with uncertain demand and production of elec-

A deterministic version of the CCP

tricity. The first one involves the application of constraint generation and duality-based reformulation to solve the robust multistage Unit Commitment Problem, using both budgeted uncertainty and a customized dynamic uncertainty set [START_REF] Lorca | Multistage robust unit commitment with dynamic uncertainty sets and energy storage[END_REF]. The second work [START_REF] Correa-Florez | Comparative analysis of adjustable robust optimization alternatives for the participation of aggregated residential prosumers in electricity markets[END_REF] involves an aggregator of residential prosumers, which participates in the day-ahead energy market to minimize operation costs.

Budgeted uncertainty is considered in energy prices, demand and PV production, and Adjustable

Robust Optimization is employed. The model takes into account energy purchases in the wholesale market, with the possibility of buying additional blocks of energy. However, no flexible commitments were considered in this framework.

A deterministic version of the CCP

In this section, we will present a simpler, deterministic model version of the CCP, denoted as DCCP, where the value of the uncertain parameters are assumed to be known in advance. The formulation comprises each microgrid component, its operational constraints, as well as the underlying contract subscription framework. The main idea of the CCP model is to find a cost-minimizing solution which provides the client with a list of energy contracts to engage in each time period, considering the whole time horizon. In the rest of this text, time is discretized into periods as indicated by I 0 , .., I t-1 and energy units are assumed to be in kWh. Moreover, we will often write t for a time period I t . Given a set of contracts offered by the partner, each contract c ∈ C t is associated with a time period I t and its fixed (v t c ) and variable prices (α t c ) may vary if the period is in peak hours or offpeak. By engaging in a contract, the client must respect the established energy quotas Π - t,c and Π + t,c , that may be positive (if the client purchases energy from the partner) or negative (the client sells energy to the partner). The partner can also sell energy to the client out of any engaged contract at a specific unit price β t .

Nomenclature

Sets

The information about energy consumption (or production) P t s of all drivable and non-drivable systems is discretized into time periods I t . Moreover, in the microgrid's energy scheduling, each time period I t is further subdivided into δ t time slots of size ∆, where ∆ is an input parameter. At this time scale, the instantaneous production/consumption of each microgrid system is measured.

Each system s ∈ S D ∪S N D ∪B may have an associated operational cost v s (e.g. energy produced by a fuel generator has positive cost). This cost can also be zero (e.g. consumer system such as a building). Additionally, for each drivable system s ∈ S D , we define minimum requirements for energy production/consumption at time period I t . In other words, for each consumer drivable system s, P min t s > 0 means system s must be supplied with P min t s units of energy before the end of time period I t (e.g. when charging an electric car). Normally, P min t s = 0 if s is a producer drivable system. Last but not least, the storage systems are a key component for the success of the contract subscription framework. A set of batteries can store energy during off-peak time periods in order to ease high demand supply in peak periods. Besides the unit cost, there are several battery-specific parameters related to the storage levels, capacity and efficiency:

h t s ≤ r t s , ∀ t ∈ T, ∀ s ∈ B (2.4)
r 0 s = u 0 s , ∀ s ∈ B (2.5) u min s ≤ r t s ≤ u max s , ∀ t ∈ T ∪ { t}, ∀ s ∈ B (2.6) r t+1 s = r t s -h t s + λsg t s , ∀ t ∈ T, ∀ s ∈ B (2.7) g t s ≤ θ abs s δ t , ∀ t ∈ T, ∀ s ∈ B (2.8) h t s ≤ θ ref s δ t , ∀ t ∈ T, ∀ s ∈ B (2.9) Π - t,c y t c ≤ q t c ≤ Π + t,c y t c , ∀ t ∈ T, ∀ c ∈ Ct : Π + t,c > 0 (2.10) Π + t,c y t c ≤ q t c ≤ Π - t,c y t c , ∀ t ∈ T, ∀ c ∈ Ct : Π - t,c < 0 (2.11) c∈C t q t c + s∈S N D P t s + s∈S D x t s P t s + s∈B λsh t s + e t ≥ s∈B g t s , ∀ t ∈ T (2.12)
The objective function (2.1) includes, respectively: (i) the fixed costs involved in the client-partner engagement through a set of contracts; (ii) the sum of costs/gains of consuming/providing the amounts of electricity predicted by the set of engaged contracts; (iii) the costs of using drivable systems; (iv) the costs of using storage systems (including depreciation); (v) the costs of consuming extra amounts of electricity not predicted in the set of engaged contracts.

There are also costs associated with the use of non-drivable systems. However, since these costs are fixed, they do not need to be included in the objective function to be minimized.

Constraints (2.2)-(2.
3) ensure the minimum usage of drivable system s, in case it produces (2.2) or consumes (2.3) electricity. Constraints (2.4) restrict the amount of electricity consumed from storage system s during a time period to be at most the amount stored. Additionally, constraints

(2.5)-(2.6) state that the initial, minimum and maximum capacities of storage system s must be respected. Constraints (2.7) determine the amount of electricity stored on storage system s at the next time period. It must take into account its loss coefficient λ s , i.e., when storing g t s kWh of energy, only λ s % is effectively stored in s. Remark that h t s includes the amount of energy provided by s as well as the energy lost during this operation. The maximum quantity of energy that can be stored by storage system s during a time period t is guaranteed by constraints (2.8), while constraints (2.9) ensure the maximum quantity of energy that can be provided by a storage system s during a time period t. Constraints (2.10)-(2.11) establish minimum and maximum quotas for contracts. They also guar-antee that a non-zero consumption/production related with a contract available at a certain time period will imply an engagement to it. Finally, constraints (2.12) define the electricity balance at each time period. When calculating the energy refunded by storage systems s, these inequalities must take into account the amount of energy lost during discharge, therefore h t s must be reduced proportionally to λ s %. Besides, at any time period, total consumption may be greater than the energy available from the microgrid's production, storage systems and currently engaged contracts. In this case, the microgrid can buy additional energy e t from the partner in order to fulfill unforeseen demand. We also assume a dissipation system is available with no cost of use associated.

We denote by MIP(DCCP) the formulation defined by objective function ( [START_REF] Laurence | Integer and combinatorial optimization[END_REF], whose solution can be obtained with both commercial and opensource solvers, using well-known branch-and-bound algorithms. As seen in the experiments with case study instances, the solution to the deterministic CCP is returned by CPLEX solver in less than a second.

A robust formulation of the CCP

We consider in this section the robust version of the CCP, denoted as RCCP, in which the uncertainty of non-drivable systems will be treated via Robust Optimization methods. The developed model is capable of protecting against the worst-case realization of production and consumption of electricity, within a provided uncertainty set, considering all uncertain non-drivable systems, denoted as S N D ⊆ S. Once again, the model solution consists of a list of contracts to engage in each time period, for the whole time horizon.

Regarding the uncertainty in non-drivable devices' production/consumption, the only information required by the model are the lower and upper bound parameters, namely {P t s , P t s }, ∀t ∈ T, ∀s ∈ S N D , which can be determined via inference schemes based on historical data:

∀ t ∈ T , ∀ s ∈ SND: P t s
lower bound on energy consumption(<0)/production(>0) of s in the whole period t P t s upper bound on energy consumption(<0)/production(>0) of s in the whole period t Similarly to drivable and non-drivable devices, uncertain devices s ∈ S N D also have associated operational costs v s , per energy unit consumed/produced.

Definition of the uncertainty sets

In this work, we adopt a min-max criterion to assess the cost of feasible solutions to the problem. This means that we look for a solution that is feasible for each attribution of the uncertain parameters and that minimizes the cost function in the worst case scenario. The uncertain data are assumed to be varying in a given uncertainty set.

The formulation of the Robust Optimization model is connected with the definition of this uncertainty set and this definition depends on the suppositions made on the problem being solved. In our problem, the set U(t, s) describes how the uncertainty is defined. [START_REF] Bertsimas | The Price of Robustness[END_REF] and largely applied [START_REF] Agra | The robust vehicle routing problem with time windows[END_REF][START_REF] Lorca | Multistage robust unit commitment with dynamic uncertainty sets and energy storage[END_REF][START_REF] Correa-Florez | Comparative analysis of adjustable robust optimization alternatives for the participation of aggregated residential prosumers in electricity markets[END_REF]:

∀ t ∈ T , ∀ s ∈ SND: P t s ∈ U(t,
U Γ = { P ∈ U box : s∈ S N D t∈T | ∆ t s |≤ Γ}.
The purpose of the budget of uncertainty is to control the level of conservatism of the robust solution, in terms of deviations in the uncertain model parameters. It allows an intuitive interpretation for the decision maker, providing a trade-off between the nominal performance of the deterministic model and the risk protection of the most conservative model. Additionally, the obtained robust counterpart remains efficiently solvable, provided that the original nominal problem can be effectively solved.

In the context of the RCCP, with the objective of simplifying the model and the analysis of the obtained results, we opted for a single budget parameter Γ. It controls the total number of deviated parameters regarding both energy consumption ( P t s < 0) or production ( P t s > 0) of all uncertain devices s ∈ S N D , over all time periods t ∈ T .

Discussing the uncertainty definition

It is expectable to have the worst case scenario defined by the lowest possible production and/or by the highest possible consumption of systems in set S N D . From Example 2.5.1, we can see that the opposite can also happen, i.e., the worst case scenario defined by the uncertain parameters can The contract offered by the partner has costs v t c 1 , α t c 1 > 0, minimal and maximal consumption Π -

c 1 = Π + c 1 = ā.
The cost of buying energy not provided by contract c 1 is β 0 > (v t c 1 + āα t c 1 )/ā. The certain and uncertain systems s 1 and s 2 are, respectively, a consumption and a production system. System s 1 has a cost v s 1 = 0 and a consumption P 0

s 1 = -ā. System s 2 has a cost v s 2 > (v t c 1 + āα t c 1 )/ā and an uncertain production P 0 s 2 ∈ [0, ā]. Consider β 0 < v s 2 .
The optimal solution is y c 1 = 0. The worst case scenario is given by P 0 s 2 = ā with a cost equal to āv s 2 . If β 0 > v s 2 , the optimal solution is also y c 1 = 0, but the worst case scenario is given by P 0 s 2 = 0 with a cost of āβ 0 .

Situations like the one depicted in this small example (highest production/lowest consumption of non-drivable uncertain systems) can cause the client to engage contracts in order to sell the excess energy produced by the systems.

Robust counterpart

Similarly to the DCCP, we describe a formulation for the robust version of the problem based on time decomposition, in which decisions are made for every time period I t . The Min-Max Adjustable Robust Counterpart (ARC) formulation, used in this work, ensures feasibility of the constraints for any realization of the uncertainty, through the appropriate selection of the second stage decision variables. For more details on Adjustable RO for multi-stage optimization problems, we refer the interested reader to [START_REF] Bram | A practical guide to robust optimization[END_REF].

In the robust version of our problem, the RCCP, variables y (defined in Section 2.4.2) are nonadjustable ones, i.e, they consist of "here and now" decisions, or first-stage variables, before having any knowledge of the actual value taken by the uncertainty. The other variables, namely q, r, h, g, x and e, are adjustable ones, i.e, they consist of "wait and see" decisions (i.e., second-stage variables)

and define a set of decisions that depend on the uncertain parameters.

The Min-Max ARC, based on formulation MIP(DCCP) from Section 2.4.2, is as follows:

+ s∈B λsh t s ( Pt) + e t ( Pt) ≥ s∈B g t s ( Pt), ∀ P ∈ U , ∀ t ∈ T, (2.15) h t s ( Pt) ≤ r t s ( Pt-1), ∀ P ∈ U, ∀t ∈ T, ∀s ∈ B, (2.16) r 0 s = u 0 s , ∀ s ∈ B,
(2.17)

u min s ≤ r t s ( Pt-1) ≤ u max s , ∀ P ∈ U, ∀ t ∈ T ∪ { t}, ∀ s ∈ B, (2.18) r t+1 s ( Pt) = r t s ( Pt-1) -h t s ( Pt) + λsg t s ( Pt), ∀ P ∈ U , ∀ t ∈ T, ∀ s ∈ B, (2.19) g t s ( Pt) ≤ θ abs s δ t , ∀ P ∈ U, ∀ t ∈ T, ∀ s ∈ B, (2.20) h t s ( Pt) ≤ θ ref s δ t , ∀ P ∈ U, ∀ t ∈ T, ∀ s ∈ B, (2.21) Π - t,c y t c ≤ q t c ( Pt) ≤ Π + t,c y t c , ∀ P ∈ U , ∀ t ∈ T, ∀ c ∈ Ct : Π + t,c > 0, (2.22)
Π + t,c y t c ≤ q t c ( Pt) ≤ Π - t,c y t c , ∀ P ∈ U , ∀ t ∈ T, ∀ c ∈ Ct : Π - t,c < 0, (2.23
)

t ≤t P t s x t s ( Pt) ≥ P min t s , ∀ P ∈ U , ∀ t ∈ T, ∀ s ∈ SD : P t s > 0, (2.24
)

t ≤t P t s x t s ( Pt) ≤ P min t s , ∀ P ∈ U , ∀ t ∈ T, ∀ s ∈ SD : P t s < 0, (2.25)
y t c ∈ {0, 1}, ∀ t ∈ T, ∀ c ∈ Ct, (2.26)
r t s ( Pt-1), h t s ( Pt), g t s ( Pt) ≥ 0, ∀ P ∈ U , ∀ t ∈ T, ∀ s ∈ B, (2.27)
e t ( Pt) ≥ 0, ∀ P ∈ U , ∀ t ∈ T, (2.28) 0 ≤ x t s ( Pt) ≤ 1, ∀ P ∈ U, ∀ t ∈ T, ∀ s ∈ SD, (2.29)
where U is the uncertainty set chosen. For a given t ∈ T , variables q t , h t , g t , x t , and e t depend on the vector of uncertain parameters P t while variables r t depend on P t -1 .

In a previous work [START_REF] Levorato | Realtime command strategies for smart grids based on the Robust Contract-based Collaboration Problem[END_REF], a conservative U box uncertainty set was assumed and preliminary computational results were obtained. In the next subsection, we will explain how the dualization approach was employed to derive a robust counterpart for the U Γ uncertainty set. Notice that the cost associated with the use of uncertain non-drivable systems, given by s∈ S N D v s t∈T P t s , must be included in the robust model. Different from the cost of certain non-drivable systems, P t s values are not constant and vary with the uncertain parameters. Also notice that constraints (2.19) can be used to eliminate variables h t s , reducing the set of second-stage variables. An approach proposed in the literature to make model (ARC) tractable consists of restricting the functional relations q t c , r t s , g t s , x t s and e t to be affine by replacing them with linear decision rules (LDR) [START_REF] Ben-Tal | Adjustable robust solutions of uncertain linear programs[END_REF]. Also known as affine policies, LDRs have been commonly used in the literature as an effective approximation to multistage RO problems [START_REF] Rabih | Adjustable robust OPF with renewable energy sources[END_REF][START_REF] Warrington | Rolling unit commitment and dispatch with multi-stage recourse policies for heterogeneous devices[END_REF][START_REF] Lorca | Multistage robust unit commitment with dynamic uncertainty sets and energy storage[END_REF], with each recourse decision taking the form of an affine function of the uncertain parameters.

This way, we restrict recourse variables, say g t s ( P t ), to be affinely dependent on the primitive uncertainties, considering all uncertain devices ς ∈ S N D and all time periods prior to t. Of course, Part , Nomenclature only in very rare occasions, linear decision rules are optimal. Indeed, the main motivation for linear decision rules is its tractability. The following decision rules were applied for the set of adjustable variables in our problem:

r t s = r 0 ts + t-1 τ =0 ς∈ S N D r τ ς ts P τ ς , ∀t ∈ T \ {0} ∪ { t}, ∀ s ∈ B, (2.30) g t s = g 0 ts + t τ =0 ς∈ S N D g τ ς ts P τ ς , ∀t ∈ T, ∀ s ∈ B, (2.31) x t s = x 0 ts + t τ =0 ς∈ S N D x τ ς ts P τ ς , ∀t ∈ T, ∀ s ∈ S D , (2.32) q t c = q 0 tc + t τ =0 ς∈ S N D q τ ς tc P τ ς , ∀t ∈ T, ∀ c ∈ C t , ( 2.33
)

e t = e 0 t + t τ =0 ς∈ S N D e τ ς t P τ ς , ∀t ∈ T. (2.34)
As seen in the next subsection, after bringing the linear decision rules to the formulation, by taking U = U Γ , each constraint holding uncertain parameters is transformed by means of strong duality theory. As a result, we obtain a linear approximation to the model, called (ARC-L1). Each inequality will be characterized in terms of max/min values, and later replaced by its corresponding dual equivalent. In this process, a new set of continuous variables and a new set of constraints will be added to the formulation. This final product is a MILP model to the robust problem, which will be called MIP(RCCP), and whose solution can be obtained with commercial optimization solvers.

RCCP under budgeted uncertainty

Given the definition of the budget uncertainty set U Γ , we now present a dualization rule that can be applied to each constraint of the robust counterpart. Each ARC constraint can be written either in form (a)

f 0 + t∈T s∈ S N D P t s f t s ≤ 0, or (b) f 0 + t∈T s∈ S N D P t s f t s ≥ 0
, where f 0 is the independent term and f t s is the term that depends on the uncertain parameters P t s ∈ U Γ . In form (a), each problem constraint can be rewritten as:

f 0 + max P ∈U Γ t∈T s∈ S N D P t s f t s ≤ 0, (2.35)
with the second term being reformulated as:

max ∆ + t,s , ∆ - t,s s t f t s v t s + ∆ + t,s . v t s -∆ - t,s . v t s : (2.36) ∆ + t,s + ∆ - t,s 1, s ∈ S N D , t ∈ T, (µ t s ) (2.37) s t ∆ + t,s + ∆ - t,s Γ, (ρ) (2.38) ∆ + t,s 0, ∆ - t,s 0, s ∈ S N D , t ∈ T 0 (2.39)
Where variables ∆ + t,s and ∆ - t,s indicate that the uncertain parameter P t s has oscillated above (or below) its nominal value P t s . Constraints (2.37) limit the oscillation according to the maximum value allowed ( v t s ) and constraints (2.38) limit the budget of uncertainty to Γ. Analogously, for each problem constraint in form (b), we derive:

min ∆ + t,s , ∆ - t,s s t f t s v t s + ∆ + t,s . v t s -∆ - t,s . v t s : s.t. (2.37)-(2.39) 0. (2.

40)

The inclusion of the above robustified equations in the tractable MILP model is possible via dualization. In both cases above, dual variables µ t s and ρ can be derived, along with dual objective function: s t µ t s + ρ.Γ + s t f t s .v t s . In the first case (a), the dual constraints are:

µ t s + ρ | v t s .f t s | ≡      µ t s + ρ v t s .f t s (∆ + t,s ) (2.41) µ t s + ρ -v t s .f t s (∆ - t,s ) (2.42) µ t s 0, ρ 0 (2.43)
And, in the second case (b), the dual constraints are:

µ t s + ρ | v t s .f t s | ≡      µ t s + ρ v t s .f t s (∆ + t,s ) (2.44) µ t s + ρ -v t s .f t s (∆ - t,s ) (2.45) µ t s 0, ρ 0 (2.46)
In form (a), after dualization, each constraint is replaced by the following constraints in the tractable MILP model:

f 0 + s t µ t s + ρ.Γ + s t f t s .v t s 0 , and (2.41)-(2.43).
While, in form (b), each constraint is replaced by constraints:

f 0 + s t µ t s + ρ.Γ + s t f t s .v t s 0 , and (2.44)-(2.46).
The resulting tractable robust MILP model has

(5 + |T || S N D |)(2|C| + |T ||S D | + 3|T ||B| + |T |) constraints and |T | 2 | S N D |(2|B| + |C| + 1) + (6|T ||S D | + 8|C| + 14|T ||B| + |T ||C|) variables.

Real-time energy scheduling with the RTCS

The solution of the CCP (either the deterministic version in Section 2.4 or the robust version from Section 2.5) provides the client a decision for the first level in our framework: the contract subscription for the whole time horizon. However, for the success of the proposed contract framework, an efficient real-time energy scheduling mechanism is needed, so that distributed energy resources, storage devices and drivable loads within the microgrid are operated in a coordinated and coherent way, together with the energy exchange with the main grid.

Recall the RTCS definition given in Section 2.2. In order to perform energy scheduling, each time period I t is further subdivided into δ t time slots of size ∆. At this time scale, the instantaneous production/consumption of each microgrid system is measured. For certain (drivable and non-drivable)

systems, the consumption/production, for each time period I t , is known beforehand. And every ∆ time units a scheduling decision has to be made by the control device, according to the state of the microgrid.

In this sense, the RTCS consists of a scheduling heuristic that, based on the microgrid state and the energy contracts engaged by the client, solves an online optimization problem, selecting in real-time the set of actions to be taken, with the objective of reducing energy consumption costs and promoting load balance, while, at the same time, dealing with the effects of uncertainty. Remark that Part , Nomenclature the solution approaches commonly used to solve off-line scheduling problems are not appropriate for the on-line scheduling case.

Since the RTCS operates according the Contract Collaboration Framework, we remark that, once the heuristic starts, the set of subscribed energy contracts y 0 , for the whole time horizon, has already been established. Such decision is made by the client after running one of the previously presented CCP models. According to the microgrid energy balance, the following operations must be considered: (a) turn on/off a production/consumption drivable system; (b) buy/sell a quantity of energy under an engaged contract; (c) recharge/retrieve energy from a storage system; (d) buy energy out of engaged contracts; (e) throw energy away (if remaining energy cannot be sold back to the grid). Also, a subset of actions taken in a specific moment must obey the Contract Collaboration Problem constraints.

Naïve RTCS policy

This section describes the most straightforward approach to perform energy scheduling. The proposed naïve control strategy can be used as a baseline strategy to schedule the use of the Battery Energy Storage Systems (BESS) and the energy exchange via contracts. The naïve strategy relies on two assumptions. First, the microgrid should only sell energy via contracts as a last resort because the selling price is typically lower than the contract buying price. Besides, most of the time, the production obtained from renewables does not match the microgrid's energy demand. As a result, the microgrid will eventually buy energy from the power grid.

The proposed naïve RTCS policy works as follows. At each time step, the current demand for electricity is determined as the sum of the amount of energy required by the consumer drivable and non-drivable systems minus the amount of energy actually produced by the microgrid. In case the produced energy outweighs the demand, the resulting surplus is used to charge the battery. If the BESS is already full or the surplus exceeds the charging rate, the excess energy is sold via contracts.

On the contrary, if existing demand goes beyond the available produced energy, the difference is provided by discharging the battery. If the stored energy is not enough, then the remaining required energy is bought from the grid, first via available engaged contracts (provided they still have existing capacity), or bought out of any engaged contracts, possibly at a higher price.

Using model solution as a look-ahead policy to guide RTCS

The solution of the CCP models provide not only a list of contracts to engage, but also a set of values that can be used as a look-ahead (LA) policy to guide the RTCS energy dispatch operations, at each time period I t . The policy is defined by the optimal value of all model variables, except y variables.

When using the deterministic model, look-ahead values are obtained directly from the model solution, while for the robust models, the LDRs (2.30)-(2.34) are used to derive the look-ahead values for the current time period I t . In Section 2.7, we will show that the look-ahead policies based on the robust models can effectively enhance the performance of the RTCS. Among the advantages, the better utilization of storage devices and greater protection against uncertainty, when compared to the deterministic model.

We propose different heuristics for the RTCS, each one with a distinct behavior. As previously mentioned, the RTCS operates based on a predefined set of engaged contracts, obtained from a specific CCP model solution. Therefore, in the remainder of this section, we refer to X-RTCS as the general RTCS that can be executed based on an existing CCP model solution X.

Algorithm 1 depicts the X-RTCS executed inside a given time period I t , every ∆ time units or, analogously, at each time slot d ∈ {1, . . . , δ t }. At this time, the uncertainty concerning energy production/consumption has been revealed for all time periods before I t , and the microgrid configuration is given by its battery storage levels, drivable system requirements, load demand and renewable production. Let X(y 0 , t ) be the X model obtained by fixing y = y 0 and all variables and parameters related with t < t . The optimal solution of X(y 0 , t ) serves as a policy for all t ≥ t . Two different parameters, named REOPTIMIZE and GAP POLICY, define how the X(y 0 , t ) solution will be used as a policy in the X-RTCS heuristic.

The first one concerns the usage of model X. The REOPTIMIZE option determines which model X solution will be used as a forecast tool to determine the initial quantities regarding how much energy will be consumed or how much excess energy will be sent to the grid, via engaged contracts1 , and how long drivable systems should remain powered on. If REOPTIMIZE is enabled (line 1), model X will be reoptimized at each time period I t , for the remaining time periods t ≥ t (line 2), and the new solution obtained will guide the initial energy quantities (line 3). Otherwise, as listed on line 5, the RTCS policy will be based on the initial solution at the start of the time horizon (t = 1), i.e., the optimal solution of X(y 0 , 1).

The next step of the algorithm is the calculation of the current microgrid energy gap (i.e., total consumption minus total production) at the current time slot d (line 9), based on collected data regarding instantaneous energy production/consumption, minimum contract engagements, as well as model predictions regarding batteries and drivable systems (lines 6-8). We denote by q t ,d c the amount of energy that will be bought or sold via the contract c in time slot d; and x t ,d s as the percentage of time in which drivable system s will be on at time slot d. Also assume P t ,d s is an estimation of the uncertain production/consumption of device s at time slot d.

Finally, according to this information, X-RTCS must decide which additional dispatch operations will be executed to balance supply and demand, by applying a GAP POLICY (Table 2.2). These operations involve, for example, seling (line 15) or buying (line 24) additional energy to/from the Part , Nomenclature partner, turning on/off drivable systems (lines 16&23) and interacting with an energy storage system (lines 14&25).

Gap

Cheapest gap policy

Positive Cheapest storage operation (batteries/drivable/contracts) Negative Cheapest retrieval operation (batteries/drivable/contracts)

Gap

Conservative gap policy

Positive Store energy surplus in batteries, then use sell contracts Negative Buy from engaged contracts first, then use batteries Table 2.2 -X-RTCS policy executed at each time slot d (inside period I t ), according to the microgrid energy gap, defined as (Production) -(Consumption). A positve gap (+) means there is energy surplus in the current time slot, while a negative gap (-) represents lack of energy (more power needs to be bought from the partner or produced by the microgrid).

In summary, the combination of REOPTIMIZE and GAP POLICY parameters yield 4 different lookahead heuristics, whose behavior is determined by which CCP model predictions are used (from reoptimized model or not), along with a strategy to either fulfill demands greater than the microgrid's own production (negative gap) or use the available energy surplus (positive gap).

Remark that the algorithm considers the cost of purchasing additional blocks of energy (negative imbalance) and the revenue from selling surplus energy (positive imbalance) due to deviations concerning the forecast of energy contract usage, made in the beginning of X-RTCS. Additionally, the amount of electricity bought out of any contract e(•) presumes an indirect penalization on price, since they are less attractive than settled day-ahead prices.

Experimental results

This section sets up a realistic microgrid and conducts simulations with different sets of scenarios, comprising uncertain electricity production and consumption in a given time horizon. The main objective is to evaluate the impact of adopting a robust approach for engaging in flexible energy contracts. This is achieved through the performance assessment of the RTCS approaches proposed in the previous section, based on contract decisions taken by either the deterministic or the robust CCP model solution.

Computational environment and simulation details

The mathematical models and numerical simulations were coded in Julia 1.6.0 using CPLEX solver 20. The RTCS simulation is based on sets of realistic scenarios from the case study defined in this section.

Remember that, in order to obtain a deterministic solution for the CCP model, it is necessary to establish a fixed value for the uncertain parameters. In this study, we solved the deterministic model by using three sets of values for uncertain parameters P s of each system s ∈ S N D .

Microgrid in a research building in Tsukuba, Japan

This case study involves the microgrid of a research building in Tsukuba, Japan. A multiyear dataset [START_REF] Vink | Multiyear microgrid data from a research building in Tsukuba, Japan[END_REF] provides microgrid statistics in full details (every second) and summarized (per hour),

for the period between april 2015 and april 2018. Supplied data includes the Battery Energy Storage System (BESS) installed (active power, voltage, current, state of charge), the power generation from the four operating solar arrays, as well as purchased electricity (voltage, active power), solar irradiance, list of holidays and electricity prices (including surcharges).

Four problem instances were generated, one for each season of the year. Thus the lower and upper bounds for uncertain consumption and production were calculated as a function of the historical data for the corresponding season.

Problem instance generation

The considered planning horizon comprises 24 time periods of 1 hour, each one with δ t = 6.

Given all periods, a total of 457 contracts were proposed, inspired by Électricité de France price distribution [START_REF] Edf | EDF -Fiche descriptive de l'offre «Tarif Bleu[END_REF], allowing the client to buy electricity from the partner at different quantities and costs.

Concerning uncertain devices demand and production of electricity at each time period t, historical data of the microgrid is used to calculate the lower and upper bounds of these values. Moreover, instead of applying simple min/max approach, we use the 10th and 90th quantiles to determine the P min and P max values, which guarantees robustness against outliers. The determination of BESS kWh price is based on the cost model of [START_REF] Börjesson | Cost models for battery energy storage systems[END_REF].

RTCS simulation and scenario types

Based on the production and consumption history of the Tsukuba microgrid, the simulation objective is twofold: to evaluate how the solutions provided by the two CCP models proposed (robust and deterministic) behave under uncertainty, and to assess the performance of the RTCS policies defined in Section 2.6.2.

For each uncertain system, a particular scenario contains the realization of the uncertain electricity production (or consumption) values for each time slot over the whole time horizon. Given a list of engaged contracts (previously obtained with the solution of the CCP model), the simulation iterates over each time step, executing the chosen RTCS policy. As explained in the previous section, at this point, real-time energy scheduling actions are taken, according to the current state of the microgrid and the realization of energy production and consumption values. Among these values, the ones concerning the uncertain systems are obtained through the given scenario data in the current simulation.

For the Tsukuba microgrid, an individual set of scenarios was generated for each of the four seasonal instances, based on real values of PV production and building consumption provided in the dataset. The spring instance scenarios, for example, encompass all information recorded between March 20th until June 21st, given the dataset's 3-year time horizon.

In summary, for each microgrid instance, the simulation process consists in testing the RTCS policies based on each CCP model solution. The combination of 2 types of gap policy (Cheapest and Conservative), with or without model reoptimization, yields a total of 4 possible X-RTCS procedures for each model X, deterministic or robust. Simulation is then performed by executing each pair of model X and X-RTCS heuristic on the proposed microgrid instances and their associated scenario groups. For each of the 4 seasonal Tsukuba instances, simulation will be executed on a specific scenario set from each season. The study performed in this section analyses several cost and reliability metrics obtained from simulations of the proposed RTCS policies. By mimicking the real-time operation of the microgrid energy management system, each simulation was based on a specific solution provided by either the robust or the deterministic CCP model. A statistical analysis was also performed to assess the cost difference between each pair of simulations, considering every combination of CCP model and RTCS policy. For this purpose, we applied the Wilcoxon signed-rank test [START_REF] Wilcoxon | Individual Comparisons by Ranking Methods[END_REF], a non-parametric alternative to the paired Student's t-test, which does not depend on the assumption that the data is normally distributed. This test is based upon the ranks of the paired differences of measurements, and the null hypothesis H 0 is that two related paired samples come from the same distribution. If valid, H 0 indicates that there is no tendency for the outcome in one group of simulations to be higher or lower than in the other group. In a pair-wise comparison with a significance level α = 0.05, considering all pairs of RTCS simulations, in only 3 cases it is not possible to reject the null hypothesis. These cases are related with the autumn, spring and summer instances, with no significant statistical difference when comparing the scenario costs of the Conservative+ReOpt RTCS based either on the Det-RTCS solution with Φ = 50% or on the Rob-RTCS with Γ = 40%. All other simulation comparisons yielded P-values inferior to 0.05, which indicates there is enough evidence to reject the null hypothesis and conclude that the tested samples were likely drawn from populations with differing distributions.

Performance of the robust solution method

As a final remark, we refer the reader to the last two measures in Tables 2.4 and 2.5. According to the average and standard deviation of BESS State Of Charge, the robust-based policies rely more on the use of batteries to regulate the microgrid's system load than Det-RTCS.

Best options for CCP model and RTCS policy

The presented results confirm the overall superiority of the RTCS simulations derived from the robust CCP model results, according to the value of the budgeted uncertainty parameter Γ. Such value will depend on the scenario type and, therefore, the season of the year. For the microgrid under study, an intermediate value of Γ = 40% proved to be the best parameter option for the robust model during spring, summer and autumn, while the maximum hedge (Γ = 100%) fits best during winter season. It is worth noting that only the Rob-RTCS policies which incorporated the look-ahead mechanism obtained improved results when compared to the deterministic-based policies.

As a complementary evaluation, based on each season and the best performing robust CCP models presented above, we now investigate the differences among the proposed RTCS policies.

Once again, we turn ourselves to Tables 2.4 and 2.5, restricting our analysis to fixed values of Γ. For each combination of season and Γ value, we split the policies into three groups: naïve, look-ahead without model re-optimization (ReOpt) and look-ahead with re-optimization applied.

As far as the robust models are concerned, it is possible to observe that the naïve policy is not able to perform well according to cost and reliability metrics, and its simulation results are inferior to those obtained by the look-ahead policies. Regarding LA policies, both average and CVaR values of scenario cost improve in re-optimization-based policies, when compared to non-re-optimized ones.

As an example, considering the summer instance, re-optimized models provide an improvement of 3% in average scenario cost and 1% in CVaR. Out of Contract (OC) costs also decrease in most cases. One possible explanation for this behaviour is related to how the look-ahead policy works when the CCP model is re-optimized. At each time period, the LA mechanism updates the values regarding uncertain energy parameters and linear decision rules, based on a new run of the optimization model. Using these updated predictions inside the RTCS policy seems to be more cost-effective than not using them.

A second analysis, based on Pareto frontier, can also be used to determine the best-performing policy. In Figure 2.2, we plot the standard deviation of the daily cost (x-axis) versus the average of this cost (y-axis) for deterministic and robust model policies, where each point denotes a specific value of Φ or Γ, respectively. On each curve, the right most point corresponds to Φ = 0% in the deterministic-based policies or Γ = 0% in the robust-based ones. Note that every point of each curve can be strictly improved in both average and std of cost by changing to a different value of Γ, without the need to trade off between average and standard deviation (std) of the cost. In other words, each point is dominated by the points to its left. Therefore, the left-most part of each curve shows the Pareto frontier of cost average vs. cost standard deviation performance of the associated model policy. This evaluation framework can be applied to choose a suitable value of Φ or Γ, making sure the system operates on the Pareto frontier.

For the winter instance, this means that, to retain the same level of average cost, the robust budget model with conservative+ReOpt policy achieves the lowest std (i.e., the highest reliability);

or, conversely, to maintain the same level of std (i.e., reliability), this policy incurs the lowest average cost. That is, robust budget / conservative+ReOpt dominates every other policy.

Finally, in Figure 2. in the long run, by comparing the accumulated costs obtained after simulating the best set of deterministic and robust CCP models and policies for each season instance, over the whole time horizon (from January 2015 until May 2018). In this analysis, at the end of the simulation time horizon, the system running with the robust model decisions incurs in no out-of-contract costs as well as significantly cheaper accumulated total cost, 21% less when compared to the best deterministic model.

Discussion

This chapter presented the Contract Collaboration Problem (CCP), a multi-contract energy trading framework based on flexible commitments, coupled with a Real-Time Command Strategy (RTCS) for usage in microgrid energy trading and scheduling. As the main component, we developed a robust model under budgeted uncertainty which provides protection against the worst-case realization of the microgrid's production and consumption of electricity, by presenting a cost-effective contract commitment planning for a given time horizon.

A case study was conducted on a real microgrid, with a total of four problem instances, one for each season of the year. Monte-Carlo simulations were used to assess the performance of the proposed CCP robust model solution (against the deterministic alternative), when used as input for real-time energy scheduling strategies. Relying on a set of real-world-inspired energy purchase contracts, simulation results have confirmed the efficacy of different robust-based RTCS strategies, according to scenario types. For specific protection levels, the robust RTCS was able to dominate the deterministic RTCS in all operational cost and system reliability metrics.

Overall, the CCP robust model under budgeted uncertainty provides a pool of solutions with different protection levels so that decision-makers can pick according to their preferences. The effectiveness of each robust solution will depend on the microgrid's load profile and renewable production, which vary according to the season of the year.

Chapter 3

THE ROBUST PERMUTATION FLOW SHOP PROBLEM (MAKESPAN OBJECTIVE)

In permutation flow shop scheduling problems, the operations concerning each job are performed in a serial flow (i.e., in a specific production sequence) on each machine, and the processing order of the jobs is the same for each subsequent step. Such configuration is commonly used in assembly lines throughout several types of industry, including chemical [START_REF] Hugh | Simultaneous optimization of chemical flowshop sequencing and topology using genetic algorithms[END_REF], petrochemical [START_REF] De Deal | Job scheduling in petrochemical production: twostage processing with finite intermediate storage[END_REF],

automobile manufacturing [155], electronic [START_REF] Zh Jin | Scheduling hybrid flowshops in printed circuit board assembly lines[END_REF], food and metallurgical [START_REF] Nicholas | A survey of machine scheduling problems with blocking and no-wait in process[END_REF]. In all these applications, maintaining a continuous flow of processing tasks while minimizing idle time and waiting time is highly important, guaranteeing process efficiency and increasing production rates and profits.

The Permutation Flow Shop (PFS) scheduling has been widely investigated considering deterministic processing times, assuming input data are accurate and known in advance. However, in real-world industrial settings, manufacturing systems usually operate in uncertain environments where interruptions (essentially random in nature) restrict the execution of production schedules precisely as they were planned. In particular, variation in processing times and other stochastic events (e.g., machine breakdowns, due-date changes, order cancellations, and raw material shortages) bring increased variability in production systems and may influence the optimization model's quality and feasibility [119].

A typical solution approach applied to these cases is Stochastic Optimization [START_REF] Daniel | Stochastic models in operations research: stochastic optimization[END_REF], whose fundamental premise states that the unknown parameters can be described using probabilities. On the other hand, Robust Optimization (RO) [START_REF] Ben | Robust optimization-methodology and applications[END_REF] provides a different approach to optimization problems under uncertain conditions. The unknown parameters are modeled as belonging to an uncertainty set, making it a more suitable modeling approach when the uncertainty interval is known, but not necessarily the probability distribution. The goal for RO is to obtain a feasible decision, no matter what the constraints turn out to be, which is optimal for the worst-case objective function.

The objective of this chapter is to provide solution methods for the Robust Permutation Flow Shop to minimize the worst-case makespan. Assuming processing times are uncertain and vary in a given interval, the only information required is the lower and upper bounds of processing times, obtained from historical data. We are interested in a job permutation that minimizes the worstcase makespan for any possible realization of job processing times under the budgeted uncertainty set [START_REF] Bertsimas | The Price of Robustness[END_REF]. Unlike other robust optimization models, which generate only one conservative solution, the budgeted approach allows the adjustment of the level of conservatism of the solution, allowing the incorporation of different attitudes toward risk (e.g., risk-averse, risk-neutral, or risk-seeking).

As a result, the decision-maker can select the schedule that achieves the best balance between robustness and optimality.

Overview

The first problem to be analyzed is the 2-machine Robust Permutation Flow Shop (2RPFS) problem to minimize the worst-case makespan. The objective is to provide exact solutions to this variation

The Deterministic Permutation Flow Shop (PFS) Problem

This section presents the Permutation Flow Shop Problem (PFSP) to minimize the makespan.

Following the well-known α|β|γ notation for scheduling problems, established by [START_REF] Ronald L Graham | Optimization and approximation in deterministic sequencing and scheduling: a survey[END_REF], where α represents the machine environment, β stands for job characteristics, and γ symbolizes the objective function, this problem is denoted as F |prmu|C max . Since job processing time values are assumed to be known in advance, we will use the term deterministic when referring to this version of the problem.

Problem definition

The problem can be stated as follows. Consider a production planning process consisting of a set J = {J 1 , J 2 , . . . , J n } of n jobs to be executed in a set M = {M 1 , M 2 , . . . , M m } of m machines. In this process, every job J i is composed of m stages O 1,i , O 2,i , . . . , O m,i , named operations. Each job operation O r,i must only be executed on machine M r . Every operation O r,i has a non-negative processing time p r,i forming the matrix P ∈ R + M×J . At any time, each machine cannot execute more than one operation. Operation O r,i can only be executed after operation O r-1,i is finished. Preemption is not allowed: once an operation is started, it must be completed without any interruption. The permutation flow shop's particularity is that the sequence in which the jobs are processed (permutation) is the same for all machines. Such sequence is defined by a permutation σ: {1, . . . , n} -→ J, with σ(j) indicating the jth job to be executed. We call Σ the set of all permutations of n jobs, hence σ ∈ Σ. The completion time of an operation O r,σ(j) , denoted by C r,σ(j) , can be defined by the recurrence:

C r,σ(j) =          p r,σ(j)
if r = 1 and j = 1, C r,σ(j-1) + p r,σ(j)

if r = 1 and j > 1, C r-1,σ(j) + p r,σ(j)

if r > 1 and j = 1, max(C r,σ(j-1) , C r-1,σ(j) ) + p r,σ(j) if r > 1 and j > 1.

The completion time of a job J i is defined as its completion time on the last machine: C m,i . The makespan is the maximum completion time C max , considering all jobs, i.e., C max = max i∈{1,...n}

C m,i = C m,σ(n)
. The PFSP objective is to find a sequence of jobs (permutation σ) that minimizes the makespan.

As far as the makespan objective is concerned, the PFSP was proved strongly NP-hard by [START_REF] Michael R Garey | The complexity of flowshop and jobshop scheduling[END_REF] for instances with three or more machines. However, the two-machine version of the problem can be solved in O(n log n) time with the well-known algorithm proposed by [START_REF] Martin | Optimal two-and three-stage production schedules with setup times included[END_REF] in one of the pioneering papers in the scheduling literature. Indeed, for the two-machine case, the optimal makespan for the deterministic flow shop problem is the same with or without the permutation constraint (i.e., the sequence in which the jobs are processed is the same for all machines) [START_REF] Michael | Scheduling: theory, algorithms, and systems[END_REF].

Several solution approaches have been developed for the PFS problem with makespan minimization: Mixed Integer Linear Programming (MIP) models [START_REF] Tseng | New MILP models for the permutation flowshop problem[END_REF], approximation algorithms [START_REF] Nagarajan | Tight bounds for permutation flow shop scheduling[END_REF][START_REF] Poggi | A linear time approximation algorithm for permutation flow shop scheduling[END_REF], branch-and-bound [START_REF] Potts | An adaptive branching rule for the permutation flow-shop problem[END_REF][START_REF] Carlier | Two branch and bound algorithms for the permutation flow shop problem[END_REF][START_REF] Ladhari | A computational study of the permutation flow shop problem based on a tight lower bound[END_REF], Simulated Annealing [START_REF] Ishibuchi | Modified simulated annealing algorithms for the flow shop sequencing problem[END_REF], Tabu Search [START_REF] Al-Turki | Tabu search for a class of single-machine scheduling problems[END_REF] and Genetic Algorithms [START_REF] Yamada | Permutation flowshop scheduling by genetic local search[END_REF], to name a few.

To our knowledge, no proven optimal solutions for the problem are currently available for instances with more than 2000 operations (n = 200, m = 10). Therefore there is scope for new approaches that provide either exact or approximate improved solutions for larger instances.

Nomenclature used in the models

Mixed Integer Programming Formulations

Several Mixed-integer linear programming (MILP) models have been developed for the PFSP with an arbitrary number of machines. For a comparative analysis among the best performing PFSP formulations, we refer the reader to [START_REF] Tseng | An empirical analysis of integer programming formulations for the permutation flowshop[END_REF], which presents an empirical study based on a standard set of 60 problem instances. We now present four competing MILP models designed for the PFS Problem.

The Wagner model

Wagner [START_REF] Harvey | An integer linear-programming model for machine scheduling[END_REF] formulated an all-integer programming model for a three-machine flow shop, which was later extended to problems where m > 3 by Baker [START_REF] Kenneth | Introduction to sequencing and scheduling[END_REF] and Stafford [START_REF] Edward | On the development of a mixed-integer linear programming model for the flowshop sequencing problem[END_REF]. The all-integer model was converted to an MILP model by Stafford. The following is a corrected and simplified version of this model:

minimize C max = C mn (3.1) subject to j∈J Z ij = 1 ∀ i ∈ J (3.2) i∈J Z ij = 1 ∀ j ∈ J (3.3) i∈J p ri Z i,j+1 - i∈J p r+1,i Z ij + X r,j+1 -X r+1,j+1 + Y r,j+1 -Y rj = 0; (1 ≤ r ≤ m -1; 1 ≤ j ≤ n -1) (3.4) i∈J p ri Z i1 + X r1 -X r+1,1 + Y r1 = 0; (1 ≤ r ≤ m -1) (3.5
) until it has completed its processing on machine r; and (b) the job in sequence position j + 1 cannot begin its processing on machine r until the job in sequence position j has completed its processing on that same machine. Constraint (3.5) was not included in Wagner's work, but was later proved to be necessary by Stafford and Tseng [START_REF] Stafford | On 'redundant'constraints in Stafford's MILP model for the flowshop problem[END_REF]. Constraint (3.6) measures the makespan of the set of jobs.

C mn = i∈J p mi + p∈J X mp ( 3

The Wilson model

Alternatively, Wilson [START_REF] Jm Wilson | Alternative formulations of a flow-shop scheduling problem[END_REF] applied sets of inequality constraints to control the JAML relationships, similar to those used in the Manne models, described in the next section. His model is formulated as follows:

Part , Nomenclature used in the models minimize

C max = B mn + i∈J p mi Z in (3.7) subject to j∈J Z ij = 1 ∀ i ∈ J (3.8) i∈J Z ij = 1 ∀ j ∈ J (3.9) B 1j + i∈J p 1i Z ij = B 1,j+1 (1 ≤ j ≤ n -1) (3.10) B 11 = 0 (3.11) B r1 + i∈J p ri Z i1 = B r+1,1 ; (1 ≤ r ≤ m -1) (3.12) B rj + i∈J p ri Z ij ≤ B r+1,j ; (1 ≤ r ≤ m -1; 2 ≤ j ≤ n) (3.13) B rj + i∈J p ri Z ij ≤ B r,j+1 ; (2 ≤ r ≤ m; 1 ≤ j ≤ n -1) (3.14)
The assignment problem (previously described in Wagner's model) is represented by constraints (3.8) and (3.9). Constraints (3.10), (3.11), and (3.12) guarantee no idle time on machine 1, and that job 1 is processed by all m machines without delay. Constraints (3.13) assure that the start of each job on machine r + 1 is no earlier than its finish on machine r. Constraints (3.14) ensure that the job in position j + 1 in the sequence only starts on machine r after the job in position j in the sequence has completed its processing on that machine.

The Manne model

Following a different approach, Manne [START_REF] Manne | On the job-shop scheduling problem[END_REF] initially proposed a dichotomous-constraints integer programming model for the general job shop problem, which assures that only one of each pair of constraints can hold: job i either precedes job k somewhere in the processing sequence, or job k precedes job i. The original Manne model was later adapted to the PFS by Stafford and Tseng [START_REF] Stafford | On the Srikar-Ghosh MILP model for the N x M SDST flowshop problem[END_REF]:

minimize C max (3.15) subject to C 1i ≥ p 1i ; (i ∈ J) (3.16) C ri -C r-1,i ≥ p ri ; (2 ≤ r ≤ m; i ∈ J) (3.17) C ri -C rk + P D ik ≥ p ri ; (r ∈ M; 1 ≤ i < k ≤ n) (3.18) C rk -C ri + P (1 -D ik ) ≥ p rk ; (r ∈ M; 1 ≤ i < k ≤ n) (3.19) C max ≥ C mi ; (i ∈ J) (3.20)
Constraints (3.16) assure that the completion time of each job on machine 1 must be at least the duration of that job's processing time on the first machine. Constraints (3.17) ensure that each job's completion time on machine r is no earlier than that job's completion time on machine r -1 plus that job's processing time on machine r. With P defined as a very large constant, the paired disjunctive constraints (3.18) and (3.19) make sure that job k is either ahead of job i or comes after job i in the sequence, but not both. Constraint (3.20) defines the makespan as the maximum completion time of all jobs on the last machine.

The Liao-You model

In Liao and You [START_REF] Liao | An improved formulation for the job-shop scheduling problem[END_REF], an alternative Job Shop model was proposed. Each pair of inequality dichotomous constraints from the original Manne [START_REF] Manne | On the job-shop scheduling problem[END_REF] model was algebraically combined into a single equality constraint, which equals a surplus variable q rik . Such variable controls the precedence relationship of jobs i and k on machine r. The model also assumes P is a very large constant. Finally, in order to guarantee feasibility, the authors added a boundary constraint on the surplus variables.

Pan [START_REF] Chao-Hsien Pan | A study of integer programming formulations for scheduling problems[END_REF] later developed an adaptation of this model to the Permutation Flow Shop Problem, which is stated below.

minimize C max (3.21) subject to S ri + p ri ≤ S r+1,i ; (1 ≤ r ≤ m -1; i ∈ J) (3.22) S ri -S rk + P D ik -p rk = q rik ; (r ∈ M; 1 ≤ i < k ≤ n) (3.23) q rik ≤ P -p ri -p rk ; (r ∈ M; 1 ≤ i < k ≤ n) (3.24) C max ≥ S mi + p mi ; (i ∈ J) (3.

Literature review

This section provides an overview of the flow shop problem with uncertain processing times, concerning existing Stochastic Optimization methods (Section 3.3.1) and Robust Optimization approaches (Section 3.3.2). [START_REF] María González-Neira | Flow-shop scheduling problem under uncertainties: Review and trends[END_REF] surveyed 100 papers that study uncertainty in different variations of flow shop scheduling problems, published between 2001 and 2016. According to their analysis, the two most common uncertain parameters are processing times and machine breakdowns. The majority of works are related to Stochastic Optimization, including heuristics [START_REF] Dodin | Determining the optimal sequences and the distributional properties of their completion times in stochastic flow shops[END_REF][START_REF] Salah | The two-machine stochastic flowshop problem with arbitrary processing time distributions[END_REF][START_REF] Baker | Three heuristic procedures for the stochastic, twomachine flow shop problem[END_REF][START_REF] Framinan | On heuristic solutions for the stochastic flowshop scheduling problem[END_REF], simheuristics [START_REF] Ferone | Combining simulation with a GRASP metaheuristic for solving the permutation flow-shop problem with stochastic processing times[END_REF], probabilistic hybrid heuristics [START_REF] Laha | An efficient stochastic hybrid heuristic for flowshop scheduling[END_REF], branch-and-bound [START_REF] Balasubramanian | A novel branch and bound algorithm for scheduling flowshop plants with uncertain processing times[END_REF], and simulation [START_REF] Framinan | The value of real-time data in stochastic flowshop scheduling: A simulation study for makespan[END_REF].

Stochastic Optimization

It is worth noting that Stochastic Optimization approaches model random parameters using probability distributions, which may be difficult to infer in many cases. Additionally, optimizing the expected value of an objective may not be the best alternative for processes that incorporate only a small number of trials. The benefits of optimum expected value shall only be visible in the long haul, after a large number of tests.

The problem was also investigated from the viewpoint of fuzzy programming [START_REF] Hong | Fuzzy Gupta Scheduling for Flow Shops with More than two Machines[END_REF][START_REF] Mitkowski | Blocks for the flow shop scheduling problem with uncertain parameters[END_REF] and stability analysis [START_REF] Lai | Sequencing with uncertain numerical data for makespan minimisation[END_REF][START_REF] Braun | Stability of Johnson's schedule with respect to limited machine availability[END_REF].

Robust Optimization

When applying Robust Optimization techniques, no assumptions are necessary concerning the underlying probability distribution of uncertain data. Also, different approaches towards risk can be incorporated into the problem. As far as robust scheduling problems are concerned, the objective is to optimize a performance measure considering the worst possible scenario, thus developing a schedule that will perform relatively well under a wide range of possible realizations of processing times. Different optimization criteria may be used to choose a robust solution [START_REF] Aissi | Min-max and min-max regret versions of combinatorial optimization problems: A survey[END_REF]. The first and most straightforward criterion is the minimax (also known as the absolute robust criterion). In this case, given a minimization problem, the robust decision is made by choosing a solution that minimizes the highest cost over all possible scenarios.

A second possible criterion is minimax regret, aiming to find the least maximum regret over all possible scenarios. Regret can be either defined as the difference or the ratio between the resulting cost of the candidate decision and the cost of the decision that would have been taken if uncertain input data were known in advance (before the decision time, i.e., before solving the problem). In the first case, where regret is defined as a difference, the so-called robust deviation decision is obtained.

For the latter case (regret being the ratio of two values), the resulting decision is the relative robust decision.

Concerning the uncertain nature of the problem, scenarios represent the set of possible realizations of processing time values. When applying RO, there are two usual ways of describing the set of scenarios. In the discrete case, an explicit scenario list is given, i.e., one processing time matrix P λ for each scenario λ. In the interval case, for each operation O r,i concerning the execution of job i on machine r, a range [p L r,i , p U r,i ] of lower and upper bounds of processing times is defined. The so-called continuous processing time interval involves, therefore, an infinite number of scenarios. Regardless of the scenario representation approach, interval or discrete, once the robust counterpart formulations have been defined, developing an appropriate solution method remains a challenge.

Table 3.1 summarizes existing works regarding the makespan-objective Robust Permutation

Flow Shop Problem, in terms of optimization criterium (problem type), solution approach (heuristics or exact methods), the number of machines, and how processing time uncertainty was represented (discrete or interval).

Given the minimax regret makespan criterion, [START_REF] Kouvelis | Robust scheduling of a twomachine flow shop with uncertain processing times[END_REF] studied both the discrete and interval cases of processing time uncertainty. Their work proposed branch-and-bound and heuristic procedures to obtain robust solutions, along with experiments based on a considerable set of randomly generated instances, with no more than 15 jobs, however. They also provided NP-hardness proof for the discrete scenario case of the robust flow shop with m = 2. Very recently, the 2-machine interval processing time case has been proven to be NP-hard by [START_REF] Shafransky | On the complexity of constructing a minmax regret solution for the two-machine flow shop problem under the interval uncertainty[END_REF].

Problem Type

Heuristics / Approximation Exact methods Concerning the existing solution approaches involving only discrete-scenario uncertainty, [START_REF] Kasperski | Approximating a two-machine flow shop scheduling under discrete scenario uncertainty[END_REF] studied the two-machine permutation flow shop problem (F 2 | prmu | C max ) with uncertain data, whose deterministic counterpart is known to be polynomially solvable. The work proved that the minimax and minimax regret versions of the problem are strongly NP-hard even for two scenarios.

Minimax

The authors developed a polynomial-time approximation scheme (PTAS) algorithm to be used with the minimax version of the problem when the number of scenarios is constant. They also stated that the minimax regret version is not at all approximable, even for two scenarios.

Regarding the interval scenario case with the minimax makespan criterion, the computational complexity of the robust flow shop with m = 2 is still an unsolved open problem [START_REF] Kasperski | Approximating a two-machine flow shop scheduling under discrete scenario uncertainty[END_REF]. Note that the problem is NP-hard for m ≥ 3 following the complexity of the deterministic problem. Several solution strategies deal exclusively with processing time uncertainty represented as intervals of known bounds. [START_REF] Averbakh | The minmax regret permutation flow-shop problem with two jobs[END_REF] studied the minimax regret flow shop with m machines but only two jobs. [START_REF] Siepak | Scatter Search based algorithms for min-max regret task scheduling problems with interval uncertainty[END_REF] proposed a Scatter Search metaheuristic for the PFSP and other two scheduling problems with interval uncertainty, based on the minimax regret criterion.

Unlike previous works, [START_REF] Ching | Scheduling the two-machine flowshop to hedge against processing time uncertainty[END_REF] adopted a new approach, which searches for a minimax robust schedule given the restricted worst-case scenario, based on the [START_REF] Bertsimas | The Price of Robustness[END_REF] budgeted uncertainty set. Simulated annealing (SA) and Iterated Greedy (IG) metaheuristics were applied to solve the problem over a set of 300 randomly generated instances.

In the same year, [START_REF] Ćwik | Evolutionary Algorithm for Minmax Regret Flow-Shop Problem[END_REF] proposed an evolutionary algorithm for the minimax regret makespan robust flow shop with three machines, assuming processing times belonged to known intervals. Later, the same authors proposed another solution approach for an arbitrary number of machines [START_REF] Ćwik | Heuristic algorithms for the minmax regret flow-shop problem with interval processing times[END_REF],

where a constructive algorithm based on the Nawaz-Enscore-Ham (NEH) heuristic [START_REF] Muhammad Nawaz | A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem[END_REF] has been introduced and experimentally evaluated against two other heuristic algorithms: the authors' evolutionary algorithm and a Middle Interval heuristic.

The two-machine Robust Flow Shop Problem (2RPFS)

From this moment on, we will concentrate on the two-machine robust flow shop problem. Different optimization criteria may be used to choose a robust solution [START_REF] Gerodimos | Robust Discrete Optimization and Its Applications[END_REF][START_REF] Aissi | Min-max and min-max regret versions of combinatorial optimization problems: A survey[END_REF]. Our research focuses on the minimax criterion, also known as the absolute robust criterion. In this case, considering a minimization problem, the robust decision is made by choosing a solution that minimizes the highest solution value over all possible scenarios, according to a predefined uncertainty set. We refer the reader to Appendix A for a summary of the two types of optimization criteria that can be applied when solving the robust version of the problem.

Given that the computational complexity remains an open problem for 2RPFS under budgeted uncertainty, in this work, we fill a gap in the literature by providing an exact solution method (see Table 3.1 from Section 3.3). Furthermore, it is worth noting that the models and the solution method presented in this section can be generalized to the m-machine variant of the robust PFSP, which is NP-hard for m ≥ 3, following the complexity of the deterministic problem.

After defining the 2RPFS problem, this section describes the application of the budgeted uncertainty set. Finally, two robust counterpart formulations are proposed, based on well-known Mixed-Integer Linear Programming (MILP) formulations for the deterministic problem.

Problem statement

Assume the matrix of individual processing times P = {p r,i } as uncertain. A scenario λ is defined as a realization of uncertainty and, for each λ, there is a unique matrix of processing times P λ = {p λ r,i ∈ R : r = 1, 2, i = 1, 2, . . . , n}. We define Λ as the set indexing all possible scenarios. Let ϕ(σ, P λ ) be the makespan of a sequence σ ∈ Σ in scenario λ (i.e., given processing time matrix P λ ). The objective of the two-machine robust (minimax makespan) flow shop is to find a job permutation σ ∈ Σ that minimizes the maximum possible makespan over all possible scenarios λ ∈ Λ:

2RPFS: min

Budgeted uncertainty set for the 2RPFS problem

[159] compared the three classical Robust-Counterpart Optimization (RCO) models in terms of the number of variables, the number of required constraints, and if the respective formulation is linear or not. The first and simplest model, by [START_REF] Allen | Convex programming with set-inclusive constraints and applications to inexact linear programming[END_REF], consists of a linear formulation that presents the smallest number of variables and constraints. However, it is not possible to adjust its degree of solution conservatism. Following a new approach, [START_REF] Ben | Robust solutions of linear programming problems contaminated with uncertain data[END_REF] proposed an RCO model with safety parameters, which allow a trade-off between robustness and performance. However, the resulting formulation is non-linear (conic quadratic) and more challenging to solve than the original problem.

Finally, the model developed by [START_REF] Bertsimas | The Price of Robustness[END_REF] provided a linear formulation that allows controlling the level of conservatism of the robust solution without resulting in a substantial increase in problem size.

With the inclusion of a budget parameter for each constraint, it is possible to adjust the number of coefficients that simultaneously take their largest variations, thus providing a compromise between robustness and optimality. Therefore, the so-called budgeted uncertainty set, defined by this RCO model, comes as a natural choice to model processing time uncertainty in scheduling problems.

The budgeted uncertainty set for the 2RPFS problem was proposed by [START_REF] Ching | Scheduling the two-machine flowshop to hedge against processing time uncertainty[END_REF]. We reproduce their definition below, with some modifications in notation as well as additional comments.

As stated in Section 3.3, there are two common ways of representing scenario set Λ. Given the interval approach for representing uncertain values, consider two positive processing time matrices P={p r,i } and P={ p r,i }, that represent the nominal values of and the maximum allowed deviations of P, respectively. Additionally, we introduce two positive integers Γ 1 and Γ 2 , which will be called budget parameters, that denote the maximum number of operations whose uncertain processing times can reach their worst-case values in machines M 1 and M 2 , respectively. We can define the bounded (processing time) uncertainty sets of operations in M 1 and M 2 , denoted as U r (r = 1, 2), as follows:

U r = P r = {p r,i } : p r,i = p r,i + δ r,i p r,i , δ r,i ∈ {0, 1}, i ∈ {1, . . . , n}, n i=1 δ r,i ≤ Γ r , (3.28)
where P r is the projection of P in the space defined by machine M r (r = 1, 2).

Part , Nomenclature used in the models

We can now define the budgeted uncertainty set as:

U Γ = U (Γ 1 ,Γ 2 ) = U 1 × U 2 .
Notice that a scenario λ ∈ Λ is defined by the matrix P λ ∈ U Γ . Also, for a given r ∈ M and i ∈ J, let δ λ r,i be the value defining the deviation of the processing time regarding the execution of job i on machine r in scenario λ, i.e., p λ r,i = p r,i + δ λ r,i p λ r,i . Therefore, the total number of operations whose processing time can deviate to its maximum value in machine M r is limited to Γ r .

The main advantage of applying budgeted uncertainty sets is the ability to model the riskaverseness of the decision-maker by varying Γ 1 and Γ 2 . As mentioned by [START_REF] Bertsimas | The Price of Robustness[END_REF], the idea is that an event where all uncertain parameters p r,i reach their worst-case values at the same time has a very low probability of happening. In particular, higher values of Γ 1 and Γ 2 lead to larger uncertainty sets and thus more conservative solutions. When Γ 1 = Γ 2 = 0, the problem is equivalent to the nominal problem, i.e., the PFSP with two machines. If Γ 1 = Γ 2 = n, we obtain the box uncertainty set [START_REF] Allen | Convex programming with set-inclusive constraints and applications to inexact linear programming[END_REF]. For a given value of Γ 1 and Γ 2 , there are Γ 1 n × Γ 2 n possible worst-case scenarios, given the budgeted uncertainty set U Γ .

[159] affirmed that obtaining an exact solution for the two-machine Robust PFSP under budgeted uncertainty would be computationally intractable for real-sized problem instances. However, with the method introduced in this research, it turns out that it is possible to obtain exact solutions for most instances from that work in reasonable execution time (see results in Section 3.6).

Robust counterparts

We now present the robust counterparts for Wagner [START_REF] Harvey | An integer linear-programming model for machine scheduling[END_REF] and Wilson [START_REF] Jm Wilson | Alternative formulations of a flow-shop scheduling problem[END_REF] PFSP MILP models.

According to the empirical study conducted by [START_REF] Tseng | An empirical analysis of integer programming formulations for the permutation flowshop[END_REF], these two assignment-problem-based models are the best performing ones, based on results obtained on a standard set of 60 problem instances.

In both models, the number of constraints and the model matrix size are smaller than the other two competing integer programming models from the literature [START_REF] Stafford | On the Srikar-Ghosh MILP model for the N x M SDST flowshop problem[END_REF][START_REF] Liao | An improved formulation for the job-shop scheduling problem[END_REF]. Experimental data suggests that this factor greatly influences the computational time of the PFS models, apparently more than the number of binary variables. [START_REF] Harvey | An integer linear-programming model for machine scheduling[END_REF] proposed an all-integer programming model for a three-machine deterministic flow shop, later extended to an m-machine MILP model by [START_REF] Edward | On the development of a mixed-integer linear programming model for the flowshop sequencing problem[END_REF], and commonly named in the literature as wagner model. We now present its robust counterpart for two machines. In this two-stage RO formulation, y and Z i,j are the first-stage variables, while X λ j and Y λ j are in the second stage.

Robust Counterpart for Wagner PFS Model

Z i,j = 1, if σ(j) = i (job i occupies position j in the sequence σ) 0, otherwise. X λ j idle time on machine M 2 before the start of operation concerning the job in sequence position j given scenario λ. Y λ j idle time of the job in sequence position j after it finishes processing on machine M 1 given scenario λ. j has completed its processing on that same machine. Remark that the original Wagner model does not enforce an important aspect: all jobs are processed on machine M 1 without any in-sequence machine idleness, i.e., the idle time before any job is processed on machine M 1 is always zero. As a consequence, the idle time of the first job after processing on M 1 is zero (Y 1 = 0).Constraints (3.33)

min y (3.29) st n i=1 p 2,i + p 2,i δ λ 2,i + n j=1 X λ j ≤ y, λ ∈ Λ, (3.30) n i=1 p 1,i + p 1,i δ λ 1,i Z i,j+1 + Y λ j+1 = n i=1 p 2,i + p 2,i δ λ 2,i Z i,j + X λ j+1 + Y λ j , 1 ≤ j ≤ n -1, λ ∈ Λ, (3.31) n i=1 p 1,i + p 1,i δ λ 1,i Z i,1 = X λ 1 , λ ∈ Λ, (3.32) n i=1 Z i,j = 1, j = 1, . . . , n, (3.33) n j=1 Z i,j = 1, i = 1, . . . , n, (3.34) Z i,j ∈ {0, 1}, i, j = 1, . . . , n, (3.35) X λ j ≥ 0, Y λ 1 = 0, Y λ j ≥ 0, j = 1, . . . , n, λ ∈ Λ, ( 3
P 1,1 P 1,1 TT 1,1 TT 1,2 P 1,1 P 1,1 X 1 TT 2,1 X 2 X j TT 2, j X j + 1 TT 2, j -1 TT 2, j + 1 . . . . . TT 1, j TT 1, j -1 TT 1, j + 1 . . . . . Y j Y j + 1 Y j -1 1 2 Time makespan M Y 1 = 0 Y 2 TT 2,2

Robust Counterpart for Wilson PFS Model

Rather than using equality constraints and idle time variables for controlling the so-called JAML relationships, [START_REF] Jm Wilson | Alternative formulations of a flow-shop scheduling problem[END_REF] applied sets of inequality constraints based on start time variables defined for each job operation and each machine. This variant of the model uses the following decision variables:

Z i,j = 1, if σ(j) = i (job i occupies position j in the sequence σ) 0, otherwise.
B λ j = start time of operation concerning job σ(j) (in position j) on machine M 2 given scenario λ.

Based on the above definitions, where variables Z i,j and B λ j are in the first and second stage, respectively, the two-stage robust-counterpart of the Wilson model for 2RPFS can be formulated as follows:

min y (3.38) st B λ n + n i=1 p 2,i + p 2,i δ λ 2,i Z i,n ≤ y, λ ∈ Λ, (3.39
)

n i=1 j =1 p 1,i + p 1,i δ λ 1,i Z i, ≤ B λ j , j = 1, . . . , n, λ ∈ Λ, (3.40)
B λ j + n i=1 p 2,i + p 2,i δ λ 2,i Z i,j ≤ B λ j+1 , j = 1, . . . , n -1, λ ∈ Λ, (3.41) n i=1 Z i,j = 1, j = 1, . . . , n, (3.42) n j=1 Z i,j = 1, i = 1, . . . , n, (3.43)
Z i,j ∈ {0, 1}, i, j = 1, . . . , n, (3.44) Solving the two models above, for all possible combinations of λ ∈ Λ, is unrealistic. Therefore, in the next section, we will introduce an algorithm capable of obtaining optimal results for 2RPFS with only a subset of these combinations.

B λ j ≥ 0, j = 1, . . . , n, λ ∈ Λ, ( 3

Column-and-Constraint Generation applied to 2RPFS problem

This section presents an exact method for solving 2RPFS under budgeted uncertainty. Our approach is based on Column-and-Constraint Generation, a cutting plane procedure for two-stage RO problems which has been recently used to solve different robust scheduling problems [START_REF] Luis | Multi-process production scheduling with variable renewable integration and demand response[END_REF][START_REF] Silva | Solution algorithms for minimizing the total tardiness with budgeted processing time uncertainty[END_REF].

The method's name originated from how the decomposition operates: besides new constraints, each cutting plane is also associated with a set of new decision variables for the recourse problem [START_REF] Zeng | Solving two-stage robust optimization problems using a columnand-constraint generation method[END_REF].

Given one of the robust counterparts presented in Section 3.4, the main idea is to relax it into a master problem (MP) where each robust constraint is written only for a finite subset U of the uncertainty set U Γ . Then, given a feasible solution to the MP, the solution is checked for feasibility by solving an adversarial separation subproblem (SP). If the SP solution indicates that one or more robust constraints become infeasible, the uncertainty set U is expanded by one or more vectors, and the master problem is augmented, according to the column-and-constraint generation procedure.

For the 2RPFS problem, the adversarial separation problem is represented by the worst-case procedure, which, given the sequence σ returned by the MP solution, returns the highest possible makespan under the uncertainty set U Γ . Since the uncertainty set U Γ , defined in Section 3.4, is polyhedral, the number of possible extreme solutions that the procedure can fetch is finite, and the algorithm terminates [START_REF] Zeng | Solving two-stage robust optimization problems using a columnand-constraint generation method[END_REF].

C&CG algorithm

In order to explain the C&CG algorithm, we will consider the 2-stage RO formulations defined in Section 3.4.3. Given that uncertainty set U (Γ 1 ,Γ 2 ) is discrete and finite, obtaining a solution for one of these formulations is equivalent to solving a probably large-scale MILP, enumerating all variables and constraints for each scenario λ in the set Λ. This possibility, as we can expect, is unrealistic. [START_REF] Zeng | Solving two-stage robust optimization problems using a columnand-constraint generation method[END_REF] propose an alternative solution approach, generating only a subset of scenarios In order to deal with the scenarios defined by Θ, we assume that an oracle can obtain an optimal solution to the worst-case subproblem for a given value of the first-stage decision variables Z i,j . The subproblem SP is defined as:

Θ = {λ 1 , . . . , λ v } ⊆ Λ.
(SP) S(σ) = max λv∈U Γ ϕ(σ, P λv ) (3.47)
where job permutation σ is derived using (MP) optimal values of variables Z i,j . In our case, the optimal solution for (SP) can be obtained by the worst-case procedure defined in Section 3.5.2.

The C&CG method is presented in Algorithm 2, where LB denotes the lower bound, UB denotes the upper bound, v is the iteration counter, Θ is the set of worst-case scenarios generated by the method, and ∈ R + represents the tolerance of optimality.

Worst-case evaluation

We now discuss how to determine the worst-case realization under the budgeted uncertainty set U Γ , for a specific sequence of jobs σ = {σ(j), j = 1, . . . , n}. From equation (3.27), given a protection level Γ = (Γ 1 , Γ 2 ) and a schedule σ, we extend the definition of worst-case makespan or robust cost Z(σ, Γ) as follows:

Z(σ, Γ) := max λ∈U Γ {ϕ(σ, P λ )}. (3.48)
We assume that parameters Γ 1 and Γ 2 , from the budgeted uncertainty set, are non-negative integers. Based on this assumption, statement (3.48) reflects a problem with a convex function being maximized over a polytope defined by uncertainty set U Γ . Thus, in order to obtain the worst-case realization of uncertainty, only specific realizations of U Γ are needed, namely the extreme points of the polytope. For each machine M r and job J i , the set of extreme scenarios are characterized either by the values p r,i or p r,i + p r,i (see proof in Appendix C), i.e., any worst-case realization will use as much budget of uncertainty as possible. Therefore, for the optimal solution of (3.48), with worst-case

scenario λ * , n i=1 |p λ * r,i -p r,i | p r,i = Γ r , ∀r ∈ {1, 2}.
We developed a worst-case solution method based on dynamic programming. The complexity of this algorithm is O(n 2 ). Given 1 ≤ r ≤ 2, 1 ≤ k ≤ n, and 0 ≤ γ ≤ n, let us define a value function α(r, k, γ) as the optimal value of the restricted separation problem for machine M r and job positions {1, . . . , k}, when at most γ jobs are using their maximum processing time on machine M r .

The optimal value of the problem is then defined by Z(σ, Γ) = α(2, n, Γ 2 ).

The value-function is defined by the recursion:

α(1, k, γ) = max p 1,σ(k) + α(1, k -1, γ), p 1,σ(k) + p 1,σ(k) + α(1, k -1, γ -1) , f or 1 ≤ k ≤ n, 0 ≤ γ ≤ Γ 1 , (3.49) α(2, k, γ) = max p 2,σ(k) + max[α(2, k -1, γ), α(1, k, Γ 1 )] , p 2,σ(k) + p 2,σ(k) + max[α(2, k -1, γ -1), α(1, k, Γ 1 )] , f or 1 ≤ k ≤ n, 0 ≤ γ ≤ Γ 2 , (3.50)
and the following initialization values:

α(r, k, γ) = -∞ if γ < 0, α(r, k, γ) = 0 if k = 0 and γ ≥ 0, α(2, k, 0) = p 2,σ(k) + max[α(2, k -1, 0), α(1, k, Γ 1 )], f or 1 ≤ k ≤ n.
If r = 1, the first maximizer argument accounts for the case when there is no delay of execution regarding job σ(k) on the first machine, while the second expression handles the case where a delay occurs. Similarly, for r = 2, we take the maximum of two cases: with or without delay when executing job σ(k) on the second machine. However, the job start time has to be computed as the maximum between the previous job's σ(k -1) worst-case completion time on the same machine M 2 , and the worst-case completion time of the same job σ(k) on the previous machine M 1 , taking into account its budget of uncertainty Γ 1 .

2RPFS Experimental results

We conducted extensive experiments on randomly generated datasets to assess the performance of the proposed solution method and additional aspects, including solution robustness, the trade-off between robustness and optimality, and the impact of data uncertainty on the obtained schedules. The analyses employed in this section follow the same lines as recent works on RO under budget uncertainty [START_REF] Lu | Robust single machine scheduling for minimizing total flow time in the presence of uncertain processing times[END_REF][START_REF] Javad | Robust quadratic assignment problem with budgeted uncertain flows[END_REF][START_REF] Silva | Solution algorithms for minimizing the total tardiness with budgeted processing time uncertainty[END_REF]. Sub-section 3.6.1 presents the testbed and environment setup, while 3.6.2 examines the robust method performance regarding execution time and the number of optimal solutions. Finally, based on Monte-Carlo simulation, we close with a case study that analyses the expected behavior of robust, stochastic, and deterministic solutions, to verify a possible increase in the expected solution cost in the long run.

Test instances and computational environment

Our experiments were based on a set of random instances generated by [START_REF] Ching | Scheduling the two-machine flowshop to hedge against processing time uncertainty[END_REF]. In his work, six groups of instances were created, each one with a different number of jobs n = {10, 20, 50, 100, 150, 200}. The expected processing time p r,i (r = 1, 2; i = 1, . . . , n) is an integer drawn from the uniform distribution [START_REF] Balasubramanian | A novel branch and bound algorithm for scheduling flowshop plants with uncertain processing times[END_REF][START_REF] Ronald L Graham | Optimization and approximation in deterministic sequencing and scheduling: a survey[END_REF] and the largest processing time deviation was set as a ratio of the expected processing time (i.e., p r,i = αp r,i ), where α = {10%, 20%, 30%, 40%, 50%}. Ten instances were generated for each combination of n and α for a total of 300 test instances. All test instances are available at https://github.com/levorato/2RPFS_Cmax_Budget.

The C&CG algorithm was coded in Julia 1.4.0, and IBM CPLEX 12.9.0 (with default parameters) was used to solve 2RPFS MILP models. All experiments were performed on a workstation with an Intel Xeon ® CPU E5640 @2.67GHz with 32 GB RAM, under Ubuntu 18.04 LTS. Time limit was set to 2 hours to solve each instance and the convergence parameter for C&CG was set to 10 -8 .

With a particular interest in examining the impact of budget parameters on the performance of the proposed robust scheduling algorithms, when solving each instance, we tested the 2RPFS models by varying Γ 1 and Γ 2 according to five ratios (20%, 40%, 60%, 80%, and 100%) of the number of operations subject to processing time deviation on machines M 1 and M 2 , respectively.

Comparative performance of the algorithms

This section examines the performance and effectiveness of the C&CG algorithm when using either Wagner or Wilson 2RPFS models. The comparison is based on the computational efficiency in terms of CPU time and the percentage of instances solved to optimality (i.e., zero solution gap).

We present in Table 3.2 overall results, comparing the performance of the algorithms. Wagnermodel C&CG is the one that solves the majority of the instances to optimality with the best execution time. The % Best Performance measurement indicates that, from the total number of instances solved to optimality, the Wagner model solved 86% of these instances faster, using less CPU time, followed by Wilson, which solved 14%. Measurements % Solved 150 and % Solved 200 indicate that the Wilson-based algorithm could not obtain optimal solutions for most of the 150 and 200job instances within the time limit. The other presented measurements (%Solved, Avg % Gap, and Median time) also favor the Wagner model. In this analysis, we present medians to mitigate the effect of instances not solved within the time limit.

Table 3.3 presents, for every instance size, the average performance of the C&CG algorithm with each robust-counterpart model, including average run time values. When using average, the results of all instances (even outliers) are taken into account. Standard deviation is also included as a secondary measure. Additionally, the average number of iterations and the standard deviation are listed. These results evidence that, as instance size grows, the models become harder to solve (especially the Wilson model), as seen on the smaller percentage of instances solved to optimality and increased average execution time.

Case study on two representative instances

In this subsection, we assess the quality and level of robustness of scheduling solutions for two large problem instances, the first one with small uncertainty (α = 20%) and the second with high uncertainty (α = 50%). The following solution methods were used:

- -SimGRASP: stochastic PFSP simheuristic solution from [START_REF] Ferone | Combining simulation with a GRASP metaheuristic for solving the permutation flow-shop problem with stochastic processing times[END_REF]. SimGRASP is a modified GRASP metaheuristic that incorporates Monte Carlo Simulation to solve the PFSP with random processing times. The objective is to find a schedule that minimizes the expected makespan. Given its stochastic nature, we obtained 25 independent runs for each instance file (and respective α parameter). For result comparison, when calculating the robust cost of each (Γ 1 , Γ 2 ) combination, we stored, for each instance, the smallest and largest robust costs found within these 25 simheuristic executions. We call them SimGRASP-Min(25) and SimGRASP-Max(25).

We assessed the robustness of each solution method by calculating the robust cost at different protection levels (Γ 1 %, Γ 2 %), using the dynamic programming algorithm defined in Section 3.5.2. Figure 3.3 depicts the robust cost Z(σ) of each solution σ under different protection levels (Γ 1 %, Γ 2 %). For clarity of the graphs, the robust costs for some protection levels were omitted.

Observe that, as the protection level (Γ 1 %, Γ 2 %) increases, so does the robust cost, i.e., makespan of the worst-case scenario defined by the protection level. In other words, higher values of Γ 1 % and Γ 2 % are equivalent to a greater quantity of operations with deviated processing times, which directly impacts the makespan.

In the examples from Figure 3.3, the extreme cases occur whenever Γ 2 % = 100, yielding the highest robust costs.

From the viewpoint of the decision-maker who needs to hedge against worst-case costs, it would be preferable to obtain a solution method that performs well under different protection levels. With this in mind, in the two graphs presented, we identify which scheduling method (and respective solution) presents the best (smallest) robust cost, considering all (Γ 1 %, Γ 2 %) values. Regarding the first graph (small uncertainty instance), note that both 2RPFS(80,40) and 2RPFS(60,40) offer improved protection against worst-case scenarios, regardless of (Γ 1 %, Γ 2 %) values used for worst-case evaluation. We also highlight the disappointing worst-case performance of both the nominal solution Det(=) and the stochastic method. The vast distance between the robust costs of the stochastic method, i.e., SimGRASP-Min(25) and SimGRASP-Max(25), reveals a significant exposure to the realization of worst-case scenarios.

In its turn, the "large uncertainty range" instance (α = 50%) presents increased robust cost differences between distinct protection levels. For this instance, the variation of Γ 1 and Γ 2 , i.e., the number of operations whose processing times can deviate on each machine, has even more impact on the worst-case makespan. In In summary, the choice of a robust solution depends on the instance and the desired protection level. The examples above illustrate how 2RPFS can provide a pool of robust schedules, depending on the value of (Γ 1 , Γ 2 ). With these options, the decision-makers can choose one of the schedules based on their risk preferences. Also, remark that, if the stochastic method is chosen, depending on the solution returned by the algorithm, the worst-case performance may be weak, as can be seen on the robust costs achieved by SimGRASP-Max(25). Indeed, neither SimGRASP nor the deterministic models have the objective of minimizing the worst-case makespan. As a complementary analysis, we evaluate the expected behavior of obtained problem solutions.

The makespan distribution of the obtained robust schedules was simulated by subjecting the processing time matrix to random perturbations. In particular, in each Monte Carlo simulation run, the (actual) processing time p r,i , ∀r ∈ M, i ∈ J, was independently drawn from a predefined probability distribution, yielding a random processing time matrix P . For this purpose, we used lognormal, symmetric triangular, and uniform distributions in [p -p, p + p] to generate random processing times.

We generated 10, 000 processing time matrices P . Then, for each 2RPFS solution σ (Γ 1 ,Γ 2 ) , obtained with a specific protection level (Γ 1 , Γ 2 ), we processed the set of all corresponding makespan values

2RPFS Experimental results

ϕ(σ (Γ 1 ,Γ 2 ) , P ) obtained through simulation on P . The same was made for the solutions returned by Det(P=) and SimGRASP-Min(25).

We first focus on simulation results presented in Finally, Table 3.4 presents some statistics related to the simulation of processing times of the large uncertainty instance. Given 10, 000 processing time matrices P obtained after simulation runs, let ϕ(σ) be the random cost (makespan) of scheduling σ, which depends on the realization of P .

E(ϕ(σ))

and SD(ϕ(σ)) are empirical estimations of expectation and standard deviation of ϕ(σ), respectively. Also, ϕ 0.95 (σ) and ϕ 0.99 (σ) are the 0.95 and 0.99 quantiles of ϕ(σ), respectively, and Based on these observations, the hedge provided by the obtained robust solutions does not cause a significant increase in the expected solution cost when compared to stochastic and deterministic solutions.

ϕ max (σ)

Evaluating price of robustness and hedge value

Given a protection level Γ, besides robust cost Z, two other measures can be used to evaluate performance: price of robustness η and hedge value H.

η(Γ) = ϕ(σ * Γ , P ) -ϕ(σ * , P ), (3.51) H(Γ) = Z(σ * , Γ) -Z(σ * Γ , Γ), (3.52)
where ϕ(.) is the makespan function, σ * Γ is the optimal solution of 2RPFS(Γ 1 , Γ 2 ) and σ * is the optimal solution of Det(P=). Table 3.4 -Simulation summary for 2RPFS, Det(P=), and SimGRASP solution methods from lognormal, triangular, and uniform distributions of processing times. Minimum values for each column are highlighted.

The first measure, η(Γ), is defined as the price paid by the decision-maker for employing the robust sequence σ * Γ in place of the optimal nominal sequence σ * in the scenario of nominal processing times (when P = P , i.e., no processing time deviations). H(Γ) represents the value gained from adopting the robust sequence σ * Γ , instead of the optimal nominal sequence σ * in the occurrence of the worst-case scenario associated with protection level Γ = (Γ 1 , Γ 2 ). In other words, η(Γ) can be seen as the trade-off between robustness and optimality, and H(Γ) represents the regret of employing sequence σ * in the worst-case scenario.

Table 3.5 displays the relative price of robustness η(Γ)%

= ϕ(σ * Γ ,P )-ϕ(σ * ,P ) ϕ(σ * ,P )
and hedge value

H(Γ)% = Z(σ * ,Γ)-Z(σ * Γ ,Γ) Z(σ * Γ ,Γ)
for various protection levels, based on instance #8 with n = 150, with different degrees of processing time uncertainty α. Observe that, given a protection level Γ, as α grows, so does the regret H(Γ)% of employing the optimal nominal sequence in the occurrence of the worst-case scenario defined by Γ. The only exception is for extreme values of Γ 1 and Γ 2 , where H(Γ)% = 0. Regarding the relative price of robustness, for several protection levels Γ, the relative robustness price η(Γ)% is zero, i.e., in the absence of processing time deviations, most robust schedules present the same makespan as the optimal nominal solution. Among these schedules,

the
Γ₂=20 Γ₂=40 Γ₂=60 Γ₂=80 Γ₂=100 α = 10% η % H % α = 20% η % H % α = 30% η % H % α = 40% η % H % α = 50%
η % H % is the average relative cost difference between 2RPFS(Γ) and Det(P=), given all simulated scenarios λ.

Part , Nomenclature used in the models

Based on the simulation framework presented in Section 3.6.3, we close this section with a further analysis of the actual cost overhead of robust solutions in the long run. Two performance measures are calculated for each variability level α, as shown in Table 3.6. The obtained results show that, for different protection levels Γ, several solutions present two important characteristics:

(i) high proportion of cheapest solutions (ω(Γ) > 50%), and (ii) smaller expected costs, i.e., negative relative cost difference ∆Φ(Γ). Overall, 2RPFS provides a pool of robust schedules decision-makers can choose based on their risk preferences.

The m-machine Robust Permutation Flow Shop Problem (Rob-PFSP)

In this section, we extend the robust permutation flow shop problem, generalizing it to an arbitrary number of machines. We start by providing a formal definition for the makespan-objective m-machine Robust Flow Shop Problem (Section 3.7.1), followed by a description of the underlying budgeted uncertainty set (Section 3.7.2). Finally, two robust counterpart formulations are proposed (Section 3.7.3), based on well-known Mixed-Integer Linear Programming (MILP) formulations for the deterministic problem.

In the subsequent sections, we will develop and test two solution procedures for this problem: an exact C&CG method, used as baseline, followed by a GRASP metaheuristic. Both procedures make use of a dynamic programming algorithm which, given a scheduling σ and a protection level Γ, determines the worst-case scenario.

Problem statement

The following problem statement generalizes the 2RPFS definition from Section 3.4.1 to the mmachine case. Assume the matrix of individual processing times P = {p r,i , r ∈ M, i ∈ J} contains uncertain data. A scenario λ is defined as a realization of uncertainty and, for each λ, there is a unique matrix of processing times denoted as P λ = {p λ r,i , r ∈ M, i ∈ J}. Let Λ be the set of all possible scenarios λ. Whenever a matrix of processing times P λ is known, an instance of the deterministic PFSP is defined.

Let ϕ(σ, P λ ) be the makespan of a sequence σ ∈ Σ given a scenario λ ∈ Λ. The objective of the m-machine Robust PFS is to find a job permutation σ ∈ Σ that minimizes the maximum makespan over all scenarios λ ∈ Λ:

RPFS: min

The m-machine Robust Permutation Flow Shop Problem (Rob-PFSP)

is called the worst-case makespan or robust cost for σ. The maximizer in (3.54) is called a worst-case scenario for σ.

Generalizing the budget uncertainty set to the m-machine problem

Similarly to Section 3.4.2, consider the interval approach for representing uncertain values. Two positive processing time matrices P and P represent the nominal value and the maximum allowed deviation of P , respectively. To apply budgeted uncertainty to the m-machine problem, we introduce the budget parameter Γ : 0 ≤ Γ ≤ mn, which denotes the maximum number of operations whose uncertain processing times can reach their worst-case values. The budgeted uncertainty set of operations (processing time), denoted as U Γ , can be defined as follows:

U Γ = P = {p r,i } : p r,i = p r,i + δ r,i p r,i , δ r,i ∈ {0, 1}, ∀r ∈ M, ∀i ∈ J : m r=1 n i=1 δ r,i ≤ Γ , (3.55)
Given uncertainty set U Γ , a scenario λ is described by one of the infinite matrices in this set. For a given operation O r,i concerning the execution of job i on machine r, let δ λ r,i be the value defining the deviation of its processing time, i.e., p λ r,i = p r,i + δ λ r,i p λ r,i . Therefore, the total number of operations whose processing time can deviate to its maximum value is limited to Γ.

As mentioned before, the main advantage of applying budgeted uncertainty sets is the ability to model the risk-averseness of the decision maker by varying Γ. The idea is that an event where all uncertain parameters p r,i reach their worst-case values at the same time has a very low probability of happening [START_REF] Bertsimas | The Price of Robustness[END_REF]. In particular, higher values of Γ lead to larger uncertainty sets and thus more conservative solutions. When Γ = 0, the problem is equivalent to the nominal problem, i.e., the deterministic PFSP. If Γ = mn, we obtain the box uncertainty set [START_REF] Allen | Convex programming with set-inclusive constraints and applications to inexact linear programming[END_REF]. For a given value of Γ, there are mn Γ possible worst-case scenarios, given the budgeted uncertainty set U Γ .

Robust counterparts

Based on existing PFSP MILP models, we developed two robust counterparts for the m-machine PFSP, based on Wilson [START_REF] Jm Wilson | Alternative formulations of a flow-shop scheduling problem[END_REF] and Wagner [START_REF] Edward | On the development of a mixed-integer linear programming model for the flowshop sequencing problem[END_REF] formulations. Both models rely on assignment constraints in order to find the position occupied by each job in the schedule. Certain parts of the models described below are similar to the ones introduced in Section 3.4.3, but adapted to the m-machine case. For completeness, we have chosen to repeat the introductory explanation of both models. For more details on the rationale behind each deterministic PFSP model, including illustrative diagrams, we refer the reader to [START_REF] Tseng | An empirical analysis of integer programming formulations for the permutation flowshop[END_REF].

Robust Counterpart for Wilson PFS Model

[149] proposed a MILP model for the makespan-minimizing flow shop scheduling problem, by applying sets of inequality constraints, based on the start time variables, of each job on each machine.

In this work, we derived a two-stage robust counterpart of his model, with the following decision variables:

Zi,j = 1, if σ(j) = i (job i occupies position j in the sequence σ), 0, otherwise. B λ r,j = start time of job σ(j) (in position j) on machine Mr given scenario λ.

Based on the above definitions, variables Z i,j are in the first stage, and variables B λ r,j are in the second stage of this robust counterpart. The two-stage robust-counterpart of Wilson model for the RPFS can be formulated as follows: [START_REF] Harvey | An integer linear-programming model for machine scheduling[END_REF] proposed an all-integer programming model for a three-machine deterministic flow shop, later extended to a m-machine MILP model by [START_REF] Edward | On the development of a mixed-integer linear programming model for the flowshop sequencing problem[END_REF], and commonly named in the literature as Wagner model. In our research, we derived a two-stage robust counterpart of the Wagner model,

Min y (3.56) st B λ m,n + n i=1 p m,i + pm,iδ λ m,i Zi,n ≤ y, λ ∈ Λ, (3.57) B λ 1,1 = 0, λ ∈ Λ, (3.58) B λ 1,j + n i=1 p 1,i + p1,iδ λ 1,i Zi,j = B λ 1,j+1 , j = 1, . . . , n -1, λ ∈ Λ, (3.59) B λ r,1 + n i=1 p r,i + pr,iδ λ r,i Zi,1 = B λ r+1,1 , r = 1, . . . , m -1, λ ∈ Λ, (3.60)
B λ r,j + n i=1 p r,i + pr,iδ λ r,i Zi,j ≤ B λ r+1,j , r = 1, . . . , m -1, j = 2, . . . , n, λ ∈ Λ, (3.61)
B λ r,j + n i=1 p r,i + pr,iδ λ r,i Zi,j ≤ B λ r,j+1 , r = 2, . . . , m, j = 1, . . . , n -1, λ ∈ Λ, ( 3

Robust Counterpart for Wagner PFS Model

Solving Rob-PFSP with an exact C&CG method

with the following decision variables:

Zi,j = 1, if σ(j) = i (job i occupies position j in the sequence σ), 0, otherwise. X λ r,j = idle time on machine Mr before the start of job in sequence position j given scenario λ. Y λ r,j = idle time of job in sequence position j after it finishes processing on machine Mr given scenario λ.

Based on the above definitions, variables Z i,j are in the first stage, and variables X λ r,j and Y λ r,j are in the second stage of this robust counterpart. The Wagner model for the RPFS can be formulated as follows: Solving the aforementioned models for all possible combinations of λ ∈ Λ is unrealistic. Therefore, in the next subsection, we will present an algorithm capable of obtaining optimal results for the m-machine RPFS with a subset of these combinations.

Min y (3.68) st n i=1 p m,i + pm,iδ λ m,i + n p=1 X λ m,p ≤ y, λ ∈ Λ, (3.69) X λ 1,1 = 0, λ ∈ Λ, (3.70) n i=1 p r,i + pr,iδ λ r,i Zi,j+1 + X λ r,j+1 + Y λ r,j+1 = n i=1 p r+1,i + pr+1,iδ λ r+1,i Zi,j + X λ r+1,j+1 + Y λ r,j , r = 1, . . . , m -1, j = 1, . . . , n -1, λ ∈ Λ, (3.71) n i=1 p r,i + pr,iδ λ r,i Zi,1 + X λ r,1 + Y λ r,1 = X λ r+1,1 , r = 1, . . . , m -1, λ ∈ Λ, (3.72) n i=1 Zi,j = 1, j = 1, . . . , n, (3.73) n j=1 Zi,j = 1, i = 1, . . . , n, (3.74) Zi,j ∈ {0, 1}, i, j = 1, . . . , n, (3.75) X λ r,j ≥ 0, Y λ r,j ≥ 0, r = 1, . . . , m, j = 1, . . . , n, λ ∈ Λ, (3.76

Solving Rob-PFSP with an exact C&CG method

Given that the uncertainty set U Γ defined in Section 3.7.2 is discrete and finite, it is possible to obtain a solution to the RPFS problem by choosing an appropriate Robust Counterpart formulation and enumerating all variables and constraints for each scenario λ in the set Λ. This possibility, as we can expect, is unrealistic.

As an alternative approach, the C&CG framework [START_REF] Zeng | Solving two-stage robust optimization problems using a columnand-constraint generation method[END_REF] generates only a subset of scenarios

Θ = {λ 1 , . . . , λ v } ⊆ Λ.
For its application, the problem has to be formulated in a master-subproblem

Part , Nomenclature used in the models framework. Solutions are then obtained iteratively, with each iteration generating one or more scenarios λ v ∈ Θ, obtained by solving a worst-case subproblem (SP).

In this section, we apply the same C&CG algorithm presented in Section 3. Additionally, we define the worst-case scenario procedure, based on dynamic programming, for the solution of the subproblem (SP), under the budgeted uncertainty set U Γ , for a specific sequence of jobs σ = {σ(j), j = 1, . . . , n}. By extending the notation of Equation (3.54), given a sequence σ and a protection level Γ, its worst-case makespan or robust cost, Z(σ, Γ) is given by: Z(σ, Γ) := max

P λ ∈ U Γ {ϕ(σ, P λ )} (3.78)
For the sake of simplicity, we assume that budget parameter Γ is a non-negative integer. Based on this assumption, statement (3.78) reflects a problem with a convex function being maximized over a polytope defined by uncertainty set U Γ . Thus, in order to obtain the worst-case realization of uncertainty, only specific realizations of U Γ are needed, namely the extreme points of the polytope. For each machine r and job i, the set of extreme point scenarios is characterized either by the values p r,i or p r,i + pr,i . Any worst-case realization will use as much budget of uncertainty as possible. Therefore we can expect that, for the optimal solution of (3.78), with worst-case scenario

λ * , m r=1 n i=1 |p λ * r,i -p r,i | pr,i = Γ.
The following worst-case method is a generalization of the dynamic programming proposed in Section 3.5.2. The novelty of this new method involves the extension for an arbitrary number of machines m, and the use of a single budget parameter Γ, which limits the number of operations with deviated processing times. The complexity of the algorithm is O(mn 2 ). Given

1 ≤ r ≤ m, 1 ≤ k ≤ n,
and 0 ≤ γ ≤ n, let us define a value function α(r, k, γ) as the optimal value of the restricted separation problem for machine r and job positions {1, . . . , k}, when at most γ operations are using their maximum processing time. The optimal value of the problem is then defined by Z(σ) = α(m, n, Γ).

The value-function is defined by the recursion:

α(1, k, γ) = max p 1,σ(k) + α(1, k -1, γ), p 1,σ(k) + p 1,σ(k) + α(1, k -1, γ -1) , f or 1 ≤ k ≤ n, 0 ≤ γ ≤ Γ, α(r, k, γ) = max p r,σ(k) + max[α(r, k -1, γ), α(r -1, k, γ)] , p r,σ(k) + p r,σ(k) + max[α(r, k -1, γ -1), α(r -1, k, γ -1)] , f or 2 ≤ r ≤ m, 1 ≤ k ≤ n, 0 ≤ γ ≤ Γ,
and the following initialization values:

α(r, k, γ) = -∞ f or 1 ≤ r ≤ m, 0 ≤ k ≤ n, γ < 0, α(r, 0, γ) = 0 f or 1 ≤ r ≤ m, and 0 ≤ γ ≤ Γ, α(r, k, 0) = p r,σ(k) + max[α(r, k -1, 0), α(r -1, k, 0)], 1 ≤ r ≤ m, 1 ≤ k ≤ n.
If r = 1, the first maximizer argument accounts for the case when there is no delay of execution regarding job σ(k) on the first machine, while the second expression handles the case where a delay occurs. Similarly, for r ≥ 2, we take the maximum of two cases: with or without delay when executing job σ(k) on machine r. However, the job start time has to be computed as the maximum between the previous job's σ(k -1) worst-case completion time on the same machine M r , and the worst-case completion time of the same job σ(k) on the previous machine M r-1 , taking into account the current budget γ.

Solving Rob-PFSP with the GRASP metaheuristic

Due to the NP-hardness of the regular PFSP with three or more machines, only relatively small instances can be solved by exact methods. To solve larger problems, several approximate methods have been developed in the literature. For a comparison of the existing heuristics and metaheuristics for the makespan objective, we refer the reader to [START_REF] Fernandez-Viagas | A new vision of approximate methods for the permutation flowshop to minimise makespan: State-of-the-art and computational evaluation[END_REF]. Since the robust PFSP is at least as difficult as regular PFSP, heuristics are very much needed. In this section, to solve the RPFS Problem, we apply the GRASP metaheuristic [START_REF] Thomas | Greedy randomized adaptive search procedures[END_REF], which has been successfully applied in other scheduling problems [START_REF] Binato | A GRASP for job shop scheduling[END_REF][START_REF] Eliana | A GRASP meta-heuristic for the hybrid flowshop scheduling problem[END_REF]. The main idea is to reuse the worst-case calculation procedure, defined in Section 3.8, as the objective function of GRASP.

GRASP is a multi-start metaheuristic in which each iteration consists basically of two phases: construction and local search [START_REF] Thomas | Greedy randomized adaptive search procedures[END_REF]. The solutions generated by a GRASP construction procedure are not guaranteed to be locally optimal with respect to simple neighborhood definitions. Hence, it is almost always beneficial to apply a local search to attempt to improve each constructed solution.

Our RGRASP is described in Algorithm 5. Instead of limiting the number of iterations, the only adopted stopping criterion is the time limit. The first task in each iteration of RGRASP is the construction of an initial solution in a greedy randomized fashion. In this phase, a feasible solution is progressively constructed with the addition of solution elements, one at a time. Choosing the next element to be added is determined using a greedy function, which measures the impact of incorporating each element in the partial solution under construction. Besides this greedy evaluation, the constructive phase of GRASP also includes a probabilistic component. Each construction step randomly selects an element among the most promising candidates, although not necessarily the top one, thus allowing the generation of different initial solutions, at each iteration of GRASP. In other words, the best rated elements (still unassigned to the current solution) are stored in a Restricted Candidate List (RCL), from which the next element to be added to the solution is taken.

The ConstructiveP hase procedure is described in Algorithm 3. For partial solution evaluation, we have applied a robust cost (minimization) gain function, suitable for Robust Optimization problems. In order to formalize it, we need some additional notation. Let σ P = {j 1 , j 2 , . . . , j k } denote a partial job permutation (i.e., a sequence of jobs of size |σ P | < n). We define below a function g : σ P → R, which will measure the impact on the robust cost Z(σ P ) of inserting a new job j ∈ J\σ P in the partial permutation σ P .

g(σ P ) = min

j∈J\σ P Z(σ P ∪ {j}). (3.79)
This minimization function compares the cost of inserting each unassigned job j into the partial permutation σ P . Note that a job with a low gain function value will probably contribute less to the robust cost if we add it to the partial permutation σ P . In this phase, the ordered set L g is defined (line 3) as the set of jobs J\σ P ordered in increasing order of function g (Figure 3.4). At each iteration, in lines 4-7, we randomly choose a job j among the first α. | L g | vertices in this set and add it to the partial permutation. This process is repeated until a full permutation σ is obtained.

Notice that this technique tends to generate different solutions every time the multi-start procedure (i.e., iteration) is run, which helps the GRASP algorithm to avoid getting trapped into a local minimum. Additionally, the α parameter provides a compromise between search exploitation (intensification using more greediness) and search exploration (diversification using more randomness). j b ... j x j t j y j z j d ... j k j u j c g min g max greedy function value: Ƶ(σ P ) RCL Small values improve the average quality of the RCL list elements and encourage exploitation. When α = 0, the constructive phase becomes a deterministic greedy algorithm, while an alpha value of one makes the algorithm completely random.

In this work, after extensive experiments, in order to determine the value of the α parameter, we opted for the so-called dynamic approach. In other words, the α value is randomly chosen from a uniform distribution in the range [β 1 , β 2 ], at each construction of a new solution. The values β 1 and β 2 then become parameters for the GRASP procedure. There is no guarantee that the construction method returns a (locally) optimal solution with respect to some neighborhood. Therefore, the solution σ obtained in ConstructiveP hase can be improved by the local search procedure V ariableN eighborhoodDescent (Algorithm 4).

The Variable Neighborhood Search (VNS) method, proposed by Mladenović and Hansen [START_REF] Mladenović | Variable neighborhood search[END_REF], is a metaheuristic that explores distant neighborhoods of the current incumbent solution, and moves to a new solution if and only if an improvement is made. The main idea is to systematically explore differing neighborhood structures, with the goal of escaping from local minima. Within this work, we apply the Variable Neighborhood Descent (VND) search, a variant of VNS.

As illustrated in Figure 3.5, VND starts with the permutation provided by the construction phase and iteratively compares the incumbent value Z(σ) with the new value Z(σ) obtained in the r -neighborhood, denoted by N r (σ) and defined as the family of all permutations obtained by

σ σ* N 1 N 2 N r
... traversing the r-th neighborhood structure over σ. In this work, we employ a local search approach similar to the one used by [START_REF] Ruiz | A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem[END_REF], but with the inclusion of other structures, in addition to the insertion neighborhood, as seen on Table 3.7. If an improvement is obtained, r is returned to its initial value and the new incumbent updated (lines 7 and 8 in Algorithm 4). Otherwise, the next neighborhood is considered (line 10). The local search halts when no better partition is found in the most distant neighborhood of the current solution. Additionally, our implementation of the VND procedure includes a Random-VND (RNVD) parameter [START_REF] Silva | A simple and effective metaheuristic for the Minimum Latency Problem[END_REF], allowing to shuffle the order according to which the neighborhood structures from Table 3.7 will be traversed by VND.

Remark that, in all employed solution neighborhoods, each evaluated solution is further improved by shifting all modified jobs to the left ("shift-to-left movement"). Moreover, since these structures are huge (great number of permutations), they are not traversed completely. The search in neighborhood #1 stops whenever it finds an improvement of the current solution (first improvement rule). In the other neighborhoods, only a single (random) movement is evaluated at each invocation.

# Name and Description 1 Move

Remove each job from its current position and insert it in all remaining positions.

2 Random Swap Select two jobs at random and swap their positions in the permutation.

3 Random Move End (d = 2) After removing d random jobs from the permutation (destruction), reinsert each one in the last d positions (construction).

Table 3.7 -Solution neighborhoods employed in the VND procedure, ordered by complexity. The RVND parameter allows to shuffle the order according to which these neighborhood structures are applied. In all employed solution neighborhoods, each evaluated solution is further improved by shifting all modified jobs to the left ("shift-to-left movement").

Rob-PFSP experimental results

Similarly to [START_REF] Juan | Using iterated local search for solving the flow-shop problem: Parallelization, parametrization, and randomization issues[END_REF], as the termination criteria for the multi-start procedure, max-time seconds is defined by the product of the number of jobs, n, the number of machines, m, and a time factor t = 0.03, such that: max-time = n × m × 0.03. This leads to very short computation times, ranging from only a few seconds to a maximum of 5 minutes for the largest instances.

Rob-PFSP experimental results

We conducted extensive experiments to assess the performance of both the exact and heuristic solution methods when solving Rob-PFSP, including the quality of the obtained heuristic schedules.

Test instances

In the PFSP literature, there exists a classical set of very well-known benchmarks commonly used to test new algorithmic approaches. However, except for the 2-machine instances proposed by [START_REF] Ching | Scheduling the two-machine flowshop to hedge against processing time uncertainty[END_REF], there are no standard benchmarks for the m-machine Rob-PFSP.

With this in mind, in order to verify the effectiveness of the proposed algorithms, our experiments were based on Ying instances (i), along with three new instance sets (ii, iii, iv)

(i) Two-machine robust PFSP instances, originally proposed by [START_REF] Ching | Scheduling the two-machine flowshop to hedge against processing time uncertainty[END_REF]. In his work, six groups of instances were created, each one with a different number of jobs n ∈ {10, 20, 50, 100, 150, 200}.

The expected processing time p r,i (r = 1, 2; i = 1, . . . , n) is an integer drawn from the uniform distribution [START_REF] Balasubramanian | A novel branch and bound algorithm for scheduling flowshop plants with uncertain processing times[END_REF][START_REF] Ronald L Graham | Optimization and approximation in deterministic sequencing and scheduling: a survey[END_REF] and the largest processing time deviation was set as a ratio of the expected processing time (i.e., p r,i = αp r,i ), where α ∈ {10%, 20%, 30%, 40%, 50%}. Ten instances were generated for each combination of n and α, for a total of 300 test instances.

(ii) Robust PFSP instances with 3, 4, 5, 10 and 15 machines. Following the same instance generation algorithm of instance set (i) [START_REF] Ching | Scheduling the two-machine flowshop to hedge against processing time uncertainty[END_REF], we generated random instances with 10 jobs and 3, 4, 5, 10 and 15 machines, respectively. Ten instances were generated for each combination of m, n and α, for a total of 250 test instances.

(iii) Taillard-based instances 2 . In order to generalize the classical Taillard PFS instances [START_REF] Taillard | Benchmarks for basic scheduling problems[END_REF] to the robust PFS problem, we assumed the provided processing times as nominal values (p r,i ). Similarly to the instance generation algorithm of [START_REF] Ching | Scheduling the two-machine flowshop to hedge against processing time uncertainty[END_REF], the maximum processing time deviations were generated as a ratio of the expected processing time (i.e., p r,i = αp r,i ), where α = {10%, 20%, 30%, 40%, 50%}. Therefore, five robust instances were generated for each original Taillard PFSP instance, yielding a total of 500 test instances.

(iv) Robust PFSP instances with random processing time deviations. For each instance of the previous three sets with variability level α = 10%, we generated 4 new instances with distinct variability levels α r,i for each operation O r,i . First, we define a maximum variability level α max ∈ {30%, 50%, 100%, 200%}. Then, in each generated instance, the variability level α r,i of each operation O r,i is drawn from a uniform distribution in the interval [0, α max ). Therefore, the maximum processing time deviation of each operation equals p r,i = α r,i p r,i . The idea behind this new set is to generate instances whose operation processing time deviation follow a completely random behavior, when compared to the previous sets. This way, we will be able to assess the impacts of such behavior on the solution method.

Implementation details and algorithm parameters

The C&CG algorithm was coded in Julia 1.6.0, and the IBM ILOG CPLEX solver 12.9.0 was used to solve the Mixed-integer programs. The GRASP algorithm was coded in C++ 11. All experiments were conducted on a workstation with an Intel Xeon ® CPU E5640 @2.67GHz with 32 GB RAM, under Ubuntu 18.04 LTS.

In the Exact method, we used CPLEX (default parameters) to solve the MILP models with time limit of 7,200 s. Relative optimality gap tolerance was set to 10 -6 . On the other hand, in the GRASP procedure, the time limit for the solution of each instance varies according to its size. In order to determine the best set of GRASP parameters, for each instance, Rob-PFSP was solved for all Γ ∈ {10%, 20%, . . . , 100%}. Moreover, all values in Table 3.8 were tested.

Only a subset of problem instances were used for GRASP parameter calibration. For this purpose, we randomly chose 20% of the instances from each group. Parameter tuning was performed with the irace package [START_REF] López-Ibáñez | The irace package: Iterated racing for automatic algorithm configuration[END_REF]. For each value of budget Γ, we ran irace twice in the following way.

In a first run, irace generated the initial configurations by uniformly sampling the parameters space (Table 3.8). In the second run, the best configurations given at the end of the first run were used as the new set of initial configurations. The final parameter set used in the experiments was defined in the end of the second run, by choosing the best configuration returned by irace, among all budget values Γ ∈ {10%, 20%, . . . , 100%}. In this study, the number of algorithm executions per irace run was set to 10 4 , yielding a total parametrization budget of 10 5 GRASP executions, considering all Γ values. The final overall time consumed in the GRASP configuration was five days wallclock time, using 8 computing cores. Apart from the previous description, the remaining irace default settings were used.

Comparative performance of the Robust Counterpart models

When assessing the performance of the exact solution method, we solved each problem instance with different values of the budget of uncertainty parameter Γ. Therefore we obtained solutions for We first present overall results in Table 3.9, by comparing the performance of Wagner and Wilson RC models, for each instance size. When using average, the results of all instances (even outliers) are taken into account. Standard deviation is also included as a secondary measure. Additionally, the average number of iterations and its standard deviation are listed. As we could expect, these results show that, as instance size grows, the models become harder to solve, as seen on the smaller percentage of solved instances and increased average execution time.

Regarding the hardest instances of the test-bed, namely Ying 15 × 5 and Taillard 20 × 5, Wagnerbased C&CG is the method that solves the majority of instances within the time limit: 64.4% and 24.7%, respectively. It also presents the smallest average gap among instances not solved to optimality. Additionally, the % Best Performance measurement indicates that Wagner model tends to solve Taillard 20 × 5 instances faster than Wilson.

A further investigation, based on the α and α max parameters, is portrayed in Tables 3.10 and 3.11. In this context, we explore solution statistics regarding Ying 15 × 5 and Taillard 20 × 5 instances, respectively. It is possible to note the decrease of model performance as α and α max values increase. This can be observed in the % Solved, Avg. % gap and Avg. time rows, from columns α = 10% until α = 50%, and from columns α max = 30% until α max = 200%.

It is worth noting that, when solving the Taillard 20×5 instances, the hardest ones in this comparison, we perceive a drastic performance reduction of the C&CG algorithm. The percentage of solved instances drops to 25% when applying the best-performing Wagner model. Also, when analyzing the % gap of instances not solved to optimality, the average % gap is considerably higher (12%), as well as its standard deviation (19%). In these cases (75% of all tested instances), the C&CG algorithm was not able to obtain an optimal solution within the 2-hour time limit.

Having achieved the limits of the exact solution method, in the next subsection, we will analyse the performance and solution quality of the GRASP metaheuristic, using C&CG solutions as a baseline for comparison. Table 3.9 -Robust PFSP C&CG performance comparison, for each instance size n×m and RC model. % Best Performance is the percentage of instances where the model achieved shorter execution time (ties included); % Solved contains the percentage of instances solved within the time limit; Avg. % Gap and Std. dev. of % Gap are the mean and standard deviation of the percentage gap of solutions from instances not solved to optimality; Avg. iterations and Std. dev. of iterations are the mean and standard deviation of the number of iterations performed; Avg. MP(SP) time is the average time (in seconds) to solve the Master(Sub) Problem; Avg. time and Std. dev. of time are the mean and standard deviation in solution time (in seconds), respectively.

Comparative performance of GRASP and C&CG

Due to its stochastic nature, for each tested instance, 50 independent GRASP executions (replicas) were run. Each replica was run for a maximum time t max = 0.03×n×m seconds, where n is the number of jobs and m is the number of machines. For the smallest instances t max = 1 second, while for the largest ones, t max = 300 seconds. A summary of GRASP execution statistics is displayed in Table 3.12, in terms of run time and number of iterations performed. On average, the algorithm takes no more than three minutes to obtain a solution to the problem. Table 3.12 -GRASP solution statistics, grouped by instance type and instance size. Median time, Avg. time and Std. dev. of time are the median, mean and standard deviation of solution time (in seconds), respectively. Median iterations, Avg. iterations and Std. dev. of iterations are the median, mean and standard deviation of the number of GRASP iterations, respectively.

I
We now compare the solutions obtained by the GRASP and C&CG robust methods when solving the same set of instances. Each solution provides an upper bound for the optimal robust cost of the problem. Let U B CCG and U B GRASP be the upper bounds obtained by the C&CG and GRASP methods, respectively. Also, let LB CCG be the lower bound obtained by the C&CG method. Whenever LB CCG = U B CCG or LB CCG = U B GRASP , we have an optimal solution to the problem. To assess the quality of the heuristic solutions obtained with GRASP, we compare their solution value, denoted as U B GRASP , with both bounds provided by the C&CG method. We define gap LB % and gap U B % as:

gap LB % = U B GRASP -LB CCG LB CCG × 100, (3.80
)

gap U B % = U B GRASP -U B CCG U B CCG × 100. (3.81)
For each instance group, Table 3.13 shows the percentage of instances which were solved optimally by the GRASP metaheuristic (i.e., gap LB % = 0, considering the best solution found after 50 independent executions) and by the C&CG exact method within 7,200 seconds. The determination of optimal solutions is based on the upper bound of each solution method, relative to the lower bound obtained by the C&CG method. GRASP was able to optimally solve all instances, except for 200 × 2 and 15 × 5 and 20 × 5 groups. Even so, regarding the 15 × 5 and 20 × 5 groups, GRASP solved far more instances to optimality than C&CG, reaching 97% and 68%, respectively.

Additionally, we deepen the analysis of the percentage of instances optimally solved, grouping by alpha and Γ% values, on Tables 3.14 and 3.15, respectively. Our evaluation is restricted to the three instance groups for which GRASP did not obtain 100% optimal solutions. By observing Table 3.14, it is possible to note the decrease of GRASP performance as α and α max values increase. Also, as the Γ% parameter values grows (Table 3.15), so does the difficulty of obtaining optimal solutions, as the number of optimally solved instances decreases. Considers all C&CG solutions, optimal or not. All GRASP solution values were obtained from 50 independent executions of GRASP.

Discussion

This section discusses the results obtained in this chapter, divided into two parts. In the first part, we proposed the first exact solution method for the two-machine robust flow shop problem based on budgeted uncertainty [START_REF] Bertsimas | The Price of Robustness[END_REF]. As a main contribution, we developed a worst-case determination procedure for the problem using polynomial-time dynamic programming. Together with new robustcounterpart formulations, we employed Column-and-Constraint (C&CG) Generation techniques. Extensive experimental results demonstrated that the proposed algorithm effectively obtained optimal robust schedules for small and medium-sized problems (e.g., instances with m = 2 and n ≤ 100).

However, it requires more computational power and thus CPU time for larger instances (m = 2, n ≥ 150) and as processing time variability level α increases.

Based on a case study with two representative instances, we have also assessed the trade-off between solution quality and cost, comparing robust solutions to deterministic and stochastic ones.

The adoption of the budget of uncertainty avoids the over-conservativeness of conventional robust scheduling approaches and, at the same time, provides a pool of robust schedules, many of which perform well under different levels of realization of uncertainty. Also, according to simulations based on three probability distributions, such robust schedules presented only a small overhead in the expected solution cost.

In the second part of the chapter, we extended our research to the m-machine robust permutation flow shop problem to minimize the worst-case makespan. Two solution methods were proposed:

an exact algorithm based on C&CG and a greedy randomized adaptive search procedure (GRASP) metaheuristic.

For the sake of performance evaluation, we proposed four sets of benchmark test instances for the robust problem, including instances based on the classical permutation flow shop literature. Af-Part , Nomenclature used in the models ter evaluating both C&CG and GRASP algorithms on this test-bed, GRASP was shown to produce optimal solutions on most small and medium-sized instances (e.g., instances with n × m ≤ 100) and associated budget parameters. In fact, it reached a higher proportion of instances solved to optimality than the exact C&CG method itself. Additionally, considering instances not solved to optimality, 75% of the observed GRASP optimality gaps are smaller than 10%.

In a nutshell, the GRASP method was able to process larger problem instances, as high as the Taillard-based 100 × 50 instances. Extensive experimental results also demonstrated that, compared to the baseline C&CG exact method, the GRASP algorithm was very efficient in obtaining robust schedules, both in solution time and quality (i.e., gaps in solution values).

repairs, corrosion removal, replacing damaged paint, and servicing pipes and water re-injection pumps. Moreover, since maintenance tasks have to be executed on every oil well connected to the platform, they must be closed simultaneously. Oil wells will only reopen for production at the end of the process, as soon as their associated maintenance operations finish.

The aforementioned process can be characterized as a permutation flow shop scheduling [START_REF] Michael | Scheduling: theory, algorithms, and systems[END_REF] in which oil-wells are represented by jobs, and maintenance tasks by machines. Each oil well is closed at the start of the schedule, while its associated equipment undergoes a series of maintenance tasks that always follow the same order. The aim is to find a schedule that minimizes the loss of oil production associated with each oil well's flow rate and for how long it remained closed, i.e., the total weighted completion time (TWCT) objective. Such optimization generates substantial financial gains, as more oil will be produced, in the order of thousands of dollars.

The TWCT criterium is usually associated with production environments where inventory levels and manufacturing cycle times are of critical concern. With a particular interest in minimizing inventory or holding costs, some production environments aim to minimize the total completion time, assuming all jobs are equal in importance. In specific contexts, however, the importance or value of each job may not be the same. For example, jobs may have different unit costs and holding costs.

Such costs could be characterized as job weights. As is the case for the oil industry, the cost criterion of each job will depend not only on its completion time but also on its weight, which represents the flow rate of each oil well.

Considering real-world characteristics, solving this scheduling problem is a challenging task and demands efficient solution approaches [START_REF] Johnny | A new heuristic for the n-job, M-machine flow-shop problem[END_REF][START_REF] Rajendran | An efficient heuristic for scheduling in a flowshop to minimize total weighted flowtime of jobs[END_REF]. Furthermore, job processing times are subject to uncertainty, and no probability distribution is known. A viable alternative, adopted here, consists in applying Robust Optimization to obtain a schedule hedging against worst-case scenarios.

Assuming processing times are uncertain and vary in a given interval, the objective of the present chapter is to provide efficient solutions for the m-machine Robust Permutation Flow Shop with the total weighted completion time objective (RPFS-TWCT). The only information required is the lower and upper bounds of processing times, which can be obtained from historical data. We are interested in a job permutation that minimizes the worst-case cost, for any possible realization of job processing times under the budgeted uncertainty set [START_REF] Bertsimas | The Price of Robustness[END_REF]. Unlike other robust optimization models, which provide only one conservative solution, the budgeted approach allows the adjustment of the solution's level of conservatism according to the decision-maker's risk-aversion.

Concerning uncertain processing times, scheduling problems that minimize the total weighted completion time have been studied from various viewpoints, for example, single-machine scheduling heuristics [START_REF] Allahverdi | Single machine scheduling problem with interval processing times to minimize mean weighted completion time[END_REF], branch-and-bound [START_REF] Pereira | The robust (minmax regret) single machine scheduling with interval processing times and total weighted completion time objective[END_REF], m-machine heuristics [START_REF] Kaminsky | Probabilistic Analysis and Practical Algorithms for the Flow Shop Weighted Completion Time Problem[END_REF], as well as stability analysis methods [START_REF] Yuri | the Stability Box in Interval Data for Minimizing the Sum of Weighted Completion Times[END_REF][START_REF] Tsung | The optimality box in uncertain data for minimising the sum of the weighted job completion times[END_REF]. To the best of our knowledge, this is the first work to treat the m-machine robust permutation flow shop problem under budgeted uncertainty, which minimizes the worst-case weighted sum of job completion times. The solution method is partly based on the column-and-

The deterministic PFSP minimizing total weighted completion time

This section presents the Permutation Flow Shop Problem (PFSP) to minimize the Total Weighted Completion Time (TWCT), also known as total weighted flow time [START_REF] Michael | Scheduling: theory, algorithms, and systems[END_REF]. For the sake of simplicity, we will refer to this problem as PFSP-TWCT. Following the well-known α|β|γ 1 notation for scheduling problems, established by [START_REF] Ronald L Graham | Optimization and approximation in deterministic sequencing and scheduling: a survey[END_REF], this problem is denoted as F |prmu| w j C j . Since job processing time values are assumed to be known in advance, we will use the term deterministic when referring to this version of the problem. Also, for completeness, we decided to restate the same basic notation and descriptions used in Section 3.2.1, with objective of redefining ϕ as the TWCT objective function.

The problem can be stated as follows. Consider a production planning process consisting of a set of jobs J = [n] to be executed in a set of machines M = [m] 2 . Each job i ∈ J has an associated weight w i and a non-negative processing time p r,i on machine r ∈ M, forming the matrix P ∈ R + M×J . Each job must be processed without preemption on each machine in the same order. At any time, a machine cannot handle more than one job. Also, at any time, a job can only be processed on one machine. We assume intermediate storage between successive machines is unlimited. The permutation flow shop's particularity is that the sequence in which the jobs are to be processed is the same for all machines. Such sequence is defined by a permutation σ : {1, . . . , n} -→ J, with σ(j) indicating the jth job to be executed. We call Σ the set of all permutations of n jobs, hence σ ∈ Σ. Consider an operation O r,σ(j) , concerning the execution of the jth job on machine r. Its completion is called the worst-case total weighted completion time or robust cost for σ. A maximizer in (4.2) is called a worst-case scenario for σ.

As mentioned in the introduction, to the best of our knowledge, this is the first research that applies the budgeted uncertainty set on the m-machine robust permutation flow shop problem. Existing works are related to either single or two-machine variants of the problem. In [START_REF] Bougeret | Robust scheduling with budgeted uncertainty[END_REF], the complexity of the single-machine version of the RPFS-TWCT problem was shown to be weakly NP-hard if Γ = 1 and strongly NP-hard for Γ > 1. [START_REF] Ching | Scheduling the two-machine flowshop to hedge against processing time uncertainty[END_REF] developed two metaheuristic algorithms to solve the twomachine problem, but with the makespan objective.

Budgeted uncertainty set for the RPFS-TWCT problem

In [START_REF] Ching | Scheduling the two-machine flowshop to hedge against processing time uncertainty[END_REF], the three classical Robust-Counterpart Optimization (RCO) models [START_REF] Allen | Convex programming with set-inclusive constraints and applications to inexact linear programming[END_REF][START_REF] Ben | Robust solutions of linear programming problems contaminated with uncertain data[END_REF][START_REF] Bertsimas | The Price of Robustness[END_REF] are compared in terms of the number of variables, the number of required constraints, and if the respective formulation is linear or not. When compared to the other RCO models [START_REF] Allen | Convex programming with set-inclusive constraints and applications to inexact linear programming[END_REF][START_REF] Ben | Robust solutions of linear programming problems contaminated with uncertain data[END_REF], the so-called budgeted uncertainty model [START_REF] Bertsimas | The Price of Robustness[END_REF] fits best for robust scheduling problems, by providing a linear formulation that allows adjusting the level of conservatism of the robust solution, without resulting in a substantial increase in problem size. The inclusion of a budget parameter provides a compromise between robustness and optimality. It is possible to adjust the number of coefficients that simultaneously take their largest variations, based on information about the application. For the case of oil-well maintenance, the problem which will be analyzed in the case study section, it is known that the probability of all maintenance tasks simultaneously deviating to their worst-case execution times is low.

Next, the budget uncertainty set for the RPFS-TWCT problem is defined. Bearing in mind that the definition below is equivalent to the one presented in Section 3.7.2, we decided to replicate it here for the sake of completeness. Consider two positive processing time matrices P={p r,i , r ∈ M, i ∈ J} and P={ p r,i , r ∈ M, i ∈ J}, that represent the nominal value of and the maximum allowed deviation of P, respectively. In order to apply budgeted uncertainty, we introduce the budget parameter 0 ≤ Γ ≤ mn, which denotes the maximum number of operations whose uncertain processing times can reach their worst-case values. The budgeted uncertainty set of operation processing times, denoted as U Γ , can be defined as follows:

U Γ = P = {p r,i } | p r,i = p r,i + δ r,i p r,i , δ r,i ∈ {0, 1}, ∀r ∈ M, ∀i ∈ J; m r=1 n i=1 δ r,i ≤ Γ , (4.3)
Given the uncertainty set U Γ , each scenario λ is described by one of the infinite matrices in for the RPFS-TWCT can be formulated as follows:

F λ i ≥ B λ m,j + p m,i + pm,iδ λ m,i Zi,j -Q(1 -Zi,j), i = 1, ...,
F λ i ≥ 0, i = 1, . . . , n, λ ∈ Λ, (4.16
)

y ≥ 0. ( 4.17)
The objective function (4.4) and constraint (4.5) state that this formulation aims to find a robust schedule for the processing of n jobs that minimizes the weighted sum of completion times of the worst-case scenario, among all possible scenarios λ ∈ Λ. Constraints (4.6)-(4.10) guarantee that the robust schedule is feasible and that start time variables are appropriately calculated, for each scenario λ. Constraints (4.11) are used to determine the completion time of job i on the last machine m, for each scenario λ. In these constraints, assume Q is a large-enough number. The same assumption is made in all other formulations, using a big-M value Q. Constraints (4.12) and (4.13) are the classical assignment constraints, ensuring, respectively, that each job is assigned to one and only one sequence position, and that each sequence position is filled by one and only one job.

Finally, constraints (4.14)-(4.17) define the domain of the variables.

Robust Counterpart for TBA PFS Model

Relying on the assignment constraints of Wilson model, Turner and Booth [START_REF] Turner | A new integer programming model for the N job M machine flow shop problem[END_REF] derived a MILP formulation for the PFSP, here called Turner-Booth alternative (TBA) model. After deriving an equivalent mathematical expression for start time variables, in terms of processing and idle times of each job, the authors applied variable substitution techniques, significantly reducing the number of model constraints. We derived a two-stage robust counterpart of this model, for the TWCT objective, with decision variables Z i,j and F λ i as well as the new ones described below:

X λ r,j = idle time on machine Mr before the start of job in sequence position j given scenario λ.

Based on the above definitions, variables Z i,j are in the first stage, and variables X λ r,j and F λ i are in the second stage of this robust counterpart. The two-stage robust-counterpart of TBA model for the RPFS-TWCT can be formulated as follows:

Min y (4.18) st (4.5), (4.12), (4.13), (4.14), (4.16), (4.17),

X λ 1,j = 0, j = 2, . . . , n, λ ∈ Λ, (4.19
)

n i=1 p r-1,i + pr-1,iδ λ r-1,i Zi,1 + j-1 q=1 n i=1 p r,i -p r-1,i Zi,q + j-1 q=1 n i=1 pr,iδ λ r,i -pr-1,iδ λ r-1,i Zi,q + j s=2 Xr,s -Xr-1,s - n i=1 p r-1,i + pr-1,iδ λ r-1,i Zi,j ≥ 0, r = 2, . . . , m, j = 2, . . . , n, λ ∈ Λ, (4.20
)

F λ i ≥ m-1 r=1 n =1 p r, + p r, δ λ r, Z ,1 + j q=1 n =1 p m, + p m, δ λ m, Z ,q + j s=1 Xm,s -Q(1 -Zi,j), i = 1, . . .

Robust Counterpart for WST2 PFS Model

Wagner [START_REF] Harvey | An integer linear-programming model for machine scheduling[END_REF] proposed an all-integer programming model for a three-machine deterministic flow Tseng released an improved model called WST and, later on, a second version called WST2 [START_REF] Tseng | New MILP models for the permutation flowshop problem[END_REF],

which enforces the initial condition that all jobs are processed on the first machine without any in-sequence machine idleness. In our research, we derived a two-stage robust counterpart of the WST2 model, for the total weighted completion time objective, with decision variables Z i,j , X λ r,j and F λ i as described in the previous formulations, and variables Y λ r,j :

Y λ r,j = idle time of job in sequence position j after it finishes processing on machine Mr given scenario λ.

Variables Z i,j are in the first stage, and variables X λ r,j , Y λ r,j and F λ i are in the second stage of this robust counterpart. The WST2 model for the RPFS-TWCT can be formulated as follows:

F λ i ≥ j p=1 n x=1 p m,x + pm,xδ λ m,x Zx,p + j p=1 X λ m,p -Q(1 -Zi,j), i = 1, . . . , n, j = 1, . . . , n, λ ∈ Λ, (4.30)
Y λ r,j ≥ 0, r = 1, . . . , m, j = 1, . . . , n, λ ∈ Λ.

Robust Counterpart for TS2 PFS Model

The TS2 MILP model for the regular flow shop is based on an earlier model with the same name that was developed by Tseng et al. [START_REF] Fan | Two MILP models for the N× M SDST flowshop sequencing problem[END_REF] for the sequence-dependent setup times flow shop problem. This model uses the job ending or completion time variables employed in other scheduling models, which eliminates the need for the X and Y variables used in Wagner-WST2 model. Besides adapting the TS2 model to the TWCT objective, we also derived a two-stage robust counterpart with variables Z i,j and F λ i as described in the first formulation, along with variables E λ r,j :

E λ r,j = completion time of job in sequence position j after it finishes processing on machine r given scenario λ.

Variables Z i,j are again in the first stage, while variables E λ r,j and F λ i are in the second stage of this robust counterpart. The two-stage robust-counterpart of TS2 model for the RPFS-TWCT can

E λ 1,j+1 = E λ 1,j + n i=1 p 1,i + p1,iδ λ 1,i Zi,j+1 j = 1, . . . , n -1, λ ∈ Λ, (4.35
)

E λ r+1,1 = E λ r,1 + n i=1 p r+1,i + pr+1,iδ λ r+1,i Zi,1, r = 1, . . . , m -1, λ ∈ Λ, (4.36
)

E λ 1,1 = n i=1 p 1,i + p1,iδ λ 1,i Zi,1 λ ∈ Λ, (4.37
)

F λ i ≥ E λ m,j -Q(1 -Zi,j) i =

Robust Counterpart for TS3 PFS Model

Using an approach similar to the one applied in the TBA model, Tseng and Stafford [START_REF] Tseng | New MILP models for the permutation flowshop problem[END_REF] proposed a MILP formulation for the PFSP called TS3. By applying variable substitution on Wilson model, the start time variable, for a given r and j, is replaced by an expression that combines the sum of the processing times of jobs in sequence positions 1 through j -1 on machine 1, and the sum of the processing times of the job in position j on machines 1 through r -1, incremented of job's idle times (following each of these same machines). To apply Robust Optimization, we derived a two-stage robust counterpart of the TS3 model, adapted to the total weighted completion time objective, with variables Z i,j , F λ i and Y λ r,j as previously defined.

As in previous formulations, variables Z i,j are in the first stage, while variables Y λ r,j and F λ i are in stage two. The two-stage robust-counterpart of TS3 model can be formulated as follows:

Robust Counterpart for Manne PFS Model

Manne [START_REF] Manne | On the job-shop scheduling problem[END_REF] proposed a dichotomous-constraints integer programming model for the general job shop problem. The model assures that, for two jobs i and k, only one of each pair of completiontime subtraction constraints can hold, i.e., job i either precedes job k somewhere in the processing sequence, or it does not, thus implying that job k precedes job i. Later, Stafford and Tseng [START_REF] Stafford | On the Srikar-Ghosh MILP model for the N x M SDST flowshop problem[END_REF] adapted this model to a permutation flow shop (makespan objective). Based on this last model, we developed its robust counterpart, adapted for the TWCT objective, with the following decision variables:

D i,k = 1,
C λ r,i -C λ r,k + QD i,k ≥ p r,i + pr,iδ λ r,i , r = 1, . . . , m, i = 1, . . . , n -1, k = i + 1, . . . , n, λ ∈ Λ, (4.48) C λ r,i -C λ r,k ≤ Q(1 -D i,k ) -(p r,k + p r,k δ λ r,k ), r = 1, . . . , m, i = 1, . . . , n -1, k = i + 1, . . . , n, λ ∈ Λ, ( 4

Robust Counterpart for Liao-You PFS Model

Liao and You [START_REF] Liao | An improved formulation for the job-shop scheduling problem[END_REF] made algebraic combinations of each pair of Manne disjunctive inequality constraints. As a result, they obtained one equality constraint associated to a surplus variable, q r,i,k , related to the precedence relationship of jobs i and k on machine r. To ensure feasibility, a second constraint was added to impose an upper bound on these surplus variables.

Based on Liao-You model (makespan objective), we developed its robust counterpart, adapted for the total weighted completion time objective, with the following additional decision variables:

S λ r,i
start time of job i on machine r given scenario λ. q λ r,i,k surplus variable related to the precedence relationship of jobs i and k on machine r given scenario λ.

In this two-stage RO formulation, D i,k are, as in the previous model, the first-stage variables, while S λ r,i and q λ r,i,k are on the second stage.

S λ r,i -S λ r,k + QD i,k -(p r,k + p r,k δ λ r,k ) = q λ r,i,k , r = 1, . . . , m, i = 1, . . . , n -1, k = i + 1, . . . , n, λ ∈ Λ, (4.56) Q -(p r,i + pr,iδ λ r,i ) -(p r,k + p r,k δ λ r,k ) ≥ q λ r,i,k , r = 1, . . . , m, i = 1, . . . , n -1, k = i + 1, . . . , n, λ ∈ Λ, (4.57)
S λ r,i ≥ 0, r = 1, . . . , m; i = 1, . . . , n, λ ∈ Λ, (4.58) Solving each of the aforementioned models, for all possible scenarios λ ∈ Λ, is unrealistic.

q λ r,i,k ≥ 0, r = 1, . . . , m; i = 1, . . . , n -1, k = i + 1, . . . , n, λ ∈ Λ. ( 4
Therefore, in the next section, we will describe an algorithm capable of obtaining optimal results for RPFS-TWCT by considering a subset of relevant scenarios.

Column-and-Constraint Generation applied to the RPFS-TWCT

This section presents an exact method for solving RPFS-TWCT under budgeted uncertainty.

Our approach is based on a cutting plane procedure for two-stage RO problems, called Columnand-Constraint Generation (C&CG), recently applied in the efficient solution of robust scheduling problems [START_REF] Luis | Multi-process production scheduling with variable renewable integration and demand response[END_REF][START_REF] Silva | Solution algorithms for minimizing the total tardiness with budgeted processing time uncertainty[END_REF][START_REF] Levorato | Exact solutions for the two-machine robust flow shop with budgeted uncertainty[END_REF], as well as in the exact solution methods proposed in the previous chapter.

Besides generating new constraints, as usual in this kind of method, each cutting plane of C&CG is also associated with a set of new decision variables for the recourse problem [START_REF] Zeng | Solving two-stage robust optimization problems using a columnand-constraint generation method[END_REF].

Given one of the robust counterparts presented in Section 4.3, the main idea is to relax it into a master problem (MP) where each robust constraint is written only for a finite subset of the uncertainty set, i.e., for a Θ ⊆ Λ. Then, given a feasible solution to the MP, this solution is checked for feasibility over the whole set Λ, by solving a separation subproblem (SP). If the SP solution indicates that one or more robust constraints become infeasible, the uncertainty set is expanded by adding one or more scenario vectors to Θ. Whenever the master problem is augmented, according to the columnand-constraint generation procedure, the process is repeated.

For the RPFS-TWCT problem, the MP solution represents a permutation σ where σ(j) is the order in which job j is executed. The separation problem is then solved by the worst-case procedure, which, given the sequence σ, returns the highest possible total weighted completion time under uncertainty set U Γ . Since the uncertainty set U Γ , defined in Section 4.3, is polyhedral, the number of possible extreme solutions that can be fetched by the procedure is finite, and the C&CG algorithm certainly terminates [START_REF] Zeng | Solving two-stage robust optimization problems using a columnand-constraint generation method[END_REF].

C&CG algorithm

We describe the solution method in a general way that can be applied to any two-stage RO

R W ilson = {B (λ) r,j , F (λ)
r,j , ∀λ ∈ Θ, r = 1, . . . , m, j = 1, . . . , n}. The master problem (MP) is solved iteratively, with each step generating a subset of problem constraints and associated recourse variables R, regarding one newly-generated scenario λ v ∈ Θ. The subset of scenarios Θ is iteratively enlarged by solving the associated subproblem at each iteration.

In order to generate the scenarios defined by Θ, we assume that an oracle can obtain an optimal solution to the worst-case subproblem, based on the current MP solution. At iteration v, for a given value of MP first-stage decision variables F, the subproblem SP is defined as:

(SP) Z(σ) = max λv∈Λ ϕ(σ, P λv ) (4.60)
where job permutation σ is derived using MP optimal values of first-stage variables F at iteration v

(either Z (v) i,j or D (v)
i,j , depending on the model). The oracle used to find the optimal solution λ * (v) for (SP) is the worst-case MILP described in Section 4.4.2.

The C&CG method is presented in Algorithm 6, where LB denotes the lower bound, UB denotes the upper bound, v is the iteration counter, and Θ is the set of worst-case scenarios generated by the method. The procedure starts by considering Θ with a single scenario in which no operation presents processing time oscillation, and stops whenever the tolerance of optimality ∈ R + is reached. It returns the optimal solution value of the robust problem, along with the first-stage variables F * , which represent the optimal permutation σ * .

Worst-case evaluation based on a MILP model

Solving the SP problem in (4.60) consists in determining the worst-case realization under the budgeted uncertainty set U Γ , for a specific sequence of jobs σ = {σ(j), j = 1, . . . , n}. From equation (4.2), given a protection level Γ and a schedule σ, we extend the definition of worst-case total weighted completion time or robust cost to Z(σ, Γ) with the equation:

Z(σ, Γ) := max P λ ∈ U Γ {ϕ(σ, P λ )}. ( 4

.61)

We assume that parameter Γ, from the budgeted uncertainty set, is a non-negative integer. Since any worst-case realization will use as much budget of uncertainty as possible, we can expect that, for the optimal solution of (4.61), with worst-case scenario λ *

(v) , m r=1 n i=1 δ λ * r,i = Γ.
The worst-case scenario, and associated robust cost, can be obtained by solving the following proposed SP MILP. As input parameters, besides the processing time matrices p r,i and p r,i , the SP MILP requires the budget parameter Γ along with the sequence of jobs σ * , provided by the current Master Problem solution F * . Since the proposed SP MILP relies on an assignment-based formulation, an equivalent input matrix of assignment values z * i,j needs to be derived in the following way:

The worst-case MILP is stated as follows: Ar,j ≥ 0, Er,j ≥ 0, Dr,j ∈ {0, 1}, r = 1, . . . , m, j = 1, . . . , n, (

Max n i=1 wi n j=1 Cm,jz * i,j (4.62) st C1,1 = n i=1 (p 1,i + p1,i∆1,i)z * i,1 , ( 4
The objective function (4.62) states that, given a fixed job permutation z * i,j , this formulation aims to find a worst-case processing time scenario that maximizes the weighted sum of completion times, among all possible scenarios defined by U Γ . Constraints is bounded by the processing time of job σ * (j) (in position j) on machine r, plus the maximum of C r,j-1 and C r-1,j , which is equivalent to the minimum of these two variables (E r,j ) plus the absolute difference between the same two variables (A r,j ). Constraints (4.73) define the budget of uncertainty regarding the maximum allowed processing time deviations m r=1 n i=1 ∆ r,i given the execution of all jobs i on all machines r. Finally, constraints (4.74)-(4.76) define the domain of the variables.

We employed two strategies to improve the performance of the SP MILP model. First, we adopted a problem-specific method when calculating Big-M values, where each Q value varies according to the constraint it belongs to. Second, in order to strengthen the formulation, the following valid inequality was added, improving solution times by a factor of 10:

A r,j = C r,j-1 + C r-1,j -2 × E r,j . (4.77)
The optimal solution of this MILP model, represented by ∆ * r,i values, consists in a valid worst- The new branching scheme produces exactly the same offsprings of each original node, but in multiple levels. In this case, one branch is always one of the children to be created (here called a permutation branch), while the second branch is a duplicate of the parent node N, which we call a meta node. Whenever a new permutation branch is created, an unscheduled job i will be fixed in position j of the partial permutation σ. This new partial permutation has to be reflected, in some way, on the node information manipulated by CPLEX, via a set of node cuts. For the flow shop MILP models at hand, this means one or more binary variables must have their bounds fixed. Observe that the other branch created, which contains the meta node, will receive no additional node cuts associated to it, but will receive additional information about the partial sequence generation.

For assignment-based flow shop models, variables Z will be fixed:

• Job i occupies sequence position j: Z i,j := 1; (4.78)

• Job i cannot occupy any other position k rather than position j: Z i,k := 0, ∀k = j; (4.79)

• No other job = i can occupy position j: Z ,j := 0, ∀ = i. (4.80)

For dichotomous-based flow shop models, partial order variables D will be fixed:

• Set all jobs that come before job i in partial permutation σ:

D ,i := 1, D i, := 0, ∀ ∈ σ, ( 4.81)
• All jobs that have not been scheduled yet will necessarily come after job i: where LB det is the lower bound of the deterministic PFSP-TWCT, assuming scenario λ and processing time matrix P λ .

D i, := 1, D ,i := 0, ∀ ∈ U. ( 4
To calculate (4.83), we applied the tight lower bound for the deterministic problem described by Chung et al. [START_REF] Chung | A branch and bound algorithm to minimize the total flow time for m-machine permutation flowshop problems[END_REF]. These authors developed a branch and bound algorithm to solve the m-machine permutation flowshop problem, which assumes that a partial permutation is defined at each step.

In their work, they considered two possible objectives: the unweighted and weighted total flow-time (i.e., TWCT). Their solution method efficiently handles test problems with n ≤ 15, thanks to an improved machine-based lower bound, together with a dominance test for pruning nodes.

It is worth noting that, despite the overhead from the combinatorial branch-and-bound emulation, the use of the lower bound LB M P to prune nodes has proved to be essential to the performance gains obtained with this new Master Problem solution method.

Experimental results

We conducted extensive experiments to assess the performance of the C&CG solution method as well as the proposed Robust Counterpart formulations.

Test instances

In the flow shop literature, there is no set of benchmark instances for the total weighted completion time objective. In order to verify the effectiveness of the proposed algorithms, our experiments were based on three instance sets3 obtained by adapting a robust PFSP instance generator described by Ying [START_REF] Ching | Scheduling the two-machine flowshop to hedge against processing time uncertainty[END_REF].

(i) Two-machine robust PFSP instances with 10 jobs (10x2). In his work, Ying [START_REF] Ching | Scheduling the two-machine flowshop to hedge against processing time uncertainty[END_REF] proposed six groups of instances, each one with a different number of jobs n ∈ {10, 20, 50, 100, 150, 200}.

The expected processing time pr,i (r = 1, 2; i = 1, . . . , n) is an integer drawn from the uniform distribution [START_REF] Balasubramanian | A novel branch and bound algorithm for scheduling flowshop plants with uncertain processing times[END_REF][START_REF] Ronald L Graham | Optimization and approximation in deterministic sequencing and scheduling: a survey[END_REF] and the largest processing time deviation is set as a fixed ratio of the expected processing time (i.e., p r,i = αp r,i ), with α ∈ {10%, 20%, 30%, 40%, 50%}. Ten instances were generated for each combination of n and α, for a total of 300 test instances. (iii) Robust PFSP instances with random processing time deviations. For each instance of the previous two sets with variability level α = 10%, we generated 4 new instances with distinct variability levels α r,i for each operation O r,i . First, we define a maximum variability level α max ∈ {30%, 50%, 100%, 200%}. Then, in each generated instance, the variability level α r,i of each operation O r,i is drawn from a uniform distribution in the interval [0, α max ). Therefore, the maximum processing time deviation of each operation equals p r,i = α r,i p r,i . The idea behind this new set is to generate instances whose operation processing time deviation follow a completely random behavior, when compared to the previous sets. This way, we will be able to assess the impacts of such behavior on the solution method.

Since all instances above are related to the makespan objective, no job weight information is available. Thus, for each instance, job weights (w j , ∀j ∈ J) were randomly generated, according to a uniform distribution in the interval [START_REF] Agra | The robust vehicle routing problem with time windows[END_REF][START_REF] Morstyn | Bilateral contract networks for peer-to-peer energy trading[END_REF]. These values are based on the job weight distribution from the real-world instances under study.

Computational environment and model observations

The C&CG algorithm was coded in Julia 1. , given all RC models and instances solved. % Best Performance is the percentage of instances where the model achieved shorter execution time (ties included); % Solved contains the percentage of instances solved within the time limit; % Solved < n × m > represents the percentage of solved instances of size n × m; Avg. % Gap is the average percentage gap of solutions from instances not solved to optimality; Median time is the median execution time, in seconds; Median iterations is the median of the number of iterations performed.

With particular interest in examining the impact of the budget of uncertainty parameter on scheduling performance, when solving each instance, we tested the RPFS-TWCT models by varying Γ according to ten ratios [START_REF] Balasubramanian | A novel branch and bound algorithm for scheduling flowshop plants with uncertain processing times[END_REF][START_REF] Braun | Stability of Johnson's schedule with respect to limited machine availability[END_REF][START_REF] De Deal | Job scheduling in petrochemical production: twostage processing with finite intermediate storage[END_REF][START_REF] Ferone | Combining simulation with a GRASP metaheuristic for solving the permutation flow-shop problem with stochastic processing times[END_REF][START_REF] Ronald L Graham | Optimization and approximation in deterministic sequencing and scheduling: a survey[END_REF][START_REF] Hussain | Robust optimization-based scheduling of multi-microgrids considering uncertainties[END_REF][START_REF] Kaminsky | Probabilistic analysis and practical algorithms for the flow shop weighted completion time problem[END_REF][START_REF] Lasseter | Microgrid: a conceptual solution[END_REF][START_REF] López-Ibáñez | The irace package: Iterated racing for automatic algorithm configuration[END_REF] and 100%) of operations with uncertain processing times. Table 4.2 summarizes the obtained results with a performance comparison of the RC models.

In this table, we present medians to mitigate the effect of instances not solved within the time limit.

Manne C&CG is the one that solves the majority of the instances. It also obtains the lowest average % gap for instances not solved to optimality. The % Best Performance measurement indicates that the Manne model solved 46% of instances with the best performance, followed by Liao-You, that solved 34%, and Wilson, with 14%. Measurements % Solved 10 × 4 and % Solved 10 × 5 reveal that the RC models which rely on job assignment constraints solved less instances to optimality within the time limit. The %Solved and Median time measurements also favor the dichotomousbased models.

A second and deeper analysis, grouped by instance size, presents, in Table 4.3, the average performance of each RC model, including average run time values. When using average, the results of all instances (even outliers) are taken into account. Standard deviation is also included as a secondary measure. Additionally, the average number of iterations and its standard deviation are listed. As we could expect, these results show that, as instance size grows, the models become harder to solve, as seen on the smaller percentage of solved instances and increased average execution time. However, our results show that this is especially true for the assignment-based models.

A complementary investigation, based on the α and α max parameters, is portrayed in Table 4.4.

In this context, we explore solution statistics regarding the four best performing models, when solving

Protection level (%)

Robust cost : Z( , )

SimGRASP-Max( 25) RPFS( 5) RPFS( 10)=RPFS( 20) RPFS( 15) RPFS( 25)=RPFS( 30)=RPFS( 35) RPFS( 40)=RPFS( 45) RPFS( 50)=RPFS(55)=...=RPFS [START_REF] Morstyn | Bilateral contract networks for peer-to-peer energy trading[END_REF] Det RPFS( 5) RPFS( 10) RPFS( 15) RPFS( 25) RPFS( 40 processing time matrices P obtained after simulation runs, let ϕ(σ) be the random cost (TWCT ) of scheduling σ, which depends on the realization of P . E(ϕ(σ)) and SD(ϕ(σ)) are empirical estimations of expectation and standard deviation of ϕ(σ), respectively. Also, V aR(ϕ(σ)) and CV aR(ϕ(σ)) are the value-at-risk and conditional value-at-risk of ϕ(σ), respectively, both at 95% confidence level.

In other words, V aR(ϕ(σ)) is equivalent to the 0.95 quantile of ϕ(σ), while CV aR(ϕ(σ)) represents the average of the largest 5% values of ϕ(σ). Also, by analyzing the smallest maximum TWCT obtained in triangular distribution simulations, the value M ax(ϕ(σ)) observed for scheduling RPFS(25,30,35) is 4.3% cheaper than SimGRASP, and, at the same time, its expected TWCT is 1.8% less than the stochastic schedule. Following these observations, the decision-maker of the oil company can evaluate the hedge provided by the obtained robust solutions, and choose a specific solution (and associated protection level) that does not cause a significant increase in the expected solution cost, when compared to stochastic and deterministic solutions.

Evaluating hedge value and price of robustness

Given a protection level Γ, besides robust cost Z, two other measures can be used to evaluate performance: hedge value H and price of robustness η, defined as: where σ * Γ is the optimal solution of RPFS(Γ), σ * is the optimal solution of Det(P=), and ϕ(.) is the TWCT function.

The first measure, H(Γ), represents the value gained from adopting the robust sequence σ * Γ , instead of the optimal nominal sequence σ * in the occurrence of the worst-case scenario associated with protection level Γ. A visual interpretation of H(Γ) can be made in Figure 4.2, by analysing to the robust cost difference between the solutions from Det (σ * ) and RPFS(Γ) (σ * Γ ) methods, at each protection level Γ. The second measure, η(Γ) is defined as the price paid by the decision-maker for employing the robust sequence σ * Γ in place of the optimal nominal sequence σ * in the scenario of nominal processing times (when P = P , i.e., no processing time deviations). In other words, H(Γ) can be seen as the regret of employing sequence σ * in the worst-case scenario, and η(Γ) represents the trade-off between robustness and optimality.

Discussion

In this chapter, we presented an exact solution method for the m-machine robust permutation flow shop problem to minimize the total weighted completion time. Similarly to the previous chap- is the average relative cost difference between RPFS(Γ) and Det(P=), given all simulated scenarios λ.

was available in the literature, we also proposed a set of benchmark instances to assess the algorithm's performance. After extensive computational experiments and algorithm enhancements, we prepared a case study to evaluate the robust solutions obtained from problem instances that depict the maintenance effort of a real oil platform. Once again, we applied Monte-Carlo simulations to compare the solutions returned by the robust, deterministic, and stochastic methods. With a particular interest in the expected behavior of the solutions from each method, we wanted to verify a possible increase in the expected solution cost of the robust method in the long run. According to simulations based on three probability distributions, the hedge provided by the obtained robust solutions did not cause a significant increase in the expected solution cost compared to the stochastic and deterministic solutions.

In summary, experimental results indicated the feasibility of applying the proposed robust solution methods to real-world problem instances, including those from the oil and gas industry. Additionally, the same methodology applied in our studies can be followed by decision-makers, when choosing an appropriate model result. By examining a pool of solutions with distinct budgeted uncertainty levels, they can select the most appropriate one according to their risk preferences, thus balancing solution protection and expected performance in the long run.

Perspectives

The different investigations conducted in this work suggest diverse questions that, to the best of our knowledge, remain open. At the end of each chapter, we have already discussed the most technical aspects related to these questions. In the following, we review the larger research points deserving some longer-term efforts.

When evaluating CCP models, we only tested contracts where the microgrid buys electricity from the energy companies, but not the opposite (i.e., selling contracts). In this sense, the energy exchange between multiple microgrids could be seen as a game-theoretic model. It would also be interesting to perform sensitivity analysis on energy contract values, such as fixed and variable prices, and minimum and maximum amounts. The main question to be answered would be: at which point does one contract become more attractive than the other?

The methodology itself could also be enhanced. For example, extending the RTCS method to use forecasting techniques that help predict the amount of energy produced or consumed by the microgrid, according to the season of the year, or following other trends and patterns. Several machine learning algorithms and frameworks are available for this task [START_REF] Siebert | A Systematic Review of Packages for Time Series Analysis[END_REF]. Another useful technique would be Reinforcement Learning [START_REF] Wiering | Reinforcement Learning: State-of-the-Art[END_REF], which could also prove helpful inside the RTCS, making better decisions on the order of execution of energy-related operations. One option involves the incorporation of an online learning algorithm for real-time energy scheduling. For instance, the scheduling procedure could predict which kind of operation would be better suited at a given period (e.g., store or sell surplus energy; retrieve from storage or buy from engaged contracts) and in which order. Lastly, model refinements could be included, such as adding ramping constraints for generators and improving the battery efficiency and degradation model. Furthermore, the uncertainty set adopted in the robust optimization model could also be extended to take into account the temporal correlations of uncertainty, following a similar approach to the dynamic uncertainty set adopted by [START_REF] Lorca | Adaptive Robust Optimization With Dynamic Uncertainty Sets for Multi-Period Economic Dispatch Under Significant Wind[END_REF]. The main idea is that, in any time slot, individual oscillations in energy production and consumption values are not independent of each other, but correlated.

Regarding the robust scheduling problems studied in this thesis, the computational complexity of 2RPFS under budgeted uncertainty remains an important topic to be studied. Future research may also attempt to develop efficient heuristics for the m-machine RPFS-TWCT problem. However, this largely depends on the efficient solution to the worst-case problem. In this sense, a computational complexity study is needed, and, if possible, a pseudopolynomial algorithm for the worst-case TWCT could be designed. Given that the RPFS-TWCT problem is NP-hard, this would be particularly important. To this end, our exact approach could play a useful role in the performance evaluation of any heuristic.

Another avenue for future research could involve the design of new sets of robust problem instances, structured according to each problem's characteristics (e.g., where processing times are such that the critical path remains fixed or alternates according to a pattern). This would allow a deeper analysis of each robust problem's easiest and most difficult instances. Moreover, the solution methods proposed in this work could be extended to similar scheduling problems and different objective functions, such as total tardiness and total flow time.

Finally, concerning all problems studied in this thesis, an interesting topic involves the generation of multiple optimal solutions for the robust problem and how to inspect the quality of each one. As [START_REF] Ruiter | The impact of the existence of multiple adjustable robust solutions[END_REF] noted, different robust solutions may even have the same worst-case objective value, but might still differ on the mean objective value, or the expected value in the long run, considering the realization of several possible scenarios. Therefore, an important research question would be: given a protection level Γ, is it possible to generate a handful of optimal solutions and compare them in terms of the hedge provided as well as the expected performance, so that the decision-maker can choose the solution that best meets these requirements? Such analysis might be conducted as an additional step inside the framework applied in this thesis, and, in this sense, the work of [START_REF] Iancu | Pareto efficiency in robust optimization[END_REF] on Pareto Robustly Optimal solutions 1 could serve as a starting point. their worst-case values, in which Γ i ∈ [0, | N i |] and is not necessarily an integer. The idea is that all uncertain coefficients in N i are often unlikely to simultaneously reach their worst-case values.

Therefore, it may be adequate to protect against up to Γ i of those coefficients in N i reaching their worst-case values, and one coefficient, say t i , to change by (Γ i -[Γ i ) âi,t i . Regarding this uncertainty set, a protection function β(x, Γ i ) for each constraint i is defined as follows: the decision maker is able to adjust the solution robustness against the level of solution conservatism. When Γ i = 0, β(x, Γ i ) = 0, the problem is equivalent to the nominal problem. On the other hand, if Γ i = N i , we obtain the most conservative version of the problem, which is equal to the worst-case model, as developed by Soyster [START_REF] Allen | Convex programming with set-inclusive constraints and applications to inexact linear programming[END_REF].

β(x, Γ i ) = max N i ∪{t i }: N i ⊆N i ,| N i |= Γ i ,t i ∈N i \ N i { j∈N i âij x j + (Γ i -Γ i )â i,t i x t i }, ∀i (
In order to solve the Budget-RO model, Bertsimas and Sim applied the duality theory, reformulating the problem as an LP problem. They began by formulating an LP problem whose objective function equals the protection function β(x, Γ i ). In other words, given the decision variable vector x, the protection function β(x, Γ i ) defined in Constraint (B.5) is equal to the objective function of the following LP problem, which will be called LP-Beta(i).

[LP-Beta(i)] Maximize The expression (B.9) defines an objective function equivalent to the protection function. Constraints (B.10) and (B.11) ensure that Γ i of those coefficients in N i reach their worst-case values and one coefficient to change by (Γ i -Γ i )â i,t i . This is equivalent to selecting a subset:

{ N i ∪ {t i } : N i ⊆ N i , | N i |= Γ i , t i ∈ N i \ N i }

Part , Chapter 1 -

 1 Introductionindicate "loss of quality" when adopting specific robust solutions instead of deterministic or stochastic ones.

-

  Mario Levorato, Rosa Figueiredo, Yuri Frota, Exact solutions for the two-machine robust flow shop with budgeted uncertainty, European Journal of Operational Research, 2021, Elsevier, ISSN 0377-2217, https://doi.org/10.1016/j.ejor.2021.10.021. [82] -Mario Levorato, Rosa Figueiredo, Yuri Frota. Robust microgrid energy trading and scheduling under budgeted uncertainty, Expert Systems with Applications, 2022, Elsevier, ISSN 0957-4174, https://doi.org/10.1016/j.eswa.2022.117471. [83] -International Conferences / Workshops -Mario Levorato, Rosa Figueiredo, Yuri Frota, Antoine Jouglet, David Savourey. Real-time command strategies for smart grids based on the Robust Contract-based Collaboration Problem International Network Optimization Conference (INOC 2019), Jun 2019, Avignon, France [84] -National Conferences / Workshops with proceedings -Mario Levorato, Rosa Figueiredo, Yuri Frota, Antoine Jouglet, David Savourey. Real-time energy scheduling for microgrids based on the Contract Collaboration Problem. 21eme Conferénce ROADEF de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2020), Feb 2020, Montpellier, France [85]1.7. Organization -Mario Levorato, Rosa Figueiredo, Yuri Frota, David Sotelo. The 2-machine robust flow shop problem under budgeted uncertainty. 22eme Conferénce ROADEF de la société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2021), Apr 2021, Mulhouse, France [86] -Submitted Articles for International Journals -Mario Levorato, David Sotelo, Rosa Figueiredo, Yuri Frota. Robust permutation flow shop total weighted completion time problem: solution and application to the oil and gas industry. Paper submitted to Computers & Operations Research, Elsevier, 2022.

Figure 2 . 1 -

 21 Figure 2.1 -The Contract Collaboration framework

Figure 2 . 1 )

 21 Figure 2.1). The solution to the so-called Contract Collaboration Problem (CCP), formally described in Section 2.2.1, provides the client with a commitment planning for the time horizon (i.e. which contracts to engage at each time period). Once this decision has been made, the list of engaged contracts cannot be changed for the whole time horizon.

Example 2 . 5 . 1 .

 251 also be associated with the highest possible production of an uncertain system s ∈ S N D . Let T = {0}, C = C 0 = {c 1 }, S N D = {s 1 }, S D = B = ∅ and S N D = {s 2 }.

Figure 2 . 3 -

 23 Figure 2.3 -Cumulative total costs and out-of-contract (OC) costs of the best deterministic (Det) and robust (Rob) CCP models (and associated policies) of each season, obtained after simulation over the whole time horizon (from January 2015 until May 2018).

  of the problem, by developing an exact method, based on the Column-and-Constraint (C&CG) generation algorithm. Afterwards, we solve the m-machine version of the problem, with the application of both metaheuristics and exact methods.We start this chapter introducing the classical Permutation Flow Shop (PFS) Problem, whose processing times are deterministic (i.e. fixed). The four most well-known MILP models for this problem are also presented, in Section 3.2.3. An extensive literature review on solution methods for the PFS problem with uncertain processing times is presented in Section 3.3. The two-machine Robust Permutation Flow Shop Problem is introduced in Section 3.4, together with the budgeted uncertainty set and two proposed robust counterpart formulations. In sequence, Section 3.5 describes an exact solution method to the 2RPFS problem, which uses a dynamic-programming-based worstcase procedure. The obtained performance is then discussed in Section 3.6, based on extensive computational experiments on existing literature instances.The second part of this chapter is devoted to the m-machine version of the Robust Permutation Flow Shop (RPFS) problem and proposes, in Section 3.7, an extension of the 2RPFS budget uncertainty set, now considering m machines and a single budget parameter. This section also presents extended versions of the Robust Counterparts originally introduced in Section 3.4.3, which can now be used to solve the RPFS problem with an arbitrary number of machines. A baseline exact solution method for the problem is then depicted in Section 3.8, generalizing the solution method and worst-case procedures initially proposed in Section 3.5. With solution method efficiency in mind, Section 3.9 introduces a Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristic to solve the RPFS, followed by Section 3.10, with the obtained results of exact and heuristic solution methods. Finally, we close this chapter with a general discussion on the results obtained when solving both 2RPFS and m-machine RPFS problems, in Section 3.11.

n

  number of jobs m number of machines r machine indices; r ∈ {1, 2, . . . , m} i, k job indices; i, k ∈ {1, 2, . . . , n} j sequence position; j ∈ {1, 2, . . . , n} J set of job indices: J = {1, 2, . . . , n} M set of machine indices: M = {1, 2, . . . , m} Input parameters {pri} m × n matrix of processing times of job i on machine r Model variables Brj start (begin) time of job in sequence position j on machine r Erj completion (end) time of job in sequence position j on machine r Sri start time of job i on machine r Cri completion time of job i on machine r Cmax maximum flowtime (makespan) of the schedule determined by the completion time of the job in the last sequence position on the last machine Xrj idle time on machine r before the start of job in sequence position j Yrj idle time of job in sequence position j after it finishes processing on machine r D ik = 1, if job i is scheduled any time before job k 0, otherwise Zij = 1, if job i is assigned to sequence position j 0, otherwise D ik and Z ij are binary integer variables, while the others are real variables that take integer values when processing times are also integer values. The four most popular MILP models for the PFS Problem are described next.

. 6 )

 6 Constraints (3.2) and(3.3) are the classical assignment problem, ensuring that each job is assigned to one, and only one sequence position; and that each sequence position is filled by one, and only one job. Constraints (3.4) and (3.5), called Job-Adjacency Machine-Linkage (JAML) constraints, ensure that (a) the job in sequence position j cannot begin processing on machine r + 1

25 )

 25 Where constraints(3.22) represent a lower bound on the start time of job i on the subsequent machine r + 1, constraints (3.23) are the algebraic combination of the paired disjunctive constraints (3.18) and(3.19) from the Manne model, and constraints (3.24) define an upper bound on the respective surplus variable q rik . Finally, constraints (3.25) represent the makespan value (largest completion time on the last machine m, given all jobs i ∈ J, such that C mi = S mi + p mi ).

1 -

 1 Regret 2 machines: Greedy [74] D, I 2 machines: 3 machines: Evolutionary [28] I Branch & Bound m machines: Constructive [29] I [74] D, I Scatter Search [123] I 2 jobs: O(m) [6] Summary of algorithms listed in the literature review regarding the Robust PFSP (makespan objective). For each work, we specify how processing time uncertainty was represented: a D means discrete processing time matrices; an I means processing time intervals.

26 )

 26 For any sequence σ ∈ Σ, the valueZ(σ) := max λ∈Λ {ϕ(σ, P λ )} (3.27)is called the worst-case makespan or robust cost for σ. A maximizer in (3.27) is called a worstcase scenario for σ.

37 )

 37 The objective function(3.29) and constraint(3.30) have the goal of finding a robust schedule that minimizes the makespan y of the worst-case scenario, among all possible scenarios. Constraints (3.31) and (3.32) are the Job-Adjacency and Machine-Linkage (JAML) constraints from the Wagner model, written for each scenario λ ∈ Λ. We refer the reader to Figure 3.1 for an illustrative JAML diagram. They ensure that, for each scenario λ: (a) the job in sequence position j cannot begin processing on machine M 2 until it has completed its processing on machine M 1 , and (b) the job in sequence position j+1 cannot begin its processing on machine M r until the job in sequence position

Figure 3 . 1 -

 31 Figure 3.1 -JAML diagram for Wagner model, where T T r,j = n i=1 p r,i + p r,i δ λ r,i Z i,j .

46 )

 46 The objective function(3.38) and constraint(3.39) state that this formulation aims to find a robust schedule that minimizes the makespan y of the worst-case scenario, among all possible scenarios. Constraints (3.40) and (3.41) guarantee that the robust schedule is feasible and that start time variables are appropriately calculated for each scenario λ. Constraints (3.42) and (3.43) are as defined in the previous formulation. Constraints (3.44)-(3.46) define the domain of the variables.

  if model = W agner then Generate MP constraints (3.30)-(3.32)&(3.36) for λ * (v) 13 if model = W ilson then Generate MP constraints (3.39)-(3.41)&(3.45) for λ * (v) 14 Update Θ := Θ ∪ {λ * (v) : δ (v) = δ * } and set (v) := (v + 1)

  Det(P=): deterministic PFSP solution with P = {p r,i }, ∀r ∈ M, i ∈ J; -2RPFS(Γ 1 , Γ 2 ): Wagner-based 2RPFS model, solved with the C&CG framework. The Γ parameters are used to control the level of the conservativeness of the robust model, and both vary in the set {20%, 40%, 60%, 80%, 100%} as a fraction of the number of jobs n. The robust model with Γ 1 = Γ 2 = 0 is equivalent to Det(P=), while the one with Γ 1 = Γ 2 = n is the deterministic model that is entirely risk-averse and overestimates all parameters. The other values of Γ 1 and Γ 2 model intermediate risk aversions; Part , Nomenclature used in the models

Figure 3 .

 3 3(b), we can observe that either 2RPFS(40,40) or 2RPFS(60,60) offer the best protection against worst-case scenarios, depending on the combination of (Γ 1 %, Γ 2 %) values. Once again, the solutions Det(=) and SimGRASP-Max(25) present high robust costs. In particular, for (Γ 1 %, Γ 2 %) = (60, 60), the solution provided by 2RPFS(60,60) is 8% cheaper than Det(=) and SimGRASP-Max(25).

(a) Small uncertainty instance # 8 ,

 8 n = 150, α = 20% (RB1502008)

( a )Figure 3 . 2 -

 a32 Figure 3.2 -Probability distributions of makespan value for 2RPFS and SimGRASP solutions, according to simulation results from lognormal, triangular, and uniform distributions for uncertain job processing times.

(a) Small uncertainty instance # 8 ,Figure 3 . 3 -

 833 Figure 3.3 -Robust cost of deterministic, 2RPFS and SimGRASP solutions versus protection level (Γ 1 %, Γ 2 %). All presented 2RPFS solutions are optimal.

Figure 3 .

 3 2(a). Regarding the small uncertainty instance, the expected makespan performance of 2RPFS(40,60), 2RPFS(40,80), 2RPFS(60,40) and 2RPFS(80,80), are equivalent to SimGRASP. However, depending on the budget parameters, if we return to worst-case evaluation, as seen in Figure 3.3(a), the protection against worst-case scenarios varies considerably. The best performing solutions, from smallest to largest robust cost, are: 2RPFS(60,40), 2RPFS(80,40), SimGRASP-Min(25) and 2RPFS(40,60). When analyzing the large uncertainty instance in Figure 3.2(b), the following robust solutions present expected makespan performance quite similar to SimGRASP: 2RPFS(40,40), 2RPFS(60,60) and 2RPFS(80,40). However, according to the worst-case evaluation, only the first two provide better protection against worst-case costs.

  is the maximum observed ϕ(σ) in the simulation. Observe that 2RPFS(60,60) has the least E(ϕ(σ)) in lognormal distribution, while 2RPFS(40,20) presents the smallest expected makespan in symmetric triangular and uniform distributions. When analyzing the largest observed makespan, 2RPFS(60,60), 2RPFS(80,80), and 2RPFS(80,80) have the lowest ϕ max (σ) for lognormal, triangular and uniform distributions, respectively. The best solutions for Det(P=) and SimGRASP did not provide minimum values for any measure of the simulateddistributions. Also, by analyzing the smallest maximum makespan obtained in uniform distribution simulations, the value ϕ max (σ) observed for scheduling 2RPFS(80,80) is 2% cheaper than Sim-GRASP, and, at the same time, its expected makespan is 0.5% less than the stochastic schedule.

  best ones, which maximize hedge value H(Γ)%, are 2RPFS(60,20) for α = 10%, 2RPFS(60,40) for α ∈ {20%, 30%, 40%}, and 2RPFS(40,40) for α = 50%.

Γ₁ = 20 Γ₂=20

 20

53 )

 53 For any sequence σ ∈ Σ, the value Z(σ) := max λ∈Λ {ϕ(σ, P λ )}(3.54)

  Zi,j ∈ {0, 1}, i, j = 1, . . . , n, (3.65) B λ r,j ≥ 0, r = 1, . . . , m, j = 1, . . . , n, λ ∈ Λ, (3.66) y ≥ 0. (3.67) The objective function (3.56) and constraint (3.57) state that this formulation aims to find a robust schedule for the processing of n jobs that minimizes the makespan of the worst-case scenario, among all possible scenarios λ ∈ Λ. Constraints (3.58)-(3.62) guarantee that the robust schedule is feasible and that start time variables are appropriately calculated, for each scenario λ. Constraints (3.63) and (3.64) are the classical assignment constraints, ensuring, respectively, that each job is assigned to one and only one sequence position, and that each sequence position is filled by one and only one job. Finally, constraints (3.65)-(3.67) define the domain of the variables.

77 )

 77 The objective function(3.68) and constraint(3.69) state that this formulation aims to find a robust schedule for the processing of n jobs that minimizes the makespan of the worst-case scenario, among all possible scenarios λ ∈ Λ. Constraints (3.70)-(3.72) guarantee that the robust schedule is feasible and that idle time variables are appropriately calculated, for each scenario λ. Constraints (3.73) and (3.74) are as defined in Wilson formulation. Finally, constraints (3.75)-(3.77) define the domain of the variables.

Algorithm 3 : 6 Update σ = σ ∪ {j} 7 L 8 return σ Algorithm 4 : V ariableN eighborhoodDescent 1 2 Output: permutation σ 3 r = 1 4 while r ≤ vnd-size do 5 for σ ∈ N r (σ) do 6 if 7 r = 1 8 σ = σ 9 if Z(σ) has not improved then 10 r = r + 1 11 return σ

 367841256719101 ConstructiveP hase 1 Input: P , P and α 2 Output: permutation σ 3 σ = ∅; L g = Order(J) 4 while L g = ∅ do 5 Choose job j randomly among the first α. | L g | elements of L g g = L g -{j}; Re-order(L g ) Input: P , P and permutation σ Z(σ) < Z(σ) then

Figure 3 . 4 -

 34 Figure 3.4 -Constructive phase.

Algorithm 5 : 1 5 σ 6 σ 8 σ * = σ 9

 515689 RGRASP Input: P , P and α 2 Output: permutation σ * 3 σ * = ∅; Z(σ * ) = ∞ 4 while time limit is not reached do = ConstructiveP hase( P , P , α) = V ariableN eighborhoodDescent( P , P , σ) 7 if Z(σ) < Z(σ * ) then return σ *

Figure 3 . 5 -

 35 Figure 3.5 -Variable Neighborhood Descent procedure. N 1 stands for neighborhood #1, N 2 stands for neighborhood #2, and so on.

Part,Y 6 PY 1 P

 61 Nomenclature used in the models Me a s u r e I n s t a n c e t y p e / I n s t a n c e s i z e / Mo d e l e r Wi l s o n % B e s t P e r f o r ma n c e % S o l v e d A v g . % g a p S t d . d e v . o f % g a p A v g . i t e r a t i o n s S t d . d e v . o f i t e r a t i o n s A v g . MP t i me A v g . S P t i me A v g . t i me S t d . d e v . o f t i me 5 e r f o r ma n c e _ P e r _ I n s t a n c e _ 1 S o ma d e V a l u e d i v i d i d o p o r I n s t a n c e t y p e , I n s t a n c e s i z e e Mo d e l v s . Me a s u r e . A e x i b i ç ã o é fi l t r a d a e m I n s t a n c e s i z e e Me a s u r e . O fi l t r o I n s t a n c e s i z e ma n t é m 6 me mb r o s . O fi l t r o Me a s u r e ma n t é m 1 0 me mb r o s . Me a s u r e I n s t a n c e t y p e / I n s t a n c e s i z e / Mo d e l e r Wi l s o n % B e s t P e r f o r ma n c e % S o l v e d A v g . % g a p S t d . d e v . o f % g a p A v g . i t e r a t i o n s S t d . d e v . o f i t e r a t i o n s A v g . MP t i me A v g . S P t i me A v g . t i me S t d . d e v . o f t i me 4 e r f o r ma n c e _ P e r _ I n s t a n c e _ 2 S o ma d e V a l u e d i v i d i d o p o r I n s t a n c e t y p e , I n s t a n c e s i z e e Mo d e l v s . Me a s u r e . A e x i b i ç ã o é fi l t r a d a e m I n s t a n c e s i z e e Me a s u r e . O fi l t r o I n s t a n c e s i z e ma n t é m 1 0 x 3 , 1 0 x 4 , 1 0 x 5 , 1 5 x 5 e 2 0 x 5 . O fi l t r o Me a s u r e ma n t é m 1 0 me mb r o s .

  P _ S t a t s S o ma d e V a l u e d i v i d i d o p o r Me a s u r e v s . I n s t a n c e t y p e e I n s t a n c e s i z e . A e x i b i ç ã o é fi l t r a d a e m Me a s u r e e I n s t a n c e s i z e . O fi l t r o Me a s u r e t e m v á r i o s me mb r o s s e l e c i o n a d o s . O fi l t r o I n s t a n c e s i z e ma n t é m 1 5 me mb r o s .

Y

  S o l u t i o nMe t h o d I n s t a n c e t y p e / I n s t a n c e s i z e c e n t a g e S o ma d e P e r c e n t a g e d i v i d i d o p o r I n s t a n c e t y p e e I n s t a n c e s i z e v s . S o l u t i o n Me t h o d . A c o r mo s t r a s o ma d e P e r c e n t a g e . A s ma r c a s s ã o r o t u l a d a s p o r s o ma d e P e r c e n t a g e . Os d a d o s s ã o fi l t r a d o s e m Mo d e l e V a r i a b l e . O fi l t r o Mo d e l ma n t é m Nu l o e Wa g n e r . O fi l t r o V a r i a b l e ma n t é m Nu l o e % S o l v e d .

Figure 3 . 6 -

 36 Figure 3.6 -Box plots of GRASP gap LB % (left plot) and gap U B % (right plot) values, grouped by instance size, compared to the lower and upper bounds obtained by the C&CG method, respectively. Considers all C&CG solutions, optimal or not.

Figure 3 . 7 -

 37 Figure 3.7 -Box plots of gap U B % values for instance group Ying 15 × 5, grouped by instance alpha (left) and by Γ% (right), based on all solution values obtained by GRASP and C&CG methods. Considers all C&CG solutions, optimal or not. All GRASP solution values were obtained from 50 independent executions of GRASP.

Figure 3 . 8 -

 38 Figure 3.8 -Box plots of gap U B % values for instance group Taillard 20 × 5, grouped by instance alpha (left) and by Γ% (right), based on all solution values obtained by GRASP and C&CG methods. Considers all C&CG solutions, optimal or not. All GRASP solution values were obtained from 50 independent executions of GRASP.

1 . 1 )

 11 Where α represents the machine environment, β stands for job characteristics, and γ symbolizes the objective function. In our case: the flow shop problem, single job permutation, minimizing total weighted completion time.2. We use the notation [n] = {1, . . . , n}.the maximum possible total weighted completion time over all scenarios λ ∈ Λ:For any sequence σ ∈ Σ, the value Z(σ) := max λ∈Λ {ϕ(σ, P λ )} (4.2)

  shop, later extended to a m-machine MILP model by Stafford [129], and commonly named in the literature as Wagner model. In 2002, based on this model and works from other authors, Stafford and

(4. 31 )

 31 The objective function(4.23) and constraints (4.5), (4.12) and (4.13) are as defined in the first formulation. Constraints (4.24)-(4.29) guarantee that the robust schedule is feasible and that idle time variables are appropriately calculated, for each scenario λ. (4.30) are big-M constraints used to determine the completion time of job i on the last machine m, for each scenario λ. Finally, constraints (4.14), (4.16), (4.17), (4.22) and (4.31) define the domain of the variables.

  (4.63)-(4.64) are used to determine the completion time of the jobs on the first machine, while constraints (4.65) define the completion time of the first job on each machine r. For each machine r and job position j, constraints (4.66) and (4.67) are used to calculate the minimum value between the completion time of the previous job on the same machine (C r,j-1 ) and the completion time of the same job on the previous machine (C r-1,j ). Constraints (4.68)-(4.69), together with disjunctive constraints (4.70)-(4.71) are used to determine the absolute value of the difference between C r,j-1 and C r-1,j . These absolute values are used to define the completion time C r,j . Constraints (4.72) ensure that the completion time C r,j

4. 5 .

 5 Hybrid C&CG Method accomplish that, instead of generating the branching tree of Figure 4.1(a), we create a branching structure following the diagram in Figure 4.1(b). Consider an arbitrary node N from Figure 4.1(a).

Figure 4 . 1 -

 41 Figure 4.1 -(a) Search tree of the deterministic flow shop combinatorial branch-and-bound. (b) Diagram illustrating how flow shop multi-way branching was performed in CPLEX.

(

  ii) Robust PFSP instances with 3, 4 and 5 machines. Following the instance generation algorithm of Ying [159], we generated random instances with sizes n × m ∈ {10 × 3, 10 × 4, 10 × 5, 15 × 5}. Ten instances were generated for each combination of m × n and α, for a total of 200 test instances.

SpecificModelStatsNoHybrid

  ZN(LOOKUP(SUM([Value]), 0)) broken down by ModelType and Model vs. Instance size and Measure. The view is filtered on Instance size and Measure. The Instance size filter has multiple members selected. The Measure filter keeps 10 members.

10 × 5

 5 instances. It is possible to note the decrease of model performance as the α and α max values grow. This can be observed in the % Solved, Avg. % gap and Avg. time rows, from columns α = 10% until α = 50%, and from columns α max = 30% until α max = 200%.According to our experiments, the Liao-You and Manne Robust Counterparts are the ones that perform best when solving the RPFS-TWCT problem. The possible reason is related to how the objective function is calculated in each robust counterpart model. In all assignment-based models (namely Wilson, WST2, TBA, TS2 and TS3), when calculating the total weighted completion time, we multiply the weight of job i by its corresponding completion time. However, in these models, there are no variables representing the completion time of job index i. Instead, they represent the completion time of job in position k. To properly calculate the objective function, the adopted solution involves the creation of an auxiliary variable F i , representing the completion time of job i (on the last machine M m ). Then, in order to calculate each value of F i , it is necessary to apply several Big-M constraints, which make the MILP model relaxation weaker.On the other hand, the Liao-You and Manne robust counterparts, which are based on disjunctive constraints, directly offers these variables which represent the completion time of job index i, so the only Big-M constraints in the model are the ones already present in the original model.

Figure 4 . 2 -

 42 Figure 4.2 -Robust cost of deterministic, RPFS and SimGRASP solutions versus protection level Γ%. All presented RPFS solutions are optimal.

Figure 4 . 3 -

 43 Figure 4.3 -Probability distributions of TWCT value for RPFS(Γ), Det and SimGRASP solutions, according to simulation results from lognormal, triangular, and uniform distributions for uncertain processing times.

  Finally, M ax(ϕ(σ)) is the maximum observed ϕ(σ) in the simulation. Observe that RPFS(25,30,35) has the least E(ϕ(σ)) in all distributions. When analyzing the largest observed TWCT, RPFS(5), has the lowest M ax(ϕ(σ)) for lognormal, triangular and uniform distributions. The best solutions for Det and SimGRASP did not provide minimum values for any measure of the simulated distributions. Indeed, SimGRASP presented the worst values for the largest observed TWCT in lognormal and triangular distributions.

Table 4 . 6 -

 46 Simulation summary for instance 9×4 with RPFS(Γ), Det and SimGRASP solutions after 10, 000 simulation runs under lognormal, triangular, and uniform distributions of operation processing times. Minimum and maximum values, for each row, are highlighted. Similar robust solutions for different Γ values are grouped in the same column (e.g., RPFS[START_REF] Balasubramanian | A novel branch and bound algorithm for scheduling flowshop plants with uncertain processing times[END_REF][START_REF] Braun | Stability of Johnson's schedule with respect to limited machine availability[END_REF]).

  H(Γ) = Z(σ * , Γ) -Z(σ * Γ , Γ), (4.84) η(Γ) = ϕ(σ * Γ , P ) -ϕ(σ * , P ),(4.85)

5 .

 5 * ,Γ)-Z(σ * Γ ,Γ) Z(σ * Γ ,Γ) for various protection levels, based on the two instances from this case study. Among the schedules obtained when solving RPFS with different Γ levels, the best ones, which maximize hedge value H(Γ)%, are RPFS(5) for instance 9 × 4, and RPFS(25) for instance 15 × Based on the simulation framework presented in Section 4.7.1, we close this section with a further analysis of the actual cost overhead of robust solutions in the long run. Two performance measures are calculated for instance 9 × 4, as shown in Table 4.8. The obtained results show that, for the protection levels Γ used in the study, robust solutions RPFS(15), RPFS(25), RPFS(30), and RPFS(35) present two important characteristics: (i) high proportion of cheapest solutions (ω(Γ) > 50%), and (ii) smaller expected costs, i.e., negative relative cost difference ∆η(Γ). All in all, RPFS provides a pool of robust schedules decision-makers can choose based on their risk preferences.

B. 5 ). 8 )

 58 where x = (x j , ∀j) is the decision variable vector. Based on the above idea, the budgeted RO model (still nonlinear) is presented as:(Budget-RO) Maximize j c j x j (B.6) subject to j a ij x j + β(x, Γ i ) ≤ b i , ∀i (B.7) x j ≥ 0, ∀j(BThe expression (B.6) to be maximized is the objective function. Constraints (B.7) are the functional constraints, which use a protection function β(x, Γ i ) for each constraint to control the degree of uncertainty. Constraints (B.8) are the non-negativity constraints. Note that by varying Γ i ∈ [0, | N i |],

  ij ≤ 1, ∀j ∈ N i (B.11)

2 The Contract Collaboration Framework Client Drivable Systems Non Drivable Systems Non Drivable Uncertain Systems produces consumes

				①
		② Real-Time Command Strategy
	t =0	t =1	t =2	Time
		Power		horizon
				max
				min
	t =0	t =1	t =2	Time
		Power		horizon

Part , Chapter 2 -The Robust Contract Collaboration Problem (RCCP) 2.

Partner Contract Subscription via a set of contracts Period Engage Cost Unit Cost Min kWh

					Max
					kWh
	1	0.033	0.009	5k	7k
	1	0.125	0.010	8k 11k
	2	0.022	0.016	2k	5k
	2	0.022	0.018	4k	5k
	2	0.437	0.004	9k 15k
	3	0.321	0.004 15k 18k
	3	0.875	0.004 30k 36k
	...

Table 2

 2

	.1 -Summary of the works listed in literature review. SO (Stochastic Opt model), RO (Robust
	Opt model). Uncertainty: list of uncertain parameters. REN (Renewable energy production), CHP
	(Combined Heat and Power), PEV (Plug-in Electric Vehicle), Wind (Wind Generator), PV (Photo-
	Voltaic). Contract: type of contract used to buy and sell energy.

  amount of energy stored in s ∈ B at time period t ∈ T ∪ { t} e t ≥ 0 extra amount of energy requested by the client (out of any engaged contract) at time period It

	Part , Nomenclature
	vs ≥ 0 cost of energy unit charged/discharged by storage system s ∈ B
	u min s	≥ 0 minimal storage level of system s ∈ B
	u max s	≥ 0 storage capacity of system s ∈ B
	u 0 s ≥ u min s	initial storage level (at period I0)
	0 ≤ λs ≤ 1 the loss coefficient of system s ∈ B
	θ abs s	> 0 maximum energy stored in s ∈ B during ∆ time units
	θ ref s	> 0 rated capacity, i.e., maximum energy delivered during ∆ time units
	Model variables
	y t c	1 if the client engages contract c ∈ Ct at period It 0 otherwise
	q t c amount of electricity sold (< 0) / bought (> 0) by the client at time period It related with contract c ∈ Ct
	0 ≤ x t s ≤ 1 percentage of time period It drivable system s ∈ SD is used
	g t s ≥ 0 energy fed into storage system s ∈ B during period It
	h t s ≥ 0 energy consumed from storage system s ∈ B during period It
	r t s ≥ 0
			I Time periods: I = {I0, .., It -1 }
			T Time period indexes: T ={0, .., t -1}
			Ct ⊆ C Contracts offered by partner at period It
			SD ⊆ S Certain drivable systems
			SND ⊆ S Certain non-drivable systems
			B (Certain, drivable) storage systems
	Input parameters -Partner
			v t c ≥ 0 fixed cost paid by the client for engaging contract c ∈ Ct at period It, ∀ t ∈ T
			α t c ≥ 0 cost per energy unit consumed/provided according to contract c ∈ Ct at period It
			Π -t,c minimal energy quota for contract c ∈ Ct during period It
			Π + t,c maximal energy quota for contract c ∈ Ct during period It
			β t ≥ 0 cost per energy unit consumed by the client at period It not provided by engaged contracts, ∀ t ∈ T
	Input parameters -Client
			δ t ≥ 0 length of period It: how many slots of ∆ time units compose this time period
			P t s energy consumption(< 0)/production(> 0) of s ∈ (SD ∪ SND) during the whole time period It
			vs cost per energy unit produced(> 0)/consumed(< 0) when using system s ∈ (SD ∪ SND)
			P min t s minimum energy to be produced(> 0)/consumed(< 0) by drivable system s ∈ SD before the end of period It

.4.2 Mixed-Integer Linear Programming formulation

	Based on the model variables defined, we present a Mixed-Integer Linear Programming (MILP)
	model, whose optimal solution provides the client with a commitment planning for the whole time
	horizon: which contracts to engage in each time period.
	Min	(v t c y t c + α t c q t c ) +	vs	P t s x t s +	vs	(g t s + h t s ) +	β t et	(2.1)
	t∈T c∈C t	s∈S D	t∈T	s∈B	t∈T			t∈T
	t ≤t P t s x t s ≥ P min t s , ∀ t ∈ T, ∀ s ∈ SD : P t s > 0				(2.2)
	t ≤t P t s x t s ≤ P min t s , ∀ t ∈ T, ∀ s ∈ SD : P t s < 0				(2.3)
					u min s	, u max s	, u 0 s , λ s , θ abs s	and θ ref s .

Nomenclature 2

  Reoptimize ccpm with t0 := t and fix engaged contracts y = y 0 Let {q t , x t , g t , h t } be the reoptimized ccpm solution at t = t0 = t

	3
	P min t s
	P max t
	c∈C t	q t ,d c	+	s∈S D	x	t ,d s δ t	P t s	+	s∈S B	(h t ,d

1.0, and their source code is available at https://github.com/levorato/ccp_rtcs. All experiments were performed on a workstation with an Intel Xeon CPU X5355 × 8 with 64 GB RAM, under Ubuntu 18.04 LTS. As defined in Section 2.6.2, each RTCS heuristic can use either Algorithm 1: RTCS algorithm that runs at each time slot d ∈ {1, . . . , δ t }, inside time period I t . Input: CCP model ccpm, initial ccpm solution X(y 0 , 1), gap policy, Reoptimize Result: Set of policies qc(•), xs(•), hs(•), e(•) 1 if Reoptimize is enabled then 2 4 else // Use initial CCP model solution at t0 = 1 5 Let {q t , x t , g t , h t } be the initial ccpm solution at t = t 6 q t ,d c := q t c /δ t , ∀c ∈ C t // Initial contract usage according to y 0 7 x t ,d s := max x t s , s , ∀s ∈ SD // Power drivable according to CCP solution 8 h t ,d s := h t s /δ t ; g t ,d s := g t s /δ t // Use batteries according to CCP solution /* Sum energy consumption/production for all devices (certain and uncertain) */ 9 gap := s∈ S N D P t ,d s + s∈S N D P t s δ t + s -g t ,d s ) if gap > 0 then // energy left over if gap policy = cheapest then Execute dispatch operations (Charge batteries, Sell via contracts, Power drivable consumers) following smallest energy cost first else // conservative gap policy gap := Charge-batteries({s ∈ SB}) gap := Sell-energy-surplus-via-contracts({c ∈ C t : Π - t ,c < 0}) gap := Power drivable consumers({s ∈ SD : P min t s < 0}) e t ,d := 0 Throw remaining energy away else // Negative gap, need for additional energy if gap policy = cheapest then Execute operations (Turn on drivable producer, Use batteries, Consume from contracts, Consume out of contract) according to smallest cost first else // conservative gap policy gap := Turn-on-drivable-producer-devices({s ∈ SD : P min t s > 0}) gap := Consume-energy-via-contracts({c ∈ C t : Π - t ,c > 0}) gap := Discharge-batteries({s ∈ SB}) e t ,d := gap // Consume remaining energy out of contracts if needed the deterministic or the robust CCP model solution as input. We denote by Det-RTCS the RTCS based on the deterministic model, and Rob-RTCS the one based on the robust budgeted model.

Table 2 .

 2

		Deterministic / Φ				Robust budget / Γ
	Instance	0	50	100	0	20	40	60	80	100
	Autumn
	Spring
	Summer
	Winter			33,728.24 0.28 s

3 -Robust vs. Determinisitc model result comparison for different budget parameters. The first value indicates the objective function value obtained, followed by the time spent (in seconds) to obtain the optimal solution. CPLEX default optimality gap of 10 -4 was applied.

Table 2 .

 2 4 -Robust vs. Deterministic RTCS performance comparison for autumn and spring scenario groups. Cost Avg is the average scenario cost over all simulations. Cost Std represents the standard deviation of scenario cost. Cost CVaR is the conditional value at risk of scenario cost at 80% con-

	31,791.0
	67.7
	28.8

fidence level (i.e., the average scenario cost of the 20% highest scenario costs). OC Cost Avg is the average cost from Out of Contract (OC) energy consumption. Penalty Freq is the proportion of time periods with OC consumption. SOC Avg and SOC Std are the average and standard deviation of BESS State Of Charge (SOC).

Table 2 .

 2 5 -Robust vs. Determinisitc RTCS performance comparison for summer and winter scenario groups. Cost Avg is the average scenario cost over all simulations. Cost Std represents the standard deviation of scenario cost. Cost CVaR is the conditional value at risk of scenario cost at 80% con-The robust CCP model under budgeted uncertainty was tested with six Γ budget parameter values (0%, 20%, 40%, 60%, 80% and 100%). They indicate the proportion of the maximum allowed deviation of uncertain parameters regarding production or consumption of energy, as defined in Section 2.5.2. As a baseline for comparison, the deterministic CCP model was tested with 3 different sets of values regarding uncertain devices. When Φ = 0%, the model is based on the most optimistic scenario, assuming minimal consumption and maximal production for uncertain consumer and producer devices, respectively. The exact opposite situation is represented by Φ = 100%, apparently the most pessimistic one. Finally, the scenario where Φ = 50% depicts the middle interval, with average values of uncertain devices. A general comparison will be conducted to determine which model behaves best under uncertainty, remembering that the Γ and Φ values used by the deterministic and robust models have different meanings.For summer, the naïve policy is not able to offer improved results when coupled with the robust CCP model. On the other hand, the robust solutions with Γ ∈ {40%, 80%, 100%} provide the best protection for all look-ahead RTCS policies, when compared to their deterministic counterparts. In particular, the robust solution for Γ = 40% coupled with Cheapest+ReRopt RTCS presents the best observed economic and reliability values (Cost Avg = 31,405.1 and Cost CVaR = 35,856.7), as well as low levels of OC Cost and zero penalty frequency. It is worth noting that, besides having elevated PV electricity production, energy consumption reaches its highest levels during this season, according to the dataset.Last, in winter season, it is possible to observe an interesting case where the maximum hedge

	Part , Nomenclature

fidence level (i.e., the average scenario cost of the 20% highest scenario costs). OC Cost Avg is the average cost from Out of Contract (OC) energy consumption. Penalty Freq is the proportion of time periods with OC consumption. SOC Avg and SOC Std are the average and standard deviation of BESS State Of Charge (SOC).

The solution statistics for each model are presented in Table

2

.3. The obtained results show that, when solving the first-stage problem to determine the list of contracts to engage, optimal solutions for robust models with different budget parameter values can be obtained in less than an hour with an 8-core CPU.

Regarding the simulation results, according to the season of the year, for each of the 4 RTCS policies proposed in the previous section, Tables 2.4 and 2.5 present statistical measures based on the operational cost (Cost Avg, Cost Std, Cost CVaR), as well as Out of Contract (OC) energy consumption cost (OC Cost Avg), penalty frequency (i.e., the proportion of time periods where OC consumption occurred) and the State of Charge (SOC) of the microgrid's BESS (SOC Avg and SOC Std). In robust and deterministic CCP models, higher values of Γ or Φ parameters, respectively, ensure improved system reliability through elevated protection against the realization of worst-case scenarios, but at the expense of increased overall cost. The above measures allow a trade-off analysis between operational cost and system reliability, which can be applied by the decision-maker to select the most appropriate model.

For the autumn season, except for the naïve RTCS policy, remark that Rob-RTCS solution with Γ = 40% significantly improves not only the operational cost (Cost Avg and Cost Std), but also microgrid's reliability (Cost CVaR metric), when compared to Det-RTCS solutions. In particular, when considering the best economic performance of Det-RTCS (Cheapest+ReOpt policy with Φ = 50%), Rob-RTCS with Γ = 40% achieves a reduction of 0.1% in Cost Avg, 22.7% in Cost Std and 3.5% in Cost CVaR.

In spring season instance, the look-ahead Rob-RTCS policies with Γ = 40% and Γ = 80% outperform the deterministic counterparts in average cost and CVaR cost metrics. When compared to the previous set of scenarios, Rob-RTCS performance is further improved, with Γ = 40% and Γ = 80% budget-based RTCS achieving the best economic performance (Cost Avg), with zero OC cost and thus zero penalty frequency. In this case, when compared to the Det-RTCS models whose policy has the lowest average cost (Cheapest+ReOpt), the Rob-RTCS with Γ = 40% is 17.6% cheaper on average, with a 3.6% decrease in Cost CVaR.

(Rob-RTCS with Γ = 100%) represents the best option from the viewpoint of worst-case protection as well as economic performance. The best results were obtained with model re-optimization enabled (either Cheapest+ReRopt or Conservative+ReRopt RTCS). The robust model with Γ = 100% presents the lowest Cost CVaR values among all models tested. It also provides the cheapest average costs (Cost Avg), considering all robust and deterministic models simulated. Once again, the robust-based naïve policy is not able to offer improved results when compared to Det-RTCS.

  Part , Chapter 3 -The Robust Permutation Flow Shop Problem (makespan objective)

Table 3 .

 3 2 -Wagner vs. Wilson Robust PFSP C&CG performance comparison, given all instances. % Best Performance is the percentage of instances solved to optimality where the model achieved shorter execution time; % Solved contains the percentage of instances solved to optimality within the time limit; % Solved < n > represents the percentage of solved instances of size n; Avg. % gap is the average percentage gap of solutions from instances not solved to optimality; Median time is the median execution time, in seconds; Median iterations is the median of the number of iterations performed.

	n / Model

Table 3 .

 3

3 -Wagner vs. Wilson Robust PFSP C&CG performance comparison, for each instance size n. % Best Performance is the percentage of instances solved to optimality where the model achieved shorter execution time; % Solved contains the percentage of instances solved to optimality within the time limit; Avg. % gap is the average percentage gap of solutions from instances not solved to optimality; Avg. time opt. and Std. dev. of time opt. are the mean and standard deviation in solution time, respectively, regarding instances solved to optimality; Avg. iterations and Std. dev. of iterations are the mean and standard deviation of the number of iterations performed.

Table 3 .

 3 5 -Relative robustness price η(Γ)% and hedge value H(Γ)% for instance #8, n = 150, for different degrees of uncertainty α ∈ {10%, 20%, 30%, 40%, 50%}. Best values are highlighted.

Table 3 .

 3

	6 -Simulation results for instance #8, n = 150, for different degrees of uncertainty α ∈
	{10%, 20%, 30%, 40%, 50%}. Comparison is based on two measures: (i) ω(Γ) is the % of simulated
	scenarios (over a total of 10,000) where 2RPFS(Γ) obtained smaller makespan cost when compared
	to Det(P=); (ii) ∆Φ(Γ) = Avg λ∈S	ϕ(σ * Γ ,P λ )-ϕ(σ * ,P λ ) ϕ(σ

* ,P λ )

  5, but this time with new Robust Counterparts and a new worst-case procedure for the m-machine robust problem. Using the RC formulations defined in Section 3.7.3, we derive two solution approaches, in which the Master Problem (MP) is based on either the Wilson or Wagner formulations.

Table 3 .

 3 8 -GRASP parameter values evaluated during calibration. The best performing parameter values are underlined.each RC model by varying Γ according to ten ratios(10, 20, 30, 40, 50, 60, 70, 80, 90 and 100%) of operations with uncertain processing times.

	Parameter name Tested values
	random-VND	false, true
	vnd-size	1, 2, 3
	first-improvement	false, true
	time-factor	30, 300
	β 1	0.2, 0.4, 0.6, 0.8, 1.0
	β 2	0.2, 0.4, 0.6, 0.8, 1.0

Table 3 .

 3 [START_REF] Ben-Tal | Adjustable robust solutions of uncertain linear programs[END_REF] -Percentage of instances solved to optimality by C&CG and GRASP solution methods, grouped by instance type and instance size.

  C&CG) is explained in Section 4.4. An important enhancement to the solution method, which uses a combinatorial branch-and-bound in the master phase of the C&CG method, is discussed in Section 4.5. The experimental results are shown in Section 4.6, based on extensive computational experiments on three sets of randomly-generated problem instances. Section 4.7 brings a case study applied to the oil and gas industry, using real data from the operation history of two Brazilian oil platforms. Finally, Section 4.8 brings the final discussions.

	4.2. The deterministic PFSP minimizing total weighted completion time
	constraint method designed for the RPFS with makespan objective and presented in the previous
	chapter.
	This chapter adopts the following structure. Section 4.2 introduces the classical deterministic
	Permutation Flow Shop Problem, minimizing total weighted completion time. The m-machine Ro-
	bust Permutation Flow Shop Problem is presented in Section 4.3, together with seven proposed Ro-
	bust Counterpart (RC) formulations. Our exact solution approach based on Column-and-Constraint
	Generation (

  The objective function(4.18) and constraints (4.5), (4.12) and (4.13) are as defined in the previous formulation. Constraints(4.19)-(4.20) guarantee that the robust schedule is feasible and that idle time variables are appropriately calculated, for each scenario λ. Constraints (4.21) are big-M constraints used to determine the completion time of job i on the last machine m, for each scenario λ. For an illustrative diagram, we refer the reader to Figure2in[136, p. 1376]. Finally, constraints (4.14), (4.16), (4.17) and (4.22) define the domain of the variables.

		, n, j = 1, . . . , n, λ ∈ Λ,	(4.21)
	X λ r,j ≥ 0,	r = 1, . . . , m, j = 1, . . . , n, λ ∈ Λ.	(4.22)

  Part , Chapter 4 -Robust scheduling in Oil and Gas exploration be formulated as:

	Min y			(4.32)
	st (4.5), (4.12), (4.13), (4.14), (4.16), (4.17),
	E λ r,j+1 ≥ E λ r,j +	n i=1 p r,i + pr,iδ λ r,i Zi,j+1, r = 2 . . . , m, j = 1, . . . , n -1,
			λ ∈ Λ,	(4.33)
	E λ r+1,j ≥ E λ r,j +	n i=1 p r+1,i + pr+1,iδ λ r+1,i Zi,j,	r = 1 . . . , m -1,
			j = 2, . . . , n, λ ∈ Λ,	(4.34)

  The objective function(4.32) and constraints (4.5), (4.12) and (4.13) are as defined in the first formulation. Constraints (4.33)-(4.37) guarantee that the robust schedule is feasible and that completion time variables are appropriately calculated, for each scenario λ. Constraints (4.38) are big-M constraints used to determine the completion time of job i on the last machine m, for each scenario λ.

		1, . . . , n, j = 1, . . . , n, λ ∈ Λ,	(4.38)
	E λ r,j ≥ 0,	r = 1, . . . , m, j = 1, . . . , n, λ ∈ Λ.	(4.39)
	Finally, constraints (4.14), (4.16), (4.17) and (4.39) define the domain of the variables.

  The objective function(4.40) and constraints (4.5), (4.12) and (4.13) are as defined in the first formulation. Constraints (4.41)-(4.42) guarantee that the robust schedule is feasible and that idle time variables are appropriately calculated, for each scenario λ. Constraints (4.43) are big-M constraints used to determine the completion time of job i on the last machine m, for each scenario λ. Finally, constraints (4.14), (4.16), (4.17) and (4.31) define the domain of the variables.

	Min y					(4.40)
	st (4.5), (4.12), (4.13), (4.14), (4.16), (4.17), (4.31),
	Y λ r,1 = 0,				r = 1, . . . , m -1, λ ∈ Λ,	(4.41)
		n i=1 p 1,i + p1,iδ λ 1,i -p r,i -pr,iδ λ r,i Zi,j-1
	+	r-1 q=1	n i=1 p q,i + pq,iδ λ q,i	Zi,j -Zi,j-1
	+	r-1 q=1 Yq,j -Yq,j-1 ≥ 0,		r = 2, . . . , m, j = 2, . . . , n, λ ∈ Λ,	(4.42)
	F λ i ≥	j q=1	n i=1 p 1,i + p1,iδ λ 1,i Zi,q +	m r=2	n i=1 p r,i + pr,iδ λ r,i Zi,j
			+	m-1 r=1 Yr,j -Q(1 -Zi,j),	i = 1, . . . , n, j = 1, . . . , n, λ ∈ Λ.	(4.43)

  In this two-stage RO formulation, D i,k are the first-stage variables, while C λ r,i are second stage ones. The robust counterpart for Manne PFS model can be formulated as follows.

		Min y			(4.44)
		st	n i=1 wiC λ m,i ≤ y,	λ ∈ Λ,	(4.45)
		C λ 1,i ≥ p 1,i + p1,iδ λ 1,i ,	i = 1, . . . , n, λ ∈ Λ,	(4.46)
		C λ r,i -C λ r-1,i ≥ p r,i + pr,iδ λ r,i ,	r = 2, . . . , m, i = 1, . . . , n, λ ∈ Λ,	(4.47)
		if job i is scheduled any time before job k
		0, otherwise.
	C λ r,i	completion time of job i on machine r given scenario λ.

  The objective function(4.44) and constraints (4.45) represent the worst-case total weighted completion time objective, i.e., the minimization of the maximum sum of the weighted completion time of

			.49)
	C λ r,i ≥ 0,	r = 1, . . . , m; i = 1, . . . , n, λ ∈ Λ,	(4.50)
	D i,k ∈ {0, 1},	i = 1, . . . , n -1, k = i + 1, . . . , n,	(4.51)
	y ≥ 0.		(4.52)

all jobs on the last machine, given all scenarios λ ∈ Λ. Constraints (4.46) insure that the completion time of each job on machine 1 occurs no earlier than the duration of that job's processing time on machine 1. Constraints (4.47) insure that each job's completion time on machine r is no earlier than the job's completion time on machine r -1 plus the job's processing time on machine r (with or without deviation). Constraints (4.48) and (4.49) are the paired disjunctive constraints, which insure that job i either precedes job k or follows job k in the sequence, but not both. Finally, constraints (4.50)-(4.52) define the domain of the variables.

  The robust counterpart for Liao-You PFS model can be formulated as follows.

	Min y		(4.53)
	st (4.51), (4.52),
	n i=1 wi(S λ m,i + p m,i + pm,iδ λ m,i ) ≤ y,	λ ∈ Λ,	(4.54)
	S λ r,i + p r,i + pr,iδ λ r,i ≤ S λ r+1,i ,	r = 1, . . . , m -1, i = 1, . . . , n, λ ∈ Λ,	(4.55)

Table 4 .

 4 .[START_REF] Hussain | Optimal operation of tri-generation microgrids considering demand uncertainties[END_REF] The objective function(4.53) and constraints (4.54) represent the worst-case total weighted completion time objective, i.e., the minimization of the maximum sum of the weighted completion time of all jobs on the last machine, given all scenarios λ ∈ Λ. Constraints (4.55) insure that each job's start time on machine r + 1 is no earlier than the job's start time on machine r plus the job's processing 1 -Size complexity of the RPFS-TWCT robust-counterpart MILP models.

	RC Model Binary variables Continuous variables Constraints
	Wilson
	TBA
	WST2	O(n 2 )	O(λmn)	O(λ(n 2 + mn))
	TS2
	TS3
	Manne	O(n 2 )	O(λmn)	O(λmn 2 )
	Liao-You O(n 2 )	O(λmn 2 )	O(λmn 2 )

time on machine r (with or without deviation). Constraints (4.56) and (4.57) are the paired disjunctive constraints, which insure that job i either precedes job k or follows job k in the sequence, but not both. Finally, constraints (4.51), (4.52), (4.58) and (4.59) define the domain of the variables.

Table 4 .

 4 1 presents the size complexity of each robust counterpart MILP model presented in this section. The number of binary variables remains the same of the original deterministic models, as they consist of first-stage variables. Also observe that the number of continuous variables as well as the number of constraints grow proportionally to the number of scenarios λ, as expected in robust counterpart formulations. Finally, the number of constraints in the assignment-based models (first five models in Table4.1) is now quadratic in n, due to the calculation of the weighted completion time of each job, which requires the use of n 2 big-M constraints.

  formulation from Section 4.3.3. Following the structure of the C&CG method, we define the Master Problem (MP) by choosing an appropriate 2-stage RO formulation. Considering Θ = {λ 1 , . . . , λ v } ⊆ Λ a subset of scenarios, let F model and R model be the set of corresponding first-stage and recourse decision variables of the model, respectively. For instance, F W ilson = {Z i,j , ∀i, j = 1, . . . , n} and

3 Comparative performance of the Robust Counterpart models

  Part , Chapter 4 -Robust scheduling in Oil and Gas exploration optimality gap tolerance was set to 10 -8 .In the literature[START_REF] Tseng | New MILP models for the permutation flowshop problem[END_REF], empirical tests have shown that the top 3 best performing PFSP MILP models are, in this order: TS3, TBA and Wilson. In this work, we will observe that the performance obtained with the PFSP robust counterparts is rather different to the existing performance of deter-GeneralModelStatsNoHybridSum of Value broken down by Variable vs. Model. The view is filtered on Model and Variable. The Model filter has multiple members selected. The Variable filter has multiple members selected.

	ministic PFSP MILP models.
	4.6.Model	% Best Per formance	% Solved 10x2	% Solved 10x3	% Solved 10x4	Variable % Solved 10x5	% Solved Avg. % gap	Median iterations Median time
	Manne	45.70	99.56	96.56	91.67	90.89	94.67	0.07	5.00	88.10
	Liao-You	34.38	99.44	96.44	91.89	90.11	94.47	0.08	5.00	85.32
	Wilson	13.78	99.33	95.00	83.56	80.89	88.38	2.33	5.00	276.03
	TS2	6.03	99.89	95.67	85.22	85.67	90.78	3.08	4.00	436.48
	TS3	4.95	99.56	92.67	78.11	86.78	89.28	1.65	5.00	334.56
	TBA	0.51	99.33	87.78	71.44	69.67	82.06	1.76	5.00	883.80
	WST2	0.14	98.00	86.78	69.67	66.44	80.22	2.09	5.00	1,143.74
						6.0. CPLEX solver 20.1 was used to solve the Master
	Problems (MP) and Gurobi solver 9.1 was used to solve the subproblems SP, since it obtained
	improved performance in preliminary experiments. The MILP time limit was set to 7,200 s and the
	number of threads was set to 16. All experiments were conducted on a workstation with an Intel
	Xeon ® CPU E5640 @2.67GHz with 32 GB RAM, under Ubuntu 18.04 LTS. In the C&CG algorithm,

Table 4 .

 4 2 -Robust PFSP C&CG performance comparison

Table 4 .

 4 3 -Robust PFSP C&CG performance comparison, for each instance size n×m and RC model. % Best Performance is the percentage of instances where the model achieved shorter execution time (ties included); % Solved contains the percentage of instances solved within the time limit; Avg. % Gap and Std. dev. of % Gap are the mean and standard deviation of the percentage gap of solutions from instances not solved to optimality; Avg. iterations and Std. dev. of iterations are the mean and standard deviation of the number of iterations performed; Avg. time MP(SP) is the average time to solve the Master(Sub) Problem; Avg. time and Std. dev. of time are the mean and standard deviation in solution time (in seconds), respectively. Part , Chapter 4 -Robust scheduling in Oil and Gas exploration StatsPerAlphaNoHybrid ZN(LOOKUP(AVG([Value]), 0)) broken down by Alpha vs. Instance size, Model and Variable. The view is filtered on Alpha, Instance size, Variable and Model. The Alpha filter keeps 9 members. The Instance size filter keeps 10x5. The Variable filter keeps 9 members. The Model filter keeps Liao-You, Manne, TS2 and Wilson.

								Alpha
	Instance .. Model	Variable	α=10%	α=20%	α=30%	α=40%	α=50%	αᵐᵃˣ=30%	αᵐᵃˣ=50% αᵐᵃˣ=100% αᵐᵃˣ=200%
	10x5	Manne	% Best Performance	55.10	75.00	82.14	75.00	38.89	60.61	80.21	65.98	67.01
			% Solved	98.00	96.00	85.00	73.00	73.00	99.00	96.00	100.00	98.00
			Avg. % gap	0.00	0.00	0.00	0.03	0.06	0.00	0.00	0.00	0.57
			Std. dev. of % gap	0.00	0.00	0.00	0.11	0.20	0.00	0.00	0.00	0.08
			Avg. iterations	10.02	20.02	57.25	95.02	82.81	6.71	24.29	8.82	12.36
			Avg. MP time	198.80	343.21	1,151.25	1,996.76	1,997.19	150.97	425.11	365.75	636.58
			Avg. SP time	13.34	103.91	215.03	457.65	575.86	13.88	81.86	89.68	214.94
			Avg. time	212.14	447.12	1,366.27	2,454.41	2,573.06	164.85	506.97	455.43	851.52
			Std. dev. of time	1,007.64	1,401.65	2,531.63	3,052.05	2,960.42	719.07	1,419.05	861.10	1,350.03
		Liao-You % Best Performance	40.82	22.92	17.86	23.61	58.33	25.25	16.67	27.84	32.99
			% Solved	98.00	96.00	84.00	72.00	72.00	99.00	96.00	97.00	97.00
			Avg. % gap	0.00	0.00	0.00	0.06	0.10	0.00	0.00	0.10	0.85
			Std. dev. of % gap	0.00	0.00	0.01	0.19	0.27	0.00	0.00	0.12	0.66
			Avg. iterations	10.47	17.30	49.77	86.26	80.75	5.20	23.08	8.77	12.19
			Avg. MP time	230.66	395.28	1,314.84	2,080.92	2,109.72	178.98	470.81	466.47	696.90
			Avg. SP time	19.05	120.31	270.29	537.54	640.74	13.57	98.86	110.64	253.15
			Avg. time	249.71	515.59	1,585.13	2,618.46	2,750.46	192.55	569.67	577.11	950.05
			Std. dev. of time	1,021.04	1,419.79	2,593.14	3,060.68	3,027.40	723.47	1,426.31	1,258.07	1,532.42
		TS2	% Best Performance	0.00	2.06	0.00	0.00	0.00	3.03	1.10	2.33	0.00
			% Solved	100.00	97.00	83.00	75.00	70.00	99.00	91.00	86.00	70.00
			Avg. % gap	0.00	0.00	0.22	0.55	0.89	0.00	0.19	1.63	2.46
			Std. dev. of % gap	0.00	0.00	0.33	0.63	1.14	0.00	0.29	1.41	2.50
			Avg. iterations	3.76	5.99	8.20	11.61	11.20	4.76	10.37	7.47	8.94
			Avg. MP time	1,017.22	1,584.34	2,063.25	2,798.91	3,133.31	669.08	1,549.04	1,800.18	3,125.41
			Avg. SP time	197.62	354.42	496.12	465.72	542.74	15.98	73.83	126.85	249.46
			Avg. time	1,214.85	1,938.76	2,559.38	3,264.63	3,676.05	685.06	1,622.87	1,927.04	3,374.87
			Std. dev. of time	1,404.58	2,030.54	2,545.68	2,696.03	2,697.30	1,182.24	2,337.84	2,468.36	3,084.71
		Wilson	% Best Performance	3.09	1.25	1.32	5.71	5.88	9.09	6.59	4.71	0.00
			% Solved	97.00	80.00	76.00	70.00	68.00	99.00	91.00	85.00	62.00
			Avg. % gap	0.07	0.34	0.68	0.79	1.17	0.00	0.23	1.93	2.18
			Std. dev. of % gap	0.12	0.34	0.55	0.76	1.10	0.00	0.37	1.77	2.46
			Avg. iterations	3.90	7.98	8.42	9.12	13.13	4.70	8.53	7.26	11.00
			Avg. MP time	1,165.72	2,266.70	2,619.72	3,019.32	3,257.35	747.88	1,508.29	1,941.32	3,315.41
			Avg. SP time	133.02	203.90	321.46	349.65	352.45	22.32	68.82	132.49	289.86
			Avg. time	1,298.74	2,470.60	2,941.17	3,368.97	3,609.79	770.20	1,577.11	2,073.81	3,605.27
			Std. dev. of time	1,944.91	2,777.29	2,764.50	2,903.50	2,836.88	1,265.93	2,319.08	2,529.15	3,098.39

Table 4 .

 4 4 -Robust PFSP C&CG performance comparison for instance size 10 × 5, grouped by α and α max values, and RC model. % Best Performance is the percentage of instances where the model achieved shorter execution time (ties included); % Solved contains the percentage of instances solved within the time limit; Avg. % Gap is the average percentage gap of solutions from instances not solved to optimality; Avg. iterations is the average number of iterations performed; Avg. time MP(SP) is the average time to solve the Master(Sub) Problem; Avg. time and Std. dev. of time are the mean and standard deviation in solution time (in seconds), respectively. Table4.5 -Robust PFSP C&CG performance comparison, for instance size 15×5, RC models Manne, Liao-You, Wilson and TS2, along with Hybrid C&CG models Manne-Hybrid, Liao-You-Hybrid, and Wilson-Hybrid. % Best Performance is the percentage of instances where the model achieved shorter execution time (ties included); % Solved contains the percentage of instances solved within the time limit of 14400s; Avg. % Gap and Std. dev. of % Gap are the mean and standard deviation of the percentage gap of solutions from instances not solved to optimality; Avg. iterations and Std. dev. of iterations are the mean and standard deviation of the number of iterations performed; Avg. time MP(SP) is the average time to solve the Master(Sub) Problem; Avg. time and Std. dev. of time are the mean and standard deviation in solution time (in seconds), respectively.

Table 4 .

 4

7 -Relative robustness price η(Γ)% and hedge value H(Γ)% for instances 9 × 4 and 15 × 5.

Table 4.7 displays the relative price of robustness η(Γ)% = ϕ(σ * Γ ,P )-ϕ(σ * ,P ) ϕ(σ * ,P )

Table 4 .

 4 8 -Simulation results for instance 9 × 4, for different protection levels Γ ∈ {5%, 15%, . . . , 100%}. Comparison is based on two measures: (i) ω(Γ) is the % of simulated scenarios (over a total of 10,000) where RPFS(Γ) obtained smaller TWCT cost when compared to Det(P=);

	(ii) ∆η(Γ) = Avg λ∈S	ϕ(σ

* Γ ,P λ )-ϕ(σ * ,P λ ) ϕ(σ * ,P λ )

  with the corresponding cost function:j∈N i âij x j + (Γ i -Γ i âi,t i x t i ).Let ω i and π ij (∀j ∈ N i ) be the dual variables corresponding to constraints (B.10) and (B.11), respectively. The dual problem [DLP-Beta(i)] is obtained as follows:[DLP-Beta(i)] Minimize j∈N i π ij + Γ i ω i (B.12) subject to ω i + π ij ≥ âij x j , ∀j ∈ N i (B.13)Since LP-Beta(i) is feasible and bounded forΓ i ∈ [0, | N i |], by strong duality, DLP-Beta(i) is also feasible and bounded, and both models have the same objective function value. The protection function β(x, Γ i ) is therefore equal to the objective function value of DLP-Beta(i).

	π ij ≥ 0, ∀j ∈ N i	(B.14)
	ω i ≥ 0	(B.15)

Finally, by substituting DLP-Beta(i) (in place of β(x, Γ i )) into Budget-RO, the following LP model is obtained:

(LP-Budget-RO) Maximize j c j x j (B.16) subject to j a ij x j + Γ i ω i + j∈N i π ij ≤ b i , ∀i (B.17

)

ω i + π ij ≥ âij x j , ∀i, ∀j ∈ N i (B.18) π ij ≥ 0, ∀i, ∀j ∈ N i (B.

[START_REF] Bougeret | Robust scheduling with budgeted uncertainty[END_REF]

)

ω i ≥ 0, ∀i (B.20)

x j ≥ 0, ∀j (B.21)

Part , Chapter 2 -The Robust Contract Collaboration Problem (RCCP)

It is worth noting, however, that the amount of electricity bought or sold via each engaged contract may be more than the initial values proposed by the model policy, depending on the actual energy demand.

All test instances are available at https://github.com/levorato/RPFS_Cmax_Budget.

Taillard instances are grouped in 12 sets of 10 instances each, according to the number of jobs and the number of machines (i.e., Set 20 x 5, set 20 x 10, set 20 x 20, set 50 x 5, set 50 x 10, set 50 x 20, set 100 x 5, set 100 x 10, set 100 x 20, set 200 x 10, set 200 x 20, and set 500 x 20).

z * i,j = 1, if σ * (j) = i (job i occupies position j in the sequence σ * ) 0, otherwise..

All test instances are available at https://github.com/levorato/RPFS_Budget_TWCT.

[START_REF] Ben | Robust solutions of linear programming problems contaminated with uncertain data[END_REF] 20 25 30 35 40 45 50 55 60 70 80 90 100

A solution is called Pareto Robustly Optimal (PRO) if there is no other robustly feasible solution that has better objective value for at least one scenario, and for all other scenarios in the uncertainty set the objective value is not worse[START_REF] Iancu | Pareto efficiency in robust optimization[END_REF].

52,028 52,340 51,647 52,340 51,548 54,375 54,221 51,774 52,254 6,619 6,606 6,820 6,606 6,941 6,749 6,772 6,841 6,725 63,528 63,812 63,712 63,812 63,939 66,126 65,959 63,751 63,972 66,839 67,319 67,344 67,319 67,843 69,442 69,447 67,677 67,532 79,857 82,729 83,287 82,729 82,151 83,973 82,780 84,934 86,193 65,110 65,854 64,481 65,854 64,435 68,049 67,890 65,121 65,599 6,739 6,687 7,176 6,687 7,392 6,893 6,946 7,027 6,865 76,531 77,215 76,973 77,215 77,362 79,567 79,620 77,399 77,372 79,360 80,181 80,060 80,181 80,801 82,532 82,649 80,683 80,383 90,901 94,283 93,286 94,283 93,362 96,123 96,399 96,200 97,623 68,566 69,399 67,838 69,399 67,730 71,538 71,426 68,739 69,143 9,153 9,066 9,706 9,066 9,878 9,331 9,414 9,432 9,280 83,425 84,246 83,831 84,246 84,266 86,717 86,839 84,490 84,393 86,487 87,533 87,398 87,533 88,013 90,096 90,223 88,086 87,699 98,076 100,090 100,462 100,090 102,587 102,107 102,600 101,782 102,039 MIN-MAX-V Max Min Neither

Rob-PFSP experimental results

Me a s u r e A l p h a α = 1 0 % α = 2 0 % α = 3 0 % α = 4 0 % α = 5 0 % α ᵐ ᵃ ˣ = 3 0 % α ᵐ ᵃ ˣ = 5 % α ᵐ ᵃ ˣ = 1 0 0 % α ᵐ ᵃ ˣ = 2 0 0 % Table 3.10 -Robust PFSP C&CG performance comparison for Ying instance size 15 × 5, grouped by α and α max values, and RC model. % Best Performance is the percentage of instances where the model achieved shorter execution time (ties included); % Solved contains the percentage of instances solved within the time limit; Avg. % Gap is the average percentage gap of solutions from instances not solved to optimality; Avg. iterations is the average number of iterations performed; Avg. time MP(SP) is the average time to solve the Master(Sub) Problem; Avg. time and Std. dev. of time are the mean and standard deviation in solution time (in seconds), respectively.

Part , Nomenclature used in the models

Me a s u r e

A l p h a

Wa g n e r

I n s t a n c e T y p e I n s t a n c e S i z e

A l p h a We also ran the GRASP method to obtain solutions for the remaining Taillard-based instances proposed in Section 3.10.1. Even though we were unable to evaluate their solution quality (due to problem-size limitations of the baseline C&CG method), we published the best solution found for each instance and Γ% value, along with the instance file set at https://github.com/levorato/ RPFS_Cmax_Budget.

Chapter 4

ROBUST SCHEDULING IN OIL AND GAS EXPLORATION

In this chapter, we propose exact solution approaches for the m-machine robust permutation flow shop problem, with the objective of minimizing worst-case total weighted completion time. In the context of the oil and gas industry, this variant of the flow shop is associated with the maintenance schedule for oil rigs.

Traditional problem formulations assume that the processing time of each operation does not vary (i.e. the most likely scenario will certainly occur). However, in oil and gas applications like platform maintenance, task duration does fluctuate according to a specific range. Rather than assigning probabilities to different scenarios in order to generate a decision which is optimal in the long run (as in Stochastic Optimization approaches), our goal is to apply Robust Optimization [START_REF] Ben | Robust optimization-methodology and applications[END_REF] techniques, by considering a set of potentially realizable scenarios and a min-max criteria that returns a solution with the best worst-case performance over the scenario set.

Similarly to the problem studied in the previous chapter, operation processing times are uncertain and vary in a given interval. Moreover, following the concept of budgeted uncertainty, only a subset of operation processing times will deviate to worst-case values. To solve this robust problem, we developed seven robust counterpart formulations, which can be used to derive optimal solutions for medium-sized problem instances by using a Column-and-Constraint Generation algorithm.

The efficacy of the solution methods is validated through experiments on three sets of randomlygenerated instances. And finally, a case study for maintenance schedule of Brazilian oil platforms is presented.

Introduction

In the context of the Oil and Gas industry, maintenance scheduling plays a very important role [START_REF] Mattos Ribeiro | A simple and robust Simulated Annealing algorithm for scheduling workover rigs on onshore oil fields[END_REF][START_REF] Zarei | Optimal well work-over scheduling: application of intelligent well control optimisation technology to conventional wells[END_REF][START_REF] Pérez | Optimizing Workover Rig Fleet Sizing and Scheduling Using Deterministic and Stochastic Programming Models[END_REF]. One major challenge is related to programmed shutdown and maintenance of oil platforms. Due to existing policies in such schedules, a well-defined set of operations must have their order of execution respected. These tasks must be performed on all equipment associated with a specific oil well. For example, they include substituting previously-installed provisional

Part , Chapter 4 -Robust scheduling in Oil and Gas exploration time, denoted by C r,σ(j) , can be defined by the recurrence:

The completion time of a job i is defined as its completion time on the last machine C m,i . The objective is to find a job sequence that minimizes the total weighed completion times on the final machine, i.e., a permutation σ minimizing ϕ(σ) = j∈{1,...n} w σ(j) C m,σ(j) .

The problem was proved strongly NP-hard by [START_REF] Michael R Garey | The complexity of flowshop and jobshop scheduling[END_REF] for instances with two or more machines, when all job weights are equal. It was also studied from the viewpoint of probabilistic analysis [START_REF] Kaminsky | Probabilistic analysis and practical algorithms for the flow shop weighted completion time problem[END_REF],

stability approach [START_REF] Yu | Minimizing total weighted flow time under uncertainty using dominance and a stability box[END_REF], heuristics [START_REF] Ludo | Four simple heuristics for scheduling a flow-shop[END_REF][START_REF] Miyazaki | Analysis for minimizing weighted mean flow-time in flow-shop scheduling[END_REF][START_REF] Rajendran | An efficient heuristic for scheduling in a flowshop to minimize total weighted flowtime of jobs[END_REF][START_REF] Wang | Several flow shop scheduling problems with truncated position-based learning effect[END_REF], combinatorial branch-and-bound [START_REF] Chung | A branch and bound algorithm to minimize the total flow time for m-machine permutation flowshop problems[END_REF], MIPbased branch-and-bound [START_REF] Hui | Minimizing total weighted completion time in a two-machine flow shop scheduling under simple linear deterioration[END_REF][START_REF] Vo | From maxplus algebra to general lower bounds for the total weighted completion time in flowshop scheduling problems[END_REF] and approximation algorithms [START_REF] Nagarajan | Tight bounds for permutation flow shop scheduling[END_REF]. Finally, the problem can be solved with MILP techniques, by adapting the objective function of existing flowshop formulations [START_REF] Tseng | An empirical analysis of integer programming formulations for the permutation flowshop[END_REF][START_REF] Tseng | New MILP models for the permutation flowshop problem[END_REF].

The robust PFSP to minimize the total weighted completion time

Different optimization criteria can be used to search for a robust solution. This study focuses on the minimax or absolute robust criterion: the robust decision looks for a solution that minimizes the highest objective value over all possible scenarios, following a predefined uncertainty set.

This section starts with a definition of the Robust Permutation Flow Shop -Total Weighted Completion Time (RPFS-TWCT) problem (Section 4.3.1), followed by a description of the underlying budgeted uncertainty set (Section 4.3.2). Then, seven robust counterpart formulations are proposed (Section 4.3.3), based on well-known Mixed-Integer Linear Programming (MILP) formulations for the deterministic problem.

Problem statement

Assume the matrix of individual processing times P = {p r,i , r ∈ M, i ∈ J} contains uncertain data. A scenario λ is defined as a realization of uncertainty and, for each possible λ, there is a unique matrix of processing times denoted as P λ = {p λ r,i , r ∈ M, i ∈ J}. Let Λ be the set of all possible scenarios λ. Whenever a matrix of processing times P λ is known, an instance of the deterministic PFSP-TWCT is defined.

Let's redefine ϕ(σ, P λ ) as the total weighted completion time of a sequence σ ∈ Σ given a scenario λ ∈ Λ. The objective of the RPFS-TWCT is to find a job permutation σ ∈ Σ that minimizes Part , Chapter 4 -Robust scheduling in Oil and Gas exploration this set. For a given scenario λ, let δ λ r,i be the value defining the deviation of the processing time regarding the execution of job i ∈ J on machine r ∈ M, i.e., p λ r,i = p r,i +δ λ r,i p λ r,i . Therefore, considering all jobs and machines, the total number of operations whose processing time can deviate to its maximum value is limited to Γ. When Γ = 0, the problem is equivalent to the nominal problem, i.e., the deterministic PFSP-TWCT. If Γ = mn, we obtain the box uncertainty set [START_REF] Allen | Convex programming with set-inclusive constraints and applications to inexact linear programming[END_REF]. For a given value of Γ, there are mn Γ possible worst-case scenarios, given the budgeted uncertainty set U Γ .

Robust counterparts

A number of MILP models were proposed in the literature for the PFSP. We now present the robust counterparts for the PFSP-TWCT, based on the following seven formulations: Wilson [START_REF] Jm Wilson | Alternative formulations of a flow-shop scheduling problem[END_REF];

TBA [START_REF] Turner | A new integer programming model for the N job M machine flow shop problem[END_REF]; Wagner-WST2; TS2 and TS3 [START_REF] Tseng | New MILP models for the permutation flowshop problem[END_REF]; Manne [START_REF] Stafford | On the Srikar-Ghosh MILP model for the N x M SDST flowshop problem[END_REF] and Liao-You [START_REF] Liao | An improved formulation for the job-shop scheduling problem[END_REF]. In their original definition, the first five models rely on assignment constraints in order to find the position occupied by each job in the schedule, while the last two apply disjunctive inequalities with Big-M reformulation to determine if a job appears either before or after another job in the sequence. For more details on the rationale behind each deterministic PFSP model, including illustrative diagrams, we refer the reader to [START_REF] Tseng | New MILP models for the permutation flowshop problem[END_REF].

It is worth noting that the first five models were further adapted for the TWCT objective. Such adaptation involved additional constraints based on the Big-M method to appropriately calculate the variables which represent the completion time of each job i on the last machine. These variables, which are not present in the original models, had to be defined for the correct calculation of total weighted completion time.

Robust Counterpart for Wilson PFS Model

Wilson [START_REF] Jm Wilson | Alternative formulations of a flow-shop scheduling problem[END_REF] proposed a MILP model for the makespan-minimizing flow shop scheduling problem, by applying sets of inequality constraints, based on start time variables, of each job on each machine. In this work, we derived a two-stage robust counterpart of his model, for the total weighted completion time objective, with the following decision variables: Update Θ := Θ ∪ {λ * (v) } and set (v) := (v + 1)

Worst-case MILP -Problem variables ∆r,i = 1, if job i will have its processing time deviated on machine r 0, otherwise.

Cr,j = completion time of job σ(j) (in position j) on machine r.

Er,j = auxiliary variable, equals to min(Cr,j-1, Cr-1,j).

Ar,j = auxiliary variable, equals to | Cr,j-1 -Cr-1,j |.

Dr,j = auxiliary variable, models the disjunction used to calculate Ar,j.

case scenario λ * under budget uncertainty set U Γ . Remark that ∆ * r,i values are used to define δ λ r,i values for the scenario added to set Θ, and used in the 2-stage RO models.

In the experiments shown in Section 4.6, the convergence of the C&CG method was also accelerated by generating multiple worst-case scenarios at each iteration, whenever possible.

Our computational experiments have evidenced that the limits of the proposed C&CG solution method lie in the solution of the Master Problem. In particular, we observed a high proportion of time spent when solving Master Problems for instances with 15 jobs and 5 machines. Nonetheless, for the oil and gas maintenance problem at hand, improved solutions are needed for instances of this size. Therefore, in the next section, we will propose an algorithm enhancement to overcome this limitation.

Hybrid C&CG Method

Unsurprisingly, the C&CG will suffer of computational limitation as instance size grows, in particular when solving the Master Problem. For this reason, we devise an improved MP solution method, which brings a combinatorial branch-and-bound inside the MILP solver tree structure.

With this new approach, we implemented an alternative Master Problem solution method for assignment-based and dichotomous-based Robust Counterparts. Similarly to the method presented in Algorithm 6, the alternative MP solution method relies on a RC model invoked in an iterative way, based on a list of C&CG cuts provided. We denote as Hybrid C&CG Method the C&CG solution method that incorporates this new MP solution technique. The main advantage relies on the alternative branching strategy employed, which provides new information used to prune nodes, as well as a powerful combinatorial lower bound.

The implementation of the hybrid C&CG method was based on the CPLEX solver 20.1. Based on its branch callback, we developed a combinatorial branch-and-bound emulation similar to [START_REF] Rubin | OR in an OB World[END_REF],

which will be described next.

Branching strategy

Consider the search tree of the classic flow shop combinatorial branch-and-bound [START_REF] Bj Lageweg | A general bounding scheme for the permutation flow-shop problem[END_REF], depicted in Figure 4.1(a). The root node (at level 0) represents the null schedule. A given node N at level s represents a partial schedule σ = (σ(1), . . . , σ(s)) of size s, indicating that job σ(j) occupies the j-th position on each machine, for 1 ≤ j ≤ s, where 1 ≤ s ≤ n. By placing any unscheduled job i in position (s + 1), we produce a child node σi = (σ(1), . . . , σ(s), i), in level s + 1.

It is clear that the flow shop search tree requires several branches at each node. However, CPLEX allows the creation of at most two branches at a node. To circumvent this limitation and produce more than two branches, we must emulate multi-way branching by binary branching. To

Part , Chapter 4 -Robust scheduling in Oil and Gas exploration

Finally, when solving the 15×5 instances, the largest ones in the test-bed, we perceived a drastic performance reduction of the algorithm. For this reason, besides extending the time limit parameter to 14, 400 seconds, we chose to solve these instances with the four best performing RC models so far: Manne, Liao-You, TS2 and Wilson. As shown in Table 4.5, the percentage of solved instances drops from 98% to 14% when applying the best-performing Manne model. Also, when analyzing the % gap of instances not solved to optimality, the average % gap is considerably higher in all models, as well as its variance. We can see that, for these instances, the C&CG algorithm was not able to perform more than 3 iterations on average.

Hybrid C&CG method performance

We will now analyse the performance of the hybrid algorithm enhancement, designed to overcome the performance limitation observed when solving the C&CG master problems.

The last three columns of Table 4.5 show additional C&CG results obtained with the new hybrid solution method. The Wilson-Hybrid model reached the best performance, for solving the highest proportion of instances to optimality (47%), and also for obtaining the shortest solution time in 56% of the instances solved to optimality, when compared to the other RC models. All hybrid solution methods achieved drastic performance improvements when compared to the initial solution method results, where the best-performing conventional C&CG algorithm, Manne, had obtained only 14% of instances solved to optimality, along with an average % gap (standard deviation of % gap) of 4.62 (8.42), respectively.

One possible answer to the obtained results may be found in how the hybridization of the solution method works. The partial permutation σ is built iteratively, using the same job fixation order of the combinatorial branch-and-bound method, i.e., fixing one job at a time, from left to right. Given this solution representation, whenever a new job k is fixed in the partial permutation, new cuts have to be added to the existing MILP model of the corresponding node in the B&B tree, in order to make the solutions from combinatorial B&B and MILP compatible. Experimental data shows that, in the case of hybrid Wilson method, the cuts added to each node, which are based on the job assignment binary variables Z i,j , turn out to be stronger than the cuts added to the Liao-You and Manne models, which are based on the job precedence variable D i,k .

Case study on two real instances

In this section, we assess the quality and level of robustness of scheduling solutions for two real problem instances, the first one representing a platform with 9 oil-wells and 4 maintenance tasks (9 × 4) and the second one a different platform with size 15 × 5. The processing time matrices p and p were obtained from the available operation history. The following solution methods were used: -Det: deterministic PFSP solution [START_REF] Jm Wilson | Alternative formulations of a flow-shop scheduling problem[END_REF] with P={p r,i }, r ∈ M, i ∈ J.

-RPFS(Γ): Wilson-Hybrid RPFS solution method, described in Section 4. -SimGRASP: stochastic PFSP simheuristic method from [START_REF] Ferone | Combining simulation with a GRASP metaheuristic for solving the permutation flow-shop problem with stochastic processing times[END_REF], properly modified to find the schedule that minimizes the expected total weighted completion time. SimGRASP is a modified GRASP metaheuristic that incorporates Monte Carlo Simulation to solve the PFSP with random processing times. Given its stochastic nature, we obtained 25 independent runs for each instance file. Then, for result comparison purposes, for each independent run, we calculated the robust cost Z at each Γ protection level. Finally, we stored, for each instance, the smallest and largest robust costs found within these 25 simheuristic executions. We call them SimGRASP-Min( 25)

and SimGRASP-Max(25).

We assessed the robustness of each obtained solution σ by calculating the robust cost at different protection levels Γ, using the worst-case MILP model defined in Section 4.4.2. Figure 4.2 depicts the robust cost Z(σ, Γ) of each solution σ under different protection levels Γ. For clarity of the graphs, the robust costs for some protection levels were omitted.

Observe that, as the protection level Γ increases, so does the robust cost, i.e., the total weighted completion time (TWCT) of the worst-case scenario defined by the protection level. In other words, higher values of Γ are equivalent to a greater quantity of operations with deviated processing times, which directly impacts the solution cost Z(σ, Γ). In the case studies from Figure 4.2, the extreme cases occur whenever Γ ≥ 60%, yielding the highest robust costs.

From the viewpoint of the decision-maker at the oil company who needs to hedge against worstcase maintenance costs, it would be preferable to obtain a solution method that performs well under different protection levels. With this in mind, in the two graphs presented, we identify which scheduling method (and respective solution) presents the best (smallest) robust cost, considering all Γ values. Regarding the first graph (9 × 4 instance), note that RPFS(10) offers improved protection against worst-case scenarios for 10% ≤ Γ ≤ 20%, while RPFS( 25) is the best-performing robust solution considering 25% ≤ Γ ≤ 35%. Finally, RPFS(50) is indicated for higher protection levels Γ ≥ 45%. We also highlight the disappointing worst-case performance of both the nominal solution Det and the stochastic method. The vast distance between the robust costs of the stochastic method, i.e., SimGRASP-Min(25) and SimGRASP-Max(25), reveals a significant exposure to the realization of worst-case scenarios, which is represented by the highlighted area in the graph.

In its turn, the larger instance (15 × 5) presents a distinct behavior in robust cost differences between distinct protection levels. In In summary, the choice of a robust solution depends on the instance and the desired protection level. The examples above illustrate how RPFS can provide a pool of robust schedules, depending on the value of Γ. With these options, the decision-makers can choose one of the schedules based on their risk preferences. Also, remark that, if the stochastic heuristic method is chosen, depending on the solution returned by the algorithm, the worst-case performance may be weak, as can be seen on the robust costs achieved by SimGRASP-Max(25). Indeed, neither SimGRASP nor the deterministic models have the objective of minimizing the worst-case TWCT.

Analysis based on Monte-Carlo simulation

As a complementary analysis, we evaluate the expected behavior of obtained problem solutions.

The TWCT distribution of the obtained robust schedules was simulated by subjecting the processing time matrix to random perturbations. In particular, in each Monte Carlo simulation run, the (actual) processing time p r,i , ∀r ∈ M, i ∈ J, was independently drawn from a predefined probability distribution, yielding a random processing time matrix P . For this purpose, we used lognormal, symmetric triangular, and uniform distributions in [p -p, p + p] to generate random processing times. We generated 10, 000 processing time matrices P . Then, for each RPFS(Γ) solution σ Γ , obtained with a specific protection level Γ, we processed the set of all corresponding TWCT values ϕ(σ Γ , P ) obtained through simulation on P . The same was made for the solutions returned by Det and SimGRASP-Min(25).

We first focus on simulation results presented in Figure 4.3(a). Regarding the 9 × 4 instance, we can observe that, in the long run, the TWCT performance of RPFS(5), RPFS [START_REF] Balasubramanian | A novel branch and bound algorithm for scheduling flowshop plants with uncertain processing times[END_REF] and RPFS [START_REF] Colson | Comprehensive Real-Time Microgrid Power Management and Control With Distributed Agents[END_REF] are equivalent to SimGRASP, a method specialized at optimizing the expected TWCT. On the other hand, as stated in the worst-case analysis of Figure 4.2(a), not all schedules are sufficiently immune against worst-case scenarios. For instance, if the decision-maker assumes an intermediate protection level of Γ ≤ 35%, the two most appropriate schedules, with smallest robust costs, are RPFS(25)

and RPFS(10).

When analyzing the 15 × 5 instance in Figure 4.3(b), the following robust solutions present expected TWCT performance quite similar to SimGRASP: RPFS(5), RPFS(15) and RPFS [START_REF] Gijs Van Essen | Robust waterflooding optimization of multiple geological scenarios[END_REF]. Taking the worst-case evaluation into account and considering a protection level 15% ≤ Γ ≤ 40%, these three robust solutions also provide better protection against worst-case costs, when compared to the stochastic solution method.

Finally, Table 4.6 presents some statistics related to the simulation of processing times of the 9 × 4 instance. In this analysis, whenever the same robust solution has been obtained for more than one Γ parameter value, their (equivalent) statistics were reported in the same column. Given 10, 000 ters, the models developed here are based on budgeted uncertainty, a powerful tool for handling robustness and the trade-off between cost and risk, avoiding the over-conservativeness of the conventional robust scheduling approaches.

Besides proposing a set of benchmark instances for the problem, we developed seven robustcounterpart formulations, coupled with an exact solution method based on Column-and-Constraint Generation (C&CG). Additionally, we implemented a hybrid C&CG method which relies on two strategies to enhance the processing of larger problem instances. First, a branching strategy used in the combinatorial branch-and-bound for scheduling problems. Second, a new lower bound for the robust problem, based on an existing bound used in the deterministic case. Computational experiments suggest that the improved algorithm can handle test problems with n ≤ 15, reaching the same instance-size limit of the best-performing deterministic solution methods. Despite the longer average processing time required to solve the larger 15 × 5 instances, good-quality solutions were obtained by the hybrid C&CG based on the Wilson formulation, with 47% of the instances solved to optimality. For the remaining instances, average gaps of 5% were obtained.

We have also assessed the cost of the solutions returned by the robust model and compared them to deterministic and stochastic solutions. According to simulations based on three probability distributions, our solution method was capable of protecting against worst-case scenarios, with just a small overhead in the expected solution cost.

Experimental results indicate the feasibility of applying this robust solution method to real-world problem instances, such as the ones from the oil and gas industry, whose current solutions are obtained through methods that disregard either uncertainty or the impact of worst-case scenarios.

Based on their risk preferences, decision-makers can then choose an appropriate schedule from a pool of robust solutions, with different levels of exposure to uncertainty.

Chapter 5

CONCLUSIONS AND PERSPECTIVES

The solution methods to all robust problems studied in this thesis rely on the budgeted uncertainty set, which provides a pool of robust solutions under different levels of realization of uncertainty, to hedge against worst-case costs. The great advantage of the applied budgeted approach lies in its capacity to avoid the over-conservativeness of conventional robust optimization approaches, at the same time enabling the decision-maker to evaluate the trade-off between robustness and higher solution cost.

Conclusions

The profile and renewable production. These, in turn, may vary according to the season of the year or even according to other recurrent patterns. Due to scope limitations, we opted not to deepen our analysis based on specific dates of the year, but we believe additional studies could be performed on this subject.

It is also worth noting that the CCP contract framework, although not yet a reality for small consumers, has the potential to be used as a tool to improve the predictability of consumption and production of microgrids. Moreover, as microgrids and actively managed distribution networks become widespread, the introduction of forward energy trading is expected to happen at the local level [START_REF] Cazalet | Transactive energy models[END_REF]. In this sense, the CCP framework could be used in the context of small aggregators of prosumers, improving energy exchange between them.

The second part of the thesis explored robust scheduling problems based on the budgeted uncertainty set. We first studied the 2-machine robust permutation flow shop (2RPFS) problem Therefore, to allow the solution of larger problem instances, we designed and implemented a Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristic, with the worst-case procedure incorporated as the objective function. Extensive experimental results demonstrated that, compared to the baseline C&CG exact method, the GRASP algorithm was very efficient in obtaining robust schedules. In the absence of literature instances, four sets of benchmark test-beds were proposed, including instances based on the classical flow shop literature. After evaluating both C&CG and GRASP algorithms on this test-bed, GRASP was shown to produce optimal solutions on most small and medium-sized instances. Indeed, GRASP obtained a higher proportion of solved instances than the exact method, which evidences its efficiency and solution quality.

The research conducted with these robust scheduling methods allowed us to develop, in the final study, an exact solution method for the m-machine robust permutation flow shop problem to minimize the worst-case total weighted completion time (RPFS-TWCT), a problem with direct application in the oil and gas industry. Similar to the previous studies, since no set of problem instances

Appendices

Appendix A

OPTIMIZATION CRITERIA FOR ROBUST PERMUTATION FLOW SHOP (RPFS) PROBLEM

Different optimization criteria may be used to choose a robust solution [START_REF] Gerodimos | Robust Discrete Optimization and Its Applications[END_REF][START_REF] Aissi | Min-max and min-max regret versions of combinatorial optimization problems: A survey[END_REF]. The first and simplest criterion is the minimax (also known as the absolute robust criterion). In this case, given a minimization problem, the robust decision is made by choosing a solution that minimizes the highest cost over all possible scenarios.

A second possible criterion is called minimax regret, which aims to find the least maximum regret over all possible scenarios. Regret can be either defined as the difference or the ratio between the resulting cost of the candidate decision and the cost of the decision that would have been taken

if uncertain input data were known in advance (prior to the decision time). In the first case, where regret is defined as the difference between two values, the so-called robust deviation decision is obtained. For the latter case (regret being the ratio of two values), the resulting decision is the relative robust decision. Either way, decisions originated from these two criteria tend to be less conservative than the absolute robust criterion, because they measure the amount of deviation of a specific candidate decision by comparing its performance with the performance of the "ideal" solution of each possible scenario (i.e. its corresponding optimal decision if uncertainty was known ahead of time).

Regarding the Rob-PFS problem, existing works deal with two possible measures of robustness, associated with the makespan objective: minimax makespan and minimax regret makespan.

A.1 Minimax Makespan (MM) Rob-PFS problem with 2 machines

The objective of the Minimax Makespan is to minimize the maximum possible makespan associated with a schedule.

A.2 Minimax Regret Makespan (MRM) Rob-PFS problem

In this case, the objective is to minimize the maximum possible regret associated with a schedule. Given a scenario λ ∈ Λ, the regret of a schedule σ is measured as the absolute difference between:

1. the makespan of the schedule σ for the scenario λ [ϕ(σ, P λ )];

2. the makespan of the optimal schedule σ * λ for the scenario λ [ϕ(σ * λ , P λ )]. The so-called absolute deviation robust schedule (σ ADRS ) satisfies [START_REF] Kouvelis | Robust scheduling of a twomachine flow shop with uncertain processing times[END_REF]:

The research on minimax regret optimization models is well-established nowadays. In particular, most of the works on flow shop robust scheduling rely on this measure of robustness, as seen in the literature review. Since the PFSP is NP-hard for 3 or more machines, it is not possible to obtain exact solutions to the MRM RPFS problem when m ≥ 3, given the difficulty to calculate the optimal deterministic schedule for a given scenario.

A BRIEF INTRODUCTION TO THE BUDGETED UNCERTAINTY MODEL

Bertsimas and Sim [START_REF] Bertsimas | The Price of Robustness[END_REF] proposed an alternative method of representing data uncertainty, avoiding the complication of non-linear formulations.

Consider the following nominal linear optimization problem:

In the above formulation, we assume that data uncertainty only affects the elements in matrix A.

Without loss of generality, it can be assumed that the objective function c is not subject to uncertainty, since it is possible to use the objective maximize z, and add the constraint z ≤ c T x, and then include this constraint into Ax ≤ B.

Consider a specific row i of matrix A = [a ij ] and let N i represent the set of coefficients in row i that are subject to uncertainty. Each entry a ij , j ∈ N i is modeled as a symmetric and bounded random variable ãij , j ∈ N i [START_REF] Ben | Robust solutions of linear programming problems contaminated with uncertain data[END_REF], and takes values in the interval [a ij -ãij , a ij + ãij ]. Associated with the uncertain data ãij , we define the random variable η ij = (a ij -ãij )/â ij , which obeys an unknown but symmetric distribution, taking values in [-1, 1].

Given the i-th constraint of the nominal problem a T i x ≤ b i , now consider that the set of coefficients a ij , j ∈ N i take values according to a symmetric distribution with mean equal to the nominal value a ij in the interval [a ij -âij , a ij + âij ]. For every i, a parameter Γ i (not necessarily integer) is introduced, and takes values in the interval [0,

Given these premises, Bertsimas and Sim defined the following symmetric and bounded uncertainty data set, in which an uncertain budget parameter Γ i is introduced to control the degree of uncertainty:

PROOF OF 2RPFS WORST-CASE SCENARIO EXTREME POINTS

Although not being explicitly stated, it is assumed that the 2RPFS budget parameters Γ 1 and Γ 2 are both integers. Now suppose that, given a permutation σ, we are calculating its worst-case scenario λ and worstcase makespan Z(σ), with fractional budget values of Γ 1 and Γ 2 . In this case, the processing time deviation amount δ r,i lies in the [0, 1] interval. Every worst-case scenario has an associated critical path as well as a set of operations O r,i that belong to this critical path. We propose the following lemma.

Lemma C.0.1. Given a permutation σ with worst-case scenario λ, consider a machine M r , for which there are two operations O r,i 1 and O r,i 2 that belong to the critical path and 0 < δ λ r,i 1 , δ λ r,i 2 < 1. Also suppose, without loss of generality, that p r,i 1 ≤ p r,i 2 . Then, there is an equivalent worst-case scenario λ # whose makespan is greater or equal than the makespan of scenario λ, such that at least one of the following is true: δ λ # r,i 1 = 0 or δ λ # r,i 2 = 1.

The proof follows by construction. The idea is that, given two operations O r,i 1 and O r,i 2 that belong to the critical path, it is always possible to "transfer" a portion of the processing time deviation δ r,i from the operation with largest maximum deviation (O r,i 2 ) to the shortest one (O r,i 1 ), until at least one of their δ r,i values reaches an extreme value of zero or one.

Let λ # be the worst-case scenario constructed in a way that at least δ λ # r,i 1 = 0 or δ λ # r,i 2 = 1:

Note that, since operations O r,i 1 and O r,i 2 belong to the critical path in both scenarios λ and λ # , the makespan ϕ of the alternative worst-case scenario λ # is calculated as: ϕ(λ # ) = ϕ(λ) -(δ λ r,i 1 p r,i 1 + δ λ r,i 2 p r,i 2 ) + (δ λ # r,i 1 p r,i 1 + δ λ # r,i 2 p r,i 2 ) ϕ(λ # ) = ϕ(λ) -(δ λ r,i 1 p r,i 1 + δ λ r,i 2 p r,i 2 ) + + (δ λ r,i 1 -min(δ λ r,i 1 , 1 -δ λ r,i 2 )) p r,i 1 + (δ λ r,i 2 + min(δ λ r,i 1 , 1 -δ λ r,i 2 )) p r,i 2 ϕ(λ # ) = ϕ(λ) + min(δ λ r,i 1 , 1 -δ λ r,i 2 )( p r,i 2 -p r,i 1 )

And the following holds true:

ϕ(λ # ) -ϕ(λ) = min(δ λ r,i 1 , 1 -δ λ r,i 2 )( p r,i 2 -p r,i 1 ) ≥ 0, since p r,i 2 ≥ p r,i 1 . We just proved that the makespan in scenario λ # is greater or equal than the makespan in scenario λ.

Remark that the same argument as above is valid for pairs of jobs that do not belong to the critical path. In particular, a change in their processing times does not affect the (worst-case) makespan. Now we can prove the following.

Corollary C.0.2. Given a permutation σ with worst-case scenario λ, for every machine M r , there is an equivalent worst-case scenario λ # where all δ λ # r,i are either zero or one, except for at most one operation O r,i where δ λ # r,i = Γ r -Γ r .

The proof follows by contradiction. Given a worst-case scenario λ induced by a permutation σ, let x(λ, r) be the number of operations O r,i on machine M r such that 0 < δ λ r,i < 1. Suppose, by contradiction, that x(λ, r) ≥ 2. Therefore, by successively applying Lemma C.0.1, we end up an alternative worst-case scenario λ # , such that x(λ # , r) ≤ 1 and, by Equation (C.1), δ λ # r,i = Γ r -Γ r .

With that being said, it is possible to have the budget parameters Γ 1 and Γ 2 fractional, with a slight adaptation in the dynamic programming table, taking into account that, for each machine M r , exactly one of its operations will deviate its processing time by a factor of Γ r -Γ r .