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

Abstract

The main topic of this thesis is the design and implementation of algorithms forsolving the school timetabling problem in a feasible and efficient way. In particular,focus is given in the well-known Particle Swarm Optimization (PSO) algorithm, whichis modified so as to fit the specific aspects of the problem’s discrete space, while enrichedwith novel ideas and techniques.It is known, for several decades, that the timetabling problems, in their generalform, belong to the NP–Hard class. Consequently, finding an exact algorithm for solvingtimetabling problems in an affordable amount of time is rather impossible whenthe size of these problems is of a great magnitude. When facing such a situation, onealternative resolution is implementing Computational Intelligence which is able to producenear optimal solutions in a reasonable amount of time by employing the set ofalgorithms it includes. Therefore, the first chapter is devoted to the hard problems ingeneral and the definition of Computational Intelligence. The second chapter dealswith the timetabling problem as it appears in the Academic world: the Exam Timetablingand University Course Timetabling. The third chapter focuses exclusively on theschool timetabling problem in detail. The fourth chapter states the description of theParticle Swarm Optimization (PSO) algorithm. The fifth chapter presents the characteristicsof the instances used for benchmarking the developed algorithms. These instancesrepresent real life situations of the Greek high school actuality. In addition, atthis chapter a novel technique based on Mixed Integer Programming is introduced inorder to either optimally solve or produce lower bounds for the aforementioned instances.In the sixth chapter, three novel algorithms are proposed for solving theschool timetabling problem. In the seventh and final chapter, the performance of the novel algorithms is studied while some open issues and directions for farther researchare introduced. The easy and simple conclusion of this thesis is that Particle SwarmOptimization (PSO), which is applied for the first time, is an excellent and promisingalternative in solving the school timetabling problem.

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