Abstract: Aiming at the virtual resequencing problem frequently raised in automobile paint shops,a 0-1 integer programming model was developed with the objective to minimize the number of color changes in the sequence of car bodies in white.A directed acyclic graph was used to represent virtual resequencing process,which was then converted to a shortest path problem.A beam search algorithm was proposed for solving this problem.During search process,both a local and a global evaluation functions were applied in selecting promising nodes.Problem instances with different parameter combinations were used to test the performance of the proposed algorithm.Computational results showed that the algorithm could significantly reduce the number of color changes in the initial sequence.Furthermore,it could result in better solutions than a simple rule-based beam search algorithm in the literature.

Key words: automobile mixed-model assembly lines, virtual resequencing, integer programming, beam search

摘要： 针对汽车涂装车间经常遇到的虚拟重排序问题,以最小化车辆生产序列中的颜色改变次数为目标建立了0-1整数规划模型,并采用一个有向无圈图来描述虚拟重排过程,将其转化成最短路径问题,进而提出求解该问题的束搜索算法。搜索过程中利用局部和全局评价函数对节点进行择优选取。采用不同参数组合的设计算例验证所提算法的性能,结果表明,该算法可以显著降低初始序列中的颜色改变次数,并且求解质量优于文献中已有的基于简单规则的束搜索算法。

关键词: 汽车混装线, 虚拟重排序, 整数规划, 束搜索