Αυτοματοποιημένη δημιουργία προγραμμάτων εξεταστικής περιόδου

Abstract

The development of satisfying exam programs in tertiary education has always been one of the problems that the educational institutes are facing. Many methods were developed to solve this problem; some of them were successful while other did not have the expected results. New perspectives came up in the field, with the development of the Evolutionary Algorithms (EAs). The last three decades, EAs are gaining more and more attention from the scientists in solving difficult and complex problems. The confrontation of the exam-timetabling problem using EAs started with the observation that this problem can be simulated by and transformed into a graph colouring problem, which the EAs were dealing with much success. Thus, the educational scientific community turn their interest to EAs in order to find a solution for this long-standing problem. In this thesis, an effort is being made to develop a solution based on EAs, for the exam-timetabling problem at the department of Informatics, of the Technological Educational Institute of Thessaloniki. For the achievement of qualitatively better results the capability of applying parallel Evolutionary Algorithms is given. The advantages and usability of Parallel EAs is also described in this thesis. Finally, the EA that has been developed was applied in a series of experiments, on test data, and the results were more than encouraging.

Η δηµιουργία ικανοποιητικών προγραµµάτων εξετάσεων, στην τριτοβάθµια εκπαίδευση, ήταν ανέκαθεν ένα από τα προβλήµατα που αντιµετώπιζαν τα ανώτερα εκπαιδευτικά ιδρύµατα. Πολλές µέθοδοι αναπτύχθηκαν, για την επίλυσή του, άλλες µε επιτυχία και άλλες µε όχι και τόσο καλά αποτελέσµατα. Νέες προοπτικές όµως εµφανίστηκαν στο χώρο, παράλληλα µε την ανάπτυξη των Εξελικτικών Αλγορίθµων (ΕΑ) οι οποίοι τις τελευταίες τρείς δεκαετίες κερδίζουν όλο και περισσότερο την προσοχή των επιστηµόνων για την επίλυση δύσκολων και πολύπλοκων προβληµάτων. Η αντιµετώπιση του προβλήµατος του χρονοπρογραµµατισµού των εξετά- σεων από τους εξελικτικούς αλγορίθµους, ήρθε µε την παρατήρηση ότι αυτό το πρόβληµα µπορεί να παροµοιασθεί και να µετατραπεί σε πρόβληµα χρωµα- τισµού ενός γράφου (graph colouring problem), κάτι το οποίο οι ΕΑ αντιµετώ- πιζαν µε επιτυχία. Έτσι λοιπόν η εκπαιδευτική επιστηµονική κοινότητα έστρεψε το ενδιαφέρον της στους ΕΑ για να επιλύσει ένα πάγιο πρόβληµά της. Στην παρούσα εργασία γίνεται µία προσπάθεια ανάπτυξης ενός ΕΑ για την επίλυση αυτού του προβλήµατος στο τµήµα Πληροφορικής του Τεχνολογικού Εκπαιδευτικού Ιδρύµατος της Θεσσαλονίκης. Για την επίτευξη καλύτερων ποιοτικά αποτελεσµάτων δίνεται η δυνατότητα εφαρµογής Παράλληλων ΕΑ, των οποίων τα πλεονεκτήµατα και η χρησιµότητα αναφέρεται στα κείµενα που ακολουθούν. Τέλος, ο ΕΑ που αναπτύχθηκε εφαρµόστηκε σε µία σειρά πειραµάτων, πάνω σε δοκιµαστικά δεδοµένα, και τα αποτελέσµατα που προέκυψαν ήταν κάτι παραπάνω από ενθαρρυντικά.