多类约束下的随机混流U型拆卸线平衡排序问题优化

发布时间：2024-04-18 22:11

　　为提高混流产品拆卸效率,针对固定工作站数量约束、位置约束、优先关系约束,考虑任务操作完成时间的不确定性,建立了以最小化循环时间(Cycle Time,CT)和最小化工作站平均空闲时间为目标的混流U型拆卸线平衡排序问题的数学模型。结合混流拆卸线的具体特点,提出了一种改进的并行邻域搜索算法(Improved Parallel Neighborhood Search,IPNS),该算法定义两类不同的邻域结构,采用动态搜索策略,通过独立搜索以及直接交换邻域的方式以最大限度寻找最优解。最后,通过多个算例验证了算法的有效性。

【文章页数】：10 页

【部分图文】：

图１Ｕ型布局图数学模型

ｕｊ，σ２ｊ））（ｊ＝１，２，…，Ｔｉ）。ＳＭＵＤＬＢ／Ｓ问题是指将集合Ｓ’中的所有任务合理地分配到Ｕ型拆卸线的ＮＷＳ个工作站（如图１所示），使得ＣＴ和工作站平均空闲时间最小。本文以最小工件组ＭＰＳ作为基本的拆卸单元，则ＭＰＳ＝｛ａ１，ａ２，…，ａＭ｝，ａｉ＝Ａｉ／Ｇ，其中Ｇ表示....

图３染色体编码任务分配（）

Ｄ中删除任务１。此时，ＥＳ＝｛２，４，８｝。由于Ｈ８＞Ｈ２＞Ｈ４，则ＴＳ＝｛１，８｝，Ｏ＝｛２，３，４，５，６，７｝，并从上图Ｄ中删除任务８。以上步骤重复执行，直至集合Ｏ为空。最后，我们将图２中的任务编码为ＴＳ＝｛１，８，２，４，３，６，５，７｝。随机产生产品顺序ＰＳ＝｛２，０，....

图４ＣＴ值比较（ＮＷＳ低水平）

ｆｉｘｅｄ”表示不存在位置约束下ＩＰＮＳ的运行结果。从图４～图９中可以看出，由于不存在位置约束，解空间更大，能搜索到更好的最优解。此外，由图４～图６可以看出，在位置约束下，ＩＰＮＳ所得到的ＣＴ值的平均值都要小于ＰＮＳ的值，而大于无位置约束下的ＣＴ值的平均值；同时由图７～图９可知，....

图６ＣＴ值比较（ＮＷＳ高水平）

ＣＴ值比较（ＮＷＳ中水平）图１０表示ＩＰＮＳ在运行算例Ｐ（２０，８，８０）所取得的ＣＴ值与平均空闲时间值的比较。从图中可以看出，随着ＣＴ的减小，平均空闲时间呈现逐步减小的趋势。但当ＣＴ值从７１下降到７０时，平均空闲时间从４２２４２．８增大到４２９１４．５；同样地，当ＣＴ从６９下降....

本文编号：3957810