Fuzzy-based adaptive sample-sort simulated annealing for resource-constrained project scheduling

摘要

This paper deals with the resource-constrained project scheduling problems (RCPSP), where the activities of a project have to be scheduled with the objective of minimizing the makespan subject to both temporal and resource constraints. Being one of the most intractable problems in the operations research area, RCPSP has often been a target and test bed for establishing new optimization tools and techniques. In order to efficiently solve this computationally complex problem in real time, we propose a parallel intelligent search technique named the fuzzy-based adaptive sample-sort simulated annealing (FASSA) heuristic. The basic ingredients of the proposed heuristic are the serial schedule generation scheme (SGS), sample-sort simulated annealing (SSA), and the fuzzy logic controller (FLC). The serial SGS generates the initial schedules following both the precedence and resource constraints. SSA is basically a serial simulated annealing algorithm, artificially extended across an array of samplers operating at statistically monotonically increasing temperatures. The FLC makes the SSA adaptive in nature by regulating the swapping rate of an activity's priority during an improved schedule generation process. The implementation results of the FASSA heuristic over extremely hard test bed, adopted from the Project Scheduling Problem Library (PSPLIB), reveal its superiority over most of the currently existing approaches.