1 Introduction

As one of the most important aspects in project management, the financial issue is attracting more and more researchers’ attention. Russell (1970) is the first researcher who attempts to model the financial aspects of project management with the objective of maximizing the net present value (NPV) of cash flows in the project. Since Russell’s pioneering work, more and more efforts have been spent on the development of schedules that take financial aspects into account and this has led to a large amount of models and algorithms. For an overview of project scheduling with the objective of the maximization of the NPV in general, we refer the reader to Icmeli et al. (1993), Özdamar and Ulusoy (1995), Herroelen et al. (1997), Brucker et al. (1999), Kolisch and Padman (2001), Demeulemeester and Herroelen (2002), Błażewicz et al. (2007), Drezet (2008), Hartmann and Briskorn (2010), and Węglarz et al. (2011).

The project payment scheduling problem (PPSP), which can be considered as a new branch of the Max-NPV project scheduling problem, involves how to schedule progress payments so as to maximize the NPV of the contractor or/and the client. Considering the single-mode PPSP where activities can only be executed with one mode, Dayanand and Padman (1997) introduce several deterministic models to maximize the contractor’s NPV where a deadline is imposed and the number and the total amount of payments from the client are fixed. Owing to the combinatorial nature of the problem, Dayanand and Padman (2001a) present a two-stage procedure for the single-mode PPSP in which a set of payments is determined using a simulated annealing algorithm in the first stage and in the second stage, activities are rescheduled to improve the NPV. Dayanand and Padman (2001b) also establish several mixed integer linear programming models from the client’s viewpoint according to practical payment rules and draw the conclusion that the client obtains the greatest benefit by scheduling the project for early completion such that the payments are not made at regular intervals. On the basis of the fact that the timing of payments and the completion times of activities are determined by the client and the contractor respectively, Szmereskovsky (2005) develops a branch-and-bound procedure for a novel single-mode PPSP model where the payment schedule is chosen by the client and the contractor protects his interests by selecting the activity schedule to maximize his own NPV and by rejecting the payment schedule if his NPV does not exceed a minimum amount.

Other researchers devote their attentions into the multi-mode PPSP where activities can be accomplished in more than one way. Ulusoy and Cebeli (2000) propose a double-loop genetic algorithm in which the outer loop represents the client and the inner loop the contractor to find an equitable payment schedule of the project for the two parties of contract. Kavlak et al. (2009) extend the work of Ulusoy and Cebeli (2000) by introducing a bargaining power concept into the objective of the problem and use simulated annealing algorithm and genetic algorithm approaches as solution procedures for the problem. He and Xu (2008) analyze the effects of the bonus-penalty structure on project payment scheduling and find that the structure can enhance the flexibility of project payment scheduling and be helpful for the two parties of contract to get more profits from the project synchronously. He et al. (2009) develop two heuristic algorithms for the multi-mode PPSP, namely simulated annealing and tabu search, and compare their performances on a data set constructed by ProGen project generator.

In practice, the preferences of the contractor and the client on payment scheduling are often contradicted with each other and the coordination of the conflict between them is always a hard work. Therefore, how to schedule payments so as to make both of the two parties be willing to accept is a problem worthwhile to be investigated intensively. Aiming at such a problem, this paper investigates the PPSP based on the distribution of the project financing cost over the contractor and the client from a joint perspective of the two parties since given the contract price of the project, payment scheduling is associated with the distribution of the project financing cost impliedly. In this problem, the project financing cost is defined as the expense for raising money from the outside or the opportunity cost of the capital devoted into the project and its distribution is determined by the relative bargaining power of the contractor and the client in contract negotiation. The activities can be performed with one of several alternative modes and the project must be finished no later than a deadline. At the completion time of the project, there exists a sole cash inflow for the client, namely the client’s expected revenue which is generated by discounting the project future incomes back to this time. The contract price of the project and the total number of payments are given in advance and during the execution of the project, the amount of payments is determined by the payment proportion and the contractor’s earned value accumulated up to the payment time. On the basis of the condition aforementioned, the task of this research is to find the project payment schedule that can not only maximize the joint revenue of the contractor and the client but also be accepted by both of the two parties.

Based on the above identification, we name the studied problem the financing cost distribution based PPSP (FCDPPSP) and divide it into the following two subproblems.

  • Subproblem 1: How to determine the execution modes and the completion times of activities so that the joint revenue of the contractor and the client is maximized.

  • Subproblem 2: How to arrange payments so as to distribute the project financing cost between the two parties according to their relative bargaining power in the contract negotiation.

We believe that the FCDPPSP, which has not been investigated so far to the best of our knowledge, may be more realistic than the PPSPs studied before because it takes the preferences of the contractor and the client into account concurrently and can facilitate the two parties to achieve a more profitable outcome.

The remainder of this paper is organized as follows. In the next section, we provide the optimization model of the FCDPPSP and an illustrative example. The simulated annealing algorithms are developed in Sect. 3 and Sect. 4 devotes to the computational experiment. Section 5 concludes the paper.

2 Problem formulation

2.1 Optimization model

Consider a project represented as an activity-on-the-node (AoN) network G=(N,A), where the set of nodes, N, represents activities, and the set of arcs, A, represents finish-start precedence constraints with a time lag of zero. The activities are numbered from the dummy start activity 1 to the dummy end activity n and each activity i, i=1,2,…,n, has to be executed in one of M i modes. The duration and the cost of activity i executed in mode m are d im and c im respectively, and we assume that c im occurs at the completion of activity i. The earned value of activity i is v i , which represents the amount of the compensation that the contractor can obtain from the client for finishing activity i. During the execution of the project, the client makes payments to the contractor at the completion of some certain activities named payment activities. The number of payments is K (K≤n) and the amount of the k-th (k=1,2,…,K−1) payment, p k , equals the product of the contractor’s earned value accumulated by the payment time and the compensation proportion θ (0≤θ≤1). The last payment K must be arranged at the completion of the dummy end activity n, and its amount is determined by the formula: \(p_{K} = U - \sum_{k = 1}^{K - 1} p_{k}\) where U (\(U = \sum_{i = 1}^{n} v_{i}\)) is the contract price of the project. The client’s expected revenue, which is assumed to occur at the completion of the project, is ER. The project deadline and the interest rate per period are denoted as D and α, respectively.

The three groups of decision variables in the FCDPPSP are defined below,

Based on the above definition of decision variables, we define the three decision vectors further for the sake of description:

Now, let β be the financing cost rate per period then the project financing cost, FC, can be calculated by

$$ \mathit{FC} = \sum_{i = 1}^{n} \Biggl\{ \Biggl[ \sum_{m = 1}^{M_{i}} (x_{im}c_{im}) \Biggr]\exp\Biggl[ \beta\Biggl( \sum_{t = \mathit{EF}_{n}}^{\mathit{LF}_{n}} (y_{nt}t) - \sum_{t = \mathit{EF}_{i}}^{\mathit{LF}_{i}} (y_{it}t) \Biggr) \Biggr] \Biggr\} - \mathit{TC}. $$
(1)

Where, TC (\(\mathit{TC}=\sum_{i = 1}^{n} \sum_{m = 1}^{M_{i}} (x_{im}c_{im})\)) is the contractor’s expense for finishing the project and [EF i ,LF i ] is activity i’s completion time window calculated using the critical path method (CPM). During the execution of the project, the client makes payments to the contractor and thus bears a part of the project financing cost, FC client ,

$$ \mathit{FC}_{\mathit{client}} = \sum_{k = 1}^{K} \Biggl\{ p_{k}\exp\Biggl[ \beta\Biggl(\, \sum _{t = \mathit{EF}_{n}}^{\mathit{LF}_{n}} (y_{nt}t) - \sum _{i = 1}^{n} \Biggl( z_{ki}\sum _{t = \mathit{EF}_{i}}^{\mathit{LF}_{i}} (y_{it}t) \Biggr) \Biggr) \Biggr] \Biggr\} - U. $$
(2)

Hence, the financing cost of the contractor is only FC cont ,FC cont =FC−FC client . We call λ (\(\lambda = \frac{\mathit{FC}_{\mathit{client}}}{\mathit{FC}}\)), which reflects the proportion of the project financing cost undertaken by the client in fact, the distribution proportion of the project financing cost over the contractor and the client. The relative bargaining power of the two parties in the contract negotiation is represented as RBP (0≤RBP≤1), which takes 0 if the client holds an overwhelming superiority over the contractor and 1 if the reverse is true.

Based on the above definitions, the optimization model of the FCDPPSP, which consists of two submodels, is constructed as follows.

  • Submodel 1

(3)
(4)
(5)
(6)
(7)
(8)

Where, NPV cont and NPV client are the NPVs of the contractor and the client respectively, NPV joint is the joint revenue of the two parties.

  • Submodel 2

(9)
(10)
(11)
(12)
(13)
(14)

Where, T k (\(T_{k} = \sum_{i = 1}^{n} [ z_{ki}\sum_{t = \mathit{EF}_{i}}^{\mathit{LF}_{i}} (y_{it}t) ]\)) and T k−1 (\(T_{k - 1} = \sum_{i = 1}^{n} [ z_{k - 1,i}\sum_{t = \mathit{EF}_{i}}^{\mathit{LF}{}_{i}} (y_{it}t) ]\)) are the occurrence times of the k-th payment and the (k−1)-th payment, respectively.

Submodels 1 and 2 correspond to subproblems 1 and 2 respectively and their solutions constitute together a solution for the FCDPPSP. In submodel 1, the decision variables include x im and y it and the objective is to maximize NPV joint , which is equivalent to the present value of ER minus the present values of c im . Constraints (4) select a mode for each activity exactly. Constraints (5) make sure that the completion time of each activity must be within its completion time window while the precedence feasibility is maintained by (6). A deadline is imposed to the project by constraint (7) and constraints (8) define the binary status of the decision variables. Through solving submodel 1, we may obtain the optimal x im and y it , which are the input data for submodel 2 where the decision variables are z ki . In submodel 2, the objective is to minimize the absolute difference between λ and RBP, i.e. Diff, making the distribution proportion of the project financing cost over the contractor and the client match their relative bargaining power as well as possible. Constraints (10) attach payments to activities and (11) secure that at a certain activity, only one payment can be arranged at most. Constraints (12) compute amounts of payments while constraint (13) forces that the total amount of payments equals the contract price. Constraints (14) give the definition field of the decision variables.

Without any loss of generality, let ER=0 and α=0, then the objective of submodel 1 can be transformed to the maximization of \(- \sum_{i = 1}^{n} \sum_{m = 1}^{M_{i}} (x_{im}c_{im})\), i.e. the minimization of TC. This means that when ER=0 and α=0 subproblem 1 can be simplified to assigning the modes and the completion times of activities to minimize the total expense under the constraint of the project deadline. Recalling that P_C|T in DTCTP (De et al. 1995) is to identify a realization of activities’ modes that minimizes the cost of the project subject to a given deadline, we can conclude immediately that subproblem 1 is a generalization of P_C|T with the consideration of the client’s expected revenue and the time value of money. Because P_C|T has been proven to be strongly NP-hard for general project networks (De et al. 1997), subproblem 1 and thus the FCDPPSP must be strongly NP-hard as well.

2.2 An example

We use an example to illustrate the FCDPPSP identified above. The AoN network of the example is depicted in Fig. 1 where activities 1 and 9 are the dummy start activity and the dummy end activity respectively. The activities in the project can be performed with two modes and their earned values as well as durations and costs under different modes are labeled with nodes. Other data of the project are as follows: K=3, θ=0.8, D=16, ER=6000, α=0.03, β=0.04, RBP=0.8. To demonstrate that a cooperative attitude may allow both the contractor and the client to get more profits from the project, we give the desirable project payment schedules under two different cases and compare the results produced below.

  • The cooperative case

Fig. 1
figure 1

An example

Full size image

In this case, we suppose that the two parties know their relative bargaining power well and take a cooperative attitude in project payment scheduling. It is easy to understand that this case satisfies the assumptions of the model constructed above, and the desirable payment schedule of the project can be worked out easily: Ω=(1,2,1,1,2,1,2,2,1), Γ=(0,4,6,10,11,11,14,14,14), and Ψ=(0,0,1,0,1,0,0,0,1). Under the desirable solution, NPV joint , FC, FC client , and FC cont are calculated below:

Where, TC=c 11+c 22+c 31+c 41+c 52+c 61+c 72+c 82+c 91=2930, U=v 1+v 2+v 3+v 4+v 5+v 6+v 7+v 8+v 9=3300, p 1=θ×(v 1+v 2+v 3)=584, p 2=θ×(v 4+v 5+v 6)=1360, p 3=U−(p 1+p 2)=1356. On the basis of the obtained FC and FC client , we can calculate λ and Diff as follows: λ=FC client /FC=0.80, Diff=|λ−RBP|=0.00, which indicate that under the desirable solution, the distribution proportion of the project financing cost can match the relative bargaining power of the two parties exactly. Besides the results aforementioned, we may calculate NPV cont and NPV client further:

  • The non-cooperative case

In this case, it is assumed that the two parties do not know their relative bargaining power very well and make decisions from their own perspectives. In practice, the modes and the completion times of activities are often arranged by the contractor while the payment activities are mainly determined by the client. Therefore, in such a case, the activities will be performed with their cheaper modes by the contractor so that his/her expense, namely TC, can be minimized. In contrast, from the angle of the client, the payment activities will be arranged in the way by which FC client can be reduced as much as possible. This may lead to another feasible solution for the problem: Ω=(1,1,1,1,1,1,1,2,1), Γ=(0,5,8,11,13,13,16,16,16), and Ψ=(0,1,1,0,0,0,0,0,1). In the light of the same process as that applied in the cooperative case, we can obtain NPV joint , FC, FC client , FC cont , TC, λ, Diff, NPV cont , and NPV client under the new solution as follows: NPV joint =1732.21, FC=512.71, FC client =266.59, FC cont =246.12, TC=2830, λ=0.52, Diff=0.28, NPV cont =179.07, NPV client =1553.14.

Compared with the results in the cooperative case, it can be considered that the contractor and the client in the non-cooperative case have achieved their respective goals to some extent since TC and FC client are both reduced. However, it is unfortunate that their decisions aforementioned decrease rather than increase their profits, i.e. NPV cont and NPV client . The decline of NPV cont derives from the increase of FC cont which is caused by the client’s changing the payment activities whereas the decrease in NPV client comes from the postponement of the occurrence of ER, which is the result of the contractor’s adjusting the modes and the completion times of the activities. The above facts indicate that the contractor and the client can obtain some benefits from their respective decisions, but these decisions may generate greater damages to the profits of the other sides, thus decreasing their NPVs as a whole.

Essentially speaking, the reason for the decreases in the NPVs of the two sides lies in the decline of NPV joint , which is the common source of NPV cont and NPV client . In the cooperative case, NPV joint is maximized and shared by the contractor and the client reasonably according to their relative bargaining power. However, in the non-cooperative case, the objective of maximizing NPV joint is ignored and the two parties pursue to enhance their own profits respectively, without the consideration of the influences on the profit of the other side. Therefore, the results in the cooperative case can be regarded as the global optimization outcomes while those in the non-cooperative case are only the local optimization ones in a sense. On the basis of the above analysis, we can conclude that if the contractor and the client know each other pretty well, in order to get more profits from the project, they will tend to take a cooperative attitude to schedule payments in the project.

3 Simulated annealing algorithm

The model constructed in Sect. 2.1 has two features that render optimal solutions a computationally difficult proposition, especially for real world projects. The model is combinatorial in nature because of the use of binary variables. Furthermore, the number of constraints severely limits the ability to solve the problem to optimality for projects of large size or long duration. For the above reasons, we use a well-known local search metaheuristic, i.e. simulated annealing which is introduced by Metropolis et al. (1953) and is applied to combinatorial optimization for the first time independently by Kirkpatrick et al. (1983) and Cerny (1985), to solve the problem. We choose simulated annealing for two reasons. Firstly, this technique has been successfully applied to a number of project scheduling problems by researchers (e.g. Boctor 1996; Shtub et al. 1996; Etgar et al. 1997; Cho and Kim 1997; Hapke et al. 1998; Viana and Sousa 2000; Dayanand and Padman 2001a; Jozefowska et al. 2001; Bouleimen and Lecocq 2003; Mika et al. 2005; Kavlak et al. 2009; He et al. 2009); and second, it is often characterized by fast convergence and ease of implementation.

Because the problem consists of two subproblems, we divide the algorithm into two modules, namely modules 1 and 2 which are designed to solve subproblems 1 and 2 respectively. In module 1, the desirable Ω and Γ are searched out while in module 2, the desirable Ψ is found on the basis of the desirable Ω and Γ obtained by module 1. In the following of this section, we present the solution representation, the objective function, the preprocessing, the initial solution generation, the neighborhood generation mechanism, and the cooling scheme at first and then describe the design of the two modules.

3.1 Solution representation

Referring to the literatures (Kolisch and Hartmann 1999; Bouleimen and Lecocq 2003; Mika et al. 2008), we represent a solution for the problem, i.e. Ω, Γ, and Ψ, using three lists defined below.

  • Execution mode list (EML): This list is composed of n elements and the i-th (i=1,2,…,n) element defines the mode of activity i.

  • Time deviation list (TDL): This list is an n-element list and the i-th (i=1,2,…,n) element, which is denoted as Δ i (Δ i ∈[0,LF i −EF i ]), indicates how many units of activity i’s completion time deviating from its possible earliest finish time.

  • Payment activity list (PAL): This list includes n 0–1 elements and the i-th (i=1,2,…,n) element is set at 1 if a payment is attached to activity i and 0 otherwise.

Based on the above three lists, Ω and Ψ are determined by EML and PAL directly while Γ is calculated using the following decoding procedure, where ACT i denotes activity i’s completion time and EAS the set of eligible activities, i.e. the unscheduled activities whose predecessors have been scheduled.

Step 1.:

Set EAS={activity 1}, ACT 1=0.

Step 2.:

Update EAS, i.e. remove the scheduled activities from EAS and add the new eligible activities into it. If EAS=∅ go to step 4; otherwise, go to step 3.

Step 3.:

On the basis of EML, calculate EF i for the new eligible activities in EAS and in terms of TDL, determine the completion times of the activities according to the formula ACT i =EF i +Δ i , then go to step 2.

Step 4.:

Stop the procedure and output all ACT i s, thus obtaining Γ.

3.2 Objective function

Given a solution represented by the above three lists, it is possible that the solution is an infeasible solution where the project deadline constraint is violated. In the algorithms, we transform the deadline constraint into a soft constraint based on a deadline feasibility test function defined as

$$ \mathit{DFT} = \max\Biggl\{ 0,\sum_{t = \mathit{EF}_{n}}^{\mathit{LF}_{n}} ( y_{nt}t ) - D \Biggr\}. $$
(15)

During the searching process, if the DFT of a solution is greater than 0 the objective function value of submodel 1 will be penalized according to the following formula:

$$ \mathit{NPV}_{\mathit{joint}}=\mathit{ER}\bigl\{\exp\bigl[-\alpha(D+DFT)\bigr]\bigr\}-\mathit{TEP}. $$
(16)

Where, TEP is the total expense of the project in which all activities are performed with their most expensive modes.

3.3 Preprocessing

Similar with Sprecher et al. (1997), we adapt the project data to the implementation of simulated annealing using a preprocessing procedure by which all inefficient modes and infeasible modes are eliminated. An inefficient mode is a mode with duration not shorter and, simultaneously, cost not less than any other modes of the considered activity. An infeasible mode is defined as follows. Suppose that \(\mathrm{EML}_{\mathit{min}}^{im}\) is an EML in which activity i is performed with mode m while other activities are performed with their modes corresponding to the minimal duration. Denote the EF n under \(\mathrm{EML}_{\mathit{min}}^{im}\) as \(\mathit{EF}_{n}(\mathrm{EML}_{\mathit{min}}^{im})\). If \(\mathit{EF}_{n}(\mathrm{EML}_{\mathit{min}}^{im}) > D\) mode m is an infeasible mode for activity i, since the project deadline constraint cannot be satisfied no matter how to adjust the modes of other activities.

3.4 Initial solution

After the implementation of the preprocessing procedure, a feasible initial solution can be generated conveniently according to the following steps.

Step 1.:

Perform each activity with its mode corresponding to the minimal duration, thus obtaining an EML.

Step 2.:

On TDL, set the values of all the elements at 0.

Step 3.:

Select randomly K−1 activities from all activities except for activities 1 and n. On PAL, set the values of the elements corresponding to the selected activities and activity n at 1 while those of the others at 0.

3.5 Neighborhood generation mechanism

There are three operators utilized in the neighborhood generation mechanism.

  • Mode change (MC): On EML, select one activity randomly and change its mode to another executable one for this activity arbitrarily, thus obtaining a neighbor solution. Compute EF n under the generated solution and judge whether EF n exceeds the project deadline or not. If the answer is false accept the neighbor solution obtained, otherwise, refuse it and repeat the above operations until the answer becomes false.

  • Deviation change (DC): On TDL, choose an activity from all the activities except for activity 1 randomly. Denote the chosen activity as activity i and change the value of Δ i to another possible one within [0,LF i −EF i ] arbitrarily, thus getting a neighbor solution.

  • Element swap (ES): On PAL, except for the last element, select randomly an element from the elements whose values are 1 and swap its position with that of another element chosen randomly from those whose values are 0, changing the current solution to its neighbor.

Note that operators MC and DC are used in module 1 while operator ES is applied in module 2.

3.6 Cooling scheme

The simulated annealing algorithm is specified by the cooling scheme, which is generally constituted of the initial temperature, the cooling function, the Markov chain length, and the stop criterion to terminate the algorithm. A great variety of cooling schemes have now been suggested by different authors and these have been classified in Collins et al. (1988), Eglese (1990), and Koulamas et al. (1994). On the basis of the literatures (Jozefowska et al. 2001; Mika et al. 2005; Kavlak et al. 2009) and a few preliminary computational experiments conducted, the cooling scheme and its parameters used in this study are designed as follows.

  • Initial temperature: In module 1, the initial temperature, Temp init, is calculated by

$$\mathit{Temp}^{\mathit{init}}=\bigl(\mathit{NPV}_{\mathit{joint}}^{\mathit{min}} - \mathit{NPV}_{\mathit{joint}}^{\mathit{init}}\bigr)/\ln \mathit{Prob}^{\mathit{init}} $$

while in module 2 it is computed from

$$\mathit{Temp}^{\mathit{init}}=\bigl(\mathit{Diff}^{\mathit{init}} - \mathit{Diff}^{\mathit{max}} \bigr)/\ln \mathit{Prob}^{\mathit{init}}. $$

Where, \(\mathit{NPV}_{\mathit{joint}}^{\mathit{init}}\) and Diff init are the objective function values under the initial solutions for submodels 1 and 2 respectively, \(\mathit{NPV}_{\mathit{joint}}^{\mathit{min}}\) and Diff max are the minimal objective function value of submodel 1 and the maximal objective function value of submodel 2 among the 50 neighbor solutions of the initial solution respectively, and Prob init, which is set at 0.95 in this application, is the initial acceptance ratio defined as the number of accepted neighbors divided by that of the proposed neighbors.

  • Cooling rate: Beginning from the initial value, the temperature is progressively reduced according to a given cooling rate, which is set at 0.9 in our implementation.

  • Markov chain length: The lengths of Markov chains, which determine the number of transitions for a given value of the temperature, are set at 12⋅n and 10⋅n in modules 1 and 2 respectively.

  • Stop criterion: The search process terminates when the current temperature drops to the final temperature, which is set at 0.01 in the two modules.

3.7 Modules 1 and 2

In the light of different searching structures used, we design two versions of module 1, which are module 1 with random sampling (M1RS) and module 1 with nested loops (M1NL) respectively. The so-called M1RS means that in the searching process, operators MC and DC are selected randomly and applied independently to the current solution to generate a neighbor solution for subproblem 1. However, in M1NL, the above operators are utilized in a nested way, based on the fact that activities’ completion times can not be arranged until their modes are all determined while the reverse is not true. More concretely, M1NL is composed of the following two nested loops.

  • INNERLOOP(EML): In this loop, the EML is given and the task is to search the desirable TDL.

  • OUTERLOOP: With the results obtained by INNERLOOP(EML), this loop seeks the desirable EML, forming a desirable solution for subproblem 1.

On the basis of the desirable EML and TDL found by module 1, module 2 searches the desirable PAL for subproblem 2, thus constituting together a desirable solution for the problem.

4 Computational experiment

4.1 Experimental design

For the sake of description, we represent the simulated annealing algorithm with M1RS and M1NL as SA-M1RS and SA-M1NL respectively in the following of the paper. In the experiment, SA-M1NL utilizes the stop criterion defined in Sect. 3.6, and during its searching process, the total number of the feasible solutions visited by modules 1 and 2 are recorded and denoted as \(\mathit{Num}_{\mathit{stop}}^{1}\) and \(\mathit{Num}_{\mathit{stop}}^{2}\) respectively. To compare the performances of SA-M1RS and SA-M1NL on a common basis, we adjust the stop criterion of SA-M1RS as follows: The algorithm stops and outputs the current solution as the desirable one when the number of the feasible solutions visited by modules 1 and 2 reaches \(\mathit{Num}_{\mathit{stop}}^{1}\) and \(\mathit{Num}_{\mathit{stop}}^{2}\) respectively. Note that in module 1 of SA-M1RS, since the two decision vectors are searched concurrently the length of Markov chains, L, is set at 140⋅n.

To evaluate the performances of SA-M1RS and SA-M1NL, we utilize a simple heuristic algorithm, namely the multi-start iterative improvement (MSII) (Mika et al. 2008; Waligóra 2008, 2009), to generate benchmark schedules for comparison. For the two subproblems, MSII starts from the same initial solution and employs the same neighbor generation mechanism as those used in SA-M1RS. In the searching course of MSII, the most improving neighbor solution is chosen and when there are no improving moves, it restarts with another feasible solution generated randomly. The algorithm terminates and takes the best solution found as the desirable one when the numbers of the visited feasible solutions for subproblems 1 and 2 reach \(\mathit{Num}_{\mathit{stop}}^{1}\) and \(\mathit{Num}_{\mathit{stop}}^{2}\), respectively.

The three algorithms are tested on a data set constructed by ProGen project generator (Kolisch et al. 1995; Kolisch and Sprecher 1996). The set consists of 80 instances and the parameter setting used to generate the instances is described in Table 1. The value of the key parameters, including α, D, β, K, and θ, is set at three levels given in Table 2. A full factorial experiment of the five parameters with three levels results in 35 replicates for each instance and 80×35=19,440 ones overall. Note that during the generation of the instances, it is ensured that there are no inefficient modes for activities through the parameter setting. However, infeasible modes, which have to be eliminated by the preprocessing procedure presented in Sect. 3.3, cannot be avoided completely since for a certain instance the parameter D needs to be set at different values. The following five indices are defined to evaluate the performances of the algorithms.

  • NUM: The number of instances for which the algorithm find a solution equal to the best solution known, i.e. the best solution found by any of the algorithms.

  • ARP: Average relative percent below the known best solution for the problems.

  • MRP: Maximal relative percent below the known best solution for the problems.

  • ACT: Average computational time of the algorithm for solving the problems.

  • MCT: Maximal computational time of the algorithm for solving the problems.

Table 1 Parameter setting used to generate the data set
Full size table
Table 2 Levels of the key parameters
Full size table

Note that since the FCDPPSP consists of two subproblems we may obtain two groups of the above indices in the experiment. The algorithms are coded and compiled with Visual Basic 6.0 and the computational experiment is performed on a Pentium-based personal computer with 1.60 GHz clock-pulse and 256 MB RAM.

4.2 Experimental results

The computational results are presented in Table 3. For subproblem 1, Table 3 makes clear that ARPs and MRPs for SA-M1RS and SA-M1NL are much less whereas NUMs for the two algorithms are much greater than the corresponding indices for MSII, in particular when the instances become larger. This indicates that SA-M1RS and SA-M1NL outperform MSII remarkably and their superiority augments with the increase of the problem scale. This result is not surprising because the intelligent search procedures generally get an advantage over the simple search method, and this advantage grows as the problem becomes more complex. As for the two simulated annealing algorithms, it can be seen that the three indices aforementioned for SA-M1NL are a bit better than those for SA-M1RS, and with the increase of the number of activities, the indices for SA-M1NL improve while those for SA-M1RS deteriorate. So, we can say that compared with SA-M1RS, SA-M1NL performs a little better in general, especially for the larger instances. The above outcomes may be explained as follows: SA-M1NL is based on the characteristics of the problem and utilizes the two nested loops to search the desirable solutions while in SA-M1RS, the two neighbor generation operators are selected in a random fashion. Therefore, it can be considered that the searching structure of SA-M1NL may be more reasonable than that of SA-M1RS, making it own a higher searching efficiency than SA-M1RS. The results for subproblem 2, which is much easier to be solved than subproblem 1, are relatively simple. Since SA-M1RS and SA-M1NL employ the same module 2, their NUMs, ARPs, and MRPs for subproblem 2 are almost identical. Compared with SA-M1RS and SA-M1NL, MSII gets a bit worse outcome because its searching process is less intelligent than those of SA-M1RS and SA-M1NL.

Table 3 Computational results of the experiment
Full size table

The computational times are ones to be expected—MSII runs faster than SA-M1RS and SA-M1NL since it owns a simpler searching process than the other two algorithms. Concerning SA-M1RS and SA-M1NL, because the searching structure of the latter is more complex than that of the former it seems a little strange that the former works longer than the latter for tackling subproblem 1. Recall that during the searching process of the algorithms, the two neighbor generation operators, i.e. MC and DC, are utilized to generate neighbor solutions based on the current one. In SA-M1RS, when operator MC is selected to generate neighbor solutions, the EML is changed while the TDL remains unchanged. Because the value of LF i −EF i is determined by the EML, this may lead to the result that Δ i >LF i −EF i , causing the generated solution to be infeasible. However, in SA-M1NL, this shortcoming is eliminated by the loop nested searching structure where operator DC works under a given EML. The facts aforementioned may explain why SA-M1NL runs faster than SA-M1RS to some extent although the former owns a more complex searching structure than the latter. Summarizing the computational results discussed above, we can draw the conclusion that SA-M1NL is the most promising procedure for the problem among the three algorithms presented.

The influences of the key parameters on average NPV joint , NPV cont , NPV client , Diff, FC cont , and FC client are presented in Table 4, from which the following phenomena can be observed. Firstly, with the growth of α, NPV joint , NPV cont , and NPV client decrease. This is an immediate observation when formula (3) is taken into account. Secondly, as ρ D increases, NPV joint and NPV cont climb while NPV client and FC cont drop. The reasons for these results are as follows. When ρ D increases D augments subsequently, so, the project deadline constraint is loosened to some degree, causing NPV joint improved. In addition, the postponement of D can make the contractor execute more activities with their cheaper modes, therefore, NPV cont rises and FC cont falls. However, for the client, because the occurrence of his/her expected revenue, which is assumed to take place at the completion of the project, may be delayed in such a case, NPV client declines. Thirdly, increasing β makes FC cont and FC client increased monotonously and this can be explained by formulae (1) and (2) directly. Fourthly, when K increases NPV cont and FC client ascend whereas NPV client ,FC cont , and Diff descend. This is because that the increase of K can make the payments occur at earlier activities and thus plays a negative effect on the client whereas a positive effect on the contractor, resulting in NPV cont and FC client increased while NPV client and FC cont decreased. Furthermore, increasing K may generate more choices on the arrangements of payments at activities, therefore, the obtained Diff cannot be worse than the one obtained for the smaller K in general. At last, as θ increases, NPV cont and FC client go up while NPV client and FC cont go down. This is a reasonable result since enhancing the value of θ leads to greater parts of payments to occur earlier during the execution of the project.

Table 4 Influences of the key parameters on the computational results
Full size table

5 Conclusions

This paper studies the project payment scheduling problem based on the distribution of the project financing cost which is defined as the expense for raising money from the outside or the opportunity cost of the capital devoted into the project. The purpose is to find the project payment schedule that can not only maximize the joint revenue of the contractor and the client but also match their relative bargaining power and thus be accepted by them. Based on its identification, we divide the studied problem into two subproblems, i.e. how to determine the modes of activities and the completion times of activities so that the joint revenue is maximized and how to arrange payments at activities so as to distribute the project financing cost according to their relative bargaining power. An optimization model, which consists of two corresponding submodels, is constructed using the activity-based method and an example is utilized to illustrate the practical utility of the constructed model. For the strong NP-hardness of the problem two simulated annealing heuristic algorithms, namely SA-M1RS and SA-M1NL which own different searching structures, are developed and compared with MSII on the basis of a computational experiment performed on a data set generated by ProGen. From the computational results, the following conclusion is drawn: The proposed SA-M1NL is the most promising algorithm for solving the defined problem, surpassing SA-M1RS somewhat while clearly outperforming MSII especially when the instances become larger.

In addition, the influences of some key parameters on the computational results are investigated through the full factorial experiment of the five parameters with three levels, and the obtained observations are described below: Increasing the interest rate decreases the contractor’s, the client’s, and their joint NPVs; When the project deadline is delayed the contractor’s and the joint NPVs climb while client’s NPV and the contractor’s financing cost drop; Increasing financing cost rate increases the contractor’s and the client’s financing costs; With the growth of the payment number or the compensation proportion, the contractor’s NPV and the client’s financing cost ascend whereas the client’s NPV and the contractor’s financing cost descend; The absolute difference between the distribution proportion of the project financing cost and the relative bargaining power of the two parties tends to go down as the payment number goes up.

Note that the research in this paper is based on the joint perspective of the two parties. Although it is not always the case that the contractor and the client take a cooperative attitude in the real-world project management, the research can still provide some supports for the coordination of the conflict between the two parties in contract negotiation and facilitate them to achieve a more profitable outcome.