Abstract: For the Distributed Heterogeneous Hybrid Flowshop Scheduling Problem (DHHFSP) with uncorrelated parallel machines,a mathematical model for minimizing the makespan was established,and a Hybrid Discrete Differential Evolution (HDDE) algorithm was proposed.Considering the complexity of heterogeneous workshops,the HDDE algorithm first introduce a new kind of factory allocation rules in the iterative search process,which could allocate jobs to more suitable factories for processing.To further enhance the quality of the initial population,an Improved Distributed Nawaz-Enscore-Ham (IDNEH) heuristic algorithm was designed,and the optimal solution was searched by using the mixed dual differential strategy of DE/rand/1 and DE/best/1.The results showed that mixing these two differential strategies could better guarantee the diversity of the population and the convergence of the algorithm.To strengthen the local search ability of the algorithm,for the unique features of the problem,a double layer variable neighbourhood descent (DVNS) algorithm based on the key factory was designed.In the part of numerical experiment,the performance was compared with GA_LS2,ES_en,IABC,IG and other algorithms,and the effectiveness of the proposed HDDE algorithm was verified.

Key words: distributed heterogeneous workshop, unrelated parallel machine, discrete differential evolution, dual differential strategy, factory allocation rule

摘要： 针对不相关并行机的分布式异构混合流水车间调度问题(DHHFSP),建立了以最小化最大完工时间为目标的数学模型,并提出了一种混合离散差分进化算法(HDDE)。考虑到异构车间的复杂性,HDDE算法首先在迭代搜索过程中引入了一类新的工厂分配规则,可将工件分配至更加合适的工厂执行加工。为进一步增强初始种群的质量,设计了改进性的DNEH启发式算法(IDNEH),并采用DE/rand/1和DE/best/1混合的双差分策略进行最优解搜索。结果表明,混合这两种差分策略可更好地保证种群的多样性与算法的收敛性。为强化算法的局部搜索能力,本文还针对问题特性设计了基于关键工厂的双层变邻域下降(DVND)算法。在数值实验部分,通过与GA_LS2、ES_en、IABC、IG等算法进行性能对比,验证了本文所提出的HDDE算法的有效性。

关键词: 分布式异构车间, 不相关并行机, 离散差分进化, 双差分策略, 工厂分配规则