混合模型平行双侧装配线平衡问题：
基于柔性代理的蚁群优化方法
摘要：装配线经常被作为组装生产复杂产品的一种方法，而双面装配线通常用于组装大尺寸产品，例如，乘用车，公共汽车，卡车。其并行定位的两条线有助于提高线路工作人员之间的协作，进而提高生产线的工作效率。本文提出了一种混合模型平行双面装配线系统，可用于在混合顺序生产中生产大尺寸产品，并且定义了混合模型并行双侧线路的平衡问题，讨论了跨线路生产和利用多线路站点的优势。作者开发了一种基于柔性代理的蚁群优化算法来解决该问题，并给出了一个数值例子来系统地解释该方法。该算法构建了适用于任何模型序列的柔性生产线平衡解决方案，此外，还研究了工作站的动态变化工作负载（基于生产过程中的特定产品模型）。本文进行了全面的实验研究，并使用一种常用的配对样本t检验对结果进行统计分析。测试结果表明，与单独平衡的混合模型双面线相比，混合模型平行双面装配线能系统减少劳动力需求，其结果还表明，所提出的算法优于禁忌搜索算法和常用于装配线平衡域的六种启发式算法。
关键词：装配线平衡； 混合装配线；双面线；基于柔性代理的系统；蚁群优化；计划生产
- 介绍
装配线是由一系列工作站组成的，用于执行一组有限的重复性任务的生产线，装配线上的每项任务都需要一定的处理时间，任务之间也存在一定的优先关系。装配线平衡问题的主要目的是以满足优先关系和容量限制（由需求和周期时间确定）以及一些性能测量（例如，工作站数量，线路效率等）优化。 由于装配线通常位于生产系统的末端，装配线平衡问题对整个制造系统的整体性能具有显着影响，因此在设计和管理生产线时，装配线平衡是一个应该足够重视的问题。
自从六十年前Salveson的装配线平衡问题面世以来，这一问题在学术界的受关注程度从未减少，而目前，该问题的研究热潮再一次被掀起。由于全球市场对定制产品的兴趣日益增加，市场上出现了混合模型装配线，并且由Thomopoulos引入了混合模型装配线的平衡问题。混合模型装配线能够实现在同一生产线上按照混合顺序生产各个不同的产品。对于解决混合模型装配线平衡问题，除了上述研究外，众多的研究学者还提出了各种启发式，元启发式和精确求解方法;例如，Kara等人； Ozcan和Toklu，Ozcan等；Mosadegh等； Manavizadeh等。Ozcan等以及Xu、Xiao、Akpinar和Bayhan开发了模拟退火方法； Hamzadayi和Yildiz以及Manavizadeh等开发遗传算法技术； Simaria、Vilarinho和Yagmahan 开发了蚁群优化（ACO）技术；Akpinar等用遗传算法杂交ACO得出了一种新的算法。 Simaria和Vilarinho开发了一个新的数学模型；Yagmahan的研究考虑了多个目标，并最大限度地减少了工作站的总数。
Bartholdi系统的介绍了混合双面装配线，他认为混合双面装配线对于大型产品（例如卡车）的装配比对小型装配（例如电钻）更实用。依据各个学者和研究人员提出的不同的启发式算法和其他遗传算法的实例，启发式算法和众多遗传算法被提议用于混合双面装配线的平衡问题。Wu等人也提出了一些新奇且实用的解决方法，并期望以最佳方式解决双面装配线平衡问题。
最近，Gouml;kccedil;en等人提出了一种装配线并行化的思想，将两条或多条具有共同资源的装配线被置于统一系统中进行平衡，并对并行装配线平衡问题进行了定义。他们的研究表明并行定位的两条直线有助于最大限度地减少工作站的总数。在接下来对于该问题的是其他研究中，有些研究者开发出了用于解决该问题的新技术（例如，Benzer等人的最短路径方法，Ozcan等人的禁忌搜索算法，Scholl的精确程序， Boysen和Kara等人的模糊目标规划模型，以及Baykasoglu等人和Ozbakir等人的基于ACO的方法。装配线并行化思想目前已初步应用于混合模型线和双面装配线。 Ozcan等人讨论了并行混合模型线，并且提出了一种模拟退火方法，用于解决这类线上的平衡和排序问题。他们引入了平行的双面装配线系统，以结合平行线和双面线的优点，并提出了禁忌搜索算法（以下称为TS）。 Kucukkoc和Zhang使用基于ACO算法的方法在平行双侧线上同时最小化了循环时间和工作站的数量得到了一种平衡结果。
从以上的描述和分析可知，有许多关于混合模型线、双面装配线和平行线的研究，关于它们的二元组合也有一些理论和成果，例如混合模型平行线，平行双面线等。然而，混合模型平行双面线的研究数量仍然相当有限。虽然在工业生产中生产大型的大批量产品时会遇到混合型并行双面装配线问题（例如Jack的梅赛德斯-奔驰巴士的伊斯坦布尔装配线以及Bloomberg描述的丰田的葡萄牙工厂的公共汽车装配线），研究人员并没有妥善处理这些问题。 Kucukkoc和Zhang介绍了混合模型并行双侧装配线平衡和排序问题，并提出了使用基于柔性代理的蚁群算法的基本方法和方案框架。
本文旨在利用Kucukkoc和Zhang在2014年提出的框架，为混合模型装配线平衡问题开发通用的解决方案并且构建具体的解决方法。首先，与Kucukkoc和Zhang的研究有所不同的是，在目前具体工作中的研究没有考虑模型排序问题，其旨在获得与任何模型序列兼容的混合模型平行双面装配线系统，因此获得的解决方案更灵活（具有更低的临界性）并且可以在模型需求不可预测或在生产环境不稳定的情况下应用。此外，还开发了基于代理的蚁群优化（ABACO）算法，该算法将适应任何模型序列，并且通过实验测试验证了所提出方法的性能。同时，我们还提出了一个数学公式来计算混合模型平行双面线的线长下限和工作站数。通过使用所提出的方法解决各种测试问题而获得的结果与通过统计分析的针对这些问题计算的下限进行比较。使用六种常用的启发式方法和TS方法也解决了相同的测试，并将结果与从ABACO获得的结果进行了比较。
本文的其余部分安排如下：第2节给出了混合模型平行双面装配线平衡问题的具体解释和描述（以下称为MPTALBP）；第3节解释了所提出的求解方法；第4节给出了一个数值例子；第5节中展示了计算实验的结果；第6节使用配对样本t检验对所得结果进行统计分析；第7节强调研究的局限性和可能的工业意义以及未来的工作方向，并且得出结论。
- 问题定义
MPTALBP是一个新的研究领域，是一种可以灵活地在平行装配线上生产大型产品的类似模型。这种新型的生产线配置方式具有许多优势，例如拥有更短的生产线长度；共用生产工具；灵活地以不同的生产率生产不同的产品模型；更低的材料处理成本；更少的人员移动；提高生产线效率和拥有更少的工作站数量。每个双面装配线与其相邻的双面装配线平行，由Lh (h=1,hellip;,H )表示,多个不同的产品模型由Mhj(j=1,hellip;,Mh)表述，在每条平行的双面装配线上生产。根据某些技术优先关系执行属于每个产品模型的一组任务thji (i=1,..,Thj)， Phji代表线Lh上的模型mhji以及任务thji的前任集合。需要在一系列工作站Whkx (k=1,hellip;Kh; x=0,1)上处理与每个任务相关联的一定量的处理时间(pthji)，其中x是二进制变量，0表示左侧线，1代表右侧线。与传统线路一样，需要满足容量约束和优先关系。但是，在分配彼此之间具有优先关系且需要在装配线的不同侧执行的任务时需要特别注意。假设任务1和3是任务5的前项任务，并且任务3和5可以在装配线的左侧进行操作，而任务1则需要相反的一侧进行加工。在这种情况下，必须在初始化任务5开始之前完成在线路另一侧的任务1的加工工作。以上这种情况在线路平衡中称为干扰，违反此规则会产生不可行的解决方案。
并行双面装配线的另一个重要优点是使用多线站。多线站有助于最大限度地减少操作员（或工作站）的总数，从而最大限度地提高生产线效率。 图1表示典型的混合模型双面装配线系统。
图一
图1是典型的混合模型并行双侧装配线系统。从图中可以看出，在队列2中两条相邻线路之间使用的多线站分配的运营商同时工作，第一行的右侧和第二行的左侧。 每行可能有不同的循环时间（Ch）：
其中Dhj表示在P的计划周期内对线Lhj上的模型mhj的需求。
在循环时间存在差异的情况下，应使用共同的循环时间来分配每个循环中的任务。这可以使用Gouml;kccedil;en等人所描述的基于最小公倍数（LCM）的程序来实现。在该过程中，计算具有不同循环时间的两条线的共同循环时间（C）。 根据线的原始循环时间与公共循环时间的比率来修改这些线上的任务的处理时间。
步骤解释：( i）找到周期时间 ( C1和 C2）的最小公倍数; （ii）LCM除以C1和 C2分别计算ld1和ld2; （iii）在第I行和第II行执行的任务的处理时间分别乘以ld1 和ld2 （iv）LCM被认为是线的共同循环时间，并且线被平衡在一起。
运用以上算法是需要满足的要求有：
-在每条平行的双面装配线上生产多个产品型号。
-任务时间和模型需求是已知和确定的。
-每条线路可能有不同的周期时间（由规划范围内的需求决定）。
-相似模型之间的共同任务必须分配到同一工作站以提高资源利用率。为实现此目标，我们为在同一生产线上生产的产品模型构建了联合优先级图。
-任务对在生产线的某一侧生产有偏好。
-任务不能在工作站之间分配，必须将每个任务分配给一个工作站。
-操作员没有任务或工作站的偏好。
-不允许使用并行工作站，只有一名操作员可以在工作站上工作。
-忽略操作员的旅行时间，不允许暂停正在进行中的工作。
-不考虑破坏或故障，并且需要在规划期间内不断执行装配过程。
基于双面装配线平衡问题的性质，我们需要投入更过的精力来避免由于在线的另一侧上的任何未完成的前项任务而可能发生的干扰。此外还必须考虑每条线上的模型变化使得问题（其已经是NP难类的组合优化问题）更难以解决。因此，确定位于两条相邻线路之间的多线站点中的运营商的可用时间，并识别将在线路上产生的模型序列的执行操作在获得可行的解决方案中起着至关重要的作用。由于任务的处理时间在生产过程中可能因产品型号而存在差异，因此位于这些工作站中的操作员在某一时刻是否处于工作状态取决于在生产线上组装产品的顺序。基于此，本文提出了一种更通用的解决方案，它符合任何模型序列。
- 目标方法
元启发式算法是解决复杂问题或者应用实例时常用的优化技术，因为它们能够在解决方案的质量和计算时间之间提供所需的权衡。 元启发式算法也比以前常用的精确方法更灵活，因为它们是独立于问题的解决方案算法，可以适应大多数现实生活中的优化问题。
ACO是一种自然启发的元启发式算法，它模拟真实蚁群的集体能力，以找到巢和食物来源之间的最短路径。蚂蚁通过一种叫做信息素的化学物质相互交流。在搜索过程开始时，蚂蚁随机在路径上徘徊。找到食物来源的蚂蚁走回巢穴，将信息素留在地上。包含信息素的路径将以一定的概率吸引其他蚂蚁，通过这种方式，较短的路径可能会更强，因为每当它们走回巢穴时，蚂蚁就会将信息素掉落在地面上。最终将在巢和觅食区之间建立最短路径。 有关ACO算法各种应用的文献综述，请参阅Dorigo和Stuuml;tzle的相关文献。
基于代理的系统也可以从该方法中得到启示，通过彼此协作以找到应对复杂问题的解决方案。本研究中开发的算法ABACO由基于ACO的线路平衡程序组成，该程序基于代理的平台构建，由具体结构由三层算法组成：促进剂（FA），计划剂（PA）和平衡剂（BA）。 每层中存在的代理相互交互，为MPTALBP构建完整的平衡解决方案。简而言之，整个过程由FA协调，而PA则提供BA所需的数据以构建平衡解决方案。 与Kucukkoc和Zhang的研究不同，ABACO不包含模型测序机制，因为其不需要考虑模型测序问题。相反，其目的旨在实现更灵活的线平衡，以实现符合任何模型序列。
图二
图2给出了ABACO的伪代码。如图所示，FA通过从电子表格和参数中读取输入数据（即任务处理时间，优先关系，计划范围和模型需求）来初始化ABACO。 来自集成用户界面的算法。 这些参数包括菌落数和每个菌落中的蚂蚁数。优先关系数据被转换为矩阵，以便在后期阶段的解决方案构建过程中可以轻松检查任务的可用性。
FA调用PA来执行计划和计算参数值。 PA使用FA导入的数据进行初步计算，作业要点如下所示：
--每条线路的周期时间是根据每条线路上产生的模型的需求和使用公式
英语原文共 37 页
资料编号：[4153]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
