e-works数字化企业网  »  文章频道  »  先进制造技术  »  柔性制造

一种自适应的柔性制造系统优化调度算法

2009/8/25    来源:万方数据    作者:何传俊  杨东升  李家霁      
关键字:FMS  偏序图  拓扑排序  关键路径法  层次分析法  
讨论了柔性制造系统的工序流程调度问题,首先通过对工艺流程偏序图拓扑排序求得每道工序的最早发生时间和最迟开始时间,利用关键路径法求得关键路径后引入层次分析法。定性与定量相结合综合考虑各种相关因素建立起自适应优化模型,从而使各数字控制设备加工任务队列根据系统实时状态及当前需求自动优化,具有最优化加工时间、平衡设备利用率以及调度简单均衡等优点。

    柔性制造系统(FMS)是由统一的信息控制系统、物料储运系统和一组数字控制加工设备组成,能适应加工对象变换的自动化机械制造系统。FMS任务调度与优化是FMS信息控制系统的核心模块,通过决定工件在设备上的分配以及工件在设备上的加工顺序这样一个过程,实现一些运行指标的优化,如提高设备利用率、避免瓶颈的产生、降低死锁可能性、减小总加工时间等要求,使得系统运行达到最佳。然而由于柔性制造系统调度问题的复杂性,人们至今未能找到一个完美的解决方案。一般而言,FMS的调度问题是一个NP难组合问题,用多项式算法不大可能求得最优解。

    FMS的调度问题可以被分为两个部分:用模型语言抽象化系统特征以建立系统模型及根据模型信息采用某种方法求调度优化解。本文首先使用关键路径法求得FMS系统加工工艺偏序图的关键路径,然后再使用层次分析法综合考虑各种相关因素,根据系统当前状态和用户需求动态调度各数字控制设备的加工任务队列,使其具有自适应的特点,为柔性制造系统的调度提供了一条有效的途径。

1 工序流程偏序图及相关术语

    一个需要加工相关工艺的FMS系统可表示为(NC,A),其中NC={NC1,NC2,NC3,…,NCn}是一个数字控制加工设备集合,由n台功能各异的加工中心组成;A={A1,A2,A3,…,Am}是工艺流程集合,集合A中的工艺Ai={Wi1,Wi2,Wi3,…,Wiq},(i∈[1,m])由q个相应的工序子任务组成,可用前驱图G(Gi,≤),(i∈[1,m])来表示。

    对于同一个工件的各工序Wij来说,不可能同时进行,同时在一台机床上加工的各工序Wij间也不需装卸和二次装夹。但由于不同机床的加工能力不同,工件的工艺偏序图中会出现多个路径。比如某工序只有某一台机床可以完成,此时就需要将已经加工完毕的工件调度到该机床进行加工。与此同时,为了提高各机床利用率,也有可能使用所有机床都参与加工工件Ai,而不是只在一台机床上加工工件Ai。

    在FMS任务调度中,工序前驱图(Gi,≤)中的每个节点表示了工艺i中相应的工序,各工序的相关执行时间用节点的权值Z(Wij)来表示。从前驱图i的节点Wir到节点Wit的有向边表示各工艺的偏序关系≤,记为Wir→Wit,即Wit和Wir应按顺序执行,Wir是Wit的直接前驱,Wit是Wir的直接后继。有向边的权值Ze(Wir,Wit)表示物料储运系统堆垛机将待加工工件送入加工中心时间以及工件二次装夹时间等相关操作的时间。在前驱图Gi中只有一个入度为零的工序(称为源点工序)和一个出度为零的工序(称为汇点工序)。

    由于每道工艺流程Ai需要完成不同的生产加工任务,需要不同的人力和设备,因此需要结合生产线的实际情况进行更进一步的分析,制定工序流程及相应的工序流程图(Gi,≤),并确定完成每道工序形,所需的时间及其最早发生时间和最迟开始时间。

    设工艺流程图Ai源点是工序Wi1,从Wi1到Wij的最长路径长度叫做工序Wij的最早发生时间,该时间决定了所有以Wij为尾的弧所表示活动的最早开始时间。用Tee(Wij)表示活动Wij的最早开始时间。而工序Wij的最迟开始时间Tll(Wij)表示在不推迟整个工程完成的前提下,活动Wij最迟必须开始进行的时间。

    对于两个不同工艺流程Ai、Ak上的不同工序Wij和Wkl,根据其权重执行时间都可以量化为工序最早开始时间Tee(Wij)Tee(Wkl),由于时间Tee(Wij)和Tee(Wkl)都是实数,因此必有Tee(Wij)≤Tee(Wkl)或Tee(Wkl)≤Tee(Wij)。这样就说明了关系“≤”是工艺集{A1,A2,A3,…,Am}上的一个全序。由于全序关系表示了集合中的全体成员都可比较,因此图A中的任意两个序偶Tij、Tkl都是拓扑有序的,图A是一个拓扑有序序列。故证明了利用对图A拓扑排序的过程中求得每道工序的最早发生时间和最迟开始时间的可行性。

2 算法设计

2.1 数据结构

    可使用邻接表(Adjacency list)来存储各个工艺的工序前驱图,同时使用数字加工设备队列和加工任务队列数组来表征FMS任务调度监控系统。

    (1)邻接表Ali(i∈[1,m]):存储Ai的工序前驱图G(Gi,≤)。

    (2)数字加工设备队列QNC:数字控制加工设备集合NC={NC1,NC2,NC3,…,NCn}所链成的队列。

    (3)数字加工设备加工任务队列数组QWi(i∈[1,n]):表示数字加工设备NCi上需加工的工序顺序。初始时队列为空,调度后任务被插入相应队列。加工设备根据队列中各工序的执行顺序以及各自工序的开始时间进行执行加工任务。

2.2 关键路径法求得关键路径

    由于工序流程图各节点权值Z(Wir)表示该工艺的相关执行时间,有向边权值Ze(Wit,Wir)表示FMS中堆垛机运送工件时间和工件二次装夹时间,故工序流程图也可看作是节点带权值的AOV-网(Activity On Vertex Network)。由于在该网络中有些工序可以在数字加工设备上并行执行,故完成整个工艺流程集合A的最短时间是从源点工序到汇点工序的最长路径的长度,即路径上各活动持续时间之和。

    此时,整个工艺流程集合A={A1,A2,A3,…,Am}表示了一个加工任务,该加工任务使用m个加工工艺用来加工m个工件。因上文说明了关系“≤”是工艺集A={A1,A2,A3,…,Am}上的一个全序,故可使用以下算法对整个工艺拓扑图集合A进行排序,用来调度一个加工任务加工多个工件。这样由于加工多个工件,每个工件有一个拓扑图,为了找出集合A的最长路径,可使用关键路径法对这些拓扑图进行拓扑排序。

    关键路径法(Critical Path Method)是一种通过分析活动序列进度安排的灵活性来预测项目工期的网络分析技术。关键路线法的关键是确定项目网络图的关键路线,这一工作需要依赖活动清单、工艺偏序图及活动持续时间估计等各方面情况。在求解时可利用对图A进行拓扑排序的过程求得每个工序的最早发生时间和最迟开始时间,从而得到每项活动的总时差TS(Wir)。首先设一栈暂存所有入度为零的顶点,再依次按照如下过程操作工序邻接表。

    (1)遍历邻接表中单链表上的表头节点Wir,得到各节点Wir的入度。

    (2)若工序节点Wir的入度为零,则该工序Wir入栈且遍历以该节点为头节点的单链表,对其每个邻接点Wit入度减1。入度为零的顶点即为没有前驱的顶点,通过弧头顶点的人度减l实现了删除工序前驱图中该顶点以及以它为尾的弧的操作。如一个工序有多个前驱工序,则选取加工时间最长的前驱以求得最早开始时间。可称每次循环中同时入栈的节点为同一层次节点,其工序最早开始时间Tee(Wir)和最早结束时间Tel(Wir)计算公式如式(1)、(2)、(3)。

    Tee(Wil)=Tee(start)=Ze(0,Wit) (1)

    其中Wil是图中的源点,权值Ze(0,Wil)为堆垛机将托盘送入数字加工设备的时间。

    Tee(Wir)=max{Tee(Wit)+Z(Wit)+Ze(Wit,Wir)} (2)

    其中∈T,且在图Ai中Wit≤Wir,T是所有以第t个节点为头的弧的集合。

    Tel(Wir)=Tee(Wir)+Z(Wir) (3)

    即最早开始时间加上工序的加工时间。

    (3)在所有的节点都进栈后,开始出栈的过程。入栈过程中每次循环同时入栈的节点此时同时出栈,如一个工序有多个后继工序,则选取加工时间最短的后继以求得最迟开始时间。则最迟开始时间Tll(Wit)和最迟结束时间Tle(Wit)为

    Tll(Win)=Tll(End) (4)

    其中Win是图中的汇点。

    Tll(Wit)=min{Tll(Wir)-Z(Wir)} (5)

    其中∈T,且在图Ai中Wir≤Wit,T是所有以第t个节点为头的弧的集合。

    Tle(Wit)=Tll(Wit)+Z(Wit) (6)

    即最迟开始时间加上工序的加工时间。

    (4)计算每项活动的总时差TS(Wir),计算公式为

    TS(Wir)=Tle(Wir)-Tll(Wir) (7)

    即最迟结束时间减去最早开始时间。得出总时差后将其写入邻接表。

    (5)当栈为空时算法结束,这样就完成了对整个图A的拓扑排序遍历,得到了每道工序的最早开始时间Tee(Wir)、最迟开始时间Tll(Wir)和总时差TS(Wir)。

    (6)最后遍历图Ai,依次找出同一层次节点中总时差最小的节点,这些节点就构成关键路线。

    (7)将关键路线上的节点按照拓扑序入数字加工设备加工任务队列QW1,其余节点按拓扑序依次平均分配到任务队列QWi(i∈[2,n])。

    分析以上算法,对于有n道工序节点、m条弧的偏序图,求各节点入度的时间复杂度为O(m);各节点入栈出栈,入度减1的操作时问复杂度都为O(n),各工序入队列的时间复杂度为0(n),所以总的时间复杂度为0(m+n)。


如有任何看法或投稿请联系 MSN:liangxi1122@hotmail.com;QQ:85557991

责任编辑:梁曦
本文为授权转载文章,任何人未经原授权方同意,不得复制、转载、摘编等任何方式进行使用,e-works不承担由此而产生的任何法律责任! 如有异议请及时告之,以便进行及时处理。联系方式:editor@e-works.net.cn tel:027-87592219/20/21。
相关资料
e-works
官方微信
掌上
信息化
编辑推荐
新闻推荐
博客推荐
视频推荐