Metaheuristics for multi-mode capital-constrained project payment scheduling

Abstract

This paper involves the multi-mode capital-constrained project payment scheduling problem, where the objective is to assign activity modes and payments so as to maximize the net present value (NPV) of the contractor under the constraint of capital availability. In the light of different payment patterns adopted, four optimization models are constructed using the event-based method. For the NP-hardness of the problem, metaheuristics, including tabu search and simulated annealing, are developed and compared with multi-start iterative improvement and random sampling based on a computational experiment performed on a data set generated randomly. The results indicate that the loop nested tabu search is the most promising procedure for the problem studied. Moreover, the effects of several key parameters on the contractor’s NPV are investigated and the following conclusions are drawn: The contractor’s NPV rises with the increase of the contractor’s initial capital availability, the payment number, the payment proportion, or the project deadline; the contractor has a decreasing marginal return as the contractor’s initial capital availability goes up; the contractor’s NPVs under the milestone event based payment pattern are not less than those under the other three payment patterns.

Introduction

Since the introduction of cash flows in project scheduling problems by Russell (1970), the problem of scheduling activities of a project in order to maximize its NPV has gained increasing attention throughout the literature. The research efforts have led to a large amount of models and algorithms under a wide variety of assumptions with respect to network representations, cash flow patterns, resource constraints, and time–cost tradeoffs. For an overview of Max-NPV project scheduling in general, we refer the reader to Icmeli et al., 1993, Özdamar and Ulusoy, 1995, Herroelen et al., 1997, Herroelen et al., 1998, Brucker et al., 1999, Kolisch and Padman, 2001, Błlażewicz et al., 2007, Drezet, 2008, Hartmann and Briskorn, 2010, We¸glarz et al., 2011.

The capital-constrained project scheduling problem (CCPSP) can be regarded as a special category of Max-NPV project scheduling problem where investment in project activities is constrained by capital constraint while payments are reinvested in the project to increase the capital availability. Although how to satisfy capital constraint is a vital component of project management, the researches on the CCPSP are relatively sparse so far. Doersch and Patterson (1977) suppose that payments and expenses are made upon the completion of certain activities and formulate the CCPSP as a zero-one integer programming. Smith-Daniels and Smith-Daniels (1987) treat materials and capital constraints in an integrated fashion and present an approach for the CCPSP. Due to the intractability of the CCPSP, Smith-Daniels et al. (1996) present three heuristic procedures and test their performances in solving relatively large capital-constrained projects. Different from the above three literatures where activities are assumed to be performed with a single mode, Özdamar and Dündar (1997) involve a multi-mode CCPSP where capital is treated as a limited nonrenewable resource, and cash outflows and inflows depend upon the selection of activity mode and the random arrival of customers over the project span, respectively. A similar scheduling problem is further analyzed in (Özdamar, 1998), where the contractor has to construct and reconstruct schedules during the progress of the project so as to maintain a positive cash balance dynamically.

The project payment scheduling problem (PPSP) involves how to schedule payments so as to maximize the NPV of the contractor or/and the client. Considering the single-mode PPSP, 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 are fixed. Owing to the combinatorial nature of the problem, Dayanand and Padman (2001a) present a two-stage procedure for the PPSP in which a set of payments is determined in the first stage and in the second stage, activities are rescheduled to improve the NPV. Dayanand and Padman (2001b) also establish several PPSP models from the client’s viewpoint according to practical payment rules. Szmereskovsky (2005) develops a branch-and-bound procedure for a novel PPSP model where the payment schedule is selected by the client and the contractor protects his interests by selecting the activity schedule and rejecting the payment schedule if his NPV does not exceed a minimum amount.

Other researchers devote their attention into the multi-mode PPSP where activities can be accomplished in more than one way. Ulusoy and Cebelli (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 from a joint standpoint of the two sides. Kavlak et al. (2009) introduce a bargaining power concept into the objective of the problem and use simulated annealing and genetic algorithm as solution procedures. He and Xu (2008) analyze the effect of the bonus–penalty structure on payment scheduling and find that this structure can enhance the flexibility of payment scheduling greatly. He et al. (2009) develop two heuristic algorithms, namely simulated annealing and tabu search, for the multi-mode PPSP and compare their performance on a data set constructed randomly.

Based on the literature review above, we can define a new problem named the capital-constrained project payment scheduling problem (CCPPSP) as the combination of the CCPSP and the PPSP. It is no doubt that considering the single-mode CCPPSP makes sense in practice, however, its multi-mode version, i.e. the multi-mode capital-constrained project payment scheduling problem (MCCPPSP), may be more worthwhile to be studied since for many real-life projects, it is possible to execute activities in several alternative modes (see, e.g., Słlowiński et al., 1994, Özdamar and Dündar, 1997, Hapke et al., 1998, Özdamar, 1998, Ulusoy and Cebelli, 2000, Ulusoy et al., 2001, Mika et al., 2005, Kavlak et al., 2009; and so on). For the reasons above, this paper investigates the MCCPPSP where the objective is to assign activity modes and payments concurrently so as to maximize the NPV of the contractor under the constraint of capital availability.

We study the problem using the event-based method by which the project is represented as an Activity-on-Arc (AoA) network and both cash inflows and outflows in the project are attached to events. Note that this may generate a limitation that some cash outflows are assumed to occur earlier than necessary to have the project completed on schedule. However, this limitation can be avoided by adding dummy activities into the network to make that the expense for each activity is associated with a unique event (Dayanand, 1995). During the course of the project, the amount of payments is calculated based on the contractor’s accumulative earned value and the payment proportion, and the total amount of payments equals a given contract price. On the basis of He et al. (2009), we consider the following four different payment patterns.

• Milestone event based payment pattern (MEBPP): A payment occurs once a milestone event is realized by the contractor.

• Progress based payment pattern (PBPP): A payment is made by the client once the contractor’s accumulative earned value reaches a given threshold.

• Expense based payment pattern (EBPP): The client makes a payment to the contractor once the latter’s accumulative expense attains a certain value.

• Time based payment pattern (TBPP): Payments are connected to events periodically based on the time elapsed from the beginning of the project.

For the above four payment patterns, MEBPP and TBPP are similar to PEO and ETI models (Ulusoy et al., 2001, Mika et al., 2005) respectively, EBPP is based on cost–reimbursement contracts, and PBPP corresponds to the contracts where the progress on projects is measured by the value of works completed by the contractor (Gilbreath, 1992). In the MCCPPSP, the number of payments over the course of project is fixed while the time of payments is arranged in the light of one of the four payment patterns.

The MCCPPSP can be recognized as an extension of the CCPSP with the consideration of the arrangement of payments or a generalization of the PPSP where the capital constraint is taken into account. Because both the CCPSP and the PPSP are proven to be NP-hard in the literatures (Smith-Daniels et al., 1996, Dayanand and Padman, 1997), the MCCPPSP must be NP-hard as well. In the MCCPPSP, besides the time–cost tradeoff there also exists the tradeoff between the delay of activities incurring cash outflows and the early completion of activities leading to cash inflows. Therefore, it is worthwhile to be investigated intensively and this research may have a great implication for the contractor to improve the project profitability.

The remainder of this paper is organized as follows. In the next section, we provide the optimization models of the MCCPPSP and an illustrative example. Metaheuristics are developed in Sections 3 Metaheuristics, 4 Computational experiment reports on the results of the computational experiments. Section 5 concludes the paper.