混合交叉熵算法求解复杂零等待流水线调度问题

Hybrid cross-entropy algorithm for solving complex no-wait flow-shop scheduling problem

中文关键词  零等待  流水线调度  序相关设置时间  释放时间  局部搜索  交叉熵

英文关键词  no-wait  flow shop scheduling  sequence dependent setup times  release times  local search  cross-entropy

中文摘要

      针对制造行业中广泛存在的一类复杂零等待流水线调度问题, 即带序相关设置时间和释放时间的零等待 流水线调度问题(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.