PaperlayerView exact revision on arXiv

Source-linked AI summary

Hybrid GA/MSDLO Approach to Solve a Greenfield Robotized Machine Tending Layout

Ramez Awad, Joshua Beck

arXiv:2609.37212v1cs.CE

TL;DR

Layout planning requires choosing production-resource arrangements in a vast continuous solution space, while engineers often rely on traditional patterns rather than exploring it systematically. The paper sequentially uses a GA as a coarse optimizer for initial resource placement, then MSDLO as a local planner to refine the layout. 7.28%: at an average simulation time of 13 seconds, there is a 95% chance of improving the Aggregated KPI by at least this amount.

  • Problem

    Layout planning requires choosing production-resource arrangements in a vast continuous solution space, while engineers often rely on traditional patterns rather than exploring it systematically.

    Source: §1 · p. 1

  • Method

    The paper sequentially uses a GA as a coarse optimizer for initial resource placement, then MSDLO as a local planner to refine the layout.

    Source: §1 · p. 1, §4 · pp. 3–4

  • Results

    7.28%: at an average simulation time of 13 seconds, there is a 95% chance of improving the Aggregated KPI by at least this amount.

    Source: §5 · p. 5

  • Takeaways & Limitations

    The authors support combining GA and MSDLO because the additional computation cost and time for MSDLO are negligible.

    Source: §6 · p. 5

    MSDLO encountered nine edge cases where usable area split into multiple sections because obstacle or boundary distance fell below 0.50 m; these were excluded from Table 4.

    Source: §5 · p. 5

Abstract

from arXiv · show

Meta-heuristics like genetic algorithms (GAs) effectively explore solution spaces but often yield suboptimal results and are sensitive to parameter tuning. In contrast, the mass-spring-damper layout optimization (MSDLO) method is fast and excels in locally optimizing resource arrangements, though its effectiveness depends on the initial resource placement. This paper first employs genetic algorithms to establish an optimal resource placement in a greenfield layout. We then apply MSDLO to fine-tune the positions and orientations of these resources. The results are presented and discussed, highlighting this approach's practicality in effectively addressing industry needs.

1. Introduction

The paper proposes a sequential hybrid that uses a genetic algorithm to find an advantageous initial resource placement and MSDLO to refine the layout. It addresses the difficulty of searching a vast continuous layout solution space and the limitations of traditional layout patterns.

Introduction

  • Factory layout decisions span a usually vast, continuous solution space, making effective optimization difficult.A good layout can improve workflow, reduce handling costs, and increase productivity, whereas a poor one can increase defects, waste, and costs.Source: §1 · p. 1
  • Production engineers often rely on traditional layout patterns rather than exploring the full solution space, motivating methods that search broadly within limited time.The paper argues such methods should compare alternatives or directly identify an optimal solution.Source: §1 · p. 1
  • In [8], MSDLO optimized Handling Cost better, while GA performed better on Area Savings; MSDLO performance also depended strongly on initial resource placement.The comparison used a Greenfield layout with n = 5 resources.Source: §1 · p. 1
  • The hybrid uses GA as a coarse optimizer for initial resource placement, then MSDLO as a local planner to refine the solution.It is evaluated on the same Greenfield layout problem used in.Source: §1 · p. 1

2. Related Work

Robotized production-line layout planning is a facility layout problem (FLP), which is NP-hard. Related work classifies FLP approaches as exact methods, heuristics, and meta-heuristics, with subsequent discussion concentrating on exact methods and meta-heuristics.

  • The FLP is NP-hard, and robotized production-line layout planning is a specific instance of this problem.Source: §2 · p. 1
  • Exact FLP methods seek a global optimum and include cutting plane, branch-and-bound, and dynamic programming algorithms [9].Source: §2 · p. 2
  • Heuristics iteratively allocate machines or departments or improve a given layout, while meta-heuristics provide general frameworks for developing heuristic optimization algorithms [13–16].Source: §2 · p. 2
  • Named meta-heuristics include genetic algorithms, simulated annealing, tabu search, ant colony optimization, and particle swarm optimization; hybrid approaches also combine meta-heuristics.Source: §2 · p. 2

Cutting Plane Algorithms (CPA) · Branch & Bound Algorithm (B&B)

The section describes CPA and B&B as exact approaches for facility-layout problems, but notes that their computational feasibility diminishes as problem size grows. CPA iteratively adds cuts, while B&B prunes subproblems using bounds.

Cutting Plane Algorithms (CPA)

Branch & Bound Algorithm (B&B)

  • B&B divides a problem into subproblems, calculates bounds, and prunes branches that cannot yield better solutions.Source: Branch & Bound Algorithm (B&B) · p. 2
  • Introduced by Land and Doig in 1960, B&B variants have been applied successfully to facility-layout problems.Source: Branch & Bound Algorithm (B&B) · p. 2
  • B&B is effective for instances up to 15 departments, and up to 36 when symmetry constraints reduce complexity; larger problems diminish computational feasibility, prompting heuristics for practical applications.Source: Branch & Bound Algorithm (B&B) · p. 2

Dynamic Programming (DP) · Genetic Algorithms (GAs) · Simulated Annealing (SA)

The section reviews three optimization approaches: DP decomposes problems into overlapping subproblems, GAs explore large solution spaces, and SA allows solutions to escape local optima.

Dynamic Programming (DP)

  • DP breaks complex problems into overlapping subproblems, stores intermediate results to avoid redundancy, then constructs the final solution.Source: Dynamic Programming (DP) · p. 2
  • DP suits dynamic facility layout problems [24], but extensive state spaces often require heuristics that may compromise global-optimality guarantees.Source: Dynamic Programming (DP) · p. 2

Genetic Algorithms (GAs)

Simulated Annealing (SA)

Tabu Search (TS) · Ant Colony Optimization (ACO)

Tabu search explores beyond local optima by preventing cycles and has been applied to facility layout problems, though it is parameter-sensitive. Ant colony optimization uses pheromone and heuristic information to explore paths and has been applied to layout problems, but faces parameter-sensitivity and scalability challenges.

Tabu Search (TS)

Ant Colony Optimization (ACO)

Particle Swarm Optimization (PSO)

Particle swarm optimization (PSO) uses swarm collaboration to explore solution spaces efficiently, but can struggle on larger instances; the broader methods overview favors meta-heuristics for complex layouts.

Particle Swarm Optimization (PSO)

3. Greenfield Layout Problem

The section defines a greenfield robotized machine-tending layout and the production workflow used to evaluate the hybrid approach. It specifies the planning horizon and the movement-cost and area-savings KPIs.

3. Greenfield Layout Problem

  • The evaluation layout is a 7200 mm × 7200 mm square, and the process uses two CNC machines, an inspection machine, a material rack, and a robot.The robot has an attached gripper and an electrical cabinet integrated at its base.Source: Figure 2 · p. 3, §3 · p. 3
  • Four handling processes move parts from the rack through CNC Machine 1, CNC Machine 2, and inspection, then return them to the rack as OK or NOK parts.The listed transfers are rack to CNC 1, CNC 1 to CNC 2, CNC 2 to inspection, and inspection to the rack.Source: §3 · p. 3
  • The planning horizon is 12 × 4 standard work weeks of 8-hour shifts, with a production volume of 68,640 units.Source: §3 · p. 3
  • Evaluation uses movement cost and area savings, combined in an aggregated KPI.Movement cost depends on handling counts, production volume, route distance, and a robot-movement cost factor of -1.25 €/km. Usable area must be at least 1.00 m², have 1.00 m of continuous shared boundary with the layout boundary, and be at least 0.50 m wide; its savings factor is +0.67 €/m4.Source: §3 · p. 3

4. The GA/MSDLO Hybrid Approach

The hybrid approach first solves the Greenfield layout with a genetic algorithm, then uses that placement to initialize MSDLO for refinement. MSDLO models resource relationships with spring-damper links and extracts the equilibrium layout and its KPIs.

4. The GA/MSDLO Hybrid Approach

  • The GA first solves the Greenfield layout, and its solution initializes the MSDLO pipeline.The MSDLO process then uses the modeled system’s equilibrium to determine resource positions and rotations.Source: §4 · pp. 3–4
  • The MSDLO model treats layout boundaries and obstacles as fixed collision bodies and places resources using the GA solution.Reachability links connect handling and non-handling resources; closeness links connect non-handling resources serviced consecutively by the same handling resource. Their spring constants depend on planning-horizon iterations, with closeness links additionally scaled to optimize rotational radius.Source: §4 · p. 4
  • At equilibrium, the method extracts resource positions and rotations and computes individual and aggregated KPIs.The modeled system is allowed to oscillate until it reaches equilibrium.Source: §4 · p. 4

5. Results and Discussion

The GA provides coarse greenfield layouts for MSDLO refinement, which can improve the Aggregated KPI while changing other layout KPIs and encountering edge cases.

Results

  • The stochastic GA was evaluated in 31 experiments, required 10 valid seeded layout solutions to converge, and averaged 5 min and 41 s of computation time per experiment.The GA’s best configuration was determined using design for experiments.Source: §5 · p. 4
  • Applying MSDLO to GA layouts decreased average Handling Cost by 11.06%, changed usable area by +0.17%, and reduced Area Savings by 15.15%.Table 3 presents changes to the original KPIs; its red-marked figures indicate KPI worsening.Source: §5 · p. 4, Table 3 · p. 5
  • In nine edge cases, usable area split into multiple sections when distance to an obstacle or boundary fell below 0.50 m; excluding them yielded the results in Table 4.The excluded experiments were #05, #08, #11, #14, #15, #16, #22, #23, and #27. Table 4 reports changes to original KPIs after filtering out edge cases.Source: §5 · p. 5, Table 4 · p. 5
  • A 13-second MSDLO simulation gave a 95% chance of improving the Aggregated KPI by at least 7.28%.When no improvement occurs, the additional cost is -0.001 € at 0,40 €/CPUh on an r6a.xlarge EC2 AWS Instance.Source: §5 · p. 5

6. Conclusions and Future Work

The results support combining GA and MSDLO: MSDLO’s additional computation cost and time are negligible, while it increases Aggregated KPI; future work will test the approach on a 20-resource Brownfield layout.

6. Conclusions and Future Work

  • With 95% confidence, MSDLO increases Aggregated KPI by at least 7.28% (= 150.12 €).Source: §6 · p. 5
  • The average Aggregated KPI increase is 20.05% (= 348.48 €), corresponding to a return on investment of 15,012,000%.Source: §6 · p. 5
  • The results support combining GA and MSDLO because MSDLO’s additional computation cost and time are negligible.Source: §6 · p. 5
  • Future work will apply MSDLO to a Brownfield layout with n=20 resources and compare it with GA and the GA/MSDLO hybrid approach.Source: §6 · p. 5
Loading 2609.37212v1…