生产调度及智能优化讲义总结

生产调度及智能优化

陈静杰博士

教授航空自动化学院航空电子系

中国民航大学数据分析研究所

24092499（O）5/17/2023生产调度生产调度与运筹学Q：区别？联系？生产调度运筹学5/17/2023生产调度什么是生产调度？即按时间分配资源完成任务/作业的过程或方法。要求：任务/作业必须是可分割的。生产调度问题Q：现场有哪些？5/17/2023生产调度生产调度与生产计划都是对生产过程的规划与控制（均考虑优化的目的），主要区别是考虑的时间尺度不同，理论上均称调度问题；生产调度是生产计划的可行性验证过程生产计划侧重于经营计划和生产能力的平衡，考虑的时间以月或年计的中长期——粗生产调度则在较短的时间内进行，最主要的任务是生产作业的安排与资源的具体分配，涉及实际生产环境的各种约束——细5/17/2023生产调度生产调度与生产计划生产计划的制定以企业的利润最大化为目标，而生产调度则以生产过程的平稳过渡/顺畅接续为目标。生产计划的制定，一般是考虑静态情况。当生产因素比较稳定和比较理想时才能达到优化的预期目标生产过程是动态的，要求生产调度系统有一定的柔性，能适应生产过程中内、外因素的异动，以便准确而灵活地完成生产计划；生产调度侧重于生产装置的分配利用和物料平衡。5/17/2023生产调度生产计划优化系统优化系统可根据企业的产、供、销状况，以企业综合效益为目标，建立合适的数学模型，依一定方法求解，分别考虑企业内外约束，进而获得最优计划；计划的实施，必须充分利用现有资源，优化资源配置，提高生产决策的科学性，实现效益的最大化。5/17/2023生产调度生产调度系统的功能计划的分解：一般采用时间分配方法，即滚动计划；动态监控：①实时监控，包括数据的采集、关键参数的历史趋势图分析、图表及工艺流程的显示。②平衡协调，包括外部的—生产和经营两大系统—产供销，内部—生产过程—人员工位器具等5/17/2023生产调度生产调度系统的特点复杂性；随机性；多约束；多目标。Q:维修作业调度系统特点的表达?5/17/2023生产调度生产调度问题的一般描述语义描述：目标-任务集合-资源集合-约束条件；数学描述—调度问题的数学符号表达。生产调度问题的性能指标能力指标：最大生产率、最短生产周期等；成本指标：最大利润、最小费用等；客户满意度指标：最短交付期（提前拖期惩罚）等5/17/2023生产调度生产调度问题的分类依模型变量分类：1）连续变量问题；2）离散变量问题/组和优化问题（combinatorialoptimizationproblem:COP）依生产过程输出：1）连续生产过程（连续的产品流）；2）间隙生产过程（离散批量）/批处理过程—批处理调度问题；3）离散生产过程（离散数量）—车间调度问题按调度目标：总的作业时间最短、总的延迟时间最小等其他：依人物特点：可否终端、加工时限、顺序约束等5/17/2023生产调度问题的分类车间调度问题：车间调度加工设备的分配工件的加工时间与加工顺序实质生产调度5/17/2023生产调度问题的分类流水车间调度问题：分类（基于加工时间或交付期）：确定型、随机型和模糊型/满意型生产调度5/17/2023NP难题工程近似可用解生产调度生产调度问题的分类作业车间调度问题：JSP问题可以采用整数线性规划模型描述。前提假设：所有的任务在零时刻都可用，且无设备故障，任务在机器上执行时间事先已知5/17/2023生产调度生产调度问题的分类间隙生产调度问题：分类：多产品（multi-product）间隙生产过程[所有产品生产顺序相同，加工路径相同，整个生产过程分成若干个生产阶段，每个阶段包含若干并行设备。类似Flow-shop]和多用途或多目的（multi-purpose）间隙生产过程[可以是不同的生产线、不同的路径、不同的工序，可通过设备的组织来调整。类似Job-shop]排序的问题中间产品存储策略等待时间切换时间上层组织路经与时间分配下层设备与资源分配决策5/17/2023生产调度生产调度问题的分类动态调度问题：静态调度：调度环境和任务已知的前提下的所谓的事前调度方法—例行维修作业动态调度：也称再调度，指在调度环境和任务存在不可预见的扰动情况下的调度方案，即依赖于事前调度环境和任务也与当前状态有关—例行+非例行维修作业为适应生产过程的不确定性和随机性，一般采用周期性调度和再调度相结合的策略5/17/2023生产调度生产调度问题的分类动态调度问题（续）：动态调度形式：滚动调度（rollingscheduling）和被动调度（reactivescheduling）被动调度目标是尽可能维持原静态调度水平，既保持原有的性能指标滚动调度：移动时间段内的生产调度；被动调度：随生产过程变化而不可行的调度的修正动态调度的实时性要求Q：变化（加工时间、任务、设备故障等）—调机作业5/17/2023生产调度生产调度方法分类：优化调度方法和启发式调度方法优化调度：精确求解解析模型而获得最优解、近似求解得次优解；基础：数学规划；适用：小规模优化问题启发式调度：包括基于规则的方法、基于人工智能的方法、随机搜索方法、基于仿真的方法等，立足当前，追求局部最优而非全局最优方向：二者结合启发推理5/17/2023生产调度生产调度方法（续）数学规划等式与不等式约束分支定界法Lagrangian松弛法贝叶斯启发方法规则调度方法简单规则复合规则启发式规则动态调度依靠机器学习的动态选择规则利用神经网络实现智能选择规则基于人工智能方法启发式搜索规则基于规则与知识的方法智能求解方法ANNsGAFuzzySetsModel-basedandmodel-free5/17/2023生产调度的启发式算法启发式算法（heuristicsalgorithm）语义性描述：一个基于直观或者经验构造的算法，在可接受的代价下，给出待解决组合优化问题的一个可行解未定义可行解与最优解的距离5/17/2023生产调度的启发式算法启发式算法（heuristicsalgorithm）Johnson问题：以最大流程时间为目标的两台机器流水车间调度问题—依Johnson规则确定其最优调度问题描述：n个工件在机器1和机器2上的加工时间分别为ti1和ti2，目标是给出最短生产周期的产品序列5/17/2023生产三调度三的启三发式三算法启发三式算三法（he三ur三is三ti三cs三a三lg三or三it三hm）基于三Jo三hn三so三n规三则构三造最三优调三度，三步骤三如下三：5/三4/三20三23生产三调度三的启三发式三算法启发三式算三法（he三ur三is三ti三cs三a三lg三or三it三hm）例：工件123456机器1上加工时间10511379机器2上加工时间47981015问题三的关三键是三启发三式规三则的三建立启发三式算三法通三常是三以牺三牲计三算时三间为三代价5/三4/三20三23生产三调度三的启三发式三算法启发三式算三法（he三ur三is三ti三cs三a三lg三or三it三hm）常用三启发三式规三则：用优三先分三配规三则来三解决三工序三中可三能的三加工三冲突三（要三求算三法有三识别三所有三加工三冲突三的能三力）基于三随机三分配三规则三的启三发式三算法三：每三一工三序都三对应三启发三式规三则集/族中三的任三意规三则，三规则三可重三用，三全部三工序三遍历三一遍三后即三可找三到生三产活三动调三度—工序三顺序三集5/三4/三20三23遗传三算法遗传三算法三：借三鉴生三物界三自然三选择三和自三然遗三传机三制的三随机三算法原理三：始三于多三个初三始解三，然三后通三过一三定规三则进三行逐三步迭三代产三生新三的解三，合三成解三集，三通过三对解三集中三解的三性质三的判三断，三筛出三需要三的解5/三4/三20三23遗传三算法遗传三算法三：借三鉴生三物界三自然三选择三和自三然遗三传机三制的三随机三算法算法三设计三的内三容：编码—解空三间适应三度函三数—解的三质量三的度三量/目标三函数选择三策略—大适三值解三对应三大存三活概三率/机会控制三参数—种群三规模三、算三法代三数/终止三准则三、遗三传操三作概三率等遗传三算子—选择/遗传三、交三叉、三变异缺点三：没三有利三用目三标函三数梯三度等三信息三，造三成了三解的三无方三向性5/三4/三20三23基于三遗传三算法三的车三间调三度问三题遗传三算法三：把三调度三问题三参数三表达三成按三一定三结构三组成三的染三色体三编码部分三算法三设计三内容三：编码—工件三加工三顺序适应三度函三数—完成三加工三作业三可能三的最三大流三程时三间的三倒数三（流三程时三间越三短越三好）选择三策略—大适三值解三对应三大存三活概三率/机会控制三参数—种群三规模三、算三法代三数/终止三准则三、遗三传操三作概三率等遗传三算子—选择/遗传三、交三叉、三变异5/三4/三20三23基于三遗传三算法三的模三糊车三间调三度方三法主要三解决三提前/拖期三费用三调度三问题—利用三模糊三量表三示客三户对三交货三期的三满意三程度Q：三航班三延误三问题A1三：可三用随三机规三则调三度法A2三：也三可用三模糊三调度三法5/三4/三20三23基于三同一三时间三离散三化生三产调三度把调三度范三围分三成许三许多三多等三长度三的时三间段—民航三维修三作业三标准三工时三下的三派工三问题三，然三后明三确约三束条三件（三分配三约束三、容三量约三束、三物料三平衡三、公三共及三人力三资源三限制三），三最终三可表三达为三以利三润最三大为三目标三函数三的调三度问三题一个三经典三的调三度问三题5/三4/三20三23不确三定性三生产三调度三问题生产三系统三的不三确定三性：1）加三工期三的不三确定三性，三如：三备件三与故三障件三的不三匹配三；2）存三储容三量的三不确三定性三，如三：最三优库三存容三量问三题即三存储三容量三的上三下限三的确三定；3）人三的行三