基于改进分散搜索的混流装配线排序问题

Advanced scatter search approach for sequencing problems in mixed model assembly lines

针对混流装配线生产效率问题,设计了以最小化工作站的闲置与超载时间和最小化总调整变换时间为优化目标的数学模型。为得到高质量且平稳性好的解,提出了适应该模型求解的改进分散搜索算法。该算法首次应用一种基于遗传理论的多样性初始解生成法,不但保证了初始种群的多样性,而且为参考集提供了高质量的初始解。设计了参考集生成更新方法、子集产生方法、子集合并方法和优化解方法等多种机制,既保持了种群的多样性,又寻求到了质量较高的满意解。通过某企业混流装配线实例,验证了所设计算法的有效性。

To deal with production efficiency of mixed model assembly line,a mathematical model aiming to minimize over-time and idle-time and total setup cost simultaneously was set up.In order to obtain high quality and stable solutions,an advanced Scatter Search（SS） algorithm was proposed.And a new diversified generation method based on Genetic Algorithm（GA） was applied in this algorithm to generate a set of potentially diversified and high-quality initial solutions.At the same time,various mechanisms for the reference set were designed such as generation and update method,subset generation method,solution merge method and improvement method which not only kept the diversity of the population but also obtained high-quality satisfactory solution.The proposed model and algorithm were applied and validated in a company.The result indicated that the proposed advanced scatter search approach was feasible and effective.