# Reduction of Computational Load in Robust Facility Layout Planning Considering Temporal Production Efficiency

Eiji Morinaga, Komei Iwasaki, Hidefumi Wakamatsu, Eiji Arai

► To cite this version:

Eiji Morinaga, Komei Iwasaki, Hidefumi Wakamatsu, Eiji Arai. Reduction of Computational Load in Robust Facility Layout Planning Considering Temporal Production Efficiency. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2019, Austin, TX, United States. pp.189-195, 10.1007/978-3-030-29996-5_22. hal-02460474

HAL Id: hal-02460474

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

Submitted on 30 Jan 2020

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
Reduction of Computational Load in Robust
Facility Layout Planning Considering Temporal
Production Efficiency

Eiji Morinaga, Komei Iwasaki, Hidefumi Wakamatsu, Eiji Arai

Graduate School of Engineering, Osaka University, Japan
{morinaga,wakamatu,arai}@mapse.eng.osaka-u.ac.jp

**Abstract.** Most researches of facility layout planning (FLP) have aimed at finding a layout with which evaluation indices based on distance are minimized. Because temporal efficiency has not been considered in this stage but in post stages, the resultant temporal efficiency may not be optimal enough. The authors have developed an FLP method considering temporal efficiency, in which facility layout is optimized using genetic algorithm (GA), and have enhanced it so that robustness against changes in production environment can be taken into consideration. However, the enhanced method involves a large computational load, since numerous production scenarios need to be considered. This paper provides a method for reducing computational load in the robust FLP based on the sampling approach where each layout plan is evaluated with only a limited number of production scenarios in the optimization process by GA. Numerical experiments showed the potential of the proposed method to efficient robust FLP considering temporal efficiency.

# 1 Introduction

Facility layout planning (FLP) is an important stage of manufacturing system design and has been actively discussed for a long time [1,2]. In this research field, evaluation indices based on distance such as total travel distance and total material handling cost have been mainly considered, and single/multi objective optimization based on those indices have been performed by mathematical optimization (quadratic assignment problem [3] and mixed integer programming [4]) or metaheuristics (simulated annealing [5], genetic algorithm [6], ant-colony optimization [7], etc.). Those indices do not include temporal efficiency, which is considered in detail in the stage of production management performed after the manufacturing system design. This may result in unsuitable optimization from the point of view of the whole system.

Some research groups have discussed FLP considering temporal efficiency [8, 9]. But, they dealt with allocation of facilities to pregiven sites, and did not consider detailed position and size of facilities. We proposed an integrated method of FLP and production scheduling in which the integrated planning problem was formulated as a mixed integer programming which aims to minimize makespan
and includes detailed position and size of facilities as decision variables [10]. We also proposed an FLP method considering detailed transportation routes and loading/unloading points of facilities in addition to temporal efficiency [11]. Due to difficulty in describing the shortest transportation route by linear equations/inequalities mathematically, genetic algorithm (GA) was used for optimization of facility layout plan in which finding the optimal routes and calculating makespan based on the routes were performed for each layout plan.

Those methods aim at finding the optimal layout plan for a fixed production scenario. However, production conditions change dynamically in actual manufacturing, and the layout plan is no longer optimal after the production conditions changed. An approach for coping with this problem is to adopt the concept of robustness against the changes [12] and robust FLP has been discussed based on enumerative method [13], branch-and-bound method [14], and so on. The integrated FLP method was also enhanced from this point of view [15]. In the enhanced method, sum of product of the probability of production scenario and makespan achieved under the scenario was defined as an evaluation index for taking robustness into consideration, and optimization based on this index was performed using GA. This method, however, involves a lot of computational load, since production scheduling for calculating makespan needs to be performed for every possible production scenario. This paper describes improvement of this robust FLP method for reducing computational load.

## 2 Outline of robust FLP Considering Temporal Efficiency

This section provides an outline of the robust FLP method considering temporal efficiency [15]. This method is intended to be applied to job-shop production of *J* kinds of jobs with *F* facilities. The *j*∈{1,..., *J*})-th kind of job needs *O*<sub>j</sub> operations. Operation *o* ∈ {1,..., *O*<sub>j</sub>} of the *j*-th kind of job is processed by facility *f*<sub>*j*o</sub> ∈ {1,..., *F*}. Width and depth of facility *f* are *w*<sub>*f*</sub> and *d*<sub>*f*</sub>. Each facility has loading and unloading points. Those facilities are located in the production area which has a rectangular shape of width *W* and depth *D*.

Because of difficulty in describing the shortest transportation route by linear equations/inequalities mathematically, optimization of facility layout plan is carried out iteratively by GA and routing and calculation of temporal efficiency are performed for each layout plan (Fig. 1). For representing a layout plan as an individual in GA, the production area is divided up into a grid of squares with sides unit length and each cell has its ID number. A layout plan is represented as an individual by defining the structure of chromosome as *F* pairs of two numbers, where the second number of the *f*-th pair is the number of clockwise rotation by 90 degrees, and the first number is the ID number of the cell on which the upper left part of facility *f* (Fig. 2).

For a layout plan represented by this method, the shortest route between any two facilities is obtained by using Dijkstra's method and required time for transportation between the facilities is calculated by dividing the length of the route by the velocity of an automated guided vehicle. Production scheduling for
<figure><img src="image_2.png" /><figcaption>Fig. 1. Flowchart of robust FLP considering temporal efficiency.</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>Fig. 2. Chromosome representation of a layout plan [11, 15].</figcaption></figure>

the layout plan is then performed for every production scenario. This process has to be performed many times and therefore should be completed in a short time. For this reason, the simulation approach using a dispatching rule is taken for this process. After performing this process for all the scenarios, the layout plan is then evaluated by the following index:

$$ \Sigma_{s=1}^{S} M_s (\Pi_{j=1}^{J} p_j^s) \qquad (1) $$

where $M_s$ is the makespan of the schedule generated with the s-th one in the given set of production scenarios S the cardinality of which is S, and $p_j^s$ is the probability of the number of production of the j-th kind of job specified by the s-th scenario, which is defined as a combination of the number of production.

## 3 Improvement for Reducing Computational Load

As for the robust FLP method stated in Section 2, the total number S of production scenarios to be considered increases exponentially as the number of the kind of jobs J increases, and therefore reduction of computational load in the optimization process is crucial. In the research field of stochastic programming, the sampling approach has been taken advantage of for reducing computational load in optimization, where only a limited number of scenarios are utilized for evaluation of an individual [16]. Because no theoretical validation had not been provided for this approach, Tokoro [17] proposed a new GA in which individuals are evaluated based on mean fitness in some scenarios sampled at random and selection is performed using Welch's test, and reported the method was effective to obtain high quality solutions for stochastic facility location problems in a very
short computation time. It is expected that this GA is also effective to reduce the computational load in the robust FLP method.

Figure 3 shows the improved robust FLP method using the new GA. As stated in the previous section, production scenario is defined as a combination of the number of production of jobs in this research. In this improved method, it is assumed that the number of production of each kind of job follows a normal distribution defined in a pre-given range, and a pre-fixed number (denoted by $\hat{S}$) of production scenarios are sampled by determining the number of production with a normal random number in the range.

Production scheduling is then performed for each of the selected scenarios, and the mean of makespans among the scenarios $\overline{M}_g^n$ is calculated as follows.

$$ \overline{M}_g^n := \Sigma_{s \in \hat{S}_g} M_s^n / \hat{S}, \qquad (2) $$

where $n$ and $g$ are the ordinal number of the individual (i.e. layout plan) and the current generation, and $\hat{S}_g$ stand for the set of the selected scenarios. Then, the history data of each individual is updated as follows:

$$ g_n = g_n + 1 \qquad (3) $$

$$ \tilde{M}_n = \tilde{M}_n + (\overline{M}_g^n - \tilde{M}_n)/g_n \qquad (4) $$

$$ \sigma_n^2 = (g_n - 2)(\overline{M}_g^n - \tilde{M}_n)^2/g_n + (g_n - 2)\sigma_n^2/(g_n - 1), \qquad (5) $$

where $g_n$ represents how many generations the $n$-th individual has survived, and $\tilde{M}_n$ and $\sigma_n$ stand for the mean and the standard deviation of the index (2) among the generations.

Because the new evaluation index (2) is calculated with the makespans obtained with a limited number of scenarios, a large value of the index does not always mean that the individual is bad and selection based on the index value of the current generation may be inappropriate. For this reason, Welch's test is utilized for determining whether an individual should be eliminated from the population. In this method, the statistic $t_n$ defined by

$$ t_n := (\tilde{M}_{n^*} - \tilde{M}_n)/\sqrt{\sigma_{n^*}^2/g_{n^*} + \sigma_n^2/g_n} \qquad (6) $$

is calculated for each individual and choose the set of individual $D := \{n | t_n > t_\alpha(\mu)\}$, where $n^*$ is the ordinal number of the best individual in the current generation, $t_\alpha(\mu)$ stands for the t-ratio with $\mu$ degrees of freedom and the confidence interval of $\alpha\%$ confidence level and $\mu$ is the integer which is closest to

$$ \mu' := (\sigma_{n^*}^2/g_{n^*} + \sigma_n^2/g_n)^2 / \left\{ \frac{(\sigma_{n^*}^2/g_{n^*})^2}{g_{n^*} - 1} + \frac{(\sigma_n^2/g_n)^2}{g_n - 1} \right\}. \qquad (7) $$

A pre-given number of the individuals in this set $D$ are eliminated from the current population, since they can be regarded as significantly-bad individuals. The same number of new individuals are then generated by performing crossover to a pair of individuals which does not belong to $D$, and all the other individuals are left to the next generation.
<figure><img src="image_4.png" /><figcaption>**Fig. 3.** Flowchart of the improved robust FLP method.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>**Fig. 4.** Result of Case 1.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>**Fig. 5.** Result of Case 2.</figcaption></figure>

# 4 Numerical Experiments

Due to page limitation, this section briefly describes results of numerical experiments using an example of $F = 7$, $J = 5$ and $O_j = 7$. The range of the number of production of each kind of job was given as {4,5,6} (Case 1) and {2,3,4,5,6,7,8} (Case 2). In Case 1, as shown in Fig. 4, the index value of the layout plan obtained by the proposed method was worse than that of the conventional robust FLP, though computation time was reduced drastically to about 10%. It was also worse than the value of the layout plan obtained considering only the standard scenario. Figure 5 shows the result of Case 2, where it was impossible to obtain a layout plan by the conventional method due to its computational load ($S = 16807$). The index value obtained by the proposed method was better than at least that of the layout obtained considering only the standard scenario. Although it is necessary to perform optimization based on the conventional method and compare the index value of the result to this value of the proposed method in a future work, it is expected this result implies a potential of the proposed method to efficient robust FLP considering temporal efficiency.

# 5 Summary

This paper has described reduction of computational load of the robust FLP method considering temporal production efficiency. The GA based on the sampling approach and a statistical theory was applied to the robust FLP method. Numerical experiments implied the proposed method has a potential to efficient robust FLP considering temporal efficiency. Further numerical studies with much narrower and broader range of scenarios will be performed in a future work.
References

1. Drira, A., Pierreval, H., Hajri-Gabouj, S.: Facility layout problems: a survey. Annual Reviews in Control, **31**(2), 255-267 (2007)

2. Hosseini-Nasab, H., Fereidouni, S., Ghomi, S.M.T.F., Fakhrzad, M.B.: Classification of facility layout problems: a review study. International Journal of Advanced Manufacturing Technology, **94**(1-4), 957-977 (2018)

3. Lawler, E.L.: The quadratic assignment problem. Management Science, **9**(4), 586-599 (1963)

4. Sherali, H.D., Fraticelli, B.M.P., Meller, R.D.: Enhanced model formulations for optimal facility layout. Operations Research, **51**(4), 629-644 (2003)

5. Chwif, L., Barretto, M.R.P., Moscato, L.A.: A solution to the facility layout problem using simulated annealing. Computers in Industry, **36**(1-2), 125-132 (1998)

6. Gonçalves, J.F., Resende, M.G.C.: A biased random-key genetic algorithm for the unequal area facility layout problem. European Journal of Operational Research, **246**(1), 86-107 (2015)

7. Pour, H.D., Nosraty, M.: Solving the facility and layout and location problem by ant-colony optimization-meta heuristic. International Journal of Production Research, **44**(23), 5187-5196 (2006)

8. Fujihara, Y., Osaki, H.: A facility layout method linked to production scheduling. Transactions of the Japan Society of Mechanical Engineers Series C, **63**(605), 297-303 (1997) (In Japanese)

9. Hino, R., Moriwaki, T.: Resource reallocation based on production scheduling (1st report). Journal of the Japan Society for Precision Engineering, **69**(5), 655-659 (2003) (In Japanese)

10. Morinaga, E., Shintome, Y., Wakamatsu, H., Arai, E.: Facility layout planning with continuous representation considering temporal efficiency. Transactions of the Institute of Systems, Control and Information Engineers, **29**(9), 408-413 (2016)

11. Morinaga, E., Iwasaki, K., Wakamatsu, H., Arai, E.: A facility layout planning method considering routing and temporal efficiency. In: 2016 International Symposium on Flexible Automation, pp. 193-198. IEEE, (2016)

12. Moslemipour, G., Lee, T.S., Rilling, D.: A review of intelligent approaches for designing dynamic and robust layouts in flexible manufacturing systems. International Journal of Advanced Manufacturing Technology, **60**(1-4), 11-27 (2012)

13. Rosenblatt, M.J., Lee, H.L.: A robustness approach to facilities design. International Journal of Production Research, **25**(4), 479-486 (1987)

14. Kouvelis, P., Kurawarwala, A.A., Gutierrez, G.J.: Algorithms for robust single and multiple period layout planning for manufacturing systems. European Journal of Operational Research, **63**(2), 287-303 (1992)

15. Morinaga, E., Iwasaki, K., Wakamatsu, H., Arai, E.: A robust facility layout planning method considering temporal efficiency. In: Lödding, H., Riedel, R., Thoben, KD., von Cieminski, G., Kiritsis, D. (eds.) Advances in Production Management Systems. The Path to Intelligent, Collaborative and Sustainable Manufacturing. APMS 2017. IFIP Advances in Information and Communication Technology, vol. 514, pp. 168-175. Springer, Cham (2017)

16. Yoshitomi, Y., Ikenoue, H., Takeba, T., Tomita, S.: Genetic Algorithm in Uncertain Environments for Solving Stochastic Programming Problem. Journal of the Operations Research Society of Japan, **43**(2), 266-290 (2000)

17. Tokoro, K.: A statistical selection mechanism of GA for stochastic programming problems. Transactions on Mathematical Modeling and its Application, **43**(SIG10), 157-164 (2002)