生产管理知识_制造过程调度理论及应用教材

制造过程调度理论及应用SchedulingTheoryforManufacturingProcessandItsApplications 自动化系曹政才2015 9 18 课程简介 为什么开设本课程 制造过程调度技术研究是国内外先进制造与自动化 系统工程 工业工程 管理工程等领域前沿性研究方向之一 制造过程调度理论和方法研究极富挑战性 NP难题 复杂优化问题 制造企业对制造过程调度理论和方法应用需求越来越强 通过开设本课程 使更多的研究生了解和掌握该领域的理论与方法 提高研究生科研能力和创新能力 培养可从事调度技术研究及应用的专业人才 促进调度技术的进一步发展 课程简介 本课程有哪些教学内容 制造过程调度问题概述制造过程调度问题基本描述方法 制造过程调度问题基本优化算法 制造过程调度问题算法仿真实验 制造过程调度问题专项课题研究 制造过程调度问题实际应用案例 制造企业参观 调度软件演示 调度问题三元表示法析取图模型数学规划模型常用分类方法 调度问题基本概念国内外发展状况常用研究方法 数学规划算法启发式算法智能优化算法 课程简介 通过本课程的学习将有哪些收获 掌握制造过程调度问题概念 基本描述方法及优化理论和方法 通过专项课题 Project 研究 培养和提高科研能力 接触制造过程调度问题的实际背景 拓宽知识面 掌握利用所学调度理论和方法解决实际调度问题的基本能力 部分学有余力的同学在课程结束时将能撰写具有一定学术水平的调度算法相关论文 课程简介 本课程的评分体系课堂表现 20 实验 20 作业 10 专项课题研究报告 50 课程简介 课程教材 参考书目 教材 刘民 吴澄 制造过程智能优化调度算法及其应用 国防工业出版社 2008 刘民 制造过程调度理论及应用 讲义 王凌 车间调度及其遗传算法 清华大学出版社 2003PeterBrucker SchedulingAlgorithms SpringerPress 1998 SigridKnustUniversityofOsnabrck Germany 课程简介 基础知识参考书目 有关遗传算法 禁忌搜索基础知识 遗传算法 陈国良 遗传算法及其应用玄光男 程润伟 遗传算法与工程设计 汪定伟等译 禁忌搜索方法 F Glover TabuSearchPartI ORSAJournalonComputing Vol 1 No 3 1989 190 206 F Glover TabuSearchPart ORSAJournalonComputing Vol 2 1990 4 32 分支定界算法 胡运权运筹学教程计算复杂性理论 组合最优化 算法和复杂性 美 帕帕季米特里乌 施泰格利茨著 刘振宏 蔡茂诚译 制造过程调度概论 本节课内容什么是制造过程调度问题为什么要研究制造过程调度理论与方法求解制造过程调度问题的常用方法小结 制造过程调度概论 本节课内容为什么要研究制造过程调度理论与方法求解制造过程调度问题的常用方法小结 什么是制造过程调度问题 制造过程调度概论 什么是调度问题 调度问题一般是指如下一类资源优化问题 如何将资源 resources 分配给任务 tasks 在满足相关约束条件 constraints 下 使得某项 或多项 性能指标 objective performance 达到最优 生产和日常生活中有哪些调度问题的例子 制造过程调度概论 什么是制造过程调度问题 制造过程调度问题是指如下一类资源优化问题 将机器 含各种配件等资源 分配给工件 任务 即安排各机器上相应工件的上机时间或上机顺序 在满足相关约束条件 工艺约束 资源约束等 下使某项或多项性能指标 制造周期 总拖期数 总拖期时间 机器利用率 能耗 物耗 成本等 达到最优 制造过程调度在企业生产过程中的位置AMR提出的三层企业集成模型 制造过程调度概论 制造过程调度是MES中的关键业务 执行生产 如何生产 生产什么 制造过程调度概论 制造过程调度的常见形式 CAD CAE CAPP PDM 制造过程调度概论 什么是制造过程调度问题 从现代集成制造系统 CIMS 制造业信息化角度 计划与调度 在制品跟踪管理 原料管理 库存管理 质量管理 设备管理 计划管理 人力资源管理 工艺管理 制造过程调度重点解决该系统中的作业计划优化制定与动态调整问题 计划与调度既属于管理自动化范畴又属于制造过程自动化的范畴 底层自动化设备 制造过程调度概论 实际制造过程调度问题的特点规模大 如纺织生产制造过程 上千台设备 上万个加工任务 约束复杂 资源约束 工艺约束 不确定因素多 订单插入 撤销 更改 设备故障 质量事故 原料短缺 工艺更改等 多目标相互制约 制造周期 总拖期时间 总拖期数 生产成本等 轧钢生产线 色织生产线汽车生产线 实际生产线调度问题举例 制造过程调度概论 本节课内容什么是制造过程调度问题求解制造过程调度问题的常用方法小结 为什么要研究制造过程调度理论与方法 制造过程调度概论 为什么要研究制造过程调度理论与方法 制造业在国民经济中占据支柱地位 钢铁石化纺织微电子机械制造业的发展状况直接影响了国家的经济基础和综合国力的强弱 全球500强企业中 制造企业占208家我国制造业年产值占GDP的37 8 制造过程调度概论 为什么要研究制造过程调度理论与方法 随着我国加入WTO 企业面临的形势愈加严峻 如何挖潜增效 在不过多增加投资的情况下实现生产过程高效运行 以有效提高生产效率 降低生产成本和能耗 物耗 提高产品质量 提高经济效益和综合竞争力已成为众多企业迫在眉睫 亟需解决的关键难题 以信息化带动工业化 促进工业化和信息化融合 用信息技术改造传统产业 实现制造业跨越式发展是国家的重要战略决策 而生产制造过程的建模 优化与调度技术是信息技术的重要组成部分之一 其在提高制造企业经济效益和综合竞争力中有举足轻重的作用 制造过程调度概论 为什么要研究制造过程调度理论与方法 早期的生产系统提高产能主要通过购买新设备及投入更多人力资源实现 随着市场竞争日趋激烈 仅靠购买新设备 投入人力资源提高产能将大幅增加企业生产成本 企业提高经济效益的有效途径应是提高产品附加值 挖掘已有生产系统产能 降低成本等 某大型色织企业制造周期每缩短1 可增加出口额上百万美元 某微电子制造企业制造周期每缩短1 可增加利润上千万元 某大型汽车制造企业制造周期每缩短10 每月可增加产值1200万元 制造过程调度概论 为什么要研究制造过程调度理论与方法 研究者们已提出各种方法 如各类数学规划方法 传统启发式方法 传统人工智能方法 专家系统 案例推理 约束满足等 智能优化算法 进化计算 禁忌搜索 基于仿真的方法等 这些方法已在实际调度问题中得到初步应用并有一些成功案例 某纺织企业在实现信息集成的基础上 采用以智能调度系统为核心的集成化智能信息系统 使总生产周期缩短50 准时交单率提高40 某汽车制造企业采用以智能调度系统为核心的MES 使总生产周期缩短12 5 制造过程调度概论 为什么要研究制造过程调度理论与方法 从生产模式的发展看 作坊生产模式 大批量生产模式 多品种小批量生产模式 批量小 产品类型少 批量大 产品类型少 产品类型多 同品种批量小 生产规模大 交货期要求高 调度过程简单 主要靠直观判断作出 调度过程具有一定难度 需要较丰富的人工经验或采用简单启发式方法 调度难度高 单凭人工经验或简单启发式方法 无法满足生产要求 制造过程调度概论 为什么要研究制造过程调度理论与方法 从控制的角度看 粗放型管理 集约型管理 单一设备控制 生产线控制 制造过程调度 调度问题不仅是一个管理优化问题 同时是一个重要的生产线控制问题 需要采用制造过程调度理论与方法解决 传统 现代控制理论所解决的问题 控制对象往往用微分 差分方程表示 主要关注 同时关注 制造过程调度问题一般无法用微分 差分方程表示 一般属于离散事件动态系统 DEDS 问题 调度问题操作优化问题故障预报问题 制造过程调度概论 为什么要研究制造过程调度理论与方法 制造过程调度问题是一类典型的复杂NP问题 该问题与诸多其它组合优化问题 TSP Packing VRP 项目调度问题等 具有许多内在相似性 该问题研究成果对解决其它组合优化问题也有很好的指导和借鉴作用 制造过程调度概论 本节课内容什么是制造过程调度问题为什么要研究制造过程调度理论与方法小结 求解制造过程调度问题的常用方法 制造过程调度概论 求解制造过程调度问题的常用方法基于运筹学的方法基于传统启发式的方法基于传统人工智能的方法基于计算机仿真的方法基于软计算的方法 制造过程调度概论 求解制造过程调度问题的主要方法基于运筹学的方法 实际制造过程调度问题 数学规划模型 运筹学方法求解 形成实际问题解 哪些数学规划模型和求解方法可以采用 以求解最优解为目标 存在 指数爆炸 现象 特点 分支定界法动态规划割平面法拉格朗日松弛等等 处理变换 化简并附加假设条件 制造过程调度概论 求解制造过程调度问题的主要方法传统启发式方法 基于规则的简单启发式方法和复杂启发式方法 实际制造过程调度问题 用与工件或机器等相关的简单信息决定上机顺序 形成实际问题解 计算量小 运行速度快 对具有复杂约束 复杂目标或大规模等特征的调度问题 其调度效果不令人满意 一些简单调度规则 基于规则的简单启发式方法 举例 特点 LPT SPT EDD 制造过程调度概论 求解制造过程调度问题的主要方法基于传统人工智能的方法 专家系统 案例推理 约束满足 采用传统人工智能方法并利用丰富的问题信息以产生比传统启发式方法更好的调度效果 前两类往往应用于特定行业调度问题中 对规模大 带复杂约束 多目标等特点的复杂调度问题难以实用 特点 制造过程调度概论 求解制造过程调度问题的主要方法基于计算机仿真的方法 实际制造过程调度问题 建立仿真模型确定初始参数 执行仿真 形成实际问题解 是否满意 建模灵活 建模过程耗时长 对复杂问题 难以得到令人满意的调度效果 单纯采用仿真方法难以有效解决实时调度问题 特点 N Y 制造过程调度概论 求解制造过程调度问题的主要方法软计算方法 遗传算法 禁忌搜索算法 模拟退火算法 粒子群算法 蚁群算法等 不以寻求问题最优解为目标 求解过程基于简单的形式化描述 如编码过程 将决策变量包含在待寻优个体中 对目标函数无特殊要求 可导 可微 凸函数等 方便在算法中加入问题特征信息 特点 制造过程调度概论 求解制造过程调度问题的主要方法遗传算法 遗传算法 由美国Michigan的Holland于1975年提出 是一种基于 优胜劣汰 自然选择思想和遗传机制的搜索算法 其基本步骤包括编码 初始种群产生 适应度评价 交叉和变异 遗传算法在计算机上模拟生物的进化过程和基因操作 实现简单 且适用问题广泛 因此近年来在优化领域得到普遍应用 制造过程调度概论 求解制造过程调度问题的主要方法人类的演化过程 制造过程调度概论 求解制造过程调度问题的主要方法禁忌搜索算法 禁忌搜索算法 由美国Mississippi大学的Glover于1986年提出 是在传统局部搜索方法基础上引入禁忌技术产生的一种基于邻域的搜索方法 其是对传统局部搜索方法的一种改进 其基本思想是在搜索过程中通过引入一个记忆装置 即具有一定长度的禁忌表 表中记录了最近所进行的所有解的移动 禁忌对象可以是一个解 也可以是解的一部分 或是解的某种属性等 以避免基于邻域的搜索过程陷入循环或局部最优 制造过程调度概论 求解制造过程调度问题的主要方法现有求解方法存在的问题对实际问题有较多前提假设 对问题简化过多 因而对复杂调度问题缺乏实用性 对调度问题本身的分析不够透彻 对实际调度问题数据利用不够充分 问题特征信息未得到充分利用 现有调度问题基本优化算法大多针对确定性调度问题提出 对不确定环境下的复杂调度问题缺乏有效求解算法 缺乏对实际问题具有较好调度性能的综合 集成 算法 制造过程调度概论 本章小结什么是制造过程调度问题为什么要研究制造过程调度问题制造过程调度问题的常用研究方法参考文献 综述文章 刘民 基于数据的生产过程调度方法研究综述 自动化学报 20