混合装配线平衡问题的启发式过程

《混合装配线平衡问题的启发式过程》由会员分享，可在线阅读，更多相关《混合装配线平衡问题的启发式过程（13页珍藏版）》请在装配图网上搜索。

1、混合装配线平衡问题的启发式过程摘要： 为了迎合高的定制要求，混合装配线是迫切需要的。该类生产线以混合序列生产多种模型。设计一套装配线应包括其平衡过程研究：工作元素向工作站的分配。即使对于单 一模式装配线而言，装配线平衡问题仍是NP难题（非多项式算法问题）因此启 发式过程常用来避免棘手的多维问题。有效的启发式是解决平衡混合生产线的便 利方法，因为在现实生活中，可行解决方案的检索一般是可以满足要求的。本文 提出了7种优先规则，它可以与一个面向解决第二类混装线平衡问题（工作站数 量已知（type-II）的工作站关联使用。优先规则和面向启发式工作站是基于 这样一种理论：即仅仅最小化循环时间并不是混装线

2、的全部目标。关键词：混装线，第二类平衡问题，启发式工作站一、 简介单一的装配线已经不能适应客户不断提升的期望和为了满足大量客制化需求而进行的 工业产能平行化。有多变种的模型可以吸引足够的客户以达到装配系统的盈利使用。变种一 般仅仅是特殊定制的模型属性不同而都是同一模型平台的衍生物。两种模型的准备时间很小 可以忽略，最终这些模型可以安排在同一生产线混流装配。设计装配线要考虑平衡过程，也就是工作元素向工作站的分配。装配线常用的目标函数 为利用率的最大化。通过在给定的循环时间内最小少工作站数目（type-I）或者在工作站给 定的情况下使循环时间最小化（t ype-II）0不能将最小化循环时间（或工作

3、站数量）当作混装条件下的唯一目标。阻塞和空闲：因 不同模型到达生产线而造成（在工作站中装配时间各不相同）；使得准确评估装配线的吞吐 量变得非常困难。工作站耗时严重依赖于所装配的不同模型，这会引起相应的短期混流排序 问题（MSP）。因为MSP问题，人们要找到模型单元的投送顺序，以满足短期计划周期的模型 流程所给定的要求，并优化某些目标。这些目标主要针对的是因多种模型的站内时间不同而 造成的效率低下问题。混合装配线平衡问题和排序问题（MSP）相互依存。一些学者建议同事考虑这两个问题。 但是，这些问题通常源于不同的订单，有着特定的不同数据，因此排序问题会因每个订单、 每天、每周的不同而出现。同时优化

4、一般是不可行的，如它们通常会有完全不同的时间框架。在更高的平衡水平上使用分层计划方法来预测排序结果看起来更加有意义。平衡化阶段 的可变性目标已在文献【2,3,9,10】中提出，以减少在分层计划方法中安排排序所遇到的困 难。值得注意的另一个问题是，在JIT条件下，混装线要满足不断变化的动态要求。所以， JIT条件下装配线的设计过程不强调排序问题，其主要研究对象是平衡问题。目前一些企业中的现有装配线需要解决方法，而这些方法不应是减少现有工作站，甚至 当设备造价昂贵时还不得不增加工作站。方法本文致力于开发简单的启发式而非构造数学模型并以优化技术来解决问题。由于装配线 平衡问题是 NP 难题，启发式过

5、程通常用以避免维数问题，通过构建单一可行解。所以，是 单一平衡。快速高效的启发式对于装配线平衡是有效的工具，因为一个可行解关注于所给工 作站的数量和循环时间，在现实中，它的获取一般较容易。Gumussoy和Kabak研究了最优 解的应用问题，这些最优解可以通过启发式方法来解决实际ALB问题，如Ranked Positional Weight（RPW）。参考工业实例，他们在论文中指出，一些最优解的寻找方法根本不能解决问 题，如二进制公式和最短路径公式。一种解决MALBP的方法是:绘制一个应用于所有模型及其平均任务次数的公用优先级图, 以获得等效的单模型问题。这种从混合模型数据到单一平均模型数据的

6、简单转化，确保了循 环时间对于完成所有模型是足够的。但是，即使使用了平均模型的最优解，在实际的装配线 操作过程中无疑会产生效率低下的问题。本文中，尽管公用的优先级图用于定义所有优先级关系，但是当且仅当个体模型的任务 次数少于或等于工作站中对应模型的可用时间时，才向工作站中分配任务。这种与简单地平 均任务时间在方法上的差异，用于量化整条装配线在平衡阶段自身的效率低下问题，从而启 发式过程可以试着消除，至少是减少这样的效率低下问题。起初，工作站对于每个模型的可用时间被当做循环时间。工作站可用时间用一个行向量 表示，其各列的数值与模型数相同。任务分配之后，用于进一步分配的可用时间（工作站中， 对于每

7、个模型的），将通过从工作站可用时间中减去模型任务时间计算得出。A. 面向启发式的工作站第一步：输入工作站数（Nw）,模型数（Nm）,所有模型的所有任务时间，以及任务优先关系。第二步:设定循环时间，作为所有模型理论最小循环时间的最大值。第三步:分配循环时间值，作为所有工作站的可用时间。第四步:打开1 号工作站，分配任务。第五步:找到可分配的任务。可分配的任务都应有前续工作站，并且其所有任务时间应小于 工作站相应模型的可用时间。第六步：令可分配的任务编号为Na。a. 如Na=0,贝I：1. 如果现有工作站数位Nw,或现有工作站的单个模型的累积空闲时间多于相应模型的允许空闲时间，贝舍弃所有任务分配，

8、循环时间增量1，返回第三步。2. 否贝，开启下一工作站并分配，到第五步。b. 如Na=1，向现有工作站中分配任务。c. 如Nal，将可分配的任务根据所用的优先级规则按照升序/降序排列，并将列表 中的第一个任务分配给当前工作站。第七步：从上一步的可用时间中减去已分配了的任务中所有模型的任务时间，得到新的可用 时间。重复 5-7 步，直到所有任务分配到给出的工作站中。B. 优先级上述的启发式过程使用优先级来构建操作顺序，根据该顺序向工作站中分配操作。 仅仅最小化循环时间不能作为MALBP-II的有效目标，因为工作站的平滑工作分配更加重 要。因此，本文中的优先级利用循环时间、模型多样性、工作站多样性

9、，或者是三种操 作对象的结合来指导启发式过程。处理装配时间多样的Bottleneck法也可以考虑来构建 优先级规则。第一优先级规则，即Mean Positional Weight (MPW)规则是一种改进Ranked Positional Weight (RPW)规贝I。RPW用于解决混流ALB问题，但须通过平均模型任务时 间，将他们转化为等效的单一模型问题。第二优先级规则是Base Model Variability(BMV), 旨在最小化模型多样性。BMV基于逻辑学，如果混装线上的个体问题可以近似地平衡为 他们各自的最优循环时间，那么MALBP的解可作为一条装配线的解。第三条规则基于 工作

10、站的工位多样性来优先化任务，根据该工作站的分配任务，叫做Task Prioritization using Station Variability (TPSV)0第四条规则综合了 MPW和BMV，第五条规则综合了 MPW和TPSV，而第六条规则融合了这三类方法。第七条优先级规则是改进型Bottleneck 方法。Bottleneck方法由Bukchin提出，他同时指出该方法在混流条件下等效仿真装配线 方面要优于其他方法。值得注意的是，他并没有使用 Bottleneck 法来获取平衡解方案， 而是等效仿真混装线的流程。 Bukchin 也在三段式平衡启发式中应用该方法，但仅针对 基于临近搜索的方

11、案改进过程。本文中，我们尝试改进Bottleneck方法，以适应任务的 优先级，并将其命名为 Bottleneck Priority Rule(BPR)。本方法的新颖之处是利用模型可变性，工位可变性和瓶颈方法当做优先级规则。据 我们所知，这是第一次在启发式中利用它们作为优先级规则来获取平衡方案。但是，应 该注意到，该优先级规则是从早期的方法中派生出来的。下面是优先级的描述：Nw 工作站数量Nm 模型数量Ntk 任务总数ntk 任务时间非零的模型数t,，m模型m的tk任务时间tkStk任务tk的所有后续任务集tkTwm 在工作站w中的模型m的站内时间T ,(平均) 工作站w的平均站内时间。wmT

12、m模型m的理论最小循环时间。cw 已分配任务的当前工作站XN X的规范化值B1. Mean positional Weight（MPW）在有相关任务分配的模型中， 对于每个模型来说，一项任务的位置权重会单独计算出 来，然后除以模型数量得到平均值，有关的任务会呈现在这里。对于没有相关任务的某个模 型m任务的位置权重置零。对于没有任务的模型m，位置权重看作0.然后将任务的 MPW 规范值取为：将任务按照其规范化的 MPW 值降序排列。B2. Base Model Variability（BMV）任务的BMV作为所有单个模型可变性数值的最大值。单个模型可变性数值这样算出:M 模型的所有站内时间与理论

13、最小循环时间的平方差。T包括任务tk的任务时间。任务 wm根据规范化BMV数值升序排列。BMVtkmax（cw/、心/ISMVj二B3. Task Prioritization using Station Variability（TPSV）站的变化值被当做当前工作站站内时间的标准偏差，而任务tk正考虑分配入该工作 站。而且，Twm包括任务tk的任务次数。TPSVtkITPSV 值同样被规范化并以升序排列来确定任务优先级。B4. MPW 结合 BMV (PWMV)PWMVt? =MPW.? - BMVtkxB5. MPW 结合 TPSV (PWSV)卩wsv/=M 卩w/- TPSVtkNB6.

14、 MPW 结合 BMV 和 TPSV (PWMSV)卩WMSVtky = NIPWj - BMVt/-TPSVtkx按照B4B6的优先级规则，以降序对任务进行排列。B7.基于Bukchin的公式，可以定义TBD (time between departures)的预期时间:E(TBD)=工工円(几丽i血巒曲曲时忖咖任务按照他们的规范化E (TBD)值以升序排列，这些数值可认为是所以模型的平均循环时 间。三、实例为了评估面向启发式和优先级规则的工作站的应用情况，引入一个包括十个问题的数据 集。图1-4的联合优先图表示了使用从文献【16】【1】【15】【17】【11】中得到任务次数和 优先关系数据

15、的这些问题。尽管【16】和【1】的联合优先图的数据相同，但是模型的数量 不同，这使得它们是不同的两个问题。工作站数量的两个不同数值引入到上述五个问题实例 中。 Table1 列举了十个问题:Tabl-e 1MALBP INSTANCESProblemInstanceProblem Nomen ckitiireJoint Precedemc-e DiagramNumber ofStations1M3W3SMFig. 132M3W5SMFig. 153M4W3JDFig 13斗M4W5JDFig. 155M3W3BUKFig. 236M3W5BUKFig. 257M2WSVSFig. 3$SM2W

16、10VSFig. 3109M2W7GKF墀4710M2W9GK.Fig. 49四、结果和结论图一：实例 1-4的联合优先图图二：For实例5和6图三： For 实例7和8图四： For 实例 9 和 10I)1$1?:B?l1012图 5-8 表示 4 个目标，即循环时间，模型多样化，工作站多样化和最大完工时间。每一 个最大完工时间的获得是通过选择启动模型的最佳序列。循环时间的显示结果表明，基于位 置权重或位置权重与模型可变、工作站可变结合的优先级规则，比单独基于模型或工作站可 变、瓶颈方法表现的更好BPR在循环时间和模型可变方面表现更差，但是与其他优先规则 相比，它在最大完工时间方面是可作为

17、参考的，在某些实例中甚至更好。 MPW BMV TPSV PWMV PWSV - PWMSV BPR图 5 循环时间UdQ ASIAIMd ASAAdV AlAIMdB ASdLB AIA19 旳d8 ASIAIMd ASAfld AlAIMdB ASdLB AIA19 AAdt/M 6040M3W35M MSW55M M4W3JD M4W5ID M3W3BUKMJW5SUK MZWSVS MJWlflVS W2W6K M2W9GKB MPW IBMV 1 TPSV aPWJVIV PWSV PWMSV图8 最大完工时间优先规则表现的良好的模型可变性是振奋人心的。注意到模型可变的最优解可以通过对 每个某型单独做平衡得到，它也是工作站可变的最优解，但反之不成立。工作站可变和最大 完工时间的可比较的结果是很有趣的。然后以稍后得到的单个模型的平衡为基础，对所有十 个问题的优先规则的表现做了比较。这种评估的两个有代表性的案例在图9、10 中给出。单独使用MPW，或BMV和TPSV联合使用要胜过其他规则，因为它有着更低的平衡延 迟值。这样的解决方案意味着生产线上更少的阻塞和空闲，会得到更高的效率。基于上述分 析，可以得出这样的结论：作为MALBP-II的平衡方法，MPW （某些问题的PWMV）表现出 很好的应用潜力。