英语原文共 13 页
具有并行性能的双边生产线平衡问题
Abdollatif Sepahi , Seyed Gholamreza Jalali Naini
Department of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran
伊朗科技大学工业工程系,伊朗德黑兰
摘要
双边生产线平衡问题(Two-ALB)通常发生在生产大型大批量产品的工厂中,例如公共汽车,卡车,机车和家用产品。在这项研究中,我们考虑使用一个双边生产线平衡的新方法,能在现实世界的机车生产工厂中并行执行任务。该问题用混合整数规划描述,并提出了一种新的启发式算法,该算法可以产生稳定的结果,并且对于一些基本的双边生产线平衡问题基准获得了更高质量的解决方案。实际上,所提出的算法针对一些小规模问题可以获得最优解,对于中等规模问题可以获得近似最优解。
关键词:启发式算法;数学建模;并行能力;并行双边生产线
1.介绍和文献综述
装配线可以分为几种类型,例如传统的直线,U形单边线,多层线和双边线。 双边装配线是本研究的主要焦点,专为生产大型产品的工厂而设计,如生产公共汽车,卡车和机车。这些产线包括一组连续工作站和任务,它们在装配线的两侧实施。
双边装配线平衡(Two-ALB)与传统的单边产线平衡(One-ALB)不同,因为能在不同的操作方向上执行任务。可在装配线的一边执行一些组装操作,而在装配线的另一边执行另一些; 因此,任务按三种类型分类:左,右或其他任务。
在先前的研究中已经在解决方法和问题定义方面讨论了双边装配线,但据我们所知,以前没有比较双边装配线平衡问题和传统的单边装配线平衡问题。1993年,Bartholdi首次在一个实际案例研究中解决了双边装配线平衡问题,他提出了一个基于一次拟合规则(FFR)的简单分配规则,专注于开发和使用交互式程序支持解决方案的快速和渐进式构建,其中FFR启发式旨在最小化作为目标函数的工作站的数量。Kim等人开发了一种遗传算法(GA)来求解双边装配线平衡问题。Le等描述了双边装配线平衡问题的分配过程,以最大化工作相关性和松弛性.Lapierre和Ruiz提出了一种增强的基于优先级的启发式算法来解决特定的双边装配线平衡问题。Kim等人使用遗传算法解决了这个问题,其目的是在位置约束下,在给定的周期时间内最小化工站数量,这种模型适用于各种双边装配线平衡问题。Ouml;zcan和Toklu使用了这个基本模型但更改了目标函数以最小化配合工站的数量。此外,Ouml;zcan和Toklu分别基于最小化工站数量和周期时间的目标,将这些双边流水线平衡问题分为TALBP-I和TALBP-II分别基于最小化站点数量和周期时间的目标。
就问题定义而言,在大多数双边装配线平衡问题中考虑了几个约束,包括分区约束,同步约束和定位约束。分区约束与任务是否指定到同一工作站(Ouml;zcan和Toklu)有关,同步约束决定了配合工站中的配对任务能否在对侧线上同时启动(Simaria和Vilarinho),定位约束确定是否将任务分配给特定站点(Kim等人)。Wu等人提出了一种用于TALBP-I的分支定界算法,它最小化了线路的长度,并以最优方式解决了Bartholdi描述的有148个任务的TALBP-I问题。Baykasoglu和Dereli应用基于蚁群的启发式算法来解决双边装配线平衡问题,其中分区约束首次被引入到双边装配线平衡问题中。Xiaofeng等人提出了一种用于求解TALBP-I问题的启发式算法,其中基于开始时间的面向工站的程序用于分配从左站开始并移动到该位置右侧工站任务。通过检查已分配任务之间的优先约束,最终删除不合适的位置分配。Ouml;zcan和Toklu提出了一个数学模型,一个用于精确目标的先用目标规划模型,以及一个用于不精确目标的模糊目标规划模型用于求解带有分区约束的TALBP,将配对站的数量,周期时间和每个工站分配的任务数视为目标。Simaria和维拉里尼奥提出了一种多目标蚁群算法,两个蚂蚁“工作”同时,分别在装配线的一侧,构建满足装配过程中优先,分区,产能,边侧和同步约束的平衡方案。主要目标是最小化装配线上的工作站数量,但工站之间的工作负载平衡也被视为附加目标。Ouml;zcan和Toklu提出了一种新的数学模型和一种模拟退火算法,以对确定周期时间最小化配对工站的数量(及装配线长度)作为主要目标,并以最小化工站的数量(即操作工的数量)作为次要目标。在所提出的算法中,同时考虑两个性能标准:最大化加权产线效率和最小化加权平滑度指数。他们的方法被用来解决一组最多148个任务的标准问题。Ouml;zcan和Toklu也针对这个问题提出了禁忌搜索算法,并通过最小化工站数解决。Rubiano-Ovalle和Arroyo-Almanza对当地一个摩托车生产厂进行了案例研究,并提出了模拟算法来解决这个问题。Kim等人开发了遗传算法用于上述带有详细特点的双边装配线平衡问题的基本数学模型。Yegul等人,随后Agpak等人通过额外的假设,引入了一种新的混合U形双边装配线,并开发了一种多通道随机分配算法,结果与标准直线双边装配线问题的结果进行了比较。Xiaofeng等人设计了一种分支定界算法来解决第一种类型的边装配线平衡问题(最小化工站数量)。Ouml;zcan在随机条件下考虑了双边装配线平衡问题(Two-ALBP),将机会约束方法应用于模型的随机约束,并提出了一个模拟退火算法来解决问题。Ouml;zcan和Toklu考虑了双边线的准备时间,并基于装配线(COMSOL)算法排序操作的计算机方法开发了一种启发式算法,最小化流水线长度和工站数量。Ouml;zcan将和现有流水线平行的额外流水线与双边线比较以改善和提高生产线的效率。Yinet al.也考虑了并行分离式工站的这个问题。Ouml;zbakir和Tapkan,以及Taha等人分别提出了蜂群算法和遗传算法,以解决双边装配线平衡问题。Tapkan等人在蜜蜂算法外,还提出了模糊环境的概念。Rabbani等人提出了一种新的多U形装配线来处理混流双边装配线问题,并弥补了简单的U形双边线的效用的降低。Chutima和Chimklai提出了一种粒子群优化算法来解决多目标,双边,混流双边装配线平衡问题,其采用Pareto最优性来同时优化冲突目标。
Purnomo等人提出了一个数学模型,使用一次拟合规则和遗传算法,目的是同时最小化给定数量的配合工作站的周期时间并平衡工作站。他们表明一次拟合规则可以利用在许多工作站上找到最佳位置的优势,并且遗传算法允许更灵活的任务分配,明显快于迭代的一次拟合。Hamta等人通过考虑灵活的操作时间来制定单边装配线平衡,开发了具有两个相反目标函数的双标准非线性整数规划模型:最小化周期时间和最小化机器总成本。他们将各种技术用于不同的目的,即用于创建合并无量纲目的LP度量方法和用于解决问题设计实验来调整参数的遗传算法。
对先前研究的回顾表明在以前的研究中没有考虑任务的并行执行。此外,TALBP-II是最不被考虑的目标函数。在下一部分,我们将描述本地机车生产工厂设置中的问题。然后使用混合整数线性规划对问题数学建模并且展现了已经提出的启发式算法。 我们将在本研究的最后部分讨论优点,缺点和计算结果。
1.1具有并行任务能力的双边装配线平衡
在这项研究中,我们检查配对任务在双边装配线平衡问题配对工站中并行执行的效果。流水线一侧的每个任务的性能都受到另一侧的并行任务的影响,该效果可以是正面的,负面的或中性的。
在先前的研究中尚未检查双边线的这一方面并仅考虑了同步约束,其对优先关系图有类似的处理方式且它不同于当前问题。
配对站上两个配对任务的并行性能可能对任务的成本和/或完成时间产生积极影响。在本地机车生产工厂中,假设在生产线的每一侧执行一项任务,并且两项任务都需要相同的质量检验员。检查员需要的某些设备必须搬运到工站。如果这两项任务是并行执行的,则可以在一次访问工厂期间执行测试,从而减少总检查时间和搬运成本。机车装配线是一条双边线,有三个或四个工作站和一些用于组装较小的部件的辅助线,如转向架和框架,它们会被转移到主线上,用于组装最终产品。机车的主干是其框架,用于支撑上部结构元件,其必须承受施加在机车上的所有载荷。
左右纵向杆是框架的重要部件,它们在辅助线上组装并转移到主线上进行最终组装。
在将纵向杆固定到夹具上之后,将较小的部件焊接到先前工作站中准备的杆上。首先在左纵向杆上进行焊接(任务A)。光顺焊接点后,焊接任务从右纵向杆开始(任务B)。如果分开进行,这些任务的焊接检查可能是耗时且非常昂贵的。但如果两个任务同时进行,则只需要进行一次焊接检查。
因此,已知配对任务的并行执行可能具有负面的相互影响。我们假设有两个配对任务,其中一个需要准确性和注意力,而另一个不会在物理上干扰第一个任务,但它会影响并行任务操作员的准确性,从而导致冗余,低质量或任务失败。在某些情况下,这些相互作用可以忽略不计。本研究的主要焦点是第一种情况,它经常发生在机车装配线上的类似并行任务中。
在本研究中,我们通过对基本的双边装配线问题建模来考虑任务的积极影响,确定了几个可以在并行线中同时执行的配对任务,从而缩短了任务完成时间,从而缩短了周期时间并提高了生产率。在我们的机车装配线问题的例子中,并行焊接任务的完成需要额外的操作员,这会产生额外的成本。对于本研究中考虑的问题,任务的并行性能受这些成本的限制,有成本是因为许多任务都是并行执行的。在下一部分中,我们使用混合线性整数规划公式描述此问题。
2.数学描述
在本研究中,我们考虑具有并行任务性能属性的双边装配线平衡问题,使用以下等式来制定,并且根据Kim等人使用基本TALBP模型。参数,集合和变量定义如下:
Sets
任务 |
|
配对工站 |
|
单个配对的工站 |
|
配对工站在边的工站 |
|
任务集 |
|
配对工站集 |
|
左侧作业集合 |
|
右侧作业集合 |
|
可在左右两侧操作的作业集 |
|
任务i紧前作业集 |
|
任务i的非直接先行作业集 |
|
任务i的直接后续作业集 |
|
任务i的非直接后续作业集 |
|
没有先行作业的任务集 |
与任务i有相反操作方向的作业集 |
|
与任务i有相同操作方向的作业集 |
|
能与任务i同时执行的作业集 |
|
与任务i没有关系的作业集 |
参数
任务i的正常的处理时间 |
|
任务i配对任务的正常处理时间 |
|
能与任务i同时执行的任务的数量 |
|
能与任务i并行执行的任务数量的上界 |
|
周期时间 |
|
任务i的操作方向 |
变量
如果任务i被分配给配对工站j操作方向为取值为1,否则为0 |
|
任务i与任务h并行执行取值为1,否则为0 |
|
任务i的完成时间 |
|
任务i比任务j早执行取值为1,否则取0 |
公式
lt;
(1) |
|
(2) |
|
(3) |
|
(4) |
|
(5) |
|
(6) |
|
(7) |
|
以上是毕业论文外文翻译,课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。