1 Introduction

Assembly lines have been used extensively to produce high-volume products in the industry and one of the well-known research areas in the production environment (Serin et al. 2019). Assembly line balancing problem can be defined as assigning tasks to workstations, considering the constraints on the line. In addition, it has to be optimized with specific objectives, such as cycle time minimization for a predetermined number of the workstations or workstation minimization for a predetermined cycle time (Ct). Also, assembly processes include between 15 and 70% of manufacturing lead time and 40% of manufacturing costs (Gökçen et al. 2006; Yadav et al. 2019). A considerable amount of research on solving conventional ALB problems is available in the literature (Baykasoğlu and Dereli 2008; Çevikcan and Durmusoğlu 2020). In addition, conventional ALBP is known as the NP-hard problems (Ege et al. 2009; Yeh and Kao 2009). The detailed reviews of such studies are given by Scholl and Becker (2006) and Becker and Scholl (2006).

Another variant of ALBP considers worker assignments. This is a major problem found in sheltered work centers for disabled. Some employees may need more time to perform certain tasks or may not be able to do so. Because of the growing interest and respect for the disabled, many industries employing them, and companies are always concerned with assigning workers on assembly lines (Blum and Miralles 2011). In this case, one of the most critical issues is that there are workers with different skill levels. There are various models created for this purpose, and such lines are called assembly line worker assignment and balancing problems (ALWABP) in the literature. In cases where task times depend on the worker, it is important to decide on assigning tasks (Miralles et al. 2007). For this reason, a high-skill level worker can perform the task quickly, while the worker with a lower skill level could more time to complete the task. ALWABP tries to determine the most appropriate assignment for both workers and workstations as seen in Fig. 1 (Shin et al. 2019). ALWABP is an assembly line balancing problem involving worker assignment and task allocation sub-problems. Worker assignment aims to distribute tasks evenly across workstations by satisfying different constraints such as precedence and cycle time constraint, while determining the assignment of workers to workstations (Dolgui et al. 2018).

Fig. 1
figure 1

Assignment example of workers and tasks for ALWABP

Full size image

In the real-world planning environment, more are occurring than the constraints involved in assembly lines. For this reason, it has become a necessity to offer solutions considering these additional constraints.

For most industrial assembly lines, setups are assumed to be negligible because their time is very short compared to task time. As a result of this situation, it is not necessary to specify task execution sequences in a workstation, but task execution order is an important issue in order to minimize station time in case of sequence-dependent setup times. Therefore, in the real-world planning environment, it may be necessary to consider sequence-dependent setup times in ALWBP. Performing one task directly before another task can affect the completion time of the next task within the same station, since a setup may be required to perform the second task. Also, if a task is assigned to a worker in a station as the last one, it may need setup time to perform the first task assigned to that station (Özcan and Toklu 2010). Andres et al. first introduced balancing and scheduling tasks in assembly lines with sequence-dependent setup times (Andres et al. 2008).

Most of the published papers about sequence-dependent setup times have focused extensively on various line balancing problems except ALWABP (Dolgui et al. 2018; Özcan and Toklu 2010; Andres et al. 2008; Scholl et al. 2008, 2013; Martino and Pastor 2010; Nazarian et al. 2010; Seyed-Alagheband et al. 2011; Yazdanparast et al. 2011; Yolmeh and Kianfar 2012; Kalayci and Gupta 2013; Akpınar et al. 2013, 2017; Hamta et al. 2013; Akpınar and Baykasoğlu 2014a, b; Şahin and Kellegöz 2017; Özcan 2019). ALWABP has been criticized for lacking real-life application since the problem structure in a real-world planning environment is much more complex. To the authors’ best knowledge, no study has been reported on ALWABP with the objective of minimizing cycle time under sequence-dependent setup times. Building on the significance and relevance of the study to sequence-dependent setup times in ALWABP, this study presents several contributions, as follows:

  1. (1)

    The first contribution is to present the ALWABP problem with sequence-dependent setup times for the first time. Also, a new mixed integer programming model is formulated and solved by GUROBI to solve small-sized problems.

  2. (2)

    The second contribution is that a metaheuristic algorithm developed to solve the large-sized problems.

  3. (3)

    A comprehensive comparative study is conducted to test the performance of the proposed algorithm. However, the result quality and CPU times of the proposed heuristic method were also compared with the mathematical model.

This paper is organized as follows. After the introduction, the ALWABP literature review is presented in Sect. 2. In Sect. 3, problem description and the MIP formulation of the problem are presented. In Sect. 4, the proposed simulated annealing algorithm for solving ALWABP is given in detail. The computational results with the application of MIP formulation and the results of the metaheuristic algorithm on a set of test problems are presented and discussed in Sect. 5 and 6. Finally, some conclusions and implications for further research are presented in the last section.

2 Literature review

In this section, firstly, the literature on assembly lines with setup time is given. Then, the literature on assembly line worker assignment and balancing problems are presented. Dolgui et al. reported that the study of assembly line balancing, scheduling and design problems is widely studied in the literature (Dolgui et al. 2018). However, there are various studies on assembly line problems with sequence-dependent setup times in the literature. Andres et al. first introduced balancing and scheduling tasks in assembly lines with sequence-dependent setup times. A binary integer programming model and greedy randomized adaptive search procedure are presented (Andres et al. 2008). Scholl et al. defined a new problem and formulated a mixed integer program for the sequence-dependent assembly line balancing problem. Also, they generated test data for computational experiments (Scholl et al. 2008). Martino and Pastor (2010) presented a heuristic to solve the same problem as Andres et al. (2008). Özcan and Toklu presented a mixed integer program and a COMSOAL-based heuristic algorithm to solve two-sided assembly line balancing problems with sequence-dependent setup times (Özcan and Toklu 2010). A mathematical formulation using mixed integer programming for sequence-dependent task times in multi-model production has been developed by Nazarian et al. (2010). Seyed-Alagheband et al. have developed a mathematical model and a simulated annealing (SA) algorithm to solve type II assembly line balancing problems with sequence-dependent setup times (Seyed-Alagheband et al. 2011). Yazdanparast et al. discussed the general assembly line balancing problem with setups and formulated a mathematical model to solve the problem (Yazdanparast et al. 2011). Yolmeh and Kianfar considered setup assembly line balancing and scheduling problem and proposed a hybrid genetic algorithm to solve the problem (Yolmeh and Kianfar 2012). Scholl et al. extended the problem by introducing backward setups. Also, they have proposed a mathematical program and heuristics algorithms in order to solve the problem (Scholl et al. 2013). Kalayci and Gupta considered sequence-dependent disassembly line balancing problem. However, a particle swarm optimization algorithm has been proposed to solve the problem (Kalayci and Gupta 2013). Akpınar et al. have presented a new hybrid ant colony algorithm with genetic algorithm for mixed-model assembly line balancing problem type I with real-world constraints such as zoning constraints, parallel workstations and sequence-dependent setup times between tasks (Akpınar et al. 2013). Hamta et al. have presented multi-objective optimization of single model assembly line balancing problem with sequence-dependent setup time exists between tasks and have proposed a particle swarm optimization algorithm with variable neighborhood search to solve it (Hamta et al. 2013). Akpınar and Baykasoğlu have presented a mixed-model assembly line balancing problem with sequence-dependent setup times. Besides, a mixed integer linear programming formulation and hybrid bee algorithm have been proposed to solve the problem (Akpınar and Baykasoğlu 2014a, b). Şahin and Kellegöz have developed a mixed-binary integer programming model, a simulated annealing algorithm and a genetic algorithm for the U-type assembly lines with sequence-dependent setup times (Şahin and Kellegöz 2017). Akpınar et al. have proposed an exact solution algorithm based on Benders decomposition for setup assembly line balancing problem (Akpınar et al. 2017). Özcan have introduced parallel assembly line balancing problem with sequence-dependent setup times. Also, they have proposed mathematical programming model and a simulated annealing algorithm to solve the problem (Özcan 2019). Yang and Cheng have examined the multi-manned assembly line balancing problem, which is widely used in large-sized productions, with sequence-dependent setup times. A mixed integer programming is presented, and a simulated annealing algorithm is also proposed to solve it (Yang and Cheng 2020).

Regarding worker assignment and balancing problems, Miralles et al. have introduced sheltered work centers in assembly line balancing and formulated a mathematical model (Miralles et al. 2007). Chaves et al. have proposed a hybrid heuristic based on clustering search to solve ALWABP (Chaves et al. 2007). Miralles et al. have defined a mathematical model for ALWABP and a branch and bound approach with different search strategies to solve the problem (Miralles et al. 2008). Chaves et al. have proposed a hybrid method based on clustering search to solve the ALWABP (Chaves et al. 2009). Blum and Miralles have developed a beam search method to solve assembly worker assignment and balancing problems (Blum and Miralles 2011). Moreira et al. have introduced a constructive heuristic based on priority rules of task-worker (Moreira et al. 2012). Mutlu et al. have developed a genetic algorithm to solve the problem. Also, results of the algorithm show that the proposed method is very robust and effective for large test instances (Mutlu et al. 2013). Vila and Pereira derived new lower bounds for the ALWABP. Nevertheless, they have developed an exact algorithm to solve the problem. This proposed branch and bound algorithm yields state-of-the-art results for ALWABP (Vila and Pereira 2014). Ramezanian and Ezzatpanah presented a mixed-model assembly line balancing and worker assignment problem. A goal programming solution procedure has been proposed to solve the problem (Ramezanian and Ezzatpanah 2015). Akyol and Baykasoğlu proposed a constructive heuristic approach for the ALWABP. Performance of the algorithm is compared with the relevant literature on test instances. Experimental results show that the proposed approach is very effective on test instances (Akyol and Baykasoğlu 2016). Janardhanan et al. studied worker assignment and line balancing problem in two-sided assembly lines. They have developed a mixed integer programming model and a migrating birds algorithm to solve the problem (Janardhanan et al. 2019).

In order to adapt the solutions offered to assembly lines to real-world systems, the problem should be examined together with the constraints such as sequence-dependent setup times encountered in the real world. When the literature is examined, it is seen that the ALWABP has not been studied together with the sequence-dependent setup time constraints. The presented study is the first study in the literature in terms of analyzing the assembly line worker assignment and balancing problem with sequence-dependent setup times (ALWABPS). Also, in this study, two main elements of setup times are considered between tasks: forward and backward setups, and the objective is to minimize the cycle time for workstations. Another contribution to the literature of the paper is to formulate a new mixed integer programming model. Furthermore, a computational study using a simulated annealing (SA) algorithm as a metaheuristic approach for test instances, involving up to 2 setup group (low and high) and total 640 test instances, is presented.

3 Assembly line worker assignment and balancing problem with sequence-dependent setup times (ALWABPS)

3.1 Problem definition

This paper will focus on proposing algorithm and approaches for solving ALWABP with the sequence-dependent setup time, based on conclusions from the literature review. This paper tackles the problem by aiming to minimize the cycle time and integrate forward and backward setup times into the problem. ALWABP, which minimizes the cycle time, can be formally expressed as: A set “I” of tasks, a set “W” of workers, and a set “WS” of stations are given by a line designer to perform these tasks. Some workers are unable to perform a number of tasks because they do not have some skills or they have a disability. Let “Wi ⊆ W” be the subset of workers that can perform task “i ∈ I”. However, let “Iw ⊆ I” be the subset of tasks that can be performed by worker “w ∈ W”. For each task “i” that can be performed by worker “w”, “Ziw” expresses the time required by the worker “w” to perform the task “i” and it is called the task time. Some tasks have precedence relationships where the current task cannot be performed before the previous one. The objective of the problem is to ensure that all work pieces (tasks) assigned to the workstation can be performed by the workers at that station, precedence relations between tasks are fulfilled and the cycle time of workstations is minimized (Pereira 2018).

Between tasks, there are two types of sequence-dependent setup times. These are forward setup and backward setup, respectively. At the same workstation, if task “i” is performed just before another task “h”, a forward setup occurs for the same workpiece to perform task “h”. It is called forward setup time, and “µih” is added to the workstation time. In a regular workstation, if task “i” is the last assigned task in a workstation and task “h” is the first assigned task at the same workstation, then it is called backward setup. It is necessary to perform task h, and a backward setup time, ŧih, is added to compute workstation cycle time.

A detailed illustration of assembly line worker assignment and balancing with sequence-dependent setup times is given in Fig. 1. As seen in Fig. 2, Worker 3 is assigned to Workstation 1 and “1–5–3” tasks are assigned to him. At the same time, these assignments are “2–4” tasks for the Worker 1, and “6–7” for the Worker 2. Setup times, i.e., forward setups; µ15 and µ24, and backward setups; ŧ31 and ŧ42, are also shown in Fig. 2.

Fig. 2
figure 2

Illustration of ALWABP with sequence-dependent setup times

Full size image

In this paper, it is assumed that the problem considered under the following conditions:

  • The task times are deterministic and known in advance.

  • Not all workers may be able to perform all tasks.

  • A task can be assigned to only one workstation.

  • A task can be assigned to only one worker.

  • A single model product is produced.

  • The precedence relationships are known in advance.

  • All components are available with no quality problems.

  • The forward and backward setup times deterministic and known in advance.

  • Each task must be performed.

  • No breakdowns occur in the assembly line.

4 Notations

The notations used in MILP of the problem are given as follows.

i, h:

A task

j:

A workstation

w:

A worker

s:

A position inside the task operation sequence of a workstation

c:

Cycle time

tiw:

Task time of “i” at worker “w”

SN:

Maximum number of tasks that can be assigned to any station

P:

Set of immediate predecessors of tasks

WS:

Number of workstations

WW:

Number of workers

SN:

Number of positions.

T:

Number of tasks

I:

Set of tasks. I = {1, 2, …., i, …T}.

W:

 Number of assignable workers on the line. W = {1, 2, …., w, …WW}.

J:

Number of workstations on the line. J = {1, 2, …., j, …WS}.

S:

Number of positions in a station. S = {1, 2, …., s, … SN}.

M:

A big number.

xijws:

1, if task “i” in workstation “j” is assigned to worker “w” in position “s” of its operation sequence; 0, otherwise.

yjw:

1, if worker “w” is assigned to workstation “w”; 0, otherwise.

pfihjw:

1, if task “i” is the immediate processor of task “h” in workstation “j” at worker “w”; 0, otherwise.

pbihjw:

1, if task “i” is the last task and “h” is the first task assigned to workstation “j” at worker “w”; 0, otherwise.

lijw:

1, if task is the last task assigned to workstation “j” at worker “w”; 0, otherwise.

4.1 Mixed integer programming model of ALWABPS

In this study, presented mathematical model is as follows:

$$\mathrm{Minimize} c$$
(1)
$$\sum_{j\in J}\sum_{w\in W}\sum_{s\in S}{x}_{ijws}=1, \forall \left(i\right)\in I$$
(2)
$$\sum_{i\in I}{x}_{ijws} \le 1, \forall \left(j\right)\in J, \forall \left(w\right)\in W, \forall \left(s\right)\in S $$
(3)
$$\sum_{j\in J}{y}_{jw} = 1, \forall \left(w\right)\in W$$
(4)
$$\sum_{w\in W}{y}_{jw} = 1, \forall \left(j\right)\in J $$
(5)
$$\sum_{i\in I}\sum_{s\in S}{x}_{ijws}\le {M*y}_{jw}, \forall \left(j\right)\in J, \forall \left(w\right)\in W$$
(6)
$$\sum_{i\in I}{x}_{ijw(s+1)} -\sum_{i\in I}{x}_{ijws} \le 0, \forall \left(j\right)\in J, \forall \left(w\right)\in W, \forall \left(s\right)\in \left\{1, 2, \dots \dots .\dots \left(SN-1\right)\right\} $$
(7)
$$\sum_{j\in J}\sum_{w\in W}\sum_{s\in S}\left(SN*\left(j-1\right)+s\right){*x}_{ijws}-\sum_{j\in J}\sum_{w\in W}\sum_{s\in S}\left(SN*\left(j-1\right)+s\right){*x}_{hjws}\le 0, \forall \left(j\right)\in J, \forall \left(w\right)\in W, \forall \left(s\right)\in S, \left(i,h\right)\in P$$
(8)
$$\sum_{i\in I}\sum_{s\in S}\sum_{w\in W}{t}_{iw}*{x}_{ijws} +\sum_{\left(i, h\right)\in I,i\ne k}\sum_{s\in S}\sum_{w\in W}{tsf}_{ih}*{pf}_{ihjw} +\sum_{\left(i, h\right)\in I}\sum_{s\in S}\sum_{w\in W}{tsb}_{ih}*{pb}_{ihjw} \le c*\sum_{w\in W}{y}_{jw}, \forall \left(j\right)\in J$$
(9)
$${x}_{ijws}+ {x}_{hjw(s+1)}-{pf}_{ihjw} \le 1, \forall \left(j\right)\in J, \forall \left(i, h\right)\in I, i\ne h, \forall \left(s\right)\in \left\{1, 2, \dots \dots .\dots \left(SN-1\right)\right\}$$
(10)
$${x}_{ijws}-\sum_{h\in I}\sum_{w\in W}{x}_{hjw(s+1)} \le {l}_{ijw}, \forall \left(j\right)\in J, \forall \left(i, h\right)\in I, i\ne h, \forall \left(s\right)\in \left\{1, 2, \dots \dots .\dots \left(SN-1\right)\right\}$$
(11)
$${l}_{ijw}+ {x}_{hjw1}-{pb}_{ihjw} \le 1, \forall \left(j\right)\in J, \forall \left(i, h\right)\in I, \forall \left(s\right)\in S$$
(12)
$$\sum_{w\in W}{y}_{(j+1)w} - \sum_{w\in W}{y}_{jw} \le 0, \forall \left(j\right)\in \{1, 2, \dots .(J-1)\}$$
(13)
$${x}_{ijws}\in \left\{0, 1\right\}, \forall \left(i\right)\in I, \forall \left(j\right)\in J,\forall \left(w\right)\in W,\forall \left(s\right)\in S$$
(14)
$${y}_{jw} \in \left\{0, 1\right\}, \forall \left(j\right)\in J,\forall \left(w\right)\in W$$
(15)
$${pf}_{ihjw}\in \left\{0, 1\right\}, \forall \left(i, h\right)\in I, \forall \left(j\right)\in J,\forall \left(w\right)\in W$$
(16)
$${pb}_{ihjw} \in \left\{0, 1\right\}, \forall \left(i, h\right)\in I, \forall \left(j\right)\in J,\forall \left(w\right)\in W$$
(17)
$${l}_{ijw} \in \left\{0, 1\right\}, \forall \left(i\right)\in I, \forall \left(j\right)\in J,\forall \left(w\right)\in W $$
(18)
$$c\ge 0$$
(19)

The objective of the model is to minimize the cycle time of workstations of the assembly line (1). Constraints 2 ensures that each task is assigned to a worker in a workstation to a position. Constraint 3 ensures that not more than one task is assigned to a position in a workstation. Constraints 4 and 5 ensure that each worker is assigned to a single workstation and a workstation can only have one worker. Constraint 6 checks whether a station has been opened. The constraint 7 allows the task positions (time period) to be opened sequentially. Constraint 8 ensures that all precedence relations among tasks of all assembly lines are satisfied, regarding not only the assignment to different workstations, but also the time period inside the same workstations. Constraint 9 ensures that the workstation global time in every workstation, including forward setup times, backward setup times and processing times of tasks, is under the cycle time. If “i” and “h” tasks are assigned to “s” and “s + 1” positions, respectively, in workstation “j” at worker “w”, it is ensured that \({pf}_{ihjw}\) takes the value of 1 by constraint 10. If the task “i” is the last task at worker “w” in workstation “j”, \({l}_{ijw}\) takes the value “1” by constraint 11. If task “i” is the last job in workstation “j” at worker “w” and job “h” is the first job in the same station, then \({pb}_{ihjw}\) gets the value “1” by constraint 12. The constraint 13 allows the stations to be opened sequentially. Constraints 14–19 are variables.

5 Proposed algorithm

Simulated annealing is an iterative random search algorithm, and it has been used in many optimization problems including ALBP (Li et al. 2016; Roshani and Giglio 2017). Originally, simulated annealing was introduced as an optimization method by Kirkpatrick et al. (1983). In this paper, a simulated annealing algorithm is proposed to ALWABPS that is able to solve problem sizes of real-world environment.

The proposed simulated annealing algorithm is described by the following procedure: SA is initialized with predetermined parameter settings such as initial temperature “Ti”, cooling rate “Cr”, the number of iterations for each temperature level (TL), and the stop criteria as finish temperature “Tf”. SA starts with an initial solution “Si” with the cost, “COi”. “Si” can be obtained with a constructive heuristic using specific or random priority rules for the problem. “COi” is the objective function value for the solution of “Si”. In the case, “Si” value is assigned to the current solution “CS” and the best solution “BS”. The cost of “CS” and “BS” is calculated as “COc” and “COb”, respectively. SA iterations begin with obtaining the initial solution by a constructive heuristic. Using a move operator, a neighbor solution “NS” is generated. The neighbor solution cost “CONS” is calculated and compared to “COc”. Afterward, the changes in the objective function values are calculated by “ΔCO = CONS – COc”. If “CONS” is better than “COc”, then “NS” is assigned to “CS”. If “CONS” is worse than “COc”, there are two different conditions called as the Metropolis criterion. The first condition is accepting “NS” as “CS” with the probability of e−ΔCO/temp (“Tc” is the current temperature and initially “Tc” is equal to “Ti”). The second condition is that “CS” remains unchanged, if the first condition is not met. Thus, accepting worse solutions by the algorithm increases the capability of jumping out of local optima. If “COc” is better than “COb”, then “CS” is accepted as “BS”; otherwise, “BS” remains unchanged. The algorithm repeats this process “TL” times at each temperature level. The parameter “Tc” is slowly decreased as in “Tc = Tc·Cr” by a cooling function until the stopping condition “Tc < Tf” is met. The algorithm will run, until the stopping criteria are satisfied.

Initial solution: In this paper, a worker-oriented strategy to get a feasible solution is presented. The workers are assigned to the workstations. Then, tasks are assigned to workers sequentially, taking the priority value of workers and tasks into consideration. In order to explain the initial solution generation is as follows:

  1. 1.

    Generate a random number between 0 and 1 by uniform distribution for each worker and task for assembly line.

  2. 2.

    Select the workers from highest priority to lowest and assign them to the workstations.

  3. 3.

    Determine the set of assignable tasks for the current workstation j = 1.

  4. 4.

    Sort the tasks in decreasing (priority rule) order.

  5. 5.

    Select the assignable first task “i”, then assign the task to workstation “j”. Otherwise close the workstation “j” and select the next workstation as j = j + 1. If workstation is the last station, go to step 6; otherwise, go to Step 4.

  6. 6.

    If all tasks are assigned to workers, then stop and save the solution as the initial solution. Otherwise, change worker priorities in turn and go to Step 2.

Neighbor generation: New line balance is created by reassign tasks to workers in workstations by using a move operator. In this algorithm, a swap operator is used. The operator ensures that the priority values of the two selected tasks are changed as seen in Fig. 3. This operator has been applied to both tasks and workers. A new neighbor solution is created from the current solution by using the swap operator in each step of the algorithm.

Fig. 3
figure 3

Swap operator for the worker and tasks

Full size image

Objective function: Maximum cycle time duration created in workstations on assembly line worker assignment and balancing problem is used as the objective function to evaluate the quality of solutions generated. The objective of the proposed algorithm for the ALWABPS is minimizing the cycle time for a given number of workers.

Stopping criteria: The proposed algorithm terminates when the Tf or maximum iteration number (Itermax) is obtained.

6 Numerical experiment

The main objective of this study is to introduce and characterize the assembly worker assignment and balancing problem with sequence-dependent setups. With this design, a new mathematical model is presented for the problem. As a solution approach, a metaheuristic approach is proposed. Proposed algorithm is a computationally simple approach, and within a short computational time, it can find good solutions. In this paper, the problem of assembly line worker assignment and balancing problem with sequence-dependent setup times is presented for the first time. There is no study on the problem for comparison with the presented algorithm in the literature. Hence, the results of the proposed simulated annealing algorithm are compared with the presented mathematical model solution on small-size test instances, and solutions of large test instances are enclosed in this paper.

The proposed mathematical model is solved by GUROBI 8.1.1; algorithm is coded by C# and executed on a PC with Intel(R) Core(TM) i7, 2.20 GHz processor and 8.00 GB of RAM. Benchmark data are considered from the ALWABP benchmark data set (Chaves et al. 2007). Test samples are derived through using five experimental factors with low and high levels. These factors are; the number of workers, the number of tasks, the variability of the task execution time, the order strength and the number of tasks that cannot be performed by workers. The details of test instance characteristics are given in Table 1. There are 320 test instances which are named into Heskia, Roszieg, Tonge and Wee-Mag.

Table 1 Characteristics of test instances
Full size table

Each one of the test instance families contains 80 problems. There are 32 task groups and each of them contains 10 test instances. Each task group is defined by the family name and a number between 1 and 8. However, the results of 80 test problems are given in detail for each family. In addition, the test instances presented by Scholl in the literature were used in terms of sequence-dependent setup times. Scholl grouped the sequence-dependent setup times of tasks into 4 groups (0.25, 0.50, 0.75 and 1.00) as seen in Table 2 (Scholl et al. 2013). Setup times used in this paper are 0.25 (low) and 1.00 (high) and available for download at “http://www.assembly-line-balancing.de”. Thus, a total of 640 test instances are presented for ALWABPS.

Table 2 Characteristics of test instances for setup times
Full size table

Each test instance was run with the proposed mathematical model for 900 s (Ritt et al. 2015) and the results were reported. Thus, the model was run a total of 9000 s for just one data set. Since the proposed algorithm is a heuristic method, each instance was run 3 times and best results are reported.

First, Roszieg and Heskia test problem instances were solved, and their results were compared with heuristic algorithm. For Roszieg test instances, although 32 problems were solved optimally, other test problems in the same problem family were solved with small gap values. In all test problems, the proposed algorithm has yielded the same results created by the mathematical model as seen in Table 3. In addition, when the mathematical model and heuristic algorithm results are compared in the Heskia family, it is seen that the heuristic algorithm produces better results in a shorter time than the mathematical model as seen in Table 4. Thus, the efficiency of the proposed heuristic algorithm has been demonstrated and tested on large-scale test problems. Large-scale test problems belonging to Tonge and Wee-Mag families were solved with a mathematical model and algorithm, but the mathematical model could not find any solution despite the removal of the time limitation. The heuristic algorithm results are presented in Table 5.

Table 3 Detailed results obtained by mathematical model and heuristic approach for Roszieg family
Full size table
Table 4 Detailed results obtained by mathematical model and heuristic approach for Heskia family
Full size table
Table 5 Detailed results obtained by heuristic approach for Tonge and Wee-Mag family
Full size table

7 Results and discussion

In this section, the performance of algorithm on some well-known test problems taken from the ALBP literature in terms of solution quality and running time is going to be examined. Since the problem has been presented for the first time in the literature, no comparable study is reported. For this reason, the presented algorithm and mathematical model have been compared on various problems. Algorithm and mathematical model were coded in C# language and GRUBI solver, and both were executed on a PC with Intel(R) Core(TM) i7, 2.20 GHz processor and 8.00 GB of RAM under a Microsoft Windows 10 environment.

Chaves et al. applied a clustering search algorithm and generated ALWABP benchmark test instances (Chaves et al. 2007). Hereby, the presented benchmark data sets, which are composed of four families (Roszieg, Heskia, Tonge and Wee-Mag), have been used in every ALWABP research study. In addition, the test instances presented by Scholl in the literature were used in terms of sequence-dependent setup times. Setup times used in this paper are 0.25 (low) and 1.00 (high) (Yolmeh and Kianfar 2012).

Small-size test instances used in the presented study are Roszieg and Heskia. These problems are used to compare the performance of the proposed algorithm with the mixed integer programming described in Sect. 2. The proposed mathematical model is solved using the GUROBI solver to find the optimal solution of the problems.

In Roszieg problem, 80 test instances with 0.25 setup time were examined, and the mathematical model optimally solved 32 of these problems. 48 of the feasible solutions found with an average Gap value of 3.91%. At the same time, the proposed algorithm yielded the same results compared with the mathematical model in all test instances. In addition, the total CPU time for mathematical model solutions is 49879 s. This solution time is 852 s for the algorithm. For the same test instances, 31 problems were solved optimally with the mathematical model at 1.00 setup time, while 49 test problems produced feasible solutions with a Gap value of 31.69%. Additionally, while the total time spent for mathematical model solutions is 55,428 s, the solution time took 852 s in the algorithm. Furthermore, the same results were found with the mathematical model in all 160 test problems for Roszieg.

In the Heskia problem, all of the maximum times were reached for each test instances defined for the mathematical model. Thus, the mathematical model was able to yield the same result with the algorithm in only 6 of 80 test problems with 0.25 setup time. The algorithm solved the 74 problem by creating better results. The algorithm presented in all 80 test problems with 1.00 setup time and provided better solutions to all problems than the mathematical model.

Thus, the efficiency of the proposed algorithm has been shown on small-sized test problems, and the results of large-sized test problems are given for Tong and Wee-Mag families in Table 5.

8 Conclusions and future research

In this paper, assembly line worker assignment and balancing problem with sequence-dependent setup times is introduced. For this purpose, a mathematical model formulation is developed for the problem. Proposed model is capable of solving some small-size instances optimally using GUROBI solver. As the mathematical model has difficulties finding optimal solutions for the real-life environment problems with a reasonable CPU time, an algorithm based on a simulated annealing is also proposed. To demonstrate the efficiency of the proposed approaches, a computational experiment is conducted. The results show that the proposed algorithm and mathematical model are effective and successful for the ALWABPS. The outcome of the study will help production managers test various possible scenarios for balancing ALWABP with forward and backward setup times and determine a feasible solution within an acceptable computational time for the production line.

According to our best knowledge, the presented paper is the first study for assembly line worker assignment and balancing problem with sequence-dependent setup times. This study is a good starting point for future studies. Future studies might extend the presented problem, like U-shaped assembly line balancing problems with disabled worker and setup time. The problem, which is NP-Hard problem structure, can be solved with exact solution algorithms. For this purpose, lower bound studies might be done to be used in the algorithm. Beside these, some real-life constraints, such as zoning constraints, positional constraints and so on, should be studied. Thus, the applicability of the studies in the literature to real-life problems will be easier.