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.
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.
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.
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.
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.
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-0027Download as .RIS
Emerald Publishing Limited
Copyright © 2018, Emerald Publishing Limited
Notation used in the SALBP-1 models
- i, r, k
= Cycle time;
= Number of tasks;
= Processing time of task i;
= Set of precedence relations; for example, r, k ∈ P if and only if task r is an immediate predecessor of task k;
= Upper bound on the number of workstations;
= 1, if any task is assigned to station j; 0, otherwise;
= 1, if task i is assigned to station j in backward direction; 0, otherwise; and
= 1, if task i is assigned to station j in forward direction; 0, otherwise.
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.
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:
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:
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).
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:
= immediate predecessors of tasks i;
= set of all predecessors of tasks i;
= immediate successors of tasks i;
= set of all successors of tasks i;
= workstation upper bound for task i obtained as , i.e. the last workstation until which task i has to be performed such that all its successors can still be altogether; and
= workstation lower bound for task i that is calculated as , 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 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.
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 ti ≤ CT 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 = C – ti), 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.
List of the constructive heuristics used
|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),|
|8||MinLB||Smallest lower bound,|
|9||MinSL||Minimum slack, UBi–LBi|
|10||MaxIP||Maximum number of immediate predecessors, |IPi||
|11||MinUB||Smallest upper bound,|
|12||MaxS||Greatest number of successors, |Si||
|13||MaxARPW||Greatest average rank positional weight,|
|14||Min (UB/S)||Smallest (upper bound divided by the number of successors),|
|15||Min (S/TaskSL)||Minimum (number of successors divided by task slack),|
|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
|Straight line||U-shaped line|
|Solution 1||Solution 2||Solution 1||Solution 2|
Solutions for the straight-line configuration
|Solution 1||Solution 2||Problem||Cycle
|Solution 1||Solution 2|
Solutions for the U-shaped line configuration
|Solution 1||Solution 2||Problem||Cycle
|Solution 1||Solution 2|
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.
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.