Download files
Abstract
Classical project scheduling problem (PSP) usually involves a set of non-preempt-able and precedence related activities that need to be scheduled. The resource constrained project scheduling problem (RCPSP) extends the classical project scheduling by taking into account constraints on the resources required to complete the activities. RCPSP is a widely studied NP~(Non-deterministic Polynomial-time)-Hard optimization problem. One particular approach for solving RCPSP instances is through the use of simple priority heuristics. A priority heuristic can be defined as a function which utilizes certain instance characteristics to construct a solution. Priority heuristics are usually the quickest way of obtaining ``good-enough" solutions and have been useful for a range of different combinatorial optimization problems.
Design of priority heuristics, however, is a non-trivial task. Usually, the process involves problem experts who extensively study instance characteristics in order to construct new heuristics. This approach can be time-consuming as well being restrictive in terms of the possibilities that can be considered by an expert. As a result, researchers are increasingly exploring methods to automate construction of heuristics, commonly known as hyper-heuristics. Genetic programming based hyper heuristics (GPHH) are more commonly used for this task. It operates on a set of problem attributes and mathematical operators to evolve heuristics. GPHHs have been used in a number of different domains such as job shop scheduling and routing. The same, however, can not be said about RCPSP, as apart from a few foundational studies, the literature is relatively scant.
The work presented in this thesis is directed towards addressing the aforementioned gap in the literature. Firstly, a GPHH is presented for evolving different types (arithmetic and decision-tree) of priority heuristics for RCPSP. The effect of different representations and attributes are empirically evaluated and an attempt is made to evolve priority heuristics which can out-perform existing human designed priority heuristics. Next, a GPHH framework is proposed for evolving variants of the rollout-justification procedure in order to leverage the strength of this approach in discovering heuristics which can perform on par with state-of-the-art algorithmic methods. Finally, a dynamic variant of the classical RCPSP is formulated and a multi-objective GPHH is proposed for discovering priority heuristics, with strong performance and low complexity, to deal with dynamic instances. Apart from these major contributions, other improvements in GP and RCPSP are also proposed as part of the research undertaken during this PhD. The heuristics discovered in this study exhibit, either, on-par or superior performance in comparison to existing human designed approaches.