第一章 绪论
1.1 研究背景及意义
1.1.1 研究背景
（1）政策与行业背景
当前随着全球经济迅速回暖，生产企业进一步加深国际化，这对企业生产调度能力提出了更高的要求。同时，企业的生产调度领域研究也引起了不少相关企业和研究学者的兴趣。企业经营过程当中受到不同产品品种、产品价格和质量、售后服务以及制造能力等诸多因素影响，这也影响到企业在市场上的竞争力。这一切的因素归根到底都要来源于企业在产品的生产和服务阶段。提高企业生产调度能力，加快生产效率，也可以将产品加工成本压缩。在保持产品质量合格的同时，对顾客的需求进行迅速调整[1]。总而言之，企业生产调度的效率直接影响到企业的经营和发展，提高生产调度能力已经成为企业应对市场竞争的重要方面。
当前，中国政府制订和出台了一系列促进国家工业水平的提升的政策， 政府方面坚持以信息化带动工业化，以工业化促进信息化，走新型工业化道路，完善工业污染治理能力，降低工业污染排放，提升产品制造效率，加快中国工业产业结构转型，提高我国制造企业的国际竞争力[2]。伴随着中国制造业信息化水平的稳步提升，工业技术应用范围以及深度不断加深，智能算法作为信息技术的重要组成部分，在中国制造企业信息化过程当中扮演了十分重要的角色。当前，智能优化算法在我国制造企业的生产调度领域当中正发挥着巨大的作用，智能算法水平的不断提升为企业进一步迈向制造自动化以及生产管理智能化提供了有效的途径[3]。
（2）理论背景
当前生产调度对于制造业以及行业都是一个重要的理论研究领域，加快生产调度理论以及智能搜索算法的深入研究，有利于提高企业生产效率，降低生产成本。目前，生产调度理论以及算法研究已有数十年历史，生产调度问题受到了世界各地多学科领域科学家的关注，这些科学家分别从应用数学、运筹学、计算机等多个领域来对调度问题提出各种理论和解决方法。但是调度问题本质上存在 NP-hard（Non-deterministicPolynomial-timehard）[4]的特点，调度问题存在难解，而且大多数情况下不存在最优解。所以，当前人们对于生产调度领域的研究主要集中在实际调度问题，流水车间调度问题成为了一个重要的研究方向。自从 1954 年 Johnson[5]首次对流水车间调度问题进行了研究之后相关学者对其进行了更加深入的探索。流水车间调度作为制造企业实际流水车间生产调度的简化模型，在实际用途中更加宽广，成为了具有代表性的车间调度模型。而置换流水车间属于流水车间问题的子问题之一，它将流水车间问题进行了一定简化，在原有问题条件上增加了一些限制[1]。PFSP 的求解方式包括数学规划精确求解[6]启发式[7]方法以及基于元启发式的智能算法[8]。
...........................
1.2 研究内容及论文框架
本文的主要研究在于将基本的群智能算法进行优化改进，并应用到置换流水车间的调度优化求解过程中，将实验结果同其他已有的改进策略进行对比和分析，验证算法性能。本文为企业在实际的流水车间调度优化过程提供了有力的支持。以下是对本文主要研究部分的概括：
（1）本文系统的阐述了置换流水车间在当前研究背景下的研究意义及国内外文献综述，对 PFSP 进行描述并分类，包括零空闲 PFSP、有限等待 PFSP、分布式 PFSP、多目标 PFSP，PFSP，对 PFSP 的研究方法进行了总结，包括精确方法、启发式方法和智能优化算法。
（2）对当前离散工业生产调度现状进行了分析，包括调度规则与调度难点，并对其使用智能优化的应用情况和求解思路进行了探讨。
（3）提出了一种基于 levy 飞行的入侵杂草优化算法，针对基本入侵杂草算法易陷入局部最优的特点，引入 levy 飞行、定向变异两种改进策略，用 6 个标准测试函数验证改进算法的优越性。
（4）提出了一种混合变异花授粉算法，将异花授粉的过程中引入混沌算法进行随机扰动以扩大种群多样性，自花授粉的过程引入交流算子以增强种群之间的信息交流，用 10 个标准测试函数验证改进策略的可行性[20]。
（5）本文将置换流水车间的问题进行分析，构建出以最小化最大完工时间为主要目标的算法模型。采用改进的入侵杂草优化算法来进行实证分析，首先将算法进行 ROV解码转换，然后利用启发式算法 NEH 生成初始可行解，利用改进后的入侵杂草算法来对杂草种群进行繁殖、扩散以及竞争，最后反复迭代，动态生产种群最优解。本文采用改进后的入侵杂草算法来对 Carlier 和 Reeves 标准案例进行求解和分析，然后将实验结果同其他算法进行对比分析，得出结论[21]。
..........................
第二章 相关理论基础及研究综述
2.1 车间调度问题研究
车间生产调度问题具体表现在加工机器的分配、加工批次的划分以及工件加工顺序等方面，从本质来看是对企业资源生产调度的计划与安排。对于此类问题我们定义为“有限的资源以及有限的时间内，分配多个任务，来实现一个目标或者多个目标。”[22]生产调度的主要目标是在一定的约束条件以及性能指标下将各个机器上的加工时间和工件顺序进行合理的安排，找到各个工件在每台机器上最佳的加工顺序，将流水车间生产效率最大化[23]。经过企业和相关学者多年的研究和探索，生产调度问题理论得到了极大的完善和发展，相关求解方式也从最开始的整数规划法、动态规划法以及分支界定法等经典数学求解方法，过渡到了多学科交叉优化研究，特别是智能算法的应用为研究学者解决更为复杂了调度问题有了新的思路。
车间调度问题的数学来描述：m 台设备加工 n 个工件，每个工件都有 k 道工序，而每道工序可在多个机器上作业。每台设备在同一时间段只能加工一道工序。因此，生产调度是依据加工对象的加工需求，通过改变不同的调度决策规则，运用不同的仿生智能算法，来对加工顺序进行系统科学的规划，并且能够依据系统目标来动态仿真结果，最后得到最佳的生产加工顺序，完成设备集和任务集的高效结合。当前，由于研究对象和目标具有一定的复杂性和无规律性，复杂性主要体现在车间调度环境的不确定性、求解计算困难性以及调度目标存在多样性，这使得车间调度优化问题存在诸多困难。
对于流水车间调度问题的研究，我们可以分为多个研究重点，对于零件和车间构成的不同可以分为：开放式车间调度（Openshopscheduling）、单机车间调度（Singlemachineshopscheduling）、并行机车间调度（Parallelshopscheduling）、作业车间调度(Jobshopscheduling)以及流水车间调度 (Flowshopscheduling)。在这当中作业流水车间以及流水车间调度问题最具有研究意义，他们具有典型的特殊工件加工特性以及加工环境。当前来说，大多数文献中对于这两种调度问题的研究也是最多的[17]。
.....................
2.2 置换流水车间调度问题描述及分类
2.2.1 置换流水车间调度问题数学描述
置换流水车间调度问题 PermutationFlow-shopSchedulingProblem，PFSP）从数学角度来看是一类组合优化问题。相关企业和研究学者已经证明了它属于 NP-hard 问题，它属于 FSP 问题的一类子问题，在 FSP 问题上进行了简化。置换流水车间问题在制造业、冶金业以及化工业等领域有着广泛的实用价值。
PFSP 问题的可行解搜索空间当中存在着众多局部最优解，当问题情况越复杂，搜索可行解时就越容易陷入到局部最优的情况，在整体上难以得到问题的最优可行解。所以面对这一情况，衍生出了很多仿生智能算法，目的是在搜索过程当中避免陷入局部最优，更快速更有效地找到全局最优解。4 个工件 4 台机器的甘特图如下图 2-2 所示:
.............................
第三章 离散工业生产调度现状分析........................26
3.1 离散工业生产调度描述..............................26
3.2 离散工业生产调度规则.................................27
第四章 改进入侵杂草算法以及改进花授粉算法研究............................33
4.1 基于莱维飞行的入侵杂草优化算法...........................33
4.1.1 基本入侵杂草优化算法..............................33
4.1.2 具有 levy 飞行机制的入侵杂草优化算法............................36
第五章 改进杂草优化算法求解 PFSP.................................49
5.1 ROV 编码.....................................49
5.2 NEH 初始化 ................................49
第六章 某钢管制造企业零部件生产调度实例研究
6.1 实例介绍
当前钢管企业流水生产车间调度问题是一个典型的置换流水车间问题，合理的优化钢管生产调度方案一方面是钢管生产车间指挥合理运行的重要手段，另一方面也是企业提高生产效率，加快企业转型升级重要领域。
我们以某钢管生产制造企业为例，该企业引进了先进的西德直缝钢管生产工艺，拥有各类大口径钢管加工制造设备，主要生产业务是为大型工程项目提供各类高精度钢管。产品远销世界，应用于煤矿气管网、大型多功能体育场馆、万吨级港口输油线路、大型码头建设、高速铁路场馆、钢构工程等重大工程建设之中，是由已成功应用于国内外超百个高端制造工程。
该企业在钢管制造领域具备丰富的技术储备，企业生产产品主要包括直缝钢管、直缝焊管、热扩钢管、焊接钢管、高频焊管（ERW）、大口径直缝钢（LSAW）管等。钢管制造工艺优良，产品成功应用到各类高压油气线路、热力管道、水路管线、船舶工程、钢构建筑、高压电路铁塔等重要领域。
当前该钢管企业存在着车间调度依赖于企业内部车间调度经验积累丰富的调度员来制定作业调度计划的问题。这对于该企业车间规模较小的时期来说是可行的，但是一旦面临车间规模增大、个性化订单、动态需求以及小批次多样化的订单需求，通过调度员安排车间调度计划就变得没有效率了。那么根据企业自身的运营方式、生产替理、产品工艺等方面的发展情况来进行研究，找出与之相适应的生产调度方法，并将其引入到信息系统中,改善企业车间加工效率，提升企业效益。将钢管企业流水车间调度进行智能算法优化有利于提升企业生产效率，降低总完工时间，减少企业生产资源消耗的同时也可以减少未完工产品。设备使用率一般定义为设备在实际加工使用时间与总计划完工时间的比值，在实际企业生产中表现为加工设备的使用效率，这在一定程度上反映了加工设备工作状态以及生产效率的情况，是典型的技术经济指标之一。钢管企业的生产设备成本往往占了较大比例的总投资。
.......................
第七章 总结与展望
7.1 研究结论
本文阐述了研究背景、研究意义及国内外文献综述，对置换流水车间问题进行描述并分类，介绍了置换流水车间调度问题及其分类，有零空闲 PFSP、有限等待 PFSP、分布式 PFSP、多目标 PFSP，PFSP 的研究方法包括三类：精确方法、构造性启发式方法和元启发式算法；提出了一种基于 levy 飞行的入侵杂草优化算法，针对基本入侵杂草算法易陷入局部最优的特点，引入 levy 飞行、自适应惯性权重、定向变异三种改进策略，用6 个标准测试函数验证改进算法的优越性；提出了一种混合变异花授粉算法将异花授粉的过程中引入混沌算法进行随机扰动以扩大种群多样性，自花授粉的过程引入交流算子以增强种群之间的信息交流，用 10 个标准测试函数验证改进策略的可行性。构建以最小化最大完工时间的置换流水车间调度问题模型，将改进入侵杂草优化算法通过 ROV解码和 NEH 寻找初始解，用于求解该模型，通过入侵杂草的繁殖、空间扩散和竞争策略,动态生成种群,我们采用 Carlier 和 Reeves 标准案例使用以上算法进行求解，然后并将各自的算法实验结果同其他算法进行比较。针对某钢管生产加工车间的调度需求，将邻域搜索策略引入基本花授粉算法中，构建以最小化最大完工时间、最大化最小设备利用率的置换流水车间调度问题模型，用于求解具体实例，对于企业合理调配生产资料和生产力，提高生产经济性提出对策建议。
参考文献（略）