生产线平衡翻译初稿.doc

-摘要本文提出了结合SALBP-1和SALBP-2的E型简单装配线平衡问题SALBP-E，更多的，本研究为提出的模型提供了解决方法。提出的模型在最小化空闲时间的同时优化装配线平衡率，为管理实践提供了更好的理解，计算结果说明：给出周期的上限以后，提出的模型可以最优的解决问题，因为它含有最少的变量，约束和计算时间。1前言从研究者第一次讨论装配线平衡问题以来，大约有50年了，在众多有关生产线平衡问题中，最根本的是简单装配线平衡问题，早在1954年，Bryton就定义并且研究了生产线平衡问题。后一年，Salverson建立了第一个生产线平衡的数学模型并提出了定性的解决步骤，这引来了很大的兴趣，在Gutjahr 和 Nemhauser说明生产线平衡是一种NP组合优化难题，大多数研究者希望开发一种能高效解决多种装配线问题的方法。在随后的几年,生产线平衡成为了一个流行的主题，Kim, Kim, and Kim (1996) 把生产线平衡分为五类问题，其中的问题1SALBP-1和问题(SALBP-)是两种根本的优化问题。研究者发表了许多有关解决SALBP-1问题的研究结果，Salverson1995用整数规划解决工作站分配问题，Jackson用动态规划解决SALBP-1，Bowman提出了两种数学模型并引入了0-1变量保证没有不同任务占用同一时间且同一任务不被分配到不同的工作站。Talbot 和 Patterson (1984)提出了一个数学模型，它还有一个单一变量，专门用来计量分配到工作站的任务数量， Essa, Delorme, Dolgui, 和 Guschins-kaya (2010) 提出了一个解决由一样的数控机床构成的线平衡问题的混合整数规划模型，Hack-man, Magazine, and Wee (1989)使用分支定界法解决了SALBP-1，为了减小分支的数量，他们提出了启发式深度测量技术，提供了一个高效率的方法，Betts and Mahmoud (1989), Scholl and Klein(1997, 1999), Ege, Azizoglu, and Ozdemirel (2009)建议实施分支定界法，其他的启发式方法已经被用来解决多种问题，这些包括模拟退火算法(Cakir, Altiparmak, & Dengiz, 2011; Saeid & Anwar,1997; Suresh & Sahu, 1994)，遗传算法(McGovern & Gupta,2007; Sabuncuoglu, Erel, & Tayner, 2000)、蚁群优化算法(Sabuncuoglu, Erel, & Alp, 2009; Simaria & Vilarinho,2009)，现今，随着顾客多样化需求的出现，多目标问题产生了。例如， Rahimi-Vahed和 Mirzaei (2007)提出了一种混合多目标算法，包括总效用工作最小化，总生产速率变化最小化、总过程本钱最小化。Chica, Cordon, and Damas (2011)提出了一种模型，包含一系列具有冲突目标的联合优化，这些冲突目标包括周期、工作站数目、工作站数目的面积等。另一个有趣的延伸是混合模型问题，这是装配线平衡的一个特殊的例子，它允许不同型号的产品在同一生产线上流动。为了解决混合模型装配线平衡问题，Erel和 Gökçen (1999)对混合模型装配线进展了研究并且建立了0-1整数规划模型和结合顺序图以减少决策变化和解决侠侣增长的约束条件。Kim 和 Jeong (2007)使用包含依赖于序列的准备时间的运输系统解决了混合模型装配线平衡中工作输入队列的优化问题。Özcan and Toklu (2009) 提出了一个数学模型，用来解决混合模型的双边装配线平衡问题，目标是解决成对工作站和周期的工作站数目的优化问题。 不同于SALBP-1，SALBP-2的目标是给定假设干工作站，最小化它们的周期时间。大多数研究都只关注SALBP-1的解，而不是关注SALBP-2的解，这是因为SALBP-2可以通过逐渐增加SALBP-1的周期直到装配线平衡的方法来解决。早在1961年，Helgeson 和 Bimie就已经提出了一种解决SALBP-2的启发式算法。Scholl (1999)提出了几个关于装配线系统安装和利用的决策问题，说明在有节奏的装配线中，平衡问题是非常重要的。Scholl运用面向任务的分支定界法来解决SALBP-2，然后将结果与已存在的解决方案进展比拟。Klein和Scholl (1996)采用新的统计方法作为解决方案，并且为直接解决SALBP-2开发了一个广义的分支定界法。此外，Gökçen 和Agpak (2006)运用目标规划求解简单U形装配线平衡问题，在这个问题中，决策者必须同时考虑几个冲突的目标。Nearchou (2007)基于微分进化提出了一个启发式算法来解决SALBP-2。紧接着，Nearchou (2008)基于多目标微分进化法又提出了一个新的启发式算法来解决SALBP-2。Gao, Sun, Wang, and Gen (2009)提出了一个机器人装配线平衡问题，在该问题中，装配线任务必须要分配给工作站，并且每一个工作站都需要选择一个可用的机器人以最小化周期为目的来处理分配到的任务。在文献中还表述了其他的方法。例如， Bock (2000)提出了用禁忌搜索解决SALBB2，他还利用并行宽度拓展了禁忌搜索，并行宽度可以用来提升现存的禁忌搜索程序以解决装配线问题，Levitin, Rubinovitz, 和Shnits(2006)开发了遗传算法，通过应用一个简单的进化规则和分支定界法解决大型、复杂的机器装配线平衡问题。Asan 和Tunali (2008)给出了遗传算法解决装配线问题的完整观点。 大多数研究都集中在SALBP-1和SALBP-2，很少有关于优化装配线平衡率的研究。这种类型的问题被称作SALBP-E，本文构建了SALBP-E和解决SALBP-E问题的模型， SALBP-E被定义为，是处理装配线平衡率等问题的。所有工作的总时间是工作站的数目与周期的乘积。SALBP-E试图让装配线平衡率最大而使空闲时间最小。换句话说，SALBP-E就是为了减少工作站的数目和周期。文章接下来的类容是这样组织的，章节2介绍SALBP-E的公式和解决过程。章节3说明利用小到中型数学计算解决一个笔记本装配线模型和一些测试问题。文章最后做了一个总结。2 SALBP-E的公式和解决过程SALBP-E集成了SALBP1和SALBP2模型，为了到达这个目标，定义以下符号和变量：n 任务数量i=1,2,3，.nm 站的数目j=1,2,3，.m 工作站最大值j=1,2,3，. 工作站最小值j=1,2,3，. 任务i的运行时间 周期P 任务i，k的子集，直接给出优先级关系决策变量： 如果任务i分配到任务j为1，否则为0， () 如果任何一个任务i分配到j为1，否则为0，(j=1.) 周期大于等于0 工作站最小数SALBP-1的原始模型如下： 1 2 3 4 5对于SALBP1的原始模型，目标函数1保证了工作站数目m最小，工作站的周期，约束2用来约束第i个工作只能被分配到一个工作站。约束3约束分配到工作站j的任务的总时间不超过周期。约束4定义了优先关系，约束5确定了如果*个工作i被分配到了工作站j，则它的值为1，否则为0，在目标函数1中，是未知的且不能解出来，变量y用来促进解决方案，修正后的模型SALBP-1-i是如下定义的，目标函数6决定了在周期CT情况下工作站最小数mmin，约束7-10与上面SALBP1的约束2-5定义类似。约束11的意思是如果任何一个工作分配到工作站j，则它的值为1，否则设置为0.SALBP-1-i：.6.789.10.11SALBP-2的模型如下，目标函数是在工作站数目的情况下保证周期最小，约束13-16与上文SALBP1约束2-5的定义方法一样。SALBP-2.1213141516SALBP-E 结合了SALBP-1和SALBP-2. (17). (18). (19). (20) (21). (22) SALBP-E被定义为，所以空闲时间为，使装配线平衡率最大和空闲时间最少可以通过使产品的工作站数目和周期最小来实现，目标函数17使产品的周期和工作站数目最小，约束18-22与SALBP1-i的定义方法一样。对于装配线平衡的大多数模型，第一步就是通过计算最早站ei和最近站li来确定哪个工作i可以被分配，来减少分配到工作站的工作。两个变量Ei和Li，用来再定义SALBP2模型， (Pastor, Corominas, & Lusa, 2004)，在SALBP2-i模型中，表示任务i之前的工作，表示任务i之后的工作。*表示不超过*的最大整数， 和是如下定义的：再定义的SALBP2模型叫做SALBP2-i，有关符号和变量如下定义：定义变量：0基于SALBP-2-i模型，目标函数23保证了在工作站数目情况下周期ct最小，约束24-27与上文中SALBP1的定义类似。SALBP-2-i.23.24.2526.27SALBP-E模型的最优工作站的数目定义为m，在此之前ctma*必须给出，ctma*表示所有工作的最大值与所有任务的时间被2除后的值中间的较大者。这个值必须大于或者等于所有任务中的最长时间同时必须所有任务的时间之和。如果ctma*比所有工作的总时间要大，则只需要一个工作站就可以了，如果ctma*小于或等于所有工作中最长时间，则问题无解。Ctma*的约束条件如下：，平衡损失为0无解在确定ctma*值之后工作站的最有数目就可以确定了。M的值介于mmin与mma*之间。工作站的最小数目mmin是所有任务的总时间除以ctma*，工作站的最大数目mma*是所有任务的总时间除以所有任务中的最长时间。M的值如下定义：周期的上界ctma*定义之后， LINGO 和 E*cel VBA 可以取得SALBP2和SALBP2-i的工作站的数目，然后可用E*CEL计算产品的工作作战数目和周期。给出一个ctma*m在mma*与mmin之间Solve SALBP-2 和 SALBP-2-i计算e=m*ct得最优的m，e，ct输出最优e，m，ct完毕mmma*NOYESLINGO 配合E*CEL VBA解决SALBP-2和 SALBP-2-i工作站数目m由E*CEL VBA确定，保证m由mma*增大到mminWIPSTRUCAFTTPDLR/IPFTCOSM打包SWDLOBE装运修复修复修复成功失败失败成功成功失败图2 典型笔记本电脑装配3计算结果表1 笔记本电脑装配职能命令功能工具ASTRUC构造装配螺旋给料器、螺丝刀、胶带分割器BAFT装配HDD、键盘、RJ45标准线、SY卡、扫描仪、笔记本功能检测TPDLCTPDL检测、程序下载DR/I运行支架试车EPFT程序功能测试电池、BIOS电池、ODD、WWAN卡、笔记本、扫描仪F修饰、打包螺丝刀、扫描仪、DTCGSWDL下载支架3.1笔记本电脑组装实例表2 笔记本组装操作与时间功能工位操作时间STRUCA1拿起主板粘贴PPID10.4A2拿起逻辑纸2.19A3装配风扇5.85A4装配逻辑纸和MB5.84A5打螺丝7.12A6装PCMCIA框架10.73A7装RAM3.25A8装调制解调器6.54A9装CPU4.25A10装火花塞线7.71A11装扬声器6.15A12装散热器6.25A13拧六角螺丝12.78ATFA14装HDD和键盘6.1A15整理、清洁5.96A16检查RJ45接口12.38A17检查1394接口5.51A18检查键盘24.28A19检查USB5.65A20检查SY CARD13.78A21装硬盘和键盘4.46A22扫描条形码6.6A23拿起SWDL支架4.51PTFC1转到根底单元3.63C2组装电脑部件36.38C3检验41.83C4分解32.07C5拿起SWDL2.12修饰与包装C6扫描条形码5.28C7分解31.04C8盖章16.21C9修饰16.36C10扫描条形码11.3C11包装28.4表3 笔记本电脑组装测试结果SALBP-2STRUC和AFTmCtm A ctVCTE289.23178.46475210.999047359.63178.89705310.996646448.28193.12935410.923208538.34191.071165510.930047631.40188.401395610.946338729.93209.511625710.850986824.39195.121585830.913745812385PTF和打包113.91227.82232410.98595481.84245.52342510.901487572.27289.36452610.91487556.06280.30562710.77701741.83250.98672810.80135622513010.897552表3续SALBP-2STRUC和AFTmCtm A ctVCTE289.23178.46375210.999047359.63178.89705310.996646448.28193.12935410.923208538.34191.071165510.930047631.40188.401395610.946338729.93209.511625720.850986824.39195.121855820.913745812385PTF和打包113.91227.82232410.98595481.84245.52342510.901487572.27289.36452610.91487556.06280.30562710.77701741.83250.98672810.80135621311810.894972表4 测试数据文件名n*TMA*TSUMJACKSON.IN2Jackson1111746MITCHELL.IN2Mitchell212113105HESKIA.IN2Heskia28281081024BU*EY.IN2Bu*ey292925324SAWYER.IN2Sawyer303025324LUTZ.IN2Sawyer3032140014140GUNTHER.IN2Gunther35113540483KILBRID.IN2Kilbridge45214555552HAHN.IN2Hahn532853177514026表5 JACKSON11测试结果SALBP-2模型mctM a ctVCTEJACKSON112234623271131648342810.95833341248452910.58333351050563010.926954673110.8518527856783210.832149303177表5 续SALBP-2-i模型mctM a ctVCTEJACKSON112234620241131648342810.95833341248452910.58333351050563010.926954673110.8518527856783210.821429300174表6 测试结果1SALBP-2 modelmctmctV*CTEMitchell213351056452<1152110510654<11Heskia28251210245770<11425610241137221Bu*ey2921623245968<1131083248869<11Sawyer3021623246165<1131083249166<1148132412167<11Lutz3227076141526573<10.999152Gunther35316148310684<11Kilbridge45227655291110<113184552136111<114138552181112<1169255227111441Hahn532701414028107138<10.999857表6 续SALBP-2-i modelmctmctV*CTEMitchell213351056452<1152110510654<11Heskia28251210245568<11425610241137211Bu*ey2921623244655<1131083248869<11Sawyer3021623245155<1131083249166<1148132412167<11Lutz3227076141524250<10.999152Gunther35316148310684<11Kilbridge45227655281100<113184552136111<114138552181112<1169255227111441Hahn53270141402886117<10.999857表7 测试结果2SALBP-2-i modelSALBP-2-i modelTV*TCTVTCMitchell21932436929433Heskia2815216661519664Bu*ey2926228822609869Sawyer3027128462702836Lutz3220907752067752Gunther353162106231541054Kilbridge452935114529251135Hahn5318629871814966 图2展示了一个典型的笔记本装配制造过程。此图描述了装配的相对序列和它的过程功能。首先所有材料组装起来转移到构造组装STRU。然后，这个未完成的局部被转移到功能测试AFT，目的是检查组装加工的功能。之后，在测试程序下载TPDL下载测试程序。下一步，这个程序是在运行过程中实现的。完成之后，这局部输入程序功能测试PTF。紧接着，这局部在软件下载SWDL下载软件。最后，这局部在包装站完成包装程序，表一是所有程序功能的指标。所有装噢诶程序都是有序设置的，其中一局部可以更改，另一局部不能。机器随着序列的变化而变化，这个程序中的三个过程不是手工组装业务：载荷检测、修复、运输。这三个功能被排除在装配线之外因为它们是线下操作。剩下的七个职能可以被分为组装职能和机器职能，如表一所示。基于引入了动作要素和人工操作，职能ABEF被称作装配职能。其他职能是机器运转。几乎所有的机器职能都是执行的机器运转。在此例中，自动化的物料搬运执行所有的动作。机器依据程序步骤的顺序在没有操作者的帮助下运转。因此，这个研究不必要涉及机器的安排。但是，装配功能涉及到许多任务和操作者的操作，也需要更多的考虑。表2展现了不同操作序列和STRUC Function, AFT Function, PFT Function,and Packing Process所需要的时间。基于上表所示的任务时间，ctma*计算出的值为90并且。通过展现SALBP-2和SALBP-2-i的模型到之间逐渐增加1，表3说明当使用SALBP-2模型去解决STRUC和ATF功能的时候，所有变量和所有约束的数分别为812和385。相反的，当使用SALBP-2-i模型的时候，变量的总数和约束的总数分别为802和375，明显的，SALBP-2-i模型是较快的解决方法。校正周期产生了不同结果。当时，最优工作站的数目为，当时，工作站的最优数目，当时，最优工作站数目，当时，最优工作站数目。不管使用哪种模型，当，是最小值，这是最高的效率。如表3所示，当使用SALBP-2模型解决PTF和包装功能时，变量数之和约束数之和分别为213和118.在这里，SALBP-2-i模型较快获得了结果。这些结果与现行装配线工作站的安排是一致的。3.2测试问题 本文的测试问题来源于Scholl, Boysen, Fliedner, and Klein (1995)建立的。表4展现了任务从11到53时的九个测试问题。例如，JAKSON拥有最少的工作任务，n的值为11.HAHN53有最多的任务数，n值为53.这节利用了SALBP-2和SALBP-2-i解决问题。表5展示了当使用SALBP-2模型解决问题Jackson 11时，变量的总数和约束的总数分别为303和177,。相反的，当使用SALBP-2-i解决JACKSON 11时，变量的总数和约束的总数分别为300和174.因此，SALBP-2-i模型是一种较快速的解决方法，因为它减少了约束和变量的数目。当使用ALBP-2-和ALBP-2-i模型解决JACKSON 11时，最优的解决方法是当时。表6总结了剩下的测试问题的结果。表7说明了当使用SALBP-2模型解决Mitchell21问题时，变量数目TV和约束的数目TC分别为932和436。当用SALBP-2-i解决问题Mitchell21时，变量和约束的数目分别为929和433.因此SALBP-2-i是一种较快的解决方法。不管是用SALBP-2还是SALBP-2-i解决Mitchell21问题，最优的解决方法是当。其它的测试问题也收到类似的结果。4总结和建议这篇文章通过SALBP-1和SALBP-2模型构造了SALBP-E模型，这个拟建的模型最小化了空闲时间，优化了装配线平衡率。这不同于先前的方法，没有明显的考虑生产线平衡效率。为了得到更快的解决方案，对拟建的模型参加了两个变量，并且重新定义了SALBP-2模型。基于笔记本电脑装配和任务数量从11到53变化时的测量结果，这个拟建模型能够获得最优工作站数目的围。平衡率是装配线平衡率很好的评价指标，因为它简单易懂，可以引导职能经理评估不同的决策，特别是当产品的不同规格要求对生产线平衡逐渐改良时。未来关于这个主题的研究的研究可以通过结合现存的启发式算法与拟建的解决程序引入更多任务或者研究其他的装配线平衡问题。致本研究支持局部由美国国家科学委员会,中华人民国国,批准号NSC99-2622-E-214-007-CC3。作者还要感两位匿名学者的建立性的和有用的评论。参考文献1 Baybars, I. (1986). A survey of e*act algorithms for the simple assembly linebalancing problem. Management Science, 32(8), 909932.2 Betts, J., & Mahmoud, K. I. (1989). Identifying multiple solutions for assemblyline balancing having stochastic task times. puters & Industrial Engineering,16(3), 427445.3 Bock, S. (2000). A new parallel breadth rst tabu search technique for solvingproduction planning problems. International Transactions in OperationalResearch, 7, 625635.4 Boysen, N., Fliedner, M., & Scholl, A. (2007). A classication of assembly linebalancing problems. European Journal of Operational Research, 183(2), 674693.5 Boysen, N., Fliedner, M., & Scholl, A. (2008). Assembly line balancing: Which modelto use when" International Journal of Production Economics, 111, 509528.6 Bryton, B. (1954). Balancing of a continuous production line. Management Sciencethesis. North-Western University.7 Cakir, B., Altiparmak, F., & Dengiz, B. (2011). Multi-objective optimization of astochastic assembly line balancing: A hybrid simulated annealing algorithm.puters & Industrial Engineering, 60, 376384.8 Chica, M., Cordon, O., & Damas, S. (2011). An advanced multiobjective geneticalgorithm design for the time and space assembly line balancing problem.puters & Industrial Engineering, 61, 103117.9 Ege, Y., Azizoglu, M., & Ozdemirel, N. E. (2009). Assembly line balancing with stationparalleling. puters & Industrial Engineering, 57, 12181225.10 Erel, E., & Gökçen, H. (1999). Shortest-route formulation of mi*ed-modelassembly line balancing problem. European Journal of Operational Research,116, 194204.11 Erel, E., & Sarin, S. C. (1998). A survey of assembly line balancing procedures.Production, Planning and Control, 9, 414434.12 Essa, M., Delorme, *., Dolgui, A., & Guschinskaya, O. (2010). A MIP approach forbalancing transfer line with ple* industrial constraints. puters &Industrial Engineering, 58, 393400.13 Gao, J., Sun, L. Y., Wang, L. H., & Gen, M. (2009). An efcient approach for type IIrobotic assembly line balancing problems. puters & Industrial Engineering,56, 10651080.14 Ghosh, S., & Gagnon, R. J. (1989). A prehensive literature review and analysis ofthe design, balancing and scheduling of assembly systems. International Journalof Production Research, 27, 637670.15 Gökçen, H., & Agpak, K. (2006). A goal programming approach to simple U-linebalancing problem. European Journal of Operational Research, 171, 577585.16 Gutjahr, A. L., & Nemhauser, G. L. (1964). An algorithm for the line balancingproblem. Management Science, 11(2), 308315.17 Hackman, S. T., Magazine, M. J., & Wee, T. S. (1989). Fast, effective algorithms forassembly line balancing problems. Journal of Operational Research, 37(6),916924.18 Helgeson, W. R., & Bimie, D. D. (1961