【作者】 郑晓军；

【导师】 滕弘飞；

【作者基本信息】 大连理工大学 ， 计算机应用， 2010， 博士

【摘要】 生产制造企业的设施布局是设施规划领域的一个重要问题。它研究如何按照一定的原则,在预先给定的生产车间内,将生产系统所使用的机器、仓库等的位置以及与之相关的物料流和人员流进行合理地组织与布置,以达到最优的设计目标(如物流成本最低、设备利用率最高等)。一个设计良好的设施布局能加快物料处理效率,减少在制品的停留时间,显著提高企业的生产效率。在理论上,本问题属组合优化问题,NP-hard问题,本文讨论的车间设施布局问题与一般的布局优化问题(如Packing问题和Cutting问题)相比,在问题描述、数学建模、数值求解等方面更困难,在工程应用上,本文研究的生产制造系统的设施布局问题是实际生产中存在的尚未很好解决的难题,具有重要的工程实用价值。本文在国家自然科学基金项目的资助下,以生产车间设施布局为研究对象,研究该类布局问题的有效求解方法。车间设施布局可分为块状布局和详细布局,前者不考虑设备的尺寸形状,只确定其在车间内的相对位置,而后者考虑设备的尺寸形状等信息,并确定其在车间内的坐标和方位。与块状布局相比,详细布局的优化目标与约束条件更多,求解也更加复杂。本文重点讨论后者。论文的主要工作如下：(1)针对一类块状布局问题——环形布局问、题的求解,提出一种称之为设施相对位置编码的方法,并基于差异演化(DE)算法,构成相对位置编码的DE算法,用于环形布局问题的求解。编码方式是决定用进化算法求解问题效率和质量的关键,该编码方式利用环形布局序列问题的解具有设施的位置排序的特点,省去实数编码算法求解该类问题时需要进行实数到整数序列的映射过程,解决了用实数编码算法求解时编码空间远大于环形布置解空间的缺点,并且减少无效编码。(2)提出一种基于图论的求解设施之间避障曼氏最短路经的连接图生成方法,用于求解详细布局问题的设施间的最短曼氏距离。设施间的物流量是设施布局优化的一个最主要的目标,而物流量的大小又与选择的设施之间的路径长度直接相关,因而设施间的路径会直接影响布局优化算法求解的质量,对于详细布局问题尤其重要。本文连接图生成方法利用了曼氏距离不同于欧氏距离的特点,可较快计算设施间的最短路径及其距禺。(3)建立了更加贴近于实际的设施详细布局数学模型并且给出一种基于满意度的差异演化算法求解该详细布局问题。建模方面,与以往详细布局文献中仅考虑设施的外形尺寸不同,该数学模型还额外考虑了设施的装卸点、设施间的连通性、设施间的最短路径、设施布置的整齐美观性等要求。求解方面,针对设施详细布局问题的多约束、多目标且具有NP难度的特点,以及求解最优解难以实现的问题,本文提出用满意解代替最优解,将满意优化原理与差异演化算法相结合,用综合满意度函数作为差异演化算法的目标函数,并且在运行过程中综合考虑满意求解,从而完成详细布局问题的求解。(4)给出开发设施详细布局优化与仿真的系统原型及其关键技术,包括：①从设施的CAD几何图形数据库中检索给定设施的检索方法,本文给出一种基于三维几何模型局部缩放的三维CAD模型检索方法；②基于Pro/E的实体简化技术,用于设备几何外形数据提取；③干涉量计算模块,用于详细布局算法求解过程中设备间干涉量的计算；④基于Pro/E二次开发的布局仿真,用于将求解获得的设施布局结果在Pro/E环境中进行三维仿真,便于设施规划人员进行综合评判。本文给出车间设施的环形布局和详细布局的数学模型和相应的求解方法,并且给出开发一类设施详细布局优化与仿真的关键技术及其系统原型实现,可为设施规划人员提供设计参考。本文方法可望推广应用于其他类型的设施规划应用领域,如机场、医院、办公室等的设施布局问题。更多还原

【Abstract】 The facility layout plays an important role in manufacturing industry. As a part of facility planning, the facility layout considers how to place the machines and storehouse and how to organize the material handling and operators in a pre-defined workshop. The major objective is to optimize the design goals, such as reduction of the material handling costs and improvement of the machine efficiency. A well-designed facility layout can speed up material handling, minimize the residence time during the production process, and significantly improve production efficiency. Theoritically, the facility layout problem under discussion is one type of combinatorial optimization problems, which belongs to NP-hard problem. Compared with cutting and packing problems, its problem description, mathematical modeling and solving process are much more complicated and also more difficult. As the facility layout problem is still unresolved in the engineering world, research on this problem has important practical significance.The work is supported by the National Natural Science Fundation of China (No. 60674078,50575031). Focusing on the layout in production workshop facilities, we look for effective methods to solve the layout problem. Facility layout can be classified into block layout and detailed layout. The former ignorzes the size and shape of facilities, and its solution is the relative position of the facilities in the workshop. In contrast, the latter takes into account the size and the shape of facilities, and its solution is the coordinate and the orientation of the facilities in the workshop. Compared with the block layout, solution of the detailed layout is more complicated, since it considers more objectives and constraints. The contents of the dissertation are as follows:(1) We propose a relative position-coded differential evolution (DE) with different encoding process from other algorighms for the loop layout problem, since encoding is the key of evolutionary algorithms. The proposed algorithm notices that the solution result of the loop layout problem is the relative position of the facilities, so it has following favourable characteristics:i it avoids mapping from float-point vectors to integer sequence; ii the coding space of the new algorithm corresponds to the solution space of loop layout; iii it resolves the illegal chromosomes in the solving process.(2) We propose a connectivity graph generation approach for obstacle-avoiding Manhattan shortest path calculation in detailed layout problem. Material handling cost, the reduction of which is the main aim of the detailed layout problem solution, is determined by the distance among facilities. Thus, the shortest path among facilities directly affects the quality of the layout optimization solution for detailed layout problem. By makeing full use of the characteristics of Manhattan distance which are different from those of Euclidean distance. the proposed approach can shorten the time of facility distance calculation in detailed layout.(3) We establish a mathematical model which is more adaptable to the actual environment and developed a satisfaction-based differential evolution to solve the detailed layout. In modeling, the mathematical model takes acount not only the shape of facilities, but also the pickup/dropoff point, the connectivity, the shortest path and orderliness of the facilities. In solving, because of multi-constraints, multi-objectives and NP-hard nature of the detailed layout problem, it is very difficult to find the global optimal solution. Therefore, we developed a method to find the satisfactory solution instead of the global optimal solution. The proposed method combines the satisfactory optimization theory and computational intelligence algorithm, and uses the overall satisfaction function as a differential evolution algorithm objective function to solve the detailed layout problem.(4) We give some key technologies while developing the facility layout optimization and simulation of the system prototype, including:①we derive a local scale-based 3D model retrieval method from the 3D model retrieval method from the CAD model library;②simplification method of irregular solid model based on Pro/E secondary development for geometry data extraction;③interference calculation module for calculating interference between facilities in detailed layout;④layout simulation based on Pro/E secondary development, to show the layout results in Pro/E three-dimensional simulation environment to facilitate comprehensive evaluation.In this dissertation, we present the mathematical models and corresponding solving methods for loop layout and detailed layout problems. Besides, we give some key technologies in developing facilities layout optimization and simulation of the system prototype. This method is expected to be applied to other fields where other types of facilities planning are involved, such as airports, hospitals, offices and so forth.更多还原