Multi-Objective Evolutionary Algorithms for Resource Allocation Problems


A resource allocation problem (RAP) is encountered in a variety of areas in operations research and management science. It is generally treated as a combinatorial optimization problem, where a limited amount of resources are to be allocated to certain number of competitive events in order to achieve the most effective allotment of the resources. An RAP usually contains a huge number of integer and/or real variables and constraints, a discrete search space, and multiple objectives. Moreover, the general RAP is NP-complete (Ibaraki and Katoh [1988], Zhang [2002], Kameshwaran [2004]). It is said that the properties of an NP-complete RAP can be used in characterizing another NP-complete RAP. Hence, it is very important to explore the similarities among different types of RAPs. However, though a number of RAPs are being studied independently, the study of similarities among them are still undeveloped. In this thesis work, two NP-complete RAPs of quite different natures, namely university class timetabling and land-use management, are considered for such studies. Based on their similarities, two similar versions of NSGA-II (Deb [2001], Deb et al. [2002]), a very popular multi-objective evolutionary algorithm, are developed for handling these two RAPs. The preparation of a class timetable is required in every academic institute once or twice a year. The problem involves the scheduling of classes (lectures), students, teachers and rooms at a fixed number of time-slots, subject to a certain number of constraints. Traditionally, the problem is solved manually by a trial and hit method, which either does not guarantee a valid solution or likely to miss far better solutions. Such uncertainties motivate the scientific study of the problem, and the development of automated solution techniques for it. Despite multiple criteria, which are to be met simultaneously, the problem is usually tackled as a single-objective optimization problem. On the other hand, in many cases, the problem is over-simplified by skipping many complex class structures, such as multi-slot, split, combined and group classes. The land-use management is another scheduling problem, where different competitive land uses are to be allocated to different units of a landscape to meet the desired long-term objectives. Land and its resources have been under tremendous pressure due to human activities on land to meet various demands, which are causing significant transformations of the land for a variety of uses. Global warming, soil degradation, deforestation, loss of biodiversity, shortage of land resources, flooding, air and water pollution, are all consequences of mismanagement of land and its resources. Hence, an integrated land-use policy framework is required to be developed for improving soil quality, ensuing biomass production, maintaining environmental stability, and extending socio-economic benefits. Although these incommensurable objectives of land management can be achieved through optimization tools, very little work has been done so far in this area. The inadequacy of classical methods, like linear and integer programming approaches and graph coloring theory, to handle the huge number of integer variables, discrete search spaces, and multiple objectives, involved with RAPs, has drawn the attention of researchers towards non-classical methods for handling these types of problems (Colorni et al. [1990], Looi [1992], Costa [1994], Matthews et al. [1999a], Aerts et al. [2003], Ducheyne [2003]). In this thesis work, evolutionary algorithms (EAs), which are among the most widely investigated non-classical methods for RAPs, are studied for handling the university class timetabling and land-use management problems. NSGA-II-UCTO (NSGA-II as University Class Timetable Optimizer) and NSGA-II-LUM (NSGA-II in Land-Use Management), two similar versions of the popular EA-based multi-objective optimizer Non-dominated Sorting Genetic Algorithm-II (NSGA-II), are developed for handling these two problems, considering various aspects that are common to most of the variants of the problems. NSGA-II-UCTO is developed as a bi-objective model from the perspectives of both students and teachers, where the average number of weekly free time-slots between two classes of a student and the average number of weekly consecutive classes of a teacher are both minimized. NSGA-II-UCTO is applied on three real problems taken from two premier technical institutes in India. On the other hand, NSGA-IILUM is developed as a three-objective model for handling spatial-GIS (Geographical Information Systems) based land-use management under a set of physical and ecological constraints. The studied objectives are the maximization of the net present economic return, maximization of the net amount of carbon sequestration, and minimization of the net amount of soil erosion. The last two objectives are considered as impacting on global warming and soil degradation, respectively, which have drawn the attention of researchers in recent years. NSGA-II-LUM is applied to a Mediterranean landscape from Southern Portugal, and a number of interesting solutions, maintaining good trade-off among them, are obtained. Finally, similarities between the class timetabling and land-use management problems, as well as between their solution techniques, are discussed. The main contribution of the thesis is summarized below: • With the aim of exploring the similarities among different types of resource allocation problems, two similar versions of NSGA-II, a well-known multiobjective evolutionary algorithm, are developed as the solution techniques for two challenging resource allocation problems, namely the university class timetabling and the land-use management. • Similarities between the university class timetabling and the land-use management problems, as well as between their solution techniques, are discussed through a number of case-studies.