，*

（1.西华师范大学数学与信息学院，四川南充 637009；2.西华师范大学计算方法及应用软件研究所，四川南充 637009）

0 引言

汽车产业的飞速发展使得汽配件的生产呈现爆发性增长。外观类汽配件通常需要进行颜色喷涂，这样既能满足顾客对汽车外观的审美需求，也能确保汽车在自然环境条件下的耐用性需求。生产线上的汽配件喷涂颜色时，若前后相邻两个汽配件需要喷涂不同的面漆色，则称为一次“换色”，此时需要更换喷枪的涂料颜色，换色次数的多少会影响生产成本。

上述情形可称为汽配件颜色喷涂顺序问题，本文选取比较常见的一种环形喷涂生产线，如图1 所示，生产线上设置有一定数量的滑橇，有特定的换件处和喷涂处。汽配件被依次安装在滑橇上，随滑橇在轨道上移到喷涂处进行喷色，当移到换件处则将其取下。

图1 汽配件喷涂生产线Fig.1 Spraying production line for auto parts

在实际生产过程中，某些类别的汽配件由于形状等因素会导致不能相邻排列、某些颜色的汽配件由于颜色原料的特定要求会导致不能相邻排列，这些因素都会影响到颜色切换次数进而影响到生产成本，因此，研究和优化一批生产任务内的汽配件序列，可以理论指导生产实践并帮助企业提高生产效率、降低生产成本。

上述问题实质上是一类产品加工顺序问题，也可看作是一类柔性作业车间调度问题。通常遇到这类调度问题首先考虑到用经典的动态规划方法来对问题进行求解，但动……