Keywords: scheduling, mathematical programming, heuristics, polyhedral study, Branchand-cut xiv

son has been extended to an existing greedy search method, and to an exact formulation based on basic integer linear programming. The proposed genetic algorithms show a good performance dominating the evaluated methods in terms of problems' sizes and time complexity for large benchmark sets of instances. We also extended three existing mathematical formulations to derive an exact solution for this problem. These mathematical formulations were validated and compared to each other by extensive computational experiments. Moreover, we proposed an integer linear programming formulations for solving unrelated parallel machine scheduling with precedence/disjunctive constraints, this model based on the intervaland m-clique free graphs with an exponential number of constraints. We developed a Branch-and-Cut algorithm, where the separation problems are based on graph algorithms. We also worked to hybridize the meta-heuristic with the mathematical program and improved our mathematical program by adding dierent classes and families of valid inequalities to strengthen the model. We also studied the polytope associated with our mathematical formulation. We discussed the separation algorithms associated with the valid inequalities and used them within branch-and-cut algorithm to solve the problem. Finally, we proposed a novel model for solving a generalized open shop task scheduling problem, and then, we adapted the model to solve the task scheduling problem in an open shop environment. We also identied some classes of valid inequalities to improve these models.

First and foremost, sincere gratitude is due to my Supervisors. Firstly, I would like to thank my Supervisor in université de Lorraine Prof. Imed KACEM, your encouragement, guidance and intellectual support from the initial to the nal level of my PhD degree enabled me to expand my knowledge by guiding me to develop new methods, and to practice a lot of research skills, and to know new research directions. Your constant pursuit for perfection, and valuable suggestions have guided me at every step of my research. It was a great pleasure and honor to work with you. Particularly, I value your respect towards professionalism and the desire to excel higher and higher. I owe you lots of gratitude for having shown me how to be an ideal researcher, a good reviewer and a hard worker.

I'm profoundly indebted to my Co-Supervisor Dr. Sebastién MARTIN who was very generous with his time and knowledge and assisted me in each step to complete this thesis. I deeply appreciate your work attitude and your work eciency. It was a great pleasure and honor to work with you too. Your perpetual energy and enthusiasm in research extremely motivated me in my studies. I shall be missing our regular meetings at 7 :30 AM.

It gives me great pleasure to acknowledge my Supervisor at University of Gezira Prof. Izzeldin M.OSMAN, his advises, constant support, availability and bright inputs helped me a lot to accomplish this work. He was always accessible and willing to help every young scientist with their research every where, and every time.

I have been extremely lucky to have a supervisors like you all, you granted me much of your time and you cared so much about my work, and responded to my queries and questions so promptly. This thesis would not have been possible without your extraordinary support. I learned a lot from you, but in fact this clearly shows that there is still a lot to learn from you.

I also must thank again Prof. Imed KACEM he accepted me as a Ph.D fellow and giving me an opportunity to pursue a doctorate degree in LCOMS. As well as funding all costs of all international conferences, publications, and the traveling costs.

I also thank the thesis reporters and all jury members for the thorough and critical judgment and evaluation of this thesis.

I would also like to thank all members, and Phd colleagues at LCOMS. I acknowledge the University of Gezira for providing me with this scholarship to pursue my doctorate studies especially Prof. Mohammed WARRAQ OMER, Prof. Abdelelah M. ALHASSAN and Prof. Osman ELAMIN. I greatly appreciate all kinds of help received from the sta members of the French embassy in Khartoum, espicially Pierre MULLER, i Jean-Noel BALEO, Geneviève ICHARD, Abusuan ALI and Salma YAGI.

I also extend my gratitude to the sta members and friends from the IUT-Metz for their help and support, especially Pierre, Frank, Zsuszana, Natali, Crystle and Nicolas, Je vais manquer le dîner annuel de Noël avec vous.

I deeply thank my wife Ebtihal MUSTAFA, who accepted my long hours at research, and endured with open heart and mind and encouraged me at every step of my career and life.

A special thanks goes to my brother Alfrazdaq and his family for living every moment of this work with me, and for his warmest welcoming in Cork, and Dublin during holidays.

Finally and forever, I acknowledge moral and emotional support I received from my mother, father, brothers during this challenging period and my life in general.

However, I'm the only person responsible for errors in this thesis.

Dedication

To my parents for their love, prays, and support. You put me through the best education possible. I appreciate your sacrices and I wouldn't have been able to get to this stage without you.

To my wife Ebtihal and my sons Mohammed, Alaa, you have persevered and endured a lot during this period.

To my brothers and my sister for unending love and support.

iii

Résumé

Cette thèse porte sur la résolution exacte et heuristique de plusieurs problèmes ayant des applications dans le domaine de l'Informatique dématérialisé (cloud computing). L'Informatique dématérialisée est un domaine en plein extension qui consiste à mutualiser les machines/serveurs en dénissant des machines virtuelles représentant des fractions des machines/serveurs. Il est nécessaire d'apporter des solutions algorithmiques performantes en termes de temps de calcul et de qualité des solutions. Dans cette thèse, nous nous sommes intéressés dans un premier temps au problème d'ordonnancement sur plusieurs machines (les machines virtuelles) avec contraintes de précédence, c-à-d., que certaines tâches ne peuvent s'exécuter que si d'autres sont déjà nies. Ces contraintes représentent une subdivision des tâches en sous tâchespouvant s'exécuter sur plusieurs machines virtuelles. Nous avons proposé plusieurs algorithmes génétiques permettant de trouver rapidement une bonne solution réalisable. Nous les avons comparés avec les meilleurs algorithmes génétiques de la littérature et avons déni les types d'instances où les solutions trouvées sont meilleures avec notre algorithme. Dans un deuxième temps, nous avons modélisé ce problème à l'aide de la programmation linéaire en nombres entiers permettant de résoudre à l'optimum les plus petites instances. Nous avons proposé de nouvelles inégalités valides permettant d'améliorer les performances de notre modèle. Nous avons aussi comparé cette modélisation avec plusieurs formulations trouvées dans la littérature. Dans un troisième temps, nous avons analysé de manière approfondie la sous-structure du sous-graphe d'intervalle ne possédant pas de clique de taille donnée. Nous avons étudié le polytope associé à cette sous-structure et nous avons montré que les facettes que nous avons trouvées sont valides pour le problème d'ordonnancement sur plusieurs machines avec contraintes de précédence mais elles le sont aussi pour tout problème d'ordonnancement sur plusieurs machines. Nous avons étendu la modélisation permettant de résoudre le précédent problème an de résoudre le problème d'ordonnancement sur plusieurs machines avec des contraintes disjonctives entre les tâches, c-à-d., que certaines tâches ne peuvent s'exécuter en même temps que d'autres. Ces contraintes représentent le partage de ressources critiques ne pouvant pas être utilisées par plusieurs tâches. Nous avons proposé des algorithmes de séparation an d'insérer de manière dynamique nos facettes dans la résolution du problème puis avons développé un algorithme de type Branch-and-Cut.

Nous avons analysé les résultats obtenus an de déterminer les inégalités les plus intéressantes an de résoudre ce problème.Enn dans le dernier chapitre, nous nous sommes intéressés au problème d'ordonnancement d'atelier généralisé ainsi que la version plus classique d'ordonnancement d'atelier (open shop). En eet, le problème d'ordonnancement d'atelier généralisé est aussi un cas particulier du problème d'ordonnancement sur plusieurs machines avec des contraintes disjonctives entre les tâches. Nous avons proposé une formulation à l'aide de la programmation mathématique pour résoudre ces deux problèmes et nous avons proposé plusieurs familles d'inégalités valides permettant d'améliorer les performances de notre algorithme. Nous avons aussi pu utiliser les contraintes dénies précédemment an d'améliorer les performances pour le problème d'ordonnancement d'atelier généralisé. Nous avons ni par tester notre modèle amélioré sur les instances classiques de la littérature pour le problème d'ordonnancement d'atelier. Nous obtenons de bons résultats permettant d'être plus rapide sur certaines instances.

Résumé du chapitre 1 :

Dans ce chapitre, nous avons proposé un état de l'art portant dans un premier temps sur les problématiques de recherche opérationnelle que l'on peut trouver dans l'Informatique dématérialisée. Ensuite, nous avons rappelé quelques problématiques d'ordonnancement s'insérant dans le cadre de l'Informatique dématérialisée. Après cet état de l'art thématique, nous nous sommes intéressés aux méthodes permettant de résoudre ces problèmes. En introduction aux méthodologies, nous avons décrit ce qu'est un problème d'optimisation combinatoire, la modélisation par les graphes et expliqué la diculté de résolution de certains problèmes en dénissant la complexité. Ensuite, nous avons commencé par décrire les heuristiques et méta-heuristiques que sont les algorithmes gloutons, les méthodes de recherches locales et les algorithmes génétiques. Puis, nous avons rappelé les concepts de la programmation en nombres entiers. Ces concepts regroupent, la modélisation, l'approche polyédrale, les algorithmes de type Branch-and-Bound et ceux de type Branch-and-Cut.

Résumé du chapitre 2 :

Dans le chapitre 2 nous décrivons le problème d'ordonnancement sur plusieurs machines avec contraintes de précédence et nous donnons une formulation à l'aide de la programmation mathématique an de comparer les heuristiques sur de petites instances. Nous discutons ensuite des algorithmes heuristiques et méta-heuristiques proposés dans la littérature et permettant de résoudre ce problème. Nous proposons un nouvel algorithme génétique basé sur l'aectation des jobs aux machines. Nous développons plusieurs vax riantes basées sur cette idée, puis nous combinons plusieurs algorithmes génétiques différents an d'améliorer la meilleure solution trouvée sur les instances de grandes tailles. Nous nissons par comparer les diérents algorithmes sur un ensemble d'instances générées aléatoirement. Nous montrons que notre algorithme génétique obtient de bien meilleures performances sur de nombreuses instances.

Résumé du chapitre 3 :

Dans ce chapitre, nous décrivons plusieurs formulations mathématiques données dans la littérature. Nous proposons une nouvelle modélisation basée sur les graphes d'intervalles. Cette formulation possède un nombre exponentiel de contraintes. Nous proposons des séparations polynomiales pour ces inégalités nous permettant de résoudre ecacement les instances testées. Cette modélisation obtient de très bons résultats et outrepasse en termes de performance toutes les modélisations proposées dans la littérature à l'exception de la formulation basée sur les ordres linéaires. Nous avons proposé de nombreuses inégalités valides pour notre modèle basé sur les graphes d'intervalles nous permettant d'obtenir de meilleurs résultats et des résultats compétitifs sur de nombreuses instances en comparaison avec la formulation basée sur les ordres linéaires.

Résumé du chapitre 4 :

Dans le chapitre 4, nous avons analysé le problème du sous-graphe d'intervalle sans clique de taille supérieure à m. Ce sous-problème se retrouve dans de nombreux problèmes d'ordonnancement. Nous avons proposé des inégalités permettant de supprimer les sous-graphes interdits dénis dans la littérature. Pour chacune de ces inégalités nous analysons leur aspect facial. Ces contraintes sont en nombres exponentiels et nous proposons plusieurs séparations, exactes et heuristiques pour chacune d'entre elle. Nous nissons par comparer les performances de chaque contrainte sur le problème d'ordonnancement sur plusieurs machines avec contraintes disjonctives. Cette comparaison nous permet de dénir les contraintes les plus intéressantes et la force des séparations proposées.

Résumé du chapitre 5 :

Dans ce chapitre, nous étudions deux problématiques qui sont des cas particuliers du problème d'ordonnancement sur plusieurs machines avec contraintes disjonctives. Le premier problème consiste à dénir le meilleur ordre des tâches sur plusieurs machines tout en respectant les contraintes disjonctives. Nous proposons une formulation par la programmation linéaire en nombres entiers pour résoudre ce problème ainsi que des contraintes spéciques. Nous avons testé ce modèle en ajoutant les contraintes basées sur le sousgraphe d'intervalle sans clique de taille m et nous comparons les résultats sur des ins-tances aléatoires. Le second problème est celui de l'ordonnancement d'atelier (open shop) largement étudié dans la littérature. Nous étendons le modèle précédent ainsi que les contraintes proposées précédemment. Ce modèle se base sur l'ordre linéaire des tâches sur une machine et appartenant à la même tâche. Nous testons la performance de notre modèle sur les instances utilisées dans la littérature.

Mots-clés: Ordonancement, programmation mathématique, heuristiques, Approche polyèdrale, Branch-and-cut.

Abstract

The Cloud Computing appears as a strong concept to share costs and resources related to the use of end-users. As a consequence, several related models exist and are widely used (IaaS, PaaS, SaaS. . . ). In this context, our research focused on the design of new methodologies and algorithms to optimize performances using the scheduling and combinatorial theories. We were interested in the performance optimization of a Cloud Computing environment where the resources are heterogeneous (operators, machines, processors...) but limited. Several scheduling problems have been addressed in this thesis. Our objective was to build advanced algorithms by taking into account all these additional specicities of such an environment and by ensuring the performance of solutions. Generally, the scheduling function consists in organizing activities in a specic system imposing some rules to respect. The scheduling problems are essential in the management of projects, but also for a wide set of real systems (telecommunication, computer science, transportation, production...). More generally, solving a scheduling problem can be reduced to the organization and the synchronization of a set of activities (jobs or tasks) by exploiting the available capacities (resources). This execution has to respect dierent technical rules (constraints) and to provide the maximum of eectiveness (according to a set of criteria). Most of these problems belong to the NP-Hard problems class for which the majority of computer scientists do not expect the existence of a polynomial exact algorithm unless P=NP. Thus, the study of these problems is particularly interesting at the scientic level in addition to their high practical relevance. In particular, we aimed to build new ecient combinatorial methods for solving parallel-machine scheduling problems where resources have dierent speeds and tasks are linked by precedence constraints.

In our work we studied two methodological approaches to solve the problem under the consideration : exact and meta-heuristic methods.We studied three scheduling problems, where the problem of task scheduling in cloud environment can be generalized as unrelated parallel machines, and open shop scheduling problem with dierent constraints. For solving the problem of unrelated parallel machines with precedence constraints, we proposed a novel genetic-based task scheduling algorithms in order to minimize maximum completion time (makespan). These algorithms combined the genetic algorithm approach with dierent techniques and batching rules such as list scheduling (LS) and earliest completion time (ECT ). We reviewed, evaluated and compared the proposed algorithms against one of the well-known genetic algorithms available in the literature, which has been proposed for the task scheduling problem on heterogeneous computing systems. Moreover, this compari-

General Introduction

Cloud computing is a natural development of the previous models of distributed and grid computing, beyond the technical innovations related to the idea of virtualization. Cloud providers provide the computing as a services, it is called infrastructure as a service (IaaS). Amazon Elastic Compute Cloud [START_REF]Amazon Web Services (AWS) -Cloud Computing Services[END_REF] is an example of IaaS. In cloud the providers deliver physical resources as virtual machines with dierent capacities to remote users as a service on pay-as-you-go basis. Remote users send their data (applications, programs, etc) to the cloud, the scheduler needs to place these data to its proper virtual machines. In scheduling theory, this problem belongs to the class of parallel machines and open shop. When the capacity of machines is dierent, then it becomes more precisely an unrelated parallel machines and a generalized case of open shop. In cloud computing most applications can be represented in a form of a directed cyclic graph (DAG). Therefore, precedence constraints and disjunctive constraints are found. Cloud management is responsible for resources allocation. When users send their applications (set of jobs with dependencies) to the cloud the scheduler aims to assign each dependent job to its virtual machines efciently. The allocation of jobs to virtual machines is a complicated process in the cloud computing environment. Optimizing the maximum completion time normally aects the performance of the whole system. The main advantage of job scheduling algorithms in cloud environment is to achieve an excellent system throughput and high performance computing.

Scheduling is the allocation of resources over time to perform a collection of tasks, in which one or several objectives have to be optimized. From this general denition of the term, we could deduce that, scheduling is an important decision making function. We can say also, scheduling is a theory when it has a collection of principles, models and techniques. Scheduling plays a crucial role in manufacturing, as well as in services industries [START_REF] Pinedo | Planning and scheduling in manufacturing and services[END_REF]. Eective scheduling becomes a necessity for survival in marketplace. For example, services companies have to schedule activities in such a way as to use the available resources in an ecient manner. Referring to Conway et al [4], scheduling is classied according to four types of information : the operations to be processed, the number and types of machines, the constraints that restrict the assignment of jobs and the criteria by which the schedule can be evaluated. In the real life, there are tremendous number of scheduling applications in manufacturing [START_REF] Wang | Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics[END_REF], production systems [START_REF] Hsu | Unrelated parallelmachine scheduling with rate-modifying activities to minimize the total completion time[END_REF] and in services industries [START_REF] Hart | Evolutionary scheduling : A review[END_REF], as well as in most information processing environment [START_REF] Dogan | Genetic algorithm based scheduling of meta-tasks with stochastic execution times in heterogeneous computing systemst1[END_REF]5]. The journey of scheduling theory starts by Henry Gantt and other pioneers. Dierent directions were pursued in academia and industry with an increasing amount of attention paid to scheduling problems. As a consequence, dierent approaches have been developed to solve the scheduling problems [START_REF] Unlu | Evaluation of mixed integer programming formulations for non-preemptive parallel machine scheduling problems[END_REF][START_REF] Van Den Akker | A polyhedral approach to single-machine scheduling problems[END_REF][START_REF] Kacem | Approximation algorithm for the weighted ow-time minimization on a single machine with a xed non-availability interval[END_REF][START_REF] Hardin | Strong valid inequalities for the resource-constrained scheduling problem with uniform resource requirements[END_REF]. These approaches, generally based on the optimization techniques including heuristics, meta-heuristics (approximate methods) and exact techniques, aim to design eective algorithms for attacking the considered scheduling problems.

Most of scheduling problems belong to the NP-Hard problems class for which the majority of computer scientists do not expect the existence of a polynomial exact algorithm. Thus, the study of these problems is particularly interesting at the scientic level in addition to their high industrial relevance.

Motivated by the optimization of the performances in cloud computing environment. The scheduling problem in cloud is generalized as an unrelated parallel machine and open shop scheduling problems according to the cloud environment. In this thesis, we proposed dierent optimization methods (approximate, and exact ) to handle such scheduling problems. Our contribution is as follows : -Several genetic algorithms have been proposed based on local search, list scheduling and some batching rules.

-Several mathematical formulations are developed to solve the parallel-machine and open shop scheduling problems.

-The proposed interval subgraph mathematical model have been investigated with the associated polytope and some facets are dened for this polytope.

-Several classes of valid inequalities have been derived.

-Several separation procedures are proposed to strengthen the model. Many experimental computations have been applied for some generated benchmarks as well as for some known benchmarks.

Outlines of the thesis

This thesis consists of ve chapters where each one could be a self-contained chapter based on the problem under the consideration and the combinatorial optimization methods used. The reader can access the chapter with the corresponding method of his interest directly. The manuscript is organized as follows :

Chapter 1 presents the preliminary and preparatory denitions and notations as a conceptual framework. This chapter includes also some state of the art on cloud computing, scheduling problem and some denitions about complexity theory, polyhedral and graph theory.

Chapter 2 focus on the approximate solutions of combinatorial problems. Greedy and genetic algorithms for solving the task scheduling problems in cloud computing are proposed in this chapter. Here, the problem is formulated as an unrelated parallel-machine with precedences and disjunctive constraints. Moreover, some related work on this area of research are presented and our results are compared with the existing works.

Chapter 3 presents the mathematical formulation of the studied problem. Our novel mathematical model, which is based on interval and m-clique free subgraphs for solving the unrelated parallel machines scheduling problem with precedence constraints is proposed. We also compared the proposed model against dierent other mathematical formulations found in the literature. At the end of this chapter computational experiments are presented and analysed.

Chapter 4 investigates our mathematical model and studies its associated polytope. We explore the subproblem of nding an interval graph and m-clique free subgraphs. Moreover, we present some facet denitions and we also describe the exact and heuristic separation algorithms to separate some forbidden subgraphs and we propose a branchand-cut algorithm based on families of strong valid inequalities presented in this chapter.

Chapter 5 discusses two problems. The rst one is the Generalized Open Shop problem and the second is the Open Shop scheduling problem. The structure of our model helps on solving such problems. By applying the idea of interval graph to propose other mathematical formulations for solving the considered problems, some classes of valid inequalities are presented. Some separation algorithms are proposed as well.

Most of the results of these chapters have been published in journals, and international conferences listed below : Two articles in international journals : M-A.

Cloud Computing

Cloud computing is a type of distributed and parallel system, which consists of physical and virtual resources. The physical resources in cloud shared virtually across a limited number of virtual machines to the end users according to their demand [START_REF] Vinothina | A Survey on Resource Allocation Strategies in Cloud Computing[END_REF]. These virtual machines are dynamically presented as computing resources to the end user based on what is called a service level agreements (SLA), which is a determined contract between end-user and service provider that denes the computing service expected from the service provider. When the computing resources are allocated to the users, they access the services such as applications and stored data from anywhere at any time. The request for virtualized resources is described through a list of parameters describing the processing, the memory and the disk needs. The hardware and software resources are allocated to the cloud applications on-demand basis. Execution of a task has a cost and this may vary depending on the resources allocated. Therefore, when the maximum completion time is minimized, that means the performance of the whole system will be improved. Cloud computing services are oered based on three-tier architecture. The challenge is that, for the cloud service providers it is dicult to allocate the virtual machines dynamically and eciently [START_REF] Vignesh | Resource Management and Scheduling in Cloud Environment[END_REF][START_REF] Vinothina | A Survey on Resource Allocation Strategies in Cloud Computing[END_REF]. The cloud service providers receive simultaneously a lot of computing requests from dierent users with dierent requirements and preferences (see Figure 1.1). Some tasks need to use a lower cost and less computing resources, while some other tasks require more computing resources and take more bandwidth and CPU. In a cloud computing environment the tasks may be distributed across distinct computational resources nodes. In order to allocate the tasks to these nodes, the available computing resources are detected and analyzed. Hence, the quality of cloud computing service can be described by network bandwidth, task costs and the completion time. The importance of task scheduling in cloud environment arises from the previous description. Scheduling algorithms in cloud computing environment can be categorized into two main groups based on the cloud mode : batch mode scheduling algorithms and online mode scheduling algorithms. In batch scheduling algorithms, jobs are queued and collected into a buer when they arrive in the system. Then, the scheduling algorithms will start after a xed period of time. In the other mode, jobs are scheduled immediately when they are arrived to the system [START_REF] Vignesh | Resource Management and Scheduling in Cloud Environment[END_REF]. There are many dierent techniques used to allocate user requests to the cloud computing resources in order to optimize some objectives that aect the performance of the cloud services (See [START_REF] Bala | A survey of various task scheduling algorithms in cloud environment[END_REF]).

Scheduling problems

Scheduling is a decision-making process, it is found in many real world applications. such as manufacturing and services industries. It is the process of allocating resources to tasks over a given time period aiming to optimize one, two, or multiple objectives. The resources and tasks can take many dierent forms in services and in manufacturing. The resources may be machines in a factory, processing units in a computing environment, etc. The tasks may be operations in a production line, processing of a computer programs, etc. In machine environment each task may have some constraints such as a precedence constraints, a possible starting time and a due date. The objectives can also take many dierent forms. One objective may be a single objective such as the minimization of the completion time of the last task, and another may be bi-objective or multi-objectives. Scheduling, as a decision-making process, plays an important role in computing environments, especially in cloud computing. Suppose that m machines M i (i = 1, ..., m) have to process n jobs J j (j = 1, ..., n). A schedule is for each job an allocation of one or more time intervals to one or more machines.

The classes of scheduling problems are specied in terms of a three-eld classication α|β|γ where α species the machine environment, β species the job characteristics and γ denotes the optimality criterion. Such a classication scheme was introduced by Graham et al [START_REF] Graham | Optimization and approximation in deterministic sequencing and scheduling : A survey[END_REF].

Computational complexity

In this section, we present some denitions and principles about the computational complexity. Complexity theory provides a mathematical framework in which computational problems are studied so that they can be classied as "easy" or "hard". A more detailed presentation can be found in the book of Garey & Johnson [START_REF] Garey | Computers and Intractability : A Guide to the Theory of NP-Completeness[END_REF]. The main issue of the theory of complexity is to determine the required resources needed (time, storage space) and to measure the performance of algorithms with respect to computational time.

The notations P, NP and co-NP are collections of decision problems : problems that can be answered by 'yes' or 'no', like whether a given graph has a perfect matching or a Hamiltonian circuit. The optimization problem is not a decision problem, but often can be reduced to it in a certain sense [START_REF] Schrijver | Combinatorial Optimization : Polyhedra and Eciency[END_REF]. An easy way to characterize the class NP is : NP is the collection of decision problems that can be reduced in polynomial time to the satisability problem. However, Cook in [START_REF] Cook | The complexity of theorem-proving procedures[END_REF] dened NP as the collection of all decision problems for which each input with positive answer, has a polynomial-time checkable of correctness of the answer (NP stands for nondeterministically polynomial-time). The NP-complete problems are the problems that are the hardest in NP : every problem in NP can be reduced to them. Next description clarify. Problem ⊂ Sigma * is said to be reducible to problem ∧ ⊂ Sigma * if there exists a polynomial-time algorithm that returns, for any input w ∈ Σ * an output x ∈ Σ * with the property : w ∈ ⇔ x ∈ ∧. This implies that if is reducible to ∧ and ∧ belongs to P, then also belongs to P. Similarly, if is reducible to ∧ and ∧ belongs to NP, then also belongs to NP. A problem is said to be NP-complete if each problem in NP is reducible to . An optimization problem is NP-hard if the corresponding decision problem is NP-complete.

One of the most successful methods of attacking hard combinatorial optimization problems is the genetic algorithm, which will be discussed in this chapter. Genetic algorithm generally generates feasible solutions that are not guaranteed to be optimal. Any approach without formal guarantee of performance can be considered as a "heuristic". Such approaches are useful in practical situations if there is no better methods available. Important classes of problems which are polynomially solvable are linear programming problems [START_REF] Khachiyan | A polynomial algorithm in linear programming[END_REF] and integer linear programming problems with xed number of variables [START_REF] Lenstra | Integer programming with a xed number of variables[END_REF]. 1.4. Heuristics and meta-heuristics

Heuristics and meta-heuristics

In this section, we present some denitions for heuristics and metaheuristics widely used in combinatorial optimization.

Heuristics

Optimization techniques can be classied, in a heuristic, exact and approximation methods. The heuristic methods try to nd optimal solutions or near-optimal solutions in a signicantly reduced amount of time. The heuristic methods categorized into constructive methods and local search methods. Constructive algorithms obtain solutions from scratch by adding solution components to an initially empty list, until reaching the nal solution.

Local search algorithms start from an initial solution and iteratively replace the current solution by a better candidate from the neighbors of the current solution [START_REF] Francisco | Parallel Meta-heuristic : A New Class of Algorithms[END_REF]. As dened in [START_REF] Vinothina | A Survey on Resource Allocation Strategies in Cloud Computing[END_REF], a heuristic technique is a method, which tries to nd good solutions at a reasonable computation cost without being able to guarantee optimality. Unfortunately, it may not even be possible to determine how close to the optimal solution a particular heuristic solution is.

Metaheuristics

The term meta-heuristic refers to a certain class of heuristic methods. As Fred Glover in [START_REF] Michalewicz | How to Solve It : Modern Heuristics[END_REF], rst used this term and dened it as follows : A meta-heuristic refers to a master strategy that guides and modies other heuristics to produce solutions beyond those that are normally generated in a quest for local optimality. In another denition, "meta-heuristics are solution methods that orchestrate an interaction between local improvement procedures and higher level strategies to create a process capable of escaping from local optima and performing a robust search of a solution space" [START_REF] Henderson | Metaheuristic Handbook The Theory and Practice of Simulated Annealing[END_REF]. The heuristics guided by such a metastrategy may be high level procedures or may include nothing more than a description of the strategies of moving from one solution to another with an associated evaluation rule (called tness). To distinguish between heuristics and metaheuristic concepts, we can mention that heuristics are often problem dependent, heuristics normally dened for a given problem to nd optimal or near to the optimal solutions for the problem under consideration, whereas the metaheuristics are problem independent techniques that can be applied for a wide range of problems. As an example, when we use simulated annealing metaheuristic in scheduling, the decision of moving from current solution to another candidate one will be done by metaheuristic procedure whereas this method does not know nothing about scheduling. In the literature there is a vast amount of research that used a heuristic and metaheuristics to attack scheduling problems.

Genetic algorithm

Holland in 1975 developed the idea of applying the principles of natural evolution to optimization problems. This idea has been published in his book "Adaptation in natural and articial systems". He built the rst genetic algorithm. Holland's theory has been further developed. Now, genetic algorithms (GAs) considered as a powerful tool for solving optimization problems. Genetic algorithms are based on the principle of genetics and evolution. Todays, GAs are used to resolve complicated optimization problems, like timetabling, job shop scheduling, games playing and others [START_REF] Sivanandam | Introduction to Genetic Algorithm[END_REF]. Now, we give a brief introduction to simple genetic algorithms and associated terminology. GAs encode the decision variables of a search problem into nite length strings of alphabets or digits of a certain cardinality. The strings which are candidate solutions to the search problem are referred to as chromosomes. The chromosome represent a single solution, the alphabets or digits are referred to as genes and the values of genes are called alleles. For example, in scheduling problems, a chromosome represents a sequence and a gene may represent a job, and an allele is a value of processing time taken by a specic job.

In contrast to traditional optimization techniques, GAs work with coding of parameters, rather than the parameters themselves. The general procedures of the GA are as follows :

1. Initialization. The initial population of candidate solutions is usually generated randomly across the search space. It can be binary or non-binary chromosomes.

Evaluation.

Once the population is initialized or an ospring population is created, the algorithm uses a tness function to evaluate each chromosome in the population. [START_REF] Hart | Evolutionary scheduling : A review[END_REF]. Selection. In the selection step, the algorithm works to prefer better solutions to worse ones. The algorithm selects a chromosome to mate the reproduction. 4. Recombination. Recombination combines parts of two or more parental solutions to create new ones. Here, the algorithm applies a genetic operator (crossover) on the selected chromosomes. 5. Mutation. Select one solution and apply a small random change to this solution. [START_REF] Wang | Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics[END_REF]. Replacement. Replace the current population with the temporary population.

If stopping condition is met, then STOP with the best chromosome as the nal solution for the problem. Otherwise, GOTO 2.

The determination of a population size is a crucial element in the GAs. In most of GA applications, the population size can be considered as a constant. The initialization of population performed by using some suitable heuristics that are relevant to the considered problem or can be created randomly. Selecting a very small size of population increases the risk of not converging to a global optimal solution. Large size of population increases the chance to converge to obtain a good solution. The second operator of GAs is the tness function, GA uses this function to evaluate the solution for each chromosome, then GA can determine if the chromosome can be kept or not. If the chromosome kept then it produces a new ospring or will be eliminated.The most important operator is the selection of chromosomes, which is ensure the convergence of the GA. When the genetic algorithm capable to select the best chromosome, then it will have a population of similar chromosomes, that led the GA to converge to a local optimum. Now, we give some selection methods : roulette wheel selection, deterministic selection, ranking selection, tournament selection and etc. In step four, the combination of two parents which combines the features of two ttest chromosomes and carries these features to the next generation by forming osprings. Many well known crossover methods have been developed and applied. One of them is the two-position crossover method, which consists in selecting two crossover positions in two chromosomes and then making swapping segments between the chromosomes. Also, there is another crossover method, which is multi-position crossover method. This method changes the number of segments during the execution of GA. Shue crossover method rst shues the crossover positions in the two selected chromosomes.

Then, it exchanges the segments between the crossover positions and nally un-shues the chromosomes. The uniform crossover method is a mix between one position and multipositions crossover methods. It produces two new children by exchanging genes in two chromosomes randomly. The fth operator in GA steps is the mutation, which exchange one or more of the chromosome genes randomly to ensure search changement, which may lead to the global optimum.

Finally, the last GA step is the stopping criterion. There are many methods, which can be used for the stopping criteria. One of them is the maximum number of generations.

The method based on the convergence is also used : the algorithm stops when the GA converges after all chromosomes have reached a certain degree of homogeneity or, by another stopping criterion, after a chromosome with a certain level of tness value is found.

Graph theory

In this section, we will introduce some basic denitions and notations of graph theory that will be used throughout the chapters of this dissertation. For more details, we refer the reader to [START_REF] Schrijver | Combinatorial Optimization : Polyhedra and Eciency[END_REF].

A graph is denoted G = (V, E) where V is the set of vertices or nodes and E is the set of edges. If e ∈ E is an edge with initial node u and terminal node v, we may also use both notations uv or (u, v) to denote e.

The graphs considered here are directed, nite, loopless and may include multiple arcs.

A directed graph or digraph is denoted G = (V, A) where V is the set of vertices or nodes and A is the set of arcs. If a ∈ A is an arc with origin node u and destination node v, we may also use both notations uv or (u, v) to denote a. The graph G is said to be complete if there exists an arc between each pair of nodes (u, v).

A graph or undirected graph is a pair G = (V, E), where V is a nite set and E is a family of unordered pairs from V . The elements of V are called the vertices, sometimes the nodes or the points. The elements of E are called the edges, sometimes the lines.

A graph G = (V , E ) is called a subgraph of a graph G = (V, E) if V ⊂ V and E ⊂ E. If E consists
of all edges of G spanned by V , then G is called an induced subgraph, or the subgraph induced by V . In notation,

G[V ] := subgraph of G induced by V , E[V ] := family of edges spanned by V
The complementary graph or complement of a graph G = (V, E) is the simple graph with vertex set V and edges all pairs of distinct vertices that are nonadjacent in G. In notation, Ḡ := the complementary graph of G.

Optimization problems

In mathematics, optimization is a branch of applied mathematics. It derives its importance from the wide variety of its applications and from the availability of ecient algorithms that have been used to solve such problems. Mathematically, it refers to the 1.6. Optimization problems minimization (or maximization) of a given objective function of several decision variables that satisfy functional constraints [START_REF] Pinedo | Planning and scheduling in manufacturing and services[END_REF]. For example, let us consider the optimization model, which addresses the allocation of limited resources among possible alternative uses in order to maximize the total prot. Objective function, decision variables, and constraints are three essential elements of any optimization problem. If the decision variables in an optimization problem are restricted to integers, or to a discrete set of possibilities, there is an integer or discrete optimization problems. The problem is a continuous optimization problem, if there are no such restrictions on the variables. Some problems may have a mixture of discrete and continuous variables, that depends on the nature of the problem. We give the generic description of an optimization problem. Given a function f (x) : R n → R and a set S ⊂ R n , the problem of nding an x * ∈ R that solves

min x f (x) (1.1) s.t. x ∈ S
is called an optimization problem (OP). We denote by f the objective function and by S the feasible region. If S is empty, the problem is called infeasible. If it is possible to nd a sequence x k ∈ S such that f (x k ) → -∞ as k → +∞, then the problem is unbounded. If the problem is neither infeasible nor unbounded, then it is often possible to nd a solution

x * ∈ S.

Combinatorial optimization

Combinatorial Optimization is a subset of mathematical optimization that is related to operations research, algorithm theory, and computational complexity theory. Its purpose is to study the optimization problems where the set of feasible solutions can be represented as a discrete one.

The combinatorial optimization problems are the problems, which are formulated as follows. Let E = {e 1 , ..., e n } be a nite set where each element e i is associated with a weight w(e i ). Let F be a family of subsets of E. If F ∈ F, then w(F ) = e i ∈F w(e i ) denotes the weight of F. The problem consists in identifying an element F * of F whose weight is minimum or maximum. The set F represents the set of feasible solutions of the problem. Such a problem is called combinatorial optimization problem.

The term combinatorial refers to the discrete structure of the representation of the feasible solution set F. Generally, this structure is represented by a graph. The term optimization tells that we are looking for the best element in the set of feasible solutions. This set may contain an exponential number of solutions. Thus, we cannot expect to solve a combinatorial optimization problem by checking or enumerating all its solutions one by one, which is not a reasonable option. Such a problem is then considered as a hard problem. Many eective techniques and approaches have been developed to attack combinatorial optimization problems. Some of these approaches use linear, integer programming, and polyhedral approach and others based on graph theory. combinatorial optimization is closely related to algorithm and computational complexity theory.

Linear programming

Linear programming deals with the OP with a linear function in the presence of linear inequalities. One of the most common optimization problems is linear optimization or linear programming (LP). It is the problem of optimizing a linear objective function subject to linear inequalities and equality constraints. Indeed, any combinatorial optimization problem can be reduced to solving a linear program. The standard form of the LP is given below :

min x C T x Ax = b (1.2) x ≥ 0, where A ∈ R m×n , b ∈ R m , c ∈ R n
are given and x ∈ R n is the variable vector to be determined. A wide variety of real life problems can be formulated as linear integer optimization problems. The combinatorial problems, such as the knapsack problem, resources allocation problem, TSP, network ow and graph problems, and many scheduling problems can also be solved as a linear integer optimization problems [START_REF] Genova | Linear integer programming methods and approaches :a survey[END_REF]. 1.6.3 Integer programming

When the variables are integer, we call the formulation of the problem as integer programming. Integer programs are optimization problems that require some or all of the variables to take integer values. This restriction on the variables usually makes the 1.7. Polyhedral approach problems very hard to solve. A pure integer linear program is given by :

min x C T x Ax ≥ b (1.3)
x ≥ 0 and integral, where A ∈ R × , b ∈ R , c ∈ R are given, and x ∈ N is the variable vector to be determined.

A very common case occurs when the variables x j represent binary decision variables, that is x ∈ {0, 1} n . The problem is then called a 0 -1 linear program (or discrete). When there are both integer constrained variables and continuous variables, the problem is called a Mixed Integer Linear Program (MILP) :

min x C T x Ax ≥ b (1.4) x ≥ 0 x j ∈ N, f or j = 1, ..., p
where A, b, c are given data and the integer p (with 1 ≤ p < n) is also part of the input.

Polyhedral approach

The development of polyhedral theory and the consequent introduction of strong valid inequalities led to a resurgence of cutting plane methods. The polyhedral method was initiated by Edmonds in 1965 for a matching problem. It consists in describing the convex hull of problem solutions by a system of linear inequalities. The problem reduces then to the resolution of a linear program. Normally, in most of the cases, it is not straightforward to obtain a complete characterization of the convex hull of the solutions for a combinatorial optimization problem. However, having a system of linear inequalities that partially describes the solutions polyhedron may often lead to solve the problem in polynomial time. This approach has been successfully applied to several combinatorial optimization problems. In this section, we present the basic notions of polyhedral theory. For detail, the reader is invited to consult [START_REF] Schrijver | Combinatorial Optimization : Polyhedra and Eciency[END_REF][START_REF] Mahjoub | Polyhedral Approaches[END_REF][START_REF] Francisco | Parallel Meta-heuristic : A New Class of Algorithms[END_REF].

First, we will recall some denitions, propositions, and properties related to polyhedral theory.

Elements of (S)

Conv(S) Figure 1.2 A convex hull 1.7.1
Elements of polyhedral theory Denition 1 Given a set S ⊆ R n , a point x ∈ R n is a of points of A if there exists a nite set of points {x i } t i=1 in S and a λ ∈ R t + with t i=1 λ i = 1 and x = t i=1 λ i x i .

Figure 1.2 shows the convex hull of a set of integral points in R 2 . We see that conv(S) can be described by a nite set of a linear inequalities and that max{cx : x ∈ S} = max{cx : x ∈ conv(S)}. Moreover, the latter problem is a linear program.

Finding an inequality description of conv(S) is not easy and questions such as the dimension of conv(S) and so on, are very important. In this section, we give some results from linear algebra.

Denition 2 A set of points x 1 , ..., x k ∈ R n is linearly independent if the unique solution of k i=l λ i x i = 0 is λ i = 0, i = 1, ..., k.
Note that the maximum number of linearly independent points in R n is n. Now, we describe the polyhedra by facets. Given a polyhedron P = {x ∈ R n : Ax ≤ b}, the question is to nd out which of the inequalities a i x ≤ b i are necessary in the description of P and which can be dropped. Indeed, we will show that those necessary to describe P are the same, whatever the initial inequality description of P .

Denition 5 The inequality πx ≤ π 0 [or(π, π 0 )] is called a valid inequality for P if it is satised by all points in P .

Note that (π, π 0 ) is a valid inequality if and only if P lies in the half-space{x ∈ R n : πx ≤ π 0 }, or equivalently if and only if max{πx : x ∈ P } ≤ π 0 . Denition 6 If (π, π 0 ) is a valid inequality for P and F = {x ∈ P : πx = π 0 }, F is called a face of P , and we say that (π, π 0 ) represents F . A face F is said to be proper if F = ∅ and F = P . Denition 7 A face F of P is a facet of P if dim(F)=dim(P)-1.

Cutting plane methods

Many combinatorial optimization problems can be formulated as mixed integer linear programming problems. Then, they can be solved by branch-and-cut methods, which are exact algorithms consisting of a combination of branch-and-bound algorithm with a cutting plane method. These methods work by solving a sequence of linear programming relaxations of the integer programming problem. Cutting plane methods improve the relaxation of the problem to more closely integer programming problem and branchand-bound algorithms carry out by a sophisticated divide and conquer approach to solve problems. Cutting plane algorithms for general integer programming problems were rst proposed by Gomory [START_REF] Lenstra | Integer programming with a xed number of variables[END_REF]. Thus, this method sometimes called "Gomory Cut", who proved that these algorithms terminate after a nite number of iterations with an optimum solution.

Now, let P be a combinatorial optimization problem, E its basic set, w(.) the weight function, and S the set of feasible solutions. The problem P consists in nding an element of S whose weight is maximum/minimum. If F ⊆ E, then the 0 -1 vector x F ∈ R E such that x F (e) = 1 if e ∈ F and x F (e) = 0 otherwise, is called the incidence vector of F . The polyhedron P (S) = convx S |S ∈ S is the polyhedron of the solutions of P or polyhedron associated with P . P is thus equivalent to the linear program max{cx|x ∈ P (S)}. Notice that the polyhedron P (S) can be described by a set of a facet dening inequalities. And, when all the inequalities of this set are known, then solving P is equivalent to solve a linear program.

The objective of the polyhedral approach for combinatorial optimization problems is to reduce the resolution of P to that of a linear program. In order to reduce P we need a deep investigation of the polyhedron associated with P . It is generally not easy to characterize the polyhedron of a combinatorial optimization problem by a system of linear inequalities. In particular, when the problem is NP-hard it is dicult to nd such a characterization. Moreover, the number of inequalities describing this polyhedron is exponential in most of time. Therefore, even if we know the complete description of that polyhedron, its resolution remains in practice a hard task because of the large number of inequalities.

Cutting plane method is based on the so-called separation problem. This consists, given a polyhedron P of R n and a point x * ∈ R n , in verifying whether if x * belongs to P , and if this is not the case, to identify an inequality a T x ≤ b, valid for P and violated by x * . In the later case, we say that the hyperplane a T x = b separates P and x * . More precisely, the cutting plane method consists in solving successive linear programs, with possibly a large number of inequalities, by using the following steps. Let LP = max{cx, Ax ≤ b} be a linear program and LP a linear program obtained by considering a small number of 1.8. Branch and cut algorithm inequalities among Ax ≤ b. Let x * be the optimal solution of the latter system. We solve the separation problem associated with Ax ≤ b and x * . This phase is called the separation phase. If every inequality of Ax ≤ b is satised by x * , then x * is also optimal for LP. If not, let ax ≤ α be an inequality violated by x * . Then, we add ax ≤ α to LP and repeat this process until an optimal solution is found.

Branch and cut algorithm

Branch and cut methods are often successful for nding an exact solution of hard optimization problems. For each instance, the method always maintains an upper bound (ub) and a lower bound (lb) for the optimum solution value. Iteratively, the value of the upper and lower bounds are improved, until they get the optimal solution, or a solution that is tight enough. It is known that, branch and cut is a special case of branch and bound method, where in branch and cut method the bounds are determined through LP and polyhedral theory. Informally, we summarize the basic concepts of branch and cut. We need a partial description Q of Q c (G) with the properties that the latter is contained in Q. We call such a polytope a relaxation polytope. The inequality system A p x ≥ b p describing Q is known and can be generated in polynomial time. We optimize over Q to solve the linear program, which is found in the form of the LP mentioned in this chapter. Fast algorithms for solving linear programs exist, for example the well known one is Simplex method. Within the branch and cut approach we start by some relaxation

Q of Q c (G).
Iteratively, we generate tighter description of the cut polytope. The upper bound (ub) on the optimum value of the maximum cut can be obtained by any heuristic. In the case where upper and lower bounds are the same we can stop and return an optimum solution, we can also stop where lower bound solution vector becomes integer. In branch and cut a sub problem is a node of the tree. The branch and cut algorithm is described as follows. Ecient job scheduling algorithms are addressed in this chapter to improve the resource utilization in cloud computing where the aim is to minimize the total completion time (Makespan). We present a genetic-based task scheduling algorithms in order to minimize Maximum Completion Time Makespan. These algorithms combines dierent techniques such as list scheduling and earliest completion time(ECT) with genetic algorithm. We reviewed, evaluated and compared the proposed algorithms against one of the well known GAs available in the literature, which has been proposed for optimizing the task scheduling on heterogeneous systems. After an exhaustive computational experiments the results identify that our proposed Genetic algorithms show a good performance dominating the evaluated algorithms in dierent problem sizes and complexity for a large benchmark set of instances. Moreover, greedy algorithm and ILP have been applied to attack the problem.

Introduction

This chapter discusses dierent solutions for the problem of unrelated parallel machine scheduling with precedence constraints based on heuristic and metaheuristic approaches. In Cloud environments a task scheduling is a process that maps and assign the interdependent tasks on the data centers (resources) [START_REF] Bala | A survey of various task scheduling algorithms in cloud environment[END_REF]. It allocates the tasks its appropriate virtual resources which is virtual machines (VMs) inorder to satisfy objective functions imposed by end-users. The idea of virtualizing a computer system resources(processors, memory, input/output devices), aiming to improve the sharing of computer resources [START_REF] Tsai | Optimized task scheduling and resource allocation on cloud computing environment using improved dierential evolution algorithm[END_REF]. Generally,an ecient task scheduling algorithm will have an important impact to the performance of the system throughput [START_REF] Ghanbari | A Priority based Job Scheduling Algorithm in Cloud Computing[END_REF][START_REF] Li | Online optimization for scheduling preemptable tasks on IaaS cloud systems[END_REF]. The scheduling problem in cloud computing can be generalized as an unrelated parallel machine with dierent speeds and precedence constraints. We consider VMs as an unrelated parallel machine because the cloud computing providers oer their services virtually by sharing their physical resources through a large number of virtual machines in parallel. These virtual machines, allocated with dierent CPU capacities, so it can be considered as an unrelated parallel machines. In cloud computing users may face hundreds of thousands of virtualized resources to utilize. It is hard to allocate user± tasks on the available resources. Due to the virtualization properties, cloud computing leaves task scheduling complexity to the virtual machine layer through resource virtualization.

Hence, to allocate the resources to each task eciently, scheduling plays more important role in cloud computing [START_REF] Shenai | Survey on scheduling issues in cloud computing[END_REF]. It is dicult to obtain an optimal solution with traditional optimization methods. Mathematical optimization techniques can solve the problems optimally for a reasonable size of instances, however, in the case of a large scale problems, their application is limited [START_REF] Balin | Non-identical parallel machine scheduling using genetic algorithm[END_REF]. Dispatching rules (EDD, SPT, LPT,...) are suitable only for small sized problems. It is also known that, no single dispatching rule guarantees optimal or near to the optimal solution in various problems [START_REF] Min | A genetic algorithm for minimizing the makespan in the case of scheduling identical parallel machines[END_REF]. Research efforts in scheduling are concentrated on heuristic approaches as well. Many heuristics and meta-heuristics have been proposed such as simulated annealing (SA), branch and bound (Branch and Bound), tabu search, and genetic algorithm (GA) [START_REF] Shenai | Survey on scheduling issues in cloud computing[END_REF]. Among these various approaches to dierent scheduling problems, there is an increasing interest in applying GAs, this interest comes from its characteristic, the ease of implementation, and the high adaptability. The important dierence between GA and other heuristics is that GA generate a set of solutions (populations) rather than a unique solution, which can lead to a better diversity. In scheduling problems, C max is equivalent to the completion time of the last task leaving the system. The small makespan usually means a high utilization. Therefore, reducing the makespan should also lead to a higher throughput rate in the overall system [START_REF] Min | A genetic algorithm for minimizing the makespan in the case of scheduling identical parallel machines[END_REF]. Three genetic algorithms have been applied to solve this problem.

2.1.1

Literature Review

The problem of task scheduling in distributed systems is known as an NP-hard [START_REF] Rahmani | A Novel Genetic Algorithm for Static Task Scheduling in Distributed Systems[END_REF]. To allocate n jobs to m virtual machines (VMs), the number of allocation is |n| |m| and the number of states will be n!. One of the objectives of scheduling in cloud computing is to determine the assignment of jobs to VMs in order to optimize the completion time of the last task in the system. The job scheduling problem in distributed, and heterogeneous systems such as cloud computing [START_REF] Bala | A survey of various task scheduling algorithms in cloud environment[END_REF], has been studied widely in the last few years. Generally, job scheduling problem can be found in two forms : dynamic and static. When all information needed for scheduling, such as data dependencies between jobs, and execution times of jobs are known by the scheduler, then the scheduling problem known as static scheduling problem. In static scheduling, jobs placed during the compile time. On the other hand, in the dynamic model, jobs are allocated to the processors upon their arrival to the scheduler, and scheduling decisions must be made immediately at run time [START_REF] Kwok | Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors[END_REF][START_REF] Sivanandam | Introduction to Genetic Algorithm[END_REF]. In this section we focus our attention on the available algorithms for static scheduling in cloud environment, as well the algorithms that haves been used to solve the unrelated parallel machine with precedence constraints scheduling problem. A survey on scheduling in cloud computing can be found in [START_REF] Bala | A survey of various task scheduling algorithms in cloud environment[END_REF], [START_REF] Shenai | Survey on scheduling issues in cloud computing[END_REF],and [START_REF] Jing | State-of-the-art research study for green cloud computing[END_REF]. Dierent methods for optimizing dierent objectives in cloud computing exist (See [START_REF] Ge | Research of cloud computing task scheduling algorithm based on improved genetic algorithm[END_REF][START_REF] Jang | The study of genetic algorithm-based task scheduling for cloud computing[END_REF][START_REF] Dao | Optimisation of precedence-constrained production sequencing and scheduling using genetic algorithms[END_REF][START_REF] Kwok | Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors[END_REF][START_REF] Falzon | Enhancing genetic algorithms for dependent job scheduling in grid computing environments[END_REF]). Some researchers proposed ecient meta-heuristics based on genetic algorithm : Zhou et al in [START_REF] Zhou | A Genetic-based Task scheduling Algorithms on Heterogeneous Computing Systems to Minimize Makespan[END_REF] proposed a genetic algorithm based on earliest completion time (ECT) to minimize completion time (we represent this GA in the next sections. Arash and Yalda also developed hybrid genetic algorithm for work ow scheduling in cloud system (HSGA). It merges best-t and Round Robin methods to obtain a good solution quickly by making an optimal initial population. It makes a job prioritization in complex graph. A particle swarm optimization (PSO) used in [START_REF] Wu | A revised discrete particle swarm optimization for cloud workow scheduling[END_REF] for workow scheduling in cloud environment, which considers not only execution cost but also the cost for transmitting dependent data. In [START_REF] Kang | A PSO-based Genetic Algorithm for Scheduling of Tasks in a Heterogeneous Distributed System[END_REF] a PSO is also formulated as a model for the multi-objective task assignment to optimize the time and cost. To the best of our knowledge, none of the existing Genetic algorithms have considered the idea of scheduling jobs with a high number of successors in order to optimize the makespan. [START_REF] Ghanbari | A Priority based Job Scheduling Algorithm in Cloud Computing[END_REF] presented a novel approach for job scheduling in cloud computing which was called priority based job scheduling algorithm. Their solution method based on multi-criteria decision-making model and multi-attribute decision-making model which was rst developed by T.Saaty in 1980 and called the theory of Analytical Hierarchy Process. The proposed algorithm mainly focused on priority of job. The experimental results indicated that the algorithm has reasonable complexity, however the authors did not expect that this algorithm provides an optimal makespan. Xiaofeng Wang et al in [START_REF] Wang | Optimizing Makespan and Reliability for Workow Applications with Reputation and Look-ahead Genetic Algorithm[END_REF] proposed a new max-min strategy specically for GAs, which use a novel task criticalness. They modeled a workow job as a Directed Acyclic Graph (DAG). The reliability driven scheduling of a workow application applied to maximize the reliability and to minimize the makespan of the application. The literature on parallel machine scheduling is fairly large, we focus mainly on the non-preemptive unrelated parallel machine problem with precedence constraints to minimize makespan criterion. There are many applications for this scheduling problem specially in distributed computing systems [START_REF] Kang | A PSO-based Genetic Algorithm for Scheduling of Tasks in a Heterogeneous Distributed System[END_REF], [START_REF] Zhou | A Genetic-based Task scheduling Algorithms on Heterogeneous Computing Systems to Minimize Makespan[END_REF]. Several heuristics and meta-heuristics have been proposed to solve this problem for optimizing dierent objectives. In [START_REF] Vallada | A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times[END_REF] Vallada and Ruiz proposed a genetic algorithm to minimize the makespan. Their GA includes a fast local search and a local search enhanced crossover operator. In [START_REF] Balin | Non-identical parallel machine scheduling using genetic algorithm[END_REF] Balin proposed a new crossover operator for genetic algorithm to minimize makespan, his algorithm achieved a high computational speed for large-scale problems. In [START_REF] Tavakkoli-Moghaddam | Design of a genetic algorithm for bi-objective unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints[END_REF] Tavakkoli-Moghaddam et al proposed a genetic algorithm to solve biobjective unrelated parallel machine scheduling problem. Jerey et al [START_REF] Herrmann | Heuristics for unrelated machines scheduling with precedence constraints[END_REF] considered the case where a task has at most one predecessor and at most one successor. They proposed a greedy search, which we use in this chapter for a comparison purpose, and they proposed also a heuristic based on a branch-and-bound procedure. They also applied a simulated annealing algorithm to solve the problem. Liu and Yang in [START_REF] Liu | A heuristic serial schedule algorithm for unrelated parallel machine scheduling with precedence constraints[END_REF] considered the case where the machines do not have specic speeds but every job has a processing time depending on the used machine, which is an extension of the constraint we used in our problem. They proposed an integer linear programming model and they provided a polynomial time algorithm that can schedule the prior job on the prior machine as early as possible for minimizing makespan. A hybrid genetic algorithm has been proposed in [START_REF] Liu | A heuristic serial schedule algorithm for unrelated parallel machine scheduling with precedence constraints[END_REF] for minimizing the total tardiness for the problem of unrelated parallel machines with precedence constraints. For other proposed approaches the reader could refer to see [START_REF] Pfund | A survey of algorithms for single and multi-objective unrelated parallel-machine deterministic scheduling problems[END_REF][START_REF] Ghirardi | Makespan minimization for scheduling unrelated parallel machines : A recovering beam search approach[END_REF][START_REF] Hariri | Heuristics for scheduling unrelated parallel machines[END_REF][START_REF] Glass | Unrelated parallel machine scheduling using local search[END_REF][START_REF] Fanjul-Peyro | Iterated greedy local search methods for unrelated parallel machine scheduling[END_REF][START_REF] Wu | A Task Scheduling Algorithm based on QoS-driven in Cloud Computing[END_REF].

Shamsollah et al in

In this chapter, we deal with the problem of job scheduling in cloud environment and we generalized this problem as an unrelated parallel machines scheduling with precedence 2.2. Problem formulation constraints for optimizing the makespan. We proposed three genetic algorithms, they show a very good performance for small and medium benchmarks. In the next section we will present the problem formulation and a mathematical formulation associated to solve unrelated parallel machine with precedence constraints scheduling problem.

Problem formulation

The problem under consideration is to schedule n jobs on m machines which are arranged in parallel with the aim of minimizing the total completion time. Let J be the set of the jobs and M be the set of the parallel machines. A precedence constraint between two jobs j 1 and j 2 is denoted by (j 1 ≺ j 2 ) and it requires that job j 2 cannot start to be processed until job j 1 will nish its processing. The type of the precedence constraint is a graph type, which is denoted by D = (V, A), where V is the set of vertices associated at each job ϑ and V denotes the set of edges associated with each precedence constraint. We called this graph the precedence graph. We take also the case where {v, w, w} ⊆ V such that v before w and w before w then v before w. We consider also the speeds for all machines denoted by s i , where i ∈ M . Every job j ∈ J has a processing time p j and its eective processing time depends on the selected machine i, where p ij = π j × s i . Each machine i ∈ M cannot process more than one job at a given time. Furthermore, machines have dierent speeds and preemption of jobs is not allowed. According to the well-known α|β|γ scheduling problem classication scheme proposed initially by Graham et al [START_REF] Graham | Optimization and approximation in deterministic sequencing and scheduling : A survey[END_REF], scheduling problem classication scheme this problem can be denoted as P |prec|C max We denote by C i the completion time of machine i, where i ∈ M , and denote by C ϑ the completion time of job j, where j ∈ J, in the rest of this chapter. Thus, the problem can be reduced to the following mathematical formulation proposed in [START_REF] Liu | A heuristic serial schedule algorithm for unrelated parallel machine scheduling with precedence constraints[END_REF] x

jir =        1 if job j is processed in position r on machine i 0 otherwise ∀j ∈ J, i ∈ M, r ∈ J C j ∈ N + the completion time of job j. C max ∈ N +
is the total length of the schedule. That is, when all the jobs have nished processing.

The model can be stated as :

min C max C j ≤ C max ∀j ∈ J, (2.1)
i∈M r∈{1,...,|J|}

x jir = 1 ∀j ∈ J, (2.2)
j∈J x jir ≤ 1 ∀r ∈ {1, ..., |J|}, ∀i ∈ M, (2.3
)

j 1 ∈J
x j 1 ir -

j 2 ∈J x j 2 ir-1 ≤ 0 ∀r ∈ {2, ..., |J|}, ∀i ∈ M, (2.4)
C j 2 -C j 1 + C(2 -x j 2 ir -x j 1 ir-1 ) ≥ p j 2 i ∀r ∈ {2, ..., |J|}, ∀i ∈ M, ∀j 1 = j 2 ∈ J, (2.5)
C j ≥ r∈{1,...,|J|} p ji x jir ∀i ∈ M, ∀j ∈ J, (2.6)
C j 2 -C j 1 ≥ r∈{1,...,|J|} i∈M p j 2 i x j 2 ir ∀(j 1 , j 2 ) ∈ A, (2.7)
x jir ∈ {0, 1}, ∀j ∈ J, ∀i ∈ M, ∀r ∈ {1, ..., |J|}, (2.8)
C j ≥ 0, ∀j ∈ J, (2.9)
C max ≥ 0, (2.10)
The objective function is to minimize the makespan. Inequalities (2.1) ensure that the global makespan is greater than or equal to the completion time for all jobs. Inequalities (2.2) ensure that each job should be assigned to one position on one machine. Inequalities (2.3) guarantee that at most one job will be assigned to a position on all machines. Inequalities (2.4) guarantee that there must be no empty time slot between jobs in sequences. Inequalities (2.5) ensure that the job j 2 must start its processing time after the nishing of job j 1 , if job j 1 is assigned on position r -1 and job j 2 on the position r on the same machine. Inequalities (2.6) bounding the completion time for all jobs, only if the job is in the rst position, otherwise C j is bounded with the inequalities (2.5). Inequalities (2.7) controls the precedence constraints. Inequalities (2.9) dene the type of decision variables. Inequalities (2.10) bounds C j . This mathematical model will be used later in computational experiments.

An existing algorithm 2.3 An existing algorithm

Greedy algorithms are simple and straightforward [START_REF] Wang | Optimizing Makespan and Reliability for Workow Applications with Reputation and Look-ahead Genetic Algorithm[END_REF]. The described algorithm in this section is an adaptation from [START_REF] Herrmann | Heuristics for unrelated machines scheduling with precedence constraints[END_REF]. We report the main steps for the sake of comparison with our genetic algorithm. The algorithm rst prepares the available tasks at each iteration, then uses the greedy technique to nd the best local completion time hopefully to lead to the global minimal completion time. At each iteration the algorithm calculates the completion time for each available tasks on all machines. Then, it allocates the job to the machine on which we achieve the best minimum completion time. This algorithm is designed as follows :

Algorithm 3: Greedy algorithm description Data: set of M = {1, ..., m} machines, and set of J = {1, ..., n} jobs Result: C max 1 Let Av be the set of all available tasks that could be scheduled.

2 Starting : C i = 0 for all i ∈ M .

3 while |Av| > 0 do 4 Let j and i be the job from the available tasks and the machine that can nish the earliest. Schedule j on i and update the availability C i of machine i . Update Av;

5 end

Genetic algorithm (GA)

The GA is a general search approach inspired by the process of the natural evolution. It has been widely exploited for solving combinatorial optimization problems [START_REF] Pfund | A survey of algorithms for single and multi-objective unrelated parallel-machine deterministic scheduling problems[END_REF]. It is introduced in the 1970s by Holland [START_REF] Vallada | A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times[END_REF] The basic idea of our algorithm is to exploit the advantages of the both of the evolutionary and heuristic based algorithms. The solution of any problem using GAs will be represented as a chromosome containing a series of genes, its tness value is related to its objective function and constraints for that solution.

The population P of generation g, denoted by (P g ), consists of a set of chromosomes. GA utilizes a population of solutions in its search in order to nd a better solution. The eciency of GA depends largely on the presentation of a chromosome which is composed of a series of genes. In this chapter we proposed two encoding methods random ). The Mutation operator reorganizes the structure of the chromosome by changing the positions of genes randomly so that a new combination of genes may appear in generation P g+1 . It manages the search by jumping form out of local optimal solutions. The reproduction process is to copy a chromosome to the next generation so that chromosomes from various generations could pull together in the evolution and the quality of the population may improved after each generation [START_REF] Balin | Non-identical parallel machine scheduling using genetic algorithm[END_REF]. The general schema of GA may be illustrated as follows :

Algorithm 4: Genetic algorithm pseudo-code 1 Generate randomly an initial population of solutions. 2 Calculate the tness of the initial population. valuate the mutated ospring. All the ospring will be the new population.

end

The instances in Figure 2.1 and Table 2.1, will be considered for numerical example.

The rest of genetic algorithms tested and compared under the following proposed benchmark of instances. The processing times are uniformly distributed between 1 and 100 as it is common in the literature [START_REF] Hall | Generating Experimental Data for Computational Testing with Machine Scheduling Applications[END_REF]. We keep the processing time for a specic size of problem as in Table 2 In this section, we present the modeling of our GAs for directed ascending graphs (DAGs) in cloud environment. These scheduling algorithms eectively addresses the issues of minimizing the makespan.

Task Scheduling Genetic Algorithm (GATS)

This GA has been proposed on heterogeneous computing systems by Zhou et al in [START_REF] Zhou | A Genetic-based Task scheduling Algorithms on Heterogeneous Computing Systems to Minimize Makespan[END_REF].

They call it, task scheduling based Genetic Algorithm (GATS). It has been modeled as follows : The linear order of all jobs forms the chromosome. Each chromosome represents a solution for the problem by scheduling the jobs in the order given by the permutation, the order of the jobs should be a valid topological order as the associated nodes in the DAG, where start nodes should be placed in the chromosome at the beginning position , while the last nodes should be placed at the end. The initial population is produced by making a random perturbation to the order of jobs in the rst chromosome to produce a valid chromosome, until the desired size of the initial population reached. Indeed, a linear crossover from a single random position applied to the two selected parents. The mutation operation operated for all individuals of the new population considering the precedence constraints topologically. Then, the objective function is evaluated by using the Earliest Completion Time (ECT) technique, which schedules a candidate job onto machines (processors) on which the completion time of the job is the earliest. The robust characteristic in this GA is the generation of a valid chromosome in the initial population. At the next generation, we modify GATS in GAT S + by just making a random mutation for two genes selected randomly and if the candidate chromosome is not valid, then we throw it out by assigning a big value as C max to this candidate. Since we have valid chromosomes in the initial population, the robust characteristics of the GATS can still be maintained and we will not spend a lot of computation time in the mutation operator. This small change increases the chance to nd a best result, especially when the computation time is less than one minute, because GATS spends a lot of time in mutation procedure if the candidate is not valid. Table 2.3 shows the results obtained by GATS and GAT S + in one second with Psize = 100, P c = 1.0 and P m = 0.5. The dashed results means that GATS does not nd a solution during one second and also when we run the instances for 10 seconds GATS cannot nd a solution with the problems of large number of instances in all of the three density sets.

Genetic Algorithm Based on Cut-point (GACP)

For this genetic algorithm (GACP), the chromosome coding composed of two rows : the rst represents a valid order of jobs according to the precedence constraints, and the second row gives an information on job positioning according to the cut-point. We generate m -1 random cut-points (cp) = {cp 1 , cp 2 , ..., cp m-1 , } to assign jobs to its VMs. The solution provided as follows : The sequence of jobs from j 0 to j cp 1 will be assigned on VM1 and the sequence of jobs from j cp 1 + 1 to j cp 2 will be assigned on VM2 and the sequence of jobs from to on VM3 and so on. In other words, we assign a valid sub-sequence of a random length of jobs on a specic VM. In this genetic algorithm we carried out one point crossover between two parents and an exchange between two random points carried as mutation operator. However, this genetic algorithm gave bad results. The best result obtained by GACP is at least two times the C max obtained by GATS.

Genetic Algorithm Based on The List of Available Jobs (GAAV)

In this section we will propose a simple idea to generate the population with lowest computational cost, where the chromosome coding depends on VMs and places the job in its associated VM, and the computational eorts will be taken in the evaluation function. In this section we will describe our second genetic algorithm, based on the list of available jobs (GAAV), which is depends mainly on the available-list scheduling heuristic.

Coding an initial population : The assignment of VMs to the list of jobs is a candidate solution to the problem. Therefore, the chromosome can be represented by a linear list of integers, each integer representing a VM, here mi considered as gene. The series of genes with the length of n are generated randomly by assigning each job of J to a random mi In GAAV there is no computational eort to produce the initial population (IP ) because it is produced by making a random number of permutations to the integer-list to produce a chromosome until the size of IP (IP size) reached. Hence, all chromosomes give a valid solution.

Fitness evaluation In GAAV, to evaluate the chromosome, rst we search the virtual machine with minimum completion time C i . For this machine we take its available jobs according to the precedence constraints, from these available jobs we schedule the job with the maximum number of successors will be placed to the selected virtual machine rst. Then, we update Available list, and search again for machine with the minimum completion time and repeat this process until we nish the evaluation process. Simply, at each placement iteration we select the machine with minimum completion time and its available job with highest number of successors. Then, we assign the job which could lead to a late schedule of some jobs in the future to its VM, maybe this job will aect the C max of the whole system. At the end of this process, a valid schedule will be obtained and the tness function (C max ) also will be calculated. 5 illustrates the GAAV tness function steps.

Algorithm 5: Fitness Evaluation Function for GAAV.

1 Let Available be the current set of jobs without predecessors parents (parent1, parent2), then a new two osprings are obtained as of f spring1, and of f spring2, the crossover operated between two chromosomes one with higher tness value and the other with the P c ratio. Table 2.5 illustrates the crossover operator. Mutation Mutation can be thought as an eectively escape method for premature convergence by randomly change the value of an individual. For maintaining the feasibility of the new generated individual. During the mutation process, one gene selected randomly and we put it on a dierent random mi from the set of M to obtain a new ospring, Table 2.6 represents the mutation operator. Stopping rule The GA is stopped when the execution time is greater than the maximum execution time allowed. Figure 2.2, represents an example of chromosome encoding solution for GATS, which is (1-3-2-6-7-4-5), and a chromosome encoding solution for GAAV, which is (2-1-1-2-2-1-1), for the instances in Table 2.1 according to the precedence constraints in Figure2.1, run on two VMs of dierent speeds which are :

C max ↓ j 1 j 2 j 6 j 7 m 1 j 3 j 4 j 5 m 2 (b) GATS solution
s 1 = 1, s 2 = 2.

Genetic Algorithm (GAAV + )

When GATS depends mainly on ECT technique and GAAV based on the local density of the DAG, according to the eectiveness of these two techniques in the optimization of scheduling unrelated parallel machine problem with precedence constraints, we combined these two techniques in GAAV + .

In this genetic algorithm GAAV + , the modication occurred in the Fitness Evaluation. Therefore, the chromosome representation as in Table 2.4, according to this coding we know the VM for each job, this tness evaluation will select the job in machine that will give the minimum C j from the available jobs j AV, where AV is the current set of jobs without predecessors, this is ECT technique. From the other hand, at the same time we considered the number of successors of this job, and this is the local density of the DAG technique. Thus, the evaluation can be taken by selecting job j from AV with the minimum value produced by the following function : α(C j ) -(1 -α)|Succ j | where α ∈ [1, 0] and |Succ j | is the number of successors of job j. We schedule the job with the minimum value of this function rst to generate a valid schedule for calculating C max .

Experimental Results

This section presents the experimental results of GAT S, GAT S + , GAAV and GAAV + . A set of simulations have been performed on Dell Intel, core i5 running at 3.4 GHz, and 8 GB of RAM. The GAs have been coded in C++, compiled with g++ compiler, and tested under Ubuntu 14.02 64-OS. The entries in the Table 2.8 are : m : number of machines, n : number of jobs, GATS : C max value for GATS, GATS+ : C max value for GATS+, GAAV : C max value for GAAV, GAAV+ : C max value for GAAV+, Genetic search is implemented through genetic operators. 2.8 show the results given by our proposed GAs (GAT S + , GAAV, and GAAV + ) compared to GATS. From this simulation study we xed the parameters with the combination of (100, 1.0, 0.5, 600), Population size, Crossover ratio, mutation ratio and the computation time respectively. We have tested out dierent values of α in GAAV + to nd the best value. Therefore, we took α = 0.5.

From the results we have noticed that when population size in GAAV is larger than 100, any increase of it has no signicant inuence on the performance of the genetic algorithm. In Table 2.8 we can see the genetic algorithm GAAV can improve 31% of the solutions obtained by GATS in low density problems, 43% in medium density problems and 43% in high density problems. One other interesting outcome is that GAAV can be considered as an ecient algorithm with the problems of small and medium number of VMs. GAAV + mostly outperforms GATS when the number of jobs 100 and 200 in high density. This may improve 50% of solutions obtained by GATS. It can also improve 50% of medium density problems and 31 of low density problems. If we focused our attention to genetic algorithm GAT S + , we can see that for low density showed a good performance and for medium and high density problems is really far from the best solutions, because when we thrown out the invalid candidates we lost some information about some generations. According to the GATS operators behaviors, it always needs more time than the specied stop criterion, with the problems of large numbers of machines and jobs.

Another interesting factor to study in the experiments is the count of best solutions obtained by GAs. In Figure 2.3 we can notice that GAT S + can nd maximum number of best solutions overall instances in one second and ten seconds, whereas GATS cannot nd best solution within the specied computation time, we noticed that GATS cannot obtain solution when we run it for 1 and 10 seconds, it needs at least 77% seconds to obtain solution with few number of iterations. We also noticed that GATS need a lot of time to nd the rst population and for other genetic algorithm operators. We can also see the similarity of a behavior for GATS and GAT S + when we run them for 10 and 60 seconds with the improvement of GAT S + . Therefore, we can say GATS+ outperforms GATS in terms of best solutions for sizes and densities. In Figure 2.3 it is clear that GAAV + has a positive relationship with the computation time, and has the ability to improve the counts of best solutions for dierent problems. The other positive thing is that, it can also obtain a solution within the specied computation time. The eciency of GAAV appears when we run it for one second ; it can always obtain the best solution for the minimum and medium problems. , where C Best max is the best known C max , obtained by the given GA, and C First max is the rst C max obtained by this GA. We noticed that GATS with low, medium and high density DAG problems cannot improve its solutions. This means GATS starts with a good initial population and the computation time will not aect this solution positively.

This behavior inherited also by GAT S + , whereas GAAV and GAAV + start with random solutions, but they can obtain a better solutions when we increase the computation time. Figure 2.4 represents the convergence traces for processing the problem of high density of a randomly generated DAG with 5 VMs and 100 jobs. It can be observed from this gure GAAV + decreases quickly. GAAV also shows a quick decreasing and provides a best solution when it runs for 10 and 60 seconds. Whereas GATS remains in the same trend, this behavior followed with most of our problems. Hence, we can say that the techniques used in GAAV and GAAV + can improve the solution and we can nd a better upper bound for this problem. The modication of GATS in GAT S + also has a good outcome.

Integral Linear Programming Solution (ILP)

The mathematical model is applied for small instances. It is implemented with CPLEX 12.4, on an Intel, core i5 running at 3.4 GHz, and 8 GB of RAM under a computation time limit of one hour (if after one hour no optimal solution is obtained, the current integer solution is returned). In Table 2.7, columns LB and UB represent the lower bounds and the upper bounds respectively for some problems, for which CPLEX is not able to nd the linear relaxation value. Indeed, we have limited the use of the RAM to 6 GB and for the most of instances this amount is not sucient for the linear relaxation with all these constraints and variables in the model.

Transformations Between Genetic Algorithms

In spite of the variety between GATS and GAAV encodings, we tried to investigate the ability of each genetic algorithm to improve the solution obtained by the other genetic algorithm. We transformed the best population generated by the rst genetic algorithm, to be the rst population for the second genetic algorithm. This also provides interesting observations, about the dierences between our proposed genetic algorithms and GATS, by doing all transformations from GATS to GAAV and GAAV + , and from GAAV,GAAV + to GATS. We noticed that, because of the dierences of the encoding and the genetic operators between GATS in comparing to GAAV and GAAV + the ARPG between the best solution obtained by the rst GA before transformation and the best solution obtained by the second genetic algorithm after the transformation.

The ARPG is computed as follows : 100

× (C FirstBest max -C SecondBest max ) C SecondBest max
, where C F irstBest max is the best known C max , obtained by the rst GA, and C SecondBest max is the best known C max , obtained by the second GA. Table 2.9 shows the ARPG of the transformation processes : the negative values mean that the second best solution is worse than the rst best. We observed that the behavior of the proposed GAs and GATS is not the same. From the transformations, GAAV and GAAV + cannot make an improvement to the best generation obtained by GATS. However, for the solutions obtained by the transformations from GAAV to GATS and from GAAV + to GATS sometimes these transformations can lead to solutions better than those obtained by GAAV, GAAV + and GATS. Table 2.10 represents a comparison between the best solutions obtained among all GAs in column labeled Best and the transformations solutions. We can see also, AV + T S can improve the best solution obtained by the rst genetic algorithm for instances of large number of jobs, but this improvement did not improve the best solution obtained among all genetic algorithms.

Instances

Low In this chapter we have proposed genetic algorithms for job scheduling problem in cloud computing with the objective of minimizing the makespan (C max ), which is considered as an unrelated parallel-machine scheduling problem under precedence constraints. GAAV includes a new local search procedure for local graph density to evaluate the chromosome. GAT S + which is based on a permutation coding and ECT, and GAAV + which is combined the innovative characteristics of GAAV with the (ECT) technique. The performances of our proposed genetic algorithms have been compared against one of the best existing genetic algorithm for the same problem. After extensive comparisons, we can conclude that the proposed algorithms can improve the solutions obtained by GATS for small and medium problems. Moreover, they can get better results than GATS within the specic running time (stop criterion) for a high and medium DAG density problem. In the future work, we will enhance the mathematical model by adding new constraints for further improvement. Another interesting topic regarding scheduling problem in cloud computing is to consider the multiobjective optimization context.

In the next chapter we will compare the available mathematical models with our proposed model, and will present some valid inequalities to our model. In this chapter we studied an unrelated parallel machine scheduling problem of minimizing makespan subject to precedence constraints R m |prec|C max . In this chapter we compared our proposed mathematical model with other mathematical formulations found in the literature. The main dierence between these formulations is the way the makespan has been linearized. We generate sets of benchmark instances and compare the performance of the mathematical formulations with extensive computational testing. Moreover, three families of valid inequalities are proposed. The rst two inequalities based on the idea of the precedence jobs and the third based on the shortest processing time(SPT). We studied the validity of the new inequalities and strength them by checking the linear combination. After an exhaustive computational and statistical analysis we can conclude that the addition of these inequalities decreases the computational requirements to obtain the optimal solution in many cases.

Introduction

This chapter addresses the unrelated parallel machines scheduling problem with precedence constraints. However, parallel machine scheduling problems (PMSPs) have been a subject of continuing interest for researchers and practitioners since they were rst introduced by McNaughton [START_REF] Mcnaughton | Scheduling with deadlines and loss functions[END_REF]. Many PMSPs for dierent manufacturing environments have been studied. Previous studies on parallel machine scheduling problems are generally classied into three categories McNaughton [START_REF] Mcnaughton | Scheduling with deadlines and loss functions[END_REF] : (1) identical parallelmachines (2) uniform parallelmachines and (3) unrelated parallel machines. Among these categories, machines that are non-identical to one another and cannot be fully correlated by simple rate adjustments are classied as unrelated parallel machines Pinedo [START_REF] Pinedo | Scheduling : theory, algorithms, and systems[END_REF]. This environment is common in dierent manufacturing and services domains, textile manufacturing, chemical, assembly lines, electronic manufacturing, the area of project management, service industries, and also in computing services. However, the case when machines are unrelated has been much less studied. Additionally, the consideration of precedence constraints between jobs has been considered in limited works (see e.g [START_REF] Kumar | Scheduling on unrelated machines under tree-like precedence constraints[END_REF]). Several mathematical formulations are proposed to solve dierent types of unrelated parallel machine scheduling problems (UPMS) [START_REF] Kumar | Scheduling on unrelated machines under tree-like precedence constraints[END_REF][START_REF] Edis | Parallel machine scheduling with additional resources : Notation, classication, models and solution methods[END_REF].

The unrelated parallel machines is a generalization of the single machine from it is theoretical point of view, and a special case of the open shop. From a practical point of view, it is important because the occurrence of resources in parallel is common in the real world. Moreover, techniques for machines in parallel are often used in decomposition procedures for multi-stage systems [START_REF] Pinedo | Scheduling : theory, algorithms, and systems[END_REF]. Garey and Johnson in [START_REF] Garey | Computers and Intractability : A Guide to the Theory of NP-Completeness[END_REF] showed that minimizing the makespan C max considering two identical machines is an NP-hard problem. Indeed, The unrelated parallel machine scheduling problem (UPMSP) is more dicult than the identical case, Chiuh and Wei-Shung in [START_REF] Chyu | A Pareto evolutionary algorithm approach to bi-objective unrelated parallel machine scheduling problems[END_REF]. The unrelated machines consist of multiple machines that have dierent speeds. This implies a dierent processing time for each job depending on the selected machine. It represents a lot of situations in several real world applications where each machine has a dierent capability (speed). For the solution of the unrelated parallel machine a variety of techniques have been developed and proposed in dierent cases [START_REF] Li | Scheduling Precedence Constrained Parallel Tasks on Multiprocessors Using the Harmonic System Partitioning Scheme[END_REF][START_REF] Mohammed-Albarra | Genetic Algorithm for Job Scheduling in Cloud Computing[END_REF], especially in heuristics [START_REF] Aho | On a parallel machine scheduling problem with precedence constraints[END_REF][START_REF] Ghirardi | Makespan minimization for scheduling unrelated parallel machines : A recovering beam search approach[END_REF][START_REF] Wang | Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics[END_REF], meta-heuristics [START_REF] Vallada | A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times[END_REF][START_REF] Balin | Non-identical parallel machine scheduling using genetic algorithm[END_REF][START_REF] Ying | Makespan minimization for scheduling unrelated parallel machines with setup times[END_REF]], and 3.2. Problem Description exact solutions [START_REF] Liaw | Scheduling unrelated parallel machines to minimize total weighted tardiness[END_REF][START_REF] Mingozzi | An Exact Algorithm for the Resources Constrained Project Scheduling Problem Based on a New Mathematical Formulation[END_REF]. In the last few decades there are numerous dierent models have been proposed to solve the problem of scheduling parallel machine considering dierent objective functions and dierent constraints [START_REF] Gacias | Parallel machine scheduling with precedence constraints and setup times[END_REF][START_REF] Hsu | Unrelated parallelmachine scheduling with rate-modifying activities to minimize the total completion time[END_REF][START_REF] Mingozzi | An Exact Algorithm for the Resources Constrained Project Scheduling Problem Based on a New Mathematical Formulation[END_REF][START_REF] João Paulo De | Hybrid GRASP Heuristics to Solve an Unrelated Parallel Machine Scheduling Problem with Earliness and Tardiness Penalties[END_REF][START_REF] Liu | A heuristic serial schedule algorithm for unrelated parallel machine scheduling with precedence constraints[END_REF][START_REF] Blazewicz | Mathematical programming formulations for machine scheduling : a survey[END_REF][START_REF] Blazewicz | Mathematical programming formulations for machine scheduling : A survey[END_REF]. A natural way to attack machine scheduling problems is to formulate them as mathematical programming models [START_REF] Kan | Machine scheduling problems[END_REF]. Therefore, in this chapter we proposed mathematical formulation for the problem of scheduling n jobs on m unrelated parallel machines with the objective of minimizing the makespan, considering the precedence constraints. We also adapted the formulations given by Chunfeng Liu and Shanlin Yang [START_REF] Liu | A heuristic serial schedule algorithm for unrelated parallel machine scheduling with precedence constraints[END_REF], and the formulations given in [START_REF] João Paulo De | Hybrid GRASP Heuristics to Solve an Unrelated Parallel Machine Scheduling Problem with Earliness and Tardiness Penalties[END_REF] by João Paulo et al in the rst and the second models respectively. The objective of this chapter is to provide a mathematical formulation. Our mathematical model has been compared with the other mentioned models. From its promising results we proposed additional valid inequalities to strength the quality of the linear relaxation of the ILP. In addition the branch and cut approach and a separation algorithms have been applied to solve the ILP. All models are tested on large sets of instances. We enhanced the obtained results by applying branch and cut and separation algorithms to our ILP relaxation.

The chapter is organized as follows. Section 3.3 introduces the dierent mathematical formulations that are found in the literature and our proposed model with the separation algorithm for SPT inequality. 3.4 presents the classes of valid inequalities. Section 3.5 represent the experimental results.

Problem Description

Recall the description of the problem stated in the previous chapter : The problem under consideration is to schedule n jobs on m machines which are arranged in parallel with the aim of minimizing the total completion time. Let J be the set of the jobs and M be the set of the parallel machines. A precedence constraint between two jobs j 1 and j 2 is denoted by (j1 ≺ j2) and it requires that job j 2 cannot start to be processed until job j 1 nishes its processing. The type of the precedence constraint is a graph type, which is denoted by D = (V, A), where V is the set of vertices associated at each job ϑ and V denotes the set of edges associated with each precedence constraint. We called this graph the precedence graph. We take also the case where {v, w, w} ⊆ V such that v before w and w before w then v before w. We consider also the speeds for all machines denoted by σ i , where i ∈ M . Every job ϕ ∈ ϑ has a processing time π ϕ and its eective processing time depends on the selected machine i, where process more than one job at a given time. Furthermore, machines have dierent speeds and preemption of jobs is not allowed. According to the well-known α|β|γ scheduling problem classication scheme proposed initially by Graham et al [START_REF] Graham | Optimization and approximation in deterministic sequencing and scheduling : A survey[END_REF], scheduling problem classication scheme this problem can be denoted as P |prec|C max We denote by C i the completion time of machine i, where i ∈ M , and denote by C ϑ the completion time of job ϑ, where ϑ ∈ ϕ.

π iϑ = π ϑ × σ i . Each machine i ∈ M cannot

Mathematical Formulations

In this section we present dierent mathematical models for the UPMSP with precedence constraints, with the objective of minimizing the makespan C max . The rst model based on the position of job on the machine and the job completion time. The second model use idea of the ow formulation which is focus on the sequence of jobs on machines. The third model is based on the partition in linear orderings. Our proposed models are based on the interval and m-clique free graphs.

In the next sections we present these mathematical formulations.

Classical Formulation

The idea of this ILP given in [START_REF] Liu | A heuristic serial schedule algorithm for unrelated parallel machine scheduling with precedence constraints[END_REF] is based on the position of job on the machine and the completion time of each job. Figure 3.1, and Figure 3.2 illustrate the idea of this formulation.

In this Formulation we will denote by C a large positive number. For describing this model, let us introduce the following variables : x jir = 1 if job j is processed in the position r on machine i 0 otherwise ∀j ∈ J, i ∈ M, r ∈ J C j ∈ N + is the completion time of job j. C max ∈ N + is the total length of the schedule. That is, when all the jobs have nished processing.

m i j j .. j 2 j 1 C j 1 C j 2 positions 1 2 ... r-1 r p ij 1
The model can be stated as :

min C max C j ≤ C max ∀j ∈ J, (3.1)
i∈M r∈{1,...,|J|}

x jir = 1 ∀j ∈ J, (3.2)
j∈J x jir ≤ 1 ∀r ∈ {1, ..., |J|}, ∀i ∈ M, (3.3)
j 1 ∈J
x j 1 ir -

j 2 ∈J x j 2 ir-1 ≤ 0 ∀r ∈ {2, ..., |J|}, ∀i ∈ M, (3.4)
C j 2 -C j 1 + C(2 -x j 2 ir -x j 1 ir-1 ) ≥ p j 2 i ∀r ∈ {2, ..., |J|}, ∀i ∈ M, ∀j 1 = j 2 ∈ J, (3.5)
C j ≥ r∈{1,...,|J|} p ji x jir ∀i ∈ M, ∀j ∈ J, (3.6)
C j 2 -C j 1 ≥ r∈{1,...,|J|} i∈M p j 2 i x j 2 ir ∀(j 1 , j 2 ) ∈ A, (3.7)
x jir ∈ {0, 1}, ∀j ∈ J, ∀i ∈ M, ∀r ∈ {1, ..., |J|}, (3.8)

C j ≥ 0, ∀j ∈ J, (3.9)
C max ≥ 0, (3.10)
The objective function is to minimize the makespan. Inequalities (3.1) ensure that the global makespan is greater than or equal to the completion time for all jobs. Inequalities (3.2) ensure that each job should be assigned to one position on one machine. Inequalities (3.3) guarantee that at most one job will be assigned to a position on all machines. Inequalities (3.4) guarantee that there must be no empty time slot between jobs in sequences. Inequalities (3.5) ensure that the job j 2 must start its processing time after the nishing of job j 1 , if job j 1 is assigned on position r -1 and job j 2 on the position r on the same machine. Inequalities (3.6) bounding the completion time for all jobs, only if the job is in the rst position, otherwise C j is bounded with the inequalities (3.5). Inequalities (3.7) controls the precedence constraints.

Flow Formulation

In this ILP we consider a graph and we search m disjoint paths where each path represent the sequence of jobs on machines. Figure 3.3 illustrate the idea. et al [START_REF] João Paulo De | Hybrid GRASP Heuristics to Solve an Unrelated Parallel Machine Scheduling Problem with Earliness and Tardiness Penalties[END_REF] for minimizing earliness and tardiness penalties. The model uses a dummy job j 0 to mark the beginning and the end of a sequence of jobs on each machine, or with another words, all paths begin and nish by a dummy job. The model involves the following variables : M C j,i ∈ N + is the completion time of job j on machine i , ∀j ∈ J ∪ {j 0 } and ∀i ∈ M .

x j 1 ,j 2 ,i = 1 if job j 1 is precedes job j 2 directly on machine i 0 otherwise ∀j 1 , j 2 ∈ J∪{j 0 }, ∀i ∈ j 4 j 1 j 2 j 3 (
C max ∈ N + is the total length of the schedule. The mathematical model is :

min C max C j,i ≤ C max ∀j ∈ J, ∀i ∈ M (3.11) i∈M j 1 ∈(J∪{j 0 })\{j 2 } x j 1 ,j 2 ,i = 1 ∀j 2 ∈ J, (3.12)
j∈J x j 0 ,j,i ≤ 1 ∀i ∈ M, (3.13)
j 1 ∈(J∪{j 0 })\{j}
x j 1 ,j,i -

j 2 ∈(J∪{j 0 })\{j} x j,j 2 ,i = 0 ∀j ∈ J, ∀i ∈ M, (3.14)
C j 2 ,i ≥ C j 1 ,i -C + (p j 2 ,i + C)x j 1 ,j 2 ,i ∀i ∈ M, ∀j 1 ∈ J ∪ j 0 , ∀j 2 ∈ J, (3.15)
C j 1 ,i 2 ≤ C j 2 ,i 1 - j∈(J∪{j 0 })\{j 2 } p j 2 i 1 x j 2 ,j,i 1 ∀(j 1 , j 2 ) ∈ A, ∀i 1 , i 2 ∈ M, (3.16)
C j,i ≥ 0, ∀(j 1 , j 2 ) ∈ A, (3.17)

x j 1 ,j 2 ,i ∈ {0, 1} ∀i ∈ M, (3.18)
The objective function is to minimize the makespan. Inequalities (3.11) ensure that the global makespan is greater than or equal to the completion time for all jobs on all machines. Inequalities (3.12) ensure that for all jobs there exist a direct predecessor. Inequalities (3.13) limit the number of successors of the rst dummy job j 0 for all machines. Furthermore, if j∈J x j 0 ,j,i = 0 then we have no job on the machine i. Inequalities (3.14) ensure that we have several disjoint paths. For instance if x j 1 ,j 2 ,i = x j 2 ,j 4 ,i = 1 then we obtain the sequence j 1 → j 2 → j 4 on the machine i(see Figure 3.4). Inequalities (3.15) controls the completion times of the job at the machines, if a job j 2 assigned to machine i after j 1 (i.e. x j 1 ,j 2 ,i = 1), it's completion time C j 2 ,i must be greater than the completion time of j 1 , C j 1 ,i plus the processing time of j 2 . If (x j 1 ,j 2 ,i =0), then the big constant C render the constrain redundant. Inequalities (3.16) ensure that in dierent machines the completion time of precedent job in an arc is less than or equal to the starting time of successor job in the same arc. Inequalities (3.17) and (3.18) bound the decision variables.

Order Formulation

This formulation proposed by Coll et al [START_REF] Coll | Multiprocessor scheduling under precedence constraints : Polyhedral results[END_REF], this formulation reveals as a part of it a polytope of partition in linear orderings for solving the problem of multiprocessors scheduling with precedence constraints. The following variables used to describe the model :

x ji = 1 if job j processed on machine i 0 otherwise ∀j ∈ J, ∀i ∈ M z j 1 j 2 =
1 if job j 1 scheduled before j 2 on the same machine 0 otherwise ∀j 1 , j 2 ∈ J y j the starting time of the execution of each job j ∈ J . -P j = {j 1 ∈ J : there exists a path in G from j 1 to j 2 }, i.e., P j is the set of predecessors of job j 1 ; -Γ j = {j 1 ∈ J : (j 1 , j 2 ) ∈ A}, i.e.,Γ j is the set of immediate predecessors of job j 2 ; -Q j = {j 1 ∈ J : there exists a path in G from j 2 to j 1 }, i.e., -Q j is the set of successors of job j 2 ; -R j = {j 1 ∈ J : there is no path in G from j 2 to j 1 or from j 1 to j 2 }. The model formulated as follows :

min C max i∈M x i j = 1 ∀j ∈ J, (3.19)
y j 1 -y j 2 + i∈M d j 1 i .x j 1 i ≤ µ j 1 j 2 (1 -z j 1 j 2 ) ∀j 2 ∈ J, ∀j 1 ∈ R j , (3.20)
y j 1 -y j 2 + i∈M d j 1 i .x j 1 i ≤ 0, ∀j 2 ∈ J, ∀j 1 ∈ Γ j , (3.21)
y j -C max + i∈M d ji .x ji ≤ 0, ∀j ∈ J, (3.22)
z j 1 j 2 + z j 2 j 1 + x j 1 i -x j 2 i ≤ 1 ∀j 1 ∈ J, ∀j 2 ∈ R j , ∀i ∈ M, (3.23)
z j 1 j 2 + x j 1 i -x j 2 i ≤ 1 ∀j 1 ∈ P j , ∀j 2 ∈ J, ∀i ∈ M, (3.24)
x

j 1 i + x j 2 i -z j 1 j 2 ≤ 1 ∀j 1 ∈ R j , ∀j 2 ∈ J, ∀i ∈ M, (3.25)
y j ≤ δ j ∀j ∈ J, (3.26)
y ji ∈ {0, 1} ∀(j, i) ∈ J × M, (3.27)
z j 1 j 2 ∈ {0, 1} ∀j 2 ∈ J, ∀j 1 ∈ R j 2 ∪ p j 2 , (3.28)
Eq. (3.19) ensure that each job is processed and assigned to exactly one processor. Inequalities (3.21) express the precedence constraints. Inequalities (3.22) dene the makespan. Inequalities (3.20) dene the sequence of starting times of the jobs assigned to the same processor, ensuring that no overlap occurs. The constant µ j 1 j 2 is such that if job j 1 and j 2 are not executed in the same processor in that order, then inequality (3.20) is always satised. Inequality (3.26) δ j is a lower bound to the earliest starting time of job j.

Interval Graph Formulation

The third Integer Linear Programming considers the beginning of the job and the relation between jobs if they run on the same machine, also verify if one job j 1 run before another job j 2 or they run the same time on dierent machines. The graph induced by the relation where two jobs run in the same time must be an interval graph and check if all jobs can be schedule on this number of machines. This model consists of the following decision variables :

y i ∈ N + the starting time of job j. x i j = 1 if job j on machine i 0 otherwise ∀j ∈ J, ∀i ∈ M z j 1 ,j 2 =
1 if job j 1 and job j 2 run at the same time 0 otherwise

∀j 1 , j 2 ∈ J zj 1 ,j 2 =
1 if job j 1 is before or runs at the same time with job j 2 0 otherwise ∀j 1 , j 2 ∈ J C max ∈ N + the total completion time The model can be described by the following ILP (P')

min C max y j + i∈M p ij x i j ≤ C max , ∀j ∈ J, (3.29)
i∈M x i j = 1, ∀j ∈ J, (3.30)
x i j 1 + x i j 2 ≤ 2 -z j 1 ,j 2 , ∀j 1 , j 2 ∈ J, ∀i ∈ M, (3.31)
y j + i∈M p ij x i j ≤ y j 1 , ∀(j, j 1 ) ∈ A, (3.32)
y j + i∈M p ij x i j ≤ y j 1 + C zj,j 1 , ∀j, j 1 ∈ J, (3.33
)

zj 1 ,j 2 + zj 2 ,j 1 ≤ 1 + z j 1 ,j 2 , ∀j 1 , j 2 ∈ J, (3.34)
j 1 ,j 2 ∈I z j 1 ,j 2 ≤ |E[I]| -1, ∀I ⊆ I, (3.35)
j 1 ,j 2 ∈K z j 1 ,j 2 ≤ |E[K]| -1, ∀K ⊆ K, (3.36)
The objective function is to minimize the makespan. Inequalities (3.29) ensure that the starting time for each job plus its processing time bound the makespan. Inequalities (3.30) controls each job to be processed on one machine. Inequalities (3.31) guarantee that there is no two jobs run on the same machine at the same time. Inequalities (3.32) controls the precedence constraints. Inequalities (3.33) ensure that the beginning of any job must began after the nishing of its predecessor. Inequalities (3.34) ensure that, if the job j 1 run before or at the same time with j 2 , and j 2 run before or at the same time with job j 1 then job j 1 and j 2 run at the same time. Figure 3.5 illustrate the status of two jobs job j 1 and job j 2 on two machines, when zj 1 ,j 2 =1, zj 2 ,j 1 = 0, then z j 1 ,j 2 = 0, this is represented in (a), when zj 2 ,j 1 =1, zj 1 ,j 2 = 0, then z j 2 ,j 1 = 0, here in (b) job j 2 is before job j 1 but not at the same time, in (c) job j 1 and job j 2 run on the same time, here zj 1 ,j 2 = 1, zj 2 ,j 1 = 1, then z j 1 ,j 2 = 1, in this case the tow jobs run at the same time.

m 1 m 2 j 1 j 2 (a) job j 1 before job j 2 m 1 m 2 j 1 j 2 (b) job j 2 before job j 1 m 1 m 2 j 1 j 2
(c) job j 1 , and job j 2 run simultaneously Remark that, If we consider a solution given by the vector (z, z, x) then the induced subgraph G = (V, E) where for each job j ∈ J we associate a vertex v j ∈ V and for all z j 1 ,j 2 = 1 we associate an edge v j 1 v j 2 ∈ E must be an interval graph and the clique of maximum size must be less or equal to m. We denote by I the set of all no interval induced subgraph and by K the set of all cliques of size greater or equal to m+1. In Figure 3.6b the induced sub graph for this valid schedule is interval and 3-clique free where we have three machines. We notice that this sub graph contains a clique of size three, but if it has a clique of size four, then it can not be scheduled on three machines, i.e, if we have an edge between job 1 and job 3 in Figure 3.6b then we have a clique of size 4, which is not a valid schedule on three machines.

The inequalities (3.35) ensure that all induced subgraph are interval graphs. The inequalities (3.36) ensure that all induced subgraph has no clique of size greater or equal to m + 1. The number of inequalities (3.35) and (3.36) may be exponential. In order to solve this integer linear program using a branch-and-cut approach, we needs ecient algorithms for separating the inequalities (3.35) and (3.36). Remark that, to separate the inequalities (3.35) and (3.36) we need only the value of the vector z.

In the following we will deal with (UPMSPC) problem. Will propose dierent families of valid inequalities to the ILP as we shall see later the numerical results improved the performance of the ILP. where each job j associated with a vertex v and if two jobs run at the same time or share any time unit there exist an associated edge E between these two jobs. The graph induced by each solution to be valid must have two properties : Must be (i) interval graph, and (ii) m-clique free graph.

Valid Inequalities

In this section we will give new inequalities that are valid for P .

Proposition 1 proposition Let j 1 and j 2 be two jobs in J then,

y j 1 -y j 2 ≤ p max j 2 z j 1 ,j 2 + C 3.37 (z j 2 ,j 1 -z j 1 ,j 2 ), (3.37)
is valid inequality for P , where C 3.37 = C H max -p min j 1 . proof 3.1 proof Consider the dierent cases of job j 1 and job j 2 when there is one job is before other or they run at the same time : Case 1 : If job j 1 is before job j 2 without sharing any time unit, then (z j 1 ,j 2 = zj 2 ,j 1 = 0). Thus, y j 1 ≤ y j 2 , it is always true. Case 2 : We will nd y j 1 ≤ y j 2 + C 3.37 when job j 2 is before job j 1 and they are not sharing any time unit, it is also a valid case when we have C 3.37 in the right side of the inequality. Case 3 : When job j 1 and job j 2 run at the same time we deduce y j 1 ≤ y j 2 + p max j 2 . This case is valid because when the two jobs share any time unit that means the starting time of job j 1 is less than the starting time of job j 2 plus it is maximum processing time which is the worst case. Therefore (3.37) is valid for P in all cases. C 3.37 appears when job j 2 run before job j 1 .

Proposition 2 Let j 1 and j 2 be two jobs in J then,

y j 1 -y j 2 ≤ C 3.38 zj 2 ,j 1 -p min j 1 zj 1 ,j 2 , (3.38)
is valid inequality for P where C 3.38 = C H max -p min j1 .

proof 3.2 proof Case 1 : Job j 1 is before job j 2 and they do not share any time unit. Then, zj 2 ,j 1 = 0, and zj 1 ,j 2 = 1. Thus, y j 1 ≤ y j 2p min j 1 , this case is valid because the starting of job j 1 plus the smallest processing time is less than the starting of job j 2 . Case 2 : Job j 2 is before job j 1 and they do not share any time unit. Then we deduce y j 1 ≤ y j 2 + C 3.38 , this case is also valid when we have C 3.38 in the right part of the inequality. Case 3 : Job j 1 and job j 2 run at the same time, or share any time unit, then we deduce y j 1 ≤ y j 2 + C 3.38 -p min j 1 , and it is true. Therefore (3.38) is valid for P .

We improved this inequality by adding (p min j 1 + p max j 2 -C 3.38 )z j 1 j 2 to the right side of the inequality is important to notice that, this part will not appear in case 1 and case 2 but will appear when job j 1 and job j 2 share any time unit. In case 3 when job j 1 and job j 2 run at the same time then we deduce that y j 1 ≤ y j 2 + p max j 2 as we can see in Figure 3.38(3-a and 3-b) this inequality can be valid. Thus, we will get the following inequality : Corollary 1 corollary Let j 1 and j 2 be two jobs in J then,

y j 1 -y j 2 ≤ C 3.38 zj 2 ,j 1 -p min j 1 zj 1 ,j 2 + (p min j 1 + p max j 2 -C 3.38 )z j 1 j 2 , (3.39)
This inequality is valid for P in all cases.

Remark that if we add the following valid inequality 0 ≤ p min j 1 z j 1 j 2 -p min j 1 zj 1 j 2 to (3.39) then we obtain (3.37), we deduce that inequality (3.37) is dominated by (3.39). Then it is not necessary to add the inequalities (3.37) in the model. Proposition 3 Let j 1 and j 2 be two jobs in J then,

y j 2 -y j 1 ≤ C 3.40 zj 1 ,j 2 - i∈M p ij 2 x i j 2 + p max j 2 z j 1 ,j 2 , (3.40)
is valid inequality for P where C 3.40 = C H max .

proof 3.3 proof Case 1 : If job j 1 is before job j 2 and they do not share any time unit, then y j 2 ≤ y j 1 -i∈M p ij 2 x i j 2 + C 3.40 , which is valid. Case 2 : If job j 2 is before job j 1 and they do not share any time unit, then y j 2 ≤ y j 1 -i∈M p ij 2 x i j 2 , which is also valid when job j 1 starts after job j 2 . Case 3 : When job j 1 and job j 2 run at the same time we deduce Corollary 2 Let j 1 and j 2 be two jobs in J then,

y j 2 ≤ y j 1 -i∈M p ij 2 x i j 2 + p max j 1 + C 3.
y j 2 -y j 1 ≤ C 3.40 zj 1 ,j 2 - i∈M p ij 2 x i j 2 +(p max j 1 + p max j 2 -C 3.40 )z j 1 ,j 2 , (3.41)
The coecient of z j 1 j 2 in (3.41) will not appear in case 1 and case 2 in (3.40). In case (3-a) when job j 1 and job j 2 share any time unit and job j 1 starts before job j 2 we obtain y j 2 ≤ y j 1 + p max j 2 , this inequality is valid where job j 2 starts before the completion of the processing time for job j 1 . In case (3-b) it is clear y j 2 ≤ y j 1 + p max j 2 is valid where job j 2 begin before job j 1 . Thus, it will improve the inequality when we reduce the right side of the inequality.

There is no linear combination between inequalities (3.39) and (3.41), because when we subtract inequality (3.41) from inequality(3.39), we nd inequality (3.42) which is invalid when job j 1 run before job j 2 and do not share any time unit

0 ≤ C zj 2 ,j 1 + i∈M p i x i j 2 + p min j 1 z j 1 ,j 2 -p max j 1 z j 1 ,j 2 -C 3.41 zj 1 ,j 2 -p min j 1 z j 1 ,j 2 , (3.42)
and when we subtract inequality (3.39) from inequality(3.41), we nd inequality (3.43) which is invalid when job j 2 run before job j 1 and do not share any time unit

0 ≤ (z j 1 ,j 2 -zj 2 ,j 1 )C - i∈M p i x i j 2 + p max j 1 z j 1 ,j 2 -p min j 1 z j 1 ,j 2 + p min j 1 zj 1 ,j 2 , (3.43)
Thus, its not possible to replace one inequality by another.

In the next section we will present another family of inequalities, these inequalities consider that, jobs are indexed in the non-decreasing order of their processing times. The principle of this inequality presented in [START_REF] Kacem | Lower bounds for tardiness minimization on a single machine with family setup times[END_REF]. This family of inequalities based on Shortest Processing Time (SPT). We will dene some notations to adapt the inequality to our problem : Let J ⊆ J. J j denotes jobs in the SPT order of J before j. SP T (J ) denotes the sum of the completion time when the jobs indexed in the non-decreasing order of their processing time in J . pos j denotes the position of job j in the SPT sequence of J . q ij = (|J | -pos j + 1)p ij + j1∈J j p ij 1 which denotes the sum of the processing time for job j plus the processing time for the next jobs in the SP T (J ) for all J ⊆ J, Proposition 4

j∈J y j + j∈J p ij x i j + j∈J i1∈M {i} q ij x i1 j ≥ SP T (J ), (3.44)
is valid inequality for P , The idea of the proof is as the following. If we have the schedule which is illustrated in Figure 3.7 and this schedule on the same machine, having p a ≤ p b ≤ p c . Then the SP T ≥ 3p a + 2p b + p c . Thus the SP T (J ) is bounding the schedule. Consider the case where job b is runs on another machine, then the SP T (J ) ≥ 2p a + p c , and still bounding the schedule. Thus, in this case we must remove the value of q ij from the SP T (J ). Thus, for all j ∈ J , if we remove job j from this machine then SP T (J ) become : SP T (J ) -q ij . Remark that, if we remove more than one job(i.e.) two jobs (job j 1 and job j 2 ), then the value of SPT will be :

a b c C a C b C c
SP T (J {j 1 , j 2 }) ≥ SP T (J ) -qij 1 -qij 2 .

Separation Algorithm for SPT Inequality

In this section we give the idea of the heuristic used to separate inequality (3.44). Given a fractional solution (x, y * , z * , z * ), the separation problem for inequalities (3.44) consists in determining whether (x, y * , z * , z * ) satises inequalities (3.44). We run this algorithm for each machine. For all machine i ∈ M we sort the jobs according to the SP T order for y * , for each job j in the order if xi j ≥ 0.99 we take this job, and continue until the SP T inequality is violated. The performance of the valid inequalities is evaluated in the experimental results section. In the following we will propose an updated formulation invented based on Interval graph formulation.

Reformulation of Interval Graph Formulation

In the following we will present another version of Interval Graph formulation, in this formulation we made some changes on the variable zj 1 j 2 , by considering the case if one job processed before the other job by using the variable zj 1 j 2 it is more nature for the precedence constraints, and this change enhanced the previous model by reducing the number of variables. We use the same variables in P with this change

zj 1 ,j 2 = 1 if job j 1 processed before job j 2 0 otherwise ∀j 1 , j 2 ∈ J.
The model can be described as follow :

min C max y j + i x i j p ij ≤ C max , ∀j ∈ J, (3.45)
i∈M x i j = 1, ∀j ∈ J (3.46) x i j 1 + x i j 2 ≤ 2 -z j 1 j 2 , ∀j 1 , j 2 ∈ J, i ∈ M, (3.47)
y j 1 + i∈M p ij 1 x i j 1 ≤ y j 2 , ∀(j 1 , j 2 ) ∈ A, (3.48)
y j 1 -y j 2 + i∈M p ij 1 x i j 1 ≤ C(1 -zj 1 j 2 ), ∀j 1 , j 2 ∈ J (3.49) zj 1 j 2 + zj 2 j 1 + z j 1 j 2 = 1, ∀j 1 , j 2 ∈ J, (3.50)
y j 2 ≤ y j 1 + i∈M p ij 1 x i j 1 + (C -p min j 1 )z j 1 j 2 ∀j 1 , j 2 ∈ J, (3.51)
(j 1 ,j 2 )∈E( Ī) zj 1 ,j 2 - (j 1 ,j 2 )∈E( Ī) zj 1 ,j 2 ≤ |E( Ī)| -1, ∀I ⊆ I, (3.52)
(j 1 ,j 2 )∈E(K) zj 1 ,j 2 - (j 1 ,j 2 )∈E(K) zj 1 ,j 2 ≤ |E(K)| -1, ∀K ⊆ K (3.53)
The objective function is to minimize the makespan. Inequalities (3.45) ensure that the beginning time for each job plus its processing time is less than or equal to the total completion time. Inequalities (3.46) controls each job to be processed on one machine. Inequalities (3.47) guarantee that there is no two jobs run on the same machine at the same time. Inequalities (3.48) controls the precedence constraints. Inequalities (3.49) ensure that the beginning of any job must began after the nishing of its predecessor. Inequalities (3.50) ensure that, if the job j 1 run before job j 2 , and j 2 run before job j 1 then job j 1 and j 2 run at the same time, this inequality made the major modication. Inequalities (3.51) ensure that the beginning of any job must began after the nishing of its predecessor.

Experimental Results

The mathematical formulations tested and compared under the following proposed benchmark of instances. The processing times are uniformly, distributed between 1 and 100 as it is common in the literature [START_REF] Hall | Generating Experimental Data for Computational Testing with Machine Scheduling Applications[END_REF]. We generated ve dierent sets of three subsets of DAG where the graph density is high, medium and low respectively, with the following combinations of number of jobs n = {10, 12, 14, 16, 18, 20, 25} and 2 machines . The speed of machines generated randomly between 10 and 20. In total 5 × 7 × 3 instances are generated. Regarding to the graph density(GD), is calculated as follow GD = |E| |V |(|V |-1) where E is the set of edges associated with precedence constraints between jobs, and V is the set of vertices associated with jobs, we generated the instances of three density sets (low, medium and high) density with the values (0.1, 0.15 and 0.25) respectively. The Mathematical model implemented with CPLEX 12.4, on an Intel, core i5 running at 3.4 GHz, and 8 GB of RAM. The obtained results in this experiment are reported in table 3.1. Each line gives the average results obtained by solving 5 instances for each problem size. The entries in these tables are :

n : the number of jobs, ILP : the Integer Linear Program used to solve : 1=classical formulation, 2=ow formulation, 3=order formulation, 4=interval graph formulation, CP U : the total CPU time in seconds, Gap : the Gap between the lower bounds and the upper bounds (100 × U B-LB LB ), GapH : the Gap between the best solution given by the heuristic and the integer linear program (100 × Heuristique-U B U B

), o/p : the number of problems solved to optimality over the number of instances tested.

Remark that, all instances are carried out for two machines and n jobs. We remark that the classical formulation give bad results and can solved only the smallest instances. We can observe that the interval graph formulation found 62%, 28% and 22% of optimal solutions in high density, medium and low density respectively. Whereas, the optimal solutions obtained by classical formulation is 17%, 11% and 11% in high density, medium and low density respectively, and ow formulation obtained 45%, 20%, and 20% in high density, medium and low density respectively, and order formulation obtained 68%, 57%, 45% in high density, medium, and low density. The dashed results means that, the model did not success to run the integer linear program due to the number of inequalities, we xed the processing time to one hour. Also we remark the Gap between the lower bounds and the upper bounds is sometimes better for the interval graph formulation. For the high density instances the Gap is always less than 40% and is acceptable for the instances with less than 20 jobs. Furthermore the interval graph formulation improve the value given by the heuristic on 11 instances and only 6 instances for the ow formulation where the classical formulation improve the value on 4 instances, and order improved 12 instances.

The ILP with the valid inequalities is tested under the following proposed benchmark of instances. The processing times are uniformly, distributed between 1 and 100 as it is common in the literature [START_REF] Hall | Generating Experimental Data for Computational Testing with Machine Scheduling Applications[END_REF]. We generated ve dierent sets of instances where the graph density is equal to 0.15 which is calculated as follows

GD = |E| |V |(|V |-1)
where E is the set of edges associated with precedence constraints between jobs, and V is the set of vertices associated with jobs, with the following combinations of numbers of jobs n ∈ {10, 12, 14, 16, 18, 20} and the number of machines m ∈ 2, 3 . The speed of machines is generated randomly between 10 and 20. In total 5 × 6 × 2 instances are generated. CPU time required is in seconds. The ILP is implemented with CPLEX 12.4, on an Intel, core i5 running at 3.4 GHz, and 8 GB of RAM. We rst present an overview of the results of computational tests for the ILP when we add the inequalities. We limit the resolution time of each instance to 3600 seconds.

The number of obtained optimal solutions from the computational experiments are presented in Table 3.2 with the average of the CPU time required by the model when we add the inequality for the ve sets of instances for each problem. We can observe that Cplex, within the established time, was not able to obtain the optimal solution for all instances. We can see that the solver founds the optimal solution for all ve instances just for the problem of 2×10. We can notice that when we add the inequalities (3.39) the model found 53% optimal solutions, whereas, the optimal solutions obtained when we add the inequalities (3.41) is 43%, and when we add the two inequalities (3.39) and (3.41) the model found 53% optimal solutions with less CPU time. The inequalities (3.44) give 46% optimal solutions, however when we add all inequalities the model found 50% optimal solution. The results of Table 3.2 also indicate that when we add the two inequalities (3.39) and (3.41) the model needs less CPU time to nd optimal solutions. We can notice also when we increase the number of machines the model is always able to nd more optimal solutions within the time limit for all families of inequalities, with the best results obtained when we add the family of inequalities (3.39).

In Table 3.3 we can see the results for the average relative percentage gap between the lower bound and the upper bound when we add the inequalities. Indeed, Gap is computed as follows 100 × Upper bound-Lower bound Upper bound . The average relative percentage gap is no more than 31% for all problems when we add the inequalities (3.39) and (3.41). However, the dashes in Cplex column indicates that the Cplex is not able to nd a valid solution within the time limit and the limited use of the RAM. Furthermore, we remark that, when the number of tasks increases with 3 machines, the gap still reduces when we use the inequalities (3.39) and (3.41).

Other analysis can be displayed in Table 3.2. We can notice that when we add inequalities (3.39) and (3.41) together, the model gives the maximum counts of best obtained results for all problems, and its also interesting to notice the ability of inequalities (3.39) for obtaining the same number in comparing with other families of inequalities when they added individually.

Generally, we can notice the improvement of the model in terms of obtained results and CPU time occurred when we add the two families (3.39) and (3.41) together to the ILP. When we add the family of inequalities (3.39) alone to the ILP the improvement happen with the obtained optimal solutions but with more CPU time. We notice a limited improvement when we add inequalities (3.41) alone to the ILP . The family of inequalities (3.44) (the separation algorithm) may need more improvements to obtain better results. We can say there is no remarkable improvements when we add all families of inequalities to the model.

Conclusion

In this chapter we considered the problem of unrelated parallel machine scheduling, minimizing makespan subject to precedence constraints. The main dierence between these formulations is the way the makespan has been linearized. To study and evaluate the eectiveness and eciency of these models, 105 instances of numerical experiments are conducted. The obtained results show the eectiveness of the interval graph formulation in comparing with the available formulations except the order formulation, but the facial structure of the polytope generated by interval graph model can be investigated to dene some facet dening inequalities, where there is an important piece of information from our model where the model could know if the jobs run at the same time or not. There are some applications require such model, specially in some cloud computing security models. We improved the interval graph formulation by adding valid inequalities based on the forbidden interval sub graph, and some Heuristics to solve the clique problem or nd the smallest no interval subgraphs. Computational results show that, the addition of these inequalities decreases the computational requirements to obtain the optimal solution, in many cases. Furthermore, we proposed other inequalities based on SPT. Some heuristics used to separate the inequality based on the SPT. In the next chapter we will dene the polytope associated with the interval model.

In this chapter we consider the problem of interval and m-clique free subgraphs and we show the relation between the graph problem and the unrelated parallel machines with disjunctives constraints (UPMSDC) problem. We study the facial structure of their polytope and we present some inequalities dening facets to bound the associated integer linear programming formulation. Moreover, we present exact and heuristic separation algorithms associated with a cutting-plane algorithm for solving the problem. Finally, we present some experimental results as well as their analysis.

Introduction

Interval, m-clique graphs have attracted the interest of researchers for many decades. The scope of current research in this area extends now to the mathematical and algorithmic properties of interval and m-clique graphs, their generalizations and the related graph parameters. One main reason for this increasing interest is that many real-world applications involve solving problems on graphs, which are either interval graphs themselves or are related to interval graphs or a clique in a natural way. Algorithmic aspects of interval graphs have been the subject of ongoing research for several decades, stimulated by their numerous applications ; see e.g. [START_REF] Golumbic | Algorithmic graph theory and perfect graphs[END_REF]. In some applications, interval representations with special properties are required. Numerous applications of interval graphs have appeared in the literature including applications to genetic structure, sequential storage and scheduling (see [START_REF] Golumbic | Algorithmic graph theory and perfect graphs[END_REF][START_REF] Gacias | Parallel machine scheduling with precedence constraints and setup times[END_REF]). An application of the interval graphs arises on the context of scheduling jobs in cloud computing. In cloud computing, we not only have to determine how many, but also which jobs should be allocated to a virtual machine. In scheduling, for example, jobs can have certain durations that should be refected by the lengths of their intervals and two consecutive jobs can require a certain handover period that is determined by how much their intervals should intersect.

All graphs in this chapter are simple and have no self-loops. Let G = (V, E) be a graph. An undirected graph G is called an interval graph if its vertices can be put into a one-to-one correspondence with a set of intervals I of a linearly ordered set (like the real line) such that two vertices are connected by an edge of G if their corresponding intervals have nonempty intersection. An interval graph is the graph showing intersecting intervals on a line. Thus, we associate a set of intervals I = {I 1 , ..., I n } on a line with the interval graph G = (V, E), where V = {1, ..., n} and two vertices, x and y, are linked by an edge if and only if I x ∩ I y = ∅. .

In parallel machines scheduling some jobs in dierent machines can share any time units, the jobs can be represented with multiple nodes and edges indicate there is a shared time units between jobs. Normally, the solution is mathematically formalized as a graph G = (V, E) where V denotes the set of vertices (associated with jobs) and E denotes the set of relationships between vertices (intersections of jobs). However, when we assign jobs to parallel machines, the solution is valid for two types of graphs (i.e., interval graph and m-clique free, where m is the number of machines). This point will be discussed in Section 4.4.

Clique is a very common structure in many applications, which is composed of a subset of vertices as well as all the possible relationships among them. Therefore, clique detection is playing an important role in various applications, such as social recommendation [START_REF] Mokoto | A cutting plane algorithm for the unrelated parallel machine scheduling problem[END_REF] and network routing . The m-clique free graph is the graph that does not contain a clique of size greater than m + 1.

Denition 8 (clique)

. Let G = (V, E) be an undirected graph. A clique in G is a subset S ⊂ V such that for any two vertices v i , v j ∈ S there exists an edge

(v i , v j ) ∈ E.
Denition 9 (m-clique). Let G = (V, E) be an undirected graph. An m-clique in G is a subset S ⊂ V and |S| = m such that for any two vertices v 1 , v 2 ∈ S there exists an edge

(v 1 , v 2 ) ∈ E.
A graph is m-clique free if it does not contain a clique of size greater or equal than m + 1. The problem under consideration is to nd an interval, and m-clique free graph.

The polytopes of interval sub-graphs

In this section, we consider the problem of characterizing an interval graph m-clique free.

Let I := {I ⊆ E |G[I] induces an interval m-clique free subgraph}. The vector z I is called the incidence vector associated with I. We dene the Interval m-Clique Free Subgraph Problem (IMCFSP) polytope as follows :

P I (G, m) := conv{z I ∈ {0, 1} |E| |I ∈ I} ,
Now, we analyze the dimension of this polytope.

Proposition 5 Polytope P I (G, m) has a full dimension. proof 4.1 We need to show the existence of |E| + 1 feasible solutions such that their incidence vectors are anely independent. Let I 0 = ∅ be a valid solution, because it has no edge. We also dene solutions I e = {e} for all e ∈ E. The incidence vectors of these solutions are clearly anely independents. Thus, we have |E|+1 vectors of P I (G, m) anely independent and the proof is completed.

In the following proposition, we will prove that the trivial inequality is a facet.

Proposition 6 Let e ∈ E. The trivial inequality z e ≥ 0 denes a facet of P I (G, m). proof 4.2 Let us denote by az ≤ α inequality -z e ≤ 0 associated with e ∈ E. Let bz ≤ β be a facet dening an equality of P I (G, m), such that {z ∈ P I (G, m) : az = α} ⊆ {z ∈ P I (G, m) : bz = β}. We show that b = ρa for some ρ ∈ R. Let I 0 = ∅ be a valid solution, and the associated incidence vector z I 0 verify -z e = 0. Let e ∈ E \ {e}. The solution I e = {e } is valid and the incidence vector z I e associated with I e veries -z e = 0. Since, az I 0 =az I e , then we deduce that bz I 0 =bz I e and this implies that b(e ) = 0 for all e ∈ E. Therefore, we set b(e) = ρ, and then b = ρa.

Forbidden subgraphs inequalities

In this section we analyze the graph properties in order to propose valid inequalities. Properties on interval graphs have been studied in [START_REF] Lekkeikerker | Representation of a nite graph by a set of intervals on the real line[END_REF]. The authors give all forbidden subgraphs. Indeed, if a graph does not contain at least one of the ve subgraphs given in Figure 4.2, then it is an interval graph. The two rst forbidden subgraphs are called Bipartite Claw and Umbrella. These subgraphs are dened on only seven nodes. The three last forbidden subgraphs are dened for dierent sizes. The n-net subgraphs are composed of n + 4 nodes {1, ..., n, a, b, c, d}, where the edges are {a -b, 1 -c, n -d} ∪ {1 -b, 2 -b, 3 -b,..., n -b} ∪ {1 -2, 2 -3,..., (n -1) -n}. The n-tent subgraphs are dened as follows : the nodes a, b, c are connected by a triangle, the nodes {1, ..., n} are connected in a line form, nodes 1 and b are connected, node n is linked to c and the nodes in {b, c, 2, ..., n -1} dene a clique. Finally, the fth forbidden conguration is a hole of more than 3 nodes, which is a cycle without chord. These ve forbidden subgraphs ensure that the graph is an interval one. In addition, to be m-clique free, all cliques of size greater or equal than m + 1 must be forbidden. (a) Bipartite Claw In the following subsection we propose some inequalities associated with all forbidden subgraphs and we prove that these inequalities dene facets for P I .

Bipartite Claw

In this subsection, we give inequalities to avoid the bipartite claw forbidden subgraph.

An example is given in Figure 4.3d.

We will give some notations to help in analyzing the bipartite claw forbidden subgraph.

Let us consider the complete graph K 7 with seven nodes. We partition this graph to BC and BC, where BC is the set of all edges that form the bipartite claw as in Figure 4.3d and BC is the set of edges in the associated complementary graph of BC. Moreover, BC is partitioned as follows :

• Subset BC 4 h contains all the edges such that each of them enables to form a hole of size 4 in a bipartite claw.

• Subset BC contains three edges such that when we add one of them to BC, then we obtain a central triangle.

• Subset BC i contains the edges that are able to form a triangle with the inner vertex.

• Subset BC 5 h is composed of all edges such that each of them enables to form a hole of size 5 in the bipartite claw. As a consequence, the previous denitions lead explicitely to the following subsets : [START_REF] Dogan | Genetic algorithm based scheduling of meta-tasks with stochastic execution times in heterogeneous computing systemst1[END_REF][START_REF] Hart | Evolutionary scheduling : A review[END_REF], [START_REF] Dogan | Genetic algorithm based scheduling of meta-tasks with stochastic execution times in heterogeneous computing systemst1[END_REF]4), [START_REF] Izakian | Metaheuristic based scheduling metatasks in distributed heterogeneous computing systems[END_REF]5), (4, 7), [START_REF] Hart | Evolutionary scheduling : A review[END_REF][START_REF] Wang | Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics[END_REF]}. BC = { (7, 1), (7, 2), (7, 3), [START_REF] Hsu | Unrelated parallelmachine scheduling with rate-modifying activities to minimize the total completion time[END_REF]5), [START_REF] Hsu | Unrelated parallelmachine scheduling with rate-modifying activities to minimize the total completion time[END_REF][START_REF] Wang | Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics[END_REF], (6, 1), (6, 2), [START_REF] Wang | Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics[END_REF]4), [START_REF] Wang | Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics[END_REF]5), (5, 1), (5, 3), (5,4), (4, 2), (4, 3), (3, 2) }. Indeed, when we add an edge from BC in Figure 4.3d, by denition, the resulting subgraph will contain a clique of size 3, which is not m-clique free in this case, as well it is 2 -net. Moreover, when we add an edge e ∈ BC h then we obtain a hole. If we add another edge to break this hole then we obtain a clique of size 3.

BC = {(1, 2),

Umbrella Inequalities

For the umbrella subgraph as shown in Figure 4.4d, let G u = (U u , E u ) be a graph that formulates the umbrella and let E u be a set of the complementary edges for G u . In the following, we will present a family of valid inequalities that delete the umbrella subgraphs. To analyze this forbidden subgraph we need the following notations : Let E i u ⊂ E u be the set of the inner three edges in the umbrella subgraph. Let E t u ⊂ E u be the set of the edges such that when we add one of these edges to the umbrella we create a new triangle. Subset E a u ⊂ E c is the dashed edges in Figure 4.6a. Finally, E a u ⊂ E u is the set of the around edges and E h u ⊂ E u is the set of edges such that if they are connected, then they will form a hole of size 4 or of size 5. Let e 3 ∈ E a u . The solution I 3 = E u \{e 3 } is valid and the incidence vectors z I 3 verify the inequality (4.4) to equality. Moreover, we have az I 1 =az I 3 . Hence, bz I 1 =bz I 3 . This implies that b(e 3 ) = -b(e 1 ). Thus, by symmetry we have b(e ) = -b(e) for all e ∈ E t u ∪E c u , e ∈ E a u .

The solutions (1, 4)} and I 8 = I 7 \ {(1, 3)} are valid. The incidence vectors z I 4 , z I 5 , z I 6 , z I 7 and z I 8 verify the inequality (4.3) to the equality. Since az I 4 =az I 5 =az I 6 =az I 7 =az I 8 , therefore bz I 4 =bz I 5 =bz I 6 =bz I 7 =bz I 8 , implying that b(e) = 0 ∀e ∈ E i u .

I 4 = E u \ {(1, 6)}, I 5 = (E u \ {(1, 6)}) ∪ E i u , I 6 = I 5 \ {(1, 5)}, I 7 = I 6 \ {
The solutions (5, 6)} and I 16 = I 15 ∪ {(3, 6)} are valid and verify the inequality (4.4) to the equality. Since az I 9 =az I 10 = az I 11 =az I 12 =az I 13 =az I 14 =az I 15 =az I 16 , therefore bz I 9 =bz I 10 = bz We set b(e) = ρ for e ∈ E u and the proof is ended.

I 9 = E u ∪ {(2, 7), (2, 4)}, I 10 = E u ∪ {(2, 5), (2, 4)}, I 11 = E u ∪ {(2, 4)}, I 12 = E u \ {(2, 3)}, I 13 = I 12 ∪ {(2, 6)}, I 14 = I 12 ∪ {(2, 5)}, I 15 = E u \ {
I 11 = bz I 12 =bz I 13 =bz I 14 = bz I 15 = bz I 16 , implying that b((2, 6)) = b((2, 5)) = b((2, 7)) = b((6, 7)) = b((3, 6)) = 0. Let e ∈ E \ (E u ∪ Ēu ). The solutions I 17 = E u \ {(4,

n-net Inequalities

The n -net forbidden subgraph is shown in Figure 4.2c. We will give some notations to help in analyzing the n -net forbidden subgraph. Let G net = (U net , E net ) be the graph that forms a net of size n (i.e., n -net) and E net be a set of complementary edges of G net . To avoid to have a subgraph that represents an n -net, where n ≥ 2 we need either to eliminate an edge from the n -net without having a hole denoted by E h net , or to add an edge that does not construct a hole denoted by E h net . To analyze this forbidden subgraph we will use the following notations. From Figure 4.2c let us consider :

-E h net = {(a, c), (a, d)} ∪ {(c, 3), (c, 4), ..., (c, n)} ∪ {(d, 1), (d, 2), ..., (d, n -2)} ∪ {(c, d)}. -E h net = {(b, 2), ..., (b, n -1)}.
We propose valid inequalities that delete the n -net forbidden subgraphs. Let e 1 , e 2 ∈ E net \ E h net be two edges, where e 1 = e 2 . We consider the edge sets

e∈Enet\E h net z e - e∈Enet\E h net z e ≤ |E net \ E h net | -1.
I 1 = E net \ {e 1 } and I 2 = E net \ {e 2 }.
Their incidence vectors z I 1 and z I 2 are solutions of P I (G, m) and satisfy the inequality (4.5) at the equality. Moreover, we have az I 1 =az I 2 and then bz I 1 =bz I 2 . This implies that b(e 1 ) = b(e 2 ). As e 1 , e 2 are arbitrary, then b(e) = b(e ) for all e, e ∈ E net \ E h net .

We consider the edge sets

I 3 = E net \ {(b, 1)} and I 4 = E net \ ({(b, 1)} ∪ E h net ).Their
incidence vectors z I 3 and z I 4 are solutions of P I (G, m) and satisfy the inequality (4.5) at the equality. Moreover, we have az I 3 =az I 4 . Hence, we have bz I 3 =bz I 4 . This implies that b(e) = 0 for all e ∈ E h net .

Let e 3 ∈ E net \ E h net . The solution I 5 = E net ∪ {e} is valid and satises the inequality (4.5) to equality. Moreover, we have az I 1 =az I 5 and then bz I 1 =bz I 5 . This implies that b(e) = -b(e ) for all e ∈ E net \ E h net and e ∈ E net \ E h net .

Considering the edge sets

I 6 = E net ∪{(c, 2), (c, 3), ..., (c, n), (c, d)}, I 7 = E net ∪{(c, 2)}, I 8 = E net ∪ {(d, 1), (d, 2), ..., (d, n -1)}, I 9 = E net ∪ {(d, n -1)},I 10 = E net ∪ {(a, 1)}, I 11 = E net ∪ {(a, 1), (a, c)},I 12 = E net ∪ {(a, n)}, I 13 = E net ∪ {(a, n), (a, d)}.
These edge sets are solutions and satisfy the inequality We set b(e) = ρ for e ∈ E net \ E h net and the proof is completed.

n-tent Inequalities Figure 4.2d shows the n -tent forbidden subgraph, the graph is non-interval if it contains an n -tent forbidden subgraph G tent . The induced subgraph G tent to be valid we need to add or remove one or more edges considering to not have a hole when we add or remove any edge. Let the graph G tent = (U tent , E tent ) be a graph that formulate n -tent for all n ≥ 3, and E tent be the set of complementary edges. From Figure 4.2c

-E h tent = {(b, c), (c, 4), (b, 2)}, -E h tent = {(1, 4), (2, 5), ..., (n, n + 3)}.
Remark that, all n-tent where n ≥ 5 contain a clique of size 5 then the clique inequality cut these n-tent sub graph if m ≤ 4. It is the same idea for all n-tent where n = 4 (resp. n = 3) then the clique inequality cut these n-tent sub graph if m = 3(resp. m = 2).

In the following we will propose valid inequalities that delete the n-tent forbidden subgraphs. Let e 1 , e 2 ∈ E tent \ E h tent be two edges, where e 1 = e 2 . We consider the edge sets I 1 = E tent \ {e 1 } and I 2 = E tent \ {e 2 }. Their incidence vectors z I 1 and z I 2 are solutions of P I (G, m) and satisfy the inequality (4.6) to equality. Moreover, we have az I 1 =az I 2 and then bz I 1 =bz I 2 . This implies that b(e 1 ) = b(e 2 ). As e 1 , e 2 are arbitrary, then b(e) = b(e ) for all e, e ∈ E tent \ E h tent .

We consider the edge sets I 3 = E tent \{(a, c)}, and I 4 = E tent \({(a, c)}∪{(b, c)}) there incidence vectors z I 3 , and z I 4 are solutions of P I (G, m) and satisfy the inequality (4.6) to equality. Moreover, we have az I 3 =az I 4 and then bz I 3 =bz I 4 . This implies by symmetry that

b((b, c)) = b((b, 2)) = b((c, 4)) = 0. Let e 3 ∈ E tent \ E h tent .
The solution I 5 = E tent ∪ {e} is valid and satises the inequality (4.6) to equality. Moreover, we have az I 1 =az I 5 . Hence, bz I 1 =bz I 5 . This implies that b(e) = -b(e ) for all e ∈ E tent \ E h tent and e ∈ E tent \ E h tent .

Let (i, i + 3) ∈ E h tent .
The solutions I 6 = E tent ∪ {(i, i + 3), (i, i + 2)} and I 7 = E tent ∪ {(i, i + 2)} are valid and satisfy the inequality (4.6) to equality. Moreover, we have az I 6 =az I 7 and then bz I 6 =bz I 7 . Thus, b(e) = 0 for all e ∈ E h tent .

Let e ∈ E \ (E tent ∪ E tent ). By considering the valid solutions I 8 = E tent \ {(a, c)} and I 9 = E tent \{(a, c)}∪{e}, we have az I 8 =az I 9 and then bz I 8 =bz I 9 . This implies that b(e) = 0.

We set b(e) = ρ for e ∈ E tent \ E h tent and the proof is completed.

Hole inequalities

Here, it is convenient to dene a hole as an induced subgraph of G isomorphic to C k for some k ≥ 4, [START_REF] Schrijver | Combinatorial Optimization : Polyhedra and Eciency[END_REF]. The hole C is a forbidden subgraph as depicted in Figure 4.2e. Let C denote the set of edges that construct the hole, i.e., C = { (u 1 , u 2 ),(u 2 , u 3 ),...,(u |C|-1 , u |C| ),(u |C| , u 1 )

}. If (i + k) > |C|, then u i+k = u i , i = (i + k) -|C|. Let C denote the set of all chords of hole C.
Suppose we have a hole of size 4 this graph is non-interval graph. The induced subgraph by a hole is valid only if we add to it at least one chord.

Proposition 13 For a hole C, the minimum number of necessary chords that should be added to the hole to be an interval graph is |C| -3, when |C| ≥ 4. proof 4.9 We prove this proposition by induction. When |C| = 4, then we need one chord k c = 1, and then the proposition is true. Let assume that the property is true until |C| = l and k c = l -3. We need to prove it for a cycle C where |C | = |C| + 1 and that k c = |C | -3. Let consider C = {u 1 , u 2 , u 3 , ..., u |C| } be the hole graph given by C where we add k c edges in order to make it hole free and Let e 1 and e 2 be two distinct edges of hole C. The solutions I 1 = C {e 1 } and I 2 = C {e 2 } are interval and m-clique graphs. We deduce that I 1 , I 2 are solutions. Moreover, we have az I 1 = az I 2 . Hence, bz I 1 = bz I 2 . This implies that b(e 1 ) = b(e 2 ). Set b(e) = (|C| -3)ρ. As e 1 , e 2 are arbitrary then b(e) = b(e ) ∀e, e ∈ C. We deduce b(e) = (|C| -3)ρ for all e ∈ C. Let u i ∈ V (C). The solution I 3 = C ∪ (δ(u) ∩ C), illustrated in Figure 4.5a, and the solution 4.5b, are valid and verify the inequality (4.8) to equality. Moreover, we have az I 3 =az I 4 and then bz

I 4 = (I 3 \ {(u i , u i+2 )}) ∪ (u i+1 , u i+3 ), illustrated in Figure
I 3 =bz I 4 . This implies that b(u i , u i+2 ) = b(u i+1 , u i+3 ). Thus, by symmetry b((u i , u i+2 )) = b((u i+1 , u i+3 ))
are arbitrary for all ∀i ∈ {1, 2, ..., |C|}. 4.5c, is valid and veries the inequality (4.8) to equality. Therefore, az I 5 =az I 3 . Hence bz I 5 =bz I 3 . This implies that b(u i , u i+j ) = b(u i+j-1 , u i+j+1 ). As these edges are arbitrary then b(e) = b(e ) for all e ∈ C. Now, we will consider the two solutions I 1 and I 3 . These solutions are valid and verify the inequalities (4.8) to equality. Hence, az I 1 =az I 3 and therefore bz I 1 =bz I 3 . This implying that b(e 1 ) =e ∈δ(u i )\C b(e ). As e 1 , and u i are arbitrary for all e ∈ C and u i ∈ V (C), then b(e 1 ) = -(|C| -3)b(e). We deduce that b(e) = -ρ ∀e ∈ C.

The solution

I 5 = (I 3 \ (u i , u i+j )) ∪ (u i+j-1 , u i+j+1 )), illustrated in Figure
Let e 3 ∈ E \(C ∪C). The solutions I 7 = I 3 ∪{e 3 } and I 3 are valid and verify the inequalities (4.8) to equality. Hence, az I 7 =az I 3 and then bz I 7 =bz I 3 . This implies that b(e 3 ) = 0. As b(e 3 ) is arbitrary, then b(e) = 0 for all e ∈ E \ (C ∪ C).

Clique inequalities

In this section we will study the clique subgraph and we will propose valid inequalities and facets.

Proposition 15 Let K be a clique and let V (K) be its set of vertices. If m = 2 the inequality

e∈E(K) z e ≤ |V (K)| -1. (4.9)
is valid and denes a facet of P I (G, m). proof 4.11 Remark that if m = 2, then a solution can be given only by a forest in the subgraph G(K). We deduce that the maximum number of edges in this subgraph is equal to

|V (K)| -1.
Let us denote by az ≤ α the inequality (4.9) associated with e. Let bz ≤ β be a facet dening an equality (4.9) such that {z ∈ P I (G, m) : az = α} ⊆ {z ∈ P I (G, m) : bz = β}. We show that b = ρa for some ρ ∈ R.

Let (u, v), (u, w) ∈ E(K), be two connected edges. Considering a line T uv beginning by (u, v) and nishing by the vertex w and the line T uw = T uv \ {(u, v)} ∪ {(u, w)}. These two solutions are valid and satisfy the inequality (4.9) to equality. Moreover, we have az Tuv =az Tuw . Hence, bz Tuv =bz Tuw . This implies that b((u, v)) = b((u, w)). By symmetry, we deduce then that b(e) = b(e ) for all e, e ∈ E(K).

Let e ∈ E \ E(K). By considering the valid solution T uv = T uv ∪ {e}, we have az Tuv =az T uv . Hence, bz Tuv =bz T uv . This implies that b(e) = 0. Let e, e be two edges in E(K). The solution I 1 = E(K) \ {e} and I 2 = E(K) \ {e } are valid and verify the inequality (4.10) to equality. Hence, az I 1 =az I 2 . Therefore, bz I 1 =bz I 2 . This implies that b(e) = b(e ). We set b(e) = ρ. As b(e) and b(e ) are arbitrary, then b(e) = b(e ) for all e, e ∈ E(K).

Let e 1 be an edge in E \ E(K). The solution I 3 = I 1 ∪ {e 1 } and I 1 are valid and verify the inequality (4.10) to equality. Hence, az I 1 =az I 3 . Therefore bz I 1 =bz I 3 . This implies that b(e 1 ) = 0. As b(e 1 ) is arbitrary we deduce that b(e) = 0, ∀e ∈ E \ E(K).

Let f (K, m) be a function giving the minimum number of edges necessary to be removed from E(K) such that the resulting graph

G (K) is m-clique free. Let α = |V (K)| m , n α-1 = mα -|V (K)| and n α = |V (K)|-(n α-1 )(α-1) α Proposition 17 f (K, m) = n α-1 (α-1)(α-2) 2 + n α (α)(α-1) 2
proof 4.13 Let E be a set of f (K, m) edges such that E(K)\E is m-clique free. Remark that in the complementary graph G(K) we have a stable set of size |K|. If we add E , then there does not exist a stable of size m + 1 (m-stable free). Let consider a minimum set of edges

E ∈ E(K) such that |E | < |E | and G(K)\E is m-clique free and thus G(K)∪E is m-stable free. Clearly E is a set of m disjoint cliques K = {K 1 , ..., K m }, otherwise E
is not minimal or contain a stable set of size m + 1. To have the minimum set of edges, it is important to balance the size of cliques. Indeed, if we have two cliques K i and K j where

|K i | ≥ |K j | + 2, then for u ∈ K i we obtain the following result |E(K i )| + |E(K j )| > |E(K i \ {u})| + |E(K j ∪ {u})|.
We deduce that the maximum dierence between two cliques of K is less or equal to 1.

Proposition 18 Let K be a clique. The inequality

e∈E(K) z e ≤ |E(K)| -f (K, m) (4.11)
is valid.

proof 4.14 By denition f (K, m) is the minimum number of edges necessary to be removed from E(K) such that the resulting graph G (K) is m-clique free. Thus, the inequality (4.11) is valid.

In the next subsection, we will improve this family of inequalities.

Clique-Hole inequalities

Remark that if we remove m disjoint cliques in G(K), then we obtain a complete bipartite subgraph between all pairs of two cliques. Let

H ij = (K i , K j , E ij ) be a complete bipartite graph. Remark that H contains a hole if |K i | ≥ 2 and |K j | ≥ 2.
To remove every hole in H ij , the minimum number of edges E necessary to be removed to obtain a hole free graph is equal to max(|K i |, |K j |)-1, otherwise we can always take 2 nodes in K i or K j such that these two nodes are not covered by E . Note that E , with size max(|K i |, |K j |) -1, covers the maximum nodes of K i and K j . We can strength the inequality (4.11) by the following inequality. Let

β = i∈m (max{|K i | -1, 0}) -max i∈m |K i | -1.
Proposition 19 Let K be a clique. The inequality

e∈E(K) z e ≤ |E(K)| -(f (K, m) + β) (4.12)
is valid and denes a facet. proof 4.15 Remark that if we unbalance two cliques K i and K j to reduce the value max(|K i |, |K j |) -1 of 1, then the number of edges necessary to be removed increases by

max(|K i |, |K j |) -min(|K i |, |K j |).
Let us denote by az ≤ α the inequality (4.12) associated with e. Let bz ≤ β be a facet dening an equality (4.12) such that {z ∈ P I (G, m) : az = α} ⊆ {z ∈ P I (G, m) : bz = β}. We show that b = ρa for some ρ ∈ R.

Let (u, v), (u, w) ∈ E(K) be two connected edges. Let consider a set of stable set where u is in the stable set i and v, w in the stable set j. We can easily nd a solution where (u, v) is an edge and (u, w) is not an edge. These two solutions are valid and satisfy the inequality (4.12) to equality. This implies by symmetry that b((u, v)) = b((u, w)). We deduce then that b(e) = b(e ) for all e, e ∈ E(K).

Let e ∈ E \ E(K). By considering a valid solution where e is not an edge and a second solution with the same edges plus e, we can deduce that b(e) = 0.

Cutting plane algorithms

Cutting plane method allows us to strengthen the linear relaxation by adding inequalities. Cutting plane algorithms mainly consist in generating constraints by means of a separation procedure (see, for example, [START_REF] Jiinger | Practical problem solving with cutting plane algorithms in combinatorial optimization[END_REF], [START_REF] Aardal | Polyhedral techniques in combinatorial optimization II : Applications and computations[END_REF], [START_REF] Vallada | Scheduling unrelated parallel machines with sequence dependent setup times and weighted earliness tardiness minimization[END_REF], [START_REF] Schrijver | Combinatorial Optimization : Polyhedra and Eciency[END_REF] and [START_REF] João Paulo De | Hybrid GRASP Heuristics to Solve an Unrelated Parallel Machine Scheduling Problem with Earliness and Tardiness Penalties[END_REF]). Let z * be the incidence vector associated with the value of the variable z in the linear relaxation. The separation problem consists in nding if there exists a valid inequality az ≤ b 0 that cuts o the solution z * ,i.e., az * > b 0 . The separation algorithm associated with a family of inequalities

a E x ≤ b E for all E ∈ E consists in nding a set E ∈ E such that a E z * > b E .
The results of the previous sections have allowed us to derive some exact separation algorithms and some heuristics separation algorithms. Furthermore, at the end of this section we propose "lazy separation procedure" to ensure that the integer solutions are interval and m-clique free subgraph. In the next paragraphs, we will describe these separation algorithms for all inequalities described in the previous section. In this section we describe the BC separation algorithms. We propose three algorithms to separate the bipartite claw inequalities. One is an exact algorithm and two others are heuristic procedures. We consider only m ≥ 3 (note that it is easy to adapt the algorithm for m = 2.).

Let the vector z * ∈ R |E| be a solution of a linear relaxation. We dene a weight for each edge of the complete graph G as follows : w(e) = z * e for all e ∈ E. The separation algorithm consists in nding one bipartite claw BC such that the associated inequality is violated by z * and then we will add this inequality to the separation linear relaxation. This corresponds to nd a bipartite claw BC ⊆ E such that : e∈BC 2z * e -e∈BC 4h ∪BC z * e -2 e∈BC i z * e > 10.

From Figure 4.3d, the subsets are the following : [START_REF] Dogan | Genetic algorithm based scheduling of meta-tasks with stochastic execution times in heterogeneous computing systemst1[END_REF][START_REF] Hart | Evolutionary scheduling : A review[END_REF], [START_REF] Dogan | Genetic algorithm based scheduling of meta-tasks with stochastic execution times in heterogeneous computing systemst1[END_REF]4), [START_REF] Izakian | Metaheuristic based scheduling metatasks in distributed heterogeneous computing systems[END_REF]5), (4,[START_REF] Hsu | Unrelated parallelmachine scheduling with rate-modifying activities to minimize the total completion time[END_REF], [START_REF] Hart | Evolutionary scheduling : A review[END_REF][START_REF] Wang | Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics[END_REF]}. [START_REF] Izakian | Metaheuristic based scheduling metatasks in distributed heterogeneous computing systems[END_REF][START_REF] Wang | Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics[END_REF], (5,4), [START_REF] Izakian | Metaheuristic based scheduling metatasks in distributed heterogeneous computing systems[END_REF][START_REF] Hsu | Unrelated parallelmachine scheduling with rate-modifying activities to minimize the total completion time[END_REF], [START_REF] Hart | Evolutionary scheduling : A review[END_REF][START_REF] Hsu | Unrelated parallelmachine scheduling with rate-modifying activities to minimize the total completion time[END_REF], (4,[START_REF] Wang | Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics[END_REF]}. BC = {(2, 3), [START_REF] Izakian | Metaheuristic based scheduling metatasks in distributed heterogeneous computing systems[END_REF]4), [START_REF] Hart | Evolutionary scheduling : A review[END_REF]4)}. [START_REF] Dogan | Genetic algorithm based scheduling of meta-tasks with stochastic execution times in heterogeneous computing systemst1[END_REF][START_REF] Wang | Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics[END_REF], (1, 7)}.

BC = {(1, 2),
BC 4 h = {(3, 5),
BC i = {(1, 5),
Proposition 20 A partial bipartite claw BC not violated, implies that each bipartite claw BC including a partial bipartite claw is not violated.

Remark that, from Figure 4.7a if we select the 3 rst vertices 1, 2 and 3 such that (2z * In the same way, if we add the vertex 4 and the value of (2z *

1,4 + 2z * 1,2 + 2z * 1,3 -z * 2,4 -z * 2,3 -z * 3,4
) is less than 4, then there does not exist a violated bipartite claw within these 4 vertices in this position. In the best case we obtain a left side value that is

6 + 2z * 1,4 + 2z * 1,2 + 2z * 1,3 -z * 2,4 -z * 2,3 -z *
3,4 . Thus, the left hand side is less than 10 and the value of e∈BC\{(1,2), [START_REF] Dogan | Genetic algorithm based scheduling of meta-tasks with stochastic execution times in heterogeneous computing systemst1[END_REF][START_REF] Hart | Evolutionary scheduling : A review[END_REF],(1,4)} 2z * e = 6. With the same argument we test the weight of all partial subgraphs to drop non interesting bipartite claws. This process is used for the exact and the rst heuristic algorithms.

Exact Separation (ExBC-Sep)

Now, we will explain the exact separation algorithm. The exact algorithm consists in testing all the possible 7 vertices in this order (1,2,3,...,7). We select the nodes such that the values of the weighted edges in the incidence graph is maximized as follows : two times the weight of BC, minus the value of edges in BC h even if in reality with the improvement presented before the running is better controlled.

Heuristic1 : Separation (H1BC-Sep)

In this heuristic we start by searching the vertices 1, 2, 3, and 4 that maximize 2w(1, 2)+ 2w(1, 3) + 2w(1, 4) -w(2, 4) -w(2, 3) -w(3, 4) from Figure 4.7a based on the results of Bipartite Claw in Section 4.2.1. If the value of (2z *

1,2 + 2z * 1,3 + 2z * 1,4 -z * 2,4 -z * 2,3 -z * 3,4
) is greater than 4, then it is possible to nd a violated BC inequality with this set of vertices. After, using the greedy approach, we search to add the best weighted vertex 5 according to the incident weighted edge, if the partial BC is violated, then we will search for the best vertex 6 and with the same idea we will add vertex 7. If the BC induced by these vertices is violated by z * , then we will add the inequality to the relaxation. Using this greedy approach the heuristic running time is O(n 4 ).

Heuristic 2 : Separation (H2BC-Sep)

This heuristic follows a greedy approach to nd a violated BC inequality. We search at each step the best next vertex to add in BC. The idea is to nd the 'best weighted' edge in the graph. This edge is considered as z 1,2 , if the weight of the edge z * 1,2 > 0. The heuristic tries to nd with the greedy approach given in heuristic.1 the next best ordering of vertices 3, 4, ..., 7. This heuristic has O(n 2 ) running time.

Umbrella separation

In this subsection we present the three algorithms for separating the umbrella forbidden subgraph. We propose an exact separation algorithm and two heuristics based on a greedy approach. Recall the inequality e∈E a u z e -e∈E t u ∪E c u z e ≤ 6 where vector z * ∈ R |E| . The separation algorithm consists in nding an umbrella, such that the associated inequality is violated by z * . If the associated inequality violated by z * , then we add this inequality to the linear relaxation. Thus, we search an umbrella, which is subset of

E such that e∈E a u z * e -e∈E t u ∪E c u z * e > 6
where m ≥ 4. Then, it is possible to adapt the algorithm for m = 2 and m = 3.

Exact separation algorithm

The exact separation algorithm starts by nding rst edges z 1,2 and z 2,3 . If z * 1,2 + z * 2,3 < 1, then the algorithm cannot nd an umbrella within these two edges in this position. In the next step, the algorithm searches the best vertex 4, that satises z * 1,2 +z * 2,3 +z 3,4 -z 2,4 ≥ 2, and then the algorithm adds vertex 5, then vertex 6 and nally it will add vertex 7.

H1U-Sep separation

In this heuristic we start by searching the vertices 1, 2, 3, and 4 that maximize (z 1,2 + z 2,3 + z 3,4 -z 2,4 ) in Figure4.6 the coecient of each edge is illustrated, and Figure 4.7b shows these basic edges. If this value is greater than 4, then we search 6, and then 7. If the Umbrella induced by these vertices is violated by z * we will add this inequality. Using the greedy approach the heuristic running time is in O(n 4 ).

H2U-Sep Separation

This heuristic follow greedy approach to nd a violated umbrella inequality we search at each step the best next edge to add in umbrella. The heuristic starts by the best weighted edge z 1,2 , then with the greedy approach search the best next vertex 3 to add to the umbrella, by following this order the best weighted vertex 3, then the best weighted In this subsection we describe the n-net separation algorithms. Let the vector z * ∈ R |E| be a solution of the linear relaxation. The weighted vector is dened in the previous sections. The separation algorithm consists in nding one n-net where n ≥ 2, such that the associated inequality is violated by z * . Then, we add this inequality to the separation linear program. This corresponds to nd an n-net ⊆ E such that : Now, we give the n-net separation algorithm. Recall the inequalities (4.5). Let the vector z * ∈ R |E| be the solution of linear relaxation with the dened weighted graph G in the previous sections. The separation algorithm consists in nding one n-net such that the associated inequality is violated by z * in order to add it to the linear relaxation. Therefore, we search an n-net such that :

e∈Enet\E h net z * e -e∈Enet\E h net z * e > |E net \ E h net | -1.
Let us consider Figure 4.8a. We search the edge (a, a 1 ) with the maximum weight w((a, a 1 )). Then, we search the best vertex b 1 such that w((a Remark that we remove the edge (a 1 , c 1 ) (see. Figure 4.8c) if n + 1 net is violated, then we add the n-net inequality (if n ≥ 2) and we stop the algorithm. The proposed heuristic running time is O(n 2 ).

n-tent separation

For the n-tent separation algorithm we propose the following algorithm, which is based on a greedy approach. The vector z * ∈ R |E| . The n-tent separation algorithm consists in nding an n-tent, such that the associated inequality is violated by z * . If the associated inequality is violated by z * , then we add this inequality to the linear program. Thus, we search an n-tent where

n ≥ 3, n-tent⊆ E such that e∈Etent\E h tent z e -e∈Etent\E h tent z e ≤ |E tent \ E h tent | -1.
We search for the best z a,b , and z a,c in the rst step (see 4.9a). In the next step, we search the best nodes 1, 2, 3 one by one using a greedy approach to maximize the sum of n-tent edges, by considering the weight of the edges from n-tent and its complementary. If 2-tent is not found, that means 3-tent does not exist. If 3-tent is found, then we try to add the best node 4, which is connected with node c and connecting c to a 1 and remove (a 1 , c) to have the structure of 4-tent. The heuristic continues for searching for n + 1-net at each step. If the heuristic failed to nd n + 1-net, then the violated n-net inequality associated with the found n-net will be added. The proposed heuristic running time is (c,d)) + w((a, d)) is maximum (see Figure 4.11). In each step we consider the clique where we connect a vertex with all other vertices in the clique. If we nd a clique where the associated inequalities is violated, then the inequality will be added.

If e∈E(K) z e ≤ |E(K)| -f (K, m), then we stop the algorithm, since we cannot nd a clique where associated inequality is violated, and we add the inequality of clique of size n -1.

4.3.5

Lazy constraint approach

In this subsection, we propose some algorithms to ensure that a solution given by an integer value vector z ∈ {0, 1} |V |×|V | induces an interval m-clique free subgraph. We consider the induced graph G = (V, Ẽ) where Ẽ contains all edges such that ze = 1. For the interval graph detection, we use the algorithm given in [START_REF] Habib | Lex-BFS and partition renement, with applications to transitive orientation, interval graph recognition, and consecutive ones testing[END_REF] to check if G is an interval graph. If G is not an interval graph then we add an interdiction inequality

e∈ Ẽ z e - e∈E\ Ẽ z e ≤ | Ẽ| -1,

This algorithm runs in

O(n + mlog(n)).
For the clique inequalities, we search the clique of a maximum size. We use the integer linear program given in [START_REF] Pardalos | The maximum clique problem[END_REF] to nd the maximum clique in G. Finding the maximum clique in G is an NP-Hard problem. We use CPLEX to solve this problem. If G contains a clique K of a size greater than m, then we add the following clique inequality associated with K, otherwise all inequalities (4.20) are valid.

e∈E(K) z e ≤ |E(K)| -1,
Remark that, lazy constraints' call back is used only to check the validity of an integer solution.

Application to URPMDC problem.

In parallel machine scheduling, a graph can be used to represent a set of jobs competing for some resources such as a set of virtual machines in cloud computing. Here, the execution of a job when it is assigned to a virtual machine can be represented as an interval. Then, we may naturally assume that two jobs share any time unit if and only if there is an overlap between the corresponding intervals. Thus, the corresponding interval graph represents the jobs sharing execution intervals among these virtual machines. Figure 4.12 illustrates the use of interval graph in parallel machines scheduling. As one of the interval and m-clique free graphs' applications we will provide the following mathematical model for dening the problem of the unrelated parallel machines with incompatibility constraints. We will apply the results obtained from the previous sections to this problem. The unrelated parallel machine scheduling problem with disjunctive constraints is dened as follows. We have n jobs and m machines, that are arranged in parallel with dierent speeds. The problem is to schedule these jobs on the machines, with the aim of minimizing the C max . Let G I = (V I , E I ) be the graph of incompatibility, where for each job j ∈ J, we associate a vertex v j ∈ V I such that there exists an edge between v j 1 and v j 2 if j 1 and j 2 cannot be run at the same time. The case where we have to force certain jobs to not run at the same time with some others can be applied in some security issues in the cloud, and in constrained unrelated parallel machine.

Mathematical formulation

In this section we present an Integer Linear Programming Model (ILPM) to solve the unrelated parallel machine scheduling problem with disjunctive constraints. This ILP considers the starting of the job and the relation between jobs if they run on the same machine. Moreover, it veries if one job runs before another job. This model is based on interval graph and an m-clique free graph, because the graph induced by each solution must be interval graph, and m-clique free graph in order to be valid. A graph G(V, E) is called interval graph if its vertices V can be represented by interval I v of the real line such that two vertices are adjacent if and only if the corresponding intervals intersect [START_REF] Schrijver | Combinatorial Optimization : Polyhedra and Eciency[END_REF]. Let K be a clique in G (K ⊆ V such that every two distinct vertices of K are adjacent). This is equivalent to the condition that the subgraph of G induced by K is complete. Let I ⊆ E be a subset of edges, the graph G[I] is an m-clique free if and only if G[I] does not contain a clique of size strictly greater than m. Now, we introduce the ILPM : For each job we consider a variable y j ∈ N + dening the starting of job j in J. We consider binary variables for assigning the jobs on machines.

x i j = 1 if job j is performed on machine i, 0 otherwise ∀i ∈ M, ∀j ∈ J.
For every two jobs sharing a time unit the associated subgraph must be interval and mclique free. For this reason we consider the following binary variables to know if two jobs share a time unit or if they are performed on disjonctive intervals :

z j 1 ,j 2 =
1 if job j 1 and job j 2 run at the same time, 0 otherwise ∀j 1 , j 2 ∈ J.

zj 1 ,j 2 = 1 if job j 1 runs before j 2 , 0 otherwise ∀j 1 , j 2 ∈ J.
For all j ∈ J, we denote by C j ∈ N + the completion time of job j.

C max ∈ N + is the maximum of C j .

The URPMPC can be solved by the following ILPM denoted by (P ) :

min C max y j + i∈M p ij x i j ≤ C max , ∀j ∈ J, (4.13)
i∈M x i j = 1, ∀j ∈ J, (4.14)
x i j 1 + x i j 2 ≤ 2 -z j 1 ,j 2 ∀j 1 , j 2 ∈ J, ∀i ∈ M, (4.15)
z j 1 ,j 2 = 0, ∀(j 1 , j 2 ) ∈ E I , (4.16
)

y j 1 + i∈M p ij 1 x i j 1 ≤ y j 2 + C -C zj 1 ,j 2 , ∀j 1 , j 2 ∈ J, (4.17
)

zj 1 ,j 2 + zj 2 ,j 1 + z j 1 ,j 2 = 1, ∀j 1 , j 2 ∈ J, (4.18)
(j 1 ,j 2 )∈E( Ī)

z j 1 ,j 2 - (j 1 ,j 2 )∈E\E( Ī) z j 1 ,j 2 ≤ |E( Ī)| -1, ∀I ⊆ I, (4.19)
(j 1 ,j 2 )∈E(K)

z j 1 ,j 2 ≤ |E(K)| -1, ∀K ⊆ K, (4.20)
The objective function is to minimize the makespan. Inequalities (4.13) ensure that the starting time for each job plus its processing time is less than or equal to the total completion time. Inequalities (4.14) control each job to be processed on one machine. Inequalities (4.15) guarantee that there is no two jobs run on the same machine at the same time. Inequalities (4.16) control the disjunctive constraints. Inequalities (4.17) ensure that the starting of any job must be after the completion of its predecessor. Inequalities (4.18) ensure that, if the job j 1 runs before or at the same time with j 2 , and j 2 runs before or at the same time with job j 1 , then jobs j 1 and j 2 run at the same time. If we consider a solution given by the vector z, then we can dene its induced subgraph G = (V, E) where :

• for each job j ∈ J we associate a vertex v j ∈ V and for all z j 1 j 2 = 1 we associate an edge uv ∈ E, G must be an interval graph and the clique of maximum size must be less or equal to m. We denote by Ī the set of all the induced non interval subgraphs and by K the set of all cliques of size greater or equal than m + 1. The inequalities (4.19) ensure that all induced subgraphs are interval graphs. The inequalities (4.20) ensure that all induced subgraphs have no clique of size greater or equal than m + 1.

Computational Results

To test the eciency of the inequalities mentioned in Section 4.2.1 we developed the mentioned exact and heuristic separations. All computational results are obtained by using Cplex 12.6 and Java for implementing exact and heuristic algorithms. The ILPM with the valid inequalities is tested on the following proposed benchmark of instances. The processing times are uniformly distributed between 50 and 150 as it is common in the literature [START_REF] Hall | Generating Experimental Data for Computational Testing with Machine Scheduling Applications[END_REF]. We generated ve dierent sets of DAG where the graph density (GD) is equal to 0.5 and calculated as follows :

GD = |E| |V |(|V |-1)
where E is the set of edges associated with precedence constraints between jobs, and V is the set of vertices associated with jobs. The speeds of machines were generated randomly between 10 and 15.

The required CPU time is measured in seconds. We limit to 3600 seconds the algorithm running time for each instance, by using 4.0 GB of RAM.

The next tables provide the following information :

|J| : number of jobs m : number of machines Method : 0 cplex only ; 1 bipartite claw inequalities with heuristic separation 1 ; 2 umbrella inequalities with heuristic separation 1 ; 3 hole inequalities ; 4 clique inequalities with heuristic separation ; 5 n-net inequalities ; 6 n-tent inequalities ; 7 all inequalities. CPU : cpu time (limited to 1 hour) Nb Nodes : number of nodes in the branching tree ct BC : number of bipartite claw inequalities added in the B&C ct UMB : number of umbrella inequalities added in the B&C ct H : number of hole inequalities added in the B&C ct Q : number of clique inequalities added in the B&C ct NN : number of n-net inequalities added in the B&C ct NT : number of n-tent inequalities added in the B&C o/p : number of instances solved (5 instances over 5 or 0 over 5)

In Table 4.1 we can see the that all the instances are solved in less than 20 seconds. These instances contain 10 jobs with 2 to 8 machines. Remark that the number of the generated inequalities is less than 200 for the bipartite claw inequalities and less than 70 for all the others. These values are relatively small. Moreover, we generate very small number of clique inequalities, which is due to a small number of jobs. We did not generate n-net inequalities, which is due to the small average number of jobs per machine. Finally, we reduce in average the size of the search tree by adding these new valid inequalities. Table 4.2 gives the results for 15 jobs with 4 to 8 machines. We easily solve the set of instances within less than 10 minutes. Adding the valid contraints reduces signicatively the number of nodes in the tree search. The computation time is variable and adding the valid contraints does not reduce it systematically. This is due to the reduced size of the instances. Moreover, it can happen to generate a lot of contraints, as in the instances of 15 jobs on 6 machines, which explains the reduced performance. We observe that the method 3 allows us to reduce the computation times in average on the instances of 15 jobs and 6 machines. Finally, we remark that we generate few clique and n-net constraints for the same reasons previously mentioned. Table 4.3 shows the results for 15 jobs and 2 machines. We did not solve the instances of this size, which demonstrates the hardness of the studied problem. Wa can notice that we improved the gap of the standard formulation by using the method 4 (exploiting the clique contraints).

For solving this problem the new valid inequalities dod not allow to signicantly improve the computation time. Nevertheless, we will demonstrate in the next chapter the positive impact of these contraints. Indeed, the instances we try to solve are too small so that the valid inequalities will be able to improve the CPLEX routines. Moreover, our separation algorithms need certainly to be improved in order to quickly generate valid contraints.

Conclusion

In this chapter we presented a polyhedral study for the problem of interval under m-clique free subgraphs. A polyhedral investigation of the convex hull of these vectors yielded several results on facet dening inequalities for the dened polytope. We designed and implemented a branch-and-cut algorithms based on families of strong valid inequalities presented in this chapter. We separate some forbidden subgraphs, and we have also applied the obtained results to the problem of unrelated parallel machines with disjunctives/precedence constraints. The computational experiments on set of instances have shown that the algorithms are capable to solve all instances more less to the optimality within less CPU time when we add these separation algorithms. Further research in this direction will be helpful to strengthen the integer programming formulations of a large variety of unrelated parallel machines problems as an application to the interval under mclique free subgraphs. In the next chapter the properties of interval graph will be applied for solving generalized Open Shop. In this chapter we continued the study of our mathematical formulation, which is based on the interval subgraph. The strong structure of its polytope encourage us to adapt this model to solve other scheduling problems. We addressed two open shop scheduling problems : the generalized version with disjunctive constraints and the standard one. We present two mathematical formulations for solving these problems. We derived dierent classes of valid inequalities to strength our models. We also add separation algorithms to the relaxed model of the generalized open shop problem. Exhaustive computational experiments on the well known sets of Taillard's benchmarks are presented. The derived valid inequalities show a good improvement to the computational time for the two models. Mo-reover, the generalized open shop model shows the eciency of adding the cutting plane inequalities.

Introduction

In this chapter, we consider a particular case related to the model of the previous chapter. This problem is called generalized open shop with disjunctive constraints. In the rst part of this chapter, we propose a model for this problem and give some valid inequalities to improve the associated linear relaxation. Furthermore, we test experimentally the dierent inequalities. In the second part of this chapter we propose an integer linear programming model for the standard open shop problem. Indeed, the open shop is a restricted case of the generalized open shop with jobs disjunctive constraints. The Open-Shop problem is an important research branch of scheduling problems and it receives an important amount of attention because of their wide range of applications, such as modern transport and logistics, modern service industry, large-scale systematic maintenance, clothing industry, health care, and so on [START_REF] Ma | Concurrent Open-shop Scheduling Model Research[END_REF][START_REF] Bai | Open shop scheduling problem to minimize makespan with release dates[END_REF][START_REF] Kyparisis | Open shop scheduling with maximal machines[END_REF]. In cloud computing, there is a special case where the job can be divided into m sub tasks. Therefore, each sub task can be processed on a virtual machine. In general, this problem can be described by a set of n jobs to be processed by a set of m machines and there is no predetermined processing route for the jobs. Therefore in the open shop, there are two decisions to make : the determination of the processing route of each job as well as the job sequence at each stage [START_REF] Naderi | Scheduling open shops with parallel machines to minimize total completion time[END_REF]. The general O||C max problem is strongly NP-hard [START_REF] Graham | Optimization and approximation in deterministic sequencing and scheduling : A survey[END_REF].

Among the many techniques proposed in the literature the problem has not been attacked a lot by the mathematical models. Masuda and Ishii [START_REF] Masuda | Two machine open shop scheduling problem with bi-criteria[END_REF] studied the open shop scheduling problem for two-machines and they proposed a bi-criteria linear program. Kis et al [START_REF] Kis | A projective algorithm for preemptive open shop scheduling with two multiprocessor groups[END_REF] described an integer program in two dimension.

We also propose new valid inequalities and we test our model on a well known Taillard's [START_REF] Taillard | Benchmarks for basic scheduling problems[END_REF] instances. The experimental results show the eciency of our model by solving all Taillard's instances of size 4 × 4, 5 × 5, 7 × 7 and 10 × 10. Furthermore, we solve all instances of size 15 × 15 and reduce all upper and lower bounds for all other instances.

Generalized open shop problem with jobs disjunctive constraints

The Generalized Open Shop with Disjunctive Constraints (GOSDC) can be formulated as follows. Let M be the set of machines. For all i ∈ M we consider the set of jobs J i must be running of the machine i and we denote by J = {J 1 , ..., J m } the set of all these sets and by J = i∈M J i the union of these sets. We denote by p ij the processing time of job j on its machine i. We consider an incompatibility graph G I = (V I , E I ), in this graph, for each job j ∈ J we associate a vertex v j ∈ V I and there exist an edge between v j 1 and v j 2 if j 1 and j 2 cannot run at the same time. Remark that, it is necessary to considering a linear ordering on each machine. To the best of our knowledge this special problem has not been studied before.

Integer linear programming formulation

In this section, we present the integer linear programming for solving the problem. We need a family of binary variables. In the following, we describe the variables used in the model :

zj 1 ,j 2 = 1 if the job j 1 runs before the job j 2 0 otherwise ∀j 1 , j 2 ∈ J. z j 1 ,j 2 = 1 if j 1 and j 2 run at the same time 0 otherwise ∀j 1 ∈ J i , j 2 ∈ J i |i = i ∈ M.
For all j ∈ J, we consider the variable y j ∈ N + representing the starting time of job j.

C max ∈ N + is the maximum completion time. The GOSDC can be solved by the following ILP, denoted by (P GOS ) : with SC i is equal to the sum of C j × p ij for all jobs in J i given by a schedule of jobs in any sequence. We notice that this inequality remains valid for any subset. Figure 5.1 illustrates this relation. In this gure, the processing times of jobs are : p 1 = 2, p 2 = 1 and p 3 = 3, where the speed of machine equal to 1. In the rst sequence, we have : Figure 5.2 illustrates the idea of this family of inequalities. Having ỹj = C max -y j and from the valid inequalities (5.8), we can derive that j∈J i p ij (ỹ j ) ≥ SC i . Thus, we can establish that :

j∈J i (C max -y j ) × p ij ≥ SC i , ∀j ∈ J, (5.9)
Therefore, we deduce that :

j∈J i C max × p ij ≥ SC i + j∈J i y j × p ij , ∀j ∈ J,
(5.10)

Previous job inequalities

Considering machine i ∈ M and the job j ∈ J i , we introduce the following valid inequality :

j ∈J i p ij zj ,j ≤ y j , (5.11)
Inequalities (5.13) ensure that the starting time of job j on machine i will be after the sum of the completion times of all previous jobs on the same machine. We derived other family of inequalities based on the idea of the previous jobs. Figure 5.3 helps to explain this family of inequalities. The C max is bounded by the sum of the starting time of job j on machine i, plus the processing time of job j on machine i, plus the sum of the processing times of all next jobs on the same machine. Thus, job j processed previous these jobs on this machine.

C max ≥ p ij + y j + j ∈J i p ij zjj , ∀i ∈ M, ∀j ∈ J i , (5.12)

Line job inequalities

This class of inequalities derived from the idea of the linear order of jobs on the same machine extended for 3 machines. Considering i, i 1 , i 2 ∈ M and a job j ∈ J i , the following inequality holds. From the obtained results, the model can solve many problems to the optimality within reasonable computation time (especially for 5 jobs per machine, for two machines, and for ten jobs per machine, for two machines). In overall, the model solved 61% of the problems to optimality within one hour. For the other problems the gap is reasonable within this time limit. We can also notice that from the structure of the polytope there is no clique inequality added. Interesting results could be extracted from this experiments. Indeed, when we add the sequence, previous, and line valid inequalities to our model, we obtain an optimal solution for the larger instances within good computational time. When we add sequence, previous, and logical valid inequalities, we obtain some good results. We can say that there is a noticeable improvement for the results when we add our derived valid inequalities to our model. The most interesting things come from the improvement of the gap when we add the inequalities given in chapter 4. These inequalities allow us to divide the gap for the harder instances by 2 to 5 and then show their eciency. Remark that we add a lot of interval subgraph inequalities for the harder instances.

j ∈J i 1 p i 1 j zj ,j + p ij + j ∈J i 2 p i 2 j zj,j ≤ C max , , (5.13)
In the next section, we adapt this model to the standard open shop problem, where the job is divided into operations and the operations will be processed on a given set of parallel machines.

Open shop problem

In the second part of this chapter, we deal with the open shop problem.

The open shop scheduling problem can be described as follows. Having a set of parallel machines and a nite set of operations, these operations have to be processed on the given set of parallel machines. Preemption is not allowed. Each job has a processing time and each operation belongs to only one job. Operations are grouped in jobs. Moreover, the operations that belong to the same job and the operations that use the same machine cannot be processed at the same time. Furthermore, each operation is assigned to an only one machine. The objective of the open shop scheduling problem is to perform all operations, so as to minimize the maximum completion time (makespan).

More formally, we have a set J = {1, 2, .., n} of n jobs to be performed on a set of machines M i where i = {1, 2, ..., m}. Each job j ∈ J consists of exactly m operations O i,j (i ∈ {1, 2, ..., m}). For every job j and every index i, operation O i,j should be performed on machine M i . The processing time of each operation O i,j is denoted by p i,j . At any time, a job can be processed by at most one machine. Moreover, any machine can process only one job at a time. Preemption of operations is not allowed. For every job j, its completion time C j is dened as the completion time of its last operation. The objective is to nd a feasible schedule that minimizes the maximum completion time C max . Figure 5.5 illustrates the schedule of three jobs j 1 , j 2 and j 3 , where job j 2 does not share any time unit with job j 3 in the system, but job j 1 is processed at the same time with job j 2 and job j 3 .

Open shop scheduling problem is NP-hard problem [START_REF] Bå | Scheduling computer and manufacturing processes[END_REF]. Using the standard notation α|β|γ of Graham et al. [START_REF] Graham | Optimization and approximation in deterministic sequencing and scheduling : A survey[END_REF], we can denote the open shop problem as O m ||C max . Numerous scheduling problems in real life applications can be modeled as an open shop : network ow has a lot of problems that can be immediately translated into an open shop scheduling problem [START_REF] Pinedo | Planning and scheduling in manufacturing and services[END_REF]. A recent literature review of open shop is found in [START_REF] Anand | Literature review of open shop scheduling problems[END_REF] Let denote by O J i the set of operations of all jobs J assigned to machine i ∈ M and by O M j the set of operations of job j assigned to all the machines. We denote by p ij the processing time of the operation associated with j ∈ J assigned to machine i ∈ M .

5.3.1

Integer linear programming formulation

zO 1 ,O 2 = 1 if O 1 runs before O 2 0 otherwise ∀i ∈ M, ∀O 1 , O 2 ∈ O J i ∨ ∀j ∈ J, ∀O 1 , O 2 ∈ O M j
For all j ∈ J and i ∈ M : y i,j ∈ N + is the starting time of operation O i,j . C max ∈ N + is the maximum of y i,j + p ij . The Open Shop can be solved by the following integer linear programming model, denoted

Previous operations inequalities

Let consider the machine i ∈ M and the job j ∈ J. The following inequalities are valid :

j ∈J p ij zO i,j ,O i,j ≤ y i,j , (5.28)
By a similar reasoning, for every job j ∈ J and every machine i ∈ M , we introduce the following valid inequality :

i∈M p ij zO i,j ,O i ,j ≤ y i ,j , (5.29)
By symmetry, we can derive the following two families of inequalities. Figure 5.6 presents a numerical example to illustrate the previous operations inequalities.

As we proposed in the rst section, the following inequalities, based on precedence reasoning, hold :

C max ≥ p ij + y ij + j ∈J p ij zo ij o ij , ∀j ∈ J, ∀i ∈ M,
(5.30)

C max ≥ p ij + y ij + i ∈M p i j zo ij o i j , ∀j ∈ J, ∀i ∈ M, (5.31)

Logical implication inequalities

Here, we adapt the logical implication for the operations.Le us consider machine i ∈ M and jobs j 1 , j 2 , j 3 ∈ J. We introduce the following valid inequalities : zO i,j 1 ,O i,j 2 + zO i,j 2 ,O i,j 3 ≤ 1 + zO i,j 1 ,O i,j 3 , (5.32) This implication is related to the same machine for dierent operations. This implication can be also applied to the operations as in Figure 5.8. Considering job j ∈ J and the machine i 1 , i 2 , i 3 ∈ M , we introduce the following valid inequalities : zO i 1 ,j ,O i 2 ,j + zO i 2 ,j ,O i 3 ,j ≤ 1 + zO i 1 ,j ,O i 3 ,j , (5.33) In the next subsection, we present the computational experiments performed to test the eectiveness of the proposed inequalities. when we add the combination of inequalities (sequence, previous and logical implication). It is also worthy to notice that the best CPU time obtained by the combination of the sequence and previous inequalities. Table 5.4 reports the results for instances (15 15). According to these results, the related problems are not easy to solve within the limited time and the memory space. Thus, few number of problems have been solved. The combination of the sequence and previous inequalities allows us to obtain some optimal solutions. It is also the same case, when we add to this combination the conditional inequalities (i.e., we obtained the same number of the optimal solutions). The gap between the obtained UB ILP and LB ILP does not exceed 5%.

Table 5.5 reports the results for instances of (20 20). Within the adjusted time to one hour, no problem has been solved for this size. But, we can see the small gaps between the UB and LB obtained by the ILP. All of them appear when we add the combination of sequence and previous inequalities.

Conclusion

In this chapter, we considered two parallel-machine scheduling problems. The rst problem is the generalized open shop with disjunctive constraints. To the best of our knowledge there is no mathematical model for this problem. The second problem is the standard open shop problem. The aim is to minimize the maximum completion time. To deal with these problems, two mathematical models were proposed. We derived some classes of valid inequalities. We also added the interval subgraph separation algorithms for the generalized open shop problem. We adapted the derived valid inequalities to the open shop mathematical formulation. The results on some instances show that the basic models can solve the small size instances to optimality, and the generalized model shows the eciency of adding the cutting plane inequalities proposed in Chapter 4, which can divide the gaps by 2 to 5. The derived valid inequalities show an important improvement of the computation time for the two models. We believe that the design of new classes of valid inequalities and the incorporation of further separation algorithms will improve the computation times of our models and it will lead to optimal solutions for some of the unsolved instances. In this thesis, we consider the scheduling problem in cloud computing, which is formulated as an unrelated parallel-machine scheduling problem under precedence constraints (URPMPC) and as a generalized case of open shop problem under disjonctive constraints.

For solving these problems we applied dierent combinatorial optimization techniques. To attack URPMPC, we proposed several genetic algorithms for job scheduling problem in cloud computing with the objective of minimizing the makespan (C max ). We also worked on dierent exact approaches. We studied the mathematical formulations that are found in literature. Moreover, we proposed a novel mathematical formulations based on interval graph. The main dierence between these formulations is the way the makespan has been linearized. The facial structure of the polytope generated by interval graph model is investigated to dene some facets. There is an important piece of information contained in this model but it cannot know if the jobs run at the same time or not. There are some applications that require such an information, especially in some cloud computing security based models. We improved the interval graph formulation by adding valid inequalities based on the forbidden interval subgraph and some heuristics to solve the clique problem or nd the smallest non interval subgraphs. Furthermore, we proposed other inequalities based on SPT (Shortest Processing Time). Some heuristics are used to separate the inequality based on the SPT. We also present a polyhedral study for the problem of interval and m-clique free graphs. A polyhedral investigation of the convex hull of these vectors yielded several results on inequalities dening facets for this new polytope. We have also applied the obtained results to the problem of unrelated parallel-machine with disjunctive constraints. We designed and implemented a branch-and-cut algorithms based on families of strong valid inequalities presented in this chapter. We separate some forbidden subgraphs. The results in heuristics and metaheuristic show that the performances of our proposed genetic algorithms have been compared against one of the best existing genetic algorithm for the same problem. After extensive comparisons, we can conclude that the proposed algorithms can improve the solutions obtained. In the exact solutions, we studied and evaluated the eectiveness and eciency of our model and the other models. Intensive numerical experiments are conducted. The obtained results show the eectiveness of the interval graph formulation compared to the available formulations except the order formulation. Computational results show that the addition of the valid inequalities decreases the computational requirements to obtain the optimal solution in many cases.

Finally, we considered the generalized open shop with disjunctive constraints and the open shop scheduling problem. To the best of our knowledge there is no mathematical model for this problem. To tackle these problems, two mathematical models are constructed. We derived some classes of valid inequalities. We also add the interval subgraph separation algorithms for the generalized open shop problem. We adapted the derived valid inequalities to the open shop mathematical formulation. The results on some instances show that the basic models can solve the small size instances to optimality. The generalized model shows the eciency of adding the cutting plane inequalities and the reduction of the gap between upper and lower bounds. The derived valid inequalities show a good improvement of the computational time for the two models.

We can conclude that, in this thesis we developed dierent approaches to tackle the scheduling problem in cloud computing. Three novel genetic algorithms based and three novel mathematical models with interesting theoretical results in polyhedral analysis were proposed. The class of scheduling problems in cloud computing has dierent perspectives in terms of optimization criteria (minimization of total completion time and other objectives). Moreover, we need to develop other heuristics for the branch and cut, to derive new classes of valid inequalities and to incorporate further separation algorithms, in order to improve the computation time of our models. Furthermore, for the theoretical point of view, the identication of further relaxations to dene more facets will be interesting in such problems. It will be also interesting to work on branch and price methods. Finally,

1. 1

 1 Task scheduling in cloud computing model. . . . . . . . . . . . . . . . . . . 1.2 A convex hull . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Valid inequality, facet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1 Precedence Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Example of the GATS and GAAV encoding. . . . . . . . . . . . . . . . . . 2.3 Counts of best results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Genetic algorithms convergence. . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Average Relatives Percentage Gap. . . . . . . . . . . . . . . . . . . . . . . 3.1 Classical Formulation Illustration. . . . . . . . . . . . . . . . . . . . . . . . 3.2 Job in position r must start its processing after job in position r -1. . . . 3.3 Flow Formulation Illustration. . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Finding Path between sequences. . . . . . . . . . . . . . . . . . . . . . . . 3.5 Illustration for the Status of Inequalities (3.34) . . . . . . . . . . . . . . . . 3.6 An induced sub graph with it's valid schedule . . . . . . . . . . . . . . . . 3.7 Schedule of three jobs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Cliques with 3, 4, 5 and 6 vertices. . . . . . . . . . . . . . . . . . . . . . . 4.2 Forbidden Subgraphs Characterization . . . . . . . . . . . . . . . . . . . . 4.3 Subsets of the complementary Bipartite Claw . . . . . . . . . . . . . . . . 4.4 Subsets of umbrella and its complementary . . . . . . . . . . . . . . . . . . 4.5 Hole free subgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.6 Coecient of umbrella and its complementary edges . . . . . . . . . . . . . 4.7 Basic edges for Bipartite Claw and Umbrella . . . . . . . . . . . . . . . . . 4.8 Adding one vertex to 2-net to nd 3-net . . . . . . . . . . . . . . . . . . . 4.9 Adding one vertex to 3-tent to nd 4-tent. . . . . . . . . . . . . . . . . . . xv Table des gures 4.10 Hole . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.11 Clique of size 4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.12 Schedule of 4 jobs on 3 machines . . . . . . . . . . . . . . . . . . . . . . . 5.1 Dierent sequences of jobs on a machine . . . . . . . . . . . . . . . . . . . 5.2 Sequence inequalities. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Previous job inequalities. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Line job inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5 Open shop for three jobs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.6 Example : previous job inequalities between operations . . . . . . . . . . . 5.7 Logical implication on one machine. . . . . . . . . . . . . . . . . . . . . . . 5.8 Logical implication between operations. . . . . . . . . . . . . . . . . . . . . xvi Liste des tableaux

Figure 1 . 1

 11 Figure 1.1 Task scheduling in cloud computing model.

Figure 1 . 3

 13 Figure 1.3 Valid inequality, facet

  Figure 2.1 Precedence Constraints

  3 while Stopping Criteria Not Satised do 4 Select a pair of parents based on tness. 5 Create two ospring using crossover. 6 Apply mutation to each child.

7

 7

2 5 Add

 5 while |Available| > 0 do 3 Selectedmachine = the machine with minimum C i . 4 Selectedjob= the job of greater number of successors in Selectedmachine. Selectedjob to Selectedmachine Update C i . 6 Update Available.

Figure 2 . 2

 22 Figure 2.2 Example of the GATS and GAAV encoding.

Figure 2 . 3

 23 Figure 2.3 Counts of best results .

Figure 2 .

 2 Figure 2.5 indicates the Average Relative Percentage Gap (ARPG) between the rst and the best solution for genetic algorithm. Indeed, ARPG is computed as follows 100 × (C First max -C Best max ) C Best max

Figure 2 . 4

 24 Figure 2.4 Genetic algorithms convergence.

Figure 2

 2 Figure 2.5 Average Relatives Percentage Gap.

2 Figure 3 . 1

 231 Figure 3.1 Classical Formulation Illustration.

Figure 3 . 2

 32 Figure 3.2 Job in position r must start its processing after job in position r -1.

Figure 3 . 3 Flow

 33 Figure 3.3 Flow Formulation Illustration.

a) An induced sub graph j 1 j 2 j 4 (Figure 3 . 4 Finding

 434 Figure 3.4 Finding Path between sequences.

Figure 3 . 5

 35 Figure 3.5 Illustration for the Status of Inequalities (3.34)

Figure 3 . 6

 36 Figure 3.6 An induced sub graph with it's valid schedule

Figure 3 . 7

 37 Figure 3.7 Schedule of three jobs.

Figure 4 . 1

 41 Figure 4.1 Cliques with 3, 4, 5 and 6 vertices.

Figure 4 .

 4 Figure 4.1 shows the cliques of size 3, 4, 5 and 6. Motivated by practical applications, this chapter studies the interval and m-clique free sub-graphs as well as the associated polytope. In particular, the next section provides the polytopes of interval and m-clique graphs.

  Hole, n ≥ 4

Figure 4 . 2

 42 Figure 4.2 Forbidden Subgraphs Characterization

Figure 4 .

 4 Figure 4.3 shows these subsets.

Figure 4 . 3

 43 Figure 4.3 Subsets of the complementary Bipartite Claw

BC

4 h

 4 = {(3, 5),[START_REF] Izakian | Metaheuristic based scheduling metatasks in distributed heterogeneous computing systems[END_REF][START_REF] Wang | Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics[END_REF],(5, 4),[START_REF] Izakian | Metaheuristic based scheduling metatasks in distributed heterogeneous computing systems[END_REF][START_REF] Hsu | Unrelated parallelmachine scheduling with rate-modifying activities to minimize the total completion time[END_REF],[START_REF] Hart | Evolutionary scheduling : A review[END_REF][START_REF] Hsu | Unrelated parallelmachine scheduling with rate-modifying activities to minimize the total completion time[END_REF],(4,[START_REF] Wang | Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics[END_REF]}.BC = {(2, 3),(2, 4),(3, 4)}, BC i = {(1, 5),[START_REF] Dogan | Genetic algorithm based scheduling of meta-tasks with stochastic execution times in heterogeneous computing systemst1[END_REF][START_REF] Wang | Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics[END_REF], (1, 7)}. BCWe consider two cases, when m = 2, and when m ≥ 3. If m = 2 then the following inequality is valid : e∈BC z e ≤ 5.

Proposition 7

 7 The inequality (4.1) denes a facet, when m = 2.

proof 4 . 3 4 h ∪ BC 5 h

 4345 Let us denote by az ≤ α the inequality(4.1). Let bz ≤ β be an inequality that denes a facet of P I (G, m), such that {z ∈ P I (G, m) : az = α} ⊆ {z ∈ P I (G, m) : bz = β}. Since P I (G, m) is of a full dimension, we need to prove that there exists ρ such that b = ρa for some ρ ∈ R. Let e 1 , e 2 ∈ BC be two edges. The solutions I 1 = BC \ {e 1 }, and I 2 = BC \ {e 2 } are valid. Their incidence vectors satisfy the inequality (4.1) to the equality. Since, az I 1 =az I 2 , therefore bz I 1 =bz I 2 implying that b(e 1 ) = b(e 2 ). We set b(e 1 ) = ρ. As e 1 and e 2 are arbitrary in BC, then b(e) = b(e ) ∀e, e ∈ BC. The solutions I 3 = BC \ {(1, 4)}, and I 4 = I 3 ∪ {(2, 4)}, I 5 = I 3 ∪ {(5, 4)}, and I 6 = I 3 ∪ {(5, 7)} are valid. Their incidence vectors satisfy the inequality (4.1) to the equality. Since, az I 3 =az I 4 =az I 4 =az I 5 =az I 6 , therefore bz I 3 =bz I 4 =bz I 4 =bz I 5 =bz I 6 implying that b((2, 4)) = b((5, 4)) = b((5, 7)) = 0. By symmetry, b(e) = 0, ∀e ∈ BC ∪ BC . The solutions I 7 = BC\{(4, 7)} and I 8 = I 7 ∪{(1, 7)} are valid and verify the inequality

( 4 . 1 )

 41 to the equality. Since, az I 7 =az I 8 , therefore bz I 7 = bz I 8 , implying that b((1, 7)) = 0. By symmetry, we have b((1, 5)) = b((1, 6)) = 0. Let e 3 ∈ E \ (BC ∪ BC). The solutions I 3 and I 9 = I 3 ∪ {e 3 } are valid and verify the inequality (4.1) to the equality. Since, az I 3 =az I 9 , therefore bz I 3 = bz I 9 , which implies that b(e 3 ) = 0. By symmetry, we have b(e) = 0 for all e ∈ E \ (BC ∪ BC).

Now, if m ≥ 3 10 ( 4 . 2 ) 5 h or BC 4 h

 3104254 then the following inequality is valid. This inequality is valid, if we add one edge of BC to the bipartite claw, then the resulting subgraph contains 2 -net. If we add one edge of BC , then we obtain a hole of size 5 respectively 4. It is clear that when we add one, two or three edges of BC i , then the resulting graph becomes interval and m-clique free.Proposition 8 Inequality (4.2) denes a facet, when m ≥ 3.

proof 4 . 4

 44 Let us denote by az ≤ α the inequality (4.2). Let bz ≤ β be an equality that denes a facet of P I (G, m), such that {z ∈ P I (G, m) : az = α} ⊆ {z ∈ P I (G, m) : bz = β}. Since P I (G, m) is of a full dimension, we need to prove that there exists ρ such that b = ρa for some ρ ∈ R. Let e 1 , e 2 ∈ BC be two edges. The solution I 1 = BC \ {e 1 } and I 2 = BC \ {e 2 } are valid. Their incidence vectors satisfy the inequality (4.2) to the equality. Since az I 1 =az I 2 , therefore bz I 1 =bz I 2 implying that b(e 1 ) = b(e 2 ). We set b(e 1 ) = 2ρ. As e 1 and e 2 are arbitrary in BC, then b(e) = b(e ) = 2ρ ∀e, e ∈ BC. Let e 3 ∈ BC i be one edge. The solutions I 3 = BC ∪ {e 3 } and I 1 are valid. Their incidence vectors satisfy the inequality (4.2) to the equality. As az I 3 =az I 1 , then bz I 3 =bz I 1 implying that b(e 3 ) = -b(e 1 ). As e 3 is arbitrary in BC i and e 1 ∈ BC, then b(e) = -b(e ). We deduce that b(e ) = -2ρ, e ∈ BC i . The solutions I 4 = BC ∪ {(2, 4), (3, 4)} and I 5 = BC ∪ {(2, 4), (2, 3)} are valid and verify the inequality (4.2) to equality. As az I 4 = az I 5 then bz I 4 = bz I 5 , implying that b((3, 4)) = b((2, 3)). By symmetry, we have b((3, 4)) = b((2, 4)) = b((2, 3)). The two solutions I 6 = BC ∪ {(2, 4), (5, 4)} and I 7 = BC ∪ {(2, 4), (2, 7)} are valid and verify the inequality (4.2) to equality. Since az I 6 = az I 7 , then bz I 6 = bz I 7 , implying that b((5, 4)) = b((2, 7)). By symmetry, we have b((2, 6)) = b((3, 5)) and b((4, 6)) = b((3, 7)). By considering the solutions I 4 and I 6 we can observe that az I 4 = az I 6 . For this reason bz I 4 = bz I 6 , which implies that b((3, 4)) = b((5, 4)). By symmetry we have b(e) = b(e ) for all e ∈ BC and e ∈ BC 4 h . By considering the solutions I 1 and I 4 are valid and verify the inequality (4.2) to equality. Hence, az I 1 = az I 4 , therefore bz I 1 = bz I 4 , this implying that b(e 1 ) = -b((2, 4))b((5, 4)), by the previous results and by the symmetry we deduce b(e) = -2b(e ) for all e ∈ BC, and for all e ∈ BC ∪ BC 4 h . Therefore b(e ) = -ρ. The solutions I 11 = BC ∪ {(5, 7), (2, 4), (5, 4)}, and the solution I 6 are valid and verify the inequality (4.2) to equality. As az I 11 = az I 9 , then bz I 11 = bz I 9 implying that b(5, 7) = 0. By symmetry, we have b(e) = 0 for all e ∈ BC 5 h . Let e 8 ∈ E \ (BC ∪ BC). The solutions I 12 = (BC \ {(1, 2)}) ∪ {e 8 } and the solution I 13 = BC \ {(1, 2)} are valid and verify the inequality (4.2) to equality. Since az I 12 =az I 13 , then bz I 12 = bz I 13 implying that b(e 8 ) = 0. By symmetry, we have b(e) = 0 for all e ∈ E \ (BC ∪ BC).

Figure 4 . 4

 44 Figure 4.4 Subsets of umbrella and its complementary

  7)} and I 18 = I 17 ∪ {e} are valid and verify the inequality (4.4) to the equality. Since az I 17 =az I 18 , therefore bz I 17 =bz I 18 . By symmetry, we have b(e) = 0.

(4. 5 )

 5 Proposition 11 Inequality (4.5) denes a facet. proof 4.7 Let us denote by az ≤ α the inequality (4.5) associated with e. Let bz ≤ β be a facet dening an equality (4.5) such that {z ∈ P I (G, m) : az = α} ⊆ {z ∈ P I (G, m) : bz = β}. We show that b = ρa for some ρ ∈ R.

( 4 . 5 )

 45 to the equality. Moreover, we have az I 6 =az I 7 =az I 8 = az I 9 =az I 10 =az I 11 = az I 12 =az I 13 . Hence, we have bz I 6 =bz I 7 =bz I 8 = bz I 9 =bz I 10 =bz I 11 = bz I 12 =bz I 13 . Thus, b(e) = 0 for all e ∈ E h net . Let e ∈ E \ (E net ∪ E net ). By considering the valid solutions I 14 = E net \ {(a, b)} and I 15 = E net \ {(a, b)} ∪ {e}, we have az I 14 =az I 15 . Hence, bz I 14 =bz I 15 . This implies that b(e) = 0.

  z e ≤ |E tent \ E h tent | -1.

(4. 6 )

 6 Proposition 12 Inequality (4.6) denes a facet, when m ≥ 5 or (n = 4 and m = 3) or (n = 3 and m = 2).

proof 4 . 8

 48 Let us denote by az ≤ α the inequality (4.6) associated with e. Let bz ≤ β be a facet dening an equality (4.6) such that {z ∈ P I (G, m) : az = α} ⊆ {z ∈ P I (G, m) : bz = β}. We show that b = ρa for some ρ ∈ R.

Proposition 16 Let

 16 K be a clique of size m + 1. The inequality e∈E(K) z e ≤ |E(K)| -1 (4.10) denes a facet of P I (G, m).

proof 4 .

 4 [START_REF] Hardin | Strong valid inequalities for the resource-constrained scheduling problem with uniform resource requirements[END_REF] Let us denote by az ≤ α the inequality (4.10) associated with e. Let bz ≤ β be a facet dening an equality (4.10) such that {z ∈ P I (G, m) : az = α} ⊆ {z ∈ P I (G, m) : bz = β}. We show that b = ρa for some ρ ∈ R.

1, 2 4 h

 24 + 2z * 1,3 -z * 2,3 ) is less than 2, then there does not exist a violated bipartite claw within these 3 vertices in this position. Indeed, if z * e = 1, ∀e ∈ BC \ {(1, 2), (1, 3)} and z e = 0, ∀e ∈ BC ∪BC , then we obtain the best case, a left hand side value less than 10. Indeed, e∈BC\{(1,2),(1,3)} 2z * e = 8. Thus, 8 + 0 + (2z * 1,2 + 2z * 1,3 -z * 2,3 ) < 10.

Figure 4 . 7 -z 3 , 5 -z 2 , 4 -z 4, 6 (Figure 4 . 6

 473524646 Figure 4.6 Coecient of umbrella and its complementary edges

Figure 4 . 8

 48 Figure 4.8 Adding one vertex to 2-net to nd 3-net

  |E net \ E h net | -1. From Figure 4.2c, the sub sets are the following : -E net = {(a, b), (c, 1), (d, n), (1, 2)..., (n -1, n)}, -E h net = {(b, 2), ..., (b, n -1)}.

Figure 4 .

 4 8b explains the process, when the dashed edges are added.

Figure 4 . 9

 49 Figure 4.9 Adding one vertex to 3-tent to nd 4-tent.

Figure 4 .

 4 Figure 4.11 Clique of size 4.

Figure 4 .

 4 Figure 4.12 Schedule of 4 jobs on 3 machines

6 Figure 5 . 1 Figure 5 . 2

 65152 Figure 5.1 Dierent sequences of jobs on a machine

Figure 5 . 3 Figure 5 . 4

 5354 Figure 5.3 Previous job inequalities.

Figure 5 . 5

 55 Figure 5.5 Open shop for three jobs

2 O 13 , p 13 = 3 C 13 = 3 y 13 = 0 m 1 Figure 5 . 6

 21331313156 Figure 5.6 Example : previous job inequalities between operations

1 Figure 5 . 7

 157 Figure 5.7 Logical implication on one machine.

1 Figure 5 . 8

 158 Figure 5.8 Logical implication between operations.

Figure 5 .

 5 7 illustrates the idea behind : when operation O 11 is before operation O 12 and operation O 12 is before operation O 13 , then operation O 11 is before operation O 13 .

6 General

 6 Conclusion and PerspectivesDue to increasing demand, scheduling in cloud environment attracted much attention in recent years. Several scheduling problems have been recently addressed in cloud computing research eld. Nonetheless, scheduling in cloud computing still lacks some research eorts, because of the everyday growing of this recent technology.

  Graph theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.6 Optimization problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Polyhedral approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.7.1 Elements of polyhedral theory . . . . . . . . . . . . . . . . . . . . . 1.7.2 Cutting plane methods . . . . . . . . . . . . . . . . . . . . . . . . . 1.8 Branch and cut algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . Valid Inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.1 Separation Algorithm for SPT Inequality . . . . . . . . . . . . . . . 3.4.2 Reformulation of Interval Graph Formulation . . . . . . . . . . . . 3.5 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 The polytopes of interval sub-graphs . . . . . . . . . . . . . . . . . . . . . 4.2.1 Forbidden subgraphs inequalities . . . . . . . . . . . . . . . . . . . Bipartite Claw . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.1 Integer linear programming formulation . . . . . . . . . . . . . . . . 5.3.2 Valid inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sequence inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . Previous operations inequalities . . . . . . . . . . . . . . . . . . . . Logical implication inequalities . . . . . . . . . . . . . . . . . . . . 5.3.3 Experimental results . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

	Table of contents
	General Introduction Chapitre 1 State-of-the-Art Chapitre 2 Chapitre 4 Polyedral study on interval graphs under m-clique free constraints General Conclusion and Perspectives 4.1 Chapitre 6 Bibliographie	71 127
	Heuristics and Meta-heuristics Solutions	23
	viii

1.1 Cloud Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Scheduling problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Computational complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Heuristics and meta-heuristics . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.1 Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.2 Metaheuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Genetic algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5 1.6.1 Combinatorial optimization . . . . . . . . . . . . . . . . . . . . . . 1.6.2 Linear programming . . . . . . . . . . . . . . . . . . . . . . . . . . 1.6.3 Integer programming . . . . . . . . . . . . . . . . . . . . . . . . . . 1.7 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Problem Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Mathematical Formulations . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1 Classical Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.2 Flow Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.3 Order Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.4 Interval Graph Formulation . . . . . . . . . . . . . . . . . . . . . . 3.4 Umbrella Inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . n-net Inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

Table des gures

 des

  2.1 Processing Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Average and Standard deviation for Instances Processing time . . . . . . . 2.3 GAT S vs GAT S + , C max Comparison . . . . . . . . . . . . . . . . . . . . . 2.4 Chromosome representation for GAAV . . . . . . . . . . . . . . . . . . . . 2.5 GAAV :Crossover Operator . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6 GAAV :Mutation Operator . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.7 Results Obtained by the ILP . . . . . . . . . . . . . . . . . . . . . . . . . .

2.8 Makespan(C max )for the proposed algorithms and GATS, (Low& Medium Density) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.9 The Average Relative Percentage Gap(ARPG) for the transformation process between Genetic Algorithms . . . . . . . . . . . . . . . . . . . . . . . 2.10 Best Makespan/ C max obtained among All GAs Comparing to AVtoTS and AV+toTS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Average Relative Percentage Gap between Optimal Solution and Obtained Solution. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Results for 10 jobs with dierent methods . . . . . . . . . . . . . . . . . . 4.2 Results for 15 jobs with dierent methods . . . . . . . . . . . . . . . . . . 4.3 Results for hard instances with 15 jobs and dierent methods . . . . . . . 5.1 Results of the generalized open shop model . . . . . . . . . . . . . . . . . 5.2 Number of optimal solutions obtained. . . . . . . . . . . . . . . . . . . . . 5.3 Number of optimal solutions obtained. . . . . . . . . . . . . . . . . . . . . 5.4 Number of optimal solutions obtained. . . . . . . . . . . . . . . . . . . . . xvii 5.5 Number of optimal solutions obtained. . . . . . . . . . . . . . . . . . . . . 126

  Hassan, I. Kacem, S. Martin, I.M. Osman, Genetic Algorithms for Job sche-duling in cloud computing. Studies in Informatics and Control, 2015, Vol. 24, No. 4, December 2015. PP. 387-399. Mohammed-Albarra Hassan, ImedKacem, Sébastien Martin, Izzeldin M. Osman : mclique free Interval sub-graph : Polyhedral analysis and Branch and Cut. (submitted to the Journal of Combinatoric Optinization (JOCO) in November 2016). Mohammed-Albarra Hassan, ImedKacem, Sébastien Martin, Izzeldin M. Osman : Unrelated Parallel Machine Scheduling Problem with Precedence Constraints : Polyhedral Analysis and Branch-and-Cut. ISCO 2016 : Lecture Notes of Computer Science (SPRINGER) PP. 308-319 (DOI :10.1007/978-3-319-45587-727). M-A. Hassan, I. Kacem, S. Martin, I.M.Osman. Valid Inequalities for Unrelated Parallel Machines Scheduling with Precedence Constraints. Proceedings of IEEE CODIT'16, 6-8 April 2016, Saint Julian's Malta : pp.677 -682 (DOI : 10.1109/Co-DIT.2016.7593644). M-A. Hassan, I. Kacem, S. Martin and I. M. Osman. Mathematical Formulations for the Unrelated Parallel Machines with Precedence Constraints.

	Four articles in international conferences : 1
	State-of-the-Art
	Proceedings of 45th
	International Conference on Computers & Industrial Engineering (CIE45), 28-30
	October 2015, FRANCE.
	Mohammed-Albarra Hassan Abdel-Jabbar, ImedKacem, Sébastien Martin : Unre-
	lated parallel machines with precedence constraints : application to cloud compu-
	ting. IEEE CLOUDNET 2014 Luxembourg : pp.438-442 (DOI : 10.1109/Cloud-
	Net.2014.6969034).
	One poster in poster session :
	Poster session presented at IAEM Journée d'automne , 15 Octobre 2014 -Faculté
	des Sciences & Technologies, Université de Lorraine, Nancy.

Contents 1.1 Cloud Computing . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Scheduling problems . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3 Computational complexity . . . . . . . . . . . . . . . . . . . . . 8 1.4 Heuristics and meta-heuristics . . . . . . . . . . . . . . . . . . . 9 1.4.1 Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.4.2 Metaheuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.5 Graph theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.6 Optimization problems . . . . . . . . . . . . . . . . . . . . . . . 12 1.6.1 Combinatorial optimization . . . . . . . . . . . . . . . . . . . . 1.6.2 Linear programming . . . . . . . . . . . . . . . . . . . . . . . . 1.6.3 Integer programming . . . . . . . . . . . . . . . . . . . . . . . . 1.7 Polyhedral approach . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.7.1 Elements of polyhedral theory . . . . . . . . . . . . . . . . . . . 1.7.2 Cutting plane methods . . . . . . . . . . . . . . . . . . . . . . . 1.8 Branch and cut algorithm . . . . . . . . . . . . . . . . . . . . . 19

  Denition 3 H ⊂ R n is a subspace if x ∈ H implies λx ∈ H for all λ ∈ R and x, y ∈ H implies x + y ∈ H.Denition 4 A polyhedron P ⊂ R n is the set of points that satisfy a nite number linear inequalities ; that is, P = {x ∈ R n : Ax ≤ b}, where (A, b) is an m × (n + 1) matrix.

		1.7. Polyhedral approach
		Valid proper face, facet
		Valid proper face, but not facet
	Valid	invalid

  0} ; Generate two sub problems in one of which x ij is set to 0, and in the other is to 1.1.8. Branch and cut algorithm Algorithm 1: Cutting Plane AlgorithmInput: A linear program LP and its system of inequalities Ax ≤ b Output: Optimal solution x

		Stop ;
	6 else
	7	nd a better description of P c (G);
	8	Goback to 2
	9 end
	10 if no better description can be found then

11 branch : select a variable x ij with x * ij / ∈ {1, * of LP Consider a linear program LP' with a small number of inequalities of LP ; Solve LP' and let x * be an optimal solution ; Solve the separation problem associated with Ax ≤ b and x * ; if an inequality ax ≤ α of LP is violated by x * then Add ax ≤ α to LP'; Repeat step 2 ; else x * is optimal for LP; return x * ; end 2 Heuristics and Meta-heuristics Solutions Contents 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.1.1 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.2 Problem formulation . . . . . . . . . . . . . . . . . . . . . . . . 27 2.3 An existing algorithm . . . . . . . . . . . . . . . . . . . . . . . . 29 2.4 Genetic algorithm (GA) . . . . . . . . . . . . . . . . . . . . . . 29 2.4.1 Modeling the problem using Genetic Algorithm . . . . . . . . . 31

Table 2 .

 2 1 Processing Time ordering method and list scheduling method to formulate the chromosome. During each iteration step (Generation), genetic operations, that is crossover, mutation and selection are processed to search potential better solutions. Crossover combines two chromosomes to generate the next generation(P g+1

  .2, and we changed the density of graph.

		processing time
		Average Stdev
		50 48.11	25.98
		100 52.26	28.62
		200 50.81	27.61
		500 49.72	27.70
		Table 2.2 Average and Standard deviation for Instances Processing time
	2.4.1	Modeling the problem using Genetic Algorithm

Table 2 .

 2 3 GAT S vs GAT S + , C max Comparison

	Instances	L-Density	M-Density	H-Density
	m	n GATS GATS+ GATS GATS+ GATS GATS+
	2	50 17274	17251 17251	17251 17274
	2 100 37667	37667 37713	37667 37667
	2 200	-	74590	-	74026	-
	2 500	-181679	-182170	-
	5	50 10349	10527 8163	8279 7813
	5 100 20791	19766 19240	18355 20049
	5 200	-	37731	-	36704	-
	5 500	-	88668	-	84741	-
	10	50 7820	7820 4850	4850 6460
	10 100 10860	10768 10858	11008 10970
	10 200	-	22236	-	20189	-
	10 500	-	48365	-	43323	-
	20	50 6238	6090 6430	6430 4540
	20 100 9775	9604 8693	8504 9628
	20 200	-	20892	-	15222	-
	20 500	-	39090	-	32557	-

Table 2 .

 2 4 Chromosome representation for GAAV from the set of M. Table2.4 shows the chromosome representation for ten jobs on ve VMs.

Table 2 .

 2

5 GAAV :Crossover Operator

Table 2 .

 2 6 GAAV :Mutation OperatorSelection Finally, the best chromosome of the rst population is stored as in a linear ranking.

				C max ↓
	m 2	j 3	j 4	j 5
	m 1	0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 j 1 j 2 j 6 j 7
		(a) GAAV solution
	0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

Table 2 .

 2 7 Results Obtained by the ILP

	Instances High Density Medium Density Low Density
	m	n	LB	UB	LB	UB	LB	UB
	2	20 8892 38480 8008	38480 8190 38480
	2	50 8887 40885 5482	40885 5575 40835
	10	50 7263 45695 4746	45695 5888 45695

Table 2 .

 2 8 Makespan(C max )for the proposed algorithms and GATS, (Low& Medium

					Density			Medium Density
	m	n GATS GATS+ GAAV GAAV+ GATS GATS+ GAAV GAAV+
	2	50 17927	17927 17927	17927 17251	17251 17251
	2 100 38577	38577 37790	37539 37661	37667 37505
	2 200 75595	75682 74659	74474 73847	73956 73210
	2 500 180908 180861 180849	195618 180375 180466 179120
	5	50 10349	9672 10073	9591	8318	8228	7997
	5 100 19921	19776 19921	19320 18467	18213 17793
	5 200 36521	36645 36036	36205 35621	35577 35575
	5 500 85015	85268 92482	114689 80365	81039 87801
	10	50	7820	7820	7820	7820	4850	4850	4887
	10 100 10494	10591 10378	10310 10580	10552 10118
	10 200 20656	21755 22980	21803 18858	19521 20010
	10 500 44935	46714 57585	73291 40309	41062 48073
	20	50	6156	6090	6156	6090	6430	6430	6430
	20 100	9310	9431	9801	9495	8206	8141	8186
	20 200 20112	19964 21151	20707 14477	14348 15395
	20 500 36364	36346 43463	54919 30117	31063 41631
	Density)

+ AV T S AV + T S T SAV T SAV + AV T S AV + T S T SAV T SAV + AV T S AV + T S

Table 2 .

 2 9 The Average Relative Percentage Gap(ARPG) for the transformation process between Genetic Algorithms

	Low Density	AV T S AV + T S	17251 17251	37488 37488	72891 72891	178334 179580
	High Density Medium Density	AV T S AV + T S Best AV T S AV + T S Best	17927 17937 17251 17251 17251 17251	37488 37488 37492 37488 37488 37667	74425 74438 73210 73112 73358 73024	179768 180377 179120 178412 178919 179612
	Instances	m n Best	2 50 17927	2 100 37539	2 200 74474	2 500 180849

Table 2 .

 2 10 Best Makespan/ C

max obtained among All GAs Comparing to AVtoTS and AV+toTS

  [START_REF] Ghanbari | A Priority based Job Scheduling Algorithm in Cloud Computing[END_REF] , which is valid when we have a positive C 3.40 in the right side of the equality. Therefore(3.40) is valid for P in all cases.Here, C 3.40 can be bounded by C H max where job j 1 runs before job j 2 . In the worst case we havey j 2 + p min j 2 ≤ y j 1 + C 3.40 .Remark that in case 3 we can reduce the value of C 3.40 by this value (p maxj 1 + p max j 2 -C H max )when job j 1 and job j 2 run at the same time, this value can be a coecient for the variable

z j 1 j 2 . Thus, we can improve (3.40) by inequality

(3.41)

Table 3 .

 3 1 Results

Table 3 .

 3

	2 Results

Table 3 .

 3 3 Average Relative Percentage Gap between Optimal Solution and Obtained Solution.

  1 , b 1 )) is maximum. By greedy search we continue for nding sequentially c 1 and c. By considering 2-net, if the value of e∈Enet\E h net by the following way : By adding a vertex (c ) connected to the vertex c.

	net z * e -e∈Enet\E h net	z * e is greater than 6, then we try to extend into
	3-

  4.5. Conclusion|J| m Method CPU Nb Nodes ct BC ct UMB ct H ct Q ct NN ct NT o/p

	10 2	0	15,4	41866,8	0	0	0	0	0	5/5
	10 2	1	15,2	35862,2	177,6	0	0	0	0	5/5
	10 2	2	15,4	40972,6	0	35,6	0	0	0	5/5
	10 2	3	13,6	35867,8	0	0	67,2	0	0	5/5
	10 2	4	15,2	41925	0	0	0	10,8	0	5/5
	10 2	5	15,4	41866,8	0	0	0	0	0	5/5
	10 2	6	18	45625,2	0	0	0	0	42,4 5/5
	10 2	7	13,8	30941,4	138,2	12,6	56,8 11	24,4 5/5
	10 4	0	0,6	2189,6	0	0	0	0	0	5/5
	10 4	1	0,8	2125,8	57,6	0	0	0	0	5/5
	10 4	2	0,6	1864,2	0	40	0	0	0	5/5
	10 4	3	0,8	1958	0	0	39,6	0	0	5/5
	10 4	4	0,6	2189,6	0	0	0	0	0	5/5
	10 4	5	0,6	2189,6	0	0	0	0	0	5/5
	10 4	6	0,6	1801,8	0	0	0	0	38,4 5/5
	10 4	7	0,8	1837,8	31,4	18,6	29,6	0	25,6 5/5
	10 6	0	0,4	980	0	0	0	0	0	5/5
	10 6	1	0,4	1046,8	38	0	0	0	0	5/5
	10 6	2	0,4	1107,2	0	40,2	0	0	0	5/5
	10 6	3	0,4	1245,4	0	0	31	0	0	5/5
	10 6	4	0,4	980	0	0	0	0	0	5/5
	10 6	5	0,4	980	0	0	0	0	0	5/5
	10 6	6	0,2	1075,2	0	0	0	0	23,2 5/5
	10 6	7	0,4	1294,2	23,2	18,8	28,4	0	23	5/5
	10 8	0	0,6	1461,4	0	0	0	0	0	5/5
	10 8	1	0,2	1060	28	0	0	0	0	5/5
	10 8	2	0,2	1018	0	30,8	0	0	0	5/5
	10 8	3	0,2	1104,4	0	0	33,4	0	0	5/5
	10 8	4	0,6	1461,4	0	0	0	0	0	5/5
	10 8	5	0,6	1461,4	0	0	0	0	0	5/5
	10 8	6	0,4	1312,4	0	0	0	0	37,8 5/5
	10 8	7	0,2	971,4	17,8	20,6	23,2	0	21,8 5/5

Table 4 .

 4

	1 Results for 10 jobs with dierent methods

Contents 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 5.2 Generalized open shop problem with jobs disjunctive constraints109 5.2.1 Integer linear programming formulation . . . . . . . . . . . . . 109 5.2.2 Valid inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . 110 5.2.3 Experimental results . . . . . . . . . . . . . . . . . . . . . . . . 113 5.3 Open shop problem . . . . . . . . . . . . . . . . . . . . . . . . . 115 5.3.1 Integer linear programming formulation . . . . . . . . . . . . . 116 5.3.2 Valid inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . 118 5.3.3 Experimental results . . . . . . . . . . . . . . . . . . . . . . . . 121 5.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

Table 5 .

 5 1 Results of the generalized open shop model

Table 5 .

 5 1 presents the results of the generalized open shop problem. The entries of this table were shown before.

Table 5 .

 5 2 Number of optimal solutions obtained.

	name	method CPU LB ILP UB ILP lb ub	nodes	Status
	taillard7 7 0	0	3600	410	435	435 438 2280194 AbortTimeLim
	taillard7 7 0	1	12	435	435	435 438 20001	Optimal
	taillard7 7 0	2	1288	435	435	435 438 1417451	OptimalTol
	taillard7 7 0	3	136	435	435	435 438 126604	Optimal
	taillard7 7 0	4	3600	427	435	435 438 3953672 AbortTimeLim
	taillard7 7 0	5	2	435	435	435 438	1482	Optimal
	taillard7 7 0	6	55	435	435	435 438 84226	Optimal
	taillard7 7 1	0	3600	436	443	443 449 3877579 AbortTimeLim
	taillard7 7 1	1	5	443	443	443 449	7161	Optimal
	taillard7 7 1	2	3600	431	443	443 449 3141616 AbortTimeLim
	taillard7 7 1	3	227	443	443	443 449 252160	Optimal
	taillard7 7 1	4	3600	436	443	443 449 1755340 AbortTimeLim
	taillard7 7 1	5	6	443	443	443 449	3029	Optimal
	taillard7 7 1	6	305	443	443	443 449 276375	Optimal
	taillard7 7 2	0	1394	468	468	468 479 1600501	OptimalTol
	taillard7 7 2	1	470	468	468	468 479 1065452	Optimal
	taillard7 7 2	2	3600	429	468	468 479 2763775 AbortTimeLim
	taillard7 7 2	3	14	468	468	468 479 10898	Optimal
	taillard7 7 2	4	109	468	468	468 479 91748	OptimalTol
	taillard7 7 2	5	30	468	468	468 479 15622	Optimal
	taillard7 7 2	6	26	468	468	468 479 14559	Optimal
	taillard7 7 3	0	52	463	463	463 467 61095	OptimalTol
	taillard7 7 3	1	25	463	463	463 467 55909	Optimal
	taillard7 7 3	2	3600	457	463	463 467 3753894 AbortTimeLim
	taillard7 7 3	3	3	463	463	463 467	3605	Optimal
	taillard7 7 3	4	3600	439	463	463 467 1960948 AbortTimeLim
	taillard7 7 3	5	5	463	463	463 467	2717	Optimal
	taillard7 7 3	6	7	463	463	463 467	4017	Optimal
	taillard7 7 4	0	96	416	416	416 419 113490	OptimalTol
	taillard7 7 4	1	7	416	416	416 419 11797	Optimal
	taillard7 7 4	2	111	416	416	416 419 108925	Optimal
	taillard7 7 4	3	4	416	416	416 419	3190	Optimal
	taillard7 7 4	4	1377	416	416	416 419 1467035	OptimalTol
	taillard7 7 4	5	2	416	416	416 419	1659	Optimal
	taillard7 7 4	6	5	416	416	416 419	4074	Optimal
	taillard7 7 5	0	3600	439	451	451 460 2153465 AbortTimeLim
	taillard7 7 5	1	893	451	451	451 460 1702917	Optimal
	taillard7 7 5	2	104	451	451	451 460 157809	Optimal
	taillard7 7 5	3	120	451	451	451 460 158977	Optimal
	taillard7 7 5	4	3600	401	451	451 460 1839871 AbortTimeLim
	taillard7 7 5	5	34	451	451	451 460 19285	Optimal
	taillard7 7 5	6	33	451	451	451 460 20461	Optimal
	taillard7 7 6	0	1143	422	422	422 435 962496	OptimalTol
	taillard7 7 6	1	169	422	422	422 435 307675	Optimal
	taillard7 7 6	2	169	422	422	422 435 152148	Optimal
	taillard7 7 6	3	10	422	422	422 435 11140	Optimal
	taillard7 7 6	4	3600	404	422	422 435 1694336 AbortTimeLim
	taillard7 7 6	5	21	422	422	422 435 12358	Optimal
	taillard7 7 6	6	37	422	422	422 435 28226	Optimal
	taillard7 7 7	0	35	424	424	424 426 60107	OptimalTol
	taillard7 7 7	1	0	424	424	424 426	0	Optimal
	taillard7 7 7	2	3600	420	424	424 426 4260918 AbortTimeLim
	taillard7 7 7	3	34	424	424	424 426 67727	Optimal
	taillard7 7 7	4	26	424	424	424 426 28765	OptimalTol
	taillard7 7 7	5	1	424	424	424 426	521	Optimal
	taillard7 7 7	6	78	424	424	424 426 127959	Optimal
	taillard7 7 8	0	254	458	458	458 460 198988	OptimalTol
	taillard7 7 8	1	0	458	458	458 460	883	Optimal
	taillard7 7 8	2	2401	458	458	458 460 2874228	Optimal
	taillard7 7 8	3	1	458	458	458 460	1224	Optimal
	taillard7 7 8	4	1422	458	458	458 460 931297	OptimalTol
	taillard7 7 8	5	2	458	458	458 460	1433	Optimal
	taillard7 7 8	6	2	458	458	458 460	1768	Optimal
	taillard7 7 9	0	120	398	398	398 400 144714	OptimalTol
	taillard7 7 9	1	0	398	398	398 400	731	Optimal
	taillard7 7 9	2	3600	369	398	398 400 1984622 AbortTimeLim
	taillard7 7 9	3	4	398	398	398 400	4252	Optimal
	taillard7 7 9	4	15	398	398	398 400 15112	OptimalTol
	taillard7 7 9	5	0	398	398	398 400	0	Optimal
	taillard7 7 9	6	2	398	398	398 400	3047	Optimal

Table 5 .

 5 3 Number of optimal solutions obtained.

	name	method time LB ILP UB ILP gap lb ub	nodes	status
	taillard15 15	7	1233	937	956	1.99 937 956 16338	MemLimFeas
	taillard15 15	8	3572	937	937	0.00 937 956 72686	Optimal
	taillard15 15	9	3600	937	947	1.06 937 956 517809 AbortTimeLim
	taillard15 15	10	2638	937	937	0.00 937 956 475219	Optimal
	taillard15 15	7	3600	918	939	2.24 918 957 34301 AbortTimeLim
	taillard15 15	8	3600	918	954	3.77 918 957 59266 AbortTimeLim
	taillard15 15	9	1550	918	949	3.27 918 957 76726	MemLimFeas
	taillard15 15	10	3600	918	933	1.61 918 957 610624 AbortTimeLim
	taillard15 15	7	952	871	897	2.90 871 899 16983	MemLimFeas
	taillard15 15	8	3600	871	896	2.79 871 899 54762 AbortTimeLim
	taillard15 15	9	462	871	871	0.00 871 899 82995	Optimal
	taillard15 15	10	3600	871	872	0.11 871 899 505148 AbortTimeLim
	taillard15 15	7	1450	934	942	0.85 934 946 27800	MemLimFeas
	taillard15 15	8	3600	934	937	0.32 934 946 52356 AbortTimeLim
	taillard15 15	9	3600	934	940	0.64 934 946 364704 AbortTimeLim
	taillard15 15	10	1518	934	934	0.00 934 946 255462	Optimal
	taillard15 15	7	3600	946	990	4.44 946 992 19375 AbortTimeLim
	taillard15 15	8	3600	946	990	4.44 946 992 54201 AbortTimeLim
	taillard15 15	9	3600	946	949	0.32 946 992 222656 AbortTimeLim
	taillard15 15	10	3600	946	969	2.37 946 992 577703 AbortTimeLim
	taillard15 15	7	1336	933	956	2.41 933 959 20458	MemLimFeas
	taillard15 15	8	3600	933	955	2.30 933 959 48663 AbortTimeLim
	taillard15 15	9	299	933	933	0.00 933 959 54583	Optimal
	taillard15 15	10	3525	933	933	0.00 933 959 557028	Optimal
	taillard15 15	7	793	891	928	3.99 891 931 14393	MemLimFeas
	taillard15 15	8	3600	891	925	3.68 891 931 92441 AbortTimeLim
	taillard15 15	9	3600	891	893	0.22 891 931 948307 AbortTimeLim
	taillard15 15	10	3600	891	897	0.67 891 931 993133 AbortTimeLim
	taillard15 15	7	619	893	916	2.51 893 916 14173	MemLimFeas
	taillard15 15	8	3600	893	900	0.78 893 916 94041 AbortTimeLim
	taillard15 15	9	455	893	893	0.00 893 916 108151	Optimal
	taillard15 15	10	1613	893	893	0.00 893 916 414890	Optimal
	taillard15 15	7	3600	899	911	1.32 899 951 95415 AbortTimeLim
	taillard15 15	8	3600	899	943	4.67 899 951 109120 AbortTimeLim
	taillard15 15	9	3600	899	900	0.11 899 951 877150 AbortTimeLim
	taillard15 15	10	3600	899	914	1.64 899 951 1046262 AbortTimeLim
	taillard15 15	7	631		12226			MemLimInfeas
	taillard15 15	8	3600	902	931	3.11 902 935 99270 AbortTimeLim
	taillard15 15	9	431	902	902	0.00 902 935 98569	Optimal
	taillard15 15	10	3600	902	912	1.10 902 935 1166219 AbortTimeLim

Table 5 .

 5 4 Number of optimal solutions obtained.

	name	method time LB ILP UB ILP gap	lb	ub	nodes	status
	taillard20 20 0	7	3600		1210		1155 1215	AbortTimeLim
	taillard20 20 0	8	3091				1155 1215	MemLimInfeas
	taillard20 20 0	9	440				1155 1215	MemLimInfeas
	taillard20 20 0	10	3600	1155	1203	4.16 1155 1215 418184 AbortTimeLim
	taillard20 20 1	7	894				1241 1332	MemLimInfeas
	taillard20 20 1	8	3602				1241 1332	MemLimInfeas
	taillard20 20 1	9	882	1241	1331	7.25 1241 1332 26232 MemLimFeas
	taillard20 20 1	10	3600	1241	1331	7.25 1241 1332 95021 AbortTimeLim
	taillard20 20 2	7	3600				1257 1294	AbortTimeLim
	taillard20 20 2	8	731				1257 1294	MemLimInfeas
	taillard20 20 2	9	270	1257	1292	2.78 1257 1294 17669 MemLimFeas
	taillard20 20 2	10	3600				1257 1294	AbortTimeLim
	taillard20 20 3	7	2412				1248 1310	MemLimInfeas
	taillard20 20 3	8	929				1248 1310	MemLimInfeas
	taillard20 20 3	9	689	1248	1309	4.89 1248 1310 20594 MemLimFeas
	taillard20 20 3	10	3600	1248	1310	4.97 1248 1310 92297 AbortTimeLim
	taillard20 20 4	7	3600				1256 1301	AbortTimeLim
	taillard20 20 4	8	2929				1256 1301	MemLimInfeas
	taillard20 20 4	9	3600	1256	1300	3.50 1256 1301 282077 AbortTimeLim
	taillard20 20 4	10	3600				1256 1301	AbortTimeLim
	taillard20 20 5	7	3600				1204 1252	AbortTimeLim
	taillard20 20 5	8	2841				1204 1252	MemLimInfeas
	taillard20 20 5	9	310	1204	1242	3.16 1204 1252 18846 MemLimFeas
	taillard20 20 5	10	3262	1204	1250	3.82 1204 1252 415290 MemLimFeas
	taillard20 20 6	7	3600				1294 1352	AbortTimeLim
	taillard20 20 6	8	2778				1294 1352	MemLimInfeas
	taillard20 20 6	9	400	1294	1352	4.48 1294 1352 18467 MemLimFeas
	taillard20 20 6	10	3600	1294	1351	4.40 1294 1352 94174 AbortTimeLim
	taillard20 20 7	7	3600				1169 1269	AbortTimeLim
	taillard20 20 7	8	1295				1169 1269	MemLimInfeas
	taillard20 20 7	9	3600				1169 1269	AbortTimeLim
	taillard20 20 7	10	3600	1169	1258	7.61 1169 1269 107821 AbortTimeLim
	taillard20 20 8	7	3600				1289 1322	AbortTimeLim
	taillard20 20 8	8	2611				1289 1322	MemLimInfeas
	taillard20 20 8	9	572	1289	1322	2.56 1289 1322 20666 MemLimFeas
	taillard20 20 8	10	3600	1289	1322	2.56 1289 1322 102128 AbortTimeLim
	taillard20 20 9	7	3600				1241 1284	AbortTimeLim
	taillard20 20 9	8	806				1241 1284	MemLimInfeas
	taillard20 20 9	9	413	1241	1280	3.14 1241 1284 18195 MemLimFeas
	taillard20 20 9	10	3600	1241	1284	3.46 1241 1284 106041 AbortTimeLim

Table 5 .

 5 5 Number of optimal solutions obtained.

Start with some P ⊆ P c (G).

end

endCrossover The process of replacing some of the genes of one parent by corresponding ones of the other parent is known as crossover. Here this operator is carried out based on a linear crossover from a single point. This operator is applied to the selected

h = {(5,

[START_REF] Wang | Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics[END_REF],(5,[START_REF] Hsu | Unrelated parallelmachine scheduling with rate-modifying activities to minimize the total completion time[END_REF], (6, 7)}.

∪ BC , minus two times the value of edges BC i . The running time of the exact algorithm in the worst case bounded by O(n 7 )

× 1 + 3 × 4 +

× 6 = 25. The second sequencing is 2 × 2 + 1 ×

+ 3 × 6 = 25. It is clear that the order will not aect the value j∈J i (y j + p ij ) × p ij .

Acknowledgments

 [START_REF] Hart | Evolutionary scheduling : A review[END_REF], [START_REF] Dogan | Genetic algorithm based scheduling of meta-tasks with stochastic execution times in heterogeneous computing systemst1[END_REF]4), [START_REF] Dogan | Genetic algorithm based scheduling of meta-tasks with stochastic execution times in heterogeneous computing systemst1[END_REF]5) }. [START_REF] Hart | Evolutionary scheduling : A review[END_REF][START_REF] Hsu | Unrelated parallelmachine scheduling with rate-modifying activities to minimize the total completion time[END_REF], (5,[START_REF] Hsu | Unrelated parallelmachine scheduling with rate-modifying activities to minimize the total completion time[END_REF] }.

E c u = {(2, 4), [START_REF] Hart | Evolutionary scheduling : A review[END_REF]5), (4,[START_REF] Wang | Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics[END_REF]}. [START_REF] Izakian | Metaheuristic based scheduling metatasks in distributed heterogeneous computing systems[END_REF][START_REF] Hart | Evolutionary scheduling : A review[END_REF], [START_REF] Hart | Evolutionary scheduling : A review[END_REF]4), (4,5), (5,[START_REF] Wang | Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics[END_REF], [START_REF] Dogan | Genetic algorithm based scheduling of meta-tasks with stochastic execution times in heterogeneous computing systemst1[END_REF][START_REF] Wang | Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics[END_REF], (4,[START_REF] Hsu | Unrelated parallelmachine scheduling with rate-modifying activities to minimize the total completion time[END_REF] }. [START_REF] Wang | Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics[END_REF][START_REF] Hsu | Unrelated parallelmachine scheduling with rate-modifying activities to minimize the total completion time[END_REF], [START_REF] Izakian | Metaheuristic based scheduling metatasks in distributed heterogeneous computing systems[END_REF]5), [START_REF] Izakian | Metaheuristic based scheduling metatasks in distributed heterogeneous computing systems[END_REF][START_REF] Wang | Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics[END_REF], [START_REF] Hart | Evolutionary scheduling : A review[END_REF][START_REF] Wang | Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics[END_REF] }.

Remark that the graph induced by

When m = 2, the triangle becomes a forbidden subgraph (and then it is not possible to nd an umbrella). For this forbidden subgraph we focus on instance where m ≥ 3.

When m = 3, in order to keep all edges of E u it is necessary to add at least one edge of

Moreover, when we add an edge from E c u in this case the subgraph contains a clique of size 4. If we add an edge from E h u , then the induced subgraph will contain a hole. Thus, the valid inequalities when m = 3 will be : Let e 1 , e 2 ∈ E a u \ {(4, 7)}. The solutions I 1 = E u \ {e 1 } and I 2 = E u \ {e 2 } are valid and the incidence vectors z I 1 and z I 2 verify the inequality (4.3) to equality. Moreover, we have az I 1 =az I 2 . Hence, bz I 1 =bz I 2 . This implies that b(e 1 ) = b(e 2 ). We set b(e 1 ) = ρ. As The solutions

are valid and the incidence vectors z I 7 , and z I 8 verify the inequality (4.3) to equality. Moreover, we have az I 7 =az I 8 . Hence bz I 7 =bz I 8 . This implies that b(e) = 0 ∀e ∈ E i u .

Let e ∈ {(2, 7), [START_REF] Hart | Evolutionary scheduling : A review[END_REF][START_REF] Hsu | Unrelated parallelmachine scheduling with rate-modifying activities to minimize the total completion time[END_REF], (1, 7), (5, 7), (6, 7)}. The solutions I 1 and I 9 = I 1 ∪ {e} are valid and the incidence vectors z I 1 , z I 9 verify the inequality (4.3) to equality. Moreover, we have az

When m ≥ 4, to nd a valid solution we can add also the edges from E c u . Then, the valid inequalities when m ≥ 4 will be : We show that b = ρa for some ρ ∈ R.

Let e 1 , e 2 ∈ E t u ∪ E c u be two edges, where e 1 = e 2 . We consider the edge sets I 1 = E u ∪ {e 1 } and I 2 = E u ∪ {e 2 } where the incidence vectors z I 1 and z I 2 are solutions of P I (G, m) and satisfy the inequality (4.4) to equality. Moreover, we have az I 1 =az I 2 . Thus, bz I 1 =bz I 2 . This implies that b(e 1 ) = b(e 2 ). As e 1 , e 2 are arbitrary, then b(e) = b(e ) for all e, e ∈ E t u ∪ E c u .

(u i , u i+1 ) is an edge, where i ∈ {1, 2, ..., |C| -1}. Now, we will construct C from C by adding the vertex u |C|+1 in C, by replacing the edge (u i , u i+1 ) by (u i , u |C|+1 ) and (u |C|+1 , u i+1 ).

Then, we nd a unique hole of a size 4 in the new cycle. Therefore,

It is necessary to add one edge to break this hole. Thus, k c = l -3 is true. As C and k c are arbitrary, then the property is true for every hole. Indeed, if we add one chord to C ⊂ {e}, then we will obtain a triangle or another cycle and it is not valid for m = 2. Remark that this inequality for m = 2 is equivalent to the clique inequalities described in the next subsection.

If m ≥ 3, then inequality (4.8) is valid. vertex 4, after the best weighted 5 until the umbrella constructed. If it is violated by z * we will add the inequality. This heuristic has O(n 2 ) running time. (a) Basic nodes for BC

Hole separation

Now, we explain the hole separation algorithm, which is based on a greedy approach. In the solution represented by vector z * ∈ R |E| . The separation algorithm consists in nding a forbidden subgraph hole, such that the associated inequality is violated by z * . If the associated inequality violated by z * will be then added to the linear program. Thus, we search a hole of size C where holeC ⊆ E such that e∈C (|C| -3)z e -e∈C z e > (|C| -1)(|C| -3).

The algorithm starts by the edge (u 1 ,u 2 ) with w((u 1 , u 2 )) is maximum (see Figure 4.10). By a greedy search, we try to nd the vertex u 3 such that w((u 2 , u 3 )) -w((u 1 , u 3 )) is maximum. With the same process, we search a sequence of vertices u 4 , ..., u n . In each step, we consider the cycle where we connect u 1 to u n . We nd a hole where the associated inequality is violated and then we add it.

If e∈C (|C| -3)z e -e∈C z e ≤ (|C| -1)(|C| -3) where C is the incident cycle, then we stop the algorithm since we cannot nd a cycle where the associated inequality is violated.

Clique separation

In this subsection we explain the clique separation algorithm. The vector z * ∈ R |E| represents the solution. The clique separation algorithm consists in nding a clique, such that the associated inequality is violated by z * . If the associated inequality is violated by z * , then this inequality will be added to the linear program. Thus, we search a clique of size

)

)

)

The objective function is to minimize the makespan. Inequalities (5.1) ensure that the beginning time for each job plus its processing time is less than or equal to the total completion time. Inequalities (5.2) and inequalities (5.3) guarantee that there is no two jobs run on the same machine at the same time and control the linear ordering. Inequalities (5.4) ensure that if two jobs are linked by an edge in the compatibility graph, then they do not run at the same time. Indeed, these two jobs j 1 , j 2 either j 1 before j 2 or j 2 before j 1 . Inequalities (5.5) ensure the three possibilities : j 1 before j 2 or j 2 before j 1 or they run at the same time. Inequalities (5.6) and (5.7) guarantee that the induced subgraphs are interval and m-clique free subgraphs. The number of inequalities may be exponential and thus we will use the separating algorithm presented in Chapter 4.

Valid inequalities

To strength the model in this section we propose some valid inequalities to (P GOS ).

Sequence inequalities

Considering every i ∈ M , we introduce the following valid inequalities :

C max is bounded by the sum of the processing times of its previous jobs, plus its processing time, plus the sum of the processing times of all next jobs. This class of inequalities is very interesting when we have jobs with long processing times, because we can avoid some empty slots on other machine.

Logical implication inequalities

Considering these jobs j 1 , j 2 , j 3 ∈ J, we introduce the following valid inequalities :

(5. [START_REF] Pinedo | Planning and scheduling in manufacturing and services[END_REF] In this valid inequalities, we apply the logical implication. If job j 1 is before job j 2 and job j 2 is before job j 3 , then job j 1 is before job j 3 .

Experimental results

The entries of the Nodes : The number of nodes in the branching tree. gap : The gap between the lower bounds and the upper bounds (100 × U B-LB LB ), o/p : the number of instances solved (5 instances over 5 or 0 over 5) by (P OS ) :

)

)

)

The objective function is to minimize the makespan. Inequalities (5.15) ensure that the starting time for each operation plus its processing time is less than or equal to the total completion time. Inequalities (5.16)

start after the completion of operation O ij 1 on the same machine. Inequalities (5.17) guarantee that if operation of job j runs on machine i 1 before its operation on machine i 2 , then the starting time of O i 2 ,j must be after the completion of operation O i 1 ,j . Inequalities (5.18) and (5.19) guarantee the linear ordering of the operations on the same machine and the linear ordering of the operations of the same job.

We also use the conditional constraints for inequalities (5.2) and (5.3). We can write these two constraints as follows :

(5.21)

Inequalities (5.20) imply that if job j 1 is before job j 2 , then it implies that, the starting time of job j 2 must be after the completion time of job j 1 . The conditional inequalities 5.21 test if the operation of job j on machine i 1 is before the operation of the same job on machine i 2 , then the starting time of the operation of job j on machine i 2 must be after the completion of the operation of job j on machine i 1 . Adding the conditional inequalities will remove the big M (C), but the solver must branch on these conditions. We will explain the results of using conditional inequalities in the section dedicated to the experimental results.

Valid inequalities

In this section, we derive various classes of valid inequalities for the integer linear programming model. In these derived inequalities, we consider the sequence of jobs on the machines, the relation between a job and its previous ones as in [START_REF] Bekrar | An improved heuristic and an exact algorithm for the 2D strip and bin packing problem[END_REF] and we consider a logical implication. We adapted the classes of valid inequalities introduced in Section 5.2.2.

Sequence inequalities

Considering job j ∈ J, we introduce the following valid inequalities : i∈M (y i,j + p ij ) × p ij ≥ SC j , (5.23) where SC j is equal to the sum of C i,j ×p ij where C i,j is the completion time of operation O i,j in any sequence. With the same idea, we can dervie similar valid inequalities for every subset of operations of job j.

By symmetry, let i ∈ M . The following valid inequalities hold :

where SC i is equal to the sum of C i,j × p ij by varying j, and C i,j is the completion time of O i,j in any sequence.

Having ỹi,j = C max -y i,j , and form the valid inequalities (5.24), we can derive that j∈J p ij (ỹ i,j ) ≥ SC i . Thus, we deduce that :

Therefore, the following relation holds :

These valid inequalities can lead to similar inequalities (5.23) for all jobs j ∈ J :

Experimental results

The experimental results were performed for several sets of instances. First, we report the instances of Taillard. In these instances, every operation is assigned to a given machine without considering the order of the operations. Detailed description about this instances is available in [START_REF] Taillard | Benchmarks for basic scheduling problems[END_REF]. The entries of the table are : name : name of the instance method : 0 basic model ;1 sequence inequalities, and logical implication ;2 conditional inequalities ; 3 previous inequalities ;4 logical implication ;5 all inequalities[1 to 4] ; 6 only conditional and previous job ; 7 : add(1,3,4) ; 8 : add(1,2,3,4) ; 9 :add(1,3) ; 10 : add(1,2,3). CPU : cpu time (limit 1 hour). LB ILP : lower bound found by our model. UB ILP : upper bound found by our model. LB : lower bound given in the le of the instance. UB : upper bound given in the le of the instance. Nb Nodes : number of nodes in the branching tree. Status : AbortTimeLim : No solution found within the 1 hour ; Optimal : found optimal solution ; MemLimInfeas : The limited memory not enough for more branching.

In order to show the eciency of our inequalities and to see the dierence between all inequalities we used CPLEX 12.4 solver with JAVA on DualCorei7, CPU 2.4 GHz. Tables 5.2, 5.3, 5.4 and 5.5 report the obtained results for the Open Shop model and its valid inequalities for dierent sized problems. In Table 5.2, it is clear that the basic model does not solve all problems within the limited resources (time and RAM). When we add the conditional and previous inequalities, the solutions for all instances are obtained within reasonable computation time. However, when we add the conditional inequalities alone, or the previous inequalities alone, they do not solve all the problems, but they just solve 50% of 77 problems. The logical implication inequalities do not show an important improvement to the basic model when these inequalities are added alone. We can also see that when we add all the inequalities, all problems are solved within the best CPU time. From these results, we can say that the addition of all the families of inequalities improved the computation time of the basic model. In Table 5.3, we tested another combination of inequalities to solve the instances (10 10). From the obtained results, we can also observe that all the problems have been solved except one problem (not solved within one hour) another interesting topic regarding scheduling problem in cloud computing is to consider the multiobjective optimization context.