# Efficient Parallel Sorting for Migrating Birds Optimization When Solving Machine-Part Cell Formation Problems

Authors: Ricardo Soto; Broderick Crawford; Boris Almonacid; Fernando Paredes
Journal: Scientific Programming
 (2016)

---

## Abstract

The Machine-Part Cell Formation Problem (MPCFP) is a NP-Hard optimization problem that consists in grouping machines and parts in a set of cells, so that each cell can operate independently and the intercell movements are minimized. This problem has largely been tackled in the literature by using different techniques ranging from classic methods such as linear programming to more modern nature-inspired metaheuristics. In this paper, we present an efficient parallel version of the Migrating Birds Optimization metaheuristic for solving the MPCFP. Migrating Birds Optimization is a population metaheuristic based on the V-Flight formation of the migrating birds, which is proven to be an effective formation in energy saving. This approach is enhanced by the smart incorporation of parallel procedures that notably improve performance of the several sorting processes performed by the metaheuristic. We perform computational experiments on 1080 benchmarks resulting from the combination of 90 well-known MPCFP instances with 12 sorting configurations with and without threads. We illustrate promising results where the proposal is able to reach the global optimum in all instances, while the solving time with respect to a nonparallel approach is notably reduced.


---

## Body

## 1. Introduction

The Machine-Part Cell Formation Problem (MPCFP) is based on the well-known Group Technology (GP) [1] widely used in the manufacturing industry. The goal of the MPCFP is to organize a manufacturing plant in a set of cells that contain a limited number of machines and parts, but minimize the cell-interchange of parts. The purpose is to reduce costs and increase productivity. The MPCFP is known to be NP-Hard, so there is always the challenge of producing high quality solutions in a limited time interval. During the last years, several techniques have successfully been applied to this problem, from mathematical methods such as linear programming [2] to classic metaheuristics such as particle swarm optimization [3] and more modern ones such as artificial fish swarms [4].In this paper, we present a new and efficient parallel version of the Migrating Birds Optimization metaheuristic for solving the MPCFP. Migrating Birds Optimization (MBO) is a population-based metaheuristic inspired by the V-shaped flight employed by birds when they migrate. This technique is known to be very effective for energy saving during flying. This interesting approach is enhanced by precisely integrating parallel procedures particularly for the efficient sorting of birds and neighboring solutions. It results in a notable improvement in terms of performance of the whole solving process. We perform computational experiments by using 90 well-known MPCFP instances, 2 well-known sorting algorithms, 1 sequential configuration, and 5 thread configurations (1, 4, 8, 16, and 32) resulting in a total of 1080 benchmarks. The obtained results are encouraging where the proposal is able to reach the global optimum in all instances, while the solving time with respect to a nonparallel approach is notably reduced.The outline of the study is as follows. In Section2, we give some information on the related work. Section 3 describes and models the MPCFP. Section 4 gives an overview of MBO. Section 5 describes how to resolve the MPCFP using MBO with parallel sort. Section 6 presents and discusses the experimental results. Section 7 concludes and provides guidelines for future work. Finally, the Appendix provides detailed results for the 1080 benchmarks, in which each includes 90 test instances.


## 2. Related Work

Several investigations that have been carried out for the problem MPCFP are as follows: linear programming [5], a goal programming model [6], a hybrid genetic algorithm [7], boolean satisfiability [8], constraint programming [9], and using an artificial fish swarm algorithm [4]. An analysis of the evolution of cell formation problem can be found in [10, 11]. As MPCFP is NP-Hard problem, many researchers have considered applying approximation methods as metaheuristics. Various research can be found in the field of metaheuristics,.in which the search is performed using iterative procedures, which allow moving from one solution to another in the search space. This type of metaheuristic performs movements in the neighborhood of the current solution, which means it has a perturbative nature. As metaheuristics are based on trajectories, among which we have simulated annealing [12–14], tabu search [15–17], local iterated search [18, 19], and local variable search [20], there is also another type of metaheuristics which are based on population. The population metaheuristics have a set of individuals, where each individual encodes a temporary solution. These metaheuristics use an evaluation function fitness of each individual, with the aim of obtaining the best values of the population that solve an optimization problem. In addition, there are disturbances in the algorithm that directed individuals in the population or part of them to possible solutions for better fitness. Among these population-based metaheuristics, ant colony optimization [21, 22], particle swarm optimization [3, 23, 24], cat swarm [25, 26], and Migrating Birds Optimization [27] can be found in problems like a hybrid flowshop scheduling with total flowtime minimisation [28], closed loop layout with exact distances in flexible manufacturing systems [29], and preliminary results for MPCFP [30]. A brief review of nature-inspired algorithms for optimization can be found in [31].In the area of manufacturing and industrial applications, parallel implementations using metaheuristics have been addressed, such as GRASP and grid computing to solve the location area problem [32], performance analysis of coarse-grained parallel genetic algorithms on the multicore Sun Ultra SPARC T1 [33], a parallel genetic algorithm for the multilevel unconstrained lot-sizing problem [34], and a memetic algorithm and a parallel hyperheuristic island-based model for a 2D packing problem [35]. We can also find research using parallel metaheuristics as a cooperative parallel metaheuristic for the capacitated vehicle routing problem [36] and optimizing shared-memory hyperheuristics on top of parameterized metaheuristics [37] and, finally, we can find a review of recent progress in implementing parallelism with metaheuristics included in the following work [38].Different studies have addressed the parallel sorting algorithms as massively parallel sort-merge joins in main memory multicore database systems [39], an efficient parallel merge sort for fixed and variable length keys [40], a randomized parallel sorting algorithm with an experimental study [41], sorting algorithm for many-core architectures based on adaptive bitonic sort [42], performance comparison of sequential quick sort and parallel quick sort algorithms [43], the time profit obtained by parallelization of quick sort algorithm used for numerical sorting [44], an efficient massively parallel quick sort [45], and, finally, a fast parallel implementation of quick sort and its performance evaluation on SUN enterprise 10000 [46].In this paper, we have chosen metaheuristic MBO because it has a friendly design, composed of two linked lists for each of the sides of the flock of birds and a node as a leader bird. Furthermore, MBO has been applied to various optimization problems with promising results [47–49]. We focus on an efficient parallel sorting for MBO when solving MPCFP, which to our knowledge has not yet been reported. It has been chosen to parallelize the sorting algorithms in MBO because 4 out of the 8 steps of the MBO metaheuristic used sorting algorithms, and therefore we believe that applying parallel sorting in these steps is possible to achieve reduction of the execution time in MBO algorithm.


## 3. Machine-Part Cell Formation Problems

The Machine-Part Cell Formation Problem (MPCFP) is NP-Hard optimization problem; the main objective is the formation of set of machines and parts in groups so that the number of intercell transportation of parts is minimized. Therefore, the initial matrix (see matrix in Table1) must be converted into a matrix that has a block diagonal structure (cells are easily visible; see matrix in Table 2). This example corresponds to a MPCFP with the following parameters: 5 machines, 7 parts, and Mmax⁡ = 3 for 2 cells. The optimum value obtained is 0, and the final incidence matrix aij is constructed from the results of the matrices yik and zjk (see Tables 3 and 4).Table 1
Initial incidence matrixM×P.
Part 1 Part 2 Part 3 Part 4 Part 5 Part 6 Part 7 Machine 1 0 1 0 1 1 1 0 Machine 2 1 0 1 0 0 0 0 Machine 3 1 0 1 0 0 0 1 Machine 4 0 1 0 1 0 1 0 Machine 5 1 0 0 0 0 0 1Table 2
Rearranged incidence matrixM×P.
Cell 1 Cell 2 Part 1 Part 3 Part 7 Part 2 Part 4 Part 6 Part 5 Cell 1 Machine 2 1 1 0 0 0 0 0 Machine 3 1 1 1 0 0 0 0 Machine 5 1 0 1 0 0 0 0 Cell 2 Machine 1 0 0 0 1 1 1 1 Machine 4 0 0 0 1 1 1 0Table 3
MatrixM×C→yik.
Cell 1 Cell 2 Machine 1 0 1 Machine 2 1 0 Machine 3 1 0 Machine 4 0 1 Machine 5 1 0Table 4
MatrixP×C→zjk.
Cell 1 Cell 2 Part 1 1 0 Part 2 0 1 Part 3 1 0 Part 4 0 1 Part 5 0 1 Part 6 0 1 Part 7 1 0A rigorous mathematical formulation of MPCFP is given by Boctor [2]. The problem is represented by the following mathematical model:(i)
Parameters, index, and sets:
(a)
aij, the M×P binary machine-part incidence matrix, where(1)aij=1ifjthpart  visitsithmachine;0otherwise,(b)
M, the number of machines,(c)
P, the number of parts,(d)
C, the number of cells,(e)
i, the index of machines (i=1,…,M),(f)
j, the index of parts (j=1,…,P),(g)
k, the index of cells (k=1,…,C),(h)
Mmax⁡, the maximum number of machines per cell.(ii)
Variables and domains:
(a)
yik, the M×C machine-cell matrix, where(2)yik=1if  machinei∈cellk;0otherwise,(b)
zjk, the P×C part-cell matrix, where(3)zjk=1if  partj∈familyk;0otherwise.(iii)
Objective function:(4)minimized∑k=1C∑i=1M∑j=1Paijzjk1-yik.(iv)
Being subject to the following constraints:(5)∑k=1Cyik=1∀i,∑i=1Myik≤Mmax⁡∀k,∑k=1Czjk=1∀j.


## 4. Migrating Birds Optimization

Migrating Birds Optimization (MBO) is a nature-inspired population metaheuristic based on the V-shaped flight of the migrating birds [50, 51], which is proven to be an effective formation in energy saving [52]. In the V-formation (shown in Figure 1), some parameters like wing-tip spacing (WTS), maximum width of the wing (w), angle of the V-formation (α), and depth and wing span (b) are important to form an effective V-formation [53, 54]. The conceptual similarity between the parameters of the algorithm of MBO with the actual migration of birds in V-flight formation is investigated in Duman et al. [27]. This conceptual similarity is described in Table 5.Table 5
Conceptual similarity of MBO metaheuristic and V-shape natural migration of birds.
Parameter description Concept in real migration birds in V-formation The number of initial solutions of the flock. Birds in V-formation. The number of neighboring solutions generated for each initial solution. The induced power required which is inversely proportional to the speed. The number of neighboring solutions shared with the next solution. Wing-tip spacing (WTS). The number of tours. The number of wing flaps before a change occurs in the leading bird. The number of iterations (total number of generated neighbor solutions). There is no conceptual relationship.Figure 1
The V-shaped flight.The MBO starts with a number ofn initial solutions corresponding to birds in a V-flight formation. These solutions are generated randomly and a solution as the leader bird is chosen; then the remaining birds are alternately distributed to each side of the flock. In the next step, for all tours, improving the leader solution is performed by generating and evaluating its k neighbors. For each solution Sr in the flock (except leader), try to improve Sr by evaluating its (k-x) neighbors and x unused best neighbors from the solution in the front. Move the leader solution to the end and forward one of the solutions following it to the leader position. Finally, when the iterations are over, return the best solution in the flock. Algorithm 1 depicts the classic procedure of MBO algorithm.Algorithm 1:Pseudocode of Migrating Birds Optimization.
(1)   Generate n initial solutions in V-formation (2)   i=0 (3)   while(i<I)do (4)   forint⁡j=0; j<m; j++do (5)    Improve the leading solution by generating and evaluating k neighbors of it (6)    i=i+k (7)    foreach solutionSrin the flock (except leader) do (8)     Try to improve Sr by evaluating (k-x) neighbors of it and x unused best neighbors from the leader (9)      i=i+(k-x) (10)   end (11)  end (12)  Move the leader solution to the end and forward one of the solutions following it to the leader position (13) end (14) Return the best solution in the flock


## 5. Solving the MPCFP Using MBO with Parallel Sort

The first step in solving the problem MPCFP is a proper integration with the MBO metaheuristic. In this sense, we conceptualize every bird of the flock (including the leader of the flock) as a possible solution to the problem MPCFP (see Figure2). Each bird will be composed of a matrix M×C and matrix P×C. These matrices are those modified while the problem lapsed iterations. In addition, they will be used for the calculation of fitness to problem MPCFP.Figure 2
Integration of Migrating Birds Optimization with the Machine-Part Cell Formation Problem.


### 5.1. Generate Initial Solutions

For generating initial solutions, consider the following inputs: machines = 4, parts = 5, cells = 2,Mmax⁡ = 2, and a matrix M×P (see Table 6).Table 6
MatrixM×P.
Part 1 Part 2 Part 3 Part 4 Part 5 Machine 1 1 0 0 1 1 Machine 2 1 0 1 0 1 Machine 3 0 1 0 1 1 Machine 4 1 0 1 0 0Considering data in Table6, the first step to generate an initial solution is as follows.Step 1.
Generate random allocations in the matrixM×P with some random method. This matrix M×C (see Table 7) satisfies constraints that exists in only one machine in a cell and Mmax⁡ is less than or equal to 2 in an entire cell.Table 7
MatrixM×C.
Cell 1 Cell 2 Machine 1 1 0 Machine 2 0 1 Machine 3 0 1 Machine 4 1 0Step 2.
Generate with a manual method the matrixP×C from the matrix M×C. For this, a connection is established with the matrix M×P and with the matrix solution M×C. In lightface, machines correspond to the cell number 1 and, in bold, machines correspond to cell number 2 (see Table 8).Table 8
Relationship between the matrixM×P with the matrix M×C.
Part 1 Part 2 Part 3 Part 4 Part 5 Cell 1 Cell 2 Machine 1 1 0 0 1 1 1 0 Machine 2 1 0 1 0 1 0 1 Machine 3 0 1 0 1 1 0 1 Machine 4 1 0 1 0 0 1 0The manual method for determining the matrixP×C involves adding the value 1 out of every position i, j of the M×P matrix and putting this value in the temporary array of sums according to the corresponding cell. We perform the operation for each value of positions i, j of the matrix M×P (see Table 9).Table 9
Generation of temporary matrix sum.
Part 1 Part 2 Part 3 Part 4 Part 5 Cell 1 Cell 2 Machine 1 1 0 0 1 1 1 0 Machine 2 1 0 1 0 1 0 1 Machine 3 0 1 0 1 1 0 1 Machine 4 1 0 1 0 0 1 0  Sum of Cell 1 2 0 1 1 1 Sum of Cell 2 1 1 1 1 2Example 1.
(i)
M × P [ 1,1 ] = 1 → is the value that is associated with cell 1; we add this value to the Row SumofCell1. (ii)
M × P [ 2,1 ] = 1 → is the value that is associated with cell 2; we add to this value to the Row SumofCell2. (iii)
M × P [ 3,1 ] = 0 → is the value that is associated with cell 2; we add to this value to the Row SumofCell2. (iv)
M × P [ 4,1 ] = 1 → is the value that is associated with cell 1; we add to this value to the Row SumofCell1.Step 3.
From the results of Table9, we build a partial solution to the matrix P×C (see Table 10).Table 10
MatrixP×C.
Cell 1 Cell 2 Part 1 2 1 Part 2 0 1 Part 3 1 1 Part 4 1 1 Part 5 1 2Step 4.
Find possible solutions toP×C.We must choose the values of the positionsi, j that belong to the temporary matrix M×P and have the largest values of each row. Subsequently, we replace larger values assigning them the value 1, and for the other values in the row we assign them the value of 0 (see Table 11). In case of draw, that is, the entire row has equal numbers, we keep unchanged if the value of their positions is 1. In the case that the same numbers are greater than 1, to each number greater than 1, we assign them a value of 1.Table 11
MatrixP×C.
Cell 1 Cell 2  Cell 1 Cell 2 Part 1 2 1 → 1 0 Part 2 0 1 0 1 Part 3 1 1 1 1 Part 4 1 1 1 1 Part 5 1 2 0 1We consider rows having values equal to 1 in this case correspond to rows pertaining to machines 3 and 4. From this point, we generate all possible combinations of matrices and randomly choose one (see Table12).Table 12
All possible combinations of matricesP×C.
Cell 1 Cell 2  Cell 1 Cell 2 Part 1 1 0 Part 1 1 0 Part 2 0 1 Part 2 0 1 Part 3 1 0 Part 3 1 0 Part 4 1 0 Part 4 0 1 Part 5 0 1 Part 5 0 1  Cell 1 Cell 2  Cell 1 Cell 2  Part 1 1 0 Part 1 1 0 Part 2 0 1 Part 2 0 1 Part 3 0 1 Part 3 0 1 Part 4 1 0 Part 4 0 1 Part 5 0 1 Part 5 0 1


### 5.2. Generating Neighboring Solutions

To generate a neighboring solution, we consider the following inputs: machines = 4, parts = 5, cells = 2,Mmax⁡ = 2, matrix M×P, matrix M×C, and matrix P×C (see Table 13).Table 13
Initial matrices for generating neighboring solutions.
(a) Cell 1 Cell 2 Cell 3 Cell 4 Cell 5 Machine 1 1 0 0 1 1 Machine 2 1 0 1 0 1 Machine 3 0 1 0 1 1 Machine 4 1 0 1 0 0 (b) Cell 1 Cell 2 Machine 1 1 0 Machine 2 0 1 Machine 3 0 1 Machine 4 1 0 (c) Cell 1 Cell 2 Part 1 1 0 Part 2 0 1 Part 3 0 1 Part 4 1 0 Part 5 0 1Step 1.
Randomly choose a positioni, j in the matrix M×C that has a value of 1 and we work with the machine associated with that row i. This is the same as selecting a machine and working with its row i. In this case, we chose randomly the position of the matrix M×C[2,2] with a value of 1, which corresponds to machine 2 (see Table 14).Table 14
Machine selection.
(a) Cell 1 Cell 2 Machine 1 1 0 Machine 2 0 1 Machine 3 0 1 Machine 4 1 0 (b) Cell 1 Cell 2 Machine 1 1 0 Machine 2 0 1 Machine 3 0 1 Machine 4 1 0Step 2.
Then on machine 2, we randomly pick a cell that has a 0. In this case, we choose the position of the matrixM×C[2,1]; we accomplish a replacement of the value of 0 to 1 and finally realize a replacement for M×C[2,2] value of 1 to 0. You can see the result of this operation in Table 15. In the case that the constraints are inconsistent, you must repeat the procedure from Step  1.Table 15
Final matrixM×C.
Cell 1 Cell 2 Machine 1 1 0 Machine 2 1 0 Machine 3 0 1 Machine 4 1 0Step 3.
We carry out the construction of the matrixP×C using the manual method explained in Section 5.1.


### 5.3. Flowchart of Migrating Birds Optimization

This section describes the stages of the algorithm MBO, as it integrates with the problem of MPCFP and in which stages parallel arrangement algorithms are applied. For a better understanding, a flow chart has been included (see Figure3) which is divided into 4 main phases: algorithm initialization, a tour process, leader replacement, and algorithm finalization.Figure 3
Flowchart of Migrating Birds Optimization.


#### 5.3.1. Algorithm Initialization

Parameter Initialization (Stage 1 in Figure3). At this stage, all the values required by the MBO metaheuristic are initialized; all the values required by the problem of MPCFP and that type of sorting algorithm are to be implemented in the metaheuristic.Among the metaheuristic values, there are(i)
number of birds (n),(ii)
number of neighbors (k),(iii)
number of tours (m),(iv)
number of shared solutions (x),(v)
number of iterations (I).And between complementary metaheuristic parameters, we can include(i)
leader exchange mode, where there are 2 types of changes of leader; exchange the leader with the successor and exchange the leader with the best;(ii)
sort type applied in the initial birds flock, where there is an ordering with random birds in the flock and another with birds ordered according to their fitness.Among the parameters required for the problem MPCFP, we have(i)
incidence matrix (M×P),(ii)
number of machines (M),(iii)
number of parts (P),(iv)
number of cells (C),(v)
maximum number of machines in a cell (Mmax⁡).Finally, for the types of sorting applied to MBO, we have the following parameters:(i)
Type of sorting algorithm: quick sort or merge sort.(ii)
Sorting technique: normal or with threads.(iii)
Number of threads if required.Generate Initial Solutions (Stage 2 in Figure3). At this stage, we generate initial solutions according to the method described in Section 5.1. These solutions must satisfy the three constraints of model MPCFP.Create Initial Flock (Stage 3 in Figure3). From the initial solutions, we create an array of birds, and finally ordered arrangement created the conceptual V-formation birds. For it, we assign the first position (first solution) in the array as the leader of the flock, and we perform an alternate distribution of birds between each side of the flock for the rest of the birds. We must consider that the birds are always sorted by fitness from low to high, the bird with lower fitness being the best solution to the problem (MPCFP is a minimization problem). Furthermore, we must consider that this is a stage in which we incorporate parallel order by quick sort and merge sort.


#### 5.3.2. A Tour Process

This phase has two subphases internally: evolution of the leader bird and the evolution of the other birds. The evolution of the leader bird phase has one stage (generating neighboring solutions for the leader) and the evolution of the other birds phase has two stages (generating neighboring solutions for the other birds and sharing neighboring solutions that are not used by the leader with the other birds).Generate Neighboring Solutions for the Leader (Stage 4 in Figure3). This stage consists of generating neighboring solutions according to the steps outlined in Section 5.2. Subsequently, these neighboring solutions are sorted using an algorithm of parallel sort; see line (5) in the algorithm MBO (Algorithm 1).Generate Neighboring Solutions for the Other Birds (Stage 5 in Figure3). In this stage, we create k-x neighboring solution to each bird of the flock; then these birds are sorted by an algorithm of parallel sort; see lines (7) and (8) in the algorithm MBO (Algorithm 1).Share Neighboring Solutions That Are Not Used by the Leader with the Other Birds (Stage 6 in Figure3). Share the other neighboring solutions of the leader with the other sides of the V-formation of birds; this is done alternately from left to right or from right to left. After sharing the neighboring solutions, we performed a sorting using an algorithm of parallel sort in all neighboring solutions that every bird in the flock has (not including the leader).Leader Replacement (Stage 7 in Figure3). At this stage, we performed a replacement of leader; for this we choose the nearest successor; that is, choose one of the birds closer to the leader. The successor will take its place and the leader will be available at the end of the flock. We must take into consideration that if we choose a successor belonging to the left section of the flock, the leader will pass to the end of the left section. The same procedure applies to the right section of the flock (see Algorithm 2).Algorithm 2:Replace leader with successor.
(1)   int⁡type_of_sort = Get_Type_Of_Sort () (2)   boolean left_or_right_side = Random_Boolean () (3)   Main FunctionReplace_Leader_With_Successor ()is (4)    ifleft_or_right_sidethen (5)     Change_Leader_With_Left_Birds () (6)     Sort_Left_Birds (type_of_sort) (7)    else (8)     Change_Leader_With_Right_Birds () (9)     Sort_Right_Birds (type_of_sort) (10)  end (11)  left_or_right_side = !left_or_right_side (12) endAlgorithm Finalization (Stage 8 in Figure3). In this step, the fitness of the leader is obtained; in addition, a procedure to remove a response matrix explicitly is made; that is, we construct an incidence matrix AM[P] according to the order given by the matrices of solutions Y and Z. The order is according to the index of less than most of the machines and parts (see Algorithm 3).Algorithm 3:Convert matrix M×C and P×C to final matrix.
(1)   Main FunctionConvert_to_final_matrix (int⁡A[i][j], int⁡Y[][], int⁡Z[][]) is (2)   int⁡final_matrix[M][P], temp_matrix[M][P], ii=0, jj=0 (3)   /∗ Sort machines ∗/ (4)   forint⁡k=0; k<C; k++do (5)   forint⁡i=0; i<M; i++do (6)     ifY[i][k]==1then (7)         forint⁡j=0; j<P; j++do (8)        temp_matrix[ii][j]=A[i][j] (9)         end (10)       ii=ii+1 (11)      end (12)    end (13)    end (14)   /∗ Sort parts ∗/ (15)   forint⁡k=0; k<C; k++do (16)    forint⁡j=0; j<P; j++do (17)     ifZ[j][k]==1then (18)       forint⁡i=0; i<M; i++do (19)        final_matrix[i][jj]=temp_matrix[i][j] (20)       end (21)       jj=jj+1 (22)     end (23)    end (24)    end (25)    returnfinal_matrix (26) end


#### 5.3.3. Sorting Algorithm

For MBO, we use two sorting algorithms, merge sort and quick sort, in which we executed sequentially and in parallel using threads.Merge Sort. It was developed in 1945 by John Von Neumann. It is a search algorithm of complexity O(nlog⁡n) (see Table 16). Algorithm 4 illustrates a general pseudocode for merge sort.Table 16
Complexity sorting algorithm.
Name Best Average Worst Memory Method Stable Merge sort O ( n log ⁡ n ) O ( n log ⁡ n ) O ( n log ⁡ n ) Depends Merging Yes Quick sort O ( n log ⁡ n ) O ( n log ⁡ n ) O ( n 2 ) O ( log ⁡ n ) Partition DependsAlgorithm 4:Merge sort.
(1)   Main FunctionMergeSort (Object[]A) is (2)    Object[]result, left, right (3)    iflength(A)≤1then (4)   returnA (5)    else (6)   int⁡middle=length(A)/2 (7)   fori=0to middledo (8)     left[i]=A[i] (9)   end (10)    fori=middle+1to length(A) do (11)      right[i]=A[i] (12)    end (13)    left = MergeSort (left) (14)    right = MergeSort (right) (15)    result = Merge (left, right) (16)    returnresult (17)  end (18) endQuick Sort. It was developed in 1959 by Charles Richard Hoare. It is a search algorithm of complexity O(nlog⁡n) (see Table 16). Algorithm 5 illustrates a general pseudocode for quick sort.Algorithm 5:Quick sort.
(1)   Main FunctionQuickSort (Object[]A, int⁡low, int⁡high) is (2)   iflow<highthen (3)    pivot_location=  Partition (A, low, high) (4)    QuickSort (A, low, pivot_location) (5)    QuickSort (A, pivot_location + 1, high) (6)   end (7)   end (1)   FunctionPartition (Object[]A, int⁡low, int⁡high) is (2)   Object pivot = A[low] (3)   int⁡leftwall = low (4)   fori=low+1to highdo (5)    ifA[i]<pivotthen (6)     Swap (A[i], A[leftwall]) (7)     leftwall = leftwall + 1 (8)    end (9)  end (10)   Swap (A[low], A[leftwall]) (11)   returnleftwall (12) end


## 5.1. Generate Initial Solutions

For generating initial solutions, consider the following inputs: machines = 4, parts = 5, cells = 2,Mmax⁡ = 2, and a matrix M×P (see Table 6).Table 6
MatrixM×P.
Part 1 Part 2 Part 3 Part 4 Part 5 Machine 1 1 0 0 1 1 Machine 2 1 0 1 0 1 Machine 3 0 1 0 1 1 Machine 4 1 0 1 0 0Considering data in Table6, the first step to generate an initial solution is as follows.Step 1.
Generate random allocations in the matrixM×P with some random method. This matrix M×C (see Table 7) satisfies constraints that exists in only one machine in a cell and Mmax⁡ is less than or equal to 2 in an entire cell.Table 7
MatrixM×C.
Cell 1 Cell 2 Machine 1 1 0 Machine 2 0 1 Machine 3 0 1 Machine 4 1 0Step 2.
Generate with a manual method the matrixP×C from the matrix M×C. For this, a connection is established with the matrix M×P and with the matrix solution M×C. In lightface, machines correspond to the cell number 1 and, in bold, machines correspond to cell number 2 (see Table 8).Table 8
Relationship between the matrixM×P with the matrix M×C.
Part 1 Part 2 Part 3 Part 4 Part 5 Cell 1 Cell 2 Machine 1 1 0 0 1 1 1 0 Machine 2 1 0 1 0 1 0 1 Machine 3 0 1 0 1 1 0 1 Machine 4 1 0 1 0 0 1 0The manual method for determining the matrixP×C involves adding the value 1 out of every position i, j of the M×P matrix and putting this value in the temporary array of sums according to the corresponding cell. We perform the operation for each value of positions i, j of the matrix M×P (see Table 9).Table 9
Generation of temporary matrix sum.
Part 1 Part 2 Part 3 Part 4 Part 5 Cell 1 Cell 2 Machine 1 1 0 0 1 1 1 0 Machine 2 1 0 1 0 1 0 1 Machine 3 0 1 0 1 1 0 1 Machine 4 1 0 1 0 0 1 0  Sum of Cell 1 2 0 1 1 1 Sum of Cell 2 1 1 1 1 2Example 1.
(i)
M × P [ 1,1 ] = 1 → is the value that is associated with cell 1; we add this value to the Row SumofCell1. (ii)
M × P [ 2,1 ] = 1 → is the value that is associated with cell 2; we add to this value to the Row SumofCell2. (iii)
M × P [ 3,1 ] = 0 → is the value that is associated with cell 2; we add to this value to the Row SumofCell2. (iv)
M × P [ 4,1 ] = 1 → is the value that is associated with cell 1; we add to this value to the Row SumofCell1.Step 3.
From the results of Table9, we build a partial solution to the matrix P×C (see Table 10).Table 10
MatrixP×C.
Cell 1 Cell 2 Part 1 2 1 Part 2 0 1 Part 3 1 1 Part 4 1 1 Part 5 1 2Step 4.
Find possible solutions toP×C.We must choose the values of the positionsi, j that belong to the temporary matrix M×P and have the largest values of each row. Subsequently, we replace larger values assigning them the value 1, and for the other values in the row we assign them the value of 0 (see Table 11). In case of draw, that is, the entire row has equal numbers, we keep unchanged if the value of their positions is 1. In the case that the same numbers are greater than 1, to each number greater than 1, we assign them a value of 1.Table 11
MatrixP×C.
Cell 1 Cell 2  Cell 1 Cell 2 Part 1 2 1 → 1 0 Part 2 0 1 0 1 Part 3 1 1 1 1 Part 4 1 1 1 1 Part 5 1 2 0 1We consider rows having values equal to 1 in this case correspond to rows pertaining to machines 3 and 4. From this point, we generate all possible combinations of matrices and randomly choose one (see Table12).Table 12
All possible combinations of matricesP×C.
Cell 1 Cell 2  Cell 1 Cell 2 Part 1 1 0 Part 1 1 0 Part 2 0 1 Part 2 0 1 Part 3 1 0 Part 3 1 0 Part 4 1 0 Part 4 0 1 Part 5 0 1 Part 5 0 1  Cell 1 Cell 2  Cell 1 Cell 2  Part 1 1 0 Part 1 1 0 Part 2 0 1 Part 2 0 1 Part 3 0 1 Part 3 0 1 Part 4 1 0 Part 4 0 1 Part 5 0 1 Part 5 0 1


## 5.2. Generating Neighboring Solutions

To generate a neighboring solution, we consider the following inputs: machines = 4, parts = 5, cells = 2,Mmax⁡ = 2, matrix M×P, matrix M×C, and matrix P×C (see Table 13).Table 13
Initial matrices for generating neighboring solutions.
(a) Cell 1 Cell 2 Cell 3 Cell 4 Cell 5 Machine 1 1 0 0 1 1 Machine 2 1 0 1 0 1 Machine 3 0 1 0 1 1 Machine 4 1 0 1 0 0 (b) Cell 1 Cell 2 Machine 1 1 0 Machine 2 0 1 Machine 3 0 1 Machine 4 1 0 (c) Cell 1 Cell 2 Part 1 1 0 Part 2 0 1 Part 3 0 1 Part 4 1 0 Part 5 0 1Step 1.
Randomly choose a positioni, j in the matrix M×C that has a value of 1 and we work with the machine associated with that row i. This is the same as selecting a machine and working with its row i. In this case, we chose randomly the position of the matrix M×C[2,2] with a value of 1, which corresponds to machine 2 (see Table 14).Table 14
Machine selection.
(a) Cell 1 Cell 2 Machine 1 1 0 Machine 2 0 1 Machine 3 0 1 Machine 4 1 0 (b) Cell 1 Cell 2 Machine 1 1 0 Machine 2 0 1 Machine 3 0 1 Machine 4 1 0Step 2.
Then on machine 2, we randomly pick a cell that has a 0. In this case, we choose the position of the matrixM×C[2,1]; we accomplish a replacement of the value of 0 to 1 and finally realize a replacement for M×C[2,2] value of 1 to 0. You can see the result of this operation in Table 15. In the case that the constraints are inconsistent, you must repeat the procedure from Step  1.Table 15
Final matrixM×C.
Cell 1 Cell 2 Machine 1 1 0 Machine 2 1 0 Machine 3 0 1 Machine 4 1 0Step 3.
We carry out the construction of the matrixP×C using the manual method explained in Section 5.1.


## 5.3. Flowchart of Migrating Birds Optimization

This section describes the stages of the algorithm MBO, as it integrates with the problem of MPCFP and in which stages parallel arrangement algorithms are applied. For a better understanding, a flow chart has been included (see Figure3) which is divided into 4 main phases: algorithm initialization, a tour process, leader replacement, and algorithm finalization.Figure 3
Flowchart of Migrating Birds Optimization.


### 5.3.1. Algorithm Initialization

Parameter Initialization (Stage 1 in Figure3). At this stage, all the values required by the MBO metaheuristic are initialized; all the values required by the problem of MPCFP and that type of sorting algorithm are to be implemented in the metaheuristic.Among the metaheuristic values, there are(i)
number of birds (n),(ii)
number of neighbors (k),(iii)
number of tours (m),(iv)
number of shared solutions (x),(v)
number of iterations (I).And between complementary metaheuristic parameters, we can include(i)
leader exchange mode, where there are 2 types of changes of leader; exchange the leader with the successor and exchange the leader with the best;(ii)
sort type applied in the initial birds flock, where there is an ordering with random birds in the flock and another with birds ordered according to their fitness.Among the parameters required for the problem MPCFP, we have(i)
incidence matrix (M×P),(ii)
number of machines (M),(iii)
number of parts (P),(iv)
number of cells (C),(v)
maximum number of machines in a cell (Mmax⁡).Finally, for the types of sorting applied to MBO, we have the following parameters:(i)
Type of sorting algorithm: quick sort or merge sort.(ii)
Sorting technique: normal or with threads.(iii)
Number of threads if required.Generate Initial Solutions (Stage 2 in Figure3). At this stage, we generate initial solutions according to the method described in Section 5.1. These solutions must satisfy the three constraints of model MPCFP.Create Initial Flock (Stage 3 in Figure3). From the initial solutions, we create an array of birds, and finally ordered arrangement created the conceptual V-formation birds. For it, we assign the first position (first solution) in the array as the leader of the flock, and we perform an alternate distribution of birds between each side of the flock for the rest of the birds. We must consider that the birds are always sorted by fitness from low to high, the bird with lower fitness being the best solution to the problem (MPCFP is a minimization problem). Furthermore, we must consider that this is a stage in which we incorporate parallel order by quick sort and merge sort.


### 5.3.2. A Tour Process

This phase has two subphases internally: evolution of the leader bird and the evolution of the other birds. The evolution of the leader bird phase has one stage (generating neighboring solutions for the leader) and the evolution of the other birds phase has two stages (generating neighboring solutions for the other birds and sharing neighboring solutions that are not used by the leader with the other birds).Generate Neighboring Solutions for the Leader (Stage 4 in Figure3). This stage consists of generating neighboring solutions according to the steps outlined in Section 5.2. Subsequently, these neighboring solutions are sorted using an algorithm of parallel sort; see line (5) in the algorithm MBO (Algorithm 1).Generate Neighboring Solutions for the Other Birds (Stage 5 in Figure3). In this stage, we create k-x neighboring solution to each bird of the flock; then these birds are sorted by an algorithm of parallel sort; see lines (7) and (8) in the algorithm MBO (Algorithm 1).Share Neighboring Solutions That Are Not Used by the Leader with the Other Birds (Stage 6 in Figure3). Share the other neighboring solutions of the leader with the other sides of the V-formation of birds; this is done alternately from left to right or from right to left. After sharing the neighboring solutions, we performed a sorting using an algorithm of parallel sort in all neighboring solutions that every bird in the flock has (not including the leader).Leader Replacement (Stage 7 in Figure3). At this stage, we performed a replacement of leader; for this we choose the nearest successor; that is, choose one of the birds closer to the leader. The successor will take its place and the leader will be available at the end of the flock. We must take into consideration that if we choose a successor belonging to the left section of the flock, the leader will pass to the end of the left section. The same procedure applies to the right section of the flock (see Algorithm 2).Algorithm 2:Replace leader with successor.
(1)   int⁡type_of_sort = Get_Type_Of_Sort () (2)   boolean left_or_right_side = Random_Boolean () (3)   Main FunctionReplace_Leader_With_Successor ()is (4)    ifleft_or_right_sidethen (5)     Change_Leader_With_Left_Birds () (6)     Sort_Left_Birds (type_of_sort) (7)    else (8)     Change_Leader_With_Right_Birds () (9)     Sort_Right_Birds (type_of_sort) (10)  end (11)  left_or_right_side = !left_or_right_side (12) endAlgorithm Finalization (Stage 8 in Figure3). In this step, the fitness of the leader is obtained; in addition, a procedure to remove a response matrix explicitly is made; that is, we construct an incidence matrix AM[P] according to the order given by the matrices of solutions Y and Z. The order is according to the index of less than most of the machines and parts (see Algorithm 3).Algorithm 3:Convert matrix M×C and P×C to final matrix.
(1)   Main FunctionConvert_to_final_matrix (int⁡A[i][j], int⁡Y[][], int⁡Z[][]) is (2)   int⁡final_matrix[M][P], temp_matrix[M][P], ii=0, jj=0 (3)   /∗ Sort machines ∗/ (4)   forint⁡k=0; k<C; k++do (5)   forint⁡i=0; i<M; i++do (6)     ifY[i][k]==1then (7)         forint⁡j=0; j<P; j++do (8)        temp_matrix[ii][j]=A[i][j] (9)         end (10)       ii=ii+1 (11)      end (12)    end (13)    end (14)   /∗ Sort parts ∗/ (15)   forint⁡k=0; k<C; k++do (16)    forint⁡j=0; j<P; j++do (17)     ifZ[j][k]==1then (18)       forint⁡i=0; i<M; i++do (19)        final_matrix[i][jj]=temp_matrix[i][j] (20)       end (21)       jj=jj+1 (22)     end (23)    end (24)    end (25)    returnfinal_matrix (26) end


### 5.3.3. Sorting Algorithm

For MBO, we use two sorting algorithms, merge sort and quick sort, in which we executed sequentially and in parallel using threads.Merge Sort. It was developed in 1945 by John Von Neumann. It is a search algorithm of complexity O(nlog⁡n) (see Table 16). Algorithm 4 illustrates a general pseudocode for merge sort.Table 16
Complexity sorting algorithm.
Name Best Average Worst Memory Method Stable Merge sort O ( n log ⁡ n ) O ( n log ⁡ n ) O ( n log ⁡ n ) Depends Merging Yes Quick sort O ( n log ⁡ n ) O ( n log ⁡ n ) O ( n 2 ) O ( log ⁡ n ) Partition DependsAlgorithm 4:Merge sort.
(1)   Main FunctionMergeSort (Object[]A) is (2)    Object[]result, left, right (3)    iflength(A)≤1then (4)   returnA (5)    else (6)   int⁡middle=length(A)/2 (7)   fori=0to middledo (8)     left[i]=A[i] (9)   end (10)    fori=middle+1to length(A) do (11)      right[i]=A[i] (12)    end (13)    left = MergeSort (left) (14)    right = MergeSort (right) (15)    result = Merge (left, right) (16)    returnresult (17)  end (18) endQuick Sort. It was developed in 1959 by Charles Richard Hoare. It is a search algorithm of complexity O(nlog⁡n) (see Table 16). Algorithm 5 illustrates a general pseudocode for quick sort.Algorithm 5:Quick sort.
(1)   Main FunctionQuickSort (Object[]A, int⁡low, int⁡high) is (2)   iflow<highthen (3)    pivot_location=  Partition (A, low, high) (4)    QuickSort (A, low, pivot_location) (5)    QuickSort (A, pivot_location + 1, high) (6)   end (7)   end (1)   FunctionPartition (Object[]A, int⁡low, int⁡high) is (2)   Object pivot = A[low] (3)   int⁡leftwall = low (4)   fori=low+1to highdo (5)    ifA[i]<pivotthen (6)     Swap (A[i], A[leftwall]) (7)     leftwall = leftwall + 1 (8)    end (9)  end (10)   Swap (A[low], A[leftwall]) (11)   returnleftwall (12) end


## 5.3.1. Algorithm Initialization

Parameter Initialization (Stage 1 in Figure3). At this stage, all the values required by the MBO metaheuristic are initialized; all the values required by the problem of MPCFP and that type of sorting algorithm are to be implemented in the metaheuristic.Among the metaheuristic values, there are(i)
number of birds (n),(ii)
number of neighbors (k),(iii)
number of tours (m),(iv)
number of shared solutions (x),(v)
number of iterations (I).And between complementary metaheuristic parameters, we can include(i)
leader exchange mode, where there are 2 types of changes of leader; exchange the leader with the successor and exchange the leader with the best;(ii)
sort type applied in the initial birds flock, where there is an ordering with random birds in the flock and another with birds ordered according to their fitness.Among the parameters required for the problem MPCFP, we have(i)
incidence matrix (M×P),(ii)
number of machines (M),(iii)
number of parts (P),(iv)
number of cells (C),(v)
maximum number of machines in a cell (Mmax⁡).Finally, for the types of sorting applied to MBO, we have the following parameters:(i)
Type of sorting algorithm: quick sort or merge sort.(ii)
Sorting technique: normal or with threads.(iii)
Number of threads if required.Generate Initial Solutions (Stage 2 in Figure3). At this stage, we generate initial solutions according to the method described in Section 5.1. These solutions must satisfy the three constraints of model MPCFP.Create Initial Flock (Stage 3 in Figure3). From the initial solutions, we create an array of birds, and finally ordered arrangement created the conceptual V-formation birds. For it, we assign the first position (first solution) in the array as the leader of the flock, and we perform an alternate distribution of birds between each side of the flock for the rest of the birds. We must consider that the birds are always sorted by fitness from low to high, the bird with lower fitness being the best solution to the problem (MPCFP is a minimization problem). Furthermore, we must consider that this is a stage in which we incorporate parallel order by quick sort and merge sort.


## 5.3.2. A Tour Process

This phase has two subphases internally: evolution of the leader bird and the evolution of the other birds. The evolution of the leader bird phase has one stage (generating neighboring solutions for the leader) and the evolution of the other birds phase has two stages (generating neighboring solutions for the other birds and sharing neighboring solutions that are not used by the leader with the other birds).Generate Neighboring Solutions for the Leader (Stage 4 in Figure3). This stage consists of generating neighboring solutions according to the steps outlined in Section 5.2. Subsequently, these neighboring solutions are sorted using an algorithm of parallel sort; see line (5) in the algorithm MBO (Algorithm 1).Generate Neighboring Solutions for the Other Birds (Stage 5 in Figure3). In this stage, we create k-x neighboring solution to each bird of the flock; then these birds are sorted by an algorithm of parallel sort; see lines (7) and (8) in the algorithm MBO (Algorithm 1).Share Neighboring Solutions That Are Not Used by the Leader with the Other Birds (Stage 6 in Figure3). Share the other neighboring solutions of the leader with the other sides of the V-formation of birds; this is done alternately from left to right or from right to left. After sharing the neighboring solutions, we performed a sorting using an algorithm of parallel sort in all neighboring solutions that every bird in the flock has (not including the leader).Leader Replacement (Stage 7 in Figure3). At this stage, we performed a replacement of leader; for this we choose the nearest successor; that is, choose one of the birds closer to the leader. The successor will take its place and the leader will be available at the end of the flock. We must take into consideration that if we choose a successor belonging to the left section of the flock, the leader will pass to the end of the left section. The same procedure applies to the right section of the flock (see Algorithm 2).Algorithm 2:Replace leader with successor.
(1)   int⁡type_of_sort = Get_Type_Of_Sort () (2)   boolean left_or_right_side = Random_Boolean () (3)   Main FunctionReplace_Leader_With_Successor ()is (4)    ifleft_or_right_sidethen (5)     Change_Leader_With_Left_Birds () (6)     Sort_Left_Birds (type_of_sort) (7)    else (8)     Change_Leader_With_Right_Birds () (9)     Sort_Right_Birds (type_of_sort) (10)  end (11)  left_or_right_side = !left_or_right_side (12) endAlgorithm Finalization (Stage 8 in Figure3). In this step, the fitness of the leader is obtained; in addition, a procedure to remove a response matrix explicitly is made; that is, we construct an incidence matrix AM[P] according to the order given by the matrices of solutions Y and Z. The order is according to the index of less than most of the machines and parts (see Algorithm 3).Algorithm 3:Convert matrix M×C and P×C to final matrix.
(1)   Main FunctionConvert_to_final_matrix (int⁡A[i][j], int⁡Y[][], int⁡Z[][]) is (2)   int⁡final_matrix[M][P], temp_matrix[M][P], ii=0, jj=0 (3)   /∗ Sort machines ∗/ (4)   forint⁡k=0; k<C; k++do (5)   forint⁡i=0; i<M; i++do (6)     ifY[i][k]==1then (7)         forint⁡j=0; j<P; j++do (8)        temp_matrix[ii][j]=A[i][j] (9)         end (10)       ii=ii+1 (11)      end (12)    end (13)    end (14)   /∗ Sort parts ∗/ (15)   forint⁡k=0; k<C; k++do (16)    forint⁡j=0; j<P; j++do (17)     ifZ[j][k]==1then (18)       forint⁡i=0; i<M; i++do (19)        final_matrix[i][jj]=temp_matrix[i][j] (20)       end (21)       jj=jj+1 (22)     end (23)    end (24)    end (25)    returnfinal_matrix (26) end


## 5.3.3. Sorting Algorithm

For MBO, we use two sorting algorithms, merge sort and quick sort, in which we executed sequentially and in parallel using threads.Merge Sort. It was developed in 1945 by John Von Neumann. It is a search algorithm of complexity O(nlog⁡n) (see Table 16). Algorithm 4 illustrates a general pseudocode for merge sort.Table 16
Complexity sorting algorithm.
Name Best Average Worst Memory Method Stable Merge sort O ( n log ⁡ n ) O ( n log ⁡ n ) O ( n log ⁡ n ) Depends Merging Yes Quick sort O ( n log ⁡ n ) O ( n log ⁡ n ) O ( n 2 ) O ( log ⁡ n ) Partition DependsAlgorithm 4:Merge sort.
(1)   Main FunctionMergeSort (Object[]A) is (2)    Object[]result, left, right (3)    iflength(A)≤1then (4)   returnA (5)    else (6)   int⁡middle=length(A)/2 (7)   fori=0to middledo (8)     left[i]=A[i] (9)   end (10)    fori=middle+1to length(A) do (11)      right[i]=A[i] (12)    end (13)    left = MergeSort (left) (14)    right = MergeSort (right) (15)    result = Merge (left, right) (16)    returnresult (17)  end (18) endQuick Sort. It was developed in 1959 by Charles Richard Hoare. It is a search algorithm of complexity O(nlog⁡n) (see Table 16). Algorithm 5 illustrates a general pseudocode for quick sort.Algorithm 5:Quick sort.
(1)   Main FunctionQuickSort (Object[]A, int⁡low, int⁡high) is (2)   iflow<highthen (3)    pivot_location=  Partition (A, low, high) (4)    QuickSort (A, low, pivot_location) (5)    QuickSort (A, pivot_location + 1, high) (6)   end (7)   end (1)   FunctionPartition (Object[]A, int⁡low, int⁡high) is (2)   Object pivot = A[low] (3)   int⁡leftwall = low (4)   fori=low+1to highdo (5)    ifA[i]<pivotthen (6)     Swap (A[i], A[leftwall]) (7)     leftwall = leftwall + 1 (8)    end (9)  end (10)   Swap (A[low], A[leftwall]) (11)   returnleftwall (12) end


## 6. Computational Experiments

### 6.1. Configuration Benchmarks

The MPCFP performance was evaluated experimentally using 90 test instances from Boctor’s experiments, composed of 10 problems considering 5 values ofMmax⁡=8,9,10,11,12 with C=2 and 10 instances considering 4 values of Mmax⁡=6,7,8,9 with C=3. The test data are available in [55]. The 90 instances have been executed 31 times using 12 different configurations of sequential and parallel sorting (see Table 18). We must also consider that the sorting algorithms (sequential and parallel) were applied in the following stages (see Figure 3) of MBO:(i)
Stage 3→ create initial flock.(ii)
Stage 4→ generate neighboring solutions for the leader.(iii)
Stage 5→ generate neighboring solutions for other birds.(iv)
Stage 6→ share neighboring solutions that are not used by the leader with the other birds.The optimization algorithm using parallel sorting was coded in Java version 1.8.0_40 using Eclipse IDE for Java Developers Version Mars.1 Release (4.5.1). For running the MBO with parallel sorting, we use Java(TM) SE Runtime Environment (build 1.8.0_40-b27). The parameter values of MBO are described in Table17. Finally, the hardware features that have run instances are MacBook Pro computer (Retina, 13-inch, late 2013) with an Intel Core i5 (processor speed = 2,4 GHz; number of processors = 1; total number of cores = 2; L2 cache per core = 256 KB; L3 cache = 3 MB), 4 GB RAM 1600 MHz DDR3, and Video Card Intel Iris 1536 MB running OS X El Capitan version 10.11.2 (15C50).Table 17
Configuration parameters for MBO.
Name Parameter Value Number of birds n 5 Number of neighbors k 3 Number of tours m 10 Number of shared solutions x 1 Number of iterations I 2591 Leader exchange mode — Exchange the leader with the successor Sort type applied in the initial birds flock — Birds ordered according to their fitnessTable 18
Configuration sorting algorithms.
Algorithm Sequential Threads 1 4 8 16 32 Merge sort Yes Yes Yes Yes Yes Yes Quick sort Yes Yes Yes Yes Yes Yes


### 6.2. Results

Tables19 and 20 represent a summary of the results provided in Appendix A [55]. These summary tables describe the average results of 90 instances. Column 1 (threads) corresponds to the identifier assigned to the number of threads used in the search algorithm. Column 2 (execution time-BET) shows the best execution time obtained in milliseconds. Column 3 (execution time-AVG) describes the average time in milliseconds of the finest time of execution of MBO. Column 4 (execution time-ST) represents the standard deviation of the best times of execution obtained by MBO. Column 5 (cycle-BC) shows the cycle in which the optimal value was found. Column 6 (cycle-AVG) describes the average cycle. Column 7 (cycle-ST) represents the standard deviation. Column 8 (time cycle-BTC) shows the best cycle time in which the optimal value was found in milliseconds. Column 9 (time cycle-AVG) describes the average cycle in milliseconds. Column 10 (time cycle-ST) represents the standard deviation in milliseconds. Finally, we must consider all tests that have achieved the global optimum.Table 19
Result of merge sort.
Threads Execution time (ms) Cycle Time cycle (ms) BET AVG ST BC AVG SD BTC AVG SD Without threads 153.9667 171.1556 21.1539 3.1667 9.0778 4.7263 13.6778 43.3778 23.8747 1 155.5556 168.4111 13.9276 3.0222 9.0778 4.7812 13.2333 42.6556 22.9180 4 153.9333 170.9556 28.8802 2.8556 9.1556 4.9501 12.1444 43.7333 25.6019 8 152.7333 155.8667 3.8451 2.9667 9.2778 4.8785 12.2111 40.2333 20.2717 16 153.1333 161.8222 11.5292 2.9222 9.1222 4.9112 12.2444 40.9000 21.5416 32 153.9222 169.5000 21.8506 3.1889 9.2000 4.8937 13.5667 43.6333 24.7712  Minimum 152.7333 155.8667 3.8451 2.8556 9.0778 4.7263 12.1444 40.2333 20.2717 Maximum 155.5556 171.1556 28.8802 3.1889 9.2778 4.9501 13.6778 43.7333 25.6019Table 20
Result of quick sort.
Threads Execution time (ms) Cycle Time cycle (ms) BET AVG ST BC AVG SD BTC AVG SD Without threads 153.3333 163.0000 12.7284 2.9889 9.0111 4.9168 12.5222 41.2222 22.1071 1 154.5778 167.9000 15.5926 3.0889 9.0778 4.8703 13.1778 42.2667 22.3487 4 153.3111 163.6778 12.2109 3.1333 9.2000 4.9019 13.3222 41.7444 22.4733 8 169.2889 195.6667 26.3893 2.8667 9.1667 4.8796 13.5667 49.6556 27.5041 16 154.3444 169.7778 18.9543 2.8111 8.9889 4.7619 12.1333 42.2444 23.6231 32 156.0889 176.7222 25.8717 2.9889 9.1111 4.8993 13.4111 45.5889 25.9852  Minimum 153.3111 163.0000 12.2109 2.8111 8.9889 4.7619 12.1333 41.2222 22.1071 Maximum 169.2889 195.6667 26.3893 3.1333 9.2000 4.9168 13.5667 49.6556 27.5041Execution Time Analysis. The execution time is the total time when the metaheuristic was searching in the search space for the best solution. In this sense, according to what is described in Tables 19 and 20, we can consider that the merge sort algorithm using 8 threads had the lowest average time (152.7333 ms) to run 90 instances (see column 2: execution time-BET in Tables 19 and 20). In addition, when we compare the times of running the metaheuristic sequentially (without threads and using merge sort algorithm), regarding the best time to run the metaheuristic reached with threads (8 threads), we can see that using 8 threads is an improvement in the execution time of the metaheuristic. This behavior can also be seen in Tables 19 and 20 (see column 3: execution time-AVG in Tables 19 and 20).Cycle Analysis. A cycle is fulfilled after replacing the leader of the flock (stage 7 in Figure 3). Currently with a parameter of 2591 iterations (I), we can achieve 38 cycles. Consequently, the leader of the flock during the algorithm changes its value 38 times. Basically, the cycles, where the best value has been obtained before the execution is finished, provided us with information to reduce the iteration time assigned in the input parameter of the metaheuristic. Considering the values of the cycles (see column 6: cycle-AVG in Tables 19 and 20), we can approximate an average value in 9, for the number of cycles to find a global optimum, for using both merge sort and quick sort, with threads and without threads. Also, this involves reducing the value of the iteration limit I=2591→I=561. But we must also consider the random factor having the metaheuristic (see stage 2 in Figure 3, stage 4 in Figure 3, and stage 5 in Figure 3), and this randomness allows the possibility of finding a global optimum with fewer cycles (see column 5: cycle-BC in Tables 19 and 20). Therefore, this is a recommended change, but it is not enough to always find a global optimum. The quick sort algorithm using threads having irregular times is even much worse than the quick sort used sequentially.Time Cycle Analysis. In relation to the average cycle time where the best optimum was found, we note that, according to the tests, the merge sort algorithm with 8 threads has been the least time used (see column 9: time cycle-AVG in Tables 19 and 20. It should be considered interesting results as it has achieved better times using parallel sort versus sequential sort, mainly by using merge sort with 4, 8, and 16 threads and quick sort with 16 threads (see column 8: time cycle-BTC in Tables 19 and 20).


## 6.1. Configuration Benchmarks

The MPCFP performance was evaluated experimentally using 90 test instances from Boctor’s experiments, composed of 10 problems considering 5 values ofMmax⁡=8,9,10,11,12 with C=2 and 10 instances considering 4 values of Mmax⁡=6,7,8,9 with C=3. The test data are available in [55]. The 90 instances have been executed 31 times using 12 different configurations of sequential and parallel sorting (see Table 18). We must also consider that the sorting algorithms (sequential and parallel) were applied in the following stages (see Figure 3) of MBO:(i)
Stage 3→ create initial flock.(ii)
Stage 4→ generate neighboring solutions for the leader.(iii)
Stage 5→ generate neighboring solutions for other birds.(iv)
Stage 6→ share neighboring solutions that are not used by the leader with the other birds.The optimization algorithm using parallel sorting was coded in Java version 1.8.0_40 using Eclipse IDE for Java Developers Version Mars.1 Release (4.5.1). For running the MBO with parallel sorting, we use Java(TM) SE Runtime Environment (build 1.8.0_40-b27). The parameter values of MBO are described in Table17. Finally, the hardware features that have run instances are MacBook Pro computer (Retina, 13-inch, late 2013) with an Intel Core i5 (processor speed = 2,4 GHz; number of processors = 1; total number of cores = 2; L2 cache per core = 256 KB; L3 cache = 3 MB), 4 GB RAM 1600 MHz DDR3, and Video Card Intel Iris 1536 MB running OS X El Capitan version 10.11.2 (15C50).Table 17
Configuration parameters for MBO.
Name Parameter Value Number of birds n 5 Number of neighbors k 3 Number of tours m 10 Number of shared solutions x 1 Number of iterations I 2591 Leader exchange mode — Exchange the leader with the successor Sort type applied in the initial birds flock — Birds ordered according to their fitnessTable 18
Configuration sorting algorithms.
Algorithm Sequential Threads 1 4 8 16 32 Merge sort Yes Yes Yes Yes Yes Yes Quick sort Yes Yes Yes Yes Yes Yes


## 6.2. Results

Tables19 and 20 represent a summary of the results provided in Appendix A [55]. These summary tables describe the average results of 90 instances. Column 1 (threads) corresponds to the identifier assigned to the number of threads used in the search algorithm. Column 2 (execution time-BET) shows the best execution time obtained in milliseconds. Column 3 (execution time-AVG) describes the average time in milliseconds of the finest time of execution of MBO. Column 4 (execution time-ST) represents the standard deviation of the best times of execution obtained by MBO. Column 5 (cycle-BC) shows the cycle in which the optimal value was found. Column 6 (cycle-AVG) describes the average cycle. Column 7 (cycle-ST) represents the standard deviation. Column 8 (time cycle-BTC) shows the best cycle time in which the optimal value was found in milliseconds. Column 9 (time cycle-AVG) describes the average cycle in milliseconds. Column 10 (time cycle-ST) represents the standard deviation in milliseconds. Finally, we must consider all tests that have achieved the global optimum.Table 19
Result of merge sort.
Threads Execution time (ms) Cycle Time cycle (ms) BET AVG ST BC AVG SD BTC AVG SD Without threads 153.9667 171.1556 21.1539 3.1667 9.0778 4.7263 13.6778 43.3778 23.8747 1 155.5556 168.4111 13.9276 3.0222 9.0778 4.7812 13.2333 42.6556 22.9180 4 153.9333 170.9556 28.8802 2.8556 9.1556 4.9501 12.1444 43.7333 25.6019 8 152.7333 155.8667 3.8451 2.9667 9.2778 4.8785 12.2111 40.2333 20.2717 16 153.1333 161.8222 11.5292 2.9222 9.1222 4.9112 12.2444 40.9000 21.5416 32 153.9222 169.5000 21.8506 3.1889 9.2000 4.8937 13.5667 43.6333 24.7712  Minimum 152.7333 155.8667 3.8451 2.8556 9.0778 4.7263 12.1444 40.2333 20.2717 Maximum 155.5556 171.1556 28.8802 3.1889 9.2778 4.9501 13.6778 43.7333 25.6019Table 20
Result of quick sort.
Threads Execution time (ms) Cycle Time cycle (ms) BET AVG ST BC AVG SD BTC AVG SD Without threads 153.3333 163.0000 12.7284 2.9889 9.0111 4.9168 12.5222 41.2222 22.1071 1 154.5778 167.9000 15.5926 3.0889 9.0778 4.8703 13.1778 42.2667 22.3487 4 153.3111 163.6778 12.2109 3.1333 9.2000 4.9019 13.3222 41.7444 22.4733 8 169.2889 195.6667 26.3893 2.8667 9.1667 4.8796 13.5667 49.6556 27.5041 16 154.3444 169.7778 18.9543 2.8111 8.9889 4.7619 12.1333 42.2444 23.6231 32 156.0889 176.7222 25.8717 2.9889 9.1111 4.8993 13.4111 45.5889 25.9852  Minimum 153.3111 163.0000 12.2109 2.8111 8.9889 4.7619 12.1333 41.2222 22.1071 Maximum 169.2889 195.6667 26.3893 3.1333 9.2000 4.9168 13.5667 49.6556 27.5041Execution Time Analysis. The execution time is the total time when the metaheuristic was searching in the search space for the best solution. In this sense, according to what is described in Tables 19 and 20, we can consider that the merge sort algorithm using 8 threads had the lowest average time (152.7333 ms) to run 90 instances (see column 2: execution time-BET in Tables 19 and 20). In addition, when we compare the times of running the metaheuristic sequentially (without threads and using merge sort algorithm), regarding the best time to run the metaheuristic reached with threads (8 threads), we can see that using 8 threads is an improvement in the execution time of the metaheuristic. This behavior can also be seen in Tables 19 and 20 (see column 3: execution time-AVG in Tables 19 and 20).Cycle Analysis. A cycle is fulfilled after replacing the leader of the flock (stage 7 in Figure 3). Currently with a parameter of 2591 iterations (I), we can achieve 38 cycles. Consequently, the leader of the flock during the algorithm changes its value 38 times. Basically, the cycles, where the best value has been obtained before the execution is finished, provided us with information to reduce the iteration time assigned in the input parameter of the metaheuristic. Considering the values of the cycles (see column 6: cycle-AVG in Tables 19 and 20), we can approximate an average value in 9, for the number of cycles to find a global optimum, for using both merge sort and quick sort, with threads and without threads. Also, this involves reducing the value of the iteration limit I=2591→I=561. But we must also consider the random factor having the metaheuristic (see stage 2 in Figure 3, stage 4 in Figure 3, and stage 5 in Figure 3), and this randomness allows the possibility of finding a global optimum with fewer cycles (see column 5: cycle-BC in Tables 19 and 20). Therefore, this is a recommended change, but it is not enough to always find a global optimum. The quick sort algorithm using threads having irregular times is even much worse than the quick sort used sequentially.Time Cycle Analysis. In relation to the average cycle time where the best optimum was found, we note that, according to the tests, the merge sort algorithm with 8 threads has been the least time used (see column 9: time cycle-AVG in Tables 19 and 20. It should be considered interesting results as it has achieved better times using parallel sort versus sequential sort, mainly by using merge sort with 4, 8, and 16 threads and quick sort with 16 threads (see column 8: time cycle-BTC in Tables 19 and 20).


## 7. Conclusions

In this paper, we use a Migrating Birds Optimization algorithm by a parallel sorting to solve Machine-Part Cell Formation Problems. Computational experiments using conventional hardware resources have been conducted in 90 test instances, 2 well-known sorting algorithms, 1 sequential configuration, and 5 thread configurations (1, 4, 8, 16, and 32), giving a total of 1080 benchmarks. Among the main results, we highlight a new alignment of the MBO parameters to solve MPCFP. The new configuration consists of the following parameter values: number of birds (n→5), number of neighbors (k→3), number of tours (m→10), number of shared solutions (x→1), and number of iterations (I→2591). We observed a decrease in cycles from 38 to 9, which means that the leader of the flock reaching the cycle number 9 has a very high probability of finding the global optimum; therefore, we can reduce the number of iteration limit from I=2591 to I=561. This observation of the number of cycles applied to all benchmarks.In addition, it is important to note that quick sort algoritm has variable times in the execution of MBO (see column 9: time cycle-AVG in Table20). There have been cases in which quick sort algorithm runs without threads; it is even more favorable than when run with threads. Otherwise, with the merge sort algorithm, we found promising results. We can consider that the merge sort algorithm using 8 threads shows a reduction in execution time compared to using sequential sorting algorithm.Among the guidelines for future research, we can point to applying different ways of generating initial solutions as well as of generating neighboring solutions. We can also compare them with other sorting algorithms implemented in MBO.



---

*Source: 9402503-2016-03-31.xml*