Improved Heuristic Procedure for Mixed-Model U-line Balancing Problem with Fuzzy Times

Abstract

Facing the increasingly competitive market environment, variety of customer needs, and rapidly changing market, more and more assembly lines are switching to U-line and mixed model produced due to the use of just-in-time production principles. Considering that some uncertainties are existing in practical problem, this paper focuses on the mixed-model U-line balancing problem (MMULBP) with processing time and cycle time as fuzzy numbers. An improved heuristic procedure is proposed to solve the problem. The procedures are based on the traditional ranked positional weight method, and some improvements are made on fuzzy number operation and two-direction search for U-line layout, in order to solve the complex practical problem. The results of an experimental study indicate that the proposed procedure is effective.

1 Introduction

Facing the increasingly competitive market environment, variety of customer needs, and rapidly changing market, the traditional straight assembly line cannot meet the demands of the modern society. More and more assembly lines are switching to U-line and mixed model produced due to the use of just-in-time production principles [1, 2].

For the importance of the simple assembly line balancing problem (ALBP), there are numerous researches on ALBP [3–5], but only few literatures focus on mixed-model U-line balancing problem (MMULBP). Sparling and Miltenburg [6] first presented MMULBP and the formulation for the problem, and an approximate solution algorithm for the MMULBP is also proposed. And then, some researches about exact algorithms are also conducted [7, 8], such as goal programming [9], mixed integer linear programming [10], and branch-and-bound algorithms [11]. The simple ALBP falls into the NP hard class of combinatorial optimization problems, and MMULBP is more complex for with larger search space. So, heuristics is an effective way to solve the problem [12].

There are numerous literatures for ALBP, and most of them assume constant and deterministic operation times, but only few studies are reported for solving the fuzzy line balancing problem. Nguyen Van [13] developed a heuristic solution for fuzzy mixed-model line balancing problem. Fonseca et al. [14] proposed modified COMSOAL and ranked positional weighting technique to solve the straight line balancing problem with a fuzzy representation of the time variables. Zhang et al. [15] proposed an effective heuristic for solving type 1 of the fuzzy ULBP. Tsujimura et al. [16] presented a genetic algorithm to solve the traditional straight ALBP with fuzzy operation time. Zacharia and Nearchou [17] presented a new multi-objective genetic algorithm for solving the fuzzy extension of the simple ALBP of type 2.

This paper presents a heuristic for the type 1 mixed-model U-shaped line balancing problem with fuzzy processing times. The rest of the paper is as follows. In Sect. 37.2, the fuzzy MMULBP-1 is discussed and mathematical model is presented. Next, Sect. 37.3 will develop the heuristic solution for fuzzy MMULBP-1. Then, an example problem is solved using the proposed method in Sect. 37.4. Finally, some conclusions are presented in Sect. 37.5.

2 Problem Statement and Formulation

2.1 Problem Statement

In order to reduce the production cost and provide customers with a variety of products in a timely manner, different products or models should be produced on the same line. Mixed-model assembly line balancing problem (MMALBP) can be described as follows: Given P models, the set of tasks associated with each model, the processing time of each task, and the set of precedence relations of tasks for each model, the problem is to assign the tasks to an ordered sequence of stations such that some constraints are satisfied and some performance measures are optimized. The mixed-model U-shaped line balancing problem is an extension of MMALBP with respect to U-shaped line instead of straight line. Three versions of the problem can be divided as follows:

• (I) MMULBP-1 consists of assigning tasks to work stations such that the number of stations is minimized for a given cycle time.

• (II) MMULBP-2 is to minimize the cycle time for a given number of stations.

• (III) MMULBP-E is obtained by maximizing the line efficiency for varying production rates and numbers of stations.

2.2 Assumptions

• 1. Task processing time of each model is given and is a fuzzy number.

• 2. Precedence diagrams for each model are given and can be accumulated into a single combined precedence diagram.

• 3. WIP inventory buffer is not allowed between workstation.

• 4. Parallel workstation is not allowed.

• 5. Common tasks exist between models that must be assigned to the same workstation.

2.3 Combined Precedence Diagram

Different models in mixed-model assembly line usually exists some similar tasks; precedence relations of same tasks in different models are usually similar. According to this character, transform different models into an equivalent single model by taking the union of the nodes and the precedence relations of the diagrams of all the models.

Let G _p be the precedence diagram of model p. G _p has a set of nodes N(p) and of arcs L(p) where

$$ N\left( p \right) = \left\{ {n\left( p \right)_{ 1} ,n\left( p \right)_{ 2} , \ldots } \right\} $$

(37.1)

$$ L\left( p \right) = \left\{ {l\left( p \right)_{ 1} ,l\left( p \right)_{ 2} , \ldots } \right\} $$

(37.2)

The nodes and arcs represent tasks and precedence relations, respectively. If an arc l(p) _h has initial node n(p) _i and terminal node n(p) _j , then the task represented by n(p) _i must be completed before the task n(p) _j .

Precedence relations for a set of models $\hat{P} = \left\{ { 1,{ 2}, \ldots ,P} \right\}$ are represented by directed graphs G ₁, G ₂, …, G _P . Then, we can define a single graph $G_{{\hat{P}}}$ with nodes $N(\hat{P})$ and arcs $L(\hat{P})$ where

$$ N(\hat{P}) = \left\{ {N\left( 1\right) \cup N\left( 2\right) \cup \cdots \cup N\left( P \right)} \right\} $$

(37.3)

$$ L(\hat{P}) = \left\{ {L\left( 1\right) \cup L\left( 2\right) \cup \cdots \cup L\left( P \right)} \right\} $$

(37.4)

For different models, a task may be included in some models and not included in others, so define δ _ip as follows:

$$ \delta_{ip} = \left\{ {\begin{array}{*{20}l} 1 \hfill & {{\text{if}}\,{\text{task}}\,n\left( p \right)_{i} \,{\text{is}}\,{\text{part}}\,{\text{of}}\,{\text{model}}\,p} \hfill \\ 0 \hfill & {\text{otherwise}} \hfill \\ \end{array} } \right. $$

(37.5)

Then, the weighted average processing time of task i ($\tilde{t}_{i}$) in the planning horizon ($\tilde{T}$) is computed as follows:

$$ \tilde{t}_{i} = \frac{{\sum\nolimits_{p = 1}^{P} {Q_{p} \delta_{ip} \tilde{t}_{ip} } }}{{\sum\nolimits_{p = 1}^{P} {Q_{p} } }} $$

(37.6)

where $\tilde{t}_{ip}$ denotes the fuzzy processing time of task i for model p, i = 1, …, N, p = 1, …, P, where N and P are the total number of tasks and models in the problem, respectively. Q _p is the production quantity of model p in the planning horizon.

The cycle time is calculated as follows:

$$ \tilde{C} = \frac{{\tilde{T}}}{{\sum\nolimits_{p = 1}^{P} {Q_{p} } }} $$

(37.7)

So if we use $\tilde{t}_{i}$ as the processing of task i in combined precedence diagram, then we can use the method of single-model assembly line balancing to solve the problem.

2.4 Constraints

• 1. All tasks must be assigned to one workstation.

• 2. Each task is assigned only once, i.e., a task cannot be split among two or more stations.

• 3. The work content in any workstation for any model cannot exceed the cycle time of that model.

• 4. The precedence constraints are not violated on the U-line.

2.5 Problem Formulation

Based on the above assumptions, the MMULBP with fuzzy times of type 1 (MMULBP-1) is formulated as follows:

$$ { \hbox{min} }\,\sum\limits_{p = 1}^{P} {\sum\limits_{k = 1}^{K} {\left( {\tilde{C}_{p} - \sum\limits_{i = 1}^{N} {v_{ipk} \tilde{t}_{ip} } } \right)} } $$

(37.8)

subject to

$$ \bigcup\limits_{k = 1}^{K} {S_{k} } = E $$

(37.9)

$$ S_{i} \cap S_{j} = \phi \quad i,j = 1, \ldots ,K\,i \ne j $$

(37.10)

$$ \sum\limits_{i = 1}^{N} {v_{ipk} \tilde{t}_{ip} } \le \tilde{C}_{p} \quad p = 1, 2, \ldots , \, P\quad k = 1, 2, \ldots ,K $$

(37.11)

$$ \begin{aligned} & \forall x \in S_{i} ,\,y \in S_{j} ,\quad {\text{if}}\,p_{xy} = 1,\,{\text{then}}\,i \le j;\,{\text{or}} \\ & \forall y \in S_{j} ,\,z \in S_{k} ,\quad {\text{if}}\,p_{yz} = 1,\,{\text{then}}\,k \le j. \\ \end{aligned} $$

(37.12)

where

E :

the set of tasks in the line, E = {1,2, …, N}.

K :

the number of workstations.

S _k :

the set of tasks assigned to workstation k, S _k  = {i|task i is assigned to workstation k}.

$\tilde{C}_{p}$ :

cycle time of model p.

$$ v_{ipk} = \left\{ {\begin{array}{*{20}l} 1 \hfill & {{\text{if}}\;{\text{task}}\;i\,{\text{of}}\,{\text{model}}\,p\,{\text{is}}\,{\text{assigned}}\,{\text{to}}\,{\text{station}}\,k} \hfill \\ 0 \hfill & {\text{otherwise}} \hfill \\ \end{array} } \right. $$

(37.13)

$$ p_{ij} = \left\{ {\begin{array}{*{20}l} 1 \hfill & {{\text{if}}\,{\text{task}}\,i\,{\text{is}}\,{\text{performed}}\,{\text{before}}\,{\text{task}}\,j} \hfill \\ 0 \hfill & {\text{otherwise}} \hfill \\ \end{array} } \right. $$

(37.14)

2.6 The Character of U-Shaped Layout

U-shaped layouts with the straight line are mainly distinct in that the entrance and exit are located in the same direction. So we can add or remove workers in assembly line according to the demands. Taking the following problem as example [8], the problem has seven tasks and the precedence diagram is given in Fig. 37.1a. The numbers within and above the nodes represent tasks and the associated task times, respectively. The directed arrow connecting the nodes specifies the precedence relations. When assuming a cycle time of 10, it can be seen that all tasks are performed at five workstations (shown in Fig. 37.1b, the idle time is 13 and the efficiency is 74 %) in traditional assembly line, whereas all tasks are performed at four workstations (shown in Fig. 37.1c, the idle time is 3 and the efficiency is 92.5 %) in U-shaped assembly line. We can see that U-shaped layout can eliminate excess idle time and achieve more balancing situation in this example. Taking tasks 1 and 7 in Fig. 37.1c as example, although tasks 1 and 7 are located at the beginning and end of the line, respectively, they have been processed by the same workstation (workstation 1). This means that the U-shaped layout has great assignment flexibility and balancing efficiency.

Fig. 37.1

Precedence diagram (a), traditional (b) and U-shaped (c) line balancing results

According to the character of U-shaped assembly line, the main difference in assigning the tasks compared to the traditional line is as follows: Straight line only allows assigning tasks according to the arcs direction in the precedence diagram. However, U-shaped line permits assigning tasks according to the arcs direction, or reverse direction, or both arcs direction and reverse direction. So, the U-shaped line balancing problem is much more complicated than the traditional line balancing problem due to the increased search space.

3 The Heuristic Procedure for MMULBP

For the content about arithmetics and ranking fuzzy numbers, the readers can refer to the paper [18].

3.1 Nomenclature

Notation for fuzzy RPWT procedure is given below:

$\tilde{t}\left( i \right)$ :

fuzzy processing time of task i(i = 1, …, n), defined as a triplet (a ₁, a ₂, a ₃)

$\tilde{W}_{i}$ :

fuzzy ranked positional weight of task i

$\widetilde{t}\left( {S_{k} } \right)$ :

fuzzy time required to complete all tasks assigned to workstation S _k (k = 1, …, m)

$\tilde{c}$ :

fuzzy cycle time after assignments

$\tilde{I}_{k}$ :

fuzzy idle time for workstation S _k , (k = 1, …, m)

$\widetilde{t}_{\text{sum}}$ :

total processing time in all workstations

$\tilde{C}_{\hbox{max} }$ :

permitted fuzzy cycle time

$\tilde{\eta }$ :

fuzzy balance efficiency

According to the characters of the problem, we can have the following result:

$$ \tilde{c} = \hbox{max} \left\{ {\widetilde{t}\left( {S_{k} } \right)} \right\}. $$

(37.15)

$$ \widetilde{t}\left( {S_{k} } \right) = \sum\limits_{{j \in S_{k} }} {\widetilde{t}\left( j \right)} ,\quad k = 1, \ldots ,m. $$

(37.16)

$$ \tilde{I}_{k} = \tilde{C}_{\hbox{max} } - \widetilde{t}\left( {S_{k} } \right). $$

(37.17)

$$ \widetilde{t}_{\text{sum}} = \sum\limits_{k = 1}^{m} {\tilde{t}\left( {S_{k} } \right)} ,\quad k = 1, \ldots ,m. $$

(37.18)

$$ \tilde{\eta } = \frac{{\widetilde{t}_{\text{sum}} }}{{m \times \tilde{c}}}. $$

(37.19)

3.2 Fuzzification of RPWT for MMULBP

The proposed procedure for fuzzy MMULBP-1 is based on the RPWT method, and some modifications should be made. We should translate the MMULBP-1 to ULBP-1 based on the methods given in Sect. 37.2.3. Then, we can use the methods for single model to solve the problem. And the fuzzy positional weight for each task, $\tilde{W}_{i}$, can be calculated by summing the processing time of the current task with the processing times of all its successors or predecessors.

$$ \tilde{W}_{i} = \hbox{max} \left\{ {\tilde{t}\left( k \right) + \sum\limits_{{i \in U_{s} \left( k \right)}} {\tilde{t}\left( i \right),\tilde{t}\left( k \right) + \sum\limits_{{j \in U_{p} \left( k \right)}} {\tilde{t}\left( j \right)} } } \right\}. $$

(37.20)

where U _p (k) [or U _s (k)] be the set of tasks which must precede (or succeed) task k, respectively.

The fuzzy operator will be utilized in this calculation for the processing times is fuzzy numbers. And the mean comparison method is used for the comparison [19].

The ranking of tasks based on their positional weights is also very important for the RPWT method in which the tasks are ranked in a decreasing order. And the average height method [18] is used for ranking of triangular fuzzy numbers. Compute the valve H for tasks $\tilde{A}$ and $\tilde{B}$ where $H(\tilde{A}) = (a_{ 1} + a_{ 2} + a_{ 3} ){/}3$ and $H(\tilde{B}) = (b_{ 1} + b_{ 2} + b_{ 3} ){/}3$; if $H(\tilde{A}) > H(\tilde{B})$, then $\tilde{A} > \tilde{B}$.

Whenever a new task is added to a workstation, fuzzy processing times are accumulated using the fuzzy addition operator. And the mean comparison method is used to check whether the station time violates the permitted cycle time or not. If $\widetilde{t}\left( {S_{k} } \right) + \tilde{t}\left( i \right) \le \tilde{C}_{\hbox{max} }$, then task i can be added to the current workstation. If $\widetilde{t}\left( {S_{k} } \right) + \tilde{t}\left( i \right) > \tilde{C}_{\hbox{max} }$ and task i cannot be assigned to the current workstation and a new workstation must be opened to accommodate the task.

3.3 Steps involved in the Procedure

The procedure of the proposed heuristic for MMULBP-1 is presented as follows.

• Step 1: Convert the mixed-model U-line balancing problem into the single-model U-line balancing problem (including the processing time, cycle time, and precedence diagrams) according to Sect. 37.2.3;

• Step 2: Based on the combined precedence diagram, establish each task’s processing time given the cycle time as TFNs;

• Step 3: Establish combined precedence relationships for the problem;

• Step 4: Aggregate fuzzy cycle time and processing time;

• Step 5: Compute the positional weight for each task in the new combined precedence diagram according to Eq. (37.20);

• Step 6: Rank positional weight into List A, and an initial task assignment sequence is obtained. We use the average height method to rank the tasks in a descending order;

• Step 7: Assign aggregated tasks in List A to workstation 1 based on the precedence relations and their positional weight rank, and the fuzzy process times will be accumulated;

• Step 8: Continue to assign the next succeeding ranked task to the workstation, as long as the task fits the precedence relationships and the station times do not exceed the cycle time;

• Step 9: If the station times exceed cycle time with the addition of new task i, then create a new workstation;

• Step 10: Repeat steps 8–9 until all tasks are assigned;

• Step 11: Determine the number of workstations and calculate idle time for each station after final assignment according to Eq. (37.17); compute fuzzy balance efficiency according to Eq. (37.19).

4 Numerical Example and Experiment

A numerical example is used to illustrate the proposed heuristic procedure. Three models, A, B, and C, with demand of Q ₁ = 400, Q ₂ = 200, and Q ₃ = 200, respectively, each day, are simultaneously assembled in a line. For one day, the production time is fuzzy number $\tilde{T}$ = (480 493 507) min. There are 20 tasks in the production, and the precedence diagram for each model is given in Fig. 37.2. The task processing times for the three models are shown in Table 37.1.

Fig. 37.2

Precedence diagram for models A (a), B (b), and C (c)

Table 37.1 Fuzzy processing time of every task in each model

According to Sect. 1.3, we can obtain the combined precedence diagram as shown in Fig. 37.3. By using Eq. (37.6), the weighted average processing time for each task i can be calculated; refer to the column $\hat{t}_{i}$ in Table 37.2. And we also can calculate the fuzzy cycle time, $\tilde{C}_{\hbox{max} } = \left( { 3 6,{ 37},{ 38}} \right)$, according to the Eq. (37.7).

Fig. 37.3

Combined precedence diagram for three models

Table 37.2 Positional weight for the problem

The fuzzy positional weight for the problem can be calculated by Eq. (37.20). The average height of the triangular fuzzy number also can be obtained according to the average height method, and the results are shown in Table 37.2.

Based on the above data, the solution can be found by using the algorithm proposed in Sect. 37.3.3, and the best solution is obtained for 6 workstations. The proposed procedure has the advantages of quick search by using positional weight ranking. For the detailed results, we can refer the readers to Table 37.3. After calculations, the practical fuzzy cycle is $\tilde{c} = \left( { 3 3,\, 3 6,\, 3 9} \right)$, the total processing time in all workstations is $\widetilde{t}_{\text{sum}} = \left( { 1 8 4. 2 5,\, 1 9 9,\, 2 1 3. 7 5} \right)$ by Eq. (37.18), and the line efficiency is (0.787, 0.921, 1) by Eq. (37.19). And we can see that this assembly line with high production rate can meet the demands of the production.

Table 37.3 Results for the problem

5 Conclusion

In this paper, an improved heuristic for MMULBP with fuzzy times is constructed. Computational experiments demonstrated the validity of the proposed procedure. In future studies, we hope to apply the improved heuristic method to extensions of the MMULBP, such as fuzzy MMULBP with multiple objectives. The integration of intelligent methods, for example, heuristic method and ACO algorithms, to MMULBP is also an interesting topic in the future.