论文部分内容阅读
针对以最小化最大完工时间、最小化最大拖期和最小化总流程时间为目标的置换流水车间调度问题(permutation flow shop scheduling problem,PFSP),基于双变量分布估计法(bi-variable estimation of distribution algorithm,BVEDA)提出改善式双变量分布估计算法(Improved BVEDA,IBVEDA)进行求解。利用BVEDA中双变量概率模型进行区块构建,根据组合概率公式进行区块竞争和区块挖掘,借用高质量的区块组合人造解,提高演化过程中解的质量;针对算法多样性较差的特点,设计在组合人造解的过程中加入派工规则最短处理时间、最长处理时间和最早交货期,将上述方法并行演化,通过top10的权重适度值总和动态调整上述方法处理的解的数量,最后利用帕累托支配筛选和保存非支配解。试验使用C++代码在Taillard标准算例上测试,IBVEDA与SPGAⅡ和BVEDA比较,并绘制解的分布图证实算法的有效性。
For the permutation flow shop scheduling problem (PFSP), which aims to minimize the maximum completion time, minimize the maximum tardiness and minimize the total flow time, based on the bi-variable estimation of distribution algorithm, BVEDA) to improve the bivariate distribution estimation algorithm (Improved BVEDA, IBVEDA) to solve. In this paper, the bivariate probabilistic model of BVEDA is used to construct the blocks. According to the combinatorial probability formula, the block competition and the block mining are carried out. The high quality block combination artificial solution is used to improve the quality of the solution in the evolutionary process. It is designed to combine the shortest processing time, the longest processing time and the earliest delivery time in the process of combining artificial solutions. The above methods are evolved in parallel and the number of solutions processed by the above method is dynamically adjusted by the sum of the weighted fitness values of top10 Finally, the use of Pareto domination screening and preservation of non-dominated solution. The tests were tested on the Taillard standard case using C ++ code, IBVEDA was compared with SPGA II and BVEDA, and the distribution of the solution was plotted to verify the validity of the algorithm.