# Dynamic Seed Genetic Algorithm to Solve Job Shop Scheduling Problems

Flávio Grassi, Pedro Schimit, Fabio Henrique Pereira

► To cite this version:

Flávio Grassi, Pedro Schimit, Fabio Henrique Pereira. Dynamic Seed Genetic Algorithm to Solve Job Shop Scheduling Problems. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2016, Iguassu Falls, Brazil. pp.170-177, 10.1007/978-3-319-51133-7_21. hal-01615722

HAL Id: hal-01615722

https://inria.hal.science/hal-01615722

Submitted on 12 Oct 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Dynamic Seed Genetic Algorithm to Solve Job Shop Scheduling Problems

Flávio Grassi, Pedro Henrique Triguis Schimit and Fabio Henrique Pereira

Universidade Nove de Julho, São Paulo, Brazil.

{schimit, fabiohp}@uninove.br

**Abstract.** This paper proposes a simple implementation of genetic algorithm with dynamic seed to solve deterministic job shop scheduling problems. The proposed methodology relies on a simple indirect binary representation of the chromosome and simple genetic operators (one-point crossover and bit-flip mutation), and it works by changing a seed that generates a solution from time to time, initially defined by the original sequencing of the problem addressed, and then adopting the best individual from the past runs of the GA as the seed for the next runs. The methodology was compared to three different approaches found in recent researches, and its results demonstrate that despite not finding the best results, the methodology, while being easy to be implemented, has its value and can be a starting point to more researches, combining it with other heuristics methods that rely in GA and other evolutionary algorithms as well.

**Keywords:** Genetic algorithms · Job shop · Scheduling · Dynamic seed

## 1 Introduction

Scheduling is the process of assigning one or more resources to perform certain activities whose processing will require a certain amount of time [1]. These resources in an industrial environment may be associated with machines, and the activities that will be processed in a machine are known as operations or tasks. Thus, a job is a set of one or more tasks.

The scheduling problems in scenarios of job shop (JSSP) is a NP-hard problem which has been studied by using exact methods, such as the Branch and Bound [2] and the Shifting Bottleneck [3]. It consists of scheduling a set of tasks in different machines; known as jobs, where the precedence of each task must be obeyed. Each job can be processed in one machine at a time, and the task started in a certain machine must be completed before this resource starts a new process, i.e., no pre-emption is allowed. The time need for each task to be processed is known in advance for deterministic problems, and finally, all the jobs are available in the time zero [1]. Usually, researchers consider the minimization of the makespan as the goal, where makespan refers to the total time needed to process all operations of all the jobs in the machines.

In recent years, the metaheuristic methods have been widely used in solving this type of problem. Among these methods, those with greater emphasis for solving JSSP are
Tabu Search [4], Simulated Annealing [5], Genetic Algorithms [6, 7], and Ant Colony Optimization [8].

This paper presents a different methodology to solve JSSP using genetic algorithms. A genetic algorithm (GA) is as a class of metaheuristic techniques that is aimed at finding solutions based on the mechanisms of natural selection and genetics. From an initial population, each individual is evaluated by a fitness function which depends on the purpose. Crossover and mutation operators are used for new generation of individuals in order to ensure a better access to the search space.

The paper is organized as follows. The detailed presentation of the JSSP is provided in Section 2. Section 3 provides the experimental results to solve a set of deterministic JSSP in comparison with different works that have been currently referenced. Section 4 presents the conclusions and suggests some aspects that could be subject to further researches.

## 2 Proposed methodology

The proposed methodology suggests a simple indirect representation based on a binary matrix and, therefore, the use of simple genetic operators, such as the one-point crossover and bit-flip mutation. Despite its simplicity, it proved powerful enough by its association with the dynamic seed, which is based on the inheritance of the previous seed that generated the best solution within a certain number of generations and its best individual, as further explained in the next sections.

In order to evaluate the simulation code developed, 10 different sequences for the FT06 problem, generated from LISA [9], were presented to the simulation code. LISA is an open-source software developed by a group of researchers at Otto-von-Guericke University (under the supervision of Prof. Dr. Frank Werner) for creating, editing and troubleshooting deterministic scheduling problems, which has a useful graphical interface.

### 2.1 Representation mechanism

The representation adopted in this work is based on a binary matrix of dimension $m \times (n-1)$, where $m$ is the number of the machines and $n$ is the number of jobs. Since this representation does not allow a direct interpretation of a solution for the problem, Figure 1 and Figure 2 are used in order to clarify the process of decoding, considering a specific instance of JSSP known as FT06, available at the OR-Library [10].

First, the matrix of routes (Figure 1a), which is given by the problem, is converted into a sequence of jobs per machine, according to the natural order of arrival of jobs, which is the seed for the solutions (Figure 1b). To that end, the initial matrix is read by columns, from left to right, for each machine, in ascending order of jobs. This process is executed just once within GA, at the first run of the optimization process.
<figure><img src="image_2.png" /><figcaption>Fig. 1. Generation of the seed (b) based on the routes (a)</figcaption></figure>

Thus, reading the first column in the matrix of routes, job 1 comes first in the ma-
chine 3, followed by jobs 3, 5, and jobs 2, 4 and 6 from the columns 2, 3 and 6 in the
matrix of routes, respectively; thereby generating the third row of the seed (Figure 1b).
Then, the process is repeated for all other machines.

The GA generates a binary matrix (Figure 2b), which is the chromosome. After the first generation, the genetic operators act over this matrix. A reading of this matrix by rows is performed, from top to bottom, and where the value 1 is identified, a permutation in the seed is accomplished. The permutation occurs between the element in the same position where the value 1 in the chromosome was found, and its successor.

Therefore, as the value of first element of the chromosome (in Figure 2b) is 1, a
permutation between the values 1 and 4 in the seed occurs (Figure 2a), generating the
first element of the new array of sequences (Figure 2c), which is the job 4, and the
second element, that is the job 1. Until this moment, the job 1 is temporarily in the
position 2, since his stay in that position depends upon the value of the second element
in the chromosome.

As the value of the second position in the chromosome is 0, there will be not swap-
ping between the second and third element of the original sequence. Thus, the first two
elements of the new matrix are really the jobs 4 and 1, respectively. This process is
repeated with all the elements of the first row of the seed, and then all the elements of
the second row of the seed, and so forth. The reason to have just five elements in the
rows of the chromosome is because the swapping occurs between the element in the
current position and its successor, which means a value of 1 in the fifth position already
generates permutation between the fifth and sixth elements of the original seed, and
therefore is not necessary to have a sixth column (considering the problem FT06).
<figure><img src="image_3.png" /><figcaption>Fig. 2. Representation schema of FT06 instance</figcaption></figure>

Finally, the new matrix generated through the permutation is turned into a matrix of
priority of the jobs per machine (Figure 2d), which is the way that the simulation code
interprets the sequences. Analyzing the first three jobs in the first row of the permuted
matrix is clear to see that job 4 should be scheduled first in the machine 1, followed by
jobs 1 and 6, respectively. Therefore, in the matrix of the priorities (which is the repre-
sentation of the solution itself), these are the jobs that receive priority values 1, 2, and
3, respectively. This process is conducted on all elements of the new matrix, called a
solution (Figure 2d).

## 2.2 Dynamic Seed Genetic Algorithm

The proposed approach, called Dynamic Seed Genetic Algorithm (DSGA), applies the
classical GA as an inner level in which the candidate solutions are generated through
permutations of the seed based on chromosomes, according to Figure 2. Additionally,
an external level is created in order to update the seed dynamically. After some gener-
ations of the classic GA in the inner level, a defined number of best solutions are chosen
and a local search is performed in each of them, related to the original route of the
problem addressed, thus generating new seeds. Specifically, the local search permutes
the predecessor and successor of a chosen job that its delay will directly cause a delay
that affects the whole system (i.e. a job that belongs to the so called critical path). Then,
the best current solution and the corresponding permuted seed are used to update the
seed from the previous step and a new set of generations in the inner level takes place.
# 3 Experiments

To prove the effectiveness of the proposed approach, a set of JSSP instances was taken from OR-Library, which is used by several researchers to compare their results against different methods and techniques. The instances set range from LA01 to LA10, due to Lawrence [11]. This set of problems deals with the classical deterministic job shop problem, which does not take into account the dynamic and stochastic behavior that can reflect more appropriately real-world industry situations. However, GA presents peculiar aspects in relation to other optimization methods and it is simple, flexible, robust and particularly useful in solving problems where other optimization techniques facing difficulties. Especially in relation to the fitness function, that may be a mathematical function, an experiment, a simulation model or a metamodel.

So, the proposed approach can be easily integrated with a simulation model in order to deal with a dynamic job shop scheduling problem that can take into account factors like, for example, random release and processing times, setup times, random machine breakdowns, and create more robust scheduling with regard to the stochastic and dynamically changes in the real manufacturing environment [12].

For each instance the proposed approach was run 10 times, in order to allow statistical references. The implementation was made through GAlib, which is a library of GA written in C++ by Matthew Wall, from the Massachusetts Institute of Technology [13]. Parameters adopted in GA are summarized in Table 1.

<table><caption>**Table 1.** Parameters of the GA adopted in the experiments</caption><thead><tr><td>Parameter</td><td>Adopted Value</td><td>Reason</td></tr></thead><tbody><tr><td>Chromosome Representation</td><td>Binary, matrix of dimension m × (n-1)</td><td>Proposed methodology</td></tr><tr><td>Selection</td><td>Steady State</td><td>[14]</td></tr><tr><td>Replacement Rate</td><td>90%</td><td>Experiments</td></tr><tr><td>Population Size</td><td>10</td><td>Experiments</td></tr><tr><td>Crossover</td><td>One-point</td><td>Proposed methodology</td></tr><tr><td>Crossover Rate</td><td>10%</td><td>Experiments</td></tr><tr><td>Mutation</td><td>Bit-flip</td><td>Proposed methodology</td></tr><tr><td>Mutation Rate</td><td>1%</td><td>Experiments</td></tr><tr><td>Total Number of Generations</td><td>20,000 (50 internal plus 400 external)</td><td>Experiments</td></tr><tr><td>Stop Criteria</td><td>Number of Generations</td><td>[15]</td></tr><tr><td>Fitness Function</td><td>Simulation code</td><td>Proposed methodology</td></tr></tbody></table>

## 3.1 Performance related to the quality of the solution

Unlike to run the total number of iterations once with elitism, which is largely used in the classic GA, in addition to inherit the best individual, the proposed approach also copies to the next generations the generator seed that was associated with that better individual. So, the seed is updated and used to create new candidate solutions in the following inner level, which contributes to the convergence process.
This approach allows the GA to route new and possibly better paths, as the initial population after each external loop is based on the best seed from previous generations in the inner level (i.e., a classic GA). By route better paths we mean to create a larger number of feasible solutions during the evolution process of the genetic algorithm in relation to the classical elitism approach, as it can be seen in Table 2.

The results of the proposed approach were also compared to three different methodologies found in the current researches. The Memetic Algorithm approach (MA) is due to [16], while the Differential Algorithm with Sub-Group (DE) is due to [17] and the Hybrid Genetic Algorithm (HGA) is due to [7].

<table><caption>**Table 2.** Feasible solutions of LA01 problem: classic GA vs. DSGA</caption><thead><tr><th colspan="3">Classic GA (with elitism)</th><th colspan="3">DSGA</th></tr><tr><th>Run</th><th>Feasible Solutions</th><th>Non-feasible Solutions</th><th>Run</th><th>Feasible Solutions</th><th>Non-feasible Solutions</th></tr></thead><tbody><tr><td>1</td><td>103377</td><td>21623</td><td>1</td><td>115866</td><td>9134</td></tr><tr><td>2</td><td>102310</td><td>22690</td><td>2</td><td>116068</td><td>8932</td></tr><tr><td>3</td><td>101788</td><td>23212</td><td>3</td><td>114116</td><td>10884</td></tr><tr><td>4</td><td>101450</td><td>23550</td><td>4</td><td>115649</td><td>9351</td></tr><tr><td>5</td><td>102594</td><td>22406</td><td>5</td><td>114525</td><td>10475</td></tr><tr><td>6</td><td>103293</td><td>21707</td><td>6</td><td>118684</td><td>6316</td></tr><tr><td>7</td><td>104061</td><td>20939</td><td>7</td><td>118174</td><td>6826</td></tr><tr><td>8</td><td>102746</td><td>22254</td><td>8</td><td>115275</td><td>9725</td></tr><tr><td>9</td><td>101706</td><td>23294</td><td>9</td><td>116231</td><td>8769</td></tr><tr><td>10</td><td>103665</td><td>21335</td><td>10</td><td>116218</td><td>8782</td></tr><tr><td>Average</td><td>82.16%</td><td>17.84%</td><td>Average</td><td>92.86%</td><td>7.14%</td></tr></tbody></table>

In order to ease compare the approaches, Table 3 summarize the makespan values obtained from the proposed methodology and those reported from other recent methodologies used to compare with. It is important highlight that the approaches DE, MA and HGA are not based only on the AG and can therefore be even more difficult to program and use.

<table><caption>**Table 3.** Makespan values obtained from the different methodologies (BKS = Best Known Solution, Avg. = Average)</caption><thead><tr><th rowspan="2">Instance</th><th rowspan="2">Size (n x m)</th><th rowspan="2">BKS</th><th colspan="8">Methodology</th></tr><tr><th colspan="2">MA</th><th colspan="2">DE</th><th colspan="2">HGA</th><th colspan="2">DSGA</th></tr><tr><th></th><th></th><th></th><th>Best</th><th>Avg.</th><th>Best</th><th>Avg.</th><th>Best</th><th>Avg.</th><th>Best</th><th>Avg.</th></tr></thead><tbody><tr><td>LA01</td><td>10 x 5</td><td>666</td><td>666</td><td>NA</td><td>666</td><td>666.0</td><td>666</td><td>NA</td><td>666</td><td>672.6</td></tr><tr><td>LA02</td><td>10 x 5</td><td>655</td><td>655</td><td>NA</td><td>655</td><td>663.6</td><td>655</td><td>NA</td><td>660</td><td>680.8</td></tr><tr><td>LA03</td><td>10 x 5</td><td>597</td><td>597</td><td>NA</td><td>597</td><td>610.4</td><td>597</td><td>NA</td><td>616</td><td>619.2</td></tr><tr><td>LA04</td><td>10 x 5</td><td>590</td><td>590</td><td>NA</td><td>590</td><td>597.3</td><td>590</td><td>NA</td><td>607</td><td>619.8</td></tr><tr><td>LA05</td><td>10 x 5</td><td>593</td><td>593</td><td>NA</td><td>593</td><td>593.0</td><td>593</td><td>NA</td><td>593</td><td>593.0</td></tr><tr><td>LA06</td><td>15 x 5</td><td>926</td><td>926</td><td>NA</td><td>926</td><td>926.0</td><td>926</td><td>NA</td><td>926</td><td>926.0</td></tr><tr><td>LA07</td><td>15 x 5</td><td>890</td><td>890</td><td>NA</td><td>890</td><td>890.0</td><td>890</td><td>NA</td><td>890</td><td>890.0</td></tr><tr><td>LA08</td><td>15 x 5</td><td>863</td><td>863</td><td>NA</td><td>863</td><td>863.0</td><td>863</td><td>NA</td><td>863</td><td>863.0</td></tr><tr><td>LA09</td><td>15 x 5</td><td>951</td><td>951</td><td>NA</td><td>951</td><td>951.0</td><td>951</td><td>NA</td><td>951</td><td>951.0</td></tr><tr><td>LA10</td><td>15 x 5</td><td>958</td><td>958</td><td>NA</td><td>958</td><td>958.0</td><td>958</td><td>NA</td><td>958</td><td>958.0</td></tr></tbody></table>
# 4 Conclusions and Suggestions

This paper presented a different methodology to solve Job Shop scheduling problems using Genetic Algorithms, which the authors called DSGA. The methodology works by using a simple indirect binary representation as the chromosome and simple genetic operators (one-point crossover and bit-flip mutation), and change the seed that generates a solution from time to time, initially defined by the original sequencing of the problem addressed, and then adopting the best individual from the past runs of the GA as the seed for the next runs.

The proposed methodology is easy to implement and, despite not finding the optimal solution for all instances, the simple proposed approach fails in problems in which the convergence to the optimal makespan is harder in all the different approaches, even for more sophisticated techniques which is especially true for square problems that are admittedly more difficult problems. Moreover, the proposed approach allows the GA to go through new and possibly better paths, which means to create a larger number of feasible solutions during the evolution process of the genetic algorithm in relation to the classical elitism approach.

As a continuity of this work, it is suggested to implement the proposed methodology in stochastic problems, with randomly processing times, obeying a probability distribution.

**Acknowledgements.** The authors would like to thank grant #2014/08688-4, São Paulo Research Foundation (FAPESP), for their funding of this research.

# References

1. Pinedo, M. L.: Scheduling: Theory, Algorithms and Systems. New York: Springer (2008)

2. Jamili, A.: Robust Job Shop Scheduling Problem: Mathematical Models, Exact and Heuristic Algorithms. Expert Systems with Applications, 55 (15), 341-350 (2016)

3. Braune, R. Zäpfel, G.: Shifting Bottleneck Scheduling for Total Weighted Tardiness Minimization—A Computational Evaluation of Subproblem and Reoptimization Heuristics, Computers & Operations Research, 66, 130-140 (2016)

4. Bo P., Zhipeng L., Cheng, T.C.E.: A Tabu Search/Path Relinking Algorithm to Solve the Job Shop Scheduling Problem. Computers & Operations Research, 53, 154-164 (2015)

5. Faccio, M., Ries, J. and Saggioro, N.: Simulated Annealing Approach to Solve Dual Resource Constrained Job Shop Scheduling Problems: Layout Impact Analysis on Solution Quality. International Journal of Mathematics in Operational Research, 7 (6), 609-629 (2015)

6. Kurdi, M.: An Effective New Island Model Genetic Algorithm for Job Shop Scheduling Problem. Computers & Operations Research, 67, 132-142 (2016)

7. Qing-Dao-Er-Ji, R., Wang, Y.: A New Hybrid Genetic Algorithm for Job Shop Scheduling Problem. Computers & Operations Research, 39 (10), 2291-2299 (2012)
8. Huang, R., Yang, C.-L., Cheng, W.-C.: Flexible Job Shop Scheduling with due Window— A Two-Pheromone ant Colony Approach. International Journal of Production Economics, 141 (2), 685-697 (2013)

9. LISA: A Library of Scheduling Algorithms [online]. Available from: http://www.math.ovgu.de/Lisa.html

10. Beasley, J. E.: OR-Library [online]. Available from: http://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/jobshop1.txt (2003)

11. Lawrence, S.: Resource Constrained Project Scheduling: An Experimental Investigation of Heuristic Scheduling Techniques (Supplement). PhD diss., Carnegie-Mellon University (1984)

12. Menezes, F. M., Blanco, G. T., Rodriguez, P. C., Pereira, F. H.: Application of Simulation and Optimization for Dynamic Job Shop Scheduling Under Stochastic Demand Variability. Proceedings of 7th International Conference on Management of computational and collective IntElligence in Digital EcoSystems (MEDES'15), v. 1, 1-8 (2015)

13. GAlib: A C++ Library Of Genetic Algorithm Components [online]. Available from: http://lancet.mit.edu/ga/dist/ [Accessed November 19, 2014].

14. Yamada, T.: Studies on Metaheuristics for Jobshop and Flowshop Scheduling Problems. PhD diss., Kyoto University (2003)

15. Mitchell, T. M.: Machine Learning. New York: McGraw-Hill (1997)

16. Gao, L., Zhang, G., Zhang, L., and Li, X.: An Efficient Memetic Algorithm for Solving the Job Shop Scheduling Problem. Computers & Industrial Engineering, 60 (4), 699-705 (2011)

17. Wisittipanich, W., Kachitvichyanukul, V. Two Enhanced Differential Evolution Algorithms for Job Shop Scheduling Problems. International Journal of Production Research, 50 (10), 2757-2773 (2012)