简单装配线平衡问题

第２章简单装配线平衡问题２．１　简单装配线平衡问题概述简单装配线平衡问题（ＳｉｍｐｌｅＡｓｓｅｍｂｌｙＬｉｎｅＢａｌａｎｃｉｎｇＰｒｏｂｌｅｍ，ＳＡＬＢＰ）是经典装配线平衡问题中被研究最多、最为深入的一个领域，是其他所有装配线平衡问题的基础，尤其是第Ⅰ类装配线平衡问题（ＳＡＬＢＰＩ———给定装配线节拍，最小化装配线工作站数量）。在装配线的 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 与安装阶段，主要以生产能力满足市场需求、系统投资少和装配线的效率高为目标。这一阶段是基于对市场需求的预测以及设备能力的估算，来最小化工作站数。最小化工作站数就意味着设备与人员的减少，从而降低设备与人员费用，优化生产 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 ，提高生产效率。系统一旦安装，短期内人员和设备难以调整，此即第Ⅰ类装配线平衡问题。随着装配线应用的日益熟练以及环境的不断变化，装配线也需要随之不断调整，此时就会出现考虑调整装配线节拍（ＳＡＬＢＰＩＩ），工作站负荷均衡的问题，以及装配线上作业元素之间相关性等问题。简单装配线平衡问题的一般描述是：已知产品的装配作业（名称、时间以及优先关系），给定该产品的市场需求Ｄ以及可用的生产周期Ｔ０，基于一定数量ｍ的工作站（如机器设备、人员等），满足生产需求。基本的装配线平衡问题的一般假设有：（１）装配线只生产一种类型的产品；（２）作业时间是确定的；（３）作业是最小不可分的最小自然单位，一个作业不能被分配到两个工作站中；（４）一个作业的时间不依赖于工作站；（５）在不违背优先关系约束的前提下，一个作业可以被分配到任何一个工作站；（６）装配线上没有并行的工作站；（７）装配线上作业人员的技术水平不存在差异，可以完成任意一项作业；（８）装配线的节拍不小于（大于或者等于）作业元素时间中的最大者。根据简单装配线平衡的目标，简单装配线平衡问题又可以分为：ＳＡＬＢＰＩ，ＳＡＬＢＰＩＩ，以及工作站负荷均衡问题和装配线上作业元素之间的相关SALBP鄄E,SALBP鄄F(SALBP鄄III)性问题(SALB鄄IV)。接下来我们将分别建立这几类问题的数学模型其中重点介绍,,SALBP鄄I,SALBP鄄II。2.2摇第一类装配线平衡问题(SALBP鄄I)2.2.1摇第一类装配线平衡问题的描述第一类装配线平衡问题是基于最少的物质资源如工作站操作人员来满足需求这(、),是其他类型装配线平衡的基础。第一类装配线平衡问题提法是假设装配线的节拍C已经确定最小化装配线的工作:,站数m。已知参数:D市场需求T可用的生产时间这里由DT可以确定节拍C=T/D我们用:,0:(,,00)。有向图G=VA摇寅t来描述产品装配作业元素优先关系其中V=n 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示产品{,,},{1,2,…,}装配作业的集合n为有向图的节点数量代表所有装配作业的数量A=ij|iVj,,;{(,)沂,F表示有向图的弧代表所有的作业i与作业j直接优先关系即作业i是作业j的直接沂i},,先行作业摇寅t=t|i=n是节点的权重代表作业i的作业时间;{i1,2,…,},。决策问题:能够使生产满足需求的最少工作站数目m。2.2.2摇模型建立假设n个装配作业已经分配到m个工作站中最少的工作站数量意味着整个装配线的,总空闲时间最短因此工作站数量最小的目标等价于装配线的总空闲时间最短。,。分配装配作业到工作站的过程就是决定作业i分派到哪一个工作站k的过程因此。,定义决策变量0鄄1当作业i被分配到第k工作站xik=1,{当作业i未被分配到第k工作站0,式中i=nk=m:1,2,…,;1,2,…,。的数学模型为SALBP鄄IModel(Ia)。目标函数(1)n(mC-ti).mini=(21)移1约束条件摇摇(2)mxik=i=n.k=1,1,2,…,(22)1移nxiktiCk=m.i=臆,1,2,…,(23)移101摇4装配流水线平衡和投产排序———模型、算法与仿真摇xxijPsetk=m.ik臆jk,坌(,)沂,1,2,…,(24)决策变量摇摇(3)当作业i被分配到第k工作站xik=1,{当作业i未被分配到第k工作站0,式中i=nk=mm是工作站数量也是决策变量:1,2,…,;1,2,…,,,。目标函数式是最小化装配线总空闲时间由于节拍C是给定的作业时间ti(2.1)。,i(=n是给定的因此目标函数实质上就是最小化工作站数1,2,…,),。约束条件式表示任何一个作业i都要被分配到一个特定工作站k中而且只能分(2.2),配到唯一的工作站中。约束条件式表示任何一个工作站k的工作站时间不能超过给定的节拍C(2.3)。约束条件式表示装配线平衡中不能违反优先关系约束在直接优先关系集合(2.4),Pset=ij|ijijV中任何一对优先关系ij作业i的分配必须不迟于作业j的{(,)刍,,沂}刍,分配。值得注意的是第一类装配线平衡问题的数学模型是非线性的这,SALBP鄄IModel(Ia),将给求解带来很大的困难因为线性规划才容易求解实际上只有当工作站数量m是给,。,定的时候才是线性的而在模型中m出现在下标中同时又是决策,Model(Ia)。Model(Ia),,变量因此模型是非线性的,Model(Ia)。因此在模型中决策变量的个数为mn+个约束条件的个数为p+,Model(Ia)(1),[(m+np为存在优先关系的作业元素个数1)],。为了求解的方便有必要把非线性的转化成线性的,Model(Ia)。由于既有整数决策变量又有决策变量是一个混合整数非线性规划Model(Ia),0鄄1,。我们把上述的混合整数非线性规划转换成一个线性规划便于求解Model(Ia)0鄄1,。首先给出一个工作站数上限m这个m不小于理论最小工作站数比如通过一些启发0,0(式算法或者经验预估等,)。决策变量如下。作业元素的标识变量如果作业i分配到第k工作站xik=1,{如果作业i没有分配到第k工作站0,式中i=nk=m:1,2,…,;1,2,…,0。工作站的标识变量如果第k工作站开启Wk=1,{如果第k工作站没有开启0,式中k=m:1,2,…,0。则上述的混合整数非线性规划可以转变为线性规划Model(Ia)0鄄1Model(Ib)。第2章摇简单装配线平衡问题01摇5摇目标函数m摇摇(1)0Wk.mink=(25)移1约束条件m摇摇(2)0xiktiCk=m.i=臆,1,2,…,0摇摇摇(26)1移m0xik=i=n.k=1,1,2,…,(27)移1Wk+Wkk=m-.1臆,1,2,…,01(28)nxikn伊Wkk=m.i=臆,1,2,…,0(29)1移mm00kxikkxjkijPset.k=臆k=,坌(,)沂(210)移1移1由于m是一个预估值是装配线可以开启的工作站数量目标函数式就是最小摇摇0,,(2.5)化装配线上最终需要开启的工作站数量。约束条件式保证工作站内的作业负荷不超过给定的节拍时间(2.6)。约束条件式保证每个作业元素都必须分配到唯一的工作站中(2.7)。约束条件式保证装配线上顺序排列的m个工作站中如果k+工作站被启(2.8)0,(1)用则前面的第k个工作站一定要启用,。约束条件式保证如果第k工作站中存在作业元素则第k工作站必须要开启(2.9),。其余的几个约束等同于混合整数规划。约束条件式是作业元素之间的优先关系约束这里使用式来代替式的(2.10)。(2.10)(2.4)好处是式中的每一个约束可以用式中的m个约束来表示显著地减少了约束数量(2.10)(2.4)0,。决策变量(3)作业元素的标识变量如果作业i分配到第k工作站xik=1,{如果作业i没有分配到第k工作站0,式中i=nk=m:1,2,…,;1,2,…,0。工作站的标识变量如果第k工作站开启Wk=1,{如果第k工作站没有开启0,式中k=m:1,2,…,0。显然是线性的规划其中变量的数量为mn+个线性约束,Model(Ib)0鄄1,:0鄄10(1),的数量为m+n+p-个其中p为存在优先关系的作业元素组的个数(301),。这里我们暂时不讨论求解算法下面先给出一个的例子,SALBP鄄I。揖例21铱简单装配线平衡[1].摇一条组装型玩具马车的装配线每天的市场需求量D=辆每天的可用生产时间J,500,为T=分钟表列出了装配线上作业的名称时间以及优先关系试进行装配线平420,2.1、。衡以最少工作站数来满足供需平衡,。01摇6装配流水线平衡和投产排序———模型、算法与仿真摇表2.1摇J型玩具马车的装配步骤及其时间作业(i)时间(ti)作业描述优先作业(j),i 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 工作站序号工作站内作业工作站时间(s)空闲时间(s)11455.424500.432,5,8,9500.443,6,7,10,11500.4汇总1956.6由于实际上装配线的工作站数是这个数字等于理论上的最小工作站数因此上述4,,装配线平衡方案就是最优的平衡方案装配线平衡结果如图所示。2.2。图装配线平衡的图示效果2.2摇对于上述模型暂时没有讨论其算法在后面的章节中将有详细论述Model(Ib),,。2.3摇第二类简单装配线平衡问题(SALBP鄄II)2.3.1摇第二类装配线平衡问题的描述在装配线系统安装后设备与人员基本固定需要优化装配线的节拍即在现有的给,,。定资源人员机器设备等基础上最大化装配线的产出此即第类装配线平衡问题(、),。域由于下列因素的存在需要对装配线做进一步调整(SALBP鄄II)。,:在生产运作管理中希望提高劳动生产率最大化装配线的产出(1),,;由于学习效应的存在生产线上的操作人员技能越来越熟练劳动定额发生变(2)“冶,,化在工作站数确定的条件下最小化装配线的节拍可以提高装配线单位时间内的产出;,,。同上面介绍的背景假设装配线上的作业时间确定工作站数量m已知最小化装配,,,线的节拍C从而最大化装配线的产出,。2.3.2摇模型建立第类装配线平衡的数学模型如下域Model(II)。02摇0装配流水线平衡和投产排序———模型、算法与仿真摇决策变量(1)作业元素的标识变量:如果作业i分配到第k工作站xik=1,{如果作业i没有分配到第k工作站0,式中i=nk=m装配线的节拍C为实数决策变量:1,2,…,;1,2,…,;。目标函数(2)C.min(211)约束条件摇摇(3)nxiktiCk=m.i=臆,1,2,…,摇摇摇摇(212)1移mxik=i=n.k=1,1,2,…,(213)1移mm00kxikkxjkijPset.k=臆k=,坌(,)沂(214)移1移1仍然是一个包含n伊m个变量和一个实数变量的线性规划目标函数摇摇Model(II)()0鄄1。式是最小化装配线节拍约束条件式以及式的含义分别同模(2.11);(2.12)、(2.13)(2.14)型的约束条件式和Model(Ib)(2.6)、(2.7)(2.10)。通常第类装配线平衡问题的数学模型相对于第类装配线,域(SALBP鄄II)Model(II)玉平衡问题的数学模型来说约束条件要少一些因此模型的变量个Model(Ib),。,Model(II)数是n伊m+其线性约束条件有m+n+p个(1);()。下面给出一个第类装配线平衡的算例来自网址为域。http://alb.mansci.de/index.php?content=classview&content2=classview&content3=classviewdlfree&content4=classview&classID中的装配线平衡的数据集文件中的问题具体数=28&type=dl(SALBPdatasets.zip)Jackson,据见表2.3。表2.3摇第域类装配线平衡中的Jackson问题的数据作业(i)时间(ti)优先作业(j,iTS在不违反优先关系和节拍的约束下将第个工作站中作业摇摇(1)(2),,1时间为但是我们将Model(IIIb)0鄄1。,0,这个约束条件忽略了从实际意义上看如果要使目标函数最小化只有C>才。,(2.19),0满足要求。2.4.3摇装配线工作站负荷均衡实例揖例23铱这里以例中数据为例来说明装配线符合均衡问题同样取工作站数量.摇2.2。为m=和m=平衡的结果见表58。2.5。可以计算出例中第类装配线平衡结果的指数当工作站数m=时相应的2.2域SI,5,最小工作站负荷为然而在负荷均衡的优化中最小的工作站负荷为相应SI=10,7,,,8,的当工作站数为m=时相应的SI=10。8,SI=22。从上面的分析可知装配线负荷均衡使得工作站中的负荷变得均匀了,。02摇4装配流水线平衡和投产排序———模型、算法与仿真摇表2.5摇装配线工作站符合均衡问题的解工作站序号工作站内作业工作站时间(s)空闲时间(s)m=(1)511,2,59126,88233,1010044,710059,1191最小节拍C=10,SI=6m=(2)811612352347042,5,76156,97068617105281143最小节拍C=7,SI=252.5摇装配线平衡中作业元素之间的相关性问题这里把装配线平衡中的作业元素之间的相关性问题称为这类问题的平衡SALBP鄄IV。条件同第类确定型装配线平衡假设给定装配线的节拍平衡的目标是玉,,:最小化装配线上的工作站数(1);在满足的条件下最大化装配线上的作业元素之间的相关性(2)(1),。装配线上作业元素之间的相关性可以使用相关性指数表示SNN=SNNPNjj=移1式中N表示工作站数PN表示在第j个工作站中各个作业元素在装配优先图中构成的孤:;j立网络数相关性指数在实践中的意义是指在分配作业元素时尽量把相关的作业元素分。,配在同一个工作站一方面便于工人的操作另一个方面便于物料的流动,,。以问题为例来说明相关系数的算法问题的优先图如图所示Bomman。Bomman2.3。图问题的优先关系图2.3摇Bomman第2章摇简单装配线平衡问题02摇5摇假设工作站的分配情况如图所示2.4。图假设装配线节拍C时工作站的分配情形2.4摇=26在上述情形下各个工作站的孤立网络数分别为,PN=PN=PN=PN=11,21,32,41相关系数为摇摇SN=4=.+++081121如图所示是工作站的另外一种分配情况在这种情况下摇摇2.5,PN=PN=PN=PN=11,21,31,41SN=4=.+++101111图假设装配线节拍C时工作站的分配情形2.5摇=26第类确定型装配线的平衡是一种多目标的平衡其算法与前面几种类似摇摇郁,。2.6摇装配线平衡中效率优化问题(SALBP鄄E)在装配线平衡问题和中是在工作站数量m或者节拍C是已知的条SALBP鄄ISALBP鄄II,件下最大化装配线的效率而问题是在工作站数量m和节拍C均未知的条件,。SALBP鄄E下最大化装配线的节拍也就是寻找一个数组mC使得mC最小,,(,)·。由于目标函数中含有两个变量的乘积问题已经不是线性模型但是可以,SALBP鄄E。,通过固定工作站数量m或者节拍C的值转化为一系列的和问题从而,SABLP鄄ISABLP鄄II,基于线性模型来求解。02摇6装配流水线平衡和投产排序———模型、算法与仿真摇数学模型与和相似为了模型的完整性这里依然列出SABLP鄄ESALBP鄄ISABLP鄄II。,的数学模型SABLP鄄E(Model鄄E)。决策变量(1)m工作站数量———;C装配线的节拍———。作业元素的标识变量如果作业i分配到第k工作站xik=1,{如果作业i没有分配到第k工作站0,式中i=nk=m:1,2,…,;1,2,…,。目标函数(2)nE=ti/mC.mini=(222)移1约束条件摇摇(3)nxiktiCk=m.i=臆,1,2,…,摇摇摇(223)1移mxik=i=n.k=1,1,2,…,(224)1移mmkxikkxjkijPset.k=臆k=,坌(,)沂(225)移1移1其中目标函数也可以写作摇摇(2.22)nmC-ti.mini=(226)移1或者mC.min(227)以图中的问题为例说明问题不同mC对应的装配线效摇摇2.3BommanSALBP鄄E,(,)率见表2.6。表2.6摇Bomman问题中SABLP鄄E分析m12345C7538282217E(%)10098.6889.2985.2388.24从表可以看出装配线的效率E首先随着工作站数量m的增加而减少当m=2.6,,4时达到最低当m>时装配线的效率E又在上升;4,。当工作站数m=时节拍C达到了最小值因为最大作业时间为所以当5,17(17)。,mC均未知时不同mC的最佳组合都被罗列在表(,),(,)2.6。装配线平衡效率优化问题与装配线平衡的可行性分析问题密切联SABLP鄄ESABLP鄄F系问题解决给定一组mC是否存在工作站数为m节拍为C的装配线平。SABLP鄄F:(,),、衡方 案例 全员育人导师制案例信息技术应用案例心得信息技术教学案例综合实践活动案例我余额宝案例 如对于图中的问题工作站数为节拍为对应的平衡效率。,2.3Bomman,3,25(E%是否可行=100)?第2章摇简单装配线平衡问题02摇7摇根据表可知当装配线上的工作站数量为时最小的节拍为因此组合2.6,3,28。,(3,25)不是一个可行的平衡方案相反地组合是一个可行的平衡方案;,(3,29)。理查德蔡斯等运营管理任建标等译北京机械工业出版社[1].B.,.[M].,.:,2004.[2]CHASERB.Surveyofpacedassemblylines[J].IndustrialEngineering,1974,6(2):14鄄18.02摇8装配流水线平衡和投产排序———模型、算法与仿真摇