IEEEJAS的个人博客分享 http://blog.sciencenet.cn/u/IEEEJAS

博文

混合离散教与学算法求解复杂并行机调度问题

已有 180 次阅读 2020-9-21 13:57 |系统分类:博客资讯

带到达时间、多工序、加工约束和序相关设置时间的并行机调度问题(Parallel Machine Scheduling Problem with Arrival Time, Multiple Operations, Process Restraints and Sequence-dependent Setup Times, PMSP_AMPS),是模具制造、半导体芯片终端测试阶段、塑料加工等行业中广泛存在的一类复杂并行机调度问题。在计算复杂度上,PMSP_AMPS属于NP-Complete问题。对于PMSP_AMPS这一类复杂并行机调度问题,无论是运筹学方法还是基于动态规划的近似算法均难以在较短时间内有效求解,故研究设计相应的智能优化算法具有重大意义。


首先,在优化模型和求解方法的宏观层面,首次对数学规划模型和排序模型的特点,以及两类模型对应的主要求解方法进行深入分析,指出采用排序模型和智能优化算法求解复杂调度问题的合理性和必要性。


然后,针对PMSP_AMPS,建立排序模型并提出一种混合离散教与学优化算法 (HDTLBO)进行求解。这是首次运用基于TLBO的算法求解PMSP_AMPS。在HDTLBO中,设计不同的排序操作,以此替换标准教与学算法的个体更新操作,使其能直接在问题的离散解空间中执行搜索,从而在保留TLBO更新机理的前提下提高了算法的全局搜索效率;构造基于Interchange和Insert邻域操作的变邻域局部搜索,对全局搜索得到的优质区域执行较为细致的搜索,使算法在全局和局部搜索之间达到较好平衡,从而增强了算法的整体搜索能力。


此外,通过计算复杂度分析,得出HDTLBO整体计算复杂度的最高次项为问题输入规模n和种群大小popsize的平方,具有较低复杂度的结论。最后,通过不同测试问题上的仿真实验和算法比较,验证了HDTLBO是求解PMSP_AMPS的有效算法。


image003.png

图1 各比较算法在不同时间参数下的均值线及95%置信度下Tukey’s HSD检验的置信区间


现有的智能调度算法,大多基于在连续优化领域取得成功应用的智能优化算法,并在其中加入编码规则来实现解连续空间到问题离散空间的映射,从而可求解相关调度问题。这一方式本质上是否有效,尚无人进行探讨和分析。

本文所提HDTLBO在保留标准TLBO进化框架基础上,直接设计各种排序操作来替换原算法的核心操作,取得了更好的搜索性能。这对其他智能调度算法的离散化设计具有一定的借鉴意义,也可促进对智能调度算法为何有效的本质原因的理解。


引用格式:何雨洁, 钱斌, 胡蓉. 混合离散教与学算法求解复杂并行机调度问题. 自动化学报, 2020, 46(4): 805-819

文章链接:http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c180321


作者简介


何雨洁

昆明理工大学信息工程与自动化学院硕士研究生.2016年获得昆明理工大学信息工程与自动化学院学士学位.主要研究方向为调度与智能优化算法.

E-mail: Hyujie_one@163.com


钱  斌

昆明理工大学信息工程与自动化学院教授. 2009年获清华大学自动化系博士学位. 主要研究方向为调度与优化. 本文通讯作者.

E-mail: bin.qian@vip.163.com


胡  蓉

昆明理工大学信息工程与自动化学院副教授. 2002年获清华大学自动化系硕士学位. 主要研究方向为优化方法和决策支持系统.

E-mail: ronghu@vip.163.com




http://blog.sciencenet.cn/blog-3291369-1251485.html

上一篇:基于形式概念分析和语义关联规则的目标图像标注
下一篇:基于学习字典的机器人图像稀疏表示方法

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2020-10-29 07:35

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部