Solving Multi-Objective Paired Single Row Facility Layout Problem Using Hybrid Variable Neighborhood Search

Authors

  • Meilinda Fitriani Nur Maghfiroh Universitas Islam Indonesia

DOI:

https://doi.org/10.9744/jti.23.2.171-182

Keywords:

Adjacency, material handler, multi-objectives, paired single-row layout problem, variable neighborhood search

Abstract

The footwear industry is distinguished by its manual assembly line and a high proportion of shared workstation configuration. This study focuses on a subset of the single row facility layout problem known as the paired single row facility layout problem. As one of type of single-row facility layout, the paired single row facility layout problem cannot be solved quickly. Further, different objectives also need to be considered in the decision-making process. Therefore, multi-objective approaches are proposed to minimize the penalty of material handler usage while maximizing the adjacency function based on each workstation's closeness rating. A Single Row Facility Layout is an NP-hard problem; this problem also belongs to the NP-hard problem class. As a result, we propose a hybrid method combining variable neighborhood search (VNS) and genetic algorithm (GA) to solve the problem of obtaining the optimal configuration of a multi-objective paired single-row assembly line. A heuristic approach was used to create the schematic representation solution. To obtain the neighborhood solutions, a hybrid VNSGA was used. The schematic representation solution employs crossover and variable neighborhood descent. Using the concept of VNS, the neighborhood was changed in each generation.

Author Biography

Meilinda Fitriani Nur Maghfiroh, Universitas Islam Indonesia

Faculty of Industrial Technology, Industrial Engineering Department, Universitas Islam Indonesia, Jl. Kaliurang Km 14.5, Slemat Yogyakarta 55584.

References

Ou-Yang C., and Utamima, A., Hybrid Estimation of Distribution Algorithm for Solving Single Row Facility Layout Problem, Computers & Industrial Engineering, 66, 2013, pp. 95-103.

Amaral, A.R.S., A New Lower Bound for the Single Row Facility Layout Problem, Discrete Applied Mathematics, 157, 2009, pp. 183-190.

Ariafar, S., and Ismail, N., An Improved Algorithm for Layout Design in Cellular Manu-facturing Systems, Journal of Manufacturing Systems, 28, 2009, pp. 132-139.

Lee, Y.H., and Lee, M.H., A Shape-based Block Layout Approach to Facility Layout Problems using Hybrid Genetic Algorithm, Computers & Industrial Engineering, 42, 2002, pp. 237–248.

Kusiak, A, and Heragu, S.S., The Facility Layout Problem, European Journal of Operational Research, 29, 1987, pp. 229-251.

Dimopoulos, C., Zalzala, A.M.S., Recent Developments in Evolutionary Computation for Manufacturing Optimization: Problems, Solu-tions, and Comparisons, Evolutionary Compu-tation, IEEE Transactions on Evolutionary Computation, 4, 2000, pp. 93-113.

Drira, A., Pierreval, H., Hajri-Gabouj, S., Facility Layout Problems: A Survey, Annual Reviews in Control, 31, 2007, pp. 255-267.

Braglia, M., Optimisation of a Simulated-Annealing-based Heuristic for Single Row Machine Layout Problem by Genetic Algorithm, International Transactions in Operational Research, 3, 1996, pp. 37-49.

Djellab, H., and Gourgand, M., A New Heuristic Procedure for the Single-row Facility Layout Problem, International Journal of Computer Integrated Manufacturing, 14, 2001, pp. 270-280.

Ficko, M., Brezocnik, M., and Balic, J., Designing the Layout of Single- and Multiple-rows Flexible Manufacturing System by Genetic Algorithms, Journal of Materials Processing Technology, 157–158, 2004, pp. 150-158.

Picard, J.C., On the One Dimensional Space Allocation Problem, Operations Research, 29, 1981, 150-173.

Heragu, S.S., and Kusiak, A., Efficient Models for the Facility Layout Problem, European Journal of Operational Research, 53, 1991, pp. 1-13.

Solimanpur, M., and Jafari, A., Optimal Solution for the Two-Dimensional Facility Layout Problem Using a Branch-And-Bound Algorithm, Com¬pu¬ter and Industrial Engineering, 55, 2008, pp. 606-619.

Samarghandi, H., and Eshghi, K., An Efficient Tabu Algorithm for the Single Row Facility Layout Problem, European Journal of Operational Research. 205, 2010, pp. 98-105.

Kar Yan T., A Simulated Annealing Algorithm for Allocating Space to Manufacturing Cells, Interna-tional Journal of Production Research, 30, 1992, pp. 63-87.

Mir, M., and Imam, M.H., A Hybrid Optimization Approach for Layout Design of Unequal-Area Facilities, Computers & Industrial Engineering, 39, 2001, pp. 49-63.

Kar Yan, T., Genetic Algorithms, Function Optimization, and Facility Layout Design, European Journal of Operational Research, 63, 1992, pp. 322-346.

Al-Hakim, L., On Solving Facility Layout Problems Using Genetic Algorithms, International Journal of Production Research. 38, 2000, pp. 2573-2582.

Datta, D., Amaral, A.R.S., and Figueira, J.R., Single Row Facility Layout Problem Using a Permutation-Based Genetic Algorithm, European Journal of Operational Research, 213, 2011, pp. 388-394.

Samarghandi, H., Taabayan, P., and Jahantigh, F.F., A Particle Swarm Optimization for the Single Row Facility Layout Problem, Computers & Industrial Engineering, 58, 2010, pp. 529-534.

Kothari, R., and Ghosh, D., Insertion Based Lin–Kernighan Heuristic for Single Row Facility Layout, Computers & Operations Research, 40, 2013, pp. 129-136.

Hani, Y., Amodeo, L., Yalaoui, F., and Chen, H., Ant Colony Optimization for Solving an Industrial Layout Problem, European Journal of Operational Research, 183, 2007, pp. 633-642.

Singh, S.P. and Singh, V. K., Three Level AHP-Based Heuristic Approach for Multi-Objective Facility Layout Problem, International Journal of Production Research, 49(4), 2010, pp. 1105-1125.

Matai, R., Singh, S.P., Mittal, M.L., Modified Simulated Annealing Based Approach for Multi Objective Facility Layout Problem, International Journal of Production Research, 51 (14), 2013, pp. 4273-4288.

Matai, R., Solving Multi Objective Facility Layout Problem by Modified Simulated Annealing, Applied Mathematics and Computation, 261, 2015, pp. 302-311.

Tayal, A., Singh, S.P., Integrated SA-DEA-TOPSIS-Based Solution Approach for Multi Objective Stochastic Dynamic Facility Layout Problem, International Journal of Business and Systems Research, 11(1-2), 2017, pp. 82-100.

Azevedo, M.M., Crispim, J.A., and Pinho de Sousa, J., A Dynamic Multi-Objective Approach for the Reconfigurable Multi-Facility Layout Problem, Journal of Manufacturing Systems, 42, 2017, pp. 140-152.

Hansen, P., and Mladenović, N., Variable Neighborhood Search for the P-Median, Location Science, 5, 1997, pp. 207-226.

Rousseau, L.M., Gendreau, M., and Pesant, G., Using Constraint-Based Operators to Solve the Vehicle Routing Problem with Time Windows, Journal of Heuristics, 8, 2002, pp. 43-58.

Maghfiroh, M.F.N, and Yu, V.F., A Variable Neighborhood Search with Path-Relinking for the Capacitated Location Routing Problem, Journal of Industrial and Production Engineering, 2014, pp. 1-14

Ripon, K.S.N., Glete, K., Khan, K.N., Hovin, M., and Torresen, J., Adaptive Variable Neighbor-hood Search for Solving Multi-Objective Facility Layout Problems with Unequal Area Facilities, Swarm and Evolutionary Computation, 8, 2013, pp. 1-12.

Kochhar, J.S., and Heragu, S.S., Facility Layout Design in A Changing Environment, Interna-tional Journal of Production Research, 37, 1999, pp. 2429-2446.

Sadrzadeh, A., A Genetic Algorithm with the Heuristic Procedure to Solve the Multi-Line Layout Problem, Computers & Industrial Engineering, 62, 2012, pp. 1055-1064.

Parwananta, H., Maghfiroh, M.F.N., and Yu, V.F., Genetic Algorithm for Solving Paired Single Row Facility Layout Problem, in: H.T.L. V. Kachitvichyanukul, and R. Pitakaso Eds (Ed.) Asia Pacific Industrial Engineering & Management Systems Conference 2012 Asian Institute of Technology, Phuket, Thailand, 2012, pp. 151-159.

Parwananta, H., Maghfiroh, M.F.N., and Yu, V.F., Two-Phase Genetic Algorithm for Solving The Paired Single Row Facility Layout Problem, Journal Industrial Engineering & Management Systems, 12, 2013, pp. 181-189.

Muther, R.., Systematic Layout Planning, 1973. Boston, CBI Publishing Company, Inc.

Chen, G.Y., Multi-objective Evaluation of Dynamic Facility Layout Using Ant Colony Optimization, The University of Texas at Arlington. ProQuest Dissertations Publishing, 2007.

Duda, J., A Hybrid Genetic Algorithm and Variable Neighborhood Search for Multi-Family Capacitated Lot-Sizing Problem, Electronic Notes in Discrete Mathematics, 58, 2017, pp. 103-110

Schermer, D., Moeini, M., and Wendt, O., A Hybrid VNS/Tabu Search Algorithm for Solving the Vehicle Routing Problem with Drones and En Route Operations, Computers & Operations Research, 109, 2019, pp. 134-158

Pham, D. T. and Binh Huynh, T. T., An Effective Combination of Genetic Algorithms and the Variable Neighborhood Search for Solving Travelling Salesman Problem, 2015 Conference on Technologies and Applications of Artificial Intelligence (TAAI), 2015, pp. 142-149.

Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T. A Fast and Elitist Multi-Objective Genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 2002, 6, 182–197

Solimanpur, M., Vrat, P., and Shanker, R., An Ant Algorithm for the Single Row Layout Problem in Flexible Manufacturing Systems, Computers & Operations Research, 32, 2005, pp. 583–598.

Anjos, M.F., and Vannelli, A., Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes, INFORMS Journal on Computing, 20, 2008, pp. 611–617.

Downloads

Published

2021-12-21

Issue

Section

Articles