The present thesis considers the University Course Timetabling Problem (UCTP). Initially, the general classes of timetabling problems are presented and subsequently the description of the specific problem as well as its algorithmic complexity is discussed. Furthermore, several solution approaches are presented and special attention is given on analyzing the soft and the hard constraints pertaining to the problem. However, the focus of the thesis is on UCTP solution approaches that are based on decomposition methods rather than linear programming monolithic models.
(EL)
Στην παρούσα διπλωματική εργασία, αναφέρεται καταρχήν, τι είναι το UCTP, όπως επίσης παρουσιάζονται γενικές κατηγορίες προβλημάτων χρονοπρογραμματισμού. Παράλληλα, γίνεται καταγραφή της πολυπλοκότητας που έχει το UCTP, καθώς και ακριβής περιγραφή του προβλήματος. Έπειτα, παρατίθενται διάφορες μέθοδοι επίλυσης του προβλήματος. Επίσης, γίνεται αναφορά, στους ανελαστικούς και ελαστικούς περιορισμούς, που συνθέτουν το πρόβλημα. Τελικά, όμως, και σε αυτό εστιάζει η εργασία, γίνεται αναφορά στις προσπάθειες επίλυσης του UCTP με γραμμικό προγραμματισμό, όχι με μονολιθικό μοντέλο, αλλά, μέσω της αποσύνθεσής του σε επιμέρους προβλήματα.
(EL)
University of Patras
