Search Heuristics for Resource Constrained Project Scheduling
针对多资源约束和优先约束的项目调度问题，开发了基于模拟退火、禁忌搜索和遗传算法的搜索过程，通过优先级编码生成可行邻域解，测试表明模拟退火和禁忌搜索优于现有启发式算法。
We develop a search procedure for project scheduling problems with multiple resource constraints as well as precedence constraints. The procedure is applied to three popular search heuristics, simulated annealing, tabu search and genetic algorithms. In the heuristics, a solution is represented with a string of numbers each of which denotes priority of each activity. The priorities are used to select an activity for scheduling among competing ones. The search heuristics with this encoding method can always generate feasible neighbourhood solutions for a given solution. Moreover, this encoding method is very flexible in that problems with objective functions of a general functional form (such as a nonlinear function) and complex constraints can be considered without much difficulty. Results of computational tests on the performance of the search heuristics showed that the search heuristics, especially the simulated annealing and tabu search algorithms worked better than existing heuristics.