多目标差异平行批调度问题的协同进化算法研究

作     者：王燕 

作者单位：安徽大学 

学位级别：硕士

导师姓名：贾兆红

授予年度：2020年

学科分类：080903[工学-微电子学与固体电子学] 12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 0809[工学-电子科学与技术（可授工学、理学学位）] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：批处理机调度 差异平行批处理机 蚁群算法 多种群协同进化 机器能耗 

摘      要：科技的进步和生产要求的提高导致制造业企业面临越来越大的生产压力,使得企业对新型生产调度方案的需求与日俱增。批调度生产是一种与实际生产环境紧密切合的生产调度模式,是传统生产调度问题的拓展。与传统生产调度相比,批调度生产模式能够提高生产效率和资源利用率。因此,针对批调度问题的研究能够为企业提高生产效率、增强企业市场核心竞争力和确定生产方案提供依据。在制造型企业中,不定期的机器更新使得在生产车间内存在新旧处理能力不同的机器同时加工的情况。在这种生产环境下,如何同时提高企业的生产效率和降低资源消耗率十分具有挑战性。本文以半导体制造业中芯片最后高温测试阶段为研究背景,将待测试芯片抽象成工件、高温烤箱抽象成批处理机,研究了在差异平行批处理机上调度一组带有不同尺寸、随机到达时间和不同加工时间的工件以最小化制造跨度和机器总能耗的问题。本文的主要研究内容如下:（1）针对本文研究的问题首先给出了具体的问题描述,并建立了一个混合整数规划模型。之后,通过对问题的分析,提出了一个针对问题特性的双蚁群协同进化算法进行求解。在双蚁群协同进化算法中,依据问题特征设计的启发式信息用于指导解的构建,并在利用双蚁群独立搜索的方式提高算法的多样性的同时,通过双蚁群之间协同搜索的方式保证算法的收敛性。最后通过仿真实验,验证了所提算法的有效性。（2）本文在深入分析双蚁群协同进化算法的性能后发现该算法在两个蚁群共同搜索的区域存在丢失有效解的问题,因此提出了一个多种群的双目标协同进化算法用以解决这一问题。该算法设计了一种基于最大角度设置偏好向量的策略和一种基于种群贡献值选择蚂蚁更新信息素的策略。多种群的双目标协同进化算法在双蚁群协同进化算法的基础上,通过一个新的子蚁群平衡两个各自偏好一个目标独立搜索的子种群的搜索程度,以避免在共同搜索的区域中丢失有效解,继而在提高算法的多样性和收敛性的同时,保证算法得到分布更均匀的解集。最后,通过大量的仿真实验,证明了多种群的双目标协同进化算法的有效性和高效性。