A Graph colouring model for timetabling problem
| dc.contributor.author | Samarasekara, L. A. M. W. I. | |
| dc.date.accessioned | 2024-10-30T05:32:42Z | |
| dc.date.available | 2024-10-30T05:32:42Z | |
| dc.date.issued | 2013 | |
| dc.description.abstract | The Timetabling problem consists of allocating a number of courses to a limited set of resources such as time slots, set of lecturers, lecture rooms, labs and group of students in such a way to satisfy predefined constraints. The constraints can be divided into two groups: hard constraints and soft constraints. A timetable has to satisfy all hard constraints in order to be feasible and it should satisfy as much as possible soft constraints in order to be good quality. Constructing a satisfactory conflict-free semester-long timetable of courses is often a difficult problem that any educational institute faces each semester.Construction of such type of timetable can be modeled as a graph colouring problem. In a graph colouring model, the timetabling problem is usually represented as a graph where events (e.g. subjects) are represented as vertices, while conflicts between the events are represented by edges. Edges of a graph are coloured in such a way,so that no adjacent edges are coloured by the same colour and each time slot in the timetable corresponds to a colour in the graph colouring problem. After finding time slots, the possible courses can be conducted in each time slot are assigned according to the graph. Finally, separate timetables for each year (first year and second year) are filled by assigning each subject for available time periods according to the proposed algorithm. The automated timetabling system is based on the proposed algorithm of the graph colouring model. The proposed system can generate not only one solution for the timetabling problem, but also many possible solutions. The system can further generate lecturers' personal timetables and also special lecture room timetables. Therefore this timetabling system exhibits a much better quality of solution and will support for the management as well. | |
| dc.identifier.uri | https://ir.lib.pdn.ac.lk/handle/20.500.14444/2878 | |
| dc.language.iso | en_US | |
| dc.publisher | University of Peradeniya | |
| dc.subject | Graph colouring model | |
| dc.subject | Timetabling | |
| dc.title | A Graph colouring model for timetabling problem | |
| dc.type | Thesis |