文摘
双边装配线广泛应用于大型产品制造业,特别是汽车装配生产。平衡生产线装配过程规划和装配生产具有重要意义。在这项研究中,我们发展一个小说和确切的方法来优化分区的双边装配线平衡问题的约束(TALBz)的目标是最小化mated-stations考虑任务的数量限制。一个混合整数规划模型是用来描述TALBz问题。加强计算效率,我们应用Dantzig-Wolfe分解就是将TALBz问题。我们进一步提出一个branch-and-price (bp)算法相结合的列生成的方法和框架。两个基准数据集与分区没有分区的约束,约束和评价bp算法的性能进行了测试。数值结果表明,我们建议的方法在大多数情况下可以有效地获得最优解。此外,在真实数据集的实验来自客运车辆组装线。提出了bp算法显示其优势在解决实际问题和任务限制。 This developed methodology therefore provides insight for solving large-scale TALBz problems in practice.
1。介绍
在最后的生产工艺在汽车制造、零部件安装在画体在装配车间。组装生产乘用车工厂非常劳动密集型,有超过一半的劳动力分配在流水线上。在汽车工业,装配线平衡(铝青铜)问题涉及寻找最优装配任务分配给工作站给定优先级约束根据预定义的单一或多目标的目标1]。基于工作站的结构,铝青铜问题可以分为简单的装配线平衡(SALB)问题和双边装配线平衡问题(TALB)。在简单的组装线,有一个工人工作在每个工作站。这种模式很常见在预装配行汽车零部件生产。相比之下,工人可以安排的左右双边装配线工作站。工作站与左、右位置被称为mated-stations,构造最部分在主生产线。工人安装部分位于一侧的车辆在相应的位置。空间两边的组装线可以有效地用于存储材料和零部件。步行花部分时间减少双边装配线。然而,TALB问题的复杂性大大增加比SALB问题。 In the TALB problem, tasks can be operated on both sides of a mated-station. The positional characteristic of the task and work station results in more variables in the TALB problem model. For different objective functions, the TALB problem can also be classified into the TALB type-I (TALB-I) problem and the TALB type-II (TALB-II) problem. The TALB-I problem minimizes the number of workstations under a given cycle time, while in the TALB-II problem, the objective is to obtain a minimum cycle time for the assembly line with a fixed length.
在实践中,存在分配限制相关装配过程的特点,分配的工具,和生产资源。这些任务限制的一种限制的任务也称为分区约束(2]。分区约束定义哪些任务必须在同一工作站和执行哪些任务必须分配给不同的工作站3]。前情况是经常发现在工作站的工具共享的不同的任务。流程、设备或质量要求也可能定义作业的这个限制。另一方面,禁止一些任务分配到同一个工作站。区域约束i型双边装配线平衡(TALBz-I)问题是研究工作mated-stations的数量降到最低。
SALB问题是一个演示了np难的问题。考虑到额外的顺序和位置参数和带约束,TALBz问题比SALB更难最佳解决问题。由于这些限制,TALBz问题是一种独特的混合整数规划问题。列生成方法证明有效解决大规模整数规划。然而,最好的作者的知识,迄今为止没有一项研究报道的发展解决TALBz问题列生成方法。因此,提出branch-and-price算法引出了数学模型,设计了列生成过程,和发展的分支策略TALBz问题。
本文的其余部分说明如下:在部分2,作者提到基于方法的文献综述,TALB的约束和特征问题。节3TALBz-I问题的数学模型和原始模型的dw分解。再形成的TALBz-I问题是构建通过主问题和子问题。节4的总体结构branch-and-price算法是首次提出的。最初的解决方案生成和分支的细节计划也在这一节中描述。节5最常用的基准数据集,以及四个新数据集从真正的生产线,这发生在一个超级品牌汽车的装配车间,进行测试。结果与原模型和比较先进的算法。总结了部分6。
2。文献综述
装配线平衡问题已被许多研究人员广泛研究,综述的Erel和沙林4),肖勒和贝克尔5,两et al。6]。由于其利用大型产品制造业,特别是汽车装配、双边装配线成为关键要素的结构组装生产系统。TALB问题取得了重要的研究在过去的二十年7]。方法来解决TALB问题可以分为三个主要方法:精确算法、启发式算法和metaheuristics。巴尔托迪(8)首次引入TALB问题,设计了一个启发式算法基于“首先满足”的规则。TALB问题定义的一般结构。此外,他捐了148 -任务的测试数据问题真正的装配线。李等人。9)设计了一个启发式程序TALB问题和考虑的工作关系和工作懈怠的决策标准。TALB启发式规则的问题被讨论,和两个问题(65 -任务和205 -)从卡车生产线提出了实验结果。胡锦涛et al。(10)提出了一个启发式算法基于station-oriented TALB点数的分配流程问题。他们的测试进行小型问题(P9 P24)。吴et al。11)提出了一个和算法来最小化装配线的总长度和开站的数量TALB问题的目的。胡锦涛et al。(12)继续开发和算法集成工作新的下界,优势规则,和减少TALB-I规范问题。Sepahi和Naini13)提出了一种新的启发式算法TALB问题,允许并行任务的性能。李和屁股14]提出的新的优先级规则TALB问题。米歇尔et al。15)应用弯管机的分解来解决multimanned装配线平衡问题。这些确切的出版,启发式方法是有效的只有在中等规模的情况下,由于计算要求和内存需求成倍增长对于大规模问题[4]。Ozcan和Toklu16)提出了一个精确解的方法,即目标规划,解决小型分区约束线平衡问题。李、Kucukkoc,张(17霍夫曼)开发新的精确方法应用启发式和分支记住(BB&R)算法,最小化的mated-stations TALB问题。新的统治规则、下界和小说的任务枚举过程设计的研究。提出BB&R算法取得了更好的解决方案比当前最好的启发式算法。
各种metaheuristic算法已经应用于解决TALB问题。遗传算法应用于解决铝青铜的问题,一些研究人员(18- - - - - -20.]。Baykasoglu和Dereli21)提出了一个蚂蚁colony-based和组分配启发式算法解决TALB与区划约束问题。Simaria et al。22)开发了一个名为2-ANTBAL的蚁群算法来解决TALB问题最优。建立了数学规划模型,其主要目标是最小化工作站的数量。提出了一种模拟退火算法由Ozcan Toklu [23)解决混合模式双边装配线平衡问题。一个新的混合整数规划模型,它包含一些特定的附加约束分区等约束,给出了位置约束和同步约束。Ozcan [24]研究了TALB问题随机任务。模拟退火算法被选为的方法解决问题,这是机会约束模型,分段线性混合整数规划。蜜蜂算法解决TALBz问题通过Ozbakır和Tapkan3]。Tapkan et al。25]也蜜蜂算法和人工蜂群算法应用于解决TALB问题,这是完全约束。
Tapkana et al。26]研究了TALB问题考虑步行时间在平行线和蜜蜂算法和人工蜂群算法开发。唐et al。27)提出了一种改进的离散人工蜂群(DABC)算法来解决二型TALB问题。该方法发现22个全新的大型问题的结果和表现优于其他九个metaheuristic算法实验。李等人。28]说明一个新的本地搜索方法叫做迭代贪婪(IG)方法解决i型TALB问题基于任务排列的编码方案。一些近期作品研究TALB问题与特定的线路配置或额外的约束,如地下工作站(29日,机器人工作站30.),现实世界的约束(31日),工人作业(32)、空间和资源的限制(33),不同的或不确定的任务时间34[],multiworker工作站35]。尽管metaheuristic算法已经广泛使用,一些缺点依然存在。从随机搜索的解决方案所得,metaheuristic算法产生不确定的结果。此外,metaheuristics需要额外培训指定合适的参数,这是浪费时间和不确定性14]。
3所示。TALBz-I问题的描述和建模
双边装配线,在图所示1,可以表示关键结构的主要生产线。汽车零部件交付材料区域线一侧并安装在中间车根据装配序列。工人可以执行安装操作在两个工作站的左右位置。TALB问题中出现的一些基本概念首次引入,以更好地了解组装生产过程:(我)周期时间:周期是由生产流水线的速度。它定义了汽车多长时间可以呆在一个工作站上安装。(2)空闲时间:除了组装业务在一个周期时间,业余时间,没有发生任何活动称为空闲时间。(3)Mated-station:双边装配线,工作站和两个面临称为Mated-station位置。(iv)优先关系:组装过程必须满足产品的结构关系。给出了装配序列的约束线平衡设计。它定义了哪个任务之前必须完成一个任务就可以开始了。(v)前任:引用之前必须执行任务,任务被称为后者的前任。(vi)继承人:任务,按照任务的引用顺序图被称为后者的继任者。(七)与任务:这些任务必须分配到同一个工作站由于分区限制。(八)不相容任务:这些任务不能分配给相同的工作站由于分区限制。
3.1。问题描述
给一个固定的周期时间,i型TALB问题寻求一条线平衡的结果,具有mated-stations的最小数量。这个值将会决定生产线的长度。数据2和3说明16 TALB问题任务的一个例子来自李的研究等。9]。图2介绍了顺序图。标签的任务由数字显示箭头连接序列任务之间的关系。例如,任务4和5 7开始之前必须完成任务。括号中的第一个值等于任务的运行时间,在括号中的第二项代表的位置信息的任务。l意味着必须完成的任务在mated-station左边位置,而任务标签R属于正确的位置。e任务可以被分配到左边或右边的位置。
在一个简单的组装线,任务分配在工作站上是连续的。一名工人的空闲时间可能只发生在他或她完成的所有操作在一个周期的结束。能力约束要求任务的操作时间的总和小于SALB周期时间的问题。然而,这是不够的在TALB问题。任务分配必须考虑双方关系的任务序列TALB mated-stations和位置约束的问题。连续工作计划可以打断了序列约束之间的任务分配给mated-station相反的头寸。操作员可以等待工作的补充在相反的位置。这种类型的等待时间称为sequence-induced空闲时间,SALB并不存在的问题。图3上面描述的线平衡解决方案16个任务情况下周期20个时间单位。例如,在转让mated-station 2,任务后10必须在正确的位置和任务7。因此,有一个空闲时间16单位任务前10。分区限制通常是根据装配过程的要求建立部队或禁止的分配不同的任务相同的工作站。应该满足这些约束线平衡的结果除了周期时间和优先约束。
3.2。TALBz-I问题的数学模型
为了缓解表示,在模型中出现的符号给出如下:指数:我,h, p:任务数量j,克:mated-stationk:一边的生产线参数:我:设置的任务J:组mated-stationsK(我):设置可用的位置的任务我P0没有前任:设置的任务P(我):设置前任的任务我P一个(我):组总任务之前的任务我年代一个(我):总任务,按照任务的设置我年代l/秒R:下界的左/右工作站的数量TSumL / R / E:笔的操作时间设置的左/右/位置的任务Xj:赋值j一个mated-station在给定的解集B:设置主作业的问题ct / ct:周期时间t我:任务的操作时间我μ:乘法器为大米π:双变量的值变量:xijk:如果任务我被分配到另一边k的站j= 1;否则,= 0Nj:如果站j打开组装生产,= 1;否则,= 0 :完成的任务我。z知识产权:指示符变量来表示任务的装配序列我和p。λj:如果任务j是包含在解决方案,= 1;否则,= 0。y我:如果列j在解决方案中选择,= 1;否则,= 0。 :如果任务我在赋值= 1;否则,= 0年代本土知识:如果任务我是拍摄的k在赋值= 1;否则,= 0
我们建立的数学模型i型TALBz问题提出的基于模型的金正日et al。20.]。他们研究了二型TALB问题,他们的目标是最小化给定一个固定数量的mated-stations周期时间。我们的模型的目标是最小化装配线的长度,等于mated-stations数量的最小化。我们用0 - 1变量Nj代表一个车站j使用。
受
三种类型的(即TALB的共同约束问题。,occurrence constraints, precedence constraints, and cycle time constraints) and extended zoning constraints are included in the type-I TALBz model. Constraint set (2)描述发生的类型约束,确保每个任务分配一个且只有一个。约束集(3)- (6)定义序列约束TALB问题。约束集(3)限制不同mated-stations之间的序列关系的任务,而且还可以应用于SALB问题;也就是说,任务不能分配给前者站在他们的前辈。约束集(4)应用于任务的优先级关系和分配给mated-station相同。由于sequence-induced TALB空闲时间的问题,必须确定装配顺序的任务分配给同一车站。我们引入的变量定义任务的完成时间我。前辈之前必须完成他们的参考任务开始时做在同一个mated-station。任务没有优先关系和出现在相同的工作站,约束集(5)和(6)变得活跃。z知识产权是设置为一个0 - 1变量的指标变量。当z知识产权= 1的任务我之前安排的任务p、约束集(6)是有效的;当任务p之前计划任务我,z知识产权= 0和约束集(5)变得活跃。约束集(7)是周期时间约束的集合。一个任务的完成时间不能大于周期时间,超过了任务的操作时间。| |Wj| |代表作品的数量分配到车站j。曾经有一个任务我分配到工作站j在一边k,变量的值xijk是1;然后,站j算作开放电台的总数,和价值的Nj= 1。另外,分区约束集(9)和(10)描述任务的限制的关系。任务(我,j),属于相关任务(LT),他们必须分配到同一个mated-station (9)。与此同时,约束集(10)保证任务(我,j)定义不相容任务在不同mated-stations (IT)设置完成。
3.3。分解的混合整数规划模型
实现branch-and-price算法的关键是使用dw原始问题分解。它是一种标准方法来获得线性规划模型用于主列生成方法的问题。
Appelgren [36]第一dw分解应用于解决一个整数programming-based船调度问题。解决部分解决方案,Appelgren [37)通过了一项和搜索树寻求基于dw的整数解分解。Lubbecke和Desrosiers38]列生成评价提供方法和理论的细节讨论Dantzig-Wolfe分解和整数规划列生成算法。在数学模型中引入前部分,决策变量将任务分配给不同的车站。我们应用dw分解的原始模型TALBz问题和现在再形成的原始模型。这个方法是用来确定哪些解决方案采用赋值设置在dw mated-station分解。
受
给定一组线平衡的解决方案X,决策变量λj意味着,如果作业j选择在最后的解决方案呢 ;否则,当作业j不包括在解决方案, 。目标函数是获取mated-stations的最小数量。约束集(15)是发生约束从(2)。约束集(16)描述序列约束的任务分配给不同的mated-stations,构造成(3)在原始模型。对于分布在同一个工作站的任务,约束集(17)- (19)确保装配序列可以满足优先级图。使用这些约束可以称为(4)- (6)在前模型。约束集(17)和约束集(18)和(19)是有效的任务,没有优先关系,分别。指标变量z知识产权还利用序列中的约束集(18)和(19)Dantzig-Wolfe分解模型。任务的完成时间的决策变量是相同的原始模型。周期时间约束(20.)也保持不变(7)。约束集(21)和(22)定义分区约束(9)和(10)成立于原始模型。
3.4。主问题和价格再形成的子问题
Dantzig-Wolfe模型的分解,每一列构成任务分配一个工作站。后可能有一个巨大的数量的分配相关工作站,这不是可行的枚举所有的任务模型的解决方案。因此,我们开发一个列生成方法来解决来自Dantzig-Wolfe分解的重构模型。
吉尔摩和Gomory第一列生成法用于解决下料问题[39,40]。本包装和削减股票问题成为一个经典的申请列生成方法,所研究的万斯等。41),陈等人。42],Vanderbeck [43]。Degraeve et al。44)内嵌列生成过程和框架下料问题。彼得斯和Degraeve45)提出了列生成算法来计算i型SALB问题的下界。列生成已被证明是最成功的方法解决大规模整数规划,尤其是对问题包含一个巨大的数量的列在其数学模型。而不是显式地列举所有列,列生成法解决了这个问题通过将列只在需要时为基础。列生成的主要优势是,最初的问题是制定主问题,只有有一组选定的列和子问题。因此,主问题被定义为限制主问题(RMP)。
列生成过程的重构模型,迭代解决RMP和定价问题。在列生成简单的想法并不代表所有变量(列)明确;它使用一个相当小的子集列。类似于寻找新的基本变量的单纯形算法,列生成处理添加列到主问题。一列最消极的降低成本添加到主问题解决后的定价问题。
TALBz RMP模型问题
受
目标是最小化的总和mated-stations表示为y我在(25)。设置变量决定的值列赋值设置和放松为连续变量。我们继续任务发生约束集(26主问题。)的集合Bij包括任务分配在不同的电台。在这个集合中每一列代表一个模式,一个mated-station任务的解决方案。
列生成是单纯形算法的扩展。RMP只包含一小部分可能列在一开始,然后其他列是由解决定价子问题。在每个迭代中列生成的一个列的任务分配最消极的降低成本是附加到解集BijRMP。从降低成本(钢筋混凝土)可以计算 在哪里是新分配方案和任务变量π代表了双重成本向量,由RMP的双变量。我们可以设计定价子问题寻求最低钢筋混凝土。
子问题是获得一个分配的解决方案给当前RMP的双变量的列表。子问题的目标源于(28)显示在(29日),最低的地方钢筋混凝土等于产品的最大数目的变量和π。
约束可以分为五个模块:位置分配约束(30.),序列(在不同站)约束(31日)、序列(在一个站)约束(32)- (34)和周期时间约束(35),和分区的限制(36)- (37)。
子问题的解决方案是一个mated-station任务分配。因为有两个位置在一个mated-station,决策变量年代本土知识建立了以确定哪一方(k=向左或向右)的任务我是分布式的。如果任务我站在任何一边的分配,那么这个变量是记录为' 1 '元素的解决方案;否则,它等于“0”。这种关系表现在约束(30.)。约束集(31日)确保任务的优先级序列在不同的电台。在原始模型中,这些都是意识到通过约束集(3)。我们新配方这个约束到nonredundant约束集(31日)。减少了尺寸后,相比它更简洁的表达式。约束(31日)可以防止这种情况的发生:前任和接班人的任务我选择的解决方案,但任务我不出现在任务。这种情况下将违反序列不同mated-stations之间的约束。约束(32)继承自(17),它定义了任务分配的优先级关系mated-stations相同。任务没有任何优先顺序要求,约束集(33)和(34)成为活跃的两个任务在一个mate-station发生在相同的位置。指标变量z知识产权创建控制的出现顺序两个任务:当任务我是之前的任务p,z知识产权= 1,如果顺序颠倒,z知识产权是0。周期时间约束(35)作为约束集(20.在dw分解模型。约束集(36)和(37)代表分区的约束。任务的集合LT必须安装在同一工作站所保证的约束(36),而任务的集合必须聚集在不同的工作站约束(限制37)。
4所示。提出Branch-and-Price算法
4.1。列生成的一般过程
branch-and-price算法通常是集成的框架和方法。我们列生成法适用于解决问题的线性模型TALB branch-and-price搜索树中的每个节点。
我们从branch-and-price树的根节点开始。TALB问题是首先通过最初的启发式算法来解决。基于此解决方案,branch-and-price算法可以进入分支节点计算阶段。列生成法设计的分支节点计算的部分。RMP来源于初始解的启发式算法。然后,TALBz问题已经解决了通过迭代计算RMP和子问题之间的关系。RMP的双值可以利用目标函数作为参数(29日)子问题模型。子问题解决后获得一组最优RMP的双重价值。新列,它代表一个工作站的线平衡解决方案,添加到RMP如果其降低成本值是负的,因为一个列与一个可以提高RMP -降低成本价值。
列生成迭代停止当RMP的价值并不比下界。两个条件表明,列生成的子问题不能改善RMP了,和列生成循环优惠:(1)如果降低成本的价值从当前的子问题是负的,没有更好的解决方案可能是通过进一步的迭代计算。(2)当降低成本是负的,其绝对星等太小,RMP不能达到一个更好的结果,即使吸收新列。这是因为线平衡问题的最终解决方案包含一个整数数量的工作站。改进RMP的围捕价值等于解决方案在降低成本时的电流环位于⌈范围内ZB⌉=⌈ZB/ (1−钢筋混凝土)⌉。
当列生成完成在一个活跃的节点,一个整数评估RMP模式的检查结果。如果RMP解决方案满足整数条件和比最好的价值,我们与这个解决方案更新当前的最佳值,理解活动节点。最新的更新值比下界。如果它等于下限的值,那么该算法休息并返回这个结果作为最优值。如果RMP提供分级结果,选择了不同的情况下:(我)部分节点我在哪里Z我>Z最好的−1,节点我对边界的堂哥。(2)部分节点j在哪里Zj≤Z最好的−1,分支发生在节点计算过程中产生的结果。新子节点生成活动节点的结果。
搜索树是由节点没有解决。然后,算法选择和进入branch-and-price搜索树中的下一个节点。这个过程一直持续到搜索树中的所有节点检测到或调用终止条件计算。
下界和上界在branch-and-price算法也扮演重要角色。在该算法中,mated-stations数的下界磅纳米计算(41)- (44),这是作为下界1从吴et al。11)和初始上限设置为启发式的解决方案的价值获得根节点。
通过降低成本价值,除了测量节点计算时将停止其解决方案满足了下界。更新上限根据最新的整数解。算法不断缩小之间的差距下界和上界,直到搜索完成。因此,一个高质量的初始上限可以促进解决过程。虽然SALB启发式方法和TALB问题进行了研究,这些方法不能直接应用于branch-and-price算法,从最初的解决方案必须满足branch-and-price Ryan-Foster分支规则实现的算法。因此,我们设计一个新颖的启发式程序获得这种类型的解决方案基于“最早开始时间”的优先级规则。
4.2。最早开始时间计算
在我们的研究中,一个初始TALBz问题的解决方案需要列在branch-and-price树中的每个节点生成过程。顺序和位置约束影响TALBz问题的最终结果。最小化空闲时间序列约束和引发的双边装配线方向约束,一个策略是不断安排任务分配。因此,任务建议尽早开始。枚举过程中,一个任务可以开始如果所有的前辈已经完成。一个任务的完成时间可以通过时间来计算传递函数:
一组“未赋值的任务”创建的启发式算法。这组包括任务没有分配给工作站。启发式过程还创建了一个“池“设置包含项目”未赋值的任务”之前设置的任务完成。当有任何的前任j为任务我在当前mated-station,完成的时间j等于它的启动时间+任务j的操作时间(45)。如果前任j没有出现在当前mated-station,其结束时间设置为零。然后,任务的最早开始时间在当前站可以由其前任的完成时间。的任务,固定位置(左或右)属性:
最早开始时间(美国东部时间)选择最大值在前任的完成时间和当前时间能力的一个位置(取决于哪一方的任务是允许执行)。
任务可以完成在生产线的左右,最早开始时间计算
由于任务没有位置偏好灵活转让双方的车站,我们喜欢的位置提供了一个早期的开始时间。因此,任务的最早开始时间我,美国东部时间我的中值,选择三个参数:(1)的最大完成时间的任务我的前辈,被分配在同一个mated-station;(2)左位置和右位置的最小容量;和(3)的最大容量左位置和右位置。
一旦我们完成一个任务,这个任务的开始时间和结束时间将被更新。只是分配任务从“池”和“未赋值的“集,和新任务添加到“池”根据他们的前辈们的地位。
4.3。启发式规则
基于传递函数和方法最早开始时间计算,我们开发mated-station-oriented TALBz问题的启发式算法。mated-station的双方同时检查来确定当前的最佳分配。一些规则是这里讨论最小化总空闲时间:(我)前辈的任务已经完成了,我们选择任务的最早开始时间的最小值。这可以减少sequence-induced任务之间的空闲时间。(2)如果有相同的任务开始时间、任务与一个固定的位置属性(左或右)提议给优先级大于E类型的任务。(3)如果并行任务仍然存在,任务运行时间最长的是更可取的。这可能增加当前工作站的利用率。
为候选人任务组”池,”测试解决方案的可行性。SALB问题,任务导向的启发式算法只检查周期时间的解决方案的能力。然而,最初的解决方案不仅在根节点,还需要在branch-and-price分支节点的算法。由于Ryan-Foster分支规则用于这项工作,我们遵循分支约束的过程中生成初步的解决方案。根据分区和分支的限制,一些任务应该分配给相同的工作站和一些不同的工作站。创建可能的分配不同的任务,有的可能修剪如果约束违反。一般来说,两个条件存在时的解决方案可以修剪。
第一个条件是,最后一个完成任务的时间超过了周期时间。
在(48),融通我设置任务的最后完成时间G我,任务我属于“池”集。作业的启发式程序考虑分支约束。的任务我一对相关的任务,我们搜索所有未赋值的任务,必须在同一个mated-station;这些任务的集合称为集团”G我”的任务分配。任务组的集合包括候选人的任务,其相关任务,和所有的前辈候选人尚未分配的任务。的过程将搜索所有有关项目的任务和前辈。组相关更新新任务添加到这个集合以迭代的方式,直到所有都包含在这一组相关的任务。然后,同时这些任务被分配在一个解决方案。我们在解决方案和完成时间最长的记录与周期时间进行比较。解决方案的最终完成时间超过周期时间修剪。
第二个条件限制的解决方案包含在一个mated-station可加以反驳的任务。我们需要检查是否以下两个病例发生在解决方案:(一)可能的任务分配,候选人的任务或分组任务,有矛盾的任务已经分配给当前mated-station。 任务我是候选人任务池中,G我群的任务吗我这应该被打包在一起。Cj表示一组的任务是不相容的项目任务j不能分配给相同的工作站。这些任务是根据定义的分区和分支约束。当任务p在Cj已经被分配,变量的值= 1。(b)的分组任务包含不相容任务对任务。 一组SCij由组中自相矛盾的物品组的任务我在游泳池里。随着节点数量的增加,分支约束变得复杂。因此,一些链接和不相容任务对可能相同的分组设置。没有任何可行的结果,因为矛盾的需求。作业设计必须修剪违反这些约束。
4.4。初始解代
启发式的关键步骤在启发式算法1。
|
||||||||||||||||||||||||||||||||||||||||||||||
4.5。分支计划
由于RMP Dantzig-Wolfe分解的线性松弛模型,部分的解决方案可能出现在最优的解决方案。然而,一个整数的结果是需要满足实际生产的要求。在处理线性规划问题的常用方法,使用和方法得到整数解。有效的分支基于分数与整数变量会导致子节点的解决方案。在这个提议branch-and-price方法,branch-and-price参数和算法结合了列生成。理论原则被阴了et al。46)采用这个方法来解决SALB问题。
分支的常见的方法处理部分变量和方法。部分变量是围捕/原始模型添加额外的约束。然而,这种方法并不在branch-and-price算法工作。变量对应列线平衡结果的集合构成了RMP的解决方案。除了最初的部分源于启发式算法,其他列生成的定价子问题。因为RMP模型中的约束不能控制定价子问题,列中根除RMP可能再次返回后列生成的过程。此外,添加新的约束模型的主问题将改变其对偶问题。因此,我们设计一个新的分支策略TALBz问题基于Ryan-Foster分支规则。在这个工作中,分支约束实现定价代替RMP的子问题。
在确定一对任务的部分解决方案,两个子节点都建立在左分支和分支。以下约束添加到子问题模型(29日)- (40在不同的节点)。在左边的分支节点,
在左边的分支、约束要求任务{l, m}在左边的分支l被分配在一起,mated-station之一。要么== 1,这意味着任务l和米包含在作业,还是== 0,这意味着当前的解决方案不包含l或米。
在正确的分支节点,
在正确的分支,约束要求任务的{l, m}在正确的分支R被分发到不同的mated-stations。因此,作业的mated-station可能只包含一个任务(= 0,= 1或= 1,{= 0),或者没有一个任务l, m}出现在当前mated-station (== 0)。
基于上述方法,分支约束集(51)和(52)可以与分区约束集(36)和(37),出现在子问题模型,其中包含任务之间的限制。我们的方法有更多的优势比其他方法,在处理这类问题采用原始模型。然而,分区约束集(36)和(37在bp算法做限制这些关系的任务。因此,他们可以直接应用于定义分支约束而不是添加额外的表达式。
5。计算实验
三个类别的数值实验。在第一部分中,基准数据集的分区约束测试来评估TALBz提出了bp算法的问题。在第二部分,基准的问题没有任何分区约束是决心做个比较TALB最近研究的问题。在第三部分,四个新数据集的实际生产线,这发生在一个超级品牌汽车的装配车间,进行测试来验证实际问题的bp算法的有效性。该bp在Python 3编码。一个接口的Gurobi7.5.2解决构建算法。的计算机进行的实验是有一个英特尔酷睿(TM) i7 - 3770 3.4 GHz CPU和8 GB RAM内存。
5.1。基准实例分区的约束
六个基准问题,源自文献,研究这部分。这些实例可以分为小型问题,P12-P16-P24,和大型的问题:P65-P148-P205。P12和P24问题进行了研究,参照[18]。数据问题P16、P65 P205取自[9]。P148包含148个任务,首先是由巴尔托迪(8]。我们修改的价值任务79从281年到111年和108年从282年根据李et al。(439]。这些实例列在表的分区的约束1取自Baykasoglu和Dereli21)和Ozcan Toklu。(16]。
计算结果如表所示2。的性能标准的数量mated-stations (NMs)是用来评估算法。有一些研究考虑到分区双边装配线平衡问题的约束。提出了bp的结果进行了比较与那些最好的研究报道。蚁群(AC) Baykasoglu和Dereli [21),目标规划(GP) Ozcan和Toklu16),和蜜蜂算法(BA) Ozbakır和Tapkan [3)获得最佳解决方案的标准工作站的数量。但是,这些发表的结果不能用于直接比较,因为他们的目标是最小化工作站的数量。同等数量的mated-stations发表结果计算的比较。工作站的数量在公布结果,并除以2。相当于mated-stations数等于这个值。如果它不是一个整数值,那么圆。工作站的平均数量是取自Ozbakır和Tapkan3];最小数量的工作站是取自Baykasoglu和Dereli21]和Ozcan Toklu [16]。此外,原始模型(1-13)测试使用Gurobi解算器比较了bp算法模型新配方的。
测试进行了在不同周期(CTs)。“最低mated-stations计算”的价值(CMS)直接使用求和的计算任务的操作时间除以CT的双重价值,CMS =T总和/ (2CT)。这个值可以测量之间的松弛时间理论最小数量的mated-stations和下界(磅)。下界mated-station的数量相当于价值(11]。我们设定一个时间限制300年代的计算。当程序的运行时间超过这个极限,算法终止并返回当前的最佳解决方案。实例测试或通过一个算法来解决与“-”标记的结果表2并在以后的结果。拟议中的bp获得最好的解决方案在27个32位实例考虑分区的限制。最初的模型是有效的小型问题(P12, P16, P24),和大型无法解决的问题Gurobi解决的期限内。医生只测试小型问题P12, P16和P24。英航优于其他算法的研究报道。5日英航生成更好的解决方案实例与bp算法相比。拟议的市净率和生成3比交流更好的解决方案。然而,这些结果不能严格评估算法的性能。这主要是因为以下:首先,mated-stations的真实数量可能超过相当于在这项研究中使用的值,当有些mated-stations只有单面上的任务分配工作站。第二,尽管工作站的平均数量为每个实例,结果生成的AC和英航的不确定性和变化的值计算。
5.2。基准实例没有分区的约束
为了使比较的最近的研究一般TALB问题,基准问题测试没有任何分区的约束。结果如表所示3。该方法相比,小组作业的启发式算法(GA)的李et al。9),和吴et al (B&B)算法。11),Ozcan的禁忌搜索(TS)算法和Toklu [47),修改的报告最好metaheuristic模拟退火算法(mSA) Khorasanian et al。48一定记住,最先进的分支(BB&R)算法的李z . et al。17]。此外,原始模型(OM)和删除分区约束集(9)和(10)是解决使用Gurobi解决bp算法评估新配方模型。
bp算法在25个32位实例取得了最好的解决方案。该算法是非常有效的和有效的小规模的问题。P12的所有测试、P16和P24达到最优结果。七个大型问题的情况下,P65 326 (CT), P148 204 (CT),和P205 (CT 1322、1510、1699、2077、2454)返回最终结果有一个单位与最好的解决方案的价值。李等人。9]显示P65的计算结果,P148, P205实例。bp在9实例找到更好的解决方案比GA mated-stations的数量。吴et al。11测试P12, P16, P24、P65和P148在他们的研究中,B&B算法优于bp算法在只有一个实例的P148 204 (CT)。bp算法也得到解决方案mated-stations少于7的TS算法实例。结果给出的mSA和四个比bp在P148和P205更好的解决方案。BB&R是一种有效和高效的方法TALB问题,它产生七比净率和更好的结果。最初的模型仍然是有效地解决小规模问题(P12, P16, P24),它几乎无法获得大规模问题的可行解(P65, P148 P205)。
关于运行时间,我们列出原始模型的计算时间(OM Gurobi)和提出了bp算法。CPU时间的B&B P12-P148解决在0.001和68.125之间(s在奔腾4 2.0 GHz PC (11]。TS算法的CPU时间之间0.06和2100年代在奔腾4 3.0 GHz PC (47]。mSA算法的计算时间小于5秒对于每个问题情况的英特尔酷睿2双核T9600 PC 2.8 GHz CPU (48]。BB&R方法找到最佳的解决方案,所有测试实例平均在1.0年代的英特尔酷睿(TM) i7 - 4790 3.2 GHZ CPU电脑。由于巨大的差异这些算法的计算机,编程编译器和运行系统,很难准确区分算法根据报告结果的性能。然而,很明显,对小型快速bp算法获得最优解的问题。P12的所有实例,P16, P24和P65在20秒内优化解决。P148的大规模问题和P205 8的16实例获得最优结果在不到20秒。
5.3。实际生产情况下
接下来,四个新问题,P56, P58 P81, P161,是来源于实际生产情况下在宝马大会商店,进行测试。问题P56, P58 P81拍摄从一个动力总成系统华晨宝马工厂流水线大公国际,包含56个,58岁的分别和81任务。P56安装的总操作时间,P58,和P81是889.46秒,731.28,和1006.96 s,分别。这三个病例发生在三个不同的部分在动力总成装配线。这个动力系统是安装在预装配区域循环时间为101秒。产量(公关)的动力部分是每小时33台。问题P161由161底部组件装配任务显示在华晨宝马铁西工厂。大多数的底部部分安装在倾斜线,如图所示4。倾斜线是一个关键的一部分,主要生产线,它是在双边模式。使用倾斜行提高了人体工程学的装配生产。主要部分安装在倾斜线包括利用、刹车线、燃料供给系统、屋顶天线,无数插头在车辆的身体。操作的工作过程由1615.82秒。为了简化线平衡问题,一些连续操作结合为一个任务根据标准引用的指令。例如,油箱总成的准备包括三个主要过程:燃料任务扫描(操作时间10.26 s),胶垫结合(操作时间15.66 s)和油箱安装(操作时间10.15秒)。这三个过程是不断在实践和综合任务执行132年P161(操作时间36.00 s)问题。最后,161年P161问题任务数。这些作品完成由38个工人在19岁mate-stations在当前生产线我们研究。 The current公关主要装配线的宝马铁西工厂每小时60单位汽车周期时间为55.38秒。分区限制参与实际生产问题,和相关任务对(LT)和不相容任务对(IT)被设计为每个问题。
使用bp算法优化后,mated-stations数量减少了对所有病例相比,在之前的生产计划。中型P56和P58问题,纳米达到下界。大型问题P81, CMS的价值几乎等于下限;我们用六mated-stations获得当前的最佳解决方案。P161问题,mated-stations的数量减少到15。这个值也等于下限。因为这些实例TALBz的新数据集的问题,我们测试的原始模型(OM)这些问题通过Gurobi解算器比较他们的表演。优化结果如表所示4。
来测试我们的方法更实际的情况下,我们设置不同的周期长度的实验。实例是延长的情况下当产量(公关)增加。经过的时间Tp汽车在每个站的计算
的推荐CT组装生产的范围(0.92∼0.95)Tp。问题P56, P58 P81涉及动力系统总成,我们集公关到34∼42(34,36岁,38岁,40岁,42)单位。周期时间是0.94Tp,其范围从80.57到99.53年代。P161问题,我们确定的周期时间是0.94Tp随着公关电梯从61年到69年(61、63、65、67、69)单位每小时。因此,周期时间从54.48到49.04年代。表4总结了计算结果。
提出了,Gurobi可以处理中等TALBz问题。然而,Gurobi无法解决任何情况下P161问题在300年代或计算完成时返回一个最佳解决方案的候补方案。bp算法提供15 24例比更好的解决方案Gurobi解算器。bp算法给出的结果等于24例的下界21。这些实例优化解决。三个案例(P56-CT89.05 P81-CT101和P161-CT50.51)获得了一个单位的最终解决方案与下界的差距。这些情况下,他们的CMS值等于下限这意味着没有松弛时间。这就解释了为什么下界是很难达到的。更少的情况下被解决了最优Gurobi处理分区的TALB问题约束。这些额外的限制导致了更高的复杂性。然而,bp算法仍然可以返回最优解在大多数情况下,在很短的时间。总结,提出bp算法是有效解决TALBz问题,虽然Gurobi不是竞争。bp算法明显优于Gurobi采用原始模型的所有情况下的计算时间。
从上面的测试结果的所有实例branch-and-price算法的性能受到几个因素的影响。(1)问题的规模大小:为小型和中型问题(P12, P16, P24、P56 P58,和P65),该算法给出了几乎所有情况下的最佳解决方案。本程序的小型和中型的问题相对较短:40 44例在15秒内优化解决。随着规模的发展,复杂性增加,导致更长的运行时间(从0.811到318.713 s)对大规模问题(P81, P148、P161 P205)。很难达到最优结果大型问题;44例31 (P81, P148、P161 P205)获得最佳的解决方案。(2)松弛时间:松弛时间是小当CMS在下界。这取决于不同的周期和不同情况下的下界。虽然CMS不计算严格下界的价值,它可以测量达到下界的可能性,因为不可避免的sequence-induced TALB空闲时间的问题。松弛时间越小,就越难达到最优解的算法。 This limits the algorithm to obtain the optimal combination of solutions in a short amount of time.
6。总结
本研究使用列生成方法的有效性验证解决TALBz问题。一个bp算法处理TALBz问题第一次。发布的模型不能直接应用于实现一个列生成过程。因此,Dantzig-Wolfe原始模型的分解。模型的主问题和子问题是新配方。拟议的分支策略被证明是有效地获得一个整数解。从最初的解决方案是使用不仅在和树的根节点,还在分支节点,启发式程序能够生成可行的解决方案,在不同的节点按照约束。
这部小说精确算法显示了优于以前的具体方法和metaheuristic方法。解决方案过程比传统的算法更有效,特别是对大规模TALBz问题。不同于metaheuristic方法,列生成过程是基于确定性模型。的具体限制TALBz问题,如分区约束的任务,可以直接嵌入到数学模型。这种方法使得它可行的实现更实际的约束条件,如流程限制,资源限制,和线路配置的限制,在实际装配生产。一个汽车公司可以减少生产成本的基础上确定的TALBz问题的结果。
实验进行的32个实例一般TALB问题和56个实例附加任务的限制。该方法获得最优结果超过80%的情况下。虽然计算时间变得不再随着任务数量的增加,尤其是对实例松弛时间短,在大多数情况下取得了可喜的成果。bp算法具有更多的优势在解决现实问题,复杂的限制与其他方法相比。比较新配方的性能模型和原始模型表明,新模型更有效和高效的获得最优解(80.68% vs 39.77%)。中产阶级和大型问题的实际组装生产,bp方法表现Gurobi解算器。在大多数情况下,速度比bp算法可以生成最优解决方案Gurobi。
进一步的研究将将这种方法扩展到混合模式进行组装生产线,更复杂,但比单模常见装配线在汽车制造厂。另一个有趣的方向可以设计一个特定的算法来解决价格问题处理解决。设计一些启发式规则生成的列的算法可能会提高性能的bp算法实例松弛时间。
数据可用性
使用的数据集或分析在当前研究可从相应的作者以合理的要求。
的利益冲突
作者宣称没有利益冲突有关的出版。
确认
这项工作得到了中国国家重点研发项目(批准号2019 yfb1705002和2017 yfb0304100),中国国家自然科学基金(批准号51634002),辽宁振兴人才项目(批准号XLYC2002041)。