# Genetic Algorithms with Simulation for a Job Shop Scheduling Problem with Crane Conveyance

Takashi Tanizaki, Hideaki Katagiri

► To cite this version:

Takashi Tanizaki, Hideaki Katagiri. Genetic Algorithms with Simulation for a Job Shop Scheduling Problem with Crane Conveyance. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2017, Hamburg, Germany. pp.483-491, 10.1007/978-3-319-66923-6_57 hal-01666172

HAL Id: hal-01666172

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

Submitted on 18 Dec 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
# Genetic Algorithms with Simulation for a Job Shop Scheduling Problem with Crane Conveyance

Takashi Tanizaki¹, Hideaki Katagiri²

¹Faculty of Engineering, Kindai University,
1 Takaya-Umenobe, Higashi-Hiroshima, Japan, 739-2116
tanizaki@hiro.kindai.ac.jp

²Faculty of Engineering, Kanagawa University

**Abstract.** In this paper, a genetic algorithm (GA) and GA with diversification generator (DG) for solving scheduling problems with crane conveyance are proposed. It becomes very difficult to obtain an optimum or near optimum schedule under consideration of restrictions to avoid crane interference in addition to many restrictions on operation of each machine. GA-based algorithms are applied to obtain high quality crane assignment which successfully leads to few working hour delays caused by crane interference. Effectiveness of this algorithm is confirmed by numerical experiments.

**Keywords:** Scheduling, Genetic Algorithm, Diversification Generator, Crane interference

## 1 Introduction

Scheduling problems of the manufacturing industry generally have a large number of variables and constraints. It is difficult to find an optimal schedule that satisfies all constraints within the practical time. Especially when the products are conveyed by two overhead cranes (hereafter crane), it is necessary to avoid interference of crane conveyance (hereafter crane interference) in addition to restrictions on operation of each machine. In the previous studies, authors proposed an enumeration tree search method [1] and an enumeration tree search method with perturbation [2]. These methods can solve the scheduling problem in a short time, but the search of crane assignment depends strongly on the initial assignment at the beginning of the methods, which fails to explore the solution space widely.

In order to solve this problem, we develop a new solution method using GA and GA with DG for crane assignment in which DG was proposed by Glover [3]. Effectiveness of the proposed method is shown through some numerical experiments.
# 2 Problem Description

## 2.1 Production Process with Crane Conveyance

The process for this research is a job shop process with two cranes (Fig. 1) [2]. The products to be produced are carried in from the left side, and are carried out to the right side after processing at any machine.

<figure><img src="image_2.png" /><figcaption>Fig. 1. Production Process with Crane Conveyance</figcaption></figure>

This production process is consist of following three steps.

(a) First step ... A

(b) Second step ... B1 ~ B5 (There are multiple machines)

(c) Third step ... C

Both cranes can move in the left and right direction. Due to the mutual positional relationship, interference may occur and the operating range may be limited. The conveyance speed and the required time for hoisting and lowering are fixed.

## 2.2 Objective Function and Constraints

The objective of this problem is the minimization of the total time from carrying-in to carrying-out of all products. Constraints are as follows:

(a) There is no division / integration of products. Weight does not increase or decrease.

(b) Each machine cannot process on two or more products at the same time.

(c) Process machines, process sequence, processing times of each machine are given.

(d) Cranes can be selected.

(e) Adjacent crane keeps a certain interval or more.

(f) The possible start time for the third step is given. Delay of start time for third process is avoided as much as possible.

(g) The first carried in time is the start time of the first step.

(h) There is no stock place between machines. If the next machine is in operation, the product to be produced stands by at present machine or at crane.
# 3 Proposed Solution Method

The decision variable of the problem is the assignment of cranes 1 and 2, which is represented as a binary variable taking 1 and 2 if each task of conveyance between machines is assigned to crane 1 and crane 2, respectively. In this paper, the decision vector of the crane assignment is called a solution which is obtained by the proposed GA-based solution method. The proposed method involves backward simulation (Section 3.1) and forward simulation (Section 3.2) to avoid machine conflicts and crane interference. For diversification of solutions explored, GA with DG is constructed by integrating diversification generator (Section 3.3) into GA.

## 3.1 Backward Simulation

The determination of the latest process starting / ending time of each machine begins from the third step in the order of due date, and then is continued by tracing back to the second step and the first step. This time is obtained by subtracting processing time of the machine and conveyance time of crane from the latest ending time of that machine. If machine conflicts occur, processing times are ahead of schedule. Also, without considering the crane interference, conveyance time is calculated moving distance / conveyance speed + lifting / hoisting time.

## 3.2 Forward Simulation

The crane assignment by GA for conveying the product is performed in order of earlier process ending time determined by backward simulation. If crane interference or machine confliction occurs, the process starting / ending times of crane and machines are shifted backward to avoid them (Fig. 2). The gene required for applying the GA is the assignment of crane (Fig. 3). The number of genes at locus is the number of crane conveyance. Forward simulation algorithm is as follows.

### S.1 Initial value setting

Set the number of individuals and the number of generations.

### S.2 Initial parent solution generation

Generate initial parent solutions randomly for the number of individuals. Generate 1 or 2 is set as a gene randomly.

### S.3 Operation simulation and Objective function value calculation

Execute operation simulation. Determine process time and calculate objective function value by the following S.3.1 to S.3.3. Repeat this procedure for the number of individuals.

S.3.1 Assign crane using genes. Determine process starting / end-
ing time of crane so as to avoid crane interference.

S.3.2 As a result of S.3.1, if a delay occurs at the latest process starting / ending time of each machine, the delay time is shifted backward. Furthermore, propagate the delay to process time of the subsequent machines and jobs.

S.3.3 Apply S.3.1 and S.3.2 to all genes in the locus. Calculate objective function value.

<figure><img src="image_3.png" /><figcaption>Fig. 2. Avoidance of crane interference and shifting backward processing time</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Fig. 3. Gene locus</figcaption></figure>
### S.4 Child solution generation (GA)

Using GA for the parent solutions, generate the child solutions for the number of individuals by the following S.4.1 to S.4.4.

S.4.1 Extract two parent solutions randomly from the parent solution group.

S.4.2 Perform two-point crossover to generate two solutions. Crossover points are chosen randomly.

S.4.3 Change the genes of the two solutions generated in S.4.2 to 1 or 2 with a probability of 5% and make them a child solution.

S.4.4 If the solution group becomes an empty set, it ends. Otherwise return to S.4.1.

### S.5 Operation simulation and Objective function value calculation

Execute operation simulation in the same way as in S.3 for the generated child solution, and calculate objective function value.

### S.6 Survivor selection

Select the top half solutions that have good objective function value in the parent and child solutions. Make them the next generation parent solutions.

### S.7 End judgment

If it repeats as many times as the number of generations set in S.1, it ends. Otherwise return to S.4.

## 3.3 Diversification Generator

There is a possibility that bias will occur in the initial solution generated randomly. Therefore, we develop a solution method to use DG for generating initial solution.

DG is a method of generating a new solution sequentially so that the Hamming distance becomes the maximum with respect to the base solution [3]. By using DG as the initial solution of crane assignment, we aim to diversify the initial solution and explore the solution space widely. Algorithm of DG for S.2 in forward simulation is as follows.

### S.1 Initial value setting

Let gene locus be $x = (x_1, x_2, \dots, x_m)$. Let $n.= 2$.

### S.2 Initialize $x$ and $m$

Let be $m$ the number of genes and initialize the element of gene with 1 (i.e. crane 1 is assigned).

### S.3 Generate element $x'_i$

Let $h = n$. Generate element $x'_i$ by following expression. Store the generated $x'_i$ in gene locus.

$$x'_{i} = 3 - x_{1+hk} \quad (\text{for } k = 0, \dots, m/h)$$

### S.4 Generate 1-2 inversion $x''_i$ of $x'_i$

Generate 1-2 inversion $x''_i$ by following expression. Store the gen-
erated $x_i''$ in gene locus.

$$x_i'' = 3 - x_i'$$

S.5 Generate right rotation shift $x_i'''$ of $x_i''$

If $h \ge 3$, generate $x_i'''$ by rotating $k$ to the right relative to $x_i'$. Store the generated $x_i'''$ in gene locus (for $k=1, 2, \dots, h-1$).

S.6 Generate right rotation shift $x_i''''$ of $x_i'''$

If $h \ge 3$, generate $x_i''''$ by rotating $k$ to the right relative to $x_i''$. Store the generated $x_i''''$ in gene locus (for $k=1, 2, \dots, h-1$).

S.7 End judgment

When the number of stored gene locus reaches the number of individuals, it ends. Otherwise, return to S.2 with $n = n + 1$.

# 4 Numerical Experiment

In order to verify the effectiveness of proposed solution, we solve scheduling problems shown in Tables 1 to 3 for the previous research [2] and proposed method, and compare objective function values and solving time.

## 4.1 Numerical Experiment Condition

Processing times and machine positions from left side are shown in Table 1. Many machines are arranged on the left side of process, because there are few equally installed machines in the factory layout. Experimental data settings are shown in Table 2. The number of individuals of GA is set to 512 from the capacity limit of our computer. The number of generation is set to 100, in which the update of the solution almost disappears from experiment result. The delivery time interval is set to 25, because the operation was not established from crane interference if it was shorter than 25 in the experimental results of the previous research. We categorized the tendency of machine selection in the second process (uniform machine selection, alternate jobs with different machine selections, high operating load of the first ten jobs, etc.) are and set the operation pattern in Table 3.

<table><caption>Table 1. Processing times and machine positions</caption><thead><tr><th>Machine</th><th>A</th><th>B1</th><th>B2</th><th>B3</th><th>B4</th><th>B5</th><th>C</th></tr></thead><tbody><tr><td>Processing time</td><td>28</td><td>20</td><td>16</td><td>21</td><td>30</td><td>15</td><td>20</td></tr><tr><td>Position</td><td>20</td><td>35</td><td>55</td><td>80</td><td>120</td><td>150</td><td>220</td></tr></tbody></table>

<table><caption>Table 2. Experimental data setting</caption><thead><tr><th>Individuals</th><th>Generation</th><th>Jobs</th><th>Interval</th><th>Simulation</th></tr></thead><tbody><tr><td>512</td><td>100</td><td>20</td><td>25</td><td>10</td></tr></tbody></table>
<table><caption>Table 3. Operation pattern</caption><thead><tr><th>Pattern</th><th>Job sequence</th><th>Characteristic</th></tr></thead><tbody><tr><td>1</td><td>A→B1→B2→B4→C</td><td>All the same machine</td></tr><tr><td>2</td><td>A→B1→B2orB3→B4orB5→C</td><td>Machine of B 2 and B 3, B 4 and B 5 is unevenly processed</td></tr><tr><td>3</td><td>A→B1→B3→B4→C<br>A→B1→B2→B5→C</td><td>Machine of B2 and B3, B4 and B5 is alternatively processed</td></tr><tr><td>4</td><td>A→B1→B4→B5→C<br>A→B2→B4→B5→C<br>A→B3→B4→B5→C</td><td>Operation with allowance in the first half of the job</td></tr><tr><td>5</td><td>A→B1orB2orB3→B4→B5→C</td><td>Machine of B1, B2, B3 is unevenly processed</td></tr><tr><td>6</td><td>A→B1→B2→B3→B4→C<br>A→B1→B2→C</td><td>The first half job has 6 machines</td></tr><tr><td>7</td><td>A→B1→B2→B3→B4→C<br>A→B1→B5→C</td><td>The second half job has 4 machines</td></tr><tr><td>8</td><td>A→B1→B2→C<br>A→B1→B2→B3→B4→C</td><td>The first half job has 4 machines</td></tr><tr><td>9</td><td>A→B1→B5→C<br>A→B1→B2→B3→B4→C</td><td>The second half job has 6 machines</td></tr><tr><td>10</td><td>A→B1→B2→B3→B4→C<br>A→B1→B2→C</td><td>The number of machines is 6 → 4 → 6 → ...</td></tr><tr><td>11</td><td>A→B1→B2→B3→B4→C<br>A→B1→B5→C</td><td></td></tr><tr><td>12</td><td>A→B1→B2→C<br>A→B1→B2→B3→B4→C</td><td>The number of machines is 4 → 6 → 4 → ...</td></tr><tr><td>13</td><td>A→B1→B5→C<br>A→B1→B2→B3→B4→C</td><td></td></tr></tbody></table>

## 4.2 Results of Numerical Experiment

Average objective function value and the best value of 10 numerical experiments are shown in table 4. Calculation time is average value of 10 numerical experiments. The following were confirmed from Table 4.

(a) Objective function values (average) of proposed solution (GA or GA+DG) are improved by about 5 to 15% compared with that of previous research except pattern 1. They are within 5% of the lower limit of 10 cases in 13 cases. In many cases, the results of GA are somewhat better than GA + DG.

(b) Objective function values (best) of proposed solution (GA or GA+DG) are improved by about 8 to 18% compared with that of previous research except pattern 1. They are within 5% of the lower limit of 10 cases in 13 cases. In many cases, the results of GA are somewhat better than GA + DG.

(c) Calculation time of proposed solution (GA or GA + DG) is 10 to 16 times that of previous research.

In the case where the number of jobs is 20, there are 2⁸⁰ possible candidates for crane assignment, which is a very large optimization problem. Previous research could solve in a short time, but it was not able to sufficiently search solution space. As improving the above
problems using GA or GA with DG, the proposed method can derive better solutions. Calculation time is about 15 minutes. It was possible to apply to the shift plan that was planned once / 8 hours.

<table><caption>Table 4. Result of numerical experiment</caption><thead><tr><th rowspan="2">pattern</th><th colspan="3">objective function value (average)</th><th colspan="3">objective function value (best)</th><th rowspan="2">Lower limit</th></tr><tr><th>PR</th><th>GA</th><th>GA + DG</th><th>PR</th><th>GA</th><th>GA + DG</th></tr></thead><tbody><tr><td>1</td><td>2702.0</td><td>2712.7</td><td>2708.9</td><td>2700.0</td><td>2710.2</td><td>2707.0</td><td>2700.0</td></tr><tr><td>2</td><td>2987.3</td><td>2649.1</td><td>2649.0</td><td>2952.0</td><td>2646.8</td><td>2645.8</td><td>2600.0</td></tr><tr><td>3</td><td>3099.6</td><td>2666.8</td><td>2666.3</td><td>3030.0</td><td>2666.0</td><td>2665.5</td><td>2600.0</td></tr><tr><td>4</td><td>3010.1</td><td>2672.1</td><td>2671.4</td><td>2993.5</td><td>2670.0</td><td>2670.3</td><td>2658.0</td></tr><tr><td>5</td><td>3020.5</td><td>2679.0</td><td>2680.4</td><td>3019.3</td><td>2678.0</td><td>2678.0</td><td>2658.0</td></tr><tr><td>6</td><td>3007.5</td><td>2641.4</td><td>2645.3</td><td>3001.5</td><td>2638.7</td><td>2638.8</td><td>2610.0</td></tr><tr><td>7</td><td>3093.0</td><td>2630.3</td><td>2633.4</td><td>3080.8</td><td>2625.0</td><td>2625.0</td><td>2600.0</td></tr><tr><td>8</td><td>3393.4</td><td>3246.7</td><td>3051.3</td><td>3388.5</td><td>3052.3</td><td>3046.8</td><td>2610.0</td></tr><tr><td>9</td><td>3706.2</td><td>3322.3</td><td>3357.9</td><td>3694.5</td><td>3278.3</td><td>3281.0</td><td>2600.0</td></tr><tr><td>10</td><td>3207.3</td><td>2766.6</td><td>2769.0</td><td>3172.8</td><td>2765.5</td><td>2767.3</td><td>2610.0</td></tr><tr><td>11</td><td>3206.7</td><td>2645.3</td><td>2645.3</td><td>3175.0</td><td>2645.3</td><td>2645.3</td><td>2600.0</td></tr><tr><td>12</td><td>2892.4</td><td>2623.9</td><td>2627.3</td><td>2869.3</td><td>2622.2</td><td>2626.2</td><td>2610.0</td></tr><tr><td>13</td><td>2972.8</td><td>2600.0</td><td>2600.0</td><td>2887.8</td><td>2600.0</td><td>2600.0</td><td>2600.0</td></tr></tbody></table><table><thead><tr><th rowspan="2">pattern</th><th colspan="3">calculation time</th><th rowspan="2"></th></tr><tr><th>PR</th><th>GA</th><th>GA + DG</th></tr></thead><tbody><tr><td>1</td><td>47.5</td><td>766.1</td><td>660.4</td><td rowspan="13">PR : Previous research<br>GA : Genetic Algorithm<br>GA + DG : GA with Diversification Generator for initial solution generation<br>Lower Limit : Sum of operation time and crane movement time<br>(without machine conflict and crane interference)</td></tr><tr><td>2</td><td>56.3</td><td>794.9</td><td>805.2</td></tr><tr><td>3</td><td>57.6</td><td>772.8</td><td>781.2</td></tr><tr><td>4</td><td>51.6</td><td>711.0</td><td>713.2</td></tr><tr><td>5</td><td>51.9</td><td>698.2</td><td>697.2</td></tr><tr><td>6</td><td>54.7</td><td>750.9</td><td>737.5</td></tr><tr><td>7</td><td>54.9</td><td>704.7</td><td>711.0</td></tr><tr><td>8</td><td>56.5</td><td>864.4</td><td>877.2</td></tr><tr><td>9</td><td>57.4</td><td>792.5</td><td>791.2</td></tr><tr><td>10</td><td>56.1</td><td>766.3</td><td>760.6</td></tr><tr><td>11</td><td>56.5</td><td>626.9</td><td>633.9</td></tr><tr><td>12</td><td>54.6</td><td>717.6</td><td>751.4</td></tr><tr><td>13</td><td>56.0</td><td>585.2</td><td>596.1</td></tr></tbody></table>

# 5 Conclusions

A scheduling method for production process with crane conveyance using GA and GA with DG has been proposed. The proposed method has been successful in searching a wider range of solution space than that of previous research, and it is confirmed that objective function value improved by about 10%. In the future, we plan to develop a solution method that realizes solution concentration and diversification.

# References

1. Tanizaki T., Tamura T., Sakai H., Takahashi Y., Imai T. : A heuristic scheduling algorithm for steel making process with crane handling, Journal of the Operations Research Society of Japan, vol.49, no.3, pp.188-201(2006).

2. Tanizaki T., Katagiri T.: A scheduling algorithm for job-shop process with crane interference (in Japanese), Journal of Japan Association for Management Systems, vol.31, no.3, pp.319-324(2015).

3. Glover F.: A template for scatter search and path relinking, Artificial Evolution, Lecture Notes in Computer Science, vol.1363, pp.1-58(2005).