混合交叉熵算法求解复杂零等待流水线调度问题
张梓琪1
钱斌2
胡蓉2
1.昆明理工大学机电工程学院,云南昆明650500;昆明理工大学信息工程与自动化学院,云南昆明6505002.昆明理工大学信息工程与自动化学院,云南昆明650500
摘要：针对制造行业中广泛存在的一类复杂零等待流水线调度问题,即带序相关设置时间和释放时间的零等待流水线调度问题(NFSSP SDSTs RTs),建立问题的排序模型并提出一种混合交叉熵算法(HCEA)进行求解,优化目标为最小化总提前和延迟时间.首先,设计了一种基于问题性质的快速评价方法,有效降低评价解的计算复杂度.其次,采用交叉熵算法学习并积累优质解的结构特征,建立概率模型对优质解的工件块分布进行有效地估计.通过合理的采样和更新方法,实现对解空间中优质区域的全局搜索.然后,为提高算法搜索效率,设计带两种搜索策略的快速局部搜索方法,对全局搜索发现的优质区域进行细致且深入的搜索.最后,仿真实验与算法对比验证了HCEA可有效求解NFSSP SDSTs RTs.
关键词：零等待流水线调度序相关设置时间释放时间局部搜索交叉熵
资助基金：国家自然科学基金(51665025)国家自然科学基金(61963022)国家自然科学基金(62173169)
论文发表日期：2021-12-28
在线出版日期：2025-08-15（本平台首次上网日期，不代表文献的发表时间）
页数：16( 1919-1934 )
英文信息