本文是一篇物流管理论文，笔者认为作业车间调度问题（JSP）特别是柔性作业车间调度问题（FJSP）既是制造领域研究的热点问题，也是企业生产管理的核心问题，属于组合优化问题范畴，已被证明是 NP-hard 问题。精确方法虽然能求解出问题的最优解，但却有求解规模限制，还要花费大量的时间，不能满足现代制造企业的调度要求，而近似算法能在较短的时间内找到问题的近似解，被大量学者广泛研究，其中智能算法容易实现、计算速度快、计算量小、鲁棒性强、自我学习能力优越，成为解决 JSP 和 FJSP 的重要手段。
第 1 章 绪论
1.1 研究背景及意义
制造业是现代国民经济的主体，是立国之本、兴国之器、强国之基。中国经济要避免脱实向虚，实现制造业大国向制造业强国的转变，就必须掌握智能制造这项核心技术，向数字化、精细化、智能化、协同化的方向发展。迅速发展的全球经济，日益激烈的市场竞争，不断发展的科技制造以及逐渐多元化的市场需求，使得产品制造品种规格越来越多、批量缩小、更新换代速度加快、交货期也越来越短。这些变化使得传统生产制造模式不再满足现代企业的需求，好的调度与管理方案的有效获取，以提高管理和生产的高效稳定运行，实现及时交货、提高客户满意度，显得尤为重要，成为提升企业竞争力的关键。
复杂制造系统高效率、高柔性和高可靠性生产与调度息息相关。高效率的生产计划和调度优化技术能大幅提高制造企业的生产效率、设备等有关资源的有效利用率、减少物资和能源的消耗和浪费、缩减产品制造周期、降低成本，促进经济效益的增长，同时还能对企业库存水平、产品供货周期以及交货期满意度等重要指标进行优化，提升企业核心竞争力。调度问题不局限于制造行业，还广泛应用于物流运输、航空航天、通讯、项目管理和能源等各个领域[1]。
车间是制造系统物流、信息流、以及控制流相交汇的集结点，这使得车间调度成为连接计划和生产的关键活动。作为生产过程控制的神经中枢，作业车间调度能够对企业生产管理模式进行优化，加强对生产过程的控制力度，在满足资源条件的约束下，实现对企业管理目标的精细化优化，促进制造过程顺利。作业车间调度问题（Job ShopSchedulingProblem,JSP）被认为是调度领域最困难的组合优化问题之一，是 NP-hard 问题。它是一类具有机器唯一性约束的调度问题，工件具有固定的加工路径，也就是说工序的加工机器是指定的、且是唯一的。然而实际生产制造时，一个工序通常可以通过几台机器中的任意一个实现加工，在不同的机器上，加工时间的长短可能不同，这就是柔性作业车间调度问题（Flexible Job Shop Scheduling Problem, FJSP）。
.......................
1.2 作业车间调度问题优化方法
1954 年，Johnson[4]对两台机器排产问题进行研究，并提出了解决 /2/F/ 问题的优化算法，代表着调度理论研究的开始。直到现在，调度问题一直是一个热点研究问题。为了使研究更适用于实际生产，调度模型越来越复杂，求解难度也越来越大，研究方法从最初的数学方法逐渐偏向于启发式智能算法。目前，学术界提出的求解 JSP 的各种优化方法，总结起来，分为精确法和近似法两种。
1.2.1 精确方法精确方法
在理论上能求解到全局最优解。但是，从可行编码方案个数的公式也不难看出，用精确法求解作业车间调度问题的代价很大，随着工件数、机器数、工序数和工序可选机器数的增加，解空间会发生指数级爆炸现象，使得问题的复杂度、求解运算量和求解难度大大增加，在有限的时间内不能确定各工件的加工路径[5]。所以精确方法只适合求解规模较小的 JSP，而且求解速度慢，越来越难以满足现代生产制造业的要求。
精确方法主要有数学规划方法和分支定界法等。
（1）数学规划方法包括拉格朗日松弛法、整数规划法、混合整数规划法以及分解方法。在优化较大规模复杂问题时，该方法时间花费巨大，求解十分困难。其中求解调度问题最常用的是混合整数规划法，它限制所有的决策变量都是整数，在一组线性约束下求解一个线性目标函数，这种求解方法往往需要大量的约束条件。分解方法是将原问题分解为多个小的子问题，对各个子问题分别优化，以此降低问题的求解难度。
（2）分支定界法通过动态树结构描述所有的可行解排序的解空间，将可行解包含在树的分支中。Balas[6]于 1969 年提出的基于析取图的枚举算法是最早用来求解调度问题的分支定界法。同数学规划方法相似，分支定界法也仅适合求解规模较小的 JSP，当调度系统的总工序超过 250 时[7]，就需要大量的计算时间，如此低的求解效率限制了它的使用。
...............................
第 2 章 问题描述与研究现状
2.1 问题描述
2.1.1 车间调度问题概述
1954 年，Johnson[4]对两台机器排产问题的研究揭开了车间调度问题研究的序幕。几十年间，生产的需要和相关技术的发展尤其是智能优化算法的不断提出和改进，促使国内外学者一直关注并研究车间调度问题。截止到目前，该问题理论研究已经取得了丰硕的成果，在工业工程和运筹学等学科中形成了独立的研究分支。
典型的车间调度问题就是在一系列资源条件的约束下，为一个待加工工件集合合理分配加工机器、合理安排加工时间，以优化调度指标的过程。该待加工工件集合中的每一个工件都包含一个工序集合，每个工序集合都由一组具有顺序约束的工序组成，不同工件的工序集合可以不同，在机器设备上按加工顺序完成加工。调度过程就是合理匹配加工工件、加工工序和加工机器这三个集合中的元素，为加工系统协调出高效的可行加工方案。
车间调度依据加工系统的复杂程度分为作业车间调度、流水车间调度和开放式车间调度。
作业车间调度问题（JSP）：这是最普遍的车间调度形式。机床设备的布局可任意安排，工件的加工路径也可任意，每个工件的工序以及工序数可以不同。
流水车间调度问题（Flow Shop Scheduling Problem，FSP）：机床设备流水线布局，所有工件的加工工序和工艺路线完全相同，依次从流水线的一端进入，顺序完成所有工序后，从另一端流出。
开放式车间调度（OpenShopScheduling，OSP）：工件的制造工艺路线无特定约束，各工序之间没有顺序约束，每道工序既可以在第一道也可以在最后一道加工。
.............................
2.2 作业车间调度问题的研究现状
20 世纪 60 年代，国内外学者就用枚举、数学规划和规则调度等方法求解了 JSP。70-80 年代，各学科的交叉发展以及对该问题研究的深入，大多数 JSP 被证明是 NP 完全问题[34]。90 年代，计算机、生物和工业等领域的发展和知识融合，许多研究者借助新技术开始使用近似方法求解作业车间调度问题，提出了禁忌搜索算法[35]、模拟退火法[36]、神经网络算法[37]等调度理论与方法。90 年代后，又有学者提出了蚁群算法[38]、粒子群算法、蛙跳算法等大量新的方法。直到现在，JSP 一直是研究的热点问题，研究者尝试使用了各种方法来求解它。早期以 GA 最多，同时新的智能算法不断涌现，为 JSP 的理论研究奠定了基础。但是每种调度算法都存在一定程度的缺点，随着各种算法日渐成熟，研究者们尝试将各种近似算法结合起来，扬长避短、各取其优，出现了许多融合算法来求解 JSP，如混合遗传算法[39]、混合蝗虫优化算法[18]、混合遗传模拟退火算法[40]、混合鲸鱼算法[41]等。
国内最早对 JSP 开展研究的是越民义[42]，他提出了 个零件在 台机床上加工顺序的问题。徐新黎等[43]对神经网络进行改进，保证得到的作业车间调度方案是全局最优或近似全局最优的可行解。黄志等[44]针对最大完工时间最小的 JSP，为有效解决不可行解的产生，采用转换瓶颈算法大幅提高了车间生产效率。赵良辉等[45]提出了回火退火算法和快速模拟退火算法，并且分析了两种算法的差异，指出回火退火算法在求解单个工序耗时长而总工序不多的 JSP 时具有明显优势，快速模拟退火算法非常适合求解大规模调度问题。胡中华等[46]模拟蜜蜂群寻找优良蜜源的过程实现组合优化问题的求解，用人工蜂群算法（ABC）求解了 JSP，该算法即能克服早熟现象，还能加快收敛速度，具有一定的通用性。
............................
第 3 章 郊狼优化算法及其改进研究...............................17
3.1 郊狼优化算法.................................17
3.1.1 种群初始化并随机成组...........................18
3.1.2 郊狼成长..........................18
第 4 章 改进郊狼优化算法求解作业车间调度问题....................37
4.1 数学模型............................37
4.2 求解离散问题的算法改进设计.........................38
第 5 章 改进郊狼优化算法求解柔性作业车间调度问题..........................51
5.1 数学模型................................51
5.2 FJSP 编码方案.............................53
第 5 章 改进郊狼优化算法求解柔性作业车间调度问题
5.1 数学模型
本章 FJSP 要解决的问题是：以最大完工时间最小为评价指标，在满足相关约束的条件下为每道工序分配加工
