摘 要：针对多品种小批量生产环境下的印刷电路板组装调度优化问题，考虑到在组装时间构成中占有极其重要地位的切换时间不仅具有其他制造业中常见的顺序依赖性，还具有特殊的沿用性，建立了以包括切换时间在内的多品种平均流程时间最小化为目标的调度优化模型，基于问题自身的特点以及这种特殊的切换后效性，分别针对印刷电路板成组、元件负荷分配、供料器切换、以及印刷电路板排序4个子问题开发了相应的算法并基于其内在联系进行了系统集成，通过仿真实验及其与现行研究的对比验证了模型与算法的有效性及可行性。
关键词：印刷电路板；多品种小批量；切换后效性；流程时间下界值；遗传算法
1 问题描述
1.1 PCB组装调度问题及其分类
在印刷电路板（Printed Circuit Board，PCB）的生产过程中，电子元器件的贴装是整条生产线的瓶颈，决定着整条生产线的生产效率［1］。PCB生产者从客户处接收的订单品种不一、批量各异，且交货期限不同，要获得最大利润，就要在生产过程中最小化各订单作业的平均流程时间，以此来最大限度地满足客户需求。
JOHNSON和SMED［2］根据PCB的种类数及机器台数，将其生产调度问题分为如下4个层次：
（1）单机单品种问题（1－1） 涉及单机优化问题，其目标为总的贴装时间最小化［3－4］。
（2）单机多品种问题（1－M） 涉及单机多品种间的切换策略问题，其目标为贴片机的切换时间最小化［5－6］。
（3）多机单品种问题（M－1） 涉及将PCB所需要贴装的元件在各台机器上的负荷分配问题，其目标为均衡分配生产线上各台贴装机的工作负荷［7－8］。
（4）多机多品种问题（M－M） 涉及（1）～（3）的所有问题。
本文解决的正是第4个层次的多机多品种的优化问题。
1.2 PCB组装的切换时间及特殊性
电子产品的组装因其元器件的数量庞大、品种繁多以及电子产品寿命周期短等特点，给生产运作调度带来了巨大的挑战，多品种、小批量、变批量已经成为电子制造的主流生产模式。在这种模式下，多品种之间的切换时间在整个组装时间中占据着越来越大的比重。
图1为典型的表面贴装技术（Surface Mounting Technology，SMT）生产线的缩略示意图，由高速贴片机和多功能贴片机组成。事实上，整条PCB组装流水线还包括送板机、丝网印刷机、点胶机、再流焊及固化炉、收板机等设备，这些设备串联起来组成PCB组装流水线，但这些辅助设备并不构成整条流水线的瓶颈工序，因而在建模时予以省略。每台贴片机能够容纳20个供料槽位，每种元件占据贴片机上的一个供料槽位。一般而言，单品种PCB所需要的元件种类数不超过供料器的容量，但多品种PCB所需的元件种类总数通常超出供料器的容量。贴装过程中不同品种PCB所需要的元件被安置在这些供料槽上，取贴装置从供料槽上取下元件后贴装到PCB上指定的位置。根据对实证研究对象的调查数据，高速贴片机平均贴装一个元件的时间为0.06 s，平均切换一个供料槽的时间为180 s。多功能贴片机有两个工作台，但只有一个工作台工作，另外一个工作台只用于放置大型或异型元件，每个工作台容纳10个供料槽，平均贴装一个元件需要0.18 s，平均切换一个供料器的时间为220 s。在不同品种的PCB间切换时，贴片机都需要一定的准备切换时间，通常为切换一个元件供料槽时间的6倍左右，即1 200 s。由此可见，切换时间在电子产品组装过程中具有举足轻重的地位。
在多品种小批量环境下，通常先对PCB进行分组，将具有相似特征的PCB分为一组，这样，在同一组内，不同品种PCB之间的组装不需要更换供料器，也不需要切换时间；但当两组PCB之间需要更换供料器时，则需要考虑它们之间的切换时间。据此将PCB的生产调度问题分为两个层次：第一层次的调度问题称为“板级”调度问题，即确定一个PCB组内的各PCB间的生产顺序；第二层次的调度问题称为“组级”调度问题，即确定PCB组织间的生产顺序。
对于给定的任何PCB组间的生产顺序，其切换时间不仅受它紧前的PCB组影响（sequence dependent setups），还与它之前的所有PCB组都有关系（carryover setups），这是因为前面各组PCB组装所需要的各种元器件在组装下一组PCB前并不是完全卸下来，而是部分卸下来，后续需要的元器件可以保留下来而无需切换。本文将兼具这两种性质的切换称为具有后效性的切换。这一切换特点在电子制造业普遍存在，是有别于其他制造业的特殊性所在。
2 相关研究综述
由于生产线上的元件供料器容量的限制，多品种PCB在表面贴装生产线上生产时，避免不了元件供料器的切换问题。不同的切换策略导致生产线的组装效率也不尽相同。LEON和PETERS［9］将切换策略分为单一切换策略、成组切换策略、最小切换策略和部分切换策略四类，他们针对单机多品种PCB的生产环境，对各种切换策略进行比较，进而探讨各种切换策略的适用环境。GÜNTHER等［10］针对一种典型的表面贴装生产线，采用最小切换策略将PCB排序，使得每种PCB都与排产在其前面的PCB有最多的相同元件数，以减少元件切换时间。LOGENDRAN等［11］针对由两台贴片机组成的典型生产线优化问题进行了研究，在已知供料器配置的情况下对PCB进行分组，然后采用最小切换策略来切换元件，最后利用禁忌搜索算法求解最优的PCB组间贴装顺序。ASHAYERI和SELEN［12］提出了两种切换策略，优化了PCB贴装排序以及元件在各台贴片机上的负荷分配问题。
关于第4个层次的多机多品种的优化问题，上述现行研究均仅研究了其中的1～2个子问题，并未进行集成研究，因而也就不能实现整体调度优化。
靳志宏等［13－14］鉴于多品种、小批量生产环境下的切换时间在整个组装时间中占有极其重要的地位，建立了以包括切换时间在内的多品种平均流程时间最小化为目标的调度优化模型；将该优化问题分解为元件负荷分配、PCB成组、供料器切换以及PCB排序4个子问题，开发了主动禁忌搜索算法，分组间搜索和组内搜索两个层次对PCB的排序问题进行优化，在此基础上进行了算法集成，并通过与理论下界值比较的仿真实验显示了模型与算法的有效性。
本文将在前期研究［13－14］的基础上，针对多品种小批量生产环境下的切换时间后效性问题，有针对性地利用电子制造领域切换后效性问题自身的特点，设计特殊的遗传算法编码方式以及相应的演算子，在缩短切换时间的基础上，实现印刷电路板表面贴装生产线调度流程时间的整体优化。
3 问题建模
在考虑PCB生产过程中切换后效性这一特点的基础上，对多品种、少批量生产环境下的单条生产线的组装调度问题进行建模。整个问题可以分为PCB成组问题、组装线上贴片机负荷均衡问题、每台贴片机供料器分配问题、每台贴片机元器件贴装顺序问题四个子问题。这四个子问题相互联系，相互影响。
3.1 参数与变量说明
（1）参数
i为PCB种类编号，i＝1，2，…，I；
c为元器件种类编号，c＝1，2，…，C；
m为贴片机编号，m＝1，2，其中，m＝1表示高速贴片机，m＝2表示多功能贴片机；
sm为贴片机m 上的供料槽编号，s＝1，2，…，Sm；
g为PCB组编号，g＝1，2，…，G；
f为供料器的类型编号（按供料器占用供料槽的数量分类，即如果供料器占用一个供料槽，则f＝1，依此类推），f＝1，2，…，F，如果用来装载元器件c的供料器类型为f，则令r（c）＝f；
ni为PCB品种i的生产批量；
nic为PCB品种i需要的元器件c的数量；
tmc为贴片机m贴装元器件c的单位贴装时间；
为贴片机m上供料器的平均切换时间；
为贴片机m上，从PCB组g到组k的切换时间与贴装组k的贴片时间之和，g，k∈｛1，2，…，G｝。
（2）决策变量
如果PCB板i属于组g，则x ig＝1，否则x ig＝0；
如果PCB组g在组间生产序列中处于k位置，则y gk＝1，否则y gk＝0；
如果PCB组g内品种i在组内生产序列中处于k位置，则
＝1，否则
＝0。
（3）取决于决策变量的状态变量
为PCB品种i在贴片机上的完工时刻；
为反映贴片机供料器配置的状态向量，贴装PCB品种i时，贴片机m上供料槽上的元器件分布；如果供料槽上没有任何供料器，则该分量为0。例如，1号供料槽上的供料器装载的元器件种类为2，2号供料槽上没有任何供料器，则
＝［2，0，…］；
为反映贴片机供料器配置的状态向量，类似于
，表示贴片机m贴装完PCB组g后，贴片机供料槽上的元器件分布状态，
表示贴片机上供料槽的初始状态。
为表示贴片机的切换状态向量，即当贴片机m从PCB组g切换到组k时，如果向量和
在某一分量上不同，则Q mgk上的对应分量为1（即此时需要切换该分量对应的元器件），否则为0（也即无需切换该分量对应的元器件）。
3.2 数学建模
目标函数（式（1））为最小化所有PCB的平均流程时间，其中ε为一任意小的正数；式（2）表示对于每一种PCB，为其装载所需的元器件的供料器所占的供料槽不超出贴片机的供料槽数量；式（3）表示相似的PCB品种分成一组后，所需的元器件在贴片机上的分布为该组内包含的PCB的元器件分布的并集；式（4）表示对于每一组PCB，为其装载所需的元器件的供料器所占的供料槽不超出贴片机上的供料槽数量；式（5）与式（6）为生产线平衡条件；式（7）表示PCB所需的同类元器件只在一台贴片机上贴装；式（8）～式（10）为PCB在机器上的生产完工时刻之间的约束；式（11）表示同类PCB都将归类于同一组PCB内；式（12）～式（13）表示PCB组与其在生产序列中的位置的一一对应关系；式（14）～式（15）表示组内PCB与其在生产序列中的位置的一一对应关系；式（16）为0-1变量约束。
4 基于切换后效性的遗传算法设计
4.1 关于切换后效性的优化算法综述
制造业中传统的切换包括顺序依赖切换（sequence dependent setup）、累积顺序切换（past sequence setup）以及延用性切换（carryover setup）等。LEON和PETERS［15］率先揭示了电子制造领域切换时间的独特性，即sequence dependent carryover setup，指出这种切换不仅具有顺序依赖性，还具有延用性，兼具这两种性质的切换与单纯的顺序依赖切换不同，即每次的切换时间不仅与前一次切换相关，还与之前的所有切换经历有关；同时，还与累积顺序切换不同，即第n次的切换时间不仅包括前n－1次切换所累积的经验导致单位切换作业时间的减少，还取决于前n－1次切换的状态链。鉴于中文文献对这类切换尚无统一称谓，本文姑且称其为具有后效性的切换。鉴于切换后效性问题的复杂性，LEON和PETERS［15］仅提供了一种关于其切换时间的简单估计算法。其他相关研究的对象组装机是较为落后的单帖片头的高速机与多功能机型，贴装效率较低。以目前最先进的大型并行系统为对象的相关研究尚未见报道。
国内在该领域的研究比较匮乏，早在2000年，高玉波［16］分析了一般制造业中的延用性切换，并将其称为“准备费用延用”，同时提出了一种启发式算法forward pass heuristic，对多品种产品组装顺序进行优化。这也是目前所能收集到的唯一一篇关于延用性切换的中文文献，此后10年未见相关跟进研究。最近，刘海明等［17］针对PCB组装过程中的sequence dependent setup，提出了一种贪婪算法，用以优化不同品种间的切换时间。刘海明等［18］针对同一问题提出了一种基于最近近邻与2-opt相结合的混合算法。这两项研究成果均考虑的是前后相邻两品种间的切换时间，并未考虑切换时间的carryover问题。
本文基于切换后效性问题自身的特点开发了相应的遗传算法，通过来源于现场数据的仿真实验，并与前期研究［13－14］以及一般的遗传算法进行了对比分析。
4.2 基于切换后效性的演算子设计
4.2.1 编码表示和适应度函数选择
用一个阿拉伯数字表示一种PCB，即｛1，2，…，i，…，I｝表示PCB种类集合，如向量［3，6，1，2，5，4］表示一个PCB板生产序列。用英文大写字母表示一个PCB组，例如：A＝｛2，4，6｝，B＝｛1，3｝，C＝｛5｝表示A组中包含2，4和6这三类PCB板，其他依次类推。字母序列BAC表示这三组PCB的生产序列。
适应度函数f i＝Tmax－Ti，其中Tmax为PCB完工时刻的估计最大值，Ti为PCB品种i的完工时刻。
4.2.2 交叉演算子设计
传统的单点交叉等遗传算法演算子在本问题中并不适宜，极易产生非可行解。针对切换后效性问题自身的特点，采用部分映射交叉算子：在染色体中随机产生两个交叉点，然后交换父代染色体交叉点之间的部分，如果生成的子染色体中有非法的重复部分，则用交叉部分对应的基因替换交叉点两侧的基因。如对于两个染色体父代1和2，其部分映射交叉操作如下：父代1：ADB｜C｜FE、父代2：BAE｜F｜CD，产生非法后代1：ADBFFE、非法后代2：BAECCD，通过交换后得到合法的子代1：ADBFCE和子代2：BAECFD。在这一过程中，非法后代1和后代2是染色体交叉操作中的过渡状态。
这种演算子的设计充分地反映了不同品种PCB之间由于所需元器件有相当一部分是完全一致的，在供料器上无需全部切换、仅需部分切换这一事实。
4.2.3 变异演算子设计
针对切换后效性的特点，设计了一种子序列变异算子。所谓子序列变异，就是针对某PCB组生产顺序，随机选择其中的一个子序列，然后仅对其所在的生产顺序进行改变，其他子序列则保持不变。这样既达到了对PCB组顺序进行改变的目的，同时也维持了其他部分PCB组的子序列的相对生产顺序不变，体现了PCB生产中的切换后效特性。例如某组装顺序序列变异前为ADBCFEHG，现随机选中了子序列DB为变异子序列，对其进行变异，假设变异点为F，把子序列DB插入到该PCB组后，则变异后的组装顺序序列为ACFDBEHG。
4.2.4 算法集成
整条组装流水线的调度优化问题可以分解成PCB成组、元件负荷分配、供料器切换以及PCB组装排序4个子问题，这些子问题相互关联、相互影响。根据内在联系对其进行集成。其中，PCB成组基于作者提出的相对相似系数［13］、元件在贴片机间的负荷分配参见前期研究［7］、供料器切换采用成组切换与部分切换（KTNS）相结合的混合切换策略［5，13］，PCB组间及组内排序采用4.2.1节～4.2.3节设计的遗传算法，整个集成算法流程如图2所示。
5 仿真算例
5.1 基于实际生产订单的仿真算例
用从生产实际中取得的数据进行模拟实验。PCB种类数为24种，各种类的生产批量和所需元器件等参数如表1和表2所示，实验平台采用了MATLAB平台。
表1 仿真算例参数
表2 各品种PCB的元器件需求清单
5.2 结果分析
针对上述现实规模问题，本文开发的遗传算法种群大小取100，最大进化代数取200，交叉概率为0.9，变异概率为0.1。算法运行得到了该实例的最优PCB生产序列：11，3，8，5，7，12，10，1，6，2，4，9，15，16，21，19，17，14，22，20，13，18，24，23。
鉴于切换后效性具有机器依赖的特征（machine-dependent setup），也即其品种切换方式（切换时间）取决于机器本身的结构与特点，而现行研究的对象组装机大都为落后的单帖片头的高速机与多功能机，为使比较具有客观可比性的基础，仅选取同为以目前最为先进的大型并行系统为研究对象的相关研究的结果进行直接比较。
表3为本文开发的算法与靳志宏等［14］所开发的禁忌搜索算法以及没有考虑切换后效性的遗传算法所得出的结果的直接比较。由表3可以看出，本文所开发的算法所得到的平均流程时间是三种算法中最短的。显示了切换时间在多品种小批量生产环境下的关键作用，同时也显示了考虑切换时间后效性的遗传演算子的设计是实用而有效的。尽管与禁忌搜索算法以及没有考虑切换后效性的一般遗传算法相比，得到近似最优解所用的时间稍长，但对于现实规模问题而言，其运行时间仍在可容忍的范围内，证实了算法的有效性与实用性。
表3 三种算法的实验结果比较
6 结束语
本文针对多品种小批量生产环境下的PCB组装生产中存在的切换后效性问题，建立了以包括切换时间在内的多品种平均流程时间最小化为目标的调度优化模型，基于问题自身的特点开发了相应的遗传算法，并在此基础上进行了算法集成。通过来源于现场数据的仿真实验及其与现行研究的对比，显示了模型与算法的有效性以及现实应用可行性。
进一步的研究方向是，在对单条组装流水线的生产调度优化的基础上，针对多条平行的生产线构成的生产系统进行整体调度优化。
