智能制造系统：计划与控制 课件 第三章 智能调度

第3章智能调度3.1智能调度概述3.2智能调度的关键技术3.3数字化质量管理应用示例3.4数字化质量管理发展趋势3.1

智能调度概述制造系统的调度问题制造系统的调度问题是指在一定时期内按照指定的性能指标标准来安排生产任务及分配制造系统资源的过程。调度问题的定义调度的本质是通过对有限资源（包括物质、时间、资金、人员等）的合理配置，寻求系统目标（如产量、效率、速度、负荷等）的最大化，最终满足客户及自身的目标要求。供应链层级的调度问题企业生产调度车间生产调度企业级以上层面的制造系统企业级的制造系统资源调度车间级的制造系统资源调度1经典三元组表示：α(机器环境)、β(加工约束)、γ(性能指标)

调度问题描述单机并行机同速机恒速机变速机流水车间柔性流水车间作业车间开放车间α(机器环境)提交时间调试时间中断故障优先约束阻塞零等待再循环批处理交货期β(加工约束)基于加工完成时间的指标最大完成时间平均完成时间基于交货期的性能指标总延迟时间基于产量/库存的性能指标平均已完成工件数基于机器负荷的性能指标最大机器负荷γ(性能指标)3.1智能调度概述2生产调度方法类型基于启发式规则的方法基于运筹学的方法基于仿真的方法基于人工智能的方法单机/简单流水车间解析优化研究数学工具应用于调度优化证明多数调度为NP完全/NP难问题智能算法·仿真建模·数学求解器调度方法的发展3.1智能调度概述3启发式规则启发式规则，又称调度策略，是指选取工件的某个或者某些属性作为工件的优先级，按照优先级的高低顺序选择工件进行加工的方法，具有计算量小、效率高、实时性好的优势。基于优先分派的规则基于负载平衡的规则混合规则这种方法是给所有待加工的工序分派一个优先权，按优先权次序排序，然后选择优先权最高的工序。RandomFCFSSPTLPT负载平衡问题就是如何将任务均匀分配给各工作站，使系统效率最高。静态负载平衡调度策略：工作站的任务量、任务间的通信量都为定值，不随时间变化。动态负载平衡调度策略：每台工作站上的任务是动态产生的，并且每台工作站的负载大小是动态变化的。混合不同的调度规则，旨在实现一个实时的调度算法。在混合调度规则方法中，由于每台机器可以申请不同的调度规则，故需要指定一个组合的基本调度规则。3.1智能调度概述4运筹学方法该方法是将生产调度问题转化为数学模型，设计目标函数、约束函数及变量，最终提炼成数学规划模型（如线性规划、整数规划、目标规划、动态规划等模型），采用基于枚举思想的分支定界法或动态规划算法求解调度问题的最优解或近似最优解，属于精确算法。方法原理典型应用场景🔥拉格朗日松弛法松弛部分约束+添加惩罚函数作业车间调度问题分解方法拆解问题→子问题优化→集成求解复杂系统调度🔥分支定界法动态剪枝搜索解空间⚠️限于N<250​​1960s理论奠基​​追求多项式时间复杂度的​​确定性最优解​​核心方法：​​混合整数规划(MIP)​​计算瓶颈：整数变量数量随问题规模​​指数级增长​发展历程​​CPLEX/Gurobi/MOSEK等数学求解器→封装优化算法，免除底层编程→实现​​全局优化调度​​→可接受时间内生成​​理论最优解​现代求解器实际应用瓶颈​动态响应短板​​特殊约束场景需简化假设无法满足​​动态重调度​​的实时需求3.1智能调度概述5基于仿真的方法该方法模拟实际制造系统的运行过程，借助仿真软件平台构建制造系统的仿真模型（一般根据具体制造系统的特点，分为离散事件系统模型和连续系统模型），模拟不同的任务需求、分派调度策略及状态变量等，用于生产线布局、工厂资源分配和调度、生产过程、仓库和物流等方面的预规划优化。设计仿真实验评价指标仿真模拟计算调度优化解对比分析发现问题调整优化降低成本3.1智能调度概述6基于人工智能的方法针对调度问题普遍存在的NP-hard特性及动态复杂性，人工智能方法通过融合启发式规则、智能算法与仿真技术，突破传统数学规划的计算局限，在降低求解时间的同时发现更优解决方案，实现制造系统的高效优化调度。智能方法规则智能选择启发式规则+仿真+智能算法计算智能驱动演化算法/神经网络群体智能协同蚁群/粒子群优化3.1

智能调度概述7智能调度一般认为，随着调度问题规模的扩大、约束的增加、覆盖面的增大，其计算复杂性也越来越高，现实中的许多组合问题比较复杂，要从可能的组合或序列中寻求出最佳调度方案需要很大的搜索空间，可能产生组合爆炸问题。采用传统的基于规则的算法，难以取得理想的调度结果，因此需要用智能算法进行调度。这种采用智能算法的调度问题被称为智能调度。基于人工智能的调度基于计算智能算法的调度基于智能体的自主调度人工智能也称机器智能，它是由计算机科学、控制论、信息论、神经生理学、心理学、语言学等多种学科互相渗透而发展起来的一门综合性学科。专家系统人工神经网络计算智能以人类、生物的行为方式或物质的运动形态为背景，经过数学抽象建立算法模型，通过计算机的计算来求解组合最优化问题。禁忌搜索模拟退火遗传算法人工免疫算法群体智能是受启发于群居生物的群体行为，并对之进行模拟抽象而成的算法和模型。蚁群优化蜂群优化微粒群优化3.1智能调度概述8起步阶段（2007-2011）1大量研究集中在车间调度、多智能体系统研究方向多围绕经典车间调度模型展开实际生产问题被简化提炼成简单的调度模型，从而设计基于运筹学或仿真的调度优化解。成熟阶段（2015至今）​3经典调度模型和“大数据”“互联网＋”“云”等理念相互结合，不断涌现出包含主动调度、动态调度、分布式协同调度、云调度等新颖关键词的研究课题。发展阶段（2012-2015）2调度问题得到广泛关注，以信息化、互动化、自动化为发展方向，以资源配置能力、运行效率、智能化水平为发展目标，拓展理论问题的适用范围，引入大量智能算法提升调度解的求解效率。智能调度发展现状3.1智能调度概述9智能调度特点与意义智能调度的特点适应动态环境考虑系统柔性和作业复杂性考虑其他生产环节的影响具有多目标性具备高效智能的算法与数字化工厂紧密结合智能调度的意义有利于减少加工等待时间，提高加工效率有利于降低库存，确保公司物流、仓储系统运行正常有利于提高产品生产管理水平，建立现代企业管理体系3.1

智能调度概述103.2智能调度的关键技术智能调度的关键技术人工智能技术模糊逻辑调度专家系统机器学习计算智能基于领域搜索的优化算法基于种群迭代的优化算法多智能体系统其他支撑数字化工厂的计算机关键技术机器视觉技术网络结构以及上云关键技术11人工智能技术-模糊逻辑Zadeh提出的模糊集合（以[0,1]区间的隶属度为核心）奠定了模糊数学基础，并衍生出模糊逻辑。该理论被应用于处理生产调度（如五类车间问题）中因信息不精确、主观性导致的不确定性（模糊调度），以提升系统适应性和灵活性，但其方法本身也存在局限性。3.2智能调度的关键技术12人工智能技术-调度专家系统专家系统是利用领域专家知识（存储在知识库中），通过推理引擎模拟专家决策来解决复杂问题的AI程序，其架构还包括用户界面。经历了从解决单一问题到多学科综合的演进，现代趋势是融合多种AI技术（如多智能体协作、神经网络）实现更强大的第四代系统。在调度领域，专家系统被专门用于生成生产计划，从早期的ISIS系统发展到如今常与其他智能算法（模糊逻辑、群智能等）集成应用，具备特定优势与不足。3.2智能调度的关键技术133.2智能调度的关键技术人工智能技术-机器学习调度中基于案例的推理调度中的归纳学习基于案例的推理(CBR)是由Schank(1982)提出的机器学习方法，其核心是通过“类比”（检索相似历史案例）来“复用”经验解决新问题，必要时进行“修正”，并将新解“保留”为案例实现增量学习（4R循环），区别于基于规则推导的专家系统。归纳学习是从具体实例推断类别通用描述（涵盖正面、排除负面）的常用方法，其代表性算法——决策树（1984年CART提出）通过递归选择最优特征并分割数据（生成）来构建树形分类/回归模型，并需剪枝优化。调度中的神经网络人工神经网络(ANN)是模拟人脑神经元连接的计算模型（本质是大规模并行分布式处理器），通过学习过程（调整突触权重）从环境中获取知识并存储在连接中，使其具备学习、记忆、模式识别等智能处理能力；学习完成后，收敛的权重矩阵使网络能对输入数据进行有效处理（如分类）。14计算智能-基于领域搜索的优化算法模拟退火算法传统局部搜索易陷入局部最优，邻域搜索（LS）算法通过启发式初始解和迭代改进对其进行扩展；为突破局部最优实现全局优化，关键策略包括：概率接受劣解（模拟退火）、扩大邻域（如k-opt）、变结构邻域搜索以及利用禁忌表避免迂回的确定性突跳（禁忌搜索）。禁忌搜索算法模拟退火算法（源于固体退火物理过程）是一种随机优化方法：它从高温/随机解出发，通过迭代生成邻域解，并依据Metropolis准则（优解必接受，劣解按概率接受）决定移动；关键的温度下降机制控制着接受劣解的概率（高温高概率利于全局探索，低温低概率趋向局部求精），最终使算法能以概率突跳跳出局部最优并收敛到全局最优解。禁忌搜索（Glover,1986）是扩展局部邻域搜索的智能优化算法，通过动态禁忌表模拟记忆功能，标记并避开近期局部最优解以减少重复搜索；其核心机制（禁忌表、禁忌长度、藐视准则）确保探索多样性，最终实现全局优化。3.2智能调度的关键技术15计算智能-基于种群迭代的优化算法进化算法群体智能算法在邻域搜索算法中，每次迭代得到一个解，其效率不高，且易于陷入局部最优。而种群迭代算法是每次迭代得到一群（代）解，较优解是一群可行解中的最优。从算法机理上而言，一群解的迭代可以较好地规避过早陷入局部最优的情形。从其产生群（代）解的机理不同，种群迭代优化可分为进化算法和群体智能算法。

进化算法（含遗传算法、进化规划等）通过模拟生物进化过程（种群迭代+适者生存）解决优化问题；其中遗传算法（Holland,1970s）凭借交叉、变异、选择操作及种群机制，在调度等组合优化领域应用最广，能以较高效率获得鲁棒解。群体智能算法模拟昆虫/鸟群/鱼群等简单个体通过合作学习涌现的群体优化能力；在调度领域，PSO算法（1995）通过粒子追随个体与群体历史最优位置进行搜索，而ACO算法（1990s）则利用蚂蚁通过信息素正反馈和挥发机制、结合概率选择（信息素浓度+启发信息）来寻找最优路径（如转化后的TSP/JSP问题），有效避免局部最优。3.2智能调度的关键技术16多智能体系统智能体（Agent）的本质"自治的软硬件实体，模拟人类协作智能"自主性反应性社会性主动性适应性学习性进化性协同性多智能体系统（MAS）社会性自治性协同性MAS是指一些智能体通过协同完成某些任务或达到某些目标的计算系统，它是由多个自治或半自治的智能体所构成的大型系统。在实际生产过程中，常常有突发的生产订单、设备故障等动态现象发生，可能导致任务之间在时间、资源等方面的冲突。因此，生产计划调度系统的成功运行协调机制和协商／冲突解决策略非常重要，两者相辅相成，缺一不可。

3.2智能调度的关键技术17构建多智能体系统智能体模型MAS体系结构交互与通信一致性与协同性MAS规划冲突处理调度MAS中的协调机制基本问题若要众多自治的智能体呈现出系统层面更强的统筹智能性，还需要规划设计MAS的协调机制和冲突消解策略。基于约束的冲突解决

基于规则的冲突解决

基于事例的冲突解决

基于协商的冲突解决

3.2智能调度的关键技术183.2智能调度的关键技术其他支撑数字化工厂的计算机关键技术前面几节介绍的主要是智能调度涉及的软件与算法技术。智能调度若要真正实现，需要结合调度问题中的实体执行对象。实际生产系统的调度对实时性的要求非常高，许多数据需要实时采集、计算分析，然后高效决策、反馈控制，从而完成调度的完整闭环。193.3智能调度发展趋势智能算法的创新及落地计算智能算法创新层面：混合算法／集成算法多目标优化算法效率的提升算法落地应用层面：约束复杂性动态调度调度中人因的导入