数学建模论文-多品种小批量生产下的生产组织优化研究.doc

摘要基于成组化技术的单元化生产是适合于目前多品种、少批量市场需求环境下产生的先进生产制造方式。在制造单元分组的过程中物流量是重要的衡量指标，利用约束条件的最小值建立了模型，并对模型的不断简化，对各机器间搬运设备移动次数（各机器间的物流量）的计算，采用整数规划和遗传算法分别进行了仿真，使得设备成组各单元间的物流量最小，来优化多品种小批量生产下的生产组织方式，使用MATLAB 仿真出了结果，并且做出了两种算法计算的可视化可执行界面，同时对两种仿真结果进行了分析验证。最后对模型进一步的分析提出了此模型的优缺点并作进一步的改进，从而得到符合实际要求的分组方案。关键字：成组化技术，物流量，约束条件，遗传算法，MATLAB 目录一、问题重述2二、问题分析2三、模型假设及符号说明33.1 模型假设33.2 符号说明3四、模型的建立34.1 模型分析34.2 单元间的物流量模型44.2.1 目标函数说明54.2.2 约束条件说明54.3 机器间物流量的确定5五、模型的求解65.1多约束的最小值malab算法65.2 模型的简化65.2.1 遗传算法的确立与求解65.2.2 遗传算法的工作原理75.2.3 遗传算法的求解75.3 遗传算法结果与分析95.4 两种算法结果综合对比分析11六、模型进一步讨论126.1 遗传算法的优点126.2 单元制造的优点13七、模型的评价13八、参考文献1414一、问题重述单元化生产方式是适合于目前多品种、小批量市场需求环境下产生的先进生产制造方式，基于成组化技术的原理，单元化制造系统提取工艺信息和制造信息以获得形成制造单元的两个基本组成部分：设备组和零件族，形成制造单元。并在此基础上进行进一步地设备布局。达到压缩生产周期、降低成本、提高生产效率的优化目的。在生产制造系统中，不同的零件可能进行类似的加工处理。当这些不同的零件族组成一个群的时候，就可以建立一组设备对该零件族进行加工。在设计制造单元时，如果不同单元之间物流量最小化，显然，这等价于单元内机器之间物流量最大化。也就意味着高度关联的一批机器包括在了同一单元内。通常在企业生产制造过程中，物流量是衡量制造成本的一个很重要的指标，因此在制造单元分组的过程中物流量也是其最重要的衡量指标。机器之间物流量的计算基于几个方面：零部件加工计划、生产产量、搬运设备的容量大小。如表1零部件加工计划和产量表，假设每次搬运设备的容量为2个单元，那么各台机器之间搬运设备移动次数的多少计为各机器间物流量。根据以上描述建立制造单元分组的数学模型。 二、问题分析在生产制造系统中，不同的零件可能进行要求类似的加工处理，当这些不同的零件组成一个族群的时候，就可以建立一组设备对该族零件进行加工。在设计制造单元时，如果不同单元之间物流量最小化，显然，这等价于单元内机器之间物流量最大化。要达到物流量最小化的目标，需要考虑到零部件加工计划、生产产量、搬运设备的容量大小，对零部件加工进行合理的单元化分配，在不同单元之间搬运设备的搬运数目也成为衡量物流量的一个重要标志。通过对不同的机器在不同单元之间的物流量进行求和，及以总的物流量为目标，通过建模，产生合理的单元化分配方案，使得总物流量为最小。三、模型假设及符号说明3.1 模型假设1、 假设搬运设备的容量为2个单元2、 搬运零件簇时产生的费用都一样3、 不考虑搬运距离以及搬运过程中的零件损耗4、 某种设备必须在某个单元中5、 不考虑设备的占地面积和设备的分布情况6、 在同一个单元内相同的设备组之间零件的加工能力，加工质量相同7、 每一零件都必须在加工计划单上有一个预先确定的加工计划8、 不考虑零部件的生产周期9、 不考虑零部件的成本3.2 符号说明K表示零部件下标;c 表示单元号；Vk表示零部件k的生产量；Dk表示搬运设备搬运k零件时的有效搬运单位；Uc表示单元规模的上限；Qijk表示零部件k在机器i和机器j之间的移动量。E(Xi)为第i代样本的均值Xi表示第i的适应度值的集合Sxi为样本的标准差。Kshift定义为进程因子Kc表示当代种群的收敛程度Pc故交叉率Pm变异率P(t)群体,Fi种群中个体的适应度四、模型的建立4.1 模型分析在模型中需要使得单元之间的物流量最小，即单元内部的物流量最大，由于物流量的大小取决于零部件加工计划、生产产量、搬运设备的容量大小，相似的零件簇可以用一个设备组来生产，设备组和零件族，就够成制造单元，根据不同的设备组和零件簇进行划分为不同的单元，不同零部件的加工需要用到搬运设备，即在在不同的设备组之间才会产生物流量。所以，物流量可以用搬运设备的次数来表示。题目中假设搬运设备的容量为2个单元，生产产量给定，则具体的零部件搬运次数可以用生产产量与搬运设备的容量之商来表示。 4.2 单元间的物流量模型该数学模型的目标是使单元间的物流量大小最小。数学目标函数模型表达为： S.T. i=1,2,3.Mij ；i=1,2,3.Mij ；i=1,2,3.Mij ；i=1,2,3.Mij ；如果机器i在第c个单元否则 i=1,2,3.Mij ；c=1,2,3.Mc；如果机器j在第c个单元否则 j=1,2,3.Mij；c=1,2,3.Mc； 其中i,j表示机器的下标（i,j=1,2, Mij ）；k表示零部件下标（k=1,2, .Mk);c 表示单元号(c=1,2, .Mc )；Vk表示零部件k的生产量；Dk表示搬运k零件时的有效搬运单位；Uc表示单元规模的上限；Qijk表示零部件k在机器i和机器j之间的移动量。 其中X 表示大于或等于X的最小整数值。4.2.1 目标函数说明 使各单元间的物流量最小，将所有有关联的机器设备的物流量求最小值。4.2.2 约束条件说明 式中的约束条件主要有：1.一个机器设备只能放在一个单元中2.分组单元不得超过机器台数3.运用1或0限制机器所处单元4.一种机器在所有单元中的总和为1 4.3 机器间物流量的确定 由已知所给出的加工计划和产量表，每次搬运设备的容量为2单元，可计算出各台机器之间搬运设备移动的次数，假设各台机器之间搬运设备移动的次数等于各机器间的物流量。机器间的物流量见表1所示：表1 机器间的流量分布五、模型的求解 此模型是多目标、多约束的优化模型，很难求出全局最优解，所以我们先将多目标规化简，通过运用两种算法进行求解最后加以比较分析得出结果。给出初设备号 模拟计算物流量 记录物流量作为下一阶段的比较值重新设置优化条件 程序仿真 得出制造单元分组 求解优化人工分析绘制单元分组图 5.1多约束的最小值malab算法模型综合考虑了极小化加权的单元间移动次数和无效移动次数的总和及其评价程序所谓无效移动是指划分到某个单元的机器对这个单元中零部件的加工是不需要的由于计算的复杂性对于大多数上述方法在解决大规模问题时是有其局限性的。5.2 模型的简化化简多约束问题，我们可以有三个出发点：分析各目标之间相关联的数学关系，减少目标函数数目或约束条件数目。依限定条件，针对具体数据挖掘隐含信息以降低求解难度。分析各目标权重，去掉影响很小的目标函数，从而达到简化目的。分析目标函数与约束条件可知要使单元间的物流量最小，且满足约束条件，传统优化方法都是从线性空间的单点出发，这就大大的简化了模型运用遗传算法可从初始群体开始搜索，避免了从单点开始搜索的方法，从而大大简化了模型并且使仿真结果更具有实际意义。5.2.1 遗传算法的确立与求解 此类算法以单元间物流量最小化为目标建立了数学优化模型，并提出了一种基于单元数遗子表示的遗传算法单元成组方法。在该模型中主要加工的20种零部件过程基本上都只是在2台到5台设备之间见附表1所示。因此在设定每个单元设备数上，定为1台到3台，基于这样的考虑设定单元数为 8台到15台之间本文运用基于单元数遗传算子表示的遗传算法，解决用整数规划形式的制造单元的设计问题。目标是使联系较为密切的一批包括在同一个单元内。从而使同一单元内设备之间的加工零部件总数最大化。5.2.2 遗传算法的工作原理 遗传算法正是模拟生物在自然界中的进化过程所形成的一种优化求解方法。这种自适应寻优技术可用来处理复杂的线性、非线性问题，且工作机理十分简单。 基于此模型的遗传算法的步骤如下： 1）构造满足约束条件的染色体。由于遗传算法不能直接处理解空间中的解，所以必须通过编码将解表示成适当的染色体。实际问题的染色体有多种编码方式，染色体编码方式的选取应尽可能地符合问题约束，否则将影响计算效率。 2）随机产生初始群体。初始群体是搜索开始时的一组染色体 ，其数量应适当选择 。 3）计算每个染色体的适应度。适应度是反映染色体优劣的惟一指标，遗传算法就是要寻得适应度最大的染色体。 4）使用复制、交叉和变异算于产生子群体。这三个算于是遗传算法的基本算子，其中复制体现了优胜劣汰的自然规律 交叉进化过程中的基因突变。 5）重复步骤3、4直到满足终止条件为止。 5.2.3 遗传算法的求解 1）编码方式遗传算法编码决定了问题的构造以及遗传操作的运作。本文采用基于单元数的遗传算子表示方法。在这种编码中，每个基因值代表了单元编号，基因所在的位置代表相应位置的机器。比如 1 5 3 4 2 6表示六台序号分别为1到6的机器排列顺序，相应的染色体为3 2 2 1 3 1。那么机器1、2被规划到单元3；机器5、3被规划到单元2；机器4、6被规划到单元1。2）交叉率和变异率的设定 本文利用均方差来表示种群的收敛程度。设n表示种群的个体数,Xi表示第i的适应度值的集合,E(Xi)为第i代样本的均值, ；Sxi为样本的标准差。 其中Smax_xi 为到目前为止Sxi的最大值，Kshift定义为进程因子，随着种群进化由0趋向于1。收敛性因子Kc表示当代种群的收敛程度。如果种群较为分散，Kshift减小，Kc增大，反之亦然。故交叉率和变异率就可以通过Kc调节： 3） 交叉与变异方法 采用两分割点杂交方式 例如选择染色体X1和X2进行杂交。 X1=3 2|3 1|1 2 X2=3 2|1 3|2 3 选择分割点位置在第2个第4个基因之后。通过交叉的后代分别为 ,=3 2|1 3|2 3=3 2|3 1|1 2 在进行变异时 随机选择一个基因并由1,Mc之间的单元数替换。比如 X1染色体第3个基因被选中，产生的随机数是2，那么经过变异后的染色体为： 3 2|2 1|1 2 4） 评估函数 定义整数规划模型中的目标函数为评估函数。即 E()=Z () i=1,2,5） 算法步骤 (图3.1)1)初始化群体P(t),并求出各个个体的适应度值( i=1,2, ,M) 2)计算单元适应度。对群体P(t)以轮转法选择机制得到 。3)交叉运算和变异运算。 4)更新单元，得到。计算新一代的Pc和Pm。 5)终止条件判断。若不满足终止条件，则：更新进化代数t t+1。转到第2)步；满足终止条件，则：输出计算结果，算法结束。 图1 算法流程6） 程序说明程序的伪代码如下Procedurebegint:=0Initialize P(t) 初始化群体While not (terminate condition) do begin 进化循环t=t+1roulette selection 轮盘选择crossover 交叉操作mutation 变异操作end whileEnd5.3 遗传算法结果与分析本文利用所建立的设备/单元的布局模型及其求解方法，对单元化生产方式进行规划设计，以检验本文研究方法的实用性和有效性。该模型中包括20台设备和主要加工的20种零部件，零部件加工计划和生产量见表2。零部件加工计划生产量1M18M51342M6M2M8463M8M20M14704M6M2M92005M8M20M9M141006M8M20M21507M8M20M18478M8M20M19M3M132009M8M20M19M3M135010M7M14M97011M18M55012M18M55013M15M910014M11M10M910015M7M14M910016M12M4M6M3M137017M12M4M6M3M135018M1M17M16M2M1310019M1M17M16M2M136020M1M17M16M2M13100表2 零部件加工计划和产量表通过遗传算法，所设计的算法流程，首先随机产生单元分组，得出单元适应度。然后选择交叉运算（随机选择不同单元中的设备互换）和变异运算（选择单元中的设备被随机设备代替），得到交叉率Pc和变异率Pm。求出使设备收敛程度最大的Kc的单元组合。根据程序运行结果（图3），得制造单元分组（表3）。单元分配如图2下：单元12 34567891011机器设备M1M17M2M16M3M13M4M12M5M18M8M20M10M11M9M14M15M7M6M19表3 单元分组图2 单元分组图5.4 两种算法结果综合对比分析 按照整数规划的约束条件，遗传算法的流程及设计的方案，利用Matlab编程进行计算仿真，分别得到了约束条件的整数规划算法和遗传算法的两种仿真结果。图3如下： 图3 仿真结果六、模型进一步讨论6.1 遗传算法的优点与传统的寻优算法相比较遗传算法具有以下特点1.通过上述仿真结果分析出，运用遗传算法是从初始群体开始搜索的并不是从单点开始搜索的，而传统优化方法都是从线性空间的单点出发，通过某些转换规则确定下一点，不断地迭代，得到较准确的结果。2.在此次仿真中以点集开始的寻优过程，初始群体是随机地在搜索空间中选取的，这样在搜索过程中达到最优值的概率远大于点到点方法的概率。3.遗传算法在搜索过程中只使用适应度函数信息而不用其他辅助信息，对于不同类型的优化问题，传统方法需要不同形式的辅助信息。4.遗传算法的主要缺陷是一般只能取得局部最优解而且取得全局最优解的概率比较低，因此在本文中与传统的计算出的物流量有误差。6.2 单元制造的优点很多设计良好的单元制造能满足 1 减少了在制品和物料搬运,一个生产单元完成几个生产步骤,可以减少零件在车间的移动 2 改善人际关系,提高团队绩效,工人组成团队来完成整个任务并负担相应任务 3 提高操作技能,在一个生产周期内,工人只能加工有限数量的不同零件,重复程度高,有利于工人快速学习和熟练掌握生产技能 4 减少原材料和制成品的库存,生产过程中工作的减少使得单元内材料得流动更快 5 缩短生产准备时间 提高设备利用率6 仅需要更少的现场监督 7 增强员工的自我成就感 8 使错误累计最小 七、模型的评价本文利用所建立的设备/单元的布局模型及其求解方法，对单元化生产方式进行规划设计，以检验本文研究方法的实用性和有效性。该模型中包括20台设备和主要加工的20种零部件，零部件加工计划和生产量见附表1。由于该模型中，不同的零件可能进行类似的加工处理，因此搬运设备相似，每次搬运设备的容量相当，由假设每次搬运设备的容量为2个单元，经过换算机器之间的物流量见表。在该模型中主要加工的20种零部件过程基本上都只是在2台到5台设备之间见附表1所示。因此在设定每个单元设备数上，定为1台到3台，基于这样的考虑设定单元数为 8台到15台之间。通过整数规划算法，对总物流量为目标进行综合的分析，得到了一种单元分布方案，该单元分布方案可使得总物流量最小。通过遗传算法，所设计的算法流程，首先随机产生单元分组，得出单元适应度。然后选择交叉运算（随机选择不同单元中的设备互换）和变异运算（选择单元中的设备被随机设备代替），得到交叉率Pc和变异率Pm。求出使设备收敛程度最大的Kc的单元组合。通过Matlab计算后，分别得到两种算法的仿真结果，从结果可知，在误差允许范围内，两种