Investigating room assignment problem using evolutionary algorithm with the matrix representation
Loading...
Date
2003
Authors
Li Pei, Wong
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
An increase in the number of courses offered at institutions of higher learning
over the last few years has resulted in a significant increase in the number of students.
This has resulted in a severe problem in allocation of rooms for lectures and
examination. This allocation problem becomes more complicated when there are other
constraints to be fulfilled simultaneously.
Universiti Sains Malaysia (USM) in particular faces such a problem when it
comes to assignment of rooms during examination. This is due to the nature of the
problem, which involves a many-to-many relationship between rooms and examination.
In this particular relationship, rooms can be shared among several examinations, and an
examination can be split over two or more rooms (split examinations). Currently, the
assignment process is done manually. This process is time consuming. The assignment
also shows many imperfections such as does not optimize the usage of available space
in USM.
This research intends to investigate the use of the Evolutionary Algorithm (EA)
in solving the room assignment for examination. EA is based on the principles of
evolution- survival of hi.e fittest. For this, a matrix representation is proposed as the
encoding scheme as it has an inherently two-dimensional structure. This structure is able
to show the many-to-many relationship naturally. The search operators such as
crossover, mutation and reproduction will be used to evolve the solutions inline with the
proposed representation scheme.
This thesis also investigates the strategy of using different weightages to handle
multiple constraints. This strategy is integrated as part of the fitness function design. It
also discusses the EA parameters estimation. It is hoped that the proposed matrix-ba~ed
EA modeling technique can be easily adapted or extended to solve other resource
allocation problems that involve the many-to-many relationship.
Description
Keywords
Assignment problem , Evolutionary algorithm