case: small size workshops under low uncertainty . . . . .

since I began working on this topic in my master thesis. Ever since, they have supported me not only by providing a research assistantship over almost four years, but also emotionally through the rough road to finish this thesis. They helped me come up with the thesis topic and guided me over almost four year of development. And during the most difficult times when writing this thesis, they gave me the moral support I needed to move on. I would like to express my deep gratitude to them. During my years of PhD at G-SCOP Laboratory, I had the chance to work in a pleasant atmosphere. Therefore, I would like to thank my colleagues and all the staff in G-SCOP Laboratory.

I wish also to express all my thanks to the committee members for the honour they gave me by participating to my thesis committee. I am indebted to Mr A. Rossi, Professor at the University of Angers, and Mr E. Sanlaville, Professor at the University le Havre, for accepting to report my thesis manuscript, for all the constructive remarks and valuable corrections. I am also indebted to my examiners Mr A. Dolgui, Professor at the IMT Atlantique and Mr R. Leus, Professor at KU Leuven for letting my defense be an enjoyable moment and for their brilliant comments and suggestions.

Finally, I would like to acknowledge my parents, my brother and my closest friends. Thank you very much for your unconditional love and support. Thank you for being my guiding light, for encouraging me, and for making me who I am today. I am extremely grateful for everything that you do.

General introduction

In the nineteenth century, the thinking was characterized by the certainty. It was marked by a confidence in the power of science and technology. Newtonian physics, for instance, showed that the universe functions according to rigid laws and that its course could be predicted with total confidence and certainty. But, a scientific revolution began to take shape when the Quantum Theory and the Theory of Relativity proved that the knowledge was incomplete since there as places in the universe such as black holes from which no information at all could be obtained. Chaos Theory also showed the limits of predicting or controlling the world. Thus, the twentieth century was marked by the emergence of uncertainty and the fall of certainty.

This new perception of the world has made a revolutionary effect not only in physics, but in all disciplines: economy, decision-making, policy, computational modelling and simulation, etc.. In computational modelling, optimization and simulation, uncertainty is inevitable when we consider real-world problems, systems or phenomena. In this discipline, the uncertainty faced by the modellers can basically arise from the model form or from the empirical data (See [START_REF] Morgan | Uncertainty: a guide to dealing with uncertainty in quantitative risk and policy analysis cambridge university press[END_REF] classification in Appendix A). The model form uncertainty can be defined as an inadequacy in the representation of the problem due to simplifications and reasoning approximations. Sometimes, it can also arise from the difficulty to choose among alternative models. But, as a model is a simplified representation intended to enhance our ability to understand, simulate, predict and control a system, a perfect compliance between the model and the reality never exists in an absolute sense. In the other hand, the model form uncertainty can be overcome only through model validation. Once the model form is validated, the model's usefulness will depend on high part on the accuracy of the data. In fact, data uncertainty can make the exploitation of the optimization and simulation results far from the desired goal in most of real-world applications.

In scheduling, the gap between the results provided by the classical scheduling algorithms and their applicability in production environment requirements was pointed out by both researchers and practitioners.

One of the reasons of such a gap is connected with the assumptions that data (related to jobs and/or machines) are known with certainty. However, scheduling in production environment is recognized to be a complex and dynamic activity in which job processing times can take longer or shorter than forecast, release dates and due dates may change, jobs may have to be inserted or canceled. Besides, the resources may become unavailable due to unforeseen events as breakdowns, accidents, operator absenteeism, etc.. Assuming a certain data can make the classical scheduling approach inadequate to solve scheduling problems under uncertainty.

Several publications claimed that ignoring data uncertainty can lead the decision-maker to be confronted with infeasible or sub-optimal schedules. Thus, computing an optimal schedule has become less important than protecting the schedule from uncertainty. We should recognize that we are no longer at the beginning of the road to develop approaches and models for dealing with optimization problems under uncertainty in

GENERAL INTRODUCTION

general and scheduling ones in particular. The number of published works in this issue exploded, but the number of problems affected with data uncertainty is unlimited. Besides, there is neither a unique approach nor a unique model to deal with uncertainty arising in a given problem. For these reasons, optimization under uncertainty provides fertile ground for researchers.

Thesis objectives and contributions: In this thesis, we focus on the makespan minimization on parallel machines with splitting (resp. preemption) under uncertain processing times. Parallel Machine Scheduling (PMS) consists in sequencing n jobs on m same function machines in order to optimize the objective. The processing time of a job on a machine represents the duration required by this machine to process this job.

PMS is a very common problem in many manufacturing industries and also in multiprocessor computing applications. In PMS, we distinguish three environment machines: the identical, the uniform, and the unrelated parallel machines. In the identical parallel machines, the job processing time is independent of the machine where it is processed. In the uniform parallel machines, each machine has a different speed and the processing times of a job in two different machines are proportional. In unrelated parallel machines, no particular relationship exists between the processing times on the different machines, i.e., there is no proportionality between the processing time of a job on a given machine and its processing time on another machine. From a mathematical point of view, the unrelated parallel machines represent the general case of PMS.

The splitting and the preemption often take place in problems. Indeed, we consider that we can divide each job into sub-jobs that can be processed independently on the machines. When we accept to overlap the sub-jobs of the same job, we address the PMS under job splitting otherwise we address the preemptive PMS.

The makespan minimization on parallel machines with job splitting is a relaxed version of the preemptive problem. In environments that are not affected by uncertainty, the makespan minimization on parallel machines under job splitting (resp. preemption) can be solved in polynomial time. Indeed, the most general case which is the makespan minimization on preemptive unrelated parallel machines has been shown to be polynomial by [START_REF] Lawler | On preemptive scheduling of unrelated parallel processors by linear programming[END_REF]. However, the uncertainty of processing times is prevalent in such problems. When we consider this uncertainty, the deterministic models can lead to schedules with poor performance when applied to the actual realizations of processing times. Therefore, we investigate the makespan minimization on parallel machines, under both splitting and preemption, taking into account the uncertain processing times. Thus, our contributions can be described in response to the following research questions:

Research question 1: How to provide solutions that withstand the uncertain processing times?

To reach this goal, we adopt a proactive approach under which we anticipate the uncertainty in order to provide robust solutions. We consider then, that in a lot of activities, the experts are able to describe uncertain data realizations by the construction of a set of discrete scenarios representing several potential futures. But, in our problems, a subsequent difficulty is related to the feasibility of the constraints under all the scenarios.

We initially propose two different approaches to deal with the uncertain processing times. The first approach aims to enforce the feasibility of the schedule under different scenarios by tolerating the violations of some processing requirements. Slack variables are used to compensate such a loss. In the second approach, we propose an artificial scenario solution based algorithm. Under this approach, we construct a set of feasible solutions and we choose among them the most robust. This choice is based on an evaluation algorithm that computes a robustness measure under each solution. Thanks to this second approach, we respect the hard constraints and ensure their feasibility under all the scenarios without any violations. However, the artificial scenario solutions are not optimal. Therefore, we propose a third approach in which we use the min-max objective -widely used in robust optimization-to generate optimal robust schedules.

The second question that we propose to answer through this thesis is related to the robustness cost of the solutions. Indeed, several authors and practitioners highlight that robustness has a cost: the more you robustify the solution, the more you deteriorate the performance and consequently the more you pay, and vice versa. In this thesis, we propose to quantify the cost of robustness of each solution in order to verify this postulate. We formulate this question as follows:

Research question 2: What is the robustness cost when we use each of the computed robust solutions?

To answer this question, we define a robustness cost indicator and then we analyse and compare the evolution of the robustness cost of the robust solutions according to different parameters: the problem size, the discrete scenario set size and the degree of uncertainty. Indeed, we distinguish low uncertainty degree, medium uncertainty degree and high uncertainty degree.

When we answer the previous questions, new research questions arise:

Research question 3: When the future turns out differently than considered, does a robust solution guarantee a good performance under the new scenario? And how much adjustment is needed to be also protected against this new scenario?

To answer these questions, we propose to evaluate the stability of the robust solutions under new scenarios. We evaluate both the performance stability and the structure stability.

Thesis outline: This thesis is divided into six chapters, providing an introduction, the major contributions and an outlook on further research questions and perspectives.

Chapters 1 and 2 provide the materials to the understanding of the issue of optimization under uncertainty in general and scheduling under uncertainty in particular. In chapter 1, we provide a background for the understanding of the various aspects of data uncertainty. We explore the existing concepts and classifications of uncertainty from different fields. Then, we propose a unified taxonomy of uncertainty in computational modeling and simulation. We propose a synthesized view of uncertainty type representations. We also survey their related optimization approaches and models. At the end, we propose a general methodology to deal with data uncertainty in optimization problems. In chapter 2, we focus on scheduling. We present the general form of the scheduling problem and define its fundamental notions. We discuss the limitations of scheduling under the hypothesis of certainty and we show the necessity to take into account uncertainty. Besides, we briefly review the representations of uncertainty in scheduling. And then, we survey the existing approaches to deal with uncertainties and disruptions when the objective is robustness and/or stability. In light of this, we show that globally there exist a lot of opportunities for future developments and we identify some areas for future research. Regarding our research questions, we identify the key tracks for the development of clear answers to these questions.

GENERAL INTRODUCTION

Chapters 3, 4, 5 and 6 contain the major ideas and contributions of this thesis. In Chapter 3, we focus on the makespan minimization on unrelated parallel machines under splitting and preemption respectively.

We present these problems in the static deterministic cases and stress the need to consider processing time uncertainty. We provide the main motivations for our work by examples. Therefore, we show that the optimal solutions computed based on a unique scenario lead to schedules with poor performance when the processing times turn to be different from the forecast one. Then, we propose to model the uncertainties by considering a set of potential scenarios (discrete scenario representation) and we show that the uncertainty in these problem models is affecting the equality constraints which impacts the feasibility. As initial contributions, we propose two different approaches to deal with the uncertainty of processing times. The first approach aims to enforce the feasibility of the schedule under different scenarios by tolerating the violations of some processing requirements. In the second approach, we propose an artificial scenario based approach.

Under this approach, we construct a set of feasible solutions and we choose the robust solutions based on an evaluation algorithm that compute the robustness measures of each solution. We do extensive computational experiments to test the validity of the third approach in both splitting and preemption cases. These results are serving to a comparable basis in the next chapters.

In Chapter 4, we show that the direct application of robust optimization techniques leads to no solution.

To overcome this difficulty, we propose formulations in which the uncertainty appears in the objective instead of the assignment constraints. Thus, we provide robust solutions in polynomial time, and we extend these results to the special cases of uniform and identical parallel machines. Extensive numerical experiments are carried out to illustrate these new proposals. We extend the application of the robust discrete optimization to the preemptive unrelated parallel machines under discrete processing time scenarios in Chapter 5. A major difference between the preemptive case and the splitting one is due to the computation of a sequence. We consider that the decision-maker is interested in computing a unique assignment solution under the set of discrete scenarios and that he accepts to have different sequences. Here again, we provide robust assignment solutions in polynomial time while the sequence construction remains the same as in the deterministic case.

The same test protocol is applied to evaluate the robustness cost of the solutions.

Finally, Chapter 6 is devoted to evaluating the stability of the structure and the performance of the robust solutions when adding a new scenario. In this approach, the term stability is used for the algorithm step at which robust solutions of the problem have been already computed, and additional calculations are performed in order to investigate how these solution structures and performances depend on changes in the set of potential scenarios. In the experimental results, we focus on the splitting case.

Chapter 1

Uncertainty: Conceptual classifications, Representations and Solving Approaches

Abstract: The goal of this chapter is to provide a background for the understanding of the various aspects of uncertainty. We introduce the existing concepts and classifications of uncertainty from different fields.

In light of this, we propose a unified taxonomy of uncertainty in computational modeling and simulation.

Besides, we review the uncertainty models developed by the mathematical community and we classify them according to their potential to represent the uncertainty types. Then, we focus on the approaches and models to formulate and solve optimization problems under uncertainty. We identify the main objectives of optimization models under uncertainty and propose a cross classification of the optimization models under uncertainty according to the objectives and to the uncertainty types. Lastly, we provide a guide to optimization under uncertainty.

Introduction

Data uncertainties are various. When they affect a modeling and simulation problem, they may require different modeling techniques and elicit divergent resolution approaches. The uncertainty conceptual classifications the most considered in the literature are based on two dimensions which are the type and the level.

By the type of uncertainty, we mean its whatness i.e. the nature resulting from its inherent characteristics.

And by the level of uncertainty, we mean its rank between full knowledge and total ignorance, if it is closer to certainty or to ignorance, and where it can be situated between them. In Section1, we review some of these conceptual taxonomies provided by different communities. The objective of this section is to highlight the convergences between existing conceptual taxonomies. Indeed, we show that there exists a consensus about uncertainty types contrary to what it is often thought. Moreover, we show that the uncertainty type and the uncertainty level classifications are highly linked. Based on this review, we propose a unified taxonomy of uncertainty considering a type-level dimension. In Section2, we review the models (formal and practical)

developed by the mathematical community in order to represent the uncertainties. We show that the uncertainty models can also be classified according to their potential to represent adequately each uncertainty type. In Section3, we address the modeling approaches and formulations to solve a decision problem under uncertainty. Given that each optimization problem under uncertainty may require a particular approach, we introduce a guide to choose the adequate model based on different entries.

Uncertainty conceptual classifications 1.Uncertainty type classification

The economist philosophy introduced by [START_REF] Knight | Risk, uncertainty andprofit[END_REF] and [START_REF] Keynes | The general theory of interest, employment and money[END_REF] was the first to build the modern history of uncertainty. Motivated by the need to develop a realistic economic theory under which the full knowledge does not exist. a) Uncertainty vs Risk: [START_REF] Knight | Risk, uncertainty andprofit[END_REF] introduced the notion of uncertainty in a distinct sense of the notion of risk that was familiar to the economists at that time. [START_REF] Knight | Risk, uncertainty andprofit[END_REF] considered that uncertainty refers to situations where the probability of future events is unknown and immeasurable while risk refers to situations where future events occur with measurable probability. For [START_REF] Knight | Risk, uncertainty andprofit[END_REF], the probability distribution under uncertainty is unknown because the uncertain events are unique, they can not be reducible to a group of similar cases which does not allow the use of probabilities contrarily to risk under which probabilities could either be theoretically identified or determined from empirical frequencies. [START_REF] Knight | Risk, uncertainty andprofit[END_REF] called this distinction as the 'practical difference' between risk and uncertainty and he wrote that "the practical difference between the two categories, risk and uncertainty, is that in the former the distribution of the outcome in a group of instances is known (either through calculation a priori or from statistics of past experience), while in the case of uncertainty this is not true, the reason being in general that it is impossible to form a group of instances, because the situation dealt with is in a high degree unique." (1936) defended similar ideas about uncertainty based upon the impossibility of determining accurate probabilities. [START_REF] Keynes | The general theory of interest, employment and money[END_REF] affirmed that uncertainty concerns basically future events that are influenced by various changes (economical, social, political) which make their extrapolation from the actual events impossible: "By uncertain knowledge, let me explain, I do not mean merely to distinguish what is known for certain from what is only probable. The game of roulette is not subject, in this sense, to uncertainty... The sense in which I am using the term is that in which the prospect of a European war is uncertain, or the price of copper and the rate of interest twenty years hence... About these matters, there is no scientific basis on which to form any calculable probability whatever. We simply do not know." [START_REF] Knight | Risk, uncertainty andprofit[END_REF] and [START_REF] Keynes | The general theory of interest, employment and money[END_REF] classifications appeared to be very similar. However, the interpretations of their texts emphasized that when talking about missing probabilities, Keynes and Knight have something very different in mind. In [START_REF] Knight | Risk, uncertainty andprofit[END_REF], the decision-maker lack of information to construct a probability distribution while in [START_REF] Keynes | The general theory of interest, employment and money[END_REF] such a probability does not exist in a non-ergodic world.

Keynes

Many debates and analyses were constructed around these interpretations ((See for example the analysis of [START_REF] Davidson | Some misunderstanding on uncertainty in modern classical economics[END_REF]). b) Risk and Savage's uncertainty vs Ambiguity:

By the mid-20 th century and under the influence of 'the theory of games and economic behavior' developed by Von [START_REF] Von Neumann | Theory of games and economic behavior[END_REF] and 'the equilibrium' of [START_REF] Nash | Equilibrium points in n-person games[END_REF], a new uncertainty classification has emerged which is about the environmental uncertainty and the behavioral uncertainty. Environmental uncertainty is when the management of a firm has little information about its environment that is unpredictable while behavioral uncertainty arises from the difficulty to predict the actions of other relevant actors in a multi-actor system, particularly in view of the potential for opportunistic ((See [START_REF] Koopmans | Allocation of resources and the price system[END_REF] and [START_REF] Williamson | Opportunism and its critics[END_REF] for more discussion). Indeed, if decisions are made in a social context, the data of the problem may be determined by the decisions made by other actors who are in situations similar to our situation.

Following this, the future is unknown and decisions must be taken under uncertainty because probability can base only on individual's subjective estimates or what is called subjective probabilities. Therefore, [START_REF] Savage | The foundations of statistics[END_REF] claimed that objective probabilities which are related to a randomness of the real world do not exist, decision-makers can only assign subjective probabilities reflecting their degrees of belief to the events.

Savage's uncertainty has been used to describe subjective risk under which the probabilities are "personal" as termed in [START_REF] Savage | The foundations of statistics[END_REF]. He proved that, if the decision-maker adheres to the axioms of rationality, believing an uncertain event has possible outcomes each with a utility function, then the decision -maker choices can be explained as arising from the combination of this utility function and the subjective probability attached to each outcome. Under this subjectivist viewpoint of uncertainty, he made the implication that all uncertainties can be reduced to risk. But, [START_REF] Ellsberg | Risk, ambiguity, and the savage axioms[END_REF] and [START_REF] Shackle | Uncertainty and expectations in economics: essays in honour of gls shackle[END_REF], who were among the first economists to insist on the importance of uncertainty, rejected the use of numerical probabilities (even subjective) for representing the uncertainty in situations where it is impossible to distinguish meaningfully between the relative "likelihood" of the outcomes. Relying on the psychology literature, [START_REF] Ellsberg | Risk, ambiguity, and the savage axioms[END_REF] chose the term ambiguity to describe the situations under which it might not be desirable to behave according to the postulate of Savage.

c) Ambiguity Vs Fundamental uncertainty:

A new refinement of the uncertainty concept has been given by [START_REF] Dequech | Fundamental uncertainty and ambiguity[END_REF] who noticed that the Keynesian uncertainty refers not only to ambiguity, but also to fundamental uncertainty without any distinction between them. Therefore, he defined the fundamental uncertainty as a significant indeterminacy in the future that reflects situations under which not only decision makers cannot attach probabilities to the future events but a scenario that is not completely imagined may occur. Accordingly, the fundamental uncertainty is characterized by the possibility of creativity, innovation and structural change in a dynamic context which is not the case under ambiguity ((See [START_REF] Freeman | The economics of industrial innovation[END_REF], [START_REF] Davidson | Why acquisitions may not be the best route to innovation[END_REF], [START_REF] Dosi | Substantive and procedural uncertainty[END_REF]). Furthermore, [START_REF] Dequech | Fundamental uncertainty and ambiguity[END_REF] argued that fundamental uncertainty is not synonymous with ignorance since its degrees vary according to many factors as human creativity and technological innovations, in contrary to ignorance that is absolute. [START_REF] Dow | Uncertainty: A diagrammatic treatment[END_REF] proposed a diagrammatic representation of the different understanding of uncertainty according to the economist philosophies.

The economist classifications have been very influential, especially among decision-making and management community. Based on the Keynesian classification, [START_REF] Luce | Games and Decisions: Introduction and Critical Survey[END_REF] divided decision situations into three classes based on whether it has been carried out under conditions of certainty, risk or uncertainty.

They distinguished: decision under certainty, decision under risk, and decision under uncertainty. This classification is discussed and used until now to precise the context under which a decision has to be made [START_REF] Armbruster | Decision making under uncertainty when preference information is incomplete[END_REF], [START_REF] Kochenderfer | Decision Making Under Uncertainty: Theory and Application[END_REF]). The risk was refereed in the early papers of global optimization by [START_REF] Dantzig | Linear programming under uncertainty[END_REF] while the vagueness or fuzziness dates back to [START_REF] Zadeh | Fuzzy sets[END_REF] who means by decision-making in a fuzzy environment, a decision process in which the goals and/or the constraints constitute classes of alternatives whose boundaries are not sharply defined. In which concerns the ambiguity, this later was addressed by [START_REF] Kouvelis | Robust discrete optimization and its applications[END_REF].

d) Aleatory uncertainty Vs Epistemic uncertainty:

Since the 90's, the risk analysis community has manifested a growing interest to the definition of uncertainty and to the classification of uncertainty types. The risk analysis community has distinguished mainly two natures of uncertainty which are the aleatory uncertainty and the epistemic uncertainty ((See for instance: [START_REF] Hammonds | An introductory guide to uncertainty analysis in environmental and health risk assessment[END_REF], [START_REF] Helton | Treatment of uncertainty in performance assessments for complex systems[END_REF], [START_REF] Rowe | Understanding uncertainty[END_REF], [START_REF] Hora | Aleatory and epistemic uncertainty in probability elicitation with an example from hazardous waste management[END_REF], [START_REF] Ferson | Different methods are needed to propagate ignorance and variability[END_REF][START_REF] Beck | A survey of techniques for scheduling with uncertainty[END_REF][START_REF] Der Kiureghian | Aleatory or epistemic? does it matter?[END_REF]). The aleatory uncertainty is defined as the inherent variation associated with the physical system or the environment under consideration while the epistemic uncertainty is defined as the lack of knowledge or information. The epistemic uncertainty could be reduced by enhancing the state of knowledge and not the aleatory uncertainty. The refinement of this classification by different communities, through the works of [START_REF] Smithson | Ignorance and uncertainty: Emerging paradigms[END_REF][START_REF] Smithson | Ignorance and uncertainty: emerging paradigms[END_REF], [START_REF] Klir | Uncertainty-based information: Variables of generalized information theory[END_REF], [START_REF] Oberkampf | Verification, validation, and predictive capability in computational engineering and physics[END_REF], [START_REF] Ayyub | Uncertainty modeling and analysis in engineering and the sciences[END_REF] and [START_REF] Wierman | An introduction to the mathematics of uncertainty[END_REF], revealed a consensus about three distinct types of uncertainty in spite of the use of different semantics. These uncertainty types are the aleatory uncertainty, the ambiguity and the vagueness ((See definitions and synonyms in table 1.1 and figure 1.1).

In behavioral sciences, [START_REF] Smithson | Ignorance and uncertainty: Emerging paradigms[END_REF][START_REF] Smithson | Ignorance and disasters[END_REF][START_REF] Smithson | Ignorance and uncertainty: emerging paradigms[END_REF]) divided uncertainty into three types which are the probability, the non specificity (ambiguity) and the vagueness ((See their typology and definitions in appendix B table B.1). A much closed taxonomy to those of [START_REF] Smithson | Ignorance and uncertainty: Emerging paradigms[END_REF] has been developed in engineering and sciences by [START_REF] Ayyub | Uncertainty modeling and analysis in engineering and the sciences[END_REF] Inherent variation associated with -likelihood [START_REF] Ayyub | Uncertainty modeling and analysis in engineering and the sciences[END_REF]), the physical system or the environment -probability [START_REF] Smithson | Ignorance and uncertainty: Emerging paradigms[END_REF]), [START_REF] Oberkampf | Verification, validation, and predictive capability in computational engineering and physics[END_REF])

-randomness or frequency [START_REF] Ayyub | Uncertainty modeling and analysis in engineering and the sciences[END_REF]),

Vagueness

Information imprecisely defined, -imprecision or approximation [START_REF] Ayyub | Uncertainty modeling and analysis in engineering and the sciences[END_REF]), or indistinct -fuzziness (Wierman ( 2010)) [START_REF] Oberkampf | Verification, validation, and predictive capability in computational engineering and physics[END_REF])

Ambiguity

Multiplicity of alternatives without -non-specificity [START_REF] Smithson | Ignorance and disasters[END_REF] preference to any alternative [START_REF] Wierman | An introduction to the mathematics of uncertainty[END_REF] considered that uncertainty can be a likelihood, an ambiguity or an approximation. [START_REF] Klir | Uncertainty-based information: Variables of generalized information theory[END_REF] and [START_REF] Wierman | An introduction to the mathematics of uncertainty[END_REF] whose research was about the development of measures of uncertainty in mathematical systems also identified ambiguity and vagueness to be two distinct types of uncertainty ((See the appendix B figure and table B.4). Accordingly, ambiguity deals with the multiplicity without preference to an alternative, we (See multiple concepts but what is (Seen does not allow to identify precisely the concept (Seek. Vagueness deals with lack of definite or sharp distinction, we (See one concept, but it does not have the resolution to determine its identity or its frontier. [START_REF] Oberkampf | Verification, validation, and predictive capability in computational engineering and physics[END_REF] considered that the epistemic uncertainty includes the vagueness, the ambiguity ((See the appendix B figure and table B.5). [START_REF] Walker | Defining uncertainty: a conceptual basis for uncertainty management in model-based decision support[END_REF] defined uncertainty to be "any departure from the unachievable ideal of complete determinism" where determinism reflects the situations where we know exactly everything. He used the level of uncertainty as a dimension for its classification. Accordingly, he divided the spectrum between certainty and total ignorance to three intermediate levels of uncertainty. These three intermediate levels are: L1-Statistical uncertainty, L2-Scenario uncertainty, L3 Recognized ignorance.

Uncertainty level classification

Statistical uncertainty concerns uncertainty that can be described adequately in statistical terms. Scenario uncertainty is when a range of possible alternatives is known, but it is not possible to describe the probability distribution of any of them. And recognized ignorance is when ignoring the statistical properties and we are unable to develop scenario representation. Walker's level dimension has been used as a starting point for new uncertainty classifications in different applications. [START_REF] Courtney | Decision-driven scenarios for assessing four levels of uncertainty[END_REF], [START_REF] Makridakis | Decision making and planning under low levels of predictability[END_REF], [START_REF] Kwakkel | Adaptive airport strategic planning[END_REF], [START_REF] Walker | Addressing deep uncertainty using adaptive policies: Introduction to section 2[END_REF][START_REF] Walker | Deep uncertainty[END_REF]) identified five levels of uncertainty including The levels of uncertainty appeared also in the economy. [START_REF] Dequech | Uncertainty: a typology and refinements of existing concepts[END_REF] has proposed a typology of the main concepts of uncertainty used by economists in which he has introduced indirectly the uncertainty levels.

Indeed, he has distinguished between weak and strong uncertainty. Under weak uncertainty, the decisionmaker can form a unique, additive, and fully reliable probability distribution. In contrast, strong uncertainty is characterized by the absence of such a distribution. According to this, Dequech (2011) combines the levels with the uncertainty types. He considered that both weak and strong uncertainties are composed of two subcategories each. The first subcategory is the Keynesian risk while the second is Savage's uncertainty.

The first subcategory of strong uncertainty is ambiguity while the second is fundamental uncertainty.

Likewise, in computational modeling and simulation, the levels of uncertainty are found basically in manufacturing systems, a classification which is about known uncertainties, suspicions about the future and complete unknowns has a large spread ((See McKay and Wiers (1999), [START_REF] Vieira | Rescheduling manufacturing systems: a framework of strategies, policies, and methods[END_REF], Aytug et al. (2005a), [START_REF] Wojakowski | The classification of scheduling problems under production uncertainty[END_REF]). In this classification the known uncertainties are those for which some information is available, the suspicions about the future arise from the intuition and the experience of the human scheduler and unknowns are unpredictable events.

In the next section, we propose to initiate a unified taxonomy of uncertainty based on the reviewed literature. For this purpose, we have to answer these questions:

-Is there a consensus about uncertainty types? And is there a link between uncertainty types and uncertainty levels?

1.2 Toward a unified taxonomy of data uncertainty

The consensus about uncertainty types

In the timeline represented in Figure E.17, we represent the evolution of the uncertainty concept through the different communities cited above. We consider three categories: the blue color represents the economists, the purple color represents the decision-making community while the green color represents the scientific communities (risk analysis, engineering, etc.), and orange for behavioral science. From the timeline, we remark a first consensus about two distinct types of uncertainty which are the aleatory uncertainty and the ambiguity. The aleatory uncertainty is termed risk by the economists and decision-making community, probabilistic, statistical or likelihood by the others. This reveals that aleatory uncertainty is of two distinct types which are: the objective aleatory uncertainty under which an objective probability distribution exists, and the subjective aleatory uncertainty under which only a subjective probability distribution can be constructed based on expert's belief. They are both characterized by the existence of an underlying probability distribution. The ambiguity definitions are often related to the multiplicity of alternatives without a preference to anyone, the lack of knowledge under ambiguity is related to the probability of each alternative.

Indeed, We can also remark a second consensus from the different communities except the economists, about the vagueness (fuzziness) as a distinct type. Ambiguity is then characterized by the lack of knowledge.

Consequently, ambiguity is an epistemic uncertainty.

The second consensus that completes the first one considers besides ambiguity another epistemic uncertainty type which is vagueness (i.e. fuzziness). This type of uncertainty was defined by all the communities except the economists. The definition of fuzziness is basically related to the imprecision. The lack of knowledge under vagueness is related to the frontier that allows to make a sharp distinction.

The economist community identified another type which is the fundamental uncertainty defined as the impossibility to build any scenario, the lack of knowledge under fundamental uncertainty is related to the information that allow to construct a scenario because of a dynamic nature of the environment.

As a result, we can consider that uncertainty is of 5 types (objective risk, subjective risk, ambiguity, vagueness and fundamental uncertainty) that can be classified according to two categories (aleatory uncertainty and epistemic uncertainty) as given in Figure 1.

The link between uncertainty types and uncertainty levels

The level classification given by [START_REF] Dequech | Uncertainty: a typology and refinements of existing concepts[END_REF] showed that the type and the level of uncertainty in economy are linked ((See Table 1.3).

The same observation can be made for the level classification, in Table 1.4, proposed by [START_REF] Walker | Defining uncertainty: a conceptual basis for uncertainty management in model-based decision support[END_REF], [START_REF] Courtney | Decision-driven scenarios for assessing four levels of uncertainty[END_REF], [START_REF] Makridakis | Decision making and planning under low levels of predictability[END_REF], [START_REF] Kwakkel | Adaptive airport strategic planning[END_REF], [START_REF] Walker | Addressing deep uncertainty using adaptive policies: Introduction to section 2[END_REF][START_REF] Walker | Deep uncertainty[END_REF]. Indeed, when we analyze the classification that was given by [START_REF] Walker | Defining uncertainty: a conceptual basis for uncertainty management in model-based decision support[END_REF], we deduce that the statistical uncertainty is linked to the objective risk, the scenario uncertainty is linked to ambiguity and the recognized ignorance is associated to the fundamental uncertainty. In the improved

A unified taxonomy of data uncertainty

In the modeling, optimization and simulation problems under uncertainty, the different uncertainties need to be represented with different models and require divergent solving approaches. From a modeling point of view, the type dimension is useful as it permits to choose an adequate representation of the uncertain data, and from a decision-making point of view considering the level (severity) is necessary to choose an appropriate approach to deal with the uncertainty. Therefore, we propose a taxonomy in which the uncertainties are classified into types that are ranked according to levels. Data is certain when the knowledge about it is complete. Known uncertainties are uncertain data that experts/modelers are able to describe somehow by using historical information or by relying on their belief degree. And the unknowns are uncertainties that cannot be described, in this state, values that are not at all imagined could be taken by the uncertain data because unimaginable events may occur (for example in situations of crisis or natural disaster).

Based on these definitions, the aleatory uncertainty, the ambiguity and the vagueness belong to known uncertainties(Figure 1.3) while fundamental uncertainty belongs to unknowns. Consequently, fundamental uncertainty represents the highest level of uncertainty that we denote L5 while the known uncertainties can be classified according to four levels:

• L1 uncertainty corresponds to objective risk: probability distribution is available.

• L2 uncertainty corresponds to subjective risk: multiple alternatives with attached probabilities.

• L3 uncertainty corresponds to ambiguity: multiple alternatives without attached probabilities.

• L4 uncertainty to vagueness: the boundaries between alternatives are imprecise.

The progressive transition from certainty (that we classify at L0) to unknowns (that we classify at L5) can be described through a diagrammatic representation in which the types of uncertainty are ranked as given in Figure 1.4. In the next section, we focus on the modeling of data uncertainties.

Uncertainty representations

The literature offers a variety of models to represent uncertainty types. These models can be classified into two distinct categories: formal models, and practical models. Formal representations gather all the mathematical theories that require effort and time for development, they are used in particular in theoretical disciplines and in applications that relate to economy, science and engineering (e.g. [START_REF] Dubois | Formal representations of uncertainty[END_REF], [START_REF] Wierman | An introduction to the mathematics of uncertainty[END_REF]). Practical representations gather all the models that provide satisfactory representation of the uncertain data [START_REF] Halpern | Reasoning about uncertainty[END_REF]), they are used in particular in risk analysis, decision-making and management sciences, and computational and simulation community (e.g. planning and scheduling, transportation and logistics, etc.).

Each of these models is developed to represent a particular type of uncertainty. In this section, we present a brief survey of the formal and practical models of uncertainty with regard to their potential to represent each uncertainty type.

Formal uncertainty representations

The study of probability dates back to Pascal and Fermat in the 17 th century, but the complete axiomatic foundation of probability theory was given by [START_REF] Kolmogorov | Foundations of probability[END_REF]. The theory of probability is adequate to represent probabilistic uncertainty. But, the probability has two interpretations. The first interpretation of probability is the frequentist interpretation called objective probability, where the probability is the limit on the frequency of the event when the experiment is repeated many times (Bernouilli's law of large numbers).

The second interpretation of the probability is when the notion of repeatability of an experiment is excluded.

The probability is then a subjective value quantifying the belief that the expert gives to the occurrence of an event [START_REF] Ramsey | The foundations of mathematics and other logical essays[END_REF][START_REF] De Finetti | La prévision: ses lois logiques, ses sources subjectives[END_REF], [START_REF] Savage | The foundations of statistics[END_REF]).

Dempster-Shafer theory of evidence [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF] and [START_REF] Shafer | A mathematical theory of evidence[END_REF]), possibility theory has been identified as attractive alternatives to model belief when the probability distribution is not known. These theories are primarily adequate to model epistemic uncertainty. The common point between these theories is to present the uncertainty by a family of probability distributions and not by a single probability distribution since this unique probability distribution is hard to identify. Thus, the idea is to build from the available data, two functions as an envelope containing the unknown distribution. The difference between the two functions reflects the uncertainty.

The theory of evidence is considered as a generalization of the theory of subjective probabilities in that it is based on less restrictive assumptions on the measures of belief, with the idea to use the only available information to reason. It is fundamentally based on the use of the mass function (or mass distribution) and two non-additive measures, belief and plausibility functions. The belief function takes into account all the available evidence. During the same period, [START_REF] Zadeh | Fuzzy sets[END_REF] has introduced the theory of possibilities based on fuzzy set theory. Fuzzy set theory provides using necessity and possibility measures to express belief degree.

An expert may believe that a given parameter is within a certain range and may even have an intuitive feel for the best value within that range.

Uncertainty representations

For an extensive review on formal representations of uncertainty, the reader is referred to [START_REF] Dubois | Formal representations of uncertainty[END_REF].

Practical uncertainty representations

Almost all practical representations are based on scenario model. [START_REF] Rockafellar | Scenarios and policy aggregation in optimization under uncertainty[END_REF] considered scenario model as a common approach to model uncertainty in practice:" The uncertainty about parameters of the system is modeled by a small number of versions of sub-problems derived from an underlying optimization problem. These correspond to different scenarios a word that is used to suggest some kind of limited representation of information on the uncertain elements or how such information may evolve." The major motivation to choose the models based on scenarios is to get relatively a modest number of constructed representative instances so that the equivalent problem can be computationally tractable. [START_REF] Kouvelis | Robust discrete optimization and its applications[END_REF] claimed that scenario model is one of the important tools in structuring data uncertainty when multiple future alternatives are potentially realizable without any attached probabilities. The scenario model requires the construction of a set of instances or data sets containing numerical values that will represent several contrasting futures (economic, technological and business possibilities of tomorrow).

Beside the purpose of modeling future alternatives, scenario model is also suitable to model objective risk (e.g. [START_REF] Nowak | Scenario generation and forecasting[END_REF], [START_REF] Schütz | Supply chain design under uncertainty using sample average approximation and dual decomposition[END_REF]). Indeed, for the sake of simplicity, a discretization of probability distribution can lead to the construction of discrete scenarios with attached probabilities. For example, if there are three random variables with six outcomes, and the random variables are independent, we can build 6x6x6=864 scenarios with attached probabilities. To reduce the scenario tree to a manageable size, Monte Carlo simulation is commonly used. In some other situations, especially when dealing with subjective risk, it is possible to construct a tree of scenarios by eliciting expert's opinion about the future alternatives and their attached probabilities. The interval representation is also widely used in practice. It is better known as bounded uncertainty representation [START_REF] Ben-Tal | Robust solutions of linear programming problems contaminated with uncertain data[END_REF]; [START_REF] Lin | A new robust optimization approach for scheduling under uncertainty:: I. bounded uncertainty[END_REF]). The interval represents the range of all possible realizations of the uncertain data. This model is useful when only the upper and lower bounds can be determined with certainty and the decision-maker is not able to choose specific scenarios. It is a continuous set representation.

The polyhedral sets based representations also represent a practical tool to model uncertainty. The uncertain data vary within a specific set. For instance, d 0 is the nominal value of the uncertain data and Z is the user specified primitive uncertainty set:

d = d 0 + L l=1 ζ l d l : ζ ∈ Z (1.1)
The geometry of the convex set Z leads to different uncertainty sets as box set, ellipsoidal set, polyhedral set, etc. ((See [START_REF] Ben-Tal | Robust optimization[END_REF]).

The main objective of these representations is to bring back the uncertain problem into a deterministic one. The focus on polyhedral set representations is mainly related to the tractability of the mathematical models contaminated with the uncertainty of data. They do not increase the complexity of the problem i.e.

for some of the most important convex optimization problems (linear optimization particularly). For more discussions on the choice of the uncertainty sets, the reader is referred to [START_REF] Li | A comparative theoretical and computational study on robust counterpart optimization: Iii. improving the quality of robust solutions[END_REF] and [START_REF] Gorissen | A practical guide to robust optimization[END_REF].

Uncertainty representations and types relationship matrix

From the reviewed literature, we notice that each type of uncertainty (aleatory, ambiguity and vagueness) can be represented adequately with at least one formal and one practical representations (Table 1.5). Objective probability can be used to describe objective risk. For instance, it is frequent to consider that the demand uncertainty is random and to represent its probability distribution (e.g. [START_REF] Liao | A multi-objective supplier selection model under stochastic demand conditions[END_REF], [START_REF] You | Optimal distribution-inventory planning of industrial gases. ii. minlp models and algorithms for stochastic cases[END_REF], Wang et al. (2015), [START_REF] Ji | Optimal production planning for assembly systems with uncertain capacities and random demand[END_REF]).

The subjective probability, called also Bayesian probability was introduced to model subjective risk (Savage's uncertainty). For example, when managers have only some partial information about the demand distribution in addition to demand observations, they cannot consider the demand as a random variable (e.g. [START_REF] Saghafian | The newsvendor under demand ambiguity: Combining data with moment and tail information[END_REF]) but, they could assign subjective probabilities to the demand based on their beliefs. Nevertheless, the fact that additive axiom is still considered even under subjective probabilities makes this theory not really adequate for modeling belief degree [START_REF] Colyvan | Is probability the only coherent approach to uncertainty?[END_REF], [START_REF] Liu | Uncertainty theory[END_REF]). In accordance with the axiom of additivity, if we believe that demand will increase with a probability equal to 60%, we should automatically attribute a probability equal to 40% to the fact that demand will decrease even if we do not have any belief about demand decrease. When we use belief functions based on the evidence, the 60% reflects the level of belief that demand will increase, but no belief that demand will decrease is expressed thus the belief that 'demand will decrease' is equal to 0% while 40% is undecided, it may pertain to 'the demand will increase' or to 'the demand will decrease' depending on the additional evidence. Based on the belief, the plausibility that demand will increase is 100% (60% level of belief comes from the direct evidence and 40% level of belief comes from the ambiguity), and the plausibility that demand will decrease is 40%. Thus, the belief function measure is more conservative than the one obtained using the probabilistic framework.

Accordingly, the theory of evidence is suitable to model ambiguity. The theory of possibility provides the appropriate framework to model vagueness (i.e. fuzziness). For instance, an expert may believe that a given parameter is within a certain range and may even have an intuitive feel for the best value within that range. For example, if demand can be vaguely expressed in different linguistic terms like 'demand is about d m but definitely not less than d l and not greater than d u '.

Then, the demand is a fuzzy variable with triangular possibility distribution where d m is the most possible value that definitely belongs to the set of available values. Another example is when the decision maker expresses the vagueness as 'demand is much larger than d l . The reader is referred to [START_REF] Petrovic | Supply chain modelling using fuzzy sets[END_REF] for more insight on the use of fuzzy sets to model demand uncertainty.

The polyhedral sets based representations are appropriate models to represent ambiguity (Ben-Tal et al.

(2009), [START_REF] Bertsimas | Robust discrete optimization and network flows[END_REF]). Also, in the case of aleatory uncertainty, some authors claimed that there are probabilistic arguments allowing to uncertainty polyhedral sets to represent the random uncertainty (e.g. [START_REF] Bertsimas | Constructing uncertainty sets for robust linear optimization[END_REF]; [START_REF] Bandi | Tractable stochastic analysis in high dimensions via robust optimization[END_REF]).

Optimization under uncertainty: Approaches and models

Optimization is a central issue to a number of disciplines as production and logistics, engineering design, policy-making and many others. We speak about optimization under uncertainty when we have a problem involving data uncertainty with one (or more) objective(s) to optimize. The basic idea of optimization under uncertainty is to integrate the available information about the uncertain data into the optimization problem formulation in order to compute solutions that withstand the uncertainty with a performance guarantee.

The literature distinguishes mainly two optimization approaches under uncertainty: stochastic optimization where uncertainty data is assumed to follow a known probability distribution and robust optimization approach where uncertain data has an unknown probability distribution ((See [START_REF] Kouvelis | Robust discrete optimization and its applications[END_REF]). Besides, [START_REF] Sahinidis | Optimization under uncertainty: state-of-the-art and opportunities[END_REF] considered fuzzy optimization as a proactive optimization approach.

Stochastic optimization approach and models

Stochastic optimization approach assumes that the uncertainty has a probabilistic description. In the stochastic optimization, three modeling variants are studied: the stochastic recourse models without control, the controlled stochastic recourse models and the chance constrained models. Recourse models often apply to situations in which decisions are made repeatedly in essentially the same circumstances, and the goal is to compute a solution that will perform well on average. The philosophy behind recourse stochastic models is to take some actions in the first stage of optimization. Then, when a random event occurs and affects the outcome of the first-stage decision, recourse decisions can be made in the following stages as corrective actions to compensate any bad effects that might have been experienced as a result of the first-stage decision. Stochastic models with recourse are widely used in multi-stage decision problems. The most applied and studied multi-stage stochastic recourse models are the two-stage linear programs. The treatment of these models and their resolution methods can be found in [START_REF] Birge | Introduction to stochastic programming[END_REF]; [START_REF] Van Slyke | L-shaped linear programs with applications to optimal control and stochastic programming[END_REF]; [START_REF] Ruszczynski | Stochastic programming[END_REF]). [START_REF] Sahinidis | Optimization under uncertainty: state-of-the-art and opportunities[END_REF] and [START_REF] Mulvey | Robust optimization of large-scale systems[END_REF] considered that the two stage stochastic optimization model does not account for the variability of the second stage costs and might lead to solutions where the actual second-stage costs are unacceptably high. Indeed, a decision is based on a first-stage and expected second-stage costs with the assumption that the decision-maker is risk-neutral. To capture the notion of risk in stochastic optimization, [START_REF] Mulvey | Robust optimization of large-scale systems[END_REF] integrate goal optimization formulations with a scenario-based description of problem data. Their robust stochastic optimization model formalizes a way to measure the trade-off between feasibility and optimality and enforce a restricted recourse. [START_REF] Mulvey | Robust optimization of large-scale systems[END_REF] proposed the minimization of the variance of the second stage decision variables. But, the variance is a symmetric risk measure penalizing costs, both above and below the expected recourse cost equally. Besides, it made the problem non linear. Therefore, [START_REF] Vladimirou | Stochastic linear programs with restricted recourse[END_REF] restricted the dispersion of the second-stage solutions to a prescribed level while [START_REF] Ahmed | Robust process planning under uncertainty[END_REF] introduced an index that is asymmetric, which measures only costs that are higher than the expected one and insures the linearity of the problem. [START_REF] Kuhn | Primal and dual linear decision rules in stochastic and robust optimization[END_REF] and [START_REF] Georghiou | Generalized decision rule approximations for stochastic programming via liftings[END_REF] also proposed special restricted recourse to multi-stage stochastic optimization problems. In chance constrained models, the focus is put on the reliability of the constraints which is the ability to meet feasibility in an uncertain environment. This reliability is expressed as a minimum requirement on the probability of satisfying constraints. There is often uncertainty regarding the constraint matrix, and the system is required to satisfy the corresponding constraint with a fixed probability ((See [START_REF] Charnes | Chance-constrained programming[END_REF], [START_REF] Kall | Chance constrained programming[END_REF]).

Robust optimization approach and models

In the robust optimization approach, the uncertainty model is not stochastic, but rather deterministic and set-based. The objective of robust models is to provide solutions that are feasible for all the realizations of the uncertain data, and that perform well in the worse-case. They use min-max and min-max regret objectives that were originally defined in the strategic decision-making literature by [START_REF] Gupta | Robustness in sequential investment decisions[END_REF], Rosenhead et al. (1972a), and introduced later in operations research problems by [START_REF] Rosenblatt | A robustness approach to facilities design[END_REF]. But, the issue of robustness can be historically traced back to robust control concepts developed in the early 30s by Bode and others, in the context of feedback amplifiers. The robust control policy is static rather than adapting to measurements of variations, the controller is designed to work assuming that variables are uncertain but bounded. Questions such as the stability margin, which is the amount of feedback gain required to destabilize a controlled system, led naturally to a "worst-case" point of view, in which bad parameter values are too dangerous to be allowed, even with low probability.

The robust optimization models date back to [START_REF] Soyster | Convex programming with set-inclusive constraints and applications to inexact linear programming[END_REF]. But, the large part of robust optimization literature has been developed since the publication of the works of [START_REF] Mulvey | Robust optimization of large-scale systems[END_REF]; [START_REF] Kouvelis | Robust discrete optimization and its applications[END_REF]; Ben-Tal and [START_REF] Ben-Tal | Robust convex optimization[END_REF][START_REF] El Ghaoui | Robust solutions to uncertain semidefinite programs[END_REF] in the late 1990's. Those works have developed many min-max and min-max regret models along with tractable solving techniques for both practical and polyhedral set uncertainty representations, especially in linear cases. This has made robust models computationally more attractive than stochastic models ((See Ben-Tal et al. (2009), [START_REF] Bertsimas | The price of robustness[END_REF], [START_REF] Averbakh | The minmax regret permutation flow-shop problem with two jobs[END_REF]). The basic robust optimization approach paradigm was based on three assumptions formulated in [START_REF] Ben-Tal | Robust optimization[END_REF]. First, all variables should have values as a result of solving the problem before the actual data reveals itself. Secondly, the decision maker is fully responsible for the consequences of the decisions to be made when, and only when, the actual data are within the pre-specified uncertainty set. And finally, the constraints of the uncertain problem in question are hard i.e., the decision maker cannot tolerate violations of constraints when the data are in the pre-specified uncertainty set. Robust models deal with hard constraints that cannot be relaxed while stochastic models deal with soft constraints since we can tolerate the infeasibility of some constraints in the first optimization stage ((See [START_REF] Mulvey | Robust optimization of large-scale systems[END_REF]; [START_REF] Kouvelis | Robust discrete optimization and its applications[END_REF]; [START_REF] Ben-Tal | Robust optimization[END_REF]; [START_REF] Bertsimas | Theory and applications of robust optimization[END_REF]. But, in the recent development of robust optimization models, the multi-stages notion has been introduced to robust optimization. Therefore, the first assumption has been relaxed: the first-stage decisions are made before the uncertainty is revealed and the second stage decisions can be adjusted later according to the actual data. Robust optimization was extended to a multi-stage setting and to random data sets, where the recourse decisions are adapted to the realization of the random data as they unfold in stages. [START_REF] Nemirovski | Robust stochastic approximation approach to stochastic programming[END_REF] proposed to restrict the recourse decisions to be affine dependent on the random parameters. This approach could perform reasonably well and even achieve optimality ((See for example, [START_REF] Bertsimas | Optimality of affine policies in multistage robust optimization[END_REF] and [START_REF] Iancu | Pareto efficiency in robust optimization[END_REF]). The robust discrete optimization, introduced by [START_REF] Mulvey | Robust optimization of large-scale systems[END_REF]; [START_REF] Kouvelis | Robust discrete optimization and its applications[END_REF], is a framework of robust optimization under which the uncertainty representation is scenario based. It has been applied as a way of self-protection in many industrial applications against undesirable impacts due to uncertain data. Decisions made according to min-max, min-max regret are the most used whenever the uncertain data are modeled using discrete scenarios.

Fuzzy optimization approach and models

Fuzzy optimization approach dates back to the seminal work by [START_REF] Bellman | Decision-making in a fuzzy environment[END_REF] who founded the basis of decision-making in a fuzzy environment. The spread of fuzzy optimization models dates back to [START_REF] Zimmermann | Fuzzy programming and linear programming with several objective functions[END_REF][START_REF] Zimmermann | Fuzzy set theory[END_REF]. Fuzzy optimization models are useful when the problems under consideration include vaguely defined relationships, or human evaluations [START_REF] Kacprzyk | Optimization models using fuzzy sets and possibility theory[END_REF]. In these models, uncertain data are considered as fuzzy numbers and constraints are treated as fuzzy sets. The degree of satisfaction of a constraint is defined as the membership function of the constraint and some constraint violation is allowed. Objective functions in fuzzy optimization are treated as constraints. The membership function is used to represent the degree of satisfaction of constraints, the decision-maker expectations about the objective function level, and the range of uncertainty of data. Flexible optimization models and possibilistic optimization models are two variants of fuzzy optimization. The former considers uncertainty only in the constraint coefficients while the second recognizes uncertainties in the objective function coefficients as well as in constraint coefficients. For a comprehensive review on fuzzy optimization, the reader is referred to [START_REF] Sahinidis | Optimization under uncertainty: state-of-the-art and opportunities[END_REF] and [START_REF] Lodwick | Introduction to Fuzzy and Possibilistic Optimization[END_REF].

In the next section we propose a general methodology for optimization under data uncertainty. In this methodology, we introduce a global reasoning under data uncertainty.

A general framework for optimization under data uncertainty

The general framework for optimization under data uncertainty can be described through five major steps ((See Figure 1.6):

Step 1 (COLLECT AND ANALYZE) aims to collect and analyze the available knowledge about the uncertain data based on existing databases and expert opinions.

Step 2 (TYPIFY) aims to the identification of the uncertainty type and level dealt with based on the analysis of the available knowledge about the uncertain data. And, Step 3 (REPRESENT UNCERTAINTY)

aims to represent the uncertain data based on the analysis and typification. In steps 2 and 3, we can be aided by the unified taxonomy given in Figure 1.3 and the adequacy matrix between uncertainty types and uncertainty representations provided in Table 1.5. • Deterministic optimization approach when one considers that the data is certain (L0)

• Sensitivity analysis when we are certain but to go further we analyse the sensitivity of the deterministic solution under small variations of data (complementary to the deterministic approach under L0).

• Proactive optimization approaches where we anticipate known uncertainties (Stochastic for L1 and L2, Robust for L3 and Fuzzy for L4).

• And online optimization approaches under unknowns, here the decision is constructed in a dynamic way as the unknown data become known (under L5).

Step 5 (VERIFY) aims to verify of the adequacy between the optimization approach and the uncertainty type-level ((See Figure 1.5). And finally, Step 6 (MODEL AND SOLVE), in this step the choice of the optimization model is related to two components: the objective and the uncertainty type (objective risk, subjective risk, ambiguity, fuzziness). The review of the optimization approaches and models in Section1.4 reveals 5 distinct objectives. Under these objectives the decision-maker aims to provide:

-A solution that insures a reliability over a given threshold or, -A solution that performs well on average, without control of the corrective actions or, -A solution that performs well on average, with control of the corrective actions or, -A solution that performs well in the worst-case or, -A solution to adapt in case conditions change or, -A solution that satisfies fuzzy constraints.

Therefore, the existing optimization models can be classified as follows:

• Chance constrained models to deal with risk whenever the objective is to provide a reliable solution.

• Stochastic recourse models to deal with the aleatory uncertainty whenever the objective is to come up with a solution that perform well in average without any control of the corrective actions.

• Stochastic models with restricted recourse to deal with risk whenever the objective is to come up with a solution that perform well on average with control of the corrective actions.

• Robust stochastic models to deal with risk whenever the objective is to come up with a solution that perform well in the worst-case.

• Robust static models to deal with ambiguity whenever the objective is to come up with a solution that perform well in the worst-case without any changes.

• Robust adjustable models to deal with ambiguity whenever the objective is to come up with a solution that perform well in the worst-case and prepare to adapt in case conditions change.

• Fuzzy models to deal with vagueness and to come up with a solution that satisfies fuzzy (imprecise) constraints.

For each model or formulation, there exists prescribed rules for resolution that are developed in the literature.

The last step is STEP 7 (ANALYZE), it is common to all optimization problems and it aims to analyze the results, to test their applicability.

Conclusion

In this chapter, we reviewed some conceptual classifications of uncertainty based on two dimensions: the type and the level of uncertainty. We showed through the discussed taxonomies that a consensus about uncertainty types exists between different communities. Besides, we showed that the type and the level dimensions are linked. Therefore, we proposed a unified taxonomy of uncertainty according to a type-level dimension. In this taxonomy we distinguished four uncertainty types which are: the objective risk, the subjective risk, the ambiguity and the vagueness. Each uncertainty type reflects an uncertainty level. Besides, we reviewed the models developed by the mathematical community in order to represent the different uncertainty types and we classify these models according to their potential to represent the uncertainty types. Then, we addressed the mathematical approaches and models to formulate and solve a decision problem under uncertainty. We identified the main objectives in optimization under uncertainty and proposed to classify the optimization models under uncertainty, according to these objectives and to the uncertainty types. The organization of these informations built the general methodology for optimization under uncertainty.

In the next chapter, we will focus on scheduling under uncertainty. We aim to review how uncertainty is considered in scheduling problems, what are the approaches and the objectives of scheduling under uncertainty.

Chapter 2

Robustness and Stability in scheduling under uncertainty

Abstract: The goal of this chapter is to provide an overview of the state of the art in scheduling under uncertainty. We present the general form of the scheduling problem and define its fundamental notions. We discuss the limitations of the classical scheduling approach under uncertainty and disruptions. Furthermore, we review the representations of the uncertainties or disruptions faced in scheduling and we survey the existing approaches to deal with them. Then, we focus on robustness and stability issues in scheduling under uncertainty. We survey the existing contributions in robust scheduling, and scheduling for stability purpose.

In light of this, we show that there exist a lot of opportunities for future works in this area.

Introduction

Scheduling is an optimization problem that aims to allocate resources to jobs over time in order to optimize one or more objectives under given constraints [START_REF] Pinedo | Scheduling: theory, algorithms, and systems[END_REF]). A large variety of algorithms -exact or approximate-are designed to solve scheduling problems, but the vast majority of these algorithms is based on the assumption of a predictable environment where information about data are complete and are not subject to change. They generate a predictive schedule, assuming a deterministic, certain and static environment.

However, manufacturing environments are subject to numerous sources of uncertainty as demand and cost fluctuations, process variability, resources reliability/availability, etc.. Under these uncertainties, an optimal predictive schedule with respect to the deterministic model and the initial data will turn to be suboptimal or infeasible during the execution. Therefore, an increasing attention was paid to scheduling problems under uncertainty in both academic and industrial research areas. The objective is to provide robust solutions that schedule jobs in such a way as to use the resources efficiently under uncertain processing times.

In this chapter, we review the existing approaches to deal with uncertainty in scheduling, and we focus on the proactive scheduling approach. We survey approaches and models to provide the robustness and the stability.

Scheduling Generalities

General form of the scheduling problem

Scheduling is an optimization problem that aims to allocate and sequence jobs on resources over time in order to optimize one or more objectives under given constraints. In its most general form, the scheduling problem is defined as follows:

Given -a set J of n jobs that must be executed, -a set M of m resources to process the activities, -a set of constraints which must be satisfied, and -a set of objectives to judge a schedule's performance, what is the best way to assign and sequence the jobs on the resources over time such that all of the constraints are satisfied and the best performance is reached?

A job j ∈ J consists of a number of tasks. If a job j is composed of only one task, then we denote p j the processing requirement of j. Furthermore, a job may have a release date r j on which the job became available for processing, a due date d j which is the date in which the job is promised to be finished, a starting time s j which is the effective date in which a job starts its processing and a completion time c j , which is the date at which the processing of the job is finished. If the different jobs have priorities, a weight w j can be associated with each job to reflect the priority. Any job may require a single resource or a set of resources.

A resource i ∈ M is an equipment, an operator or a financial capital. A resource i may be renewable or non-renewable. Renewable resources are available at each period without being depleted (e.g. labor and many types of equipment). Non-renewable resources are depleted as they are used (e.g. capital and raw materials). The resource usage may vary over the duration of the job depending on the characteristics of jobs. Some jobs, once begun, may not be interrupted until completion. Alternatively, some jobs may be interrupted at any time, possibly with some corresponding cost. Job and resource characteristics will define the constraints of the scheduling problem. Thus, constraints are often task-based and/or resource-based.

The constraints define the feasibility of a schedule while the objectives define the optimality of a schedule. Objectives should be optimized while constraints must be satisfied. The objectives often relate to performance measures called criteria. The criteria that are commonly used are related to time, resource usage, or to costs induced by the schedule.

A feasible schedule satisfies all of the constraints. An optimal schedule not only satisfies all of the constraints, but also has the best performance measure over all the feasible schedules. Schedules may be represented by Gantt charts. In scheduling, Gantt charts are often machine-oriented (Figure 2.1).

M 1 J 1 J 2 J 3 M 2 J 4 M 3 J 2 J 4 FIGURE 2.1: A machine oriented Gantt chart

Graham notation and problem classification under certainty

The theory of scheduling is characterized by an unlimited number of problems (see e.g. Błażewicz et al.

(2012), Pinedo ( 2012)). To classify deterministic scheduling problems under certainty, [START_REF] Graham | Optimization and approximation in deterministic sequencing and scheduling: a survey[END_REF] proposed a three-field notation α|β|γ where α describes the machine environment, β describes the job characteristics and γ describes the optimality criteria. This classification is widely used in the literature.

Machine environment: The machine environment is characterized by the field α which is composed of two parameters α 1 and α 2 . α 1 describes the machine environment, it can be ∅, P, Q, R, F, J, O.

If α 1 = ∅, then all jobs are processed on a single machine.

If α 1 ∈ {P, Q, R}, then we have parallel machines, i.e. , each job can be processed on each of the machines. If α 1 = P , then the parallel machines are identical parallel machines. Thus the processing time of job j on machine i is the same for all machines p ij = p j . If α 1 = Q, then the parallel machines are uniform parallel machines, i.e. p ij = p j /v i where v i is the speed of machine i. Finally, if α 1 = R, then the parallel machines are unrelated parallel machines, i.e. p ij = p j /v ij where v ij is job dependent speeds of machine i. Parallel machine problems are considered as a generalization of single machine problems.

If α 1 ∈ {F, J, O}, then we have multi-task models. Non-renewable resources are depleted as they are used (e.g. capital and raw materials). When α 1 = F , we deal with a flow shop, it means that the order of execution on different machines is the same for all jobs. We determine a job shop problem by α 1 = J, in Chapter 2. Robustness and Stability in scheduling under uncertainty this configuration each job has its own order. Finally, α 1 = O is used for open shop problem where the order of execution on the machines is totally free. α 2 denotes the number of machines if it is a positive integer. If α 2 = m then m is an arbitrary but fixed number. Whereas, if the field α 2 is empty, the number of machines is arbitrary.

Job characteristics

The field β describes the job and machine characteristics, it often describes the constraints of the scheduling problem. β may be composed of many sub-fields, for instance:

If β 1 = Split, the jobs can be split into independent tasks, and the task can be processed with allowed parallelism. If β 1 = pmtn: the processing of a job can be interrupted and later resumed (on the same or on another machine). A job may be interrupted several times. But, the parts of the same job cannot be processed in parallel.

If β 2 = prec, then precedence constraints exist between jobs. Certain jobs must be completed before another job can be started.

If β 3 = r i , then release date may be specified for each job.

Similarly, if β 4 = d i , then a deadline d i is imposed for each job. When the completion time of a job exceeds its due date, the job is late.

We notice that when there are no constraints related to a sub-field β k , this sub-field simply does not appear in the notation.

Optimality criteria The field γ describes the optimality criteria. There exist essentially two types of cost functions (criteria), γ = f max called bottleneck objectives and γ = j f i called sum objectives. The most common criteria used through literature are :

• the makespan max j c j which is the maximal completion time over jobs, γ is denoted C max ,

• the total flow time where γ = j c j and the weighted total flow time written as γ = j w j c j .

• and the criteria depending on due dates such as the maximal tardiness T max = max j max{0, c j -dj}, and the maximal lateness L max = max j {c j -dj}.

In these cases, we write respectively, γ = T max and γ = L max . The total number of late jobs is also widely considered, in this case:

U j =    1 if j is late 0 otherwise and γ = j U j
Examples: To illustrate the three field notation of Graham, we present some examples.

-1|| c j : total flow time minimization on a single machine, and 1|| w j c j weighted total flow time minimization on a single machine -F 2||C max : makespan minimization in 2-machine flow shop.

-Rm|Split|C max : makespan minimization on m unrelated parallel machines with splitting, and Rm|pmtn|C max : makespan minimization on m unrelated parallel machines with preemptive jobs.

The limits of classical scheduling approach under uncertainty

The classical approach in scheduling relies on one typical instance called the nominal instance, under which the problem data are assumed to be completely known in advance (during the generation of the schedule) and to be constant (during the execution of the schedule). The schedule performance is optimized and evaluated only with respect to the nominal instance. The resulting schedule is called the predictive schedule. Unfortunately, scheduling is recognized to be a complex and dynamic activity in which job processing times can take longer or shorter than forecast, release dates and due dates may change, jobs may have to be inserted or canceled. Besides, the resources may become unavailable due to unforeseen events as breakdowns, accidents, operator absenteeism, etc.. Assuming a certain data and a static environment makes the classical scheduling approach inadequate in modeling and solving scheduling problems under uncertainties or disruptions. As it was emphasized in several publications, ignoring uncertainties and disruptions can lead to:

• infeasible schedules when the uncertainties or the disruptions modify the constraints of the problem, thus the computed schedule no longer respect the constraints of the real problem,

• sub-optimal schedules when the computed schedule is still feasible, but its performance is affected,

• and unstable schedules when the frequent adjustments to restore the schedule feasibility highly modify the assignment and the sequence which leads to many re-configurations and adjustment efforts. [START_REF] Vieira | Rescheduling manufacturing systems: a framework of strategies, policies, and methods[END_REF] has pointed out that these aspects are known as nervousness syndromes.

Therefore, practically speaking, computing an optimal schedule is often less important than protecting the schedule from uncertainties and disruptions. For these reasons, the issue of scheduling under uncertainty have received a lot of attention from both academic and industrial communities.

In the next section, we focus on scheduling under data uncertainty. We survey the uncertainty types and disruptions besides their representations. Then, we review the scheduling approaches under uncertainties and disruptions. Finally, we focus on the different objectives used through literature to protect a schedule from the negative effects of uncertainties and disruptions.

Scheduling under data uncertainties and disruptions 2.2.1 Uncertainties and disruptions in scheduling

Uncertainties concern job data whose exact values cannot be predetermined with accuracy. The most faced are: processing time uncertainties (e.g. Daniels and Kouvelis (1995a), [START_REF] Kouvelis | Robust scheduling of a two-machine flow shop with uncertain processing times[END_REF], [START_REF] Petrovic | Fuzzy job shop scheduling with lot-sizing[END_REF], [START_REF] Rahmani | Robust and stable flow shop scheduling with unexpected arrivals of new jobs and uncertain processing times[END_REF]), due date uncertainties (e.g. [START_REF] Aissi | Minimizing the number of late jobs on a single machine under due date uncertainty[END_REF], Kasperski and Zieliński (2016), [START_REF] Ebrahimi | Hybrid flow shop scheduling with sequence dependent family setup time and uncertain due dates[END_REF]), and release date uncertainties [START_REF] Lai | Sequencing with uncertain numerical data for makespan minimisation[END_REF] Abumaizar and Svestka (1997), [START_REF] Jain | Production scheduling/rescheduling in flexible manufacturing[END_REF], [START_REF] Wang | Multi-priority online scheduling with cancellations[END_REF], [START_REF] Rao | Rescheduling activities in face of disruption in house hold goods manufacturing supply chain[END_REF]) and rush orders (e.g. [START_REF] Jain | Production scheduling/rescheduling in flexible manufacturing[END_REF]). In the scheduling community, it makes sense to distinguish disruptions from uncertainty, but for modelers, the treatment of disruptions is quite similar to the treatment of uncertainties (we will show later that disruptions are considered as aleatory uncertainties in the modeling step).

The uncertainties and disruptions in scheduling could be divided into known In scheduling problems, the practical representation have more spread than the formal representations.

Under aleatory uncertainty/disruption, it is usual to construct scenarios with attached probabilities in order to represent the random parameters. And when these probabilities are unknown i.e. under ambiguity, the discrete scenario and interval representations are widely used to model the uncertain parameters. Moreover, to describe fuzzy parameters, it is frequent to use fuzzy intervals.

Scheduling approaches under uncertainties and disruptions

To deal with uncertainties and disruptions in scheduling, there are basically two approaches: proactive scheduling approach and reactive scheduling approach (see [START_REF] Beck | A survey of techniques for scheduling with uncertainty[END_REF], Herroelen andLeus (2004b) Herroelen andLeus (2005), [START_REF] Billaut | Flexibility and Robustness in Scheduling[END_REF], [START_REF] Ouelhadj | A survey of dynamic scheduling in manufacturing systems[END_REF]).

Proactive approach algorithms anticipate the uncertainties and the disruptions in order to generate solutions whose performances (or structures) are insensitive to the potential realization of data (see the illustration in Figure 2.2), while reactive approach algorithms respond once the uncertainties are revealed (or the disruptions occur) in order to build a new schedule or to adjust an existing schedule. In completely reactive scheduling, the scheduling will generate a response to the uncertainty or the disruptions in real time (see the illustration in Figure 2.3). But, the totally reactive scheduling in real time can also result in greater cost and lower performance as explained in [START_REF] He | Scheduling flexible job shop problem subject to machine breakdown with route changing and right-shift strategies[END_REF]. The proactive approach is extensively studied since it allows the anticipation of the uncertainty and the generation of baseline schedules that does not need The reader is referred to Mehta and Uzsoy (1998), [START_REF] Herroelen | Project scheduling under uncertainty: Survey and research potentials[END_REF], and Aytug et al. (2005b) for extended discussion of the proactive scheduling approach advantages. The proactive approach is suitable to deal with known uncertainties and known disruptions as explained in Chapter 1. Based on the uncertainty or disruption representations, we can distinguish: stochastic scheduling under probabilistic representations of uncertain data [START_REF] Pinedo | Scheduling: theory, algorithms, and systems[END_REF]), robust scheduling under set representations of uncertain data [START_REF] Kouvelis | Robust discrete optimization and its applications[END_REF]), and fuzzy scheduling under fuzzy representation of uncertain data [START_REF] Dubois | Fuzzy scheduling: Modelling flexible constraints vs. coping with incomplete knowledge[END_REF]).

Chapter 2. Robustness and Stability in scheduling under uncertainty

According to [START_REF] Moukrim | Parallel machine scheduling with uncertain communication delays[END_REF], an algorithm is proactive (off-line) if the schedule is determined before the execution begins.

In the reactive scheduling approach, uncertainties and disruptions are not anticipated because they are often unknowns due to the dynamic of the environment. Consequently, the schedule is built in a reactive way during the execution. Reactive scheduling is also called on-line scheduling. According to [START_REF] Moukrim | Parallel machine scheduling with uncertain communication delays[END_REF], an algorithm is reactive (on-line) if the schedule is built during the execution. Decision-makers consider that a baseline schedule should coordinate activities to increase the productivity and reduce the operating costs. In dynamic environments, scheduling algorithms should also react quickly to unexpected events and repair the baseline schedules. Therefore, decision-maker may opt for hybrid scheduling approaches. The hybrid approaches are necessary composed of two steps:

• Step 1: in the off-line phase, we compute a baseline schedule that will serve as a starting point of coordination between the production and the supporting activities.

•

Step 2: in the on-line phase, we react to new data and disruptions and repair the baseline schedule.

Hybrid approaches could be divided into two sub-approaches: the predictive reactive approach (see the illustration in figure 2.4) and the proactive-reactive approach (see the illustration in figure 2.5). The distinction is related to the model used to compute the baseline schedule:

If the baseline schedule is computed using a deterministic algorithm that considers an instance of reference (nominal scenario), then the approach is predictive-reactive.

If the baseline schedule is computed using a proactive model (robust, stochastic, fuzzy) in which we take into account not only an instance, but a set of uncertainties, then the approach is proactive-reactive. An example of the application of such approach is given in the case of parallel machines with communication delays.

When some activities are realized, the decision-maker will have more reliable information which may be used reactively to make the necessary adjustments. The reactive strategy should use fast polynomial-time algorithms. [START_REF] Vieira | Rescheduling manufacturing systems: a framework of strategies, policies, and methods[END_REF] have defined rescheduling as the process of updating an existing schedule baseline in response to disruptions or uncertainties. Therefore, the predictive-reactive and proactive-reactive approaches can be viewed as a rescheduling process.

Scheduling objectives under uncertainty and disruptions: robustness and flexibility

Under uncertainties and disruptions, the decision-maker can be interested in computing a set of solutions that adapt well and that offer a freedom during the execution phase, or he/she can be interested on computing a solution that withstand a set of known uncertainties or disruptions without any change (or little changes)

during the execution phase. In the former case, the objective is the flexibility of the schedule, while in the second the objective is the robustness of the schedule.

Flexibility refers to a degree of freedom available during the execution phase [START_REF] Billaut | Flexibility and Robustness in Scheduling[END_REF]).

It can be temporal (i.e. regarding the starting times of jobs), or sequential (i.e. regarding the sequence in which the jobs are sequenced), or a flexibility of assignment (i.e. regarding the machines that execute jobs). Given that disruptions will occur and unforeseen circumstances arise, the aim is to propose one or more solutions that adapt well to disruptions and then produce reactive decisions with fast implementation.

Robustness refers to the aptitude of a solution to withstand areas of ignorance, and to provide protection against deplorable impacts, such as results that are much worse than expected [START_REF] Roy | Robustness in operational research and decision aiding: A multi-faceted issue[END_REF]. A robust schedule is a proactive schedule that is able to absorb some level of unexpected events without rescheduling [START_REF] Herroelen | Project scheduling under uncertainty: Survey and research potentials[END_REF]). A robust schedule is often calculated by anticipating uncertainty and optimizing robustness measures that are often related to the schedule performance. There exists also a range of techniques for generating robust schedules based on the insertion of temporal protection (see slack based techniques in [START_REF] Gao | Building robust schedules using temporal protection: an empirical study of constraint based scheduling under machine failure uncertainty[END_REF], [START_REF] Davenport | Slack-based techniques for robust schedules[END_REF]).

In the scheduling literature, we can distinguish two kinds of robustness: the robustness of the performance and the robustness of the structure. A robust schedule according to its performance is a schedule whose performance is insensitive to the data uncertainty and does not significantly degrade under disruptions. A robust schedule according to its structure is commonly known as stable schedule. The structure stability is commonly referred to as stability and it is defined as the aptitude of a solution to stay close to the solution of reference if small perturbations of data occur [START_REF] Leus | Stability and resource allocation in project planning[END_REF]). A stable schedule is a schedule whose realization does not deviate much from the schedule of reference under disruptions, and this deviation concerns the difference between the schedule of reference and the realized schedule themselves in term of structure rather than performance [START_REF] Sabuncuoglu | Hedging production schedules against uncertainty in manufacturing environment with a review of robustness and stability research[END_REF]. A stable schedule can be obtained by optimizing stability measures. When the robustness concerns a performance, the robust schedule is usually a proactive schedule computed according to robust optimization models and it does not need to be repaired to meet the realizations of uncertain data. When robustness concerns the structure of the solution, the stability models always require the computation of a reference solution. The stability measures are relative to the job characteristics of this solution. In addition, the stability can be deployed under different approaches: proactive, predictive-reactive, proactive-reactive, and post-optimization. When the solution of reference is deterministic and the stability is optimized off-line by anticipating the uncertainties that could occur, the stability is deployed under a proactive approach. But when the solution of reference is deterministic and the stability is optimized on-line in response to an uncertainty or a disruption that occurs, the stability is then deployed under a predictive-reactive approach. Under both proactive and predictive-reactive approaches, the stability and the performance are conflicting objectives: the optimization of the stability measures leads to the degradation of the schedule performances (e.g. Jorge [START_REF] Leon | Robustness measures and robust scheduling for job shops[END_REF]; Sabuncuoglu

and Goren ( 2009)). Therefore, most of the studies that belong to this class propose a bi-objective function to optimize the schedule stability without loss of performance. To anticipate the loss of performance, the stability could also be deployed under a proactive-reactive approach by computing a robust solution of reference and optimizing the stability to make few adjustments on-line. The stability as a post-optimization approach was introduced by [START_REF] Sotskov | Stability of an optimal schedule[END_REF]. Under this approach, an optimal solution of reference is computed in a deterministic way and its stability is evaluated ex-post like in sensitivity analysis. The research question is formulated around how one can vary the data in the problem in such a way that an optimal schedule remains optimal. The answer conducts to the calculation of the stability radius of an optimal schedule which is the largest quantity of independent data variations under which an optimal schedule remains optimal.

In the next section, we will review the works dealing with uncertainties and disruptions through robustness and stability models.

Literature review on robustness in scheduling 2.3.1 Performance robustness optimization

The worst-case performance and the maximum regret are reference criteria and starting point in robustness analysis. The best worst-case performance and the best maximal regret refer respectively to min-max and min-max regret objectives that were originally defined in the strategic decision-making literature by [START_REF] Gupta | Robustness in sequential investment decisions[END_REF]; Rosenhead et al. (1972b), and that were introduced later in operations research problems by [START_REF] Rosenblatt | A robustness approach to facilities design[END_REF].

Under discrete scenario representation, [START_REF] Kouvelis | Robust discrete optimization and its applications[END_REF] define the worst-case performance and the maximal regret as follows:

• S is the set of discrete scenarios that represent the uncertainty,

• X is a feasible solution,

• Z s * is the optimal performance criterion under scenario s ∈ S,

• Z s (X) is the performance criterion when solution X is applied to scenario s ∈ S.

The worst-case performance of solution X is given in Equation 2.1 as

Z w (X) = max s∈S {Z s (X)}. (2.1)
And the maximum regret of solution X is given in equation Equation 2.2 as

Z r (X) = max s∈S {Z s (X) -Z s * }. (2.
2)

The worst-case performance of a given solution over all the scenarios measures the maximal cost of this solution. The worst-case performance is often used for non-repetitive decisions, in environments where protection measures are indispensable. The maximum regret measures the maximal deviation from the optimal performance over all the discrete scenarios when we use a solution instead of the optimal one. The maximal regret is more suitable in situations where the magnitude of deviations varies strongly among the scenarios.

In other words, minimizing the worst-case performance aims to find the cheapest schedule, while minimizing the maximal regret aims is to reduce the opportunity loss, rather than the cost.

The worst-case performance and the maximal regret measures have been used to compute robust schedules under discrete scenario representation of uncertain processing times in different machine environment studies and with various scheduling criteria.

For many polynomial solvable scheduling problems, their corresponding robust versions (min-max or min-max regret) are weakly or strongly NP-hard when taking into account the uncertainty, even in the case of the single machine (Table 2.1). For the sake of simplicity, we propose to use a short notation that combines the notations of [START_REF] Averbakh | The minmax regret permutation flow-shop problem with two jobs[END_REF], and [START_REF] Aloulou | Complexity of single machine scheduling problems under scenario-based uncertainty[END_REF] NP-hard even if there are two scenarios. [START_REF] Kouvelis | Robust scheduling of a two-machine flow shop with uncertain processing times[END_REF] considered the two machines permutation flow shop problem with makespan minimization under uncertain processing times. F 2||C max is is known to be polynomially solvable by using Johnson's algorithm. [START_REF] Kouvelis | Robust scheduling of a two-machine flow shop with uncertain processing times[END_REF] showed that the minimization of the maximal regret in makespan of two machine permutation flow shop under uncertain processing times, DmMR(F 2||C max ; p j ), is weakly-NP-hard. For the same scheduling problem, [START_REF] Kasperski | Approximating a two-machine flow shop scheduling under discrete scenario uncertainty[END_REF] has shown later that DmM(F 2||C max ; p j ) and the DmMR(F 2||C max ; p j ) are strongly NP-hard even for two scenarios.

Other uncertainties were considered in scheduling problems as due dates (d j ), release dates (r j ) and job priorities (w j ). [START_REF] Aloulou | Complexity of single machine scheduling problems under scenario-based uncertainty[END_REF] proved that DmM(1|prec|f max ; d j ) can be optimally solved in polynomial time by means of Lawler's algorithm applied to the worst-case artificial scenario under which all the processing times take their maximal values. They proved that DmM(1|prec|f max ; d j , pj) is solved to optimality in polynomial time by the MinMax-Lawler algorithm. Besides, they showed that the minimization of the number of late jobs on a single machine when the processing times are certain and due dates are uncertain, DmM(1|| U j ; d j ), can be optimally solved by means of Moore's modified algorithm applied to the worst-case artificial scenario s max under two due date scenarios. For a variable number of scenarios and two distinct due dates over all scenarios, the problem is NP-hard in the strong sense and non-approximable in pseudo-polynomial time with approximation ratio less than 2 according to [START_REF] Aissi | Minimizing the number of late jobs on a single machine under due date uncertainty[END_REF]. It is polynomially solvable if the number of scenarios and the number of distinct due dates over all scenarios are given constants. When the job weights are uncertain, [START_REF] Aloulou | Complexity of single machine scheduling problems under scenario-based uncertainty[END_REF] proved that the minimization of the total weighted flow time in single machine DmM(1|| w j c j ; w j ) is NP-hard even if the number of scenarios equals 2 and the processing time of each job equals the unit. The minimization of the weighted sum of late jobs under uncertain weights is known to be NP-hard for two weight scenarios, strongly NP-hard and hard to approximate within any constant factor if the number of weighted scenarios is a part of the input (The reader is referred to Kasperski and Zieliński (2014)).

When we consider the interval representation of uncertain parameters as an extension of discrete scenario representation where the number of scenarios is infinite, we could also focus on the following studies. [START_REF] Kasperski | Minimizing maximal regret in the single machine sequencing problem with maximum lateness criterion[END_REF] have considered the single machine sequencing problem with maximum lateness criterion where the parameters are uncertain and belong to intervals. He has shown that the IMm(1|prec|L max ; p j , d j )

is polynomial. [START_REF] Lebedev | Complexity of minimizing the total flow time with interval data and minmax regret criterion[END_REF] have proved that the min-max regret version of under uncertain processing times that belong to intervals, i.e. ImM((1|| c j ; p j ) is NP-hard. They showed that in the case where all intervals of uncertainty have the same center, the problem can be solved in polynomial time if the number of jobs is even, and is NP-hard if the number of jobs is odd. [START_REF] Kasperski | A 2-approximation algorithm for interval data minmax regret sequencing problems with the total flow time criterion[END_REF] considered the general ImMR(1|prec| c j ; p j ), which is total flow time minimization with precedence constraints, under uncertain processing times. The general deterministic problem is strongly NP-hard [START_REF] Lenstra | Complexity of scheduling under precedence constraints[END_REF]). [START_REF] Kasperski | A 2-approximation algorithm for interval data minmax regret sequencing problems with the total flow time criterion[END_REF] proved that the optimal schedule under the midpoint scenario is a 2-approximation for ImMR(1|prec| c j ; p j ). Conde (2010) developed a 2-approximation method for min-max regret optimization problems which extends the work of [START_REF] Kasperski | A 2-approximation algorithm for interval data minmax regret sequencing problems with the total flow time criterion[END_REF] from finite to compact constraint sets. [START_REF] Pereira | The robust (minmax regret) single machine scheduling with interval processing times and total weighted completion time objective[END_REF] considered the single machine sequencing problem with total weighted flow time under interval processing times. He showed thatImMR(1|| w j c j ; p j ) is NP-hard and presented an exact branch-and-bound method to solve the problem. [START_REF] Conde | A mip formulation for the minmax regret total completion time in scheduling with unrelated parallel machines[END_REF] has proposed a Mixed Integer Programming formulation of the unrelated parallel machine with total flow criterion under uncertain processing times. Each processing time belongs to a known interval. In this context, they showed that the problem is NP-hard and considered that an optimal solution of ImMR(Rm/sumc j ; p j ) is a suitable approximation to the optimal schedule under an arbitrary choice of the possible processing times. Siepak and Józefczyk (2014) also the same problem. They proposed a simple 2-approximate middle interval time efficient algorithm besides a scatter search based heuristic algorithm. They showed via experiments that this latter is more time consuming, but it is better in terms of the quality of solutions. [START_REF] Xu | Robust makespan minimisation in identical parallel machine scheduling problem with interval data[END_REF] addressed the min-max regret version of the makespan minimization on identical parallel machines under interval processing times. They showed that ImMR(P m||C max ; p j ) is NP-hard and they proved that a regretmaximizing scenario for any schedule belongs to a finite set of extreme point scenarios. Then they derived two exact algorithms using a general iterative relaxation procedure. [START_REF] Xu | Hedge against total flow time uncertainty of the uniform parallel machine scheduling problem with interval data[END_REF] considered the total flow time minimization on uniform parallel machines under interval processing times. They proved that the optimal schedule under the midpoint scenario is a 2-approximation for the ImMR(Qm|| c j ; p j ). Drwal and Rischke (2016) showed that the ImMR(P m|| c j , p j ) is strongly NP-hard. [START_REF] Cwik | Evolutionary algorithm for minmax regret flow-shop problem[END_REF] considered the makespsan minimization in a flow-shop problem with interval processing times. The maximal regret is used to evaluate a solution which gives the min-max regret binary optimization problem.

They proposed an evolutionary heuristic solution algorithm to solve ImMR(F ||C max ; p j ) and compared it with a simple middle interval heuristic algorithm for three machines instances. [START_REF] Drwal | Min-max regret scheduling to minimize the total weight of late jobs with interval uncertainty[END_REF] considered the minimization of the total weight of late jobs in a single machine under interval processing times. They showed that ImMR(1|| w j U j ; p j ) is NP-hard and proposed a heuristic algorithm based on mixed-integer linear programming to compute a robust solution.

Besides theoretical scheduling, the robustness under scenario uncertainty or interval uncertainty has been spread to several applications as project scheduling, line balancing, energy optimization, etc.. In project scheduling, [START_REF] Artigues | Robust optimization for resource-constrained project scheduling with uncertain activity durations[END_REF] examined the min-max regret Resource-Constrained Project Scheduling Problem. They showed that the robust problem turned out to be exceptionally difficult, in that even exact objective-function evaluation is intractable and computationally overly demanding, even for medium-sized instances. They implemented a scenario-relaxation algorithm that produces optimal solutions but requires excessive running times even for medium-sized instances. Furthermore, they proposed a scenario-relaxationbased heuristic that produces high-quality solution for medium-sized instances in less CPU times. In robust line balancing, [START_REF] Dolgui | Scenario based robust line balancing: Computational complexity[END_REF] studied the line balancing problem under uncertain processing times where the objective is to minimize the worst-case maximum execution time of the same station. They represented uncertainty by a set discrete scenarios and proposed an approach to reduce its cardinality. They showed that several special cases of the problem are NP-hard and strongly NP-hard. Furthermore they suggested enumerative dynamic programming algorithms and problem-specific polynomial time algorithms for some cases. For more examples, the reader is referred to [START_REF] Bentaha | A bibliographic review of production line design and balancing under uncertainty[END_REF]. The min-max and min-max regret criteria lead to a risk-averse decision since they assume that decision makers risk-averse (or pessimistic). It follows from the fact, that the computation of schedules that minimize the worst-case performance (resp. the maximal regret) is particularly constrained with the worst-case scenarios, ignoring the information connected with the remaining scenarios. In some context where protection measures should be taken, the choice of these criteria is crucial. But, in context where decision makers are less risk averse, other approaches can be applied. Instead of seeking for a solution that optimize the robustness measure, the decision makers impose conditions that solutions must satisfy in order to be considered as robust. For instance, [START_REF] Daniels | β-robust scheduling for single-machine systems with uncertain processing times[END_REF] defined a β-robustness measure that is based on the likelihood of achieving system performance no worse than a given target level. [START_REF] Daskin | α-reliable p-minimax regret: A new model for strategic facility location modeling[END_REF] proposed a α-reliable min-max regret model to compute a solution that minimizes the maximum regret with respect to a selected subset of scenarios whose probability of occurrence is at least α (a value defined by the decision maker). [START_REF] Kalaï | l'α-robustesse lexicographique: une relaxation de la β-robustesse[END_REF], [START_REF] Kalaï | Lexicographic α-robustness: an application to the 1-median problem[END_REF] proposed an approach called lexicographic α-robustness which considers all scenarios in lexicographic order from the worst to the best, and where α is a tolerance threshold in order to not discriminate among solutions with similar values.

The expected performance is known to be the most-appropriate for a risk-neutral decision maker. It is widely used in scheduling under both random processing times and under random machine breakdowns Jorge [START_REF] Leon | Robustness measures and robust scheduling for job shops[END_REF]; [START_REF] Wu | A graph-theoretic decomposition of the job shop scheduling problem to achieve scheduling robustness[END_REF]; [START_REF] Goren | Optimization of schedule robustness and stability under random machine breakdowns and processing time variability[END_REF]).The study of the performance distribution is also important when dealing with stochastic scenarios. For example, in project scheduling under stochastic durations, [START_REF] Ballestin | Resource-constrained project scheduling for timely project completion with stochastic activity durations[END_REF] minimized the expected makespan and studied the distribution of makespan realizations for a given scheduling policy. The analytic calculation of the expected performance measure is often complicated when the probability distribution is continuous which justify the use of simulation or surrogate measures to estimate this value. When decision-makers are able to assign discrete probabilities or sampling, the expected performance of solution X could be calculated as given in Equation 2.

3

Z e (X) = s∈S {p s Z s (X)}, (2.3)
where p s is the probability attached to scenario s.

The expected performance minimization is often combined with a stability objective as we will see in Table 2.2. In the next section, we focus on the studies that considers the stability issue in scheduling under uncertainty.

Structure robustness optimization

To construct stable schedules, the stability measures proposed in the literature are basically related to: the starting times or the completion times deviations (e.g. [START_REF] Wu | One-machine rescheduling heuristics with efficiency and stability as criteria[END_REF]; Abumaizar and Svestka (1997); [START_REF] Mehta | Predictable scheduling of a single machine subject to breakdowns[END_REF]; Dong and Jang (2012)), the sequence deviation (e.g. [START_REF] Wu | One-machine rescheduling heuristics with efficiency and stability as criteria[END_REF]; Abumaizar and Svestka (1997); [START_REF] Cowling | Using real time information for effective dynamic scheduling[END_REF]; [START_REF] Leus | Stability and resource allocation in project planning[END_REF]), the number of disrupted jobs (e.g. [START_REF] Ozlen | Rescheduling unrelated parallel machines with total flow time and total disruption cost criteria[END_REF]).

Starting time and completion time deviations are very useful measures of stability, especially in shop environments where secondary resources such as tooling and handling should be prepared. A change in job starting or completion time may incur carrying costs if the material is delivered earlier than expected, or perhaps more importantly, rush order costs if the tools and material are requested earlier than expected [START_REF] Wu | One-machine rescheduling heuristics with efficiency and stability as criteria[END_REF]). An example of such stability measure in Equation 2.4 is given by summing the absolute value of the differences in job starting times between the realized schedule and the schedule of reference:

Starting time deviation = j∈J | s j -s initial j | (2.4)
Where s j and s initial j are respectively the starting time of job j in the realized schedule and the initial schedule. The absolute values permit to report both delay and rush.

The sequence deviation measure is critical if machine setups are prepared in advance based on the initial sequence. For instance, jobs may wait in a sequence queue, and tooling may be planned in advance according to the initial sequence. Thus, a sequence deviation will incur costs in handling and reallocating the jobs, and re-planning the tools changeover [START_REF] Wu | One-machine rescheduling heuristics with efficiency and stability as criteria[END_REF]). An example of such measure is defined by Abumaizar and Svestka (1997) as follows:

• S 1 : set of jobs processed before operation j in the initial schedule.

• S 2 : set of operations processed after operation j in the new schedule.

• N ij : cardinality of S = S 1 ∩ S 2 .
The formula in Equation 2.5 gives the measure of jobs sequence deviation over all the machines:

sequence deviation = i∈I j∈J N ij (2.5)
Starting/Completion times deviations, and sequence deviation are widely used in single machine, job shop and project scheduling problems under stochastic machine breakdowns and/or stochastic processing times. The vast majority of these studies are bi-objective. They consider both stability and efficiency, for instances: [START_REF] Wu | One-machine rescheduling heuristics with efficiency and stability as criteria[END_REF] considered the makespan minimization on a single machine under stochastic machine breakdowns. They proposed a bi-objective heuristics in order to optimize the stability and to maintain a good makespan. For this purpose, they used the total deviation in starting times and the sequence deviation as stability measures. Their computational results show that the schedule stability can be increased significantly with little or no sacrifice on the makespan. Abumaizar and Svestka (1997) considered a job shop problem affected by disruptions modelled as stochastic machine breakdowns. They also considered starting time deviation and sequence deviation as stability measures, and they presented a heuristic that optimizes both the makespan and the stability measures to produce an efficient and stable schedule.

Mehta and Uzsoy (1998) consider job shop environment under machine breakdowns. They present a linear programming based heuristic that minimizes the deviation of the starting times compared with a schedule that contains ample slack, while respecting a deadline for the project. They insert additional idle time into the schedule to absorb the impact of breakdowns, and invoke earliness or lateness penalties whenever the last operation of a job ends sooner or later than planned. [START_REF] Mehta | Predictable scheduling of a single machine subject to breakdowns[END_REF] showed that the bi-criterion approach significantly outperforms the deterministic approach based only on makespan. [START_REF] Goren | Robustness and stability measures for scheduling: single-machine environment[END_REF] addressed the problem of finding robust and stable schedule in a single machine environment under stochastic machine breakdowns. Many schedule performances were studied: makespan, total flow time, and total tardiness. The robustness of the schedule is measured through the expected performance of the realized schedule, while the stability is measured through the expected sum of absolute deviations in job completion times. The surrogate measures of robustness and stability are embedded in a tabu-search algorithm. [START_REF] Goren | Optimization of schedule robustness and stability under random machine breakdowns and processing time variability[END_REF] extended the list of stability measures to the sum of the squared differences of the job completion times, the sum of absolute differences of the job completion times and the sum of the variances of the realized completion times.

In project scheduling, [START_REF] Van De Vonder | The trade-off between stability and makespan in resource-constrained project scheduling[END_REF] addressed the trade-off between stability and robustness in resource constrained project scheduling. They proposed a heuristic algorithm that minimizes the weighted deviation of starting times and provided an extensive simulation experiment to assess the trade-off between stability and robustness (measured through the completion time).

In parallel machine scheduling, the authors used, particularly, two measures which are the number of disrupted jobs and the total cost of reassignments. As the jobs could be assigned to different machines after the disruption, the research question is often about finding the solution that offers the best trade-off between stability and performance. [START_REF] Azizoglu | Parallel-machine rescheduling with machine disruptions[END_REF] defined the number of disturbed jobs as given in [START_REF] Kaplan | Exact and heuristic algorithms for the aerial refueling parallel machine scheduling problem with due date-to-deadline window and ready times[END_REF]. Five heuristic algorithms are introduced to handle the bi-objective problem using algorithms by [START_REF] Kaplan | Simulated annealing and metaheuristic for randomized priority search algorithms for the aerial refuelling parallel machine scheduling problem with due date-to-deadline windows and release times[END_REF]. Their experiments solved small size and large size problems for different types of disruptions.

The complexity of machine scheduling for stability is rarely addressed in the literature, to the best of our knowledge, only [START_REF] Leus | The complexity of machine scheduling for stability with a single disrupted job[END_REF] studied the complexity of machine scheduling for stability.

They used the expected weighted deviation in start times as stability measure. They showed that single machine, single machine with unequal ready times, and single machine with precedence constraints under single-disruption are NP-hard. Then, they considered parallel machine problem. They also showed that the single-disruption stability problem with free number of parallel machines is strongly NP-hard.

To evaluate the stability of optimal solutions, the stability as post-optimality analysis has been used in single machine scheduling [START_REF] Sotskov | Minimizing total weighted flow time under uncertainty using dominance and a stability box[END_REF], in job (general) shop scheduling problems [START_REF] Sotskov | Stability of an optimal schedule[END_REF]; [START_REF] Sotskov | Stability of an optimal schedule in a job shop[END_REF]), in assembly line problem [START_REF] Sotskov | Stability radius of the optimal assembly line balance with fixed cycle time[END_REF]; [START_REF] Sotskov | Stability analysis of an optimal balance for an assembly line with fixed cycle time[END_REF]. [START_REF] Sotskov | Minimizing total weighted completion time with uncertain data: A stability approach[END_REF] discussed the application of this approach to the job (and general) shop problem with the makespan and the total flow time criteria. This approach is based on the separation of the structural input data (precedence and capacity constraints) from the numerical input data. The approach is based on an improved stability analysis of an optimal digraph. In application to semi-conductor production environment, [START_REF] Rossi | Ordonnancement en milieu incertain, mise en oeuvre d'une démarche robuste[END_REF][START_REF] Rossi | A robustness measure of the configuration of multi-purpose machines[END_REF] presented an approach for measuring the stability of a configuration of parallel multipurpose machines under demand uncertainty. They assessed the minimum magnitude of forecast demand perturbations that may lead to breaking the deadline provided by the decision maker. They showed accordingly the practical use of "the stability radius" in industry. The stability analysis approach was also applied to several scheduling problems, where the deterministic versions allow a polynomial-time solution. [START_REF] Sotskov | Minimizing total weighted completion time with uncertain data: A stability approach[END_REF] presented additional results for the two-machine flow (and job) shop problem with interval processing times both the off-line scheduling problem and the on-line problem is considered. The stability approach was also implemented for the single machine mean flow time problem with interval processing times [START_REF] Sotskov | Minimizing total weighted completion time with uncertain data: A stability approach[END_REF][START_REF] Sotskov | The stability box in interval data for minimizing the sum of weighted completion times[END_REF]).

2.4

Literature review synthesis and research potential issues

Literature synthesis

We have surveyed published works on scheduling under uncertainties for robustness and/ or stability objective published between 1995 and 2017 (Table 2.2). The total population of published works on the topic falls into one of four clusters organized around 4 seminal publications:

-Cluster 1 (Robust scheduling) includes all the works based on the approach of Daniels and Kouvelis (1995a). These works belong to the purely proactive approach aim to compute robust schedule under ambiguity. Most of the addressed problems belong to theoretical scheduling problems. Single machine environment is the most considered. Processing times, followed by due dates and then job weights are the most frequently analysed uncertainties. The uncertain data are modeled by discrete scenarios (or intervals) and the authors use min-max (regret) objectives or extension of these objectives. An unavoidable question under these works is related to the complexity of the robust versions of the scheduling problems. The vast majority of these robust version is NP-hard. Therefore, the authors propose, design and evaluate multiple algorithms to compute the robust solutions.

-Cluster 2 (Stable scheduling) includes all the works that extend the research question of [START_REF] Wu | One-machine rescheduling heuristics with efficiency and stability as criteria[END_REF]. These works which belong to the predictive reactive approach use bi-objective function to optimize the stability and to maintain a good performance under stochastic uncertainty or disruptions. The authors use the expected performance as performance objective and stability measures. -Cluster 3 (Robust Stable scheduling) includes all the works that extend the research question of Jorge [START_REF] Leon | Robustness measures and robust scheduling for job shops[END_REF]. These works which belong to the proactive-reactive approach or to the purely proactive approach. They use bi objective function to optimize the robustness and the stability of the schedule under stochastic uncertainty/disruptions, the processing times followed by machine breakdowns being the most frequently addressed uncertain parameters.

-Cluster 4 (Stability as post-analysis) includes all the works that extend [START_REF] Sotskov | Stability of an optimal schedule[END_REF] research questions. Under this approach, an optimal solution of reference is computed in a deterministic way and its stability is evaluated a-posteriori under small perturbations of the data. The research question is formulated around how one can vary the data in the problem in such a way that an optimal schedule remains optimal.

The answer conducts to the calculation of the stability radius (resp. a ball or a box).

Research potential issues

From these clusters, we can remark that there exist a lot of opportunities for future works. Here some points:

i) Cluster 1 works can provide schedules that are immune against uncertainties and disruptions for a described uncertainty. But, some robust solutions may fail when the future turns out differently than considered. A robust model may not guarantee a good performance under a scenario outside the set of considered discrete scenarios or interval. The robustness oriented studies rarely addressed these questions. There is a lack of studies that address the stability of robust solutions from both structural and performance viewpoints.

ii) Cluster 2 and Cluster 3 works deal basically with stochastic uncertainties and disruption (frequently processing times and machine breakdowns). The future research might focus on other uncertainties and disruptions as the due dates, the release dates, the setup times, etc..They can also model the uncertainties and the disruptions using other representations as intervals or scenarios instead of probability distributions.

The existing works in cluster 2 can also be extended to consider robustness objective besides the stability objective. The results provided by the works of Cluster 1 can be embedded in these works to provide robust solutions using min-max and min-max regret objectives.

iii) Stability as post optimization analysis is a promising approach for further research since it focus until now on deterministic solutions and use complicated measure to answer only one question "what is the data change for which the optimality is not affected?". This question is important in Cluster 1 as we have pointed out. Thus, the basic idea of stability analysis can be used to answer the question. But we can also address the stability with a different research question as What is the impact of a given data change on the robust solution? vi) Parallel machine scheduling problem under uncertainty, which constitutes our subject of study, is treated with different approaches in the literature for robustness or stability objective. Under robustness, the objective is to deal with uncertain processing times while under stability the objective is principally to deal with machine breakdowns. The robustness and the stability in parallel machine scheduling are rarely addressed jointly. Besides, the preemptive version is rarely addressed.

Conclusion

In this chapter, we presented the general form of the scheduling problem and define its fundamental notions.

We discussed the limitations of scheduling under the hypothesis of certainty based on previous work claims.

Then, we reviewed the representations of the uncertainties and disruptions in scheduling. We classified the scheduling approaches and objectives under uncertainties and disruptions. In the review, we focused on the works that are oriented toward robustness and stability.

The survey revealed that the contributions are organized around four clusters. The analysis of these clusters showed that there exist a lot of opportunities for future developments. Robust optimization can provide schedules that are immune against uncertainties and disruptions but, robust solutions may fail when the future turns out differently than considered. The robustness oriented studies do not consider this issue while stability models do. However, stability and robustness are mentioned to be conflicting objectives.

Besides, most of the studies that consider robustness focus on the performance robustness and do not address the robustness of the structure that is in part very important for practitioners. Stability analysis approach focuses on deterministic solutions and use complicated measures. Based on these remarks, we will consider a parallel machine scheduling environment under processing times uncertainty under which we will address all these points:

Research question 1: How to provide robust solutions that withstand the uncertain processing times? The classical problem of scheduling parallel machines consists in sequencing n jobs on m same function machines in order to optimize the objective. Each job j must be performed on a machine with a fixed processing time p ij . p ij represents the processing time of job j in machine i. In parallel machine scheduling, we distinguish three environments of the machines. In the case of parallel identical machines (α = P m),

the job processing time is independent of the machine where it is processed. For uniform parallel machines α = Qm, each machine has a different speed. The processing time is equal to the processing requirement divided by the speed of the machine. In unrelated parallel machines α = Rm, no particular relationship exists between the processing times on the different machines, i.e. there is no proportionality between the processing time of a job on a given machine and the processing time of the same job on another machine.

The literature on scheduling parallel machine problems is abundant, a deep review is provided in [START_REF] Mokotoff | Parallel machine scheduling problems: A survey[END_REF]). Among all possible objectives, the most widely used in scheduling parallel machines is the makespan minimization. Indeed, the makespan minimization allows the maximization of machine utilization and provides a good load-balance. The makespan minimization is denoted as γ = C max .

In general, the classical scheduling problems in parallel machines assume that:

-Each job cannot be processed in more than one machine simultaneously;

-A job once started should be completed;

-Processing time does not depend on the sequence;

-The job can wait for a free machine;

-No machine can process more than a job at a time;

-The number of jobs n is known and fixed;

-The number of machines m is known and fixed;

-Processing times are known and certain;

-During the schedule, no machine breakdowns are considered.

When the processing requirement of a job is considered as its total demand (e.g. lot), we can split the jobs into sub-jobs (e.g. sub-lots) that can be processed independently on the machines. Under splitting, we accept to overlap the sub-jobs so as to finish the processing requirement as soon as possible. [START_REF] Potts | Integrating scheduling with batching and lot-sizing: a review of algorithms and complexity[END_REF] referred to this process as lot-streaming or lot-sizing and [START_REF] Xing | Parallel machine scheduling with splitting jobs[END_REF] denote the job characteristic as β = Split. When the processing of a job can be interrupted several times and later resumed but, the sub-jobs of the same job cannot be processed in parallel, we denote β = pmtn to mean preemption.

In the classical scheduling algorithms, it is assumed that the scheduler has full information about the problem instance before the process of scheduling actually starts (e.g. the number of machines, the number of jobs, the processing times are known with exactitude). However, the uncertainty of processing times is prevalent in the applications that involves such problems. In Section 3.1, we describe the problems Rm|Split|C max and Rm|pmtn|C max and we show the limits of the classical deterministic algorithms in solving these problems under uncertain processing times. Besides, we propose a preliminary approach that aims to enforce the feasibility of the schedule under different scenarios by tolerating the violations of some processing requirements, and we show that under this approach the overproduction or the shortage can be very important. To avoid this, we propose in Section 3.2 an artificial scenario based approach under which we construct a set of feasible solutions based on a set of generated artificial scenarios. We choose the robust solutions based on an evaluation algorithm that computes a robustness measure of each solution. In Section 3.3, we report the results of the computational experiments respectively in splitting and preemptive cases.

3.1 The need for robustness under uncertain processing times

Makespan minimization on unrelated parallel machines under splitting and preemption

The makespan minimization on unrelated parallel machines with splitting denoted Rm|Split|C max is defined as follows. n independent jobs are allowed to be processed by any of the m unrelated parallel machines.

The processing times p ij depends on job j and machine i. Each job can be split into continuous sub-jobs and processed independently on the m machines with allowed parallelism so as to finish the processing of all demands as soon as possible. For a high utilization of the machines and a good load-balancing, the objective is to determine the optimal schedule so as to minimize the makespan C max . According to [START_REF] Xing | Parallel machine scheduling with splitting jobs[END_REF], this process is referred to as lot-sizing or lot-streaming and the split parts as continuous sub-lots.

The deterministic problem Rm|Split|C max was formulated by [START_REF] Xing | Parallel machine scheduling with splitting jobs[END_REF] as a linear problem

(LP Split ): Minimize C max (3.1) Subject to m i=1 t ij p ij = 1, j = 1, . . . , n (3.2) n j=1 t ij -C max ≤ 0, i = 1, . . . , m (3.3) 0 ≤ t ij , i = 1, . . . , m, j = 1, . . . , n (3.4)
where each temporal variable t ij is the total amount of time spent by job j on machine i and C max is the makespan which is the maximum job completion time over the m machines. The objective function (3.1) in (LP Split ) minimizes the makespan. Constraints (3.2) ensure that each job j receives the required amount of processing, while constraints (3.3) enforce that the total processing on each machine i is less or equal to the makespan. Lastly, constraints (3.4) imply that each temporal variable t ij is positive.

The given formulation can be solved in polynomial time. An optimal solution which is a matrix of durations T allows to construct an optimal schedule. Indeed, all the sequences are feasible.

In the preemptive case, the makespan minimization on unrelated parallel machines, denoted Rm|pmtn|C max , is as an extension of the split case. The major difference between the preemptive problem and the split one is that in the makespan minimization on unrelated parallel machines with preemption, the computation of a sequence is also a part of the decision. In fact, each job can be split into continuous sub-jobs that can be processed independently on the m machines without parallelism (no overlapping). [START_REF] Lawler | On preemptive scheduling of unrelated parallel processors by linear programming[END_REF] have suggested a two step algorithm to solve Rm|pmtn|C max . The first step consists in solving a linear formulation (LP pmtn ) given as follows:

Minimize C max (3.5) Subject to m i=1 t ij p ij = 1, j = 1, . . . , n (3.6) n j=1 t ij -C max ≤ 0, i = 1, . . . , m (3.7) m i=1 t ij -C max ≤ 0, j = 1, . . . , n (3.8) 0 ≤ t ij , i = 1, . . . , m, j = 1, . . . , n (3.9)
where each temporal variable t ij is the total amount of time spent by job j on machine i and C max is the makespan. Constraints (3.6) ensure that each job j is receiving the required amount of processing. The constraints (3.7) ensure that the (workload) total amount of processing on each machine i is less or equal to C max while the constraints (3.8) also insures that the total processing time of each job do not exceed the makespan. The constraints (3.8) prohibit the overlap between job parts of the same job. Lastly, constraints (3.9) imply that variable t ij is positive. The objective (3.5) minimizes the makespan.

The linear formulation can be solved in polynomial time, but the solution of (LP pmtn ) does not prescribe an actual schedule. The second step, then, consists of the construction of the optimal schedule with the information provided by (LP pmtn ) resolution. Indeed, for any feasible solution to the linear program, there exists a feasible schedule with the same values of t ij and C max . To prove this assertion, [START_REF] Lawler | On preemptive scheduling of unrelated parallel processors by linear programming[END_REF] solved the preemptive open-shop scheduling problem Om|pmtn|C max defined by [START_REF] Gonzalez | Open shop scheduling to minimize finish time[END_REF]. It comes back to consider that once the durations and the corresponding makespan are computed, the problem becomes a sequencing problem of a set of jobs that are composed of a number of tasks (that we call the sub-jobs) where no restrictions are placed in the order in which the tasks (sub-jobs)

of any job should be processed. The only constraint to respect is that a machine can process only one job at a time and a job can be worked by only one processor at a time. There is no restriction on the order in which a given job can be worked on by the different processors, or on the order in which a given processor can work on jobs (Hence the term "open shop."). However, the construction of a sequence might require additional preemption. It means that the t ij s once assigned to a given machine can be interrupted and resumed later in that machine. According to [START_REF] Gonzalez | Open shop scheduling to minimize finish time[END_REF], Om|pmtn|C max is solvable in polynomial

time. An analysis of computations done by [START_REF] Gonzalez | A note on open shop preemptive schedules[END_REF] has shown that the Om|pmtn|C max is solvable in O(r + min(r 2 , n 4 , m 4 )) where r is the number of nonzero elements in T the matrix of durations t ij 's.

The maximum number of preemptions introduced is min{rn, rm, n 3 , m 3 }. And according to [START_REF] Lawler | On preemptive scheduling of unrelated parallel processors by linear programming[END_REF], an upper bound on the number of preemptions required for a C max -optimal schedule on unrelated parallel machines is 4m 2 -5m + 2.

Limitations of the classical algorithms under uncertain processing times

In practice, the processing times p ij s are not often certain. In fact, each processing time p ij depends both on the processing requirement p j of the job j representing its demand, and the speed v ij of machine i to process the job j. Each p ij can be decomposed as:

p ij = p j /v ij .
If the demands are uncertain, which is often the case in reality, the processing times become also uncertain. Under these uncertainties, the solving approaches introduced in the previous sections, LP Split and the 2 step algorithm of Lawler based on LP pmtn , may lead to schedules that cannot be executed as planned: when applied to the actual realization of processing times, the optimal schedules based on the nominal instance of processing times become sub-optimal and sometimes infeasible. To point out this claim we will consider the following example:

Example 3.1.1 We consider an example in which 4 jobs are to be processed by 3 unrelated parallel machines. The v ij s are certain and depend on both machines and jobs as given in Table 3.1.

We consider a forecast instance of p n ij s called the nominal instance I n (Table 3.2) corresponding to the demand: D n = (30, 50, 30, 100).

TABLE 3.1: Matrix of speeds v ij J 1 J 2 J 3 J 4 M 1 3 2 4 1 M 2 3 1 3 2 M 3 3 4 4 4
a-In the splitting case: according to LP Split resolution, Job 1 and Job 3 are entirely processed on machine 1 for 10 units and 7.5 units respectively, Job 2 is processed for 5.62 units on machine 1 and for 9.69 units on machine 3, and Job 4 is processed for 23.12 units on machine 2 and for 13.44 units on machine 3.

The optimal makespan, which is equal to 23.12 units, features a high utilization of the three machines with

M 1 J 1 J 2 J 3 M 2 J 4 M 3 J 2 J 4
a strict load balancing (Figure 3.1). But, under demand uncertainty, the realization of processing times will be different from the nominal instance. For a real demand given as: D r = (50, 30, 80, 50), the real instance I r of p r ij s is represented in Table 3.3. In that case, the decision-maker may have two basic strategies:

M 1 J 3 M 2 J 1 J 3 J 4 M 3 J 2 J 4
The first strategy is to adapt the schedule to the new instance I r by the computation of its corresponding optimal schedule. Accordingly, the four jobs are to be scheduled as shown in Figure 3.2: Job 1 is entirely processed on machine 2 for 16.67 units, Job 2 is to be entirely processed on machine 3 for 7.5 units, Job 3 is processed on machine 1 for 19.23 units and on machine 2 for 1.02 units, Job 4 is processed for only 1.53 units on machine 2 and for 11.73 units on machine 3. Nevertheless, this strategy is not stable because it requires new machine setup and changeover (even if we do not consider explicitly these costs), besides job handling to make the needed adjustments. The more different the structures of the two schedules are, the more important the adjustment efforts will be. These syndromes of schedule nervousness, as called by practitioners, can turn out to be a serious problem under big instances because they generate a considerable amount of efforts and hidden costs as well as a general loss of confidence in the scheduling function.

The second strategy is to schedule the real instance according to the optimal nominal schedule. Therefore, we propose to calculate the machine participation ratios to process jobs according to the optimal schedule of the nominal instance as given in table of Figure 3.3:

t n ij * p n ij
and then we apply these ratios to schedule the real instance.

FIGURE 3.3: Schedule of the real instance according to the nominal instance solution in the splitting case

t n ij p n ij J 1 J 2 J 3 J 4 M 1 1 0.22 1 0 M 2 0 0 0 0.46 M 3 0 0.
M 1 J 1 J 2 J 3 M 2 J 4 M 3 J 2 J 4

Schedule of the real instance

By applying the optimal nominal solution to schedule the real instance I r we obtain a schedule that requires a makespan equal to 40.04 time units (Figure 3.3). The generated decision is suboptimal: the makespan C max has increased over 108% time units compared to the optimal makespan of the real scenario C r * max . Besides the load balancing is altered as the machine M 1 is overused while machines M 2 and M 3 are more than half schedule time in the idle time.

b-In the preemptive case: The observations are similar to those in the splitting case, i.e. when we ignore the uncertainty, the optimal preemptive schedule based on the nominal instance become vulnerable when applied to the real instance.

M 1 J 2 M 2 J 1 J 3 M 3 J 4
According to the resolution of (LP pmtn ), the preemptive optimal schedule of the nominal instance I n can handle all jobs with a makespan equal to 25 time units (see Figure 3.4). As we can observe, for this particular instance, each job was completely assigned to only one machine without any preemption: Job 2 is processed on machine 1 and Job 4 is processed on machine 3 for 25 units respectively, whereas Job 1 and job 3 are processed on machine 2 for 10 units respectively. Consequently, there is no need to solve the corresponding preemptive open shop in order to construct the schedule.

M 1 J 3 M 2 J 1 J 4 M 3 J 4 J 2 J 3 FIGURE 3
.6: Schedule of the real instance according to the nominal instance solution in the preemptive case

t n * ij p n ij J 1 J 2 J 3 J 4 ≺ M 1 0 1 0 0 J2 M 2 1 0 1 0 J1 ≺ J3 M 3 0 0 0 1 J4
M 1 J 2 M 2 J 1 J 3 M 3 J 4

Schedule of the real instance

If we again consider the real instance of processing times given in (Table 3.3), the two basic strategies have weakness points. When we totally adapt the schedule to the real instance, we construct an optimal schedule which is very different from the nominal schedule (see Figure 3.5) under which Job 1 is processed for 16.67 units on machine 2, Job 2 is processed for 7.5 units on machine 3, Job 3 is processed for 18.32 units on machine 1 and for 1.66 units on machine 3, and Job 4 is processed for 3.25 units on machine 2 and for 10.75 units on machine 3. The makespan is equal to 20 units. But, as we can observe, the total adaptation can imply high deviations in terms of assignments, starting times and completion times. Consequently, the nervousness aspects can be accurate under a totally adaptive strategy in the preemptive case.

When we schedule the real instance based on the permutation and the machine participation ratios to process jobs according to the optimal schedule of the nominal instance (see Figure 3.6), we notice that the degradation of the makespan is very significant (see Figure 3.6).

The example shows that a nominal schedule which is determined to be optimal regarding the makespan criterion prior to its execution can turn to be vulnerable under minor or serious uncertainty. Furthermore, the calculation of a new solution under each new scenario can also lead to hidden costs due to nervousness aspects.

The major weakness of the classical scheduling approach, when the processing times are uncertain, is that the schedules which are optimal with respect to the nominal instance (forecast instance) might be substantially infeasible or yield poor performance when evaluated relatively to the actual processing times. For decision makers that have to face the consequences regardless of the realized instance, schedule infeasibility or sub-optimality are unacceptable, even though that schedule is the "optimal" one for the nominal scenario.

It is generally admitted that forecast values are usually wrong. Any scheduling algorithm that ignores this fact, and is focused on the "nominal" instance of forecast processing times, is unacceptable for decision environments subject to uncertainty. As shown in the example, the schedules which are determined to be optimal based on the nominal instance can lead to poor performances when applied to the real instance.

Furthermore, the calculation of a new schedule under each new instance does not provide a baseline schedule and requires adjustment efforts. In light of this, the scheduling approach to develop should be designed to take into account the uncertainty of processing times.

Stochastic scheduling models adopt a probabilistic viewpoint, treating uncertain processing times as random variables. Under this scheme, a probability distribution of the processing times should be available and the scheduling model is formulated with the objective to optimize the expected makespan. However, in many cases, such a distribution is not available.

When schedulers are confronted with a significant uncertainty of processing times that cannot be approximated with a probability distribution, many authors claimed that non-probabilistic discrete scenarios offer a good representation of uncertainty (e.g. [START_REF] Kouvelis | Robust discrete optimization and its applications[END_REF], [START_REF] Averbakh | The minmax regret permutation flow-shop problem with two jobs[END_REF], [START_REF] Aissi | Minimizing the number of late jobs on a single machine under due date uncertainty[END_REF], [START_REF] Kasperski | Approximating a two-machine flow shop scheduling under discrete scenario uncertainty[END_REF], [START_REF] Roy | Robustness in operational research and decision aiding: A multi-faceted issue[END_REF], etc.). As discussed earlier in Chapter 1 and Chapter 2, the discrete scenarios are suitable in situation of ambiguity when there is a lack of information about the probabilities and when the schedulers aim to be protected against any potential future. They are widely used to represent the uncertain processing times in scheduling problems especially when the uncertainty is due to uncertain demand. Furthermore, many approaches called robust result from the use of discrete scenarios. Under these approaches, we generally seek for solutions that optimize a global performance instead of seeking for solutions that optimize a local performance as the performance of the decision is evaluated across all the potential scenarios.

From the foregoing, we assume that the uncertainty of processing times can be represented by a set of discrete scenarios Ω k = {s 1 , s 2 , . . . , s k }. Each scenario s ∈ Ω k represents a potential realization of the uncertain processing times and captures a situation that might occur. We denote by p s ij the processing time of job j on machine i under scenario s, and C s * max the optimal makespan under scenario s. The nominal scenario is also included in the set Ω k which makes the deterministic formulation only a special case.

Based on the deterministic linear formulation of Rm|Split|C max (resp.. Rm|pmtn|C max ), the uncertainty of processing times is affecting the data in the equality constraints. Thus, the robust problem is equivalent to a constraint feasibility problem where the objective is to find the schedule that is feasible under any scenario as expressed in the constraints Equation 3.10.

m i=1 t ij p s ij = 1, j = 1, . . . , n, s = s 1 , . . . , s k .
(3.10) Under this formulation, the set of solutions may be empty since the equality constraints cannot be insured for different scenarios.

To overcome the infeasibility, a first solution consists in adding slack variables in the equality constraints as suggested in [START_REF] Mulvey | Robust optimization of large-scale systems[END_REF]. This approach that we call "slack based approach" is explained in details in the next section.

3.2 Slack based approach under discrete processing time scenarios

m i=1 t ij + z s+ ij -z s- ij p s ij = 1, j = 1, . . . , n, s = s 1 , . . . , s k (3.11)
We distinguish two kinds of error terms in (3.11):

-The z s+ ij express the necessity of a replenishment to reach the processing times required by jobs under each scenario ( case of under-production).

-The z s- ij compensate an overrun of the processing times under each scenario (case of overproduction). We control the violations due to the slacks through a weighted penalty function ρ(.):

ρ(.) = w k s k s=s 1 Z s max or ρ(.) = w. max s∈{s 1 ,...,s k } Z s max (3.12)
where Z s max is the maximal violation induced by the use of slacks under a scenario s, w is the weight of the penalty and k the number of potential scenarios.

One can choose over different strategies:

-Case 1: Z s max is the maximal violation over machines computed according to the following constraints:

n j=1 (z s+ ij + z s- ij ) ≤ Z s max , i = 1, . . . , m, s = s 1 , . . . , s k , (3.13)
-Case 2: Z s max is the maximal violation over jobs computed according to the following constraints:

m i=1 (z s+ ij + z s- ij ) ≤ Z s max , j = 1, . . . , n, s = s 1 , . . . , s k , (3.14)
-Case 3: Z s max is the maximal violation over jobs and machines computed according to the following constraints

z s+ ij + z s- ij ≤ Z s max , i = 1, . . . , m, j = 1, . . . , n, s = s 1 , . . . , s k (3.15)
-Case 4: Z s max is the total of all violations over jobs and machines computed as

m i=1 n j=1 (z s+ ij + z s- ij ) = Z s max , s = s 1 , . . . , s k (3.16)
The objective is to: Minimize C max + ρ(.) The minimization of the makespan C max aims to optimize the performance of the schedule while the penalty function ρ(.) aims to minimize the violation over all the potential scenarios (average or max) .

Here, we present some cases of the slack based approach to compute model robust schedules in the case of the makespan minimization on unrelated parallel machines with splitting (resp.. preemption). We can propose different formulations.

Formulation 1:

Minimize C max + w |k| k s=1 Z s max (3.17) Subject to m i=1 t ij + z s+ ij -z s- ij p ij = 1, j = 1, . . . , n, s = s 1 , . . . , s k (3.18) n j=1 t ij -C max ≤ 0, i = 1, . . . , m (3.19) m i=1 (z s+ ij + z s- ij ) ≤ Z s max , j = 1, . . . , n, s = s 1 , . . . , s k (3.20) 0 ≤ t ij + z s+ ij -z s- ij , i = 1, . . . , m, j = 1, . . . , n, s = s 1 , . . . , s k (3.21) 0 ≤ t ij , z s+ ij , z s- ij , i = 1, . . . , m, j = 1, . . . , n, s = s 1 , . . . , s k (3.22)
(z s+ ij + z s- ij ) ≤ Z s max , s = s 1 , . . . , s k (3.24)
In the formulations 1 and 2, we minimize the sum of the makespan C max and the total weighted violation over all the scenarios k s=1 Z s max . The slack variables in the constraints (3.18) allow the feasibility of the equality under all the scenarios. Constraints (3.21) combined with the objective function imply the computation of non-null matrix T . In the formulation 1, Z s max is computed as the total violation over jobs under the scenario s (c.f. constraints (3.20)) while in the formulation 2 it is computed as the total violation by machines and jobs (c.f. constraints (3.24)). The temporal variables t ij and the slack variables z s+ ij , z s- ij are positive (3.22).

(z s+ ij + z s- ij ) ≤ Z s max , s = s 1 , . . . , s k (3.26) Z s max ≤ Z max , s = s 1 , . . . , s k (3.27)
In the formulation 3, we minimize the sum of the makespan C max and the maximal violation over all the scenarios Z max . Z max = max k s=1 Z s max is computed as the maximal total violation over jobs and machines, over the scenario s (c.f. constraints (3.26),(3.27)).

In order to extend the formulations to the preemptive case, one should add the constraints of non overlapping (Equation 3.8) .

We illustrate the proposed approach through the example initiated in section 3.1.1.

Example 3.2.1 We assume that uncertain processing times are due to uncertain demands. We represent the uncertainty of demand by 5 potential scenarios corresponding to the future realizations (Table 6.1). The matrix of job-machine dependant speeds v ij is invariant (Table 3.5).

J 1 J 2 J 3 J 4 M 1 3 2 4 1 M 2 3 1 3 2 M 3 3 4 4 4
a-In the case of splitting: The resolution of the slack based approach applied to Rm|Split|C max gives the following results. Under formulation 1, for w = 6, the produced quantities according to the robust schedule are: (48.75, 35, 75, 55) with a makespan equal to 20 units (see Table 3.6). The demand deviations (%) due to the error terms are represented in Table 3.7. This shows that the over productions and the under productions are important for all the scenarios except for s 2 . b-In the case of preemption: For w = 6, the resolution of formulation 1 leads to the same schedule and the same quantities as in the case of splitting. In contrary, the resolution of formulation 2 leads to an equivalent solution with a makespan that is also equal to 23.33 units (Table 3.10). This solution is also a solution to the case of splitting. The jobs are assigned to the machines with different durations, but the produced theoretical quantities are the same as in the case of splitting: (40,50,80,70). Consequently, the over productions and the under productions are the same as those obtained in Table 3.9.

We can notice from the example that the overproduction and the underproduction quantities are important for all the scenarios. Nevertheless, the penalty function in formulation 2 lead to better results than the penalty function in formulation 1. The slack based formulations lead to solutions that correspond to scenarios which are not in the set of the potential realizations.

When the demand is uncertain and its satisfaction is a must, accepting overproduction or underproduction does not solve the real problem but only a relaxed version of this problem. Therefore, this modelling approach cannot be used in all activity sectors because overproduction and underproduction are not often accepted in practice. [START_REF] Ben-Tal | Robust optimization[END_REF] claimed that one should avoid whenever possible using slack variables in order to ensure the feasibility of the constraints. Therefore, we will present in section 3 another approach that provides feasible solutions under the discrete processing time scenarios without introducing slack variables. This approach called artificial scenario solution based approach is a constructive approach designed for decision-makers interested in using simple heuristics to generate robust solutions.

Artificial scenario solution based approach under discrete processing time scenarios

In contrary to the slack based approach, the artificial scenario solution based approach aims to construct a set of feasible solutions without introducing slack variables.

The artificial scenario solution approach is based on scenario analysis, is a form of projection under which we evaluate a solution under a scope of possible futures instead of considering a single exact future. The uncertainty of processing times is represented by discrete scenarios that reflect the future data realizations. And, the scope of their related future decisions is observed and evaluated.

The global approach description

The artificial scenario solution based approach is divided into four successive steps as described in algorithm 1.

Algorithm 1: Artificial scenario solution approach Data: Ω k : the set of potential scenario. 1 Construct the set of artificial scenarios of processing times Ω a k from Ω k the set of potential scenarios; 2 Construct the set of feasible solutions based on the artificial scenario solutions; 3 Compute the local performances of the artificial scenario solutions; 4 Compute the robustness measures of the artificial scenario solutions and their ranking;

In Step 1, from the set of potential scenarios Ω k , we construct a set of artificial scenarios Ω a k . We consider scenarios that are commonly used in practice by decision-makers. These artificial scenarios are:

• s max the scenario in which the processing times take the maximal values among all the values of the potential scenario processing times in Ω k ,

• s average the scenario in which the processing times take the average values among all the values of the potential scenario processing times in Ω k , it represents the called "forecast" scenario,

• s median the median scenario in which the processing times are computed by sorting the values of the potential scenario processing times in Ω k , and picking the middle ones,

• s min the min scenario in which processing times take the minimal values among all the values of the potential scenario processing times in Ω k ,

The term artificial is used to mean that these scenarios do not necessarily belong to the set of potential scenarios.

The artificial worst-case scenario s max is the scenario in which processing times take the maximal values among all the values of the potential scenarios. This scenario can inherently provide temporal protection due to the fact that the processing times are extended, and it can provide flexibility thanks to the offered margins.

But, the worst-case scenario is often viewed as pessimistic.

The average scenario s average can be used as an alternative scenario to s max since it increases only the processing times under the average while it reduces the processing times that are over the average. However, the average values do not reflect the tendency of the distribution. For this reason, we proposed also to compute the median scenario s median . The processing times of s median are values that divide the list of processing times among Ω k into a list of higher half and a list of lower half. p s median ij is found by arranging all the values from lowest value to highest value and picking the middle one.

s min is the scenario in which the processing times take the minimal processing times values over all the potential scenarios values. It represents the best-case scenario in opposite to s max . And finally, we construct random scenarios by picking processing time values on the potential scenario processing times, and we denote:

• s random the scenario of randomly picked processing times in Ω k ,

The objective is to compare the artificial scenario solutions that are commonly used in practice between them, and also to compare them to random solutions. For s max solution and s median solution particularly, some optimality (or approximation) results are provided in robust scheduling literature (seeAloulou and Della Croce (2008), Kasperski and Zieliński (2016)). We will verify if these properties can be extended to the studied problems.

In Steps 2 and 3, we generate a set of feasible solutions based on the artificial scenario solutions, and we compute their local performances when applied to each potential scenarios s ∈ Ω k .

An artificial scenario solution is composed of two decisions which are the matrix of assignments and the job permutations on machines. We will distinguish the case of splitting and the case of preemption:

a-In the case of splitting, for each artificial scenario s a , we solve the deterministic formulation LP Split by considering the processing time of the artificial scenario as data entry of the linear program. This leads to a matrix durations T s * a . Then, we compute the assignment ratio of each job j to each machine i according to the considered artificial scenario solution such as:

x s * a ij = t s * a ij p sa ij , ∀s a ∈ Ω a k (3.28)
We choose any feasible permutation to construct the optimal schedule. The algorithm 2 gives the example of s max solution computation under splitting.

Algorithm 2: Computation of the artificial scenario s max solution in the case of splitting Data: p smax ij : processing times under the artificial scenario s max Result: X s * max optimal assignment ratio matrix of s max 1 Solve (LP Split ) by considering the processing times (p smax ij ) of the scenario s max ; T smax ← optimal duration matrix of scenario s max ; 2 Compute the ratio of participation of each machine i to the realization of a job j under the considered artificial scenario solution

foreach (i ∈ M, j ∈ N ) do x s * max ij ← t smax ij p smax ij end return X s * max
Let M be the set of m machines and N the set of n jobs. For each artificial scenario solution, we calculate the local performances of the potential scenarios under this solution. For this purpose, we schedule each potential scenario s ∈ Ω k according to the assignment ratios of X s * a and then we compute its makespan under (3.29) and its regret

X s * a C s max (X s * a ) = max i∈M n j=1 p s ij x s * a ij ,
C s max (X s * a ) -C s * max (3.30)
where C s * max is the optimal makespan of the potential scenario s. b-In the case of preemption, for each artificial scenario s a , we solve the deterministic formulation LP pmtn by considering the processing times of the artificial scenario as data entry of the linear program. We compute the ratio of participation of each machine i to the realization of a job j (assignment ratios) under the considered artificial scenario solution as given in (3.28).

The algorithm 3 describes the computation of the artificial scenario s max solution under preemption:

Algorithm 3: Computation of the artificial scenario s max based solution in the preemptive case Data: p smax ij : processing times under the artificial scenario s max Result: X s * max optimal assignment ratio matrix of s max 1 Solve (LP pmtn ) by considering the processing times (p smax ij ) of the scenario s max ; T smax ← optimal duration matrix of scenario s max ; 2 Compute the ratio of participation of each machine i to the realization of a job j under the considered artificial scenario solution foreach (i ∈ M, j ∈ N ) do

x smax ij ← t smax ij p smax ij end return X s * max
As the sequence is part of the decision in the preemptive case, we solve the open shop corresponding to T s * a according to [START_REF] Gonzalez | Open shop scheduling to minimize finish time[END_REF]). We then deduce a permutation σ s * a and we denote:

σ s * a i (j) = j , if j is scheduled bef ore j on machine i. (3.31)
We could schedule each potential scenario s ∈ Ω k according to the optimal schedule of s a , i.e. we assign the jobs according to the assignment ratio solution X s * a and we sequence the jobs with respect to the permutation σ s * a . To correct the jobs overlapping, we use the right-shift algorithm introduced in Abumaizar and Svestka (1997). The second alternative is to compute the durations of the potential scenarios according to the artificial scenario assignment ratios and then construct for each scenario a feasible sequence by solving a preemptive open shop. The sequence is not necessary the same for all scenarios.

A feasible schedule for each scenario is then obtained: -p s ij x s * a ij is the sub-job j duration in machine i under scenario s according to s a assignment, -s s ij (X s * a ) is the starting time of job j in machine i under scenario s. We compute the maximal completion time of scenario s such as:

C s max (X s * a ) = max i∈M max j∈N (s s ij (X s * a ) + p s ij x s * a ij ). (3.32)
Finally, in Step 4, we evaluate the robustness of the computed solutions under the set of discrete scenarios Ω k . We use the classical robustness measures which are the worst-case makespan and the maximal regret under both splitting and preemption.

The worst-case makespan of the artificial scenario solution X s * a across all the scenarios of Ω k measures the maximal cost of X s * a . It is defined as

max s∈Ω k {C s max (X s * a )}, (3.33)
And the maximal regret of the artificial scenario solution X s * a across all the scenarios of Ω k measures the maximal deviation from the optimal makespans of the potential scenarios. It is defined as:

max s∈Ω k {C s max (X s * a ) -C s * max }, (3.34)
Let us consider the same example as given in the previous section to implement the artificial scenario solution based approach under both splitting and preemption:

Example 3.3.1 In the example 3.2.1, we represented the uncertainty of demands by 6 different scenarios corresponding to the future realizations of demands (Table 6.1), the matrix of speeds v ij is invariant (Table 3.5). Step 1: From the set of potential scenarios Ω 6 , we construct the set of artificial scenarios: we represent in Table 3.12 the job processing requirements (demands) of the artificial scenarios. The matrix of speeds is invariant. a-In the splitting case:

Step 2: For each artificial scenario, we solve using CPLEX the corresponding LP Split model to compute the optimal durations and then we compute the assignment ratios. These decisions are reported in Table 3.13.

Step 3: We schedule the potential scenarios according to the artificial scenario schedules (see C and Appendix C). We compute the local performances: the makespan and the regret of each potential scenario scheduled according to the artificial scenario schedule (Table 3.14).

To compute the regrets, we compute the optimal makespans of the potential scenarios:

Step 4: We compute the global performances, i.e. the worst-case makespans and the maximal regrets over the potential scenarios (Table 3.15). In this example, the ranking of the artificial scenario solutions according to the global performances shows that if the decision-maker aims to minimize the worst-case

X max J 1 J 2 J 3 J 4 M 1 6.
X min J 1 J 2 J 3 J 4
M 1 6.9 (0.69) 0.0 (0.0) 7.5 (1.0) 0.0 (0.0) M 2

3.1 (0.31) 0.0 (0.0) 0.0 (0.0) 11.25 (0.45) M 3 0.0 (0.0) 7.5 (1.0) 0.0 (0.0) 6.87 (0.55) But, we can notice that the gap between the global performances of s median , s average and s max is relatively low. We also compare the global performances of the robust artificial solutions and the optimal solution of the nominal scenario. The robustness measures of the nominal scenario solution given Table 3.16 show that the worst-case makespan and regret of s nominal are superior to those provided by the robust artificial scenario solutions. Similarly, we apply the artificial scenario solution based approach to the preemptive problem Rm|pmtn|C max under uncertain processing times. Contrarily to the Rm|Split|C max , the preemption requires to compute the sequence. We consider the same data example, as used in the previous section.

X random J 1 J 2 J 3 J 4 M 1 0.
Example 3.3.2 We have 6 scenarios of processing requirement and an invariant matrix of speed. Step 1: The set of the artificial scenarios is the same as given in Table 3.12.

Step 2: For each artificial scenario, we solve using CPLEX the corresponding LP pmtn model to compute the optimal durations. We construct an optimal permutation of each artificial scenario solution by solving

the subsequent preemptive open shop.

Step 3 and Step 4: We use the ratios and the permutation of the potential scenarios (see Table 3.18) to schedule the potential scenarios according to the artificial scenario schedule (see Appendix D). Then, we compute the local performances (see Table 3.19) and the robustness measures of each artificial scenario solution over the set of potential scenarios (see Table 3.20). As we can notice, the ranking of the artificial

s max J 1 J 2 J 3 J 4 ≺ M 1
1.25 (0.06) 4.5 (0.16) 25.0 (1.0) 0.0 (0.0)

J ≺ J 3 ≺ J 2 M 2
18.75 (0.94) 0.0 (0.0) 0.0 (0.0) 12.5 (0.25) J ≺ J 1 M 3 0.0 (0.0) 12.50 (0.83) 0.0 (0.0) 18.75 (0.75) J ≺ J 4

s average J 1 J 2 J 3 J 4 ≺ M 1
1.87 (0.13) 2.50 (0.11) 18.33 (1.0) 0.0 (0.0)

J ≺ J 3 ≺ J 2 M 2
12.22 (0.87) 0.0 (0.0) 0.0 (0.0) 10.45 (0.30) J ≺ J 1 M 3 0.0 (0.0) 10.41 (0.89) 0.0 (0.0) 12.29 (0.70) J ≺ J 4

s median J 1 J 2 J 3 J 4 ≺ M 1
1.66(0.12) 1.66 (0.07) 20.0 (1.0) 0.0 (0.0)

J ≺ J 3 ≺ J 1 M 2
11.66 (0.88) 0.0 (0.0) 0.0 (0.0) 11.66 (0.33) J ≺ J 4 M 3 0.0 (0.0) 11.66 (0.93) 0.0 (0.0) 11.66 (0.67 minimize the worst-case makespan and the maximal regret, the solution to choose is the artificial scenario s max solution. We notice a good improvement compared to the robustness measures of s nominal . In fact, the worst-case makespan of the nominal scenario is equal to 46.8 units (see Table 3.21).

) J ≺ J 2 s min J 1 J 2 J 3 J 4 ≺ M 1 0.0 (0.

Computational results

Data generator and test protocol

In the numerical experiments, we consider different problem sizes (Table 3.22): For each instance, a nominal scenario of processing times p n ij is randomly generated using a uniform distribution in the interval I= [5,50]. Around this nominal scenario, we generate the potential scenarios according to the following formula:

p s ij = p n ij (1 + ζ ij ) ∀s, ∀i, ∀j (3.35)
Where ζ ij is a random variable that reflects the variation. According to ζ ij we distinguish three uncertainty degree:

• for d = 1 we have a low uncertainty degree where the potential scenarios vary between -10% and 10% around the nominal scenario:

ζ ij ∼ U [-0.1,0.1] ,
• for d = 2 we have a medium uncertainty degree where the potential scenarios vary between -50%

and 50% around the nominal scenario:

ζ ij ∼ U [-0.5,0.5] ,
• and for d = 3 we have a high uncertainty degree where the potential scenarios vary between -100%

and 100% around the nominal scenario:

ζ ij ∼ U [-1,1] .
The artificial scenario based approach algorithm is coded in Java using ILOG CP LEX Concert to solve the mathematical formulations LP Split and LP pmtn . We have generated 1000 replications of nominal scenarios for each combination of m, n. We have varied the number of scenarios around the nominal one from 1 to 100 scenarios. Over the computational results, we use as robustness cost indicator the worstcase makespan deviation from the nominal makespan (Equation 3.36). This indicator allows to measure the rate of increase in the makespan when we opt for a robust solution X instead of a classical one, and it is computed below. C s * n max is the optimal makespan of a nominal instance when we suppose that the problem is not affected by uncertainty of processing times.

max s∈Ω k {C s max (X)} -C s * n max C s * n max , (3.36)
In all the reported figures, the horizontal axis represents the number of potential scenarios and the vertical axis represents the mean values of the worst-case makespan robustness cost (the standard deviations are negligible). Each curve is relative to an artificial scenario solution. We report the results according to the three uncertainty degrees (d = 1, 2, 3). We distinguish the case of splitting and the case of preemption.

Robustness cost of the artificial scenario solution evaluation

Artificial scenario solution robustness cost evaluation in the case of splitting

In the case of splitting, under low uncertainty degree, the results show that the worst-case makespan robustness cost of all the artificial scenario solutions follow a logarithmic trend line (e.g. Figure 3.7 and Figure 3.8).

For all the curves, the R-squared value are superior to 0.95, which is a good fit of the line to the data.

The analytic equation of the logarithmic trend line is given as:

y = b.ln(x) + b 0 (3.37)
where y is the worst-case makespan robustness cost and x is the number of potential scenarios considered besides the nominal one. The interpretation of the coefficients is as follows. When we add the first potential scenario to the nominal one (x = 1), the worst-case makespan robustness cost is equal to b 0 . Thus, b 0 can be considered as the initial robustness cost: when we cover a scenario besides the nominal one, the makespan increase by b 0 % compared to the case under which the processing times are certain. In small size workshops under small variety of jobs (Figure 3.7 graph a. and table d), the robustness costs are comprised between 3.5% and 8%. The logarithmic functions of the artificial solutions (X average and X median ) have very similar coefficients: around 3.7% as initial robustness cost and around 0.9% as an increase rate. X max initial robustness cost is slightly inferior to 3.3% but its increase rate is around 1%. X min has the highest initial robustness cost 4.77% but the lowest increase rate 0.62%.

When we increase the number of jobs, both the initial robustness costs and the increase rates decrease. For instance, under medium job variety (Figure 3.7 graphic b. and table d.), the robustness costs are comprised between 0.5% and 3.5%. The initial robustness costs are around 0.5% and the maximal rate of increase is equal to 0.63% and under high job variety (Figure 3.7 graph c. and table d.), the robustness costs are comprised between 0.12% and 0.8%, the initial robustness costs are around 0.1% and the rate of increase are also around 0.1%.

When we increase the number of machines, the initial robustness costs increase, but the increase is small. For instance, in medium size workshops under small job variety (Figure 3.8 graphic a. and table d.), the robustness costs are comprised between 4.8% and 12%. X max is the most robust while X median is the least robust. The initial robustness cost of X max equals 4.8% and its increase rate is small (0.68%). The initial robustness cost of X median equals 6.8% and its increase rate is small (0.98%). X average robustness cost gets close to X max robustness cost as the number of scenarios increases. The initial robustness cost of X min equals 7.7% and its increase rate is very small (0.43%). When we increase the number of jobs (Figure 3.8 graphics b. c. and table d.), once again both the initial robustness costs and the increase rates of the artificial scenario solutions decrease. The solution ranking according to the robustness cost is the same.

When we increase the degree of uncertainty, the robustness costs highly increase.

Under medium degree of uncertainty, we observe an important increase in which concern both the initial robustness cost and the increase rate of all the artificial scenario solution logarithmic trend lines. X min is clearly the less robust, its robustness cost become more significant as the job variety become important.

For instance, in small size workshops under low job variety (Figure 3.9 graphic a. and table d.), the initial robustness cost of X min is equal to 23% which represents a huge increase compared with the case of low uncertainty degree (more than five times more expensive) and the increase rate is equal to 3.5%. X max , X average and X median solutions have closest trend lines. Their initial robustness cost is around 18.22%

(more than five times more expensive) and their increase rate is around 5%.

The impact of the number of machines and the number of jobs increasing is still the same (e.g. Figure 3.9 graphic b. and Figure 3.10).

Under high uncertainty degree, the robustness cost of X max , X average and X median are still following logarithmic trend lines. The increase in both the initial robustness cost and the increase rate of X max , X average and X median is huge. For instance, in small size workshops under small job variety (Figure 3.11 graphic a. and table d.), the initial robustness cost of X max , X median and X average is around 40% (the robustness cost is 10 times more expensive compared to low uncertainty). The increase rates have also increased: around 10% for X max and X median and around 9.2% for X average . Under high uncertainty degree particularly, the robustness cost of X min follows a polynomial trend line instead of logarithmic trend line in the tested interval of scenario numbers, we approximate its trend line by a second degree polynomial function when x ∈ [1, 100]:

y = a 2 x 2 + a 1 x + a 0 i.e. dy dx = 2a 2 x + a 1 (3.41)
This means the variation of the robustness cost y is linear according to the number of scenarios x. This tendency could be explained by the fact that when the number of scenarios increases, the minimal processing times over the scenarios does not increase, in contrary they are more subject to decrease. Under high uncertainty degree, as the number of scenarios increases, the difference between s min and the worst-case scenario that leads the worst-case makespan will be important. Consequently, and contrarily to X max which the solution of the upper extreme scenario, the robustness of X min will highly decrease and consequently, its robustness cost will increase. The trend line increase will continue until we reach the minimum scenario and cover the worst-case scenario over all the potential scenarios that could be generated.

Under high uncertainty degree, we also notice that when we increase the number of jobs, the robustness costs of the artificial scenario solutions decrease slightly. However, they increase very significantly as the number of machines increases (Figure 3.12): the increasing tendencies are more accurate under high uncertainty than the decreasing tendencies. The computational tests in high size workshops lead to the same conclusions (see Appendix E).

Artificial scenario solution robustness cost evaluation in the case of preemption In this section, we report the computational results in the preemptive case. We remark that the preemptive case shares common properties with the splitting case concerning the evolution of the robustness costs graphic a. and table d.), the robustness costs of the artificial scenario solutions are comprised between 4.2% and 11%. The initial robustness cost of X max which is the most robust is equal to 4.2% and its increase rate is equal to 1%. X min is the less robust, its initial robustness cost is equal to 5% and its increase rate is equal to 1.2%. When we increase the number of jobs, both the initial robustness costs and the increase rates decrease. Under medium job variety Figure 3.13 graphic b. and table d.), the robustness costs of the artificial scenario solutions are comprised between 1.2% and 4.8% i.e. 3.5 times less expensive.

When we increase the numbers of machines, we notice an important increase in the robustness cost.

And this increase is also significant compared to the splitting case. For instance in medium size workshops under small job variety Figure 3.14 graphic a. and table d.), the robustness costs are comprised between 13% and 23%.

Under medium degree of uncertainty, in small size workshops under low job variety (Figure E.2 graphic a. and table d.), the robustness cost of X max is comprised between 21.18% and 42% while the robustness costs of the other solutions are comprised between 23% and 110%. The initial robustness cost of X max is equal to 21.18% and its increase rate is equal to 15.21%. The initial robustness cost of X average is equal to 23% and its increase rate is equal to 15.60%. The initial robustness cost of X median is equal to 27.18% and its increase rate is equal to 17.25%. The initial robustness cost of X min is equal to 28.45% and its increase rate is equal to 1.69%.

Finally, under high uncertainty degree, the robustness cost of X max , X average and X median , like in the splitting case, still follow a logarithmic trend lines while the robustness cost of X min follow a polynomial trend line exactly like in the case of splitting. For example, in small size workshops under small job variety (Figure 3.15 graphic a. and table d.), the worst-case makespan deviations of X max , X median and X average is between 44% and 53%. The initial robustness cost of X max is equal to 44.31% and its increase rate is equal to 11.23%. The initial robustness cost of X average is equal to 45.56% and its increase rate is equal to 12.57%

and the initial robustness cost of X median is equal to 53% and its increase rate is equal to 13.24%. When we increase the number of job, the robustness cost decreases. Under medium job variety (Figure 3.15 graphic b. and table d.), the initial robustness cost of X max and X average is around 24% while the initial robustness cost of X median is equal to 26.45%. The increase rate is equal to 11.43% for X max , 12.13% for X average , and 13.45% for X median . Under high job variety (Figure 3.15 graphic c. and table d.), the initial robustness cost of X max is around 12% while the initial robustness cost of X average and X median is around 14%. The increase rate is equal to 5.5% for X max and 6.73% for X average , and its around 6.85% for X median . The computational tests in high size workshops lead to the same conclusions (see Appendix E).

Results discussion and analysis

From the computational results, we can deduce that the robustness cost of the robust artificial scenario solutions increases as the number of scenarios increases or the degree of uncertainty increases. Indeed, when we need to cover more potential scenarios, we need to pay additional cost to be protected against uncertainty. But, as it was shown in the results, most of the robust artificial solutions follow a logarithmic trend line which means that the robustness cost increases quickly when we cover the first potential scenarios besides the nominal one (the initial robustness cost) then for each additional scenario, we pay a marginal cost.

Under small, medium and high uncertainty degree, X max , X average and X median follow logarithmic trend lines. Their robustness costs increase as the degree of uncertainty increases. Both the initial robustness cost and the increase rate are concerned by a such increase and this can be explained by the fact that the scenarios become very different.

In which concerns X min , we observe that this solution also follows logarithmic trend lines under small and medium uncertainty degrees. However, under high uncertainty degree, the trend line of X min is no longer logarithmic but it is polynomial for the considered interval of scenario numbers. As explained in the previous sections, the polynomial tendency could be explained by the fact that when the number of scenarios increase, the minimal processing times over the scenarios does not increase, in contrary they are more subject to decrease. As the number of scenarios that belongs to high uncertainty degree increase, the difference between s min and the worst-case scenario over the set of scenarios becomes important. Consequently, the ability of X min to withstand the worst-case scenario is small because when constructing s min , we do not provide any temporal margin. Consequently, X min do not absorb the variations which lead to a robustness cost that highly increases.

Furthermore, we observed that the robustness cost of the solutions increases as the number of machines increases and decreases as the number of jobs increases. This tendency can be related to the performance of the nominal solution more than the performance of the robust solutions. Indeed, when the number of machines is important, the optimization in the deterministic case of the nominal scenario can lead to a small makespan value which makes the deviation between this one and the worst-case makespan very important and consequently, it increases the robustness cost. But when the number of jobs is important while the number of machines is small, the optimization in the deterministic case of the nominal scenario can lead to an important makespan value which make the deviation between this one and the worst-case makespan very small and consequently it decreases the robustness cost which makes the robust solutions more interesting.

In the case of splitting under small and medium uncertainty degrees, the robust scenario solutions X max , X average , X median and X min lead to similar robustness costs except when the number of jobs is close to the number of machines. Under this special case, X max solution is clearly more robust. And under high uncertainty degree, the robustness cost of X min is extremely high.

Contrarily to the splitting case, in the preemptive case, the artificial scenario solution X max is more robust than the other artificial scenario solutions, followed by X average and X median , while X min solution is the least robust. This ranking is the same for all problem sizes and under all the uncertainty degrees. Besides, the artificial scenario solutions follow the same trend lines as in the splitting case but their initial robustness costs and their increase rates are more important. This increase is due to the non-overlapping constraints that induces idle times under the preemptive case. Moreover, the non-preemptive constraints allow to X max , which offers temporal protection, to perform better than the other robust solutions.

Conclusion

In this chapter, we have considered the makespan minimization on parallel machines under both splitting and preemption under uncertain processing times. We have shown first that the optimal solutions computed based on the nominal scenario leads to infeasible schedules, or schedules with poor performance when the processing times are uncertain. We then proposed a preliminary approach that aims to enforce the feasibility of the schedule under different scenarios by tolerating the violations of some processing requirements.

Slack variables are used to compensate a such a loss. However, the results show that under this approach the overproduction or the shortage are very important. Consequently, additional costs are needed to make the adjustments for all the scenarios. To avoid such efforts, we have proposed an artificial scenario based approach that does not require the slacks.

Under this approach, we have constructed a set of feasible solutions based on a set of artificial scenarios.

Then, we have chosen the robust solutions based on an evaluation algorithm that compute a robustness measure of each solution. The approach is resumed on a general algorithm composed of 4 steps with specific instructions in the case of preemption (to take into account the sequence decision). Thanks to this approach, the hard constraints are respected and the feasibility is insured without recourse actions.

We have done extensive computational experiments to test the validity of such an approach. Besides, we have shown that in both splitting and preemption case, the robustness cost of the artificial scenario solutions follow logarithmic line-trends according to the number of scenarios under low and medium uncertainty degrees. Under high uncertainty degree, the robustness cost of the considered artificial scenario solutions follow logarithmic line-trends except s min solution that has a polynomial line-trend which is very huge. Nevertheless, it will be necessary to verify this logarithmic tendency on other data generated differently to be sure that it does not depend on the data generation. Moreover, the interpretation of the solution X min polynomial trend line should be questioned especially that the number of considered scenarios in the computational test was limited to 100 scenarios.

In the next chapter, we will use the robust discrete optimization framework developed by [START_REF] Kouvelis | Robust discrete optimization and its applications[END_REF] to compute the optimal robust solutions for the makespan minimization on unrelated parallel machines with job splitting (resp.. preemption) under uncertain processing times. The objective is to reduce more the robustness cost of the solutions.

Chapter 4

Robust parallel machine scheduling with job splitting under uncertain processing times Abstract: The goal of this chapter is to propose robust formulations, based on the robust discrete optimization framework developed by [START_REF] Kouvelis | Robust discrete optimization and its applications[END_REF], to compute the optimal robust solutions for the makespan minimization on unrelated parallel machines with job splitting under uncertain processing times.

We show that the direct application of robust optimization techniques leads to no solution. To overcome this difficulty, we propose a formulation in which the uncertainty appears in the objective instead of the assignment constraints. Accordingly, we propose two formulations to compute robust solutions with min-max and min-max regret objectives. The computational tests show that these formulations are able to provide robust solutions in polynomial times. Extensive numerical experiments show that these formulations improve the robustness cost compared with the artificial scenario solutions. Lastly, we extend the robust formulations to the special cases of uniform and identical parallel machines.

Introduction

In this chapter, we apply the robust discrete optimization framework developed by [START_REF] Kouvelis | Robust discrete optimization and its applications[END_REF] to compute optimal robust schedules under uncertain processing times. The robust discrete optimization framework is a comprehensive mathematical programming framework for robust decision making under which the uncertainty is represented by discrete scenarios and the objective is to optimize a robustness measure. Accordingly, the deterministic linear formulation is extended to incorporate a discrete scenario representation and the objective is to optimize a global performance. Under the robust discrete optimization, the constraints are hard i.e." they must be satisfied for all the scenarios.

In Chapter 3, we have shown that in the formulation of the problem Rm|Split|C max , the uncertainty of processing times is affecting the data in the equality constraints while the objective and the inequality constraints are not affected with the uncertainty. Thus, the robust counterpart, which is an extension of the deterministic linear formulation, is a constraint feasibility problem. In this constraint feasibility problem, the objective is to find the schedule that is feasible under any scenario as expressed in the constraints below:

m i=1 t ij p s ij = 1, j = 1, . . . , n, s = s 1 , . . . , s k . (4.1)
But, the equality constraints cannot be insured for different scenarios. In order to construct a feasible schedule under all the scenarios, we propose to change the decision variables in the deterministic problem.

We will consider x ij as the assignment ratio of job j to machine i:

x ij = t ij
p ij . This transformation will lead to the deterministic linear programming (LP assign ) below:

Minimize C max Subject to m i=1 x ij = 1, j = 1, . . . , n, s = s 1 , . . . , s k n j=1 p ij x ij -C max ≤ 0, i = 1, . . . , m 0 ≤ x ij ≤ 1, i = 1, . . . , m j = 1, . . . , n
LP assign will return assignment ratios as decision variables instead of temporal durations. Accordingly, the processing times appear in the inequality constraints instead of the equality constraints. Based on this remark, we will be able to formulate and solve the robust versions according to the robust discrete optimization framework.

Let us denote M the set of m machines, N the set of n jobs, S the set of k discrete scenarios, and F the set of all feasible solutions under the constraints of the deterministic LP assign i.e

F = {(x ij ) i∈M,j∈N ∈ [0, 1] mn / m i=1 x ij = 1, ∀j ∈ N }.
To compute optimal robust solutions, we consider: the worst-case makespan which is already presented in Chapter 3 and the maximal regret.

We define the optimal robust solutions as follows:

Definition 4.0.1 We call a solution X optimal robust with respect to the worst-case makespan if it satisfies the following conditions:

• X is feasible for each scenario s ∈ S taken independently.

• Whatever the values of the processing times p s ij , X minimizes the worst-case makespan over all scenarios.

Definition 4.0.2 We call a solution X optimal robust with respect to the regret if it satisfies the following conditions:

• X is feasible for each scenario s ∈ S taken independently.

• Whatever the values of the processing times p s ij , X minimizes the maximal deviation from the optimal makespans over all scenarios.

In Section 4.1, based on the ratio transformation and the robust solution definitions, we formulate and solve the robust versions of Rm|Split|C max under discrete processing times scenarios. In Section 4.1.1, we formulate the mathematical model that minimizes the worst-case makespan (DmM(Rm|Split|C max ; p ij )), respectively, we formulate the model that minimizes the maximal regret (DmMR(Rm|Split|C max ; p ij )). We use the same example presented in Chapter 3 to illustrate the approach. In Section 4.2" we report the computational results based on the data generator given in Chapter 3. We report the computational times required to solve the proposed formulations under different problem sizes. Besides, we evaluate and compare the optimal robust solutions by measuring their the robustness cost, we compare them also to the artificial scenario solutions. In Section 4.3, we address the robust versions of parallel uniform machines Qm|Split|C max : DmM(Qm|Split|C max ; p ij ) and DmMR(Qm|Split|C max ; p ij ) and extend the results to the robust version of identical parallel machines P m|Split|C max ): DmM(P m|Split|C max ; p ij ) and DmMR(P m|Split|C max ; p ij ).

4.1 Formulations of the robust unrelated parallel machine scheduling problem with splitting under discrete processing time scenarios

In this section, we provide mathematical formulations to compute the optimal robust schedules on the unrelated parallel machine under splitting. We formulate the discrete min-max version of Rm|Split|C max under uncertain processing times to compute the robust solution minimizing the worst-case makespan in Section 4.1.1. And we formulate the discrete min-max regret version of Rm|Split|C max under uncertain processing times to compute the robust solution minimizing the maximal regret in Section 4.1.2.

We remind that in the splitting case, an optimal robust assignment solution leads to an optimal robust schedule with the same makespan without any sequencing constraints.

Formulation of discrete min-max version of Rm|Split|C max under discrete processing time scenarios

Let X be an element of F the set of feasible solutions. The completion time of machine i when the solution X is applied to the scenario s is defined as

C s i (X) = n j=1 p s ij x ij ,
and the makespan is defined as

C s max (X) = max i∈M {C s i (X)}.
The worst-case makespan of solution X over all the scenarios of S is then :

Z a (X) = max s∈S {C s max (X)}.
The discrete min-max version of Rm|Split|C max under uncertain processing times can be formulated as the problem of finding X * the optimal robust solution in absolute sense, i.e the solution that minimizes the worst-case makespan among all feasible solutions. It can be stated as

min X∈F max s∈S max i∈M {C s i (X)}.
Thus, the discrete min-max version of Rm|Split|C max under uncertain processing times could be formulated as the following mathematical model:

Minimize max s∈S max i∈M {C s i (X)} Subject to m i=1 x ij = 1, j = 1, . . . , n 0 ≤ x ij ≤ 1, i = 1, . . . , m, j = 1, . . . , n.
This formulation is nonlinear, we linearize max i∈M {C s i (X)} by introducing a variable C s max such that

C s i (X) ≤ C s max , i = 1, . . . , m, s = s 1 , . . . , s k .
This lead to the following (still nonlinear) formulation:

Minimize max s∈S {C s max } Subject to m i=1 x ij = 1, j = 1, . . . , n n j=1 p s ij x ij -C s max ≤ 0, i = 1, . . . , m, s = s 1 , . . . , s k 0 ≤ x ij ≤ 1, i = 1, . . . , m, j = 1, . . . , n
We linearize also max s∈S {C s max } by introducing a variable y such that The uncertain processing times appear in the inequality constraints instead of equality constraints which makes the model solvable.

The robust discrete min-max version of (Rm|Split|C max ) under uncertain processing times remains an LP. The proposed mathematical formulation has the same number of decision variables (mn + 1) as the (Rm|Split|C max ) reformulation and a set of additional constraints proportional to the number of scenarios:

n + m * k. Hence, and based on [START_REF] Khachian | A polynomial algorithm in linear programming[END_REF]; [START_REF] Karmarkar | A new polynomial-time algorithm for linear programming[END_REF], we have the following result:

Corollary 4.1.1 DmM(Rm|Split|C max ; p ij ), the robust version the polynomial-time solvable

Rm|Split|C max , is also polynomial.

Let us go back to our example 3.2.1.

Example 4.1.1 We solve LP w-Split , the formulation of the discrete min-max version of (Rm|Split|C max ),

under the six scenarios of processing requirements. The optimal robust solution in the absolute sense X w is reported in Table 4.1. Under this robust solution: 55% of J1 is processed on machine 1, and 45% on machine 2. J2 is mainly processed on machine 3, only 5% of its requirement is processed on machine 1. 72% of J3 is processed on machine 1, 12% is processed on machine 2 and 16% is processed on machine 3.

And finally, 43% of J4 is processed on machine 2 and 56.4% is processed on machine 3 and only 0.6% is processed on machine 1. The optimal worst-case makespan is equal to 27.16 time units. We notice that in this example, the worst-case makespan of the optimal robust solution X w is less expensive compared to the worst-case makespan of the robust artificial scenarios and the worst-case makespan of the nominal solution.

The gaps reported in Table 4.2 measure the relative deviation between the worst-case makespan of each solution and the worst-case makespan of X w .

s1: M J 1 J 2 J 3 J 4 M J 1 J 3 J 4 M J 2 J 3 J 4 s2: M J 1 J 2 J 3 J 4 M J 1 J 3 J 4 M J 2 J 3 J 4 s3: M J 1 J 2 J 3 J 4 M J 1 J 3 J 4 M J 2 J 3 J 4 s4: M J 1 J 2 J 3 J 4 M J 1 J 3 J 4 M J 2 J 3 J 4 s5: M J 1 J 2 J 3 J 4 M J 1 J 3 J 4 M J 2 J 3 J 4 s6: M J 1 J 2 J 3 J 4 M J 1 J 3 J 4 M J 2 J 3 J 4
4.1.2 Formulation of robust discrete min-max regret version of Rm|Split|C max under discrete processing time scenarios

In this section, we propose the mathematical formulation that computes the optimal robust solution minimizing the regret over all the scenarios.

Let X be an element of F . The maximal deviation of solution X is such that

Z r (X) = max s∈S {C s max (X) -C s * max }.
where C s * max is the optimal makespan of Rm|Split|C max under the scenario s. The robust discrete min-max regret version of Rm|Split|C max can be formulated as the problem of finding X the optimal robust solution in relative sense, i.e., the solution minimizing the maximal deviation from the optimal makespan over all the scenarios among all feasible solutions X ∈ F . It can be stated as

min X∈F max s∈S {max i∈M {C s i (X)} -C s * max }.
Thus, the robust discrete min-max regret version of (Rm|Split|C max ) under uncertain processing times could be formulated as the following mathematical model:

Minimize max s∈S {max i∈M n j=1 p s ij x ij -C s * max } Subject to m i=1 x ij = 1, j = 1, . . . , n 0 ≤ x ij ≤ 1, i = 1, . . . , m, j = 1, . . . , n.
This formulation is nonlinear. By the same reasoning as proposed in the previous section, we linearized

max i∈M n j=1 p s ij x ij by introducing a variable z s Minimize max s∈S {z s -C s * max } Subject to m i=1 x ij = 1, j = 1, . . . , n n j=1 p s ij x ij ≤ z s , i = 1, . . . , m, s = s 1 , . . . , s k 0 ≤ x ij ≤ 1, i = 1, . . . , m, j = 1, . . . , n.
We linearise also max s∈S {z s -C s * max } by introducing a variable y:

Minimize y Subject to m i=1 x ij = 1, j = 1, . . . , n z s -C s * max ≤ y, s = s 1 , . . . , s k n j=1 p s ij x ij ≤ z s , i = 1, . . . , m, s = s 1 , . . . , s k 0 ≤ x ij ≤ 1, i = 1, . . . , m, j = 1, . . . , n.
This leads to the following linear program:

Minimize y Subject to

m i=1 x ij = 1, j = 1, . . . , n n j=1 p ij s x ij -C s * max ≤ y, i = 1, . . . , m, s = s 1 , . . . , s k 0 ≤ x ij ≤ 1, i = 1, . . . , m, j = 1, . . . , n.
For each scenario s, we must solve a deterministic problem Rm|Split|C s max . Moreover, we can prove that for each scenario s there exists an optimal schedule such that the m machines complete simultaneously. This property can be formulated as

C s * max = n j=1 p s ij x s * ij , ∀i ∈ M, ∀s ∈ S.
Indeed, let us suppose that there exists an optimal schedule in which the m machines do not complete simultaneously. There exists a machine in which the completion time is higher than the completion times of the other machines. If j is the job that increases the completion time, we can split this job j and assign the sub-jobs of j to the other machines. By this procedure, the completion times of jobs are not increasing. We can repeat this procedure until we get an optimal schedule in which the m machines complete simultaneously.

By using this recent property, the new formulation of the problem is (LP r-Split ):

Minimize y Subject to

m i=1 x ij = 1, j = 1, . . . , n n j=1 p ij s (x ij -x s * ij ) ≤ y, i = 1, . . . , m, s = s 1 , . . . , s k 0 ≤ x ij ≤ 1, i = 1, . . . , m, j = 1, . . . , n.
Consequently, robust discrete min max regret version of Rm|Split|C max under uncertain processing time can be solved to optimality according to the proposed linear formulation.

The mathematical formulation of the robust discrete min-max regret version of Rm|Split|C max remains a LP as the optimal deterministic solutions of the discrete scenarios can be already calculated by determin- The optimal robust solution minimizing the maximal regret X r is represented in Table 4.3. Under this robust solution: 57% of J1 is processed on machine 1, and 43% on machine 2. J2 is processed on machine 1 for 25%, and for 75% on machine 3. 47% of J3 is processed on machine 1, 21% is processed on machine 2 and 32% is processed on machine 3. And finally, 40% of J4 is processed on machine 2 and 60% is processed on machine 3. The optimal regret is equal to 3.5 units. Under 4 scenarios: s 1 , s 2 , s 3 and s 5 , the regret is equal to 3.5 units while it is equal to 3.22 under s 6 and 2.82 under s 4 (See Figure 4.2). We notice in this example that the worst-case makespan of the optimal robust solution X r is less expensive compared to the worst-case makespan of the nominal solution but its is quite similar to the worst-case makespan of the robust artificial scenario solutions X max and X average (See Table 4.4). We will examine if this property could be generalized or not through the computational results.

s1: M J 1 J 2 J 3 M J 1 J 3 J 4 M J 2 J 3 J 4 s2: M J 1 J 2 J 3 M J 1 J 3 J 4 M J 2 J 3 J 4 s3: M J 1 J 2 J 3 M J 1 J 3 J 4 M J 2 J 3 J 4 s4: M J 1 J 2 J 3 M J 1 J 3 J 4 M J 2 J 3 J 4 s5: M J 1 J 2 J 3 M J 1 J 3 J 4 M J 2 J 3 J 4 s6: M J 1 J 2 J 3 M J 1 J 3 J 4 M J 2 J 3 J 4
In this section, we have formulated the robust versions of the problem Rm|Split|C max using two different objectives and we have shown that the robust solutions in the example have led to good improvements. In the next section, we have carried out extensive numerical experiments to test the performance of the proposed robust formulations.

Computational results

In these numerical experiments, we consider the different problem sizes and the three uncertainty degrees introduced in the test protocol Chapter 3. The objectives of the computational results are summarized in 2 points:

1. We report the CPU times required to solve the robust formulations for different problem sizes.

2. We analyse the robustness cost of the optimal robust solutions (as given in Chapter 3). We also compare the optimal robust solutions to X max and X average solutions. robustness cost is around 1% and the increase rate is also around 1%. The improvement in comparison with X max is very notifiable especially concerning the initial robustness cost (1% instead of 4%) which makes the robustness cost 4 times less expensive. The robustness cost of X r is comprised between 2.7% and 7%.

Its initial robustness cost is around 2.7% and the increase rate is around 1%. Here again, the improvement in comparison with X max is notifiable, the initial robustness cost is equal to 2.7% instead of 4%. Furthermore, we notice that the robustness cost of the robust optimal solutions become more and more interesting as the number of jobs increases. For instance, under high job variety (Figure 4.4 graph c. and table d.), the robustness cost of X w is almost null while the initial robustness cost and the increase rate of X r are negligible: the robustness cost of X r is comprised between 0.01% and 0.25%.

When we increase the number of machines, the robustness costs of the robust optimal solutions increase as it was the case for the artificial scenario solutions. For example, in medium size workshops under low job variety (Figure 4.5 graph a. and table d.), the robustness cost of X w is comprised between 2.3% and 7%. Its initial robustness cost is around 2.3% and its increase rate is around 1.29%. The improvement in comparison with X max is still significant as the initial robustness cost is equal to 2.3% under X w instead of 4.82% under X max but, we can observe that the ratio has decreased: the robustness cost is only 2 times inferior. The of X r is comprised between 3.8% and 8.2%. Its initial robustness cost is around 3.8% and the increase rate is around 1.5%. Once again, there is an improvement when we apply X r instead of X max , but the improvement ratio has decreased (only 1.26 times less expensive).

Under medium and high degrees of uncertainty, the the robustness costs of X w and X r increase but their trend lines are also logarithmic. For instance, under medium uncertainty in small size workshops under low job variety (Figure 4.6 graph a. and table d.), the worst-case relative deviation of X w is comprised between 4.44% and 27%. Its initial robustness cost is around 4.4% and the increase rate is also around 4.73%. In this case, the improvement in comparison with X max is very significant, we observe that the initial robustness cost of X w is more than four times less expensive (4.4% instead of 18.22%). The robustness cost of X r is comprised between 7.9% and 30%. Its initial robustness cost is around 8% and the increase rate is around 4.8%.

Furthermore, under high uncertainty degree, in small size workshops under low job variety (Figure E.4 graph a. and table d.), the initial robustness cost of X w is around 9%. The rate change is around 11%.

The initial robustness cost of X r is around 13% and its increase rate is around 3.4%. In both cases, the improvement in comparison with artificial scenario solutions is very significant. The initial robustness cost is 5 times less expensive when we use X w instead of X max and it is 3 times less expensive when we use X r instead of X max .

The curves in high size workshops lead to the same conclusions (See Appendix E).

Overall, the robustness costs of the robust optimal solution are very interesting. The initial robustness costs are relatively low besides the increase rates are insignificant. These properties are more accurate when the variety of jobs is important while the number of machines is small. In these special cases, the robust optimal solutions are very favourable and not expensive compared to the nominal solution under the deterministic case.

linear programs when the uncertainty of processing times is due to the uncertainty of demands.

Discrete min max versions of Qm|Split|C max under discrete processing time scenarios

When the parallel machines are uniform, the machine speeds are not job dependent:

p ij = p j /v i , ∀i ∈ M, ∀j ∈ N.
where v i is the speed of machine i and p j the processing requirement of job j.

In the deterministic case, there exists an optimal solution that consists in splitting each job into m subjobs, the size of the subjob of job j to assign to machine i is equal to the ratio v i m i=1 v i . The optimal assignment solution X * of Qm|Split|C max depends only on machine speeds.

x * ij = v i m i=1 v i , ∀i ∈ M, ∀j ∈ N. (4.3)
Consequently, the optimal makespan is such that:

C * max (X * ) = n j=1 p ij x * ij = n j=1 ( p j v i ) v i m i=1 v i = n j=1 p j m i=1 v i
The deterministic makespan calculation is done in O(n).

Case1: If the processing times are uncertain due to the uncertainty of job requirements, we will denote:

p s ij = (p s j )/v i
where p s j is the processing requirement of job j under scenario s. Given that the optimal solution X * depends only on machine speeds (See equation 4.3), X * is also an optimal solution for any scenario from S. The worst-case makespan of X * is then:

max s k ∈S C s k max (X * ) = max s k ∈S n j=1 p s k j m i=1 v i = 1 m i=1 v i max s k ∈S n j=1 p s k j .
Based on this equality, the worst-case scenario s w is the scenario where the total quantity of demand over jobs is maximal. Consequently, we have the following results:

* ij = v i m i=1 v i ∀i ∈ M , ∀j ∈ N .
The worst-case makespan is equal to the makespan of X * applied to the worst-case scenario s w where the total of job processing requirements is maximal.. Moreover, the maximal deviation of the solution X * over scenarios is

max s k ∈S {C s k max (X * ) -C s k * max } = max s k ∈S {C s k * max -C s k * max } = 0
which gives the following result:

Corollary 4.3.2 DmMR(Qm|Split|C max ; p j ) could be solved to optimality in constant time by mean of the deterministic optimal solution X * that depends only on machine speed such that x * ij = v i m i=1 v i , and the maximal deviation of X * is equal to zero.

Discrete min max versions of P m|Split|C max under discrete processing time scenarios

When the parallel machines are identical p ij = p j . We can then draw the same results as for the case uniform parallel machines with further simplification.

In the deterministic case, there exists an optimal assignment solution that consists in splitting each job j into m subjobs, the size of the subjob of j to assign to each machine i is equal to

p j m . x * ij = 1 m , ∀i ∈ M, ∀j ∈ N.
Consequently:

C * max (X * ) = n j=1 p j x * ij = n j=1 p j 1 m = 1 m n j=1 p j .
The deterministic makespan calculation is done in O(n).

If the processing times are uncertain and the uncertainty is due to job requirements, we will denote:

p s ij = p s j
Given that X * depends only on machines number, X * is also an optimal solution for any scenario from S. The worst-case makespan of X * is then:

max s k ∈S C s k max (X) = max s k ∈S n j=1 1 m p s k j = 1 m max s k ∈S n j=1 p s k j
Based on this equality, the worst-case scenario s w is the scenario where the total quantity of demand over jobs is maximal. Consequently, we have the following result:

Corollary 4.3.3 DmM(P m|Split|C max ; p j ) could be solved to optimality in O(n | S |) time by mean of the optimal deterministic solution X * where all the jobs are split into m equal sub-jobs:

x * ij = 1 m , ∀i ∈ M , ∀j ∈ N . And the worst-case makespan is equal to the makespan of X * applied to the worst-case scenario s w where the total of job processing requirements is maximal.. The maximal regret of the solution X * over scenarios is

max s k ∈S {C s k max (X * ) -C s k * max } = max s k ∈S { n j=1 p s k j m - n j=1 p s k j m } = 0
Thus, we have the following results:

Corollary 4.3.4 DmMR(P m|Split|C max ; p j ) could be solved to optimality in constant time by mean of the deterministic optimal solution X * where all the jobs are split into m equal sub-jobs, and the maximal deviation of X * is equal to zero.

Conclusion

In this chapter, we have applied the robust discrete optimization framework developed by [START_REF] Kouvelis | Robust discrete optimization and its applications[END_REF] to compute the optimal robust solutions for the makespan minimization on unrelated parallel machines with job splitting under uncertain processing times. We showed that the direct application of robust optimization techniques led to no solution. To overcome this difficulty, we proposed a formulation in which the uncertainty appears in the objective instead of the assignment constraints. For this purpose,

We used assignment ratios as decision variables instead of temporal variables, to insure the feasibility. We provide robust solutions in polynomial time using respectively the minimization of the worst-case makespan and respectively the minimization of the maximal regret. We also considered the special cases of uniform and identical parallel machines. For the unrelated parallel machines, the computational results show that the robust formulations can be solved with modest CPU times even for large size instances. The CPU time required to minimize the maximal regret is not so much higher than the CPU time required to minimize the worst-case makespan.

Besides, the computational results show that the robustness costs of the optimal robust solutions minimizing the worst-case makespan (resp. the maximal regret) also follow logarithmic trend lines. They increase when we increase the number of machines, the number of scenarios or the degree of uncertainty. But, they decrease when we increase the number of jobs. Moreover, these solutions reduce considerably the robustness cost compared to X max and X average solutions. The optimal robust solution that minimizes the worst-case makespan X w leads to very interesting results in term of robustness cost, followed by the optimal robust solution that minimizes the maximal regret X r .

In the next chapter, we extend the robust formulations to compute optimal robust solutions when we consider the preemptive case (Rm|pmtn|C max ) under discrete processing time scenarios.

Introduction

In this chapter, we extend the application of the robust discrete optimization framework to the preemptive unrelated parallel machines under discrete processing time scenarios. The major difference between the preemptive case and the splitting case is due to the computation of a sequence decision. Indeed, as it was mentioned earlier in chapters 3 and 4, the computation of a robust preemptive schedule on parallel machines is composed of two steps: the computation of a duration matrix and then the construction of a feasible sequence.

Under a set of discrete potential scenarios, some decision-makers might be interested in computing a robust assignment solution which is unique. In which concerns the sequence, they may tolerate to have different sequences (one per scenario). In Section 5.1, we propose robust formulations of (Rm|pmtn|C max )

that allow to answer the former concern. In Section 5.2, we present the computational results that allow to quantify the robustness cost of the optimal robust solutions and to compare them to the artificial scenario solutions.

Robust schedules based on the robust assignment solutions: A sequential approach

When decision makers are interested in computing a unique assignment solution and they accept to have different sequences and permutations (one per scenario), the problem can be solved in two steps as follows:

-The first step consists in computing a robust assignment solution x * ij in a proactive way as done in the case of splitting. This solution can be obtained by solving different robust formulations (see Sections 5.1.1 and 5.1.2). Therefore, we propose to change the decision variables in the static preemptive problem proposed by [START_REF] Lawler | On preemptive scheduling of unrelated parallel processors by linear programming[END_REF]. We consider x ij as the assignment ratio of job j to machine i: x ij = t ij p ij . This transformation will lead to the deterministic linear programming (LP pmtn-assign ) below:

Minimize C max Subject to m i=1 x ij = 1, j = 1, . . . , n, s = s 1 , . . . , s k n j=1 p ij x ij -C max ≤ 0, i = 1, . . . , m n i=1 p ij x ij -C max ≤ 0, j = 1, . . . , n 0 ≤ x ij ≤ 1, i = 1, . . . , m j = 1, . . . , n
LP pmtn-assign will return assignment ratios as decision variables instead of temporal durations. Based on this, we will formulate and solve the robust versions of the preemptive problem by extending the robust formulations given in the case of splitting (see Chapter4). The proofs are very similar.

-The second step consists in constructing a sequence for each scenario. This step can be postponed until the real scenario is revealed, or it can be executed in a proactive way under a reasonable number scenarios. We compute the duration matrix of each scenario according to the robust assignment solution as: d s ij = p s ij x * ij and then, we solve for each scenario s a preemptive open shop problem (Om|pmtn|C max ) according to [START_REF] Gonzalez | Open shop scheduling to minimize finish time[END_REF])'s algorithm by considering the durations d s ij s as data entries. In Section 5.1.1, we develop the robust assignment formulation to compute a solution minimizing the worst-case makespan. And in Section 5.1.2, we develop robust assignment formulation to compute a solution minimizing the maximal regret.

Formulation of the min-max version of Rm|pmtn|C max under discrete processing time scenarios

To provide a robust assignment solution minimizing the worst-case makespan, we can solve the discrete min-max version of Rm|pmtn|C max that we formulate as follows (LP w-pmtn ):

Minimize C w Subject to m i=1 x ij = 1, j = 1, . . . , n (5.1) n j=1 p s ij x ij -C w ≤ 0, i = 1, . . . , m, s = s 1 , . . . , s k (5.2) m i=1 p s ij x ij -C w ≤ 0, j = 1, . . . , n, s = s 1 , . . . , s k (5.3) 0 ≤ x ij ≤ 1, i = 1, . . . , m, j = 1, . . . , n (5.4)
In this formulation, x ij is the robust assignment ratio of job j to machine i that minimizes the worst-case makespan C w over all the scenarios (the proof is similar to the proof of the Rm|Split|Cmax).

The mathematical formulation of the robust discrete min max version of Rm|pmtn|C max for the computation of the robust assignment solution is an LP. Thus, the assignment problem is polynomial based on [START_REF] Khachian | A polynomial algorithm in linear programming[END_REF]; [START_REF] Karmarkar | A new polynomial-time algorithm for linear programming[END_REF]. Moreover, for each scenario s the construction of the resolution of the preemptive open shop is polynomial, solvable in O(r + min(r 2 , n 4 , m 4 )) where r is the number of nonzero elements in X the matrix of assignments x ij 's, and consequently:

Corollary 5.1.1 DmM(Rm|pmtn|C max ; p ij ), the robust version of the polynomial-time solvable Rm|pmtn|C max , is polynomial.

Example 5.1.1 By solving LP w-pmtn , the optimal robust assignment solution over the six scenarios (cf.

Figure 5.1) has a worst-case makespan of 28.92 units. Under this solution, J1 is processed for 43% on machine 1 and for 57% on machine 2. J2 is processed for 52% on machine 1, and for 48% on machine 3.

J3 is processed for 31% on machine 1 and for 45% on machine 2 and for 24% on machine 3 while J4 is processed for 16% on machine 2 and for 84% on machine 3 (see Table 5.1). Based on the robust assignment ratio solution X w , we construct the duration matrices corresponding to the six potential scenarios. Each scenario can be scheduled independently according to the robust assignment solution without exceeding the robust makespan. For this purpose, we can solve the six independent preemptive open shop problems. These schedules are represented in Figure 5.1. Compared to the nominal scenario solution X s nominal and the artificial scenario solutions X max and X average , the worst-case makespan has been reduced under X w (see Table 5.2).

FIGURE 5.1: Potential scenarios scheduled according to X w in the preemptive case

s1: M J 2 J 1 J 3 J 2 J 3 M J 1 J 3 J 4 M J 4 J 2 J 3 J 4 s2: M J 1 J 2 J 3 M J 3 J 1 J 4 M J 2 J 4 J 3 J 4 J 3 s3: M J 1 J 3 J 2 M J 4 J 1 J 3 M J 3 J 2 J 4 s4: M J 2 J 3 J 1 M J 3 J 1 J 4 M J 4 J 2 J 3 s5: M J 2 J 1 J 3 M J 1 J 3 J 4 M J 3 J 4 J 2 s6: M J 2 J 3 J 2 J 1 M J 1 J 3 J 4 M J 3 J 4 J 2

Formulation of the min-max regret version of Rm|pmtn|C max under discrete processing time scenarios

We can also provide a robust assignment solution by solving the min-max regret version of Rm|pmtn|C max under discrete processing time scenarios. Based on the proof given in Section (4.1.2) and by considering the constraints that prohibit the overlapping, we can formulate the problem as (LP r-pmtn ):

Minimize r max Subject to

m i=1 x ij = 1, j = 1, . . . , n n j=1 p ij s x ij -C s * max ≤ r max , i = 1, . . . , m, s = s 1 , . . . , s k n i=1 p ij s x ij -C s * max ≤ r max , j = 1, . . . , n, s = s 1 , . . . , s k 0 ≤ x ij ≤ 1, i = 1, . . . , m, j = 1, . . . , n.
In this formulation, x ij is the robust assignment ratio of job j to machine i that minimizes the maximal regret r max over all the scenarios. C s * max is the optimal makespan under scenario s. For each scenario s, we solve the deterministic problem Rm|pmtn|C s max under the scenario s to obtain C s * max . The computation of the robust assignment solution minimizing the maximal regret for the preemptive unrelated parallel machine is an LP. The optimal deterministic solutions of the discrete scenarios are already computed by solving the deterministic LPs of each scenario. Thus, the assignment problem is polynomial based on [START_REF] Khachian | A polynomial algorithm in linear programming[END_REF]; [START_REF] Karmarkar | A new polynomial-time algorithm for linear programming[END_REF]. Moreover, for each scenario s the construction of the resolution of the preemptive open shop is polynomial, solvable in O(r + min(r 2 , n 4 , m 4 ) where r is the number of nonzero elements in X the matrix of assignments x ij 's, which leads to the following: Corollary 5.1.2 DmMR(Rm|pmtn|C max ; p ij ), the robust version the polynomial-time solvable Rm|pmtn|C max , is also polynomial.

Example 5.1.2 By solving LP r-pmtn , the optimal robust solution X r that minimizes the maximal regret has a maximal regret equal to 4.02 units. The assignment ratios according to this solution are as follows: J1 is processed on machine 1 and 2 for 58% and 42% respectively. J2 is processed on machine 1 for 43%, on machine 2 for 1% and on machine 3 for 47%. J3 is processed for 34% on machine 1, for 37% on machine 2 and for 29% on machine 3. And finally, J4 is processed for 16% on machine 2 and for 84% on machine 3. Each scenario can be scheduled independently according to the robust assignment solution X r .

For this purpose, we construct the duration matrices corresponding to the six potential scenarios and solve their corresponding preemptive open shop problems. These schedules are represented in Figure 5.2: small, the optimization in the deterministic case of the nominal scenario can lead to an important makespan value, which makes the relative deviation between this one and the worst-case makespan of the robust optimal solution very small. And consequently, it makes the robust solution cost very interesting.

: M J 3 J 1 J 2 M J 2 J 3 J 1 J 4 M J 4 J 2 J 3 J 4 s2: M J 1 J 2 J 3 M J 3 J 4 J 1 J 2 M J 2 J 4 J 3 J 4 s3: M J 3 J 2 J 1 J 3 M J 2 J 3 J 4 J 3 J 1 M J 4 J 3 J 4 J 2 J 3 s4: M J 2 J 3 J 1 M J 3 J 1 J 2 J 4 M J 4 J 3 J 2 s5: M J 1 J 3 J 2 J 2 M J 4 J 2 J 1 J 3 M J 2 J 3 J 4 J 2 J 4 J 3 s6: M J 1 J 3 J 1 J 2 M J 4 J 1 J 2 J 3 J 1 J 3 M J 2 J 4 J 3 J 4 J 3

Conclusion

In this chapter, we have used the robust optimization techniques to address the preemptive unrelated parallel machine scheduling under uncertain processing times. We have proposed robust formulations of the

Introduction

To further develop the work presented in the previous chapters, we consider the fact that in manufacturing systems, discrete scenario representation permit to limit the set of possible futures but, in reality the workshop will often face new scenarios because of numerous factors of perturbations. Thus, focusing on the robustness as a unique objective can be restrictive. In fact, the solution robustness is guaranteed only for processing time realizations that belong to the represented scenario set. Consequently, from one hand, the robust solution might have no robustness guarantee if the real scenario is a new one. On the other hand, the robust approach is not useful to help the decision-maker understand how much the objective could deviate, nor how much adjustment should be taken to cover it. Indeed, depending on whether a plausible scenario is taken into account or not, the structure of the robust solution could be very different. This aspect of robustness dependency to the chosen scenarios was already pointed out by [START_REF] Roy | Robustness in operational research and decision aiding: A multi-faceted issue[END_REF] who claims that "adding or removing a scenario from the set of scenarios may lead to defining very different solutions as robust". From practitioners viewpoint, the quantification of these deviations under new scenarios both in terms of structure and performance is a very important question. Moreover, schedulers confronted with data uncertainty agree that it is difficult to list all the potential scenarios. Therefore, it is crucial to identify robust solutions whose structure and performance do not deviate significantly under new scenarios or to be able to choose the desired trade-off. In other words, it is important to choose among the robust solutions those with the most stable structure and the most stable performance.

In Chapters 3, 4 and 5, we dealt with the uncertain processing times in unrelated parallel machine scheduling under splitting (resp. preemption) by providing robust solutions under discrete processing time scenarios. The proposed approaches provided an efficient way to incorporate uncertainty in the models and to provide robust solutions. But, for both practical and computational reasons, it is impossible to take into account all the uncertainties. Demand uncertainty that induces uncertain processing times results from a variety of reasons: seasonal effect, changes in customers interests and needs, the number and the product quality/price of the competitors, etc. Consequently, it could be difficult for some sector of activity or during some economic periods to list all the potential scenarios, which means that a new scenario is always susceptible to occur. As the structure and the performance of the robust solution are very dependent on the set of discrete scenarios, the stability of the solutions can be affected if the real scenario is a not captured by the scenario generation process. Therefore, we evaluate the stability of the structure and the performance of the robust solutions when adding new scenarios. In this approach, the term stability is used for the algorithm step at which robust solutions of the problem have been already computed, and additional calculations are performed in order to investigate how these solution structure and performance depend on changes in the set of potential scenarios. In Section 6.2, we describe a robust solutions generation and stability analysis approach. In Section 6.3, we make a statistical analysis of the results. We choose the splitting problem as a case study to apply the approach and we show accordingly that the robust solution computed in Chapters 3, Algorithm 11: The magnitude of ratio changes computation at iteration k Data: M = {1, . . . , m} the set of m machines, N = {1, . . . , n} the set of n jobs X k-1 robust = (x k-1 ij ) i,j the robust solution for Ω k-1 X k robust = (x k ij ) i,j the robust solution for Ω k Result: M C k (X robust ): magnitude of ratio changes in the robust solution X robust at iteration k. // Initialisation M C k (X robust ) ← 0;

foreach i ∈ M do foreach j ∈ N do if (x k ij -x k-1 ij > 0) then M C k (X robust ) ← M C k (X robust ) + x k ij -x k-1 ij ; end end end return M C k (X robust )
This measure gives an idea about the handling operations necessary to make the adjustment. We choose the sup operator to count the change only once.

In the cases where permutation decisions are also important, we can consider also the permutation deviation. But we do not consider this issue in this work. Example 6.2.1 Let us consider the same example used in the previous chapters. We add a new scenario s 7 to the set of six scenarios: We take the example of X r . The new robust optimal solution X 7 r under the set ω 7 computed according to (LP r-Split ) is given as: When we apply X 6 r to the scenario s7, we obtain a makespan that is equal to 30.14 units. The worst-case makespan of X 6 r has increased and it is equal to 30.14 units instead of 29.34 units. Thus, the W CM D 7 of X r at iteration 7 is equal to 0.8 units.

Performance stability evaluation

In this section, we evaluate the performance stability of the robust solutions. For this purpose, we report the computational results concerning the worst-case makespan deviation (WCMD) under new scenarios. Under low uncertainty degree, the robust solution worst-case makespan deviations are insignificant (<< 1%).

In small size workshops under small job variety (Figure 6.1 graphic a.), the robust solution's WCMD are very low for all the solutions. The WCMD mean values of X max , X min , X w , X average and X median are around 0.01% with standard deviations that are around 0.03%. For X r , the WCMD mean value is equal to 0.06% with a standard deviation that is equal to 0.08%.

When we increase the number of jobs, we remark that the WCMD does not increase except for X w and X r (e.g. Figure 6.1 graphic b.). X w 's WCMD mean value is equal to 0.07% with a standard deviation that is equal to 0.13%. And the WCMD mean value of X r is equal to 0.23% with a standard deviation that is equal to 0.23%. When we increase the numbers of machines, we notice a small decrease in the WCMD especially for X r and X w . For instance, in medium size workshops under small jobs variety (Figure 6.1 graphic c.). X w FIGURE 6.12: Magnitude of ratio change under medium and high uncertainty degrees in the splitting case

The magnitude of ratio changes 0 0,2 0,4 0,6 0,8 1 X-max X-average X-median X-min X-w X-r X-l

Powered by TCPDF (www.tcpdf.org) Powered by TCPDF (www.tcpdf.org)

X w can be considered as quite stable: even when the number of changed ratios is important, the magnitude of ratio changes are very small. X average and X median are the less stable because under these solutions the numbers of perturbed jobs and perturbed machines are important, besides the number of changed ratios and the magnitude of changed ratios are significant.

The results also show that the structure stability of the solutions is highly affected by the degree of uncertainty increase and the number of machines. The solution structures become less stable. In the former case, this property is due to the fact that the new scenario under high uncertainty can be very different from the scenarios considered to compute the solution in the previous iteration, which lead to two solution structures that are very different. When we increase the number of machines, the number of alternative solutions increases and consequently the structures can be very different. The ranking of the solutions is not affected. Contrarily to the previous cases, the solution structure becomes more stable as the number of jobs increases due to the fact that the number of alternative solutions become small.

Conclusion

In this chapter, we proposed an approach to evaluate the stability of the structure and the performance of the robust solutions when adding a new scenario. In this approach, we used a 2 step-algorithm. In the first step, a set of robust solutions is computed according to the algorithms and formulations given in the previous chapters, and in the second step, additional calculations are performed in order to investigate how these solution structures and performances depend on changes in the set of potential scenarios. We evaluate the performance stability by computing the deviation of the worst-case makespan from the previous one when considering an additional scenario. And we evaluate the stability of the structure by computing different stability measures namely, the number of perturbed jobs and machines, the number of changed ratios, the number of new assignments and cancellations and the magnitude of ratio changes.. The computational results in the case of splitting show that under a new scenario, all the robust solutions are performance stable and globally they are structure stable. The worst-case makespan deviations and the magnitude of ratio changes are not significant. X max , X min and X w are the most stable. X average and X median and X r are less stable than the former ones. The structure stability of the solutions decreases as the degree of uncertainty increase. In fact, when the scenarios become very different, the solution structures also become significantly different. Besides, as the number of machines increases, the structure stability decreases. This could be explained by the fact that the number of potential solutions is more important when the number of machines is important. Contrarily to the degree of uncertainty and the number of machine effects, the solution structures became more stable as the number of jobs increases. We would extend the computational experiments to the preemptive case.

Conclusion and Prospects

The classical scheduling algorithms compute solutions assuming a full knowledge about data before the process of scheduling starts. However, the uncertainties and disruptions are prevalent in scheduling applications.

The study of robustness in scheduling allows to take into account these uncertainties and disruptions when they affect the scheduling problem. Throughout this thesis, we have been interested in scheduling on parallel machines under uncertain processing times. In the first case study, the splitting is tolerated, i.e., we consider that each job can be split into continuous sub-jobs processed independently on the machines so as to finish the processing of all demands as soon as possible. In the second case study, we consider the non-overlapping splitting that is termed in literature as preemption. When the objective is to minimize the makespan, the deterministic linear formulations that assume certain processing times allow solving these problems in polynomial times. But, they suffer from limitations to hedge against the uncertain processing times: they lead to infeasible or suboptimal schedules.

The methodology and the contributions proposed in this thesis can be represented according to the general framework of optimization under uncertainty (see Chapter 1) given in Figure 6.13.

Accordingly, we considered that the uncertainty of processing times is due to uncertain demands. In fact, the decision-maker deals with different potential futures without attached probabilities. Thus, the demand uncertainty can be typified as ambiguity and consequently, the processing time uncertainty is also an ambiguity. Based on the matrix of uncertainty type representations, the discrete scenario are suitable to represent the uncertain processing times. Thus, we modelled the uncertain processing times by a finite set of potential scenarios. Furthermore, we showed through an example that there is a need for a proactive schedule that takes into account different potential scenarios instead of a schedule that is updated each time that the real scenario is revealed. For these reasons, we opted for the robust scheduling approach in order to compute, in a proactive way, solutions that withstand the uncertain processing times. The literature in Chapter 2 also showed that the robust scheduling approach under discrete scenarios is effective to compute robust schedules under uncertain parameters.

Over this thesis, we used different algorithms and models to compute robust schedules under the discrete scenario of processing times. Firstly, we showed that under the slack based approach, when we aim to enforce the feasibility of the schedule under different potential scenarios by tolerating the violations of some processing requirements, the overproduction or the underproduction are very significant (both in splitting and preemption). To avoid these consequences, we proposed a second approach called "the artificial scenario based approach" that is summed up in a general algorithm composed of 4 steps. Under this approach, we built a set of feasible solutions based on a set of artificial scenario solutions that represent special policies such as the maximal scenario, the average scenario, the median scenario, etc.. We applied these solutions to the We showed that the artificial scenario solutions insured the feasibility of all the constraints without overproduction or underproductions, and besides they can provide good performances especially the artificial scenario solution X max . However, the computational results showed that the robustness costs of these solutions are not satisfying. Therefore, in Chapters 4 and 5, we proposed to compute optimal robust solutions under splitting and respectively preemption. We applied the robust discrete optimization framework developed by [START_REF] Kouvelis | Robust discrete optimization and its applications[END_REF] to compute the optimal robust solutions for the makespan minimization on unrelated parallel machines with job splitting (resp. preemption) under uncertain processing times. To insure the feasibility, we used assignment ratios as decision variables instead of the temporal variables in order to insure the feasibility of the constraints under the set of scenarios. This variable change allowed us to deal with the uncertain processing times in the objective instead of the equality constraints and to provide linear formulations to compute robust optimal solutions in polynomial times: we respectively minimized the worst-case makespan (min-max objective) and the maximal regret (min-max regret objective). To analyse the results provided by these approaches, we made extensive computational tests under which we distinguished different instance sizes and different uncertainty degrees. As first analysis, we focused in the robustness cost of the robust solutions. To evaluate the robustness cost of each solution, we define an indicator that measures the relative deviation between the worst-case makespan and the nominal makespan (i.e. the optimal makespan under the nominal scenario). The computational results showed that, in both splitting and preemptive cases, the robustness costs of the robust solutions increase as the number of scenarios increases or the degree of uncertainty increases. Indeed, when we need to cover more potential scenarios, we need to pay additional cost to be protected against the uncertain. But, most of the robust solutions follow logarithmic trend lines which means that the robustness cost increases quickly when we cover the first potential scenario besides the nominal one (the initial robustness cost) then for each additional scenario, we pay a marginal cost.

Under small uncertainty degree, for X max , X min , X average , X median , X w and X r , the trend lines as increasing logarithms i.e., each percent change in the number of scenarios is associated with a change of 0.01b in the robustness cost where b is the rate of increase of the logarithmic function.

The cost of robustness under small uncertainty degree can be considered as moderate. In the splitting case, X w followed by X r highly reduced the cost of robustness. X max , X min , X average , X median lead to very similar results, their robustness cost are quite superior to the optimal one. In the preemptive case, X w and X r also highly reduced the cost of robustness and besides X max is more robust compared to the other artificial scenario solutions. However, compared to the case of splitting, the robustness cost of the robust solutions is more important in the preemptive case.

Under medium uncertainty, the robustness costs of all the solutions increase under both splitting and preemption but, the properties and the solution ranking are the same. Under high uncertainty degree, the cost of robustness highly increases for all the solutions. For X min exceptionally, the cost of robustness becomes extremely huge and its trend line is no longer logarithmic but polynomial. This property is observed under both splitting and preemption. Once again, in the preemptive case, The artificial scenario solution X max is more robust than the other artificial scenario solutions. It is followed by X average and X median . And X min solution is the less robust. X w and X r a lead to the lowest robustness cost.

As second analysis, we considered a new issue in robust scheduling which is the stability of the robust solution performances under a new scenario. Indeed, the discrete scenario representation that permits to compute the robust solutions is used primarily to limit the set of possible futures but, in reality the workshop will often face new scenarios. Thus, focusing on the robustness of the performance under a specific set of scenarios as a unique objective can be restrictive. In fact, the solution robustness is guaranteed only for processing time realizations that belong to the represented scenario set. Consequently, from one hand, the robust solution might have no robustness guarantee if the real scenario is a new one. On the other hand, the robust approach is not useful to help the decision-maker understand how much the objective could deviate, nor how much adjustment should be taken to cover it. Indeed, depending on whether a plausible scenario is taken into account or not, the structure of the robust solution could be very different. This aspect of robustness dependency to the chosen scenarios was already pointed out by [START_REF] Roy | Robustness in operational research and decision aiding: A multi-faceted issue[END_REF] who claims that "adding or removing a scenario from the set of scenarios may lead to defining very different solutions as robust". From practitioners viewpoint, the quantification of these deviations under new scenarios both in terms of structure and performance is a very important question. Moreover, schedulers confronted with data uncertainty agree that it is difficult to list all the potential scenarios. Therefore, it is crucial to identify robust solutions whose structure and performance do not deviate significantly under new scenarios or to be able to choose the desired trade-off. In other words, it is important to choose among the robust solutions those with the most stable structure and the most stable performance.

The stability of the performance under a new scenario is measured through the worst-case makespan deviation, and the structure stability is measured according to different measures: the number of perturbed jobs, the number of perturbed machines, the number of changing ratios, the number of new assignments, the number of cancelled assignments and the magnitude of ratio changes.

Overall, the computational results show that X max is quite robust, performance stable and structure stable under all uncertainty degrees. Under small and medium uncertainty degrees, X min is quite robust, performance stable and structure stable but under high uncertainty degree, it is performance stable and structure stable but it is not robust. The most robust solution X w is moderately stable as its performance stability and its structure stability decrease as the degree of uncertainty increase. X r is also robust but less stable than X w . In which concerns X average and X median , these solutions are quite robust and quite stable under all the uncertainty degrees.

The results also show that the structure stability of the solutions is highly affected by the degree of uncertainty and the number of machines. The solution structures become less stable but, the ranking of the solutions is not affected. Contrarily to the previous cases, the solution structures become more stable when the number of jobs increases.

Research prospects

Following the results described in this thesis, the future works can be oriented towards the following developments.

As short term developments, we aim to address the robust preemptive problem with unique sequence.

Indeed, in some decision environments, the decision-maker does not admit having different sequences (one by scenario) but, in some sectors it might be necessary to compute a robust schedule with a unique assignment and a unique sequence. The main questions that arise from this are related to the complexity of the robust integrated problem resolution. Besides, it would be also interesting to extend the approaches developed in this thesis to the non-preemptive case which is known to be NP-hard even under certainty. The evaluation of the robustness cost in this case and if it also follows logarithmic trend line would be a good research question.

As mid and long-term developments, we can consider different future works. Indeed, in a real scheduling environment, there are possible scenarios in which activities may be added or removed (new jobs or cancelled jobs), or temporal constraints may be revised. Due to the practical importance, it is therefore desirable to extend our methodologies to modelling and solving these scheduling problems under job disruptions or resource disruptions.

Furthermore, it would be interesting to integrate reactive procedures with the robust scheduling approaches. In fact, in this thesis, we solved the scheduling problems from the perspective of proactive scheduling and obtained robust execution strategy off-line. One of our research efforts aims to integrate robust models with reactive scheduling algorithms, implement the obtained execution strategy and evaluate it.

And lastly, many additional opportunities for future research can be identified when adapting our approaches to an industrial context.

Abstract: Scheduling on unrelated parallel machines is a common problem in many systems (as semiconductors manufacturing, multiprocessor computer applications, textile industry, etc.). In this thesis, we consider two variants of this problem under uncertain processing times. In the first case, each job can be split into continuous sub-jobs and processed independently on the machines with allowed overlapping. In the second case which is termed preemption, we prohibit the overlapping. From a mathematical viewpoint, the splitting problem is a relaxed version of the preemptive problem. The objective is to minimize the makespan. The deterministic linear formulations provided by the literature allow solving these problems in polynomial times under the hypothesis of certainty. But when we consider uncertain processing times, these algorithms suffer from some limitations. Indeed, the solutions computed based on a nominal instance, supposed to be certain, turn usually to be suboptimal when applied to the actual realization of processing times.

Our approach consists in incorporating the uncertain processing times in these problems without making any assumption on their distribution. Hence, we use discrete scenarios to represent the uncertain processing times, and we adopt a proactive approach to provide robust solutions. We use special case policies that are commonly used in the industry to compute robust solutions. We show that the solutions based on some of those policies are potentially good in terms of robustness according to the worst-case makespan, especially the scenario s max solution under which all the processing times are set to their maximal values. However, the robustness costs of these solutions are not satisfying. Thus, we propose to compute optimal robust solutions. For this purpose, we use a variable change that allows us to formulate and solve, in polynomial times, the robust versions of the considered scheduling problems. Moreover, the computational results assert that the robustness cost of the robust optimal solutions is not usually very high. Moreover, we assess the stability of the robust solutions under a new scenario induced by variations. In fact, the decision-maker is only responsible for the consequences of the decisions when the processing time realizations are within the represented uncertainty set. Thus, we define stability of a robust solution as its ability to cover a new scenario with minor deviations regarding its structure and its performance.

Our main contributions in this thesis are to provide a guide to understand uncertainty issues and their handling, in particular in scheduling on parallel machines. In this context, we have proposed a solving approach to help decision-makers compute robust solutions and choose among these solutions those with the most stable structure and the most stable performance.

Keywords: robustness, min-max, min-max-regret, discrete processing time scenarios, parallel machines, stability analysis

6. 1

 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Robust solution stability analysis approach . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.1 Robust Solution Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.2 Stability Analysis of robust solution performances . . . . . . . . . . . . . . . . . . 6.2.3 Stability analysis of robust solution structures . . . . . . . . . . . . . . . . . . . . . 6.3 Computational results in the case of splitting: Statistical analysis . . . . . . . . . . . . . . . 6.3.1 Performance stability evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3.2 Structure stability evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3.3 Results synthesis and analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . types identified by different communities . . . . . . . . . . . . . . . . . . . . . 1.2 A unified taxonomy of uncertainty types . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Known uncertainty types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 The progressive transition from certainty to unknowns . . . . . . . . . . . . . . . . . . . . 1.5 Optimization approaches under data uncertainty . . . . . . . . . . . . . . . . . . . . . . . . 1.6 General framework for optimization under data uncertainty . . . . . . . . . . . . . . . . . . 2.1 A machine oriented Gantt chart . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Purely proactive scheduling approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Purely reactive scheduling approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Predictive-reactive scheduling approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Proactive-reactive scheduling approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6 A simplified clustering diagram on robustness and stability issues in scheduling . . . . . . . 3.1 An optimal schedule of the nominal instance in the splitting case . . . . . . . . . . . . . . . 3.2 An optimal schedule of the real instance in the splitting case . . . . . . . . . . . . . . . . . 3.3 Schedule of the real instance according to the nominal instance solution in the splitting case 3.4 An optimal schedule of the nominal instance in the preemptive case . . . . . . . . . . . . . 3.5 An optimal schedule of the real instance in the preemptive case . . . . . . . . . . . . . . . . 3.6 Schedule of the real instance according to the nominal instance solution in the preemptive case 3.7 Artificial scenario solution worst-case makespans in the splitting case: small size workshops under low uncertainty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.8 Artificial scenario solution worst-case makespans in the splitting case: medium size workshops under low uncertainty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.9 Artificial scenario solution worst-case makespans in the splitting case: small size workshops under medium uncertainty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.10 Artificial scenario solution worst-case makespans under splitting: medium size workshops under medium uncertainty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.11 Artificial scenario solution worst-case makespans under splitting: small size workshops under high uncertainty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.12 Artificial scenario solution worst-case makespans under splitting: medium size workshops under high uncertainty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

FIGURE

  FIGURE 1.3: Known uncertainty types

FIGURE 1 . 4 :

 14 FIGURE 1.4: The progressive transition from certainty to unknowns

FIGURE 1

 1 FIGURE 1.5: Optimization approaches under data uncertainty

FIGURE

  FIGURE 1.6: General framework for optimization under data uncertainty

  conceptual classifications . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.1 Uncertainty type classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.2 Uncertainty level classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2 Toward a unified taxonomy of data uncertainty . . . . . . . . . . . . . . . . . . . . . . 10 1.2.1 The consensus about uncertainty types . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2.2 The link between uncertainty types and uncertainty levels . . . . . . . . . . . . . 11 1.2.3 A unified taxonomy of data uncertainty . . . . . . . . . . . . . . . . . . . . . . . 12 1.3 Uncertainty representations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.3.1 Formal uncertainty representations . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.3.2 Practical uncertainty representations . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.3.3 Uncertainty representations and types relationship matrix . . . . . . . . . . . . . . 16 1.4 Optimization under uncertainty: Approaches and models . . . . . . . . . . . . . . . . 17 1.4.1 Stochastic optimization approach and models . . . . . . . . . . . . . . . . . . . . 17 1.4.2 Robust optimization approach and models . . . . . . . . . . . . . . . . . . . . . . 18 1.4.3 Fuzzy optimization approach and models . . . . . . . . . . . . . . . . . . . . . . 19 1.5 A general framework for optimization under data uncertainty . . . . . . . . . . . . . 20

  , etc.), job weight uncertainties (e.g.[START_REF] Pereira | The robust (minmax regret) single machine scheduling with interval processing times and total weighted completion time objective[END_REF]). Disruptions are discrete unforeseen events that occur and change the structure of the ongoing schedule, they concern both resources and jobs. The disruptions that are the most faced in production environments are machine breakdowns (e.g.[START_REF] Xiong | Robust scheduling for multi-objective flexible job-shop problems with random machine breakdowns[END_REF],[START_REF] Shi | Production planning and pricing policy in a make-tostock system with uncertain demand subject to machine breakdowns[END_REF],Wang et al. (2015) [START_REF] Ahmadi | A multi objective optimization approach for flexible job shop scheduling problem under random machine breakdown by evolutionary algorithms[END_REF]), new job arrivals[START_REF] Malve | A genetic algorithm for minimizing maximum lateness on parallel identical batch processing machines with dynamic job arrivals and incompatible job families[END_REF],[START_REF] Yang | Predictive-reactive scheduling on a single resource with uncertain future jobs[END_REF],[START_REF] Hosseini | Two meta-heuristics for solving a new two-machine flowshop scheduling problem with the learning effect and dynamic arrivals[END_REF],[START_REF] Rahmani | Robust and stable flow shop scheduling with unexpected arrivals of new jobs and uncertain processing times[END_REF]), job cancellations (e.g.

  uncertainties and unknown one (see the classification given in chapter 1). Known uncertainties and disruptions can be measured and represented somehow during the schedule generation while unknowns are revealed progressively during the schedule execution. Based on the level of knowledge, we can classify scheduling problems into three categories: scheduling under certain data, scheduling under known uncertainties or known disruptions, and scheduling under unknowns. Known uncertainties and disruptions are often observed in static environments while unknowns are often observed in dynamic environments. Processing times, due dates and release dates, are often treated as known uncertainties. And machine breakdowns are often treated as known disruptions (see for instance Xiong et al. (2013), Shi et al. (2014), Wang et al. (2015)). In contrary, new job arrivals and job cancellations are often treated as unknowns (e.g. Zhou et al. (2014) and Pei et al. (2016) assumed dynamic job arrivals as dynamic). Nevertheless, this classification can be different depending on the context and the application. For example, processing times could be considered as unknowns in a dynamic environment where their values are revealed progressively during the schedule execution and decision-makers do not have any knowledge to represent their values prior to the execution (see for instance Chiang et al. (2010)).

FIGURE 2 . 2 :

 22 FIGURE 2.2: Purely proactive scheduling approach

FIGURE 2 .

 2 FIGURE 2.4: Predictive-reactive scheduling approach

  to represent the robust versions of a scheduling problem α|β|γ. Let θ be the set of uncertain problem data, we will denote: DmM(α|β|γ; θ) the min-max version of α|β|γ under discrete scenario representation of θ (resp. DmMR(α|β|γ; θ) the minmax regret version of α|β|γ under discrete scenario representation of θ). Under interval representations, we denote ImM(α|β|γ; θ) and respectively ImMR(α|β|γ; θ).Daniels and Kouvelis (1995b) considered the single machine scheduling problem with a total flow time criterion (1|| c j ) under uncertain processing time, to formalize the concept of robust scheduling and to introduce the worst-case and the maximal regret measures under uncertain processing times. They showed that DmM(1|| c j ; p j ) and DmMR(1|| c j ; p j ) are NP-hard even in the case of two scenarios.[START_REF] Yang | On the robust single machine scheduling problem[END_REF] confirmed that minimizing the worst-case total flow time and the maximal regret in total flow time of the single machine problem under uncertain processing times are NP-hard and have proposed a dynamic algorithm, as well as polynomial heuristics to solve it. But, the complexity of these methods increases with the number of discrete scenarios. In the more general case, de Farias et al. (2010) proposed a cutting-plane algorithm for solving the DmM(1|| w j c j ; p j ) with the weighted sum of completion time

  considered the maximum lateness minimization on a single machine under stochastic machine breakdowns. The effects of disruption on planned activities are measured through job completion time deviation.[START_REF] Cowling | Using real time information for effective dynamic scheduling[END_REF] considered the single machine problem with the objective of minimizing the average completion time with no allowed preemption. They used the sum over all jobs of the starting time and completion time deviation divided by the number of jobs to measure the impact of moving from the initial schedule to the repaired schedule.Mehta and Uzsoy (1998) considered job shop environment under stochastic machine breakdowns. They presented a linear programming based heuristic that minimizes the deviation of the starting times, while respecting a deadline for the project. They inserted additional idle time into the schedule to absorb the impact of breakdowns, and invoked earliness or lateness penalties whenever the last operation of a job ends sooner or later than planned.Herroelen and Leus (2004a) adapted the linear programming based heuristic that was developed by[START_REF] Mehta | Predictable scheduling of a job shop subject to breakdowns[END_REF] to run in a project scheduling environment. They gave two mathematical programming models to minimize the expected weighted starting time deviation in order to construct a stable baseline project schedule, when the activities durations increase. Yang (2013) considered a single machine rescheduling problem. Disruptions such as new job arrivals and cancelled jobs occur after the initial scheduling. The objective is the minimization of the completion times deviation while preserving a small makespan. The artificial due dates for the remaining jobs are set to completion times in the original schedule while newly arrived jobs do not have due dates. The objective of rescheduling is to minimize the maximum earliness without tardiness. They developed three simple heuristics and demonstrated that two heuristics perform much better than the other one.[START_REF] Yin | Rescheduling on identical parallel machines with machine disruptions to minimize total completion time[END_REF] considered identical parallel machines subject to machine disruptions with the objective of minimizing the total completion time. The objective is to schedule the affected jobs and maximize the stability with respect to the original schedule. Schedule stability is measured by the completion time deviation. The study is bi-objective and focuses on the trade-off between the total completion time of the adjusted schedule and completion time deviation. They developed pseudo-polynomial-time solution algorithms for the problem with a fixed number of machines and conduct extensive numerical studies to evaluate the performance of the proposed algorithms.In project scheduling,Herroelen and Leus (2004a) devoted their attention to the development of the stable pre-schedule under uncertainty. They proposed two mathematical formulations to minimizing the expected weighted deviation of starting times under job disruption. In the former, they anticipate the disruption of one job duration while in the second one, they anticipate two disruptions. To serve as benchmark, they proposed three additional models. Some of these models are adapted from original version provided by the literature of machine scheduling as the linear programming based heuristic given in[START_REF] Mehta | Predictable scheduling of a job shop subject to breakdowns[END_REF].Only few studies considered both stability and robustness. Jorge[START_REF] Leon | Robustness measures and robust scheduling for job shops[END_REF] considered the job shop problem with stochastic machine breakdowns and processing time variations. The authors addressed the case of single disruption which serves as a basis for treatment of the more general case. The model is bi-objective and is based on the minimization of the expected makespan of the realized schedule (robustness) and the expected deviation from the original schedule makespan (stability). The experimental results

  (2005) considered a rescheduling problem on identical parallel machine environment subject to stochastic machine breakdowns. They addressed the trade-off between between efficiency and stability. They considered the total flow time as an efficiency measure while the stability is measured in terms of the number of disrupted jobs that are processed on different machines in the original and new schedules.[START_REF] Özlen | Generating all efficient solutions of a rescheduling problem on unrelated parallel machines[END_REF] considered unrelated parallel machine subject to stochastic machine breakdowns. They consider the total flow time as a performance measure and the total reassignment cost caused by the schedule deviation as stability measure. They illustrated that the efficient schedules with respect to the two objectives can be found in polynomial time.[START_REF] Ozlen | Rescheduling unrelated parallel machines with total flow time and total disruption cost criteria[END_REF] also considered unrelated parallel machines under stochastic machine breakdowns. The affected jobs are rescheduled by optimizing the total flow time, and the total reassignments cost caused by the differences between the initial and current schedules. They provided polynomial-time solution methods to the problems of minimizing total disruption cost among the minimum total flow time schedules and minimizing total flow time among the minimum total disruption cost schedules. Besides, they proposed exponential-time algorithms to generate all efficient solutions. The computational tests on large size problem instances show that the algorithm finds the best solution by generating only a small portion of all efficient solutions.[START_REF] Curry | Rescheduling parallel machines with stepwise increasing tardiness and machine assignment stability objectives[END_REF] examined the rescheduling in parallel machine problems due to the arrival of new jobs. They considered machine reassignment costs to minimize the instability. Their simulation experiments showed significant gains in schedule stability by selecting the alternative optimal solution with the fewest machine reassignment cost. Besides,[START_REF] Kaplan | Minimising the total weighted tardiness and instability for the parallel machine re-scheduling problem with deadlines and ready times[END_REF] considered the parallel machine disrupted by the arrival of new jobs, the departure of an existing job, and changes to job priority. A bi-criteria objective function was considered to simultaneously minimize both the total weighted tardiness and schedule instability. They formulated the problem by extending the mixed integer linear programming model of the scheduling problem in

FIGURE

  FIGURE 2.6: A simplified clustering diagram on robustness and stability issues in scheduling

TABLE 2 . 2 :

 22 Literature review synthesis (an overview)

Research question 2 :

 2 What is the robustness cost when we use a robust solution in order to withstand the uncertainty? Research question 3: Which solutions are robust stable when confronted to a new scenario? Introduction Parallel machine scheduling was and is still a rich and promising field of research with numerous applications in manufacturing lines, computer processing, preemptive multitasking, and multi-stage systems (see Cheng and Sin (1990)). The following examples illustrate the role of parallel machines in different applications(e.g. semi-conductors: Rossi (2003, 2010), Bilyk and Mönch (2012), Aubry et al. (2012), processors: Guinand et al. (2004), textile: Silva and Magalhaes (2006), aircraft planning: Hancerliogullari et al. (2013), etc.).

FIGURE 3 . 2 :

 32 FIGURE 3.2: An optimal schedule of the real instance in the splitting case

FIGURE 3 . 4 :

 34 FIGURE 3.4: An optimal schedule of the nominal instance in the preemptive case

FIGURE 3 . 5 :

 35 FIGURE 3.5: An optimal schedule of the real instance in the preemptive case

  of scenarios increases with one percent ( dx x = 1%), then the robustness cost will increase with b 100 . Thus, b can be considered as the increase rate: Each percent change in x is associated with a change of 0.01b in y.

FIGURE 3 . 7 :

 37 FIGURE 3.7: Artificial scenario solution worst-case makespans in the splitting case: small size workshops under low uncertainty

FIGURE 3 . 8 :

 38 FIGURE 3.8: Artificial scenario solution worst-case makespans in the splitting case: medium size workshops under low uncertainty

FIGURE 3 . 9 :

 39 FIGURE 3.9: Artificial scenario solution worst-case makespans in the splitting case: small size workshops under medium uncertainty

FIGURE 3 .

 3 FIGURE 3.10: Artificial scenario solution worst-case makespans under splitting: medium size workshops under medium uncertainty

FIGURE 3 .

 3 FIGURE 3.11: Artificial scenario solution worst-case makespans under splitting: small size workshops under high uncertainty

FIGURE 3 .

 3 FIGURE 3.12: Artificial scenario solution worst-case makespans under splitting: medium size workshops under high uncertainty

FIGURE 3 .

 3 FIGURE 3.13: Artificial scenario solution worst-case makespans in the preemptive case: small size workshops under low uncertainty

FIGURE 3 .

 3 FIGURE 3.15: Artificial scenario solution worst-case makespans in the preemptive case: small size workshops under high uncertainty

  need for robustness under uncertain processing times . . . . . . . . . . . . . . . . 51 3.1.1 Makespan minimization on unrelated parallel machines under splitting and preemption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.1.2 Limitations of the classical algorithms under uncertain processing times . . . . . . 53 3.2 Slack based approach under discrete processing time scenarios . . . . . . . . . . . . . 58 3.3 Artificial scenario solution based approach under discrete processing time scenarios . 62 3.3.1 The global approach description . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.4 Computational results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 3.4.1 Data generator and test protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 3.4.2 Robustness cost of the artificial scenario solution evaluation . . . . . . . . . . . . 72 3.4.3 Results discussion and analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

  C s max ≤ y, s = s 1 , . . . , s k . x ij -C s max ≤ 0, i = 1, . . . , m, s = s 1 , . . . , s k 0 ≤ x ij ≤ 1, i = 1, . . . , m, j = 1, . . . , n.C s max is an intermediate variable that could be eliminated, and then discrete min-max version of Rm|Split|C max under uncertain processing times can be solved to optimality by the linear program below LP w-Split : x ij ≤ y, i = 1, . . . , m, s = s 1 , . . . , s k 0 ≤ x ij ≤ 1, i = 1, . . . , m, j = 1, . . . , n.

FIGURE 4 . 1 :

 41 FIGURE 4.1: Potential scenarios scheduled according to X w in the splitting case

istic

  LPs. Compared to the mathematical model of Rm|Split|C max , the mathematical model of the robust discrete min-max regret version of Rm|Split|C max has the same number of decision variables and a set of additional constraints related to the discrete scenarios. Hence, and based on Khachian (1979); Karmarkar (1984), we have the following result: Corollary 4.1.2 DmMR(Rm|Split|C max ; p ij ), the robust version the polynomial-time solvable problem Rm|Split|C max , is also polynomial. Example 4.1.2 We solve LP r-Split the robust discrete formulation of min-max regret version of Rm|Split|C max .

FIGURE 4 . 2 :

 42 FIGURE 4.2: Potential scenarios scheduled according to X r in the splitting case

FIGURE 4 . 3 :

 43 FIGURE 4.3: CPU times of the robust formulations resolution in the case of splitting

4. 3 .

 3 Robust makespan on uniform and identical parallel machine scheduling problems with splitting under discrete processing time scenarios 103 Corollary 4.3.1 DmM(Qm|Split|C max ; p j ) could be solved to optimality in O(n | S |) time by mean of the optimal deterministic solution X * where: x

FIGURE 5 . 2 :

 52 FIGURE 5.2: Potential scenarios scheduled according to X r in the preemptive case

FIGURE 5 . 6 :

 56 FIGURE 5.6: Optimal robust solution worst-case makespans in the preemptive case: small size workshops under high uncertainty

FIGURE 6 . 1 :

 61 FIGURE 6.1: The worst-case makespan deviation under low uncertainty degree in the splitting case

FIGURE 6 .

 6 FIGURE 6.13: Application of the general framework to the parallel machines scheduling problems under uncertain processing times

TABLE 1

 1

			.1: Uncertainty type meanings and synonyms
	Type	Definition	Synonyms
	Aleatory

TABLE 1 . 2 :

 12 Uncertainty levels according to the economist risk analysis community

	Uncertainty level Meaning
	L1	Decision-maker admits that he is not absolutely certain,
		but he is able to measure the degree of uncertainty explicitly
	L2	Statistical uncertainty (Walker et al. (2003))
	L3	Decision-maker is able to enumerate multiple alternatives
		and is able to rank them in term of perceived likelihood.
	L4	Scenario uncertainty (Walker et al. (2003)): Decision-maker is able to
		enumerate multiple alternatives
		and is not able to rank them in term of perceived likelihood.
	L5	Recognized ignorance (Walker et al. (2003))
	the levels identified by Walker ((See Table 1.2). Walker et al. (2013) referred to scenario uncertainty and
	recognized ignorance as "deep uncertainty".

  2.

		FIGURE 1.2: A unified taxonomy of uncertainty types
		Uncertainty
	Aleatory		Epistemic
	Objective risk	Subjective risk	Ambiguity	Vagueness	Fundamental uncertainty

TABLE 1 .

 1 3: Uncertainty types and levels according to the economist philosophy

	level	Associated type
	Weak	Aleatory
		Subjective risk
	Strong Ambiguity
		Fundamental uncertainty

TABLE 1

 1

		.4: Uncertainty types and levels according to risk analysis community
	Level		Associated type
	L1	Decision-makers is not absolutely certain, but he is
		able to measure the degree of uncertainty explicitly
	L2	Statistical uncertainty (Walker et al. (2003))	Aleatory (objective risk)
	L3	Decision-maker enumerate multiple alternatives	Aleatory (subjective risk)
		rank them in term of perceived likelihood
	L4	Scenario uncertainty (Walker et al. (2003))	Ambiguity
	L5	Recognized ignorance (Walker et al. (2003))	Fundamental uncertainty

classification given by

[START_REF] Walker | Deep uncertainty[END_REF]

, we can also link the fourth level of uncertainty with the subjective risk.

Based on this, the level dimension and the type dimension are linked. These uncertainty types represent different level of severity, consequently we consider that the data uncertainty type dimension is correlated to what is called the level dimension.

TABLE 1

 1

	.5: Uncertainty representations and uncertainty types relationship matrix
		Objective risk Subjective risk Ambiguity Vagueness
	Objective Probability	x
	Subjective Probability		x
	Possibility theory			x
	Evidence theory			x
	Scenarios			x
	Weighted scenarios	x	x
	Intervals			x
	Fuzzy intervals			x
	Polyhedral sets	x	x	x

  Scenario model is suitable to model ambiguity. Under ambiguity, the uncertain demand can be represented by a vector of potential demands: d ∈ {d 1 , d 2 , ..., d n }. Under objective or subjective risk, the aleatory demand can be represented by a vector of potential demand scenarios with attached probabilities p i : d ∈ {(d 1 , p 1 ), (d 2 , p 1 ), ..., (d n , p n )}. These probabilities represent the weights of scenarios. Interval model can be considered as a scenario representation under which the number of scenarios is infinite. Therefore, we can

	consider that interval model can also be suitable to model ambiguity but with a continuous set. For example,
	if an expert can express its uncertainty as "demand will not be more than d and not less than d but I do not
	know exactly which value it will take", the most appropriate model is the interval model: d ∈ [d, d].

  1.6: General framework for optimization under data uncertainty

	COLLECT AND ANALYZE
	Analyze the available knowledge
	about the uncertain data
		SO
		M
	TYPIFY	ac
	Identify the uncertainty type and
	level dealt with
	(Figure 1.4)
	SELECT APPROACH	REPRESENT UNCERTAINTY
	Choose the optimization approach based	Model the uncertain data
	on uncertainty analysis and context	according to its identified type
	requirements	(Table 1.5)
	VERIFY
	Verify the adequacy between the
	approach and the uncertainty
	(Table 1.6)
	(Table
	MODEL AND SOLVE
	Choose the mathematical model
	based on the objective and the
	uncertainty representation
	ANALYZE
	Analyze the results, their
	applicability and make decisions

TABLE 2

 2

	.1: Complexity of min-max scheduling problems under discrete scenario represen-
		tation of data uncertainty
	D(I)mM(R)(α|β|γ; θ)	Complexities

criterion. Several inapproximability results for this problem are established in

[START_REF] Mastrolilli | Single machine scheduling with scenarios[END_REF]

.

[START_REF] Aloulou | Complexity of single machine scheduling problems under scenario-based uncertainty[END_REF]

studied several robust single machine scheduling problems. They proved that the minimization of the worst-case of general maximum cost function f max ∈ {C max , L max , T max } with job precedence under uncertain processing times (i.e. DmM(1|prec|f max ; p j )) is optimally solved in a polynomial time by the MinMax-Lawler algorithm. Moreover, they proved that DmM(1|| U j ; p j ) is

  2.6: A simplified clustering diagram on robustness and stability issues in scheduling

		Discrete scenarios or intervals	Proactive approach	Complexity issues
				Robustness
	Deterministic		measures
			Robust
	Post-optimization analysis		Scheduling (Daniels and Kouvelis 1995a)	Proactive-Reactive approach
	Stability	Stable	Robustness	Robust stable
	radius	(Sotskov 1991) Scheduling	Stability And	(Jorge Leon scheduling	Bi-objective
				1994)
	Optimal
	solution
			Stable
	Small		Scheduling (Wu et al.1993)		Stability measures
	variations
		Intervals		Stochastic
			Predictive
			Reactive
			approach

TABLE 2

 2

		.3: Parallel machine scheduling under uncertainty: review synthesis
	Scheduling problem				Objectives
	Environment	Performance	Uncertainty	disruption	Model Rob Stab	References
	P m	Makespan	pj		D	x	Xu et al. (2013)
	P m	Total flow time	pj		D	x	Drwal and Rischke (2016)
	Qm	Total flow time	pj		D	x	Xu et al. (2014)
	Rm	Total flow time	pj		D	x	Conde (2014)
	Rm	Total flow time	pj		D	x	Siepak and Józefczyk (2014)
	P m	Total flow time		brdwn	S	x	Azizoglu and Alagöz (2005)
	P m	Total flow time		brdwn	S	x	Özlen and Azizoglu (2009)
	Rm	Total flow time		brdwn	S	x	Özlen and Azizoglu (2009)
	P m	Total tardiness		new job	S	x	Kaplan and Rabadi (2015)
	P m	Total tardiness		new priority S	x	Kaplan and Rabadi (2015)
	P m	Total flow time		brdwn	S	x	Yin et al. (2016)

TABLE 3

 3

			.2: Nominal Instance
	p n ij	J 1	J 2	J 3	J 4
	M 1 30/3 50/2 30/4 100/1
	M 2 30/3 50/1 30/3 100/2
	M 3 30/3 50/4 30/4 100/4

TABLE 3

 3

			.3: Real instance
	p r ij	J 1	J 2	J 3	J 4
	M 1 50/3 30/2 80/4 50/1
	M 2 50/3 30/1 80/3 50/2
	M 3 50/3 30/4 80/4 50/4

  [START_REF] Mulvey | Robust optimization of large-scale systems[END_REF] suggested a general robust optimization framework for mathematical programs with continuous variables. This framework integrates a goal programming formulation with a scenario-based representation of uncertain problem data. The model based on Mulvey's framework recognizes that it may not always be possible to get a feasible solution to a problem under all the potential scenarios. Therefore, the model through the use of error terms and penalty function allows to find a solution that violates the

constraints by the least amount. Its objective is to compute a solution that remains "almost" feasible for any realization of s: a model robust solution. When we assume a discrete scenario representation of the processing times, based on Mulvey's approach, we propose a robust reformulation that admits the violation of these constraints. For this purpose, we add slack variables in the equality constraints as follows:

TABLE 3

 3

	.4: Potential scenar-
	ios of demand	TABLE 3.5: Matrix of
		speeds
	p 1 p 2 p 3	p 4
	s 1 30 50 30	100
	s 2 50 30 80	50
	s 3 40 50 100 80
	s 4 35 40 50	70
	s 5 40 60 100 50
	s 6 60 50 80	70

TABLE 3

 3

			.6: A slack based
		schedule based on formula-
			tion 1
	t ij	J 1	J 2	J 3	J 4
	M 1 1.25 0	18.75 0
	M 2 15	0	0	5
	M 3 0	8.75 0	11.25

TABLE 3

 3 Under formulation 2, for w = 6, the produced quantities are: (40, 50, 80, 70) with a makespan equal to 23.33 time units (Table3.8). The produced demand deviations are given in Table3.9.

		.7: Job processing
	requirement deviations in the
	splitting case based accord-
	ing to formulation 1 resolu-
		tion
	p 1	p 2	p 3	p 4
	s 1 +62.5%	-30%	+150% -45%
	s 2 -2.5%	+16.6% -6.25% -10%
	s 3 +21.87% -30%	-25%	-43.75%
	s 4 +39.2%	-12.5%	+50%	-21.42%
	s 5 +21.87% -41.66% -50%	+10%
	s 6 -18.75% -30%	-6.25% -21.42%

TABLE 3

 3

		.8: A slack based
	schedule according formula-
	tion 2 resolution
	J 1	J 2	J 3 J 4
	M 1 3.33 0	20 0
	M 2 10	0	0	13.33
	M 3 0	12.5 0	10.83

TABLE 3

 3

		.9: Job processing
	requirement deviations in the
	splitting case based on for-
		mulation 2
	p 1	p 2	p 3	p 4
	s 1 +33.33% 0%	+16.66% -30%
	s 2 -20%	+66.6% 0%	+40%
	s 3 0%	0%	-20%	-12.5%
	s 4 +14.28% +25%	-60%	0%
	s 5 0%	-16.66% -20%	+40%
	s 6 -33.33% 0%	0%	0%

TABLE 3 .

 3 10: Model robust solution in the preemptive case based on formulation 2

	J 1	J 2	J 3 J 4
	M 1 1.66	1.66	20 0
	M 2 11.66 0	0	11.66
	M 3 0	11.66 0	11.66

TABLE 3 .

 3 11: Optimal makespans of the potential scenarios in the splitting case

		s 1	s 2	s 3	s 4	s 5	s 6
	C s * max	23.12 19.23 25.83 19.79 23.46 25.0

TABLE 3

 3

	.12: Job processing requirements of the artificial scenarios
	Ω a k	p 1	p 2	p 3	p 4
	s max	60	60	100	100
	s average 42.5 46.66 73.33 70
	s median 40	50	80	70
	s min	35	30	30	50
	s random 40	60	100	50

TABLE 3 .

 3 13: Optimal schedules of the artificial scenarios in the splitting case: durations (ratios)

TABLE 3 .

 3 14: Local performances of the artificial scenario solutions in the splitting case

		Measures	s 1	s 2	s 3	s 4	s 5	s 6
	X max	Makespan	28.75 25.20	29.16 21.37 29.16 26.25
		Regret	5.62	5.97	3.33	1.58	5.701 1.25
	X average Makespan	28.27 25.14	29.11 21.04 29.11 26.74
		Regret	5.14	5.91	3.28	1.25	5.65	1.74
	X median Makespan	27.97 24.16	28.33 22.08 28.33 28.33
		Regret	4.85	4.93	2.49	2.29	4.87	3.33
	X min	Makespan	26.25 31.456 34.16 20.52 34.16 33.75
		Regret	3.12	12.22	8.33	0.72	10.70 8.75
	X random Makespan	29.42 26.38	28.30 24	23.46 32.95
		Regret	6.3	7.15	2.47	8.51	0	7.95

makespan or the regret, then the solution to choose is the artificial scenario s median solution (X median ).

TABLE 3 .

 3 15: Robustness measures of the artificial scenario solutions in the splitting case Artificial scenario solution Worst-case makespan Maximal regret

	X max	29.16	5.97
	X average	29.11	5.91
	X median	28.33	4.93
	X min	34.16	12.22
	X random	32.95	8.51

TABLE 3 .

 3 16: Local performances of the nominal scenario solution in the splitting case

	X s1	s 1	s 2	s 3	s 4	s 5	s 6
	Makespan	23.12 40.04 43.95 28.66 45.08	45.62
	Regret	0.0	20.81 18.12 8.875 21.625 20.62
	See the schedules in Appendix C.
	b-In the preemptive case:

TABLE 3

 3

.17: Optimal makespans of the potential scenarios in the preemptive case

TABLE 3 .

 3 18: Optimal schedules of the artificial scenarios in the preemptive case: durations (ratios) and permutation

TABLE 3 .

 3 19: Local performances of the artificial scenario solutions in the splitting case

		Measures	s 1	s 2	s 3	s 4	s 5	s 6
	X max	Makespan	31.25 23.5	30	22	30.83 27.5
		Regret	6.25	3.5	4.12	2	5.83	2.5
	X average Makespan	32.5	23.81 29.44 22.9	30	27.9
		Regret	7.5	3.81	3.56	2.9	5	2.9
	X median Makespan	33.3	25	28.33 23.33 28.66 31.66
		Regret	8.3	5	2.45	3.33	3.66	6.66
	X min	Makespan	35.19 27.73 37.7	25.75 40.2	32.65
		Regret	10.19 7.73	11.82 5.75	15.2	7.65
	X random Makespan	32.5	21.66 28.5	24	25	27
		Regret	7.5	1.66	2.62	4	0	2

scenario solutions according to the robustness measures shows that for the decision-maker who aims to

TABLE 3 .

 3 20: Robustness measures of the artificial scenario solutions in the preemptive case Artificial scenario solution Worst-case makespan Maximal regret

	X max			31.25		6.25
	X average			32.5		7.5
	X median			33.3		8.3
	X min			40.02		10.19
	X random			32.5		7.5
	TABLE 3.21: Local performances of the nominal scenario solution in the preemptive case
	X s1	s 1 s 2	s 3	s 4	s 5	s 6
	Makespan	25 43.33 46.67 28.34 46.67 46.67
	Regret	0	23.33 20.78 8.34	21.67 21.67

TABLE 3

 3

		.22: Instance size generation
		small size	medium size high size
	low variety	(m=3,n=10)	(m=7,n=10)	(m=15,n=15)
	medium variety (m=3,n=50)	(m=7,n=50)	(m=15,n=50)
	high variety	(m=3,n=200) (m=7,n=200) (m=15,n=200)

TABLE 4

 4

	.1: An optimal robust solution minimizing the worst-case makespan in the splitting
			case: (X w )
	x w ij	J 1	J 2	J 3	J 4
	M 1 0.55 0.05 0.72 0.006
	M 2 0.45 0	0.12 0.43
	M 3 0	0.95 0.16 0.564
	TABLE 4.2: The worst-case makespan gaps under X w in the splitting case
	X	Worst-case makespan Gap(%)
	X s nominal		45.62		67%
	X max		29.16		7.3%
	X average		29.11		7.17%

TABLE 4

 4

	.3: An optimal robust solution minimizing the maximal regret in the splitting case:
			(X r )
		J 1	J 2	J 3	J 4
	M 1 0.57 0.25 0.47 0
	M 2 0.43 0	0.21 0.40
	M 3 0	0.75 0.32 0.6
	TABLE 4.4: The worst-case makespan gaps under X r in the splitting case
	X	Worst-case makespan Gap(%)
	X s nominal		45.62		55.4%
	X max		29.16		-0.6%
	X average		29.11		-0.7%

TABLE 4

 4

		.5: CPU times for the optimal worst-case makespan computation under different
					problem sizes
						CPU(ms)
	m	n |S| = 3 |S| = 6 |S| = 12 |S| = 24 |S| = 48 |S| = 64 |S| = 96
		10	2.1	3.4	3.7	5.8	7.3	9.6	37.9
	7	50	10.0	11.5	12.7	46.5	66.0	93.0	110.6
		200	35.2	45.7	119.3	155.9	468.0	591.2	791.2
		15	3.1	5.4	7.5	9.2	9.3	11.6	56.2
	15	50	30.0	45.5	62.7	96.2	116	154	278.5
		200	105.2	130.9	215.9	270.5	540.4	1250.9	1930.5
	TABLE 4.6: CPU times for the optimal regret computation under different problem sizes
						CPU(ms)
	m	n |S| = 3 |S| = 6 |S| = 12 |S| = 24 |S| = 48 |S| = 64 |S| = 96
		10	2.9	4.1	4.7	6.3	7.3	10.4	42.5
	7	50	12.0	15.4	16.3	57.2	87.0	112.0	147.5
		200	45.7	56.2	123.4	176.1	494.0	620.4	810.2
		15	4.6	6.6	8.8	11.2	13.2	14.6	69.1
	15	50	42.0	62.5	62.7	96.2	130	173	298.2
		200	114.1	160.1	250.2	346.7	892.3	1506.5	2305.2

  The complexity results in the case of splitting are summarized in the table

	4.3. Robust makespan on uniform and identical parallel machine scheduling problems with splitting under discrete processing time scenarios 105
	TABLE 4.7: Complexity results in the case of splitting
	DmM(R)(α|β|γ; θ)	Complexities References
	DmM(Rm|Split|C max ; p ij )	Polynomial	Section 4.1.1
	DmMR(Rm|Split|C max ; p ij ) Polynomial	Section 4.1.2
	DmM(Qm|Split|C max ; p ij )	Polynomial	Section 4.3.1
	DmMR(Qm|Split|C max ; p ij ) Polynomial	Section 4.3.1
	DmM(P m|Split|C max ; p ij )	Polynomial	Section 4.3.2
	DmMR(P m|Split|C max ; p ij ) Polynomial	Section 4.3.2
	below:

TABLE 5 .

 5 1: An optimal solution minimizing the worst-case makespan in the preemptive case: (X w )

	X * w	J 1	J 2	J 3	J 4
	M 1 0.43 0.52 0.31 0
	M 2 0.57 0	0.45 0.16
	M 3 0	0.48 0.24 0.84
	TABLE 5.2: The worst-case makespan gaps under X w in the preemptive case
	X	Worst-case makespan Gap(%)
	X s nominal		46.67		61%
	X max		31.25		7.8%
	X average		32.5		12.1%

TABLE 6

 6

	.1: Job processing requirements scenarios
	p 1	p 2 p 3	p 4
	s 1 30	50 30	100
	s 2 50	30 80	50
	s 3 40	50 100 80
	s 4 35	40 50	70
	s 5 40	60 100 50
	s 6 60	50 80	70
	s 7 100 50 90	40

TABLE 6

 6

		Complexities References
	DmM(P m|Split|C max ; p j )	Polynomial	Chapter 4
	DmMR(P m|Split|C max ; p j ) Polynomial	Chapter 4
	DmM(Qm|Split|C max ; p j )	Polynomial	Chapter 4
	DmMR(Qm|Split|C max ; p j ) Polynomial	Chapter 4
	DmM(Rm|Split|C max ; p j )	Polynomial	Chapter 4
	DmMR(Rm|Split|C max ; p j ) Polynomial	Chapter 4
	DmM(Rm|pmtn|C max ; p j )	Polynomial	Chapter 5
	DmMR(Rm|pmtn|C max ; p j ) Polynomial	Chapter 5

.4: Complexity of min max parallel scheduling problems under discrete scenario uncertainty D(I)mM(R)(α|β|γ; θ)

0.05ln(x) + 0.005 0.96 d. logarithmic trends

Acknowledgements

First and foremost, I wish to thank my advisors: Mrs M.-L. Espinouse, Professor at the University of Grenoble and Mr V.-D. Cung, Professor at Grenoble Institute of Technology. They have been supportive

Powered by TCPDF (www.tcpdf.org) Powered by TCPDF (www.tcpdf.org) Powered by TCPDF (www.tcpdf.org) Powered by TCPDF (www.tcpdf.org) Powered by TCPDF (www.tcpdf.org) Powered by TCPDF (www.tcpdf.org) Powered by TCPDF (www.tcpdf.org) Powered by TCPDF (www.tcpdf.org) Powered by TCPDF (www.tcpdf.org) Powered by TCPDF (www.tcpdf.org) Powered by TCPDF (www.tcpdf.org)

Chapter 3

Toward a robust schedule on unrelated parallel machines under uncertain processing times Abstract: The goal of this chapter is to address the makespan minimization on parallel machines with job splitting (resp. preemption) under uncertain processing times. We show that when the processing times are uncertain, the optimal solutions computed based on the nominal scenario can lead to infeasible schedules, or schedules with poor performance. To remedy this, we anticipate the uncertainty by constructing proactively robust schedules. In the first approach, we enforce the feasibility of the schedule under the set of potential scenarios by tolerating the violations of some processing requirements. We use a weighted function of slack variables to control the violations. We show that the schedule constructed under this approach can lead to important overproduction and underproduction for some jobs. In the second approach, we guaranty the feasibility under a set of potential scenarios without violations: we construct a set of feasible solutions based on artificial scenario schedules and we choose over this set the solution that leads to the best performance in the worst-case. This second approach allows to respect the constraints of the problem under any potential scenario, and allows to construct a schedule with a good performance.

Contents

according to the number of scenarios, the number of jobs, the number of machines and the uncertainty degrees. The robustness costs of the artificial scenario solutions also follow a logarithmic trend line under low and medium uncertainty degrees (see Figure 3.13, Figure 3.14). The robustness costs increase as the number of machines increases and decrease as the number of jobs increases. But we notice a major difference compared to the splitting case: overall, X max is the most robust and X min is the less robust. Moreover, the robustness costs are slightly more important compared to the case of splitting. For instances:

For instance, under low uncertainty degree in small size workshops under small job variety (Figure 3.13 With respect to point (1), the results regarding the computational times for varying problem sizes have been summarized in Table 4.6. The reported CPU times clearly illustrate the effect of the problem size on the CPU times. We notice that the computational times increases highly as the size of the deterministic problem increases while the curve maintain the same trends. For both worst-case makespan and maximal regret, the computational time increases as the number of scenarios increases. As expected, the computational times required to obtain the optimal regret are more important than the computational time required to obtain the optimal worst-case makespan. But, we can observe that the CPU times demonstrate that the approach is able to solve medium-sized and high-sized instances with modest computational efforts. With respect to point (2), we address the evolution of the robustness cost of the optimal robust solutions according to the number of discrete scenarios introduced in Chapter 3. We analyse the results according to the problem size and we distinguish the three uncertainty degrees. The first observation that can be made is that the worst-case relative deviation of the optimal robust solutions minimizing the worst-case makespan X w (resp. the maximal regret X r ) also follows a logarithmic line-trend. Moreover, we can easily remark that these solutions highly reduce the robustness cost in comparison with the artificial scenario solutions.

For instance, under low uncertainty degree, in small size workshops under a low job variety (Figure 4.4 In this section, we are interested in the robust makespan on uniform parallel machines Q and identical parallel machines P with splitting. Given that Q and P are special cases of R and based on the complexity results of DmM(Rm|Split|C max ; p ij ) and DmMR (Rm|Split|C max ; p ij ), we deduce that the robust versions DmM(α|Split|C max ; p ij ) and DmMR(α|Split|C max ; p ij ) are polynomial when α ∈ {Qm, P m}. Furthermore, we will show in this section that their optimal robust solutions can be identified without solving the Chapter 5

Robust parallel machine scheduling with job preemption under uncertain processing times

Abstract: The goal of this chapter is to extend the robust formulations developed in Chapter 4 to compute the optimal robust solutions for the makespan minimization on unrelated parallel machines with job preemption under uncertain processing times. The major difference between the preemptive case and the splitting one is due to the computation of a sequence decision. We consider in this work that the decision-maker is interested in computing a robust assignment solution which is unique and accepts to have different sequences (one per scenario). Thus, we propose robust formulations of (Rm|pmtn|C max ) that allow to construct robust schedules based on robust assignment solutions. We respectively use the worst-case makespan minimization and the maximal regret minimization to compute robust assignment solutions. We can use preemptive open shop algorithm given by [START_REF] Gonzalez | Open shop scheduling to minimize finish time[END_REF] to construct each scenario sequence. In the computational results, once again, we quantify the robustness costs of the optimal robust solutions and to compare them to those of the artificial scenario solutions in the case of preemption. Compared to the nominal scenario solution X s nominal and the artificial scenario solutions X max and X average , the worst-case makespan has also been reduced under X r and it does not deviate too much from the worst-case under X w (see Table 5.4).

In the next section, we report the computational results under which we focus on the robustness cost of the optimal robust solutions in the preemptive case.

Computational results

The computational tests considered in this section are the extension of the computational results presented in Chapter 3 and Chapter 4. We base on the results provided in Chapter 3 (i.e. the robustness costs of X max and X average ) to evaluate the improvements with respect to the robust optimal solutions. We again distinguish the three degrees of uncertainty.

The first observations show that the robustness cost of the optimal robust solutions minimizing the worstcase makespan (resp. the maximal regret) also follows a logarithmic line-trend as it was the case under splitting under the three uncertainty degrees.

Under low uncertainty degree, we notice that the logarithms coefficients values are very similar to the case of splitting. For instance, in small size workshops under small job variety (Figure 5.3 graphic a. table d.), the robustness cost of X w is comprised between 2.1% and 6.1%. Its initial robustness cost is equal to 2.2% and its increase rate is equal to also 0.85%. The improvement in comparison with X max is significant as the initial robustness cost is two times less expensive. The robustness cost of X r is comprised between 2.9% and 7%. Its initial robustness cost is around 3.5% and the increase rate is around 1.1%. The improvement under X r in comparison with X max is less important, the ratio is equal to only 1.1. Besides, the effect of the number of jobs increase is also less important than in the case of splitting. As we can observe, under high job variety (Figure 5.3 graphic c. table d.), the robustness cost of X w is no longer null as it was the case under splitting but the values are still insignificant. Its initial cost is equal to 0.06% and its increase rate is equal to 0.05%. The improvement in comparison with X max is significant as the initial robustness cost is four times less expensive. In the case of X r , this claim is more notifiable as the initial robustness cost of X r is equal to 0.14% and the increase rate is equal to 0.07%. The improvement under X r in comparison with X max has become more important, the ratio is equal to 1.74 instead of 1.1.

When we increase the number of machines, the optimal solution robustness costs increase and this effect is more important than in the case of splitting. For instance, in medium size workshops under small job variety (Figure 5.4 graphic a. table d.), the robustness cost of X w is comprised between 3.6% and 10.5%.

Its initial robustness cost is equal to 3.6% and the increase rate is around 1.11%. The robustness cost of X r is comprised between 4.2% and 11.8%. Its initial robustness cost 4.2% and its increase rate is around 1.6%.

The improvement in comparison with X max notifiable especially for X w , the improvement ratio is equal to 2. In the case of X r , this ratio is equal to 1.7

When we increase the degree of uncertainty, we observe a notifiable increase in the robustness cost of the optimal solution, and the effect of uncertainty degree is very significant. For instance, under medium uncertainty degree, in small size workshops under small job variety (Figure 5.5 graphic a. table d.), the initial robustness cost is equal 8.1% and its increase rate is equal to 5.3%. Here, we can observe that the improvement ratio between X w and X max become more interesting around 2.6. The robustness cost of X r is comprised between 16.07% and 40%. Its initial robustness cost is equal to 16.07% and its increase rate is equal to 6.14%. We notice that the improvement ratio between X r and X max is around 1.3. And under high uncertainty degree, for the same problem size (Figure 5.6 graphic a. table d.), the initial robustness cost of X w is equal to 12%. The increase rate is equal to 13%. The improvement ratio has increased under X w and it is around 3.6 which means that X w is 3.6 times less expensive than X max . For X r , the initial robustness cost is equal to 15% and its increase rate is equal to 13.1%. We notice here that X r is 3 times less expensive than X max .

Globally, when the variety of jobs is important while the number of machines is small, the robust optimal solutions are very favourable and not expensive compared to the nominal solution in the deterministic case.

This observation is due to the fact that when the number of jobs is important while the number of machines is (Rm|pmtn|C max ) based on the linear formulation proposed by [START_REF] Lawler | On preemptive scheduling of unrelated parallel processors by linear programming[END_REF] in which we propose to compute robust optimal assignment solutions first. Secondly, for each scenario, we constructed schedules corresponding to these robust assignment solutions. These algorithms are interesting when the decision makers are interested in computing a unique assignment solution. In which concerns the sequence, they may tolerate to have different sequences and permutations (one per scenario). We used the same ratio technique as in Chapter4. Consequently, we obtained the following complexity results: The computational results showed that the optimal robust solution that minimizes the worst-case makespan (respectively the maximal regret) improved the results and lead to robust schedules with acceptable robustness costs under uncertainty. They follow the same trend line as in the splitting case. However, their initial robustness costs are slightly superior but the improvement ratios compared to X max and X r are still interesting. To go further, we propose in the next chapter to evaluate the stability of the robust solutions when a new scenario that is not taken into account is faced. The objective is to show that the proposed robust solutions are robust stable outside the set of discrete scenarios that is defined.

Chapter 6

Stability analysis in unrelated parallel machines under uncertain processing times Abstract: In this chapter, we develop a framework to support decision in unrelated parallel machine scheduling under uncertain processing times. The uncertainty arising from a range of plausible futures is anticipated through a set of potential scenarios as shown in the previous chapters. Alternative robust solutions are generated and ranked according to a robustness measure. But because the future could change, the stability of these robust solutions should be evaluated under new scenarios induced by variations. We define the stability of a robust solution as its ability to cover a new scenario with minor deviations in both the solution structure and the solution performance. We use classical and new stability measures to evaluate the structural stability of the robust solutions and we calculate the worst-case makespan increase to evaluate the performance stability. Our motivation is to provide a decision support to help the decision-maker to choose among the robust solutions those with the most stable structure and the most stable performance. We perform an experimental study of these different metrics and run the model that includes the alternative solutions many times to determine how these solutions perform in a range of uncertainty degree.

Robust solution stability analysis approach

The robust solution stability analysis approach is mainly based on a 2-stage algorithm (see Algorithm 4). The first stage is the Robust Solution Generation (RSG) module while the second stage (or step) is the Robust Solution Stability Evaluation (RSSE) module. We suppose that a scenario of reference always exists, we call this scenario: the nominal scenario. The algorithm starts with this nominal scenario s nominal , the set of discrete scenarios is initially reduced to a single element: Ω k ={s nominal }. We set up the deterministic problem (Rm/Split/C max ) with the nominal scenario s nominal and compute its optimal solution denoted as X 1 robust .

Algorithm 4: Robust solution stability analysis algorithm Data: s nominal the nominal scenario K: the number of iterations 1 Generate a nominal scenario; 2 Set up the deterministic problem based on the nominal scenario

Generate robust solutions for the set Ω k through RSG module;

6

Evaluate the stability of robust solutions through RSSE module; until k = K; 7 analyse the trade-off robustness stability of each robust solution;

The module RSG is designed to compute a set of robust solutions and their worst-case makespan at each iteration. For this purpose, at each iteration k, we generate a new potential scenario s k that is a variation around the nominal scenario and we add it to the set of potential scenarios:

Then, we calculate a set of robust solutions. We call X k robust the robust solution that considers the k scenarios that belong to Ω k . RSG uses all the approaches developed in the previous Chapters (3,4 and 5). It computes the set of robust solutions: X k max , X k average , X k median , X k min , X k w and X k r and it computes their corresponding worst-case makespans over Ω k .

In the same iteration k, RSSE module is designed to evaluate the stability of each robust solution when we confront a new potential scenario i.e, it measures the deviation between X k-1 robust and X k robust . For this purpose, we evaluate the stability of each robust solution according to two components: the stability of its performance and the stability of its structure.

The iterations go on until the stopping criterion is satisfied: a stability threshold fixed by the decisionmaker is reached by a robust solution or the variations of the stability measures over the iterations become negligible. Once, a robust solution is satisfying the stability objectives, Ω K could be defined as the minimal scenario set to consider in order to compute a robust stable solution: "Ω K is the best uncertainty-immunized scenario set" that can be associated to our uncertain problem.

In the last step of the algorithm, the robustness and stability measures computed over the iteration permit to compare the different robust solutions and allow the analysis of the trade-off that offers each robust solution. We will use visualization and statistical analysis of the resulting runs to help decision-makers distinguish solutions that perform well from those that perform poorly. These informations can help decisionmakers identify, evaluate, and choose robust strategies that resist over a wide range of futures and that are most stable under changes.

Robust Solution Generation

In the Robust Solution Generation module (RSG), at each iteration k, we update the set of potential scenarios Ω k and we compute over Ω k the optimal robust solutions (X k w and X k r ) and the robust solutions based on the artificial scenario approach (X k max , X k average , X k median and X k min ). Then, we measure the performance stability and structure stability of each solution.

Stability Analysis of robust solution performances

Algorithm 5: Robust Solution Generation algorithm at iteration k

robust when applied to Ω k-1 ; 3 Compute and save the robustness measures of X k-1 robust when applied to Ω k-1 ; 4 Update the set of potential scenarios by adding s k :

robust when applied to s k ; 6 Compute and save the robustness measures of X k-1 robust when applied to Ω k ; 7 Compare the robustness measures of X k-1 robust for the two successive sets ;

At each iteration k, to measure the performance stability of a robust solution X robust , we quantify the deviations of the robustness measure of each robust solution X k-1 robust when we consider a new potential scenario (see Algorithm 5). For this purpose, for each robust solution X k-1 robust , we calculate the difference between the worst-case makespan of X k-1 robust when applied to the set of scenarios Ω k-1 and its worst-case makespan when applied to the set of scenarios Ω k . We call this difference the worst-case makespan deviation at iteration k and we calculate it as:

Stability analysis of robust solution structures

When adding a new potential scenario, the instability of solutions in parallel machine results primarily in machine assignment. At each iteration k, to measure the structure stability of a robust assignment solution X robust , we compare X k robust and X k-1 robust by computing:

• the number of perturbed jobs P J k j (X robust ) (see Algorithm 7);

• the number of perturbed machines P M k i (X robust ) (see Algorithm 8);

• the number of changing ratios CR k (X robust ) (see Algorithm 6):

• the number of new assignments N A k (X robust ) (see Algorithm 9);

• the number of cancelled assignments CA k (X robust ) (see Algorithm 10);

• the magnitude of ratio changes M C k (X robust ) (see Algorithm 11).

Algorithm 6: The number of changing ratios computation at iteration k Data: M = {1, . . . , m} the set of m machines, N = {1, . . . , n} the set of n jobs

CR k (X robust ) measures the number of ratios that have increased or decreased when we consider a new potential scenario. This stability measure gives a macroscopic idea about the structural similarities between the robust solution X k robust that considers a new potential scenario and the robust solution X k-1 robust that does not:

Algorithm 7: The number of perturbed jobs computation at iteration k Data: M = {1, . . . , m} the set of m machines, N = {1, . . . , n} the set of n jobs

Algorithm 8: The number of perturbed machines computation at iteration k Data: M = {1, . . . , m} the set of m machines, N = {1, . . . , n} the set of n jobs

Nevertheless, CR k (X robust ) does not quantify how many jobs and how many machines are involved in this ratio change. Therefore, we measure the number of disrupted jobs P J k and the number of disrupted machines P M k . P J k = j∈N P J k j where

To measure extreme ratio changes, we introduce N A k (X robust ) and CA k (X robust ). N A k (X robust ) measures the number of ratios that were null in X k-1 robust and takes a positive value in X k robust when we consider a new potential scenario. It reflects the number of additional setups or changeovers in machines when we take into account a new potential scenario. Similarly, CA k (X robust ) measures the number of ratios that were positive in X k-1 robust and then become null in X k robust . It may report a machine setup that is no longer necessary when we consider a new potential scenario, and may be behind this cancellation, another machine has to take the job in order to make up the difference. N A k (X robust ) and CA k (X robust ) are computed such Algorithm 10: The number of cancelled assignments computation at iteration k Data: M = {1, . . . , m} the set of m machines, N = {1, . . . , n} the set of n jobs

They are critical if a machine setup or tooling are prepared in advance, and jobs wait in a sequence queue based on the previous solution. They indicate a sequence deviation that will incur costs in handling and reallocating the jobs, and re-planning the tools changeover.

In relation with the CR k (X robust ), M C k (X robust ) measures the magnitude of ratio changes. -a new assignment (N A 7 = 1).

-a cancelled assignments (CA 7 = 1).

-11 changed ratios (CR 7 = 11).

-4 perturbed jobs (P J 7 = 4), -3 perturbed machines(P M 7 = 3), -60% is the total magnitude of assignment ratio change (M C 7 = 0.6).

In the next section, we represent the computational results concerning the stability analysis of the robust solutions.

Computational results in the case of splitting: Statistical analysis

We consider the same data generator used along this thesis.

We fixed the number of iterations at K=100. At each iteration we compute the robust approximate solutions (X max , X min , X average and X median ) and the robust optimal solutions (X w and X r ) in the splitting case. Then we evalute the stability of each solution according to all the stability indicators over the 100 iterations.

For each indicator, we represent the computational results through box-plots to represent the mean values and the distribution of the values around the mean value.

and X r 's WCMD mean values are respectively equal to 0.02% and 0.05% with standard deviations that are respectively equal to 0.05% and 0.08%.

When we increase the degree of uncertainty, we observe that the W CM D of the solutions increase but their values are small.

Under medium uncertainty degree, in small size workshops under low job variety (Figure 6.2 graphic a.), the increase is more important for X w and X r than for the other solutions. But the W CM D is still very low for all the solutions. For X max , X min , X average and X median , The W CM D mean values are around 0.07% with standard deviations that are around 0.2%. And the W CM D of X w and X r mean values are respectively equal to 0.35% and 0.38% with a standard deviation that is equal to 0.4%.

Under high degree of uncertainty, we observe that the WCMD mean value of X min , X w and X r become more significant relatively to the previous cases. For instance, in the case of small size workshops under medium job variety (Figure 6.2 graphic a.), for X min , the WCMD mean value is equal to 1.2% with a standard deviation that is equal to 2.3%. X w and X r WCMD mean values are respectively equal to 1.9% and 2.6% with standard deviations that are respectively equal to 2.3% and 2.5%. In the next sections, we report the results concerning the structure stability of the solutions.

Structure stability evaluation

In this section, we evaluate the structure stability of the solutions according to different structure stability indicators.

a-The number of perturbed jobs: According to the P Js, under low uncertainty degree, X max and X min are the most stable.

In small size workshops under small job variety (Figure 6.3 graphic a.), the P Js are low for all the solutions except for X average and X median . X max and X min are the most stable, followed by X w , X r . P J mean values of for X max and X min are respectively equal to 1.65% and 1.60% with standard deviations that are respectively equal to 3.63% and 3.98%. For X w , P J mean value is equal to 5.22% with a standard deviation that is equal to 7.06% and for X r , the mean value of P J is equal to 6.66% with a standard deviation that is equal to 8.75%. P J become significant under X median , P J mean value is equal to 9.97% with a standard deviation that is equal to 4.64%. For X average , P J mean value increases highly, it is equal to 18.08% with a small standard deviation that is equal to 0.4%.

When we increase the number of jobs, we remark that the P Js decrease. X max and X min are the most stable, followed by X average and X median instead of X w and X r . Under medium job variety (Figure 6.3 graphic b.), P J mean values of X max and X min are respectively equal to 1.12% and 1.01% with a standard deviation that are respectively equal to 1.75% and 1.83%. For X average and X median , P J mean values are around 4.2% with standard deviations that are respectively equal to 0.46% and 1.05%. X w 's P J mean value is equal to 5.4% with a standard deviation that is equal to 4.41%. And P J mean value under X r is more significant, it is equal to 8.8% with a standard deviation that is equal to 6.10%.

When we increase the number of machines, we remark that the P Js highly increase (both the mean values and the standard deviations). For instance, under medium workshop size with low job variety (Figure 6.3 graphic a.). For X min and X max which are the most stable, P J mean value of X min is equal to 4.33% with a standard deviation that is equal to 9.88% and P J mean value of X max is equal to 5.12% with a standard deviation that is equal to 11.05%. For X w , P J mean value is equal to 20.79% with a standard deviation that is equal to 18.86%. For X r , P J mean value is equal to 29.1% with a standard deviation that is equal to 21.32%. For X median , P J mean value is equal to 31.08% with a standard deviation that is equal to 13.22%. And for X a verage which is the less stable, P J mean value is very high, it is equal to 50.62%

with a standard deviation that is equal to 2.38%. When we increase the degree of uncertainty, the P Js increase also. The increase in the P Js is more important when the number of machines increase. For instance, under medium uncertainty degree, in medium workshop size and low job variety (Figure 6.4 graphic c.), only X max and X min are relatively stable as their P J mean values are less than 11% while all the other solutions are unstable as their mean values of perturbed jobs are superior to 50%. The P J mean value of X max is equal to 11.08% with a standard deviation that is equal to 14.71%. For X min , the P J mean value is equal to 10.22% with a standard deviation that is equal to 15.06%. For X w , theP J mean value is equal to 44.90% with a standard deviation that is equal to 25.39%. For X r , the P J mean value is equal to 61% with a standard deviation that is equal to 26.60%. For X median , the mean value of perturbed jobs is equal to 53.5% with a standard deviation that is equal to 20.60%. And For X average , the P J mean value is equal to 54.66% with a standard deviation that is equal to 2.95%.

Under high uncertainty degree, we observe that the P Js have the same properties and the same magnitude as in the case of medium uncertainty (see for instance Figure 6.4).

b-The number of perturbed machines:

In which concerns the number of perturbed machines (P M ), the computational results show the following properties: Under low uncertainty degree, X min and X max are the most stable regarding the P M s, followed by X w and X r . The other solutions are not stable. In small size workshops under small job variety (Figure 6.5 graphic a.), The P M mean values under X min and X max do not exceed 10% but their standard deviations are important. X w and X r 's P M mean values are around 13% with relatively important standard deviation. And X median and X average are not stable. The P M mean value of X max is equal to 9.47% with a standard deviation that is equal to 20.69%. For X min , the P M mean value is equal to 8.81% with a standard deviation that is equal to 19%. X w and X r lead to similar results. For X w , the P M mean value is equal to 13.5% with a standard deviation that is equal to 19.67%. For X r , the P M mean value is equal to 15.76% with a standard deviation that is equal to 17.96%. For X median , the P M mean value is equal to 55% with a standard deviation that is equal to 26%. X average is not stable, the P M mean value under X average is equal to 100%. According to the distributions, the P M upper values can reach 100% for all the solutions except for X w and X r for which they are respectively equal to 80% and 90% while the lower value is equal to 0%.

When we increase the number of jobs, we remark that the P M s increase. For instance, under medium job variety (Figure 6.5 graphic b.), the ranking of the solutions regarding the P M s is the same but both the mean values, the standard deviations and the upper values are more important. The P M mean value of X max is equal to 23.15% with a standard deviation that is equal to 33.58%. For X min , the P M mean value is equal to 21.25% with a standard deviation that is equal to 31.40%. For X w , the P M mean value is equal to 28.33% with a standard deviation that is equal to 17.9%. The P M mean value is more important under X r and it is equal to 41.42% with a standard deviation that is equal to 26.6%. X average , X median are not stable, the P M are around 100%. All the P M upper values are reaching the 100%.

When we increase the number of machines, we remark that the P M s slightly increase for the solutions X w , X r . But they slightly decrease for X min and X max . For instance, under medium workshop size and low job variety (Figure 6.5 graphic c.). The P M mean value of X max is equal to 9.68% with a standard deviation that is equal to 20.49%. Similar values are obtained under X min . For X w and X r , the mean values of perturbed machines are respectively equal to 29% and 39% with a standard deviation that is around 25%.

For X median , the P M mean value is equal to 58.2% with a standard deviation that is equal to 22%. And the P M upper values are all superior to 90%.

When we increase the degree of uncertainty, the P M s highly increase for all the solutions. Under medium uncertainty degree, in small size workshops under low job variety (Figure 6.6 graphic a.), X min , X max , X w and X r are quite stable while X median and X average are unstable according to the P M s. The P M mean value of X min is equal to 16% with a standard deviation that is equal to 22%. X max , X w and X r lead to similar results. Their P M mean values are around 21% with standard deviation that are around 20%.

For X median and X average , the P M mean value are more than 92%. When we increase the number of jobs or machines, almost all the solutions are unstable regarding the P M s (e.g. Figure 6.6 graphics b. and c.).

Under high degree of uncertainty, the results are similar to the case of medium uncertainty. The increase is relatively small (Figure 6.6). c-The changing ratios In which concerns the number of changed ratios CRs, under low uncertainty degree, the CRs are very low. Furthermore, X max and X min are the most stable. For example, in small size workshops under small job variety (Figure 6.7 graphic a.), the CRs are low for all the solutions except for X average . X max and X min are the most stable, followed by X w , X r and X median . The CR mean values of X max and X min Chapter 6. Stability analysis in unrelated parallel machines under uncertain processing times (m=3,n=10,d=3) are respectively equal to 1.14% and 1.17% with standard deviations that are respectively equal to 2.54% and 2.78%. For X w , the CR mean value is equal to 3.61% with a standard deviation that is equal to 4.85%. For X r , the CR mean value is equal to 4.54% with a standard deviation that is equal to 5.96%. The CR mean value increases under X average and it is equal to 12.72% but, it standard deviation is equal to only 0.26%.

When we increase the number of jobs, we remark that the CRs decrease. X max and X min are the most stable, followed by X average , X median instead of X w and X r . And when we increase the number of machines, the increase of the CRs is not significant (see Figure 6.7 graphic c.).

When we increase the degree of uncertainty, the CRs increase. However, under medium uncertainty degree, the increase is very small. In small size workshops under small job variety (Figure 6.8 graphic a.),

the CR mean values are low for X max and X min (less than 3%). But, the CRs become significant under X w , X r , X median and X average . For X w and X r , the CR mean values are equal to 10% with a standard deviation that is equal to 8%. And for X median and X average , the CR mean values are around to 13% with standard deviations that are around 1.5%. Under high uncertainty degree, the results are very similar to the case of medium uncertainty degree (see Figure 6.8). d-The number of new assignments and cancelled assignments Under low uncertainty degree, the number of new assignments (N A) is very small under all the solutions (less than 1%). For instance, in small size workshops under small job variety (Figure 6.9 graphic a.), for X max , X min , X median and X average , the N A mean values are less than 0.05% and their standard deviations are less than 0.5%. For X w and X r , the N A mean values are around 0.5% and their standard deviations are around 0.5%.

When we increase the number of jobs, the N As slightly increase. Under medium job variety (Figure 6.9 graphic b.), for X max , X min , X median and X average , the N A mean values are less than 1% and their standard deviations are less than 0.5%. For X w and X r , the N A mean values are around 0.6% and their standard deviations are around 1%. And when we increase the number of machines, the N As are of the same order of magnitude, the changes are not notifiable. Under medium workshop size (?? graphic a.), X max , X min , X median and X average , the mean value of new assignment are less than 0.1% and their standard deviations are less than 0.5%. For X w and X r , the mean values of new assignment are around 0.4% and their standard deviations are around 1%.

When we increase the degree of uncertainty, we observe a small increase of the N As but the values are very small, the mean values are less than 2% (see e.g. Figure 6.10 ). Under low uncertainty degree, all the solutions are stable according to the M Cs. In small size workshops under small job variety (Figure 6.11 graphic a.), for X max , X min , X average and X median , the M C mean values are almost null. For X w and X r , the M C mean values are around 1% with a standard deviation that is equal to 1.5%.

When we increase the number of jobs, we remark that the M C increase is insignificant (e.g. ). But, when we increase the number of machines, we observe that the M Cs increase for X average , X median , X w and X r is relatively significant but the values are small. For example, in medium size workshops under small job variety (Figure 6.11 graphic c.). For X max and X min , the M C mean values and standard deviations are respectively equal to 0.5% and 0.3%. For X w and X r , the M C mean value is equal to 1.5% with standard deviations that are equal to 2%. And for X average and X median , the average value of ratio magnitude change is equal to 3% with standard deviations that are equal to 2%.

When we increase the degree of uncertainty, the results are very similar to the case of low uncertainty degree (e.g. Figure 6.12).

a. (m=3,n=10,d=2)

The magnitude of ratio changes 0 0,2 0,4

Powered by TCPDF (www.tcpdf.org) Powered by TCPDF (www.tcpdf.org)

b. (m=3,n=50,d=2)

The magnitude of ratio changes 0 0,2 0,4 0,6 0,8 1 X-max X-average X-median X-min X-w X-r X-l

Powered by TCPDF (www.tcpdf.org) Powered by TCPDF (www.tcpdf.org) c. (m=7,n=10,d=2)

The magnitude of ratio changes 0 0,2 0,4 0,6 0,8 1 X-max X-average X-median X-min X-w X-r X-l

Powered by TCPDF (www.tcpdf.org) Powered by TCPDF (www.tcpdf.org) d. (m=3,n=10,d=3)

Results synthesis and analysis

The results show that according to the performance stability indicator, we can conclude that under low uncertainty degree, all the solutions can be considered as stable: the worst-case makespan deviations are insignificant. Indeed, the scenarios have similar structure and consequently the worst case scenario is very similar to the considered scenarios.

Under medium uncertainty degree, X max , X min , X average and X median are the most stable. X w can be considered as moderately stable while X r can become unstable especially when we increase the number of jobs. And under high uncertainty degree, X max , X average and X median are the most stable. X min is quite stable. X w and X r are the less stable. These observations can be explained by the fact that the worstcase makespans under X w and X r are optimized considering the constraints of the scenario set, they take smaller values compared to the other solution makespans. In contrary, the worst-case makespans of the other solutions are already high and consequently, the deviations are less important.

According to the structure stability, we can conclude that:

-Under small uncertainty, X max , X min can be considered as the most stable as their number of perturbed jobs, of perturbed machines, of changed ratios and their magnitude of ratio changes are very small. X r and -------------------------------------

The potential scenarios scheduled according to s max in the splitting case .

The potential scenarios scheduled according to s average in the splitting case

Scheduling example in the preemptive case

The potential scenarios scheduled according to s average in the preemptive case --------------------------------------

Appendix E

Logarithmic trend line functions

-------------------------------------- [START_REF] Smithson | Ignorance and disasters[END_REF] Probability vs Ambiguity vs Vagueness [START_REF] Bellman | Decision-making in a fuzzy environment[END_REF] Decision in fuzzy environment [START_REF] Davidson | Why acquisitions may not be the best route to innovation[END_REF]