# A Multiobjective Optimization Approach to Solve a Parallel Machines Scheduling Problem

Authors: Xiaohui Li; Lionel Amodeo; Farouk Yalaoui; Hicham Chehade
Journal: Advances in Artificial Intelligence
 (2010)

---

## Abstract

A multiobjective optimization problem which focuses on parallel machines scheduling is considered. This problem consists of schedulingn independent jobs on m identical parallel machines with release dates,
due dates, and sequence-dependent setup times. The preemption of jobs is forbidden. The aim is to minimize
two different objectives: makespan and total tardiness. The contribution of this paper is to propose first a new mathematical
model for this specific problem. Then, since this problem is NP hard in the strong sense, two well-known approximated methods,
NSGA-II and SPEA-II, are adopted to solve it. Experimental results show the advantages of NSGA-II for the
studied problem. An exact method is then applied to be compared with NSGA-II algorithm in order to prove the efficiency of
the former. Experimental results show the advantages of NSGA-II for the studied problem. Computational experiments show that on
all the tested instances, our NSGA-II algorithm was able to get the optimal solutions.


---

## Body

## 1. Introduction

The parallel machines scheduling problem is a widely studied optimization problem. This problem considers several available identical machines to execute a set of jobsN={1,…n}. Indeed, it can be described as a special hybrid flowshop scheduling problem which has only one stage. Every job j is considered with a processing time pj, a release date rj, a due date dj, and a sequence-dependent setup time sij which means the transfer time between two adjacent jobs i and j (job j is scheduled immediately after job i). Two different objectives are minimized at once in this work: makespan and total tardiness. According to the lawler scheduling classification, the studied problem is defined as Pm|sij,rj|(Cmax,∑Tj) [1].The most studied criteria for scheduling problems is the makespan. It is the completion time of the job which is finished at last (maximum completion time of jobs). Cheng and Sin [2] have proved that the problem of minimizing the makespan on two identical parallel machines is NP hard. Burcker [3] has proved that if the number of machines is greater than two, then the problem is even strongly NP hard. In the literature, many methods are proposed to solve it. Gendreau et al. [4] have proposed a heuristic and a lower bound for the Pm|sij|Cmax problem. Yalaoui and Chu [5] have proposed a heuristic for Pm|sij,split|Cmax. An exact method is also developed to solve it. Gharbi and Haouari [6] have proposed a lower bound and use the branch-and-bound method to solve the Pm|rj,qj|Cmax problem, where qj is the delivery time. Néron et al. [7] have used two branching schemes for the parallel machines scheduling problem with release dates and tails. Zouba et al. [8] present heuristic algorithms to solve a parallel machines scheduling problem with a period-based changing mode operators to minimize the makespan. Fanjul-Peyro and Ruiz [9] have proposed the size-reduction heuristics for the unrelated parallel machines scheduling problem with the minimization of makespan.The total tardiness is another concerned criterion which is the sum of tardiness of all jobs. The parallel machines scheduling problem to minimize the total tardiness is known as NP hard according to Koulamas [10]. Some exact methods are proposed to solve this problem. Azizoglu and Kirca [11] have proposed a branch-and-bound method to the parallel machines problem with total tardiness minimization. Yalaoui and Chu [12] have also developed a lower bound and a branch-and-bound to solve the same problem. In the work of  Shim and Kim [13], they developed dominance properties and a lower bound for the same problem, and a branch-and-bound method is adopted to solve it. In 2008, Shim and Kim [14] have used a branch and bound algorithm for solving a parallel machines scheduling problem with a job splitting property. Nguyen et al. [15] proposed a new dynamic programming formulation for solving this problem. Moreover, many heuristics have been developed, such as of Pritsker et al. [16], Alidaee and Rosa [17], Baker and Bertrand [18], and Lamothe et al. [19].Many approximated methods have been proposed to solve the multiobjective optimization problems (MOPs). In 1985, Schaffer [20] proposed an algorithm named VEGA (vector evaluated genetic algorithm) to solve the multiobjective optimization problem. It was the first method which is based on the simple genetic algorithm to solve MOPs. Kursame [21] has proposed the VOES method (Vector-Optimization Evolution Strategy) in 1990. Hajela and Lin [22] have proposed the HLGA (Hijela’s and Lin’s genetic algorithm) in 1993, but these three algorithms are non-Pareto approaches. In the multiobjective optimization problems, there is no single optimal solution, but a set of nondominated solutions. They are called the Pareto optimal solutions. Recently, the Pareto-based approaches are interested by the researchers. Multiple Objective Genetic Algorithms (MOGA) [23], Niched Pareto Genetic Algorithm (NPGA) [24], Nondominated Sorting Genetic Algorithm (NSGA-II) [25], Strength Pareto Evolutionary Algorithm (SPEA-II) [26], Pareto Archived Evolution Strategy (PAES) [27] and Pareto envelope-based selection algorithm (PESA) [28] are proposed for solving MOP and widely used for scheduling problems.The parallel machines multiobjective scheduling problem is NP hard in the strong sense. Therefore, approximated methods are widely proposed for solving it. In 2003, Cochran et al. [29] have proposed a two-stage multipopulation genetic algorithm (MPGA) to minimize three different criteria: makespan, the total weighted tardiness, and the total weighted completion time. Chang et al. [30] have minimized the makespan and the total tardiness for parallel machines scheduling problem in 2005 by means of a two-phase subpopulation genetic algorithm (SPGA). The numerical results demonstrate that the SPGA is better than NSGA-II and MOGA. After that, they have proposed a modified version of SPGA by using a global archive and an adaptive strategy for solving the same problem [31] in 2006. In the works of Baesler et al. [32], a multiobjective optimization algorithm is appropriate to solve the Pm||(Cmax,∑Tj) problem. This algorithm is the combination of a genetic algorithm and a local search and is compared with the MOGA and the MOSA for the Pm||(Cmax,∑Tj) problem. Furthermore, Baesler et al. [33] have proposed MultiObjective Simulated Annealing with Random Trajectory Search (MOSARTS) for the same problem. Bouibede-Hocine et al. [34] used NSGA-II and SPEA for the P|ri,di|Cmax,Lmax problem. Dugardin et al. [35] have used the NSGA-II for solving a hybrid job shop and a parallel machines scheduling problems. Gao et al. [36] have presented a new parallel genetic algorithm for the multiobjective parallel machines scheduling problem which is subjected to a special process constraint. The aim is the minimization of the makespan and the earliness/tardiness penalty. Later, Gao [37] have proposed a novel artificial immune system for solving the same problem. Fang [38] proposed an improved weighted-based multiobjective genetic algorithm for the typical parallel machines scheduling problem. Lian [39] have proposed a united search particle swarm optimization algorithm for the parallel machines problem with different due dates. Chyu and Chang [40] have developed a pareto evolutionary algorithm for a biobjective unrelated parallel machines scheduling problem.Our main contribution in this paper is to consider a special multiobjective parallel machines scheduling problem taking in consideration additional constraints compared to other previous works such as these of Baesler et al. [32, 33] or that of Bouibede et al. [34]. These additional constraints are the release date, the due date and the sequence-dependent setup times. At our knowledge, no other studies take in consideration all these constraints for multiobjective parallel machines scheduling problem, and thus we may consider that the problem studied in this paper is a specific scheduling problem.Furthermore, as the problem is NP hard in the strong sense, two approximated methods: thenon-dominated sorting genetic algorithm (NSGA-II) and Strength Pareto Evolutionary Algorithm (SPEA-II) are developed in this paper for the first time to solve the studied problem. An integer mathematical model is also proposed for modelling this problem, and we have proposed a special chromosome to encode it. An exact method is applied to demonstrate the efficiency of the proposed methods.The rest of the paper is organized as follows: Section2 describes the considered problem and the mathematical model. In Section 3, we develop the NSGA-II and the SPEA-II algorithms. Computational results are shown in Section 4. Our conclusion and perspectives are given in Section 5.


## 2. Problem Description and Mathematical Formulation

In the parallel machines scheduling problem, a set ofn independent jobs should be scheduled on m identical machines without preemption. Each job has a processing time pj, a release date rj and a due date dj. The sequence-dependent setup times sij are also considered in this problem. It deals with the setup time when a machine switches the production from job i to job j (job i precedes immediately job j on the same machine). Without loss of generality, we have set sjj=0. We assume that s0j=0, and it means that if job j is scheduled at the beginning on a machine, no setup time is required. All these job data are generated randomly based on a protocol test which is described in Section 4. Some assumption must be respected: each machine can execute only one job at once; each job can be processed only once.Some notations are defined below:n:
the number of jobsm:
the number of machinesj:
the index of jobsj=1,…,nk:
the index of machinesk=1,…,mr:
the order of job in the machinerj:
the release date of jobj, j=1,…,ndj:
the due date of jobj, j=1,…,nsij:
the sequence-dependent setup times if jobj is the immediate successor of the job i on the same machine.pj:
the processing time of jobj, j=1,…,nCj:
the completion time of jobj, j=1,…,nTj:
the real tardiness of jobj, j=1,…,n, Tj=max(Cj-dj,0)Cmax:
make span,Cmax=maxjCjnk:
the number of jobs assigned to machinek.The problem can be formulated as follows:(1)Minimize⁡(Cmax⁡,∑Tj),
subject to(2)∑j=1nXjkr=1k=1,2,…,m,r=1,2,…,nk,(3)∑k=1m∑r=1nkXjkr=1,j=1,2,…,n,(4)p[kr]=∑j=1nXjkrpj,k=1,2,…,m,r=1,2,…,nk,(5)s[kr]=∑i=1n∑j=1nXjkrYijsij,k=1,2,…,m,r=1,2,…,nk(6)r[kr]=∑j=1nXjkrrj,k=1,2,…,m,r=1,2,…,nk,(7)d[kr]=∑j=1nXjkrdj,k=1,2,…,m,r=1,2,…,nk,(8)C[kr]=max⁡(C[k,r-1]+s[kr],r[kr])+p[kr],k=1,2,…,m,r=1,2,…,nk,(9)T[kr]=max⁡(C[kr]-d[kr],0),k=1,2,…,m,r=1,2,…,nk,(10)Cmax⁡=max⁡k=1mmax⁡r=1nkC[kr],(11)∑Tj=∑k=1m∑r=1nkT[kr],(12)Xjkr=0or1,k=1,2,…,m,r=1,2,…,nk,j=1,2,…,n,(13)Yij=0or1,i=1,2,…,n,j=1,2,…,n.Equation (1) represents the objective function, and the goal of our work is to minimize the makespan and the total tardiness. Constraint (2) ensures that only one job can be scheduled at the rth job position. Constraint (3) means that each job can be scheduled only once. Constraints (4)–(9) denote the data of jobs which are scheduled at the rth job position of kth machine position jobs, such as processing times, setup times, release dates, due dates, completion times, and tardiness times. Constraints (10) and (11) explain how to compute the makespan and the total tardiness. Constraint (12) is a decision variable: if job j is scheduled on machine i in position r, then Xjkr=1, otherwise 0. Constraint (13) shows that if job j is the immediate successor of the job i on the same machine, then Yij=1; otherwise, Yij=0.


## 3. Resolution Methods

In this section, two approximated methods and an exact method are developed to solve our problem. Two well-known algorithms have been chosen: NSGA-II and SPEA-II. The experimental results of these algorithms are compared in the following section.


### 3.1. Encoding Strategy

A special encoding of the studied problem is presented here. It is adopted for our developed methods: NSGA-II and SPEA-II. A chromosome (see Table1) with a (N×3) matrix is proposed to encode the problem. The elements in each column correspond to the job index, the number of the machine where the job is scheduled, and the position of the job on the machine. It is described hereafterTable 1
An example of chromosome.
N# of jobs12345N# of machine12112Position on the machinek21132a(j,1) shows the index of jobs, j=1,2,…,n,(14)a(j,2)={kifjobjisscheduledonmachinek,0otherwise,(15)a(j,3)={rifjobjisscheduledatpositionronthemachine,0otherwise,All feasible solutions of the initial population are randomly generated. A HOT (High priority Order Transition) sequence rule is adopted here. A random value is generated in a uniform distribution [0,1] for each job, and all the jobs are ranked by the decreasing order of this value. Thereafter, the job with the highest value is served first on the machine which is earliest available.For instance, Table1 presents an example for which the Gantt chart is illustrated in Figure 1.Figure 1
An example of the Gantt chart.


### 3.2. NSGA-II

The Non-dominated Sorting Genetic Algorithm (NSGA-II) is the second version of the NSGA algorithm. The latter has been widely used to solve multiobjective optimization problems. It was proposed by Deb et al. [25] in 2000 as a fast and efficient multiobjective genetic algorithm to find the non-dominated solutions based on the Pareto dominance relationship. In this algorithm, the procedure begins starting from the creation of an initial population. All the feasible solutions in this population are randomly generated. At each generation, selection, crossover, and mutation operations as well as ranking, the different solutions are realized. These four operations are the main concept of the NSGA-II.The binary tournament technique is used in the operations of the parents selection. We chose the classic one-point crossover operator in this study, and an operator of reparation is necessary for the created children. In the mutation operator, two columns are randomly chosen and they are interchanged. In the operator of ranking, all the different solutions are assigned to several non-dominated fronts. A computation of the crowding distance has been done to sort the solutions in the same front.Several parameters are to be set in this algorithm. The population size and the number of generations determine the computational duration. The crossover probability and the mutation probability decide the convergence and the diversity of the results. The parameters setting of NSGA-II is complex. In this work, several tests have been carried out to choose the best parameters of crossover and mutation probabilities. We have tested this problem with a crossover probability equal to{0.6,0.7,0.8,0.9,1.0} and {0.05,0.1,0.15,0.20,0.25} for the mutation probability. The final values of the parameters are chosen according to the measuring criteria which are presented in Section 4. We have set a great crossover probability equal to 0.9 and a small mutation probability equal to 0.1. The population size and the generation number are set to 100. For the comparison with another approximated method, a fixed computing time is considered as the stopping criteria. We have chosen 1 second, 2 seconds, and 5 seconds for the different problems (see Section 4).The main process of NSGA-II is described in Algorithm1 [25].Algorithm 1:Structure of the NSGA-II algorithm [25].
(1) Generate the initial populationPt of size ns(2) Evaluate these solutions(3) Sort these solutions by non domination and crowding distance(4) Creation of the offspring populationQt with the operators of selection, crossover and mutation(5) Evaluate all solutions(6) Sort the solutions of two populations:Pt and Qt(7) Choose the best solutions for the new populationPt with the remaining steps (ranking into nondominated front, crowding distance)(8) If the stopping criteria is satisfied then the algorithm is stopped, the obtained results are all thesolutions in the first non dominated front; repeat steps (4) to (7) otherwise


### 3.3. SPEA-II

The second version of the SPEA (Strength Pareto Evolutionary Algorithm) is presented here, which has been introduced by Zitzler et al. [26]. A regular population and an archive mechanism (Pareto archive) are used in SPEA-II. During the generation, all the non-dominated solutions are copied to the Pareto archive. Compared with SPEA, the Pareto archive size is fixed in this algorithm. The Pareto archive is filled with the non-dominated solutions until the considered archive size. If there are not enough non-dominated solutions, the dominated solutions which have the best objective values are also considered. On the other side, if there are too many non-dominated solutions than the archive size, we only kept the best of them with a decreasing order of distance σ (see [26]).We have used the same operations used in NSGA-II for the selection, crossover, and mutation. In the parameters settings of the algorithm, we have chosen the same crossover probability, mutation probability, and size of the population. We have set the archive size to 50 based on the tested results. The main concept of SPEA-II is described in Algorithm2 [26].Algorithm 2:Structure of the SPEA-II algorithm [26].
(1) Generate an initial populationPt and an empty Pareto archive Qt, set t to 0(2) Evaluate all the solutions inPt and Qt(3) Find the non dominated solutions betweenPt and Qt. If there are too many non dominatedsolutions for the archive, calculate the distanceσ of the solutions, we only kept the best solutionswith a decreasing order of distanceσ. In contrary, if there are not enough non dominated solutions inthe archive, the best dominated solutions must be filled in the archive till this archive is full(4) If the stopping criteria is satisfied, then stop the algorithm and export the non dominatedsolutions in the Pareto archive as the result(5) The operators of selection, crossover and mutation are applied for the new populationPt+1, andthen return to step (2)


### 3.4. Exact Method

A full enumeration method is applied here. The aim is to enumerate all the feasible solutions and find the absolute Pareto optimal solutions among them. We have used the same ranking operation of NSGA-II to find the nondominated solutions. Because of the too long computational times, this method can be applied only the small instances. The results of the comparison between the exact method and the NSGA-II algorithm (which has been proved to be better than SPEA-II as shown in the next section) are shown in the following section.


## 3.1. Encoding Strategy

A special encoding of the studied problem is presented here. It is adopted for our developed methods: NSGA-II and SPEA-II. A chromosome (see Table1) with a (N×3) matrix is proposed to encode the problem. The elements in each column correspond to the job index, the number of the machine where the job is scheduled, and the position of the job on the machine. It is described hereafterTable 1
An example of chromosome.
N# of jobs12345N# of machine12112Position on the machinek21132a(j,1) shows the index of jobs, j=1,2,…,n,(14)a(j,2)={kifjobjisscheduledonmachinek,0otherwise,(15)a(j,3)={rifjobjisscheduledatpositionronthemachine,0otherwise,All feasible solutions of the initial population are randomly generated. A HOT (High priority Order Transition) sequence rule is adopted here. A random value is generated in a uniform distribution [0,1] for each job, and all the jobs are ranked by the decreasing order of this value. Thereafter, the job with the highest value is served first on the machine which is earliest available.For instance, Table1 presents an example for which the Gantt chart is illustrated in Figure 1.Figure 1
An example of the Gantt chart.


## 3.2. NSGA-II

The Non-dominated Sorting Genetic Algorithm (NSGA-II) is the second version of the NSGA algorithm. The latter has been widely used to solve multiobjective optimization problems. It was proposed by Deb et al. [25] in 2000 as a fast and efficient multiobjective genetic algorithm to find the non-dominated solutions based on the Pareto dominance relationship. In this algorithm, the procedure begins starting from the creation of an initial population. All the feasible solutions in this population are randomly generated. At each generation, selection, crossover, and mutation operations as well as ranking, the different solutions are realized. These four operations are the main concept of the NSGA-II.The binary tournament technique is used in the operations of the parents selection. We chose the classic one-point crossover operator in this study, and an operator of reparation is necessary for the created children. In the mutation operator, two columns are randomly chosen and they are interchanged. In the operator of ranking, all the different solutions are assigned to several non-dominated fronts. A computation of the crowding distance has been done to sort the solutions in the same front.Several parameters are to be set in this algorithm. The population size and the number of generations determine the computational duration. The crossover probability and the mutation probability decide the convergence and the diversity of the results. The parameters setting of NSGA-II is complex. In this work, several tests have been carried out to choose the best parameters of crossover and mutation probabilities. We have tested this problem with a crossover probability equal to{0.6,0.7,0.8,0.9,1.0} and {0.05,0.1,0.15,0.20,0.25} for the mutation probability. The final values of the parameters are chosen according to the measuring criteria which are presented in Section 4. We have set a great crossover probability equal to 0.9 and a small mutation probability equal to 0.1. The population size and the generation number are set to 100. For the comparison with another approximated method, a fixed computing time is considered as the stopping criteria. We have chosen 1 second, 2 seconds, and 5 seconds for the different problems (see Section 4).The main process of NSGA-II is described in Algorithm1 [25].Algorithm 1:Structure of the NSGA-II algorithm [25].
(1) Generate the initial populationPt of size ns(2) Evaluate these solutions(3) Sort these solutions by non domination and crowding distance(4) Creation of the offspring populationQt with the operators of selection, crossover and mutation(5) Evaluate all solutions(6) Sort the solutions of two populations:Pt and Qt(7) Choose the best solutions for the new populationPt with the remaining steps (ranking into nondominated front, crowding distance)(8) If the stopping criteria is satisfied then the algorithm is stopped, the obtained results are all thesolutions in the first non dominated front; repeat steps (4) to (7) otherwise


## 3.3. SPEA-II

The second version of the SPEA (Strength Pareto Evolutionary Algorithm) is presented here, which has been introduced by Zitzler et al. [26]. A regular population and an archive mechanism (Pareto archive) are used in SPEA-II. During the generation, all the non-dominated solutions are copied to the Pareto archive. Compared with SPEA, the Pareto archive size is fixed in this algorithm. The Pareto archive is filled with the non-dominated solutions until the considered archive size. If there are not enough non-dominated solutions, the dominated solutions which have the best objective values are also considered. On the other side, if there are too many non-dominated solutions than the archive size, we only kept the best of them with a decreasing order of distance σ (see [26]).We have used the same operations used in NSGA-II for the selection, crossover, and mutation. In the parameters settings of the algorithm, we have chosen the same crossover probability, mutation probability, and size of the population. We have set the archive size to 50 based on the tested results. The main concept of SPEA-II is described in Algorithm2 [26].Algorithm 2:Structure of the SPEA-II algorithm [26].
(1) Generate an initial populationPt and an empty Pareto archive Qt, set t to 0(2) Evaluate all the solutions inPt and Qt(3) Find the non dominated solutions betweenPt and Qt. If there are too many non dominatedsolutions for the archive, calculate the distanceσ of the solutions, we only kept the best solutionswith a decreasing order of distanceσ. In contrary, if there are not enough non dominated solutions inthe archive, the best dominated solutions must be filled in the archive till this archive is full(4) If the stopping criteria is satisfied, then stop the algorithm and export the non dominatedsolutions in the Pareto archive as the result(5) The operators of selection, crossover and mutation are applied for the new populationPt+1, andthen return to step (2)


## 3.4. Exact Method

A full enumeration method is applied here. The aim is to enumerate all the feasible solutions and find the absolute Pareto optimal solutions among them. We have used the same ranking operation of NSGA-II to find the nondominated solutions. Because of the too long computational times, this method can be applied only the small instances. The results of the comparison between the exact method and the NSGA-II algorithm (which has been proved to be better than SPEA-II as shown in the next section) are shown in the following section.


## 4. Computational Results

### 4.1. Definition of the Protocol Test

For the computational experiments, a protocol test is developed in which the job data are randomly generated. The job data include the processing timespj, the release dates rj, the due dates dj and the sequence-dependent setup times sij. In a previous work [41], we have presented a protocol test based on the work of [12, 42]. For each job, the processing times pj are generated using a uniform distribution [1,100]. After the generation of the processing times, the setup times sij are set to α×min(pi,pj), where α is a coefficient randomly generated in [A,B], and [A,B]∈{[0.1,0.2],[0.1,0.5]}. The release dates are generated using a uniform distribution [0,50.5×N×β/M]. The value of β is considered from {0.6,0.8} [43]. The due dates of jobs are in the interval [P×(1-TF-(RDD/2)), P×(1-TF+(RDD/2))], where P=∑j=1npj/m, and we have chosen TF and RDD between 0.2 and 0.4. Since there are four parameters to set, and two values are proposed to each parameter, we have then 16 different configurations to test, and the index of each configuration is shown in Table 2. For the comparison of two approximated methods, three types of instances have been processed: the problem with 10 jobs and 3 machines, the problem with 20 jobs and 3 machines, and the problem with 50 jobs and 5 machines. The full enumeration method cannot be applied on large problems because of the too long execution times. Therefore, the comparison between the proposed methods and the full enumeration method is realized on the problems with 5, 6, 7, and 8 jobs.Table 2
The index of configurations.
β, [A,B]TF, RDD0.20.20.40.40.20.40.20.40.6, [0.1, 0.2]12340.8, [0.1, 0.2]56780.6, [0.1, 0.5]91011120.8, [0.1, 0.5]13141516


### 4.2. Measuring Criteria

The comparison of two different Pareto fronts for solving the same MOP is very complicated, since each front is not a single scalar value, but a set of non-dominated solutions. An approximated method involves the following objectives [44]: the distance to the absolute Pareto optimal front is to be minimized, the diversity of the generated solutions is to be maximized and the spread of the obtained front is to be maximized.Recently, several measuring criteria have been proposed for comparing two non-dominated fronts. Ranjithan et al. [45] have proposed a spread metric which determines the maximum range represented by the non-dominated solutions in the objective space and a coverage metric that characterizes the distribution of solutions. Kumar and Ranjithan [43] have proposed a D factor that represents the degree of dominance of non-dominated solutions from two obtained fronts which are produced by two different algorithms. Van Veldhuizen [46] has proposed an error-ratio criterion and a generational distance (GD). The former one represents the proportion of nontrue Pareto solutions in the obtained front. It measures the general progress to the reference set. Zitzler and Thiele [44] have presented a Zitzler measure, a μ distance is presented by Riise [47]. The two latter measures were adopted in this work, because they do not require to compute the absolute Pareto optimal front (reference set). The number of nondominated solutions ns of the Pareto front is also considered in our work.LetA and B be two Pareto fronts obtained by different methods. nA and nB are the number of nondominated solutions in fronts A and B, respectively. The μ distance is defined as μ=∑i=1nAdi/nA, where di is the distance between solution i of A and its orthogonal projection on B. The value of di is negative, when solution i is below the front B (or the extrapolated front). The μ distance shows if front A is closer to the optimal solutions than front B. The lower of the value μ we find, the better quality of front A we will get.The Zitzler measure has been presented by Zitzler and Thiele [44], where C1 measures the ratio of solutions in A which are dominated by at least one solution in B. The equation is defined by C1=|{a∈A∣∃b∈B:b≻a}|/|A|, where a and b are the non-dominated solutions in fronts A and B respectively. When C1=1, it means that all of the solutions in A are dominated by solutions in B. However, when C1=0, it means that there are no solutions in A that are dominated by at least one solution in B. On the other side, C2 measures the ratio of solutions in B which are dominated by at least one solution in A.


### 4.3. Results

#### 4.3.1. Comparison of NSGA-II and SPEA-II

First, the experimental results of NSGA-II and SPEA-II are compared. Figure2 shows an example where 20 jobs should be scheduled on 3 identical parallel machines. The objective values of all the obtained solutions are shown in Table 3. We can observe that the front obtained by NSGA-II dominates the other front obtained by SPEA-II. Indeed, in this example, we have C1=0, which means that there is no solution in the NSGA-II front that is dominated by at least a solution from SPEA-II. C2=1 means that all the solutions of SPEA-II are dominated by at least one solution of NSGA-II front. Finally, we have μ=-38.071; μ is negative because the NSGA-II front dominates the SPEA-II front.Table 3
Objective values correspond to the NSGA-II/SPEA-II comparison.
Number of solutionNSGA-IISPEA-IICmax∑TjCmax∑Tj14141256416144924151202423135034161060431133844189904331022542096843610036432952469100174399328440867Figure 2
Example of NSGA-II/SPEA-II comparison.Tables 4, 5, and 6 show the comparison results of NSGA-II and SPEA-II to solve three different problems with 16 different configurations. The index of the configuration is shown in Table2. For each configuration, we have tested 10 instances. The mean value of μ, the minimum value and the maximum value of μ(max_μandmin_μ), the mean values of C1 and C2 are presented. In this work, 480 instances are therefore tested.The first line of Table4 is explained. This problem is defined with 10 jobs and 3 machines. Index 1 means that the jobs data are randomly generated with β=0.6, [A,B]=[0.1,0.2], RDD=0.2, and TF=0.2 (see Table 3). The next 7 elements show the comparison results. Since each configuration is tested for ten instances, the value of ns shows that the NSGA-II has obtained more non-dominated solutions than SPEA-II with respective mean values of 4 and 3.2. The mean value of the Riise distance μ=-10.719 indicates that the obtained front of NSGA-II dominates the SPEA-II front, since this value is negative. The minimum and maximum values of μ are both negatives, which means that the Riise distance is always negative during the ten tests. The results show that C1=0; that is, there are no solutions provided by NSGA-II that are dominated by at least one solution of the SPEA-II. On the other side, C2=1 means that all solutions provided by SPEA-II are dominated by at least one solution of NSGA-II.Table 4
The comparison results for 10 jobs and 3 machines.
nsNSGA-IInsSPEA-IIμmax_μmin_μC1C2143.2-10.719-0.427-32.9980.0200.94123.73.7-23.331-5.572-57.5410134.53.6-12.328-6.213-29.6210.0330.96044.83.7-8.414-0.236-36.0700.0200.82054.33.1-12.079-0.437-25.0910.0400.85064.23.6-11.865-7.612-20.7590174.83.3-16.530-5.301-39.4320184.54.3-16.052-4.020-37.31400.98093.63.4-28.844-1.658-36.94800.9671033.6-29.923-24.467-40.08201114.23.5-21.510-4.712-63.82100.917124.73.3-17.275-1.108-36.91500.967133.33.2-20.658-2.105-44.0510.0330.883143.43.6-20.507-5.982-38.35801153.43.1-6.748-0.369-25.93801163.33-2.677-1.189-7.18400.900Table 5
The comparison results for 20 jobs and 3 machines.
nsNSGA-IInsSPEA-IIμmax_μmin_μC1C215.23.6-57.783-26.900-157.1650126.23.8-64.773-19.398-183.8240136.73.8-43.357-9.967-116.9360146.73.7-80.565-11.515-158.0750.0200.98655.63.9-38.786-5.863-65.5530166.34.5-84.840-15.780-150.4370176.33.3-70.763-13.980-121.5990186.64.2-130.905-39.507-207.3970194.44.4-89.322-33.199-242.74201105.63.6-90.343-19.670-177.62601115.43.5-69.500-30.652-162.87001126.63.7-102.433-16.751-226.405011353.9-83.883-19.717-160.02701145.23.6-61.100-3.506-122.7100.0250.950156.83.7-56.728-18.379-96.92601164.53.5-125.261-33.281-199.40401Table 6
The comparison results for 50 jobs and 5 machines.
nsNSGA-IInsSPEA-IIμmax_μmin_μC1C215.44.4-121.605-71.3029-276.4540126.93.9-95.738-28.279-251.5800.0570.93336.95.7-147.188-63.880-253.70101474.7-131.867-26.957-255.18101563.2-151.970-58.576-281.4310165.22.9-168.611-101.356-280.06801773.8-194.197-73.031-302.2000186.73.4-132.477-51.033-212.6410195.24-161.820-75.712-253.03701107.13.5-177.886-46.687-287.34501117.44-147.448-58.326-305.01701127.14.4-163.878-22.844-362.630011354.1-149.905-71.089-269.73301145.73.8-207.573-63.686-291.703011573.4-189.336-103.498-277.89201167.43.5-201.379-62.870-325.05001In this work, we have chosen a fixed computing time as a stopping criterion for NSGA-II and SPEA-II. One second, two seconds, and five seconds are the execution times that are fixed for the problems with 10 jobs, 20 jobs, and 50 jobs, respectively. Tables 4, 5, and 6 show a comparison between NSGA-II and SPEA-II for the tested instances.The values ofμ are always negative, which means that the NSGA-II front always dominates the SPEA-II front. The absolute value of μ distance is not high for small-size problems. However, we can observe that the absolute values of the μ distance are higher for large-size problems. That means that for small problems, the two fronts of NSGA-II and SPEA-II are both very close to the absolute Pareto front (the efficiency of NSGA-II is demonstrated in the following section). So, the difference between the two fronts is not very obvious, and the number of non-dominated solutions in the obtained fronts are quiet similar. When solving complex problems, the advantage of NSGA-II is obvious. The NSGA-II front is under the SPEA-II front and the distance between the two fronts is larger than before. The NSGA-II has obtained more non-dominated solutions than SPEA-II. The value of C1 is always less than C2. In fact, the values of C1 are nearly equal to 0, while those of C2 are nearly equal to 1. Based on all the tested instances, the comparison between the different numerical results show the advantages and the efficiency of NSGA-II.


#### 4.3.2. Comparison with the Pareto Optimal Solutions

In this section, the absolute Pareto optimal solutions obtained by an exact method are compared to the solutions of the NSGA-II, which has been proved to be better than SPEA-II. This exact method consists of enumerating all the possible solutions of the problem. Since the full enumeration requires too much execution time, we cannot solve large-size problems with this exact method. In this work, we are able to solve the problem with a maximum number of 8 jobs. The results in Table7 have shown that the NSGA-II has obtained the same solutions (μ=0,  C1=C2=0) than the exact method for the tested instances. The main advantage of the NSGA-II is that it requires less computing time (CT NSGA-II) than the full enumeration (CT FE).Table 7
NSGA-II/Full enumeration comparison.
Problem(n,m)nsNSGA-IInsFEμC1C2CTFECTNSGA-II(5, 2)550000.016s0.688s(5, 3)440000.016s0.743s(6, 2)330000.922s0.688s(6, 3)440000.890s0.766s(7, 2)44000132s0.672s(7, 3)55000206s0.750s(8, 2)6600038004s0.672s(8, 3)3300042608s0.687s


## 4.1. Definition of the Protocol Test

For the computational experiments, a protocol test is developed in which the job data are randomly generated. The job data include the processing timespj, the release dates rj, the due dates dj and the sequence-dependent setup times sij. In a previous work [41], we have presented a protocol test based on the work of [12, 42]. For each job, the processing times pj are generated using a uniform distribution [1,100]. After the generation of the processing times, the setup times sij are set to α×min(pi,pj), where α is a coefficient randomly generated in [A,B], and [A,B]∈{[0.1,0.2],[0.1,0.5]}. The release dates are generated using a uniform distribution [0,50.5×N×β/M]. The value of β is considered from {0.6,0.8} [43]. The due dates of jobs are in the interval [P×(1-TF-(RDD/2)), P×(1-TF+(RDD/2))], where P=∑j=1npj/m, and we have chosen TF and RDD between 0.2 and 0.4. Since there are four parameters to set, and two values are proposed to each parameter, we have then 16 different configurations to test, and the index of each configuration is shown in Table 2. For the comparison of two approximated methods, three types of instances have been processed: the problem with 10 jobs and 3 machines, the problem with 20 jobs and 3 machines, and the problem with 50 jobs and 5 machines. The full enumeration method cannot be applied on large problems because of the too long execution times. Therefore, the comparison between the proposed methods and the full enumeration method is realized on the problems with 5, 6, 7, and 8 jobs.Table 2
The index of configurations.
β, [A,B]TF, RDD0.20.20.40.40.20.40.20.40.6, [0.1, 0.2]12340.8, [0.1, 0.2]56780.6, [0.1, 0.5]91011120.8, [0.1, 0.5]13141516


## 4.2. Measuring Criteria

The comparison of two different Pareto fronts for solving the same MOP is very complicated, since each front is not a single scalar value, but a set of non-dominated solutions. An approximated method involves the following objectives [44]: the distance to the absolute Pareto optimal front is to be minimized, the diversity of the generated solutions is to be maximized and the spread of the obtained front is to be maximized.Recently, several measuring criteria have been proposed for comparing two non-dominated fronts. Ranjithan et al. [45] have proposed a spread metric which determines the maximum range represented by the non-dominated solutions in the objective space and a coverage metric that characterizes the distribution of solutions. Kumar and Ranjithan [43] have proposed a D factor that represents the degree of dominance of non-dominated solutions from two obtained fronts which are produced by two different algorithms. Van Veldhuizen [46] has proposed an error-ratio criterion and a generational distance (GD). The former one represents the proportion of nontrue Pareto solutions in the obtained front. It measures the general progress to the reference set. Zitzler and Thiele [44] have presented a Zitzler measure, a μ distance is presented by Riise [47]. The two latter measures were adopted in this work, because they do not require to compute the absolute Pareto optimal front (reference set). The number of nondominated solutions ns of the Pareto front is also considered in our work.LetA and B be two Pareto fronts obtained by different methods. nA and nB are the number of nondominated solutions in fronts A and B, respectively. The μ distance is defined as μ=∑i=1nAdi/nA, where di is the distance between solution i of A and its orthogonal projection on B. The value of di is negative, when solution i is below the front B (or the extrapolated front). The μ distance shows if front A is closer to the optimal solutions than front B. The lower of the value μ we find, the better quality of front A we will get.The Zitzler measure has been presented by Zitzler and Thiele [44], where C1 measures the ratio of solutions in A which are dominated by at least one solution in B. The equation is defined by C1=|{a∈A∣∃b∈B:b≻a}|/|A|, where a and b are the non-dominated solutions in fronts A and B respectively. When C1=1, it means that all of the solutions in A are dominated by solutions in B. However, when C1=0, it means that there are no solutions in A that are dominated by at least one solution in B. On the other side, C2 measures the ratio of solutions in B which are dominated by at least one solution in A.


## 4.3. Results

### 4.3.1. Comparison of NSGA-II and SPEA-II

First, the experimental results of NSGA-II and SPEA-II are compared. Figure2 shows an example where 20 jobs should be scheduled on 3 identical parallel machines. The objective values of all the obtained solutions are shown in Table 3. We can observe that the front obtained by NSGA-II dominates the other front obtained by SPEA-II. Indeed, in this example, we have C1=0, which means that there is no solution in the NSGA-II front that is dominated by at least a solution from SPEA-II. C2=1 means that all the solutions of SPEA-II are dominated by at least one solution of NSGA-II front. Finally, we have μ=-38.071; μ is negative because the NSGA-II front dominates the SPEA-II front.Table 3
Objective values correspond to the NSGA-II/SPEA-II comparison.
Number of solutionNSGA-IISPEA-IICmax∑TjCmax∑Tj14141256416144924151202423135034161060431133844189904331022542096843610036432952469100174399328440867Figure 2
Example of NSGA-II/SPEA-II comparison.Tables 4, 5, and 6 show the comparison results of NSGA-II and SPEA-II to solve three different problems with 16 different configurations. The index of the configuration is shown in Table2. For each configuration, we have tested 10 instances. The mean value of μ, the minimum value and the maximum value of μ(max_μandmin_μ), the mean values of C1 and C2 are presented. In this work, 480 instances are therefore tested.The first line of Table4 is explained. This problem is defined with 10 jobs and 3 machines. Index 1 means that the jobs data are randomly generated with β=0.6, [A,B]=[0.1,0.2], RDD=0.2, and TF=0.2 (see Table 3). The next 7 elements show the comparison results. Since each configuration is tested for ten instances, the value of ns shows that the NSGA-II has obtained more non-dominated solutions than SPEA-II with respective mean values of 4 and 3.2. The mean value of the Riise distance μ=-10.719 indicates that the obtained front of NSGA-II dominates the SPEA-II front, since this value is negative. The minimum and maximum values of μ are both negatives, which means that the Riise distance is always negative during the ten tests. The results show that C1=0; that is, there are no solutions provided by NSGA-II that are dominated by at least one solution of the SPEA-II. On the other side, C2=1 means that all solutions provided by SPEA-II are dominated by at least one solution of NSGA-II.Table 4
The comparison results for 10 jobs and 3 machines.
nsNSGA-IInsSPEA-IIμmax_μmin_μC1C2143.2-10.719-0.427-32.9980.0200.94123.73.7-23.331-5.572-57.5410134.53.6-12.328-6.213-29.6210.0330.96044.83.7-8.414-0.236-36.0700.0200.82054.33.1-12.079-0.437-25.0910.0400.85064.23.6-11.865-7.612-20.7590174.83.3-16.530-5.301-39.4320184.54.3-16.052-4.020-37.31400.98093.63.4-28.844-1.658-36.94800.9671033.6-29.923-24.467-40.08201114.23.5-21.510-4.712-63.82100.917124.73.3-17.275-1.108-36.91500.967133.33.2-20.658-2.105-44.0510.0330.883143.43.6-20.507-5.982-38.35801153.43.1-6.748-0.369-25.93801163.33-2.677-1.189-7.18400.900Table 5
The comparison results for 20 jobs and 3 machines.
nsNSGA-IInsSPEA-IIμmax_μmin_μC1C215.23.6-57.783-26.900-157.1650126.23.8-64.773-19.398-183.8240136.73.8-43.357-9.967-116.9360146.73.7-80.565-11.515-158.0750.0200.98655.63.9-38.786-5.863-65.5530166.34.5-84.840-15.780-150.4370176.33.3-70.763-13.980-121.5990186.64.2-130.905-39.507-207.3970194.44.4-89.322-33.199-242.74201105.63.6-90.343-19.670-177.62601115.43.5-69.500-30.652-162.87001126.63.7-102.433-16.751-226.405011353.9-83.883-19.717-160.02701145.23.6-61.100-3.506-122.7100.0250.950156.83.7-56.728-18.379-96.92601164.53.5-125.261-33.281-199.40401Table 6
The comparison results for 50 jobs and 5 machines.
nsNSGA-IInsSPEA-IIμmax_μmin_μC1C215.44.4-121.605-71.3029-276.4540126.93.9-95.738-28.279-251.5800.0570.93336.95.7-147.188-63.880-253.70101474.7-131.867-26.957-255.18101563.2-151.970-58.576-281.4310165.22.9-168.611-101.356-280.06801773.8-194.197-73.031-302.2000186.73.4-132.477-51.033-212.6410195.24-161.820-75.712-253.03701107.13.5-177.886-46.687-287.34501117.44-147.448-58.326-305.01701127.14.4-163.878-22.844-362.630011354.1-149.905-71.089-269.73301145.73.8-207.573-63.686-291.703011573.4-189.336-103.498-277.89201167.43.5-201.379-62.870-325.05001In this work, we have chosen a fixed computing time as a stopping criterion for NSGA-II and SPEA-II. One second, two seconds, and five seconds are the execution times that are fixed for the problems with 10 jobs, 20 jobs, and 50 jobs, respectively. Tables 4, 5, and 6 show a comparison between NSGA-II and SPEA-II for the tested instances.The values ofμ are always negative, which means that the NSGA-II front always dominates the SPEA-II front. The absolute value of μ distance is not high for small-size problems. However, we can observe that the absolute values of the μ distance are higher for large-size problems. That means that for small problems, the two fronts of NSGA-II and SPEA-II are both very close to the absolute Pareto front (the efficiency of NSGA-II is demonstrated in the following section). So, the difference between the two fronts is not very obvious, and the number of non-dominated solutions in the obtained fronts are quiet similar. When solving complex problems, the advantage of NSGA-II is obvious. The NSGA-II front is under the SPEA-II front and the distance between the two fronts is larger than before. The NSGA-II has obtained more non-dominated solutions than SPEA-II. The value of C1 is always less than C2. In fact, the values of C1 are nearly equal to 0, while those of C2 are nearly equal to 1. Based on all the tested instances, the comparison between the different numerical results show the advantages and the efficiency of NSGA-II.


### 4.3.2. Comparison with the Pareto Optimal Solutions

In this section, the absolute Pareto optimal solutions obtained by an exact method are compared to the solutions of the NSGA-II, which has been proved to be better than SPEA-II. This exact method consists of enumerating all the possible solutions of the problem. Since the full enumeration requires too much execution time, we cannot solve large-size problems with this exact method. In this work, we are able to solve the problem with a maximum number of 8 jobs. The results in Table7 have shown that the NSGA-II has obtained the same solutions (μ=0,  C1=C2=0) than the exact method for the tested instances. The main advantage of the NSGA-II is that it requires less computing time (CT NSGA-II) than the full enumeration (CT FE).Table 7
NSGA-II/Full enumeration comparison.
Problem(n,m)nsNSGA-IInsFEμC1C2CTFECTNSGA-II(5, 2)550000.016s0.688s(5, 3)440000.016s0.743s(6, 2)330000.922s0.688s(6, 3)440000.890s0.766s(7, 2)44000132s0.672s(7, 3)55000206s0.750s(8, 2)6600038004s0.672s(8, 3)3300042608s0.687s


## 4.3.1. Comparison of NSGA-II and SPEA-II

First, the experimental results of NSGA-II and SPEA-II are compared. Figure2 shows an example where 20 jobs should be scheduled on 3 identical parallel machines. The objective values of all the obtained solutions are shown in Table 3. We can observe that the front obtained by NSGA-II dominates the other front obtained by SPEA-II. Indeed, in this example, we have C1=0, which means that there is no solution in the NSGA-II front that is dominated by at least a solution from SPEA-II. C2=1 means that all the solutions of SPEA-II are dominated by at least one solution of NSGA-II front. Finally, we have μ=-38.071; μ is negative because the NSGA-II front dominates the SPEA-II front.Table 3
Objective values correspond to the NSGA-II/SPEA-II comparison.
Number of solutionNSGA-IISPEA-IICmax∑TjCmax∑Tj14141256416144924151202423135034161060431133844189904331022542096843610036432952469100174399328440867Figure 2
Example of NSGA-II/SPEA-II comparison.Tables 4, 5, and 6 show the comparison results of NSGA-II and SPEA-II to solve three different problems with 16 different configurations. The index of the configuration is shown in Table2. For each configuration, we have tested 10 instances. The mean value of μ, the minimum value and the maximum value of μ(max_μandmin_μ), the mean values of C1 and C2 are presented. In this work, 480 instances are therefore tested.The first line of Table4 is explained. This problem is defined with 10 jobs and 3 machines. Index 1 means that the jobs data are randomly generated with β=0.6, [A,B]=[0.1,0.2], RDD=0.2, and TF=0.2 (see Table 3). The next 7 elements show the comparison results. Since each configuration is tested for ten instances, the value of ns shows that the NSGA-II has obtained more non-dominated solutions than SPEA-II with respective mean values of 4 and 3.2. The mean value of the Riise distance μ=-10.719 indicates that the obtained front of NSGA-II dominates the SPEA-II front, since this value is negative. The minimum and maximum values of μ are both negatives, which means that the Riise distance is always negative during the ten tests. The results show that C1=0; that is, there are no solutions provided by NSGA-II that are dominated by at least one solution of the SPEA-II. On the other side, C2=1 means that all solutions provided by SPEA-II are dominated by at least one solution of NSGA-II.Table 4
The comparison results for 10 jobs and 3 machines.
nsNSGA-IInsSPEA-IIμmax_μmin_μC1C2143.2-10.719-0.427-32.9980.0200.94123.73.7-23.331-5.572-57.5410134.53.6-12.328-6.213-29.6210.0330.96044.83.7-8.414-0.236-36.0700.0200.82054.33.1-12.079-0.437-25.0910.0400.85064.23.6-11.865-7.612-20.7590174.83.3-16.530-5.301-39.4320184.54.3-16.052-4.020-37.31400.98093.63.4-28.844-1.658-36.94800.9671033.6-29.923-24.467-40.08201114.23.5-21.510-4.712-63.82100.917124.73.3-17.275-1.108-36.91500.967133.33.2-20.658-2.105-44.0510.0330.883143.43.6-20.507-5.982-38.35801153.43.1-6.748-0.369-25.93801163.33-2.677-1.189-7.18400.900Table 5
The comparison results for 20 jobs and 3 machines.
nsNSGA-IInsSPEA-IIμmax_μmin_μC1C215.23.6-57.783-26.900-157.1650126.23.8-64.773-19.398-183.8240136.73.8-43.357-9.967-116.9360146.73.7-80.565-11.515-158.0750.0200.98655.63.9-38.786-5.863-65.5530166.34.5-84.840-15.780-150.4370176.33.3-70.763-13.980-121.5990186.64.2-130.905-39.507-207.3970194.44.4-89.322-33.199-242.74201105.63.6-90.343-19.670-177.62601115.43.5-69.500-30.652-162.87001126.63.7-102.433-16.751-226.405011353.9-83.883-19.717-160.02701145.23.6-61.100-3.506-122.7100.0250.950156.83.7-56.728-18.379-96.92601164.53.5-125.261-33.281-199.40401Table 6
The comparison results for 50 jobs and 5 machines.
nsNSGA-IInsSPEA-IIμmax_μmin_μC1C215.44.4-121.605-71.3029-276.4540126.93.9-95.738-28.279-251.5800.0570.93336.95.7-147.188-63.880-253.70101474.7-131.867-26.957-255.18101563.2-151.970-58.576-281.4310165.22.9-168.611-101.356-280.06801773.8-194.197-73.031-302.2000186.73.4-132.477-51.033-212.6410195.24-161.820-75.712-253.03701107.13.5-177.886-46.687-287.34501117.44-147.448-58.326-305.01701127.14.4-163.878-22.844-362.630011354.1-149.905-71.089-269.73301145.73.8-207.573-63.686-291.703011573.4-189.336-103.498-277.89201167.43.5-201.379-62.870-325.05001In this work, we have chosen a fixed computing time as a stopping criterion for NSGA-II and SPEA-II. One second, two seconds, and five seconds are the execution times that are fixed for the problems with 10 jobs, 20 jobs, and 50 jobs, respectively. Tables 4, 5, and 6 show a comparison between NSGA-II and SPEA-II for the tested instances.The values ofμ are always negative, which means that the NSGA-II front always dominates the SPEA-II front. The absolute value of μ distance is not high for small-size problems. However, we can observe that the absolute values of the μ distance are higher for large-size problems. That means that for small problems, the two fronts of NSGA-II and SPEA-II are both very close to the absolute Pareto front (the efficiency of NSGA-II is demonstrated in the following section). So, the difference between the two fronts is not very obvious, and the number of non-dominated solutions in the obtained fronts are quiet similar. When solving complex problems, the advantage of NSGA-II is obvious. The NSGA-II front is under the SPEA-II front and the distance between the two fronts is larger than before. The NSGA-II has obtained more non-dominated solutions than SPEA-II. The value of C1 is always less than C2. In fact, the values of C1 are nearly equal to 0, while those of C2 are nearly equal to 1. Based on all the tested instances, the comparison between the different numerical results show the advantages and the efficiency of NSGA-II.


## 4.3.2. Comparison with the Pareto Optimal Solutions

In this section, the absolute Pareto optimal solutions obtained by an exact method are compared to the solutions of the NSGA-II, which has been proved to be better than SPEA-II. This exact method consists of enumerating all the possible solutions of the problem. Since the full enumeration requires too much execution time, we cannot solve large-size problems with this exact method. In this work, we are able to solve the problem with a maximum number of 8 jobs. The results in Table7 have shown that the NSGA-II has obtained the same solutions (μ=0,  C1=C2=0) than the exact method for the tested instances. The main advantage of the NSGA-II is that it requires less computing time (CT NSGA-II) than the full enumeration (CT FE).Table 7
NSGA-II/Full enumeration comparison.
Problem(n,m)nsNSGA-IInsFEμC1C2CTFECTNSGA-II(5, 2)550000.016s0.688s(5, 3)440000.016s0.743s(6, 2)330000.922s0.688s(6, 3)440000.890s0.766s(7, 2)44000132s0.672s(7, 3)55000206s0.750s(8, 2)6600038004s0.672s(8, 3)3300042608s0.687s


## 5. Conclusion

In this work, an identical parallel machines scheduling problem with release dates, due dates, and sequence-dependant setup times is considered. The goal is to minimize the makespan and the total tardiness. The contribution of this paper is to develop a new mathematical model and two metaheuristics which are the NSGA-II and SPEA-II. The computational results show the advantage of NSGA-II over the SPEA-II on the 480 tested problems based on the adopted measuring criteria. After that, the NSGA-II is compared to the full enumeration for small-size problems. We can observe that NSGA-II is able to obtain the absolute optimal solutions. The full enumeration method cannot solve problems with more than 8 jobs. Hence, the perspective is to develop another exact method to compare the results of the two methods with larger and more complex problems. On the other side, the setting of crossover and mutation probabilities is very difficult. Therefore, it would be interesting to develop a self-adopted GA which can set the probabilities during the generations.



---

*Source: 943050-2010-12-02.xml*