软件项目支付进度问题研究

曹 萍, 张 剑, 陈福集

(1.福州大学 经济与管理学院,福建 福州 350116; 2.上海工程技术大学 航空学院,上海 201620)



软件项目支付进度问题研究

曹 萍1, 张 剑2, 陈福集1

(1.福州大学 经济与管理学院,福建 福州 350116; 2.上海工程技术大学 航空学院,上海 201620)

软件项目的复杂性和特点使得其支付进度问题较具特殊性。针对软件质量的差异性，对软件项目支付进度问题进行研究。以承包商净现值最大化为优化目标，构建了具有惩罚结构的支付进度优化模型，该模型反映了不同软件质量对承包商收益的影响；针对该问题的特点设计了启发式求解算法；最后通过一个算例对模型进行了验证。可为承包商在签订外包合同及外包实施中的策略提供决策依据。

软件项目；支付进度安排；优化模型；启发式算法；软件承包商

0 引言

软件外包项目实施过程中外包双方均面对各种决策，收益最大化是决策的重要依据和目标。Kweku-Muata等认为外包合同是外包决策的重要组成部分[1]。外包合同中支付进度的安排直接影响到外包双方的收益，因此支付进度问题(payment scheduling problems，PSP)成为承包商和客户所共同关注的一个关键性决策问题[2]。支付进度研究如何合理安排项目的支付进度，包括支付次数、支付量及支付时间以使项目的收益最大化[3]。

在传统工程项目领域，支付进度问题研究已取得了一些基本成果。如Dayanand和Padman研究了在项目时间和支付总数固定的情况下，以承包商的净现金流量(Net Present Value，NPV)最大为目标分析了支付进度问题[4]；后又从客户的角度研究了支付进度问题，根据实际的支付规则构建了支付进度的混合整数规划模型，确定出使客户NPV最大化的支付进度安排[5]；Ulusoy和Cebelli从双方联合角度研究了平等的项目支付进度问题，指出承包商和客户的理想解分别是在项目开始和结束时一次性付清[6]。何正文等研究了具有多种执行模式的项目支付进度安排问题，认为业主和承包商对支付进度安排的偏好差异明显[7]。这些研究均针对传统工程项目领域，由于软件项目的特殊性和相对复杂性，现有研究成果并不适用于软件项目领域。而目前文献中尚未见有关软件项目领域的支付进度问题的研究。软件项目与传统的工程项目相比较为复杂，具有许多工程项目不具备的特性，如交付的软件质量的差异性等，具体支付规则亦不完全同于传统工程项目。因此，软件外包项目支付进度问题的研究，无论在理论和实践上都具有重要意义。

在软件项目外包的实践中，为了约束承包商使其保持较高的表现水平，按照软件质量等级规定对承包商设置惩罚措施是一种经常被客户采用的做法[8]。Kweku-Muata和Ojelanki认为信息系统(IS)的质量等级与承包商的表现水平有关，可由承包商的努力程度决定[1]。本文对存在质量差异情况下的软件项目支付进度问题(Software Project Payment Scheduling Problem , SPPSP)进行研究。首先对问题进行了界定，然后从承包商的角度构建该问题的基本数学模型；奖励惩罚结构对双方收益的影响以及如何对该种结构进行评价；针对该问题的特点设计相应的启发式算法；最后，通过一个算例对研究成果进行说明。

1 基本假设及符号定义

软件外包项目中客户对承包商的付款通常为里程碑支付，即在里程碑开始或结束时刻进行支付。如可在以下里程碑处进行支付：项目执行初期、系统分析与设计阶段、系统的构建与测试阶段、系统验收后等。

1.1 基本假设

假设1 软件项目活动的工期和费用是确定的；

假设2 软件项目的费用按一定比例在其开始和结束节点之间进行分配；

假设3 在项目交付时，按照事先约定的标准对软件项目的质量进行评估，确定其质量等级，对于质量等级存在惩罚结构；

假设4 客户的收益与软件质量等级有关，客户为避免收益下降，预留一部分合同款用于项目评价结束后支付，通常根据软件质量等级进行扣除相应数额后支付；

假设5 软件质量等级由承包商的表现水平决定，不同的表现水平下承包商花费的费用和时间存在差异；

假设6 客户在里程碑事件发生时对承包商进行支付，在每一个里程碑事件完成后支付一部分工程款。

1.2 符号定义

为将现金流与事件相联系，可将软件项目的实施过程用AOA(Activity-on-Arc)网络图来描述，假设一个软件项目有N个活动，M个事件，F个里程碑，里程碑事件的集合描述为：mf={m1,…,mF}，文中用到的符号定义如下：

NPVprovider为承包商现金流净现值；α为现金折现率；ESm为事件m发生的最早开始时间；LSm为事件m发生的最晚开始时间；dij为项目活动(i,j)的持续时间；Ct为软件项目在第t期的支出；Pk为第k次支付的支付量;Pq为若未达到质量等级的罚款;Cm为完成事件m需要的费用;ymt为事件m在时期t发生的0-1变量;xm为事件m处发生支付;Q为质量等级Q={q，q=1,2,…H};T*为事件发生时间的集合;T*={t,ymt=1;m=1,2,…,M};P*为支付量集合P*={pk；k=1,2,…,M};∏*为支付进度，∏*={T*，P*，Q*}。

2 SQ-PPSP优化模型的构建

合同总价款U分为两部分，U=UA+UB，UA为支付款总额，UB为预留罚款部分，可设UB=ξU，通常在项目结束时依据评估结果进行支付。ξ称作预留罚款比例系数，由双方签订合同时商定。假设t时期后的收益折现到项目开始时的收益为exp(-αt)≈(1+α)-t，承包商累积发生费用被支付的比例为β，k为支付变量，从承包商的角度建立SQ-PPSP优化模型：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

目标函数式(1)为承包商现金流的净现值最大化；约束条件式(2) 保证事件m在其时间窗[Em,Lm]内发生；式(3)表示支付次数为K次，即在项目开始和里程碑事件处分别进行一次支付；式(4)为活动(v,w)的开始和结束事件的优先关系约束。式(5)为支付量约束，在时期T内支付总量不超过承包商累积发生费用的一个比例β；式(6)保证全部支付的总和对于项目合同中的支付款总额。

项目交付时专家组对软件项目质量会进行评价，假设在软件项目开发中承包商的努力水平与软件质量成正比，不同的努力水平下承包商所需成本不同，软件质量不同，客户的收益也不同。当客户和承包商的偏好存在差异时，为激励承包商提高表现水平，客户常对承包商设置奖惩结构。当存在奖惩结构时，承包商的最终收益依赖于软件项目的质量等级。承包商的最终收益可表示为：

maxNPVprovider=NPVprovider+pqexp(-αt)yMtq=1,2,…,H

(8)

其中：pq表示与评价等级有关的付款，可表示为：pq=Uβ-γ(B1-Bq)U。

B1为客户预期的收益，即质量评价等级为最好时客户的收益，在这种情况下，承包商的表现水平满足预期要求，客户按照预定的合同价格向承包商支付剩余的全部款项。一般而言，承包商的努力程度是私人信息，客户无法对承包商的表现水平进行评价，只有对软件产品的质量进行评价从而决定对承包商的奖惩。项目完成时若评价级别低于预期结果，即q>1，则项目完成时客户在向承包商支付时扣除罚款。罚款为客户预期收益与实际收益之差的一个比例，即γ(B1-Bq)，γ为惩罚系数。

3 求解SQ-PPSP问题的算法设计

PPSP问题已经证明属于NP-hard问题，而SQ-PPSP求解比PPSP更为复杂，它不仅要考虑质量等级不同造成的成本、时间的不同，同时还要确定活动的开始时间。在文献[8]的基础上，结合SQ-PPSP的特点，开发了针对软件项目进度支付的启发式模拟退火算法。每个等级的项目支付进度优化流程图如图1所示。

图1 项目支付进度优化流程图

事件发生时间的选择机理如下：首先在项目的事件序列中选择ESm作为事件发生集合的初始值，之后从ESm≠LSm的随机中地挑出一个事件，将该事件的发生时间在其时间窗内随机地变动一个时间单位，检查该事件与其前后事件的优先关系约束，如违反，则调整发生时间直至满足优先关系约束为止，所有事件的新发生时间构成了一个新的事件发生时间集合。图中的ε是一个较小的正数。图1描述的是每一个等级下的项目支付进度优化的流程图，为求出所有等级中最优的支付进度，可增加一个外循环，将相同条件下所有不同等级的支付进度进行比较，找出其中最优的支付进度。具体步骤如下：

步骤1 确定初始解T0，在不违反优先关系约束的前提下，为每个事件在其时间窗内随机地安排一个实现时间，得到一个事件实现时间向量T，如果T中结束事件M的实现时间不晚于项目截止日期D1，则接受T为一个可行的初始事件实现时间向量T0，反之重复该步操作，直至得到一个可行的T0为止。计算P0和项目收益NPV0；

步骤2 初始温度t=Temp0，终止温度Tempf，冷却速率μ(0<μ<1)，搜索精度ξ,Markov链长度L，可令L=10*N(N为项目的活动数)；

步骤3 生成一个临点T1，从除开始事件之外的其余事件中随机地选择一个事件，在其时间窗内将该事件的实现时间随机地变动一个单位，并确保网络优先关系约束能够得到满足。检查结束事件的实现时间是否超过项目截止日期，如果没有超过则得到当前T0的一个可行邻点T1，反之，重复该算子操作直至获得一个可行的T1为止。计算在T1下的NPV1；

步骤4 若ΔNPV=NPV1-NPV0>0，则该临点成为当前解：T0←T1，NPV0←NPV1，否则生成一个[0,1]之间的一个随机数，若R≤eΔNPV/T,则接受临点成为当前解：T0←T1，NPV0←NPV1；反之拒绝T1；

步骤5 更新温度，Temp1←μTemp0，若满足Temp1>Tempf，转步骤3；反之终止搜索过程；

图2 某软件项目网络图

步骤6 输出搜索到的结果T0和NPV0，搜索结束。

4 算例分析

图2是一个AOA软件项目活动网络图。每条弧上的数字代表了活动的序号。里程碑事件为{3,5,10,12}。项目合同总价为U=68万元，某软件系统经过规划与概要设计，预计42周后投入运行，活动费用在其开始和结束事件之间的分配比例η为0.5，承包商的边际利润率为π=20%，β=115%，贴现率α=0.0026，客户对承包商的支付共分为5次，预留罚款：UB=ξU，UA=U-U0-UB。后4次支付分别发生在里程碑事件处。软件交付时要对软件质量进行评估，借此对若承包商的表现水平进行考核，假设评价结果分为三个等级，q={1,2,3}。分别代表由高到低的水平，质量级别为1级时，表明承包商没有逃避行为，客户将剩余款UB全部付给承包商，否则根据承包商表现水平扣除一定罚款。承包商3种表现水平下客户收益为Bq={110,105.8,102.5}，各项活动的工期和费用如表1所示。

表1 不同质量等级下软件项目各项活动的工期和费用

4.1 计算结果

首先由表1计算出各事件发生的时间窗，SQ-PPSP是一个NP-hard问题，ε=0.001，利用上述算法求得该项目的支付进度∏*={T*，P*，Q*}，预留款比例ξ和惩罚系数γ在不同取值时最优支付进度如表2所示。

表2 预留款比例ξ和惩罚系数γ在不同取值时最优支付进度

4.2 结果分析

从表2中可见预留款比例系数ξ的差异会影响承包商的收益。在相同的惩罚系数条件下，ξ的值越大，即预留奖惩款项UB越多，承包商的收益就越低。因此承包商在合同谈判时，应尽量降低预留款比例系数。此外，惩罚系数γ会影响到承包商的表现水平，表中结果显示无论ξ值如何，当γ≥0.04时，承包商的努力水平必须保持在使软件质量等级为1级的程度，才能获取较高的收益。反之承包商的努力水平不能保持在1级的水平时，虽然较低的努力水平能够使承包商较低成本，缩短完工时间，但因为惩罚结构的存在，却并不能提高承包商的收益水平。当γ<0.04时,承包商有较大的选择余地，努力水平越低，越能节省费用和时间，带来额外的收益。因此，较低的惩罚系数γ对承包商是有益的。

5 结论

本文构建了基于质量等级的软件项目支付进度优化模型。该模型考虑到了软件项目一般在里程碑事件的支付特点，及针对客户经常使用扣留部分项目款用于软件交付后对承包商表现水平不足进行相应惩罚，以达到约束承包商的做法，构建了具有惩罚结构的承包商收益最大化模型。将工程项目领域使用的网络计划图用于项目进度支付中，用净现金流量描述承包商的收益，能够更准确地反映承包商的真实收益。同时,给出了模型的求解算法，最后利用一个数值算例对模型和求解结果进行了说明。本文的研究表明，承包商的净现值收益与业主的支付行为、预留款比例及惩罚系数密切相关，这对承包商在合同签订时的谈判策略具有重要的借鉴意义。

[1] Kweku-Muata O, Ojelanki K N. Managing risks in information systems outsourcing: an approach to analyzing outsourcing risks and structuring incentive contracts[J]. European Journal of Operational Research, 2006, 174(1): 245-264.

[2] Christenson C. Construction of present value tables for use in evaluation of capital investment opportunities[J]. The Accounting Review, 1995, 10(4): 666- 673.

[3] Tavares L V. A review of the contribution of operational research to project management[J]. European Journal of Operational Research, 2002,136(1): 1-18.

[4] Dayanand N, Padman R. On modeling progress payments in project networks[J]. Journal of the Operational Research Society, 1997,48(9): 906-918.

[5] Dayanand N, Padman R. A two stage search heuristic for scheduling payments in projects[J]. Annals of Operations Research, 2001, 102: 197-220.

[6] Ulusoy U, Cebelli S. An equitable approach to the payment scheduling problem in project management[J]. European Journal of Operational Research, 2000, 127(2): 262-278.

[7] 何正文,徐渝.多模式项目支付进度安排的优化模型及求解[J].系统工程学报,2007,22(5):474- 479.

[8] Bubshait A, Bubshait A. Incentive/disincentive contracts and its effects on industrial projects[J]. International Journal of Project Management, 2003, 21(1): 63-70.

Research on Payment Scheduling Problems of Software Project

CAO Ping1, ZHANG Jian2, CHEN Fu-ji1

(1.SchoolofEconomicandManagement,FuzhouUniversity,Fuzhou350116,China; 2.SchoolofAirTransportation,ShanghaiUniversityofEngineeringScience,Shanghai201620,China)

The complexity and characteristic of software project makes the Payment Schedule Problem(PSP)has its own unique characteristics. The PSP of software project is studied in this paper according to difference level of software quality. A payment schedule optimization model with penalty structure is constructed to maximize the Net Present Value(NPV)of the contractor, which reflects the impact of different software quality on contractor's gains. And then a heuristic algorithm is developed to solve the PSP. Finally, the validity of the model and algorithm is verified by an instance. It can provide a decision-making basis for contractor in process of signing outsourcing contract and implementing project.

software project; payment scheduling; optimal model; Heuristic algorithm; contractor

2011-10-17

国家杰出青年基金资助项目(70925004)；国家社科基金资助项目(10CGL005)

曹萍(1971-)，女，重庆江津人，管理学博士，副教授，研究方向：决策技术，软件项目管理。

C935；F224.33

A

1007-3221(2015)04- 0282- 06