Assembly line balancing problem: A comparative evaluation of heuristics and a computational assessment of objectives

Masood Fathi (Department of Production and Automation Engineering, University of Skövde, Skövde, Sweden)
Dalila Benedita Machado Martins Fontes (Faculty of Economics, University of Porto, Porto, Portugal and Laboratory of Artificial Intelligence and Decision Support (LIAAD), INESC TEC, Porto, Portugal)
Matias Urenda Moris (Department of Industrial Engineering and Management, Jönköping University, Jönköping, Sweden and Division of Industrial Engineering and Management, Department of Engineering Sciences, Uppsala University, Uppsala, Sweden)
Morteza Ghobakhloo (Department of Industrial Engineering, Minab Higher Educational Center, University of Hormozgan, Bandar Abbas, Iran)

Journal of Modelling in Management

ISSN: 1746-5664

Publication date: 14 May 2018

Abstract

Purpose

The purpose of this study is to first investigate the efficiency of the most commonly used performance measures for minimizing the number of workstations (NWs) in approaches addressing simple assembly line balancing problem (SALBP) for both straight and U-shaped line, and second to provide a comparative evaluation of 20 constructive heuristics to find solutions to the SALBP-1.

Design/methodology/approach

A total of 200 problems are solved by 20 different constructive heuristics for both straight and U-shaped assembly line. Moreover, several comparisons have been made to evaluate the performance of constructive heuristics.

Findings

Minimizing the smoothness index is not necessarily equivalent to minimizing the NWs; therefore, it should not be used as the fitness function in approaches addressing the SALBP-1. Line efficiency and the idle time are indeed reliable performance measures for minimizing the NWs. The most promising heuristics for straight and U-shaped line configurations for SALBP-1 are also ranked and introduced.

Practical implications

Results are expected to help scholars and industrial practitioners to better design effective solution methods for having the most balanced assembly line. This study will further help with choosing the most proper heuristic with regard to the problem specifications and line configuration.

Originality/value

There is limited research assessing the efficiency of the common objectives for SALBP-1. This study is among the first to prove that minimizing the workload smoothness is not equivalent to minimizing the NWs in SALBP-1 studies. This work is also one of the first attempts for evaluating the constructive heuristics for both straight and U-shaped line configurations.

Keywords

Citation

Fathi, M., Fontes, D., Urenda Moris, M. and Ghobakhloo, M. (2018), "Assembly line balancing problem", Journal of Modelling in Management, Vol. 13 No. 2, pp. 455-474. https://doi.org/10.1108/JM2-03-2017-0027

Download as .RIS

Publisher

:

Emerald Publishing Limited

Copyright © 2018, Emerald Publishing Limited


Notation used in the SALBP-1 models

i, r, k

= Task;

j

= Workstation;

C

= Cycle time;

N

= Number of tasks;

ti

= Processing time of task i;

P

= Set of precedence relations; for example, r, kP if and only if task r is an immediate predecessor of task k;

Mmax

= Upper bound on the number of workstations;

yj

= 1, if any task is assigned to station j; 0, otherwise;

zij

= 1, if task i is assigned to station j in backward direction; 0, otherwise; and

xij

= 1, if task i is assigned to station j in forward direction; 0, otherwise.

1. Introduction

The assembly line balancing problem (ALBP) aims at assigning assembly operations to a set of workstations to optimize some performance measures, while satisfying technological, operational and organizational constraints (Benzer et al., 2007). According to the literature (Koltai et al., 2014; Becker and Scholl, 2006; Boysen et al., 2007; Alavidoost et al., 2015), ALBPs are categorized into two main groups based on their assumptions and limitations, namely, simple assembly line balancing problems (SALBPs) and generalized assembly line balancing problems (GALBPs).

The SALBP is one of the most well-studied problems within the area of line balancing and the majority of the reported research on ALBPs has been targeted at SALBP (Scholl and Becker, 2006; Fathi et al., 2011. An important aspect that differentiates SALBPs is the performance measure, usually referred to as objective, considered. Following the literature (Ritt and Costa, 2015; Esmaeilbeigi et al., 2015; Ariffin et al., 2012), the SALBPs are classified into two main groups based on their objective, namely, SALBP-1, which aims to minimize the number of workstations (NWs) for a known, fixed and common (to all workstations) cycle time, and SALBP-2, which aims to minimize the cycle time while the NWs is fixed. According to the literature (Bautista and Pereira, 2009; Wei and Chao, 2011; Fathi and Ghobakhloo, 2014), most of the research works on SALBPs have been concentrated on improving solution procedures for SALBP-1.

Considering the shape of the line, the two common configurations of assembly lines are straight and U-shaped (Nilakantan and Ponnambalam, 2016). In principal, in a straight line, assembly tasks can only be assigned to operators from one end of the line (front or back), whereas tasks from both ends of the line can be handled by the same operator in a U-shaped line. A schematic view of straight and U-shaped line is depicted in Figure 1.

The SALBP has been shown to be NP-hard and therefore, optimal solutions to realistic sized problems cannot be found in a reasonable amount of time (Pitakaso, 2015; Pape, 2015). Thus, most of the research works regarding this problem have been on heuristic methods (Fathi et al., 2010). Comprehensive discussions on heuristic methods for SALBPs can be found in the studies by Fathi and Ghobakhloo (2014) and Battaïa and Dolgui (2013). To find more about other type of ALBPs and solution methods, the interested readers are referred to the studies by Sivasankaran and Shahabudeen (2014), Li et al. (2017) and Make et al. (2016).

The effectiveness and efficiency of heuristic algorithms depend, among other factors, on the fitness function used. The fitness function has a major role as, in addition to being used to identify the best solution found, it is also used to guide search for good quality solutions as it points the algorithm towards an area of the feasible region with promising solutions. Therefore, the fitness function must be closely correlated with the objective of the original problem to avoid losing the best-found solution, due to miscalculation of the solution quality, and to avoid late convergence and consequently higher computational times. In addition, the computation of the fitness function must be easy and fast due to the iterative nature of heuristic methods.

One of the often-used fitness functions for SALBP-1 is the workload smoothness index (SI) (Fathi and Ghobakhloo, 2014). In this paper, we show that the minimization of the SI, using its common formula provided in equation (12), may not satisfy the objective of the SALBP-1, i.e. the resulting solution may not minimize the NWs, regardless of the line configuration considered (straight and U-shaped). Therefore, the SI should not be used as the fitness function in the studies targeted at minimizing the NWs as, as shown in Section 3, solutions with worst SI may have better NWs, and vice-versa.

Many different heuristic have been proposed overtime for the SALBP-1. Nevertheless, a comprehensive computational comparative study on their performance has never been done. Here, we shed some light on the choice and performance of 20 constructive heuristics considering 100 benchmark problem instances and two different line configurations (straight and U-shaped). We chose to test constructive heuristics, as they are a very useful type of heuristics, as they can play several roles in solutions approaches: as a stand-alone method, given the ability of finding feasible solutions, as an initial solution generator and as a foundation for complex heuristics. We also use these heuristics to compare the NWs used and the workload SI of the solutions obtained, thus providing empirical evidence on the inadequacy of using the smooth index as a fitness function to solve this problem.

The remainder of this paper is organized as follows: Section 2 describes the SALBP-1 in detail and provides the corresponding mathematical formulation, both for straight and U-shaped line configurations. The validity of selecting the workload smoothness as the fitness function in SALBP-1 studies is investigated in Section 3 by resorting to 100 benchmark problem instances. Section 4 reports the comparative evaluation of 20 heuristics for SALBP-1 and Section 5 presents the conclusions drawn, as well as some future research directions.

2. Problem description and formulation

The SALBP-1, first proposed by Bowman (1960) and Urban (1998), aims to minimize the NWs given a set of assembly tasks i(i = 1,.., N) with known precedence relationships, and a set of undistinguishable workstations j(j = 1,.., Mmax).

The general assumptions of the straight and U-shaped SALBP-1 are presented below, followed by the notation used in the mathematical programming models.

2.1 Assumptions

  • The assembly line is a paced line producing a single model (mass-production of one homogeneous product).

  • The cycle time is known, fixed and common to all workstations.

  • The assembly tasks are connected by precedence constraints.

  • An assembly task cannot be divided among several workstations.

  • Only one task can be performed in a workstation at a given time.

  • The time to perform a task does not depend on the assigned workstation.

  • A task can be performed in any workstation (workstations are equally equipped).

  • The processing time of each assembly task is known and deterministic.

2.2 Mathematical model

The mathematical model of SALBP-1 for straight line is as follows:

(1) Minimizej=1Mmaxyj
(2) j=1Mmaxxij=1,  i=1,2,...,N,
(3) i=1Ntixij=Cyj,  j=1,2,...,Mmax,
(4) j=1Mmaxj(xrjxkj)0,  (r,k)P,
(5) xij,yj{0,1},  i=1,2,...,N;j=1,2,...,Mmax.

The objective in this problem is to minimize the total number of used workstations, which here is enforced by assigning the last task to the earliest possible station as in equation (1). Equation (2) ensures that each task will be assigned to exactly one workstation. Equation (3) controls the workstations’ workload, by guaranteeing the total processing time of the tasks assigned to each used workstation to be at most the given cycle time. Equation (4) imposes the precedence relations amongst the assembly tasks. Finally, the domain of the variables is defined in equation (5).

The mathematical model of SALBP-1 for U-shaped line is as follows:

(6) Minimizej=1Mmaxyj
(7) j=1Mmax(xij+zij)=1,  i=1,2,...,N,
(8) i=1Nti(xij+zij)=Cyj,  j=1,2,...,Mmax,
(9) j=1Mmaxj(Mmaxj+1)(xrj+xkj)0,  (r,k)P,
(10) j=1Mmaxj(Mmaxj+1)(zkj+zrj)0,  (r,k)P,
(11) xij,zij,yj{0,1},  i=1,2,...,N;j=1,2,...,Mmax

As earlier, the objective is to minimize the number of used workstations, equation (1) is here renumbered as equation (6). Equation (7) ensures that every task is performed exactly once, either in the backward or forward direction. Similar to equation (3), equation (8) ensures that the total processing time of the assigned tasks to each used workstation does not exceed the given cycle time. Equations (9) and (10) ensure precedence constrains, more specifically, equation (9) ensures that forward direction task assignment occurs after all predecessors of each specific task have been assigned, whereas equation (10) requires all successors to be assigned before a backward direction assignment is made. Finally, variables’ domain is defined in equation (11).

The objective of SALBP-1 is, by definition, the minimization of the NWs. Although, the NWs can easily be defined and modelled as a simple counter or binary variable, usually more complex fitness functions are used in research studies where a heuristic algorithm is presented. It is obvious that, the efficiency of the heuristic algorithms vastly depends on the fitness function used, as it plays a significant role in evaluating the generated solutions and in guiding the algorithm toward good solutions. Therefore, the fitness function must be closely correlated with the objective of the original problem to avoid late convergence and consequently higher computational times. Furthermore, optimizing the fitness function should imply optimizing the original objective function, as otherwise good or even optimal solutions might go unnoticed and therefore lost.

One of the most commonly used objective functions in SALBPs is the minimization of the SI, which allows for evenly distributing the workload amongst the workstations (Fathi and Ghobakhloo, 2014; Hu et al., 2014). The importance and advantages of such objective have been vastly discussed in the literature (Kellegöz, 2016; Mozdgir et al., 2013; Nourmohammadi and Zandieh, 2011; Nearchou, 2011) and are out of the scope of this work. The most common formula to compute the SI is given in equation (12).

(12) SI=j=1M(TmaxTj)2M
where M is the number of workstations, Tmax is the maximum workstation time (max{∑i∈jtj;j=1,2,...,M}), and Tj is the time of jth workstation (∑i∈jtj;j=1,2,...,M).

In the next section, we will investigate, through a set of computational experiments, whether SI satisfies the objective of SALBP-1 (minimizing the NWs) as it is being used in such studies; see for example the recent studies by Baykasoglu (2006) and Baykasoğlu and Özbakir (2015).

3. Assessment of objectives to minimize the workstations

As far as we are aware, there has been no discussion in the literature regarding the applicability of the SI as the optimization criterion to solve the SALBP-1. Given its widespread use as such and the fact that it is neither equivalent nor implies the optimization of the NWs used, here we carry out a set of experiments to infer on the validity of doing so. The computational experiments involve both straight and U-shape assembly line configurations. For each of these configurations, a set of 100 benchmark problem instances, which can be found at the assembly line optimization research homepage (Scholl et al., 2007), is considered. It should be noticed that many of these problems come from industrial applications, namely, Bartholdi, Gunther, Hahn, Heskiaoff, Lutz, Mukherjee, Tonge and Warnecke (Scholl, 1997).

All instances are solved by 20 different constructive heuristics that have been collected from previous studies (Fathi et al., 2016; Moreira et al., 2012; Kellegöz and Toklu, 2015) (Table I). All the heuristics were coded in MATLAB 2014a and run on a personal computer with a 2.6-GHz Intel Core i5 CPU and 16 GB of RAM.

The notation used to present the heuristics in Table I, which has not been introduced before, is as follows:

IPi

= immediate predecessors of tasks i;

Pi

= set of all predecessors of tasks i;

ISi

= immediate successors of tasks i;

Si

= set of all successors of tasks i;

UBi

= workstation upper bound for task i obtained as N+1[(ti+rSitr)C]+, i.e. the last workstation until which task i has to be performed such that all its successors can still be altogether; and

LBi

= workstation lower bound for task i that is calculated as [(ti+rPitr)C]+, i.e. the first work station in which task i can be performed as all its predecessor have to be already performed.

For illustration purposes and as it would be impossible to report full details for all the 20 solutions of the 200 instances solved, we provided an example where full details for two solutions for each assembly line configuration are reported. To this end, we have considered the Sawyer instance, a well-known benchmark problem instance. The relative precedence network for the Sawyer’s problem is shown in Figure 2, where the number above a node represents the task processing time, in seconds, and the one within the node represents the task number. The cycle time is 41 s.

Table II reports two feasible solutions (Solution 1 and Solution 2) for each of the two assembly line configurations considered (straight and U-shape). The last row of Table II provides the SI value for each solution, computed as given by equation (12). The first column identifies the workstations by associating a number to each one of them. The second and third columns provide two different feasible solutions for the straight-line configuration, whereas the fourth and fifth columns provide the two feasible solutions for the U-shaped line configuration. Each column (except the first) identifies the tasks to be performed in the corresponding workstation (Column 1). Regarding the straight-line configuration, Solution 1 (Column 2) requires the use of ten workstations and has an SI value of 10.601, whereas Solution 2 (Column 3) requires nine workstations and has an SI value of 11.522. Thus, according to the SI values, Solution 1 would be better (10.601 is smaller than 11.522). However, since in the SALBP-1, the NWs is to be minimized, Solution 2 is actually better as it requires only nine workstations. A similar situation is exemplified for the U-shaped line, as Solution 1 has an SI value smaller than Solution 2 (Columns 4 and 5, respectively); however, Solution 2 only requires nine workstations, whereas Solution 1 requires ten. Again, Solution 2 is better, though having a larger SI value.

Each of the 200 instances considered has been solved by each of the 20 heuristics described in Table I. We report on the SI value and the NWs required for each of the solutions found. Here, in Tables II and III, we only report two different solutions for the instances considered; nevertheless, results for all problem instances obtained by each heuristic can be found in http://goo.gl/5zzJTL.

Tables III and IV refer, respectively, to the straight-line and U-shaped assembly line configurations and report both on the SI value and the NWs used. In each table, we provide two solutions for the problem instances considered: Solution 1 (given in Columns 3 and 4 and 9 and 10) has a smaller SI value, whereas Solution 2 (given in Columns 5 and 6 and 11 and 12) requires a smaller NWs. Therefore, considering the SI as the main fitness function, Solution 1 would be chosen which is inconsistent with the SALBP-1 objective.

Further evidence is provided by comparing the SI results obtained by the different heuristics for the same problem instance. To avoid massive number of pairwise comparisons, we compare each heuristic results with the ones obtained by the heuristics with a higher identification number, that is the results obtained by heuristic h are compared with the results obtained by heuristics h + 1, h + 2, … , H. Therefore, a total of h=1H(h1) pairwise comparisons are performed, where, H is the total number of heuristics.

A comparison is considered to involve conflictive pairs, whenever a solution involving a lower SI value but higher NWs is preferred to a solution that although having a higher SI is indeed better as it has lower NWs. In Figures 3 and 4, we depict the number of times a conflictive pairwise comparison occurs for each problem instance for straight and U-shaped assembly lines, respectively.

As it can be seen in Figures 3 and 4, for each problem instance solved, there are, on average, more than 11 cases in which the “best” solution is wrongly chosen. This happens both for straight and U-shaped line configurations. Therefore, in all these cases, an inferior solution would be chosen, although a better one was found. Furthermore, although in some cases the phenomenon is not too frequent, in some others it happens up to 90 times for the straight-line configuration and 64 times for U-shaped line configuration, which corresponds to almost 50 per cent and 35 per cent of the comparisons, respectively.

Given the results obtained, it is safe to conclude that the SI [equation (12)] is not a good choice for the fitness function as its inaccurate evaluation of solutions will likely lead to a poor choice of solutions. This in turn will not only lead to late convergence and consequently higher computational times, but also to the choice of a solution that is not the best one found. Therefore, we recommend the use of a different (and valid) fitness function. Among the different objectives available in the literature for SALBP-1, it can be easily proven that the line efficiency (LE) and the idle time (IT), which can be calculated, respectively, as given by equations (13) and (14), are valid alternatives for NWs. Unlike the SI, proving the equivalency of LE and IT to the NWs is not a difficult task and does not need computational exploration. It is obvious that in the area of SALBP-1, where the cycle time is given and processing time of tasks is known with certainty, any changes in the values of equations (13) and (14) can only be caused by the “number of workstations”, as everything else is constant. Therefore, it can be stated with certainty that minimizing the NWs in SALBPs of type-1 is equivalent to minimize the IT or maximize the LE.

(13) IT=M×Ci=1Nti
(14) LE=i=1NtiM×C

It should be noticed, however, that the SI might be an important performance measure and therefore interesting to use as a complementary objective, for example, for breaking ties where more than one solution with the same NWs exists.

4. Comparative evaluation of heuristics

The majority of constructive heuristics for ALBP have been proposed for SALBP (Kellegöz and Toklu, 2015). Constructive heuristics are very popular and can be used in three different ways, namely, as a stand-alone method capable of finding feasible solutions very quickly, as an initial solution generator for algorithms evolving or changing solutions (e.g. metaheuristics, local search, etc.) and imbedded as a part of more sophisticated heuristic/metaheuristic methods. The general assignment procedure of constructive heuristics for SALBP-1 is presented as algorithm 1.

Algorithm 1. General assignment procedure of constructive heuristics for SALBP-1.

Input: Cycle time (C), precedence relationships between tasks, and tasks’ time

 1. Open a workstation, CT = C.

 2. Determine the list of candidate tasks, LCT. Task i is a member of LCT if tiCT and has no immediate predecessors.

 3. If the list of candidate tasks is not empty, assign task i to the current workstation based on the priority defined by the heuristic; otherwise, go to Step 5.

 4. Update the workstation cycle time (CT = Cti), remove task i from the list of precedence tasks for all the tasks that have task i as an immediate predecessor and, go to Step 2.

 5. If all the tasks are assigned, terminate the process. Otherwise, go to Step 1.

Given the importance and vast use of constructive heuristics, it is crucial to know, or at least to have some idea of, the heuristics performance regarding to each problem type and objective. To the best of our knowledge, no comprehensive evaluation on the performance of the available constructive heuristics for SALBP-1 has been reported in the literature. In this section, the efficiency and performance of the 20 heuristics given in Table I, at solving SALBP-1 for both straight and U-shaped assembly line are evaluated through a series of computational tests. The comparison is performed based on the results obtained for the 200 instances solved. Each heuristic is compared to the others with respect to two objectives, namely, minimizing the NWs and minimizing the SI. The results of comparisons are plotted in the charts of Figures 5-10.

Figure 5 shows the cumulative number of times, i.e. number of problem instances, each heuristic found the lowest NWs amongst the 20 heuristics, both for straight and U-shaped line configurations. In many cases, several heuristics have been able to find the same “best” solution. From the graph, it can be seen that the “maximum ranked positional weight” (heuristic 6) is the best-performing heuristic for the straight-line configuration, as it has found the smallest, or at least as small, NWs in 80 of 100 instances solved. This heuristic is closely followed by heuristic 7, i.e. “greatest (processing time divided by the upper bound)”, which had such performance for 78 instances. It is still worth mentioning heuristic 1, the “longest processing time”, as it has done so for 71 instances. Heuristics numbers 7 and 1 stand out, as these have achieved the “best” value in 94 and 92 instances for U-shaped line, respectively. This number comes down to 75 for the third best-performing heuristic, heuristic 6. It is interesting to notice that the three top-performing heuristics are the same for both line configurations, although not exactly in the same order.

Another important aspect regarding the heuristics’ robustness is how good or bad it is when not performing well. To analyse this, all the heuristics are ranked from 1 to the end in each problem instance solved, considering the NWs found. It is obvious that there could be more than one heuristic with the same rank in each problem instance. In Figure 6, we plotted for each heuristic the average of its ranks, out of the 100 instances solved, for each line configuration. As we are minimizing the NWs, the closer to 1 the rank is, the better the heuristic performance.

As it can be seen in Figure 6, the top three heuristics remain the same. Moreover, the ranking among them is also the same, namely, heuristics 6, 7 and 1 for the straight-line configuration and 7, 1 and 6 for the U-shaped line configuration.

Regarding the NWs, for each heuristic we have also compared the NWs found with the optimal one (Figure 7). The optimum NWs can be found at the assembly line optimization research homepage (Nourmohammadi and Zandieh, 2011). This comparison is not a relative comparison but an absolute comparison. As it can be seen in Figure 7, the top two heuristics remain unchallenged, although in the U-shaped case, they swapped positions. However, the third performing heuristic, for both configurations, is different. For the straight-line configuration, the heuristic based on “greatest number of successors” (number 12) is now third, whereas heuristic number 1 became fourth. In regard to the U-shaped configuration, the third best heuristic is now the one based on the “minimum slack” (number 9) and number 6 became fourth. It is interesting to notice that, in all the three comparisons made for NWs the worst-performing heuristic is heuristic number 2 (“shortest processing time”). It is also worth mentioning that heuristics are more successful at finding an optimum for straight-line instances than for U-shaped ones. An optimum was found in 43 of 100 problem instances solved for straight line, while this number came down to 26 for U-shaped line.

According to Figures 5-7, it is safe to say that heuristics 6 and 7 are the recommended ones for straight-line instances, as these have consistently performed better at finding the “best” NWs. For U-shaped instances, the recommended ones are heuristics 7 and 1.

Similar statistics have been collected regarding the heuristics performance in finding the best SI. Figure 8 shows the number of times each heuristic was able to match the best SI found amongst the 20 heuristics. The best-performing heuristics for straight line were heuristics 6 (“maximum ranked positional weight”), 7 (“greatest (processing time divided by the upper bound)”) and 9 (“minimum slack”) and 13 (“greatest average rank positional weight”). For the U-shaped line, there was almost always more than one heuristic with the same performance ranking: heuristics 5 (“smallest task number”) and 13 (“greatest average rank positional weight”), heuristics 7 (“greatest (processing time divided by the upper bound)”) and 9 (“minimum slack”) and heuristics 1 (“longest processing time”) and 17 (“maximum task time of immediate successor tasks”). It is noteworthy that although heuristic 5 obtained very good results for U-shaped line, it has not been able to find even one good solution for straight line.

Just like the case of NWs, we have averaged the ranks of the heuristics in finding the SI. From Figure 9, it can be observed that the best results for the straight line configuration are due to heuristics 9 (“minimum slack”), 16 (“maximum positional weight of successor tasks”) and 11 (“smallest upper bound”), whereas for U-shaped line are due to heuristics 13 (“greatest average rank positional weight”), 5 (“smallest task number”) and 16 (“maximum positional weight of successor tasks”) and 9 (“minimum slack”).

As no optimum SI value is available, we do not know how close the solutions obtained are to optimality. From the observation of Figures 8 and 9, it can be concluded that the performance of the heuristics regarding SI is not as consistent as it was for NWs. Therefore, a conclusion regarding the best heuristics for achieving good SI values seems to be difficult. However, heuristic 9 is in the top three for both indicators, regarding straight line. Regarding U-shaped line configuration, the ranking of the top three heuristics is 13, 5 and 9.

One last comparison of the heuristics’ performance is obtained by finding how many times each heuristic found simultaneously the best value for both NWs and SI (i.e. found a non-dominated solution) (Figure 10). As it can be seen, the best results for straight line were obtained by heuristic 6 (“maximum ranked positional weight”), 7 (“greatest (processing time divided by the upper bound)”) and 13 (“greatest average rank positional weight”). Regarding U-shaped line, the best heuristics are 5 (“smallest task number”) and 13 (“greatest average rank positional weight”), 7 (“greatest [processing time divided by the upper bound]”) and 17 (“maximum task time of immediate successor tasks”).

5. Conclusion and future work directions

This study empirically investigates the adequacy of using the SI as the fitness function to solve the simple assembly line balancing problem of type-1 (SALBP-1). As minimizing the SI is neither equivalent to minimizing the NWs nor implies it, we recommend not using the SI as the fitness function. Otherwise, it may happen that:

  • the best solution found is lost, as the method misidentifies the solution with the best SI as the best solution and not the one with the best NWs;

  • it may guide the search away from best solutions and thus lead to late convergence of the algorithm; and

  • computational requirements become larger. Due to the above explanations, the selection of the SI as the fitness function when solving the SALBP-1 is not recommended.

This has been illustrated by solving a set of 100 benchmark problem instances, each for straight and U-shaped line configurations.

Researchers should use instead the IT, which should be minimized, or the LE, which should be maximized, since both are equivalent to minimizing the NWs in SALBP-1.

In addition, a comparative evaluation of 20 constructive heuristics is presented, again both for straight and U-shaped line configurations. All the heuristics were compared using two objective functions, namely, NWs (which is the SALBP-1 objective function) and SI. The heuristics were compared regarding the number of times each was able to find the best solution amongst the 20 heuristic solutions obtained, and the average of the ranks of heuristics, out of the 100 instances solved. Regarding the first objective (NWs), we were also able to compare the solution obtained by each heuristic with an optimal solution, since one is known. This study allowed for the conclusion that for SALBP-1, i.e. minimizing NWs, heuristics 6 “maximum ranked positional weight” and 7 “greatest (processing time divided by the upper bound) undoubtedly produce better results for the straight line configuration and heuristics 7 “greatest (processing time divided by the upper bound) and 1 “longest processing time” are the recommended ones for U-shaped line configuration. The conclusions regarding the minimization of SI are more difficult and weak; nevertheless, it seems that the best-performing heuristics are 9 “minimum slack” for straight line configuration and 13 “greatest average rank positional weight” and 5 “smallest task number” for U-shaped line configuration.

A final comparison was performed by simultaneously considering both objectives and looking at the number of non-dominated solutions each heuristic was able to find. The results obtained showed that the best heuristics are different for straight and U-shaped line configurations; however, two of the heurists, namely, 7 “greatest (processing time divided by the upper bound)” and 13 “greatest average rank positional weight”, can provide a good solution to both line configurations.

The computational time of the heuristics, although slightly different, is quite small (merely a few seconds) for all heuristics.

Similar studies should be performed for other ALBP problems with considering different line configurations. Moreover, such studies may be useful to evaluate the efficiency of heuristics in other scheduling problems, e.g. job shop scheduling, considering these or other constructive heuristics.

Figures

Straight and U-shaped assembly line configurations

Figure 1.

Straight and U-shaped assembly line configurations

Sawyer’s problem instance: precedence network

Figure 2.

Sawyer’s problem instance: precedence network

Number of conflictive pairs found for each problem in straight-line configuration

Figure 3.

Number of conflictive pairs found for each problem in straight-line configuration

Number of conflictive pairs found for each problem in U-shaped line configuration

Figure 4.

Number of conflictive pairs found for each problem in U-shaped line configuration

Number of problem instances for which each heuristic found the best NWs, amongst the 20 heuristic solutions obtained

Figure 5.

Number of problem instances for which each heuristic found the best NWs, amongst the 20 heuristic solutions obtained

The average of the ranks of heuristics in finding NWs, out of the 100 instances solved, for both line configurations

Figure 6.

The average of the ranks of heuristics in finding NWs, out of the 100 instances solved, for both line configurations

Number of times each heuristic was able to find the optimum NWs, considering 100 problem instances both for straight-line and U-shaped line configurations

Figure 7.

Number of times each heuristic was able to find the optimum NWs, considering 100 problem instances both for straight-line and U-shaped line configurations

Number of problem instances for which each heuristic found the best SI, amongst the 20 heuristic solutions obtained

Figure 8.

Number of problem instances for which each heuristic found the best SI, amongst the 20 heuristic solutions obtained

The average of the ranks of heuristics in finding the SI, out of the 100 instances solved, for both line configurations

Figure 9.

The average of the ranks of heuristics in finding the SI, out of the 100 instances solved, for both line configurations

Number of times each heuristic found a non-dominated solution, considering simultaneously the NWs and the SI

Figure 10.

Number of times each heuristic found a non-dominated solution, considering simultaneously the NWs and the SI

List of the constructive heuristics used

No. Notation Definition
1 MaxTime Longest processing time, ti
2 MinTime Shortest processing time, ti
3 MaxIS Maximum number of immediate successors, |ISi|
4 RP Random priority, random i
5 MinTaskNo Smallest task number, i
6 MaxRPW Maximum ranked positional weight, ti+∑r∈Sitr
7 Max (Time/UB) Greatest (processing time divided by the upper bound), tiUBi
8 MinLB Smallest lower bound, [(ti+rPitr)C]+
9 MinSL Minimum slack, UBiLBi
10 MaxIP Maximum number of immediate predecessors, |IPi|
11 MinUB Smallest upper bound, N+1[(ti+rSitr)C]+
12 MaxS Greatest number of successors, |Si|
13 MaxARPW Greatest average rank positional weight, (ti+rSitr)(|Si|+1)
14 Min (UB/S) Smallest (upper bound divided by the number of successors), UBi(|Si|+1)
15 Min (S/TaskSL) Minimum (number of successors divided by task slack), |Si|(UBiLBi)
16 MaxPWS Maximum positional weight of successor tasks, ∑r∈Sitr
17 MaxTimeIS Maximum task time of immediate successor tasks, |ISi|
18 MinS Minimum total number of successor tasks, |ISi|
19 MaxTimeS Maximum total time of successor tasks, T|ISi|
20 MaxP Maximum total number of predecessor tasks, |Pi|

Assigned tasks to workstations on straight and U-shaped lines

Workstations
no.
Straight line U-shaped line
Solution 1 Solution 2 Solution 1 Solution 2
1 1,2,3,5,10 3,16,1,10 30,10,2,28,1,5,6 3,19,10
2 4,6,7,16 4,2,12,13,5,17 4,7,8,9 11,16,18,2
3 11,12,13,17 11,14,18 11,29 12,1,4,28
4 14,18,8,9 19,20,24 12,13,14,15 13,14,20,24
5 15,19 21,25 19,18,17 21,25,5
6 20,24,25 15,22,23 3,16 15,22,23,17
7 21,22 6,7,8,9,26 20,24,25 6,7,8,30,9
8 23,26 27,29,30 26,21 29,27
9 27,28 28 22,23 26
10 29,30 27
SI 10.601 11.522 9.969 11.030

Solutions for the straight-line configuration

Problem Cycle
time
Solution 1 Solution 2 Problem Cycle
time
Solution 1 Solution 2
NWs SI NWs SI NWs SI NWs SI
Arcus2 5755 29 867,862 28 1033,461 WeeMag
Barthol2
35 61 9,104 60 10,752
5785 29 889,899 28 1097,889 41 60 14,650 59 16,370
6016 28 900,591 27 1014,214 42 60 15,699 58 17,115
6540 26 991,418 25 1137,606 49 33 5,228 32 7,112
6837 25 1004,463 24 1097,046 50 33 6,562 32 7,646
7162 24 1385,143 23 1515,575 52 33 8,393 32 9,170
7520 22 924,132 21 1188,827 87 52 7,467 51 8,037
7916 21 1234,790 20 1498,703 89 52 10,756 51 11,610
8356 22 1779,336 21 1919,477 91 50 8,471 49 9,305
8847 19 1276,417 18 1651,457 95 48 9,647 47 11,067
9400 19 2053,123 18 2323,971 97 47 10,163 46 13,103
10027 17 1496,067 16 1817,392 99 48 14,898 47 15,046
10743 16 1927,561 15 2306,204 101 46 13,114 45 13,807
11378 15 2098,387 14 2211,087 104 44 11,954 43 12,180
11570 15 2197,221 14 2821,288 106 44 13,281 43 14,558
Arcus1 3786 23 705,213 22 757,927 109 42 13,569 41 15,050
4454 20 785,054 19 822,348 112 42 14,713 41 16,337
Lutz3 75 27 17,429 26 19,791 121 38 16,085 37 18,429
79 24 11,690 23 13,951 125 37 16,213 36 21,044
83 23 14,739 22 15,900 129 36 18,536 35 21,428
87 22 15,582 21 19,475 133 35 19,828 34 20,575
92 20 12,304 19 14,502 137 33 11,940 32 12,539
97 20 18,753 19 21,600 142 32 14,409 31 14,690
118 16 18,107 15 22,9928 152 32 28,000 31 29,987
Barthol1 403 16 92,419 15 97,401 157 29 17,956 28 19,710
470 14 112,509 13 121,021 170 27 23,069 26 24,004
Kilbrid 62 11 13,757 10 16,583 Lutz2 15 37 2,760 36 2,833
Tonge 160 25 26,811 24 28,928 18 30 2,330 29 2,722
168 24 30,692 23 33,318 20 28 3,375 27 3,404
176 23 31,792 22 32,913 21 27 3,610 26 3,695
185 22 35,926 21 36,555 Mukherjee 176 28 37,444 27 37,592
195 22 45,071 21 48,535 183 26 27,878 25 28,136
220 19 48,751 18 51,804 201 24 31,040 23 38,722
251 16 45,097 15 53,902 222 21 33,565 20 37,873
270 15 51,533 14 63,687 234 21 47,223 20 47,810
293 14 57,711 13 70,869 281 18 61,128 17 64,231
320 13 75,989 12 76,452 Rosenberg 18 9 4,496 8 5,111
Warnecke 54 36 13,812 35 14,420 Sawyer 27 15 5,633 14 5,781
56 35 12,760 33 13,620 30 14 7,540 13 7,625
58 31 10,933 30 11,457 33 13 8,682 12 10,400
62 30 10,605 29 11,965 41 10 10,601 9 11,522
65 30 16,386 29 16,418 47 9 8,006 8 13,143
68 27 13,211 26 13,376 Michel 15 10 4,969 9 5,754
82 23 17,444 22 19,533 Lutz1 2020 9 454,073 8 460,832
86 21 17,254 20 17,541 Buxey 30 14 7,483 13 8,057
92 20 18,253 19 21,111 33 13 8,673 12 9,814
111 17 23,141 16 26,483 Heskiaoff 138 10 34,111 9 36,624
WeeMag 30 64 6,338 63 6,952 Mertens 8 6 1,354 5 1,414
31 63 6,904 62 7,5462 10 6 1,354 5 2,569
33 62 8,526 61 9,111 Gunther 81 8 24,085 7 28,415

Solutions for the U-shaped line configuration

Problem Cycle
time
Solution 1 Solution 2 Problem Cycle
time
Solution 1 Solution 2
NWs SI NWs SI NWs SI NWs SI
Arcus2 5785 28 633,315 27 876,754 Warnecke 111 17 19,846 16 23,361
6016 27 697,933 26 995,851 WeeMag 31 63 6,781 62 7,7115
6267 26 698,570 25 976,165 32 63 7,673 61 8,195
6540 25 669,417 24 966,391 40 62 14,307 60 15,941
6837 24 795,840 23 1061,722 41 62 14,307 59 16,634
7162 23 1028,547 22 1150,053 54 32 8,708 31 9,310
8847 19 1269,022 18 1810,323 Hahn 2004 9 580,260 8 663,836
9400 18 1675,933 17 1986,974 2338 8 798,734 7 811,828
10743 17 2354,341 15 2723,262 Barthol2 85 53 7,180 52 11,214
11378 15 1929,730 14 2205,274 93 48 6,429 47 10,280
11570 15 2101,473 14 3074,314 95 47 7,326 46 10,725
Arcus1 3985 22 687,569 21 789,094 97 46 6,500 45 10,975
4454 20 785,054 19 904,545 104 44 10,485 43 15,003
5048 17 693,701 16 894,809 106 43 10,188 42 14,237
5408 16 768,244 15 937,570 112 40 8,351 39 11,967
6309 14 1055,114 13 1307,023 118 39 13,208 38 17,697
6842 13 1086,770 12 1485,723 129 35 14,149 34 17,156
6883 13 1418,948 12 1572,319 133 34 9,591 33 16,581
Lutz3 83 22 10,647 21 15,226 142 32 17,306 31 19,058
87 21 11,328 20 14,010 163 28 17,010 27 22,414
92 20 13,928 19 19,128 170 27 23,958 26 26,621
97 19 13,080 18 19,442 Lutz2 15 35 1,740 34 2,319
110 17 17,756 16 23,138 17 31 1,951 30 2,822
118 16 23,659 15 28,696 18 30 2,183 29 2,281
127 15 21,228 14 25,472 19 28 2,211 27 2,993
137 14 23,271 13 33,890 20 26 1,829 25 2,236
Barthol1 434 15 81,822 14 114,665 21 25 2,000 24 2,188
470 14 111,319 13 128,427 Mukherjee 176 26 21,819 25 25,458
Kilbrid 56 12 12,138 11 16,113 183 25 19,866 24 23,954
57 12 12,138 11 16,138 192 24 22,005 23 29,281
62 11 13,892 10 18,390 201 23 25,048 22 34,500
79 9 22,085 8 26,537 211 22 29,339 21 39,165
Tonge 160 24 16,668 23 25.395 234 20 32,556 19 45,737
176 22 21,660 21 25,777 248 19 42,514 18 48,756
185 23 37,290 22 39,031 281 17 47,617 16 60,404
195 20 27,736 19 34,614 301 16 48,172 15 71,582
207 19 35,480 18 40,7049 30 13 6,838 12 7,359
234 18 42,542 17 44,692 33 12 4,222 11 7,982
251 16 46,300 15 57,926 41 10 9,969 9 11,030
293 14 56,255 13 68,987 Buxey 30 13 6,189 12 6,879
320 13 52,778 12 82,088 33 12 6,582 11 8,836
Warnecke 54 33 8,177 32 9,303 36 11 7,077 10 7,823
58 30 8,209 29 10,214 47 9 7,141 8 13,351
60 30 9,791 29 10,221 Heskiaoff 138 10 35,318 9 38,231
68 26 9,687 25 10,877 Mertens 7 6 1,354 5 1,549
71 25 10,019 24 11,210 8 6 1,354 5 2,645
74 24 12,179 23 14,154 Gunther 44 13 8,142 12 9,945
78 23 13,689 22 15,765 54 11 12,037 10 14,110
86 20 10,747 19 11,410 61 10 9,596 9 18,726
92 19 12,303 18 13,666 69 9 18,511 8 20,949

References

Alavidoost, M., Tarimoradi, M. and Zarandi, M.F. (2015), “Fuzzy adaptive genetic algorithm for multi-objective assembly line balancing problems”, Applied Soft Computing, Vol. 34, pp. 655-677.

Ariffin, M.K.A.M., Fathi, M. and Ismail, N. (2012), “A new heuristic method to solve straight assembly line balancing problem”, Pertanika Journal of Science & Technology, Vol. 20 No. 2, pp. 355-369.

Battaïa, O. and Dolgui, A. (2013), “A taxonomy of line balancing problems and their solutionapproaches”, International Journal of Production Economics, Vol. 142 No. 2, pp. 259-277.

Bautista, J. and Pereira, J. (2009), “A dynamic programming based heuristic for the assembly line balancing problem”, European Journal of Operational Research, Vol. 194 No. 3, pp. 787-794.

Baykasoglu, A. (2006), “Multi-rule multi-objective simulated annealing algorithm for straight and u type assembly line balancing problems”, Journal of Intelligent Manufacturing, Vol. 17 No. 2, pp. 217-232.

Baykasoğlu, A. and Özbakir, L. (2015), “Discovering task assignment rules for assembly line balancing via genetic programming”, The International Journal of Advanced Manufacturing Technology, Vol. 76 Nos 1/4, pp. 417-434.

Becker, C. and Scholl, A. (2006), “A survey on problems and methods in generalized assembly line balancing”, European Journal of Operational Research, Vol. 168 No. 3, pp. 694-715.

Benzer, R., Gökçen, H., Cetinyokus, T. and Cerçioglu, H. (2007), “A network model for parallel line balancing problem”, Mathematical Problems in Engineering, Vol. 2007.

Bowman, E.H. (1960), “Assembly-line balancing by linear programming”, Operations Research, Vol. 8 No. 3, pp. 385-389.

Boysen, N., Fliedner, M. and Scholl, A. (2007), “A classification of assembly line balancing problems”, European Journal of Operational Research, Vol. 183 No. 2, pp. 674-693.

Esmaeilbeigi, R., Naderi, B. and Charkhgard, P. (2015), “The type e simple assembly line balancing problem: a mixed integer linear programming formulation”, Computers & Operations Research, Vol. 64, pp. 168-177.

Fathi, M. and Ghobakhloo, M. (2014), “A technical comment on ‘a review on assembly sequence planning and assembly line balancing optimisation using soft computing approaches’”, The International Journal of Advanced Manufacturing Technology, Vol. 71 Nos 9/12, pp. 2033-2042.

Fathi, M., Ariffin, M. and Ismail, N. (2010), “A note on ‘a multi-objective genetic algorithm for solving assembly line balancing problem’”, The International Journal of Advanced Manufacturing Technology, Vol. 50 Nos 5/8, pp. 771-773.

Fathi, M., Lvarez, M.J.Á. and Rodríguez, V. (2016), “A new heuristic-based bi-objective simulated annealing method for u-shaped assembly line balancing”, European Journal of Industrial Engineering, Vol. 10 No. 2, pp. 145-169.

Fathi, M., Jahan, A., Ariffin, M. and Ismail, N. (2011), “A new heuristic method based on CPM in SALBP”, Journal of Industrial Engineering International, Vol. 7 No. 13, pp. 1-11.

Hu, X., Zhang, Y., Zeng, N. and Wang, D. (2014), “A novel assembly line balancing method based on PSO algorithm”, Mathematical Problems in Engineering, Vol. 2014.

Kellegöz, T. (2016), “Balancing lexicographic multi-objective assembly lines with multi-manned stations”, Mathematical Problems in Engineering, Vol. 2016.

Kellegöz, T. and Toklu, B. (2015), “A priority rule-based constructive heuristic and an improvement method for balancing assembly lines with parallel multi-manned workstations”, International Journal of Production Research, Vol. 53 No. 3, pp. 736-756.

Koltai, T., Tatay, V. and Kalló, N. (2014), “Application of the results of simple assembly line balancing models in practice: the case of a bicycle manufacturer”, International Journal of Computer Integrated Manufacturing, Vol. 27 No. 9, pp. 887-898.

Li, Z., Kucukkoc, I. and Nilakantan, J.M. (2017), “Comprehensive review and evaluation of heuristics and Meta-heuristics for two-sided assembly line balancing problem”, Computers & Operations Research, Vol. 84, pp. 146-161.

Make, M.R.A., Rashid, M.F.F.A. and Razali, M.M. (2016), “A review of two-sided assembly line balancing problem”, The International Journal of Advanced Manufacturing Technology, pp. 1-21.

Moreira, M.C.O., Ritt, M., Costa, A.M. and Chaves, A.A. (2012), “Simple heuristics for the assembly line worker assignment and balancing problem”, Journal of Heuristics, Vol. 18 No. 3, pp. 505-524.

Mozdgir, A., Mahdavi, I., Badeleh, I.S. and Solimanpur, M. (2013), “Using the Taguchi method to optimize the differential evolution algorithm parameters for minimizing the workload smoothness index in simple assembly line balancing”, Mathematical and Computer Modelling, Vol. 57 Nos 1/2, pp. 137-151.

Nearchou, A.C. (2011), “Maximizing production rate and workload smoothing in assembly lines using particle swarm optimization”, International Journal of Production Economics, Vol. 129 No. 2, pp. 242-250.

Nilakantan, J. and Ponnambalam, S. (2016), “Robotic u-shaped assembly line balancing using particle swarm optimization”, Engineering Optimization, Vol. 48 No. 2, pp. 231-252.

Nourmohammadi, A. and Zandieh, M. (2011), “Assembly line balancing by a new multi-objective differential evolution algorithm based on topsis”, International Journal of Production Research, Vol. 49 No. 10, pp. 2833-2855.

Pape, T. (2015), “Heuristics and lower bounds for the simple assembly line balancing problem type 1: Overview, computational tests and improvements”, European Journal of Operational Research, Vol. 240 No. 1, pp. 32-42.

Pitakaso, R. (2015), “Differential evolution algorithm for simple assembly line balancing type 1 (salbp-1)”, Journal of Industrial and Production Engineering, Vol. 32 No. 2, pp. 104-114.

Ritt, M. and Costa, A.M. (2018), “Improved integer programming models for simple assembly line balancing and related problems”, International Transactions in Operational Research, Vol. 25 No. 4, pp. 1345-1359.

Scholl, A. (1997), “Data of assembly line balancing problems”, tech. rep., Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).

Scholl, A. and Becker, C. (2006), “State-of-the-art exact and heuristic solution procedures for simple assembly line balancing”, European Journal of Operational Research, Vol. 168 No. 3, pp. 666-693.

Scholl, A., Boysen, N., Fliedner, M. and Klein, R. (2007), Assembly Line Balancing: Data Sets & Research Topics, available at: https://assembly-line-balancing.de (accessed January 2017).

Sivasankaran, P. and Shahabudeen, P. (2014), “Literature review of assembly line balancing problems”, The International Journal of Advanced Manufacturing Technology, Vol. 73 Nos 9/12, pp. 1665-1694.

Urban, T.L. (1998), “Note. optimal balancing of u-shaped assembly lines”, Management Science, Vol. 44 No. 5, pp. 738-741.

Wei, N.-C. and Chao, I.-M. (2011), “A solution procedure for type e simple assembly line balancing problem”, Computers & Industrial Engineering, Vol. 61 No. 3, pp. 824-830

Acknowledgements

The first author is partially supported by the European Union’s Horizon 2020 research and innovation programme under grant agreement No. 723711 through the MANUWORK project.

Conflict of interests: The authors declare that there is no conflict of interests regarding the publication of this paper.

Corresponding author

Masood Fathi can be contacted at: fathi.masood@gmail.com