基本信息
- 项目名称：
- 带kick策略的TS算法在电子表面装贴分配问题中的应用
- 来源：
- 第十一届“挑战杯”国赛作品
- 小类：
- 信息技术
- 大类：
- 自然科学类学术论文
- 简介：
- 作品研究带有流水线调度和并行调度双重性质的表面装贴分配问题，其目标为最小化元器件的贴装时间。针对该NP难问题，提出了改进型的禁忌搜索算法进行求解。在该算法中，将传统的禁忌搜索算法融合了序优化算法与分散型的kick移动策略。实验结果表明，此算法能够有效地搜索出问题的近优解，缩短贴装时间，提高电子组装的生产效率。
- 详细介绍：
- 贴装设备是典型的高利用率设备，实现将元器件贴放在PCB板上。贴片设备一般是流水式的排列在电子组装生产线中，其价格昂贵，设备维护费用高，一般中小企业不轻易引入，被认为是电子组装生产线上的“瓶颈”机器。因此贴片机的贴装效率直接影响着整个组装生产线的效率。由于不同类型的贴片机可贴装的元器件范围、贴装速度、贴装质量上具有不同的特点，因此在贴装工序中，PCB板和元器件的生产安排有较大的优化空间，从而缩短生产完成时间，提高生产效率。 对PCB板和元器件的生产安排包括PCB板的生产顺序安排和元器件在不同贴片机上的分配，我们统称为电子表面贴装分配问题。该问题是一个强NP难问题。作品利用改进型的禁忌搜索算法去解决该问题。禁忌搜索算法是近年来受到普遍关注的一种高效率的现代智能启发式优化技术，对解决NP难的组合优化问题具有良好的效果。但传统的禁忌搜索算法存在它本身的缺陷和不足，如对初始解依赖性。作品根据传统禁忌搜索算法本身的不足和实际的表面贴装问题对算法进行改进，融合序优化的思想产生初始解和分散型kick移动策略协助算法跳出局部最优解。利用序优化的思想产生初始解，尽量弥补禁忌搜索算法对初始解的依赖性；引入分散型的kick移动策略，试图加强禁忌搜索算法的全局搜索能力。 实验结果表明，利用本文提出的改进型禁忌搜索算法去解决表面装贴分配问题可取得良好的效果，其算法结果优于多点下降算法和传统的禁忌搜索算法。此优化算法适用于多个贴片机同时工作的情况和各种不同的任务规模，具有很好的通用性。算法结果对提高电子组装的生产效率和信息化优化管理具有一定的应用价值和现实意义。
作品专业信息
撰写目的和基本思路
- 1)撰写目的: 在可接受的时间内寻找一个近优的PCB排序和元器件分配方案，最大限度地缩短贴装时间，达到提高生产效率的目的。 2)基本思路：采用基于禁忌搜索的智能优化算法去解决该问题。在禁忌搜索算法的基础上，融合序优化算法产生初始解和分散型kick策略协助算法跳出局部最优解，尽量弥补了禁忌搜索算法对初始解的依赖性，并试图加强禁忌搜索算法的全局搜索能力。
科学性、先进性及独特之处
- 作品所研究问题不是单纯的流水线调度或并行调度问题，而是一个新型的带有流水线调度和并行调度双重特性的优化问题。利用现代智能启发式的禁忌搜索算法，并融合了序优化思想产生初始解和分散型kick策略协助算法跳出局部最优解，有效地解决此表面贴装分配问题。所提出的优化算法明显优于多点下降算法和传统的禁忌搜索算法。
应用价值和现实意义
- 贴片机是电子组装生产线中的关键设备，实现元器件在PCB等基板上的贴装。作品研究元器件在多台流水放置的贴片机上的分配优化问题，对提高生产线效率，对生产线信息化优化管理具有一定的实际价值。作品提出的优化算法能在可接受的时间内有效地搜索出问题的满意解，尽可能地缩短贴装时间。此优化算法适用于多台贴片机流水线排列工作的情况，能解决稍大规模的电子表面贴装分配实例，具有较好的通用性和灵活性。
学术论文摘要
- 电子表面贴装分配问题是在电子组装过程中出现的生产优化问题，其任务是实现对PCB板的排序和元器件在不同贴片机上的分配。该问题具有流水式的并行机调度特点，为NP难问题。为更好地搜索出问题的好解，我们提出了一种改进型禁忌搜索算法，即在传统禁忌搜索算法的基础上融合了序优化算法特点和分散型kick移动策略。序优化算法的应用弥补了禁忌搜索算法对初始解具有较大的依赖性的不足；而分散型kick策略的引入则增强了禁忌搜索算法的全局搜索能力。实验结果表明，利用本文提出的改进型禁忌搜索算法去解决所研究问题可取得良好的效果。
获奖情况
- 1）作品获EI和ISTP检索，EI检索号：20091412011861，ISTP检索号：10416287。 2）作品论文的英文版本已被2008年在中国武汉举办的国际会议“IEEE亚太地区计算智能与工业应用研讨会（IEEE PACIIA 2008）”接收，会议由美国电子和电气工程师协会(IEEE)和美国电子和电气工程协会工业电子分会支持 (IEEE IES)，武汉工程大学主办。 3）第十届省赛“挑战杯”一等奖。
鉴定结果
- 在国内公开发表的中文文献中，未见涉及“针对电子贴装工序（具有流水式并行机调度特点）的分配问题，采用kick策略的禁忌搜索算法进行求优”的文献报道。
参考文献
- 现有技术： 禁忌搜索算法；序优化算法；kick移动策略。 １）禁忌搜索算法（TS）：TS的思想是利用存储结构存储搜索过程中的信息，在进一步的迭代搜索中尽量避开已搜索路径，提高搜索的分散性。TS收敛速度快，局部搜索能力强，但对初始解有较强的依赖性。 ２）序优化算法（OO）：OO算法通过从解空间中随机抽取一定数量的可行解组成表征集合，从而将对解空间的操作转移到表征集合上以实现优化目标，是一种统计优化方法。 ３）kick移动策略：kick策略是迭代局部搜索算法中跳出局部最优解的搜索策略，当算法陷入局部最优解时，对当前局部最优解进行移动，产生新的不同于当前解的新解，从而开始新的搜索过程。 技术文献检索目录见附件1。
同类课题研究水平概述
- 表面贴装工序为电子组装过程中的关键工序，是提高组装生产线效率的突破点。关于表面贴装生产优化的研究都集中在对单个贴片机的优化上，如上海交大对贴片机的贴装头路径优化研究[1]，而对生产线上多个贴片机之间的任务安排研究不多。在国外则有相对较多的研究成果，在算法上多采用启发式、遗传算法对问题进行求解，已取得了一些结果。但其研究多是将生产线中元器件的分配问题归结为并行机调度问题，而忽略了当贴片机流水线排列对元器件分配的影响。 Ji等[2]对多台不同贴片机上的PCB分配问题进行了研究。论文假设已知元器件类型在机器上的处理时间，由此建立了以最小化表面贴装完成时间为目标的整数规划模型，提出基于遗传算法的启发式算法进行求解。Ammons等[3]假定已知元器件类型在机器上的估计贴装时间，建立了整数规划模型，实现对元器件类型在机器上的分配，以最小化表面贴装的完成时间；并提出了基于链处理的启发式和基于线性规划的分支定界求解。与此研究不同，Kodek 和Krisper[4]另外还考虑了机器的启动时间，根据数学模型提出了问题的下界，构造了有效的分支定界算法搜索近优解。Müller-Hannemann和Weihe[5]则研究如何将元器件分配在多工作站上，证明了该问题为NP难问题，提出有效的启发式算法获得问题的近优解。 本作品的研究充分考虑了贴片机流水线放置的特性和元器件并行分配的特点，对电子表面贴装的分配优化问题进行研究。在算法研究方面，禁忌搜索算法的发展已经初步成熟，且其已经被国内外的学者们应用到各式各样的优化问题中去。但是，针对本文所研究的问题，禁忌搜索是否也能够像其在其他问题中一样发挥优势，是一个亟待探讨的问题。且国内外的学者们都意识到，禁忌搜索算法本身并不是很完美的，其对初始解的依赖性、其局部搜索的局限性等。因此本作品在尝试用禁忌搜索算法来解决所研究问题的同时也致力与对算法本身的改进。对算法的改进集中在改进初始解和局部搜索能力上面，将序优化思想应用于产生初始解，将迭代局部搜索算法的kick策略融入禁忌搜索算法，提高全局搜索能力。 总的来说，目前关于电子表面贴装分配问题的研究在国内研究不多，在国外的研究方法也比较单一，因此十分有必要采用新的搜索方法对其进行进一步的研究。 参考文献见附件2。
