A Hybrid Metaheuristic based on the Firefly and Bat Algorithms to Solve the Alternative Subgraphs Assembly Line Balancing Problem

doi:10.21203/rs.3.rs-2740227/v1

Download PDF

Research Article

A Hybrid Metaheuristic based on the Firefly and Bat Algorithms to Solve the Alternative Subgraphs Assembly Line Balancing Problem

https://doi.org/10.21203/rs.3.rs-2740227/v1

This work is licensed under a CC BY 4.0 License

Version 1

posted

You are reading this latest preprint version

Assembly line balancing problem is the process of assigning a set of tasks to a group of stations, considering the precedence relations between tasks. Precedence relations are commonly definite, however, tasks may have alternative precedence relations due to different mounting alternatives. In the presence of alternative precedence relations, the classical balancing problem becomes more complicated given that two interdependent problems, namely selection and balancing, must be solved hierarchically. This type of balancing problem is named as the Alternative Subgraph Assembly Line Balancing Problem (ASALBP). This current paper concerns itself to develop an efficient solution procedure for the ASALBP by hybridizing the firefly and bat algorithms. The proposed hybrid algorithm is evaluated on a set of benchmark problems and numerically compared against the standard firefly and bat algorithms, and some formerly developed heuristic methods. Computational results reveal the satisfactory performance of the proposed algorithm in solving ASALBP instances.

Alternative subgraph assembly line balancing problem

hybrid metaheuristic

firefly algorithm

bat algorithm

Assembly lines – a combination of workstations with a material handling system – are one of the most important types of the production systems. Thanks to assembly lines producing large quantities of products become possible and they have been provided efficiently use of scarce resources. To benefit from these advantageous of the assembly lines, they are required to be designed as efficiently as possible. The design problem of the assembly lines is known as the balancing problem, which is one of the main topics in the related literature on optimization of the assembly lines. Assembly line balancing problem (ALBP) is known as the decision problem of optimally partitioning the assembly work among the workstations with respect to some objectives (Scholl, 1999). In this problem type, the objective could be either to reduce the number of workstations or cycle time. According to Baybars (1986), ALBPs consist of two basic types of problems, simple assembly line balancing problem (SALBP) and generalized assembly line balancing problem (GALBP).The simple case (SALBP) is an assembly line where only one standard product is produced on a serial assembly line. If the problem have more complexity and limitations, then it should be considered as GALBP. For more detailed information, the reader could be suggested to read the review papers of Becker & Scholl (2006), Boysen et al. (2007) and Battaia & Dolgui (2012).

Normally, in an assembly line balancing problem, the precedence graph of all tasks is one, while in real-life problems some tasks may have optional precedence relations (Pinto et al. (1983), Das & Nagendra (1997), Bukchin & Tzur (2000), Senin et al. (2000)). Within this context, a new kind of GALBP named as Alternative Subgraph Assembly Line Balancing Problem (ASALBP) has been introduced by Capacho & Pastor (2005, 2008). This problem is mostly related to the assembly line balancing problem faced by suppliers with a large product range and product number, which enables them to offer more options to their customers in direct proportion to increasing customer needs. The distinctive aspect of the ASALBP is that it has alternative sub-graph precedence relations, not definite precedence relations. The ASALBP mainly considers the mounting alternatives for different parts of an assembly or manufacturing process. Each alternative is represented by a sub-graph that specifies the tasks, task times and task precedence relations required to produce a product. It must be here noted that each subassembly option has a specific task sequence with different precedence relations. Like the other ALBPs, the ASALBP is mainly divided into two groups with regard to its objective: ASALBP–1 seeks the minimum number of stations for a given cycle time while ASALBP–2 tries to minimize the cycle time for a given number of stations Capacho & Pastor (2005, 2008). This current paper intends to tackle the ASALBP–1 by developing an effective approximation algorithm.

ASALBP–1 mainly contains two decisions to be resolved: selecting one of the alternative precedence subgraph and then assigning assembly tasks to a minimum number of stations for a given cycle time. As the number of precedence sub-graph alternatives and tasks numbers increases and therefore the solution space expands, ASALBP–1 is evaluated in the NP-hard problem class Capacho & Pastor (2005, 2008). Additionally, as the problem data grows, it is required too much time to solve the problem to optimality via exact solution methods. Thereof, designing effective approximation algorithms to tackle the ASALBP–1 turns into a necessity. In the related literature, although, ASALBP–1 has been solved by many heuristic methods, metaheuristics have not been studied extensively on this subject. Consequently, in the related literature, designing metaheuristic algorithms to solve the ASALBP–1 comes out as a research gap, which is going to be exhibited in the literature review section. Therefore, this current paper proposes a novel hybrid metaheuristic that combines the firefly algorithm (FA) (Yang, 2008) with the bat algorithm (BA) (Yang, 2010) to solve the ASALBP–1 as effectively as possible.

The remainder of this paper is organized as follows. Problem definition and the relevant literature on ASALBPs are given in Section 2. The developed hybrid metaheuristic is described in Section 3. Computational results are given in Section 4. Finally, the paper concludes with some remarks in Section 5.

This section firstly describes the ASALBP–1 through the mathematical programming model developed by Capacho & Pastor (2006). Afterwards, the literature on ASALBPs is summarized.

2.1. Problem Formulation

ASALBP–1 as a general assembly line balancing problem refers to the design problem of a product assembly process where different assembly alternatives exist. In the presence of different assembly alternatives, the balancing problem becomes more complicated, since two interdependent problems must be solved simultaneously. These two problems may be named as selection and assignment problems. The selection problem aims to choose the most appropriate one among the existing assembly alternatives, while, the balancing problem aims to partition the assembly tasks among a minimum number of stations by considering a predetermined cycle time with regard to selected alternative. The ASALBP–1 has been formulated as a binary linear programming model by Capacho & Pastor (2005, 2008). Later Capacho & Pastor (2006) extended the definition of the ASALBP–1 with the consideration of sub-processes composed of different tasks and formulized the problem as a mathematical programming model. The notations with their definitions belonging to this formulation are given in Table 1. This current paper is interested in this extended variant of the ASALBP–1.

Table 1

Model notations with their definitions
Parameters	$n$	Number of tasks
	$nr$	Number of routes
	$nsr$	Number of different sets of routes (subgraphs) such that the routes within a set are alternatives to each other
	${m}_{max} \left({m}_{min}\right)$	Upper (Lower ) bound on the number of stations
	${R}_{i}$	Set of all assembly routes through which task $i$ can be processed
	$C$	Cycle time
	${t}_{ir}$	Processing time of task $i$, if task $i$ processed route$r$
	${TR}_{r}$	Set of tasks that are affected by route$r$
	${P}_{ir}$	Set of the possible immediate predecessors of task $i$, if task $i$ processed through route $r$
	${PT}_{i}$	Set of all possible immediate predecessors of task$i$
	${E}_{ir} \left({L}_{ir}\right)$	Earliest (Latest) station that task $i$ can be assigned to, if task $i$ is processed through route$r$
	${SCR}_{q}$	Subset of $q$ assembly routes that are alternative among one other.
Decision Variables	${x}_{ijr}\in \left\{\text{0,1}\right\}$	Equals 1 if task $i$ is assigned to station $j$ and processed through route $r$, and 0 otherwise
	${y}_{j}\in \left\{\text{0,1}\right\}$	Equals 1 if there is any task assigned to station $j$, and 0 otherwise
	${ar}_{r}\in \left\{\text{0,1}\right\}$	Equals 1 if there is any task processed through route $r$, and 0 otherwise

$$Min Z =\sum _{j={m}_{min}+1}^{{m}_{max}}j*{y}_{j} \left(1\right)$$

$$\sum _{j={E}_{i0}}^{{L}_{i0}}{x}_{ij0}=1 \forall i|i\in {TR}_{0} (2)$$

$$\sum _{\forall r\in {R}_{i}}\sum _{j={E}_{ir}}^{{L}_{ir}}{x}_{ijr}=\sum _{\forall r\in {R}_{i}}{ar}_{r} \forall i|i\notin {TR}_{0} (3)$$

$$\sum _{r=0}^{nr}\sum _{\forall i|\left(r\in {R}_{i}\right)\bigwedge \left(j\in \left[{E}_{ir},{L}_{ir}\right]\right)}{t}_{ir}*{x}_{ijr}\le C j=1,\dots ,{m}_{min} \left(4\right)$$

$$\sum _{r=0}^{nr}\sum _{\forall i|\left(r\in {R}_{i}\right)\bigwedge \left(j\in \left[{E}_{ir},{L}_{ir}\right]\right)}{t}_{ir}*{x}_{ijr}\le C*{y}_{j} j={m}_{min}+1,\dots ,{m}_{max} \left(5\right)$$

$$\sum _{j={E}_{p0}}^{{L}_{po}}j*{x}_{pj0}\le \sum _{j={E}_{i0}}^{{L}_{i0}}j*{x}_{ij0} \forall i\in {TR}_{0},\forall p\in {PT}_{i}|p\in {TR}_{0} (6)$$

$$\sum _{\forall s\in {R}_{p}}\sum _{j={E}_{ps}}^{{L}_{ps}}j*{x}_{pjs}\le \sum _{j={E}_{io}}^{{L}_{i0}}j*{x}_{ij0} \forall i\in {TR}_{0}, \forall p\in {PT}_{i}|p\notin {TR}_{0} (7)$$

$$\sum _{j\in {E}_{p0}}^{{L}_{p0}}j*{x}_{pj0}\le \sum _{\forall r\in {R}_{i}}\sum _{j={E}_{ir}}^{{L}_{ir}}j*{x}_{ijr}+{m}_{max}*\left(1-\sum _{\forall r\in {R}_{i}}{ar}_{r}\right) \forall i\notin {TR}_{0}, \forall p\in {PT}_{i}|p\in {TR}_{0} (8)$$

$$\sum _{j={E}_{pr}}^{{L}_{pr}}j*{x}_{pjr}\le \sum _{j={E}_{ir}}^{{L}_{ir}}j*{x}_{ijr} \forall i\notin {TR}_{0}, \forall r\in {R}_{i}, \forall p\in {P}_{ir}\left|\left[p\notin {TR}_{0}\bigwedge r\in {R}_{p}\right] \right(9)$$

$$\sum _{\forall s\in {R}_{p}}\sum _{j={E}_{ps}}^{{L}_{ps}}j*{x}_{pjs}\le \sum _{\forall r\in {R}_{i}}\sum _{j={E}_{ir}}^{{L}_{ir}}j*{x}_{ijr} \forall i\notin {TR}_{0}, \forall p\in {PT}_{i}\left|\left[p\notin {TR}_{0}\bigwedge \left({R}_{i}\cap {R}_{p}=\varnothing \right)\right] \right(10)$$

$$\sum _{r\in {SCR}_{q}}{ar}_{r}=1 q=1,\dots ,nsr \left(11\right)$$

$$\sum _{\forall i\in {TR}_{r}}\sum _{j={E}_{ir}}^{{L}_{ir}}{x}_{ijr}\le {ar}_{r}*\left|{TR}_{r}\right| r=1,\dots ,nr \left(12\right)$$

The objective function (1) of the model minimizes the total number of stations. Constraint set (2) and (3) guarantee that every task - belonging to a selected route - is assigned to exactly one station. Constraint sets (4) and (5) ensure the sum of the processing times of the tasks assigned to a station not to exceed the predetermined cycle time. Constraint set (6), (7), (8), (9) and (10) guarantee that a task can only be assigned to station $j$ if all its predecessors have already been assigned to a preceding station of $j$ on the line or to station $j$. Constraint set (11) constructs a unique assembly route by selecting exactly one route for each subassembly among the possible routes. Finally, constraint set (12) ensures assigning the tasks belonging to a particular subgraph to the same route.

2.2. Literature Review

Product assembly therefore the assembly line balancing problems commonly contains certain precedence relations between assembly tasks. Nevertheless, products may have some parts which could have alternative assembly processes in real life and this requires to selection of one of the alternative precedence relations before seeking the optimum balance of the related assembly line. In such circumstances, the balancing problem of an assembly line becomes more complicated due to alternative assemblies and therefore the alternative precedence relations between tasks. Pinto et al. (1983) handled such an assembly line balancing problem for the first time in the related literature. The processing alternatives had been occurred due to need to select of limited equipment in the Authors' case, however, the precedence relations between tasks have always been maintained. The assembly line balancing problem with processing alternatives due to need to select of limited equipment was been studied by also Bukchin & Tzur (2000). On the other hand, assembly line balancing problem that contains alternative subgraphs were been handled by Park et al. (1996), Das & Nagendra (1997) and Senin et al. (2000) for the industries of power washers manufacturing, toy manufacturing and commercial hand-held drills production, respectively.

Subsequent to afore-mentioned works, Capacho & Pastor (2005, 2008) introduced the alternative subgraph assembly line balancing problem (ASALBP) for the first time in the related literature. They gave the character traits of the ASALBP, described the problem with small examples and formulated the problem as a binary linear programming model to solve the problem to optimality. Capacho & Pastor (2006) introduced another variant of ASALBP with assembly sub-processes with different tasks. The Authors also formulized this new variant of the ASALBP as a mathematical programming model to solve the problem to optimality. The exact solution methods developed to solve both above mentioned variants of ASALBP are suffering to solve medium and large scale problem instances. Therefore, Capacho et al., (2006a) proposed three single-pass and two multi-pass heuristic methods to solve medium and large scale problem instances of the ASALBP–1. Additionally, in the related literature, 14 different heuristic methods (Capacho et al., 2006b), approximation methods (Capacho et al., 2006c) and constructive heuristics methods (Capacho et al., 2009) were also been developed to solve the ASALBP–1 as effectively as possible. An alternative representation of the ASALBP was proposed by Scholl et al. (2009) and the Authors formulated the problem as a new mixed integer programming model and tried to solve through a SALOME based solution approach. As distinct the previous works, Capacho & Pastor (2011) tried to solve the ASALBP with a metaheuristic algorithm, Greedy Randomized Adaptive Search Procedure (GRASP). The proposed GRASP selects the subgraphs and determines an initial assignments of tasks in the first phase and tries to improve the solution through a local search in the second phase. Besides this work, a new variant of the problem – ASALBP with resource selection and parallel stations – has also been solved through a genetic algorithm by Leiber et al. (2021). The Authors have also formulated the new variant of the problem as a mathematical programming model. The aforementioned literature review on ASALBPs indicates the lack of metaheuristic algorithms to tackle the problem, since it is difficult to solve the medium and large scale problem instances through the proposed mathematical programming approaches. However, there are plenty number of heuristics, whose results can potentially be improved, designed to solve the problem in the related literature. Additionally, studies in the related literature have suggested to design metaheuristic algorithms for ASALBP as future research directions. To contribute the research on eliminating this research gap, this current paper aspires to develop a hybrid metaheuristic based on firefly and bat algorithms to solve the ASALBP-1 as effectively as possible.

Both the firefly and bat algorithms were originally designed to solve continuous optimization problems, however, these two algorithms have been employed to solve plenty types of optimization problems. The variants and application areas of these two algorithms were comprehensively classified by two recent review papers of Agarwal and Kumar (2021) and Kumar and Kumar (2021). The reader can strongly be suggested to read these two review papers to be informed about the firefly and bat algorithms. These two review papers put forward that there is not any research paper on the implementation of these two algorithms to an assembly line balancing problem in the literature. From this point of view, we can conclude that this current paper will reveal some information about the potential performances of both firefly and bat algorithms in solving assembly line balancing problems.

As a final note, it must be here noted, combining the firefly and bat algorithms within a hybrid algorithmic framework is a scarce research field, since we could attain only three papers hybridized these two algorithms (Arunarani et al, 2017; Sureshkumar et al., 2018; Chen et al., 2019) from a Web-of-Science search. This situation also brings an added value to the struggle of this current paper.

This section presents the proposed hybrid Firefly and Bat (HFABA) Algorithm to solve the ASALBP–1 in detail. As a part of a hybrid algorithm, firefly algorithm has the potentials of improving the poor solutions and providing an accelerated convergence speed (Guo et al., 2013), while bat algorithm has the potential of providing an improved convergence rate (Yang & He, 2013). Therefore, it is projected to combine these two algorithms under a hybrid algorithmic framework would provide an effective solution procedure for ASALBP–1.

The proposed hybrid HFABA algorithm starts its search by tuning the values of the required parameters. The HFABA then generates an initial population of fireflies and updates the population through the search procedure of FA. Afterwards, the new population formed because of the FA is caught by the BA. At this point, BA reacts as a local search procedure and tries to improve the population through its pulse rate and loudness condition. The HFABA fulfils one single iteration through this hierarchical execution of the FA and BA. Following, The HFABA checks the termination criteria: if it is satisfied the algorithm ends and reports the best solution ever found, otherwise the FA catches the population improved by the BA. Within this context, the proposed HFABA algorithm – depicted in Fig. 1 – repeats itself until a pre-specified number of iterations reached. The algorithmic components of the proposed HFABA algorithm is going to be explained in the following sub-sections in detailed.

3.1. Solution Representation and Initial Population

A solution representation of the ASALBP–1 must be consisted of the sum of the tasks of the subgraph, chosen by the number of subassemblies that the assembly line balancing problem has. Therefore, the HFABA algorithm employs the task-based representation as it is the best fit for any assembly line balancing problem in the related literature. Figure 2a visualizes an example precedence diagram consist of 2 sub-assemblies each one having 2 subgraphs, while Fig. 2b depicts the solution representation of the assembly process resulted from the selections of subgraph-2 and subgraph-3.

The length of the solution representation is defined by the total number of assembly tasks resulted from the selected subgraphs. Tasks are assigned to stations by obeying the sequence given as the solution representation (Fig. 2b) to decode it. When a station’s idle time does not permit to assign a new task, a new station is opened. This procedure continues till all tasks are assigned to a station.

The proposed HFABA algorithm starts its search by constructing an initial population with a predefined size. Each individual of the population consists of fixed tasks, and different tasks that the alternative subgraphs have of different subassemblies. Therefore, the HFABA firstly selects the subgraphs for every individual randomly. The population is formed from assembly tasks with the same or different subgraphs. All the alternatives option combinations are used at least once for each assembly. After selecting the alternative subgraphs, individuals are created with the ranked positional weight technique (Helgeson and Birnie, 1961) and randomly – since previous studies (Capacho et al., 2006c) reported good results for these two techniques – to form initial population.

3.2. Distance and Attractiveness Calculation

After forming the population, the proposed HFABA algorithm employs FA firstly. In the FA phase, the proposed HFABA firstly determines the attractiveness of the individuals between each other. The attractiveness of an individual mainly depends on its performance namely fitness function value. Besides the fitness function, the other component of the attractiveness of an individual is the distance to other individuals. In other words, individual $f$ attracts individual $g$ if $f$ has better fitness value than $g$, and the level of attractiveness depends on the rate calculated by the dividing the fitness value of $f$ to the distance between the individuals $f$ and $g$. The proposed HFABA algorithm uses the Hamming distance – the sum of the number of tasks in different orders between the two different assembly sequences – when calculating the attractiveness of the individuals between each other.

Alternative subgraphs in ASALBP–1 can contain the same or different number of tasks. Therefore, any two individuals may have the same number of tasks or different number of tasks. Figure 3 depicts the distances – calculated with different tasks (shown in bold) in different assembly order – between any two individuals having the same number of tasks (Fig. 3a) and different number of tasks (Fig. 3b).

In accordance with, the distance between the two individuals in Fig. 3a is 4. If it has different number of tasks as in Fig. 3b, the distance is calculated over the individual having greater number of tasks. The missing number of digits in the individual having less number of tasks are indicated with zero at the end of the sequence. Thus, the distance between the individuals in Fig. 3b is found as 4, too.

As the distance between individuals decreases, the light intensities that they use to impress other individuals increases, and therefore, the attractiveness between two individuals increases. The proposed HFABA algorithm calculates the attractiveness between any two individuals through Eq. 13 as original FA does.

$${\beta }_{fg}={\beta }_{o}*{e}^{-\gamma {d}^{2}} \left(13\right)$$

where, ${\beta }_{o}$ is the initial attraction when $d=0$, $\gamma$ is the light absorption coefficient and $d$ is the distance between the individuals $f$ and $g$. If the attractiveness of the individual $f$ is greater than the individual $g$, then the individual $g$ is going to move towards $f$. In this way, the proposed HFABA algorithm tries to improve the individuals as the original FA does.

3.3. Movement of Individuals

After calculating the attractiveness of the individuals, the proposed HFABA algorithm is going to generate new individuals from the existing ones through the movement operation of the FA. The HFABA algorithm moves the individual ${f}$ towards the individual ${g}$ having a better attractiveness through the Eq. 14.

 ${x}_{f}=rand\left(2,{d}_{fg}\right) \left(14\right)$

The amount of movement of individual $f$ – ${x}_{f}$ – is a random integer chosen from the interval $\left[2 {,d}_{fg}\right],$ where ${d}_{fg}$ is the amount of distance between the individuals of $f$ and $g$. In this step, the proposed HFABA algorithm applies ${x}_{f}$ times a neighbourhood search algorithm to the individual $f$. Therefore, the HFABA algorithm generates ${x}_{f}$ candidate individuals from the individual $f$ and replace individual $f$ with the best candidate if it is better than $f$. The proposed HFABA algorithm employs the swap and insertion heuristics (see Fig. 4) as the neighbourhood search algorithms. One of the heuristics are randomly selected while generating a candidate individual. Both the swap and insertion heuristics randomly select the tasks to be relocated and generates a candidate individual if and only if relocation of the selected tasks do not violate the precedence constraints.

3.4. Local Search

After the movement step, FA phase of the proposed HFABA algorithm is completed and newly formed population is going to be caught by the BA to perform a local search phase. At this phase the proposed HFABA algorithm only employs the pulse rate and loudness condition of the original BA to generate new individuals and decide whether to accept them. In line with this purpose, the HFABA algorithm randomly selects a number from the interval $\left[\text{0,1}\right]$ for each individual of the population and compares it against the pulse rate parameter of the BA. If the randomly selected number is greater than the pulse rate for the related parent individual, then, the HFABA algorithm randomly selects one of the neighbourhood search algorithms (swap and insertion) and generate a new individual by applying it once on the parent individual. The HFABA algorithm replaces the parent individuals with the newly generated individual, if it has a better or equal fitness value in comparison to its parent and satisfies the loudness condition simultaneously. The loudness condition – ${A}_{f}$ – is a parameter and it generally takes a random value from the interval $\left[\text{0.7,1}\right]$ for each newly generated individual $f$. To check the loudness condition for each newly generated individual $f$, the HFABA algorithm selects a random number from the interval $\left[\text{0,1}\right]$ and compares it against the loudness value of ${A}_{f}$. If the randomly selected number is less than the loudness value, then the loudness condition is satisfied.

3.4. Termination Criteria

After the local phase the HFABA algorithm checks whether the termination criteria is satisfied. If it is satisfied the algorithm ends itself and reports the BEST individual ever found, otherwise, FA catches the population formed by BA, and FA and BA iteratively and hierarchically runs within the concept of the proposed HFABA until the termination criteria is met. For the termination criteria, the HFABA algorithm uses both a pre-defined number of iterations and a pre-defined execution time limit.

This section firstly compares the proposed HFABA algorithm against the standard FA and BA on a set of ASALBP–1 benchmark problems. Afterwards, a comparison against formerly developed 14 heuristics methods (Capacho et al., 2006c) is also provided. Following subsections respectively present main characteristics of the benchmark problems, and the computational results.

4.1. Benchmark Problems

The performance of the proposed HFABA algorithm is evaluated on 12 benchmark sets (Capacho & Pastor, 2006) consisting of 133 problem instances in total and available at www.assembly line balancing.de. The benchmark sets included 13 small-sized problems, 75 medium-sized problems and 45 large-scale problems, and consisted of different subgraphs, tasks and cycle times. Main characteristics of the test problems are exhibited in Table 2.

Table 2

Benchmark problems
Problem size	Problem Name	Cycle times					Number of subgraphs
		Cycle times					5	8	11
		C1	C2	C3	C4	C5	Number of tasks
Small size	Mansor	48	62	94	-	-	11	-	-
	Bowman	20	-	-	-	-	10	-	-
	Buxey	30	36	54	-	-	29	-	-
	Mitchell	14	21	35	-	-	21	21	-
Medium size	Gunther	41	49	49	61	81	37	37	37
	Kilbridge	51	79	92	138	184	45	46	48
	Hahn	2004	2338	2806	3504	4676	56	56	63
	Warnecke	54	62	74	92	111	63	63	67
	Tonge	160	176	207	251	320	73	75	75
Large size	Arcus2	5785	6540	7916	9400	11570	115	121	125
	Bartholdi	403	470	564	705	805	151	157	160
	Scholl	1394	1584	1699	2049	2787	299	302	305

4.2. Computational Results

The proposed HFABA algorithm and the standard firefly and bat algorithms were coded in MATLAB, and run on a Core™ i3 CPU 2.27 GHz personal computer. The proposed HFABA algorithm has some control parameters required to be tune before execution. The values of the control parameters were determined through some preliminary experiments and Taguchi method (Taguchi, 1986), and are given in Table 3.

Table 3

Parameter values of the HFABA algorithm
Parameter	Definition	Value
		5 Subgraphs			8 Subgraphs			11 Subgraphs
		Problem Size			Problem Size			Problem Size
		Small	Medium	Large	Small	Medium	Large	Small	Medium	Large
$PS$	Population Size	20	40	50	20	40	50	20	40	50
$A$	Loudness Value	$\left[\text{0.7,1}\right]$	$\left[\text{0.7,1}\right]$	$\left[\text{0.7,1}\right]$	$\left[\text{0.7,1}\right]$	$\left[\text{0.7,1}\right]$	$\left[\text{0.7,1}\right]$	$\left[\text{0.7,1}\right]$	$\left[\text{0.7,1}\right]$	$\left[\text{0.7,1}\right]$
$PR$	Pulse Rate	0.1	0.1	0.1	0.1	0.1	0.1	0.1	0.1	0.1
$\gamma$	Light Absorption Coefficient	0.05	0.05	0.05	0.05	0.05	0.05	0.05	0.05	0.05
${\beta }_{o}$	Initial Attraction	1	1	1	1	1	1	1	1	1
$TC$	Termination Criteria	200 iterations	2.000 iterations	18.000 seconds	200 iterations	2.000 iterations	18.000 seconds	200 iterations	2.000 iterations	18.000 seconds

PS and TC are the parameter values should be set on a problem size basis and we defined an interval for the parameter A. Therefore, the values for these three parameters were set through preliminary experiments. For the remaining three parameters of $PR$, $\gamma$ and ${\beta }_{o}$, we determined three levels for each as a result of preliminary experiments as $PR\left(1\right)=0.1$, $PR\left(2\right)=0.15$, $PR\left(3\right)=0.2$, $\gamma \left(1\right)=0.05$, $\gamma \left(2\right)=0.1$, $\gamma \left(3\right)=0.15$, ${\beta }_{o}\left(1\right)=1$, ${\beta }_{o}\left(2\right)=$2 and ${\beta }_{o}\left(3\right)=3$. To identify the appropriate values of these three parameters a Taguchi method was conducted. From Taguchi results it was observed that these 3 parameters have a meaningful effect at the 5% significance level over the objective value, and the parameters $PR$, $\gamma$ and ${\beta }_{o}$were set to 0.1, 0.05 and 1, respectively.

After fine tuning the values of the HFABA’s parameters, Table 4 firstly compares the proposed HFABA algorithm against the standard FA and BA by reporting the total number of best solutions achieved for the 133 ASALBP–1 instances after 10 runs.

Table 4

Comparison of the HFABA algorithm against FA and BA
Problem Size	Algorithm
Problem Size	FA	BA	HFABA
Small	13	13	13
Medium	68	69	75
Large	45	45	45
Total	126	127	133

As can be clearly observed from Table 4, the proposed HFABA algorithm was able to achieve best results for all the 133 problems, while standard FA and BA were able to achieve 126 and 127 best results respectively. In other words, the proposed HFABA algorithm has a success level of 100%, while standard FA and BA have success levels of 94.74% and 95.49% respectively. From these findings, we can claim that the HFABA algorithm is an improvement for both the standard firefly and bat algorithms on solving the ASALBP–1 instances, especially for the medium-sized problems.

After putting forward the satisfactory performance of the proposed HFABA algorithm in solving ASALBP–1 instances, now it is turn to come to compare the HFABA algorithm against he formerly developed solution procedures in the related literature. In line with this purpose, the HFABA algorithm is comparable against 14 heuristics methods (Capacho et al., 2006c) and GRASP (Capacho & Pastor, 2011), since the benchmark set was also been solved within the context of this two studies. However, unfortunately, among these two studies, results of the GRASP algorithm is not available for us. Therefore, we can compare the HFABA algorithm against the heuristic methods only. Table 5 compares the HFABA algorithm against the heuristic methods by considering the best results achieved. Note that, the bold values in Table 5 indicate the improved results achieved by the proposed HFABA algorithm.

Table 5

Comparison of the HFABA algorithm against the heuristic methods
Problem Name	Cycle Time	Number of Subgraphs	BKS	HFABA	Problem Name	Cycle Time	Number of Subgraphs	BKS	HFABA
Gunther	7	5	14	14	Tonge	160	5	23	23
		8	14	14			8	23	23
		11	14	14			11	23	23
	44	5	12	12		176	5	21	21
		8	12	12			8	21	21
		11	12	12			11	21	21
	49	5	11	11		207	5	18	18
		8	11	11			8	18	18
		11	11	11			11	18	18
	61	5	9	9		251	5	15	15
		8	9	9			8	15	15
		11	9	9			11	15	15
	81	5	7	7		320	5	12	12
		8	7	7			8	12	12
		11	7	7			11	12	12
Kilbridge	57	5	10	10	Arcus2	5785	5	27	27
		8	10	10			8	27	27
		11	10	10			11	27	27
	79	5	7	7		6540	5	24	24
		8	7	7			8	24	24
		11	7	7			11	24	24
	92	5	6	6		7916	5	20	20
		8	6	6			8	20	20
		11	6	6			11	20	20
	138	5	4	4		9400	5	17	17
		8	4	4			8	17	17
		11	4	4			11	17	17
	184	5	3	3		11570	5	14	14
		8	3	3			8	14	14
		11	3	3			11	14	14
Hahn	2004	5	8	8	Bartholdi	403	5	15	15
		8	8	8			8	15	15
		11	8	8			11	15	15
	2338	5	7	7		470	5	13	13
		8	7	7			8	13	13
		11	7	7			11	13	13
	2806	5	6	6		564	5	11	11
		8	6	6			8	10	11
		11	6	6			11	10	11
	3507	5	5	5		705	5	8	9
		8	5	5			8	8	8
		11	5	5			11	8	8
	4676	5	4	4		805	5	8	8
		8	4	4			8	7	8
		11	8	4			11	15	8
Warnecke	54	5	32	31	Scholl	1394	5	51	51
		8	32	31			8	51	51
		11	32	31			11	51	51
	62	5	28	27		1584	5	45	46
		8	28	27			8	45	45
		11	28	27			11	45	45
	74	5	22	22		1699	5	42	42
		8	22	22			8	42	42
		11	22	22			11	42	42
	92	5	18	18		2049	5	35	35
		8	18	18			8	35	35
		11	18	18			11	35	35
	111	5	15	15		2787	5	26	26
		8	15	15			8	26	26
		11	15	15			11	26	26
Bowman	20	5	5	5	Mitchell	14	5	8	8
Mansor	48	5	4	4		21		5	5
	62		3	3		35		3	3
	94		2	2		14	8	8	8
Buxey	30	8	12	12		21		5	5
	36		10	10		35		3	3
	54		7	7	BKS: Best Known Solution achieved by one of the heuristic methods

As it is evident in Table 5, the proposed HFABA algorithm was able to hit the best known solution for 128 problems out of 133, which refers to a success level of 96.24%. Additionally, the HFABA algorithm has identified new best solutions for 8 problems, which refers to a 6.02% improvement. The identified new best results – with their tasks assignments – are given in Appendix in detailed. As a summary, HFABA was able to solve all the problems successfully and therefore we can conclude that the HFABA is a powerful algorithm in solving ASALBP–1 instances.

This paper aimed at developing a novel hybrid metaheuristic algorithm to solve the ASALBP–1 effectively. Firstly, the firefly and bat algorithms were modified so as to be applicable for a combinatorial optimization problem, since both algorithms were originally designed to solve continuous optimization problems. After that, these two algorithms were combined within the hybrid metaheuristic framework to constitute an effective search algorithm for ASALBP–1. As it is obviously known from the literature on the metaheuristics and hybrid metaheuristics, an effective search algorithm must realize a balanced use of the diversification and intensification strategies. In line with this phenomenon, the proposed hybrid metaheuristic algorithm employed firefly and bat algorithms respectively to diversify and intensify its search. The proposed hybrid metaheuristic algorithm was firstly compared against the standard firefly and bat algorithms to observe whether it could improve the search capabilities of the firefly and bat algorithms in solving ASALBP–1 instances. After concluding the satisfactory performance of the HFABA algorithm against the firefly and bat algorithms, it was compared against some formerly developed heuristic methods. The proposed HFABA algorithm was able to hit the best known solutions for all the ASALBP–1 instances. Moreover, the HFABA algorithm identified new best solutions for 8 problems out 133.

To summarize, computational results indicate that the proposed HFABA algorithm is able to solve the ASALBP–1 instances with a satisfactory performance.

In future research, the proposed HFABA algorithm may be to solve other assembly line balancing and combinatorial optimization problems.

Funding: No funding

Conflicts of interest/Competing interests: The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Availability of data and material (data transparency): Available if it will be requested.

Code availability: Available if it will be requested.

Ethics approval: Verbal informed consent was obtained from all subjects before the study.

Consent to participate:

Ümmühan PALAMUT: Conceptualization, Methodology, Software, Data curation, Writing- Original draft preparation, Validation, Writing- Reviewing and Editing.

Şener AKPINAR: Conceptualization, Methodology, Software, Data curation, Writing- Original draft preparation, Validation, Writing- Reviewing and Editing, Supervision.

Consent for publication: The signed Consent ensures that the Publisher has the Author's permission to publish the relevant Contribution

Agarwal, T., & Kumar, V. (2021). A systematic review on bat algorithm: Theoretical foundation, variants, and applications. Archives of Computational Methods in Engineering, 1-30.
Arunarani, A. R., Manjula, D., & Sugumaran, V. (2017). FFBAT: A security and cost‐aware workflow scheduling approach combining firefly and bat algorithms. Concurrency and Computation: Practice and Experience, 29(24), e4295.
Battaïa, O., & Dolgui, A. (2013). A taxonomy of line balancing problems and their solutionapproaches. International Journal of Production Economics, 142(2), 259-277.
Baybars, I. (1986). A survey of exact algorithms for the simple assembly line balancing problem. Management Science, 32, 909–932.
Becker, C., & Scholl, A. (2006). A survey on problems and methods in generalized assembly line balancing. European Journal of Operational Research, 168(3), 694-715.
Boysen, N., Fliedner, M., & Scholl, A. (2007). A classification of assembly line balancing problems. European Journal of Operational Research, 183, 674−693.
Bukchin, J. & Tzur, M. (2000). Designs of flexible assembly line minimize equipment cost. Institute of Industrial Engineers Transactions, 32, 585−598.
Capacho, L. & Pastor, R. (2005). ASALBP: The alternative subgraphs assembly line balancing problem. Technical Report: IOC−DT−P−2005−5. UPC. Barcelona, Spain.
Capacho, L., & Pastor, R. (2006, May). The ASALB problem with processing alternatives involving different tasks: definition, formalization and resolution. In International Conference on Computational Science and Its Applications (pp. 554-563). Springer, Berlin, Heidelberg.
Capacho, L., & Pastor, R. (2008). ASALBP: The alternative subgraphs assembly line balancing problem. International Journal of Production Research, 46(13), 3503-3516.
Capacho, L., & Pastor, R. (2011). A Metaheuristic Approach to Solve the Alternative Subgraphs Assembly Line Balancing Problem. In Assembly Line-Theory and Practice (pp. 554-563). IntechOpen.
Capacho, L., Guschinskaya, O., Dolgui, A., & Pastor, R. (2006b). Approximation methods to solve the alternative subgraphs assembly line balancing problem. Technical Report G2I-EMSE 2006-500-003, Ecole des Mines de Saint Etienne, France.
Capacho, L., Guschinskaya, O., Dolgui, A., & Pastor, R. (2006c). A comprehensive comparative analysis of heuristic methods for the alternative subgraphs assembly line balancing problem. Research Report: G2I-EMSE 2006-500-005, Ecole des Mines de Saint Etienne, France, 2006.
Capacho, L., Pastor, R., Dolgui, A., & Guschinskaya, O. (2009). An evaluation of constructive heuristic methods for solving the alternative subgraphs assembly line balancing problem. Journal of Heuristics, 15(2), 109-132.
Capacho, L., Pastor, R., Guschinskaya, O., & Dolgui, A. (2006a, October). Heuristic methods to solve the alternative subgraphs assembly line balancing problem. In 2006 IEEE international conference on automation science and engineering (pp. 501-506). IEEE.
Chen, G., Qian, J., Zhang, Z., & Sun, Z. (2019). Multi-objective optimal power flow based on hybrid firefly-bat algorithm and constraints-prior object-fuzzy sorting strategy. IEEE Access, 7, 139726-139745.
Das, S. & Nagendra, P., (1997). Selection of routes in a flexible manufacturing facility. International Journal of Production Economics, 48, 237-247.
Guo, L., Wang, G-G., Wang, H., & Wang, D. (2013). An effective hybrid firefly algorithm with harmony search for global numerical optimization. The Scientific World Journal,2013, 1-9.
Helgeson, W. B., & Birnie, D. P. (1961). Assembly line balancing using the ranked positional weight technique. Journal of Industrial Engineering, 12(6), 394-398.
Kumar, V., & Kumar, D. (2021). A systematic review on firefly algorithm: past, present, and future. Archives of Computational Methods in Engineering, 28(4), 3269-3291.
Leiber, D., Vuong, A. T., & Reinhart, G. (2021). Alternative subgraphs assembly line balancing problem with resource selection and parallel stations. Engineering Optimization, 1-16.
Park, K., Park, S. & Kim, W. (1997). A heuristic for an assembly line balancing problem with incompatibility, range, and partial precedence constraints. Computers & Industrial Engineering, 32(2), 321−332.Physica–Verlag.
Pinto, P., Dannenbring, D. & Khumawala, B. (1983). Assembly line balancing with processing alternatives: an application. Management Science, 29, 817−830.
Scholl, A. (1999). Balancing and sequencing assembly lines (2nd. Ed.). Heidelberg:
Scholl, A., Boysen, N., & Fliedner, M. (2009). Optimally solving the alternative subgraphs assembly line balancing problem. Annals of Operations Research, 172, 243–258.
Senin, N., Gropetti, R., & Wallace, D. R. (2000). Concurrent assembly planning with genetic algorithms. Robotics and Computer Integrated Manufacturing, 16, 65-72.
Sureshkumar, T., Lingaraj, M., Anand, B., & Premkumar, T. (2018). Hybrid firefly bat algorithm (HFBA)–based network security policy enforcement for PSA. International Journal of Communication Systems, 31(14), e3740.
Taguchi, G. (1986). Introduction to Quality Engineering: Designing Quality into Products and Processes, 1st ed., White Plains: Asian Productivity Organization.
Yang, X. S. (2010). A new metaheuristic bat-inspired algorithm. In Nature inspired cooperative strategies for optimization (NICSO 2010) (pp. 65-74). Springer, Berlin, Heidelberg.
Yang, X. S., & He, X. (2013). Bat algorithm: literature review and applications. International Journal of Bio-inspired Computation, 5(3), 141-149.
Yang, X., S. (2008). Nature – inspired metaheuristic algorithm (2nd ed.). England: Luniver Press.

No competing interests reported.

APPENDIXNewSolutions.docx

Download PDF

Version 1

posted

You are reading this latest preprint version

Parameters	\(n\)	Number of tasks
	\(nr\)	Number of routes
	\(nsr\)	Number of different sets of routes (subgraphs) such that the routes within a set are alternatives to each other
	\({m}_{max} \left({m}_{min}\right)\)	Upper (Lower ) bound on the number of stations
	\({R}_{i}\)	Set of all assembly routes through which task \(i\) can be processed
	\(C\)	Cycle time
	\({t}_{ir}\)	Processing time of task \(i\), if task \(i\) processed route\(r\)
	\({TR}_{r}\)	Set of tasks that are affected by route\(r\)
	\({P}_{ir}\)	Set of the possible immediate predecessors of task \(i\), if task \(i\) processed through route \(r\)
	\({PT}_{i}\)	Set of all possible immediate predecessors of task\(i\)
	\({E}_{ir} \left({L}_{ir}\right)\)	Earliest (Latest) station that task \(i\) can be assigned to, if task \(i\) is processed through route\(r\)
	\({SCR}_{q}\)	Subset of \(q\) assembly routes that are alternative among one other.
Decision Variables	\({x}_{ijr}\in \left\{\text{0,1}\right\}\)	Equals 1 if task \(i\) is assigned to station \(j\) and processed through route \(r\), and 0 otherwise
	\({y}_{j}\in \left\{\text{0,1}\right\}\)	Equals 1 if there is any task assigned to station \(j\), and 0 otherwise
	\({ar}_{r}\in \left\{\text{0,1}\right\}\)	Equals 1 if there is any task processed through route \(r\), and 0 otherwise

A Hybrid Metaheuristic based on the Firefly and Bat Algorithms to Solve the Alternative Subgraphs Assembly Line Balancing Problem

Status:

Version 1

Abstract

Figures

1. Introduction

2. Problem Definition And Literature Review

2.1. Problem Formulation

3. Hybrid Firefly And Bat Algorithm For Solving Asalbp–1

3.1. Solution Representation and Initial Population

3.2. Distance and Attractiveness Calculation

3.3. Movement of Individuals

3.4. Local Search

3.4. Termination Criteria

4. Performance Evaluation Of The Proposed Hfaba Algorithm

4.1. Benchmark Problems

4.2. Computational Results

5. Conclusions

Declarations

References

Additional Declarations

Supplementary Files

Status:

Version 1