求解异构并行机调度问题的混合多目标教–学优化算法  

A hybrid multi-objective teaching-learning-based optimization algorithm for unrelated parallel machine scheduling problem

作　　者：宋强 SONG Qiang(School of Computer Science and Software,Zhaoqing University,Zhaoqing Guangdong 526061,China;School of Information Engineering,Wuhan University of Technology,Wuhan Hubei 430070,China)

机构地区：[1]肇庆学院计算机科学与软件学院,广东肇庆526061 [2]武汉理工大学信息工程学院,湖北武汉430070

出　　处：《控制理论与应用》2020年第10期2242-2256,共15页Control Theory & Applications

基　　金：国家自然科学基金项目(60773212);肇庆市科技创新类项目(201904030404);肇庆学院科研基金项目(201948)资助.

摘　　要：以异构并行机调度(UPMS)为研究对象,考虑了最小化makespan和提前/延误惩罚成本总和的多目标优化问题.首先,基于问题描述构建了数学优化模型,并设计了"约束法求解流程.其次,提出了混合多目标教–学优化算法(HMTLBO).HMTLBO算法借助分解机制将Pareto前沿逼近问题转化为一系列单目标子问题,并通过教–学优化算法(TLBO)求解各子问题.针对问题特点设计了序列编码方式,并据此融合3种交叉算子构筑了个体更新方法,同时建立了变邻域下降搜索以增强算法的局部搜索能力.最后进行了仿真实验与分析,测试结果验证了HMTLBO求解当前调度问题的高效性.In the context of unrelated parallel machine scheduling(UPMS),this paper investigates a multiple-objective problem on purpose of minimizing makespan and total earliness/tardiness penalty cost.First,a mathematical model is developed and an epsilon-constraint method is presented according to the problem statement.Then,a developed algorithm named hybrid multi-objective teaching-learning-based optimization(HMTLBO)is proposed.HMTLBO decomposes the investigated multi-objective problem into single-objective problems and solves each of them by virtue teaching-learningbased optimization(TLBO).To coordinate the problem characteristic,a sequence coding technique is designed and individuals are updated by three crossover operators.In addition,variable neighborhood descent search is applied to improve the performance of the algorithm.Finally,the simulations are performed and analyzed.The results verify the outstanding performance of HMTLBO in solving the considered UPMS problem.

关 键 词：异构并行机 调度 多目标 教–学优化算法 分解 

分 类 号：TH186[机械工程—机械制造及自动化] TP18[自动化与计算机技术—控制理论与控制工程]