A Discrete Multi-Objective Artificial Bee Colony Algorithm for a Real-World Electronic Device Testing Machine Allocation Problem

In this study, the EDTMAP was investigated based on a real-world electronic device production factory with multiple testing workshops. Each workshop tests different types of products to determine their reliability. Each product is sequentially tested at various stages, and the testing times at the different stages are different. Multiple machines can be used to test the products at the same stage. Compatibility and quantity constraints exist for machine interfaces at each stage. If the interfaces of the machine match a stage and satisfy the quantity requirement for the stage, the machine can be scheduled for the stage. The total number of products tested at each stage per week is calculated based on the testing time and the number of machines at each stage. The minimum amount of products tested in the series of stages is the weekly production. In addition, all the testing machines are initially distributed in different workshops. These machines therefore must be scheduled for multiple workshops. We attempt to keep the total scheduling distance among the machines as short as possible, while keeping the total production of the factory as large as possible.

Briefly, the EDTMAP can be described as follows: there are m testing workshops in a factory, and each workshop produces n types of product. In addition, there are different types of testing machines in the factory that are initially distributed in various workshops. The number of machines of the same type in each workshop differs. Currently, it is necessary to schedule machines for different stages in multiple workshops to test products to maximize weekly production. Meanwhile, the total scheduling distance among the machines with respect to multiple workshops should be as short as possible. The main characteristic of the EDTMAP is that multiple machines that meet the adaptability constraint of interfaces can be allocated at the same stage.

There are some necessary assumptions for the proposed mathematical model of the EDTMAP:

The notations and decision variables for the mathematical model of the EDTMAP are given as Table 1.

Based on the above notations, a multi-objective mathematical model of the EDTMAP is designed to simultaneously maximize the total production and the inverse of the total scheduling distance among machines. The mathematical model is as follows:where f₁ denotes the weighted sum of production in all workshops and f₂ represents the inverse of the total scheduling distance among all testing machines. The constraints of this problem are as follows:Constraint (3) computes the weekly production of the testing machine at each stage. Constraint (4) calculates the maximum total scheduling distance among all machines. Constraint (5) ensures that only machines with interfaces that match a stage can be scheduled for the stage. Constraint (6) ensures that only machines that meet the interface quantity requirement of a stage can be scheduled for the stage. Constraint (7) guarantees that any machine can be scheduled for only one stage every week at most. Constraint (8) describes the range of the decision variables.

Based on the above model, there are some differences between the EDTMAP and the traditional MAP. The classic MAP only considers machine scheduling between multiple production lines in a single workshop, but not that among various workshops. Conversely, the EDTMAP considers machine scheduling between numerous production lines as well as between multiple workshops. Scheduling machines for a different workshop may increase productivity, but the scheduling distance among machines will increase accordingly, resulting in increased machine damage probability and cost. Balancing these two objectives is the focus of our algorithm design, as introduced in the next section.

In addition, the traditional MAP does not need to consider the interface compatibility of machines. However, the EDTMAP should consider compatibility and quantity constraints for machine interfaces at each stage. The machine can be scheduled for the stage only if the interfaces of the machine match the stage and satisfy the quantity requirement for the stage.

Table 2a–c describes an example of the EDTMAP. Table 2a describes the two testing workshops in a factory. Each workshop tests two types of products, and each type of product is tested sequentially in two stages. The testing times and required interface quantities of the products at each stage are listed in Table 2a. Table 2b lists the types and number of machines in each workshop. The matching stage and interface quantity of each type of machine are listed in Table 2b. Table 2c shows the distance between workshops. If a machine is not in use, then the scheduling distance is 0. Handling distances exist in the same workshop. Therefore, if the initial workshop of a machine is the same as the workshop where it is scheduled, then the scheduling distance is 0.5. Table 3 shows the allocation scheme for the testing machines in this example. “M3W1 (2)” denotes that two third-type machines (M3) are initially in the first workshop (W1). In the allocation scheme, the two third-type machines are scheduled to test product A2T2R at Stage 2 in W1. “Null” denotes that no machine is scheduled for the stage.

In this paper, a DMOABC algorithm to obtain non-dominated solutions for balancing the production and scheduling distances is presented. Considering the compatibility and quantity constraints for the interfaces of machines, we designed three operators, i.e., FSG, LSO, and XO, to ensure the feasibility of solutions and cause the population to evolve in the correct direction. FSG is designed to ensure that the initial solution is a feasible machine-allocation scheme. LSO is used as a solution to execute a local search. This effectively improves the local search ability of the DMOABC algorithm. A slight change in the solutions helps the algorithm to jump out of the local optimum. XO implements a crossover operator that allows individuals in the population to exchange information with each other. This effectively improves the global search ability of the DMOABC algorithm. Hence, LSO and XO can balance the local search and global search abilities of DMOABC.

The original ABC algorithm was designed to solve continuous optimization problems. Considering that the EDTMAP is a discrete optimization problem, we modified the encoding to make the solution a feasible allocation scheme. The proposed DMOABC employs a fast non-dominated sorter and a crowding distance sorter [12] to store the non-dominated individuals from each generation to the next. The procedure for the proposed DMOABC is illustrated in Figure 1.

The critical elements of DMOABC are the FSG, LSO, XO, fast non-dominated sorter, and crowding distance sorter, which are described in detail below.

A feasible solution for the EDTMAP is a machine-allocation scheme that satisfies the given allocation constraints. First, we define a permutation A_k that includes all stages of n types of products in m workshops. Then, for each stage k ∈ A_k, the unallocated machine that matches stage k is sorted into a set S_l. For each machine l ∈ S_l, a number r in the range [0, 1] is randomly generated. If r < 0.5, machine l is allocated to stage k; otherwise, the machine is not assigned. Finally, a feasible machine-allocation scheme is generated. The pseudo-code of the FSG is outlined in Operator: FSG.

The LSO is used by employed bees to execute a local search, enabling them to look for nectar separately. First, we define a permutation A_k that includes the stages of n types of products in m workshops. Subsequently, in each stage, k ∈ A_k is selected to execute the local search. There are four neighborhood structures available: (1) add one of the machines that has not been allocated and matches stage k to stage k. (2) Reduce one of the existing machines at stage k. (3) Select one of the machines that has not been allocated and matches stage k with less scheduling distance or interface quantity to replace one of the existing machines at stage k. (4) Nothing has changed at stage k. Finally, a new machine allocation scheme is generated after the local search has been completed for each stage. The pseudo-code of the LSO is shown in Operator: LSO.

An illustrative example of the LSO is shown in Table 4, based on the case described in Table 2a–c above. For the sake of brevity, we use “W1, A2T2R, S1” to represent stage 1 of product A2T2R in workshop 1. “M3W2N1” denotes the first of the third type of machines in the second workshop. The number r generated for each stage is [4, 1, 1, 1, 2, 2, 4, 3]. Therefore, “W1, A2T2R, S1” and “W2, B2T4R, S1” have not changed. “W1, A2T2R, S2”, “W1, A2T4R, S1” and “W1, A2T4R, S2” add one machine. “W2, B2T2R, S1” and “W2, B2T2R, S2” reduce one machine. “W2, B2T4R, S2” exchanges one machine.

The XO is designed to allow onlooker bees to exchange information so that the bee colony can move in the nectar direction. The crossover operation is as follows: (1) randomly choose two stages as the cross points. (2) The machine allocation scheme is copied at stages between the two cross points from the onlooker bee to a newly employed bee. (3) Copy the machine allocation scheme at stages outside the two cross points from the initially employed bee to the newly employed bee. (4) Remove repetitive machinesfrom the stages outside the two cross points for the newly employed bee. The pseudo-code for the XO is shown in Operator: XO.

An illustrative example of the XO is given in Table 5a–c, whose symbolic representation is the same as that describing the LSO. First, two stages are randomly selected as the cross points: “W1, A2T2R, S2” and “W1, A2T4R, S2. The green shades represent the machine allocation within the crossover points. Second, the machine allocation scheme is copied at the stages between the cross points from the onlooker bee to a newly employed bee. Then, the machine allocation scheme is copied at the stages outside the cross points from the employed bee to the newly employed bee. Finally, the duplicate machines “M2W2N1” at stage “W2, B2T2R, S1” and “M4W1N1” and “M4W1N2” at stage “W2, B2T2R, S2” are removed from the initially employed bee to obtain a newly employed bee. Red lines indicate the removal operations.

The design of the non-dominated sorter is based on NSGA-II [12], which is used to divide all solutions into different levels. The specific procedure of the sorter is as follows: (1) for each solution p, store each solution dominated by p in a solution set S_p and calculate n_p, the total number of solutions dominating p. (2) Put the solutions that have not been dominated by any solution (i.e., n_p = 0) into level 1. (3) For each solution p belonging to level 1, visit each solution q in S_p and set n_q = n_q −1. n_q = 0 implies that q is dominated by solutions belonging to level 1, so put q into level 2. (4) As in Step 3, all solutions can be assigned to different levels. The pseudo-code of the non-dominated sorter is presented in Algorithm: Non-dominated sorter.

A crowding distance sorter based on NSGA-II [12] is employed. The specific procedure for the sorter is as follows: (1) the crowding distance of each solution is set to 0. (2) For each objective m, the solution set is sorted according to the objective function value in ascending order. We then set the crowding distances of the first and last solutions to infinity. Finally, other solutions are assigned a crowding distance value equal to the absolute normalized difference in the function values of two adjacent solutions. The corresponding procedure for the crowding distance sorter is described in Algorithm: Crowding distance sorter.

In this section, the performance of DMOABC in solving the EDTMAP is evaluated. Numerical experiments of size n×m were designed. The number of workshops n ∈ {2, 3, 4} and the number of product types m ∈ {2, 3, 4} in each workshop constitute the problem n×m. Other parameters include the runtime of each machine, and the production efficiency was set as follows: t_minute = 60, t_hour = 24, t_day = 7, η = 0.85. In addition, we assumed that the production weight of each type of product is equal.

Two classic multi-objective optimization algorithms, NSGA-II and SPEA2, were selected for comparison with DMOABC. To guarantee comparison fairness, all the parameters in the various algorithms were set consistently. The number of function evaluations (NFEs) is used as the control variable. In DMOABC, NSGA-II, and SPEA2, the NFEs were all set to n×m×10⁵, and the population size was 100. In NSGA-II and SPEA2, the crossover probability was 0.9, and the mutation probability was 0.2. All of the algorithms were coded in Java and implemented on an Intel Core 3.0-GHz PC with 8-GB memory.

Because the result of a multi-objective optimization problem is a Pareto solution set, the performance of our proposed multi-objective optimization algorithm cannot be evaluated merely by the values of the objective functions. The evaluation indices should indicate the dominance between the solutions, how close the Pareto solution set is to the true Pareto front (PF), and how uniformly the Pareto solution set is distributed. Therefore, this study uses two indices to measure the performance of DMOABC for solving the EDTMAP.C(A, B) is not necessarily equal to 1 − C(B, A). C(A, B) = 1 indicates that all solutions in B are dominated by some solutions in A, and C(A, B) = 0 implies that no solution in B is dominated by a solution in A. Hence, C(A, B) > C(B, A) implies that the Pareto solution set of A is better than that of B.

In this section, a statistical analysis of the comparison results for the three algorithms is presented. Normalization was used to eliminate the influence of the various magnitudes of the objective value. Each scale of the problem contained three other test cases, each of which ran ten times independently. The mean of the C-metric is shown in Table 6, and the mean of the D-metric is analyzed in Table 7. The optimal values are set in bold font among these three algorithms. A testing instance with a size of 3×2 was selected to compare the PF of these algorithms, as shown in Figure 2. The horizontal axis represents the inverse of the machine scheduling distance, whereas the vertical axis denotes production. The red circle points “○” denote the PF of DMOABC, the green rectangular points “□” indicate the PF of NSGA-II, and the blue triangle points “△” are the PF of SPEA2.

These statistical results demonstrate that DMOABC performs better than the other algorithms on all test instances in terms of the C-metric and D-metric. It can be observed from Table 6 that the C-metric values obtained for DMOABC are more extensive than those obtained for the other two algorithms. This indicates that those obtained for DMOABC dominate most of the solutions obtained for NSGA-II and SPEA2. In Table 7, the statistical results for the D-metric reveal that the solutions obtained by DMOABC are closer to the ideal PFs than those obtained by the other two algorithms. Figure 2 shows that those obtained by DMOABC dominate most of the solutions obtained by NSGA-II and SPEA2.

The superiority of DMOABC is attributed to the following facts. First, in the employed bee phase, the LSO can improve the quality of each solution in the population. Second, in the onlooker bee phase, the XO can improve population quality because employed bees and onlooker bees share nectar information. Finally, in the scout bee phase, each scout bee can abandon a solution that has not been improved during the limited number of generations to avoid falling into a local optimum. In summary, according to the above analysis, we can conclude that DMOABC is effective for solving the multi-objective EDTMAP.

A WRFM is a modular digital radio product, a high-performance professional radio module for data transmission implemented through digital signal processing and radio technologies. WRFMs have many applications, such as in wireless remote controllers, remote garage doors, remote control lighting, communication, and security. A diagram of a WRFM is shown in Figure 3.

In this real-world case study, there are three workshops in the factory. Each workshop tests three types of WRFM. The actual WRFM production line for each workshop is shown in Figure 4. In actual production, each type of WRFM is tested in three stages. There are various types of testing machines with other interfaces in each workshop. All of these machines can be allocated to any workshop. To maximize both the total production and the inverse of the total scheduling distance of the machines, a reasonable testing machine allocation scheme is required. The testing time and requirements associated with 16 compatibilities and quantities for interfaces of each type of WRFM at the various stages are listed in Table 8a, information concerning available testing machines in each workshop is provided in Table 8b, and the distances among the three workshops are listed in Table 8c.

DMOABC and its comparison algorithms (i.e., NSGA-II and SPEA2) were applied to this real-world case. All the parameter settings were the same as those in Section 4. Each algorithm was run independently 30 times. The statistical results for the C-metric are shown in Table 9, and the statistical results for the D-metric are summarized in Table 10. In terms of the C-metric, the values obtained for DMOABC were significantly larger than those obtained for the other algorithms. This shows that the solutions obtained by DMOABC dominate most of the PF solutions obtained by NSGA-II and SPEA2. In terms of the D-metric, the values obtained by DMOABC were smaller than those obtained by the other algorithms. This implies that the PF accepted by the DMOABC is closer to the ideal PF than that obtained by NSGA-II and SPEA2. The above results show that DMOABC outperforms the comparison algorithms in solving this case.

Figure 5 shows the PFs obtained using the different multi-objective optimization algorithms. In this figure, the horizontal axis represents the inverse of the scheduling distance of the machines, while the vertical axis represents production. The red circles “○” denote the PF obtained by DMOABC, the green rectangles “□” indicate those obtained by NSGA-II and the blue triangles “△” are those obtained by SPEA2. It is easily observed that most of the solutions obtained by DMOABC can dominate those obtained by NSGA-taine SPEA2. Based on this figure, we can conclude that the DMOABC is superior to its comparison algorithms in terms of convergence performance.

Points A and B in Figure 5 correspond to the two extreme objectives of this case. More specifically, Point A is the machine allocation scheme with the maximum production on the PF for DMOABC. Point B is the machine allocation scheme with the minimum scheduling distance of machines on the PF for DMOABC. Point A is (− 130.5, 6686.33), and Point B is (0, 0). The maximum production values on the PF for NSGA-II and SPEA2 are 5985.04 and 6013.92, respectively. Therefore, compared with NSGA-II and SPEA2, DMOABC improved the production capacity by 11.72% and 11.18%, respectively. Decision makers can select an appropriate testing machine allocation scheme from PF solutions according to real-world production needs. For instance, the machine allocation scheme at Point A might be selected if the executors wish to have more production without considering the increase in the machine scheduling cost. When the production target is given, the executors expect the machine scheduling costs to be as high as possible. In this case, the solution on the PF can be selected to obtain the machine allocation scheme that both satisfies the production target and minimizes the machine scheduling cost. The allocation scheme of Point A is shown in Table 11, and Point B indicates that no machine is scheduled. From the allocation scheme of Point A, we can observe that six M1F1, two M1F2, and two M2F3 are scheduled for stage 1 of product C2T2R in workshop 3. This allocation scheme demonstrates one characteristic of the EDTMAP: that machines are compatible. Additionally, more machines are scheduled to increase the production capacity, but the total scheduling distance increases; thus, the scheduling cost increases. Hence, there is a clear conflict between the production and scheduling distance, which confirms that the EDTMAP is a typical multi-objective problem.