Recursive Heuristic Algorithm for Balancing Mixed–Model Assembly Line Type–II in Stochastic Environment

Abstract

Straight assembly line and U-shaped assembly line usually required to be extended and updated in order to solve line balancing problems in the real-world based on computational intelligence. In the literature, most models are presented for solving assembly line balancing (ALBP) assume deterministic processing time. This paper is extended solving ALBP with the stochastic environment using fuzzy theory as one of the main pillars of computational intelligent, it’s called “Worker–Task Stochastic Assigned to Workstation Heuristic” (W–TSAWH) is adopted. The framework can be structured by creating stochastic work environment (SWE) and assigning process. Firstly, SWE is adopted, with three fuzzy logic models as fuzzy skill level, fuzzy work stability and dynamic fuzzy processing time models. These models are used in order to represent uncertainty associated with task processing time in real assembly system. Secondly, a heuristic algorithm is developed to obtain best solution. The algorithm organized by sequence vector, and a mathematical model that assigns task and worker that subjected to some constraints into constant number of workstations to minimize cycle time. Finally, the performance validation of the methodology is proved using a numerical example.

1 Introduction

The early production began by assembly of one unit of production. The assembly line which have the procedure of specific product produced on the line, which operate manually or with the aid of instruments for handling or completing the procedure of product assembly. A typical assembly line consists of a series of successive workstations, each of which contains some work elements known as tasks. Each performed in a crisp value called task processing time. In addition, the balancing problem refers to equality of output of each successive operation in the sequence of the assembly line. If they are all equal, then it is a condition of perfect balance can be considered to be smooth [1]. The assembly line balancing problem (ALBP) is one of a class problems which are known to be computationally difficult (NP-hard problems), basically that based on the assignment the set of tasks into given workstations in a way that not violating precedence constraint among tasks and some other constraints. The assignment of tasks to workstations is done to insure that the assembly can meet the demand rate. Thus each workstation is given a fixed amount of time to complete its work, max of them called cycle time [1,2,3]. Most common class of ALBP is based on objectives are usually classified into four categorize: Minimize the number of workstations for given cycle time is (Type–I), this type is utilized for installing a new assembly line; Minimize the cycle time of the assembly line for given number of workstations is given (Type–II), this is applied when changes occur for improving of an existing assembly line [multi-objective fuzzy assembly line balancing using genetic algorithm]; Minimizing both cycle time and number of workstation simultaneously is given (Type–E); Generating a feasible solution while both cycle time and number of workstation is given (Type–F) [4].

Today’s increasingly competitive global market climate forces manufacturing companies to improve productivity plans with the goal of increasing efficiency and effectiveness. In this direction, an efficient assembly line considered as the most important in developing assembly line [3]. Therefore. assembly line also can categorized into other classification according to shape layout into two versions: straight assembly line balancing (SALB), that allocating assembly tasks only predecessors are already allocated to straight workstations, and U-shaped (UALB), which allocating assembly tasks whose predecessors and successors are already allocated to workstations along the assembly line with respect to the solution efficiency can be estimated to be better for the same number of workstations due to available more options of assignable tasks than straight version of the assembly line [3, 5, 6]. Figure 1 illustrates the two versions of the assembly line according to layout.

Fig. 1.

Tasks arrangement in versions of assembly line ((a) straight assembly line (b) U-shaped assembly line) [7]

However, the task processing time of almost assembly line was considered a crisp, that mean task may be completed in standard time and this may lead to delay in specified cycle time and in product completion [8]. Whilst, in practical there is a high uncertainty, ambiguity, and vagueness in processing time of tasks are performed by worker. This case of worker, significant variation may result from worker fatigue, non skilful workers, motivations of the employees, lack of training, etc. also varying production rate may result from machine breakdowns. To incorporate process time uncertainty in ALBP, task processing time may be treated by estimating uncertain data [1]. Computational intelligent technique (CI) proved their abilities to reach more efficient solutions for real-world problems. The main aspect of real–world problem is imprecise and uncertain data, thus, the input data must be only estimated as within uncertainty due to both machine and worker factors. This uncertainty can be organized a fuzzy number to reduce errors of uncertainty. Therefore, stochastic nature of task processing time is to be considered [9].

2 Relevant Literature

There are numerous literatures have been reviewed studies for solving ALBP, and most of them related with solving ALPB assuming that the processing time as a crisp, but others reported with fuzzy processing time, some of them were summarized as the following: Samah and AllaEldin (2020) [10] presented a novel methodology for solving a mixed-model assembly line balancing problem using a worker-assigned heuristic workstation (W-TAWH) model to address both SALB and UALB versions. The proposal enhanced performance measures depending on the number of suitable workers and tasks that assigned to the given workstation. Finally, these measures are integrated and optimized by employing the desirability function approach for optimization. Salehi et al. (2017) [6] proposed a new hybrid fuzzy interactive approach to solve a new multi-objective ALB problem and it was formulated in a fuzzy environment. Two examples and case studies were adopted for experimental study to demonstrate the effectiveness of the solution and proved the notability of the proposed approach compared with benchmark approaches in the literature. Alavidoost et al. (2016) [3] introduced a novel bi-objective fuzzy mixed-integer linear programming model to represent uncertainty associated with task processing time, the proposed model considered to optimize two conflicting objectives (minimizing cycle time and workstations number) simultaneously. A numerical example, besides benchmark study was considered over some test problems to assess the performance of the proposed solution. The results show that the proposed model can be utilized not only in ALBP but also it would be helpful to handle any practical multi-objective linear programming. Anthony et al. (2016) [9] proposed fuzzy logic model for balancing a single model assembly line. The fuzzy toolbox was used in the analysis of the data, these data obtained from a tricycle assembly line. Results show that the efficiency of the assembly line increased from 88.1% to 92.4%, while idle time was reduced by 56.5% as well as reduction of the bottleneck. Yilmaz et al. (2016) [11] used a genetic algorithm and heuristic priority rule to solve stochastic two-sided U-shape assembly line balancing problem The proposed procedure aims to minimize the number of positions and minimize number of workstations for given cycle time. Finally, to validate the efficiency of the proposed algorithm a comparison study for test problems taken from the literature is conducted. The obtained results demonstrate that the proposed algorithm performs well. Zeqiang and wenming (2015) [12] improved a heuristic procedure based on traditional ranked positional weight method to solve mixed –model U-line balancing problem (MMULBP) with two parameters are task processing time and cycle time as fuzzy numbers. The results obtained of an experimental study show that the improved procedure is effective. Zacharia (2012) [13] proposed a fuzzy of the simple assembly line balancing problem type–II. The task processing times formulated as triangular fuzzy membership functions. A multi-objective genetic algorithm is presented for solving FALBP-II. Fitness function represented as a total fuzzy cost function with the weighted sum of multiple fuzzy objectives. These weights were studied for three different methods (fixed, random, adaptive weight). The aim of this work is to solve the assembly line balancing problem which consists of SALB problem and UALB problem in real-world. The organization of the study is described as follows. In the next section, formulate the W-TSAWH model, then proposed a solution approach to solve this problem. The next numerical example is used to demonstrate the effectiveness, validity, and reality of the developed approach. Finally, conclusion and future works are given.

3 Formulation of W–TSAWH Problem

In this study, the research effort towards exploitation the features of the ALBP to assign a proper task and best available worker that subjected to a set of constraints into suitable fixed workstation numbers as a consequence reducing the cycle time in stochastic environment. In another words, the aim is to increase the efficiency of overall throughput of the assembly line. The extension of assembly line balancing model type–II (W-TSAWH) developed to achieve a satisfactory best or near best solution with respect to both straight and U-shaped models. Generally, the framework is to solve W-TSAWH problem described by designing three–phases. Firstly, is devoted to convert deterministic task processing time into stochastic using fuzzy theory. Whereas the second and third are dedicated to developing an inclusive mathematical model for recursive algorithms for assigning processes for both tasks and workers, with the main objective to minimize workstations cycle time in both straight and U-shaped assembly line models. Figure 2 demonstrates the framework of W-TSAWH. The developed algorithm is subject to the following constraints:

• 1. Task assigned to workstation if the precedence relationship not violated.

• 2. Every task processing time is considered in stochastic work environment.

• 3. The time of set-up, loading, unloading material are involved in the processing time.

• 4. The number of task processing times allocated to each workstation must not exceed the cycle time specified.

• 5. Given workstations number must be identical with worker number (it guarantees that each worker will be allocated only to one the workstation).

Fig. 2.

The framework of the developed W–TSAWH approach.

3.1 Phase 1: Stochastic Work Environment

To ensure taking into account the uncertainty of processing time in real – assembly systems, this phase intended to response the need for a comprehensive capability for work conditions in which fuzzy parameters such as skill level and work stability. The traditional methods for solving assembly line balancing depend on deterministic time. This study presented approach to address balancing assembly line under stochastic work environment, it is devoted to estimating data according to human intuition to cover variability and uncertainty in task processing time. This phase strictly interferes with customers satisfied in the form of due date that the most distinctive quality of modern industry. Data required to be collected so as to structure the integral framework for the developed model are related data which includes product data, worker data, and machine data. Typically, at each workstation there are variables considered as a main because inherent stochastic in assembly process. In this study, the variables can be categories into worker skills that assigned to perform tasks and work stability as important curability measures associated with nature of the complete time of tasks for uncertain work environment. According to author’s knowledge, such variables are not reported in existing literature. Thus, this study proposes stochastic work environment (SWE). The basic idea of this module is treating the related input data utilizing fuzzy logic theory, while, the output is representing process time as stochastic output. However, the outline of SWE organized by developing three fuzzy logic models. These are fuzzy skill level (FSL) model, fuzzy work stability (FWS) model, and dynamic fuzzy processing time (DFPT) model.

Fuzzy Skill Level (FSL) Model

FSL model is structured to estimate skill level for each worker (SLk) measure on an assembly line to satisfy the constraint (2) that says a given task in difference processing time due to different worker efficiency in the form of processing time the change amount of time due to the diversity in work accumulated experience according to employment period (EP) and training period (TP) variables, which are structured according to standard classification of occupation. The output variable (SL) is controlled using 25 fuzzy rules reasoning according to general formula (IF <condition> THEN <result>). Finally, the Mamdani interference method was used to fuzzy logic of FSL model in order to get crisp value (SLk) value. Figure 3 depicted the outline of the FSL model.

Fig. 3.

Outline of the developed FSL model.

Fuzzy Work Stability (FWS) Model

FWS model allows taking into account the degree of available of worker (AWk) and available of machine (AM) as fuzzy input variables in order to estimate work stability for each worker (WSk). These variables can be formulated with relative importance which defined according to expert knowledge, the use of FWS was proposed according to the following procedure:

• Step-1: Calculate the working ratio (WRk) for each worker by using Eq. (1).

  $${\text{WRk}} = \left( {{\text{WDk}}} \right)/\left( {{\text{TWD}}} \right)$$

  (1)

  Where:

  • $WD_{k}$: Working days of worker (k)

  • $TWD$: Total working days

• Step-2: Calculate the ascertain ratio (ARk) for each worker by using Eq. (2).

  $${\text{ARk}} = \left( {{\text{ATk}}} \right)/\left( {{\text{TTL}}} \right)$$

  (2)

  Where:

  • $AT_{k}$: Assigned tasks of worker

  • $TTL$: Total tasks on assembly line

• Step-3: Calculate the availability of worker (AWk) which results from average of two percentages are working ratio, and ascertain ratio.

  While the availability of machine (AM) is the actual time that the machine is capable of production as a percent of total planned production time and formulated in Eq. (3).

  $${\text{AM}} = {\text{RT}}/{\text{PPT}}$$

  (3)

  Where.

  • AM: available of machine

  • RT: run time

  • PPT: planned production time

The input/output variables are fuzzified trapezoidal membership function shaped. Finally, all computation procedures of the inference process is achieved by mamdani inference method. Figure 4 denote the outline of the FWS model.

Fig. 4.

Outline of the developed FWS model.

Dynamic Fuzzy Processing Time (DFPT) Model

Dynamic Fuzzy Processing Time (DFPT) model is designed to treat the difference in max value of processing time (PT). When a max value in each fuzzy set turns, dynamic process is developed. The output of FSL model and FWS model (SL & WS) are used as input variables for DFPT model. Input/output variables are fuzzified into set of triangular and trapezoidal membership function shape in range from 0–1. Finally, a fuzzy inference procedure is similar to those used in FSL and FWS models in order to estimate PTik of task (i) needed by worker (k). Figure 5 denote the outline of the FWS model.

Fig. 5.

Outline of the developed DFPT model.

3.2 Phase 2: Assigning Tasks to Workstation

The assignment aims to minimize the cycle time for balancing assembly tasks along assembly line. Thus, task- heuristic recursive algorithm (T-HRA) is developed to achieve this aim. The evolved algorithm’s search process is based on achieving maximum equality in total execution time along the assembly line, in such a manner that maximum equality in partition sequence vector (SV) data is achieved for all workstations. Under this consideration, there was lower variation in workstation time between workstations, as shown in Fig. 6. For further details, the following steps will summarize the procedure of the developed algorithm.

• Step 1:- To address the imposed precedence relationship constraint between all of tasks, a positional weight priority rule of the form SV was used to rank the set of tasks. In the academic scene, a set of heuristic priority rules is used in forming SV to rank the set of tasks according to their priority function and precedence relationships among them. In this study, the maximum total number priority rule for SALB and UALB was used and its corresponding equation is presented in Eq. (4) & (5), respectively.

  $${\text{P}}_{{{\text{tp }}\left( {{\text{max}}} \right)}} { } = {\text{max }}\left\{ {\sum\nolimits_{{{\text{i}} \in {\text{p}}}} {\text{i}} } \right.$$

  (4)
  $${\text{p}}_{{{\text{maxf }}\left( {\text{c}} \right)}} = {\text{ max }}\left\{ {{\text{number of task}} \in { }\upmu _{{\text{c}}}^{{\text{s}}} ,\,{\text{number of tasks }} \in\upmu _{{\text{c}}}^{{\text{p}}} { }} \right\}$$

  (5)

• Step 2:- Segmentation the sequence vector into A & B parts by dividing the given workstations by 2.

• Step 3:- Calculate workstation ratio (WR), that display the ratio of the given workstations that allocated to each sub-vector, that subject to the impost condition, that say, WR ≤ 1.

• Step 4:- Calculate time ratio (TR), displays the set of data ratio assigned to each part (A & B), and the idea is based on dividing the SV into two parts called sub-vector, each one can be represented by the left and right positions (PL & RP), as formulated in Eq. (6).

  $${\text{ TR}} = \sum\nolimits_{{{\text{j}} = {\text{PL}}}}^{{\text{i}}} {{\text{APT}}_{{\text{j}}} } /\sum\nolimits_{{{\text{j}} = {\text{i}} + 1}}^{{{\text{Pr}}}} {{\text{APT}}_{{\text{j}}} }$$

  (6)

• Step 5:- Checking of the condition that says (TR ≤ WR), if yes, a new position (i + 1) must be added, if not, continue to step (6), which ensures that the amount of time allotted for the sub-vector has the least variation.

• Step 6:- The last position (i) must be deleted from the sub-vector (A), to ensure that the TR ≤ WR condition not violating.

• Step 7:- All steps from (1–6) should be repeated until the rest of the given workstations become 1, in another words, each sub-vector which represents a workstation that has a number of tasks assigned to it.

Fig. 6.

Flowchart of the recursive algorithm for assigning tasks to workstations.

3.3 Phase 3: Assigning Worker to Workstation and Evaluation

The assignment is aimed for minimizing the cycle time for worker assembly line balancing problem. Thus, worker - heuristic recursive algorithm (W-HRA) is developed to achieve this goal. Workers assigned to given workstations have been summarized in the following procedure and can be shown in Fig. 7.

• Step 1:- Compute workstation time (WT), as shown in Eq. (7), it shows the total time needed to finish the assigned tasks to the workstation.

  $${\text{T}}_{{{\text{sw}}}} = \sum\nolimits_{{{\text{i}} = 1}}^{{\text{n}}} {\sum\nolimits_{{{\text{i}} \in {\text{s }}}} {{\text{TT}}_{{{\text{ki}}}} {\text{A}}_{{{\text{si}}}} } } \;\;\;\;\;{\text{for }}\;\;\;\;{\text{k}} = 1, \ldots .,{\text{W}}$$

  (7)

• Step 2:- Repeat step (1) for available workers until given workers have been assigned to a workstation based on the minimum Tsw.

• Step 3:- The steps above should be repeated for each workstation.

• Step 4:- Finally, determine the minimum cycle time of assembly line using Eq. (8).

  $${\text{CT}} = \max { }\left( {{\text{Tsw}}} \right)\;\;\;\;{\text{for}}\;\;\;\forall {\text{ s }} \in {\text{S}}$$

  (8)

Fig. 7.

Flowchart of the recursive algorithm for assigning workers to workstations.

4 Implementation Mechanism of the Developed W-TSAWH Approach

Generally, instead of using deterministic data, the evolved mechanism is experimentally tested using theoretical data to account for the uncertainty associated with task processing time. So, the reality, effectiveness, and validity of the developed approach can be highlighted. Two types of mixed models are critical for the criteria of the mechanism of two products (A&B) with data given in Table 1 and 2 respectively and the precedence relationship is given in Fig. 8. Generally, the two mentioned products (A&B) are required 12 tasks, each can be performed by any one of four workers with different capabilities, i.e. process time. The experiments testes through four points of parameters i.e. (EP, TP, AW, AM). EP and TP are dealt by two critical points (VL, VS), while the two others AW and AM are tested at (AV, UAV), which represents the extreme levels. The crisp value of the extreme points is belonging to fuzzy sets. Tables 3 and 4 denoted the extreme point range of each fuzzy set under study. Then, maximum values of input &output variables are specified by authors and listed in Table 5. Obviously, fuzzy inference will be executed using toolbox Graphical User Inference (GUI) in MATLAB.

Fig. 8.

Precedence graph of combined product.

Table 1. Data set of the product (A).

Table 2. Data set of the product (B).

Table 3. Fuzzy sets ranges of model 1

Table 4. Fuzzy sets ranges of model 2

Table 5. Data for setting input/output fuzzy variables

Table 6. Results of W – TSAWH approach for case A

Table 7. Results of W – TSAWH approach for case B

In order to demonstrate the applicability of the proposed mathematical model and effective solution of the developed solution approach, two cases (case A & case B) covering diversity of the work condition are studied for both examined layout of mixed assembly line SAL and UAL. These cases were solved according to the above-mentioned parameter values and the final decision is focusing on estimated processing time and then the best solution of cycle time required for the analysis and comparative is approached.

• Case A: Fixed Skill Level, Variable Work Stability

  This case examined data for two test problems (A1, A2), each test will benchmark the performance of the developed approach through the two examined WS extreme levels. Table 6 presents the results from the developed approach for SAL & UAL, respectively.

  • i. A1 SL is VS, WS is AV & UAV

    • A11 EP is VS AND TP is VS AND AW is AV AND AM is AV.

    • A12 EP is VS AND TP is VS AND AW is UAV AND AM is UAV.

  • ii. A2 SL is VL, WS is AV & UAV

    • A21 EP is VL AND TP is VL AND AW is AV AND AM is AV.

    • A22 EP is VL AND TP is VL AND AW is UAV AND AM is UAV.

• Case B: Variable Skill Level, Fixed Work Stability

  This case treated the examined data for two test problems (B1, B2), as listed below, each test will benchmark the performance of the developed approach through the examined SL extreme levels. Table 7 presents the results from the developed approach for SAL & UAL, respectively.

  • i. B1 SL is VS & VL, WS is AV

    • B11 EP is VS AND TP is VS AND AW is AV AND AM is AV.

    • B12 EP is VL AND TP is VL AND AW is AV AND AW is AV.

  • ii. B2 SL is VS & VL, WS is UAV

    • B21 EP is VS AND TP is VS AND AW is UAV AND AM is UAV.

    • B22 EP is VL AND TP is VL AND AW is UAV AND AM is UAV.

5 Numerical Results and Discussion

The performance of W-TSAWH approach was evaluated over A & B cases. In the experiments, we included eight test, concerning the two examined versions of ALB problem. Hence, for each test, the # of tasks = 12 must be assigned to 4 workstations/workers. Comparing the results yielded by the two versions of W-TSAWH approach, one can observe that W-TSAWH with U-shaped outperforms the other one version. This is established from the fact that the increasing ratio of minimum cycle time about rang 0.06–0.07. It is cleared that the processing time of the tests are sensitive with respect to the change credibility measures. Generally, in comparison between all the eight tests, that the tests have best minimum cycle time because in these tests they take higher SL scores while WS take lower or higher score for the examined extreme points, that means SL was the more impact because of its related with manual and semi-automated assembly line. Figure 9 display the divergence of the minimum cycle time obtained by the two versions of the developed approach over the cases examined. It is clear from this figure that, in most of the tests the U-shape version perform better than other one (although the difference is not large), in other words, this study proved the U–shaped version was preferred for examined parameters basically based on worker. Figure 10 and 11 shows the comparison of the cycle time obtained by two versions over the straight layout, case A, case B and U- shaped layout, case A, case B. The diagram confirm that the tests represented A21, A22, B12, B22 related with high SL are given CT = 38.26 & 35.88 for SAL and UAL respectively, in the contrary, that the tests A11 and B11 have high score of WS are given CT = 114.95, 107.8 for SAL and UAL respectively.

Fig. 9.

Cycle time for all tests.

As mentioned earlier, the most important stochastic parameters, EP, TP, AW, AM, are considered in the stochastic work environment of W–TSAWH approach. To obtain sufficient details of the effect of these parameters and their levels on experimental results as listed in Table 8, Taguchi method was used. This method has developed a special design of orthogonal array to study the entire problem parameters space with small number of experiments based on number of factors and their levels.

To determine the best parameters level, a robust design criterion entitled Signal–to–Noise (S/N) ratio, which establishes the relative importance of each parameter with respect to its main impacts on the objective function. Usually, the S/N ratio classifies objective function into three types: a nominal the better, smaller the better, larger the better, each type calculates the S/N ratio differently [14, 15]. The examined objective function are classified as smaller the better. MINITAB 17 was used for Taguchi method implementation. The parameter values with impact effect expected to have great improvement of objective function (minimum cycle time). The standard orthogonal array (L16) (24) is conducted for the SWE parameter combinations on an examined problem.Analysis of variance (ANOVA) is applied to investigate the effect of the parameters and their interactions, from Tables 9 and 10 EP, AW, EP*TP, EP*AW, TP*AW, have significant impact on the objective function because taking P–value less than 0.05, thus these obtained results proved the main role of worker rather than machine that were considered in manual and semi-automation assembly systems.

Table 8. Input variables with their fuzzy values

Table 9. ANOVA results for straight assembly line

Fig. 10.

Cycle time for a straight assembly line in case A & case B.

Fig. 11.

Cycle time for U - shaped assembly line in case A & case B.

6 Conclusions and Future Works

In this study a developed W–TSAWH approach for balancing mixed-model straight and U–shaped is presented. We concern with the assigned of the suitable task/worker to the suitable workstation based on minimizing cycle time as the main objective that subjected to some constraints. The problem also was formulated in an uncertain environment with fuzzy parameters. SWE is used to estimate stochastic processing time, and then recursive algorithm is developed for tasks/worker allocation to proper workstation. Finally, the performance of the developed approach was validated through set of numerical experiments. The developed model is proven to be capable to address the two types of assembly line are straight and U–shaped balancing problem under uncertainty work environment. Virtually, it is proved their efficiency through specify the more effect element in uncertain work environment. The extensive computational study proved the superiority of the parameters regard to workers over the other examined because we are dealing with manual or semi-automation. Although, it is limited by two versions of assembly line balancing models are straight and U–shaped, future works can focus on solving more complicated problems such as two-sided or parallel layout of assembly line using the W–TSAWH model. In addition, the developed algorithm could solve by employing multi-objective genetic algorithm.