第一章生产调度概论

制造过程调度理论及应用SchedulingTheoryforManufacturingProcessandItsApplications自动化系曹政才2015.9.18课程简介为什么开设本课程？制造过程调度技术研究是国内外先进制造与自动化、系统工程、工业工程、管理工程等领域前沿性研究方向之一；制造过程调度理论和方法研究极富挑战性；NP难题；复杂优化问题；制造企业对制造过程调度理论和方法应用需求越来越强；通过开设本课程，使更多的研究生了解和掌握该领域的理论与方法，提高研究生科研能力和创新能力，培养可从事调度技术研究及应用的专业人才，促进调度技术的进一步发展课程简介本课程有哪些教学内容？制造过程调度问题概述制造过程调度问题基本描述方法；制造过程调度问题基本优化算法；制造过程调度问题算法仿真实验；制造过程调度问题专项课题研究；制造过程调度问题实际应用案例；制造企业参观/调度软件演示…调度问题三元表示法析取图模型数学规划模型常用分类方法调度问题基本概念国内外发展状况常用研究方法数学规划算法启发式算法智能优化算法课程简介通过本课程的学习将有哪些收获？掌握制造过程调度问题概念、基本描述方法及优化理论和方法；通过专项课题(Project)研究，培养和提高科研能力；接触制造过程调度问题的实际背景，拓宽知识面，掌握利用所学调度理论和方法解决实际调度问题的基本能力；部分学有余力的同学在课程结束时将能撰写具有一定学术水平的调度算法相关论文；课程简介本课程的评分体系课堂表现：20％；实验：20％；作业：10％；专项课题研究报告：50％；课程简介课程教材/参考书目：教材：刘民，吴澄.《制造过程智能优化调度算法及其应用》，国防工业出版社，2008；刘民，《制造过程调度理论及应用》讲义；王凌，《车间调度及其遗传算法》，清华大学出版社，2003PeterBrucker,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中的关键业务执行生产如何生产生产什么制造过程调度概论制造过程调度的常见形式复杂生产制造过程原料投产成品产出作业计划制定重调度ERP/MES/SCM等管理系统订单、设备、跟踪信息工艺、原料、库存等信息设备故障质量事故订单更改工艺变更加工时间不准确设备层实时调度设备级作业计划关键工序作业计划拖期状况作业计划更改方案投产计划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…制造过程调度概论求解制造过程调度问题的主要方法基于传统人工智能的方法；专家系统；案例推理；约束满足；采用传统人工智能方法并利用丰富的问题信息以产生比传统启发式方法更好的调度效果，前两类往往应用于特定行业调度问题中；对规模大、带复杂约束、多目标等特点的复杂调度问题难以实用；特点：制造过程调度概论求解制造过程调度问题的主要方法基于计算机仿真的方法；实际制造过程调度问题建立仿真模型确定初始参数执行仿真形成实际问题解是否满意建模灵活；建模过程耗时长；对复杂问题，难以得到令人满意的调度效果；单纯采用仿真方法难以有效解决实时调度问题；特点：NY制造过程调度概论求解制造过程调度问题的主要方法软计算方法；遗传算法；禁忌搜索算法；模拟退火算法；粒子群算法/蚁群算法等；终止条件初始解通过某种寻优策略改进当前解新解退出不以寻求问题最优解为目标；求解过程基于简单的形式化描述（如编码过程），将决策变量包含在待寻优个体中；对目标函数无特殊要求(可导/可微/凸函数等)；方便在算法中加入问题特征信息；特点：制造过程调度概论求解制造过程调度问题的主要方法遗传算法；遗传算法(由美国Michigan的Holland于1975年提出)是一种基于“优胜劣汰”自然选择思想和遗传机制的搜索算法，其基本步骤包括编码、初始种群产生、适应度评价、交叉和变异。遗传算法在计算机上模拟生物的进化过程和基因操作，实现简单，且适用问题广泛，因此近年来在优化领域得到普遍应用。制造过程调度概论求解制造过程调度问题的主要方法人类的演化过程制造过程调度概论求解制造过程调度问题的主要方法禁忌搜索算法；禁忌搜索算法(由美国Mississippi大学的Glover于1986年提出)是在传统局部搜索方法基础上引入禁忌技术产生的一种基于邻域的搜索方法，其是对传统局部搜索方法的一种改进。其基本思想是在搜索过程中通过引入一个记忆装置，即具有一定长度的禁忌表(表中记录了最近所进行的所有解的移动，禁忌对象可以是一个解，也可以是解的一部分，或是解的某种属性等)，以避免基于邻域的搜索过程陷入循环或局部最优。制造过程调度概论求解制造过程调度问题的主要方法现有求解方法存在的问题对实际问题有较多前提假设、对问题简化过多，因而对复杂调度问题缺乏实用性；对