引用本文:张梓琪,钱斌,胡蓉.混合交叉熵算法求解复杂零等待流水线调度问题[J].控制理论与应用,2021,38(12):1919~1934.[点击复制]
ZHANG Zi-qi,QIAN Bin,HU Rong.Hybrid cross-entropy algorithm for solving complex no-wait flow-shop scheduling problem[J].Control Theory and Technology,2021,38(12):1919~1934.[点击复制]
混合交叉熵算法求解复杂零等待流水线调度问题
Hybrid cross-entropy algorithm for solving complex no-wait flow-shop scheduling problem
摘要点击 1163  全文点击 362  投稿时间：2020-10-30  修订日期：2021-09-24
查看全文  查看/发表评论  下载PDF阅读器
DOI编号  10.7641/CTA.2021.00755
  2021,38(12):1919-1934
中文关键词  零等待  流水线调度  序相关设置时间  释放时间  局部搜索  交叉熵
英文关键词  no-wait  flow shop scheduling  sequence dependent setup times  release times  local search  cross-entropy
基金项目  国家自然科学基金项目(51665025, 61963022, 62173169)资助.
作者单位E-mail
张梓琪 昆明理工大学 zzq768894018@vip.qq.com 
钱斌* 昆明理工大学 bin.qian@vip.163.com 
胡蓉 昆明理工大学  
中文摘要
      针对制造行业中广泛存在的一类复杂零等待流水线调度问题, 即带序相关设置时间和释放时间的零等待 流水线调度问题(NFSSP SDSTs RTs), 建立问题的排序模型并提出一种混合交叉熵算法(HCEA)进行求解, 优化目 标为最小化总提前和延迟时间. 首先, 设计了一种基于问题性质的快速评价方法, 有效降低评价解的计算复杂度. 其 次, 采用交叉熵算法学习并积累优质解的结构特征, 建立概率模型对优质解的工件块分布进行有效地估计. 通过合 理的采样和更新方法, 实现对解空间中优质区域的全局搜索. 然后, 为提高算法搜索效率, 设计带两种搜索策略的快 速局部搜索方法, 对全局搜索发现的优质区域进行细致且深入的搜索. 最后, 仿真实验与算法对比验证了HCEA可 有效求解NFSSP SDSTs RTs.
英文摘要
      This paper proposes a hybrid cross-entropy algorithm (HCEA) and formulates a sequence-based model for solving a type of complex no-wait flow-shop scheduling problem with sequence dependent setup times and release times (NFSSP SDSTs RTs), which widely exists in the manufacturing industry. The criterion of the NFSSP SDSTs RTs is to minimize the total earliness and tardiness. Firstly, a speed-up evaluation method based on problem property is devised, which can effectively reduce the computational complexity of solution evaluation. Secondly, a cross entropy algorithm is used to learn and accumulate the structural characteristics of high-quality solutions, and a probability model is established to effectively estimate the distribution of job blocks in superior solutions. Then, the global search for promising regions in solution space is performed by using the reasonable sampling and updating methods. Thirdly, in order to enhance the search efficiency of HCEA, a fast local search with two search strategies is developed to execute detailed and in-depth exploitation in these promising regions found by the global exploration. Finally, simulation experiments and comparison results demonstrate that the proposed HCEA can effectively solve the NFSSP SDSTs RTs.