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

针对制造行业中广泛存在的一类复杂零等待流水线调度问题,即带序相关设置时间和释放时间的零等待流水线调度问题(NFSSP SDSTs RTs),建立问题的排序模型并提出一种混合交叉熵算法(HCEA)进行求解,优化目标为最小化总提前和延迟时间.首先,设计了一种基于问题性质的快速评价方法,有效降低评价解的计算复杂度.其次,采用...

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

This paper proposes a hybrid cross-entropy algorithm (HCEA) and formulates a sequence-based model forsolving 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 tominimize 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 isused to learn and accumulate the structural characteristics of high-quality solutions, and a probability model is establishedto effectively estimate the distribution of job blocks in superior solutions. Then, the global search for promising regionsin solution space is performed by using the reasonable sampling and updating methods. Thirdly, in order to enhance thesearch efficiency of HCEA, a fast local search with two search strategies is developed to execute detailed and in-depthexploitation in these promising regions found by the global exploration. Finally, simulation experiments and comparisonresults demonstrate that the proposed HCEA can effectively solve the NFSSP SDSTs RTs.