Variable Neighborhood Search Algorithm For Single Row Latout Problem

Reasonable facilities layout can help the factory save up to30%of the cost. Since the competition is intense, enterprise gradually found the rationality of logistics facilities planning has become the third profit source, the focus has been put into this area. Single row layout problem is a typical form of facility layout problem, attention and concerned. Single-row layout problem is the basic problem in the workshop layout, it is also a unit of variety complex facilities layout problem, combined with the problem is NP-Hard problem which traditional methods are difficult to solve, and therefore the study of the problem has theory value and practical significance.This paper detailed discussed on the single row layout problem, found out the key factors affecting the objective function value of the problem. Compared with QAP problem, and put forward the solution to SRLP. Based on the characteristics and difficulties of the SRLP, and variable neighborhood search algorithm can solve the advantage of large scale combinatorial optimization problem, in this paper, a modified variable neighborhood search algorithm was proposed to solve the single row layout problem. There was no research on single row layout problem by using a variable neighborhood search algorithm, so this article is more valuable. In variable neighborhood search algorithm, good design of neighborhood structure is the key to ensure the quality of algorithm, so this paper constructed four neighborhood structures based on the single row layout problem and designed the search mechanism from simple to complex to ensure the algorithm is global search. The improvement of algorithm mainly includes three aspects:1) Algorithm design of objective function, this paper puts forward two kinds of design ideas and implementation to the algorithm, compared two algorithm, results show that for the single row layout problems using the algorithm design based on using the coordinate to solve equipment spacing is more efficient.2) The structure of the initial solution, based on the key influencing factors of single-row layout problem objective function value, this paper constructs two kinds of initial solution for solving single row layout problem, by solving the numerical examples, the results showed the heuristic method based on equipment spacing in the initial solution is more efficient to find the optimal solution.3) Improved the local search, including improve the initial solution of local search and evaluation function, using a perturbation to the current global optimal solution to generate initial solution in local search, ensure algorithm toward a better direction, improve the evaluation function to improve the efficiency of the algorithm. Finally perfect the algorithm process, set the related parameters, programmed the algorithm with Matlab software.Solved a large number of instances of the different scale with the modified variable neighborhood search algorithm, and compared with many algorithms proposed by foreign scholars. The results show that, for small and medium-sized example in this paper, the proposed algorithm can get exact solution in a short period of time, and for the massive examples, the proposed algorithm can obtain good nearly optimal solution in a short time, the gap between near optimal solution and the accurate value is up to0.24%. Taken together, the proposed algorithm is very efficient in performance and better than other algorithms mentioned in the article, fully shows the theory value.Finally, through the investigation of a large semiconductor company’s production line layout problem, use the proposed algorithm to optimize the actual single row layout problem, obtained better production line layout, and save a large amount of transportation cost, fully shows the practical significance of the work in this thesis.