Σχεδίαση, ανάπτυξη και εφαρμογή αλγορίθμων υπολογιστικής νοημοσύνης σε προβλήματα εύρεσης βέλτιστου ωρολογίου προγράμματος σε σχολεία δευτεροβάθμιας εκπαίδευσης (school timetabling) και χρονοπρογραμματισμού (scheduling)
Authors: Τασσόπουλος Ιωάννης 
Published: September 2021

Ο σκοπός της παρούσας Διδακτορικής Διατριβής είναι η διερεύνηση της συμπεριφοράς καινοτόμων αλγορίθμων της Υπολογιστικής Νοημοσύνης, όσον αφορά στην κατασκευή ποιοτικών ωρολογίων προγραμμάτων για σχολεία της Δευτεροβάθμιας Εκπαίδευσης. Είναι γεγονός ότι, τα τελευταία χρόνια, το δύσκολο έργο της κατασκευής ωρολογίων προγραμμάτων σε λίγες μόνο περιπτώσεις επιτελείται χωρίς την βοήθεια Η/Υ. Συνήθως χρησιμοποιείται κάποιο λογισμικό, το οποίο υλοποιεί έναν αλγόριθμο που είναι σε θέση να παράξει ένα ωρολόγιο πρόγραμμα, που να καλύπτει κατά το μεγαλύτερο μέρος τις λειτουργικές ανάγκες ενός σχολείου, μέσα σε διάστημα που κυμαίνεται από λίγα λεπτά έως λίγες ώρες. Στην διεθνή επιστημονική κοινότητα υπάρχει συνεχώς αυξανόμενο ενδιαφέρον για την ανάπτυξη νέων αλγορίθμων, οι οποίοι θα βελτιώνουν διαρκώς την ποιότητα των ωρολογίων προγραμμάτων, θα εκμεταλλεύονται τις διαρκώς βελτιούμενες δυνατότητες των Η/Υ και θα στηρίζονται σε νέες θεωρητικές και πρακτικές ανακαλύψεις του χώρου της Πληροφορικής. Υπάρχει συνεπώς πρόσφορο έδαφος για την ανακάλυψη νέων αλγορίθμων ή/και μεθοδολογιών που επιστρατεύονται για την λύση του αντίστοιχου προβλήματος. Το γεγονός αυτό γέννησε την ιδέα του πειραματισμού με αλγορίθμους της Υπολογιστικής Νοημοσύνης, οι οποίοι δεν έχουν εφαρμοστεί στο παρελθόν για την επίλυση του αντίστοιχου προβλήματος και της διερεύνηση της συμπεριφοράς τους.Η μεθοδολογία που ακολουθήθηκε, εν ολίγοις συνοψίζεται στην πρακτική και θεωρητική μελέτη του προβλήματος, στην ανασκόπηση της σχετικής διεθνούς βιβλιογραφίας,καθώς και στην επιλογή, τροποποίηση και εφαρμογή ενός καταξιωμένου αλγορίθμου σε παρεμφερή προβλήματα, που όμως να μην έχει εφαρμοστεί πριν στο συγκεκριμένο πρόβλημα. Επίσης, η μεθοδολογία συνίσταται στην εύρεση ενός αναγνωρισμένου συνόλου δεδομένων (data set) που να αντικατοπτρίζει ρεαλιστικές καταστάσεις και που να έχει ήδη χρησιμοποιηθεί σε προγενέστερες ερευνητικές προσπάθειες.Με αυτόν τον τρόπο, είναι δυνατή η άμεση και δίκαιη σύγκριση των όποιων αποτελεσμάτων της Διατριβής και η εξαγωγή ασφαλών συμπερασμάτων για την ποιότητα τους, σε πραγματικά προβλήματα.Στην παρούσα Διδακτορική Διατριβή παρουσιάζονται τρείς πρωτότυποι υβριδικοί αλγόριθμοι, οι οποίοι επιλύουν το πρόβλημα κατασκευής ωρολογίων προγραμμάτων σχολείων της Δευτεροβάθμιας Εκπαίδευσης κατά σχεδόν βέλτιστο τρόπο. Οι υβριδικοί αλγόριθμοι αυτοί βασίζονται στον γνωστό αλγόριθμο Particle Swarm Optimization(PSO). Ο αλγόριθμος PSO μετασχηματίστηκε έτσι ώστε να μπορεί να εφαρμοστεί στο διακριτό χώρο έρευνας του προβλήματος. Οι τρείς πρωτότυπες εκδοχές που παρουσιάζονται αποτελούν διαδοχικές προσπάθειες και προσεγγίσεις για την επίλυση του School Timetabling προβλήματος. Οι αλγόριθμοι και τα αποτελέσματα που παρήχθησαν έχουν δημοσιευθεί σε έγκυρα διεθνή περιοδικά. Περισσότερες πληροφορίες για τις δημοσιεύσεις υπάρχουν στην ενότητα «Δημοσιεύσεις που πραγματοποιήθηκαν στα πλαίσια της παρούσας Διατριβής και συμμετοχή σε Συνέδρια» του Παραρτήματος. Επίσης, με εργαλείο τον Μεικτό Ακέραιο Προγραμματισμό(MIP), επιχειρήθηκε η εύρεση των ανώτατων ποιοτικών ορίων των ωρολογίων προγραμμάτων που αντιστοιχούν στα αντίστοιχα δεδομένα που επελέγησαν. Τέλος,τα παραχθέντα αποτελέσματα συγκρίνονται με αντίστοιχα άλλων ερευνητών καθώς και με αυτά που παράγει το λογισμικό aSc–Timetables. Το συγκεκριμένο λογισμικό χρησιμοποιείται ευρέως στα σχολεία της Ελληνικής επικράτειας και όχι μόνο.Όσον αφορά στην καινοτομία της παρούσας Διατριβής και στην συνεισφορά της στην ερευνητική κοινότητα, αυτή συνίσταται στην επιλογή του αλγορίθμου ParticleSwarm Optimization (PSO), ο οποίος εφαρμόζεται για πρώτη φορά στο συγκεκριμένο πρόβλημα. Η πρωτότυπη προσαρμογή του PSO, ώστε αυτός να μπορεί να εφαρμοστεί σε διακριτό χώρο, αποτελεί μια ακόμη καινοτομία. Άλλωστε, το γεγονός ότι, τελικά,τα αποτελέσματα που παρήχθησαν είναι μακράν καλύτερα από αντίστοιχα αποτελέσματα προγενέστερων ερευνητικών προσπαθειών, συνηγορούν υπέρ της καινοτομίας της Διατριβής. Επίσης, για πρώτη φορά επιχειρείται η εύρεση των τελικών βέλτιστων ποιοτικών ορίων των ωρολογίων προγραμμάτων, τα οποία βασίζονται στα αρχεία εισόδου του data set το οποίο επελέγη και το οποίο έχει χρησιμοποιηθεί αρκετές φορές από άλλους ερευνητές. Η προσπάθεια εύρεσης των τελικών βέλτιστων ορίων στηρίζεται σε ακριβείς μεθόδους και μάλιστα σε μεθόδους του Μεικτού Ακέραιου Προγραμματισμού (MIP), όπως αναφέρθηκε παραπάνω. Τέλος, θα πρέπει να αναφερθεί ότι, στα πλαίσια Διπλωματικής εργασίας, αναπτύχθηκε ένα ολοκληρωμένο Πληροφοριακό σύστημα, το οποίο βασίζεται στους αλγορίθμους οι οποίοι αναπτύχθηκαν για τους σκοπούς της παρούσας Διατριβής, και δίνει πλέον την δυνατότητα σε σχολεία της Ελληνικής επικράτειας να δημιουργήσουν ωρολόγιο πρόγραμμα που θα καλύπτει τις ανάγκες τους και μάλιστα χωρίς χρέωση. Το γεγονός της δημιουργίας του εν λόγω Πληροφοριακού Συστήματος αναδεικνύει την πρακτική αξία της Διδακτορικής διατριβής.