A multiple-rule based constructive randomized search algorithm for solving assembly line worker assignment and balancing problem

Abstract

This paper proposes a constructive heuristic approach for the assembly line worker assignment and balancing problem (ALWABP). ALWABP arises when the operation time for every task differs according to the worker who executes the task. Since the operation times of tasks vary due to the workers, the problem requires a simultaneous solution to the double assignment problem. Tasks must be assigned to workers and workers to stations, concurrently. This problem is especially proposed in sheltered work centers for the disabled. However, it is not only important for the assembly lines with the disabled, but also for manually operated assembly lines with high labor turnover. In this paper, a multiple-rule based constructive randomized search (MRBCRS) algorithm is proposed in order to solve the ALWABP. Thirty nine task priority rules and four worker priority rules are defined. Performance of the proposed MRBCRS is compared with the relevant literature on benchmark data. Experimental results show that the proposed MRBCRS is very effective for benchmark problems. The results show that the algorithm improves upon the best-performing methods from the literature in terms of solution quality and time.

Introduction

Assembly lines are a special case of flow-line production systems that manufacture standardized commodities in large amounts. In an assembly process, subassemblies and components are put together on the semi-finished assembly which moves from station to station where the parts are added in sequence until the final assembly is produced. The tasks can be executed by workers, robots or both of them. The assembly line concept has been present in various types of industries such as automobiles and other transportation vehicles, household appliances, electronic goods, computers, engines, and etc. In today’s highly competitive market trends, companies need to meet the consumers’ expectations in short time with minimum acceptable costs in order to be sustainable. This is why assembly line concept is so popular among all manufacturing systems. In such environment, an important decision problem, assembly line balancing problem (ALBP) arises.

ALBP is relevant for the allocation of the tasks, each having an operation processing time and a set of precedence relations, among workstations so that a given objective function is optimized and the precedence relations are satisfied. The most common problems used in the literature are Type-1 and Type-2 problems and each type of them belong to the NP-hard class of the combinatorial optimization problems (Karp 1972). Type-1 problems try to minimize the number of workstations hence; the cycle time must be predetermined. In industrial life this type of balancing problems is generally occurred when the designing phase of a new assembly line. On the other hand, Type-2 problems try to minimize the cycle time for a fixed number of workstations. So, this type of balancing problems is more appropriate when redesigning an existing line. Moreover, Type-E problems try to maximize the line efficiency by simultaneously minimizing the cycle time and the number of workstations. Type-F problems seek for a feasible assembly line exists or not for predetermined cycle time and number of workstations. In classic ALBP, it is assumed that every task has a fixed operation time. However, in recent years the traditional ALBP has evolved and it is understood that the fixed operation time assumption is inconvenient for the real life manufacturing systems. Because every worker has unique characteristics such as skill, experience, ability, etc., especially in labor intensive assembly lines a task operation time differs depending on the worker who executes the task. In order to close this gap between the traditional ALBP and real life assembly line systems, a special case of ALBP which is called assembly line worker assignment and balancing problem (ALWABP) is introduced to the assembly line literature.

ALWABP arises when operation times of tasks vary due to the worker who executes the task, and some task-worker incompatibilities are occurred. Since task times are dependent on the worker, the concept of assigning tasks to workers is occurred in additional to the ALBP. In other words, ALWABP is a double assignment problem which includes assigning tasks to workers and workers to stations, simultaneously. Even the traditional ALBP is NP-hard; the ALWABP is also NP-hard. Since the ALWABP is a NP-hard hot research topic, many researchers have proposed various solution techniques to solve the problem. However, none of the proposed solution strategies is proven to be optimal for every benchmark test instance, and the problem is still attractive for researchers. The aim of this paper is to introduce an efficient solution approach for the ALWABP, which tries to minimize the cycle time of the line, in order to contribute satisfactory results to the literature.

The remainder of the paper is organized as follows. In “Literature review” section, the relevant literature is briefly reviewed. In “Formal problem definition and mathematical model” section, the ALWABP is defined and mathematical model of the problem is presented. Later in “A multiple-rule based constructive randomized search algorithm for solving ALWABP-2” section, the proposed constructive heuristic approach is introduced. In “Computational study” section, computational study and results of experiments are stated. Finally, “Conclusions” section concludes the paper and suggests some future work.

Literature review

Miralles et al. (2007) introduced the ALWABP for the first time to the assembly line literature. They proposed the “Sheltered Workcenters for Disabled” (SWD) concept and presented a case study in an assembly line that have a fixed number of workstations. They expressed that disabled workers can be changed with normal operators without any production loss by a logical assignment.

Chaves et al. (2007) applied a clustering search approach and tested it on the generated ALWABP-2 data. Since then, the proposed benchmark data sets, which are composed of four families (Roszieg, Heskia, Tonge and Wee-Mag), have been used in every ALWABP-2 research study. One year later, Miralles et al. (2008) developed a branch-and-bound algorithm for the ALWABP, enabling the solution of small-sized instances. They randomly generated data based on the Jackson problem from the SALBP (Hoffmann 1990) and solved the problem via branch and bound. Then, they integrated a heuristic approach to the branch and bound and applied the proposed method to an industrial case. Because of the problem complexity and the need to solve larger instances, the literature has since then shifted its efforts to heuristic methods.

Guo et al. (2008) proposed a novel flexible assembly line balancing problem with work sharing and workstation revisiting restrictions. They described a two-level solution procedure that uses both genetic algorithm and heuristic method. Solution procedure was applied to industrial data and experimental results showed the effectiveness of the proposed model. Costa and Miralles (2009) incorporates job rotation to the ALWABP. They integrated the training aspects associated with job rotation and ALWABP and offered a mixed integer linear model and a heuristic method in order to cope with to the proposed problem. The results showed that even in very complex contexts such as in SWD, it is possible to improve the welfare of workers by applying job rotation, without important losses in productivity.

Chaves et al. (2009) hybridized clustering search algorithm with the iterated local search in order to solve the ALWABP-2 benchmark data. They obtained good results in reasonable computation times. Moreira and Costa (2009) developed a minimalist tabu search algorithm that tries to be successful at simplicity, flexibility, accuracy and speed. Blum and Miralles (2011) proposed an iterated beam search algorithm for the ALWABP-2 and obtained the best results in the previous literature. Moreira et al. (2012) proposed a simple constructive heuristic approach that was based on 16 task priority rules and 3 worker priority rules and hybridized it with the genetic algorithm. They obtained the fastest results found so far. Zaman et al. (2012) proposed an operator assignment problem in an assembly line with fixed number of workstations and developed a genetic algorithm procedure to tackle with it. Araujo et al. (2012) introduced two new versions of the classic ALWABP which are parallelization and collaboration between different workers. In order to solve the proposed problem, the authors developed an integer programming model and hybridized it with a constructed heuristic algorithm. Mutlu et al. (2013) proposed an iterative genetic algorithm for the ALWABP-2 and obtained satisfactory solutions in short CPU times. Borba and Ritt (2014) developed an interval probabilistic beam search and hybridized it with the branch and bound procedure. Except the Wee-Mag family, they almost achieved the best results. Vila and Pereira (2014) developed a branch and bound procedure with three different remember algorithms by a time constraint of 60, 600 s and with no time constraints. The time constraint of 600 s and no time constraint versions of their approaches acquired the best solutions in the relevant literature.

Sungur and Yavuz (2014) presented a new assembly line configuration that consists of workers whose qualification levels are ranked hierarchically. They proposed a model in which a lower qualified worker can be substituted by higher qualified ones with respect to a cost. They proposed an integer linear programming model in order to tackle with the problem and obtained good computational results. Polat et al. (2015) proposed a two-phase variable neighbourhood search algorithm for solving the ALWABP. They implemented the proposed method both on the benchmark data and a real life problem. The results showed the efficiency of the proposed procedure. Ritt et al. (2015) enhanced the ALWABP by adding stochastic worker availability. The authors presented a two-stage mixed integer program and local search heuristics for dealing with the proposed problem. As a result of computational experiments, they showed that stochastic modeling is a good idea for improving the line’s efficiency and obtained good results for instances of small-sized problems.

Moreira et al. (2015) introduced the Assembly Line Worker Integration and Balancing Problem (ALWBP) which contains assembly lines with normal operators and disabled workers simultaneously. They introduced benchmark data and presented mathematical models and heuristic methodologies in order to solve the newly proposed problem. Guo et al. (2015) proposed a novel harmony search-based memetic optimization model for integrated production and transportation scheduling. They converted the proposed problem into an order assignment problem by using the heuristic approach. The experimental results proved the efficiency of the proposed solution method. More recently, Zacharia and Nearchou (2016) are presented a multi-objective evolutionary algorithm in order to solve the bi-criteria ALWABP. The results showed that the proposed solution procedure as a very satisfactory performance in terms of solution quality.

As it is mentioned above, ALWABP is a relatively new type of the traditional ALBP. It has been studied for almost a decade. There are many research attempts to cope with ALWABP, but none of the related work have obtained optimal solutions for all of the test instances. The aim of this study is to make a contribution to the relevant literature by proposing a new rule based solution procedure in order to obtain good results in short computational times.

Formal problem definition and mathematical model

In this section, we present a formal definition of the ALWABP-2. In analogy with the traditional ALBP; ALWABP also have the same types of problems such as; -1, -2, -E, and -F. In ALWABP-1 the number of workstations is tried to be minimized for a predetermined cycle time; and in ALWABP-2 the cycle time is tried to be minimized for a fixed number of workstations. In the relevant literature, single model of ALWABP-2 with paced line is the most common situation. The following notation is used in the remainder of this paper:

i, j::

task index,

h::

worker index,

s::

workstation index,

N::

set of tasks,

H::

set of available workers,

W::

set of workstations,

c::

cycle time,

$t_{hi}$::

processing time of i when worker h executes it,

${IP}_{i}$::

set of immediate predecessors of i,

$x_{shi}$::

binary variable equal to 1 only if task i is assigned to worker h in station s,

$y_{sh}$::

binary variable equal to 1 only when worker h is assigned to station s.

Fig. 1

Flowchart of the proposed RBCRS heuristic for the ALWABP-2

A mathematical model that was proposed by Miralles et al. (2008) can be written as follows:

$$\begin{aligned} \hbox {Min}&\quad c \end{aligned}$$

(1)

$$\begin{aligned} \hbox {subject to:}&\quad \sum _{h\in H} \sum _{s\in W} {x_{shi} } =1\quad \forall i\in N, \end{aligned}$$

(2)

$$\begin{aligned}&\quad \sum _{s\in W} y{ }_{sh}\le 1\quad \forall h\in H, \end{aligned}$$

(3)

$$\begin{aligned}&\quad \sum _{h\in H} y{ }_{sh}\le 1\qquad \forall s\in W, \end{aligned}$$

(4)

$$\begin{aligned}&\quad \sum _{h\in H} \sum _{s\in W} {s\cdot x_{shi} } \le \sum _{h\in H} {\sum _{s\in W} {s\cdot x_{shj} } } \quad \forall i,j/i\in IP_j , \end{aligned}$$

(5)

$$\begin{aligned}&\quad \sum _{i\in N} t_{hi} \cdot x{ }_{shi}\le c\quad \forall h\in H;\forall s\in W, \end{aligned}$$

(6)

$$\begin{aligned}&\quad \sum _{i\in N} x{ }_{shi}\le M\cdot y_{sh} \quad \forall h\in H;\forall s\in W \nonumber \\ \hbox {with}&\quad y_{sh}\in \left[ {0,1} \right] \quad \forall s\in W,h\in H \nonumber \\&\quad x_{shi}\in \left[ {0,1} \right] \quad \forall s\in W,h\in H,i\in N \nonumber \\&\quad M>\sum _{h\in H} {\sum _{i\in N} {t_{hi} } } \end{aligned}$$

(7)

The objective function given in (1) minimizes the cycle time. The constraint given in (2) ensures that every task i is assigned to a single station s and worker h. Constraints sets given in (3) and (4) expresses that every worker can be assigned to only one station; and in every station there is only one worker, respectively. The set of constraints given in (5) states the precedence relations between tasks i and j, where i is predecessor of j. Constraints sets given in (6) and (7) ensures that every worker h assigned to station s can have more than one task, whenever given cycle time c is not achieved. As cycle time c and $y_{sh}$ are both variables, (6) and (7) are defined separately in order to maintain the model linearity.

A multiple-rule based constructive randomized search algorithm for solving ALWABP-2

In this study a multiple-rule based constructive randomized search (MRBCRS) heuristic is developed in order to solve the ALWABP-2. The heuristic prioritizes tasks and sequentially assigns tasks to the current station in order and then assigns the best suitable worker to that station. This is called station-oriented assignment procedure in the relevant literature (Scholl and Voß 1996). The flowchart of the proposed algorithm is given in Fig. 1.

Initially, benchmark data is read and by using the data cycle time values (lower bound, upper bound, average and expected) are calculated. Assignable tasks are determined according to the precedence relations and then rule based search algorithm, which will be explained in detail later, is applied. After prioritizing tasks, a task is chosen randomly via roulette wheel selection. All assignable tasks are chosen one by one and are put in order sequentially. Then, worker selection rules are applied to the unassigned workers and one of them is selected.

After determining the worker, it must be checked that, is there any task which can be operated by only the selected worker, which is called bottleneck task in this work. If such a situation exists, it must be controlled that if the task is executed on the current station or not. If not, then the solution is infeasible, because none of the remaining workers can operate the bottleneck task. If this is not the case then, the selected worker and tasks, which are a subset of the sequential task list, are assigned to the current station. While choosing tasks from the sequential list, two important points must be considered:

• If there is a task in the list that cannot be executed by the current worker, eliminate that one and go on from the sequential task list.

• Sum of operation times of the assigned tasks, namely station time, cannot exceed the cycle time.

When the feasible solution is obtained, then the current cycle time is reduced and the whole process is applied again. By this way, at every feasible solution cycle time is diminished and finally one feasible solution with the minimum cycle time is gathered when maximum iteration number is achieved.

Rule based task and worker selection strategy

In this study, in order to select one task/worker among tasks/workers in an intelligent manner, we apply 39 rules to the tasks and 4 to the workers. Most of the following rules are collected from Baykasoğlu (2006) and Moreira et al. (2012). Although we will use the notation given above, there are some additional ones in order to express the proposed algorithm:

$IS_{i}$::

set of immediate successors of i,

$S_{i}$::

set of all successors of i,

$P_{i}$::

set of all predecessors of i,

${ UB}_{i }$::

upper bound on the station to which i may be assigned, $UB_i =N+1-\left[ \left( {t_{hi} +\sum _{j\in S_i } {t_{hj} } } \right) /c \right] ^{+}$,

${LB}_{i}$::

lower bound on the station to which i may be assigned, $LB_i =\left[ \left( {t_{hi} +\sum _{j\in P_i } {t_{hj} } } \right) /c \right] ^{+}$.

Some rules are based on the cycle time. Because of the varying operation times, we calculate the expected cycle time $(c_{exp})$ and use it instead of cycle time in the relevant rules. The upper bound $(c_{UB} )$, lower bound $(c_{LB} )$, average $(c_{avg})$ and expected $(c_{exp})$ values of cycle time are calculated as follows:

$$\begin{aligned} c_{UB}= & {} \max \left\{ {\sum {\frac{\max \left\{ {t_{hi} } \right\} }{W},\max \left\{ {t_{hi} } \right\} } } \right\} \quad \forall h\in H,\forall i\in N \nonumber \\\end{aligned}$$

(8)

$$\begin{aligned} c_{LB}= & {} \max \left\{ {\sum {\frac{\min \left\{ {t_{hi} } \right\} }{W},\min \left\{ {t_{hi} } \right\} } } \right\} \quad \forall h\in H,\forall i\in N \nonumber \\\end{aligned}$$

(9)

$$\begin{aligned} c_{avg}= & {} \sum {\left( {avg\left\{ {t_{hi} } \right\} } \right) } /W \quad \forall h\in H \end{aligned}$$

(10)

$$\begin{aligned} c_{\exp }= & {} \frac{1}{6}\left( {c_{UB} +4*c_{avg} +c_{LB} } \right) \end{aligned}$$

(11)

where $\hbox {max}\{t_{hi}\}$, $\hbox {min}\{t_{hi}\}$, $\hbox {avg}\{t_{hi}\}$ are the maximum, minimum and average values of the operation time of task i executed by worker h, respectively.

Task selection rules

Most of the priority rules are based on the task execution times, which is a parameter that depends on the worker assigned to each workstation in our problem. So, to overcome this complication we consider a task’s minimum, average and maximum operation times $(t_i^{\min } ,t_i^{avg} ,t_i^{\max } )$. Task priority rules used in the proposed approach are listed in the following:

• (1) Maximum Longest Processing Time $(\hbox {LPT}_{\max }), t_i^{\max }$;

• (2) Minimum Longest Processing Time $(\hbox {LPT}_{\min }), t_i^{\min }$;

• (3) Average Longest Processing Time $(\hbox {LPT}_{\mathrm{avg}}), t_i^{avg}$;

• (4) Maximum Shortest Processing Time $(\hbox {SPT}_{\max }), t_i^{\max }$;

• (5) Minimum Shortest Processing Time $(\hbox {SPT}_{\min }), t_i^{\min }$;

• (6) Average Shortest Processing Time $(\hbox {SPT}_{\mathrm{avg}}), t_i^{avg}$;

• (7) Greatest Number of Immediate Successors (GNIS), ${\vert }{} { IS}_{i}{\vert }$;

• (8) Greatest Number of Successors (GNS), ${\vert }S_{i}{\vert }$;

• (9) Greatest Number of Immediate Predecessors (GNIP), ${\vert }{} { IP}_{i}{\vert }$;

• (10) Greatest Number of Predecessors (GNIP), ${\vert }P_{i}{\vert }$;

• (11) Random priority (R);

• (12) Smallest Task Number (STN), i;

• (13) Maximum Greatest Ranked Positional Weight (GRPW), $t_i^{\max } +\sum _{i\in S_i }^i {t_j^{\max } }$;

• (14) Minimum Greatest Ranked Positional Weight (GRPW), $t_i^{\min } +\sum _{i\in S_i }^i {t_j^{\min } }$;

• (15) Average Greatest Ranked Positional Weight (GRPW), $t_i^{avg} +\sum _{i\in S_i }^i {t_j^{avg} }$;

• (16) Maximum Greatest Average Ranked Positional Weight (GARPW), $\left( {t_i^{\max } +\sum _{j\in S_i }^ {t_j^{\max } } } \right) /\left( {\left| {S_i } \right| +1} \right)$;

• (17) Minimum Greatest Average Ranked Positional Weight (GARPW), $\left( {t_i^{\min } +\sum _{j\in S_i }^ {t_j^{\min } } } \right) /\left( {\left| {S_i } \right| +1} \right)$;

• (18) Average Greatest Average Ranked Positional Weight (GARPW), $\left( {t_i^{avg} +\sum _{j\in S_i }^ {t_j^{avg} } } \right) /\left( {\left| {S_i } \right| +1} \right)$;

• (19) Maximum Smallest Upper Bound (SUB), $N+1-\left[ {\left( {t_i^{\max } +\sum _{j\in S_i } {t_j^{\max } } } \right) /c_{\exp } } \right] ^{+}$;

• (20) Minimum Smallest Upper Bound (SUB), $N+1-\left[ {\left( {t_i^{\min } +\sum _{j\in S_i } {t_j^{\min } } } \right) /c_{\exp } } \right] ^{+}$;

• (21) Average Smallest Upper Bound (SUB), $N+1-\left[ {\left( {t_i^{avg} +\sum _{j\in S_i } {t_j^{avg} } } \right) /c_{\exp } } \right] ^{+}$;

• (22) Maximum Smallest Upper Bound Divided by the Number of Successors, (S_UB_NS), $UB_i^{\max } /\left( {\left| {S_i } \right| +1} \right)$;

• (23) Minimum Smallest Upper Bound Divided by the Number of Successors, (S_UB_NS), $UB_i^{\min } /\left( {\left| {S_i } \right| +1} \right)$;

• (24) Average Smallest Upper Bound Divided by the Number of Successors, (S_UB_NS), $UB_i^{avg} /\left( {\left| {S_i } \right| +1} \right)$;

• (25) Maximum Greatest Processing Time Divided by the Upper Bound, (G_PT_UB), $t_i^{\max } /UB_i^{\max }$;

• (26) Minimum Greatest Processing Time Divided by the Upper Bound (G_PT_UB), $t_i^{\min } /UB_i^{\min }$;

• (27) Average Greatest Processing Time Divided by the Upper Bound (G_PT_UB), $t_i^{avg} /UB_i^{avg}$;

• (28) Maximum Smallest Lower Bound (SLB), $\left[ {\left( {t_i^{\max } +\sum _{j\in P_i } {t_j^{\max } } } \right) /c_{\exp } } \right] ^{+}$;

• (29) Minimum Smallest Lower Bound (SLB), $\left[ {\left( {t_i^{\min } +\sum _{j\in P_i } {t_j^{\min } } } \right) /c_{\exp } } \right] ^{+}$;

• (30) Average Smallest Lower Bound (SLB), $\left[ {\left( {t_i^{avg} +\sum _{j\in P_i } {t_j^{avg} } } \right) /c_{\exp } } \right] ^{+}$;

• (31) Maximum Smallest Slack (SSLK), $UB_i^{\max } -LB_i^{\max }$;

• (32) Minimum Smallest Slack (SSLK), $UB_i^{\min } -LB_i^{\min }$;

• (33) Average Smallest Slack (SSLK), $UB_i^{avg} -LB_i^{avg}$;

• (34) Maximum Smallest Number of Successors Divided by Task Slack, (S_NS_SLK), $S_i^ /\left( {UB_i^{\max } -LB_i^{\max } } \right)$;

• (35) Minimum Smallest Number of Successors Divided by Task Slack, (S_NS_SLK), $S_i^ /\left( {UB_i^{\min } -LB_i^{\min } } \right)$;

• (36) Average Smallest Number of Successors Divided by Task Slack, (S_NS_SLK), $S_i^ /\left( {UB_i^{avg} -LB_i^{avg} } \right)$;

• (37) Maximum Greatest Task Time Divided by Task Slack (TT_SLK), $t_i^{\max } /\left( {UB_i^{\max } -LB_i^{\max } } \right)$;

• (38) Minimum Greatest Task Time Divided by Task Slack (TT_SLK), $t_i^{\min } /\left( {UB_i^{\min } -LB_i^{\min } } \right)$;

• (39) Average Greatest Task Time Divided by Task Slack (TT_SLK), $t_i^{avg} /\left( {UB_i^{avg} -LB_i^{avg} } \right)$. Maximum Longest Processing Time $(\hbox {LPT}_{max}), t_i^{\max }$.

Worker selection rules

Four worker selection rules are applied in this study:

• (1) Greatest Number of Tasks that can be Executed (GNTE), $\sum {N_i }$;

• (2) Greatest Number of Tasks that can be Executed in Minimum Time (GNTEMT), $\sum {t_i } /\sum {N_i }$;

• (3) Maximum Utilization (MU);

• (4) Random priority (R).

Assignable tasks (workers) are prioritized by using the above rules. Then, a task (worker) is randomly selected within assignable tasks (workers) such that the task (worker) with the higher priority takes the higher selection probability. This strategy is called roulette wheel selection in the literature. The pseudo codes of the proposed rule-based adaptive task search and worker selection mechanisms are illustrated in Algorithms 1 and 2, respectively.

Illustrative example

In order to explain the proposed MRBCRS approach more clearly, a simple numeric example is given in this section. Data used in the illustrative example is collected from a harness production company which manufactures cable networks for automotive sector. The harness production company has two main production areas; cable cutting area and final assembly area. This simple example is gathered from the final assembly area of the most basic product of the company. The assembly line is composed of 3 workstations, 3 workers and 8 tasks. The task operation times per worker and precedence relations are given in Table 1 and Fig. 2, respectively. “X” in Table 1 represents that there are some task-worker incompatibles (i.e. worker 1 and tasks 2 and 4).

Table 1 Task execution times per worker

Fig. 2

Precedence relations of the numeric example

Cycle time values are found by Eqs. (8)–(11). $c_{UB} =\max \left\{ {64,42} \right\} =64$; $c_{LB} =\max \left\{ {38,22} \right\} =38$; $c_{avg} =51.3$; $c_{\exp } =51.2$. For the first iteration we set cycle time equal to the$c_{UB}$. In the beginning there are 2 assignable tasks according to the precedence relations {1, 5}. We apply task priority rules to the candidate tasks. The prioritized values of the two candidates are listed in Table 2.

Table 2 The prioritized values of the candidate tasks

The bold parts are the superior ones for the corresponding rule. Among the all 39 rules, Task 1 overperforms for the 34 rules and Task 5 overperforms for 11 rules. So, there will be a selection with the probabilities:$p_1 =34/(34+11)=0.76$; $p_5 =11/(34+11)=0.24$. We pick a random number between [0, 1] that is 0.65 which corresponds to the Task 1. We put Task 1 to the sequential task list as the first element. All workers can execute Task 1 and the operation times of the Workers 1, 2 and 3 are 8, 6 and 10, respectively. Now, Tasks 2, 3, 4 and 5 are assignable. We apply the priority rules again for the new tasks adaptively and then select one of them randomly by considering the probabilities. Let the newly selected task be the Task 5. Then, the sequential task list contains 1 and 5. Note that Worker 3 cannot execute Task 5. So, at the end of the iteration if Worker 3 is assigned to the current station (station 1), Task 5 should be eliminated and not assigned to the station. Through the iteration, we continue to select tasks according to the rule based method and update the station time. At the end, we obtain the results as shown in Table 3.

Table 3 Task-worker assignment for the first station

Table 3 represents task and worker assignments to the first station. First row shows the sequence of tasks (sequential task list). Rows 2, 3 and 4 illustrates the station times if Worker 1, 2 or 3 are selected, respectively. The sign ’X’ represents that the current worker cannot execute the corresponding task and the ‘–’ sign means that the current worker cannot operate relevant task because of the precedence relations. Moreover, bold numbers illustrate that the cycle time is exceeded. For example, row 4 of Table 3 represents that if Worker 3 is selected for station 1, according to the sequential task list Task 1 must be assigned firstly. Then, task 5 cannot be assigned because Worker 3 is incapable of executing it (“X”). The next task which is Task 3 should be assigned from the sequential task list. Now, the next task in the sequential task list is Task 7. However, it cannot be selected because of the precedence relations. Since Task 7 is an immediate successor of Task 5 and Task 5 is not assigned yet, Task 7 could not be executed (“-”). Then, Task 2 must be assigned according to the list and the station time becomes 62 s. Since the cycle time is 64 s, there are not any assignable tasks in the sequential task list and station must be closed.

Table 4 The prioritized values of the candidate workers

Then, in order to select a worker we apply priority rules to the unassigned workers (see Table 4). According to the Table 4 Workers 1 and 2 are superior for one rule and Worker 3 is superior for three rules. So, the probabilities of selection of the workers are 0.2, 0.2 and 0.6 for Workers 1, 2 and 3, respectively. Let the random number be 0.11, then Worker 1 is selected for the first station. Tasks 1, 5, 3 and 7 and Worker 1 are assigned to the station 1, for the first iteration. After assigning the first station, the whole process is repeated for the remaining stations. At the end of the first iteration an initial solution is obtained. Table 5 illustrates the solution obtained by the end of the first iteration.

Table 5 Initial solution of the numeric example

Table 6 Test instance characteristics

Table 7 Test groups characteristics

Table 5 indicates that Tasks 1, 5, 3 and 7 and Worker 1 are assigned to Station 1; Tasks 2 and 4 and Worker 3 are assigned to Station 2 and lastly, Tasks 6 and 8 and Worker 2 are assigned to Station 3. Station times of the Stations 1, 2 and 3 are 51, 37 and 57 s, respectively. Next, the cycle time has to be decreased and a new solution will be gathered by using new cycle time. This process will be continued until the maximum iteration number, which is 1000 in our case, is achieved.

Cycle time update

The algorithm whose pseudo code is illustrated in Algorithm 3 tries to find the minimum cycle time in the feasible search space. Inertia weight is used in order to decrease cycle time efficiently. In the relevant literature in order to obtain fast convergence, several cycle time update mechanism are applied (Simaria and Pedro 2004; Akyol and Bayhan 2011; Bansal et al. 2011; Mutlu et al. 2013). In this study, the ratio of the current cycle time to the upper bound of the cycle time is used. If this ratio is greater than 75 %, it means that the current cycle time is far away from the minimum cycle time in the feasible search space and it should be decreased drastically. If the ratio is between 75–60 %, then the current cycle time is nearer to the minimum cycle time and the moves should be made more slightly when finding the new cycle time. Lastly, if the ratio is smaller than 0.60, the new cycle time should be obtained by decreasing the current cycle time in very small steps in order not to miss the minimum cycle time.

Computational study

In this section, a computational study of the proposed MRBCRS heuristic is presented. The proposed heuristic is implemented in Microsoft Visual Studio Premium 2012 C# version 11.0.1. The tests were run on a Core 2 Duo i7 2.2 GHz processor and 6 GB main memory running the Windows 7 operating system.

Benchmark data is generated from the corresponding SALBP benchmark data set (Chaves et al. 2007). Test instances are derived by using five experimental factors at a low and a high level. These factors are the number of tasks, the number of workers, the order strength (OS), the variability of the task execution time, and the number of infeasible task-worker pairs ($\hbox {OS} = \hbox {the number of precedence relations}/[\hbox {N}*(\hbox {N}-1)]$). The details of these characteristics are given in Tables 6 and 7. There are 320 test instances which are grouped into four families: Heskia, Roszieg, Tonge and Wee-Mag. Each one of the families contains 80 instances. There are 32 task groups that each of them contains 10 test instances. Each task group is defined by the family name and a number between 1 and 8.

Because the proposed algorithm is a heuristic method, in order to obtain accurate results we run every single instance 10 times (10 replications) for 1000 iterations. It means that we run our program for 3200 times and every run has a maximum iteration number of 1000. Table 8 reports the detailed results of the comparison of our proposed algorithm to the relevant literature.

Table 8 Comparison of the proposed MRBCRS approach to the relevant literature

Table 9 Comparison of the CPU times

The first column represents the benchmark data family, while the second one represents the group number of that family. As it is stated previously, each family group consists of 10 instances, so the table shows the average results of 10 instances for each group of each family. The third column reports the optimum results found so far in the relevant literature under no running time constraints. The rest of the columns represent the referred papers and their solution techniques and results. CPU times of the solution procedures are reported in Table 9. The CPU times of Vila and Pereira (2014) for the Roszieg and Heskia families are not given, because they are not reported in the corresponding paper. Authors claimed that their proposed algorithm solves every instance from the Heskia and Roszieg groups in less than one second. According to Tables 8 and 9, the results show that our proposed MRBCRS algorithm is superior to the all other techniques in general, but a detailed examination may indicate the following findings:

• We obtain the best results for the 75 % of the 320 test instances for the ALWABP-2.

• For the Roszieg family, we report the best feasible solutions for all of the test instances. None of the referred papers have found results close to ours yet.

• For the Heskia family, we obtain the very best results found so far for 6 of the 8 test groups (1, 2, 4, 5, 6 and 7). Also, we get the best results for the remaining groups 3 and 8. These results are pioneer in the relevant literature.

• For the Tonge family, we report the minimum cycle time value that have ever found for the group number 4; and for the rest of the family we obtain the best values found so far in the recent literature. As it can be seen from Table 8, only the last two references could have report the best values for some of the test groups. Except our algorithm, none of the above methods can get optimum solutions for all Tonge groups.

• We could not obtain the best results for all of the Wee-Mag family this may be related to problem size. However, for group 5 our solution is 15.0 which is much more less than the solutions obtained by Chaves et al. (2009) and Moreira and Costa (2009). Also, we obtained better results than Moreira and Costa (2009) for the groups 6, 7 and 8.

• Order strength of the Roszieg family is pretty high, but it contains a limited number of tasks (see Table 6). Similarly, the number of tasks of the Heskia family is also low. From this point of view, it can be claimed that the proposed solution procedure is capable of obtaining much better results for small sized test instances.

• Tonge is one of the large-scaled problem families with order strength of 59.42 and task number of 70. The proposed algorithm performs very well on Tonge family; it finds the very best result so far on test group 4 and obtained the best results on rest of them. None of the studies in the relevant literature could obtain the best results for all groups of the Tonge family. Our work not only gets the best results for all of the groups, but also found a new best solution for the group 4. Moreover, test group 4 includes high percentage of task-worker incompatibilities and high operation times variability (see Table 7). Hence, it can be concluded that our algorithm works well on high task-worker incompatibilities and operation time varibilities.

• Table 9 compares the CPU times of our proposed algorithm to the other approaches in the literature. Note that all of the algorithms were run on different computers with different operating systems and performances. Thus, it is not logical to compare them in terms of the computational time. However, it can be stated that our proposed algorithm performs better results in limited times and obtains minimum CPU times at every data family.

Conclusions

Human factors play an important role in labor intensive assembly lines. Since every worker has his own characteristics, such as skill, ability, morale, experience, etc., it is inappropriate to consider workers as unique. However, in classical assembly line balancing literature, this aspect is disregarded and all workers are assumed to be unique. Consequently, task operation times are assumed to be fixed and do not depend on the workers. But this assumption does not represent the real life assembly systems. In order to relax fix operation times assumption, ALWABP is introduced to the assembly line literature, recently.

ALWABP is a decision problem that occurs when operation times of tasks differs according to the operator. Although the operation time of a task is assumed to be fixed in classical ALBP, it depends on the operator who executes the task in ALWABP. Even though ALWABP is a relatively new problem, it has attracted the scientists’ interest. Many research studies have been made to solve ALWABP in recent years, but one optimum solution method cannot be found so far. Minimizing the cycle time is commonly used as a primary objective in ALWABP literature (ALWABP-2). Even traditional ALBP is NP-hard, this much more complex ALWABP-2 is NP-hard, of course. Because of the complex problem nature, optimum seeking methods are not capable of solving it. So, in this paper a rule based constructive heuristic approach was proposed in order to solve ALWABP-2. In the proposed MRBCRS heuristic, 39 task priority rules and 4 worker priority rules were used to sequence tasks and select workers. In order to evaluate the performance of the proposed solution procedure, it is tested on ALWABP-2 benchmark data which consists of four families, each having 80 test instances. Every test instance was run for 10 replications, and our proposed heuristic was executed for 3200 times, in total. Experimental results showed that our proposed algorithm outperforms all others in the relevant literature. Concisely, the contribution of this study to the relevant literature is that a novel solution procedure for solving ALWABP-2 was presented and the proposed solution procedure was proven to be efficient in terms of solution quality.

Possible future research directions for both the problem and the solution method include; the proposed solution procedure could be applied to a real life assembly line; some other task/worker selection rules may be added to the heuristic approach; and the proposed heuristic could be extended to solve different assembly line balancing problems with different line configurations such as U-shaped line, stochastic worker availability, multi/mixed model assembly lines.