Automated Design of Heuristics for the Resource Constrained Project Scheduling Problem

Created by W.Langdon from gp-bibliography.bib Revision:1.7831

@PhdThesis{Chand:thesis,

• author = "Shelvin Chand",
• title = "Automated Design of Heuristics for the Resource Constrained Project Scheduling Problem",
• school = "Engineering \& Information Technology, Australian Defence Force Academy, University of New South Wales",
• year = "2018",
• address = "Australia",
• month = "6 " # nov,
• keywords = "genetic algorithms, genetic programming, Resource Constrained Project Scheduling, Optimization, Scheduling, Heuristics, Hyper-Heuristics",
• URL = "http://unsworks.unsw.edu.au/fapi/datastream/unsworks:52846/SOURCE02?view=true",
• URL = "http://handle.unsw.edu.au/1959.4/60621",
• size = "240 pages",
• abstract = "Classical project scheduling problem 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. 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 uses certain instance characteristics to construct a solution. 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 as 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. GPHH 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, for which, 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 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.",
• notes = "Supervisors: Dr. Hemant Singh and Prof. Tapabrata",

}

Genetic Programming entries for Shelvin Chand

Citations