Abstract: To improve logistics balance of production lines and strengthen time connection between stages, thedynamic reentrant flexible flowshop problem with unrelated parallel machines on each stage is studied, which is an extension of scheduling theory on general reentrant flexible flowshop. The objective is to minimize the total weighted completion time. The job processing time at each stage is dependent on the machine assigned for processing the job. Since the above problem is NP-hard, an integer programming model is firstly formulated. Then, a cellular matrix coding scheme is designed and a hybrid DABC-GA algorithm is developed combining discrete artificial bee colony(DABC)algorithm and genetic algorithm (GA) to obtain near-optimal solutions. The employed bees use Gaussian mutation to search new honey sources; the onlooker bees apply GA for these honey sources to find better neighborhood solutions; the scout bees achieve new honey sources through reverse operation. Finally, to evaluate the hybrid algorithm, the proposed algorithm is compared with several meta-heuristic algorithms for different scale problems. The experimental results show the effectiveness of the proposed algorithm.

Key words: dynamic re-entrant flexible flowshop problem, unrelated parallel machine, total weighted completion time, hybrid DABC-GA algorithm

摘要： 为了改善生产线的物流平衡和加强阶段间的时间衔接,扩展一般可重入柔性流水车间调度理论,以最小化总加权完工时间为目标,研究了每阶段含不相关并行机的动态可重入柔性流水车间问题,工件在各阶段的加工时间取决于加工它的机器。鉴于所研究问题为NP-hard问题,首先,建立整数规划模型;其次,设计元胞矩阵编码方案,提出融合离散人工蜂群算法和遗传算法的一种混合算法以获得问题的近优解;最后,为了评估混合算法的性能,将所提出算法和一些元启发式算法进行了不同规模问题的对比测试,实验结果说明了所提算法的有效性。

关键词: 动态可重入柔性流水车间问题, 不相关并行机, 总加权完工时间, 混合DABC-GA算法