汽车电缆装配线平衡问题
Hager Triki1, Wafik Hachicha2, Ahmed Mellouli3, Faouzi Masmoudi4
- University of Sfax, Sfax Engineering School, ENIS, Tunisia
- Higher Institute of Industrial Management Sfax, Tunisia
- University of Sousse, Sousse Engineering School, ENISo, Tunisia
- Laboratory Research of Mechanics, Modeling and Production (La2MP) Engineering School of Sfax, Tunisia
Corresponding author:
Hager Triki
University of Sfax
Sfax Engineering School, ENIS, LA2MP:
Mechanic Modelisation and Production Laboratory Research
BP 1173, 3038, Sfax, Tunisia
phone: ( 216) 97752848
e-mail: Hager Triki@yahoo.fr
摘要：本文将介绍在一个真实的汽车电缆制造公司的装配线平衡问题（ALBP），这家公司需要提高生产速度，因此有必要平衡生产线。在这个ALBP中，站的数量是已知的，目的是为了减少周期时间，同时优先级和分区的限制必须满足。因而此问题就转化为一个二元线性规划问题（BLP）。由于该问题是NP困难问题，因此提出一种新的遗传算法。利用全因子设计得到更好的组合GA参数，并对停止准则进行简单收敛性实验研究，以减少计算时间。该结果与CPLEX软件比较表明，在一个合理的时间，GA产生一致的，非常接近他们的最佳的解决方案。因此，所提出的遗传算法是非常有效并且有优势的。
关键词：装配线平衡问题，遗传算法，周期时间，优先级和分区约束。
介绍：在过去的几年里，经典的简单的组装线平衡问题（SALBP）[ 1 ]已被广泛丰富，通过许多实际的方法和努力拉进了学术理论和产业现实距离[ 2 ]。每一SALBP的扩展对于解决实际问题是非常有用的，如处理任务间的[ 3 ]不兼容许多复杂的约束问题，空间约束问题[ 4 ]和资源分配等问题[ 5 ]。
在本文中，装配线平衡电机电缆的过程是在利奥尼跨国公司（http://www.leoni.com）研究下用以提高生产效率的。这家公司是是一家提供电线、光纤、电缆和电缆系统以及主要在汽车行业中的业务应用相关开发服务的全球供应商。在这个行业的一个有趣的SALBP扩展重点是考虑设置任务之间的分区限制，使不相容的任务都被分配到不同的站。例如，一些原材料（文件、管道等）可以如此相似以至于在质量考虑和处理条件下使得不同的工作站分配到某些成对的任务。
在这种情况下，站数（m）是已知的，同时目标是在满足任务之间的优先级和分区约束情况下使得循环时间最小化，因为所有版本的SALBP问题都是NP困难问题，这一ALBP问题也是NP困难问题。
许多应用已经在文献中采用精确的方法解决ALBP，如线性规划，整数规划[ 7 ]，[ 8 ] [ 9 ]，动态规划和分支定界方法[ 10 ]。然而，这些方法被证明只对小部分情况有效。因此，许多研究人员一直致力于发展启发式[ 11 ]和元启发式，如禁忌搜索[ 12 ]，模拟退火[ 13 ]和遗传算法[ 14 ]。所有启发式搜索方法的共同特点是智能地使用特定于问题的知识来减少搜索努力[ 15 ]。在这些算法中，遗传算法（GAs）是一个增加受到研究者的关注因为它提供了一种替代传统的优化技术，它采用随机搜索的方式，在复杂的环境中找出出最优解[ 16 ]。遗传算法是一种模拟遗传进化和适者生存的随机过程。它是智能随机搜索机制，用于解决制造优化问题，包括调度问题、装配线平衡问题和总生产计划问题。那些对GA更感兴趣的读者可以参考[ 17, 18 ]和[ 19 ]，Aytug等人[ 19 ]，他们审查了110多篇关于利用气体解决各种生产经营管理问题的论文，包括控制、设施布局设计、线路平衡、供应链等。
已有的文献研究表明，遗传算法可以作为解决NP难问题的一种非常有效的搜索技术，因为它能够从一个解集转移到另一个解集，并灵活地包含特定于问题的特征。为了达到这些好处，标准GA设计应该适当地修改和适应问题域。
然而，大多数以前的研究已经验证了他们的GA性能使用问题模拟，但很少关注真正的案例研究数据[ 20, 21 ]。此外，许多研究还没有集成一个优化工具来选择其AG参数。
由于这些限制，本文提出了一种新的遗传算法。提出的遗传算法分三个阶段设计。在第一阶段，以一个新的交叉算子为纲。在第二阶段中，使用全因子设计来选择更好的GA参数。在第三阶段，对停止准则进行了简单的收敛性实验研究，以减少计算时间。通过对一个汽车电缆制造商的实际案例研究来实现对GA有效性的评估。
本文的其余部分概述如下：第2节描述问题并提出二进制线性规划（BLP）用于解决ALBP。第3节提出了遗传算法。第4部分阐明了应用案例的步骤和选择GA参数的实验结果。第5节显示计算结果。最后，结束语发表在第6节。
问题方程：
一个实例（T，S，G）的提出源主要由三部分组成的：
T = 1hellip;n；一组n任务，
·s＝1hellip;m }；一组m站，
g；优先图。
这个装配线平衡问题（ALBP）具有以下的假设和特征：
bull;每个操作的性能时间是确定的且任务不能细分。
bull;汇编任务之间的优先关系是已知且不变的。
bull;在线路上装配多种产品类型。
bull;各站之间不考虑缓冲区。
bull;给定数目站（m）的速度线。
bull;分区约束包括在车站的任务分配中。
bull;每个任务只分配给一个工作站。
数学模型中所考虑的符号和决策变量定义如下：
bull;索引和参数
i，j：装配任务数，i，j＝1, 2，。..，N
s：工作站数，S = 1, 2，。..，我
n：装配任务总数
m：工作站总数
ti:任务任务的处理时间
pre(i)：任务i的前直接任务集
bull;决策变量：
1 若任务j安排到了工作站s;
0 其他
IT：代表一组不兼容的任务对（i，j）isin;T（当ilt;j时）任务对不兼容。
这个问题可以归结于以下的方式作为一个二进制线性规划（BLP）模型：
Min C （1）
服从于：
（2）
（3）
（4）
（5）
（6）
目标函数（1）最大限度减少周期时间C。约束（2）保证每个任务iisin;T被分配到唯一工作站sisin;S。约束（3）保证任务间优先关系的尊重。如果一个任务jisin;T被分配给一个站sisin;S，所有的任务iisin;pre(j)只能分配给站s′isin;S与s′le;s。约束（4）确保分配给工作站sisin;S的任务的处理时间的总和不超过循环时间C.不等式（5）禁止将（IT）的任务对分配给同一站。最后，约束（6）保证变量是一个二进制变量。
大量的约束和二元变量的存在使得大尺寸问题的数学求解困难。因此，拟议的GA将详细介绍以下部分。
提出的遗传算法：
由于所提出的问题是NP困难问题，所以我们选择了应用GA方法，因为它是一个用来寻找NP困难问题的优解的有力工具。
步骤1：染色体编码
编码方案是面向任务的，它类似于[ 22 ]生成的方案。染色体的长度等于任务的数目，染色体的每个基因代表一项任务。
步骤2：随机生成初始种群
初始种群是随机生成的，保证了优先关系的可行性。
这些限制可能会导致产生不可行解。这些不可行解消除和替换操作需要一个重要的时刻。本文用[ 23 ]的方法来满足优先关系。首先,任务的注册是在前人基础上，然后从没有前人评价的随机任务（自由任务）选择为染色体序列的第一个位置分配。第二，更新自由任务集，并从新集合中选择下一个任务。重复这个过程直到最后一个任务被分配。
步骤3：适应度评价
染色体（个体）的适应度定义为逆解的周期时间是适合一个最小化问题。因此，解决方案的最低周期时间越短，其适应度越高。
表示染色体j的适应度函数值；j=1,...,J.
适应值在搜索空间中评估个体的性能。
染色体的周期时间由以下步骤决定：
步骤1：确定初始周期时间值的下限（LB）计算如下：
(7)
步骤2：通过以下步骤[ 24 ]鉴定工作站编号：只要预定周期时间不超时，根据任务序列在染色体的结果把任务分配给工作站。一旦这种循环时间至少超过一个模型，或者IT设置的分区约束不满足时，将打开一个新的工作站进行分配，并重复这个过程直到最后一个任务被分配为止。
步骤3：如果所获得的站数等于给定的m到步骤4，否则循环时间c将递增1并转到步骤2。
步骤4：完成过程并显示染色体的周期时间。表5说明了分配任务到工作站的步骤说明顺序图，如图1（Fg.1）所示的例子。(m=6站（S）,n=10个任务，（4，5）isin;IT)。
步骤4：复制：选择、交叉和变异算子
bull;选择算子
根据每个个体的繁殖概率在人口、母染色体选择的“轮盘赌”战略提出的[ 25 ]。
bull;交叉运算操作员 (CO)
–第一个交叉运算符 (两个交叉点)。
第一个交叉算子 (外交部) 由 [26] 介绍。它的工作方式如下:
* 随机选取两个点, 如图2所示, 将父项分为三部分 (0-1、1-2、2-3)。
* 将第一个父级 (P1) 的部件 (0-1、2-3) 中的所有元素复制到 offspring1 (O1) 中的相同位置。
* 第一个父部分 (1-2) 中的所有元素根据其在第二个父向量 (P2) 中的外观顺序进行重组, 以生成后代1的其余部分。
其他子代 (O2) 是使用相同的方法生成的, 其父级的角色被反转。
–第二个交叉运算符 (四个交叉点)
第二交叉算子 (上海合作组织) 使用四交叉点, 它的工作方式如下:
* 随机生成四点, 将每个父级分成五部分 (0-1、1-2、2-3、3-4、4-5), 如图3所示。
* 从第一个父项的部分 (0-1、2-3、4-5) 中的所有元素复制到子代1中的相同位置。
* 第一个父项的部分 (1-2、3-4) 中的所有元素根据其在第二个父向量中的外观顺序进行重组, 以生成后代1的其余部分。
bull;变异运算符: 争夺突变
该过程包括在后续解决方案中随机选择一个位置, 如图4所示。这个位置把后代切成两部分 (片段)。片段1和片段2被介绍如下:
–片段 1: 所有元素都放置在第一个位置之前。
–片段 2: 所有元素都放置在第一个位置之后。
片断1在新的变异的后代被投射 (新的一代), 但片断2经历重建过程 [24]。
步骤 5: 新人口
在 [27] 中应用的替换策略用于创建新的填充。这个策略考虑到个人的适应度价值。新世代的个人必须有最佳的适应度 (更高的适应价值 = 最小的周期时间) 所有各自的形式:
一) 目前的人口,
二) 由交叉产生的后代,
三) 遭受变异的后代。
为了避免世代的损失, 每一代人的最佳解决方案都是存储的。
步骤 6: 停止条件
迭代的次数是停止条件。当达到这个数字时, GA 将被停止, 否则返回到步骤3。
应用案例与分析：
提出的 GA 是用 MATLAB 7.6 实现的。所有实验都是在 Windows 7 专业安装在英特尔 (R) 核心 (TM) i3-2310MCPU, 2.10 GHz 的 PC 上运行的。为了表征遗传算法的参数和性能, 本文探讨了在公司莱尼中产生多种类型电机电缆的装配线实例。
步骤 5: GA 参数的选择
全文共10818字，剩余内容已隐藏，支付完成后下载完整资料
英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[11039]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
