# A Mathematical Model and a Simulated Annealing Algorithm for Balancing Multi-manned Assembly Line Problem with Sequence-Dependent Setup Time

Authors: Wucheng Yang; Wenming Cheng
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

Multi-manned assembly lines have been widely applied to the industrial production, especially for large-sized products such as cars, buses, and trucks, in which more than one operator in the same station simultaneously performs different tasks in parallel. This study deals with a multi-manned assembly line balancing problem by simultaneously considering the forward and backward sequence-dependent setup time (MALBPS). A mixed-integer programming is established to characterize the problem. Besides, a simulated annealing algorithm is also proposed to solve it. To validate the performance of the proposed approaches, a set of benchmark instances are tested and the lower bound of the proposed problem is also given. The results demonstrated that the proposed algorithm is quite effective to solve the problem.


---

## Body

## 1. Introduction

As flow-oriented production systems, assembly lines have been widely used in the industrial production of high quantity standardized commodities since Ford developed such a line in 1913. With the usage and spread of assembly lines, a combinatory problem, named assembly line balancing problem (ALBP), has aroused great interest of researchers [1–3]. As the simplest problem of ALBP, the simple assembly line balancing problem (SALBP) is to assign tasks to an ordered sequence of stations such that the precedence constraint and the cycle time constraint are satisfied, and one or more objectives are optimized. In terms of the mathematical complexity, the SALBP is strongly NP-hard, since it can be subsumed as a special case of the bin packing problem, which was being proved as a NP-hard problem [4]. Thus, numerous researchers have been devoted to developing various approaches including exact algorithm, heuristics, and metaheuristics to solve the problem [5, 6].However, when assembly lines are applied to produce large-sized products such as cars, trains, or aircraft, there is enough space to assign two or more workers to each station; the SALBP is no longer suitable since it assumes that only one operator is allowed in one station. In such conditions, the multi-manned assembly line balancing problem (MALBP) is proposed to bridge the gap by resuming that more than one worker is allowed in one station, as shown in Figure1. Another very similar problems is two-sided assembly line balancing problem (TALBP) firstly addressed by [7]. However, the main difference between TALBP and MALBP is that only two workers can be in the same multi-manned workstation and there are preferred operation directions of tasks that restrict the assignments of them to workstations [8]. Thus, the TALBP can be regarded as a special case of MALBP.Figure 1
Configuration examples of a (a) simple assembly line and (b) multi-manned assembly line.
(a)(b)As an extension of SALBP, the MALBP is also NP-hard problem and an increasing number of approaches have been designed to solve the problem. To the best of authors’ knowledge, Dimitriadis [9] is the first researcher to address the MALBP by proposing a two-level heuristic algorithm to study a real case from an automobile assembly plant. In terms of the characteristics of the objective functions, the MALBP can be divided into three versions: MABLP-I to minimize the number of workers/stations, MALBP-II to minimize the cycle time, and MALBP-C to minimize the total production cost.Regarding the MABLP-I, Fattahi et al. [10] firstly developed a MIP model and an ant-colony-based algorithm, and then Yilmaz and Yilmaz [11] corrected their mathematical model. Kellegöz and Toklu [12] modified the branch-and-bound algorithm to minimize the length of the line. Then, the same author developed a priority-rule based constructive heuristic approach for the same problem [13]. Roshani et al. [14] designed a simulated annealing algorithm to solve the problem by simultaneously optimizing the line efficiency, the line length, and the smoothness index. Recently, Kellegöz [15] modified the simulated annealing algorithm by performing on Gantt representations of solutions, and a new MIP model requiring less number of variables and constraints was also developed. Michels et al. [16] proposed a benders’ decomposition algorithm to minimize the number of workers as the primary objective. For other extension of MALBP-I, Chen et al. [17] additionally considered the resource constraint. Şahin and Kellegöz [18] assumed that workers could walk between different stations. Lopes et al. [19] defined the flexible multi-manned assembly lines with flexible station frontiers, in which multiple workers in the same station were allowed to start operating as possible as they can. Although the MALBP-II is a major practice for reconfiguration of the installed assembly lines, research on the MALBP-II is much less than that on the MALBP-I. Roshani and Giglio [20] presented a mathematical model and two simulated annealing-based algorithms for solving the MALBP-II: one solves it directly and another one solves it by repeatedly solving the MALBP-I. Besides the above mentioned two time-oriented objectives, the cost-oriented objective gradually gets more attention since the production cost has been the key to win in competitions among factories. Regarding the MALBP-C, Roshani and Giglio [21] presented a MIP mathematical model to describe the problem. Giglio et al. [22] assumed workers were skilled and a MIP model was also built. Şahin and Kellegöz [23] additionally considered the resource constraint in the MALBP-C; a MIP model and a particle swarm optimization algorithm were both developed to solve it.Furthermore, despite it being certainly an argument whose setups are ubiquitous to the realistic work environment and cannot be ignored for decision-making [24], most researchers still assumed setups as negligible in the literature. This phenomenon may be caused by the following: (i) the influence of setups has been reduced to a large degree by using some advanced manufacturing technologies, such as flexible manufacturing system; (ii) in some real cases, the setup time is ignored because it is too small; (iii) researchers simplified their problem by assuming the setup time as an assignment constraint (e.g., incompatible task). However, there are still many environments where setup time is significant, especially in the case when a station is operated at or near full capacity. The time required to perform a setup activity is called as setup time. Setup time can be classified as sequence-dependent setup time and sequence-independent setup time. In assembly lines, sequence-dependent setup time occurs when the setup time of a task depends on which task was set up on the station prior to operate that task. With respect to the sequence-independent setup time, the sequence-dependent setup time needs more consideration (such as scheduling tasks intra each station). Hence, treating this kind of setup time separately from processing time allows operations to be performed simultaneously and hence improves performance. Furthermore, in multi-manned assembly lines, setups usually cannot be ignored and should be considered more carefully with respect to the traditional single-manned assembly lines. The reason of this is that the large-sized products are often assembled in the former assembly lines. Thus, the setups tend to be large enough with respect to their task time, such as the travel time of operators caused by its moving around the work piece (large-sized) to perform the assigned tasks [25].Andres et al. [26] made the first attempt to solve the assembly line balancing problem with setups (ALBPS); they also proposed a binary linear program model and a greedy randomized adaptive search procedure. Since then, various metaheuristics were proposed for solving the problem [27–29]. Then, Scholl et al. [30] extended the problem by distinguishing the forward and backward setup time; a MIP model and several heuristics were also developed. For other extensions of ALBPS, Nazarian et al. [31] presented a MIP model for the multimodel ALBPS. Sahin and Kellegoz [32] defined the crossover setup time in u-shaped assembly lines. Özcan [33] defined the line-switching setup time in parallel assembly lines; a binary linear program model and a simulated annealing algorithm were proposed to solve it. Akpinar et al. [34] developed a hybrid ant-colony optimization algorithm for solving the mixed-model ALBPS; then, Akpinar and Baykasoğlu [35, 36] extended this problem by distinguishing the forward and backward setup time (mALBPS). Ozcan and Toklu [37] firstly considered the two-sided assembly line balancing problem with setups (TALBPS) and developed a MIP model and a heuristic approach to solve it. Janardhanan et al. [38] also extended the TALBPS to the robotic two-sided assembly lines by proposing a MIP model and a metaheuristic migrating bird optimization algorithm. Aghajani et al. [39] extended the TALBPS to mixed-model two-sided robotic assembly lines, and they proposed a MIP model and a simulated annealing algorithm. Furthermore, Esmaeilbeigi et al. [40] developed three formulations for the ALBPS and designed several possible improvements in the form of valid inequalities and preprocessing approaches. Akpinar et al. [41] improved the model for the ALBPS and mALBPS and an exact procedure and introduced the benders decomposition algorithm.Although a great deal of research has been devoted to various approaches for solving MALBP, according to our best knowledge, no published paper on MALBP in the literature has simultaneously considered forward and backward setup time before.In this study, the MALBP is extended by considering the sequence-dependent setup time to minimize the number of workers as primary objective and minimize the number of stations as secondary objective (MALBPS-I). A mixed-integer programming mathematical model is built to characterize the MALBPS, and a metaheuristic algorithm based on simulated annealing (SA) approach is also developed to solve the problem.The rest of this article is organized as follows. In Section2, the problem to solve is formalized and the MIP model is also presented. Besides, an example of the proposed problem is given. Section 3 is devoted to the description of the proposed SA algorithm. In Section 4, the design of experiment is presented and the results are discussed. The conclusion and future direction are given in Section 5.


## 2. The MALBPS-I

In this section, the MALBPS-I is described in detail and the problem assumptions are listed. Finally, before calculating the lower bound, the proposed MIP formulation is developed.


### 2.1. Problem Definition

A series of multi-manned stations (j=1,…Smax) are utilized on the paced straight assembly lines to produce single model products. A set of workers k=1,2,3,…Wmax are assigned to each multi-manned station. A set of tasks i=1,2,3,…n,m are being assigned to workers and stations to minimize the number of workers and the number of multi-manned stations without violating the cycle time constraint and the precedence constraint. As depicted in Figure 2, worker 1, worker 2, and worker 3 are assigned to multi-manned station 1; worker 4 and worker 5 are assigned to multi-manned station 2. Besides, in such a multi-manned assembly line, the sequence-dependent idle time may occur. For example, task his delayed by its predecessor task i, which is operated by different workers in the same multi-manned station.Figure 2
An example of multi-manned assembly lines with setup times.
(a)(b)In assembly lines, setup time may occur in two ways: the forward and backward setup time. As we can see from Figure2, when a task i is immediately performed before another task p operated by the same worker at the same multi-manned station in the same cycle, then a forward setup occurs for the same work piece to perform task p and a forward setup time fstip is added to the finish time of task p. Furthermore, when a task p is the last task operated by a worker and, in the next cycle, task i is the first task operated by the same worker at the same multi-manned station, then a backward setup occurs for the next work piece to perform task i, and a backward setup time bstpi is added to compute the global station time.Moreover, the sequence-dependent idle time can be used for dealing with setup operations. As depicted in Figure2, the sequence idle time Idle1 occurs in worker 1. Thus, the finish time of task p is calculated as ftp=fti+tp+maxIdel1,fstip. Besides, the station idle time also can be used to deal with backward setup operations. As depicted in Figure 2, the station idle time Idle2 occurs in worker 1 and a backward setup time bstpi also occurs; if Idle2≥bstpi, then constraint (8) is satisfied. Otherwise, the cycle time constraint is violated.


### 2.2. Problem Assumptions

The problem assumptions of the MALBPS-I are listed as below.Task time, setup time, and precedence diagram are deterministic in nature and known in advanceAll stations are equally equipped and all workers are assumed having the same ability to perform any tasksMore than one worker is allowed to be assigned to each stationForward and backward setup time may occur between two adjacency tasksThe buffers or WIP are not allowed


### 2.3. Notations

The notation is given in Table1.Table 1
Notations.
Indicesi, h, p, mA taskkA workerjA multimanned stationnThe total number of tasksM:A big numberCtThe given cycle timefstipThe forward setup time between taski and task pbstipThe backward setup time between taski and task pWmaxThe maximum allowed number of workers in one stationSmaxThe upper bound of number of multimanned stationNmaxThe maximum allowed number of tasks for each workerP(i)Set of all immediate predecessors of taskiPa(i)Set of all predecessors of taskiS(i)Set of all immediate successors of taskiSa(i)Set of all successors of taskiWSkSet of tasks assigned to workerkθA controlling parameter between 0 and 1ParametersISet of tasksI = 1, 2, 3, … n, mKSet of workersK = 1, 2, 3, … WmaxJSet of stationsJ = 1, 2, 3, … SmaxWSSet of positionsWS = 1, 2, 3, … NmaxtiThe task time of taskiDecision variablesxijks1, if taski is assigned to the position s of station (j, k); 0, otherwiseftiThe finish time of taskiwjk1, if at least one task is assigned to station (j, k); 0, otherwiseWSjk1, ifk workers are used in station j; 0, otherwiseIndicator variableszipjk1, if taski is assigned to the immediately predecessor position of task p in station (j, k); 0, otherwiseltijk1, if taski is assigned to the last position of station (j, k); 0, otherwise


### 2.4. The Mathematical Model

The mathematical model proposed by [10, 11, 37] are extended to develop a MIP model for the MALBPS-I in this study. Task m is assumed as a virtue node with zero task time, and it is a final node of the precedence graph; thus, the station, which task m is assigned to, is the final station. The model is given as follows:(1)Min∑jϵJ∑k∈Kwjk+1Wmax×n+1∑j∈J∑k∈K∑s∈WSj⋅xmjks,(2)∑j∈J∑k∈K∑s∈WSxijks=1,∀i∈I,(3)∑i∈Ixijks≤1,∀j∈J,k∈K,s∈WS,(4)∑i∈Ixijks+1−∑i∈Ixijks≤0,∀j∈J,k∈K,s∈WS∧s<Nmax,(5)∑g∈J∑k∈K∑s∈WSNmax⋅g−1+s⋅xhgks−∑j∈J∑k∈K∑s∈WSNmax⋅j−1+s⋅xijks,≤0,∀i∈I,h∈Pi,(6)fti−fth+M⋅1−∑k∈K∑s∈WSxhjks+M⋅1−∑k∈K∑s∈WSxijks≥ti,∀i∈I,h∈Pi,j∈J,(7)ftp−fti+M⋅1−∑k∈K∑s>1s<nxpjks+M⋅1−∑k∈K∑s>0s<nxijks+M⋅1−zipjk,≥tp+fstip,∀i∈I,p∈I∧p≠i,j∈J,k∈K,(8)ftp−fti+Ct+M⋅1−xpjk1+M⋅1−ltijk+M⋅1−zipjk≥tp+bstip,∀i∈I,p∈I,j∈J,k∈K,(9)xijks+xhjks+1≤1+zihjk,∀i∈I,h∈I∧h≠i∧h∉Pi,j∈J,k∈K,(10)xijks−∑h∈I∧h≠m∧h≠i∧h∉Pixhjks+1≤ltijk,∀i∈I,j∈J,k∈K,s∈WS∧s<Nmax,(11)ltijk+xhjk1≤1+zihjk,∀h∈I,i∈I∧i∉Ph,j∈J,k∈K,(12)∑i∈I∧s∈WSxijks−Nmax⋅wjk≤0,∀j∈J,k∈K,(13)∑k∈Kk⋅wsjk−∑k∈Kwjk=0,∀j∈J,(14)wjk+1≤wjk,∀j∈J,k∈K∧k<Wmax,(15)∑i∈I,s∈WSxijks−wjk≥0,∀j∈J,k∈K∧k<Wmax,(16)∑k∈Kwsj+1k≤∑k∈Kwsjk,∀j∈J∧j<Smax,(17)fti≥ti,∀i∈I,(18)fti≤Ct,∀i∈I,(19)xijks∈0,1,∀i∈I,j∈J,k∈K,s∈WS,(20)wjk∈0,1,∀j∈J,k∈K,(21)wsjk∈0,1,∀j∈J,k∈K,(22)zihjk∈0,1,∀i∈I,∀j∈J,k∈K,h∈I,(23)ltijk∈0,1,∀i∈I,∀j∈J,k∈K.Objective function (1) minimizes the number of workers as the primary objective and minimizes the number of stations as the secondary objective. Constraint (2) ensures that each task is assigned to one position s of one station j,k. Constraint (3) ensures that at most one task will be assigned to one position s of one station j,k. Constraint (4) ensures that the position will be opened in increasing order. Constraint (5) ensures that all precedence relations among tasks are satisfied. Constraints (6)–(8) control the sequence-dependent finish time of tasks. If task i and its immediate predecessor task h are assigned to the same station j, then constraint (6) becomes fti−fth≥ti. Constraints (7) and (8) ensure when the forward or backward setup occurs; then, the forward or backward setup time must be considered. When two tasks are assigned to the successive position in the same cycle of a station, then constraint (7) becomes ftp−fti+≥tp+fstip. When two tasks are assigned to the successive position in the next cycle of a station, then constraint (8) becomes ftp−fti+Ct≥tp+bstip. Constraint (9) ensures that if two tasks are assigned to two adjacent positions of station j,k, then zihjk will be equal to one. Constraint (10) ensures that if task i is the last task of station j,k, then ltijk will be equal to one. Constraint (11) provides us to determine the backward setup between the last task and the first task of a station. Constraint (12) ensures that if any task has been assigned to station j,k, then wjk will be equal to one. Constraint (13) ensures that if k workers are assigned to station j, then wsjk will be equal to one. Constraint (14) observes the sequence of workers’ index in a multi-manned station. Constraint (15) ensures that if no task is assigned to station j,k, then wjk will be equal to zero. Constraint (16) observes the sequence of stations’ index in lines. Constraints (17) and (18) ensure that the range of the finish time of task i is between its completion time and the cycle time. Constraints (19)–(23) are the internality constraints. The lower bound of the problem is given in Appendix A.


### 2.5. An Example to Illustrate the MIP Model

The Merten problem [42] with or without setup time are both solved optimally by using the MIP model. The setup time is generated in Section 4 and the detailed data is given in Table 2. The cycle time is set as seven and the Wmax is set as three. As shown in Figure 3, when considering setups, one more worker is needed with respect to the problem without setups.Table 2
The detailed data of the example instance.
Task (i)PiTaskForward/backward sequence-dependent setup time12345671∼10.00/0.190.10/0.110.20/0.230.01/0.060.16/0.230.21/0.250.15/0.162150.23/0.240.00/0.210.04/0.150.11/0.140.14/0.240.17/0.190.04/0.103240.03/0.120.21/0.220.00/0.220.22/0.230.11/0.140.08/0.140.06/0.084130.23/0.230.04/0.120.17/0.180.00/0.160.09/0.100.18/0.210.12/0.185250.16/0.210.18/0.200.21/0.230.18/0.200.00/0.090.03/0.160.17/0.186560.02/0.050.14/0.160.21/0.220.17/0.200.02/0.080.00/0.210.08/0.167450.03/0.110.15/0.200.16/0.190.04/0.100.08/0.160.16/0.190.00/0.17Figure 3
The optimal task assignment to stations of multi-manned assembly lines without setup time (result (a)) and with setup time (result (b)) for Merten problem.
(a)(b)


## 2.1. Problem Definition

A series of multi-manned stations (j=1,…Smax) are utilized on the paced straight assembly lines to produce single model products. A set of workers k=1,2,3,…Wmax are assigned to each multi-manned station. A set of tasks i=1,2,3,…n,m are being assigned to workers and stations to minimize the number of workers and the number of multi-manned stations without violating the cycle time constraint and the precedence constraint. As depicted in Figure 2, worker 1, worker 2, and worker 3 are assigned to multi-manned station 1; worker 4 and worker 5 are assigned to multi-manned station 2. Besides, in such a multi-manned assembly line, the sequence-dependent idle time may occur. For example, task his delayed by its predecessor task i, which is operated by different workers in the same multi-manned station.Figure 2
An example of multi-manned assembly lines with setup times.
(a)(b)In assembly lines, setup time may occur in two ways: the forward and backward setup time. As we can see from Figure2, when a task i is immediately performed before another task p operated by the same worker at the same multi-manned station in the same cycle, then a forward setup occurs for the same work piece to perform task p and a forward setup time fstip is added to the finish time of task p. Furthermore, when a task p is the last task operated by a worker and, in the next cycle, task i is the first task operated by the same worker at the same multi-manned station, then a backward setup occurs for the next work piece to perform task i, and a backward setup time bstpi is added to compute the global station time.Moreover, the sequence-dependent idle time can be used for dealing with setup operations. As depicted in Figure2, the sequence idle time Idle1 occurs in worker 1. Thus, the finish time of task p is calculated as ftp=fti+tp+maxIdel1,fstip. Besides, the station idle time also can be used to deal with backward setup operations. As depicted in Figure 2, the station idle time Idle2 occurs in worker 1 and a backward setup time bstpi also occurs; if Idle2≥bstpi, then constraint (8) is satisfied. Otherwise, the cycle time constraint is violated.


## 2.2. Problem Assumptions

The problem assumptions of the MALBPS-I are listed as below.Task time, setup time, and precedence diagram are deterministic in nature and known in advanceAll stations are equally equipped and all workers are assumed having the same ability to perform any tasksMore than one worker is allowed to be assigned to each stationForward and backward setup time may occur between two adjacency tasksThe buffers or WIP are not allowed


## 2.3. Notations

The notation is given in Table1.Table 1
Notations.
Indicesi, h, p, mA taskkA workerjA multimanned stationnThe total number of tasksM:A big numberCtThe given cycle timefstipThe forward setup time between taski and task pbstipThe backward setup time between taski and task pWmaxThe maximum allowed number of workers in one stationSmaxThe upper bound of number of multimanned stationNmaxThe maximum allowed number of tasks for each workerP(i)Set of all immediate predecessors of taskiPa(i)Set of all predecessors of taskiS(i)Set of all immediate successors of taskiSa(i)Set of all successors of taskiWSkSet of tasks assigned to workerkθA controlling parameter between 0 and 1ParametersISet of tasksI = 1, 2, 3, … n, mKSet of workersK = 1, 2, 3, … WmaxJSet of stationsJ = 1, 2, 3, … SmaxWSSet of positionsWS = 1, 2, 3, … NmaxtiThe task time of taskiDecision variablesxijks1, if taski is assigned to the position s of station (j, k); 0, otherwiseftiThe finish time of taskiwjk1, if at least one task is assigned to station (j, k); 0, otherwiseWSjk1, ifk workers are used in station j; 0, otherwiseIndicator variableszipjk1, if taski is assigned to the immediately predecessor position of task p in station (j, k); 0, otherwiseltijk1, if taski is assigned to the last position of station (j, k); 0, otherwise


## 2.4. The Mathematical Model

The mathematical model proposed by [10, 11, 37] are extended to develop a MIP model for the MALBPS-I in this study. Task m is assumed as a virtue node with zero task time, and it is a final node of the precedence graph; thus, the station, which task m is assigned to, is the final station. The model is given as follows:(1)Min∑jϵJ∑k∈Kwjk+1Wmax×n+1∑j∈J∑k∈K∑s∈WSj⋅xmjks,(2)∑j∈J∑k∈K∑s∈WSxijks=1,∀i∈I,(3)∑i∈Ixijks≤1,∀j∈J,k∈K,s∈WS,(4)∑i∈Ixijks+1−∑i∈Ixijks≤0,∀j∈J,k∈K,s∈WS∧s<Nmax,(5)∑g∈J∑k∈K∑s∈WSNmax⋅g−1+s⋅xhgks−∑j∈J∑k∈K∑s∈WSNmax⋅j−1+s⋅xijks,≤0,∀i∈I,h∈Pi,(6)fti−fth+M⋅1−∑k∈K∑s∈WSxhjks+M⋅1−∑k∈K∑s∈WSxijks≥ti,∀i∈I,h∈Pi,j∈J,(7)ftp−fti+M⋅1−∑k∈K∑s>1s<nxpjks+M⋅1−∑k∈K∑s>0s<nxijks+M⋅1−zipjk,≥tp+fstip,∀i∈I,p∈I∧p≠i,j∈J,k∈K,(8)ftp−fti+Ct+M⋅1−xpjk1+M⋅1−ltijk+M⋅1−zipjk≥tp+bstip,∀i∈I,p∈I,j∈J,k∈K,(9)xijks+xhjks+1≤1+zihjk,∀i∈I,h∈I∧h≠i∧h∉Pi,j∈J,k∈K,(10)xijks−∑h∈I∧h≠m∧h≠i∧h∉Pixhjks+1≤ltijk,∀i∈I,j∈J,k∈K,s∈WS∧s<Nmax,(11)ltijk+xhjk1≤1+zihjk,∀h∈I,i∈I∧i∉Ph,j∈J,k∈K,(12)∑i∈I∧s∈WSxijks−Nmax⋅wjk≤0,∀j∈J,k∈K,(13)∑k∈Kk⋅wsjk−∑k∈Kwjk=0,∀j∈J,(14)wjk+1≤wjk,∀j∈J,k∈K∧k<Wmax,(15)∑i∈I,s∈WSxijks−wjk≥0,∀j∈J,k∈K∧k<Wmax,(16)∑k∈Kwsj+1k≤∑k∈Kwsjk,∀j∈J∧j<Smax,(17)fti≥ti,∀i∈I,(18)fti≤Ct,∀i∈I,(19)xijks∈0,1,∀i∈I,j∈J,k∈K,s∈WS,(20)wjk∈0,1,∀j∈J,k∈K,(21)wsjk∈0,1,∀j∈J,k∈K,(22)zihjk∈0,1,∀i∈I,∀j∈J,k∈K,h∈I,(23)ltijk∈0,1,∀i∈I,∀j∈J,k∈K.Objective function (1) minimizes the number of workers as the primary objective and minimizes the number of stations as the secondary objective. Constraint (2) ensures that each task is assigned to one position s of one station j,k. Constraint (3) ensures that at most one task will be assigned to one position s of one station j,k. Constraint (4) ensures that the position will be opened in increasing order. Constraint (5) ensures that all precedence relations among tasks are satisfied. Constraints (6)–(8) control the sequence-dependent finish time of tasks. If task i and its immediate predecessor task h are assigned to the same station j, then constraint (6) becomes fti−fth≥ti. Constraints (7) and (8) ensure when the forward or backward setup occurs; then, the forward or backward setup time must be considered. When two tasks are assigned to the successive position in the same cycle of a station, then constraint (7) becomes ftp−fti+≥tp+fstip. When two tasks are assigned to the successive position in the next cycle of a station, then constraint (8) becomes ftp−fti+Ct≥tp+bstip. Constraint (9) ensures that if two tasks are assigned to two adjacent positions of station j,k, then zihjk will be equal to one. Constraint (10) ensures that if task i is the last task of station j,k, then ltijk will be equal to one. Constraint (11) provides us to determine the backward setup between the last task and the first task of a station. Constraint (12) ensures that if any task has been assigned to station j,k, then wjk will be equal to one. Constraint (13) ensures that if k workers are assigned to station j, then wsjk will be equal to one. Constraint (14) observes the sequence of workers’ index in a multi-manned station. Constraint (15) ensures that if no task is assigned to station j,k, then wjk will be equal to zero. Constraint (16) observes the sequence of stations’ index in lines. Constraints (17) and (18) ensure that the range of the finish time of task i is between its completion time and the cycle time. Constraints (19)–(23) are the internality constraints. The lower bound of the problem is given in Appendix A.


## 2.5. An Example to Illustrate the MIP Model

The Merten problem [42] with or without setup time are both solved optimally by using the MIP model. The setup time is generated in Section 4 and the detailed data is given in Table 2. The cycle time is set as seven and the Wmax is set as three. As shown in Figure 3, when considering setups, one more worker is needed with respect to the problem without setups.Table 2
The detailed data of the example instance.
Task (i)PiTaskForward/backward sequence-dependent setup time12345671∼10.00/0.190.10/0.110.20/0.230.01/0.060.16/0.230.21/0.250.15/0.162150.23/0.240.00/0.210.04/0.150.11/0.140.14/0.240.17/0.190.04/0.103240.03/0.120.21/0.220.00/0.220.22/0.230.11/0.140.08/0.140.06/0.084130.23/0.230.04/0.120.17/0.180.00/0.160.09/0.100.18/0.210.12/0.185250.16/0.210.18/0.200.21/0.230.18/0.200.00/0.090.03/0.160.17/0.186560.02/0.050.14/0.160.21/0.220.17/0.200.02/0.080.00/0.210.08/0.167450.03/0.110.15/0.200.16/0.190.04/0.100.08/0.160.16/0.190.00/0.17Figure 3
The optimal task assignment to stations of multi-manned assembly lines without setup time (result (a)) and with setup time (result (b)) for Merten problem.
(a)(b)


## 3. Proposed SA Algorithm for MALBPS-I

As an extension of MALBP, the MALBPS is also strongly NP-hard problem. Thus, it is necessary to develop a heuristic or metaheuristic-based algorithm to solve large-sized problem. In this paper, a simulated annealing (SA) approach is proposed for solving the MALBPS-I. Since the SA algorithm was introduced by Kirkpatrick et al. [43] as an iterative random search technique, it has widely been used to solve various combinatorial optimization problems including general assembly line balancing problem [14, 15, 20, 44, 45]. Basically, the SA algorithm is a local search-based metaheuristic, which derives its acceptance mechanism from the annealing process to let the current solution escape from local optima. The detailed procedure of the proposed SA algorithm is given below.


### 3.1. Initial Solution

Considering that the number of stations is uncertain and it is essential to determine the task sequence in the proposed problem, a priority-based coding method is adopted, in which solutions are constructed according to a priority list (PL) of tasks. Then, the initial solution is randomly generated as a sequence between 1 to n by a uniform distribution (1, 2, 3, 4, 5, 6, 7), as shown in Figure 4. To obtain a feasible solution, the assignable task with the lowest priority value is being selected and then it is being assigned to a worker according to some given rules as Section 3.2. Then, the process continues until all tasks are assigned.Figure 4
An example of the coding method.


### 3.2. Building a Feasible Solution

A feasible balancing solution is to determine how to assign works to stations and how to assign tasks to workers without violating the precedence constraint and the cycle time constraint. The procedure to build a feasible solution is given as Algorithm 1 in Figure5. An example is also illustrated in Table 3. The procedure to calculate the finish time (tFTl) of a task i is given as Algorithm 2 in Figure 6. The rules of accepting the task assignment to current multi-manned station are defined as follows (if one of the following conditions (a or b) is fulfilled):Figure 5
The procedure to build a feasible solution for MALBPS-I.Table 3
An example of the procedure to build a feasible balancing solution for the MALBPS-I.
StartStep 1Step 2Step 3Step 4Step 5Step 6Ct=7,PL=1245367,Ns=0, T0=15Ns=1,L=2AT = [1]Select task1Randomly select a worker 1 in station1; then,ft1=t1=1<7;t1+bst11=1.19<7AT = [2,4]Select task2Calculate the earliest start time for all workers as min[1,1] = 1; then, randomly select a worker 2 in station 1,ft2=ft1+t2=6<7;t2+bst22=5.21<7AT = [3,4,5]Select task5Calculate the earliest finishing time for all workers as min[6,6] = 6; then, randomly choose worker 2,ft5=ft2+t5+fst25 = 11.14 > 7; then, check station 1Midle = 4, UB = 1.02, δ=2.98, L = 2, R = 0.543 < Exp (−δ/T0=0.81, accept the assignment; then, Ns=2Ns=2,L=2AT = [3,4,5]Select task5Randomly select a worker 1 in station2; then,ft5=t5=5<7;t5+bst55=5.09<7AT = [3,4,6]Select task3Calculate the earliest start time for all workers as min[5,0] = 0; then, select worker 2;ft3=t3=4;.t3+bst33=4.22<7AT = [4,6]Select task4Calculate the earliest start time for all workers as min[5,4] = 4; then, select worker 2;ft4=ft3+t4+fst34>7; then, check station 2Midle = 2.5, UB = 1.02δ=1.48, L = 2, R = 0.824 < Exp (−δ/T0=0.91, accept the assignment; then, Ns=3Ns=3,L=2AT = [4,6]Select task4Randomly select a worker 1 in station3 then,ft4=t4=3<7;t4+bst44=3.16<7AT = [6,7]Select task6Calculate the earliest start time for all workers as min[3,0] = 0; then, select worker 2.ft6=t6=6<7; t6+bst66=6.21<7AT = [7]Select task7Calculate the earliest start time for all workers as min[3,6] = 3; then, select worker1,ft7=ft4+t7+fst47>7; then, check station 3Midle = 2.5, UB = 1.02δ=1.48, L = 2, R = 0.746 < Exp (−δ/T0=0.91, accept the assignment; then, Ns=4Ns=4,L=2AT = [7]Select task7Randomly select a worker 1 in station4; then,ft7=t7=5<7;t7+bst77=5.17<7All tasks are assignedFigure 6
The procedure to calculate the finish time of tasks.(a)
The number of workers (L) working in current station equals to one.(b)
A generated random number (0<R<1) is not larger than exp−δ/Tc, where δ is the difference between the mean idle time per worker in current station (Midle) and a predetermined upper bound of acceptable idle time (UB):(24)Midle=Ct×l−∑i∈WSltil,(25)UB=θ⋅Ct×THL−∑i∈ItiTHL,(26)THL=∑i∈ItiCt,(27)δ=Midle−UB.


### 3.3. Neighborhood Generation

Neighborhood structures are main approaches to produce new solution in the SA algorithm by moving from a solution to its neighborhood one. For the proposed SA algorithm, the neighborhood structures are designed the same as [14] swap and insert based operators. An example is explained in Figure 7.Figure 7
An example of neighborhood structures for Merten problem.


### 3.4. Objective Function

In this paper, three factors are taken into consideration including the line efficiency (LE), the line length (LN), and smoothing index (SI) for the MALBPS-I. Moreover, these criterions are combined together to build a single objective function by using a minimum deviation method [14]. Let LE0, LN0, and SI0, which are obtained from a initial solution, be the least desirable objective value of LE,LN, and SI. The objective function of the proposed algorithm is formulated as follows:(28)LE=∑i∈ItiNw⋅Ct,(29)LN=Ns,(30)SI=∑j∈JCt−∑i∈SLti2Nw,(31)Minimizef=LEmax−LELEmax−LE0+LNmin−LNLNmin−LN0+SImin−SISImin−SI0,where LEmax, LNmin, and SImin, are, respectively, the most desirable objective value of LE,LN, and SI. For the problem of MALBPS-I, the value of the LEmax is set as 100, LNmin is set as THL/Wmax, and SImin is set as 0.


### 3.5. Description of Proposed SA Algorithm

The proposed SA algorithm starts with an initial solution (Section3.1) in a predetermined temperature Tc (initialized as T0) and navigates around it through some predetermined neighborhood structures (Section 3.3) to find better neighborhood solution. With the searching process of the algorithm, the temperature decreases during the iteration as Tc=α⋅Tc, where α is the predetermined cooling rate. In each temperature, the Tc remains the same for a period of time (TT, the Marko chain length), and then it falls through the algorithm, the probability decreases, and the result converges to the best solution. The neighborhood solution will be accepted as the probability exp−Δf/Tc, where Δf is the difference of fitness between the current solution and its neighbourhood solution. The algorithm stops when the Tc is lower than a predetermined value Tf. Then, output the best found solution. The procedure is given in Figure 8.Figure 8
The procedure of the proposed SA algorithm.


## 3.1. Initial Solution

Considering that the number of stations is uncertain and it is essential to determine the task sequence in the proposed problem, a priority-based coding method is adopted, in which solutions are constructed according to a priority list (PL) of tasks. Then, the initial solution is randomly generated as a sequence between 1 to n by a uniform distribution (1, 2, 3, 4, 5, 6, 7), as shown in Figure 4. To obtain a feasible solution, the assignable task with the lowest priority value is being selected and then it is being assigned to a worker according to some given rules as Section 3.2. Then, the process continues until all tasks are assigned.Figure 4
An example of the coding method.


## 3.2. Building a Feasible Solution

A feasible balancing solution is to determine how to assign works to stations and how to assign tasks to workers without violating the precedence constraint and the cycle time constraint. The procedure to build a feasible solution is given as Algorithm 1 in Figure5. An example is also illustrated in Table 3. The procedure to calculate the finish time (tFTl) of a task i is given as Algorithm 2 in Figure 6. The rules of accepting the task assignment to current multi-manned station are defined as follows (if one of the following conditions (a or b) is fulfilled):Figure 5
The procedure to build a feasible solution for MALBPS-I.Table 3
An example of the procedure to build a feasible balancing solution for the MALBPS-I.
StartStep 1Step 2Step 3Step 4Step 5Step 6Ct=7,PL=1245367,Ns=0, T0=15Ns=1,L=2AT = [1]Select task1Randomly select a worker 1 in station1; then,ft1=t1=1<7;t1+bst11=1.19<7AT = [2,4]Select task2Calculate the earliest start time for all workers as min[1,1] = 1; then, randomly select a worker 2 in station 1,ft2=ft1+t2=6<7;t2+bst22=5.21<7AT = [3,4,5]Select task5Calculate the earliest finishing time for all workers as min[6,6] = 6; then, randomly choose worker 2,ft5=ft2+t5+fst25 = 11.14 > 7; then, check station 1Midle = 4, UB = 1.02, δ=2.98, L = 2, R = 0.543 < Exp (−δ/T0=0.81, accept the assignment; then, Ns=2Ns=2,L=2AT = [3,4,5]Select task5Randomly select a worker 1 in station2; then,ft5=t5=5<7;t5+bst55=5.09<7AT = [3,4,6]Select task3Calculate the earliest start time for all workers as min[5,0] = 0; then, select worker 2;ft3=t3=4;.t3+bst33=4.22<7AT = [4,6]Select task4Calculate the earliest start time for all workers as min[5,4] = 4; then, select worker 2;ft4=ft3+t4+fst34>7; then, check station 2Midle = 2.5, UB = 1.02δ=1.48, L = 2, R = 0.824 < Exp (−δ/T0=0.91, accept the assignment; then, Ns=3Ns=3,L=2AT = [4,6]Select task4Randomly select a worker 1 in station3 then,ft4=t4=3<7;t4+bst44=3.16<7AT = [6,7]Select task6Calculate the earliest start time for all workers as min[3,0] = 0; then, select worker 2.ft6=t6=6<7; t6+bst66=6.21<7AT = [7]Select task7Calculate the earliest start time for all workers as min[3,6] = 3; then, select worker1,ft7=ft4+t7+fst47>7; then, check station 3Midle = 2.5, UB = 1.02δ=1.48, L = 2, R = 0.746 < Exp (−δ/T0=0.91, accept the assignment; then, Ns=4Ns=4,L=2AT = [7]Select task7Randomly select a worker 1 in station4; then,ft7=t7=5<7;t7+bst77=5.17<7All tasks are assignedFigure 6
The procedure to calculate the finish time of tasks.(a)
The number of workers (L) working in current station equals to one.(b)
A generated random number (0<R<1) is not larger than exp−δ/Tc, where δ is the difference between the mean idle time per worker in current station (Midle) and a predetermined upper bound of acceptable idle time (UB):(24)Midle=Ct×l−∑i∈WSltil,(25)UB=θ⋅Ct×THL−∑i∈ItiTHL,(26)THL=∑i∈ItiCt,(27)δ=Midle−UB.


## 3.3. Neighborhood Generation

Neighborhood structures are main approaches to produce new solution in the SA algorithm by moving from a solution to its neighborhood one. For the proposed SA algorithm, the neighborhood structures are designed the same as [14] swap and insert based operators. An example is explained in Figure 7.Figure 7
An example of neighborhood structures for Merten problem.


## 3.4. Objective Function

In this paper, three factors are taken into consideration including the line efficiency (LE), the line length (LN), and smoothing index (SI) for the MALBPS-I. Moreover, these criterions are combined together to build a single objective function by using a minimum deviation method [14]. Let LE0, LN0, and SI0, which are obtained from a initial solution, be the least desirable objective value of LE,LN, and SI. The objective function of the proposed algorithm is formulated as follows:(28)LE=∑i∈ItiNw⋅Ct,(29)LN=Ns,(30)SI=∑j∈JCt−∑i∈SLti2Nw,(31)Minimizef=LEmax−LELEmax−LE0+LNmin−LNLNmin−LN0+SImin−SISImin−SI0,where LEmax, LNmin, and SImin, are, respectively, the most desirable objective value of LE,LN, and SI. For the problem of MALBPS-I, the value of the LEmax is set as 100, LNmin is set as THL/Wmax, and SImin is set as 0.


## 3.5. Description of Proposed SA Algorithm

The proposed SA algorithm starts with an initial solution (Section3.1) in a predetermined temperature Tc (initialized as T0) and navigates around it through some predetermined neighborhood structures (Section 3.3) to find better neighborhood solution. With the searching process of the algorithm, the temperature decreases during the iteration as Tc=α⋅Tc, where α is the predetermined cooling rate. In each temperature, the Tc remains the same for a period of time (TT, the Marko chain length), and then it falls through the algorithm, the probability decreases, and the result converges to the best solution. The neighborhood solution will be accepted as the probability exp−Δf/Tc, where Δf is the difference of fitness between the current solution and its neighbourhood solution. The algorithm stops when the Tc is lower than a predetermined value Tf. Then, output the best found solution. The procedure is given in Figure 8.Figure 8
The procedure of the proposed SA algorithm.


## 4. Computational Results

In this section, there are mainly two folds. Firstly, the test instances are solved by using the MIP model. The model is solved by IBM ILOG CPLEX 12.6.3. Secondly, the test instances in the literature are solved by the proposed SA algorithm, which is coded by MATLAB 2016a software. All experiments are executed on PC with Inter® Core™ i3, 3.4 GHz processor, and 4.0 GB of RAM.The test instances are a group of well-known Talbot data set including 64 problems from [42]. The forward setup time is randomly generated as U0,0.25⋅min∀i∈Iti for problems with low-level setups and U0,0.75⋅min∀i∈Iti for problems with high-level setups. The backward setup time is randomly generated as U0,1.15⋅0.25⋅min∀i∈Iti for problems with problems with low-level setups and U0,1.15⋅0.75⋅min∀i∈Iti for problems with high-level setups. The number of maximum allowed workers is set as two. All the parameters of the proposed SA algorithm are determined through preliminary experiments by using the Taguchi method [46]. To determine the values of parameters including T0,Tf,α,andTT, three test instances are randomly selected as Mansoor (n=11,Ct=63), Kilbridgen=45,Ct=92, and Arcus problem(n=111,Ct=5755). Three levels of T02000,1000,100, three levels of Tf0.001,1,10, and three levels of α0.99,0.95,0.9 are all tested. The value of TT is fixed to n. According to the number of levels and factors, the Taguchi method L9 is used for the adjustment of the parameters. Each test problem is solved ten times, and a performance measureRPD is defined as(32)RPD=fi−fminfmin×100,where fmin and fi are the best solution obtained for a given instance and the objective value obtained for a trial, respectively. According to the results of the statistical analysis, the value of T0,Tf,andα are determined as 1000,0.001, and 0.99, respectively.


### 4.1. The Result of the MIP Model

The results of the MIP model for solving the MALBPS-I with different level setups are given in Table4. The model is coded by OPL language and each test stops until the running time is larger than 7200 seconds. As we can observe from the table, only very limited small-sized (n ≤ 20) test instances can be solved optimally in the time limit. The best found number of workers/stations (Nw/Ns) and the CPU time are also reported. The bold text in the table shows that compared with the problem without setups, the same problem with setups need more stations or workers, and the higher the setups are, the more stations or workers are needed. ∗ means that not optimal results, but the best feasible results found by the model in time limit are reported.Table 4
The results of the MIP model for problems with different level setups.
AuthornCtNo setupLow setupsHigh setupsNsNwTime (s)NsNwTime (s)NsNwTime (s)Merten773[5]<13[6]6.93[6]7.583[5]3.63[5]3.63[5]4.6103[3]13[4]5.63[4]7152[2]12[3]10.42[3]5.7181[2]<11[2]5.11[2]7.1Bowman8204[5]<14[5]4.64[5]3.4214[5]34[5]5.64[5]4.3244[4]14[4]5.24[4]4.5282[3]12[4]46.12[4]32312[3]12[3]31.22[3]23.3Jaeschke976[7]56[8]2.76[8]4.485[6]16[7]8.66[7]22.7104[4]134[5]158.54[5]115.9182[3]12[3]69.73[3]104.3Mansoor11543[4]48.23[4]3367.13[4]4425.4632[3]35.32[4]∗<72002[4]4243.6722[3]29.42[3]1118.12[3]1069.5812[3]15.92[3]730.32[3]1031.5Jackson1194[6]39.64[7]∗<72004[7]∗<7200104[5]34.24[6]∗<72004[6]∗<7200133[4]21.43[4]4271.83[4]6119.2143[4]40.23[4]6312.13[4]3691.5212[3]23.12[3]1578.62[3]3326.4


### 4.2. The Result of the Proposed Algorithm

In this section, the 62 test instances are solved by using the proposed SA algorithm. Each instance is solved ten times and the results are reported in Table5. The Best and Mean mean the best and mean found number of stations/workers (NsNw), respectively. The LB is the optimal value of the ALBP-I from [42], which can be regarded as the lower bound of the number of workers for the MALBP-I. The BM is the optimal result of number of stations/workers (NsNw) for MALBP-I obtained by [10]. The BHA is the best reported number of stations/workers (NsNw) in the literature for the MALBP-I without setups [14, 15]. The LB1 is the lower bound of the number of workers given in this paper for the MALBPS-I.Table 5
The computation results of the SA algorithm.
ProblemCThree different level setup timesZero levelLow levelHigh levelLBBMBHALB1BestMeanG%G1%DbDcLB1BestMeanG%G1%DbDcCPU (s)Jackson (11)964[6]4[6]64[7]4[7]16.6716.670064[7]4[7]16.6716.67001.031054[5]4[5]54[6]4[6]20.0020.000054[6]4[6]20.0020.00001.521343[4]3[4]43[4]3[4]0.000.000043[4]3[4]0.000.00003.161443[4]3[4]43[4]3[4]0.000.000043[4]3[4]0.000.00001.642132[3]2[3]32[3]2[3]0.000.000032[3]2[3]0.000.00000.17Mansoor (11)5443[4]3[4]43[4]3[4]0.000.000043[4]3[4]0.000.00000.516332[3]2[3]32[3]2[3]0.000.000042[4]2[4]0.0033.33001.087232[3]2[3]32[3]2[3]0.000.000032[3]2[3]0.000.00000.028132[3]2[3]32[3]2[3]0.000.000032[3]2[3]0.000.00000.02Mitchell (21)148∼7[8]87[9]7[9]12.5012.500087[9]7[9]12.5012.500053.99158∼7[8]87[8]7[8]0.000.000087[8]7[8]0.000.000059.77215∼5[5]64[6]4[6]0.0020.000064[6]4[6]0.0020.000024.85265∼4[5]54[5]4[5]0.000.000054[5]4[5]0.000.000016.54353∼3[3]43[4]3[4]0.0033.330043[4]3[4]0.0033.33006.12393∼2[3]33[3]3[3]0.000.000033[3]3[3]0.000.000013.56Heskia (28)1388∼5[8]85[8]5[8]0.000.000085[8]5[8]0.000.00002.812055∼3[5]63[6]3[6]0.0020.000063[6]3[6]0.0020.00001.162165∼3[5]53[5]3[5]0.000.000053[5]3[5]0.000.000011.492564∼3[4]53[5]3[5]0.0025.000053[5]3[5]0.0025.00000.063244∼2[4]42[4]2[4]0.000.000042[4]2[4]0.000.00000.063423∼2[3]42[4]2[4]0.0033.330042[4]2[4]0.0033.33000.01Sawyer (30)2713∼8[13]138[13]8[13]0.000.0000138[13]8[13]0.000.0000326.043012∼7[12]127[12]7[12]0.000.0000127[12]7[12]0.000.0000192.793610∼6[10]106[10]6[10]0.000.0000106[10]6[10]0.000.0000125.99418∼6[8]85[9]5.2[9]12.5012.500096[9]6[9]0.0012.5000112.99547∼4[7]74[7]4[7]0.000.000074[7]4[7]0.000.00004.42755∼3[5]53[5]3[5]0.000.000053[5]3[5]0.000.00001.39Kilbridge (45)797∼5[7]84[8]4[8]0.0014.290085[8]5[8]0.0014.29007.64826∼4[6]74[7]4[7]0.0016.670074[7]4[7]0.0016.67000.991106∼3[6]63[6]3[6]0.000.000063[6]3[6]0.000.00000.281384∼3[4]53[5]3[5]0.0025.000053[5]3[5]0.0025.00000.381843∼2[3]42[4]2[4]0.0033.330042[4]2[4]0.0033.33000.02Tong (70)17621∼12[21]2112[21]12[21.1]0.000.000.10.092112[21]12[21.2]0.000.000.20.171108.736410∼7[10]106[10]6[10]0.000.0000106[10]6[10]0.000.0000226.84109∼5[9]95[9]5[9]0.000.000095[9]5[9]0.000.0000133.94688∼4[8]84[8]4[8]0.000.000084[8]4[8]0.000.000088.15277∼4[7]74[7]4[7]0.000.000074[7]4[7]0.000.000070.4Arcus (83)504816∼10[16]1611[16]11.2[16]0.000.00001612[16]12[16]0.000.000027.8585314∼10[14]1410[14]10[14]0.000.00001410[14]10.7[14]0.000.00009.3684212∼8[12]129[12]9[12]0.000.0000129[12]9.4[12]0.000.000013.3757111∼6[11]118[11]8[11]0.000.0000118[11]8.2[11]0.000.00004.6841210∼6[10]107[10]7[10]0.000.0000107[10]7.9[10]0.000.000016.489989∼6[9]97[9]7[9]0.000.000097[9]7[9]0.000.00000.54108168∼5[8]85[8]5.9[8]0.000.000086[8]6[8]0.000.000020.2Arcus (111)575527∼16[27]2717[27]17.7[27.2]0.000.000.20.162718[27]18[27.2]0.000.000.20.16265.2884718∼12[18]1812[18]12[18]0.000.00001812[18]12.1[18]0.000.000075.11002716∼10[16]1610[16]10.9[16]0.000.00001610[16]10.9[16]0.000.0000326.71074315∼9[15]1510[15]10.6[15]0.000.00001510[15]10.5[15]0.000.0000141.51137814∼9[14]149[14]9.2[14]0.000.0000149[14]9.4[14]0.000.0000232170679∼5[9]96[9]6.7[9]0.000.000096[9]6.8[9]0.000.000091.71In order to evaluate the effectiveness of the proposed algorithm, the indexG% represents the gap between the best found number of worker and the lower bound of MALBPS-I and can be calculated as G%=BestNw−LB1/LB1×100. Another index G1% represents the gap between the best found number of worker and the BHANw and can be calculated as G1%=BestNw−BHANw/BHANw×100. Moreover, Db represents the difference between the best and average found number of workers and Dc represents the variance of number of workers found by the SA algorithm in ten times’ runs.The results in Table5 show that the proposed SA algorithm is able to find good solutions to MABLPS-I in a reasonable time. Besides, a summary of computational results is given in Table 6. For all test instances, the average values of G% from LB1 for problems with low-level and high-level setups are 1.23% and 0.98%, respectively. These results show that the proposed algorithm produces very close results to the lower bound. Besides, among 50 test problems in Table 5, the proposed SA algorithm obtained 46 and 47 optimal solutions equal to the lower bound for problems with low-level and high-level setups, respectively. In addition to this, the average value of the LB1 and the average value of best found Nw for problem with high-level setups are both larger than the value for problems with low-level setups. The results show that the setups may increase the number of utilized workers, and the number of workers will be increased with the level of setups. Furthermore, the average value of Db and Dc for all test problems are 0.007 and 0.006, respectively, which show that the proposed SA algorithm has a high rate of convergence and stability.Table 6
Summary of the computational results.
Level of setupsLowHighAverage ofG%1.23%0.98%Average ofG1%5.65%6.32%Percentage of optimal solutions obtained92%94%Average ofLB8.228.22Average ofBHA8.228.22Average ofLB18.408.44Average of best solutions8.488.50Average ofDb0.0060.008Average ofDc0.0050.007


## 4.1. The Result of the MIP Model

The results of the MIP model for solving the MALBPS-I with different level setups are given in Table4. The model is coded by OPL language and each test stops until the running time is larger than 7200 seconds. As we can observe from the table, only very limited small-sized (n ≤ 20) test instances can be solved optimally in the time limit. The best found number of workers/stations (Nw/Ns) and the CPU time are also reported. The bold text in the table shows that compared with the problem without setups, the same problem with setups need more stations or workers, and the higher the setups are, the more stations or workers are needed. ∗ means that not optimal results, but the best feasible results found by the model in time limit are reported.Table 4
The results of the MIP model for problems with different level setups.
AuthornCtNo setupLow setupsHigh setupsNsNwTime (s)NsNwTime (s)NsNwTime (s)Merten773[5]<13[6]6.93[6]7.583[5]3.63[5]3.63[5]4.6103[3]13[4]5.63[4]7152[2]12[3]10.42[3]5.7181[2]<11[2]5.11[2]7.1Bowman8204[5]<14[5]4.64[5]3.4214[5]34[5]5.64[5]4.3244[4]14[4]5.24[4]4.5282[3]12[4]46.12[4]32312[3]12[3]31.22[3]23.3Jaeschke976[7]56[8]2.76[8]4.485[6]16[7]8.66[7]22.7104[4]134[5]158.54[5]115.9182[3]12[3]69.73[3]104.3Mansoor11543[4]48.23[4]3367.13[4]4425.4632[3]35.32[4]∗<72002[4]4243.6722[3]29.42[3]1118.12[3]1069.5812[3]15.92[3]730.32[3]1031.5Jackson1194[6]39.64[7]∗<72004[7]∗<7200104[5]34.24[6]∗<72004[6]∗<7200133[4]21.43[4]4271.83[4]6119.2143[4]40.23[4]6312.13[4]3691.5212[3]23.12[3]1578.62[3]3326.4


## 4.2. The Result of the Proposed Algorithm

In this section, the 62 test instances are solved by using the proposed SA algorithm. Each instance is solved ten times and the results are reported in Table5. The Best and Mean mean the best and mean found number of stations/workers (NsNw), respectively. The LB is the optimal value of the ALBP-I from [42], which can be regarded as the lower bound of the number of workers for the MALBP-I. The BM is the optimal result of number of stations/workers (NsNw) for MALBP-I obtained by [10]. The BHA is the best reported number of stations/workers (NsNw) in the literature for the MALBP-I without setups [14, 15]. The LB1 is the lower bound of the number of workers given in this paper for the MALBPS-I.Table 5
The computation results of the SA algorithm.
ProblemCThree different level setup timesZero levelLow levelHigh levelLBBMBHALB1BestMeanG%G1%DbDcLB1BestMeanG%G1%DbDcCPU (s)Jackson (11)964[6]4[6]64[7]4[7]16.6716.670064[7]4[7]16.6716.67001.031054[5]4[5]54[6]4[6]20.0020.000054[6]4[6]20.0020.00001.521343[4]3[4]43[4]3[4]0.000.000043[4]3[4]0.000.00003.161443[4]3[4]43[4]3[4]0.000.000043[4]3[4]0.000.00001.642132[3]2[3]32[3]2[3]0.000.000032[3]2[3]0.000.00000.17Mansoor (11)5443[4]3[4]43[4]3[4]0.000.000043[4]3[4]0.000.00000.516332[3]2[3]32[3]2[3]0.000.000042[4]2[4]0.0033.33001.087232[3]2[3]32[3]2[3]0.000.000032[3]2[3]0.000.00000.028132[3]2[3]32[3]2[3]0.000.000032[3]2[3]0.000.00000.02Mitchell (21)148∼7[8]87[9]7[9]12.5012.500087[9]7[9]12.5012.500053.99158∼7[8]87[8]7[8]0.000.000087[8]7[8]0.000.000059.77215∼5[5]64[6]4[6]0.0020.000064[6]4[6]0.0020.000024.85265∼4[5]54[5]4[5]0.000.000054[5]4[5]0.000.000016.54353∼3[3]43[4]3[4]0.0033.330043[4]3[4]0.0033.33006.12393∼2[3]33[3]3[3]0.000.000033[3]3[3]0.000.000013.56Heskia (28)1388∼5[8]85[8]5[8]0.000.000085[8]5[8]0.000.00002.812055∼3[5]63[6]3[6]0.0020.000063[6]3[6]0.0020.00001.162165∼3[5]53[5]3[5]0.000.000053[5]3[5]0.000.000011.492564∼3[4]53[5]3[5]0.0025.000053[5]3[5]0.0025.00000.063244∼2[4]42[4]2[4]0.000.000042[4]2[4]0.000.00000.063423∼2[3]42[4]2[4]0.0033.330042[4]2[4]0.0033.33000.01Sawyer (30)2713∼8[13]138[13]8[13]0.000.0000138[13]8[13]0.000.0000326.043012∼7[12]127[12]7[12]0.000.0000127[12]7[12]0.000.0000192.793610∼6[10]106[10]6[10]0.000.0000106[10]6[10]0.000.0000125.99418∼6[8]85[9]5.2[9]12.5012.500096[9]6[9]0.0012.5000112.99547∼4[7]74[7]4[7]0.000.000074[7]4[7]0.000.00004.42755∼3[5]53[5]3[5]0.000.000053[5]3[5]0.000.00001.39Kilbridge (45)797∼5[7]84[8]4[8]0.0014.290085[8]5[8]0.0014.29007.64826∼4[6]74[7]4[7]0.0016.670074[7]4[7]0.0016.67000.991106∼3[6]63[6]3[6]0.000.000063[6]3[6]0.000.00000.281384∼3[4]53[5]3[5]0.0025.000053[5]3[5]0.0025.00000.381843∼2[3]42[4]2[4]0.0033.330042[4]2[4]0.0033.33000.02Tong (70)17621∼12[21]2112[21]12[21.1]0.000.000.10.092112[21]12[21.2]0.000.000.20.171108.736410∼7[10]106[10]6[10]0.000.0000106[10]6[10]0.000.0000226.84109∼5[9]95[9]5[9]0.000.000095[9]5[9]0.000.0000133.94688∼4[8]84[8]4[8]0.000.000084[8]4[8]0.000.000088.15277∼4[7]74[7]4[7]0.000.000074[7]4[7]0.000.000070.4Arcus (83)504816∼10[16]1611[16]11.2[16]0.000.00001612[16]12[16]0.000.000027.8585314∼10[14]1410[14]10[14]0.000.00001410[14]10.7[14]0.000.00009.3684212∼8[12]129[12]9[12]0.000.0000129[12]9.4[12]0.000.000013.3757111∼6[11]118[11]8[11]0.000.0000118[11]8.2[11]0.000.00004.6841210∼6[10]107[10]7[10]0.000.0000107[10]7.9[10]0.000.000016.489989∼6[9]97[9]7[9]0.000.000097[9]7[9]0.000.00000.54108168∼5[8]85[8]5.9[8]0.000.000086[8]6[8]0.000.000020.2Arcus (111)575527∼16[27]2717[27]17.7[27.2]0.000.000.20.162718[27]18[27.2]0.000.000.20.16265.2884718∼12[18]1812[18]12[18]0.000.00001812[18]12.1[18]0.000.000075.11002716∼10[16]1610[16]10.9[16]0.000.00001610[16]10.9[16]0.000.0000326.71074315∼9[15]1510[15]10.6[15]0.000.00001510[15]10.5[15]0.000.0000141.51137814∼9[14]149[14]9.2[14]0.000.0000149[14]9.4[14]0.000.0000232170679∼5[9]96[9]6.7[9]0.000.000096[9]6.8[9]0.000.000091.71In order to evaluate the effectiveness of the proposed algorithm, the indexG% represents the gap between the best found number of worker and the lower bound of MALBPS-I and can be calculated as G%=BestNw−LB1/LB1×100. Another index G1% represents the gap between the best found number of worker and the BHANw and can be calculated as G1%=BestNw−BHANw/BHANw×100. Moreover, Db represents the difference between the best and average found number of workers and Dc represents the variance of number of workers found by the SA algorithm in ten times’ runs.The results in Table5 show that the proposed SA algorithm is able to find good solutions to MABLPS-I in a reasonable time. Besides, a summary of computational results is given in Table 6. For all test instances, the average values of G% from LB1 for problems with low-level and high-level setups are 1.23% and 0.98%, respectively. These results show that the proposed algorithm produces very close results to the lower bound. Besides, among 50 test problems in Table 5, the proposed SA algorithm obtained 46 and 47 optimal solutions equal to the lower bound for problems with low-level and high-level setups, respectively. In addition to this, the average value of the LB1 and the average value of best found Nw for problem with high-level setups are both larger than the value for problems with low-level setups. The results show that the setups may increase the number of utilized workers, and the number of workers will be increased with the level of setups. Furthermore, the average value of Db and Dc for all test problems are 0.007 and 0.006, respectively, which show that the proposed SA algorithm has a high rate of convergence and stability.Table 6
Summary of the computational results.
Level of setupsLowHighAverage ofG%1.23%0.98%Average ofG1%5.65%6.32%Percentage of optimal solutions obtained92%94%Average ofLB8.228.22Average ofBHA8.228.22Average ofLB18.408.44Average of best solutions8.488.50Average ofDb0.0060.008Average ofDc0.0050.007


## 5. Conclusion

In this paper, the type-I problem of balancing multi-manned assembly lines with sequence-dependent setup time is introduced and characterized. A MIP and a simulated annealing algorithm are proposed to solve the problem. To demonstrate the efficiency of SA algorithm and MIP model, a computational experiment is conducted. The results show that the proposed approach is effective and successful for the problem. Furthermore, according to our best knowledge, this paper is the first study on the multi-manned assembly line balancing problem with forward and backward setup time; thus, this paper gives a good starting point for future studies. The following directions may be studied in future: (1) more recent developed metaheuristics and exact algorithm should be developed; (2) other extension and assignment constraints, such as u-shaped lines and zoning constraints should be considered according to the need of real line; (3) more effective procedure to build a feasible solution for the proposed should be developed; (4) tighter lower bound should be given; (5) dynamic job rotation tools can be combined with the proposed problem [47]; (6) multiple-user defined criteria should be considered and a real case should be studied [47].



---

*Source: 8510253-2020-05-23.xml*