Research On Facility Layout Method Combining Heuristic Algorithm And Exact Algorithm

Facing the increasingly competitive market environment,manufacturing enterprises need not only the reasonable production planning,but also the stable and efficient production environment.Facility layout is an important part of the production environment.An effective facility layout planning can significantly improve the system throughput and production efficiency,and reduce operating costs.Facility layout problem(FLP)can be defined as determining the most effective arrangement of facilities in accordance with some objectives(e.g.minimising materials handling costs,minimising layout area and maximising adjacency function)under certain constraints,such as non-overlapping constraints and maximum-ratio constraints.In recent years,scholars have successively proposed various FLPs variants and corresponding solution approaches.In most of the researches,FLP is modeled as a discrete optimization problem.However,in the real production environment,determining the exact locations of facilities is usually a continuous optimization problem.Considering the exact locations of facilities can effectively reduce the material handling cost.This dissertation focuses on the discrete and continuous characteristics of the FLP,and deeply studies the double row facility layout,multi-row facility layout and closed loop facility layout problems with these two characteristics.The main work of this dissertation includes the following three aspects:(1)This dissertation studies the stochastic robust double row facility layout problem(SR-DRLP).In the small-batch multi-variety production model,due to the uncertain characteristics of market demand,it is difficult to accurately predict the product demand in the future production planning horizon.This dissertation studies a stochastic robust double row facility layout problem,where the product demand is modeled as an independent normally distributed random variable with known variance and expectations.A mixed integer programming model is established for SR-DRLP.A surrogate model is used to linearize the nonlinear term in the MIP to achieve a mixed integer linear programming model,which can be readily solved by an exact method to yield high-quality solutions(layouts)for small-scale SR-DRLPs.Furthermore,we propose a hybrid approach combining a local search algorithm and an exact approach(LS-EA)to solve large-scale SR-DRLPs.Firstly,a local search algorithm is designed to optimize the machine sequences on two rows and the clearance from the most left machine on row one to the left boundary.Then,the exact location of each machine is further optimized by an exact approach.The LS-EA is applied to six problem instances ranging from 8 to 50 machines.Experimental results show that the surrogate model is effective and LS-EA outperforms the comparison approach.(2)This dissertation studies the multi-row facility layout problem with extra clearances(MRLP-EC).Existing studies on MRLPs typically either ignore clearances between adjacent machines or consider only the minimum clearances.This dissertation studies a multi-row facility layout problem with the objectives of minimising material flow cost and layout area.A mixed integer programming formulation is established for MRLP-EC.A hybrid approach combining an improved multi-objective greedy randomised adaptive search procedure(mGRASP)and linear programming(LP)is proposed for the problem.The mGRASP is used to optimise machine sequences to obtain a set of nondominated machine sequences.A segments-based dominance method is proposed to measure the dominance relationship of any pair of machine sequences.LP is used to optimise extra clearances between adjacent machines(i.e.the exact location of each machine)for each non-dominated machine sequence.The proposed approach is compared against an exact method and two multiobjective heuristics.Experiments show that the approach is effective for MRLPEC and outperforms comparative approaches.(3)This dissertation studies the closed loop facility layout problem with extra clearances(CLLP).Existing studies on CLLPs typically ignore clearances between adjacent cells and do not optimize the dimension of the closed loop.A mixed integer programming formulation(MIP)is established for the CLLP.Then,based on the formulation,a hybrid approach combining an improved differential evolution algorithm and an exact approach(iDE-EA)is proposed to solve the CLLP.The iDE with a hybrid coding is utilized to optimize the dimension of closed loop and the placement sequence of cells simultaneously.The EA is to determine the exact location of each cell(i.e.,the clearance between each pair of adjacent cells).The iDE-EA is compared against the traditional differential evolution algorithm and existing approaches for the CLLP.Experiments show that iDE-EA outperforms comparative approaches in terms of material handling cost.