【作者】 文一凭；

【导师】 陈志刚；

【作者基本信息】 中南大学 ， 计算机科学与技术， 2013， 博士

【摘要】 目前,工作流技术已成为实现企业业务过程自动化的核心技术之一,并已广泛应用于工作流管理系统、业务过程管理系统、企业资源计划系统等过程感知的信息系统中。与此同时,在现实生产、管理等业务过程中存在着许多需要根据同一过程多个实例间的关联或约束关系进行实例方面处理的情形。这种处理有利于提高过程的执行效率并降低执行成本,但目前支持这种实例方面处理的工作流建模方法、保障其正确运行的工作流调度方法尚不完善。主要表现在：现有工作流建模方法与工作流模型尚未能完全描述出实例方面处理所需的过程实例之间的关联或约束关系。现有工作流执行机制缺乏对同一过程中多个密切联系的活动进行实例方面调度控制与优化处理。而现有工作流挖掘方法也不能有效的从事件日志中构建出反映了实例方面处理情况的工作流模型。本文针对这些问题展开了深入研究,主要工作与贡献如下：(1)研究了支持实例方面处理的工作流模型。本文分析了实例方面处理对工作流模型所带来的新需求,根据这些需求,通过引入实例方面处理区、可实例方面处理活动、实例方面处理数据操作等新元素,扩展了工作流管理联盟WfMC定义的工作流元模型,并提出了可描述这些新元素以及投影、分组选择、合并、分发、拆分等数据操作的工作流实例方面模型。(2)提出了一种工作流实例方面调度控制机制。该机制通过过程控制器、BPA控制器、活动实例管理器MShell、执行者资源管理器等组件及相关控制算法来控制活动实例分组合并过程,并由MShell维护活动实例分组信息,解决了由实例方面处理引发的多个活动间活动实例分组一致性保障问题。同时,本文根据该机制设计了一个基于ECA规则的实例方面处理调度控制引擎,该引擎通过对工作流执行服务进行功能扩展来实现,并能与传统工作流引擎有效结合。实例展示表明,该引擎可使活动实例分组合并过程在受控状态下自动完成,完全可满足现实应用中的实例方面处理需求。(3)以最小化活动实例总停留时间为目标,建立了活动实例分组调度时间优化问题(本文记之为UM,N|1|Tmin)的优化模型,并提出了两种调度优化算法PSOSA-T与ACO-T。活动实例分组调度方案包括活动实例的分组、指派执行者、安排在执行者上的执行顺序三个方面的决策信息。PSOSA-T算法仅对活动实例的选择顺序进行隐式编码,通过将微粒群优化算法与模拟退火算法相结合搜索产生不同的活动实例选择序列,对该序列进行解码后再获得活动实例分组调度方案。ACO-T算法利用蚁群优化算法的特点直接构建可行解,并考虑了分组中活动实例执行难度问的差异对活动实例停留时间的影响,提出了分组浪费时间的概念来设计启发式信息以指导蚂蚁更有效的搜索。通过对解的质量及算法时间性能的实验评估,验证了这两个算法的有效性。(4)以最小化活动实例总停留时间及最小化活动实例总执行费用为目标,建立了活动实例分组调度时间费用优化问题(本文记之为YM,N|1|Tmin,Cin)的优化模型,提出了两种调度优化算法MOPSO-TC与PACO-TC。MOPSO-TC算法采用了与PSOSA-T算法相似的编码与解码方法,并利用时分变异机制及拥挤距离测度来引导微粒群体的搜索过程,最终产生一组满足约束条件的Pareto优化调度方案。PACO-TC算法构建可行解的方式与ACO-T算法相似,并针对优化目标函数的特点,提出了分组浪费时间与分组浪费费用的概念来设计启发式信息与候选列表。MOPSO-TC算法具有较低的算法复杂性,PACO-TC算法以执行时间增加为代价可以找到较优的解。两算法各有优势,具有重要的参考价值。(5)提出了一种基于工作流网的工作流实例方面模型挖掘方法。该方法通过分析描述了业务过程实际执行情况的事件日志中活动输入输出等数据的特点,提出了活动实例方面处理特征等概念来探测活动实例方面处理情况,并结合现有工作流挖掘算法来挖掘工作流实例方面模型。该方法充分利用了现有工作流挖掘方法的优越性能,同时也解决了现有工作流挖掘方法无法挖掘出工作流实例方面模型的问题。仿真实验验证了该方法的有效性。更多还原

【Abstract】 Nowadays, workflow technology has become one of the core technologies of achieving enterprise business process automatization. Many process-aware information systems such as workflow management system, business process management system and enterprise resource planning system have employed workflow technology. At the same time, the relationship and constraints among multiple workflow instances of the same type commonly exist in practical production or administrative business process. Some of them have been noticed and utilized to improve efficiency or save execution cost. However, current workflow modeling methods for describing relationship and constraints among workflow instance still need to be further researched. Current workflow scheduling methods for dynamic workflow instance aspect handling are incomplete also. For example, it is still difficult to effectively and completely model the relationship and constraints among multiple workflow instances of the same type as what is happened in traditional worklow. Existing workflow scheduling mechanisms lack the capability of supporting multiple activities’dynamic instance aspect handling and optimization. Mining workflow model from event logs is an important workflow mining method, but existing workflow mining algorithms cann’t obtain information on workflow instance aspect. The above problems are researched deeply in this thesis. The main work and contributions of the thesis are as followes:(1) To describe and suit for the characteristic of dynamic instance aspect handling in workflows, a workflow instance aspect model is proposed.The new requirements of workflow model to support workflow instance aspect handling are analyzed. To meet these requirements, new elements such as instance aspect handling area, activity able of instance aspect handling and data operation supporting instance aspect handling are introduced to extend the process definition meta-model by the Workflow Management Coalition. Based on the extended meta-model, a workflow instance aspect model is proposed, which can describe these new elements and related data operations such as projection, selection, combination, distribution and division.(2) To solve the problem of supporting multiple activities’dynamic instance aspect handling under workflow management system environment, a mechanism that controls the process of workflow instance aspect handling is presented.The proposed control mechanism consists of several components such as process controller, BPA controller, activity instance manager, executor manager and related control algorithms. Among these components, the activity instance manager is mainly to maintain information related to activity instance groups, by which the control problems caused by workflow instance aspect handling can be solved. Besides, a scheduling engine supporting workflow instance aspect handling is designed according to such mechanism. The proposed scheduling engine can be viewed as an extention to workflow enactment service and it can work well with traditional workflow engine. An exhibited example shows that the proposed control mechanism can well control the automation process of workflow instance aspect handling and meet the needs of practical applications completely.(3) To solve the time optimization problem of grouping and scheduling multiple workflow activity instances with the objective of minimum acitity instances’total dwelling time and multiple constraints, denoted by UM.N|1|Tmin, its mathematic model is constructed and two scheduling algorithms of PSOSA-T and ACO-T are proposed.The PSOSA-T algorithm is based on particle swarm optimization and simulated annealing algorithm. It adopts a coding approach based on the sequence of activity instances. The feasible solutions are produced indirectly by decoding such sequence. Because traditional particle swarm optimization is easy to get trapped in local minima, simulated annealing algorithm is used to overcome such drawback. In the ACO-T algorithm, the candidate solutions are constructed directly by using the ACO’s characteristic in construction, which obviously improved the efficiency in optimization. Besides, the conception of wasted grouping time is defined according to the optimization objective of the Um,N|1|Tmin problem, which is used as a base of constructing heuristic information to guide the search process of ant colony. The results of simulation experiment show the effectiveness of these two algorithms.(4) To solve the time-cost trade-off optimization problem of grouping and scheduling multiple workflow activity instances with the objectives of minimum acitity instances’total dwelling time and minimum acitity instances’total cost and multiple constraints, denoted by UM,N|1|Tmin,Cmin, its mathematic model is constructed and two scheduling algorithms of MOPSO-TC and PACO-TC are proposed.The coding and decoding methods in the MOPSO-TC algorithm are similar to the PSOSA-T algorithm. However, MOPSO-TC adopts crowding distance measure of particle’s density and a time variant mutation operator based on random swapping to guide the search process of particles. A set of Pareto optimal solutions satisfying constraints can be obtained in the end. In the PACO-TC algorithm, the solutions are constructed just like the ACO-T algorithm. Besides, the conception of wasted grouping time and wasted grouping cost are introduced according to the two different optimization objectives of the UM,N|1|Tmin,Cmin problem, based on which the heuristic information and candidate list for the ants are designed. The experiments are also performed to evaluate these two algorithms in Pareto solution quality and time consuming. In comparison with MOPSO-TC, PACO-TC can get better solutions at the cost of increased time consuming.(5) To overcome the shortcomings of traditional workflow modeling methods, an algorithm to mine workflow instance aspect model from event logs is proposed.The proposed mining algorithm can effectively mine batch processing workflow models from event logs by considering the instance aspect relations among activity instances in multiple workflow cases. The notion of instance aspect handling feature and its corresponding mining algorithm are also presented for discovering the instance aspect handling area in the model by using the input and output data information of activity instances in events. The proposed two mining algorithms can make full use of current workflow mining algorithms and help to enhance their applicability in some sense. The experiment results show their effectiveness.更多还原