流水车间调度问题的快速多目标混合进化算法

摘要：针对最大完工时间最小和总流经时间最小的双目标流水车间调度问题，提出一种快速多目标混合进化算法。算法将矢量评价遗传算法的采样策略与一种新的基于Pareto支配与被支配关系的适应度函数的采样策略进行了融合。新的采样策略弥补了矢量评价遗传算法（VEGA）采样策略的不足。VEGA善于搜索Pareto前沿面的边缘区域，但却忽略了Pareto前沿面的中心区域，而新的采样策略则倾向于Pareto前沿面的中心区域。这两种机制的融合保证了混合算法能够快速平稳地向Pareto前沿区域收敛。此外，由于混合采样策略不需要考虑距离，使得算法效率也得到了很大的提升。在对Taillard基准测试集进行的仿真实验结果显示，相对于非支配排序遗传算法（NSGAⅡ）和强度Pareto进化算法（SPEA2），该快速多目标混合进化算法在收敛性和分布性两方面都有所提高，并且算法的效率也得到了改进。所提出的混合算法能够更好地解决双目标的流水车间调度问题。

关键词：流水车间调度；混合进化算法；采样策略；矢量评价遗传算法；多目标优化

中图分类号：TP18 文献标志码：A

0引言

调度问题研究的是在一定的约束条件下将稀缺的资源分配给同一时刻的不同任务，它是一个决策过程，其目的是优化一个或多个目标[1]。流水车间调度问题（Flow shop Scheduling Problem， FSP），也称置换流水车间调度问题，是车间调度问题中的典型，属于NPhard问题[2]。

近年来，国内外许多学者针对于FSP进行了广泛的研究和探讨。文献[3]针对混合车间流水调度问题提出了一种新的数学模型，利用一种新的启发式算法来计算完工时间；文献[4]在启发式算法[5-7]的基础上提出了混合启发式算法，最大限度地减少了无等待流水车间调度的总流程时间；文献[8]提出了一种新的混合并行遗传算法来解决车间调度问题，改进了遗传算法的杂交和变异算子。然而，以上研究偏好于单目标的FSP，但多目标的FSP才更符合实际生产的需求。文献[9]提出了一种多目标混合遗传算法来求解FSP，算法中引入基于累计排序策略和自适应密度评估的适应度计算方式更好地保持群体多样性；文献[10]提出一种粒子群优化算法与变邻域搜索算法结合的混合粒子群优化算法，使算法在集中搜索和分散搜索之间达到合理的平衡；文献[11]对遗传算法进行改进，利用模糊聚类建立了新的种群更新规则，并采用随机权重法和偏好信息相结合的方式简化适应度的分配和选择操作。文献[9-11]方法虽然同时考虑了两个甚至是多个目标，但在提升算法性能的同时牺牲了算法效率。

矢量评价遗传算法（Vector Evaluated Genetic Algorithm， VEGA）[12]将种群分为多个子种群，每一个子种群朝着一个单一的目标演变。VEGA的这种特性使它拥有很强的向Pareto前沿面的边缘区域收敛的能力。然而，VEGA的多样性并不是很好，原因就在于它的选择偏好。非支配排序遗传算法（Nondominated Sorting Genetic AlgorithmⅡ， NSGAⅡ）[13]和强度Pareto进化算法（Strength Pareto Evolutionary Algorithm2， SPEA2）[14]已经被证明在解决多目标优化问题中能够得到较好的结果。NSGAⅡ精英种群的更新依赖于Pareto的rank排序机制和个体的拥挤距离；SPEA2则基于原始适应度值分配机制和密度机制，更新精英种群时要同时考虑原始适应度值和个体距离。因此，SPEA2要比NSGAⅡ占用更多的CPU时间。

为了同时提升收敛性和分布性并减少运算时间，本文提出了一种多目标混合进化算法（MultiObjective Hybrid Evolutionary Algorithm， MOHEA）用以解决多目标FSP。本文算法在VEGA的采样策略的基础上融合了一种基于Pareto支配与被支配关系的适应度函数（Pareto Dominating and Dominated Relationshipbased Fitness Function， PDDRFF）的采样策略。混合采样机制不仅能提高算法的收敛速率，而且也能增强算法分布性能。本文的结构安排如下：第1部分对FSP进行了描述并构建了该问题的数学模型；第2部分详细介绍了MOHEA；第3部分给出了仿真实验数值并对结果进行了讨论与分析；第4部分为结论和未来工作展望。

4结语

本文针多目标FSP提出了一种新的算法――MOHEA，同时考虑了完工时间最小化和总流经时间最小化，并构建了相应的双目标FSP的优化模型。MOHEA引入了新的适应度评价函数PDDRFF进行个体的评价，并与VEGA的采样策略进行了巧妙的融合。VEGA的采样策略偏向于Pareto前沿面边缘区域，而基于PDDRFF的采样策略有着向Pareto前沿面中心区域收敛的趋势。新的混合采样策略使得本文算法能够同时维护收敛和分布性能并降低了计算复杂度。针对双目标FSP的特点，采用整数编码对染色体进行编码，提升了算法的效率，局部映射交叉算子和互换变异增强了算法的搜索范围。从对9个不同规模的TA测试问题的仿真实验结果上看，与NSGAⅡ和SPEA2相比，MOHEA在收敛和分布性能上要好；在运算效率方面，MOHEA明显优于两者。

本文只研究了双目标的FSP，对于多目标以及更复杂的FSP并没有涉及，因此未来会将更多与生产相关的目标，如工件的最大拖期时间、总消耗和总成本等，以及大量包括各种实例的基准测试函数用来验证MOHEA的性能和效率，并会对MOHEA作进一步的改进。

未来的研究内容：会将更多与生产相关的目标，例如工件的最大拖期时间和总成本等，以及大量包括各种实例的计算实验用来验证MOHEA的性能和效率。

参考文献：

[1]

PINED M.调度：原理、算法和系统[M]. 张智海， 译.北京：清华大学出版社， 2007： 1-7.（PINEDO M. Scheduling： Theory， Algorithms and Systems [M]. ZHANG Z H， translated. Beijing： Tsinghua University Press， 2007： 1-7.）

[2]

GONZALEZ T， SAHNI S. Flow shop and job shop schedules： complexity and approximation [J]. Operations Research， 1978， 26（1）： 36-52.

[3]

ZIAEIFAR A， TAVAKKOLIMOGHADDAM R， PICHKA K. Solving a new mathematical model for a hybrid flow shop scheduling problem with a processor assignment by a genetic algorithm [J]. International Journal of Advanced Manufacturing Technology， 2012， 61（1）： 339-349.

[4]

GAO K， PAN Q， SUGANTHAN PN， et al. Effective heuristics for the nowait flow shop scheduling problem with total flow time minimization [J]. International Journal of Advanced Manufacturing Technology， 2013， 66（9）： 1563-1572.

[5]

GAO K， PAN Q， LI J. Discrete harmony search algorithm for the nowait flow shop scheduling problem with total flow time criterion [J]. International Journal of Advanced Manufacturing Technology， 2011， 56（5）： 683-692.

[6]

BERTOLISSI E. Heuristic algorithm for scheduling in the nowait flow shop [J]. Journal of Materials Processing Technology， 2000， 107（3）： 459-465.

[7]

LAHA D， CHAKRABORTY U K. A constructive heuristic for minimizing makespan in nowait flow shop scheduling [J]. International Journal of Advanced Manufacturing Technology， 2009， 41（1）： 97-109.

[8]

SPANOS A C， PONIS S T， TATSIOPOULOS I P， et al. A new hybrid parallel genetic algorithm for the job shop scheduling problem [J]. International Transactions in Operational Research， 2014， 21（3）： 479-499.

[9]

杨开兵. 基于进化计算的多目标流水车间批组调度问题研究[D]. 大连：大连理工大学， 2011：31-52.（YANG K B. Research on multiobjective flowshop scheduling with batching based on evolutionary algorithm [D]. Dalian： Dalian University of Technology， 2011：31-52.）

[10]

何启巍， 张国军， 朱海平， 等. 一种多目标置换流水车间调度问题的优化算法[J]. 计算机系统应用， 2013， 9（1）： 111-118， 110.（HE Q W， ZHANG G J， ZHU H P， et al. A hybrid particle swarm optimization algorithm for multiobjective permutation flows shop scheduling problem [J]. Computer Systems & Application， 2013， 9（1）： 111-118， 110.）

[11]

周晏明.基于改进遗传算法的多目标作业车间调度研究[D]. 哈尔滨：东北林业大学， 2013：8-19.（ZHOU Y M. Research on multiobjective job shop scheduling problem based on the improved genetic algorithm [D]. Harbin： Northeast Forestry University， 2013：8-19.）

[12]

SCHAFFER J D. Multiple objective optimization with vector evaluated genetic algorithms [C]// Proceedings of the 1st International Conference on Genetic Algorithms Table of Contents. Hillsdale， NJ： Lawrence Erlbaum Associates， 1985： 93-100.