Institute of Mathematical Sciences, Faculty of Science, University of Malaya, 50603 Kuala Lumpur, Malaysia
Copyright © 2015 Noor Hasnah Moin et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
The job shop scheduling problem (JSSP) is one of the well-known hard combinatorial scheduling problems. This paper proposes a hybrid genetic algorithm with multiparents crossover for JSSP. The multiparents crossover operator known as extended precedence preservative crossover (EPPX) is able to recombine more than two parents to generate a single new offspring distinguished from common crossover operators that recombine only two parents. This algorithm also embeds a schedule generation procedure to generate full-active schedule that satisfies precedence constraints in order to reduce the search space. Once a schedule is obtained, a neighborhood search is applied to exploit the search space for better solutions and to enhance the GA. This hybrid genetic algorithm is simulated on a set of benchmarks from the literatures and the results are compared with other approaches to ensure the sustainability of this algorithm in solving JSSP. The results suggest that the implementation of multiparents crossover produces competitive results.
The job shop scheduling problem (JSSP) is one of the well-known hard combinatorial scheduling problems and it has been studied extensively due its practical importance. During the past three decades, optimization strategies for JSSP ranging from exact algorithms (mathematical programming) to approximation algorithms (metaheuristics) have been proposed . Exact methods which are based on exhaustive enumeration and decomposition method guarantee global convergence and have been successfully applied to small instances. But, for the moderate and large scale instances, they require very high computational time to be either ineffective or inefficient . Therefore, a lot of researchers focused their attention on approximation methods. Metaheuristics is one of the approximation methods that were proposed in the literatures to deal with JSSP which include tabu search (TS) , simulated annealing (SA) , genetic algorithm (GA) , and discrete artificial bee colony (DABC) .
In recent years, since the first use of GA based algorithm to solve the JSSP proposed by Davis , various GA strategies are introduced to increase the efficiency of GA to find the optimal or near optimal solutions for JSSP . In the GA strategies, hybridization of GA with local search methods provides good results in solving the problems where GA capitalizes on the strength of the local search in locating the optimal or near optimal solutions. For example, Gonçalves et al.  and Zhang et al.  embedded the local search procedure of Nowicki and Smutnicki  into GA due to the effectiveness of the local search that increases the performance of GA. Qing-Dao-Er-Ji and Wang  proposed new crossover operator and mutation operator together with local search in improving local search ability of GA.
Additionally, the structure of the GA can be modified and enhanced to reduce the problems often encountered in GA. Yusof et al.  implemented a migration operator in GA by using parallelization of GA (PGA) to find the near optimal solutions. Watanabe et al.  proposed a GA with search area adaption and a modified crossover operator for adapting to the structure of the solutions space. Ripon et al.  embedded heuristic method in the crossover to reduce the tail redundancy of chromosome. Particularly, recombination operators, especially crossover operators, play important roles in the structure of GA.
Crossover between two parents is traditionally adopted in GA  for JSSP but the GA can be modified accordingly to suit the problem at hand including selecting several numbers of parents for the crossover operation which is known as multiparents crossover.
The application of multiparents recombination can be found in different research areas. Mühlenbein and Voigt  proposed gene pool recombination (GPR) in solving discrete domain problems. Eiben and van Kemenade  introduced the diagonal crossover as the generalization of uniform crossover in GA for numerical optimization problems. Wu et al.  proposed multiparents orthogonal recombination to determine the identity of an unknown image contour. The crossover operators that were used in those areas show the good search ability of the operator but are very much problem dependent.
The above literatures indicated the ascendency of multiparents crossover over two parents’ crossover. Although multiparents crossover has been used in different fields, to the best of our knowledge, only limited numbers are applied to combinatorial scheduling problems and none has been proposed for JSSP. In particular, Eiben et al.  proposed multiparent for the adjacency based crossover (ABC) and Ting et al.  developed multiparent extension of partially mapped crossover (MPPMX) for the travelling salesman problems. Although the experimental results point out that ABC of multiparents has no tangible benefit, MPPMX shows significant improvement in the use of multiparents in crossover. In other words, one would expect that, by biasing the recombination operator, the performance of the GA would improve.
In this paper, we propose extended precedence preservative crossover (EPPX) as a multiparent crossover. EPPX is based on the precedence preservative crossover (PPX) proposed by Bierwirth et al. . Because of its ability to preserve the phenotypical properties of the schedules. EPPX as crossover operator will retain this advantage in the GA. EPPX is used in GA in conjunction with neighborhood search to solve JSSP. The rest of the paper is organized as follows. JSSP and the different types of schedules are described in detail in the next section. In Section 3, we present our approach to solve the JSSP: chromosome representation, schedule generation procedure, neighborhood search procedure, and GA with multiparents crossover. Section 4 provides experimental results and analysis. The conclusions are drawn in Section 5.
2. Problem Definition
2.1. Job Shop Scheduling Problem (JSSP)
The JSSP can be defined as a set of jobs that need to be processed on a set of machines. A job consists of a set of operations , where represents the th operation of the th job. The technological requirement for each operation processing time is denoted as and a set of machines is denoted by .
Precedence constraint of the JSSP is defined as  operation th must finish before operation in the job. A job can visit a machine once only. Only one operation at a time for one time is allowed to be processed in a machine. It is assumed that the delay time for the job transfer machine will be neglected and operation allocation for machine will be predefined. Preemption of operations is not allowed. There are no precedence constraints among the operations of different jobs.
The main objective of JSSP is to find the minimum makespan for the scheduling. The finish time of job with last operation, , is represented by . The time for the whole schedule to complete or the makespan is also the maximum finish time of a set of the jobs . Therefore, the makespan is expressed as follows:
Let be the set of operations being processed in machine and let
The conceptual model of the JSSP is shown as below:
The objective function represented by (3) minimizes the maximum finish time in the set of the jobs and therefore minimizes the makespan. Equation (4) satisfies precedence relationships between operations and (5) imposes that an operation can only be assigned to a machine at a time.
Table 1 shows an example of 3 jobs and 3 machines and their sequences for JSSP.
Table 1: Example for 3-job and 3-machine problem.
2.2. Type of Schedules
Three types of feasible schedule are considered: semiactive, active, and nondelay schedule . In a semiactive schedule, there are no operations that can be started earlier without altering the sequences of the operations. In a semiactive schedule the makespan may often be reduced by shifting an operation to the left without delaying other jobs. Reassignment of operations is called a permissible left shift. An active schedule is a schedule with no more permissible left shifts. Therefore, the set of active schedules is a subset of semiactive schedules. In a nondelay schedule, no machine is kept idle at a time when it could begin processing other operations and hence the set of nondelay schedules is a subset of active schedules. In addition the search space can be further reduced by implementing a full-active schedule introduced by Zhang et al. . A full-active schedule is defined as a schedule where there is no more permissible left or right shift. Optimal solution of the scheduling always lies in the full-active schedule. Figure 1 illustrates the interaction of the schedules.
Figure 1: Relationship of the schedules.
In order to generate the full-active schedule, we employ a scheduling approach called iterative forward-backward pass  in Section 3.1.2 which performs a kind of local search that can be used to introduce heuristic improvement into genetic search.
3. Hybrid Genetic Algorithm
GA is a stochastic search optimization technique that mimics the evolutionary processes in biological systems. This approach begins with a population, which represents a set of potential solutions in the search space. Each individual in the population is assigned a value by GA according to a problem specific objective function. The individuals will attempt to combine the good features in each individual in the population using a reproduction operator step such as crossover or mutation in order to construct individuals which are better suited than previous individuals. Through this evolution process, individuals that are less fit tend to be replaced by fitter individuals to generate a new population which eventually the desired optimal solutions will be found.
3.1. Schedule Generator Procedure
3.1.1. Chromosome Representation and Decoding
Representation of JSSP in chromosome is classified by Cheng et al.  into two approaches: direct and indirect. The direct approach directly encodes and decodes the representation into schedule while the indirect approach needs a schedule builder to encode and decode the chromosome into the schedule. The indirect approach is adopted in this study to represent the individual.
The chromosome in this paper is represented as operation based representation. In this representation, represents the number of jobs and is repeated according the total number of operations in the job. Figure 2 illustrates the representation of 3 jobs and 3 machines. The chromosome is represented as , where jobs 1, 2, and 3 are represented as numbers 1, 2, and 3 in the chromosome, respectively. The number of occurrences in each chromosome depends on the number of operations required. The chromosome is scanned from left to right and at the th occurrence of a job number refers to the th operation in the technological sequence of this job. The chromosome created is always feasible and legal.
Figure 2: Permutation with repetition representation for 3 jobs and 3 machines.
A scheduling can be built by constructing a schedule builder that performs a simple local search to decode the genes of the chromosome from left to right to a list of ordered operations. The first operation in the list is scheduled first, then the second operation, and so on. The operation will always be shifted to the left until time is equal to zero or inserted into a blank time interval between operations to find the earliest completion time. The process is repeated until all operations are scheduled. A schedule generated by the procedure can be guaranteed to be an active schedule . Figure 3(a) illustrates the scheduling encoded by following operation sequences in the chromosome . Applying the process will enable the job to find possible earlier start time before being appended as last operation in the machine (Figure 3(b)) and the chromosome encoded is transformed to . In this representation, two or more chromosomes decoded may be translated into an identical schedule.
Figure 3: Permissible left shift for semiactive schedule.
3.1.2. Schedule Generation Procedure
The procedure used to construct full-active schedule is based on a scheduling scheme called iterative forward-backward pass. This approach was proposed by Lova et al.  which had been shown to produce significant improvement in reducing makespan in the other field of scheduling problems.
The algorithm described in Section 3.1.1 uses a forward pass approach to generate an active schedule with the makespan in the schedule in which the operations are able to shift left until time is equal to zero. Backward pass is a reverse process of the forward pass where the operations in a schedule start from end of the schedule and end at the beginning of the schedule , in which the operations are able to shift right until time is equal to .
The iterative forward-backward pass approach can be described with the following steps.
Step 1. An active schedule chromosome is generated by forward pass with maximum makespan .
Step 2. Apply backward pass on the chromosome from Step 1. Chromosome is scanned starting from right to left to generate a schedule with start time (Figure 4). Through the right shifting in the schedule, we can obtain the beginning of the schedule and the makespan of this schedule is given as and denote makespan and minimum time, respectively, in this new schedule. The new schedule is encoded into a new chromosome with makespan .
Step 3. If , the makespan obtained from the schedule in Step 2 is less than the makespan in the schedule of Step 1, there is improvement of the schedule makespan, and then the new chromosome is used in Step 1; otherwise the active schedule chromosome and the makespan generated by forward pass are maintained. Steps 1 and 2 are repeated until there is no further improvement on the schedule (Figure 5).
Figure 5: Iterative forward-backward pass.
In this iterative function, the makespan of both processes is mutually restricted and hence the makespan of new solution generated either is lesser or remains unchanged. The last schedule generated by forward pass is equivalent to the last schedule generated by backward pass with the same makespan and they are sharing the same critical path.
Figure 6 shows the steps where each chromosome generated by the GA employed the schedule generator procedure. The procedure starts from generating the full-active schedule by schedule generation procedure and then applying the neighborhood search to improve the schedule obtained. After improvement of the schedule ends, the corresponding quality of the makespan is obtained. The neighborhood search is presented in the next section.
Figure 6: Architecture of schedule generation procedure.
3.1.3. Neighborhood Search Procedure
Reduction of the search space does not guarantee the optimal solution will be found. Therefore we use a neighborhood search as an exploitation mechanism to decrease the makespan. This mechanism is restricted to searching the possible solutions in a critical path that consists of longest sequences of operation in a schedule. Swapping the operations on the path by using neighborhood search significantly reduces the total length of the makespan .
Instead of the swap operation which is determined deterministically as in , we modify the operation such that we chose the operations to be swapped randomly in a critical block. The neighborhood search starts with the identification of the critical path in the schedule generated by the scheduling process. Operations on the critical path are called critical operations. A critical block consists of a maximal sequence of adjacent critical operations that are processed on the same machine . Our neighborhood is defined as the random swap between two jobs in a critical block that contains two or more operations. No swap is made if the critical block contains only one operation.
All possible moves of the operations are predetermined (Figure 7). A swap of the operations is accepted if it improves the makespan; otherwise the operations remain unchanged. Once the swap is accepted, the new critical path must be identified. The procedure is repeated and stops if there is no swap that can improve the makespan. Pseudocode for the neighborhood search is presented in Algorithm 1.
Algorithm 1: Pseudocode for neighborhood search.
Figure 7: Critical path, critical operations, and possible operations swaps.
3.2. Hybrid GA
In our proposed hybrid GA, the search methods will be based on intensification and diversification mechanisms. The neighborhood search acts as an intensification mechanism that exploits the better solution in an individual and GA functions as diversification mechanism that explores the search space to provide different individuals for the local search. Structure of the hybrid GA that is based on a standard GA may be represented by the pseudocode in Algorithm 2.
Algorithm 2: Pseudocode for a standard GA.
Population is initialized randomly with a set of parameters and a particular chromosome which is often referred to as an individual. Each individual is evaluated by a fitness function and the parents selected for the recombination, which favors fitter individuals. The selected chromosomes are recombined using mechanisms of crossover and mutation to produce offspring. These offspring are then evaluated and then elitism strategy is applied to the new offspring with best fitness to replace the worst individuals in the previous population to generate a new population. Termination criterions of the GA in JSSP are set to terminate once the GA had achieved the optimal solution (if have) or maximum number of generations is reached.
3.2.1. Fitness and Selection Method
In this paper, we use nonlinear ranking to rank the evaluated chromosomes and each chromosome competes with the others and the selected chromosome survives to the next generation based on the fitness value (objective function). Chromosome with greater fitness indicates the greater probability to survive. The highest ranking chromosome in a population is considered the best solution. It is noted that the lowest makespan is given the highest ranking.
Stochastic universal sampling (SUS) is applied to select the parents for recombination in our GA. SUS is one of the selection methods that are often used in practice because they have less stochastic noise and have a constant selection pressure . This fitness based proportionate selection will choose the chromosomes process with minimum spread and zero bias. SUS uses equally spaced pins on wheel, where is the number of selections required. The population is shuffled randomly and a single random number in the range is generated in which represents the sum of all the fitness values of the individuals in the population.
3.2.2. Proposed Extended Precedence Preservative Crossover (EPPX)
Generally in natural biological system the reproduction takes place between two parents (bisexual) or in a single parent (asexual). However from the computational perspective, there is no restriction on the number of parents to use. Therefore some of the multiparents crossover operators are extended from the two-parent crossover operators [17–20