Χρονοδρομολόγηση μέσω βελτιστοποίησης
Loading...
Date
2025-10-10
Authors
Θεοφιλογιαννάκος, Γεώργιος
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Στο αρχικό κεφάλαιο της παρούσας εργασίας, δίνεται έμφαση στον τρόπο με τον οποίο σχεδιάζονται και οργανώνονται τα μαθήματα σε ένα πανεπιστημιακό τμήμα, με ιδιαίτερη προσοχή στη διαδικασία κατανομής των καθηγητών, των αιθουσών διδασκαλίας και των χρονικών περιόδων. Η χειροκίνητη διαχείριση αυτής της διαδικασίας αποδεικνύεται ιδιαίτερα χρονοβόρα, ενώ είναι ευάλωτη σε σφάλματα, καθώς απαιτεί τη συνδυαστική ενσωμάτωση πολλών παραμέτρων και προτιμήσεων από διαφορετικούς εμπλεκόμενους. Το πρόβλημα αυτό κατατάσσεται στην κατηγορία των NP-hard προβλημάτων, γεγονός που σημαίνει ότι είναι εξαιρετικά περίπλοκο και δύσκολο να επιλυθεί με συμβατικές μεθόδους.
Στο επόμενο κεφάλαιο, παρουσιάζονται αναλυτικά προηγούμενες προσπάθειες και μέθοδοι που έχουν εφαρμοστεί για τη βελτιστοποίηση και τον προγραμματισμό μαθημάτων. Η προσέγγιση περιλαμβάνει τόσο τη θεωρητική ανάλυση όσο και την πρακτική εφαρμογή, ενώ εξετάζονται συστήματα λήψης αποφάσεων και τεχνικές βελτιστοποίησης που έχουν χρησιμοποιηθεί για την επίλυση αντίστοιχων προβλημάτων στο παρελθόν.
Το Κεφάλαιο 3 παρουσιάζει τη μαθηματική διατύπωση του προβλήματος χρονοπρογραμματισμού. Περιγράφονται τα βασικά δεδομένα και η προ-επεξεργασία (διακριτοποίηση χρόνου, κανονικοποίηση διάρκειας μαθημάτων, διαθεσιμότητες καθηγητών) και εισάγεται η έννοια των υποψηφίων μπλοκ ως συμπαγών χρονοθυρίδων. Ορίζονται δείκτες δυνητικών αναθέσεων και οι δυαδικές μεταβλητές απόφασης x που ενεργοποιούν μία (και μόνο μία) έγκυρη ανάθεση ανά μάθημα. Οι σκληροί περιορισμοί διασφαλίζουν μοναδικότητα, μη σύγκρουση αιθουσών και καθηγητών, ενσωματωμένη διαθεσιμότητα και αποφυγή πλεονασμών. Η αντικειμενική συνάρτηση ελαχιστοποιεί σταθμισμένες ποινές ποιότητας. Ακολουθούν ανάλυση μεγέθους και πολυπλοκότητας, ιδιότητες ακεραιότητας, στρατηγικές ανακατασκευής εφικτών λύσεων, διαγνωστικοί έλεγχοι και συζήτηση ισοδυναμιών λύσεων.
Το Κεφάλαιο 4 παρουσιάζει τη συνολική πειραματική ροή από την οργάνωση των δεδομένων μέχρι την αξιολόγηση των λύσεων. Οι είσοδοι κωδικοποιούνται σε JSON αρχεία με τυποποιημένα πεδία για καθηγητές, μαθήματα, διαθέσιμες χρονοθυρίδες και αίθουσες· εφαρμόζονται έλεγχοι συνέπειας και πληρότητας. Ο κώδικας Python υλοποιεί διαδοχικά: φόρτωση και επικύρωση, κανονικοποίηση διαθεσιμοτήτων, παραγωγή υποψηφίων block assignments, upstream ελέγχους εφικτότητας και κατασκευή μοντέλου MILP. Ακολουθεί επίλυση με ρυθμίσεις (π.χ. time limit, gap), εξαγωγή των επιλεγμένων αναθέσεων, δημιουργία πινάκων/οπτικοποιήσεων και στατιστικών κάλυψης. Τέλος, εξετάζονται οι καταστάσεις του solver και καταγράφονται τα αποτελέσματα για περαιτέρω ανάλυση στο επόμενο κεφάλαιο.
Στο πέμπτο και τελευταίο κεφάλαιο, η εργασία καταλήγει στο συμπέρασμα ότι η ενσωμάτωση τεχνικών βελτιστοποίησης μπορεί να συμβάλλει σημαντικά στη βελτίωση της ακρίβειας και της αποτελεσματικότητας του προγραμματισμού μαθημάτων. Προτείνονται επίσης κάποιες πιθανές επεκτάσεις, όπως η ενσωμάτωση περισσότερων παραμέτρων και η ανάπτυξη πιο εξελιγμένων αλγορίθμων. Οι προτάσεις αυτές αποσκοπούν στην αντιμετώπιση πιο πολύπλοκων και ρεαλιστικών σεναρίων.
Τέλος, στο link που ακολουθεί: https://drive.google.com/drive/folders/1lpo5p4mUbHr-55F5qFOVjwiyT7lqrP1R?usp=sharing περιλαμβάνονται όλοι οι κώδικες που αναπτύχθηκαν κατά τη διάρκεια της εργασίας πριν από τη δημιουργία του τελικού αλγορίθμου.
Description
Keywords
Xρονοδρομολόγηση, Βελτιστοποίηση