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

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

针对制造行业中广泛存在的一类复杂零等待流水线调度问题,即带序相关设置时间和释放时间的零等待流水线调度问题(NFSSP_SDSTs_RTs),建立问题的排序模型并提出一种混合交叉熵算法(HCEA)进行求解,优化目标为最小化总提前和延迟时间.首先,设计了一种基于问题性质的快速评价方法,有效降低评价解的计算复杂度.其次,采用交叉熵算法学习并积累优质解的结构特征,建立概率模型对优质解的工件块分布进行有效地估计.通过合理的采样和更新方法,实现对解空间中优质区域的全局搜索.然后,为提高算法搜索效率,设计带两种搜索策略的快速局部搜索方法,对全局搜索发现的优质区域进行细致且深入的搜索.最后,仿真实验与算法对比验证了HCEA可有效求解NFSSPSDSTsRTs.

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.