用于优化业务进程管理模型的方法和系统

摘要

本发明提供了用于优化业务进程管理模型的方法和系统，结合了混合整数规划和离散事件模拟。取决于包括多个控制参数的控制参数矢量，BPM与BPM模型和多个关键性能指标相关联。该方法包括：将控制参数分离为线性控制参数矢量(X)和非线性控制参数矢量(X′)，为控制参数矢量迭代地计算一组候选值，每个候选值都是根据与BPM模型、多个关键性能指标(KPI)、以及非线性控制参数(X′)的预选值相关联的混合整数规划(MIP)模型的执行，为非线性控制参数(X′)的预选值确定的，以及基于控制参数矢量的所述候选值中的至少一个，调整BPM模型。

说明书

技术领域

本发明一般涉及业务进程管理系统(BPM，Business Process  Management)，具体而言，涉及用于优化BPM模型的方法和系统。

背景技术

业务进程管理系统被用来组织和管理大量的信息。

业务进程管理(BPM)专注于使组织满足客户的需求。利用先进的 工作流技术，BPM从业务进程的方面对企业执行全方位的管理，并支持 业务进程的持久改进。它为企业内以及企业间的各种业务提供统一的建 模、执行和监测环境。BPM技术可使业务要求和IT系统之间的不匹配 降低，改进效率，并降低操作和开发成本。

业务进程是产生满足一定要求的服务或产品的相关的结构化活动的 集合。业务进程对于商业组织是关键的，因为它们产生收入并常常表示 成本的有效比例。

业务进程管理包含用于建模、开发、执行和管理一个组织的业务进 程的一组方法、技术和工具。BPM可使业务分析师创建业务进程模型， 然后，由IT工程师将该业务进程模型细化为可执行的模型。将可执行的 进程模型部署到进程引擎，该进程引擎通过将任务委派到资源(人和服 务)来执行进程。

基于关键性能指标(KPI，key performance indicator)来度量 BPM系统中的业务进程性能。关键性能指标(KPI)一般是由BPM设计 师来定义的。

BPM设计师专注于通过调节一定数量的控制参数，针对KPI来优化 BPM模型。

业务进程管理系统依赖于初始建模阶段，在该初始建模阶段，业务 分析师的职能被确定为描述业务进程的步骤、规则和KPI，并通过离散 事件模拟来估计预期的性能。

用于增强BPM系统的性能的当前解决方案提供有关KPI成绩的信 息。然而，当KPI需要被优化时，一般需要确定哪些控制参数需要在以 后由业务分析师进行调整。然而，KPI常常取决于多个度量，使得难以 标识次最优性的原因。

类似地，参与初始建模阶段的BPM(业务进程管理)建模者可能需 要查看改变控制参数的一些值的影响。当前，这些参数改变是手动执行 的，通过启动返回期望的KPI的离散事件模拟模型来实验这些改变的效 果。然而，此过程会非常长，并要求BPM专家的输入。给某些现有的 BPM工具提供了加快调节控制参数矢量的局部搜索机制。然而，局部搜 索引擎没有关于BPM网络的结构的知识：为了调节控制参数，此局部搜 索解决方案简单地获取来自模拟的关键性能指标结果，但忽略问题的结 构，这使得它十分慢。

因此，需要用于确定关于KPI的最佳控制参数值的改进的方法和系 统。

发明内容

根据本发明，提供了根据独立权利要求1的优化BPM模型的方法， 根据所附权利要求9的计算机程序，根据所附权利要求10的计算机可读 介质以及根据所附权利要求11的系统。在所附的从属权利要求中定义了 优选实施例。

本发明可以自动解决在BPM设计过程中出现的复杂的BPM参数优 化问题，而不要求人工测试、试验步骤。

根据本发明，使用混合整数规划(MIP，Mixed Integer  Programming)作为优化引擎，并使用离散事件模拟作为模拟引擎，可 使优化和模拟在同一个级别操作。使用模拟来验证和细化BPM系统的 MIP近似，并使用BPM问题的控制参数作为通信矢量。

本发明的另一个优点是，将能够通过混合整数规划建模的数据与无 法通过混合整数规划建模的数据分离，并反复使用该区别作为自动化局 部搜索的“部分”提示。本发明的再一个优点是将双方之间的通信减少到 只有控制参数。

本发明导致MIP和模拟之间的协作，该协作使得能够从MIP结果的 质量并从模拟时由局部搜索细化给出的精确度得到益处。

在阅读附图和详细描述之后，本发明的进一步的优点对于本领域的 技术人员来说将变得显而易见。此处旨在包括任何额外的优点。

附图说明

现在将通过示例，并参考各个附图，来描述本发明的各个实施例， 在各个附图中，类似的标号表示类似的元件，其中：

图1示出了一个框图，示出了其中可以使用本发明的示例性硬件体 系结构；

图2示出了根据本发明的某些实施例的BPM优化单元的高级视图；

图3示出了根据本发明的各个实施例的BPM优化单元的详细视图； 以及

图4示出了描述根据本发明的某些实施例的BPM优化步骤的流程 图。

附图旨在只描述本发明的典型实施例，因此，不应当被视为限制本 发明的范围。

具体实施方式

图1概要地示出了其中可以实现本发明的业务进程管理系统 (BPM)的示例性硬件体系结构100。

BPM体系结构100包括服务器101，该服务器101通过网络106，如广 域网(WAN)(如全球因特网)、私有WAN、局域网(LAN)、电信 网络或上述网络的任何组合，与一组客户端计算机102、103、104进行 交互。服务器101可被用户用来管理业务进程。

服务器101可包括业务进程管理(BPM)软件引擎，这些引擎向客 户端计算机102、103、104传递数据和/或用户功能。应该注意，虽然图 1只示出了一个服务器101和三个客户端计算机102、103、104，但是， 本发明的系统支持经由网络106连接的任意数量的服务器和客户端计算 机。

在各实施例中，BPM系统包括可通过网络访问的至少一个图形用户 界面(GUI)105，该界面使得用户能够查看业务进程的性能。

体系结构100还包括BPM优化单元15，用于优化由关键性能指标表 示的BPM性能准则。

BPM优化单元15可以包括被编译以产生执行本发明的各种功能的计 算机指令的计算机源代码、脚本语言代码或解释语言代码。

尽管BPM优化单元15被示出为与体系结构100的其他组件分离，但 是，本领域技术人员将容易理解，它也可以驻留在服务器101上或以分 布式方式驻留在服务器101和客户端计算机102、103、104上。在本发明 的一个实施例中，BPM优化单元15是客户端-服务器应用，该应用具有 驻留在客户端计算机102、103、104上的客户端部分和驻留在服务器101 上的服务器部分。

BPM服务器101包括进程模型生成工具11，该工具11可被进程分析 师用来生成进程模型111(在下文中也被称为BPM模型或业务进程模 型)，该模型描述业务进程的步骤、规则集和关键性能指标(KPI)。 业务进程模型可以使用诸如BPMN(业务进程建模符号)或XPDL (XML进程定义语言)的任何适当语言来定义。在BPM建模阶段，基 于诸如业务目标、进程性能度量的许多控制参数以及诸如服务质量 (QoS)度量的技术参数，来定义关键性能指标(KPI)和它们的目标 值。

由此所生成的进程模型描述了业务进程中的步骤的序列。该模型指 定负责执行每个步骤的软件系统或人类角色以及管理步骤执行的规则。 进程模型还能够指定在进程步骤中所要求的每个资源的成本和可用量、 每个步骤的预期处理持续时间、以及处理路径中的各种分叉处的分支 比。

在第二阶段，BPM服务器装配进程模型，以便使用从软件库12检索 的一组软件组件来实现它。可以从进程模型自动生成进程组件。

BPM服务器101还包括一组用于部署装配的进程模型的执行引擎 13。提供执行引擎13以自动化进程模型的执行。执行引擎13根据装配的 进程模型中所定义的步骤来路由工作的每个实例。执行引擎13进一步自 动化和管理建模的业务进程中所定义的BPM，同时确保处理符合预定义 的规则。

BPM优化单元15适于通过不仅使用优化技术而且还使用离散事件模 拟来计算KPI的最佳控制参数，来优化BPM进程(下面也被称为BPM模 型或BPM进程模型)。

图2是BPM优化单元15的高级视图。为了在与模拟的KPI存在偏差 的情况下或在进程执行阶段的上游计算优化控制参数，BPM优化单元15 使用描述业务进程的(装配的)进程模型110、构成将被优化的目标的 KPI参数或KPI矢量152的预定义的线性组合、以及构成控制参数矢量的 一组控制参数154。控制参数矢量和KPI集合是从被用户预定义为BPM 模型的一部分的参数中选择的。在预定义的控制参数和KPI中，某些是 在MIP模型中实现的(因此，将由MIP优化引擎处理)，而所有其他控 制参数和KPI将由局部搜索算法与模拟引擎一起处理。

BPM优化单元15适于根据进程模型110、KPI矢量152和控制参数矢 量154，来确定相对于KPI参数152提供最佳性能的最优控制参数矢量 200。

所确定的优化控制参数矢量200将被提供给执行引擎13，以执行或 再执行进程模型，使得KPI参数被满足。

图3概要地示出了根据本发明的各实施例的BPM优化单元15的结 构。

BPM优化单元15包括控制参数分离器301，该控制参数分离器301用 于将包括要被优化的一组控制参数的控制参数矢量154分离为线性控制 参数矢量X和非线性控制参数矢量X′。控制参数矢量154在下面将被指定 为矢量(X，X′)。

由控制参数分离器301提供的非线性控制参数矢量X′被传输到搜索 单元302，该搜索单元302执行局部搜索以查找非线性参数，并为非线性 控制参数X′反复地提供提示。

根据本发明的某些实施例，线性控制参数X将在混合整数规划 (MIP)模型中被捕获为常量，而非线性参数X′将被从MIP模型中排 除，而是将使用局部搜索机制被优化。由对于非线性控制参数X′的局部 搜索提供的非线性控制参数提示将被用作MIP模型中的常量。

混合整数规划是指用于解决各种实际优化问题的技术。一般而言， 混合整数规划(“MIP”)是以下列形式呈现的优化问题：

minimize f(x)

Subject to G(x)＝b

l＜＝x＜＝u

some or all xj integral，

其中，x是变量的矢量，l和u是界限的矢量，f(x)是目标表达式，而 G(x)＝b是一组约束表达式。

尽管上面的模型具有最小化目标，但是，本领域的技术人员将认识 到，模型可以具有最大化目标。

MIP模型的最简单的并且最广泛使用的形式是下列形式的混合整数 线性规划(MILP)：

minimize c＜T＞x

subject to Ax＝b

l＜＝x＜＝u

some or all xj integral，

其中，A是被称为约束矩阵的m x n矩阵，而c是线性目标矢量。 MILP是带有对某些或全部变量的完整性限制的线性规划(“LP”)。

可以使用混合整数规划形式的数学模型来表示业务进程管理问题。 数据模型通过资源、资源类别、进程步骤以及时间桶来索引。具体而 言，可以使用MIP规划方法来确定BPM模型和模拟业务进程中的资源分 配以生成资源分配建议，并将资源分配建议应用到未来的执行中以提供 最优环境。

本发明允许使用局部搜索将模拟与MIP结合，以为所有控制参数矢 量X′提供一个值。搜索单元302可以应用任何适当的局部搜索机制(例 如，爬山、禁忌或模拟退火法)，以反复地为非线性控制参数矢量X′确 定提示。根据本发明的各实施例，由搜索单元所提供的提示然后成为 MIP模型的常量，并能够通过分支限界法/分支切割法等等来求解。

线性控制参数矢量X与由搜索单元302计算的非线性参数的提示值一 起被提供该离散事件模拟单元303。

模拟单元303包括模型格式转换器304，用于将以第一格式接收的进 程模型110转换为第二格式。转换器304是这样的，它过滤接收到的进程 模型110的某些数据，以确保只有MIP模型生成和执行所需的信息被保 持在第二格式的进程模型中。在本发明的一个实施例中，进程模型110 的第一格式是BPMN格式，而第二格式的类型是“实体/关系”格式。根 据本发明的此实施例，由转换器304以一个或多个“实体-关系”表的形式 来转换进程模型110。

由转换器304转换的进程模型110被提供该MIP模型生成和执行单元 305(以下也被称为“MIP模型单元”)。

MIP模型单元305基于为非线性控制参数矢量X′确定的提示值、由 转换器304转换的进程模型110、以及KPI参数152，创建并执行MIP模 型。

MIP模型单元305可以通过捕获BPM参数调节问题的实质子部分， 根据任何适当的方案，如在US 2009/0228309中所描述的方案，生成MIP 模型。这样的方案优化了整体优化问题的实质子部分，然而实际上只解 决了控制参数的(MIP易处理的)子集、KPI的(MIP易处理的)子 集、以及BPM模型的(MIP易处理的)近似模型。它例如允许求解任何 资源评价问题以及任何某种资源分配问题。它允许以最少的成本、以固 定的资源来找到最大吞吐量，或对于目标吞吐量找到最便宜的资源使用 率。其他示例包括没有限制地找到用于最小化每项的成本的最佳配置。

MIP模型单元305运行如此生成的MIP模型，并计算MIP模型的最 优线性控制参数X的近似值X^＊。它进一步提供了KPI参数的近似值c^＊和 BPM输出值的近似值Y^＊。BPM输出值表示来自BPM模型的任何统计结 果，所述统计结果既不是控制参数，也不是KPI，但是对于BPM模型设 计师来说仍有某些兴趣。BPM输出值的一个示例可以是每个资源的空闲 时间，或者所有资源的平均空闲时间。

然后，由离散事件模拟模块306来测试X的线性控制参数矢量的结果 近似值X^＊。模拟器306根据由MIP模型执行单元305计算的最优线性控制 参数的近似值X^＊，来确定精确的KPI参数值″c#″(也被称为KPI的“目 标值”)和精确的BPM输出值″Y#″(也被称为BPM输出的“目标值”)。 术语“精确的”在这里用来指定由几乎完全捕获了BPM模型的复杂性的数 学模型计算的值。

然后，精确度比较器308使用由性能模拟器306获得的KPI参数的近 似值来评估模拟的精确度。精确度比较器308将由MIP模型执行单元305 提供的MIP解(c^＊，Y^＊)与性能模拟器306的输出(c#，Y#)进行比较。

如果精确度比较器308确定MIP解(c^＊，Y^＊)相对于精确值(c#，Y#)的精 确度不令人满意(由用户提供绝对或相对距离上限)，则将控制参数的 近似值X^＊传输到细化单元310，该细化单元310通过使用局部搜索机制来 细化最优控制参数的近似值X^＊。当满足停止条件时(诸如与精确度或迭 代次数有关的条件)，结束细化阶段。

如果精确度比较器308确定MIP解(c^＊，Y^＊)相对于值(c#，Y#)的精确度 令人满意，则对于(由搜索单元302提供的)非线性控制参数X′的相邻 值重复该过程，直到检测到停止条件。

从而，本发明通过对于一组控制参数以及对于适当的KPI(MIP易 处理的KPI的子集)，以混合整数规划模型来建模进程模型基础结构的 一部分，并使用MIP问题求解算法(例如，单纯形算法、分支切割法、 分支限界法)来解决该子问题，显著地加快了局部搜索进程。根据本发 明的各实施例的BPM优化方案在模拟和MIP模型之间提供了结合机制， 以便提供相对于KPI的优化的控制参数。

BPM优化单元15通过生成捕获了由线性控制参数X表示的BPM参数 调节问题的实质子部分的MIP模型，自动地优化与KPI参数相关联的控 制参数。然而，对于由非线性参数X′表示的、太复杂或不适合用混合整 数规划模型来建模的BPM参数调节问题的次要部分，使用局部搜索机 制。然后，BPM优化单元15组合这两个部分以提供优化的控制参数矢量 200。

因此，通过将MIP问题优化与被用作局部搜索的评估函数的离散事 件模拟结合(这两者都不能有效而完全地捕获)，可以优化BPM设计的 性能。通过只交换选定的控制参数值来实现双方的协作。

尽管本发明不限于任何控制参数矢量和KPI矢量，当控制参数和 KPI具有在预定义的MIP间的有效子集时，本发明具有某些优点。

图4是根据本发明的某些实施例的用于计算涉及KPI的最优控制参 数的流程图。

在步骤400中，接收与进程模型相关联的控制参数矢量，而在步骤 402中，将控制参数矢量分离成线性参数X和非线性参数X′。

优化KPI控制参数的方法可以用公式表示为：

(X，X′)/max c/(c，Y)＝f(X，X′)

在A(X′).X＜B(X′)约束下

其中：

-f表示包括离散事件模拟的评估函数；

-X表示线性控制参数(或变量)，

-X′表示非线性控制参数，

-Y表示BPM输出变量，

-c表示KPI目标矢量；在本发明的优选实施例中，它包括KPI的有 序有限集，这允许判断解是否令人满意(例如，比另一个更好、相当或 更差)，以及

-A和B是线性(MIP)矩阵和矢量，X′的函数，表示对X的已知 MIP约束。

评估函数f将被局部搜索法用来评估由控制参数提供的解。根据本 发明的各实施例，通过模拟BPM模型并观察KPI结果来实施评估函数。

非线性控制参数X′将由局部搜索机制处理(由框41所表示)，以确 定非线性控制参数矢量X′的提示，其将被优化/模拟分支45使用。

更具体而言，在局部搜索分支41的步骤404中，迭代地应用任何适 当的局部搜索机制(诸如爬山、禁忌或模拟退火)，以为非线性控制参 数X′提供一个或多个值，诸如，例如，第一提示X′0。非线性控制参数 X′的所选值对于MIP模型将成为常量，使得它们能够被求解(例如，通 过分支限界/分支切割法)。

在步骤406中，将进程模型从第一格式(例如，BPMN格式)转换 成第二格式(例如，实体-关系格式)。

在步骤407中，基于第一提示X′0、线性控制参数X、业务进程模型 110以及KPI矢量152，生成MIP模型。

在步骤408中，执行MIP模型以确定最优控制参数的近似值X^＊、 KPI矢量的近似值c^＊、以及业务进程输出的近似值Y^＊。MIP近似值是根 据下列问题公式来确定的：

max c＝G(X′).(X，Y)

L(X′).(X，Y)＜E(X′)

A(X′)X＜B(X′)

其中，G是f的线性近似，而L和E表示线性(MIP)矩阵和矢量， X′的函数，表示BPM系统，带有额外的内部变量矢量Y(输入和输出变 量之间的链接的线性近似)。

在步骤410中，通过模拟f(X^＊，X′)来测试为X确定的结果近似值X^＊。 在此阶段，使用X^＊作为解决优化问题中的线性控制参数X的提示，并且 模拟提供KPI值c#(下面被称为“精确KPI值”)和BPM输出值Y#(下面 被称为“精确BPM输出值”)。

在步骤412中，通过比较KPI和BPM系统变量的近似值(x^＊，Y^＊)与它 们的精确值(c#，Y#)＝f(X，X′)来计算模拟的精确度。在此步骤中，可以 基于(c#，Y#)和(c^＊，Y^＊)来确定精确度指标PR，然后将其与阈值(P-容差) 进行比较。此精确度条件表达了不能预期模拟的结果与MIP优化的结果 完全相等。高达用户定义的某个百分比或高达用户定义的某个最大绝对 松弛(slack)的近似相等性可能是令人满意的。性能指标PR具体而言 被确定为等于：

PR＝|(c#，Y#)-(c^＊，Y^＊)|/|(c#，Y#)|

如果精确度令人满意(PR＞P-容差)，如果不满足停止条件，则 重复局部搜索机制(分支41)，以为非线性参数X′提供下一值。

分支41的局部搜索机制为非线性参数矢量X′提供新提示。在步骤 415中，计算矢量X′的邻域。在步骤416中，判断是否满足预定义的停止 条件，诸如涉及精确度的条件、涉及局部搜索迭代的数量的条件(利用 计数器跟踪的)或涉及KPI的条件。如果满足了停止条件，则在步骤 417中结束循环。如果不满足停止条件，则步骤404选择X′的近邻值 X′next作为X′的下一值，并使用此值作为确定MIP模型的常量。利用新 的值X′next重复步骤406到414。

然后，比较为每一个提示X′找到的不同近似值X^＊，以便只保留最佳 解。

如果在步骤414中确定精确度不令人满意(PR＜P-容差)，则由使 用局部搜索机制的细化分支45来细化控制参数的近似值X^＊本身。细化分 支45的局部搜索机制可以与局部搜索分支41中使用的相同，或者使用另 一种。

细化分支45应用局部搜索机制来细化线性控制参数的近似值X^＊。

在步骤418中，计算矢量X^＊的邻域，并选择X^＊的近邻值Xnext作为 X^＊的下一值。在步骤419中，使用X^＊的近邻值Xnext来重新计算模拟值 (c#，Y#)＝f(X，X′)。在步骤420中，确定是否满足了预定义的停止条件， 诸如涉及精确度的条件、涉及局部搜索迭代的数量的条件(利用计数器 跟踪的)或涉及KPI的条件(例如，检测KPI的递增)。如果满足了停 止条件，则通过迭代局部搜索分支41的步骤415和416来确定新提示。如 果不满足停止条件，则重复步骤418和419。

在步骤416和420中与相应的局部搜索机制相关地使用的停止条件被 定义成检测到增强减慢。在步骤420中依据KPI的矢量计算出的优化目 标c的示例性停止条件可以包括确定当前最优解是否没有被增强超过x％ (例如，0.1％到1％)，如果满足了此条件，则停止所考虑的进程。这 种相对增强阈值“x％”可以被替换为绝对增强阈值。

本领域技术人员将容易理解，与步骤416和420的局部搜索机制相关 地使用的术语“近邻”或“邻域”在这里被用来指定根据任何适当的准则与 给定解(或给定值)“靠近”的解(或值)。例如，可以基于距离准则来 确定给定解的邻域。例如，给定解的近邻可以被定义为包括预定义的距 离内的解或值。距离可以是满足三角不等式的度量，例如，笛卡儿距离 (两个矢量的元素之间的松弛的平方和的平方根)、曼哈顿距离(两个 矢量之间的松弛的绝对值的和)等等。

前面的内容只是对本发明的原理的说明。此外，由于本领域技术人 员可以容易地想到很多修改和变化，因此，不希望将本发明限于所显示 和描述的准确的结构和操作，因此，可以采用本发明的范围内的所有适 当修改和等效方法。具体而言，本发明不限于供细化单元和搜索单元使 用的局部搜索机制。此外，本发明可应用于任何控制参数或KPI目标的 集合。本发明不限于上文对于本发明的某些实施例所描述的应用；取决 于其中提供捕获系统的有效部分的MIP模型的控制参数，它也应用于涉 及KPI的任何应用。

通过将MIP优化组件与局部搜索机制结合，本发明可以更快地调节 BPM模型，消除了手动迭代的必要性。从而，本发明实现了操作研究技 术(局部搜索、混合整数规划)与离散事件模拟技术的结合，而这样的 结合在现有技术中被认为是不兼容的。根据本发明的各实施例，BPM模 型被MIP模型“近似地”捕获，并被模拟模型“精确地”捕获。

本发明可以呈现完全是硬件实施方式、完全是软件实施方式或包含 硬件和软件元件两者的实施方式的形式。在优选实施例中，本发明是以 软件实现的，包括但不限于固件、常驻软件、微代码等等。

此外，本发明还可以呈现计算机程序产品的形式，该产品可以从计 算机可用的或计算机可读的介质进行访问，其提供了程序代码，供计算 机或任何指令执行系统使用或与它们结合使用。对于此说明书，计算机 可用的或计算机可读的介质可以是能够包含、存储、传递、传播或传输 供指令执行系统、设备或装置使用或与它们结合使用的程序的任何设 备。

介质可以是电子的、磁性的、光学的、电磁的、红外线的或半导体 系统(设备或器件)或传播介质。计算机可读介质的示例包括半导体或 固态存储器、磁带、可移动计算机磁盘、随机存取存储器(RAM)、只读 存储器(ROM)、硬磁盘和光盘。光盘的当前示例包括光盘-只读存储器 (CD-ROM)、光盘读取/写入(CD-R/W)以及DVD。

适用于存储和/或执行程序代码的数据处理系统将包括通过系统总 线直接或间接地耦接到存储器元件的至少一个处理器。存储器元件可以 包括在程序代码的实际执行过程中使用的本地存储器、大容量存储器以 及高速缓冲存储器，其提供了至少某些程序代码的临时存储器，以便减 少在执行过程中必须从大容量存储器检索代码的次数。

输入/输出或I/O设备(包括但不限于键盘、显示器、指示设备等 等)可以直接或者通过I/O控制器耦接到系统。