王 静， 刘 冰， 李 辉， 王 涛＊

（1.长春工业大学计算机科学与工程学院，吉林长春 130012；2.吉林省塑料研究院，吉林长春 130022）

基于约束满足的ERP测试计划方法

王 静1， 刘 冰1， 李 辉2， 王 涛1＊

（1.长春工业大学计算机科学与工程学院，吉林长春 130012；2.吉林省塑料研究院，吉林长春 130022）

将约束编程与ERP产品自身特点相结合，提出了一种基于约束满足的ERP测试计划方法。通过对某饲料行业ERP中记账凭证软件进行约束建模。该测试计划方法已经应用于饲料行业ERP平台中。

约束满足；ERP；测试计划；约束建模

0 引 言

企业资源计划（Enterprise Resource Planning，ERP）以其信息化管理方式改进企业的业务流程、完善供需链、提高企业经济效益，虽然目前ERP在我国的应用并不成熟，但是这种信息化的管理方式具有充分的发展空间。对于ERP产品，其持续有效存活取决于产品的质量，因此产品的测试工作尤为重要。据统计，在一个软件产品开发过程中，软件测试工作所占比重大致为软件开发总工作量的40%［1］。ERP具有开发周期长、流程化的特点，目前，ERP测试计划的制定多以经验为指导，只是根据产品模块以及测试人员的时间等因素主观进行测试资源分配，文献［1］给出一种软件测试计划方法，一定程度上提高了测试的效率，但对ERP产品而言并不完全适合。ERP具有模块联系紧密的特性，对业务操作流程不熟悉的测试人员而言，测试结果可能并不尽人意，遗留bug过多必然影响产品的正常实施［1］。因此对于ERP的测试，一般需要具有符合产品特点的实施测试的计划和方法，对测试的模块、内容、分配的测试人员等方面进行详细描述，制定合理的测试资源分配方法是十分必要的。

约束程序（Constraint Programming，CP）是人工智能领域一个重要的研究分支，其在描述约束满足问题方面取得了很多成熟的研究结果，软件测试的分配方法类似于约束满足问题中的一类调度问题，因此，文中将ERP测试计划问题转化为约束满足问题（Constraint Satisfaction Problem，CSP）进行求解，具有一定的可行性与合理性。基于此，文中提出了一种基于约束满足的ERP测试计划方法，对某饲料行业ERP中记账凭证软件约束建模，测试验证了文中方法的有效性，目前，该测试方法已经应用于饲料行业ERP平台并取得较好效果。这对于指导ERP产品的测试工作具有很重要的现实意义［2－3］。

1 测试模块的选取

软件测试是软件质量保证的重要手段，研究表明：软件产品开发费用和软件质量与软件产品中存在问题发现时间早晚有直接关系。尽早发现产品中的问题，后期维护费用也相应会减少。目前软件测试的工作主要放在测试技术上，对软件测试过程关注很少，软件测试过程对软件的有效性及软件质量具有很好的衡量作用，因此，软件测试过程的改进具有重要的现实意义。CMMI是针对软件过程改进提出的，软件产品测试为软件过程的一部分，因此，CMMI模型对于软件产品测试具有一定的指导意义。度量由CMMI提供，主要是为了获取过程的表征数据［45］。ERP对企业的采购、生产、销售进行统一整合，每部分功能关联紧密。软件产品的测试人员并不一定是参与开发的人员，对产品的代码结构并不一定熟悉，因此，选取功能点数作为产品规模的度量元。

ERP产品中功能点数根据需求计划书确定。最终功能点数Nnm即为测试模块的个数。功能点之间存在相互制约和无约束两种关系。存在制约关系的功能点记为：mi∧mj（i，j＜Nnm）；无约束关系记为：mx∨my（x，y＜Num）。子测试模块集Mn包括多个测试模块，至此得到测试模块M：

由上式可得测试模块及模块间关系。

2 ERP测试方法CP建模

2.1 约束满足问题

约束满足问题是由一组预先定义的变量、变量的值域和变量间的约束关系组成，对约束满足问题的求解意味着在满足所有约束条件下对每个变量指派一个合法的域值。其形式化为：问题P是一个三元组P＝（X，D，C）。其中，X＝｛x1，x2，…，xn｝是CSP中的变量集合；D＝｛D1，D2，…，Dn｝是论域的集合，其中，Di∈D对应xi∈X，是变量xi的有限值域；C＝｛c1，c2，…，ck｝是一个有限约束集合，其中，任意cj∈C表示变量取值之间的制约关系［6］。其解为每个变量赋其论域上的一个值，使之同时满足所有的约束［7－10］。

约束程序综合了运筹学和人工智能的知识，可以用来求解组合优化问题。约束指一个包含若干变量的关系表达式，用以表示这些变量必须满足的条件［11－12］。求解CSP的基本思想是定义问题领域的变量，每个变量预先设置各自的值域，通过描述各变量之间的约束，寻找满足全局所有约束的一个或多个解［13－16］。ERP测试计划方法问题涉及到测试模块的测试时间、测试人员对测试工作的能力值、测试人员对模块的熟悉程度、测试模块并发之间的平衡，具有NP-难的复杂性。

2.2 CP建模

2.2.1.ERP程序的变量描述

根据饲料行业ERP记账凭证模块测试的实际情况，确定测试分配方法中的变量如下：

1）测试工作开始时间：Ts。

2）测试模块交付时间：Te。

3）测试模块集合：M。

4）每个测试模块在理想状态下的测试工时：W＝｛w1，w2，…，wi｝。

5）测试人员集合：P＝｛p1，p2，…，pz｝。

6）测试人员P对测试中关注项T＝｛t1，t2，…，tk｝的能力值Q＝｛q1，q2，…，qz｝。

7）测试人员P对测试模块mi熟悉程度：Fzi。

下面对上述变量进行化简。每个测试模块mi的测试开始时间Tsi有两种情况：

1）整个测试工作的开始时间Ts即为模块测试的开始时间Tsi＝Ts；

2）根据前置测试模块的测试结束时间Te

i－1确定Tsi。每个测试模块的测试工时并不确定，工时的长短取决于测试人员对该测试模块的熟悉程度Fzi，以及测试人员的个人能力值T。

根据饲料行业ERP实际情况，测试人员对测试主要关注项T的能力值见表1（完全熟悉记作1.0；本测试团队人员为5）。

表1 测试人员对测试过程主要关注项能力值

测试人员P的测试能力值用对各关注项T的加权平均表示。

测试工时W是指测试人员能力值以及测试人员对测试模块的熟悉程度均为1.0时的测试用时。根据表1以及测试人员pz对测试模块的熟悉程度Fzi按照公式wi／（qz×Fzi）可以得到测试人员P对每个测试模块M进行测试的工时，记为Wzi。

至此，变量3），5），6）化简为测试人员对每个测试模块的测试工时：Wzi。

2.2.2.ERP程序的约束描述

测试模块时间顺序约束。模块测试开始时间Tsi应该等于或晚于整个模块测试开始时间Ts，记作：Tsi≤Ts；测试模块的结束时间Tei应该早于或等于模块交付时间Te，记作：Te≤Tei；测试模块mj应该在测试模块mi测试结束之后进行测试，即满足：Tsi＞Tsj∧Tei＞Tsj，其中i，j为模块集个数。

测试模块间并发约束。测试中的部分测试模块的测试是可以同时进行的。用M′＝｛m′1，m′2，…，m′i｝表示，其中M′模块的个数大于等于2，并发模块M′是依据测试过程不断变化的。

个人能力约束。测试模块人员分配应根据测试人员测试关注项的能力值和测试人员对测试模块的熟悉程度确定。

同一时刻、同一测试模块只能由一位测试人员进行测试。

3 模型求解算法

3.1 约束传播

约束传播技术是通过在搜索过程中不断缩小搜索空间来简化问题的求解难度［17］。该案例ERP凭证部分的测试方法通过使用约束传播技术，可以及时、有效地去除部分无用值，进而简化求解过程。

3.2 回溯

当某变量被赋值后，则进行约束传播，此时约束传播的值域缩减，这就使得未赋值集合中某些变量的值域为空，这就说明此时的赋值并没有可行解［18－20］。这个时候需采用回溯方法取得可行解。

在变量的集合和约束已知的前提下，CSP技术可以找到满足所有约束的合理的解集。文献［1］根据需求树确定测试模块集，文中的测试模块则是根据功能点确定，这更符合ERP产品的行业特色。对模型求解算法如下：

输入部分根据测试人员对测试模块的熟悉程度和测试人员对测试关注项的能力值，得到测试人员对各测试模块的测试工时；输入模块中包含由式（1）得到的测试模块及关系。

算法开始，若测试模块中包含未测试的模块mi，则对其分配测试人员。若mi包含在并发测试模块中，则对其进行并发处理。为当前模块mi分配测试人员后需要进行约束传播，若发生冲突，则进行回溯操作，直至找到可行解并输出。

3.3 并发测试模块

并发问题在测试工作中比较常见［20］，本ERP凭证部分的测试显然存在并发问题。测试开始时，对于手工填制凭证、采购转凭证、生产转凭证、销售转凭证是可以同时发生的，对于并发测试模块集的处理如下。

选取并发测试模块中理想状态下测试工时最大的子测试模块Max（W），在测试人员中选取对当前测试模块测试工时最小Min（Wzi）的测试人员，若该测试人员资源被占用，则回溯。若没有未分配任务的测试人员，则未分配测试人员的测试模块处于等待状态，等待最近一次结束的测试人员，其它模块则开始测试，此时测试过程转化为顺序执行测试。

4 模型求解方法示例与分析

对于ERP系统而言，财务是整个系统的核心，企业的采购、生产、库存状况最终都将体现在财务系统，财务数据的准确性可直观地体现企业的经济效益，因此，财务系统成为企业人员最为关心的部分，对于测试人员而言，在业务流程稳定的前提下，测试的重点理应放在财务系统上。因此，这里选取饲料行业ERP财务系统的核心记账凭证模块进行测试。该财务模块分为两部分：手工填制的凭证和业务数据的转凭证。手工填制凭证主要对凭证中各部分内容进行填制、对凭证进行审核签字、凭证的打印设置、打印及删除功能；业务数据的转凭证主要是将业务部分的采购单、生产单、销售单转为记账凭证，根据需求，这里的转凭证是一单一转，因此，对于这三大部分的转凭证应分为3个模块，而每部分所转的记账凭证也具有审核签字、打印设置、打印以及删除功能。至此得到测试模块集M：

饲料行业ERP有测试人员5人，模块测试标准工时为48h，测试人员对测试模块的熟悉程度Fzi见表2。

表2 测试人员对测试模块熟悉度

每个测试模块的标准测试工时W见表3。

表3 每个测试模块的标准测试工时 W／h

由表1～表3可得测试人员对每个测试模块的工时，见表4。

表4 测试人员对测试模块的工时 W／h

如此得到一个可行解，如图1所示。

图1 基于约束满足的测试分配方法图

图中，横坐标表示测试时间，纵坐标表示测试模块。由图1可知，记账凭证部分测试完成为22h。

较之基于经验的测试分配方法，文中提出的方法不仅缩短了完成工期，而且测试更全面。测试人员基于经验的测试方法和文中测试方法在时间和测试全面性（bug数目为依据）的对比情况分别如图2和图3所示。

图2 测试人员测试用时对比图

图3 测试人员测试全面性对比图

每个测试人员的测试工时缩短的同时，测试更具全面性、科学性，这就降低了模块中出现异常的可能性，为整个产品的交付提供了保障。

5 结 语

根据ERP本身测试的特点，将测试方法问题模为约束求解问题，并提出了一种全新的基于束满足的测试方法。将该方法应用于饲料行业P记账凭证模块的测试方法取得了较好的效。目前，有很多不同类型、不同性质的软件产，由于不同软件产品对软件测试所关注点以及试人员能力值差异等问题，约束集合的确定还要根据具体情况而定，这就需要进一步对约束足问题进行研究，根据自身特点构造出合适的件测试方法。

［1］李悦，李娟，陈伟.基于约束满足的测试计划方法［J］.计算机工程与设计，2008（3）：535-539.

［2］柏淑琴.高校排课问题的约束满足优化模型与算法［J］.科技视界，2012（18）：39-42.

［3］Freuder E C，Mackworth A K.Constraint Satisfaction：An Emerging Paradigm.RossiF，van Beek P，Walsh T，eds.Handbook of Constraint Programming［C］／／Amsterdam：Elservier，2006：13-28.

［4］李宏博，李占山，王涛.改进求解约束满足问题粗粒度弧相容算法［J］.软件学报，2012，23（7）：1816-1823.

［5］Minton S，Johnston M D，Laird P.Minimal conflicts：A heuristic repair method for constraint satisfaction and scheduling problems［J］.Artificial Intelligence，1992，58（1）：161-206.

［6］Bessière C，Cardon S，Debruyne R，et al.Efficient algorithms for singleton arc consistency［J］.Constraints，2011，16（1）：25-50.

［7］Bessière C.Constraint Propagation.Rossi F，van Beek P，Walsh T，eds.Handbook of Constraint Programming［C］／／Amsterdam：Elservier，2006：29-84.

［8］Freuder E C，Mackworth A K.Constraint Satisfaction：An Emerging Paradigm［C］／／Rossi F，van Beek P，Walsh T，eds.Handbook of Constraint Programming.Amsterdam：Elservier，2006：13-28.

［9］Bessière C，Regin J C，Yap RHC，et al.An optimal coarse-grained arc consistency algorithm［J］.Artificial Intelligence，2005，165（2）：165-185.

［10］Jones C.Software assessments，benchmarks，and best practices［M］.Beijing：China Machine Press，2003.

［11］Ivar Jacobsen，Grady Booch，James Rumbaugh.The unified software development process［M］.Beijing：China Machine Press，2002.

［12］James Rumbaugh，Ivar Jacobsen，Grady Booch.The unified modeling language reference manual［M］.USA：Addison Wesley Longman Inc，1999.

［13］Lecoutre C，Boussemart F，Hemery F.Exploiting multidirectionality in coarse-grained arc consistency algorithms［C］／／In：Proc.of the CP 2003.Kinsale，2003.

［14］Mehta D，Van Dongen MRC.Reducing checks and revisions in coarse-grained MAC algorithms［C］／／In：Proc.of the IJCAI，2005.

［15］Wallace R J，Freuder E C.Ordering heuristics for arc consistency algorithms［C］／／In：Proc.of the 9th Canadian Conf.on Artificial Intelligence.Vancouver，1992.

［16］Van Dongen M R C.Saving support checks does not always save time［J］.Artificial Intelligence Review，2004，21（3／4）：125-132.

［17］Li Z S，Li H B，Zhang Y G，et al.An approach of solving constraint satisfaction problem based on cycle-cut［J］.Chinese Journal of Computers，2011，34（8）：235-242.

［18］Boussemart F，Hemery F，Lecoutre C，et al.Boosting systematic search by weighting constraints［C］／／In：Proc.of the 16th European Conf.on Artificial Intelligence.Valencia，2004.

［19］Smith B M，Dyer M E.Locating the phase transition in binary constraint satisfaction problems［J］.Artificial Intelligence，1996，81（1）：565-582.

［20］SEI Software.Engineering measurement and analysis［EB／OL］.http：／／www.sei.cmu.edu／sema／welcome.html，2001.

Constraint-satisfaction based method for ERP test plan

WANG Jing1， LIU Bing1， LI Hui2， WANG Tao1＊
（1.School of Computer Science ＆Engineering，Changchun University of Technology，Changchun 130012，China；2.Jili Province Plastics Research Institute，Changchun 130022，China）

Combing the constraint programming with the characteristics of the ERP products，we put forward a ERP test plan based on constraint-satisfaction.The mathematical model of the vouchers in ERP of a feed industry is established.The test plan has be applied in the ERP platform of the feed industry.

constraint satisfaction；Enterprise Resource Planning（ERP）；test plan；constraint modeling.

N 39

A

1674-1374（2014）01-0071-06

2013-05-21

吉林省科技厅重点项目（20110361）

王 静（1987－），女，汉族，山东莱芜人，长春工业大学硕士研究生，主要从事约束求解方向研究，E-mail：wj1grace＠163.com.＊通讯作者：王 涛（1969－），女，汉族，吉林长春人，长春工业大学副教授，硕士，主要从事约束求解方向研究，E-mail：wangtao＠mail.ccut.edu.cn.