一种求解随机有限缓冲区流水线调度的混合差分进化算法

针对随机有限缓冲区流水线调度问题(Flow shop scheduling problem, FSSP), 提出混合差分进化(Differential evolution, DE)算法OHTDE, 用来最小化提前/拖后指标和最小化总体完成时间指标. OHTDE将DE和最优计算量分配(Optimal computing budget allocation, OCBA)技术以及假设检验(Hypothesis test, HT)有效结合. DE用于执行全局搜索和局部搜索; OCBA用于对有限计算量进行合理分配, 从而保证优质解得到较多仿真计算量, 提高了在噪声环境下获得优质解的置信度; HT用于在统计意义上比较解的性能, 从而一定程度上避免在解空间相近区域进行重复搜索. 进而, 对由OCBA和HT确定的优质解执行一种特殊的交叉操作, 加强DE的局部开发能力. 同时也采用有限马氏链理论对OHTDE的随机收敛性进行了分析. 仿真实验和算法比较验证了算法的有效性和鲁棒性.

A Hybrid Differential Evolution Algorithm for Stochastic Flow Shop Scheduling with Limited Buffers

A hybrid differential evolution (DE) algorithm, namely OHTDE, is proposed to solve the stochastic flow shop scheduling problem (FSSP) with limited buffers between consecutive machines. Two different criteria are considered. The first is to minimize a general earliness/tardiness cost function and the second is to minimize the total completion time. The proposed algorithm is a hybrid of DE and two techniques: the optimal computing budget allocation (OCBA) technique and hypothesis test (HT). DE is used to execute both global and local search. OCBA is utilized to reasonably allocate a limited sampling budget for every solution, assigning more for better individuals to improve the confidence level of getting good solutions under noise environment. HT is adopted to perform a statistical comparison on solutions' performances so that the repeated search on the similar region of the solution space can be avoided to some extent. Moreover, a special crossover, which is performed on some good solutions identified by OCBA and HT, is designed to enhance the capability of local search. Furthermore, the stochastic convergence property of OHTDE is analyzed by using the theory of finite Markov chain. Experimental results and comparison show the effectiveness and robustness of the proposed OHTDE.