Abstract

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.