1.1研究背景

20世纪年代以来,我国制造业持续高速发展,成为国民经济发展的主要拉动力量。车间生产调度是制造系统的基础,生产调度的优化是先进制造技术和现代管理技术的核心，即“如何把有限的资源在合理的时间内分配给若干个任务,以满足或优化一个或多个目标”。调度优化问题几乎存在于各个领域,比如企业管理、交通运输、航空航天、医疗卫生、能源动力和网络通讯等,由此可见对调度问题的研究有重大意义。

调度问题的研究始于20世纪50年代，1954年Johnson提出了解决n/2/F/和部分特殊的n/3/F/问题的有效优化算法，代表经典理论研究的开始。柔性作业车间调度问题（Flexible Job Shop Scheduling Problem,FJSP）是经典作业车间调度问题的扩展,该问题除了要解决JSP中的确定加工顺序外，还要解决各工序分配到哪台机器进行加工，使问题更加复杂。柔性作业车间调度问题已被证明属于NP难问题，难以找到多项式时间算法，因此有效的启发式算法成为解决FJSP问题的主要途径。80年代以来，随着计算机技术、生命科学和工程科学等学科的相互交叉渗透，许多跨学科的方法被应用到研究中，如神经网络技术、遗传算法、约束传播、粒子群优化、蚁群算法和DNA算法等新算法大量涌现。每种算法都有一定的优势，却也存在一定的缺点。故针对实际调度问题的复杂性和多样性，提出有效的搜索方法与算法模型获得全局最优解，对于柔性作业车间调度问题研究发展及实现先进制造企业的现代化具有重要的理论价值和实际意义。

1.2 国内外研究现状

自然启发式算法在解决数值优化方面彰显了越来越强大的功能，特别是在旅行商问题、车辆路径规划、分类问题、无线传感器网络路由问题和多处理机调度问题等NP难问题。这些实际的优化问题通常可能来自给定数学模型的多个全局或局部最优（即，目标函数）。如果将一个逐点的经典数值优化方法用于解决该类问题，经典方法每次都要将花费大量的时间寻找不同的最优解，使得工作量大幅增加，工作效率降低。因此，受自然启发的元启发式算法凭借其易于实现，并且更快收敛到全局最优的优势，已然成为一个热门的研究课题。

遗传算法(GA)最初由Holland提出，以解决数值优化问题，它模拟了达尔文的基因选择和自然淘汰的生物进化过程，并揭开了自然启发的元启发式算法的序幕。该方法主要通过个体（染色体）选择、交叉和变异来尽可能寻找全局最优解。其中，通过结合两个个体的部分来创造新的个体的交叉算子显著地影响了遗传系统的性能。Michalewicz提出了随机(均匀)突变和非均匀突变来解决数值优化问题。Deb提出的多项式变异算子是最广泛使用的变异算子之一。自1975年Holland教授提出GA以来，国内对其在求解车间调度问题的文献非常多，其中清华大学的王凌和郑大钟较好的对GA及其在调度问题中的应用进行了分析和总结。总之，在处理不同的优化问题时，选择或设计合适的选择、交叉和变异算子是非常重要的。

Storn和Price提出的微分进化(DE)算法，以尽量减少可能的非线性和不可微的连续空间函数。它包含与遗传算法不同的三个关键的操作，即突变、交叉和选择。首先，在微分进化算法的变异阶段产生一个与目标矢量的每个成员矢量相对应的供体矢量。然后，交叉操作发生在目标矢量和供体矢量之间，其中试验矢量是通过从供体矢量或具有交叉概率的目标矢量中选择分量而产生的。选择过程决定了目标矢量或试验矢量能否在下一代中存活。如果试验矢量更好，它将取代目标矢量;否则，目标矢量将继续保持在群体中。自方案提出以来，DE算法在解决许多实际的优化问题中越来越受到研究者和工程师的欢迎，针对不同的实际问题衍生出了各种解决方案。常用的微分进化算法方案有DE/best/1/bin, DE/best/1/exp, DE/rand/1/bin, DE/best/2/exp, E/rand/2/exp等。

粒子群优化(PSO)是由肯尼迪和埃伯哈特提出的一种基于群体智能的算法，该算法的灵感来自于鸟类群集的社会行为。自该算法被提出以来，已经被应用于解决许多复杂且困难的实际优化问题。在传统的PSO算法中，每一个粒子都根据其速度和位置的更新，移动到一个新的位置，粒子位于该更新位置的速度与它的认知最佳位置和社会最佳位置有关。到目前为止，针对不同的优化问题科研工作者提出了大量的PSO变体模型。例如Shi和Eberhart在PSO (PSO- ldiw)中引入了线性减少惯性权重，它可以平衡全局搜索和局部搜索，用于函数优化；Zhan等提出了函数优化的自适应PSO (APSO)，实现了参数的自动控制，提高了搜索效率和收敛速度，并采用了一种精英学习策略，跳出了可能的局部最优解；PSO算法在车间调度中的应用国内研究较多，尤其华中科技大学的高亮等在PSO算法的应用方面做了大量的工作。PSO算法最初应用于连续问题优化，如何较好的离散化应用于组合优化问题是一个研究热点。除此之外，还有大量其他的自然启发算法，如蚁群优化(蚁群算法)、蜜蜂群优化(BSO)和大爆炸(BB-BC)等。

1.3研究目的

提出一种利用鲸鱼群算法求解柔性作业车间调度问题的调度算法。建立柔性作业车间调度问题的数学模型，基于鲸鱼狩猎行为的新颖的迭代规则，将鲸鱼群算法应用于解决柔性作业车间调度问题，避免算法陷入局部最优并提高全局搜索能力，从而得到柔性车间作业问题的全局最优解。

1.4研究意义

如今，受自然启发的元启发式算法凭借其易于实现，并且更快收敛到全局最优的优势，已然成为一个热门的研究课题。目前，求解FJSP问题的常用方法有模拟退火（SA）、禁忌算法（TS）、粒子群算法（PSO）和遗传算法（GA）等。但由于实际调度问题的复杂性和多样性，以上方法并不能完全满足所有FJSP问题的要求，需要引入更多新思想为解决FJSP问题提出更优的解决方案。本课题即通过将鲸鱼群算法应用于解决柔性作业车间调度问题，提高种群的多样性和全局的勘探能力，避免算法陷入局部最优，为求解FJSP问题提出了一种新方式，具有很大的理论研究意义。

从实际生产方面来讲，实际生产状况中具有多资源、多约束和动态等特性，柔性作业车间调度问题在实际生产中更具有应用价值。本文由单目标柔性作业车间调度问题开始研究，逐渐深入，进一步对多目标柔性作业车间调度问题进行研究，减少实际生产中设备的闲置和等待时间，提高设备利用率，使各道工序之间更加连续、紧凑。本文采用C 编程写出算法的代码形式，可应用于企业创造价值。由于现实应用中会遇到更加复杂的调度问题，进一步丰富车间调度理论成果并应用于实际生产调度问题或缩小理论成果与实际问题的差距，都将会产生巨大的经济效益和实践价值。

2. 研究的基本内容与方案

2.1研究的基本内容

本课题“基于鲸鱼群算法的柔性作业车间调度方法研究”，对现有鲸鱼群算法进行改进，并将其应用于求解柔性作业车间调度问题，利用鲸群形成过程中个体位置改变的迭代方式，保证种群多样性，避免算法陷入局部最优，提高全局搜索能力，获得全局最优解。主要工作内容包括：