Abstract: 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, canmake 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.

Key words: No-wait distributed permutation flow shop, arrival times, adaptive estimation of distribution algorithm, allocation rule

摘要： 随着经济的发展，在各行各业中分布式生产变得越来越普及，我们将更多的注意力放在分布式生产模型之上。为求解带有序相关设置时间和到达时间的零等待分布式流水线调度问题(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)规则，使得解的生成过程有适当的判断，更加快速地提高当前代生成解的质量。其次，针对不同的问题规模进行局部搜索的深度做出相应的调整，使得在不同的规模下算法都能有很好的局部搜索能力。

关键词: 零等待分布式流水线调度, 到达时间, 自适应分布式估计算法, 分配规则