Abstract: To deal with the distributed heterogeneous non-permutation flowshop scheduling problem,a mixed-integer linear programming model was formulated to minimize total weighted tardiness.In view of the complexity of the problem,a two-stage hybrid iterative greedy algorithm was proposed based on an depth analysis of the relationship between the permutation solutions and non-permutation solutions.The proposed algorithm employed a two-stage hierarchical search strategy with a permutation solution search stage and a non-permutation solution search stage,where the first stage was to find the permutation solution while the second stage was to find the non-permutation solution.In the first stage,an improved NEH heuristic was developed to generate a high-quality initial solution at first,and a perturbation strategy was designed to avoid the algorithm falling into a local optimum.Finally,to improve the solution quality,two adaptive local search strategies with different domain structures were proposed to generate a high-quality permutation solution.In the second stage,the permutation solution generated in the first stage was improved by changing the sequence of jobs on certain machines.A greedy insertion strategy was first used for perturbation.Then,two adjacent swap local search strategies with different job swapping sequences were designed in an alternating manner to improve the new solution.The perturbation process and the local search process were performed iteratively to enhance the exploration of the solution space.Finally,the efficiency of the proposed algorithm was verified through experiments with data of different scales and comparative analysis with comparative algorithms.

Key words: distributed heterogeneous non-permutation flowshop scheduling problem, mixed-integer linear programming model, two-stage hierarchical strategy, hybrid iterated greedy algorithm

摘要： 针对分布式异构非置换流水车间调度问题,建立以最小化总拖期惩罚费用为目标的混合整数线性规划模型。鉴于问题的复杂性,在深入分析置换与非置换解关系的基础上,提出了一种两阶段混合迭代贪婪算法。该算法采用了置换解搜索阶段和非置换解搜索阶段的两阶段递阶搜索策略。在第一阶段中,首先采用改进NEH启发式生成高质量初始解;随后,提出一种扰动策略以避免算法陷入局部最优;最后,为提高求解质量,提出两种不同结构的自适应局部搜索策略,进而生成一个高质量置换解。第二阶段则通过改变某些机器上的工件排序来改进第一阶段产生的置换解。在第二阶段中,首先运用贪婪插入策略进行扰动;然后,交替运用两种不同工件交换顺序的相邻交换局部搜索策略对新解进行改进。扰动过程和局部搜索过程迭代进行,以加强对解空间的探索。最后,通过不同规模的数据实验和与对比算法的比较分析,验证了所提算法的高效性。

关键词: 分布式异构非置换流水车间调度, 混合整数线性规划, 两阶段递阶策略, 混合迭代贪婪算法