一类分布式零等待流水线自适应EDA调度

Adaptive Estimation of Distribution Algorithm for Solving a kind of Distributed No-waiting Flow Shops

随着经济的发展,在各行各业中分布式生产变得越来越普及,故将更多的注意力放在分布式生产模型之上。为求解带有序相关设置时间和到达时间的零等待分布式流水线调度问题(No-wait Distributed Flow Shop with Sequence Dependent Setup Times and Arrival Times,NDPFSP with SDSTs and RDs),提出了一种自适应的分布估计算法(Adaptive Estimation of Distribution Algorithm, AEDA),用于最小化最大完成时间。首先,提出了更加适合于带到达时间问题的最早完成工厂问题的带有到达时间的最早完成工厂(the Earliest Completion Factory with Arrival Time, ECFAT)规则,使得解的生成过程有适当的判断,更加快速地提高当前代生成解的质量。其次,针对不同的问题规模进行局部搜索的深度做出相应的调整,使得在不同的规模下算法都能有很好的局部搜索能力。

With the development of the economy, distributed permutation production becomes more and more widespread in all walks of life, more attention is put on distributed models. An adaptive estimation of distribution algorithm(AEDA) is proposed for solving no-wait distributed permutation flow shop with Sequence Dependent Setup Times and Arrival times(NDPFSP with SDSTs and RDs) and minimizing the largest completion time. First of all, this paper proposes the earliest completion factory with arrival time(ECFAT), which is more suitable for this problem, can make a judgment in the generation process of solution and improve the quality of the current solution faster. Next, according to different problem scales, the proposed local search can adjust the depth of local search to ensure its ability for solving this problem.