Open Access Open Access  Restricted Access Subscription or Fee Access

Significance of Heuristics in Getting Optimal Solution for Class Timetabling

M. Nandhini, Dr. S. Kanmani

Abstract


Timetabling means scheduling activities to time slots in an order by satisfying hard constraints and soft constraints. Hard constraints should be satisfied but the violations of soft constraints to be minimized. This problem can be done in Artificial Intelligence or Operations Research domain. Class Timetabling of Undergraduate Science courses of Pondicherry University was implemented using Steepest –Ascent Hill Climbing algorithm and is compared with the proposed approach with heuristics for class timetabling implementation. By analyzing the results obtained in both the methods, significance of applying heuristics to get the optimal solution has been established.


Keywords


constraints, heuristics, states apace, optimal soluiton.

Full Text:

PDF

References


Edmund Burke, Yuri Bykov, James Newall, Sanja Petrovic, “A Time-Predefined Approacto Course Timetabling” , Yugoslav Journal of Operations Research Iiisn 0354-0243, Vol 13, 139-151 , 2003.

A. Schaerf, “A Survey of Automated Timetabling ”, SpringerLink Netherlands, ISSN 0269-2821, Vol 13, Number 2 , 1999.

Hana Rudov_a1 and Keith Murray, “University Course Timetabling with Soft Constraints”, LNCS, ISSN 0302-9743 , Vol. 2740,2003.

Masanori Horio1 Atsuo ,”Application to a University Course Timetabling Problem by a General Project Scheduler”, 7th International Symposium on Operations Research and Its Applications (ISORA’08), pp. 266–273,2008.

Abdelaziz Dammaki Abdelkarim Elloum Hichem Kamoun Jacques A.Ferland, “ Course Timetabling At a Tunisan Univesity: A Case Study” ,J Syst Sci Syst Eng , Vol. 17(3): 334-352 ISSN: 1004-3756 (Paper) 1861-9576 , Sep 2008.

Salwani Abdullah Edmund K. Burke Barry McCollum,“Using a Randomised Iterative Improvement Algorithm with Composite neighbourhood Structures for the University Course Timetabling Problem.”, Springer US,ISSN 1387-666X , Vol. 39, pp. 153-169,2007.

E K. Burke, D. de Werra and J. H. Kingston , “Applications to Timetabling,”, In: J.Gross and J.Yellan(eds). The Handbook of Graph Theory, Chapman Hall/CRC Press, pp. 445-474. ,2004.

E. K. Burke and J. P. Newall : “Enhancing Timetable Solutions with Local Search Methods.”, LNCS, vol. 2740, pp. 195--206. Springer Berlin, Heidelberg, 2003.

Wikipedia , Hill Climbing , http://en.wikipedia.org/wiki/Hillclimbing

E.K. Burke, J.P.Newall , “ Solving Examination Timetabling Problems through Adaption of Heuristic Orderings” , In Annals of Operations Research,pp. 129, 107-134, Netherland., 2004.

Andrea Schaerf , “Tabu Search techniques for large High-School Timetabling problem ”, Netherlands, 1996

Rong Qu, Edmund Burke, Barry McCollum ,Liam T.G. Merlot and Sau Y. Lee , “ A Survey of Search Methodologies and Automated Approaches for Examination Timetabling ”, In Computer Science Technical Report No. NOTTCS-TR, 2006.

Rhydian Lewis, Ben Paechter, Olivia Rossi-Doria , “Metaheuristics for University Course Timetabling ” , Springer,Vol. 49, ISBN 978-3-540-48584-1_9,pp. 237-272,2007.

Edmund K. Burke , Barry Mccollu, Amnon Meisels, Sanja Petrovic Qui, “A Graph- Based Hyper-Heuristic for Educational Timetabling Problems”, Journal of Operational Research, 176 pp- 177-192, 2007.

Abu Bakar Md Sultan, Ramlan Mahmud, Md Naisr Sulaiman, Md Rizam Abu bakar, “Measuring Metaheuristics Performance over Timetabling Problem Instances Using Fitness Distance Correlation Method ”, IJCSNS, Vol. 6, NO.6 , June. 2006.


Refbacks

  • There are currently no refbacks.