NonIdentical Parallel Machine Scheduling with Sequence and Machine Dependent Setup Times Using MetaHeuristic Algorithms
 Author: Joo Cheol Min, Kim Byung Soo
 Organization: Joo Cheol Min; Kim Byung Soo
 Publish: Industrial Engineering and Management Systems Volume 11, Issue1, p114~122, 01 March 2012

ABSTRACT
This paper considers a nonidentical parallel machine scheduling problem with sequence and machine dependent setup times. The objective of this problem is to determine the allocation of jobs and the scheduling of each machine to minimize makespan. A mathematical model for optimal solution is derived. An indepth analysis of the model shows that it is very complicated and difficult to obtain optimal solutions as the problem size becomes large. Therefore, two metaheuristics, genetic algorithm (GA) and a new populationbased evolutionary metaheuristic called selfevolution algorithm (SEA), are proposed. The performances of the metaheuristic algorithms are evaluated through compare with optimal solutions using randomly generated several examples.

KEYWORD
NonIdentical Parallel Machine Scheduling , Sequence and Machine Dependent Setup Time , MetaHeuristic Algorithms

1. INTRODUCTION
A technique for production scheduling problems is a methodology that optimizes the use of available resources by ordering a sequence of operations of jobs assigned to each resource. The scheduling problems are computationally very complex and therefore it is difficult to optimally solve in a reasonable time due to the combinatorial nature of its solution. As a result, finding a nearoptimal solution in a reasonable time is important in real manufacturing area.
In a parallel machine scheduling problem, a set of the independent jobs are processed on a number of available identical parallel machines. Each machine processes only one job at a time, and each job can be processed on one of any machines with same processing time. But, in a nonidentical parallel machine scheduling problem, the processing times of jobs depend upon the machine to which they are assigned to. Furthermore, the consideration of setup times between jobs is dependent upon not only the sequence of jobs to be processed on a machine but also the machine to which the jobs are assigned. In other words, the setup time between job
i andj on machinek is different from the setup time between jobj andi on the same machinek . In addition, the setup time between jobi andj on machine s is different from the setup time between jobi andj on machinep . This is the most common in the manufacturing industry, which is also the generalization of a parallel machine scheduling in practice.Solving scheduling problems with sequencedependent setup times is a very active research area (Allahverdi
et al. , 2008). The single machine scheduling problem with sequencedependent setup times is known to be NPhard (Pinedo, 1995), and for the case of parallel machines, it is proved that the problem of minimizing the makespan with two identical machines is NPhard (Garey and Johnson, 1997). The problem of minimizing the makespan on a scheduling problem ofm parallel machines with sequencedependent setup times is also NPhard (Naitet al. , 2003; Sveltanaet al. , 2001; Yalaoui and Chu, 2003). But the problem of this paper is more complex because it considers not only considering sequencedependent setup times but also machine dependent setup times and machine dependent processing time.For identical parallel machine problems, Monma and Potts (1989) considered the complex computing of scheduling parallel machine with sequencedependent setup cost in batch processing machines. Tahar
et al. (2006) presented a heuristic based on linear programming modeling to minimize maximum completion time for sequencedependent setup time parallel machine scheduling. The performance of their proposed method was tested on problems with a lower bound. Rochaet al. (2007) proposed a variable neighborhood search algorithm and showed that their algorithm outperforms a greedy randomized adaptive search procedure algorithm. Several papers addresses the sequencedependent setup times and nonzero release times for identical parallel machine scheduling was addressed. Ovicik and Uzsoy (1995) presented a time based decomposition approach to minimize the maximum lateness of the jobs. Nessahet al. (2005) presented a heuristic to minimize the total weighted completion time. Logendrana,et al. (2007) considered the minimization of the weighted tardiness of jobs in unrelated parallel machine scheduling with sequence dependent setup times considering dynamic release of jobs and dynamic availability of machines. In Taharet al. (2006) a linear programming approach was proposed with job splitting and sequencedependent setup times. Pfundet al. (2008) presented a metaheuristic method for the parallel machine scheduling problem with three objective functions. Gharehgozliet al. (2009) presented a new mixedinteger goal programming model to minimize the total weighted flow time and the total weighted tardiness simultaneously for a parallel machine scheduling problem with sequencedependent setup times and release dates. Joo (2009) proposed ant colony optimization (ACO) for a parallel machine scheduling problem with sequencedependent setup times and job release time.Driessel and Monch (2010) addressed a parallel machine scheduling problem to minimize total weighted tardiness with sequencedependent setup times, precedence constraints and ready time and proposed variable neighborhood search (VNS) heuristic to solve the problem.
For nonidentical parallel machine scheduling problems, several studies have found. Agarwal
et al. (2006) proposed several heuristics using a new neural network formulation to minimize the makespan. Hop and Nagaur (2004) considered then printed circuit boards (PCBs) scheduling problem processed bym nonidentical machines to minimize total makespan using a genetic algorithm. Li and Yang (2009) considered for the nonidentical parallel machine scheduling to minimize total weighted completion time. TavakkoliMoghaddamet al. (2009) proposed a genetic algorithm to minimize the number of tardy jobs and total completion time for a unrelated parallel machine scheduling problem with sequencedependent and machinedependent setup times, ready times, and duetimes. Gharehgozliet al. (2009) presented a new mixedinteger goal programming model to minimize the total weighted flow time and the total weighted tardiness simultaneously for a nonidentical parallel machine scheduling problem with sequencedependent and machinedependent setup times, ready times, and duetimes. Balin (2011) presented a genetic algorithm for the nonidentical parallel machine scheduling to minimize makespan of the machines without having setup times, ready times, and duetimes. In the nonidentical parallel machine scheduling problem, if setup times are considered, they are sequencedependent and machinedependent in general case. In this paper, the authors propose a new “crossover operator” and a new “optimality criterion” in order to adapt the GA to nonidentical parallel machine scheduling problem. Koet al. (2010) proposed a dispatching rule that guarantees a predetermined minimum quality level for nonidentical parallel machines with multiple product types. They only considered sequencedependent setup times between product types. Vallada and Ruiz (2011) presented hybrid genetic algorithms to minimize makespan including a fast local search and a local search enhanced crossover operator based on the two dimensional representation of a chromosome for nonidentical parallel machine scheduling problem.Motivated by the literature discussed above, this paper considers the nonidentical parallel machine scheduling problem with sequence and machine dependent setup times to minimize makespan. Though the problem can be formulated to a mathematical model, the model is not tractable as the problem size become large. Therefore, two metaheuristic approaches are designed to solve the problem in a reasonable time. In section 2, a mathematical model is derived for finding the optimal solution. Two metaheuristic algorithms, genetic algorithm (GA) and a new populationbased evolutionary metaheuristic called selfevolution algorithm (SEA), are proposed in section 3. In section 4, the performances of the metaheuristics are evaluated through computational experiments. Finally, summary and further research areas are remarked in section 5.
2. MATHEMATICAL MODEL
In this section, we propose a mixed integer programming model for a nonidentical parallel machine scheduling problem with sequence and machine dependent setup times scheduling problem to minimize makespan. The following notations are used:
Parameters pik : processing time of job i on machine k.
sijk : sequence and machine dependent setup time of job j processed after job i on machine k.
sOik : setup time of job i if job i is the first job in job sequence on machine k.
MS : set of machines
JS : set of jobs to be scheduled
O : dummy job index
M : big number
Continuous variables xi : starting time of job i
cmax : makespan
Binary variables The mathematical model is as given below:
xi ≥ 0, for ∀i ∈ JS,
yik = 0 or 1, for ∀i ∈ JS, ∀k ∈ MS,
zijk = 0 or 1, for ∀i ∈ JS, ∀k ∈ MS,
zoik = 0 or 1, for ∀i ∈ JS, ∀k ∈ MS,
In this model, a dummy job notation
O is introduced to take care of the setup time for the job assigned to the first position in the sequence on each machine. Constraint (2) calculates the makespan. Constraint (3) ensures the precedence relation of jobs assigned in the same machine. Constraint (4) confirms that each job is processed in exactly one machine. Constraints (5)(7) ensure that jobs assigned in the same machine must be appeared once in their sequence. Constraint (5) guarantees that the dummy jobO is positioned at the beginning of the sequence before all the jobs on each machine. Constraint (6) depicts that if a job is assigned to a machine, then it will be immediately preceded by one job. Similarly Constraint (7) describes that if a job is assigned to a machine then it can be succeeded by at most one job. The job in the last position of the sequence on a machine will not have a succeeding job. Therefore, in total, model contains 2(JS ×MS ) +JS ^{2}×MS binary variables,JS + 1 continuous variables andJS ^{2} + 2(JS ×MS ) + 2JS + MS ?1 constraints. This MIP model will be used later in the computational experiments.3. METAHEURISTIC ALGORITHMS
The mixed integer programming model is not tractable for the problems over total 12 jobs because of the computation time (See Section 4). Thus, we focus on developing effective metaheuristic approaches instead. In identical parallel machine scheduling problems with sequence dependent setup times, several authors have reported the effectiveness of the metaheuristic approaches. Mendes
et al. (2002) proposed TS (Tabu Search) in the parallel machine scheduling problem with sequence dependent setup times. Behnamianet al. (2009) proposed hybrid algorithm including ACO (Ant Colony Optimization), SA (Simulated Annealing) and VNS (Variable Neighborhood Search). Joo (2009) proposed an improved (ACO) for a parallel machine scheduling problem with sequencedependent setup times and job release time. TavakkoliMoghaddamet al. (2009) proposed a genetic algorithm with one dimensional representation with a special character for unrelated parallel machine scheduling problem. Balin (2011) presented a genetic algorithm for nonidentical parallel machine scheduling using 01 encoding of two dimensional representation.In this paper, we propose two metaheuristics as solution approach for the nonidentical parallel machine scheduling problem; conventional genetic algorithm (GA) and selfevolution algorithm (SEA) using one dimensional representation with special character. SEA is a new populationbased evolutionary metaheuristic. GA is one of the most powerful and broadly applicable metaheuristic based on principles from evolution theory. GA was first introduced and investigated by Holland (1975), and known as an effective and efficient algorithm for combinatorial optimization problems (Gen and Cheng, 2000). In general, the solution representation (chromosome) with a special character for separating machines has been used to apply GA in parallel machine scheduling problems (Cheng and Gen, 1997; TavakkoliMoghaddam
et al. , 2009). In GAs, two chromosomes are selected as parents and execute a sexual reproduction by the crossover operation. Therefore, the good characteristic of both chromosomes can be inherited to next generation. However, SEA executes a selfreproduction by a single parent without the sexual reproduction by two parents. SEA explores broader solution space than GA by constantly maintaining the randomness during every generation and provides better effectiveness of solutions than GA by various neighborhoodsearch operations.3.1 Representation of Solutions
In metaheuristics, the solution performance is highly dependent upon the representation of a solution. For both metaheuristic GA and SEA, it is necessary to describe the representation of a solution for the corresponding nonidentical parallel machine schedule, and the representation is called
chromosome . To represent machine assignments and the job sequences of each machine, the chromosome with a special character for separating machine is used in this paper. This representation has been popular in parallel machine scheduling problems since firstly introduced by Cheng and Gen (1997). The chromosome with a special character for separating machines has a single dimensional string array expressed byn digits from 1 ton and (m 1) machine separation indicator ‘ * ’ s, wheren is the number of jobs andm is the number of machines. The digits between ‘ * ’ represent the sequence of jobs assigned to a same machine. Hence, the dispatching jobs to the corresponding machines and the sequencing of jobs in each machine are straightforwardly determined at the same time. Based on the representation of a chromosome with machine separation indicator ‘ * ’ and its corresponding schedule are illustrated in Figure 1. The chromosome represents the assigning and sequencing of nine jobs to two machines. Job 2, 4, 8 and 3 are assigned to machine 1 and job 7, 1, 6, 9 and 5 are assigned to machine 2.3.2 Genetic Algorithm (GA)
In the GA using chromosomes with special character, every chromosome is encoded into a structure that represents its properties, and the set of chromosomes forms a population. Initial population is generated randomly for the first generation. The chromosomes in the population are evaluated using the makespan of nonidentical parallel machines as the measure of fitness. The chromosomes that have higher fitness value (lower objective function value) than the average fitness of current population make a potential parent pool. Parents are randomly selected only in the potential parent pool. Using three genetic operators such as a crossover operator, a mutation operator and a reproduction operator, the selected parents reproduce new chromosomes (i.e., children) to generate a population for the next generation. Onepoint crossover is used for both GA, and the crossover is illustrated in Figure 2. One point is randomly selected for dividing one parent. The set of genes on left side is inherited from the parent to the child, and the other genes are placed in order of their appearance in the other parent. For the mutation, two genes of a parent randomly selected are interchanged in GA as shown in
Figure 3 (swap mutation). So a new generation is probabilistically formed according to the fitness values of chromosomes by genetic operators. Then the generation is evaluated and this process is repeated until a stopping criterion (maximum number of generations) is met.
3.3 SelfEvolution Algorithm (SEA)
SEA is a new metaheuristic algorithm which has a population (a set of solutions) based mechanism using the evolution of a solution by itself (selfevolution). Similar to GA, the set of chromosomes forms a population. The chromosome with special character proposed in Section 3.1 is also used for SEA. Initial population is generated randomly, and the chromosomes in the population are evaluated using the makespan of the nonidentical parallel machines as the measure of fitness. A chromosome from the population is randomly selected and executes a selfreproduction using a randomly selected evolution operator to make a new chromosome. Then the new chromosome is evaluated and it replaces the original chromosome, if the fitness value of the new chromosome is better than that of the original chromosome. The algorithm continues until the number of selfreproductions becomes a predetermined stopping value.
We propose five evolution operators (pull operator, insert operator, swap operator, inner random operator and outer random operator) to make a new chromosome. For the operators, two points in the selected original chromosome are randomly selected. The pull operator is illustrated in Figure 4(a). The genes on right side of
point 2 (including point 2) are pulled to the position of point 1, and the genes between point 1 and 2 (including point 1) are placed after. The two genes at the points are interchanged for swap operator as shown in Figure 4(b). Insert operator simply insert the gene at point 2 into the position of point 1 as shown in Figure 4(c). Inner random operator and outer random operator are illustrated in Figure 4(d) and Figure 4(e). The inner or outer genes of point 1 and 2 are randomly replaced for the operators.
SEA is running without providing any parameters for the algorithm, because all the selection processes in SEA, such as selection of chromosome from the population for selfevolution, selection of evolution operator, and selection of points for the operator are randomly executed.
4. COMPUTATIONAL RESULTS
To evaluate the performances of the metaheuristic algorithms proposed in this paper, computational experiments were conducted using randomly generated test problems. Since the complexity of a problem highly depends on the number of jobs per machine, we fixed the number of machines as 2, 3, and 4 and generated two problem groups according to the average job size per machine. Total job size of each problem group is summarized in Table 1. The processing time and sequence and machine dependent setup time were randomly generated according to the range of [60, 180] and [10, 60], respectively, and the initial setup time was randomly generated by one value in the 70% range of the setup time.
The small sized problems in the first group were generated for comparing the solutions obtained by meta
heuristic algorithms with optimal solutions. We used ILOG CPLEX 10.2 for finding the optimal solutions with the mathematical model presented in section 2. We imposed a 3600(sec.) time limit and simply terminated a particular run if the optimal solution had not been found and verified in that amount of time. The second group is to compare the performance of each metaheuristic algorithm with large sized problems. GA was running with a population size of 2 ？
n and a generation size of 1000, and fixed crossover and mutation rates of 0.8 and 0.2. The values of the crossover and mutation rates were predetermined by extensive preliminary experimentations. SEA was running with 2 ?n × 1000 iterations in order to be equally compared with GAs. All experiments solving each test problem using CPLEX and metaheuristic algorithms were executed on a PC with 1.86 GHz Intel Core 2 processor and 2 GB RAM.The test results of small sized problems are summarized in Table 2. Table 2 shows the optimal solution by CPLEX and mean and mean absolute deviation (
MAD ) of 10 replications, and relative percentage deviation (RPD ) calculated with the expression (8) by GA and SEA for each test problem.where
MH_{sol} is the solution obtained by metaheuristic algorithms andBest is the best solution of all experiments for each test problem.Best can be optimal solution if the optimal solution is obtained. The optimal solutions for all the test problems up to total 12 jobs could not be obtained by CPLEX in a time limit. TheRPD s andMAD s of SEA are much better than those of GA in all test problems. Both theRPD s andMAD s of SEA are nearly 0 in all test problems. This means that SEA is a very effective algorithm with low variation for the nonidentical parallel machine scheduling problem.The
RPD andMAD of 10 replications by metaheuristic algorithms of each large sized test problem are summarized in Table 3. Similar to the results of small sized problems, we can see that SEA is more effective with low variation than the conventional GA. Average
RPD andMAD of SEA are 2.84 and 0.15, respectively. MeanwhileRPD andMAD of SEA are 11.59 and 0.21.In order to validate the results, it is interesting to check if the observed differences in the
RPD values of each metaheuristic algorithm are statistically significant. Figure 5 shows the mean plots and Tukey HSD intervals at the 95% confidence level of all problems in Table 3. We can clearly see that there are statistically significant differences between theRPD values between SEA and GA because there is no overlap between the algorithms. The observed differences are more statistically significant as the average number of jobs per machine and the number of machines increase, as shown in Figure 6. These results indicate that SEA consistently gives good performance for the nonidentical parallel machine scheduling problem in any jobs size per machine and any machine size, but GA give worse performance as jobs size per machine and machine size become large.The computation times of all test problems are summarized also in Table 2 and Table 3. The computation time of CPLEX significantly increases as the number of jobs per machine increases, and the optimal solution for the problem over total 12 jobs could not be obtained in a 3600(sec.) time limit by CPLEX. Meanwhile the computation time of GA is smaller than SEA, but the difference of the computation times is small enough to obtain solutions in a reasonable time. The difference is caused by the complexity of evolution operators for SEA.
5. CONCLUSIONS
In this paper a nonidentical parallel machine scheduling problem with sequence and machine dependent setup times is considered. The objective of this problem
is to determine the allocation of jobs and the scheduling of each machine to minimize makespan. To address the problem, two different solution approaches are proposed. The first approach is based on a mixed integer programming model. Since the mathematical model is not tractable for the problems over total 12 jobs, we propose metaheuristic algorithms (GA and SEA) to increase solution efficiency. SEA is a new metaheuristic algorithm which has a population (a set of solutions) based selfevolution mechanism. Two problem groups are tested to verify the performance of proposed metaheuristic algorithms. The test results indicate that SEA is very effective and efficient algorithm with low variation for the nonidentical parallel machine scheduling problem.
Further study is required to assess the performance of SEA with other metaheuristics (Simulated Annealing, Tabusearch and Antcolony optimization, etc.) in the scheduling problems or other combinatorial problems.

[Figure 1.] Chromosome and Corresponding Schedule.

[Figure 2.] OnePoint Crossover for GA.

[Figure 3.] Swap Mutation for GA.

[Figure 4.] Operators for SEA.

[Table 1.] Total Job Size.

[Table 2.] Test Results of Small Sized Problems.

[Table 3.] Test Results of Large Sized Problems.

[Figure 5.] Mean Plots and Tukey HSD Intervals at the 95% Confidence Level of GA and SEA.

[Figure 6.] Mean Plots and Tukey HSD Intervals at the 95% Confidence Level of GA and SEA.