Simulated annealing for Max-NPV multi-project scheduling in a sharing-economy environment
摘要
This paper considers a Max-NPV multi-project scheduling problem in a sharing-economy environment, where the task consists of matching project activities with joined enterprises and arranging activities’ start times to maximise the net present value (NPV) of multiple projects. First, we define the used notation, and we formulate the studied problem as an optimisation model, from which several properties of the problem are extracted. Next, due to the NP-hardness of the problem, we propose a simulated annealing algorithm, where a measure designed based on the problem’s properties is employed to improve the search efficiency. Finally, an extensive computational experiment is carried out on a randomly generated dataset to test the proposed algorithm, and based on the obtained results, the impacts of key parameters on the objective function value are analyzed. The conclusions of the research are as follows: Among the tested algorithms including simulated annealing, tabu search, and multistart iteration improvement, the proposed algorithm can obtain the best results, which are less than 1% worse than the optimal solutions for the small instances. However, varying the key parameters, the effect of the improvement measure in the algorithm changes. The NPV of multiple projects increases when the project deadline, the resource strength, the number of milestone activities or the payment proportion climb, whereas it decreases with an increased discount rate per period.