当前位置：首页 > 实用文档 > 其他范文> 基于零件虚拟工序队列的FMS动态调度研究

基于零件虚拟工序队列的FMS动态调度研究

时间：2023-08-02 08:14:49 其他范文收藏本文下载本文

基于零件虚拟工序队列的FMS动态调度研究（共6篇）由网友“蠢货不会总结”投稿提供，下面是小编为大家整理后的基于零件虚拟工序队列的FMS动态调度研究，如果喜欢可以分享给身边的朋友喔!

篇1：基于零件虚拟工序队列的FMS动态调度研究

基于零件虚拟工序队列的FMS动态调度研究注意：本文已经在《中国机械工程》(,10(12):1367～1369)杂志发表

使用者请注明文章内容出处

赵天奇陈禹六李培根摘要提出虚拟工序队列的概念，并在此基础上提出一种基于静态零件分批（静态调度）的FMS动态生产调度方法，该算法充分考虑到FMS的系统资源限制及零件运输等环节，能较好地解决生产调度中的设备负荷平衡、系统紧急事件发生（如机床故障、新零件加入等）、可替代加工工序等问题，且易于实现，具有较广泛的适应性。

篇2：基于零件虚拟工序队列的FMS动态调度研究

中国图书资料分类法分类号TH165TP271Dynamic Scheduling Based on Virtual Operation Queue of Part for FMSsZhao Tianqi(Tsinghua University,Beijing,China)ChenYuliuLi Peigenp 1367-1369Abstract: In this paper a concept of Virtual Operation Queue of part is proposed, a dynamic production scheduling algorithm is presented based on static batching of FMSs. The restricts of manufacturing resources, influence of part handling system and some emergency events (e.g. machine breakdown, rush order joining etc.), alternative operations, etc. are considered in the algorithm. The algorithm is easy to be realized, and can be applied to dynamic scheduling for most types of FMSs, which have one or more AGVs and have linear or loop layout.

Key words:FMSVirtual Operation Queue of PartDynamic schedulingDispatching Rule对于有效地利用已有FMS中的各种资源提高生产效率而言，合理完善的调度控制系统是关键。调度是指在时间意义上所有系统资源的定位、分配和处理，其系统分为加工子系统和运输子系统(刀具流系统和物料流系统)，其调度分为静态调度和动态调度。FMS的调度控制比较复杂，尤其当涉及的因素较多时，若要根据某一调度目标得到最优调度结果，往往很难满足实时性的要求。其实，多数情况下调度目标是人为的，FMS调度只要得到近优解即可［1，2］。

本文在零件静态分批的基础上提出零件虚拟工序队列的概念，并在此基础上提出1个解决FMS动态生产调度的启发式调度算法。1FMS调度问题描述

FMS动态调度及零件静态分批之间的关系见图1。这里所研究的动态调度是在零件静态分

批的基础上以分好的零件子批为加工任务进行调度的［3，4］。因在加工任务静态分批阶段已充分考虑了系统的部分资源(如装卸站、缓冲站、刀具、夹具、托盘等因素)，故在此不需考虑。

图1动态调度与零件静态分批之间的关系FMS动态调度的目标是使系统具有较好的加工性能，一方面能使系统具有较高的生产率，即较高的设备利用率，另一方面能及时完成给定的加工任务。在本文中，调度主要考虑2方面的性能，即尽量满足加工任务中零件的交货期和尽可能减少系统生产时间。用以下2个指标来描述：工件平均延误时间（mean tardiness，MT）和工件平均流通时间（mean flow-time，MFT）。

MT反映零件是否满足交货期，MFT则反映工件在系统中的驻留时间，能较全面地反映系统生产时间。调度目标f=min{W1×MT+W2×MFT}式中，W1、W2为权值；×反映调度目标中MT和MFT的侧重程度。2零件虚拟工序队列的概念及特点

零件在FMS中加工的过程可用排队理论和方法来描述，由于加工中影响因素较多，如零件的某些工序存在可替代加工工序和零件的加工工序之间的加工先后关系的柔性等。这些因素给系统性能的提高创造了有利的条件，但无疑也为系统的调度控制系统的实现增加了难度。这也是目前大多数调度控制系统采用固定加工工艺的.主要原因之一。利用本文提出的零件虚拟工序队列方法可大幅度降低调度问题的复杂性。

零件虚拟工序队列方法的基本原理见图2。假设系统内的每一台机床前都存在一队列(集合)，该集合中存放的是当前该设备能够加工的工序(机床的可加工工序集合)。在调度开始时各设备前可加工工序集合为空(也可按给定系统状态设定)，当有新零件进入系统或设备加工完一零件时，首先判明该零件当前能加工的工序及其对应的机床，然后使这些工序进入对应机床的可加工工序集合中。若当前可调度工序存在可替代加工工序，则该工序同时加入到对应设备的可加工工序集合中。设备的下一个加工零件是在该机床的可加工工序集合中按一定的规则进行选择的。当机床选择好1个工序后，从所有设备的可加工工序集合中删去该工序对应的零件的所有工序，从而避免不同设备同时选择同一零件的情况。

图2零件虚拟工序队列概念图采用零件虚拟工序队列方法有如下特点：

(1)有广泛的适应性。对机床故障、紧急零件进入、可替代加工工序以及改变调度目标等通常意义上的重调度情况都很容易处理。

(2)避免了算法中零件在不同的机床队列之间不必要的相互传送及调整。

(3)在零件优化分批的基础上，可实现批内各机床加工负荷的近似自动平衡。机床最大负荷不均衡量为零件的最后一道加工工序的加工时间。

(4)适用于多种零件的混流生产，也适用于传统的Job－Shop生产。

(5)简化了FMS动态调度控制中的规则系统，使得调度控制更易于实现。

用零件虚拟工序队列方法保证了各加工设备加工负荷的近似均衡，若结合合适的调度规则在机床的可调度零件集合中选择合适的加工零件，所得到的结果必为系统的近优解甚至最优解。3基于零件虚拟工序队列的FMS启发式动态调度算法

该算法是在加工任务分批的基础上，同时考虑了工件运输系统的影响而提出的。机床前输入/输出缓冲站配置不同，其调度算法略有不同。本文针对机床前具有1个输入和1个输出缓冲器的典型FMS情况进行研究，提出动态调度算法，其流程图见图3。

>图3FMS动态调度原理图

在调度算法中提出了系统决策点的确定方法。通过计算各机床上所有工件的加工完成时刻，确定具有最小加工完成时间的机床，把该机床当前加工工件的加工完成时刻作为决策点。该方法一方面全面考虑了各机床的加工负荷情况，另一方面也找出了系统中最迫切需要调度决策的机床进行决策和运输，从而提高整个加工和运输系统的利用率，使总加工时间最短。

设备在加工过程中情况主要有6种（见图4）。图4a和图4b中，系统中各机床均有工件加工，且输入存储器中皆有待加工工件，选择t2时刻最小的机床（机床2）的t1时刻作为决策点tD。

图4机床工件选择的决策点分析示意图

图4c和图4d中，此时系统中有机床（机床1）输入存储器中无待加工工件（t2=∞），找出t2最小的机床（机床3）的t1作为决策点tD。

图4e和图4f中，此时系统中有机床（机床1）当前为空闲状态，同样找出t2最小的机床（机床2）的t1作为决策点tD。

除上面几种情况外，还有1种特殊情况，即各机床输入存储器中都为空、各机床或空闲、或只有1个工件。此时把新工件进入系统时刻或系统中工件的工序加工完成时刻作为系统的决策点。

在算法中提出的动态预调度方法，能在系统决策点处预先决策好机床待加工的零件，并通知零件运输系统送入机床的输入缓冲站中，这样当机床加工好零件后可直接通过托盘交换装置把机床上的零件送入输出缓冲站，并把输入缓冲站中的零件送入机床。零件的动态预调度能显著地减少机床的等待时间，提高机床的生产率。

为了实现调度目标，提出调度规则的动态选择方法，即根据系统的主调度目标，确定系统的主调度规则。在系统中未出现特殊情况时，用主调度规则实现对系统的调度；若出现特殊情况，则根据系统的辅助调度目标和特殊状况的类型确定辅助调度规则。主调度规则和辅助调度规则在系统中的动态选择，使系统可达到较好的主调度目标和辅助调度目标。本文通过采用最小松弛时间和零件优先级规则可使MT最小，从而保证零件的交货期。

4实例仿真

根据上面提出的零件虚拟工序队列的概念及动态调度算法，以直线型双排布局的FMS为例，在我们所研制的FMS动态调度仿真系统上对1个典型的加工任务进行仿真试验。该FMS由5台加工中心、1台AGV（正常运行速度为0.2 m/s）、1个装卸站、8个缓冲站和8个可用托盘组成。零件的某一子批加工计划（指经静态分批后生成的子加工计划）见表1，零件的加工工艺见表2，在没有对动态调度仿真系统进行人工干预的情况下经过14.293 32 min的仿真试验得出仿真结果。系统总加工时间为23.822 2 h，总生产率为2.395 5件/h,所用托盘数为6个。表3给出了机床和运输小车的仿真性能结果。因考虑了零件的可替代加工工序，且是在零件静态分批的基础上进行的，所以无法提供可供比较的例子。

表1零件的子批加工计划

零件编号批量交货期（天）零件优先级对应托盘数 A1 20 3 1 1 A2 12 2 1 2 A3 25 3 2 1 A4 24 2 2 1 A5 24 3 1 1 表2零件加工工艺及可替代加工工序

零件

编号工序加工时间(min) 机床1 机床2 机床3 机床4 机床5 A1

1 20 ― 25 ― ― 2 ― 25 ― 25 23 3 10 12 ― ― ― A2

1 60 ― 65 70 ― 2 ― 25 20 ― 20 A3

1 ― ― 40 ― 50 2 40 40 ― 35 ― 3 ― 35 40 ― 40 A4

1 ― 20 20 ― ― 2 ― 30 ― 25 25 A5

1 30 ― 20 ― ― 2 ― 25 ― 25 25 3 15 12 15 ― ― 4 ― 45 ― ― 25 表3对该子批零件的调度结果

机床

编号利用率

(%) 通过工

件数加工时间

（h）生产率

（件/h） MC1 78.777 38 17.5002 1.5951 MC2 89.13 26 20.3661 1.0914 MC3 86.262 24 19.7496 1.0075 MC4 52.333 24 11.6668 1.0075 MC5 78.987 25 17.9834 1.0494 AGV1 40.392 - - -

通过对调度结果的分析可知，本文提出的基于零件虚拟工序队列的动态调度算法是切实可行的。

*国家科学技术部重大攻关计划资助项目和国家863高技术发展计划资助项目(863―511―9608―004)

作者简介：赵天奇男，1965年生。清华大学（北京市100084）自动化系博士后研究人员、工学博士。研究方向为敏捷制造、并行工程、ERP、企业过程管理与优化。发表论文20余篇。

作者单位：陈禹六北京市100084清华大学

李培根武汉市430074华中理工大学

参考文献

1.邓子琼.FMS建模及仿真.北京:国防工业出版社,1993:58～96

2.赵天奇,李培根，段正澄.华中理工大学学报，,26(2):12～14

3.Andrew Kusiak. Intelligent Manufacturing Systems.New York:Prentice Hall, Inc., 1990:125～143

4.Chung Dae Young, Chank Wan Park.Computers Ind. Engin.，,31(3):557～568

篇3：基于零件虚拟工序队列的FMS动态调度研究

中国图书资料分类法分类号TH165TP271

Dynamic Scheduling Based on Virtual Operation Queue of Part for FMSs Zhao Tianqi(Tsinghua University,Beijing,China)ChenYuliuLi Peigenp 1367-1369 Abstract: In this paper a concept of Virtual Operation Queue of part is proposed, a dynamic production scheduling algorithm is presented based on static batching of FMSs. The restricts of manufacturing resources, influence of part handling system and some emergency events (e.g. machine breakdown, rush order joining etc.), alternative operations, etc. are considered in the algorithm. The algorithm is easy to be realized, and can be applied to dynamic scheduling for most types of FMSs, which have one or more AGVs and have linear or loop layout.

Key words:FMSVirtual Operation Queue of PartDynamic schedulingDispatching Rule

对于有效地利用已有FMS中的各种资源提高生产效率而言，合理完善的调度控制系统是关键。调度是指在时间意义上所有系统资源的定位、分配和处理，其系统分为加工子系统和运输子系统(刀具流系统和物料流系统)，其调度分为静态调度和动态调度。FMS的调度控制比较复杂，尤其当涉及的因素较多时，若要根据某一调度目标得到最优调度结果，往往很难满足实时性的要求。其实，多数情况下调度目标是人为的'，FMS调度只要得到近优解即可。

本文在零件静态分批的基础上提出零件虚拟工序队列的概念，并在此基础上提出1个解决FMS动态生产调度的启发式调度算法。

1FMS调度问题描述

FMS动态调度及零件静态分批之间的关系见图1。这里所研究的动态调度是在零件静态分

图1动态调度与零件静态分批之间的关系

FMS动态调度的目标是使系统具有较好的加工性能，一方面能使系统具有较高的生产率，即较高的设备利用率，另一方面能及时完成给定的加工任务。在本文中，调度主要考虑2方面的性能，即尽量满足加工任务中零件的交货期和尽可能减少系统生产时间。用以下2个指标来描述：工件平均延误时间（mean tardiness，MT）和工件平均流通时间（mean flow-time，MFT）。

MT反映零件是否满足交货

[1] [2] [3]

篇4：面向FMS生产调度和控制的零件动态工艺模型研究

面向FMS生产调度和控制的零件动态工艺模型研究

面向FMS生产调度和控制的零件动态工艺模型研究*注意：本文已经在《中国机械工程》(,9(9):36～38)杂志发表

使用者请注明文章内容出处赵天奇邓建春童国帆李培根段正澄摘要：提出一种基于FMS生产调度与控制的零件动态工艺模型。该模型由零件加工工序和各个工序之间的约束关系描述两部分组成，去掉了传统人为的加工顺序约束，易于与生产调度控制系统集成，能充分发挥FMS生产调度柔性的特点，为FMS优化生产调度的实现提供一条较好的途径。

关键词FMS生产调度CAPP动态工艺模型

中国图书资料分类法分类号TH165笔者根据FMS生产调度的特点，在现有零件模型的基础上提出零件的动态工艺模型。

1零件工艺模型的常用表达方法

通常的CAPP系统只能设计出静态的或只具有部分柔性的理想化的工艺规程。

1.1固定加工顺序的工艺文件方式

通常生产调度中使用的零件工艺文件格式为

零件名；

零件号；

工序1，机床名加工时间；

工序2，机床名加工时间；

……

工序n，机床名加工时间；

END

该方法的优点是表达方式简单明了，缺点是限制了加工的自由度及柔性，使得加工只能严格按给定的工艺顺序进行，从而限制了柔性加工系统最优指标的实现。该方法对单机加工或JOB―SHOP生产较合适。

1.2多工艺方案与/或图的表示方法［1，2］

图1为一个实例零件的与/或图。用与/或图

图1实例零件的加工顺序与/或图可以表示出零件加工顺序的部分约束关系。通过对该图按一定的启发式搜索算法进行搜索可得到多个可行的加工工艺路线。

该方法在一定程度上增加了CAPP的柔性，并考虑到了静态生产环境，但是没有考虑实际的动态生产情况，因而还很难在FMS生产系统中应用。

1.3有向图表示方法

有向图可以表示零件的加工工艺顺序。图2为一实例。通过对有向图的遍历可得到多个工艺方案。

图2实例零件工序结构的有向图表示该方法直观地表达了零件加工工序及工序之间的约束关系，可用图论的方法进行描述与变换，但对FMS可替代加工工序无法表达，须对多个加工工艺方案进行复杂的评价才有可能得到可行的加工方案。

2基于FMS的零件动态工艺模型

为了适应FMS生产柔性的特点，零件工艺描述必须既能反映零件的所有加工特征，又能反映出加工工序之间的约束关系，同时还能表示出加工工序的可替代性。所谓可替代加工工序是指某一工序可以由不同的机床加工完成，一旦确定好加工机床，则可完成该工序加工的其它候补工序即取消。

为了增加零件工艺表达的灵活性，减少人为的.对工艺加工顺序的约束，笔者以现有零件工艺模型为基础，提出了一种更灵活的表示方法。

零件动态工艺模型仍用有向图表示(见图3)，图中节点表示零件的一个加工工序或一系列的可替代加工工序，该工序与加工机床及对应的加工参数相联系(如加工时间、刀具号、NC文件名等)；有向弧表示零件工序的加工顺序约束关系。任何从头节点(Head)到尾节点(End)的遍历路径都是一个有效的加工工艺路线。

图3实例零件的动态工艺模型假设该有向图有n条遍历路线(工艺方案)，第i道工序有ki种加工方案(即有ki-1个可替代加工工序)，共有m个节点(不计Head和End节点)，则零件可能有的加工方案数为。

常用的CAPP系统产生的工艺方案较大地限制了零件工艺表达的柔性。较好的情况是仅考虑了部分生产调度的静态因素，而且一定要产生完整的和确定的加工工艺路线(一般要通过对多工艺方案进行评价后得到)，这使得CAPP系统过于复杂。这里提出的零件动态工艺模型却是仅提供零件的工序、可替代工序及工序加工顺序之间的约束关系，至于实际生产中具体选择什么样的加工顺序、每道工序中选择哪一个可替代工序则完全由实际生产中的资源状态、零件本身的加工情况以及用户的具体要求进行选择，零件的具体加工工艺路线不需要事先确定，直到零件加工好后才知道，并且相同类型的零件可能有不同的工艺路线，零件的具体加工工艺是在实际加工中根据系统的状态及加工性能指标动态重组而成。

这样的零件描述相对传统的Job-Shop生产而言似乎是不完备的，但却为现代化的柔性生产提供了更大的调度空间。该方法不仅大大减少了CAPP的工作量及难度，显著提高了实际生产调度控制中的灵活性，而且不会提高调度控制的难度，从而为FMS生产性能(如系统生产率、总加工时间、机床负荷平衡率等)的提高创造了条件。

3零件动态工艺模型的计算机表示方法及数据结构

3.1零件工艺参数描述

该部分描述了零件的所有工序参数，以文件形式表示，其结构为

零件名；

零件号；

工序1，工序11 工序12 … 工序1k1；

工序2，工序21 工序22 … 工序2k2；

……

工序n，工序n1 工序n2 … 工序nkn；

END

工序i表示第i道工序的信息节点；工序ij表示工序i的所有可完成该工序加工的工序节点序列。上述文件表示零件共有n道加工工序，其中工序1有k1种实现方法，工序2有k2种实现方法，……工序n有kn种实现方法。

工序信息节点及可替代工序节点的数据结构(C++语言表示)为

class ProcedureInfo∥工序信息节点类

｛ public：

ProcedureInfo:∥构造函数

ProcedureInfo(int,float,ProcedureInfo* AlternativeProcedureInfo=NULL)；

～ProcedureInfo();∥析构函数

int Machine_No;∥机床号

float Machining_Time;∥加工时间

ProcedureInfo* Alternative ProcedureInfo;∥替代工序的加工信息

｝；

class Procedure∥工序节点类

｛ public：

Procedure();∥构造函数

Procedure(int);∥构造函数

～Procedure();∥析构函数

int Procedure_No;∥工序号

ProcedureInfo*?ThisProcedureInfo;∥当前工序

Procedure* NextProcedure;∥下一道工序

｝；

3.2工艺约束关系描述

零件工艺约束关系主要描述各加工工序之间的加工顺序。因工序是有向图中的节点，工序之间的约束关系即为节点之间的关系，可用图论方法进行描述。

3.2.1用邻接矩阵方法

以图3为例来说明。

邻接矩阵

因实际零件邻接矩阵多为稀疏矩阵，也可用十字链

表结构表示。

3.2.2用邻接表方法

仍以图3为例说明。其邻接表(见图4)为

图4实例零件的邻接表形式

邻接表中每个方框表示零件的一道工序(即工序节点)，方框内的数字表示工序号。工序节点按工序号顺序排放(第一列)，并用箭头指向其相邻的工序节点。相邻的工序节点中节点号为正表示该节点为后续工序节点，为负表示该节点为前继工序节点。邻接表中工序节点的结构与类Procedure相似。

4基于零件动态工艺模型的调度控制方法的实现算法与特点

4.1实现算法

基于零件动态工艺模型的调度控制算法是在零件动态工艺模型的基础上结合启发式动态调度算法实现的，其过程为

Step 1：搜索零件邻接表，把无前继节点的工序节点加入可调度工序集合中。

Step 2：在可调度工序集合中动态选择一工序。

Step 3：搜索出该工序节点的后续节点。

a.删除这些后续工序节点中对应所选择的加工工序的前继工序节点；

b.在可调度工序集合中删除所选择的工序节点；

c.判断这些后续工序节点是否有前继节点，把无前继节点的工序节点加入可调度工序集合中。

Step 4：判断可调度工序集合中的元素个数：

若为零，则该零件加工完成，转Step 5；

否则转Step 2。

Step 5：发出该零件加工完成指令。

4.2零件动态工艺模型的特点

(1)易于实现。在CAPP阶段只根据零件工艺特征及生产系统资源产生实现这些特征的加工工序节点或可替代工序节点，以及工序之间的约束关系，而不需要直接产生确定的加工工艺方案以及对这些方案的评价；

(2)合理描述了零件的工艺过程，去掉了人为的不合理的加工顺序约束，并增加了对FMS中经常存在的可替代加工工序的描述；

(3)充分考虑了FMS生产的特点，易于与生产调度控制系统集成；

(4)能充分发挥FMS生产调度的柔性，并且不会显著增加调度控制的工作量与难度，为FMS的优化生产调度的实现奠定了基础。

参考文献

1Deng Chao.An Integrated System of CAPP and JOB-SHOP Scheduling.International Conference on Manufacturing Automation,HongKong,.

2Cai L G,Li P G,Duan Z C.An Applied Part Model Based on Form Feature Binary Tree for Integrated CAD/CAPP/CAM System of Rotational Componences.ICIM’95，Wuhan,1995.

赵天奇男，1965年生。华中理工大学(武汉市430074)机械科学与工程学院制造自动化研究所博士研究生、讲师。研究方向为柔性制造系统建模、仿真、调度与控制，CAD/CAPP/CAM集成技术，智能制造系统等，发表论文10多篇。

邓建春童国帆李培根段正澄武汉市430074华中理工大学

*国家863高技术计划资助项目(863―511―9608)

收稿日期：1997―05―20修回日期：1997―12―29

The Research on Part Dynamic Process Model Based on the Scheduling and controlling for FMS

Zhao Tianqi(Huazhong University of Science & Technology, Wuhan,P.R. China)

Deng Jianchun, Tong Guofan, Li Peigen, Duan Zhengcheng

Abstract: In thia paper adynamic process model of part is built based on the sceduling and controlling for FMS. It is composed of the processes(include the alternative processes)description and the constraint relationships among these processes.The model can celstraditional man-made constrains among processes, and can bring the flexibility to be integrated with production and sceduling system, so it provide a good method for optimal production and sceduling for FMS.

Keywords: FMS,sceduling, CAPP, dynamic process model