资源描述
第九章第九章 制造系统的调度控制制造系统的调度控制 n 概述概述 n流水排序调度方法流水排序调度方法 n非流水排序调度方法非流水排序调度方法 n基于规则的调度方法基于规则的调度方法 n基于仿真的调度方法基于仿真的调度方法 第一节第一节 概述概述 n调度控制的调度控制的根本任务根本任务 实施战术层下达的生产作业计划。实施战术层下达的生产作业计划。控制工件的投放和在系统中的流动以及控制工件的投放和在系统中的流动以及资源的使用。如资源的使用。如“某机床某时刻开始对某机床某时刻开始对某零件的某道工序进行加工某零件的某道工序进行加工”等。等。n调度控制系统的调度控制系统的基本结构基本结构：调度控制器调度控制器制造过程制造过程输入输入R R控制控制U U输出输出C C扰动扰动D D状态反馈状态反馈X X第一节第一节 概述概述 工作过程：工作过程：调度控制器调度控制器根据根据输入信息输入信息R R（包括来自上级的生（包括来自上级的生产作业计划、设计要求和工艺规程）和产作业计划、设计要求和工艺规程）和反馈信息反馈信息X X（即生产（即生产现场的实际状态）进行实时决策，产生现场的实际状态）进行实时决策，产生控制信息控制信息U U（即调度（即调度控制指令）。控制指令）。制造过程制造过程在调度控制指令的控制下运行，克服在调度控制指令的控制下运行，克服外界扰动外界扰动D D的影响，生产出满足输入信息要求的的影响，生产出满足输入信息要求的产品产品C C闭环自动控制系统闭环自动控制系统n静态调度静态调度n动态调度动态调度 动态调度动态调度是指调度控制系统能对外部输是指调度控制系统能对外部输入信息、制造过程状态和系统环境的动态变入信息、制造过程状态和系统环境的动态变化作出实时响应的调度控制系统。化作出实时响应的调度控制系统。第一节第一节 概述概述 n调度控制系统的调度控制系统的分类分类：n调度控制问题中的调度控制问题中的难点难点：l信息处理的实时性要求信息处理的实时性要求l被控对象的建模被控对象的建模l调度控制器的设计调度控制器的设计l外界扰动对系统的影响。外界扰动对系统的影响。第一节第一节 概述概述 n解决调度控制问题的解决调度控制问题的方法方法：静态调度静态调度方法和方法和动态调度动态调度方法两类。方法两类。具体方法：具体方法：l基于排序理论的调度方法基于排序理论的调度方法l基于规则的调度方法基于规则的调度方法l基于离散事件系统仿真的调度方法基于离散事件系统仿真的调度方法l基于人工智能的调度方法基于人工智能的调度方法第一节第一节 概述概述 第二节第二节 流水排序调度方法流水排序调度方法n应用场合：应用场合：用于具有相同工艺路线的一批工件的加工用于具有相同工艺路线的一批工件的加工情况。情况。n流水排序问题描述：流水排序问题描述：设有设有n n个工件和个工件和m m台设备，每个工件均台设备，每个工件均需按相同的顺序通过这需按相同的顺序通过这m m台设备进行加工。台设备进行加工。要求以某种性能指标最优（如制造总工期要求以某种性能指标最优（如制造总工期最短等）为目标，求出最短等）为目标，求出n n个工件进入系统的个工件进入系统的顺序。顺序。第二节第二节 流水排序调度方法流水排序调度方法n属静态调度方法属静态调度方法n流水排序调度的实施过程流水排序调度的实施过程：先通过作业排序得到调度表，然后按调先通过作业排序得到调度表，然后按调度表控制生产过程的运行。如果生产过程度表控制生产过程的运行。如果生产过程中出现异常情况（如设备负荷不均匀、工中出现异常情况（如设备负荷不均匀、工件加工出现堵塞现象等），则重新排序，件加工出现堵塞现象等），则重新排序，再按新排出的调度表继续控制生产过程的再按新排出的调度表继续控制生产过程的运行。运行。n排序算法排序算法：单机排序算法单机排序算法两机排序算法两机排序算法 三机排序算法三机排序算法m m机排序算法机排序算法第二节第二节 流水排序调度方法流水排序调度方法1.n1.n作业单机排序作业单机排序n问题描述问题描述：n n个工件和个工件和1 1台设备，要求以某种性能台设备，要求以某种性能指标最优为目标，求出这指标最优为目标，求出这n n个工件的加工个工件的加工顺序或者说进入系统的顺序。顺序或者说进入系统的顺序。n性能指标性能指标：对于对于n n作业单机排序，为实作业单机排序，为实现最优作业排序，以作业平均通过时间现最优作业排序，以作业平均通过时间（mean flow timemean flow time，MFTMFT）最短作为性能）最短作为性能指标。计算公式如下：指标。计算公式如下：式中式中：i i作作业的完工的完工时间 i i作作业的等待和加工的等待和加工时间。1.n1.n作业单机排序作业单机排序n基本原理（排序方法）基本原理（排序方法）：按最短加工时间（按最短加工时间（SPTSPT）优先原则）优先原则排序可使排序可使MFTMFT最短。即具有最短加工最短。即具有最短加工时间的作业优先加工（处理）。时间的作业优先加工（处理）。推论：推论：MFTMFT最小可保证作业平均延最小可保证作业平均延误时间（误时间（mean lateness,MLmean lateness,ML）最小。）最小。1.n1.n作业单机排序作业单机排序n问题描述问题描述：n n个工件和个工件和2 2台设备台设备M1M1、M2M2，每个工件均，每个工件均需按相同的顺序先在需按相同的顺序先在M1M1上加工，再在上加工，再在M2M2进进行加工。要求以某种性能指标最优为目标，行加工。要求以某种性能指标最优为目标，求出求出n n个工件进入系统的顺序。个工件进入系统的顺序。2.n2.n作业两机排序作业两机排序n性能指标性能指标：以制造总工期以制造总工期L L最短作为最优目标。最短作为最优目标。n基本原理（调度方法）：基本原理（调度方法）：规则规则1 1：在在M1M1上加工时间最短者应最上加工时间最短者应最 先加工。先加工。规则规则2 2：在在M2M2上加工时间最短者应最上加工时间最短者应最后加工。后加工。2.n2.n作业两机排序作业两机排序n实施步骤（排序算法）实施步骤（排序算法）：（1 1）列出各项作业在列出各项作业在M1M1，M2M2上的加工时间；上的加工时间；（2 2）扫视全部加工时间，找出最小加工时间；扫视全部加工时间，找出最小加工时间；（3 3）如果最小加工时间发生在如果最小加工时间发生在M1M1，则该作业最，则该作业最先加工；如果最小加工时间发生在先加工；如果最小加工时间发生在M2M2，则该作，则该作业最后加工；业最后加工；（4 4）消去已排序作业，重复（消去已排序作业，重复（2 2）（）（3 3）两步，）两步，直到全部排序完成；直到全部排序完成；（5 5）如果发生在如果发生在M1M1，M2M2上加工时间相等的情况，上加工时间相等的情况，则可任意排在最先或最后，而不影响总工期。则可任意排在最先或最后，而不影响总工期。2.n2.n作业两机排序作业两机排序2.n2.n作业两机排序作业两机排序n应用举例：应用举例：某车间有某车间有6 6项作业，均需先在项作业，均需先在M1M1上加工，后在上加工，后在M2M2上上加工，加工时间数据见表，试找出最优排序使完成加工，加工时间数据见表，试找出最优排序使完成全部任务的总工期最短。全部任务的总工期最短。作业J1J1J2J2J3J3J4J4J5J5J6J6M1M110128191815M2M2161216141721最优排序：最优排序：J3-J1-J2-J6-J5-J4;J3-J1-J6-J5-J4-J2J3-J1-J2-J6-J5-J4;J3-J1-J6-J5-J4-J2n问题描述问题描述：n n个工件和个工件和3 3台设备台设备M1M1、M2M2、M3M3，每个，每个工件均需按相同的顺序先在工件均需按相同的顺序先在M1M1上加工，再上加工，再在在M2M2进行加工进行加工,再在再在M3M3进行加工。要求以进行加工。要求以某种性能指标最优为目标，求出某种性能指标最优为目标，求出n n个工件个工件进入系统的顺序。进入系统的顺序。3.n3.n作业三机排序作业三机排序3.n3.n作业三机排序作业三机排序n性能指标性能指标：以制造总工期以制造总工期L L最短作为最优目标。最短作为最优目标。n基本原理（调度方法）：基本原理（调度方法）：（分支定界法）用树形结构描述问题的分支定界法）用树形结构描述问题的求解过程，每一节点表示一种待定的排序，求解过程，每一节点表示一种待定的排序，计算当前全部节点的制造工期下限值，然计算当前全部节点的制造工期下限值，然后从下限值最低的节点继续分枝，直至找后从下限值最低的节点继续分枝，直至找到最优排序。到最优排序。n工期下限计算方法工期下限计算方法：从三台设备无空闲着手分析从三台设备无空闲着手分析 所以三机流水生产情况下，节点所以三机流水生产情况下，节点P P上制造上制造工期下限为：工期下限为：3.n3.n作业三机流水排序作业三机流水排序n求解步骤求解步骤：n从根节点开始求各节点的工期下限值从根节点开始求各节点的工期下限值n先求已排序作业集合先求已排序作业集合 通过通过 的总时间的总时间 ;通过通过 的总时间的总时间 ；通过；通过 的总时间的总时间 n求最小工期下限求最小工期下限n求每层各节点的工期下限值求每层各节点的工期下限值n比较同一层各节点的工期下限值，以比较同一层各节点的工期下限值，以LBLB最小节点为最小节点为根继续分枝。画分枝图。根继续分枝。画分枝图。3.n3.n作业三机流水排序作业三机流水排序 第三节第三节 非流水排序调度方法非流水排序调度方法 n应用场合：应用场合：适用于具有相似工艺路线的适用于具有相似工艺路线的n n个工件的个工件的加工情况加工情况n非流水排序问题描述非流水排序问题描述：给定给定n n个工件，每个工件以不同的顺个工件，每个工件以不同的顺序和时间通过序和时间通过m m台设备进行加工。要求以台设备进行加工。要求以某种性能指标最优为目标，求出这些工某种性能指标最优为目标，求出这些工件在件在m m台机床上的最优加工顺序。台机床上的最优加工顺序。第三节 非流水排序调度方法 n属于静态调度方法属于静态调度方法n实施过程：实施过程：先通过作业排序得到调度表，然后先通过作业排序得到调度表，然后按调度表控制生产过程的运行，如果运按调度表控制生产过程的运行，如果运行过程出现异常情况，则需重新排序，行过程出现异常情况，则需重新排序，再按新排出的调度表继续控制生产过程再按新排出的调度表继续控制生产过程运行。运行。n性能指标性能指标：完成两作业的总工期完成两作业的总工期L L最短。最短。n基本原理（图解法）基本原理（图解法）：两作业合成轨迹总长度最短。两作业合成轨迹总长度最短。两作业两作业m m机非流水排序（图解法）机非流水排序（图解法）n问题描述问题描述：2 2个工件，每个工件以不同的顺序和个工件，每个工件以不同的顺序和时间通过时间通过m m台设备进行加工。要求以某种台设备进行加工。要求以某种性能指标最优为目标，求出这些工件在性能指标最优为目标，求出这些工件在m m台机床上的最优加工顺序。台机床上的最优加工顺序。n求解步骤：求解步骤：画直角坐标系，其横轴表示作业画直角坐标系，其横轴表示作业1 1的加工工序和时间，的加工工序和时间，纵轴表示作业纵轴表示作业2 2的加工工序和时间。的加工工序和时间。将两作业需占用同一机器的时间用方框标出，表示不将两作业需占用同一机器的时间用方框标出，表示不可行区。可行区。用水平线、垂直线和用水平线、垂直线和4545度线度线3 3种线段表示两作业推进过种线段表示两作业推进过程的合成轨迹。水平线表示作业程的合成轨迹。水平线表示作业1 1加工，作业加工，作业2 2等待，垂直等待，垂直线表示作业线表示作业2 2加工，作业加工，作业1 1等待，等待，4545度线表示两作业同时加度线表示两作业同时加工。为使制造总工期最短，应使工。为使制造总工期最短，应使4545度线段占的比例最大。度线段占的比例最大。通过本步应找出所有可能的合成轨迹。通过本步应找出所有可能的合成轨迹。以轨迹总长度最短为目标，通过直观对比和计算，从以轨迹总长度最短为目标，通过直观对比和计算，从第第步确定的候选合成轨迹中找出最优合成轨迹。步确定的候选合成轨迹中找出最优合成轨迹。求解最优合成轨迹上的时间转折点，得到调度表。求解最优合成轨迹上的时间转折点，得到调度表。两作业两作业m m机非流水排序（图解法）机非流水排序（图解法）随着作业数量和机器数量的增加，排序随着作业数量和机器数量的增加，排序计算量大。在实际应用中无法对较大规计算量大。在实际应用中无法对较大规模的排序问题求得最优解。模的排序问题求得最优解。n 存在的问题存在的问题两作业两作业m m机非流水排序（图解法）机非流水排序（图解法）第四节第四节 基于规则的调度方法基于规则的调度方法 调度控制器调度控制器制造过程制造过程输入输入R R控制控制U U输出输出C C扰动扰动D D状态反馈状态反馈X X 调度控制系统的基本结构框图调度控制系统的基本结构框图 n基本原理：基本原理：系统运行时，调度控制器根据输入信息和系统运行时，调度控制器根据输入信息和制造过程的反馈信息按一定的制造过程的反馈信息按一定的调度规则调度规则进行决进行决策，对制造过程的运行操作实现控制。策，对制造过程的运行操作实现控制。n调度规则调度规则：简单优先规则简单优先规则 直接根据系统状态和参数确直接根据系统状态和参数确定下一步操作的调度规则。采用简单优先规定下一步操作的调度规则。采用简单优先规则可保证系统某一或某几个性能参数达到一则可保证系统某一或某几个性能参数达到一个较好的效果。个较好的效果。组合优先规则组合优先规则 是根据某些参数（如队列长是根据某些参数（如队列长度等）交替运用两种以上简单优先规则对零度等）交替运用两种以上简单优先规则对零件进行处理的复合规则。件进行处理的复合规则。加权优先规则加权优先规则 是通过引入加权系数对简单是通过引入加权系数对简单优先规则和组合优先规则进行综合运用而构优先规则和组合优先规则进行综合运用而构成的复合规则。成的复合规则。启发式规则启发式规则 利用人工智能的复杂调度规则利用人工智能的复杂调度规则先进先出：先进先出：根据零件到达工作站的先后顺序来执行加工根据零件到达工作站的先后顺序来执行加工作业，先来的先进行加工。作业，先来的先进行加工。最短加工时间规则：最短加工时间规则：优先选择具有最短加工时间的零件优先选择具有最短加工时间的零件进行处理。是一种经常使用的规则。进行处理。是一种经常使用的规则。最早到期日规则：最早到期日规则：根据订单交货期的先后顺序安排加工，根据订单交货期的先后顺序安排加工，即优先选择具有最早交付期的零件进行处理。即优先选择具有最早交付期的零件进行处理。最少作业数规则：最少作业数规则：根据剩余作业数来安排加工顺序，剩根据剩余作业数来安排加工顺序，剩余作业数越少的零件越先加工。较少的作业意味着较少余作业数越少的零件越先加工。较少的作业意味着较少的等待时间。的等待时间。下一队列工作量规则：下一队列工作量规则：优先选择下一队列工作量最少的优先选择下一队列工作量最少的零件进行处理。下一队列工作量是指零件下一工序加工零件进行处理。下一队列工作量是指零件下一工序加工处的总工作量（加工零件和排队零件的工作量之和）处的总工作量（加工零件和排队零件的工作量之和）剩余松弛时间规则：剩余松弛时间规则：剩余松弛时间越短越先加工。剩余剩余松弛时间越短越先加工。剩余松弛时间是将在交货期前所剩余的时间减去剩余的总加松弛时间是将在交货期前所剩余的时间减去剩余的总加工时间所得的差值。工时间所得的差值。几种典型简单优先规则几种典型简单优先规则n规则调度方法的局限性：规则调度方法的局限性：上述任何一种规则只能使系统在某一上述任何一种规则只能使系统在某一方面，或针对某一特定的性能参数取得方面，或针对某一特定的性能参数取得一个好的效果，所以每一种规则相对其一个好的效果，所以每一种规则相对其他规则并没有绝对的优势。这种静态的、他规则并没有绝对的优势。这种静态的、固定应用某种调度规则的调度方法对于固定应用某种调度规则的调度方法对于动态变化的系统环境很难适应。动态变化的系统环境很难适应。规则动态切换调度控制系统规则动态切换调度控制系统 动动态态选选择择R1R2Rr.计计算算决决策策输入输入输出输出制造制造过程过程系统状态系统状态调度控制器调度控制器原理：原理：根据制造系统的实际状态，确定适当调度规则集，并根据制造系统的实际状态，确定适当调度规则集，并设计规则设计规则动态选择逻辑动态选择逻辑和相关的和相关的计算决策装置计算决策装置。系统运行时，。系统运行时，根据实际状态，动态选择规则集中的规则，通过实时决策实现根据实际状态，动态选择规则集中的规则，通过实时决策实现调度控制。调度控制。运行过程：运行过程：动态选择模块根据输入指令和系统状态动态选择动态选择模块根据输入指令和系统状态动态选择规则集中的某一条规则规则集中的某一条规则RiRi，计算决策模块根据被选中的规则计，计算决策模块根据被选中的规则计算每一候选调度方案对应的性能准则值，然后根据准则值的大算每一候选调度方案对应的性能准则值，然后根据准则值的大小做出选择调度方案的决策，并向制造过程发出相应的调度控小做出选择调度方案的决策，并向制造过程发出相应的调度控制指令。制指令。第五节第五节 基于仿真的调度方法基于仿真的调度方法n基本原理：基本原理：基于仿真的调度方法是一种以仿真作为基于仿真的调度方法是一种以仿真作为制造系统控制决策的决策支持系统、辅助制造系统控制决策的决策支持系统、辅助调度控制器进行决策优化、实现制造系统调度控制器进行决策优化、实现制造系统优化控制的一种方法。优化控制的一种方法。调度控制器调度控制器制造过程制造过程输入输入R R控制控制U U输出输出C C扰动扰动D D状态反馈状态反馈X X计算机仿真计算机仿真n运行过程：运行过程：当调度控制器接收来自上级的输入信息和来当调度控制器接收来自上级的输入信息和来自生产现场的状态反馈信息后，通过初始决策确自生产现场的状态反馈信息后，通过初始决策确定若干候选调度方案，然后将各方案送往计算机定若干候选调度方案，然后将各方案送往计算机仿真系统进行仿真，最后由调度控制器对仿真结仿真系统进行仿真，最后由调度控制器对仿真结果进行分析，做出方案选择决策，并据此生成调果进行分析，做出方案选择决策，并据此生成调度控制指令来控制制造过程的运行。度控制指令来控制制造过程的运行。n基于仿真调度方法的关键问题基于仿真调度方法的关键问题仿真建模：仿真建模：建立能准确描述实际系统的仿真建立能准确描述实际系统的仿真模型是实现仿真调度方法的前提。模型是实现仿真调度方法的前提。目前在调度控制仿真中所用的模型主要是逻辑模目前在调度控制仿真中所用的模型主要是逻辑模型。型。实验设计：实验设计：那如何安排实验或进行实验设计，那如何安排实验或进行实验设计，以最少的试验次数从可选方案中选择出最佳的方案以最少的试验次数从可选方案中选择出最佳的方案是仿真控制方法的一个重要问题。是仿真控制方法的一个重要问题。目前常用的实验设计和结过分析方法有回归分析目前常用的实验设计和结过分析方法有回归分析方法、扰动分析方法和正交设计方法等。方法、扰动分析方法和正交设计方法等。n基于仿真调度方法的关键问题基于仿真调度方法的关键问题仿真运行：仿真运行：计算机仿真模型及其仿真运行都计算机仿真模型及其仿真运行都是通过计算机编程来实现的，目前常用的仿真和编是通过计算机编程来实现的，目前常用的仿真和编程语言有程语言有C C语言、专业仿真语言和仿真软件包等。语言、专业仿真语言和仿真软件包等。控制决策：控制决策：控制决策的任务是对仿真结果进控制决策的任务是对仿真结果进行分析从中选出最佳方案，并据此生成调度控制指行分析从中选出最佳方案，并据此生成调度控制指令控制制造过程的运行。令控制制造过程的运行。目前一些实际系统中多由人机结合的方式来完目前一些实际系统中多由人机结合的方式来完成决策任务。成决策任务。第六节第六节 智能调度方法智能调度方法n基本原理：基本原理：基于智能的调度方法是根据制造系统的实际情况，基于智能的调度方法是根据制造系统的实际情况，确定适当的调度规则集。系统运行时，根据生产过程确定适当的调度规则集。系统运行时，根据生产过程的实际状态，通过专家系统动态选择规则几种的规则的实际状态，通过专家系统动态选择规则几种的规则进行调度控制的一种方法。进行调度控制的一种方法。专专家家系系统统R1R2Rr.计计算算决决策策输入输入输出输出制造制造过程过程系统状态系统状态调度控制器调度控制器第六节第六节 智能调度方法智能调度方法输入处理调度推理机调度推理机输出处理输入信息输入信息反馈信息反馈信息切换控制切换控制调度调度知识库知识库数据库数据库规则选择专家系统的基本结构规则选择专家系统的基本结构第六节第六节 智能调度方法智能调度方法n专家系统运行过程：专家系统运行过程：当输入处理模块对来自上级的输入信息和来当输入处理模块对来自上级的输入信息和来自生产现场的状态反馈信息进行处理，将其转换自生产现场的状态反馈信息进行处理，将其转换为便于调度推理机使用的内部形式。调度推理机为便于调度推理机使用的内部形式。调度推理机利用知识库的知识，在数据库的配合下根据输入利用知识库的知识，在数据库的配合下根据输入信息进行推理，做出调度规则选择决策。输出模信息进行推理，做出调度规则选择决策。输出模块将决策结果转换为规则切换控制指令，以实现块将决策结果转换为规则切换控制指令，以实现对调度规则的动态选择和切换控制，并据此生成对调度规则的动态选择和切换控制，并据此生成调度控制指令来控制制造过程的运行。调度控制指令来控制制造过程的运行。
展开阅读全文