张 光 前， 何 晓 飞

(大连理工大学 经济管理学院，辽宁 大连 116024)

0 引 言

在汽车涂装时，当两个即将面漆的车身喷不同颜色时，喷头必须重新清洗.为避免喷枪清洗以及更换涂料等过程所引发的高昂切换成本[1]，涂装车间希望相同颜色的车身尽量排在一起.通常，从上一车间出来的车身序列无法自然地满足这一要求，需对进入的车身序列进行一定调整，尽量满足涂装车间对车身序列的要求.这就形成了汽车涂装中的重排序问题.在汽车生产中，不同车间对车身序列的要求也各不相同，因此重排序问题普遍存在于汽车生产过程中.

重排序模式有两种：带缓冲区的物理重排序(physical re-sequencing)和不带缓冲区的虚拟重排序(virtual re-sequencing)[2-3].物理重排序是通过设置缓冲区(buffer)来调整序列，重排序后的个体在序列中的位置会发生改变.在虚拟重排序中，个体在序列中的位置不变，发生变化的是分配到个体上的属性，以此实现序列重排.本文关注的是虚拟重排序问题.

Epping等[4]将需要涂装的车身序列看成是由一串有色字母组成的单词，通过置换相同的字母得到一个颜色变化次数最少的单词(paint shop problem for words，PPW)，并采用动态规划的方法求解了该问题.Epping等也证明涂装的虚拟重排序问题是NPC(NP-complete)问题.随后，一些学者对PPW问题进行了研究，如对PPW问题的一种特殊情况，即二元PPW问题，Bonsma等[5]探讨了该问题的下界；Andres等[6]得出了二元PPW问题颜色转换的期望值；Gorbenko等[7]提出了PPW(2，1)问题求解算法.Inman等[8]研究了按单装配(assemble to order，ATO)敏捷系统中位于涂装……