1. 研究目的与意义（文献综述）

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难问题。这些实际的优化问题通常可能来自给定数学模型的多个全局或局部最优（即，目标函数）。如果将一个逐点的经典数值优化方法用于解决该类问题，经典方法每次都要将花费大量的时间寻找不同的最优解，使得工作量大幅增加，工作效率降低。因此，受自然启发的元启发式算法凭借其易于实现，并且更快收敛到全局最优的优势，已然成为一个热门的研究课题。

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

2.1研究的基本内容

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

第一章：绪论

主要介绍本毕业设计的研究背景、意义和研究内容，综述调度问题、现有求解方法和国内外研究现状等情况，最后对论文的结构和主要研究工作进行了阐述。

第二章：柔性作业车间调度问题

针对柔性作业车间调度问题进行详细介绍，同时建立柔性作业车间调度问题数学模型，逐渐深入，最终围绕单目标和多目标两种情况进行阐述。

第三章：鲸鱼群算法总体设计

描述鲸鱼群算法基本原理，并建立算法模型，该模型来源于曾兵等建立的求解最优化函数的鲸鱼群算法，本课题针对于柔性作业车间调度问题进行改进，包括初始化配置参数，种群初始化，对种群个体的评估，鲸鱼（种群）移动等，以获得全局最优解。

第四章：鲸鱼群算法详细设计

分别详细阐述种群初始化、鲸鱼群算法的算法框架及具体步骤，并使用MicroSoft Visual C 6.0进行C 编程。

第五章：实验结果及分析

为检验算法效果，在标准算例集中选取不同规模问题进行测试，对求解结果进行分析，并与采用同算例的文献进行算法的比对测试。

第六章：总结、分析与展望

2.2研究目标

提出一种利用鲸鱼群算法求解柔性作业车间调度问题的调度算法。

2.3拟采用的技术方案及措施

（1）建立柔性作业车间调度问题数学模型

FJSP可描述为：加工系统有n个工件在m台设备上加工，每个工件包含个预先确定加工顺序的工序，每个工序可在多台设备上加工，且加工时间随着设备性能的差别而不同。调度目标是在设备能力约束和工序约束下，将工序分配到设备，并确定在每台设备上工件的加工顺序。

FJSP的数学模型涉及的参数定义如下：

M={|1≦k≦m}，表示设备集；

J={|1≦i≦n}，表示工件集；

={|1≦j≦}，表示工件的工序集；

={|=1}，表示工件的工序的可用设备集；

表示工序在设备上的加工时间；

表示工序在设备上的开始加工时间；

表示工序在设备上的完工时间；

表示所有工件在设备上的完工时间；

FM表示所有工件的最后完工时间；

1 工序由设备加工；

=

0 其他

1 与同在上加工，先加工

=

0 其他

以最小化最大完工时间为目标函数：

min FM = min（max（）） ，1≦k≦m

对以上问题做以下约束：

设备约束：—≥，

=1， ==1，表示每台设备同一时间只能加工一个工件。

过程约束：—=，

=1，表示工序的加工过程不可中断。

工艺约束：—≥ 0，

==1，表示同一工件的工序之间有顺序约束，不同工件间不存在工序约束。

（2）建立鲸鱼群算法基本流程框架

鲸鱼群算法源于鲸的捕猎行为。在捕猎时，鲸鱼依靠超声波传递信息进行判断，从而积极地、随机地朝靠近它的“最佳”鲸鱼方向移动，并向远离它的鲸鱼进行消极的、随机的移动。其中鲸鱼X在其“最佳”鲸鱼Y的引导下进行的移动可描述为：

（1）

通过该公式实现鲸鱼个体的移动。具体算法流程如下：

图1 鲸鱼群算法流程图

首先初始化配置参数、初始化个体的位置和对每个个体进行评估，这与大多数其他的元启发式算法是相似的。在这里，每条鲸鱼对应一种调度方案。所有的鲸鱼都被随机分配到搜索区域。接下来是鲸鱼群算法的关键步骤:鲸鱼移动。即每只鲸鱼都需要通过集体合作来获得更好的食物。首先，一条鲸鱼应该找到它的“最佳”鲸鱼，如果它的“最佳”鲸鱼存在，那么它将在“最佳”鲸鱼的指导下按照公式（1）所示进行移动，若不存在则按照随机方法重新组成调度方案并返回进行个体评估，直到满足结束要求，输出全局最优解。

1. 种群编码与解码

   种群编码采用两段式编码方法，第一段基于工序顺序编码，第二段基于设备分配编码。先建立一张工序顺序表OS，将工序按照工件顺序和工艺顺序排列，参照表1可得{，，，，，，，}。编码长度与工序数一致，即遍历全部工序。对于第一段编码W，每个码位用于记录工件号i，工件出现出现的次数i即工件所要加工的工序数；第二段编码同第一段长度一致，每个码位对应加工该工序的设备在设备集M中的编号。如图2所示为根据表1的示例产生的可行解的编码，在的W编码中，=1表示工件的第二个工序；G编码中，=3代表工序在其设备集中的设备上进行加工。将不可用于加工工序的设备的时间设置为0，从而在编码时避免取到该设备，保证编码的有效性、合理性。

   在解码阶段，由编码W可得出各工件的加工序列，由G根据工序表可得出每个工序的加工设备，再按照时间约束和设备约束将工序安排在适当的时间，生成最终调度方案。

   
   

   表1 一个部分柔性的3×4 FJSP

3. 研究计划与安排

4. 参考文献（12篇以上）

[1] phu-ang a, thammano a. memetic algorithm based on marriage in honey bees optimization for flexible job shop scheduling problem[j]. memetic computing, 2017, 9(4): 295-309.

[2] li x, gao l. an effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem[j]. international journal of production economics, 2016, 174: 93-110.

[3] zhang g, gao l, shi y. an effective genetic algorithm for the flexible job-shop scheduling problem[j]. expert systems with applications, 2011, 38(4): 3563-3573.