混合装配线平衡问题的启发式过程
摘要：
为了迎合高的定制要求，混合装配线是迫切需要的。该类生产线以混合序列生产多种模型。
设计一套装配线应包括其平衡过程研究：工作元素向工作站的分配。即使对于单一模式装配线而言，装配线平衡问题仍是NP 难题（非多项式算法问题）因此启发式过程常用来避免棘手的多维问题。有效的启发式是解决平衡混合生产线的便利方法，因为在现实生活中，可行解决方案的检索一般是可以满足要求的。本文提出了7种优先规则，它可以与一个面向解决第二类混装线平衡问题（工作站数量已知（type-II ））的工作站关联使用。优先规则和面向启发式工作站是基于这样一种理论：即仅仅最小化循环时间并不是混装线的全部目标。
关键词：
混装线，第二类平衡问题，启发式工作站
一、 简介
单一的装配线已经不能适应客户不断提升的期望和为了满足大量客制化需求而进行的工业产能平行化。有多变种的模型可以吸引足够的客户以达到装配系统的盈利使用。变种一般仅仅是特殊定制的模型属性不同而都是同一模型平台的衍生物。两种模型的准备时间很小，可以忽略，最终这些模型可以安排在同一生产线混流装配。
设计装配线要考虑平衡过程，也就是工作元素向工作站的分配。装配线常用的目标函数为利用率的最大化。通过在给定的循环时间内最小少工作站数目（type-I ）或者在工作站给定的情况下使循环时间最小化（type-II ）。
不能将最小化循环时间（或工作站数量）当作混装条件下的唯一目标。阻塞和空闲：因不同模型到达生产线而造成（在工作站中装配时间各不相同）；使得准确评估装配线的吞吐量变得非常困难。工作站耗时严重依赖于所装配的不同模型，这会引起相应的短期混流排序问题（MSP ）。因为MSP 问题，人们要找到模型单元的投送顺序，以满足短期计划周期的模型流程所给定的要求，并优化某些目标。这些目标主要针对的是因多种模型的站内时间不同而造成的效率低下问题。
混合装配线平衡问题和排序问题（MSP ）相互依存。一些学者建议同事考虑这两个问题。但是，这些问题通常源于不同的订单，有着特定的不同数据，因此排序问题会因每个订单、每天、每周的不同而出现。同时优化一般是不可行的，如它们通常会有完全不同的时间框架。 在更高的平衡水平上使用分层计划方法来预测排序结果看起来更加有意义。平衡化阶段的可变性目标已在文献【2,3,9,10】中提出，以减少在分层计划方法中安排排序所遇到的困难。
值得注意的另一个问题是，在JIT 条件下，混装线要满足不断变化的动态要求。所以，JIT 条件下装配线的设计过程不强调排序问题，其主要研究对象是平衡问题。
目前一些企业中的现有装配线需要解决方法，而这些方法不应是减少现有工作站，甚至当设备造价昂贵时还不得不增加工作站。
二、 方法
本文致力于开发简单的启发式而非构造数学模型并以优化技术来解决问题。由于装配线平衡问题是NP 难题，启发式过程通常用以避免维数问题，通过构建单一可行解。所以，是单一平衡。快速高效的启发式对于装配线平衡是有效的工具，因为一个可行解关注于所给工作站的数量和循环时间，在现实中，它的获取一般较容易。Gumussoy 和Kabak 研究了最优解的应用问题，这些最优解可以通过启发式方法来解决实际ALB 问题，如Ranked Positional Weight(RPW)。参考工业实例，他们在论文中指出，一些最优解的寻找方法根本不能解决问题，如二进制公式和最短路径公式。
一种解决MALBP 的方法是：绘制一个应用于所有模型及其平均任务次数的公用优先级图，以获得等效的单模型问题。这种从混合模型数据到单一平均模型数据的简单转化，确保了循环时间对于完成所有模型是足够的。但是，即使使用了平均模型的最优解，在实际的装配线操作过程中无疑会产生效率低下的问题。
本文中，尽管公用的优先级图用于定义所有优先级关系，但是当且仅当个体模型的任务次数少于或等于工作站中对应模型的可用时间时，才向工作站中分配任务。这种与简单地平均任务时间在方法上的差异，用于量化整条装配线在平衡阶段自身的效率低下问题，从而启发式过程可以试着消除，至少是减少这样的效率低下问题。
起初，工作站对于每个模型的可用时间被当做循环时间。工作站可用时间用一个行向量表示，其各列的数值与模型数相同。任务分配之后，用于进一步分配的可用时间（工作站中，对于每个模型的），将通过从工作站可用时间中减去模型任务时间计算得出。
A. 面向启发式的工作站
第一步：输入工作站数（Nw ），模型数（Nm ），所有模型的所有任务时间，以及任务优先关系。 第二步：设定循环时间，作为所有模型理论最小循环时间的最大值。
第三步：分配循环时间值，作为所有工作站的可用时间。
第四步：打开1号工作站，分配任务。
第五步：找到可分配的任务。可分配的任务都应有前续工作站，并且其所有任务时间应小于
工作站相应模型的可用时间。
第六步：令可分配的任务编号为Na 。
a ．
1. 如Na=0，则： 如果现有工作站数位Nw ，或现有工作站的单个模型的累积空闲时间多于相应模型
的允许空闲时间，则舍弃所有任务分配，循环时间增量1，返回第三步。
2. 否则，开启下一工作站并分配，到第五步。
b. 如Na=1，向现有工作站中分配任务。
c. 如Na>1，将可分配的任务根据所用的优先级规则按照升序/降序排列，并将列表
中的第一个任务分配给当前工作站。
第七步：从上一步的可用时间中减去已分配了的任务中所有模型的任务时间，得到新的可用
时间。重复5-7步，直到所有任务分配到给出的工作站中。
B. 优先级
上述的启发式过程使用优先级来构建操作顺序，根据该顺序向工作站中分配操作。仅仅最小化循环时间不能作为MALBP-II 的有效目标，因为工作站的平滑工作分配更加重要。因此，本文中的优先级利用循环时间、模型多样性、工作站多样性，或者是三种操作对象的结合来指导启发式过程。处理装配时间多样的Bottleneck 法也可以考虑来构建优先级规则。
第一优先级规则，即Mean Positional Weight（MPW ）规则是一种改进Ranked
Positional Weight（RPW ）规则。RPW 用于解决混流ALB 问题，但须通过平均模型任务时间，将他们转化为等效的单一模型问题。 第二优先级规则是Base Model Variability（BMV ），旨在最小化模型多样性。BMV 基于逻辑学，如果混装线上的个体问题可以近似地平衡为他们各自的最优循环时间，那么MALBP 的解可作为一条装配线的解。 第三条规则基于工作站的工位多样性来优先化任务，根据该工作站的分配任务，叫做Task Prioritization using Station Variability（TPSV ）。 第四条规则综合了MPW 和BMV ，第五条规则综合了MPW 和TPSV ，而第六条规则融合了这三类方法。第七条优先级规则是改进型Bottleneck 方法。Bottleneck 方法由Bukchin 提出，他同时指出该方法在混流条件下等效仿真装配线方面要优于其他方法。值得注意的是，他并没有使用Bottleneck 法来获取平衡解方案，而是等效仿真混装线的流程。Bukchin 也在三段式平衡启发式中应用该方法，但仅针对基于临近搜索的方案改进过程。本文中，我们尝试改进Bottleneck 方法，以适应任务的优先级，并将其命名为Bottleneck Priority Rule（BPR ）。
本方法的新颖之处是利用模型可变性，工位可变性和瓶颈方法当做优先级规则。据我们所知，这是第一次在启发式中利用它们作为优先级规则来获取平衡方案。但是，应该注意到，该优先级规则是从早期的方法中派生出来的。
下面是优先级的描述：
Nw 工作站数量
Nm 模型数量
Ntk 任务总数
ntk 任务时间非零的模型数
t tk ，m 模型m 的‘tk ’任务时间
S tk 任务‘tk ’的所有后续任务集
Twm 在工作站‘w ’中的模型‘m ’的站内时间
T wm ’（平均） 工作站‘w ’的平均站内时间。
Tm 模型‘m ’的理论最小循环时间。
cw 已分配任务的当前工作站
X N ‘X ’的规范化值
B1. Mean positional Weight（MPW ）
在有相关任务分配的模型中， 对于每个模型来说，一项任务的位置权重会单独计算出来，然后除以模型数量得到平均值，有关的任务会呈现在这里。对于没有相关任务的某个模型‘m ’，任务的位置权重置零。对于没有任务的模型‘m ’，位置权重看作0.
然后将任务的MPW 规范值取为：
将任务按照其规范化的MPW 值降序排列。
B2. Base Model Variability（BMV ）
任务的BMV 作为所有单个模型可变性数值的最大值。单个模型可变性数值这样算出：’M ’模型的所有站内时间与理论最小循环时间的平方差。T wm 包括任务‘tk ’的任务时间。任务根据规范化BMV 数值升序排列。
B3. Task Prioritization using Station Variability（TPSV ）
站的变化值被当做当前工作站站内时间的标准偏差，而任务‘tk ’正考虑分配入该工作站。而且，Twm 包括任务‘tk ’的任务次数。
TPSV 值同样被规范化并以升序排列来确定任务优先级。
B4. MPW结合BMV （PWMV ）
B5. MPW结合TPSV （PWSV ）
B6. MPW结合BMV 和TPSV （PWMSV ）
按照B4—B6的优先级规则，以降序对任务进行排列。
B7. 基于Bukchin 的公式，可以定义TBD （time between departures）的预期时间：
任务按照他们的规范化E （TBD ）值以升序排列，这些数值可认为是所以模型的平均循环时间。
三、实例
为了评估面向启发式和优先级规则的工作站的应用情况，引入一个包括十个问题的数据集。图1-4的联合优先图表示了使用从文献【16】【1】【15】【17】【11】中得到任务次数和优先关系数据的这些问题。尽管【16】和【1】的联合优先图的数据相同，但是模型的数量不同，这使得它们是不同的两个问题。工作站数量的两个不同数值引入到上述五个问题实例中。Table1 列举了十个问题：
四、结果和结论
图一：实例1-4的联合优先图
图二： For 实例5和6
图三：For 实例7和8
图四： For 实例9和10
图5-8表示4个目标，即循环时间，模型多样化，工作站多样化和最大完工时间。每一个最大完工时间的获得是通过选择启动模型的最佳序列。循环时间的显示结果表明，基于位置权重或位置权重与模型可变、工作站可变结合的优先级规则，比单独基于模型或工作站可变、瓶颈方法表现的更好。BPR 在循环时间和模型可变方面表现更差，但是与其他优先规则相比，它在最大完工时间方面是可作为参考的，在某些实例中甚至更好。
图5 循环时间
图6 模型可变
图7 工作站可变
图8最大完工时间
优先规则表现的良好的模型可变性是振奋人心的。注意到模型可变的最优解可以通过对每个某型单独做平衡得到，它也是工作站可变的最优解，但反之不成立。工作站可变和最大完工时间的可比较的结果是很有趣的。然后以稍后得到的单个模型的平衡为基础，对所有十个问题的优先规则的表现做了比较。这种评估的两个有代表性的案例在图9、10中给出。
M3W3SM
M2W7GK
单独使用MPW ，或BMV 和TPSV 联合使用要胜过其他规则，因为它有着更低的平衡延迟值。这样的解决方案意味着生产线上更少的阻塞和空闲，会得到更高的效率。基于上述分析，可以得出这样的结论：作为MALBP-II 的平衡方法，MPW （某些问题的PWMV ）表现出很好的应用潜力。