一、选题的背景与意义

随着社会的进步，经济的发展，市场环境的转变，制造业正面临着愈来愈激烈的竞争，企业之间的竞争方向在外界方面逐渐转为满足客户的需求，在企业内部则是降低生产成本和缩短生产周期，在这一情况下，如果一个企业要想生存下去就必须努力提高自己的竞争能力，不仅要满足客户个性化的需求，还要争取最低的生产成本和最短的生产周期。目前，制造业是国民经济的重要支柱，生产车间是制造业最基本的生产单元^[3]，生产车间进行产品的加工过程，可以将原材料转化为产成品。设备是生产车间的基本配置，车间布局决定了以后车间的物流方向和效率，对产品的生产周期和工作人员的安全等方面也具有很大的影响，良好的设备布置可以缩短运输距离，降低运输成本。同一车间，同样的人员，设备和技术也都是一样的，只是因为布局是不一样的，车间的生产状况就可以有很大的差别，因此企业愈来愈注重车间的布置，期望一个良好的布置方案可以提高车间生产的效率。 设施布局要按照一定的原则,在设施和车间内部空间面积的约束下,对车间内各组成单元、工作地以及生产设备进行合理的布置。图论法是基于对输入数据及对生产活动的作用及其关系的理解,进行材料流及活动关系分析,形成空间关系图。然后再根据实际可用的面积做出几种布局方案,进行评价择优。

二、国内外研究综述

车间布局设计的历史比较悠久，最早出现在手工作坊时期，为了加快生产速度和工作效率，人们开始凭借经验对作坊内的生产工具和工作台的位置进行调整。1831年，数学家高斯(Gauss)就开始从科学的角度研究布局问题，到现在已经有180多年历史了^[15]。

上世纪初至三十年代是工业工程学科的萌芽期，以泰勒的科学管理方法和福特发明流水线生产方法为标志。人们开始认识到车间布局设计和物流规划管理对工厂效益的重要意义，但对车间布局设计的研究还局限于”工作研究”。该时期的车间布局还主要凭借设计者经验和感觉。

上世纪四十年代至六十年代是设施规划学科的高速发展时期。对车间布局设计的研究己由”工作研究”拓展至物料搬运方法(Material Handling)与工厂布置(Plani Layout)的研究，即探求工厂内所有设备设施的相对排列方法，车间布局成为研究对象更为广泛的并且具有独立的学科方向和技术体系的学科。这个时期的车间布局问题没有模型化，大多根据所生产产品的工艺路线特点来进行布局设计，其中最具代表性的方法是美国的理查德#183;缪瑟(R.Muther)提出的系统化设施布置方法(Systematic Layout PI~g，SLP)，使车间布局设计从定性发展到了定量。SLP 方法是以图形模型和图表分析为手段，把量化的概念引入整个设计分析的全过程，使得布局设计更加科学化、系统化、合理化，是到目前为止仍在一般的车间布局设计中广泛应用的一种方法^[2]。

90年代威廉#183;温拿提出了新的战略设施规划(SFP)其发展主要有两点：①把设施布置设计提升至战略高度，通过一次根本性的再聚焦以及精益原则来提高企业整体生产力。实施的关键是运用企业流程再造原理：即首先进行业务流程重组，然后将主、次流分离（产品物流与非产品物流分离），最终的布置由主流的轮廓图发展而来，次流伴随着主流被调整至剩余空地、头上和地下空间。这样一来，顾客愿意付钱的产品的价值增值速度加快，企业竞争能力加强。②新的战略设施规划融合了优良的计算机辅助设施布置方法，一定程度上实现了设施布置的快速响应、布局信息、的计算机化和较丰富的设计方案以供决策者选择。

计算机辅助设施布置方法自从出现以来，就一直是人们研究的重点，发展非常迅速。计算机辅助设施布置软件的建模是计算机辅助设施布置的核心内容。起初，人们根据假设情况（如：设备之间的流量是已知的固定数量；布置问题在计划展望期内看作是静态问题；布置的目标仅仅是物流费用最小等等）建立了第一类模型。然而，这些假设越来越不符合现代制造系统的现实要求。为寻求改进，人们做了许多工作。一方面，人们根据现实问题发展了许多扩展模型：如实际布置是多目标优化问题且目标间可能相互矛盾，为此近年来构造了多种多目标决策布置模型；由于经营、发展、需求波动以及生产混和的动态特性，设备之间的物流量随着阶段的不同而变化，当一些这样的改变是可计划时，可发展为动态布置模型；当产品混和、机器故障、周期性的波动和需求不确定时，针对不确定性发展了随机布置模型、鲁棒性及柔性布置模型。另一方面，由于目前构造通用的布置模型还很困难，于是人们又针对特定类型制造系统不断开发更具体、实用的第三类模型^[7]。

最初的计算机辅助设施布置软件（如 CORELAP 和 CRAFT）所用算法主要为新建法（Const ruction methods）和改进法（Improvement methods）等传统启发式算法。这些算法的主要缺陷是在达到满意方案前的选择过程中未充分考虑其它的方案，并且它们对初始布置敏感，导致最终布置未必好^[17]。近十几年来，人工智能技术的发展为设施布置提供了新算法。由于设施布置是典型的NP问题，人工智能技术成为在有效时间内寻求满意解的可行算法。它们应用快速并行处理，可以同时得到多个解，丰富了备选方案；并且它们允许代价更高的解出现，从而可以跳出局部最优点，解决对初始布局敏感，所以在设施布置中（特别是在寻优段）这些人工智能技术获得广泛应用。