英语原文共 8 页
装配线平衡问题汽车电缆
Hager Triki1, Wafik Hachicha2, Ahmed Mellouli3, Faouzi Masmoudi4
1 Sfax大学，Sfax工程学院，ENIS，突尼斯;2 Sfax工业管理高等学院，突尼斯
3苏塞大学，苏塞工程学院，突尼斯ENISo
4突尼斯Sfax机械、建模与生产(La2MP)工程学院实验室研究
通讯作者:Hager Triki
斯法克斯大学
Sfax工程学院，ENIS, LA2MP:
机械建模和生产实验室研究BP 1173, 3038, Sfax，突尼斯
电话:( 216)97752848
电子邮件:海格Triki@yahoo.fr
收稿日期:2014年11月16日
接受时间:2015年1月11日本文提出了一个装配线平衡问题(ALBP)
汽车电缆制造公司。这家公司发现有必要平衡生产线，因为它需要提高生产率。在这个ALBP中，站点的数量是已知的，目标是最小化必须满足优先级和分区约束的循环时间。这个问题被表述为一个二元线性程序(BLP)。针对这一问题的np困难，提出了一种新的遗传算法。采用全因子设计获得了较好的组合遗传算法参数，并对停止准则进行了简单的收敛实验研究，以减少计算时间。将所提出的遗传算法结果与CPLEX软件进行比较，结果表明，在合理的时间内，遗传算法生成的解与最优解非常接近。因此，提出的遗传算法是非常有效和有竞争力的。
关键字：装配线平衡问题，遗传算法，循环时间，优先级和分区约束。
介绍
经典的简单装配线平衡问题(SALBP)[1]在过去的几年里得到了广泛的丰富，采用了许多现实的方法，并为缩小理论与工业实际之间的距离做出了很大的努力。SALBP的每一个扩展都可以很好地解决实际问题，解决任务[3]之间的不兼容性、空间约束[4]和资源分配[5]等复杂约束问题。
本文以跨国公司LEONI (http://www.leoni.com)为研究对象，对电机电缆的装配线平衡过程进行了研究提高生产率。本公司是一家全球性的电线、光纤、电缆和电缆系统供应商，并为主要应用于汽车行业的许多行业提供相关的开发服务。在这个行业中，SALBP的一个有趣的扩展重点是，考虑任务集之间的分区约束，因此不兼容的任务必须分配到不同的站点。例如，一些原材料(文件、管子等)可能彼此非常相似，以至于质量考虑和加工条件迫使某些对任务分配到不同的工位。在这种情况下，已知站的数目(m)，目标是尽量缩短循环时间。
管理和生产工程评审
必须满足任务之间的优先级和分区限制。因为所有版本的salbp都是NP-hard[6]，所以这个ALBP也是NP-hard。利用线性规划、整数规划、动态规划和分支定界法等精确求解ALBP的方法在文献中得到了广泛的应用。然而，这些方法只在小的实例中被证明是有效的。因此，启发式和禁忌搜索、模拟退火、遗传算法[14]等元启发式算法的发展成为众多研究者关注的焦点。所有启发式搜索方法的共同特点是智能地使用特定于问题的知识来减少搜索量。在这些元启发式算法中，遗传算法(GAs)因其在复杂地形[16]中利用有向随机搜索来寻找最优解，为传统的优化技术提供了一种新的选择，越来越受到研究者的重视。遗传算法是一种模拟遗传遗传和适者生存的生物进化过程的随机过程。它是一种智能随机搜索机制，用于解决生产优化问题，包括调度问题、装配线平衡和总生产计划。对GA进一步感兴趣的读者可以参考和。Aytug等人[19]查阅了110多篇论文，使用GAs解决了各种类型的生产和运营管理问题，包括控制、设施布局设计、线路平衡、供应链等。已有的文献研究表明，遗传算法能够从一个解集移动到另一个解集，灵活地结合问题的具体特征，可以作为求解np难问题的一种非常有效的搜索技术。为了达到这些好处，标准的遗传算法设计应该适当地修改和适应问题领域。然而，以往的研究大多是通过问题模拟来验证遗传算法的性能，很少关注实际的案例研究数据[20,21]。此外，许多研究还没有集成优化工具来选择它们的AG参数。针对这些局限性，本文提出了一种新的遗传算法(GA)。提出的遗传算法分三个阶段进行设计。在第一阶段，一个新的交叉算子是creed。在第二阶段，采用全因子设计来选择较好的遗传算法参数。第三阶段进行了简单的收敛性实验研究停止准则，以减少计算时间。该遗传算法的有效性评估是通过对某汽车电缆制造商的实际案例研究的各种实例集来实现的。本文其余部分的大纲如下:第2节描述了这个问题，并提出了一个二进制线性程序(BLP)来解决这个ALBP问题。第3节介绍了提出的遗传算法的步骤。第4节给出了选择遗传算法参数的应用实例和实验结果。第5节给出了计算结果。最后，结束语载于第6节。
问题公式化
拟议ALBP的一个实例(T, S, G)由以下三部分组成:
bull;T ={1hellip;n};一组n个任务，
bull;S ={1hellip;m};一套m站，bull;G;优先图。
这个ALB问题(ALBP)有以下假设和特征:
bull;每个操作的执行时间是确定的。
bull;任务不能再细分。
bull;装配任务之间的优先关系是已知且不变的。
bull;线上装配多种产品类型。bull;站与站之间不考虑缓冲区。
bull;给定车站数量(m)的有节奏的线。
bull;分区约束包含在站点的任务分配中。
每个任务只分配给一个站。
数学模型中考虑的符号和决策变量定义如下:
bull;索引和参数
i, j:装配任务，i, j = 1,2，hellip;，ns:工位，s = 1,2，hellip;，m
n:装配任务总数m:工位总数
任务一的处理时间
pre(i):任务ibull;决策变量的直接前辈集xj如果任务j被分配到工作站s0，则为
其中:表示不相容的对任务集(i, j)isin;T，其中不相容的对任务集(i lt; j)isin;T。
该问题可表示为二元线性程序(BLP)模型:
目标函数(1)最小化循环时间c。约束条件(2)保证每个任务iisin;T只分配给一个站sisin;s。约束条件(3)保证任务之间优先关系的尊重。以防任务jisin;T是分配给一个站isin;年代,所有任务我isin;(j)以前只能分配给电台年代′isin;s和s′sle;。约束(4)确保处理时间之和的任务分配给一个车站isin;年代不超过周期c不等式(5)禁止对任务的分配(IT)同一车站。最后，约束(6)确保xis是一个二进制变量。
大量约束条件和二元变量的存在，使得用精确的方法求解大型问题变得困难。因此，建议的遗传算法将在下面详细介绍。
提出的遗传算法
由于所提出的问题是NP难问题，因此我们选择使用GA方法，因为它是一种强大的工具，可以很好地解决NP难问题。
第一步:染色体编码
该编码方案是面向任务的，与[22]生成的方案相似。染色体的长度等于任务的数量，染色体的每个基因代表一个任务。
第二步:随机生成初始种群
初始种群是随机生成的，保证了优先关系的可行性。这些约束可能导致产生不可行的解决方案。消除和替换这些不可行的解决办法需要一个重要的时间。本文采用[23]的方法来满足优先关系。首先，根据任务的前体对任务进行注册，然后从没有前体的任务中选择一个随机任务(自由任务)分配到染色体的第一序列位置。其次，更新空闲任务集，从新任务集中选择下一个任务，重复这个过程，直到分配最后一个任务。
第三步:健康评估
染色体(个体)的适应度被定义为解的周期时间的倒数，以适应最小化问题。因此，解的循环时间越短，其适应度越重要。
f(j) = 1c表示染色体j的适应度函数值;j = 1，hellip;,J。
适应度值评估个体在搜索空间中的性能。
染色体的周期时间由以下步骤决定:
步骤一:确定初始循环时间值，下界(LB)计算如下:
步骤二:通过以下步骤确定工位数量[24]:只要不超过预定的周期时间，根据染色体上的任务序列将任务分配给工位。一旦至少超过一个模型的这个周期时间，或者不满足集合的分区约束，就会打开一个新站点进行分配，并重复这个过程，直到分配最后一个任务为止。
步骤3:如果得到的站数等于给定的m，则转到步骤4，否则循环时间C将增加1，转到步骤2。
第四步:完成整个程序并给出染色体的周期时间。表5给出了任务分配到各个站点的步骤，图1中给出了优先图G的一个示例(m = 6个站点(S)， n = 10个任务，(4,5)isin;IT)。
表1
任务分配到说明站的任务
的例子。
图1所示。说明示例的优先图G。
第四步:繁殖:选择、交叉和变异算子
bull;选择运营商
根据群体中每个个体的繁殖概率，采用[25]提出的“轮盘赌策略”选择亲本染色体。
bull;交叉算子(CO)
-第一个交叉算子(两个交叉点)。
第一个交叉算子(FCO)是由[26]引入的。其工作原理如下:
*随机选取两个点，如图2所示，将父代分为0- 1,1 - 2,2 -3个部分。
*来自第一个父(P1)的部件(0- 1,2 -3)的所有元素被复制到子代1 (O1)中相同的位置。
*将第一个父(1-2)部分中的所有元素按照它们在第二个父向量(P2)中出现的顺序进行重组，生成子(1)的其余部分。
其他的子代(O2)是用同样的方法生成的，其父代的角色是相反的。
图2所示。第一交叉算子(FCO)。
-第二交叉算子(四个交叉点)
第二交叉算子(SCO)使用四个交叉点，其工作原理如下:
*随机生成4个点，将每个家长分成5个部分(0- 1,1 -2,2-3,3-4,4-5)，如图3所示。
*所有来自第一个父元素的部件(0- 1,2 - 3,4 -5)的元素被复制到子代1中相同的位置。
*将第一个父向量的part(1- 2,3 -4)内的所有元素按照其在第二个父向量中出现的顺序进行重组，生成子向量1的剩余部分。
图3所示。第二交叉算子(SCO)。
bull;变异算子:打乱变异
该过程包括在解离串中随机选择一个位置，如图4所示。这个位置将后代切成两部分(片段)。片段1和片段2如下:
-片段1:所有元素都放在第一个位置之前。
-片段2:所有元素都放在第一个位置之后。
图4所示。变异算子:置乱变异。
片段1被投射到新的突变子代(new O)上，而片段2经历了一个重建过程[24]。
第五步:新增人口
在[27]中应用的替换策略用于创建新的种群。这种策略考虑到个体的适应度价值。新一代的个体必须具有所有个体形式中最佳的适应度(更高的适应度值=最小周期时间):
i)现时人口，
ii)交叉产生的off弹簧，
iii)发生突变的离体弹簧。
每一代的最佳解决方案都被存储起来，以避免其在以后的几代中丢失。
步骤6:停止标准
迭代次数是停止条件。当达到这个数字时，GA将停止，否则返回到步骤3。
应用案例及分析
提出的遗传算法用MATLAB 7.6实现。所有实验均在安装了英特尔(R) Core (TM) i3-2310MCPU, 2.10 GHz的PC机上运行Windows 7 Professional。为了对遗传算法进行参数表征和性能评价，我们对LEONI公司生产多种类型电机电缆的装配线进行了实例研究。
步骤5:选择遗传算法参数
遗传算法在解决方案质量和编译时间上的性能与不同的遗传参数值有关。
必要的迭代次数没有预先定义。我们改变了迭代的停止次数，以使某些实例的循环时间最小化，如表2所示。
由表2可知，初始种群的迭代次数固定为ntimes;1000次50个人。实际上，它给出了一个具有可接受编译时间的最小周期时间。然后经过ntimes;20代后停止算法
ntimes;1000并返回最佳解。
表2计算4个数字的3个实例的循环时间的迭代。
|
的迭代次数 |
N实例? |
最小循环时间 |
最大编译时间(分钟) |
|
1 |
70 250 480 |
||
|
100牛 |
|||
|
3. |
|||
|
1 |
69 240 470 |
||
|
500牛 |
|||
|
3. |
|||
|
1 |
68 230 475 |
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
