打开文本图片集
[摘要]柔性制造系统的生产调度问题是一个典型的非多项式困难问题。在整个调度过程中,常会发生各种意想不到的事情,从而影响原定的调度计划。文章详细讨论生产过程中可能出现的各类不确定性事件,并基于动态数据驱动仿真的思想,采用多智能体技术建立柔性制造企业生产线调度模型,给出模型的总体结构和各功能模块的详细说明,在此基础上,阐述模型的运行机制,为解决柔性制造系统的生产调度问题提供一种新的思路和方法。
[关键词]柔性制造系统;动态数据驱动仿真;多智能体;生产调度
[基金项目]杭州市社科联基金项目(B08YJ08)
[作者简介]江波,杭州职业技术学院金都管理学院讲师,工商管理硕士,研究方向: 管理信息系统、电子商务,浙江杭州,310018
[中图分类号] TP391.8[文献标识码] A[文章编号] 1007-7723(2010)03-0034-0005
一、引言
柔性制造系统(Semiconductor Wafer Fabrication System,SWFS)规模庞大、造价昂贵、设备繁多,具有反复重入型加工和多品种混合生产的特点,被列为有别于Flow-shop和Job-shop的第三类生产制造系统 。针对这一系统的生产线调度问题是具有NP特征的一类高度复杂而具有挑战性的课题,并且对实际生产具有重大意义。传统的求解方法基于组合优化、排队论、整数规划以及动态规划等的运筹学方法,由于柔性制造系统维数高,不确定性因数多,很难取得满意的结果。目前,国内外学者多采用建模与仿真的方法对这一领域的问题进行研究,并且取得了一些研究成果。Zhou 等分析了Petri网方法对柔性系统建模、离散事件仿真、性能分析和调度中的应用,表明Petri网模型对柔性制造过程中的复杂并行行为和并发行为有效;Kumar 和Dabbas 分别进行了基于启发式规则和复合优先级控制策略的调度仿真研究,其基本思想是同时优化多个运行中的性能指标;李莉等基于群体智能思想,对柔性制造系统生产线重调度问题进行了研究,代表了柔性制造系统调度理论研究的新的方向,但目前的研究还远未成熟。
动态数据驱动应用系统(Data Driven Application System, DDDAS)是一种能够将试验或测量数据与仿真紧密结合在一起的新型研究模式,是未来仿真应用的重要发展方向之一。通过在仿真运行时将附加数据动态地引入模型,并在此基础上有选择性地抽象、细化初始模型或进行模型替换,可以实现仿真模型与实验之间的动态反馈 。区别于传统的静态仿真,DDDAS具有良好的综合集成结构、仿真实时性好、适应性强等特点。而这些特点都有利于我们把它作为研究复杂系统问题的研究手段。
为了解决柔性制造系统生产线调度问题,本文首先分析其生产过程中可能出现的各类不确定性事件,然后基于动态数据驱动思想和多智能体技术,提出动态数据驱动的柔性制造系统企业生产线调度模型,并且在此基础上,对模型的功能模块、运行机制进行详细阐述。
二、柔性制造系统的不确定性
柔性制造系统的制造过程非常复杂,包括外延、氧化、光刻、注入、溅射、刻蚀、淀积等7道加工工艺。由于多重入流的特性,典型的柔性制造系统加工流程往往有250～600个工步,涉及设备种类60～80种,设备台数多达上百台。柔性制造系统生产线是典型的离散事件动态系统,存在各种各样的不确定性事件。不确定性事件的发生会影响生产线的运行,造成系统性能指标的恶化,生成的调度方案不再可用。其可能存在的不确定因素很多,按发生性质的不同,可以分为外部环境的不确定性、生产环境的不确定性、生产过程的不确定性、生产性能的不确定性等四类,如表1所示。
三、动态数据驱动仿真的概念和系统框架
Frederica Darema博士在20世纪80年代利用仿真和测量做石油开采的辐射传播计算时,首先产生了DDDAS的思想 。由于受当时计算机水平的限制,其研究思想并没能得到实现。直到2000年3月美国NSF(The National Science Foundation)组织的专题讨论会上,动态数据驱动应用系统(DDDAS, Dynamic data driven application system)这一术语才被正式确定。DDDAS是一种全新的仿真应用模式,旨在将仿真与试验有机结合起来,使仿真在运行过程中动态地从实际系统中接收新的数据,并作出响应,仿真结果也可以动态地控制实际系统的运行,并指导数据测量的进行。仿真与实际系统之间构成一个相互协作的共生的动态反馈控制系统。在DDDAS的概念中,试验是指真实系统的实际运行,包括真实事件活动和试验活动。本文中我们特指柔性制造系统生产线上的整个加工流程。新数据指的是通过测量和数据采集获得的生产线上各设备加工点的运行数据,该数据既可以实时反馈到仿真系统,支持模型动态调整和运行,也可以存档读出,作为离线模型挖掘和更新知识库的试验数据。
(一)区别于静态的仿真系统,DDDAS的动态性主要表现在三个方面
1.根据仿真结果,仿真系统实时调整仿真模型和模型分辨率,并且据此控制真实系统和选择采集注入数据。
2.根据真实数据与仿真结果的对比,仿真系统实时调整仿真模型和模型分辨率,并且据此控制真实系统和选择采集注入数据。
3.根据专家的决策,由专家选择仿真模型和模型分辨率,仿真系统自适应控制真实系统和选择采集注入数据。
DDDAS的系统框架如图1所示:
(二)各单元模块的功能如下
1.控制单元:控制仿真模型运行,抽取模型的状态特征数据与注入数据对比分析,据此调整模型和分辨率;控制实际生产线运行,根据仿真结果数据反馈生产线调度优化方案;控制数据采集,根据仿真结果数据产生数据采集策略,反馈数据采集模块执行。
2.仿真模型单元:根据控制系统指令,产生新的仿真目标策略。据此,从模型库调用相应模型进行新模型的构建,并动态调整模型或模型参数,达到仿真结果与仿真目标逼近。最后,将模型与仿真结果进行分析评价,并形成知识保存在知识库中,为完善模型库构建和模型选择提供依据。
3.人机接口单元:显示仿真结果,支持用户对仿真策略进行调整和控制,支持用户根据仿真结果对生产线运行进行控制,支持用户根据仿真结果对数据采集策略进行选择控制。
4.数据采集单元:根据控制系统指令,生成新的数据采集策略。据此,采集生产线上的数据,并且具备多信息源数据融合能力。
四、基于动态数据驱动和多智能体的柔性制造系统生产线调度模型
根据上节描述的DDDAS的系统结构,本文采用多智能体技术建立了柔性制造系统生产调度模型。如图2所示:
从图2中可见,系统模型由独立的、具有一定功能而又相互联系的智能体单元组成,在此基础上分别建立各单元模型,并对各单元间的相互作用进行表述,从而建立整个系统的模型。其具体的组成结构及功能如下:
(一)动态数据驱动仿真单元
此单元由调度模块和仿真模块组成,完成调度方案的生成功能。
其中,调度模块包括相互协同的两个层次:上层模块是生产计划调度器,采用全局优化的方法,利用群体智能蚁群算法进行寻优,可产生一个静态的调度计划,其寻优时间长的问题可以通过多Agent建模的分布式计算能力得到解决。下层模块是实时调度模块,采用启发式的规则对生成的调度计划进行调整,并通过仿真进行分析和验证。当不确定事件发生,生产线上的环境变量发生改变时,该模块负责调整调度计划适应新的系统状态。如果在多个调度目标无法优化的情况下,通知上层模块,重新生成调度计划。整个过程是一个动态反馈过程。采用智能算法的优点在于能够从全局的角度进行优化,缺点在于模型描述的精度不高和易于陷入局部优化解;利用带启发式规则的仿真方法恰恰能够精确地描述模型和改善局部的解的性能,同时在较短的时间内生成优化的调度方案。上层的调度结果不仅会指导下层的调度过程,即带启发式规则的仿真是对智能蚁群算法产生的调度计划的局部修改;而且下层的调度结果也能帮助上层的调度寻优,启发式规则产生的某些局部优化解也可以作为启发信息指导蚁群算法更快地收敛。
仿真模块完成以下三种功能:首先,它能够实现用户可视化的生产线建模,模型的复杂程度可以根据用户研究问题的深度不同进行定义和设置;其次,为适应动态变化的生产环境,在仿真运行过程中,生产模型也可以根据生产线的具体情况进行自动修正,如某个设备失效等;最后,对调度模块产生的调度方案进行仿真,并把由此生成的对该调度方案的多目标评价值和对瓶颈设备的预测数据反馈给调度模块,作为对下一步调度优化判断的依据。
(二)动态数据驱动仿真控制单元
由中心推理机和辅助功能Agent组成,共同构成一个调度决策支持系统。中心推理机实现基于案例库或规则库的智能决策功能,辅助功能Agent在中心推理机的协同下工作,包括多目标管理Agent、优化策略管理Agent、调度仿真剧情管理Agent、调度因素分析Agent等四种类型的Agent,它们分别实现不同的控制功能。
多目标管理Agent:负责控制当前调度优化的方向,对调度方案评价函数中多个不同目标的权重进行动态的参数调整,实现调度目标与当前生产线的实际生产情况一致。柔性制造系统生产线调度问题是一个多目标的优化问题。短期优化目标包括:最大化生产量、最大化WIP移动步数、最小订单交货延迟率、降低加工周期、降低加工周期方差、降低WIP水平等。目标之间存在相互制约的关系,如何选取各目标优化的权重以平衡各目标优化的能力是需要解决的问题。各目标权值的大小比例是一个动态调适的过程。首先,它必须与我们生产计划对当前生产的要求和侧重点一致。同时,它也在不断地动态调整,保持与生产线当前的实际生产情况一致,完成这个任务需要中心推理机的协同,如基于案例库的推理等。
优化策略管理Agent:直接对调度和仿真模块下达指令,负责监控调度仿真的执行过程。优化策略管理Agent根据控制模块设定的优化目标或调度模块反馈的优化目标的达成情况,在中心推理机的帮助下,按照推理规则,进行模型和算法的调整,实现全局优化算法和局部优化算法之间的动态协作,当满足一定的条件时,返回优化的调度方案作为当前的最优解。
调度仿真剧情管理Agent:协助用户完成“what-if”分析。与传统仿真不同,动态数据驱动仿真是一种与生产线生产过程并行的仿真方法。因此,我们可以在仿真过程中设置多个时间断点,通过改变假设条件来进行生产预测;同时,也可以进行回放分析,这在传统仿真方法中是无法实现的。对多剧情仿真的管理由仿真剧情管理Agent实现;同时,仿真参数和得到的结果也将作为知识保存在案例库中。
调度因素分析Agent:接收来自数据采集模块的实时生产线数据,比较仿真数据与生产数据的差异,如果发现两者有较大的偏差,即参数超出了允许的域值范围,则使用中心推理机分析原因,并将分析的调度因素传递给优化策略管理Agent,作为调整调度模型和算法的依据。同时,将调度因素反馈给数据采集策略Agent,由后者按一定的策略完成下一步的生产线数据采集工作。
(三)动态数据注入单元
由数据采集策略Agent根据调度因素分析Agent反馈的结果生成下一步的数据采集策略,然后派出对应的移动Agent到生产制造EMS系统中采集生产线上的生产数据。由于柔性制造系统生产线由上百个生产设备构成,如果对所有的生产数据进行采集必然影响数据的采集效率,所以采用移动Agent既缩短时间又提高数据的精确性,同时还可以根据需要对数据作一定的预处理以缩小传递的数据量。
(四)用户界面交互Agent
负责把仿真数据展示给用户,同时,接收用户对仿真模型或参数的控制。使用户可以实时地控制仿真的整个过程,并利用仿真结果指导生产和数据采集过程。
五、模型运行机制
为了反映模型的动态特征,在模块功能划分的基础上,我们对模型的运行机制进行说明。采用标准UML活动图进行描述,如图3所示:
从图3中可见,动态数据驱动仿真的过程与生产线的生产过程是并行进行的。仿真系统根据一定的时钟节拍采样生产线上的数据;然后,将仿真数据与生产线数据作比较,使用因素分析Agent分析原因。如果发现两者有较大的偏差,即参数超出了允许的域值范围,则调整仿真模型,重新进行仿真。其中,仿真模型根据动态注入的生产数据完成自适应调整是整个DDDAS的核心,本文采用分层优化的思想生成调度方案,同时达到全局和局部的优化目标。首先,将智能搜索技术与离散事件仿真技术相结合,得到上层的调度方案;然后,应用优化策略Agent对仿真结果进行分析,找到进一步优化的方向,利用启发式调度规则进行方案调整得到下层的调度方案,并反复地使用仿真进行验证。不仅下层的调度方案建立在上层调度方案的基础上;同时,上层的调度模块接受下层调度方案的局部优化解作为启发信息引导搜索过程,以加快收敛,在较短的时间内得到全局的优化解。与传统的静态仿真不同,DDDAS仿真能动态地吸收新的数据,并将仿真过程同真实系统相融合,让二者相互协同起来。一方面,通过真实系统运行过程中产生的参数同步地对仿真系统进行调整,可以大大提高仿真的准确性、时效性、智能化;另一方面,通过仿真提供的数据同步地为真实系统地运行提供决策支持,这些将大大地扩展仿真系统的应用能力。
六、结语
柔性生产制造系统是一类复杂的生产系统,由于其生产环境变量容易发生改变导致生成的调度方案时效性差,传统的基于静态仿真的方法,必须人为干涉和设定参数,在研究此类问题上具有局限性。本文基于动态数据驱动仿真的思想,采用多智能体建立了柔性制造系统制造企业生产线调度模型;并且给出了主要功能结构与数据联系,阐述了模型的运行机制,为原型系统的实现奠定了基础。
[参考文献]
[1]Uzsoy R, Lee C Y, Martin V, Louis A. Review of production planning and scheduling models in the semiconductor industry part II: shop-floor control[J]. IIE Transactions, 1994,26(5): 44-55.
[2]Zhou MC,Venkatesh K.Modeling, Simulation and Control of Flexible Manufacturing System:A Petri Net Approach. Singapore:World Scientific.1998
[3]Kumar P. R.Scheduling Semiconductor Manufacturing Plants [J]. IEEE Transactions on Semiconductor Manufacturing 1994,9(1):33-40
[4]Dabbas R M,Chen H N,Fowler J W,Shunk D.A Combined Dispatching Criteria Approach to Scheduling Semiconductor Manufacturing Systems [J] Computers& Industrial Engineering,2001 39:307-324.
[5]李莉. 半导体生产线动态实时智能调度方法研究[D]. 同济大学,2005.
[6]Catriona Kennedy, Intelligent Management of Data Driven Simulations to Support Model Building in the Social Sciences[C]. ICCS 2006, Berlin, Springer-Verlag, 2006, LNCS 3993:562-569.
[7]Frederica Darema. Grid Computing and Beyond: The Context of Dynamic Data Driven Applications Systems [J]. Proceeding of the IEEE(S0018-9219), 2005, 93(3): 692-697.
[8]Frederica Darema. The Next Generation Software Program [J]. International Journal of Parallel Programming (S0885-7458), 2005,33(2): 73-79.