Application Of Discrete Differential Evolution Algorithm In Production Optimization Problems

The decision-making, planning, and design in the production industry can often be formulated as optimization problems. A good solution is searched from the feasible solution space by minimizing the objective function value in order to increase productivity or reduce production costs. For combinatorial optimization problems, the research on their solving method is an important research direction. In this thesis, discrete differential evolution algorithm(DDEA) is focused on and applied to solving two combinatorial optimization problems from the actual production:the first one is two-dimensional rectangular board packing and stacking problem, which exists widely in the furniture and other packages’ optiimization, the other is vertical light-emitting diode(LED)’s placement optimization problem in electronic manufacturing.DDEA is a kind of evolutionary algorithm and has the following main features:an intermediate solution is generated by adding the differential information of two solutions to the third solution in mutation operator; each gene in the offspring is selected from the intermediate solution generated and the parent solution through probability parameters in the crossover operator.In the two-dimensional rectangular board packing and stacking problem, the boards are stacked into layers and the layers are grouped into packages. The problem belongs to board combinatorial optimization problems. To improve the space utilization of packages, DDEA is applied to solve the problem:1) A signed sequence is used to denote a packing solution to the problem;2) In order to make the best use of gaps, a new lowest horizontal line-gap reused heuristic is proposed to decode the sub-sequence for a single package, which results in a packing solution to the sub-problem for this package;3)Through the sequences’mutation and crossover operators, solution population evolves gradually to obtain a good solution. The experimental results show that the solutions by the DDEA are better than those by genetic algorithm and the original packing solutions for both the simulation data and the real packages data.LED placement optimization is actually to optimize the placement sequence of LEDs with the objective of minimizing the length of the total placement routing path. Its solution could be denoted as a permutation. The problem could be reduced to a vehicle routing problem(VRP). For this problem, LED components are first divided into different regions, in each region’s cycle group, the sub-sequence of LEDs is generated by the nearest neighborhood heuristic; and then the sub-sequence of LEDs are integrated to form a whole solution sequence. DDEA is applied to the whole solution sequence population in order to find a good solution in a short time by mutation and crossover operators. The experimental results obtained on better algorithm solutions when test on the real production data.The search above shows that the DDEA performs well for the two problems considered in the thesis. It indicates that the DDEA could be applied to solve other combinatorial optimization problems to obtain better solutions.