Research On Line Facility Layout Problem Modeling And Optimization Method

Facility layout problem is about the arrangement of a given number of facilities in a specific area so that the total cost between the facilities is minimized.The reasonable layout configuration could decrease the material handling cost and improve production efficiency.The row layout problem is one of the most important facility layout problem,the facilities are along the row arrangement,widely used in production and services environment.The row layout problem is NP-hard,it is very difficult to get the optimal solution in polynomial time,so it is of great significance to build an efficient mathematical model and propose the high performance optimization algorithm to solve the problem.The dissertation focuses four types of row layout problem,named single row facility layout problem,double row layout problem,corridor allocation problem and parallel ordering problem.Based on the analysis of the model,the more efficient mixed integer programming models are proposed.At the same time,the heuristic algorithms are developed to solve the problem according to the characteristics of the problem.The main research contents of this dissertation are as follows:(1)The extended single row facility layout with asymmetric flow and corridor width is considered for minimizing the material handling cost.Four mixed integer programming models are developed according to the different modelling methods.Take the solution quality,the running time,the number of branch and bound node and the linear programming relaxation value into account to evaluate the model performance.The computational experiment results indicate that the model based on the polytope theory has the best performance.At the same time,replace the disjunction constraint with inductor constraints of two models.The results show the performance of one model no significant change and the performance of another one is get worse.To further improve the model with the best performance,the symmetry-breaking constraint and replace non-overlapping constraints are developed to build the improved model.The computational results show that the improved model is significant better than the original model on the Gap,the number of branch and bound node and the solution time.(2)Analyze the extended single row facility problem model based on the polytope theory.On the basis of replacing non-overlapping constraint model,the position p-q method and position q method are used to produce the symmetry-breaking constraints.The computational results show that the position p-q method is better.Improving the original model.Compared to the original model,the position p-q method results in a 56.77% reduction on the average solution time and reduces the number of branch and bound node by 49.78%.Two valid inequalities and one equation and seven combinations of them are proposed for identifying the influence of the model with position p-q method.The results indicate that the model MET with the equation and triangle inequality constraints and the model METS with equation,triangle inequality and star inequality constraints has the better performance on the solution time,the number of branch and bound node,the linear programming relaxation value and the number of dual simplex iterations.Particularly,it fall average Gap?LP from 62.749% to 16.987%.(3)Because the extended single row facility layout problem is NP-hard,it is impossible to obtain the optimal solution in polynomial time.Based on analysis the optimal solution structure,six construction heuristic algorithm are developed.The computational results show that the algorithm LBP based on the facility length significantly outperforms other construction heuristic algorithms.Hybrid the LBP and the exact method to solve the extended single facility layout problem could decrease the solution time and the value of Gap.At the same time,six improvement heuristic algorithm are proposed.The computational results show the heuristic using the insertion neighborhood has the best performance.Four simulated annealing algorithms with insertion neighborhood are developed.The computational experiment results indicate the LBP provides the initial solution could enhance the performance of the simulated annealing algorithm.Additionally,the increase of number of iteration will make the solution time get longer,but it can effectively improve the quality of the solution.Compared with the optimal solution of the current classic instance,the proposed simulated annealing algorithm can be used to effectively solve the extended single row facility layout problem.(4)Analyze the double row layout problem model based on the polytope theory and prove it involves one redundant constraint.Compared and analyzed the removing the redundant constraint and adding a valid inequality constraint model with classical instance.The results indicate that the model removing the redundant constraint could decrease the solution time,and the model removing the redundant constraint and adding a valid inequality constraint could improve the value of the linear programming relaxation value.Decrease the value of big M could further improve the performance of the model.Finally,the effects of four kinds of choose facility method for symmetry-breaking constraints and implied within-building constraints on model are studied.(5)For the extended corridor allocation problem with asymmetric flow and corridor width and facility width is considered.The mixed integer programming model is proposed.Since the problem is NP-hard,the learning-oriented cloud theory based simulated annealing algorithm is developed.The computational experiment are carried out randomly generated instance for evaluating the performance of the algorithms.The results indicates that the learning-oriented cloud theory based simulated annealing algorithm is significantly outperforms the standard simulated annealing algorithm and cloud theory based simulated algorithm on the quality of solution and the solution time.For the small scale instances,the learning-oriented cloud theory based simulated annealing algorithm could obtain the optimal solution for instance with size up to n = 15.(6)Improve the non-overlapping constraints of the parallel ordering problem mixed integer programming model to develop an improved mixed integer programming model.The result indicate that the improved model could find the optimal solution in a shorter time for small size instances.On the other hand,the improved model has better performance on solution time and the value of Gap.Moreover,some optimal solution for small size instance that could not find in the literature are given.The optimal solution for some instance with size n = 24,n = 25 and n = 30 could be found using the improved model,so it could increase the instance scale for exact solution.The dissertation studies four classes of row facility layout problems and the extended problems.The objective is minimize the material handling cost between facilities.Corresponding mixed integer programming model is proposed and the algorithms are also developed.This study enriches the research content and method of the row facility layout problem and positively promote the development of the facility layout theory.