000			02252nam a2200241 4500
001			UPMIN-00000009283
003			UPMIN
005			20230106170546.0
008			230106b |||||||| |||| 00| 0 eng d
040			_aDLC _cUPMin _dupmin
041			_aeng
090			_aLG993.5 2004 _bA64 E44
100	1		_aElipian, Erick Cezar O. _91255
245	0	0	_aUniversity examination timetabling using graph coloring and Tabu search methods / _cErick Cezar O. Elipian
260			_c2004
300			_a46 leaves
502			_aThesis (BS Applied Mathematics) -- University of the Philippines Mindanao, 2004
520	3		_aUniversity 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.
658			_aUndergraduate Thesis _cAMAT200
905			_aFi
905			_aUP
942			_2lcc _cTHESIS
999			_c311 _d311