大规模项目调度问题的分解和协调优化方法

Decomposition and optimization methods for large-scale project schedules

为了解决大规模有资源约束的项目调度问题,提出一种串行分解和并行分解相结合的项目逐层分解方法,以便克服精确算法求解时间不可接受,而启发式算法解的质量较差的问题。根据该分解方法特点,提出基于采样选择的启发式协调方法,以及基于分枝定界方法的精确底层调度的子项目协调优化算法,并通过仿真分析了关键参数的选取。仿真结果表明,该算法解的平均质量明显优于相关启发式算法,并且求解时间能够满足工程上的要求,能够有效地提高大规模项目调度问题的求解质量,具有实用价值。

Exact algorithms for large-scale resource constrained project schedules require excessive computing times while the solution quality of heuristics algorithms are not good enough. A project decomposition method with intelligent optimization was developed by combining serial and parallel decomposition methods. The optimization algorithm was the project coordination method based on sampling selection with sub-projects optimized by a bound algorithm. The effect of key parameters on the solution quality and time were analyzed for various simulated scenarios. The simulations show that the algorithm provides a better average quality of solutions than other heuristic algorithms.