基于贪嚼算法的快速可重组制造系统布局规划研究

基于贪嚼算法的快速可重组制造系统布局规划研究

在可繁殖于制造系统的布局计划中，通常有许多优化方法，如极值法、数学规划法、多目标优化法、网络理论、最大原则函数分析、随机优化法等。采用基于拟阵的贪婪算法,则可以针对不同的生产情况,快速、准确地响应市场不断变化的规划目标,优化可重组制造系统的布局规划。1优化数学模型在快速可重组制造系统布局规划的研究内容中,系统布置(组态)是一个重要的概念。由于可能的组态方案很多,如6台机床组成的制造系统可能有54种组合可能,即:串行、平行和52种混联(串并行)可能,因此要采用仿真软件和产品的产出分析软件来分析评定。为了建立布局的数学模型,要确定最优准则并从抽象和简化某车间的生产情况开始。在订货条件下,车间采用基于成本的测度,即在满足客户质量要求和其它要求的前提下,尽量降低成本;如果订单产量变化大而快时,应主要采用基于完成时间的测度;此外,还要考虑基于加工中心故障率的测度,最优性准则可建立在以下3个测度和它们不同的组合度基础上:基于成本的测度、基于完成时间的测度、基于故障率惩罚的测度。通常,要根据不同的最优准则来进行不同的规划布置。以江苏某计算机组件厂为应用实例。其车间实际生产情况为:所加工零件为一族零件,具有较高的相似性;在一定时期内,一个制造系统只生产一种特定的零件;零件加工总数由订单和周生产计划预先指定;机床能力与每种零件的加工参数(加工时间、平均加工成本等)为已知,但每种零件加工工序不相同,最大工序数为m,每道工序可选用的机床有多种加工方案。现对车间的生产情况作一些必要的假设:只考虑CNC加工中心的串行和并行安排;任何CNC机床均可以用于固定的几种工序;机器Mj(j=1,2…,m)上加工工序Si(i=1,2,…,n)的参数(时间、成本、故障率)是预先测定的。在上述已知条件和假设下,将车间的生产情况简化为图1,假设某零件有3道工序S1,S2,S3,每道工序有几台加工中心(方框中为加工中心序号)可以选择,图中表示了实际可行的加工方案。这些加工方案组成了一个有向网络图。在每条连线上,定义一个权ωi,代表连线终端加工中心的主要参数,如加工时间、故障率、成本等等。我们所要研究的就是选择一条路线,使其具有最小(大)权基(权基定义为所有选择中的权ωi的总和,最小或最大应视参数性质而定),而对于权ωi所代表的不同参数,则分别求出最小(大)权基,即为完成不同目标的优化设计。假设ωi代表加工时间,若ω1+ω4+ω6=min(t),则按照时间最短的优化判据,应选择如图1中粗线所示路线。以上问题可以转化为这样一个矩阵:A=⎡⎣⎢ω1ω20ω3ω4ω5ω6ω70⎤⎦⎥A=[ω1ω20ω3ω4ω5ω6ω70]其中每一行代表一道工序,每行中的元素为可选择的加工中心的权。这样,目标为求A中元素的一个子集S,使得S中均为非零元素且任何两个元素不在A的同一行里,以使S中的元素之和最小(大)。由拟阵理论可知,这个矩阵属于划分拟阵,而此问题的求解是拟阵中的一类典型问题,即求最大(小)权基的问题。如上所述,将生产实践中的问题通过简化、抽象以后,建立了以拟阵为中心的数学模型。应用拟阵的数学模型,其突出的优点是算法的通用性,即对于不同的零件和不同的规划目标,只要改变矩阵A的容量和权ωi,就可用同一种算法完成多种优化设计。2使用一个拟阵的推动方法在各种优化算法中,常见的有遗传算法、单纯形法、贪婪算法等等。要选择一个合适的算法,首先要明确此处优化内容的特点:属于中小规模优化问题;数学模型比较简单;对运算的快速性能无特别要求;虽然是单目标规划,但目标具有可变性。本文选用的拟阵的贪婪算法,由于其直观性和通用性,可以用同一个算法来实现不同的规划目标。选用这一方法使优化问题简化为由不同的数据源得出不同的拟阵。贪婪算法的主要思想是:按元素的权由大到小的顺序,每次找一个最大权的未检查过的元素进行检查,若该元素与已选取的元素构成独立集(即不在同一行里),则选取它,否则丢掉它。在剩下的未检查元素中重复上述过程,直到选取k个元素为止,最后被选取的元素所构成的集合即为所求。对于上节所得到的矩阵A,其中的独立集就是不在同一行的元素的集合。或者所有剩下的元素都已检查完了,此时说明M中不存在k-独立集。3原型法的开发和调试本课题所要求的应用软件应体现4个特点:开发周期短,开发人员少,系统规模小、简单,可以在使用过程中进行调整修改,不要求高度的正确率。为了提高效率,选用原型法进行软件的开发和调试工作。开发工具主要采用MicrosoftVisualC++6.0。其它辅助的开发工具有MicrosoftVisualFoxpro,为应用程序提供数据库支持,同时应用VisualC++的ODBC类创建数据库访问。开发平台为Windows98。3.1加工信息表的建立考虑到本系统中所用数据具有数据量小、逻辑关系较简单的特点,不采用数据库格式,而采用自由表的格式,在程序体中通过编程完成查询、修改等功能。车间数据库主要由5张自由表组成:零件基本信息表、加工工序基本信息表、加工中心及其加工成本信息表、加工中心的加工时间信息表、加工中心的故障率信息表。从零件信息表中,可以得到零件的名称、包括哪些加工工序及其它相关信息;从加工工序基本信息表中,可以得到每道工序的名称及可以用哪些加工中心来进行加工;从加工中心及其加工成本信息表中,可以得到每台加工中心的名称及其相应工序的成本;从加工中心及其加工时间信息表中,可以得到每台加工中心的名称及其相应工序所用时间;从加工中心及其故障率信息表中,可以得到每台加工中心的名称及其相应工序的故障率。这5张自由表之间通过获取表中的逻辑值,可以在程序中完成相应的检索修改功能。3.2生成报告文件系统程序的主要流程为:首先由用户输入必要的数据,包括输入目标产量,选择所加工零件和规划目标(最优准则)。数据准备好以后,就可以把这些数据作为输入,应用贪婪算法,计算出最优化结果,生成报告文档。用户可以根据这个报告文档,进行下一步的车间布局规划。在每一步中,由不同的数据表来提供数据支持。如在选择规划目标以后,需要根据所选的规划目标来选择对应的数据表。3.3生成报告命令此软件包括以下几个用户界面:(1)数据初始化。包括输入目标函数,选择规划目标,选择零件。(2)生成规划报告文档。点击菜单中生成报告命令,可以生成一个文本文件。此文档的内容包括:基本数据信息(每天目标产量,规划目标,所加工零件ID、名称及备注);零件加工信息(零件的工序名称、每道工序可用的数控机床的名称);生成的矩阵;运算结果(每道工序选择的数控机床、所需数控机床数量、加工参数)。(3)数据修改。选择菜单项中数据表选项,用户可以修改各个参数,同时结果保存到原数据库中。4制造系统的重组江苏某计算机组件厂是外资独资企业,有两个主要加工车间,主要生产计算机硬盘的磁头支架,共有9种规格,1999年的总产量达到4千万件。由于客户订单的不确定性和多变性,需要定期变换生产计划(一般为根据客户订单制订周生产计划),经常需要对制造系统进行重组,其中,最长的周期为几个月,最短的重组周期为8小时。如此频繁的重组,除了依据订单对车间和加工中心进行重新布置外,更重要的是考虑加工成本的降低,加工时间的缩短等等一系列因素。在调研过程中,我们发现,该厂生产车间重组的规划,基本上都是采用手工计算的方式来完成的,因此,需要开发一个规划软件来辅助完成车间的重组规划,以代替手工计算部分,达到快速优化重组布置,缩短单件时间、降低成本和提高质量与重组准备周期的目的。4.1各目标优化下的最优化准则选择不同的规划目标,运行上面的应用程序,选择名为CONNER的零件,日产量为15000件,在此初始条件下生成3个项目及相应结果,如表1所示。结果分析:(1)对于拟阵模型A=⎡⎣⎢ω1ω20ω3ω4ω5ω6ω70⎤⎦⎥A=[ω1ω20ω3ω4ω5ω6ω70]将不同的参数代替其中的ωi,则可以得到不同的拟阵,这些拟阵可以通过同一个贪婪算法来得到最优解。(2)由表1可以看出,选择不同的规划目标即最优化准则,可以得到不同的优化结果。(3)比较各个优化结果,它们之间具有较大差别。至于用户采用何种最优化准则来进行重组规划,需要根据不同的生产情况而定。(4)此软件只能实现单目标规划,暂时不能实现多目标规划。4.2结果分析表2为江苏某计算机组件厂115#车间的某日生产任务,以及实际的手工优化结果与使用此软件得到的优化结果的比较。结果分析:(1)对比两组数据可见,选择的数控机床类型几乎全同,数量也大致相同,说明计算结果与实际情况基本相符,说明此软件有一定的实用价值。(2)程序优化结果与手工优化结果的机器数量绝对误差在1台到4台之间,在允许误差范围之内。(3)误差源于建模过程中对生产条件和生产过程所作的假设。因此,要消除误差,需要建立更加精确的模型。5在多目标规划时的应用(1)随着RRMS研究的深入,对其系统的规划与运作管理的研究将会成为重要的课题。基于拟阵的