改善式BVEDA求解多目标调度问题
Improved bi-variables estimation of distribution algorithms for multi-objective permutation flow shop scheduling problem

摘要： 针对以最小化最大完工时间、最小化最大拖期和最小化总流程时间为目标的置换流水车间调度问题(permutation flow shop scheduling problem, PFSP),基于双变量分布估计法(bi-variable estimation of distribution algorithm, BVEDA)提出改善式双变量分布估计算法(Improved BVEDA, IBVEDA)进行求解。利用BVEDA中双变量概率模型进行区块构建,根据组合概率公式进行区块竞争和区块挖掘,借用高质量的区块组合人造解,提高演化过程中解的质量;针对算法多样性较差的特点,设计在组合人造解的过程中加入派工规则最短处理时间、最长处理时间和最早交货期,将上述方法并行演化,通过top10的权重适度值总和动态调整上述方法处理的解的数量,最后利用帕累托支配筛选和保存非支配解。试验使用C++代码在Taillard标准算例上测试,IBVEDA与SPGAⅡ和BVEDA比较,并绘制解的分布图证实算法的有效性。
Abstract: Aiming at permutation flow shop scheduling problem(PFSP)with the minimum maximum makespan, the minimum maximum tardiness and the minimum total flow time as objectives, improved bi-variable estimation of distribution algorithm(IBVEDA)based on bi-variables estimation of distribution algorithm(BVEDA)was proposed. Building blocks was designed using bi-variable probability model of IBVEDA, according to combination probability formula for block competition and block mining, then artificial chromosomes were generated using high quality blocks to improve the quality of solution in the evolution process. To enhance the diversity of algorithm, dispatching rules, the shortest processing time, longest processing time,earliest due date were added in parallel evolution while injecting artificial chromosomes, the number of individual for next iteration processed by the methods above depended on the above methods top 10 total weighted fitness of last iteration to do dynamic adjustment, finally Pareto dominance was used to select and save non-dominated solutions. The experiment used C++ code tested on Taillards standard instances, IBVEDA was compared with SPGAⅡand BVEDA and solution distribution of the three algorithms were plot which the effectiveness of IBVEDA was validated