Christoph D Ürr

Julien Moncel

André Rossi

Foremost, I would like to express my sincere

Titre : Ordonnancement parallèle avec contraintes de précédence Mots clés : Ordonnancement, complexité, contraintes de précédence Résumé : Dans cette thèse, nous considérons une famille des problèmes d'ordonnancement avec machine parallèle identique et contraintes de précédences. Ce champ de recherche fait l'objet de nombreuses études. Malgré tout, la complexité de ces problèmes varie selon de nombreux paramètres, notamment le type de graphe de précédence ou le critère retenu. De plus, il existe encore de nombreux problèmes ouverts. Nous étudions certains de ces problèmes dans cette thèse. Nous montrons notamment que le problème ouvert avec tâches de durée unitaires et graphe de précédence de type intree est NP-complet. Puis, nous prouvons que le problème avec graphe de précédence de type levelorder est NP-complet aussi. La preuve est ensuite étendue à des problèmes connexes.

Par la suite, on améliore un algorithme exponentiel pour un problème spécifique qui est NP-complet. Enfin, nous proposons un modèle linéaire pour le problème avec contraintes de précédence quelconque, améliorant aussi les résultats de littérature.

Title : Parallel machine scheduling with precedence constraints Keywords : Scheduling, complexity, precedence constraints Abstract : The main problem studied in this thesis is that of parallel machine scheduling with precedence constraints. The complexity depends on the shape that the precedence graph takes and the objective function. We prove that one minimum-open problem of scheduling equal-processing-time jobs which subject to in-tree precedence constrains is NPcomplete while minimizing the total competition time. Then, we prove that the open problem of scheduling level-order precedence constrains is NP-complete too. We adapted the second proof to other scheduling problems as well.

On the other hand, we improved an exponential algorithm designed for a specific NP-hard problem. At the end, we propose a linear programming model for the general scheduling problem with arbitrary precedence constraints and processing-time. We adapt the existing models which are originally designed for other scheduling problems to parallel scheduling problem and compare these models with ours.

List of Tables

1. 1 An overview of open parallel scheduling problems with equal-processing-time jobs . . . . . . . The scheduling theory is widely applied in various scenarios such as manufacturing processes, practical computer systems, distribution settings, project management, etc. Thus, the scheduling problems are described as an allocation of resources to tasks over given time periods and its goal is to optimize one or more objectives in (Pinedo, 2012). This allocation indicates the information about the order of jobs to be executed, which is known as the sequencing problem when time is not considered. This thesis deals primarily with job-machine scheduling models, where the resources, such as real machines in workshop, processing units at a construction site, are modeled as machines and the tasks to be scheduled are modeled by jobs.

In scheduling problems, variables are usually considered as discrete. As a combinatorial optimization problem, a scheduling problem has various constraints and an objective function. In particular, constraints that we study include precedence constraints between jobs (or precedence relations in some literature). This relation between jobs can commonly be found in project management, logistics, routing, assembly flow, and networking. In precedence constraints, jobs are partially-ordered and can be represented by nodes in a directed acyclic graph (DAG). Jobs must be scheduled with respect to their priority order given by these constraints. Ordinarily, the objective function to minimize is the makespan (length) or the total completion time of all jobs. The makespan describes the utilization of machines while the total completion time reflects holding time (flow time) incurred by the schedule.

An early systematic mathematical study of scheduling problem can be traced back to the 60th [START_REF] Conway | Theory of scheduling. eading[END_REF]. Then, during the past 50 years, the scheduling theory has been developed in a variety of directions:

In terms of decision time, the scheduling problem exists in two forms: static (off-line) and dynamic (on-line). In static scheduling, the data, including jobs' processing times, precedence constraints and synchronizations, are known beforehand. On the opposite in dynamic scheduling, which is also referred to as real-time scheduling, few assumptions can be made before execution, and thus, scheduling decisions must be made on-the-fly. According to the fact that we are interested in complexity, we address only the static scheduling problem in this study.

In terms of number of machines, scheduling problems have single-machine and multi-resources versions. Recently, as the development of High-performance computing (HPC) is explored, it is widely recognized that multi-machine scheduling is becoming more and more important. We consider a special case of multi-machine scheduling problem: parallel scheduling, where machines are identical, which means each one can execute all the jobs with the same speed. This assumption does not necessarily hold in real world but could be seen as a simplified version of unrelated parallel machines (RM). It is significant as a lower bound. Another extensively studied multi-machines case is shop scheduling problem, where jobs have to be processed at different stages in series. When machines are partitioned into work centers for different stages, the model is called flexible or hybrid, and is a generalization of parallel scheduling problem as well because machines in each work center are used in parallel. The related research is so abundant that some valuable results can be applied to parallel scheduling.

For the general case, when the processing time and the precedence graph are arbitrary, the parallel scheduling problem is N P-complete, yet some specially simplified version can be optimally solved by a polynomial-time algorithm. A common simplification assumes that jobs are released at the beginning and have equal-processing-time (even unit-processing-time) and have no due date. However, the intractability also stems from the structure of the precedence graph to a large extent. A considerable amount of studies have been carried out since the 70th on the computational complexity of problems with specific precedence graphs [START_REF] Ullman | NP-complete scheduling problems[END_REF]. They reveal that the complexity varies with the form, such as chains or trees, that the precedence graphs take. Prot and Bellenguez-Morineau (2017) surveyed these relevant results and pointed out that there exists still great number of open problems. Hence, we focus on these open problems in this thesis. This work goes on with the age-old research issue of studying scheduling problems' complexity which aims for sake of clarifying and understanding the borderline between the "hard" and "easy" cases. As all efforts to find polynomial time algorithms for the N P-complete problems have failed, the significance is to close open problems in order to avoid wasteful attempt to optimally solve these N P-complete problems by a polynomial algorithm, unless P = N P . We give the proof of N P-completeness for some problems. The results of these works will have implications for range of practical applications which can be modeled by the parallel scheduling problem with precedence constraints.

Once a problem has been closed, a wide range of methods can be proposed to solve it. Polynomial algorithms are designed for tractable problems. Many of them choose a dispatching rule, such as the Shortest Processing Time (SPT) or Highest Level First (HLF). They are called list scheduling and can be used as heuristic or even approximate methods for intractable problems. Add to this, there exist several exponential methods. For general scheduling problems, some integer-programming-based models already exist. In the second part of this thesis, we study different existing models and adaptation in order to improve resolution of parallel scheduling problem and add precedence constraints. We propose a new model which requires less variables (space) and less time for a linear-programing solver such as CPLEX. Furthermore, exponential algorithms can be used to solve optimally N P-hard problems. These algorithms have an exponential complexity, where the exponents are widely the number of machines m. When m is fixed, the problem is polynomial solvable. We consider the problem where the precedence graph is an in-tree while minimizing the total completion time, and propose an improvement of an exact method for this problem.

In the following reminder we describe in detail the organization of this thesis: Chapter 1 defines the notion of scheduling problems, including different precedence constraints and a sketch of complexity results in literature.

Then, in part II, we present our N P-completeness results of different scheduling problems with unitprocessing time jobs. We first introduce the 3-Partition problem. Then, two scheduling problems, P |p j = 1, i.t.| C j and P |p j = 1, l.o., pmtn|C max , are separately considered in chapter 2 and 3. In the latter chapter, we adapt the proof to other scheduling problems as well.

Part III is dedicated to solve some N P-complete scheduling problems. We first study the problem P |p j = p, i.t.| C j in chapter 4. We put forward an algorithm which is both theoretically and experimentally faster than the existing algorithm. Then, chapter 5 is developed to model the general scheduling problem P |prec|C max . We adapted the existing models which are originally designed for other problems, and propose a new one. We compare their performance and show that our model outperforms the others.

Finally, in part IV, we conclude by presenting a synthesis of all the results and by providing perspectives.

Chapter 1

General framework

In this thesis, we consider deterministic and off-line scheduling problems. We consider mainly parallel scheduling problem with precedence constraints. In this chapter, we first present the notations and the framework of problems we study throughout this thesis. Then, we are interested in the relation between the precedence constraints and the complexity. So, we introduce in section 1.2 the different graphs that will be considered.

The general complexity result will be presented in section 1.3, while we point out the background where our research begins.

Notation

As mentioned, the scheduling problems are about allocating resources to a set of jobs over the time. We use J T to represent the set of all the n jobs to be scheduled. Similarly, a blackboard bold typeface such as J and X represent always a set of jobs. We use always j to represent a job throughout the text. The problems can be precisely described in terms of machines, constraints and objective function. Respectively, a triplet α|β|γ, called 3-field notation, is generally used to represent scheduling problems. This notation is introduced by Graham et al. (1979) and updated by Brucker (2007).

Machine environment

The machine environment is described by the α-field, in the following we will consider one of those cases: P parallel identical machines environment. Most problems studied in this thesis consider parallel machine environment, where machines have the same processing speed and no relationship between each other. The number of machines is represented by m throughout the text.

P m

The number of machines m is considered as a constant. If the variable m is chosen as a fixed parameter, some N P-hard problem may have polynomial algorithms.

profile In some studies, such as [START_REF] Dolev | Profile scheduling of opposing forests and level orders[END_REF], the number of available machines varies along the time as a function. This is called profile scheduling.

Constraints environment

The constraints environment is described by β-field:

prec The precedence constraints can be represented by a directed acyclic graph (DAG): G = (J T , E), where job j 1 precedes j 2 is represented by respectively j 1 ≺ j 2 or j 1 → j 2 . In some literature, it is represented by a partial order (≺, J T ), which is equivalent to a DAG.

Most particular structures of precedence constraints which are widely discussed are more intuitive when described by DAG, such as chains, trees, and forests to be presented in the next section, while some others are originally defined as a partial order, such as interval orders [START_REF] Fishburn | Interval orders and interval graphs: A study of partially ordered sets[END_REF]. As those representations are equivalent, to facilitate discussion, DAG are more generally used and also called precedence graphs. Precisely, when the precedence graph takes a particular structure, its acronym will replace the item prec. We will successively consider:

1. chains (ch.)

2. in-tree (i.t.)

3. out-tree (o.t.)

4. opposing forests (o.f.)

5. level-order (l.o.)

6. series parallel (s.p.)

Those particular graphs will be detailed in section 1.2.

pmtn During a schedule, preemption may be allowed, it means a job may be preempted by other job (s) and resumed later. We assume that the preemption and resumption of jobs are immediate and take no time.

r j Each job is given an integer release date r j , which is the moment of time when the job arrives, and it cannot start before r j .

dj Each job is given a deadline dj , as its name implies, it is the maximum completion time of one job in a feasible schedule. The term feasible is used to describe a schedule which satisfies all the constraints. d j A relaxation of deadline is the due date d j of jobs. It is not a constraint, but a committed completion date (Pinedo, 2012). A job that finishes after the due date is called a tardy job.

p j = p Each job requires a processing time, or execution time in some literature, represented by p j . A simplified case can be considered when they have equal processing time, noted as p j = p. A further simplified one is unit processing time, or UET in some literature, i.e. p j = 1. Those two cases are not distinguished when the release date, due date, and deadline are integer multiples of p.

Objective function

The γ-field describes the objective function, which may be:

C max The makespan, which is the largest completion time. The completion time of job j is note C j , then C max = max j∈J T C j . Besides, the starting time of job j in a schedule is represented as S j .

L max The maximum lateness, where the lateness of a job is defined as L j = C j -d j and L max = max j∈J T L j .

C j The total completion time, also named as total flow time or mean flow time in some literature when all jobs are released at the beginning as flow time is usually defined as C j -r j . When jobs are weighted differently, this can be written as w j C j , the total weighted completion time.

U j The number of tardy jobs where the binary U j takes value 1 if and only if job j is tardy, i.e. C j > d j .

When jobs are weighted differently, this can be written as w j U j .

T j The total tardiness, where the tardiness is defined as T j = max {L j , 0}. When jobs are weighted differently, this can be written as w j T j .

Precedence Graphs

In this section, we give the full definitions of the different precedence graphs that will be used in this study. First of all, we use the term predecessor and successor only in the sense of precedence constraints, to distinguish from the jobs executed before or after in a certain schedule. We define the job which does not have a successor (predecessor) as a final (initial) job.

The first considered graph is chains (abbrv. ch), where each job has at most one direct predecessor and at most one direct successor. An in-tree (abbrv. i.t.) is a connected graph where each job has at most one direct successor. In an opposite way, an out-tree (abbrv. o.t.) is a connected graph where each job has at most one direct predecessor.

It should be remarked that in some literature, the in-trees (out-trees) or in-forests (out-forests) is a collection of in-trees (out-trees). But by adding into this graph a dummy job which precedes (successes) all others, we combine the components 1 in a single in-tree (out-tree). It has been showed that non-delay schedule are dominant in [START_REF] Weiss | Scheduling: Theory, algorithms, and systems[END_REF], which means solutions without enforced idle time. So, this dummy job will clearly be scheduled right after (before) the schedule of the sub-components. Then, it is clear that in-trees can be transformed into an equivalent in-tree. So, only the term in-tree (out-tree) is used in this thesis. Nevertheless, a combination of in-tree and out-tree, which is defined as an opposing forest (abbrv. o.f.), is worth discussing. For the next definition, we consider the level in a graph. But it is defined using different ways in literature. It is sometimes confused with term height. We hereby choose the following definition:

The height of job j, h(j) is the length of the longest chain from j to a final job. The height of the graph is the largest height of job in this graph, noted as h. The level of job j, l(j) is recursively defined as:

l(j) = h if j is initial task in G min{l(p)|p ∈ pred(j)} -1 otherwise
Their difference can be seen in Figure 1.2. The term level represents the set of jobs on the same level when there is no ambiguity. Then, we may introduce the definition of a level-order graph, such that in each component, jobs on the same level precede all jobs of the next level. Finally, a more general class of graph which covers all the graphs above: series-parallel (abbrv. s.p.) [START_REF] Lawler | Sequencing jobs to minimize total weighted completion time subject to precedence constraints[END_REF] .

The relation between these classes can be seen in Fig. 1

(iii) F 2 || C max , (iv) Jm || C max , (v) F F c || C max .
The complexity hierarchy is depicted in Figure 2 As it can be seen, all objective functions are generated from two basic criteria: C max and C j . In this thesis, we study problems with these two basic objective functions for the most part.

(i) 1 || L max , (ii) 1 | prmp | L max , (iii) 1 | r j | L max ,
Considering the makespan [START_REF] Lenstra | Complexity of machine scheduling problems[END_REF] proved that the general problem, P 2||C max , is N Pcomplete even without any precedence for 2 machines while minimizing the makespan. Minimizing the total completion time seems to be more tractable: [START_REF] Bruno | Scheduling independent tasks to reduce mean finishing time[END_REF] proposed an optimal polynomial algorithm for a generalized problem without precedence constraints where machines are allowed to be unrelated, i.e. R|| C j . However, when the simplest precedence constraints, chains, are added, the problem (P 2|ch| C j or P 2|ch|C max ) is N P-complete no matter for total completion time or for makespan even with only two machines [START_REF] Du | Scheduling chain-structured tasks to minimize makespan and mean flow time[END_REF].

A common simplification is to consider the unit-processing-time jobs. However, the problem P |prec, p j = 1|C max is still N P-complete for arbitrary precedence constraints no matter whether preemption is allowed [START_REF] Ullman | Complexity of sequencing problems[END_REF] or not [START_REF] Ullman | NP-complete scheduling problems[END_REF]. But when the precedence graph is chains, in-tree, out-tree, level-order or opposing forests presented in the last subsection, the complexity results may change according to objective functions.

In the following two subsections, we present the complexity results separately for minimizing the makespan and total completion time, when focusing on equal-processing-time jobs.

Minimizing the makespan

Now, we consider the makespan as the objective function. A well-known scheduling algorithm is proposed by [START_REF] Coffman | Optimal scheduling for two-processor systems[END_REF]. It is termed as Coffman-Graham algorithm, or CG algorithm as well. This algorithm minimizes the makespan for two machines scheduling with an arbitrary precedence graph, P 2|prec, p j = 1|C max . This algorithm labels jobs according to certain rules. Then, it executes jobs with the largest labels when there are more than m available jobs. This kind of strategy is called list scheduling in some literature, because it gives jobs a priority order, and then simply executes jobs according to this order. Another well-know list scheduling algorithm which labels jobs according to their height in the precedence graph is proposed by [START_REF] Hu | Parallel sequencing and assembly line problems[END_REF]. It solves optimally the problem P |i.t., p j = 1|C max with unit-processingtime jobs when preemption is not allowed and the precedence graph is in-tree.

Then, as a reversed in-tree can be seen as an out-tree, Hu's algorithm can also be used to give a minimum makespan for out-tree precedence graph P |o.t., p j = 1|C max . After that, we could consider the generalization P |o.t., r j , p j = p|C max where jobs have release date and equal-processing-time. It can be optimally solved by an algorithm proposed by [START_REF] Brucker | Scheduling equal-length tasks under treelike precedence constraints to minimize maximum lateness[END_REF]. They also proved that another generalized problem P |o.t., p j = p|L max with due dates is N P-complete.

When it comes to the combination of in-tree and out-tree, called the opposing forest, the problem P |o.f., p j = 1|C max is proved N P-complete by [START_REF] Garey | Scheduling opposing forests[END_REF]. They proposed a polynomial algorithm when m is fixed. Another problem scheduling with level-order precedence graph, i.e. P m|l.o., p j = 1|C max is also polynomial solvable if m is fixed [START_REF] Dolev | Profile scheduling of opposing forests and level orders[END_REF]. However, when m is not fixed, the problem P |l.o., p j = 1|C max is still open.

Moreover, we can consider the case when preemption is allowed. The problem P |i.t., pmtn|L max and P |o.t., pmtn|L max are proved N P-complete by [START_REF] Lawler | Preemptive scheduling of. precedence-constrained jobs on parallel machines[END_REF]. When it comes to equal-processing-time jobs, i.e. P |o.t., pmtn, p j = 1|L max , the complexity is open.

Baptiste and Timkovsky (2001) showed that preemption is advantageous2 for minimizing the makespan. So, despite the complexity results of their non-preemptive version, problems P |l.o., pmtn, p j = 1|C max , P |o.f., pmtn, p j = 1|C max and P |o.t., pmtn, p j = 1|L max are open.

Minimizing the total completion time

In the literature, Hu's algorithm is cited as an optimal algorithm for solving the problem with out-tree precedence graph while minimizing the total completion time, though there is no definite proof in [START_REF] Hu | Parallel sequencing and assembly line problems[END_REF], which is dedicated for makespan, but it can be extended. Add to this, the generalized problem P |o.t., r j , p j = 1| C j is indeed polynomially solvable [START_REF] Brucker | A polynomial algorithm for P |p j = 1, r j , outtree| C j[END_REF].

On the other side, Hu's algorithm cannot optimally solve the problem for in-tree P |i.t., p j = 1| C j as Huo and Leung (2006) provided a counter-example. Although [START_REF] Baptiste | Ten notes on equal-processing-time scheduling[END_REF] find an algorithm for a fixed m, it is among the minimal open problems according to [START_REF] Knust | Complexity results for scheduling problems[END_REF] and Prot and Bellenguez-Morineau (2017). The problem is open for level-order or opposing forests too, even when m is fixed. Now, let us consider the problem with preemption. Preemption is useless for problem with chains precedence constraints even when jobs have arbitrary processing time [START_REF] Du | Scheduling chain-structured tasks to minimize makespan and mean flow time[END_REF]. [START_REF] Brucker | How useful are preemptive schedules?[END_REF] proved that it is even redundant3 for T j when there is no precedence. But for in-tree and out-tree, (Baptiste and Timkovsky, 2001) illustrated that preemption is advantageous. So, to the best of our knowledge, P |o.f., pmtn, p j = 1| C j and P |l.o., pmtn, p j = 1| C j are open.

Additional results

A considerable amount of researches about other graphs have been done as well.

The studies about interval order, where each job can be described by an interval and the precedence constraints are given by the relations between the intervals, are given by [START_REF] Papadimitriou | Scheduling interval-ordered tasks[END_REF], [START_REF] Möhring | Computationally tractable classes of ordered sets[END_REF] and [START_REF] Djellab | Scheduling preemptive jobs with precedence constraints on parallel machines[END_REF].

In bounded height graph, as its name suggests, the height of the graph is not larger than a given number. It is also a fixed parameter problem, where the parameter is chosen as the graph height. The studies about the complexity can be seen in [START_REF] Lenstra | Complexity of scheduling under precedence constraints[END_REF] and [START_REF] Dolev | Scheduling precedence graphs of bounded height[END_REF]. Some other graphs are not extensively studied. For example, Quasi interval order and over interval order are two extended version of interval order. They are defined and studied respectively in [START_REF] Moukrim | Non-preemptive profile scheduling and quasi interval orders[END_REF])

β γ C max C j L max i.

Conclusion

In this chapter, we presented a view on the state of the art of the computational complexity of the scheduling problems with specific precedence constraints and objective functions. Specific results to be used will be discussed later. According to the complexity hierarchies shown in Figure 1.5, in Table 1.1, we briefly remind the open problems with equal-processing-time jobs, i.e. P |p j = 1, β|γ, where () means the result derived directly from the complexity hierarchy.

One aim of the thesis is to close as much as possible open problems in this table. The last part will be dedicated to solve some N P-hard problems.

Part II

Computational complexity

In this part, we prove the N P-completeness of different scheduling problems with unit-processing time jobs. For the different proofs, we employ reductions from a well-known N P-complete problem: 3-Partition. An instance π 3P of the 3-Partition problem is defined as hereunder [START_REF] Garey | Computers and intractability[END_REF]: Definition 1. Let A be a set of 3q elements and B an integer, ∀a ∈ A, ∃w a ∈ Z + , B 4 < w a < B 2 and a∈A w a = qB. The decision question is whether there is a partition A 1 , A 2 , . . . , A q of A, such that a∈Ai w a = B, ∀i = 1, . . . , q.

WLOG, we assume that w a is an integer multiple of 10q 10 , i.e.

w a = 10q 10 w a w a ∈ Q (1.1)
This is because when each w a and B are multiplied by 10q 2 , the answer to the decision question does not change.

3-Partition is N P-complete in the strong sense [START_REF] Garey | Computers and intractability: a guide to np-completeness[END_REF], which enables us to construct a pseudo-polynomial transformation from π 3P to an instance of a given scheduling problem. This means the number of jobs n is polynomial in B , and therefore polynomial in B.

The reduction from 3-Partition to the scheduling problem consists of 2 steps. First, we transform any instance π 3P to a decision version of an instance of scheduling problem. Then, we prove that π 3P is a yes-instance if and only if the instance of scheduling problem is a yes-instance.

Chapter 2

P |p j = 1, i.t.| C j
This section discuses the problem P |p j = 1, i.t.| C j . We first transform any instance π 3P to an instance of this scheduling problem. Then, we prove the equivalence of these instances in the next two sections, which reveals the N P-completeness of the scheduling problem.

Transformation

We propose a pseudo-polynomial transformation. So, we build an instance of the scheduling problem with in-tree precedence constraints from π 3P . We set the number of machines m := 3q + 1 + B. First, we build some dummy jobs, named x-jobs. We define

m k := B + 3k -3 ∀k ≤ q + 1 K := B 5
The number of x-jobs on k th level is set as mm k and tree height is set as K 3 . The corresponding tree is presented in the Figure 2.1. Those x-jobs subject to in-tree precedence constraints. In that tree, we fix for any k ≤ q + 1,

x 1 k-1 ≺ x 1 k , x 2 k-1 ≺ x 1 k and x 3 k-1 ≺ x 1 k . Then, ∀i ∈ {4, 5, . . . , m -m k-1 }, we set x i k-1 ≺ x i-3 k .
Thereafter, for ∀k ∈ {q + 2, q + 3, . . . , K 3 }, x k-1 ≺ x k , so, this part forms a chain.

Thereafter, for each a ∈ A of π 3P , we create two sets of jobs, which are u-jobs and v-jobs: u 1 a , u 2 a , . . . , u wa a , and v 1 a , v 2 a , . . . , v Kwa a . All the u-jobs precede directly v 1 a , i.e. ∀i ≤ w a , u i a ≺ v 1 a . Subsequent to that, we set v i a ≺ v i+1 a , ∀i < Kw a , so, they form a chain. The corresponding tree of the u-jobs and v-jobs for a given a ∈ A can be observed in the Figure 2.2. As there are 3q elements in A, they form 3q in-tree components.

Thus, we transformed π 3P to an instance π i.t. of the considered scheduling problem. The construction is made in polynomial time of B and q (pseudo-polynomial). We build a decision version π Cj i.t. by asking: whether π i.t. has a schedule such that C j ≤ T CT * , where:

T CT * := q i=1 i(3(q + 1 -i) + 1) + K 3 i=q+1 i + B q i=1 i + a∈A Kwa i=1 i + KB q i=1 i
To establish the N P-completeness, we hereafter prove that π Cj i.t. is a yes-instance if and only if π 3P is a yes-instance.

Proof for If

We firstly show that if π 3P is a yes-instance, i.e. there exists a partition A 1 , A 2 , . . . , A q for π 3P , such that a∈Ai w a = B , then, we can build a feasible schedule (S * ) for π i.t. such that C j ≤ T CT * . W.l.o.g. we assume that, for each subset A k in the partition for k = 1, . . . , q, the three elements in it are a k 1 , a k 2 and a k 3 .

x

1 1 x 2 1 x 3 1 x 4 1 x 5 1 x 6 1 x 7 1 x 8 1 x 9 1 x 10 1 x m-m1 1 x 1 2 x 2 2 x 3 2 x 4 2 x 5 2 x 6 2 x 7 2 x m-m2 2 x 1 3 x 2 2 x 3 2 x 4 2 x m-m3 3 x 4 q x 1 q x q+1
x q+2

x q+3

x q+4

x q+5

x K 3 q -1 q q + 1 t 5 6 We make use of notation T CT * x (resp. T CT * v and T CT * u ) for representing the total completion time of x-jobs (resp. v-jobs and u-jobs) in (S * ). In the subsequent part, we show how jobs are scheduled in (S * ) together with calculating the TCT (total completion time).

Firstly, x-jobs are executed once they are ready, which means every x-job begins immediately after the completion time of its last-finished predecessor. Formally, ∀i ≤ q, ∀j ≤ mm i , C

x j i = i; ∀q ≤ i ≤ K 3 , C xi = i.
Accordingly, we consider TCT for the x-jobs:

T CT * x = q i=1 m-mi j=1 C x j i + K 3 i=q+1 C xi (2.1) as ∀i ≤ K 3 , ∀j ≤ m -m i , C x j i = i, the first part is equivalent to: q i=1 m-mi j=1 C x j i = q i=1 m-mi j=1 i = q i=1 i(m -m i )
and as mm i = 3(q + 1 -i) + 1, we have:

q i=1 m-mi j=1 C x j i = q i=1 i(3(q + 1 -i) + 1)
Then, for i > q, we also have C xi = i, so the second part of (2.1) is:

K 3 i=q+1 C xi = K 3 i=q+1 i
Accordingly, we can obtain the TCT of all x-jobs:

T CT * x = q i=1 i(3(q + 1 -i) + 1) + K 3 i=q+1 i (2.2)
In the second step, considering the x-jobs, the k th time-slot for k ≤ q + 1 has m k available machines for both u-jobs and v-jobs. All the u-jobs corresponding to the subset A k are executed in the same time-slot, the k th time-slot. They need exactly B machines by definition of 3-Partition. Formally, ∀k ≤ q, ∀a ∈ A k , ∀i ∈ {1, 2, 3}, and ∀j ≤ w a k i , C u j a k i = k. Thus, there are exactly B u-jobs executed in each time slot, i.e.

|{u|C u = t}|= B, ∀t ≤ q. So, we are able to deduce that all the u-jobs are accomplished before t = q, and we have:

T CT * u = q t=1 t|{u|C u = t}|= B q i=1 i (2.3)
Thereafter, every v-job is executed without any delay in accordance with the precedence constraints.

Formally, ∀a ∈ A, C v 1 a = C u 1 a + 1 and ∀i ∈ {2, 3, . . . , Kw a }, C v i a = C v i-1 a + 1. So, for each v-chain corresponding to the element a ∈ A, we have C v i a = C v i-1 a + 1, ∀i ∈ {2, 3, . . . , Kw a }, that is equivalent to C v i a = C v 1 a + i -1. Let u a be any u-job preceding v 1 a , as C v 1 a = C ua + 1, we have C v i a = C ua + i
. Now, we calculate the TCT for this given chain:

Kwa i=1 C v i a = Kwa i=1 C ua + Kwa i=1 i = Kw a C ua + Kwa i=1 i
Then, we deduce the TCT for all the v-chains, i.e. all the v-jobs:

T CT * v = a∈A Kwa i=1 C v i a = K a∈A w a C ua + a∈A Kwa i=1 i
We know the fact that, for each subset a ∈ A i , we have C ua = i. So, we are able to deduce that the first part is equivalent to:

K a∈A w a C ua = K q i=1 a∈Ai w a i = K q i=1 i a∈Ai w a = K q i=1 iB So, T CT * v = K q i=1 iB + a∈A Kwa i=1 i (2.4)
In k th time slot of (S * ), k < q + 1, there are exactly mm k x-jobs, B v-jobs and 3k -3 v-jobs. By definition of m k , there are exactly m jobs in progress. After t = q, there are only one x-job and at most 3q v-jobs executed in parallel. Thus, there are no more than m jobs. So, this schedule respects the availability of machines.

Then, we deduce that the total completion time of (S * ), which is a feasible schedule for π i.t. , is:

C j = T CT * v + T CT * u + T CT * x = T CT *

Proof for Only If

Now, we prove that if π i.t. has a feasible schedule respecting the T CT * , then π 3P has a partition. WLOG, let (S) be a feasible active schedule, defined in (Pinedo, 2012). We prove in the following part that (S) takes the same shape as (S * ) and show how to get a partition from (S).

For that purpose, we first define the TCT of u-jobs, v-jobs and x-jobs in (S) as T CT u , T CT v and T CT x . Subsequent to that, we define the following gaps:

∆ u = T CT u -T CT * u ∆ v = T CT v -T CT * v ∆ x = T CT x -T CT * x
In order to have (S) respecting the T CT * , we clearly have:

∆ x + ∆ u + ∆ v ≤ 0 (2.5)
First of all, let us consider the x-jobs. We show that the x-jobs must have the same profile as in (S * ), which corresponds to the following lemma: Proposition 1. The x-jobs are scheduled once they are ready, i.e. ∆ x = 0.

Proof. By contradiction: assume that there is at least one delayed x-job. (S) is active; accordingly, this x-job can be delayed only by insertion of u-jobs or v-jobs.

Notice that the x-jobs can take no more than mm 1 machines in parallel because of their precedence constraints. At any moment, there are at least m 1 = B available machines for both the v-jobs and u-jobs. Moreover, in an active schedule, the makespan (C max ) is not larger than the number of jobs. As the total number of v-jobs and u-jobs is KB + qB, the last v-job or u-job finishes before or at KB + qB. Consequently, the delay must happen before KB + qB.

As the length of the final x-chain is K 3 , at least K 3 -(KB + qB) jobs are right-shifted. We observe that when a chain of n c jobs is right-shifted by one time slot, then its TCT will be increased by n c . Following this observation, we have

∆ x ≥ K 3 -KB -qB Remind that by definition, T CT * u K 2 , T CT * v K 2 ,
and K = B 5 , B K. Thus, we have:

∆ x T CT * u + T CT * v
In accordance with the definition, we have ∆ u > -T CT * u and ∆ v > -T CT * v , then

∆ x + ∆ v + ∆ u > ∆ x -T CT * u -T CT * v 0
This is a contradiction to (2.5). So, our assumption is false, there is no delay during the execution of the x-jobs.

Since ∆ x = 0, (2.5) becomes

∆ u + ∆ v ≤ 0 (2.6)
Here we conclude that the number of available machines in (S) is the same as in (S * ) to schedule u-jobs and v-jobs. Now, let us deal with the u-jobs. Definition 2. We define the u-jobs in the same component as a u-set and define U t as the number of u-jobs in all the u-sets, which are completed exactly at time t.

Proposition 2. At time t * ≤ q, t * t=1 U t ≤ t * B.
Proof. The number of jobs finished at t * ≤ q is at most t * m which is:

t * m = t * B + t * (3q + 1) ≤ t * B + 3q 3
Considering that the number of u-jobs in a u-set is w a , which is integer times q 5 , so, the number of u-jobs in u-sets which are executed before or at t * is at most t * B. Now, let us move on to the v-jobs. Definition 3. We define V t as the number of v-jobs in the chains starting exactly at the time t for t < q in (S), and V q as the number of v-jobs in the chains starting at or after t = q. Proposition 3. In (S), at any time t ≤ q, the total length of the v-chains beginning at t in (S) is exactly KB, i.e. V t = KB.

Proof. First, according to the precedence constraints, we have a relation between V t and U t :

t * t=1 V t ≤ K t * t=1 U t ∀t * < q
So, from Proposition 2, we can deduce:

t * t=1 V t ≤ t * BK ∀t * < q
which is:

(2.7)

V 1 ≤ KB V 1 + V 2 ≤ 2KB V 1 + V 2 + V 3 ≤ 3KB . . . . . . V 1 + V 2 + V 3 + • • • + V q-1 ≤ (q -1)KB
If we sum them up, we get:

(q -1)V 1 + (q -2)V 2 + • • • + V q-1 ≤ KB q 2 -q 2 (2.8)
By definition, we understand that q t=1

V t corresponds to the norm of whole set of v-jobs and it is equal to KqB:

q t=1 V t = KqB (2.9)
Then, by multiplying (2.9) by q, we get:

qV 1 + qV 2 + . . . qV q = KBq 2 (2.10)
With (2.10)-(2.8), we get

V 1 + 2V 2 + • • • + (q -1)V q-1 + qV q ≥ KB q 2 + q 2
which leads to conclude:

q i=1 iV i ≥ KB q i=1 i
Now, suppose by absurd that

q i=1 iV i > KB q i=1
i. By definition, V i is the total length of some v-chains, which implies that V i is integer multiple of K. So, we have:

q i=1 iV i ≥ KB q i=1 i + K (2.11)
When all the v-jobs in one chain are executed without any delay, the v-jobs have the following minimum TCT:

T CT v ≥ a∈A Kwa i=1 i + q i=1 iV i (2.12)
Reminding the expression of T CT * v in (2.4), we can deduce that:

∆ v ≥ q i=1 iV i -KB q i=1 i (2.13)
By (2.13) and (2.11), we have ∆ v ≥ K. Then, by (2.6), we have ∆ u ≤ -K. This contradicts the fact that ∆ u ≥ -T CT * u -K. Thus, we demonstrated that

q i=1 iV i = KB q i=1
i. So, every decomposition of group (2.7) is written with an equality, which indicates that

V 1 = V 2 = • • • = V q = KB.
Finally, we can conclude that ∆ v = 0 and V t = KB, ∀t ≤ q. This suggests that, at any t, the length of v-chains that start is exactly KB. The 3 propositions above allows us to build a partition from V i by selecting the elements corresponding to its 3 v-chains of KB jobs. Thus, we accomplished the proof for Only If. So, we are able to reduce π 3P to π Cj i.t. , then, we have:

Theorem 1. P |p j = 1, i.t.| C j is N P-complete.
We finished the proof for the problem with in-tree precedence constraints. The transformation and the proof in this chapter is dedicated merely to the problem P |p j = 1, i.t.| C j , while in the next chapter, we move on to other scheduling problems with different precedence constraints, which requires a new reduction, where the transformation and the proof are reused.

Transformation

We transform π 3P to an instance of the scheduling problem with level-order precedence graph, noted as π l.o. . We set the number of machines m = B + 2, then build 3 sets of jobs.

First, we build a set of dummy jobs, noted x-jobs. They form a component of qB + 1 levels. Let the number of x-jobs on level i be L i , we set:

L i =      1 i = kB + 1, ∀k = 1, . . . , q -1 2 i = qB + 1 B + 1 otherwise (3.1)
x-jobs are subject to precedence relations where jobs on level l, which are noted x 1 i , . . . , x Li i , precede every job on level l + 1 (see Figure 3.1).

Then, the second set contains u-jobs and the third v-jobs. For each a ∈ A, we create a component of w a ujobs and w a v-jobs. In each component, the u-jobs form a chain, and they precede all the v-jobs which have no precedence constraint between each other to form a unique level. Formally, we create u 1 a ≺ u 2 a . . . ≺ u wa a ≺ v k a , ∀k = 1, . . . , w a , which corresponds, by definition, to a level-order graph (see Figure 3.2). As |A|= 3q, there are 3q non-dummy components.

In addition, remind that the term profile introduced in 1.1.1, is used to describe the number of available machines along the time.We define a specific profile, the profile P, such as m t = m -L t . This profile will be used in all this chapter. A profile of available machines is said to be filled by a set of jobs if those jobs are scheduled on the available machines without any idle time.

We have transformed π 3P to π l.o. by creating (qB +1)(B +2) = O(qB 2 ) jobs, which is pseudo-polynomial. We build the first decision version π Cmax l.o. of π l.o. by asking: whether π l.o. has a schedule such that C max ≤ qB + 1.

Proof for If

In this section, we show that if π 3P is a yes-instance, which means it admits a partition, then π Cmax l.o. is a yes-instance, i.e. π l.o. has a schedule such that C max ≤ qB + 1.

We build such a schedule (S * ) by executing the x-jobs once they are ready. Formally, C x i i = i, ∀i = 1, . . . , qB + 1 and ∀i = 1, . . . , L i . The Gantt chart of (S * ) is given in Figure 3.3. By observation, the x-jobs enforce the profile P. Now, we show that the u-jobs and v-jobs can fill it non-preemptively:

We use [t 1 , t 2 [ to represent the half-open time interval from t 1 to t 2 .∀i = 1, . . . , q, 1. In [(i -1)B, iB -1[, successively execute the 3 corresponding u-chains of

A i = {a i 1 , a i 2 , a i 3 }, which corresponds to jobs: u 1 a i 1 , . . . , u w a i 1 a i 1 , u 1 a i 2 , . . . , u w a i 2 a i 2 , u 1 a i 3 , . . . , u w a i
A i , v 1 a i 1 , . . . , v w a i 1 a i 1 , v 1 a i 2 , . . . , v w a i 2 a i 2 , v 1 a i 3 , . . . , v w a i 3 a i 3 .
Thus, we built a schedule which finishes all jobs exactly at t = qB + 1 and finish the proof.

Because the profile P is filled, we set the following proposition:

Proposition 4. If π 3P is a yes-instance, then the u-jobs and v-jobs can fill the profile P non-preemptively.

The schedule (S) * we built has no idle time. We call this a full schedule. In fact, a schedule such that C max = n m is full and vice versa. So, Proposition 5. π Cmax l.o. is a yes-instance if and only if π l.o. has a full schedule.

we have also proved: Proposition 6. If π 3P is a yes-instance, then π l.o. has a full non-preemptive schedule.

Proof for Only If

In this section, we prove that when preemption is allowed, if π Cmax l.o. is a yes-instance, i.e. π l.o. has a schedule (S) such that C max ≤ qB + 1 , then π 3P is a yes-instance.

We first show that the x-jobs enforce the profile P in (S). By observation, any delay of the x-jobs (which means they are not executed once they are ready) or preemption resumed later will right-shift the jobs on the last level (the qB + 1 th level). It will be finished strictly after t = qB + 1, which contradicts the makespan of (S). So, the x-jobs are executed continuously once they are ready. As the x-jobs enforce the profile P, the u-jobs and v-jobs should fill the profile P to complete a full schedule. ∀i = 1, . . . , q, we define Φ i = [iB, iB + ξ[ as a half-open interval, where each machine executes at most one piece of job, ξ is a positive number as small as needed.

Define V i as v-jobs executed in Φ i , and PV i as the set of u-jobs predecessors of the jobs in V i . ∀i = 1, . . . , q, define the pipeline intervals: PI i = [(i -1)B + 1, iB[. ∀i = 0, . . . , q, define the column intervals: CI i = [iB, iB + 1[. They are noted in Figure 3.3.

We now prove that ∀i = 1, . . . , q, |PV i |= B. We use a mathematical induction. First, we prove that this proposition holds for i = 1, i.e. |PV 1 |= B.

By definition, PV 1 should be finished before t = B. They can only be executed in CI 0 and PI 1 .

Lemma 1. There are at most 3q u-jobs executed in parallel at any time.

Proof. Only one u-job in the chain of each component can be executed because of the precedence of constraints and there are 3q components in total.

By definition of u-jobs and Lemma 1, we have:

Lemma 2. The amount of work of u-jobs in any column interval is at most 3q, so, the total amount of work of u-jobs in all column intervals is at most 3q 2 .

In addition, we can set:

Lemma 3. The total amount of work in any pipeline interval is at most B -1.

Proof. The total amount of work in any pipeline interval, where there is only one available machine in the profile P, cannot be greater than its length, i.e. B -1.

By Lemma 3 and 2, we know that the total amount of work of PV 1 in CI 0 and PI 1 is at most B -1 + 3q.

Lemma 4. ∀i = 1, . . . , q, if |PV i |< B + 10q 2 , then |PV i |= B.
Proof. We first prove that ∀i = 1, . . . , q, |V i |≥ B -3q for preparation. Suppose by contradiction that ∃i = 1, . . . , q, s.t. |V i |< B -3q. In Φ i , each machine executes at most one job in parallel. As the profile P indicates, the number of available machines for u-jobs is:

m iB -|V i |> B -(B -3q) > 3q.
So, there must be more than 3q u-jobs in parallel to fill the profile P, which is a contradiction to Lemma 1. With our assumption, we can deduce that |V i |≥ B -3q.

PI ≤k takes at most the rest 3q 2 , which is:

W k+1 PI ≤k ≤ 3q 2 . ( 3
|PV k+1 |= W k+1 CI ≤k + W k+1 PI k+1 + W k+1 PI ≤k ≤ B + 6q 2 < B + 10q 2 . (3.6)
By Lemma 4, we have |PV k+1 |= B. As we finished the mathematical induction, we proved that PV i = B, ∀i = 1, . . . , q.

To obtain a partition of A, we only need to check the v-jobs executed in each Φ i . The number of their predecessors is exactly B, and the elements corresponding to each Φ i can form a partition.

Add to this, by Proposition 5, we proved that:

Proposition 7. When preemption is allowed, if π l.o. has a full schedule, then π 3P is a yes-instance. and Proposition 8. When preemption is allowed, if the u-jobs and v-jobs can fill the profile P, then π 3P is a yes-instance.

As we finished the proof for both if and only if, we conclude:

Theorem 2. P |p j = 1, l.o., pmtn|C max is N P-complete.

As the discussion about the preemptive case is done, we now assume that the preemption is forbidden. We aim at showing that π 3P and π Cmax l.o. are still equivalent. First, we set the following proposition: Proposition 9. π l.o. has a full non-preemptive schedule if and only if π 3P is a yes-instance.

Proof. If: It can be directly given by Proposition 6.

Only If: Assume that π l.o. has a full non-preemptive schedule, then of course, it can still have a (the same) full schedule when preemption is allowed. By Proposition 7, π 3P is a yes-instance. This leads directly to conclude:

Theorem 3. P |p j = 1, l.o.|C max is N P-complete.
In the next section, we change the objective function to the total completion time and consider other precedence constraints graph. We do a similar transformation and adapt the proof to show the equivalence of their decision questions.

Other problems

Level-order graph and total completion time

In this section, we prove the considered problem is N P-complete when the objective function is changed to the total completion time. To that purpose, we only need to build another decision version π Cj l.o. of instance π l.o. by setting the question as: whether π l.o. has a schedule such that C j ≤ T CT * , where

T CT * = qB+1 i=1
im.

We first discuss the preemptive case. As a preliminary step, we begin with a property of scheduling n = km unit processing time jobs, where k is an integer: For the preemptive case, [START_REF] Brucker | How useful are preemptive schedules?[END_REF] proved that preemption is redundant for the problem P |p j = p| T j , in which P |p j = 1| C j is a subcase by setting d j = 0 and p j = 1 for all job j. Even in P |p j = 1| C j , where there is no precedence constraint, preemption cannot reduce the total completion time from a full non-preemptive schedule which is optimal for C j . An optimal preemptive schedule exists only when there already is a non-preemptive one. Then, we discuss the case when preemption is not allowed. In this case, a non-preemptive schedule such that

C j ≤ qB+1 i=1
im is equivalent to a full non-preemptive schedule too. Similarly, we have: Up to the present, we have proved that for both total completion time and makespan, scheduling unitprocessing-time jobs with level-order precedence constraints is N P-complete whether it is preemptive or not. In the precedence graph we built, the u-jobs and v-jobs can be recognized not only as level-order, but also as out-trees. Based on this fact, in the following two sections, we extend this proof to scheduling problems with other precedence graphs by rebuilding only the x-jobs to respect the considered graph shape but keep the profile P.

Theorem 5. P |p j = 1, l.o.| C j is N P-complete.

Out-trees, Maximum Lateness

Similarly, we transform π 3P to π o.t. , an instance of the given scheduling problem with out-trees precedence constraints.

We build the u-jobs and v-jobs as previously. Their due dates are set as qB + 1. The x-jobs are rebuilt as following:

• ∀i = 1, . . . , qB + 1, build L i x-jobs on the i th level, where L i is defined as the same as in (3.1):

x 1 1 , . . . x L1 1 . . . . . . x 1 i , . . . x Li i . . . . . . x 1 qB+1 , . . . x L qB+1 qB+1
• ∀i = 1, . . . , L i , set the due date of jobs on the i th level as

d x i i = i.
• The precedence constraints are set as:

x 1 i ≺ x i i+1 .
They can be seen as an out-tree (see Figure 3.4). The number of machines is still m = B + 2.

We give the decision version π Lmax o.t. of the problem by asking whether π o.t. has a schedule whose L max ≤ 0. Then, this section is dedicated to prove its equivalence with π 3P , i.e. it is a yes-instance if and only if π 3P is a yes-instance.

Proof for If

Here, we show that if π 3P is a yes-instance then we can create a schedule whose L max ≤ 0 for π o.t. . Execute the x-jobs once they are ready to respect the due date constraints. We observe that the xjobs enforce the number of available machines for u-jobs and v-jobs to the profile P. Then, according to Proposition 4 we fill the profile P by the u-jobs and v-jobs, in which all jobs are finished before qB + 1, i.e. L max ≤ 0. This answers yes to π Lmax o.t. .

Proof for Only If

Let (S) be a schedule whose L max ≤ 0 for π o.t. . First, consider a x-job x i i for i ≤ L i . It cannot be started before t = i -1 according to the precedence constraints. However, to meet its due date, it must be finished at t = i. These two rules force x i i to get started once ready. As x-jobs enforce the profile P, and the u-jobs and v-jobs in (S) finish before qs + 1 to satisfy L max ≤ 0, the u-jobs and v-jobs must fill the profile P. Then, by Proposition 8, we know that π 3P is a yes-instance.

As we finished the proof for both If and Only If directions, we conclude: Theorem 6. P |p j = 1, o.t., pmtn|L max is N P-complete.

Up to this point, we finish the proof for N P-completeness of scheduling problem with out-tree precedence constraints. In the following two sections, we consider the opposing-forest while minimizing the makespan and the total completion time.

Opposing-forest, makespan

Now, we transform π 3P to π o.f. , an instance of the scheduling problem with unit-processing-time jobs where the precedence constraints are opposing-forest.

We build the u-jobs and v-jobs as previously. The x-jobs are built to compose in-trees and out-trees, see Figure 3.5. First, we build an in-tree of qB + 1 levels, such that

• for i ≤ qB + 1, recursively define L I i =          2qB i = 1 L I i-1 -B i = kB + 1, ∀k = 1, 2 . . . , q -1 L I qB -B + 1 i = qB + 1 L I i-1 otherwise (3.7)
• On the i th level, build L I i jobs x 1 I,i , . . . x L I i I,i

• set the precedence constraints as:

-if L I i = L I i-1 , x i I,i-1 ≺ x i I,i , for i = 1, . . . , L I i -if L I i < L I i-1 , let ∆ = L I i-1 -L I i-1 + 1, then set x i I,i-1 ≺ x 1 I,i , for i = 1, . . . , ∆; and x i +∆ I,i-1 ≺ x i I,i for i = 1, . . . , L I i -∆.
Then, we build an out-tree of qB + 1 levels

• for i ≤ qB + 1, recursively define L O i =      1 i = 1 L O i-1 + B i = kB + 2, ∀k = 1, 2 . . . , q -1 L O i-1 otherwise (3.8)
• On the i th level, build

L O i jobs x 1 O,i , . . . x L O i O,i
• set the precedence constraints as:

-if L O i = L O i-1 , x i O,i-1 ≺ x i O,i , i = 1, . . . , L I i -if L O i < L O i-1 , let ∆ = L O i -L O i-1 + 1 = B + 1, then set x 1 O,i-1 ≺ x i O,i , for i ≤ ∆; and x i O,i-1 ≺ x i +∆ O,i for i = 1, . . . L O i-1 -∆.
In this instance, the number of machines is set to m = 2qB + 2. We compare number of x-jobs on the i th level

L O i + L I i = L i + δ, where δ = 2qB + 2 -(B + 2) = 2qB -B.
It is exactly the difference between m defined in π o.f. and π l.o. . We find that scheduling the x-jobs once they are ready still enforces the profile P of available machines for u-jobs and v-jobs and the previous propositions about the v-jobs, u-jobs and the profile P still yield.

The first decision version π Cmax o.f. asks: whether π o.f. has a feasible schedule such that C max ≤ qB + 1.

Then, we prove its equivalence with π 3P by showing that π 3P is a yes-instance if and only if π Cmax o.f. is a yes-instance.

Proof for If

As π o.f. contains (qB + 1)m jobs, then π Cmax o.f. is a yes-instance if and only if π o.f. has a full schedule. In this subsection, we set that: Proposition 11. If π 3P is a yes-instance, then π o.f. has a full non-preemptive schedule.

Proof. Using Proposition 4, as π 3P is a yes-instance, the u-jobs and v-jobs can fill the profile P nonpreemptively. Thus, we can build a schedule by letting the x-jobs be executed once they are ready and filling the profile P with the u-jobs and v-jobs.

As all jobs are finished before qB + 1, and there are exactly (qB + 1)m jobs in π o.f. , this is a full schedule without preemption.

Proof for Only If

In this subsection, we prove that if π o.f. has a full schedule, then π 3P is a yes-instance. We begin with studying the u-jobs and v-jobs and the profile P.

First, by observation, whether in the in-tree or in the out-tree, every x-job has a successor in the (qB +1) th level. So, any delay will right-shift this job. It will be finished strictly after t = qB + 1, which contradicts the makespan qB + 1. So, the x-jobs are executed once ready and enforce the profile P. Thus, the u-jobs and v-jobs must fill the profile P to finish before qB + 1.

Then, by Proposition 8, we have:

Proposition 12. When preemption is allowed, if π o.f. has a full schedule, then π 3P is a yes-instance.

Proposition 11 and 12 bring out:

Theorem 7. P |p j = 1, o.f., pmtn|C max is N P-complete.

If π o.f. has a non-preemptive full schedule, then it has one full schedule when preemption is allowed, so by Proposition 12, we have: Proposition 13. If π o.f. has a non-preemptive full schedule, then π 3P is a yes-instance.

We move to another objective function, the total completion time, and prove that the problem is still N P-complete. is a yes-instance if and only if π o.f. has a full non-preemptive schedule. Furthermore, Proposition 11 and 13 show that π o.f. has a full non-preemptive schedule if and only if 3-Partition is a yes-instance, which brings out:

Opposing-forest, total completion time

Theorem 8. P |p j = 1, o.f., pmtn| C j is N P-complete. β γ C max C j L max i.

Conclusion

In this chapter, we first put forward a proof of N P-completeness for P |p j = 1, in-tree| C j . Then, we proved that scheduling unit-processing-time jobs under level-order or opposing-forests precedence constraints is N P-complete, for both C max and C j whether or not preemptive. Scheduling out-trees is shown to be N P-complete by using similar proof when minimizing L max . This work updates the earlier study of scheduling problems' complexity in literature. The Table 1.1 can be updated. New complexity results of parallel scheduling unit-processing-time jobs under different precedence constraints are shown in Table 3.1.

Another result comes from the complexity hierarchy. When the criterion is the total tardiness T i = max{L max , 0} or the total number of tardy jobs U j (binary U j equals 1 if and only if j is tardy), our result also implies that P |o.t., p j = 1, pmtn| T j and P |o.t., p j = 1, pmtn| U j are N P-complete as well. With this hierarchy, the results can be extended to other open problem not included in Table 3.1.

The table also shows that when preemption is allowed, the complexity of the problem P |p j = 1, i.t., pmtn| C j is still open. However, the preemption is not redundant to reduce the total completion timeand previous results cannot be directly extended.

Despite the fact that preemption may reduce the total completion time, we still conjecture that, with the same transformation, the equivalence of π 3P and π Cj i.t. still holds even if preemption is allowed, and the problem shall be N P-complete as well.

Considering the fixed parameter m, there are still some other problems whose complexity is open, such as P m|p j = 1, l.o., pmtn|C max . Our next research avenue may be dedicated to study these open problems.

As the problems are N P-complete, they have no polynomial algorithm unless P = N P . In the next part, we focus on how to exponentially solve these problems.

Part III

Problem solving

In this part, we focus on how the scheduling problems we study can be solved. We put forward an algorithm for the specific problem P |p j = p, i.t.| C j , which is both theoretically and experimentally faster than the existing algorithm for this problem. Then, we study the general problem P |prec|C max by integer programming models. We adapted the existing models which are originally designed for other problems, and propose a new one. We compare their performance and show that our model outperforms the others.

Chapter 4

An improved algorithm for P |p j = p, i.

t.| C j

In this chapter, we study how to solve the problem P |p j = p, i.t.| C j , which deals with in-tree precedence graph while minimizing the total completion time. We proved in Chapter 2 that the problem is N P-hard. However, when the number of machines m is fixed, the problem, written as P m|p j = p, i.t.| C j , can be polynomially solved in O(n m ) by an algorithm by [START_REF] Baptiste | Ten notes on equal-processing-time scheduling[END_REF]. We here propose a new algorithm in O(h m ) where h is the height of the tree, and show that it is also experimentally faster than Baptiste's algorithm.

First, we introduce the state of the art in the following section. Second, we propose and prove a theorem, on which the optimality of our algorithm is based. Third, we illustrate the algorithm with an example. Then, we compare it to Baptiste's algorithm and present the experiment results.

Previous studies

This section is dedicated to introduce the work of [START_REF] Hu | Parallel sequencing and assembly line problems[END_REF] and [START_REF] Baptiste | Ten notes on equal-processing-time scheduling[END_REF], that will be useful for next parts.

Let us recall that in [START_REF] Hu | Parallel sequencing and assembly line problems[END_REF] the height of job j is defined as the length of longest chain from j to the final job, noted as h(j). He proved that an algorithm who executes the highest jobs (with largest h(j)) when there are more than m candidates, is optimal for makespan, i.e. P |p j = p, i.t.|C max .

On the other hand, [START_REF] Baptiste | Ten notes on equal-processing-time scheduling[END_REF] showed that an optimal schedule who minimizes the total flow time always takes the shape described in Fig. 4.1. The set of jobs in the first incomplete slot is noted as J * . J * separates jobs into 2 parts. As the second part J 2 is composed of successors of J * , when J * is given, the 2 parts can be immediately obtained. Thus, an optimal schedule can be generated in polynomial time from J * : the full partial schedule of the first part can be obtained by Hu's algorithm, and any active partial schedule of J 2 is optimal. To obtain J * , they proposed to check all sets of at most m -1 jobs, which requires O(n m ) iterations. When m is fixed, this method finds an optimal schedule in polynomial time.

Further analysis

We aim at a more efficient way to find a J * instead of checking all combinations. In this section, we prove that there exists always a J * who satisfies some properties.

Definitions

We first formally define different sets of jobs in an optimal schedule. As J * is the set of jobs in the first slot with less than m jobs, and J 2 is its successors, we define J as the set of jobs in the previous slot of J * . Then, let J 1 be the jobs executed before J .

We partition set J * into A * and B * : each job in B * has predecessor in J , and jobs in A * do not. Reversely, we define B ⊂ J , the set of predecessors of B * , and A := J \ B . See Fig. 4.1. The in-tree graph. Job j is in red, set X is in box , L X (j) = ∅, P X (j) is solid, and S X (j) is in the oval.

Then, we recall the level of a job introduced in section 1.2: h minus the length of the longest chain from an initial job to j, represented by l(j) to distinguish from h(j), the length of the longest chain from j to a final job. Their difference can be seen in Fig. 1.2. The terms high (higher, highest) and low (lower, lowest) are used to describe l(j) from now on.

The formal definition of l(j) is:

l(j) := h if j is initial task in G min{l(p)|p ∈ pred(j)} -1 otherwise
Then, we consider 3 different operators on a job j and a set X. They return a set of jobs.

1. The set of jobs in X which are strictly lower than j :

L X (j) := {j * ∈ X|l(j * ) < l(j)} 2. A pruned tree: P X (j) := {j 1 ∈ J T |l(j 1 ) > l(j 2 ), ∀j 2 ∈ L X (j)} \ pred(L X (j))
It removes all predecessors of L X (j) from jobs strictly higher than jobs in L X (j).

3. The set of jobs in P X (j) which are on the same level as j :

S X (j) := {j s |l(j s ) = l(j), j s ∈ P X (j)} See Fig. 4.2 for an illustration. ∀j ∈ X, if |S X (j)|≤ k, then j is called k-limited in X,
where k is a positive number. Furthermore, a set X is pure-k-limited when all jobs in it are k-limited. Finally, a set X ⊂ J T is defined as regular if either it has a pure-m-limited superset V, such that |V|≤ m; or the jobs in X can be partitioned into 3 groups: Group 1 in which jobs are m-limited in X, i.e. |P X (j)|≤ m.

Group 2 in which jobs are 2m-limited in X and admit the same level, noted as l Group 2 , i.e. ∀j ∈Group 2, |P X (j)|≤ 2m and l(j) = l Group 2 .

Group 3 in which each job j is the lexicographically first one in S X (j), and l(j) ≥ l Group 2 .

Using this definition, we set:

Theorem 9. For any instance of P |p j = p, i.t.| C j , there exist an optimal schedule with a regular J * .

For convenience, a schedule is also called a regular schedule if J * is regular. The following of this section is dedicated to prove the Theorem, i.e. the existence of a regular J * . To show the existence of a regular J * , we first build a particular schedule (S) from an arbitrary optimal one (S * ). Then, we prove that the J * of (S) is regular. W.l.o.g. we assume that J 1 ∪ J = ∅, otherwise any active schedule is optimal. 4.2.2 Construction of regular optimal schedule (S) from an arbitrary optimal schedule (S * )

Let (S * ) be any optimal solution for P |p j = p, i.t.| C j .

Step 1: Build the reverse graph G R = {J ∪ J 1 , E R }. Set j 1 ≺ R j 2 , ∀j 2 ≺ j 1 , where ≺ R means edges in E R . An example can be seen in Fig. 4.3 and the reverse graph of J ∪ J 1 in Fig. 4.5.

Step 2: Use Hu's algorithm to get a full schedule (S 1 ) for jobs in G R . For jobs of the same height in G R , the priority is given to those who have a successor in J * in G. Jobs with same priority are executed in lexicographical order. Step 4: Replace the sub-schedule of J ∪ J 1 in (S * ) by (S 1 ). See Fig. 4.4.

Step 5: ∀j A * ∈ A * , ∀j J J 1 ∈ J ∪ J 1 , if 1. l(j J J 1 ) < l(j A * ), or l(j J J 1 ) = l(j A * ) but j J J 1 lexicographically precedes j A * , and 2. pred(j A * ) = ∅, or pred(j A * ) finishes before S j J J 1 , and 3. succ(j J J 1 ) = ∅, or succ(j J J 1 ) begins after C j A * , then, switch j J J 1 and j A * . Go back to Step 1.

After these operations, the schedule (S * ) is renamed as (S). Notice that Hu's algorithm is optimal for makespan and out-tree. The reverse schedule of a feasible schedule of the reverse graph is feasible. The switch in Step 5 respects the precedence constraints. The profile of the Gantt chart is unchanged, (S) is still optimal. Finally, we underline that the go-back-loop finishes within n 2 repetitions because every time it moves the level of a jobs in A * down.

Properties of (S)

Before completing proof of the Theorem, we introduce the following properties, which will be used to prove the regularity of (S).

Propriety 1. If A * = ∅ and A = ∅, then ∀j A * ∈ A * , ∀j A ∈ A , l(j A ) ≥ l(j A * ).
Proof. By definition, jobs in A * have no predecessor in J and jobs in A have no successor in J * . If l(j A ) < l(j A * ), j A and j A * should have been switched in Step 5. Propriety 2. ∀j J ∈ J , ∀j J J 1 ∈ J 1 ∪ J if l(j J ) > l(j J J 1 ) and j J J 1 does not have a successor in J , then j J J 1 ∈ J .

Proof. Separately consider two cases:

Case 1: j J J 1 does not have a successor in J 1 . Let j be the image of job j in the reverse graph G R . We find a relationship between l and h: l(j) + h(j

) = h (4.1)
This relationship is clearly shown in Fig. 4.5.

As j J J 1 does not have a successor in J 1 ∪ J , when the precedence graph is reversed, its image j R J J 1 becomes an initial job in G R . We have h(j R J J 1 ) > h(j R J ). j R J J 1 have priority over j R J according to Hu's algorithm. As j R J is executed in J , which is the first time slot of (S 1 ), and as j R J J 1 is also initial, we deduce that j R J J 1 is in the first slot of (S 1 ) too, i.e. j J J 1 is in J .

Case 2: j J J 1 has a successor in J 1 . This case does not actually exist, we show it by a contradiction. Let j f s J J 1 be its last successor in J 1 . As l(j f s J J 1 ) < l(j J J 1 ) < l(j J ), we find that j f s J J 1 is in Case 1 we just proved. So, j f s J J 1 ∈ J . It is a contradiction to the fact that j f s J J 1 is in J 1 .

Corollary 14. ∀j J ∈ J , ∀j J 1 ∈ J 1 , if l(j J ) > l(j J 1 ), then j J 1 has a successor in J .

Propriety 3. If A = ∅, ∀j A ∈ A , ∀j J J 1 ∈ J 1 ∪ J if l(j A ) ≥ l(j J J 1
) and j J J 1 has a direct successor in J * then j J J 1 ∈ J .

Proof. j J J 1 has a direct successor in J * means that j J J 1 does not have a successor in J because every job has only one successor by definition of in-tree. So, their images j R A and j R J J 1 are initial jobs in G R , the reverse graph.

Case 1 l(j A ) > l(j J J 1 ) Propriety 2 holds. j J J 1 ∈ J .

Case 2 l(j A ) = l(j J J 1 ) As j J J 1 has a direct successor in J * , and by definition j A does not, according to Step 2, j J J 1 takes priority over j A and finishes no later than j A . So, j J J 1 ∈ J . Proof. First, prove that all jobs in A * are on the same level. Suppose by absurd that ∃j 1 A * , j 2 A * ∈ A * such that l(j 1 A * ) = l(j 2 A * ), w.l.o.g. we assume l(j 1 A * ) < l(j 2 A * ). Because of the definition of level, we can find a direct predecessor of j 1 A * on level l(j 1 A * ) + 1, let it be j 1dp A * . So, we have l(j 1dp A * ) ≤ l(j 2 A * ). ∀j A ∈ A , according to Propriety 1, l(j 2 A * ) ≤ l(j A ), so l(j 1dp A * ) ≤ l(j A ). As j 1dp A * has a successor in J * , according to Propriety 3, we have j 1dp A * ∈ J , which is a contradiction to definition of A * . So, all jobs in A * are on the same level. Now, we show that ∀j A ∈ A , ∀j A * ∈ A * , l(j A * ) = l(j A ) to finish the proof.

Let j lp A * be a lowest predecessor of j A * on level l(j A * ) + 1.

If l(j lp

A * ) ≤ l(j A ), as j lp A * has a successor in J * , according to Propriety 3, we have j lp A * ∈ J , which is a contradiction to definition of A * . So, we have l(j lp A * ) > l(j A ). So, l(j A ) < l(j A * ) + 1, which is l(j A ) ≤ l(j A * ). By Propriety 1, we have l(j A ) ≥ l(j A * ). So, l(j A ) = l(j A * ).

Propriety 5. Let X be a set of jobs on level l X , if either X ∩ (J ∪ J 1 ) = ∅ or X ∩ (A * ∪ J 1 ∪ B ) = ∅, then we have |X|≤ m.

Proof. We first consider the case when X ∩ (J ∪ J 1 ) = ∅ .

We build a partition of X: X J * and X J 2 , which represent the subset of X resp. in J * and J 2 . As all jobs in X J 2 have predecessors in J * , define these predecessors as X J 2 J * . Then, ∀j

X J 2 J * ∈ X J 2
J * , we have l(j

X J 2 J *
) > l X . So, X J 2 J * has no intersection with X J * . In an in-tree, different jobs on the same level have different predecessors, we have

|X J 2 J * |≥ |X J 2 |, so |X|= |X J * |+|X J 2 |≤ |X J * |+|X J 2
J * |< m, which closes the first case. Now, we consider the second case, where X ∩ (A * ∪ J 1 ∪ B ) = ∅. Partition X into X A , X B * , and X J 2 , which represent resp. subset of X in A , B * and J 2 . Similarly, we define the predecessors of X J 2 in A * and B * as X J 2

A * and X J 2 B * , we have

|X J 2 A * |+|X J 2 B * |≥ |X J 2 |. X A , X B * , X J 2
A * and X J 2 B * have no intersection with each other because jobs in

X J 2 A * and X J 2 B * are not on level l X . Case 1 If X J 2 A * = ∅ : If A = ∅, X A = ∅; if A = ∅,
we still have X A = ∅ because applying Propriety 4 leads to know that jobs in X A would be on the same level as jobs in X J 2 A * , which is, however, strictly higher than l X . As X B * , X J 2 A * and X J 2 B * are subset of J * , we have:

|X|≤ |X J 2 A * |+|X J 2 B * |+|X B * |≤ |J * |< m Case 2 If X J 2 A * = ∅: Define X B the predecessors of X B * and X J 2 B * in B .
As jobs in X B are not on level l X , we have X B ∩ X = ∅. As subsets of J , we have:

|X B |+|X A |≤ |J |= m As |X B |≥ |X J 2 B * |+|X B * |≥ |X J 2 |+|X B * |, we have |X|= |X A |+|X J 2 |+|X B * |≤ m
Propriety 6. ∀X ⊂ J T , ∀j ∈ X, jobs in S X (j) have no successor in X.

Proof. Suppose by absurd that j S ∈ S X (j) has a successor j s S in X. As l(j s S ) < l(j S ), l(j s S ) < l(j), and we have j s S ∈ L X (j), which is a contradiction to definition of S X (j).

Corollary 15. Let X be any superset of B * , jobs in S X (j) neither are in B nor have successor in B .

Proof. ∀j S ∈ S X (j), whether j S ∈ B or j S has a successor in B , can we find a successor of j S in B * , which is also in X. This contradicts Propriety 6.

Propriety 7. If A * = ∅ and B * = ∅, then ∀j A * ∈ A * , ∀j B * ∈ B * , we have l(j A * ) ≥ l(j B * )
Proof. Suppose by absurd that l(j A * ) < l(j B * ). We can find a lowest direct predecessor j ldp A * of j A * , and a predecessor j p B * of j B * in B . We have l(j p B * ) > l(j B * ) ≥ l(j ldp A * ). As the only direct successor of j ldp A * is in J * , j ldp A * cannot have any successor in J . Using Propriety 2, j ldp A * ∈ J , which is a contradiction to definition of A * . Propriety 8. ∀j A * ∈ A * , each job in S J * (j A * ) ∩ J 2 has a predecessor in A * .

Proof. First, let j h

A * be a highest job of A * and its last finished predecessor be j lp A * . ∀j S ∈ S J * (j A * ) ∩ J 1 , consider its last successor j f s S in J 1 , if j S is final then j f s S = j S . We have l(j f s S ) ≤ l(j S ) = l(j A * ) ≤ l(j h A * ) < l(j lp A * ) In Step 5 when constructing (S), we exchange jobs when the 3 conditions are satisfied. Now, check the following conditions of switching j f s S and j h A * : 1. by Propriety 9, j lp A * is finished strictly before j f s S ; 2. by Propriety 6, j S has no successor in J * , which implies that j f s S is final and has no successor in J * . If l(j f s S ) < l(j h A * ), j f s S should have been switched with j h A * by Step 5. So, we have l(j f s S ) = l(j h A * ) and the inequality above becomes l(j f s S ) = l(j S ) = l(j A * ) = l(j h A * ) < l(j lp A * ) This implies j S = j f s S , i.e. j S is final; and l(j A * ) = l(j h A * ), i.e. j A * is a highest job. Now, we prove the S J * (j A * ) \ J * ⊂ J 1 . Job in S J * (j A * ) ∩ J 2 would have predecessor in A * by Propriety 8, which contradicts the fact that j A * is already a highest job in A * , so S J * (j A * )∩J 2 = ∅. Then, S J * (j A * )∩J = ∅ can be deduced by Corollary 15. While we have both S J * (j A * ) ∩ J 2 = ∅ and S J * (j A * ) ∩ J = ∅, we have

S J * (j A * ) \ J * ⊂ J 1 .

Proof for the regularity

Using all the previous properties of (S), we prove the regularity of J * . Case 1: A * = ∅ We assume that A * = ∅. We prove that in this case, J * , which is B * , has a pure-m-limited superset.

Let us define such a superset as B * unions the jobs in A which are strictly lower than jobs in B * :

V := {j A ∈ A |∀j B * ∈ B * , l(j A ) < l(j B * )} ∪ B *
We prove that V is pure-m-limited: ∀j ∈ V, |S V (j)|≤ m. Consider ∀j S ∈ S V (j), we show that j S / ∈ J 1 . We find j h B the highest job in B , and we have l(j S ) < l(j h B ). If j S ∈ J 1 , according to Corollary 14, j S has a successor in J , let it be j s S . However, j s S ∈ A implies that j s S ∈ V because l(j s S ) < l(j S ); j s S ∈ B implies that j s S has successor in B * . In both case can we find a successor of j S in V, which contradicts Propriety 6. Corollary 15 indicates that S V (j) ∩ B = ∅, so, S V (j) ∩ (B ∪ J 1 ) = ∅. By Propriety 5, as A * = ∅, we have |S V (j)|≤ m.

As we proved that V is pure-m-limited, J * is regular when A * = ∅.

Case 2: A * = ∅

The rest of our proof shows that when A * = ∅, jobs in J * are in one of the 3 groups: Group 1, Group 2, and Group 3. Firstly, consider jobs in B * . ∀j B * ∈ B * , we prove that j B * is in either Group 1 or Group 2.

Proof. By Propriety 10, if l(j B * ) < l(j lowest A *

), then j B * is m-limited. Otherwise, j B * is 2m-limited. Jobs in Group 2 are the highest jobs of B * , on the same level.

Secondly, let us consider A * in the subcase where A = ∅. ∀j A * ∈ A * , we prove that j A * is in Group 3.

Proof. Suppose by absurd that j S is the lexicographically first job in S J * (j A * ), j S = j A * , and j S / ∈ J * . If j S ∈ J 2 , according to Propriety 8, it has a predecessor in A * . However, this contradicts the fact that jobs in A * are on the same level according to Propriety 4. So, j S ∈ J 1 ∪ J .

As A = ∅, Propriety 4 also tells that jobs in A is on the same level as j S . This means during Hu's algorithm in Step 2 when constructing (S), j S has the same priority as jobs in A . As we execute jobs in

Conclusion

We developed an algorithm for the scheduling problem P |p j = p, i.t.| C j , with a complexity O(h m ), where h is the height of in-tree if the number of machines is considered as a constant. This leads to the conclusion that the complexity is mainly determined by the height of the graph.

However, based on the properties we proved, this algorithm still has large room for improvement. For example, a more strict and efficient constraint |L|≤ m -|X| can replace |L|≤ m. Moreover, to make the algorithm practical for real instances, several technical improvements can be made, such as checking whether |J 1 ∪ J | is divisible by m before generating a schedule from every candidate set. These techniques may refine the algorithm to a certain extent, however, not in the sense of complexity.

Chapter 5

Modeling P |prec|C max

Considering the makespan, we recall that the problem is N P-hard even without precedence constraints and a fixed number of machines equal to 2 [START_REF] Lenstra | Complexity of machine scheduling problems[END_REF]. In previous chapters, we discussed that even when the jobs have equal-processing-time, and the precedence constraints take particular shape, the problem is still N P-hard for most of the cases. Nevertheless, generalized as a combinatorial optimization problem, all scheduling problems can be solved by various general problem-solving methods, such as tree-search procedures and mixed integer programming which benefits from its intuitive modeling and efficient solvers.

We are interested in this chapter in proposing a way to solve the general scheduling problem P |prec|C max with arbitrary precedence constraints and arbitrary processing-time. This method will be adaptable for specific processing time or precedence graph.

We adapt some models, which are originally designed for other problems, to parallel scheduling problems and propose a new one. Then, we compare their performance by testing them on benchmarks with precedence constraints from [START_REF] Kolisch | Psplib -a project scheduling problem library[END_REF].

Preliminary

Every model to be presented uses the variables S j and C j as starting time and completion time of j. The objective function is C max , the following constraints hold for all models, and they are omitted hereafter: C j = S j + p j , ∀j ∈ J T C max ≥ C j , ∀j ∈ J T S j ≥ C j , ∀j , j ∈ J T and j ≺ j where p j is the processing time of job j and j ≺ j means j precedes j. J T and M T are the sets of all jobs and machines. In the following sections, j , j ∈ J T and θ ∈ M T . M represents a large number, which can be defined as p j . Indeed, any one of C j and S j can be represented by the other one. However, the model is solved faster using both C j and S j then using just one of them, as we can see from the experimental results.

Time-Indexed Model (TIM)

The time-indexed model (TIM) is formulated in [START_REF] Thomalla | Job shop scheduling with alternative process plans[END_REF] for job shop scheduling problems. The principal variables it uses are x θ t,j which is 1 if j starts on θ at t. It requires an estimation of an upper bond of C max , which is noticed as t max . We proposed a version for TIM by using a nominal variable C j :

(5.1a) S j ≥ tx θ t,j , ∀j ∈ J T , t ≤ t max ; θ ∈ M T (5.1b) x θ1 t1,j + x θ2 t2,j ≤ 1, ∀j ≺ j, t 1 + p j ≥ t 2 , θ 1 , θ 2 ∈ M T (5.1c)

t ≤tmax θ ∈M T
x θ t,j = 1, ∀j ∈ J T

Test Result and Analysis

We tested the models with benchmarks we built from precedence constraints in [START_REF] Kolisch | Psplib -a project scheduling problem library[END_REF]. The instances are originally designed for scheduling problems with shared resources and multiple resource consumption, including renewable, non-renewable or doubly constrained resources. Jobs have informations such as due date, release date and tardiness cost etc. We removed all the constraints other than precedences constraints, set the number of machines differently, and set a unique requirement of resources consumption. The platform we used is: IBM ILOG CPLEX Optimization Studio V12.6.0 on Intel Core i7-4600U @2.10GHz. We compared their average time consumed to solve instances with different scales of jobs and machines in Table 5 We find that when m is set as 4, the models took longest time for solving. As it can be seen, CM stays ahead of the others and requires less space. The different speed of models results mostly from the different decision variables used.

The Time-Indexed Model (TIM) requires an estimation of an upper bound of C max . It can be as large as p j for the worst case (single machine) in practice, which leads to large amounts of variables. In our test, we set t max as the exact value of C max , which minimizes the number of variables. In fact, the number of variables could be extremely large if p j is not an integer. However, TIM is still the slowest even for instances of unit-processing-time jobs. Both ROIM2 and ROIM2 use O(n 2 m) binary variables: ROIM1 uses two 3-dimension variables, while ROIM2 and AOIM use only one. AOIM is the only one which requires extra integer variable. The fastest model CM uses only 2-dimension binary variables and requires fewest variables, which may be the principal advantage of CM.

CM does not have the fewest constraints. The fewest constraints are not necessarily another advance. There exists some redundant constraints, such as (5.2f) and (5.5c), which exert positive effects on models, see Table 5.3.

However, the redundant constraints does not certainly play a positive role in all models. For example, we find that adding T l θ = l-1 l =1 j β l θ,j p j to AOIM, which fix the value of T l θ immediately when the decision variable β l θ,j is fixed, makes the model dramatically slower, see Table 5.4. In addition to redundant constraints, the variables C j which could totally be replaced by S j + p j , can be seen as redundant variables. We tested and find that they improve the models.

In this thesis, we discussed the complexity of parallel scheduling problems with precedence constraints and the way to solve it.

We first put forward a proof of N P-completeness for P |p j = 1, in-tree| C j . We also proved that scheduling unit-processing-time jobs under level-order or opposing-forests precedence constraints is NP-complete, for both C max and C j whether it is preemptive or not. Then, we adapt the proof to other scheduling problems, such as out-tree and opposing forests. This work updates the earlier study of scheduling problems' complexity in literature.

On the other hand, we developed an algorithm for the N P-complete scheduling problem P |p j = p, i.t.| C j , with a complexity O(h m ), where h is the height of the in-tree. This algorithm is both theoretically and experimentally faster than Baptiste's algorithm [START_REF] Baptiste | Ten notes on equal-processing-time scheduling[END_REF]. Afterwards, we consider solving the general scheduling problem P |prec|C max by linear integer programming models. We adapted some existing models which are originally designed for other problems, and propose a new one, which uses less variables and runs faster on LP solver such as Cplex.

All this work refines the complexity limits and closes open cases. This could be particularly useful to classify a huge set of problems that derivate from parallel scheduling, such as hybrid shop problem. We also proposed resolution improvement to help decision tools being faster and more efficient.

Add to those extensions and applications, several theoretical research avenues also exist. In terms of complexity, there exist still open problems, such as P |p j = 1, i.t., pmtn| C j , that we have to study. We pointed out that our proof cannot be immediately adapted to this preemptive version by proposing a counterexample. So, this need further investigation. In addition, when the number of machines is fixed, some problems are still open such as P m|p j = p, ch., r j | C j . Another open problem, P m|p j = p, l.o.| C j , is conjectured to be polynomial solvable.

Regarding resolution methods and practical aspects to have efficient methods for real problems, we proposed some research avenues on exponential algorithms, which could be extended to other areas, such as shop scheduling problems and other sequencing problems. For example, in ride-sharing systems such as Uber, Didi, Lyft etc, demand list what a driver picks can be modeled as a sequence of jobs that a machine executes.

On another aspect, scheduling problems are not the only ones which depends on the shape of the graph. We may consider other OR problems where a graph is involved, such as network restoration problem (Averbakh, 2017), in which the shortest recovery time to reach every nodes has to be found. In such a field, the complexity may also vary when the graph takes a particular shape (e.g. tree) or some parameters are fixed. So, there clearly exist open problems too.

3. 1

 1 An updated overview of complexity of P |p j = 1, β|γ . . . . . . . . . . . . . . . . . . . . . . . 4.1 Experimental results: average time in seconds, where B,N stand for Baptiste's algorithm and the new algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1 Performance of various models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Number of variables and constraints, where BV/IV/C means number of binary variables/integer variables/constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Performance of ROIM1 and CM with/without redundant constraints, average time in sec. . . 5.4 Performance of AOIM with/without redundant constraints, average time in sec. . . . . . . . . 5.5 Models' performance solving instances of n = 30, m = 4 with/without C j . . . . . . . . . . . . Part I Introduction 1

Figure 1 . 1 :

 11 Figure 1.1: Opposing forest, where the left component is an in-tree and the right component is an out-tree

Figure 1 . 2 :

 12 Figure 1.2: level vs height.

Figure 1 . 3 :

 13 Figure 1.3: Example of a level-order graph with two components 1 A component is a subgraph where there is a path connecting any two nodes

Fig. 2 . 7

 27 Fig. 2.7 Complexity hierarchies of deterministic scheduling problems: (a) Machine environments (b) Processing restrictions and constraints (c) Objective functions

Figure 1 . 5 :

 15 Figure 1.5: Complexity Hierarchies (Pinedo, 2012)

Figure 2 . 1 :Figure 2

 212 Figure 2.1: in-tree of x-jobs

Figure 2 . 3 :

 23 Figure 2.3: Gantt graph of (S * )

Chapter 3 P

 3 |p j = 1, l.o., pmtn|C max and other problems In this chapter, we begin with the problem P |p j = 1, l.o., pmtn|C max . Then, we show how to adapt the proof to other open scheduling problems in the following order: 1. P |p j = 1, l.o.|C max 2. P |p j = 1, l.o., pmtn| C j 3. P |p j = 1, l.o.| C j 4. P |p j = 1, o.t., pmtn|L max 5. P |p j = 1, o.f., pmtn|C max 6. P |p j = 1, o.f., pmtn| C j

Figure 3 . 2 :

 32 Figure 3.1: x-jobs

Figure 3 . 3 :

 33 Figure 3.3: A full non-preemptive schedule (S * ) where blue (yellow, red) represents the x-jobs (resp. v-jobs, u-jobs)

Proposition 10 .

 10 Let π * be an instance of a scheduling problem with n = km unit processing time jobs where k is an integer. The decision version π Cj * asks: whether it has a schedule such that C j ≤ T CT * , where T CT * = k i=1 im. π Cj * is a yes-instance if and only if π * has a non-preemptive full schedule. Proof. If : A full non-preemptive schedule of π * has exactly C j = k i=1 im. Only If: If π * has a non-preemptive schedule such that C j ≤ k i=1 im, this schedule itself is a full schedule.

Figure 3 . 4 :

 34 Figure 3.4: x-jobs built by out-tree

Figure 3

 3 Figure 3.5: x-jobs built by an opposing-forest where green (brown) points represent an in-tree (out-tree)

  Considering the total completion time, we build another decision version πCj o.f. of π o.f. . We set the decision question as: whether π o.f. has a feasible schedule such that C j ≤ T CT * , where T CT * = qB+1 i=1 im. As π o.f. contains (qB + 1)m jobs, when preemption is allowed, by Proposition 10, π Cj o.f.

Figure 4 . 1 :

 41 Figure 4.1: Profile of an optimal schedule

Figure 4 . 2 :

 42 Figure 4.2:The in-tree graph. Job j is in red, set X is in box , L X (j) = ∅, P X (j) is solid, and S X (j) is in the oval.

Figure 4 . 3 :Figure 4 . 4 :

 4344 Figure 4.3: example: J T in graph G and an optimal schedule (S * )

Figure 4 .

 4 Figure 4.5: example: J ∪ J 1 in G and its reverse graph G R . The relation of height and level.

Figure 4 .

 4 Figure 4.6: example: schedule by Hu's algorithm and its reverse schedule

Propriety 4 .

 4 If A * = ∅ and A = ∅, jobs in A * and A are on the same level.

  .4. → γ 2 means that minimizing γ 1 is a sub-case of minimizing γ 2 . So, if it is N P-hard to minimize γ 1 , then, it is N P-hard to minimize γ 2 ; if the problem can be solved for γ 2 , then it can be solved for γ 1 .

	𝑖. 𝑡.	cℎ.	𝑜. 𝑡.
		𝑙. 𝑜.
	𝑠. 𝑝.
	Figure 1.4: Graphs relations
	1.3 Complexity result overview
	In this section, we give here a general overview of complexity results and open problems. Pinedo (2012)
	illustrates the complexity hierarchies of scheduling problems on objective functions, see Fig. 1.5, in which
	γ 1

.8. || Example 2.4.2 (A Complexity Hierarchy) Consider the problems

Table 1 .

 1

	t.	P(Hu, 1961)		OPEN	P(Brucker et al., 1977)
	l.o.	OPEN		OPEN	OPEN
	o.f.	NPH(Garey et al.,	OPEN	(NPH)
		1983)
	s.p.	(NPH)		OPEN	(NPH)
	i.t.,pmtn P(Gonzalez	and	OPEN	P(Lawler, 1982)
		Johnson, 1980)
	o.t.,pmtn P(Lawler, 1982)	P(Brucker et al., 2001)	OPEN
	l.o.,pmtn OPEN		OPEN	OPEN
	o.f.,pmtn OPEN		OPEN	OPEN
	s.p.,pmtn OPEN		OPEN	OPEN

1: An overview of open parallel scheduling problems with equal-processing-time jobs and (Chardon and Moukrim, 2005). The divide-and-conquer graph is defined and studied in (Kubiak et al., 2009) graphs.

These precedence graphs are not studied and detailed in this thesis, but a complete survey can be seen in (Prot and Bellenguez-Morineau, 2017).

Table 3 .

 3 1: An updated overview of complexity of P |p j = 1, β|γ

	t.	P(Hu, 1961)		NPH	P(Brucker et al., 1977)
	l.o.	NPH		NPH	(NPH)
	o.f.	NPH(Garey et al.,	(NPH)	(NPH)
		1983)
	s.p.	(NPH)		(NPH)	(NPH)
	i.t.,pmtn P(Gonzalez	and	OPEN	P(Lawler, 1982)
		Johnson, 1980)
	o.t.,pmtn P(Lawler, 1982)	P(Brucker et al., 2001)	NPH
	l.o.,pmtn NPH		NPH	(NPH)
	o.f.,pmtn NPH		NPH	NPH
	s.p.,pmtn (NPH)		(NPH)	(NPH)

  .1, where TC means average time consumed to solve the instances; '-' means the model did not solve any instance on this scale within 6000sec. Table 5.2: Number of variables and constraints, where BV/IV/C means number of binary variables/integer variables/constraints

		m		4		3	5	10
		n	15	30	60	30	30	30
		CM	0.92	1.22 13.32	0.98	0.34	0.06
	ROIM2	1.77	6.41 97.23	6.32	4.88	1.66
	AOIM	3.19 14.66	-14.32 13.98 14.53
	ROIM1 15.41 79.23	-	9.36	4.28	3.32
		TIM 48.39	-	-	-40.26 20.94
		Table 5.1: Performance of various models
	Model		BV	IV			C
	CM	n 2 + nm	2n		n 2 (m 2 + m + 1) + n
	ROIM2 n 2 m + nm	2n		2n 2 m + 2mn + n
	AOIM n 2 m + nm 2n + nm		3n 2 m + mn + n
	ROIM1	2n 2 m	2n		3n 2 m + n 2 + 2n
	TIM	nm p j	2n	n 2 m p

j + mn p j + mn + n

Preemption is advantageous means that there is always preemption in an optimal schedule.

Preemption is redundant means that there exists always an optimal schedule where there is no preemption even preemption is allowed.

Acknowledgement

List of Figures

The number of u-jobs in one component, which is w a in (1.1), is an integer multiple of 10q 2 . As PV i consists only of entire u-chains, |PV i | is an integer multiple of 10q 2 too. By definition, the u-jobs and v-jobs of a component consists of the same number of u-jobs and v-jobs, using |V i |≥ B -3q we just proved, we have |PV i |≥ |V i |≥ B -3q > B -10q 2 . As we have already |PV i |< B + 10q 2 , so B -10q 2 < |PV i |< B + 10q 2 , the only value that |PV i | can take is B.

As we have B + 3q -1 ≥ |PV 1 |, by Lemma 4, we have |PV 1 |= B. Now, we assume that the proposition |PV i |= B holds for i = 1, . . . , k, where k = 1, . . . , q -1. We aim at proving that it holds for k + 1.

As PV 1 , PV 2 , . . . , PV k are all finished no later than t = kB, they are executed in CI 0 , PI 1 , . . . , CI k-1 , PI k . We regroup this amount of work in two parts:

• Note the work of PV 1 , PV 2 , . . . , PV k in PI 1 , PI 2 , . . . , PI k as W ≤k PI ≤k ;

• Note the work of PV

Then, consider PV k+1 , which should be finished no later than t = (k +1)B. It is executed in CI 0 , PI 1 , CI 1 , . . . , CI k , PI k+1 . We regroup this amount of work in three parts:

• Note the work of PV k+1 in PI 1 , PI 2 , . . . , PI k as W k+1 PI ≤k ;

• Note the work of PV k+1 in PI k+1 as W k+1 PI k+1 ;

• Note the work of PV k+1 in CI 0 , CI 1 , . . . , CI k as W k+1 CI ≤k .

Similarly by Lemma 2, we have:

By Lemma 3, we have:

Using Lemma 3, we can directly deduce that the total amount of works in PI 1 , PI 2 , . . . , PI k is at most kB. Remind that in (3.2), the jobs in PV 1 , PV 2 , . . . , PV k take at least kB -3q 2 of these works. So, Proof. Each job in S J * (j A * ) ∩ J 2 has a predecessor in J * . This predecessor is strictly higher than j A * , and according to Propriety 7, jobs in B * are not higher than j A * . So, this predecessor can only be in A * .

Proof. According to the fact that J 1 ∪ J is scheduled by reversing the result of Hu's algorithm of G R . Let j R 1 , j R 2 be the images of j 1 , j 2 in G R . As j R 1 , j R 2 are initial jobs, by (4.1), h(j R 1 ) > h(j R 2 ), and according to Hu's algorithm, we have

We now prove that they are not in the same time slot, i.e. C j R 1 = C j R 2 . We separate J 1 ∪ J into two parts: pred(B * ) and pred(B * ) =: J 1 ∪ J \ pred(B * ). Then, note their images as pred(B * ) R and pred(B * ) R . As A = ∅, pred(B * ) R contains at least m initial jobs. Any finished job in pred(B * ) R can release at least one successor by the structure out-tree of G R . As pred(B * ) R are higher than pred(B * ) R , when it comes to the execution of j R 1 , at least m jobs in pred(B * ) R with priority to j R 2 are available, see Fig. 4.7. They fill this slot, and j R 2 has to be executed later. So,

Proof. We first prove S J * (j B * ) ∩ J 1 = ∅. Suppose by absurd that ∃j S ∈ S J * (j B * ) ∩ J 1 . By Corollary 14, j S has a successor in J , let it be j s S . By Corollary 15, j s S / ∈ B , so j s S ∈ A . As Propriety 4 and 7 hold, we have l(j s S ) ≥ l(j h B * ), where j h B * is the highest job in B * . However, j s S is a successor of j S , l(j S ) = l(j B * ) > l(j s S ) ≥ l(j h B * ), contradicts the fact that j h B * is the highest job in B * . Then, by Corollary 15, we have

In particular, when l(j B * ) < l(j lowest

lexicographic order and j S is the lexicographically first one, we have j S ∈ J . By Corollary 15, j S / ∈ B . So, j S ∈ A .

However, in Step 5 when constructing (S), we exchange jobs when 3 conditions are satisfied. Now, check the following 3 conditions:

1. As j S ∈ A , succ(j S ) begins strictly after J * .

2. As j A * ∈ A * , prec(j A * ) finishes strictly before J .

3. l(j S ) = l(j A * ), and j S lexicographically precedes j A * . j S should have been switched with j A * by Step 5. So, we have a contradiction. As j A * is the lexicographically first one, it is in Group 3.

Thirdly, we consider the other subcase, i.e. A = ∅. ∀j A * ∈ A * , we prove that j A * is in either Group 1 or Group 3.

Proof. If j A * is not a highest job in A * , we show that it is in Group 1. By Corollary 15 and Propriety 11,

If j A * is a highest job, we show that it is in Group 3. Suppose by absurd that j S is the lexicographically first job in S J * (j A * ), j S = j A * , and j S / ∈ J * . By Propriety 11, we have j S ∈ J 1 . In Step 5 when constructing (S), we exchange jobs when 3 conditions are satisfied. Now, we can state that:

1. The predecessors of j A * , which are higher than j S , finish before j S according to Propriety 9.

2. By Propriety 11, j S is final 3. l(j S ) = l(j A * ), and j S lexicographically precedes j A * . j S should have been switched with j A * in Step 5. So, we have a contradiction. Propriety 7 reveals that Group 3 which contains jobs in A * are not lower than Group 2, which contains jobs in B * . Thus, jobs in A * and B * are in one of the 3 groups, we accomplished the proof of regularity of J * .

The algorithm

We just proved that there always exists a regular set J * . To find the regular J * , we only need to explore all regular sets, which are recursively listed by Algorithm 1.

The sets are generated by choosing jobs from bottom to the top. Jobs added to C by line 10, 16 or 20 correspond to the 3 groups:

1. A m-limited job in Group 1 is picked from at most hm candidates.

2. A 2m-limited job in Group 2 is picked from at most 2hm candidates.

The lexicographically first job in Group 3 is picked from at most h candidates.

As each job is picked from at most 2hm candidates, noticing that m is fixed, the complexity is O(h m ). Line 26 is dedicated to the case where J * has a pure-m-limited superset. Creating subsets from at most m -1 jobs is in O(2 m ), which is a constant when m is fixed. Thus, the total complexity of the algorithm is O(h m ).

Example

We illustrate how the algorithm lists regular sets by the example in Fig. 4.8 where 19 jobs are to be scheduled by m = 3 parallel machines.

When k = 0 and L = ∅, the first loop gives:

• Line 10 adds {16}, {17}, {18}, {19}, {16, 17}

• line 16 adds {1}, {12}

Experiments

Our algorithm generates all regular sets in time O(h m ), while it requires extra calculation, for example, a tree-pruning of P in every step. It is still meaningful to implement our algorithm and compare it with Baptiste's algorithm on the running time.

For each couple n, m, we create 5 different instances with a height from 3 to 6, on which we ran both algorithms. The instances of in-trees are randomly generated in the following way:

1. generate a chain of length h = 3, . . . , 6 2. create n jobs 3. randomly (equiprobably) assign each job a successor from candidate jobs where candidate jobs are those who have already at least 1 but at most h -1 successors

We report the average time consumed in table 4.1.

As it can be seen, both algorithm consumed exponential time to n while our algorithm performs much better. The theoretical ratio is O(n m ) O(h m ) = O(w m ) where w = n h can be regarded as the average width. However, the experimental ratio is not so perfectly exponential to n due to the randomness.

(5.1d)

(5.1a) defines C j . (5.1b) describes the precedence constraints. (5.1c) and (5.1d) make sure that each job is executed only once.

In TIM, the variables has a time index t. In the following, we present the other models, in their principal variables, the solution are represented by the order of jobs executed in the schedule.

Relative-Order-Indexed Model1 (ROIM1)

This model uses binaries y θ j ,j and z θ j ,j as decision variables. y θ j ,j = 1 if j is executed immediately before j on θ; z θ j ,j = 1 if j is executed before j on θ. The relative order of job j and j is implied in y θ j ,j and z θ j ,j if they are on the same machine.

Different formulations of this model can be seen in B lażewicz et al. (1991) and Unlu and Mason (2010) for parallel scheduling problems without precedence constraints. We introduce S j and C j for precedence constraints by adding (5.2b), and we propose the following formulation:

(5.2a)

(5.2a) ensures that z θ j ,j = 1 if y θ j ,j = 1. (5.2c), (5.2d), (5.2e) and (5.2f) enforce each job to have exactly one predecessor and one successor. Notice that in (5.2e) and (5.2f), each job has to be executed before (after) some other job. In practice, some dummy jobs are created to represent jobs after (before) the last (first) executed jobs on each machine.

In fact, (5.2e) and (5.2f) convey the same meaning: if every job follows another (except the first one), then every job has a follower (except the last one). If we remove one of (5.2e) and (5.2f), experimental results show that the model still works well, but slower. So, we kept them. We call them redundant constraints.

Relative-Order-Indexed Model 2 (ROIM2)

We present another relative-order-indexed model, which uses binaries z θ j ,j and x θ j as decision variables.

To associate these two variables, [START_REF] Low | Modelling and heuristics of fms scheduling with multiple objectives[END_REF] and [START_REF] Gao | Scheduling jobs and maintenances in flexible job shop with a hybrid genetic algorithm[END_REF] use the following non-linear constraint for job shop problems:

The version for job shop problem in Özgüven et al. ( 2010) is linear. However, it introduces new integer variables. Here, we proposed a new formulation, which is linear and does not introduce new integer variables:

(5.3a)

(5.3d) z θ j ,j + z θ j,j ≤ 1, ∀j, j ∈ J T , θ ∈ M T (5.3e) M (z θ j ,j + z θ j,j ) ≥ x θ j + x θ j -1, ∀j , j ∈ J T , θ ∈ M T

(5.3a) forces each job to be executed once. (5.3b) ensures that C j ≤ S j if z j ,j = 1. (5.3c) considers one case: x θ j = 0 then ∀j ∈ J T , z θ j ,j = 0. (5.3c) means that only one of z θ j ,j and z θ j,j takes value 1. (5.3e) works when both j , j are on θ, and forces one to precede the other. We remind the reader that M is a relative large number.

Absolute-Order-Indexed Model (AOIM)

We consider another model which uses β l θ,j as its principal variable. The variable equals 1 if j is the l th job on θ, where l is the absolute-order.

It was originally designed for parallel scheduling problem without precedence constraints by B lażewicz et al. (1991). To add precedence constraints for job shop problems, Demir and İşleyen (2013) introduces T l θ to the model, which is the starting time of the l th job of θ, and x θ j to indicate the machine of jobs. Here, we propose a similar formulation, where we removed the variables x θ j from the formulation of (Demir and İşleyen, 2013):

(5.4a)

(5.4e) forces each job to be executed once. (5.4d) ensures that only one job can be executed as the l th job on θ. (5.4c), (5.4b) and (5.4a) works when β l θ,j = 1, they guarantee T l θ = S j and T l+1 θ -T l θ = p j .

Compact Model (CM)

We propose a new order-indexed model here. It can be seen as an improved ROIM. It uses δ j ,j , which equals 1 if j is executed before j on the same machine, and x θ j as decision variables.

(5.5a)

(5.5a) connects δ j ,j , C j and S j (if δ j ,j = 1 then C j ≤ S j ). When both j , j are on θ, (5.5b) forces one precedes the other. (5.5d) makes each job be executed exactly once. (5.5c) sets δ j ,j and δ j,j as 0 when j , j are on different machines.

Notice that when minimizing C max , (5.5c) is redundant because when j , j are on different machines, δ j ,j = 1 or δ j,j = 1 can not reduce C max . However, it helps to give δ j ,j a comprehensible meaning (δ j ,j = 1 if and only if j precedes j on the same machine) and has a positive impact on the model.

Conclusion and Perspective

We adapted models to the parallel scheduling problem with precedence constraints and proposed a new one which outperforms the others in running test. TIM, ORIM1, ORIM2 and AOIM have an original version for flexible job-shop problem (FJSP). The only difference is that FJSP has dedicated machine constraints, which means the machines are not identical. It's not hard to add these constraints to our new model and adapt it to FJSP. We conjecture that it can still win out over the others. For parallel scheduling problem, they can also be easily adapted to other objective function such as the total completion timeor L max by adding a constraint on C j . The model can be employed not only for the scheduling problems but for other ordered assignment problems as well.

Besides, the time to solve does not depend merely on instance's scale, but also on number of machines, the processing time of jobs, and the shape of precedence constraints. The model is helpful to study experimentally how the different precedence constraints impact the time to solve.

Model