<p>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.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Simulated annealing for Max-NPV multi-project scheduling in a sharing-economy environment

  • Yidan He,
  • Zhengwen He,
  • Nengmin Wang,
  • Erik Demeulemeester

摘要

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.