新颖的阻塞流水车间调度量子差分进化算法

　　在冶金、化工等多种工业环境中，广泛存在着流水车间调度问题（Flowshop Scheduling Problem， FSP。该问题描述为：n个作业要在m台机器上加工，每个作业需通过m道工序，每道工序要求在不同机器上加工，n个作业在m台机器上加工顺序相同，作业i在机器j上的加工时间给定，调度目标求解n个作业的最优加工顺序，使特定的性能指标得到满足。阻塞流水车间调度问题（Blocking Flowshop Scheduling Problem， BFSP是对FSP的进一步约束，它考虑m台相邻串行机器中间存储量为0，如果给定的机器加工完某一作业后，而下一台机器仍处于忙碌状态，那么这个作业就不能分配给下一台机器，作业需在该机器上等待，因此该机器保持空闲状态，即阻塞现象[1]。已经证明，当机器数m>2时，该问题是NPComplete问题[2]。近年来粒子群算法、蛙跳算法、蜂群算法、和声搜索等智能优化算法已成功应用于求解BFSP[1-5]，并获得较好的优化效果，但这些研究大多数只考虑了单个算法的应用，没有结合其他算法的优点，这样易产生早熟收敛现象，需要进一步改进。

　　量子进化算法（Quantuminspired Evolutionary Algorithm， QEA是量子计算与进化计算相融合的产物[6]，它利用量子叠加性、纠缠性和相干性，通过量子比特编码染色体，引入量子旋转、交叉和变异等算子实现种群的进化，同时利用当前最优个体的信息来更新量子旋转门，以加速算法收敛。该类算法具有种群规模小、收敛速度快、全局寻优能力强、易于实现等优点，因而被广泛应用于自动控制、逻辑电路设计、信息安全等领域[7-9]。差分进化（Differential Evolution， DE算法是一种新型群智能算法，具有与遗传算法类似的交叉、变异及选择操作，算法主要基于当前种群的两个随机个体对之间的差异来实现进化，具有全局寻优能力强、易于理解与实现等特点，常用于与其他启发式算法混合来解决复杂的实际问题。文献[10]将QEA与DE结合，提出一种混合量子差分进化（Hybrid Quantum DE， HQDE算法，有效地解决了01背包问题和旅行商问题；文献[11]针对N皇后问题，设计一种量子干扰机制，并结合DE的变异方案以实现种群更新，实验结果表明所提算法的优越性；文献[12]针对多目标置换FSP问题，提出一种量子差分进化算法（Quantum Differential Evolutionary Algorithm， QDEA，实验结果表明QDEA的高效性。上述算法的成功应用，显示出量子差分进化思想的优越性，然而，这些算法对解空间缺乏高效的局部探索机制，随着问题规模的增大，算法易“陷入”局部最优，因此，需采用新的策略进行优化，如结合邻域搜索算法，以便在不同规模问题下获得最优或近似最优解。

　　为了更有效地求解BFSP，本文在QEA基础上提出了一种新颖的量子差分进化算法（Novel Quantum Differential Evolutionary， NQDE，利用差分进化思想[11]设计量子旋转门以控制种群进化方向，同时采用基于变邻域搜索（Variable Neighborhood Search， VNS的量子进化算法（Quantum-inspired Evolutionary AlgorithmVNS， QEAVNS协同进化方案增加算法的全局搜索能力。基于典型算例进行仿真，实验结果表明NQDE能更好地改善解质量，对大规模BFSP有效。

　　第3期

　　齐学梅等：新颖的阻塞流水车间调度量子差分进化算法

　　计算机应用 第35卷

　　1问题描述

　　在BFSP中，常见的优化目标有最小化最大完工时间、总完工时间和总延误时间等，其中，最小化最大完工时间意味着最大化生产能力，对其进行优化调度可有效地提高企业生产效率和资源利用率。最小化最大完工时间的阻塞流水调度问题记为Fm|block|Cmax。在Fm|block|Cmax中，令π={π1，π2，…，πn}为一个调度，pπi， j为作业πi在机器j上的加工时间，C（πi， j表示作业πi在机器j上的完工时间。调度π的各个作业在机器上的完工时间定义为：

　　C（πi，0=0，i=1，2，…，n

　　C（π1， j=C（π1， j-1+pπ1， j，j=1，2，…，m

　　C（πi， j=max{max（C（πi-1， j，C（πi， j-1+pπi， j，C（πi-1， j+1}， i=2，3，…，n， j=1，2，…，m（1

　　则π对应的Cmax定义为：

　　Cmax=f（π=C（πn，m（2

　　图1为4个作业在4台机器上的Fm|block|Cmax调度。