Please use this identifier to cite or link to this item: http://hdl.handle.net/10889/9939
Title: Σχεδίαση, ανάπτυξη και εφαρμογή αλγορίθμων υπολογιστικής νοημοσύνης σε προβλήματα εύρεσης βέλτιστου ωρολογίου προγράμματος σε σχολεία δευτεροβάθμιας εκπαίδευσης (school timetabling) και χρονοπρογραμματισμού (scheduling)
Other Titles: Design, implementation and application of computational intelligence algorithms to the school timetabling problem and scheduling
Authors: Τασσόπουλος, Ιωάννης
Keywords: Ωρολόγιο πρόγραμμα
Σχολεία δευτεροβάθμιας εκπαίδευσης
Υπολογιστική νοημοσύνη
Βελτιστοποίηση
Αλγόριθμος σμήνους
Keywords (translated): Timetabling
High school
Computational inteligence
Optimization
Abstract: Ο σκοπός της παρούσας Διδακτορικής Διατριβής είναι η διερεύνηση της συμπε-ριφοράς καινοτόμων αλγορίθμων της Υπολογιστικής Νοημοσύνης, όσον αφορά στην κατασκευή ποιοτικών ωρολογίων προγραμμάτων για σχολεία της Δευτεροβάθμιας Εκπαίδευσης. Είναι γεγονός ότι, τα τελευταία χρόνια, το δύσκολο έργο της κατασκευ-ής ωρολογίων προγραμμάτων σε λίγες μόνο περιπτώσεις επιτελείται χωρίς την βοή-θεια Η/Υ. Συνήθως χρησιμοποιείται κάποιο λογισμικό, το οποίο υλοποιεί έναν αλγό-ριθμο που είναι σε θέση να παράξει ένα ωρολόγιο πρόγραμμα, που να καλύπτει κατά το μεγαλύτερο μέρος τις λειτουργικές ανάγκες ενός σχολείου, μέσα σε διάστημα που κυμαίνεται από λίγα λεπτά έως λίγες ώρες. Στην διεθνή επιστημονική κοινότητα υ-πάρχει συνεχώς αυξανόμενο ενδιαφέρον για την ανάπτυξη νέων αλγορίθμων, οι οποί-οι θα βελτιώνουν διαρκώς την ποιότητα των ωρολογίων προγραμμάτων, θα εκμεταλ-λεύονται τις διαρκώς βελτιούμενες δυνατότητες των Η/Υ και θα στηρίζονται σε νέες θεωρητικές και πρακτικές ανακαλύψεις του χώρου της Πληροφορικής. Υπάρχει συνε-πώς πρόσφορο έδαφος για την ανακάλυψη νέων αλγορίθμων ή/και μεθοδολογιών που επιστρατεύονται για την λύση του αντίστοιχου προβλήματος. Το γεγονός αυτό γέννησε την ιδέα του πειραματισμού με αλγορίθμους της Υπολογιστικής Νοημοσύνης, οι οποίοι δεν έχουν εφαρμοστεί στο παρελθόν για την επίλυση του αντίστοιχου προ-βλήματος και της διερεύνηση της συμπεριφοράς τους. Η μεθοδολογία που ακολουθήθηκε, εν ολίγοις συνοψίζεται στην πρακτική και θεωρητική μελέτη του προβλήματος, στην ανασκόπηση της σχετικής διεθνούς βιβλιο-γραφίας, καθώς και στην επιλογή, τροποποίηση και εφαρμογή ενός καταξιωμένου αλ-γορίθμου σε παρεμφερή προβλήματα, που όμως να μην έχει εφαρμοστεί πριν στο συ-γκεκριμένο πρόβλημα. Επίσης, η μεθοδολογία συνίσταται στην εύρεση ενός αναγνω-ρισμένου συνόλου δεδομένων (data set) που να αντικατοπτρίζει ρεαλιστικές καταστά-σεις και που να έχει ήδη χρησιμοποιηθεί σε προγενέστερες ερευνητικές προσπάθειες. Με αυτόν τον τρόπο, είναι δυνατή η άμεση και δίκαιη σύγκριση των όποιων αποτελε-σμάτων της Διατριβής και η εξαγωγή ασφαλών συμπερασμάτων για την ποιότητα τους, σε πραγματικά προβλήματα. Στην παρούσα Διδακτορική Διατριβή παρουσιάζονται τρείς πρωτότυποι υβριδι-κοί αλγόριθμοι, οι οποίοι επιλύουν το πρόβλημα κατασκευής ωρολογίων προγραμμά-των σχολείων της Δευτεροβάθμιας Εκπαίδευσης κατά σχεδόν βέλτιστο τρόπο. Οι υ-βριδικοί αλγόριθμοι αυτοί βασίζονται στον γνωστό αλγόριθμο Particle Swarm Optimi-zation (PSO). Ο αλγόριθμος PSO μετασχηματίστηκε έτσι ώστε να μπορεί να εφαρμο-στεί στο διακριτό χώρο έρευνας του προβλήματος. Οι τρείς πρωτότυπες εκδοχές που παρουσιάζονται αποτελούν διαδοχικές προσπάθειες και προσεγγίσεις για την επίλυση του School Timetabling προβλήματος. Οι αλγόριθμοι και τα αποτελέσματα που παρή-χθησαν έχουν δημοσιευθεί σε έγκυρα διεθνή περιοδικά. Περισσότερες πληροφορίες για τις δημοσιεύσεις υπάρχουν στην ενότητα «Δημοσιεύσεις που πραγματοποιή-θηκαν στα πλαίσια της παρούσας Διατριβής και συμμετοχή σε Συνέδρια» του Παραρτήματος. Επίσης, με εργαλείο τον Μεικτό Ακέραιο Προγραμματισμό (MIP), επι-χειρήθηκε η εύρεση των ανώτατων ποιοτικών ορίων των ωρολογίων προγραμμάτων που αντιστοιχούν στα αντίστοιχα δεδομένα που επελέγησαν. Τέλος, τα παραχθέντα αποτελέσματα συγκρίνονται με αντίστοιχα άλλων ερευνητών καθώς και με αυτά που παράγει το λογισμικό aSc–Timetables. Το συγκεκριμένο λογισμικό χρησιμοποιείται ευρέως στα σχολεία της Ελληνικής επικράτειας και όχι μόνο. Όσον αφορά στην καινοτομία της παρούσας Διατριβής και στην συνεισφορά της στην ερευνητική κοινότητα, αυτή συνίσταται στην επιλογή του αλγορίθμου Particle Swarm Optimization (PSO), ο οποίος εφαρμόζεται για πρώτη φορά στο συγκεκριμένο πρόβλημα. Η πρωτότυπη προσαρμογή του PSO, ώστε αυτός να μπορεί να εφαρμο-στεί σε διακριτό χώρο, αποτελεί μια ακόμη καινοτομία. Άλλωστε, το γεγονός ότι, τελι-κά, τα αποτελέσματα που παρήχθησαν είναι μακράν καλύτερα από αντίστοιχα αποτε-λέσματα προγενέστερων ερευνητικών προσπαθειών, συνηγορούν υπέρ της καινοτο-μίας της Διατριβής. Επίσης, για πρώτη φορά επιχειρείται η εύρεση των τελικών βέλτι-στων ποιοτικών ορίων των ωρολογίων προγραμμάτων, τα οποία βασίζονται στα αρ-χεία εισόδου του data set το οποίο επελέγη και το οποίο έχει χρησιμοποιηθεί αρκετές φορές από άλλους ερευνητές. Η προσπάθεια εύρεσης των τελικών βέλτιστων ορίων στηρίζεται σε ακριβείς μεθόδους και μάλιστα σε μεθόδους του Μεικτού Ακέραιου Προ-γραμματισμού (MIP), όπως αναφέρθηκε παραπάνω. Τέλος, θα πρέπει να αναφερθεί ότι, στα πλαίσια Διπλωματικής εργασίας, αναπτύχθηκε ένα ολοκληρωμένο Πληροφο-ριακό σύστημα, το οποίο βασίζεται στους αλγορίθμους οι οποίοι αναπτύχθηκαν για τους σκοπούς της παρούσας Διατριβής, και δίνει πλέον την δυνατότητα σε σχολεία της Ελληνικής επικράτειας να δημιουργήσουν ωρολόγιο πρόγραμμα που θα καλύπτει τις ανάγκες τους και μάλιστα χωρίς χρέωση. Το γεγονός της δημιουργίας του εν λόγω Πληροφοριακού Συστήματος αναδεικνύει την πρακτική αξία της Διδακτορικής διατρι-βής.
Abstract (translated): The main topic of this thesis is the design and implementation of algorithms for solving the school timetabling problem in a feasible and efficient way. In particular, focus is given in the well-known Particle Swarm Optimization (PSO) algorithm, which is modified so as to fit the specific aspects of the problem’s discrete space, while en-riched with novel ideas and techniques. It is known, for several decades, that the timetabling problems, in their general form, belong to the NP–Hard class. Consequently, finding an exact algorithm for solving timetabling problems in an affordable amount of time is rather impossible when the size of these problems is of a great magnitude. When facing such a situa-tion, one alternative resolution is implementing Computational Intelligence which is able to produce near optimal solutions in a reasonable amount of time by employing the set of algorithms it includes. Therefore, the first chapter is devoted to the hard problems in general and the definition of Computational Intelligence. The second chapter deals with the timetabling problem as it appears in the Academic world: the Exam Timetabling and University Course Timetabling. The third chapter focuses ex-clusively on the school timetabling problem in detail. The fourth chapter states the description of the Particle Swarm Optimization (PSO) algorithm. The fifth chapter presents the characteristics of the instances used for benchmarking the developed algorithms. These instances represent real life situations of the Greek high school actuality. In addition, at this chapter a novel technique based on Mixed Integer Pro-gramming is introduced in order to either optimally solve or produce lower bounds for the aforementioned instances. In the sixth chapter, three novel algorithms are pro-posed for solving the school timetabling problem. In the seventh and final chapter, the performance of the novel algorithms is studied while some open issues and di-rections for farther research are introduced. The easy and simple conclusion of this thesis is that Particle Swarm Optimization (PSO), which is applied for the first time, is an excellent and promising alternative in solving the school timetabling problem.
Appears in Collections:Τμήμα Διοίκησης Επιχειρήσεων Αγροτικών Προϊόντων και Τροφίμων (ΔΔ)

Files in This Item:
File Description SizeFormat 
PhD Tassopoulos.pdf3.17 MBAdobe PDFView/Open


This item is licensed under a Creative Commons License Creative Commons