Ανάπτυξη εξεταστικού ημερολογίου

Abstract

Η κατάρτιση ενός εξεταστικού ημερολογίου σε ένα τριτοβάθμιο εκπαιδευτικό ίδρυμα είναι μία ιδιαίτερα επίπονη διαδικασία για το διοικητικό προσωπικό του πανεπιστημίου ιδιαίτερα όταν η διαδικασία αυτή γίνεται χωρίς κάποια αυτοματοποίηση. Το συγκεκριμένο πρόβλημα ανήκει στην οικογένεια των προβλημάτων χρονοπρογραμματισμού (Scheduling) και ανήκει στην οικογένεια NP – Complete. Η κατάρτιση του εξεταστικού ημερολογίου έχει επιλυθεί με διάφορες τεχνικές προγραμματισμού. Στην παρούσα διπλωματική θα επιλυθεί το πρόβλημα κατάρτισης του εξεταστικού ημερολογίου, με την βοήθεια των αλγορίθμων εξέλιξης (Evolutionary Algorithms). Με την βοήθεια των γενετικών αλγορίθμων έχουν επιλυθεί αρκετά προβλήματα ΝΡ - Complete. Οι αλγόριθμοι αυτοί προσομοιώνουν την βιολογική εξέλιξη των ειδών, σε ένα πρόβλημα προγραμματισμού. Η λύση του προβλήματος που προκύπτει από την εκτέλεση τους, ικανοποιεί τους περιορισμούς που μπορεί να περιέχει το πρόβλημα αλλά μπορεί να μην είναι η βέλτιστη δυνατή. Ο αλγόριθμος που προτείνεται για την επίλυση του εξεταστικού ημερολογίου δίνει ιδιαίτερη έμφαση στην ικανοποίηση των περιορισμών που αφορούν τους φοιτητές και στην επιλογή των αιθουσών και των χρονοθυρίδων με τέτοιο τρόπο ώστε να μην υπάρχει περίπτωση να μην υπάρχουν διαθέσιμες θέσεις για τους φοιτητές που πρόκειται να εξεταστούν. Στο τελευταίο κεφάλαιο ο αλγόριθμος εκτελείται με πραγματικά δεδομένα από το Ελληνικό Ανοικτό Πανεπιστήμιο σε μικρά προβλήματα (όσον αφορά τον αριθμό των μαθημάτων) και παράγει αποδεκτά εξεταστικά ημερολόγια. Σε μεγάλα προβλήματα παρατηρείτε ότι ο γενετικός αλγόριθμος έχει πάρα πολύ μεγάλες απαιτήσεις για υπολογιστική ισχύ, οπότε προτείνετε η εκτέλεση του αλγορίθμου σε Grid υπολογιστές.