基于Arena的车间作业排序问题建模方法及其仿真优化系统设计

-1-基于Arena的车间作业排序问题建模方法及其仿真优化系统设计*潘燕春1，周泓1，冯允成1(1.北京航空航天大学经济管理学院，北京100083)摘要：针对生产车间作业排序问题的固有复杂性、目标函数难于解析求解等特点，建立了一个优化与仿真的集成系统框架。为解决传统方法中直接编写仿真器模式存在的难度大、求解能力弱等问题，提出了一种新的建模求解思路：首先，以通用仿真工具Arena为平台，提出虚拟抢占规则，实现了车间作业排序问题的仿真建模。然后，以GRASP优化算法为基础，结合高级语言VB，利用面向对象编程思想，通过Arena类库，设计了一个通用的车间作业排序问题的仿真优化系统框架，从而实现了优化和仿真的外部集成。在该框架下，可引入各种随机因素，提高对实际系统的建模与求解能力。最后，通过实例说明了这种方法的有效性。关键词：车间作业排序；仿真；优化；贪婪随机自适应搜索算法中图分类号：TP391.9文献标识码：A1．引言车间作业排序问题（JobShopScheduling）是生产系统和服务系统中的一类典型问题，其一般描述如下：有M个资源，N个作业，各作业在资源上的处理路径和时间(或成本)可能不同，研究目标是确定每个资源上的作业顺序和开工时间，使得某项评价指标达到最优(如作业平均逗留时间、最迟完工时间、作业总成本等)。[1]这类问题已被证明是NP难题，具有相当大的计算复杂性，随着问题规模的增加计算难度呈指数增长，传统的解析方法已经难于甚至根本不可能对其进行求解。[2]处理这类问题的常用的也是比较有效的方法就是现代启发式优化算法，由于目标函数难于解析求解，故在优化时往往利用仿真过程求取性能指标值[3]。这类方法的一个难点就是如何建立仿真系统模型，通常的做法是用程序语言(如Fortran、Pascal、C等)直接撰写仿真器嵌入到优化算法中进行调用，如文献[4]，针对实际车间作业排序问题，提出以遗传算法和分派规则相结合的优化方法，并引入基于事件驱动的仿真机制来模拟加工系统的运行过程，得到加工结果，由此对加工序列的性能指标进行评价从而进行优化搜索，这就将优化与仿真*基金项目：国家自然科学基金资助项目(70371005)，高校博士点专项科研基金资助项目(20020006-4)作者简介：潘燕春(1979.10-)，男(汉族)，江西赣州人，北京航空航天大学博士研究生，主要从事生产管理、序贯决策、计算机仿真、优化等研究。[e-mail]。集成了起来解决实际生产问题。但是，这种方法存在着许多不足之处，主要有①专业性较强，工作量较大。因为要自行编写仿真模型嵌入到优化算法中，所以对有关人员的计算机技术有很高的要求，而且大量的编程工作占用了不少时间；②因为是自己通过语言建立仿真模型，所以考虑的因素不可能很全面，如难于考虑实际系统中存在的加工时间的随机性、机器故障的随机性、运输时间和调整时间等，建模能力也就因此受到了较大的限制；③友好性和适用性不够强，通常难于用很好的动画交互界面将现实系统表现出来。随着仿真技术的发展，许多大型仿真软件相继推出，它们大多能提供友好的图形用户界面，并能根据用户输入的图形流程自动生成仿真程序，从而大大提高了仿真的规模、效率和实用性。但遗憾的是这类仿真软件本身一般都不具备优化能力，如果使其与优化算法直接集成，将能取得很好的效果。文献[5]对此作了一定的研究，利用面向对象编程方法建立了通用连续生产装置分析对象类，利用高级开发工具开发出相应的应用系统，但是文中所使用的是炼油装置的专业仿真工具，这也就限制了其通用性。本文以Arena[6][7]作为车间作业排序问题仿真建模的工具，利用其通用性，有效地克服了直接通过高级语言建模的专业性强、工作量大、很难考虑实际系统随机因素、不直观不友好等缺点，以GRASP（GreedyRandomizedAdaptiveSearchProcedure，贪婪随机自适应搜索算法）优化算法为例，提出了一个仿真优化系统的集成框架，并通过实例验证了其有效性，为仿真优化提供了一个新的思路。2．车间作业排序问题仿真优化系统的构建思想、方法与框架传统的仿真优化集成思想可用图1表示。对系统建立仿真模型，将仿真输出信息作为优化器的输入，优化器对仿真输出进行分析与评价后，得出新的系统参数或决策变量再作为仿真模型的新输入，以上过程不断重复，直至满足一定的停止规则。这种思想实现了优化算法与仿真的外部集成，提高了对问题的建模能力和灵活性。图1.传统仿真优化集成图以上述集成思想为基础，以通用仿真软件Arena为平台构建仿真模型进行仿真求取系统评价值，引入GRASP算法实现车间作业排序问题的仿真优化，其首要问题就是如何解决仿真和优化的集成。Arena采用面向对象编程的思想，将其核心模块都以类的形式封装在Arena类库中，以动态库的形式表现，在任何开发环境中都可以引用这个动态库，从而使用Arena的所有模块来达到控制整个仿真模型和仿真过程的目的。本文主要使用的Arena类库的对象如表1所示。表1.Arena类库有关对象的主要属性和方法列表对象名称属性或方法功能Models获取所需的仿真模型ApplicationQuit终止Arena应用程序BatchMode设定仿真是否动画显示Modules获取模型的所有模块（如到达、服务、队列、工艺路线等等）Save保存仿真模型Go驱动仿真模型进行仿真运行SIMAN获取模型的SIMAN对象用于在仿真模型处于运行状态时来控制仿真过程ModelEnd终止当前仿真模型的运行Data建模时读取和设置有关仿真模型参数ModuleUpdateShapes建模时保存模型参数VariableArrayValue运行时获取模型的变量值（系统评价值）SIMANSymbolNumber运行时获取对仿真模型参数的引用在优化程序中引用Arena的动态库，调用上述对象的有关属性和方法，不需要额外编程，即可集成Arena并控制其仿真运行。整个仿真优化系统的框架如图2所示，左半部分为优化系统，右半部分为仿真系统，虚线部分就是利用组建对象模型技术通过Arena类库实现优化和仿真互联。其中虚线1表示所生成的加工时间p(i,j)（即零件i的第j步操作的加工时间）和加工路径a(i,j)（即零件i的第j步操作所使用的机器号），虚线2表示由优化系统求得的可行解s(i,j)(即机器i的第j道工序所加工零件的零件号)，它们被转换并通过Arena类库导入到Arena系统的相应模块中，作为仿真模型的输入；虚线3表示通过仿真获得的最迟完工时间Cmax，它也通过Arena类库被转换成优化系统的输入参数。．GRASP算法GRASP算法是解决组合优化问题的一类很好的算法，主要由美国Texas大学机械工程学院教授DrThomasA.Feo于1989年提出，当时成功地用于解决飞机航班调度等著名的NP-Hard组合优化难题[8]。GRASP算法的每代循环都包含两个阶段：结构化阶段和局部搜索阶段。结构化阶段主要用于生成一个较好的初始可行解，其过程是根据贪婪函数的结果从可供选择的元素列表（称为RCL，RestrictedCandidateList）中一次选择一个元素，每选择一个元素RCL都变化一次，当所有的元素都选择完毕之后即生成了一个可行解。如果每次都选择RCL中的第一个元素则为完全贪婪算法，如果每次都从RCL中任意选择一个元素则为完全随机算法。按照贪婪函数确定的初始可行解并不一定是局部最优的，因此第二阶段主要是对第一阶段的解进行优化，其实现方法可根据具体的问题而定，一般都是采用不同的邻域变换策略进行的，最终可以得到每代循环的局部最优解。所有循环代数中的最好局部解就作为全局满意解。GRASP算法的结构化优化求解思路大致如图3所示。其中求解目标为最小化，J为所有未分配元素，Z′为局部最优值。图3.GRASP算法基本流程图以车间作业排序系统为例，假设有10台机器10个零件，每个零件在每台机器上有且仅有一道工序，则所有未分配元素（工序）为100个，因为一共有10台机器，所以每次可以从10道工序中选取一道进行加工，直至剩余未分配元素个数小于10，即RCL长度为10。如果采用最小加工时间优先为贪婪函数，则每次都比较一下RCL中10道工序的加工时间并由小到大排序，若k值取为6，则每次都从RCL前6个元素中随机选取一个进行加工，每安排一道工序RCL都更新一次。当100个元素都安排完成即生成一个可行解，然后就可以采用有效的搜索策略对该初始可行解进行局部优化。本文之所以采用GRASP作为仿真的优化算法，是由于GRASP算法的结构化特性，只要共享全局最优解和全局最优值，就非常容易实现并行计算，从而在仿真和优化集成时提高计算效率。事实上，本文提出的仿真优化框架已经实现了仿真和优化的外部集成，Arena作为仿真平台用于对复杂系统建模并求取系统评价值、验证优化结果的可行性；优化算法可以控制仿真的全过程，利用仿真输出的系统评价值逐步寻优。二者相对独立又互相联系，所以在此集成框架下，也可以考虑采用诸如遗传算法、禁忌搜索、神经网络等其它现代优化算法，以期达到更好的优化效果。4．车间作业排序系统的仿真建模建立车间作业排序仿真模型，要解决的一个主要问题就是如何在模型中表示作业排序，即每台机器前的加工顺序。本文利用优先级结合排队规则提出了一种实现方案，即在作业排序中越先被处理的零件给其赋一个越高的加工优先级，并且在队列中按最小属性值规则进行排队，用加工优先级作为该属性值，属性值越小优先级越高，其在队列中也就排在越前，这样就能越早被机器处理，即通过零件的加工优先级来实现作业排序。下面以3台机器3个零件的车间作业排序系统为例，说明作业排序与加工优先级的对应关系。如图4所示，正方形为零件，零件正上方数字为其对应的加工优先级数。设M(i，j)为第i台机器上第j个被加工的零件，则定义其加工优先级为P[M(i，j)]=j，如第1台机器上第3个被处理的零件是1，即M(1，3)=1，则定义机器1上零件1的加工优先级相应为P[M(1，3)]=P[1]=3。图4.作业排序与加工优先级的对应关系图但以上表示存在一个问题，因为离散事件仿真是按照未来事件顺序进行触发推进的，如果有个优先级较低的零件到达一台空闲的机器队列中，则系统将马上自动对其进行加工处理，例如在图4中，假设所有零件的加工路线均为机器1、机器2、机器3，零件3在机器1上加工完成后首先到达机器2，由于机器空闲，仿真系统将自动对其进行加工，这与机器2上定义的加工序列(先加工1，再加工3，最后加工2)相违背。而且，按以上过程得到的排序属于无延迟排序(non-delayscheduling)，根据作业排序的有关理论可知，最优解不一定在这类排序中[1]，故这可能会遗漏最优解。为了解决这一问题，本文设计了一种抢占(Preempt)模型，在出现上述情况时，让优先级高的零件抢占优先级低的零件的资源，并使该优先级低的零件重排到机器队列中，等待重新加工，且忽略其被抢占前所进行的加工处理，这样就能与给定的排序保持一致。但如果优先级低的零件加工完成了，优先级高的零件还没到达，则肯定不会发生抢占，此时优先级低的零件将被直接送往下一道工序进行加工，因而仿真系统仍会改变给定排序。为解决以上问题，本文设计了一个分支模块，让先获取资源的优先级低的零件延迟一个很大的时间值(相对加工时间而言为无穷大)，目的是等待优先级高的零件到达，从而发生必要的抢占。经过上述处理后，抢占模型中机器的加工顺序就与给定的排序完全保持一致了，最优解也不会被遗漏。上述抢占规则只是在仿真模型中虚拟进行的，实际加工过程是根据仿真结果来进行，所以并不违背