Local cover image
Local cover image
Local cover image
Local cover image

University examination timetabling using graph coloring and Tabu search methods / Erick Cezar O. Elipian

By: Material type: TextTextLanguage: English Publication details: 2004Description: 46 leavesSubject(s): Dissertation note: Thesis (BS Applied Mathematics) -- University of the Philippines Mindanao, 2004 Abstract: University timetabling is an assignment-type problem that deals with the scheduling of the university programs. There are two types of university timetabling, the course timetabling and the examination timetabling. Course timetabling deals with the scheduling of courses offered by the university while the examination timetabling deals with the scheduling of examinations. The objective is to obtain a timetable in such a way that sets of constraints were satisfied. Two types of constraints were identified in any timetabling problem, hard constraints for the feasibility and soft constraints for quality. Several methods such as graph coloring and tabu search method are able to solve timetabling problems. Graph coloring is a vertex coloring search process while tabu search is a metaheuristic search that guides a heuristic search process to obtain a better solution. This study aimed to formulate a timetabling system using graph coloring and tabu search method. From the set of soft constraints, the objective function was formulated. The objective function was used to measure the quality of the timetable. Fifty-five feasible timetables were produced, one from graph coloring and the remaining from tabu search method. The timetable obtained from graph coloring serves as a primary timetable. Tabu search was used to enhance the quality of the primary timetable. Manual manipulation was applied to produce these timetables. An algorithm for producing a feasible timetable using graph coloring and tabu search method was designed.
Tags from this library: No tags from this library for this title. Log in to add tags.
Star ratings
    Average rating: 0.0 (0 votes)
Holdings
Cover image Item type Current library Collection Call number Status Date due Barcode
Thesis Thesis University Library Theses Room-Use Only LG993.5 2004 A64 E44 (Browse shelf(Opens below)) Not For Loan 3UPML00011089
Thesis Thesis University Library Archives and Records Preservation Copy LG993.5 2004 A64 E44 (Browse shelf(Opens below)) Not For Loan 3UPML00020899

Thesis (BS Applied Mathematics) -- University of the Philippines Mindanao, 2004

University timetabling is an assignment-type problem that deals with the scheduling of the university programs. There are two types of university timetabling, the course timetabling and the examination timetabling. Course timetabling deals with the scheduling of courses offered by the university while the examination timetabling deals with the scheduling of examinations. The objective is to obtain a timetable in such a way that sets of constraints were satisfied. Two types of constraints were identified in any timetabling problem, hard constraints for the feasibility and soft constraints for quality. Several methods such as graph coloring and tabu search method are able to solve timetabling problems. Graph coloring is a vertex coloring search process while tabu search is a metaheuristic search that guides a heuristic search process to obtain a better solution. This study aimed to formulate a timetabling system using graph coloring and tabu search method. From the set of soft constraints, the objective function was formulated. The objective function was used to measure the quality of the timetable. Fifty-five feasible timetables were produced, one from graph coloring and the remaining from tabu search method. The timetable obtained from graph coloring serves as a primary timetable. Tabu search was used to enhance the quality of the primary timetable. Manual manipulation was applied to produce these timetables. An algorithm for producing a feasible timetable using graph coloring and tabu search method was designed.

There are no comments on this title.

to post a comment.

Click on an image to view it in the image viewer

Local cover image Local cover image
 
University of the Philippines Mindanao
The University Library, UP Mindanao, Mintal, Tugbok District, Davao City, Philippines
Email: library.upmindanao@up.edu.ph
Contact: (082)295-7025
Copyright @ 2022 | All Rights Reserved