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

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