Processes 2021 , 9 , 274
12of 24
Algorithm 2 VNS 1. Construct the set of neighborhood structures S i , i = 1,2,3. 2. Set the maximum iterations M for searching in the first, second, and third neighborhood
structures M 1, M 2, M 3. 3. Set the initial solution. 4. for each i ∈ [ 1,2, . . . , M ] do 5.
for each j ∈ [ 1,2, . . . , M 1 ] do
6. Based on the current solution, the first neighborhood structure S 1 is used to search for better solutions than the current solution, and it means that the solutions found can dominate the current solution. 7. endfor 8. for each j ∈ [ 1,2, . . . , M 2 ] do 9. Based on the current solution, the second neighborhood structure S 2 is used to search for better solutions than the current solution, and it means that the solutions found can dominate the current solution. 10. endfor 11. for each j ∈ [ 1,2, . . . , M 3 ] do 12. Based on the current solution, the third neighborhood structures S 3 is used to search for better solutions than the current solution, and it means that the solutions found can dominate the current solution. 13. endfor 14. If the stopping criteria are not satisfied, continue; otherwise, stop and output the best solution. 15. endfor The core of the VNS algorithm lies in the design of neighborhood structure set. In the production scheduling, the neighborhood structure of VNS can be obtained by exchang- ing the order of two jobs or inserting one job before another. This study designs three neighborhood structures, which are S 1 , S 2 , and S 3 . The neighborhood solutions of S 1 are generated as follows: select two jobs randomly and exchange their positions to generate a new neighborhood solution. The neighborhood solutions of S 2 are generated as follows: select three jobs randomly and then disrupt their order to generate five new neighborhood solutions. The neighborhood solutions of S 3 are generated as follows: select four jobs randomly and then disrupt their order to generate 23 new neighborhood solutions. The parameters M , M1 , M2 , and M3 affect the search range. A large value means a large search range, but at the same time, it reduces the operating efficiency of the algorithm. On the contrary, the operating efficiency of the algorithm will improve, but it means that the search range becomes smaller. In order to balance the two, it is reasonable to set their value within10. 3.3. IMOEA/DTL Despite the outstanding global search capability of MOEA/DTL, it is likely to miss the locally better solution because MOEA/DTL does not search the neighborhood of the solution in detail in each iteration process. The MOEA/DTL is combined with VNS (IMOEA/DTL) to enhance its local search ability and performance. In IMOEA/DTL, the solution obtained in each iteration of MOEA/DTL is searched locally using the VNS algorithm to find a better solution. This study carries out VNS after the first update of EP , and VNS is carried out as Algorithm 3.
Algorithm 3 Combination method of VNS and MOEA/DTL 1. for each i ∈ [ 1,2, . . . , N ] do 2. nex _ x i = VNS x i 3. endfor 4. Output the new population.
Made with FlippingBook - Online magazine maker