Abstract: A meta-heuristic approach for solving the flexible job-shop scheduling problem (FJSP) is presented in this study. This problem consists of two sub-problems, the routing problem and the sequencing problem and is among the hardest combinatorial optimization problems. We propose a Genetic Algorithm (GA) for the FJSP. Our algorithm uses several different rules for generating the initial population and several strategies for producing new population for next generation. Proposed GA is tested on benchmark problems and with due attention to the results of other meta-heuristics in this field, the results of GA show that our algorithm is effective and comparable to the other algorithms.
INTRODUCTION
One of the most necessary subjects in the planning and managing of manufacturing environments is the scheduling of operations . To find the best schedule can be very easy or very difficult, depending on the shop environment, the process constraints and the performance indicator (Pinedo, 2002). The Job-shop Scheduling Problem (JSP) is one of the most popular scheduling models existing in practice (Cheng et al., 1996). It has attracted many researchers due to its wide applicability and inherent difficulty (Nowicki and Smatnicki, 1996; Jain and Meeran, 1999). The classical JSP consists in scheduling a set of jobs on a set of machines with the objective to minimize a certain performance indicator, subject to the constraint that each job has a specified processing order through all machines which are fixed and known in advance. A typical performance indicator for JSP is the makespan, i.e., the time needed to complete all the jobs. FJSP is NP-hard since it is an extension of the job-shop scheduling problem (Gao et al., 2008).
FJSP is an extension of the classical JSP which exist an allowable set of machines for each operation to processes on any among them. FJSP can decomposed into two sub-problems: Assigning the operations to machines (the routing problem) and sequencing the operations on the machines (the sequencing problem) in order to minimize the performance indicators. Then, FJSP is more difficult than the classical JSP because it contains an additional problem that is assigning operations to machines.
Bruker and Schlie (1990) developed a polynomial algorithm for solving the flexible job-shop scheduling problem with two jobs. Exact methods developed, but they are not applicable for instances with more than 20 jobs and 10 machines (Pinedo, 2002). In recent years, meta-heuristics such as simulated annealing, tabu search and genetic algorithms has used to solve FJSP. They can be categorized into 2 groups: Hierarchical approach and integrated approach. The hierarchical approach attempts to solve the problem by decomposing it into a sequence of sub-problems, with reduced difficulty. A typical decomposition is assign-then-sequence, coming from the trivial observation that once the assignment is done, the resulting sequencing problem is a JSP (Pezzella et al., 2008). Brandimarte (1993) and Paulli (1995) followed this approach. Kacem et al. (2002a) proposed a genetic algorithm and expanded approach by localization to achieve capable initial assignments. Xia and Wu (2005) applied a hybrid of Particle Swarm Optimization (PSO) and Simulated Annealing (SA) as a local search algorithm to solving this problem as a hierarchical approach.
Integrated approaches are used by considering assignment and sequencing at the same time and usually obtain better results than hierarchical approach, but they are much more difficult to solve. Gao et al.(2008) used a hybrid of GA and Variable Neighborhood Descent (VND) for this problem as an integrated approach. Pezzella et al. (2008) employed several different strategies for initial population generation and new individual reproduction, specially an intelligent mutation, in a GA framework based on approach by localization for solving FJSP as an integrated approach. Fattahi et al. ( 2007) presented a SA and a Tabu Search (TS) and proposed two hierarchical approaches and four integrated approaches by hybridization of them for solving the FJSP.
A genetic algorithm as an integrated approach is presented for solving this problem. To achieve initial assignments, we do the same as (Pezzella et al., 2008) that adopted the approach by localization of (Kacem et al., 2002a, b) as Assignment Rule 1 and Assignment Rule 2. Then, random selection of the next job is adopted to sequence the operations to generate the initial population. Our algorithm also employs multiple different mutation and crossover operators for assigning and sequencing. We present the computational results on a number of benchmark problems and compare them with the results presented by previous authors.
PROBLEM DEFINITION
The FJSP can be explained as follows. It is given a set of jobs, J = {J1, ..., Jn}, and a set of machines, A = {M1, ..., Mm}, such that each job Ji consists of a sequence of ni operations, Oi,1, Oi,2, ...,Oi,ni. Job Ji is completed when its operations performed one after another in the given order. For each operation of job Ji, Oi,j, there are a set of allowable machines called Aij ⊆ A, which Oi,j can be performed on one of them such as Mk ε Aij. The FJSP is machine-dependent because the performance of each operation on each allowable machine has a different processing time like pijk>0. Flexibility of problems can be categorized into partial flexibility and total flexibility. It is partial, when at least one of Aij be proper subset of A (Aij ⊂ A) and it is total, when we have Aij = A for all operations. Operations execute on machines without preemption and machines can perform at most one operation at a time. All jobs and machines are available at time 0. An example is given in Table 1. Each row refers to an operation, each column refers to a machine and cells are processing times. Notice that this example has partial flexibility and unallowable machines for each operation denoted by ∞ in processing times table (Table 1).
| Table 1: | Processing times of example |
THE SOLUTION ALGORITHM
In this study, a genetic algorithm for solving the flexible job-shop scheduling problem (FJSP) is presented. This algorithm uses several different rules for generating the initial population and several strategies for producing new population for next generation.
Genetic algorithm: Genetic algorithms (Gas)were introduced by Holland (1975) and have been applied in a number of fields, e.g., mathematics, engineering, biology, and social science (Goldberg, 1989). GAs are intelligent stochastic optimization techniques based on the mechanism of natural selection and genetics. GAs start with an initial set of solutions, called population. Each solution in the population is called a chromosome (or individual), which represents a point in the search space. A chromosome consists of some genes. GAs work iteratively, each single iteration is called a generation. At each generation, the fitness of each chromosome is evaluated, which is decided by the fitness function, and the chromosome is stochastically selected for the next generation based on its fitness. New chromosomes, called offspring (or children), are produced by two genetic operators, crossover and mutation. The offspring are supposed to inherit the excellent genes from their parents, so that the average quality of solutions is better than that in the previous generations. This evolution process is repeated until some termination criteria are met.
Proposed GA approach: The proposed GA steps are as follows:
Step 1: Initialization:
| (a) | Parameters setting: set the number of initial population (popsize), number of generation(ng), percent of Assignment Rule 1(pa1), percent of Assignment Rule 2 (pa2), probability of each crossover (pc), and probability of each mutation (pm) |
| (b) | Initial population generation |
| (b1) | Initial assignments |
| (i) | Generate pa1* popsize initial assignments by Assignment Rule 1 |
| (ii) | Generate pa2* popsize initial assignments by Assignment Rule 2 |
| (b2) | Sequence the initial assignments randomly |
Step 2: Objective function evaluation: Evaluate the makespan of each chromosome
Step 3: Producing next population:
| (a) | Sort the chromosomes based on makespan value |
| (b) | Reproduction: Copy only the best chromosome to the next generation |
| (c) | Crossover operation: Apply crossover to generate pc* (popsize-1) individuals of the next population using roulette wheel selection strategy |
| (d) | Mutation operation: Select pm* (popsize-1) chromosomes randomly and apply the mutation to make pm* (popsize-1) new individuals of the next population |
Step 4: Termination test: Check the stopping criteria, if the stopping criterion is met return the best chromosome; else go to step 2
Initial population generation: In order to generate the initial population, first, we generate initial assignments, then make the initial population by randomly sequence (randomly select a job) of them. To generate the initial assignments we apply two ways proposed by Pezzella et al. (2008) as Assignment Rule 1 and Assignment Rule 2. They followed the approach by localization of (Kacem et al., 2002a, b) and modified it. Assignment Rule 1 foresees to start from the operation that corresponds to the global minimum in the processing times data. Assignment Rule 2 foresees to permute randomly the jobs and the machines before to apply the approach by localization.
Chromosome representation: In order to perform our algorithm, we use a string of triples (i, j, k), proposed by Kacem et al. (2002a), one for each operation, in which
| • | i is the job that operation is belong to; |
| • | j is the progressive number of that operation within job i |
| • | k is the machine assigned to that operation |
The length of the string equals to the total number of operations. For example, for the problem explained in Table 1, a feasible solution can be represented like this: (1, 1, 1), (3, 1, 3), (2, 1, 2), (3, 2, 1), (2, 2, 3), (1, 2, 2), (1, 3, 2), (2, 3, 1), (2, 4, 2). The Gantt chart of this solution is shown in Fig. 1.
Genetic operators: To generate the next population, the crossover and mutation genetic operators are applied. We employ four genetic operators that can be divided to assignment operators and sequencing operators. Assignment operators which only change the assignment nature of the chromosomes and the sequencing of operations is preserved.
| Fig. 1: | Gantt chart |
| Fig. 2: | Illustration of the reordering mutation |
Sequencing operators which only change the sequence of operations in the chromosomes and the assignment of operations is kept.
Mutation operators: In this study, we employ two mutation operators namely, assignment mutation and reordering mutation. Assignment mutation only exchanges the assignment of a single operation in a single parent. In reordering mutation, we select two positions and reorder the operations between randomly, with observing the precedence constraints, as shown in Fig. 2.
Crossover operators: We also apply two crossover operators, precedence preserving order-based crossover (POX) operator of Lee et al. (1998) and assignment crossover. In POX generates two children starting from two parents. First, POX selects an operation from the first parent, copies in the first child all the operations of the job which the selected operations belong to, then complete this new individual with the remaining operations, in the same order as they appear in the second parent. The symmetric process is repeated for the second parent and the second child. POX preserves the sequencing constraints (Pezzella et al., 2008). Assignment crossover exchanges the assignment of the subset of operations between the two parents and generate new individual.
COMPUTATIONAL RESULTS
We coded proposed GA by C++ language and implemented it on a 2 GHz Pentium IV processor, with 256 MB RAM. To evaluate the performance of our algorithm, we tested it on the data set consist of 20 problems from Fattahi et al. (2007) (Fdata) and compare our results with recent results obtained by them.
Computational experience proves that roulette wheel selection strategy is suitable for performing crossover, randomly selection is suitable for performing mutation and the following values are more effective for our algorithm parameters:
| • | Percent of assignment rule 1 (pa1): 20% |
| • | Percent of assignment rule 2 (pa2): 80% |
| • | Probability of assignment mutation: 10% |
| • | Probability of reordering mutation: 10% |
| • | Probability of assignment crossover: 40% |
| • | Probability of POX crossover: 40% |
Values of some parameters are different for each problem (Small Flexible Job-Shop (SFJS) and Medium Flexible Job-Shop (MFJS)) which are presented in Table 2.
In Table 3 we show the best obtained result by our GA after five runs and compare them with the other results by integrated approaches by Fattahi et al. (2007) on Fdata. They proposed two integrated approaches: ISA (integrated approach with simulated annealing heuristic) algorithm and ITS (integrated approach with tabu search heuristic). The first column refers to problem name. The second and third columns refer to the number of jobs and the number of machines, respectively. The fourth column shows the lower bound of instances. The fifth, 6th and 7th columns present the average of makespans, the best makespan and the average of CPU times over five runs of our GA, respectively.
| Table 2: | Parameter levels of GA |
Other columns are the results of other algorithms we compare to. Also, relative deviation of them with respect to our algorithm is presented in Table 3. The relative deviation is defined as:
(1) |
which Cbest is the makespan obtained by GA and Cf is the makespan of the algorithm we compare to.
Table 4 compares the results of our GA with the results by hierarchical approaches by Fattahi et al. (2007) on Fdata. They presented four hierarchical approaches HSA/SA, HSA/TS, HTS/TS and HTS/SA algorithms. In Table 5, the Mean Relative Error (MRE) of the best solution obtained by our GA and six different approaches by Fattahi et al. (2007) is presented. The relative error (RE) is defined as:
(2) |
which Cbest is the best makespan obtained by the algorithm and LB is the lower bound. In the following, we present the schedule obtained by GA for problem MFJS5 of Fdata with the makespan equal to 514.
| M1: | (O3,1: 0-87)(O2,1: 87-301) |
| M2: | (O4,1: 0-65)(O5,1:65-188)(O1,2: 188-318)(O2,: 318-384) (O5,3: 384-484) |
| Table 3: | Comparison with the hierarchical approaches of Fattahi on Fdata |
| * Av(CPU) is the average computing time in seconds | |
| Table 4: | Comparison with the integrated approaches of Fattahi on Fdata |
| Table 5: | Mean relative error on Fdata |
| M3: | (O1,1:0-100)(O7,1: 100-245)(O7,2: 245-369) |
| M4: | (O6,1: 0-154)(O6,2: 154-304)(O1,3: 318-468) |
| M5: | (O4,2: 65-238)(O3,3: 238-338)(O7,3: 369-514) |
| M6: | (O4,3: 238-374)(O2,3: 384-479) |
| M7: | (O3,2: 87-232)(O5,2: 232-318)(O6,3: 318-498) |
CONCLUSION
In this research, a genetic algorithm investigated for solving flexible job-shop scheduling problem. In this study, the proposed approach is explained in detail by solving benchmark problems and programmed in C++ language. As shown in Table 3 and 4, our GA is effective to overcome mentioned problems. Obtained results are comparable properly with the best results of other authors. We have some recommendation on future works:
| • | Studying in this field with additional constrains, such as maintenance requirements or breakdowns can be interesting |
| • | Developing the meta-heuristics to optimize the other objectives in this field, such as earliness and tardiness will be remarkable |