Multi-row Facility Layout Problem With Identical Machines And Its Hyper Heuristic Algorithm

With the rapid development of science and technology, the market demand is gradually diversified, the product cycle is shortened day by day,and the competition of enterprises is becoming more and more fierce. As an important engineering problem of manufacturing system, facility layout has been widely concerned and valued by enterprises and researchers. Good facility layout plan is very important to save production cost, shorten product cycle and improve production efficiency.Multi-row facility layout is widely applied, and it is a common pattern of workshop facility layout in manufacturing industry. Therefore, it is significant to study the problem of multi-row facility layout.In order to adapt to the market changes and shorten the production cycle of new products, the manufacture mode of enterprises is changing from mass production and single species to small batch and multi-varieties production. Flexible Manufacturing System (FMS) has been rapidly developed. The system relates to the multi-row layout of production facilities, and often uses the identical machines to realize the multi-product flowline to improve the production efficiency and the facility utilization rate. This paper takes multi-row facility layout in the flexible manufacturing system as the research object and introduces identical machines to multi-row facility layout. A multi-row facility layout problem with identical machines and its solution method are proposed. This paper includes the following sections: (1) A mathematical programming formulation is established for this problem, with the objective of minimizing material flow cost. (2) A three-stage algorithm(MCH-LP-XCG) to solve this problem is proposed. The method decomposes the problem into three sub problems, namely, the facility ordering, the facilities’ exact location optimization and the distribution of the material flow. Firstly, the material flow between facilities is initialized by equal flow assignment method. Then, based on the assigned material flow between facilities, a Monte Carlo hyper-heuristic (MCH) is devised to optimize the sequence of machines on multiple rows. Secondly, a linear programming (LP) is used to determine the optimal exact location of each facility. Finally, an exchange heuristic (XCG) is used to reassign material flows between facilities to further reduce cost. To avoid local optima and improve the quality of the solution, an iterative optimization strategy is proposed. This strategy reduces the material flow cost by repeatedly executing MCH, LP and XCG. (3) The approach is applied to problem instances and the results are compared with those of CPLEX and LINGO.Experiments show that it can effectively solve multi-row facility layout problems with identical machines and significantly decrease the material flow cost by the iterative optimization strategy.