Abstract: In reality, as projects are implemented, the contractors may incur a series of cash flows occurring in the following two forms: Cash outflows are induced mainly by activity execution while cash inflows generally result from payments based upon the contract between the contractor and the client. It is easy to understand that throughout the projects, maintaining a positive balance between cash outflows and inflows is very important for the contractor, because if the outflows cannot be covered by the inflows in time, the contractor may not be able to smoothly implement the projects or may even incur project failure. However, in the area of project scheduling, although there exist a lot of researches that take cash flows into account, most of them focus on the problem of how to maximize the net present value of the projects’ cash flows. To the best of our knowledge, the multi-project scheduling problem with the objective of balancing the cash flows positively has not been studied intensively thus far.
Based on the facts aforementioned, this paper investigates a milestone payment based multi-mode multi-project cash flow balance scheduling problem, in which the contractor needs to implement multiple projects concurrently, activities can be performed with several discrete modes, and the objective is to minimize the maximal cash flow gap under the constraint of project deadline. First, on the basis of the problem definition, we construct a nonlinear integer programming optimization model for the studied problem using the defined notations. In the model, the decision variables are the arrangement of the execution mode and start time of activities whereas the constraints include the precedence relationship between activities, project deadlines, calculation formulae of payment amounts, and definition domain of decision variables. Through the analysis of the constructed model, we proposed three properties for the problem, which can be employed to determine the maximal cash flow gap under a given schedule conveniently and reduce this gap by adjusting the completion or start times of some relevant milestone activities or non-milestone activities properly.
Then, due to the NP-hardness of the problem, we develop a tabu search algorithm where the proposed properties are utilized to improve the generated initial and neighbour solutions and hence enhance the searching efficiency of the algorithm. In the algorithm, two decision variable sets are adopted to represent the solution of the problem and a decoding procedure is designed to transform the solution into the corresponding schedule of projects. The algorithm starts with an initial solution that is constructed according to the following way: Under the constraint of project deadline, the execution mode of activities is assigned as the one with lowest cost while the start time of milestone (non-milestone) activities are arranged asearly (late) as possible. During the searching process, neighbour solutions are generated randomly and the two decision variables are searched in a nested manner. When the operation time of the algorithm reaches a certain value, the algorithm stops and outputs the best solution gotten as the desirable solution.
Finally, we utilize a real case, which consists of two projects that own different activity networks, project deadlines, payment conditions, and activity parameters, to verify the proposed model and algorithm. The two versions of the algorithm, namely the original and improved tabu search algorithms, are compared and the obtained results indicate that the latter can obtain the best solution for the case more quickly than the former, thus validating the contribution of the improvement measure to the algorithm. In addition, for the studied case, the desirable schedule found by the algorithm is remarkably better than the practical schedule and by comparing the two schedules, we derive the managerial insights described below: The contractor can reduce the maximal cash flow gap effectively by properly delaying the completion time of the relevant milestone activity or adjusting the start time of the relevant non-milestone activities based on the occurrence period of the maximal cash flow gap. Moreover, the balance status between cash outflows and inflows can be improved further through moving the schedule of some individual projects in light of the cash flow distribution over the course of the projects.

Key words: multi-project scheduling, cash flow balance, optimization model, tabu search, milestone based payment

摘要： 现金流入与流出的动态平衡,对于承包商平稳实施项目具有重要的现实意义。本文基于这一实际背景,研究了在里程碑支付条件下,活动具有多种执行模式的多项目现金流平衡调度问题。首先,在对研究问题进行界定的基础上,构建了多模式多项目现金流平衡调度优化模型并提炼了模型的基本性质;其次,针对问题的NP-hard属性,开发了禁忌搜索启发式求解算法,根据问题性质提出算法的改进措施;最后,用一个实际案例对模型和算法进行了验证,得到如下管理启示:基于最大现金流缺口发生时段,适当延后相关里程碑活动的完成时间或调整相关非里程碑活动的开始时间,同时,根据现金流分布合理平移部分单项目的进度计划,能实现现金流出与流入的最佳匹配并有效减小最大现金流缺口。

关键词: 多项目调度, 现金流平衡, 优化模型, 禁忌搜索, 基于里程碑支付