Solving the FS-RCPSP with hyper-heuristics: A policy-driven approach
针对活动工期同时存在模糊性和随机性的资源受限项目调度问题，提出一种自适应差分进化超启发式方法，通过演化调度策略来最小化项目期望完工时间，在960个测试问题上表现优于CPLEX。
In this paper, a problem in the area of scheduling, namely Fuzzy Stochastic Resource-Constrained Project Scheduling Problem (FS-RCPSP), is addressed. Like the original Resource-Constrained Project Scheduling Problem (RCPSP), the objective is to minimise the expected makespan of the project subject to precedence and resource constraints. However, due to mixed uncertainty comprising fuzziness and randomness in the estimates of activity durations, the makespan is a fuzzy stochastic number. Recognising both fuzziness and randomness in activity durations results in more robust schedules but the scheduling problem is harder to solve. A hyper-heuristic, named Self-adaptive Differential Evolution to Scheduling Policy (SADESP) is proposed to address this issue. SADESP has two key modules: (1) a module (policyEvolver) which evolves scheduling policy and (2) a dynamic scheduling procedure (dScheduler) which makes scheduling decisions using a particular scheduling policy. The performance of SADESP is benchmarked against CPLEX across an extensive set of 960 problems created with ProGen – a standardised problem generator for creating benchmark problems in scheduling. The results returned by SADESP for FS-RCPSP are very encouraging, both in terms of accuracy and computational performance.