混合装配线平衡问题的启发式过程Word格式.docx
《混合装配线平衡问题的启发式过程Word格式.docx》由会员分享,可在线阅读,更多相关《混合装配线平衡问题的启发式过程Word格式.docx(12页珍藏版)》请在冰点文库上搜索。
变种一般仅仅是特殊定制的模型属性不同而都是同一模型平台的衍生物。
两种模型的准备时间很小,可以忽略,最终这些模型可以安排在同一生产线混流装配。
设计装配线要考虑平衡过程,也就是工作元素向工作站的分配。
装配线常用的目标函数为利用率的最大化。
通过在给定的循环时间内最小少工作站数目(type-I)或者在工作站给定的情况下使循环时间最小化(type-II)。
不能将最小化循环时间(或工作站数量)当作混装条件下的唯一目标。
阻塞和空闲:
因不同模型到达生产线而造成(在工作站中装配时间各不相同);
使得准确评估装配线的吞吐量变得非常困难。
工作站耗时严重依赖于所装配的不同模型,这会引起相应的短期混流排序问题(MSP)。
因为MSP问题,人们要找到模型单元的投送顺序,以满足短期计划周期的模型流程所给定的要求,并优化某些目标。
这些目标主要针对的是因多种模型的站内时间不同而造成的效率低下问题。
混合装配线平衡问题和排序问题(MSP)相互依存。
一些学者建议同事考虑这两个问题。
但是,这些问题通常源于不同的订单,有着特定的不同数据,因此排序问题会因每个订单、每天、每周的不同而出现。
同时优化一般是不可行的,如它们通常会有完全不同的时间框架。
在更高的平衡水平上使用分层计划方法来预测排序结果看起来更加有意义。
平衡化阶段的可变性目标已在文献【2,3,9,10】中提出,以减少在分层计划方法中安排排序所遇到的困难。
值得注意的另一个问题是,在JIT条件下,混装线要满足不断变化的动态要求。
所以,JIT条件下装配线的设计过程不强调排序问题,其主要研究对象是平衡问题。
目前一些企业中的现有装配线需要解决方法,而这些方法不应是减少现有工作站,甚至当设备造价昂贵时还不得不增加工作站。
二、方法
本文致力于开发简单的启发式而非构造数学模型并以优化技术来解决问题。
由于装配线平衡问题是NP难题,启发式过程通常用以避免维数问题,通过构建单一可行解。
所以,是单一平衡。
快速高效的启发式对于装配线平衡是有效的工具,因为一个可行解关注于所给工作站的数量和循环时间,在现实中,它的获取一般较容易。
Gumussoy和Kabak研究了最优解的应用问题,这些最优解可以通过启发式方法来解决实际ALB问题,如RankedPositionalWeight(RPW)。
参考工业实例,他们在论文中指出,一些最优解的寻找方法根本不能解决问题,如二进制公式和最短路径公式。
一种解决MALBP的方法是:
绘制一个应用于所有模型及其平均任务次数的公用优先级图,以获得等效的单模型问题。
这种从混合模型数据到单一平均模型数据的简单转化,确保了循环时间对于完成所有模型是足够的。
但是,即使使用了平均模型的最优解,在实际的装配线操作过程中无疑会产生效率低下的问题。
本文中,尽管公用的优先级图用于定义所有优先级关系,但是当且仅当个体模型的任务次数少于或等于工作站中对应模型的可用时间时,才向工作站中分配任务。
这种与简单地平均任务时间在方法上的差异,用于量化整条装配线在平衡阶段自身的效率低下问题,从而启发式过程可以试着消除,至少是减少这样的效率低下问题。
起初,工作站对于每个模型的可用时间被当做循环时间。
工作站可用时间用一个行向量表示,其各列的数值与模型数相同。
任务分配之后,用于进一步分配的可用时间(工作站中,对于每个模型的),将通过从工作站可用时间中减去模型任务时间计算得出。
A.面向启发式的工作站
第一步:
输入工作站数(Nw),模型数(Nm),所有模型的所有任务时间,以及任务优先关系。
第二步:
设定循环时间,作为所有模型理论最小循环时间的最大值。
第三步:
分配循环时间值,作为所有工作站的可用时间。
第四步:
打开1号工作站,分配任务。
第五步:
找到可分配的任务。
可分配的任务都应有前续工作站,并且其所有任务时间应小于工作站相应模型的可用时间。
第六步:
令可分配的任务编号为Na。
a.如Na=0,则:
1.如果现有工作站数位Nw,或现有工作站的单个模型的累积空闲时间多于相应模型的允许空闲时间,则舍弃所有任务分配,循环时间增量1,返回第三步。
2.否则,开启下一工作站并分配,到第五步。
b.如Na=1,向现有工作站中分配任务。
c.如Na>
1,将可分配的任务根据所用的优先级规则按照升序/降序排列,并将列表中的第一个任务分配给当前工作站。
第七步:
从上一步的可用时间中减去已分配了的任务中所有模型的任务时间,得到新的可用时间。
重复5-7步,直到所有任务分配到给出的工作站中。
B.优先级
上述的启发式过程使用优先级来构建操作顺序,根据该顺序向工作站中分配操作。
仅仅最小化循环时间不能作为MALBP-II的有效目标,因为工作站的平滑工作分配更加重要。
因此,本文中的优先级利用循环时间、模型多样性、工作站多样性,或者是三种操作对象的结合来指导启发式过程。
处理装配时间多样的Bottleneck法也可以考虑来构建优先级规则。
第一优先级规则,即MeanPositionalWeight(MPW)规则是一种改进RankedPositionalWeight(RPW)规则。
RPW用于解决混流ALB问题,但须通过平均模型任务时间,将他们转化为等效的单一模型问题。
第二优先级规则是BaseModelVariability(BMV),旨在最小化模型多样性。
BMV基于逻辑学,如果混装线上的个体问题可以近似地平衡为他们各自的最优循环时间,那么MALBP的解可作为一条装配线的解。
第三条规则基于工作站的工位多样性来优先化任务,根据该工作站的分配任务,叫做TaskPrioritizationusingStationVariability(TPSV)。
第四条规则综合了MPW和BMV,第五条规则综合了MPW和TPSV,而第六条规则融合了这三类方法。
第七条优先级规则是改进型Bottleneck方法。
Bottleneck方法由Bukchin提出,他同时指出该方法在混流条件下等效仿真装配线方面要优于其他方法。
值得注意的是,他并没有使用Bottleneck法来获取平衡解方案,而是等效仿真混装线的流程。
Bukchin也在三段式平衡启发式中应用该方法,但仅针对基于临近搜索的方案改进过程。
本文中,我们尝试改进Bottleneck方法,以适应任务的优先级,并将其命名为BottleneckPriorityRule(BPR)。
本方法的新颖之处是利用模型可变性,工位可变性和瓶颈方法当做优先级规则。
据我们所知,这是第一次在启发式中利用它们作为优先级规则来获取平衡方案。
但是,应该注意到,该优先级规则是从早期的方法中派生出来的。
下面是优先级的描述:
Nw工作站数量
Nm模型数量
Ntk任务总数
ntk任务时间非零的模型数
ttk,m模型m的‘tk’任务时间
Stk任务‘tk’的所有后续任务集
Twm在工作站‘w’中的模型‘m’的站内时间
Twm’(平均)工作站‘w’的平均站内时间。
Tm模型‘m’的理论最小循环时间。
cw已分配任务的当前工作站
XN‘X’的规范化值
B1.MeanpositionalWeight(MPW)
在有相关任务分配的模型中,对于每个模型来说,一项任务的位置权重会单独计算出来,然后除以模型数量得到平均值,有关的任务会呈现在这里。
对于没有相关任务的某个模型‘m’,任务的位置权重置零。
对于没有任务的模型‘m’,位置权重看作0.
然后将任务的MPW规范值取为:
将任务按照其规范化的MPW值降序排列。
B2.BaseModelVariability(BMV)
任务的BMV作为所有单个模型可变性数值的最大值。
单个模型可变性数值这样算出:
’M’模型的所有站内时间与理论最小循环时间的平方差。
Twm包括任务‘tk’的任务时间。
任务根据规范化BMV数值升序排列。
B3.TaskPrioritizationusingStationVariability(TPSV)
站的变化值被当做当前工作站站内时间的标准偏差,而任务‘tk’正考虑分配入该工作站。
而且,Twm包括任务‘tk’的任务次数。
TPSV值同样被规范化并以升序排列来确定任务优先级。
B4.MPW结合BMV(PWMV)
B5.MPW结合TPSV(PWSV)
B6.MPW结合BMV和TPSV(PWMSV)
按照B4—B6的优先级规则,以降序对任务进行排列。
B7.基于Bukchin的公式,可以定义TBD(timebetweendepartures)的预期时间:
任务按照他们的规范化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)表现出很好的应用潜力。