Adaptable search neighborhoods for Resource Constrained Scheduling

Abstract

Resource Constrained Scheduling problem (RCSP) is a scheduling problem in which each activity may require more than one resource and resources may not be available in the same quantity throughout the planning period. This thesis describes a methodology for RCS that can be easily adapted to consider different regular measures of performance. The solution approach is based on the generation of strong search neighborhoods using methods recently published in the literature. Computational results are encouraging when searching these spaces using simple local search techniques and genetic algorithms. Close-to-optimal solutions are found for standard problems from the literature. A special case of RCSP, the flexible flow line (FFL) scheduling problem, is also studied. Computational results on some real industrial data produced close-to-optimal solutions. In both cases (RCS and FFL), the performance measures used to the test the procedures are makespan and mean tardiness.