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 near-optimal 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 non-identical 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 and j on machine k is different from the setup time between job j and i on the same machine k. In addition, the setup time between job i and j on machine s is different from the setup time between job i and j on machine p. 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 sequence-dependent setup times is a very active research area (Allahverdi et al., 2008). The single machine scheduling problem with sequence-dependent setup times is known to be NP-hard (Pinedo, 1995), and for the case of parallel machines, it is proved that the problem of minimizing the makespan with two identical machines is NP-hard (Garey and Johnson, 1997). The problem of minimizing the makespan on a scheduling problem of m parallel machines with sequence-dependent setup times is also NP-hard (Nait et al., 2003; Sveltana et al., 2001; Yalaoui and Chu, 2003). But the problem of this paper is more complex because it considers not only considering sequence-dependent 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 sequence-dependent setup cost in batch processing machines. Tahar et al. (2006) presented a heuristic based on linear programming modeling to minimize maximum completion time for sequence-dependent setup time parallel machine scheduling. The performance of their proposed method was tested on problems with a lower bound. Rocha et 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 sequence-dependent setup times and non-zero 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. Nessah et 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 Tahar et al. (2006) a linear programming approach was proposed with job splitting and sequence-dependent setup times. Pfund et al. (2008) presented a meta-heuristic method for the parallel machine scheduling problem with three objective functions. Gharehgozli et al. (2009) presented a new mixed-integer goal programming model to minimize the total weighted flow time and the total weighted tardiness simultaneously for a parallel machine scheduling problem with sequence-dependent setup times and release dates. Joo (2009) proposed ant colony optimization (ACO) for a parallel machine scheduling problem with sequence-dependent setup times and job release time.

Driessel and Monch (2010) addressed a parallel machine scheduling problem to minimize total weighted tardiness with sequence-dependent setup times, precedence constraints and ready time and proposed variable neighborhood search (VNS) heuristic to solve the problem.

For non-identical 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 the n printed circuit boards (PCBs) scheduling problem processed by m non-identical 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. Tavakkoli-Moghaddam et 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 sequence-dependent and machine-dependent setup times, ready times, and due-times. Gharehgozli et al. (2009) presented a new mixed-integer goal programming model to minimize the total weighted flow time and the total weighted tardiness simultaneously for a non-identical parallel machine scheduling problem with sequencedependent and machine-dependent setup times, ready times, and due-times. Balin (2011) presented a genetic algorithm for the non-identical parallel machine scheduling to minimize makespan of the machines without having setup times, ready times, and due-times. In the non-identical parallel machine scheduling problem, if setup times are considered, they are sequence-dependent and machine-dependent 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 non-identical parallel machine scheduling problem. Ko et al. (2010) proposed a dispatching rule that guarantees a predetermined minimum quality level for non-identical parallel machines with multiple product types. They only considered sequence-dependent 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 non-identical parallel machine scheduling problem.

Motivated by the literature discussed above, this paper considers the non-identical 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 meta-heuristic 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 meta-heuristic algorithms, genetic algorithm (GA) and a new population-based evolutionary meta-heuristic called self-evolution 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.

In this section, we propose a mixed integer programming model for a non-identical 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 job O 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²× MS binary variables, JS + 1 continuous variables and JS² + 2(JS× MS) + 2JS + MS ?1 constraints. This MIP model will be used later in the computational experiments.

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 meta-heuristic approaches instead. In identical parallel machine scheduling problems with sequence dependent setup times, several authors have reported the effectiveness of the meta-heuristic approaches. Mendes et al. (2002) proposed TS (Tabu Search) in the parallel machine scheduling problem with sequence- dependent setup times. Behnamian et 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 sequence-dependent setup times and job release time. Tavakkoli-Moghaddam et 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 non-identical parallel machine scheduling using 0-1 encoding of two dimensional representation.

In this paper, we propose two meta-heuristics as solution approach for the non-identical parallel machine scheduling problem; conventional genetic algorithm (GA) and self-evolution algorithm (SEA) using one dimensional representation with special character. SEA is a new population-based evolutionary meta-heuristic. 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; Tavakkoli-Moghaddam 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 self-repro-duction 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 neighborhood-search operations.

In meta-heuristics, the solution performance is highly dependent upon the representation of a solution. For both meta-heuristic GA and SEA, it is necessary to describe the representation of a solution for the corresponding non-identical 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 by n digits from 1 to n and (m-1) machine separation indicator ‘ * ’ s, where n is the number of jobs and m 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.

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. One-point 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.

SEA is a new meta-heuristic algorithm which has a population (a set of solutions) based mechanism using the evolution of a solution by itself (self-evolution). 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 self-reproduction 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 self-evolution, selection of evolution operator, and selection of points for the operator are randomly executed.

To evaluate the performances of the meta-heuristic 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 meta-heuristic 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 meta-heuristic algorithms and Best 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. The RPDs and MADs of SEA are much better than those of GA in all test problems. Both the RPDs and MADs of SEA are nearly 0 in all test problems. This means that SEA is a very effective algorithm with low variation for the non-identical parallel machine scheduling problem.

The RPD and MAD of 10 replications by meta-

heuristic 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 and MAD of SEA are 2.84 and 0.15, respectively. Meanwhile RPD and MAD 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 meta-heuristic 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 the RPD 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 non-identical 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.

In this paper a non-identical 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 meta-heuristic algorithm which has a population (a set of solutions) based self-evolution mechanism. Two problem groups are tested to verify the performance of proposed meta-heuristic algorithms. The test results indicate that SEA is very effective and efficient algorithm with low variation for the non-identical parallel machine scheduling problem.

Further study is required to assess the performance of SEA with other meta-heuristics (Simulated Annealing, Tabu-search and Ant-colony optimization, etc.) in the scheduling problems or other combinatorial problems.