Abstract
In this paper, a genetic algorithm for the robotic assembly line balancing problem (RALBP) is developed that supports multimodal stochastic processing times and multiple parallel-working robots per workstation. It has the objective to minimize the amount of workstations at a given production rate and probability limit for violating the cycle time (PL). The algorithm is evaluated on the BARTHOLD data set in a range of 1 % to 50 % for PL using an experimentally determined and a normal distribution for the task times. The increase of PL results in a shift of tasks from rear to front stations, because more tasks can be assigned to each station. The shift using normal distributed task times is stronger. This demonstrates the importance of realistic stochastic distribution assumptions. For practical applicability, more constraint types have to be included in the future.
You have full access to this open access chapter, Download conference paper PDF
Similar content being viewed by others
Keywords
1 Introduction
Robots play an important role in high-volume assembly lines, because they are reliable and repetitively accurate [1]. One widely used joining technology for robotic assembly lines is resistance spot welding (RSW) [2]. RSW welds car body sheets rapidly and forms a welding nugget in between the parts. Shape and size of the nugget affects the strength of the welded joint. To avoid excessive destructive tests to inspect weld quality and to react to disturbances during the welding process, feedback control systems (FCS) are used (see [3]). Since the weld strength cannot be measured directly, correlating electrical variables such as the dynamic resistance are commonly employed. The FCS determines the time of current termination based on experimentally determined values of the measurement variable, this leads to variation in the welding times.
Figure 1 shows the distribution of weld times for one weld point. The FCS is programmed to extend the weld time up to a preset prolongation limit [4]. This leads to a major weld time mode at −0.5 ms to 0.5 ms deviation from the predefined weld time of 450 ms, a center mode at about 7.5 ms to 8.5 ms and a closing mode at about 18.5 ms to 19.5 ms deviation. Similar distributions but different positions and heights of the modes can be found for other weld points. Gaussian Kernel-Density Estimation (KDE) is used to approximate a Gaussian Mixture Model (GMM). Its probability density function is shown in the figure.
In order to take into account the effects of processing time distributions on the robotic assembly line in early planning phases, this work introduces a computational approach to consider multimodal stochastic processing times in the robotic assembly line balancing problem (RALBP). In this approach, the planner specifies a probability limit for exceeding the cycle time in the stations, which is then respected by the algorithm. The probability of exceeding the cycle time is thus known in contrast to deterministic approaches and can be taken into consideration in subsequent planning steps so that, for example, the utilization of the stations can be optimized in a controlled manner. The proposed approach is inspired by the balancing of labour-intense assembly lines with normal distributed processing times, see ref. [5, 6].
2 State of Research
The RALBP, first described by Rubinovitz and Bukchin [7], is an extension to the popular assembly line balancing problem (ALBP). The goal is to assign a collection of tasks with their corresponding processing times and precedence relationships to workstations and to find a suitable robot for each station to optimize an objective function without violating resource and technological constraints.
As Chutima [8] shows, the RALBP is predominantly solved using meta-heuristics followed by exact algorithms and heuristics, because they show the highest effectiveness for practical sized problems.
Levitin et al. [9] present a genetic algorithm (GA) for the RALBP with the objective to minimize the cycle time at a given amount of serially arranged workstations (type II). The GA manipulates the order of the tasks, in which they are distributed to the stations. To avoid violation of their precedence constraints, the authors introduce a special reordering procedure to correct invalid solutions and a fragment reordering crossover as well as mutation operator. The actual assignment to stations and the selection of a robot is done in the decoding procedure.
3 Objective
The objective of this paper is to develop a method to address multimodal stochastic processing times that result from RSW process control using RALBP. In the context of car body construction, multiple robots per workstation are working on the same part in parallel. Multimodal processing time distributions have to be experimentally determined. The objective of the method is to minimize the amount of workstations. In addition, the influence of the distribution assumptions that are chosen to represent the task time variation will be investigated.
4 Genetic Algorithm
The proposed approach is based on the GA developed by Levitin et al. [9] and introduces a new decoding procedure. The assumptions for the RALBP made by Rubinovitz and Bukchin [7] are modified as follows:
-
1.
The precedence relationships for all tasks are known and cannot be changed. They are represented by a precedence matrix \(\boldsymbol{P}_{T\times T}\), where \(p_{ij}=1\) means, task i must be a predecessor of task j.
-
2.
The duration of a task is distributed and approximated by variations of the probability density function in Fig. 1. Tasks cannot be subdivided.
-
3.
The only limitations for assigning tasks to stations are the probability limit PL for violating the given cycle time and the precedence constraints in \(\boldsymbol{P}\).
-
4.
K robots are assigned to each station. There are no limitations for assigning a task to a robot other than the cycle time violation probability limit.
-
5.
Loading, unloading and material handling times as well as setup and tool changes are neglected or are included in the task times.
-
6.
The line is balanced for a single product.
-
7.
There are no limitations for the availability of robots.
The notation used in this paper is described in Table 1.
4.1 Solution Representation
This paper uses a partition-oriented encoding scheme following Kim et al. [10]:
-
Vector \(\boldsymbol{v}\): Contains a permutation of the task elements. This vector is generated by the genetic algorithm.
-
Vector \(\boldsymbol{s}\): Contains pointers to elements in \(\boldsymbol{v}\) to partition it into stations.
-
Matrix \(\boldsymbol{R}\): \(K\times T\) binary matrix which contains the assignments of tasks to robots (if task i is assigned to robot k, \(r_{ki}\) is 1, otherwise 0).
4.2 Steps of the GA
The steps of the algorithm can be summarized as follows, for further details the reader is referred to [9]: i) generate a random valid initial population ii) decode and sort the population by their fitness using the decoding procedure in Sect. 4.3 iii) create offspring of some of the best chromosomes and replace the worst with them iv) randomly mutate some of the chromosomes v) jump back to step ii) for G times or stop after not improving for H times.
4.3 Decoding Procedure for the RALBP
The decoding procedure populates vector \(\boldsymbol{s}\) and matrix \(\boldsymbol{R}\), i.e. assign the tasks to workstations and robots. It considers a probability limit PL for violating the cycle time in each robot. The algorithm consists of the following steps:
- D1:
-
Set variables \(m=1\) and \(n=1\).
- D2:
-
Open a new station by adding the index of the current task m to station vector \(\boldsymbol{s}\). Set \(n=m\).
- D3:
-
Select element \(v\left( m\right) \) if \(m\le |v|\), otherwise stop the algorithm.
- D4:
-
Check, if the selected task element \(v\left( m\right) \) fits into the station:
- D4.1:
-
If \(n=m\), set \(r_{1m}=1\) and increase m to \(m+1\). Jump to step D3.
- D4.2:
-
Sort the robots by their descending free capacity \(\boldsymbol{cp}\), see Eq. 1, which leads to a permutation \(d = \left( d\left( 1\right) ,\dots , d\left( K\right) \right) \).
$$\begin{aligned} cp_k = C - \sum _{a=n}^{m-1}r_{ka}\cdot e_{v\left( a\right) },\, k\in \left( 1, \dots , K\right) \end{aligned}$$(1) - D4.3:
-
For each robot \(d\left( l\right) \) in \(l\in \left( 1,\dots , K\right) \), do a monte carlo simulation to check if the probability to violate the cycle time of the tasks in the robot including the random numbers \(X_{v\left( m\right) }\) of the currently selected task \(v\left( m\right) \) exceeds the given limit PL. If it does not, the current task fits on the robot. Break the loop and jump to step D4.4. If \(l=K\) and no robot has been found to be able to complete task \(v\left( m\right) \), jump to step D2.
- D4.4:
-
Set \(r_{d\left( l\right) m}=1\) and increase m to \(m+1\). Jump to step D3.
5 Results
The presented algorithm is evaluated on the basis of practical problems from car body construction. The BARTHOLD problem statement from the data sets by Scholl [11] is chosen because it matches the F-Ratio (0.7 to 0.8) and WEST-Ratio (15 to 25) (see Dar-El [12]), which we have found to be typical for car body construction problems. The cycle times and processing times of the problem are multiplied by 0.1 s, which results in cycle times of 56.4 s, 62.6 s, 70.5 s, and 80.5 s. It consists of 149 tasks with processing times within a range of 0.3 s to 38.3 s. For each test case, the probability limit of cycle time violations PL is gradually increased from 1% to 50%, the decoding procedure assigns the tasks in such a way that PL is not exceeded in the stations. A normal distribution (\(\mathcal {N}\)) is derived from the expectation value (454.98 ms) and standard deviation (6.67 ms) of the weld time distribution in Fig. 1 and compared to the approximated GMM. The BARTHOLD problem contains deterministic task times \(t_i\). The random variables \(X_i\) are linearly scaled so that their expectation values match \(t_i\).
The gradually increase of the probability limit PL allows to assign more tasks to each station, resulting in a shift from rear to front stations and an increasing free capacity in the last workstation. At a certain probability limit, the shift is sufficient to save one station. The position of this limit is essentially determined by the problem and the process time distribution of the tasks. The boxplot in Fig. 2 shows the free capacity of the last station \(\mathcal {S}\) for all test cases, where the boxes contain the values of \(\mathcal {S}\) for PL in a range from 1 % to 50%.
In all scenarios except at a cycle time of 70.5 s, the range of \(\mathcal {S}\) is wider with the normal distribution. The interquartile range is between 12 % (\(C={80.5}\,s\)) and 56 % (\(C={62.6}\,s\)) larger than with GMM. Normal distributed processing times therefore save more capacity.
6 Conclusion and Future Research
A genetic algorithm considering stochastic processing times and multiple parallel-working robots per workstation for the RALBP was presented. The algorithm was evaluated on the basis of practical test problems using an approximated GMM and a normal distribution to represent stochastic task times. The results show that with a normal distribution more capacity in the last station could be saved by increasing the probability limit for violating the cycle time, which can lead to savings of workstations at lower risk. It can be concluded from this that the choice of distribution and the underlying problem play a decisive role. Quality of the input data as well as appropriate and process adequate distribution assumptions strongly affect the results. Therefore inaccuracies may lead to false assumptions and therefore to lasting effects on following operations.
For practical application of the proposed approach, some features are missing and may be subject to future research: i) Support for in-station constraints, which result from geographical positions of the tasks and depend on the actual set of tasks being assigned to the station and ii) a procedure to preserve precedence constraints in the stations and on the parallel-working robots.
References
Sule, D.R.: Manufacturing Facilities: Location, Planning and Design, 2nd edn. PWS Publishing Company, Singapore (1998)
Stiebel, A., et al.: Monitoring and control of spot weld operations. SAE Techn. Paper Ser. (1986)
Podržaj, P., et al.: Overview of resistance spot welding control. Sci. Technol. Weld. Join. (2008)
Bosch Rexroth AG. Rexroth PSI 6xxx - UI regulation and monitoring
Aǧpak, K., Gökçen, H.:. A chance-constrained approach to stochastic line balancing problem. Eur. J. Oper. Res. (2007)
Lolli, F. et al.: Stochastic assembly line balancing with learning effects. IFAC-PapersOnLine (2017)
Rubinovitz, J., Bukchin, J.: Design and balancing of robotic assembly lines. In: Proceedings of the Fourth World Conference on Robotics Research (1991)
Chutima, P.: A comprehensive review of robotic assembly line balancing problem. J. Intell. Manufact. (2020)
Levitin, G., Rubinovitz, J., Shnits, B.: A genetic algorithm for robotic assembly line balancing. Eur. J. Oper. Res. 168(3), 811–825 (2006)
Kim, Y.K., Kim, Y.J., Kim, Y.: Genetic algorithms for assembly line balancing with various objectives. Comput. Industr. Eng. 30(3), 397–409 (1996)
Scholl, A.: Data of assembly line balancing problems. In: Schriften zur Quantitativen Betriebswirtschaftslehre Technische Hochschule Darmstadt (1993)
Dar-El, E.M.: MALB-a heuristic technique for balancing large single- model assembly lines. AIIE Trans. 5(4), 343–356 (1973)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
Copyright information
© 2023 The Author(s)
About this paper
Cite this paper
Stade, D., Manns, M. (2023). Robotic Assembly Line Balancing with Multimodal Stochastic Processing Times. In: Kiefl, N., Wulle, F., Ackermann, C., Holder, D. (eds) Advances in Automotive Production Technology – Towards Software-Defined Manufacturing and Resilient Supply Chains. SCAP 2022. ARENA2036. Springer, Cham. https://doi.org/10.1007/978-3-031-27933-1_8
Download citation
DOI: https://doi.org/10.1007/978-3-031-27933-1_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-27932-4
Online ISBN: 978-3-031-27933-1
eBook Packages: EngineeringEngineering (R0)