ENHANCING PERFORMANCE OF CELL FORMATION PROBLEM USING HYBRID EFFICIENT SWARM OPTIMIZATION

ENHANCING PERFORMANCE OF CELL FORMATION PROBLEM USING HYBRID EFFICIENT SWARM OPTIMIZATION

4.1 OBJECTIVE

Cellular manufacturing design is apprehensive about the creation and activity of manufacturing cells to take the benefits of adaptability, adequate flow, and high creation rate. The way toward forming manufacturing cells with the highest efficiency is the most critical strides in cellular manufacturing. In the second stage of the work, we proposed a novel Monarch Butterfly Optimization (MBO) with FireFly (FF) based meta-heuristic proposed for solving a multi-objective cell formation problem (CFP). This hybridized MBO-FF acquires optimal arrangements in a good measure of time, particularly for large-sized issues, and focused on enhancing the performance of the CFP. This algorithm is competent to investigate the search space viably and recognize the global optimal within a short measure of time. Here, the percentage of exceptional elements (EE), machine utilization (MU), grouping efficacy (GE), and cell efficiency (CE) considered as performance measures. Computational results of the presented MBO-FF herein demonstrate they are superior or equivalent to the benchmark instance collected from the literature.

4.2 INTRODUCTION

        Cell formation problem is a part of Group Technology (GT), which was presented by Mitrofanov (1959) and later disseminated by Burbidge (1971) for the application of many manufacturing industries. Grouping of Machines and parts in a cellular manufacturing framework has given resemblance is known as the cell formation problem. Cell Formation (CF) forms a set of elements that can work in a predetermined group of specific machines. Sometimes cell configurations are streamlined in diverse planning periods for the variety of product mix and demand volumes. Based on this formation, there is a fundamental relation between machines and parts. Parts would then be able to be doled out to families to such an extent that all elements in the family handled on a similar gathering of machines. Comparatively, machines can assembled into cells on the off chance that they procedure a similar arrangement of parts. It has demonstrated that the cell formation problem is an NP-difficult problem.

There are a few targets to measure the viability of cellular manufacturing system, for example, the minimum number of intercellular/intracellular moves, the part operations performed inside a particular cell, maximum machine utilization, minimal total expenses by decreasing setup times, work-in-process (WIP), minimal capital speculation and a minimum number of voids in the cells. Cellular manufacturing system (CMS) design includes interrelated subproblems, specifically machine grouping, part family formation, and cell design. The entire production system is decomposed into production cells through CM for the maximization of the number of parts flows processed within cells.

CFP has considered an optimization problem in manufacturing for over 90 years. Because of the NP-hard nature of the CFP, heuristic, meta-heuristics, and hybrid meta-heuristics approaches have effectively proposed to produce satisfactory arrangements within a nominal time. The CFP to solve the NP-hard like a difficult problem, structure by utilizing combined algorithms. The implementation of a cellular manufacturing system that attracts lesser preparation time, material transportation cost, and works in the process also improved production, quality of the product, and work flexibility.

The hybrid meta-heuristic algorithm to maximizing the grouping efficacy with an unknown number of cells on real-sized problems. The artificial bee colony algorithm adapted to solve combinatorial optimization problems like single machine scheduling by employing random selection from an operator pool. An efficient model for CFP presented with a variable number of manufacturing cells. To develop this model, a mixed-integer linear programming technique and Dinkelbach approach used. They found that the computational time creased by analyzing two sets of databases.

By solving the CF problem through a genetic algorithm. They had great attention to the question of part/machine/worker cell formation for large-size datasets. The authors found an optimal solution in small-size problems, but the significant size problems got a nearly optimal solution within a reasonable time.  Modified adaptive resonance theory neural network used for cell formation dealt with binary data, non-binary data, operation sequences, and operation sequence with production volume. The dynamic cell formation problems using mathematical modeling for inter/intracellular layout problems and operator assignment with reduced cost. They also presented four numerical examples and validated by using two meta-heuristics approaches: Multi-objective simulated annealing and multi-objective vibration-damping optimization.

A complete cell formation is clustering the similar parts into families and relevant machines into cells also with social issues. Worker assignment strategies are used for decision-makers to assign suitable workers to particular tasks within a cell or between cells. A novel heuristics and meta-heuristics to solve CFP in 2012. They compared their proposed branch and bound algorithm and hybrid combination of genetic algorithm with numerical modeling. The results illustrated that the maximum effect achieved in that hybrid model for large-sized CF problems. A hybrid approach to solve concurrent cell formation and layout design. They compared two hybrid algorithms as the combination of genetic algorithm and simulated annealing with linear programming. These algorithms produce a low production cost and maximum machine utilization rate.

Optimization considered to be the subset of mathematics, which includes a review of techniques, procedures, methods, algorithms to obtain an optimum result of a given problem. Optimization is the process of getting the best solution of any question either by using minimization or maximization functions while specifying underline the various constraints. The principle objectives of providing optimized solution are Design variables i.e., a numerical input that will change during the process of optimization; Objective function i.e., describes the main motive of the service i.e., whether to minimize or maximize, depending upon nature of the problem; Constraints i.e., conditions that must be satisfied while solving the problem and Standard Formulation i.e., representation of optimal solution (optimization) problem in mathematical notation, as depicted in Figure 4.1.

Figure 4.1 Steps involved in obtaining an optimal solution (optimization)

The critical task in cellular manufacturing is the Cell Formation Problem (CFP). They are setting up a set of machine cells and their relevant part families to reduce the inter-cell moves at the same time, increasing the utilization of the machines. In the CFP, a group of parts separated into different part families in a manner that the elements located in the part families related in their geometry, production sequence, and production requirement, etc., and during the past decade, the majority of the research point towards the binary method. The usage of numerical optimization techniques to obtain optimal solutions, but the implementation of such technologies in the real world is a cumbersome task and unpredictable. The mathematical optimization techniques are incapable of solving any problem, where optimization required due to the absence of gradient information and computational limitations. Due to drawbacks and limitations of numerical optimization techniques to opt for either heuristic or metaheuristic approaches for solving optimization problems. The cell in such a situation may show up an excellent performance with measures developed for conventional GT goals like grouping efficiency, grouping efficacy, percentage of exceptional elements, and cell efficiency.

The proposed investigation presents a novel methodology, Monarch Butterfly Optimization (MBO), with a Firefly (FF) algorithm to minimize the percentage of exceptional elements, Machine Utilization, Grouping Efficacy, and Cell Efficiency. To approve these goals, a new methodology is proposed and simulate with a hybrid strategy.

4.3 PROBLEM STATEMENT

In this section, mathematical modeling formulated to solve CFP. Here, a few presumptions considered to evaluate CFP as only one machine of each kind is accessible. The features followed as,

• The number of cells to formed is known ahead of time,
• All machines are to be doled out and
• Each machine can relegate to just a single cell; each part has only a unique procedure plan for production.

4.4 PROPOSED METHODOLOGY

4.4.1 Nomenclature

–     Index for parts;

–     Index for machines;

–     Index for cells;

–

p_ik   –

q _jk    –

–

4.4.2 Modeling of Cell Formation Problem

To explain the modeling of cell formation problem seven machines and 11parts, the incidence matrix considered that given in table 4.1(a) is taken from the source Boctor 1991. The three cell partition, which minimizes the number of exceptional elements, shown in table 4.1(b). In this separation: Cell 1 includes machines 2, 3 and parts 1,2,6,9. Cell 2 consisting machines 1, 5, 6, and parts 3, 7, 11, and Cell 3 comprising machines 4, 7, and parts 4, 5, 8, 10.

Mathematical programming strategies broadly used to manage CFP with various optimization objectives. The proposed model validate by utilizing simulation modeling. Here, the proposed MBO-FF amplifies machine utilization, grouping efficacy, and cell efficiency and limiting the percentage of exceptional elements. The performance of the algorithm tested on benchmark problems existing in the literature to demonstrate the applicability and viability of the proposed model. Table 4.1 represents the example of CFP.

4.1 (a) Initial Matrix

4.1 (b) Final matrix

4.4.3 Objective function

The mathematical model has an objective to maximize the grouping efficacy, cell efficiency, and machine utilization and also minimizing the percentage of exceptional elements.

Grouping Efficacy (GE): GE controls the number of exceptional elements and the voids in the diagonal matrix of CFP. In this examination, the grouping efficacy measure utilized as the solution evaluation. Grouping efficacy measure expressed as equation (1):

(4.1)

Constraints

Constraint (1) guarantees that each machine must assigned to only a single cell. Constraint (2) ensures that each part ought to allotted to a single cell. Constraints (3) and (4) ensure that each machine and part can be doled out to one cell, if and just if the cell encircled. Constraint (5) connotes that decision variable paired.

Machine Utilization (MU): MU demonstrates the percentage of times the machines inside the groups utilized in production. MU can processed as:

(4.2)

Where signifies the machine utilization; represents the total number of one’s inside the block diagonal form; represents the number of machines in the cell; depicts the number of components in the cell;

Cell efficiency (CE): Cell efficiency shows the proportion of voids in block diagonal form to the total number of voids in the problem ought to be less and the ratio of several ones in block diagonal form to the total number of operations ought to be high. CE can be figured by

(4.3)

Where denotes the total number of operations; identifies the number of voids inside the block diagonal form.

Percentage of exceptional elements (EE): EE acquired from dividing the number of extraordinary aspects by the total number of items with ‘1’ in the entry, is utilized to incorporate the likely impact of problem size.

4.4.4 Validation of CFP on a hybrid algorithm

Mathematical models of the CFP process may force computational challenges and may not be resolvable utilizing commercial optimization software for medium-to-extensive measured problems. In this manner, proficient heuristic strategies required to take care of the proposed model for problems of bigger sizes. Here, we develop a heuristic method based on a hybrid algorithm i.e., the combination of monarch butterfly optimization with firefly to solve the proposed model.

4.4.4.1 Fitness Function

The objective function can be calculated based on the fitness function. The fitness function evaluated as maximizing the G.E, C.E, M.U, and minimizing the percentage of E.E. It shown in equation (4.4).

(4.4)

4.4.5 Monarch butterfly optimization (MBO)

MBO is a naturally-inspired monarch algorithm. It is motivated by the behavior of the ruler butterfly during migration.

4.4.5.1 Steps for MBO Algorithm

Monarch Butterfly Optimization Algorithm proposed by Wang et al. (2015), the whole population is separated into two parts as indicated by the fitness, called subpopulation, one and subpopulation two, respectively.

Step 1: Initialization Phase. Set the generation counter t = 1; initialize the population P of NP monarch butterfly individuals randomly; set the maximum generation, Max Gen, monarch butterfly number NP1 in Land 1 and monarch butterfly number NP2 in Land 2, max step S Max, butterfly adjusting rate BAR, migration period peri, and the migration ratio p.

Step 2: Fitness evaluation. Evaluate each monarch butterfly according to its position.

Step 3: While the best solution not found or t < Max Gen do Sort all the monarch butterfly individuals according to their fitness. Divide monarch butterfly individuals into two subpopulations (Land 1 and Land 2); for i= 1 to NP1 (for all monarch butterflies in Subpopulation 1) do

Generate new Subpopulation 1, according to Algorithm 1.

end for i for j= 1 to NP2 (for all monarch butterflies in Subpopulation 2) do

Generate new Subpopulation 2, according to Algorithm 2.

end for j.
The measure of the whole population, subpopulation1, and subpopulation 2 are individual.

Where denotes the entire population of monarch butterflies, refers to the subpopulation one and subpopulation 2signifies the proportion of subpopulation 1 in the whole population.

Parameters initialization: At first, initialize the population of monarch butterflies in land 1 and land 2 that referred to as subpopulation 1 and subpopulation 2. Here, each monarch butterfly position represents grouping parts and machines into cells and also evaluate the fitness according to the location of each MB. Accordingly, the locations of the monarch butterflies updated in two ways: the migration operator and the butterfly adjusting operator.

Migration operator: To keep the population unaltered, the migration operator supplanting its parent with recently produced one if it has better fitness when contrasted with its parent. The position of individual i from generation t to t+1 can defined by equation (4.5).

(4.5)

Where represents the element of at generation that presents the position of the monarch butterfly, shows the aspect of that is the newly generated position of the monarch butterfly, is the current generation number. The value of h is set to 5/12 as per migration period, where r1 and r2 are randomly selected from subpopulation1 and subpopulation 2, respectively, r can be calculated as,

(4.6)

Where is a random number in [0, 1] and indicates the migration period?

Butterfly adjusting operator: For individual i in subpopulation 2, its position in search space mostly relies upon the accompanying three perspectives: the global best individual among the whole population, outsider individual in subpopulation two, and levy flight. The development of individual i from generation t to t+1 can communicated as takes after

(4.7)

Where indicates the element of the current global best individual in the entire population in generation h. The butterfly adjusting rate is a control parameter that chooses a butterfly changing rate and can acquire by utilizing a levy flight. The parameter is the weighting factor resolved

(4.8)

(4.9)

Where means the most extreme walk step that a monarch butterfly individual can move in one stage at the present generation h. MBO means to supplant the relatively worse solutions by the new conceivably better solutions and keep for the next generation. To create a solution, machines and parts are chosen one by one and appointed to one of the cells in light of the control parameter and random walk. The arrangement of MBO enhances fitness work and gets an optimal method.

4.4.6 FireFly optimization (FF)

FireFly optimization impersonates the social behavior of fireflies in the tropical summer sky. Fireflies convey, search for prey, and discover mates utilizing bioluminescence with shifted flashing patterns. Fundamentally, FF uses the accompanying three glorified principles: Fireflies are unisex with the goal that one firefly will be attracted to other fireflies paying little respect to their sex. The attractiveness is corresponding to the brightness, and they both reduce as their distance increases. Therefore for any two flashing fireflies, the less luminous one will move towards the more luminous one. If there is no more splendid one than a particular firefly, it will move haphazardly. The brightness of a firefly related to the objective function.

4.4.6.1 Steps for FF optimization

Step 1: Each part of the machine operation is randomly chosen and sequenced to the point that all transactions are attracted request to make a firefly, which speaks to a matrix solution. This random choice rehashed to create a swarm of fireflies with the required size. The length of spaces in fireflies is equivalent to the total number of operations to perform. The measure of the firefly population decides the cell formation or the standard of search in the solution space.

       Step 2: The following stage is to measure the flashing light intensity of the firefly, which relies upon the problem considered. In this work, the evaluation of the dependability of schedules estimated by the fitness function.

       Step 3: Every firefly assessed to decide the target function value. The objective function value of every Firefly is related to the light intensity of the comparing Firefly. FF with less brightness is attracted and moved to a firefly with more shine. The light intensity resolved as

(4.10)

Where, is the attractiveness and is an absorption coefficient, which controls the decrease of the light intensity.

        Step 4: The attractiveness ascertained for every firefly. At that point, the development of the Firefly controlled by relying upon the attractiveness of the firefly.

(4.11)

Where is the original light attractiveness at; the distance between any two fireflies positions, respectively, it can be defined as a Cartesian distance as follows:

(4.12)

Where a component of the spatial coordinate of the firefly and is the number of dimensions. Finally, movement of a firefly, when attracted to another more attractive (brighter) Firefly, is determined by:

(4.13)

Where is the firefly position of the next generation; the first term in the condition is the present position of a firefly. The second term means a firefly’s attractiveness, and the last name is utilized for random development if there is no more brilliant firefly. The randomness parameter spoken to by and the rand is a casual number created consistently distributed somewhere in the range of 0 and 1.

       Step 5: The above steps repeated until the termination criterion met.

4.4.7 Proposed hybrid model (MBO-FF)

All the meta-heuristic algorithms can classified into two types:  local search heuristic methods and population-based methods. Community-based methods work with a set of solutions for every iteration. Whereas the local search heuristic methods function with a single solution.

The proposed hybrid MBO-FF approach is the population-based meta-heuristic algorithm to maximize the G.E., C.E., and M.U. to minimize the percentage of E.E in cell formation environment.

The CF problem can rectify, and the performance will improve to the best by the execution of the proposed hybrid MBO-FF approach.  Computational results of CFP showed that the hybrid algorithm gives an optimal solution when compared with the actual results.

Step 1: Initialization Phase. Set the generation counter t = 1; initialize the            population P of NP monarch butterfly individuals randomly;

Each part of the machine operation randomly chosen. This random choice rehashed to create a swarm of fireflies with the required size.

        Step 2: The Fitness evaluation. Evaluate each monarch butterfly according to its position.

To measure the flashing light intensity of the firefly is the problem considered and is estimated by the fitness function.

Step 3: While the best solution not found or t < Max Gen does Sort all the monarch butterfly individuals according to their fitness. Divide monarch butterfly individuals into two subpopulations (Land 1 and Land 2); for i= 1 to NP1.

Every firefly assessed to decide the target function value. FF with less brightness is attracted and moved to a firefly with more brightness.

        Step 4: To keep the population unaltered, the migration operator supplanting its parent with recently produced one if it has better fitness when contrasted with its parent.

The attractiveness ascertained for every firefly and rank.

       Step 5: Update the position by butterfly adjusting operator.  Update the location of the firefly.

Generate new Subpopulation 1& 2 according to Algorithm 1 & 2.

The above steps repeated until the termination criterion met.

end for i

end for j.

4.4.7.1 Optimal solution

Based on the hybridization process, the new solutions attained. Then, the fitness value found out for the latest updated solutions. From that, the solution which gives the minimized/maximized fitness function used as the optimal solution (equation 14). Otherwise, the above steps processed for the new solution sets. To compare both the individual algorithms (MBO-FF), the best solution considered as an optimal solution.

(4.14)

Where represents the optimal fitness function, which has been achieved by the above processes. The following figure 4.2 shows the flowchart of the proposed model – hybrid approach MBO-FF techniques.

Figure 4.2 Flowchart for the proposed model

4.5 RESULTS AND DISCUSSION

The proposed CFP with an optimization method for accomplishing the optimal solution is finished by utilizing MATLAB software variant 2016a most recent form in a system having 8 GB RAM with a 64-bit operating system having i5 processor. The performance of the hybrid algorithm MBO-FF systematically evaluated in comparison with other existing methods on standard benchmark testing problems. All these data are available for downloading from the http://opt-hub.com/problems/cfp hub.

Table 4.2 Comparison of performance measures of the proposed model to other algorithms.

Table 4.2 represents the comparison of performance measures of the proposed model to other algorithms.

4.5.1 Performance evaluation

Table 4.1 depicts the comparison of the proposed model to other algorithms with computational results. Here, the performances of CFP for twenty benchmark problems are analyzed and are named as A1, A2 … up to A20. In this table, M signifies the machines; P identifies Parts, and C indicates Cell.

The G.E, C.E, M.U, and percentage of EE compared with every problem. The evaluation of the proposed MBO-FF compared with the existing techniques such as Dragonfly-Fruit Fly Algorithm (DF-FFA). The MBO-FF attains optimal value, and it reaches the global optimum solution based on increasing the efficiency, efficacy, and machine utilization and reducing the exceptional elements. The performance of the proposed algorithm MBO-FF evaluated 20 different benchmark test problems taken from the literature.

Table 4.2 depicts the sources and sizes for these problems. For every problem source number of machines, parts, cells, grouping efficacy, cell efficiency, machine utilization, and percentage of exceptional elements and the best cell size obtained. Also, this table reported the computational time required to get the best solution for each problem source by the proposed approach.

The grouping efficacy of the solutions obtained by the MBO-FF is as good as the best solution available in the literature. Our solution is better than that of all the 20 methods. Therefore, the proposed method outperforms all the other methods. The cell efficiency of the solutions obtained by the MBO-FF is superior to the 17 ways out of 20 methods. Therefore, the proposed method performs well. The performance on machine utilization attained by the MBO-FF is shown improvement in 18 methods out of 20 ways.

The percentage of exceptional elements by the proposed MBO-FF model outperforms on 7 methods and equivalent to the remaining 13 problems taken from the 20 methods as the best solution available in the literature.

Based on the performance measures such as grouping efficacy, cell efficiency, machine utilization, and percentage of exceptional elements, the MBO-FF shows best performs.

4.3 (a) G.E evaluation

4.3 (b) M.U evaluation

4.3 (c) C.E analysis

4.3 (d) Percentage of EE analysis

Figure 4.3 Performance evaluation of MBO-FF

Figure 4.3 shows the convergence graph representation of all the performance parameters compared with different techniques. The G.E., M.U., C.E., and percentage of E.E. attained for varying iterations.

It denotes that increasing iterations will improve the optimal solution. That means for significant sized problems; the result can be confirmed optimal. Comparing the effects of different techniques is a difficult task, but the convergence graph illustrates that the optimal solution achieved in MBO-FF than DF-FFA.

4.5.2 Comparison evaluation

Figure 4.4 shows the comparative analysis of performance parameters based on the five sample benchmark problems such as King (A1), Waghodekar and Sahu (A2), Seifoddini (A3), Kusiak and Cho (A4) and Kusiak and Chow (A5), DF-FFA and the proposed MBO-FF. Here, Actual value refers to the experimental values of the above mentioned existing techniques.

The Grouping Efficacy for MBO-FF values of A1-85.96, A2-77.45, A3-83.95, A4-89.45, and A5-64.12 is higher than the actual costs of A1-82.3, A2-69.5, A3-80.85, A4-79.17, and A5-60.87. The benchmark problem works under the basis of the cell forming of particular parts working in machines. On cell efficiency and Machine utilization, the proposed algorithm MBO-FF scores maximum performance, as shown in figure 3.

The Percentage of Exceptional Elements for MBO-FF values of A1- 0, A2-12.5, A3-12.5, A4-24.6, and A5-23 are the minimum of the actual costs of A1- 0, A2-12.5, A3-12.5, A4-25 and A5-23.7.

This study concludes that M.U G.E, C.E achieves maximum value in the proposed model i.e., maximum G.E. reaches 93.66%, C.E. as 91.54%, M.U as 92.85%, and minimum in the percentage of EE as 0 and 0.7. The proposed model achieves an optimal result in CFP.

Figure 4.4 (a)

Figure 4.4 (b)

Figure 4.4 (c)

Figure 4.4 (d)

Figure 4.4 Comparison analysis a) G.E comparison b) C.E comparison c) M.U analysis d) Percentage of E.E comparison analysis.

Figure 4.4 illustrates the comparison analysis a) G.E comparison b) C.E comparison c) M.U analysis d) Percentage of E.E comparison analysis.

4.6 SUMMARY

In the second stage of the work, a hybridization model MBO-FF algorithm for solving CFP proposed. The proposed algorithm has maximization of G.E, C.E, and M.U and minimization of the percentage of exceptional elements as objective. The MBO-FF algorithm is proficient at tackling the CFP and get the optimal solution on entire benchmark problems based on the comparison and assessment that done on performance measures. The performance of the proposed algorithm compared to a set of 20 test problems from the existing literature. The quality of the solutions of MBO-FF with other methods indicates the algorithm is a better algorithm for solving the cell formation problem.  Computational outcomes played out that optimal fitness function accomplished in the proposed model when contrasted with experimental algorithms and Dragon Fly-Fruit Fly Algorithm. The improvement and newness of this work in association with the recent endeavor are as follows:

• Preparing a mathematical model for the CFP and evaluate the attained solution with other methods.
• The proposed model’s computational results produce good-quality solutions.
• Presenting a hybrid meta-heuristic algorithm in which monarch butterfly optimization with firefly is united to solve the large-size cell formation problem.
• The performance of the proposed algorithm is comparing with the 20 existing methods.
• Applying this meta-heuristic approach to solve the complicated real-sized problems using cellular manufacturing models is the future researches.