教学优化算法及其在车间调度问题中的应用研究

作     者：张斌 

作者单位：兰州理工大学 

学位级别：硕士

导师姓名：张其文

授予年度：2021年

学科分类：08[工学] 081104[工学-模式识别与智能系统] 0802[工学-机械工程] 0811[工学-控制科学与工程] 

主      题：教学优化算法 置换流水车间调度 零等待流水车间调度 迭代贪婪算法 知识库 

摘      要：调度问题的本质是在满足工艺、设备、资金等约束条件下,通过对资源进行合理分配、对工序或其他操作进行合理安排,使得产量、能耗、时间等问题目标实现最优化。车间调度是调度问题中不可或缺的一部分,直接决定了生产效率,从而影响制造系统的运行、企业的效益以及市场竞争力。大部分车间调度问题都是NP-Hard问题,随着问题规模增大和科学研究的不断深入,人们对计算复杂度和求解效率也有了更高的要求,因此,开发简单高效易于实现的方法仍然是本领域的研究热点。教学优化算法（Teaching-Learning-Based Optimization Algorithm,TLBO）是一种受教学过程启发的群体智能优化算法。TLBO算法因其优化过程简单,不需要额外的参数,已经广泛应用于数值优化和工业设计。本文对TLBO进行了深入研究,通过分析TLBO算法的优化过程,并将该算法与其他算法相结合,对TLBO进行了两种不同的改进。同时将改进后的算法分别应用两种不同的车间调度问题,通过仿真测试及实验分析,验证了算法的有效性和可行性。本文的主要研究内容和相关工作如下:（1）针对标准的TLBO算法在求解离散问题时存在的学习者之间信息交流不足、单一教师容易陷入局部最优的问题,本文提出了一种多班级教学优化算法（Multi-Classes Teaching-Learning-Based Optimization Algorithm,MCTLBO）,并将MCTLBO用于求解置换流水车间调度问题（Permutation Flowshop Scheduling Problem,PFSP）。在MCTLBO中,以基于置换的变异方法和NEH进行初始化,保持初始种群的质量和多样性;在教学阶段,考虑教师与学生之间的差异,给出了基于位置的交叉方法,同时以去重操作避免无意义的教学过程;引入了学生的自学阶段,以莱维飞行消除随机变异的不确定性,并以变邻域搜索提升解的质量。在相互学习阶段,以种群的平均适应度作为筛选条件,避免差生之间的相互影响,有效的保证了优势个体相互交流。通过对标准测试集Rec进行测试,并与相关算法进行比较,验证了MCTLBO求解离散问题的有效性和稳定性。（2）针对零等待流水车间调度问题（No-Wait Flowshop Scheduling Problem,NWFSP）,提出了一种离散的教学优化算法（Discrete Teaching-Learning-Based Optimization Algorithm,DTLBO）。在DTLBO中,从工件差异（学生水平）的角度出发,重新定义了重新定义了教学优化过程。在教学阶段,教师根据学生水平的不同采取不同的教学方式,以达到因材施教的效果。在相互学习阶段,根据自身水平的不同,学生也表现出不同的学习行为。此外,以迭代贪婪算法的破坏重构操作作为局部搜索。将改进后的算法应用于求解NWFSP问题,通过仿真实验及相关的结果分析,验证了算法的有效性。（3）对迭代贪婪算法的破坏过程进行了分析,给出了破坏过程中存在的不均匀性和无意义性两种情况。以工件及其对应的无意义破坏次数构建知识库,每次破坏之前从知识库中获取知识,从而动态的改变破坏过程中工件的选取方式。此外,以知识有效期为限制对早期知识进行擦除,只保留一定迭代次数的知识,保证了知识积累的有效性。最后将改进的破坏过程融入到DTLBO中,仿真结果表明改进破坏过程对算法求解效率提升的有效性。