Ο χρονοπρογραμματισμός (scheduling) μπορεί να οριστεί ως το πρόβλημα εύρεσης μιας βέλτιστης σειράς για την εκτέλεση ενός πεπερασμένου συνόλου λειτουργιών, χωρίς να παραβιάζεται ένα συγκεκριμένο σύνολο κανόνων. Η παρουσα διπλωματική ασχολείται με την υλοποίηση γραφικού περιβάλλοντος για τη γραφική παρουσίαση των δεδομένων του προβλήματος χρονοπρογραμματισμου όπως αναπτύχθηκε για τον διαγώνισμό ITC07. Η διεπαφή παράγει έγκυρα (εφικτά) (για παράδειγμα δεν θα προγραμματίζονται διαφορετικές εξετάσεις στην ίδια περίοδο εφόσον έχουν κοινούς φοιτητές) προγράμματα εξεταστικής και σχεδιασμένα με γνώμονα την διευκόλυνση των φοιτητών (θα παρέχoνται δηλαδή επαρκή χρονικά διαστήματα μεταξύ των εξεταζόμενων μαθημάτων για όλους τους φοιτητές). Το κάθε πρόγραμμα που παράγεται λαμβάνει υπόψη τους εκάστοτε περιορισμούς και συγκροτεί ορθολογικά ένα κατά το δυνατόν βέλτιστο πρόγραμμα.Ο χρήστης μπορεί να τροποποιεί τα δεδομένα του προβλήματος και να ζητά την επαναϋπολογισμό του κόστους προσδοκώντας καλύτερη ποιότητα λύσης. / -

Η εργασία πραγματέυεται τη δημιουργία βοηθητικών εργαλείων για την χρήση δεδομένων από αρχεία xml και την επεξεργασία τους με αλγορίθμους σμήνους για την εξαγωγή συμπερασμάτων. / The current post graduate thesis addresses the issue of school timetabling problem through the usage of PSO algorithms. In order to achieve greater efficiency complementary tool have been designed and developed.

Είναι πολύ συχνή η ανάγκη κατασκευής ωρολογίων προγραμμάτων για εκπαιδευτικούς οργανισμούς, για μέσα μαζικής μεταφοράς, για τεχνικές εταιρίες κ.α. Η κατασκευή ωρολογίων προγραμμάτων (timetabling) εντάσσεται στη γενικότερη κατηγορία προβλημάτων που είναι γνωστά ως προβλήματα χρονοδρομολόγησης (scheduling). Ένα πρόβλημα χρονοδρομολόγησης έχει γενικά σαν σκοπό να τοποθετήσει μέσα στο χρόνο ένα σύνολο από δραστηριότητες δεδομένου ενός συνόλου πόρων που αυτές οι δραστηριότητες χρειάζονται για να πραγματοποιηθούν. Ειδικά για τα σχολικά προγράμματα με τα οποία ασχολείται η παρούσα εργασία πολλές μέθοδοι και αλγόριθμοι έχουν εφαρμοστεί με στόχο την δημιουργία βέλτιστων προγραμμάτων. Παρόλα αυτά δυστυχώς η πράξη αποδεικνύεται να ανατρέπει πολλές από αυτές τις λύσεις. Έτσι η χρήση της μεθόδου των έμπειρων συστημάτων, που δεν φαίνεται να έχει χρησιμοποιηθεί ευρέως στο πρόβλημα αυτό, είναι μια υποψήφια μέθοδος για να μας δώσει πιο γενικά αποδεκτές λύσεις, που να συμβαδίζουν καλύτερα με την πραγματικότητα, αφού βασική τεχνική είναι η προσομοίωση ενός έμπειρου προγραμματιστή. Η παρούσα εργασία ασχολείται με την δημιουργία ενός έμπειρου συστήματος για την σχεδίαση εβδομαδιαίου προγράμματος μαθημάτων για το Ελληνικό Γυμνάσιο. Για την δημιουργία του έμπειρου συστήματος απευθυνθήκαμε σε ειδικούς σχεδίασης προγραμμάτων σε ελληνικά σχολεία (προγραμματιστές) οι οποίοι μας έδωσαν πλήρη περιγραφή των κανόνων και διαδικασιών που χρησιμοποιούν ώστε να εκδοθεί ωρολόγιο πρόγραμμα. Στη συνέχεια έγινε ανάλυση και εξαγωγή των στόχων και των περιορισμών του προβλήματος καθώς επίσης ορίστηκε και ο τρόπος καταχώρησης των δεδομένων. Στη συνέχεια έγινε σχεδιασμός εφαρμογής για εξαγωγή προγραμμάτων του Ελληνικού Γυμνασίου και επιλέχθηκαν οι τεχνολογίες που είναι πιο κατάλληλες για την υλοποίηση της εφαρμογής. Οι τεχνολογίες που εφαρμόσαμε ώστε να επιτευχθεί η υλοποίηση του πληροφοριακού συστήματος έκδοσης ωρολογίου προγράμματος για το Γυμνάσιο ήταν (α) το εργαλείο CLIPS (1) για την πραγμάτωση του έμπειρου συστήματος, (β) η χρήση PHP (3) και MYSQL (4) για την καταχώρηση των βασικών παραμέτρων του προγράμματος με χρήση του WEB, (γ) το εργαλείο PHLIPS (2) για την σύνδεση του CLIPS με PHP, με στόχο την εξαγωγή στο WEB των αποτελεσμάτων. Έτσι δημιουργήθηκε πληροφοριακό σύστημα όπου κάθε προγραμματιστής σχολείου μπορεί να καταχωρήσει τα στοιχεία του σχολείου, των καθηγητών, τις διαθέσιμες ώρες τους κ.α. με την ευκολία του περιβάλλοντος WEB για ένα η περισσότερα σχολεία που έχει αναλάβει. Η χρήση του WEB δίνει την ευκολία διαχείρισης του προγράμματος από οποιοδήποτε σημείο έχει πρόσβαση με το διαδίκτυο και ταυτόχρονα την χρήση γραφικού περιβάλλοντος για επίτευξη καλύτερης διαχείρισης των πληροφοριών του. Επίσης μπορεί ο χρήστης εύκολα με αλλαγή των παραμέτρων να λαμβάνει διαφορετικά αποτελέσματα και να αποφασίζει σύμφωνα με τις ανάγκες του ποια λύση θεωρεί πιο εφικτή με βάση την καθημερινή πρακτική. Η χρήση του CLIPS για επίτευξη έξυπνων έμπειρων συστημάτων και η σύνδεση μέσω του προτύπου ανάπτυξης συστημάτων PHLIPS δίνει μεγάλες δυνατότητες για τον συνδυασμό της τεχνικής νοημοσύνης με τις τεχνολογίες διαδικτύου. Η εφαρμογή δοκιμάστηκε σε αρκετά γνωστά σετ δεδομένων και πραγματικά δίνει αξιόπιστες και ανταγωνιστικές λύσεις με την καινοτομία όμως ότι είναι πιο αποδεκτές στην καθημερινή πρακτική από άλλες που δίνουν άλλες μέθοδοι τεχνικής νοημοσύνης που αναζητούν βέλτιστες λύσεις με βάση απλά ποσοτικοποιημένα κριτήρια όπως το σύνολο των κενών ορών, η καλύτερη επίτευξη των απαιτήσεων των καθηγητών κ.α. / There is a common need for the construction of timetables for educational organizations, public transportation, for construction companies, etc. The construction of timetables (timetabling problem) is part of a general category of problems known as scheduling problems. The task of a scheduling problem generally is to have a set of activities distributed through time given a set of resources which are needed in order to have these activities to be accomplished. This postgraduate thesis deals with a school timetabling problem. A variety of methods and algorithms have been implemented in order to create optimized timetables. Nevertheless, real life has shown that many of these solutions cannot be realistic. Thus the use of expert systems method, which seems not to have often used in such problems, is a good candidate to gives a more realistic and acceptable solutions, given that it tries to simulate the way an expert school timetabling maker works. This Thesis deals with the creation of an expert system that designs weekly timetables for the Greek High School. To create the expert system, we interviewed experts in designing school timetables in Greek schools, who gave us full description of the rules and procedures they use in order to construct a school timetable. Then we analyzed and extracted the objectives and constraints of the problem and we defined the method of storing the data. Then, we developed an application which produces timetables for the Greek High schools. We chose the appropriate technologies needed and were most suitable to construct the application. The technologies we have used to achieve the implementation of a computerized system for exporting timetables for the high school were, (a) the CLIPS programming tool for the creation of the expert system, (b) the PHP and MYSQL to record the key parameters of the program in a WEB environment, (c) the PHLIPS tool for the connection of CLIPS with PHP, to be able to export the results back into the WEB environment. Thus we created a computerized system where every school timetable maker can register the data concerning the school, the teachers, the available hours and dates etc. with the ease of the WEB environment for one or more schools. The potential of using the WEB environment provides the user with ease of managing the program from anywhere with access to the Internet, while using the graphical user interface for obtaining the best data management. We can easily change the parameters to obtain different results and act in accordance with our needs the most feasible solution based on daily practice. Using CLIPS to create an expert system, and the connection through the PHLIPS development standard gives great potential for the combination of artificial intelligence and internet technologies. The application was tested on several well-known data sets and really gives a reliable and competitive solutions but with the innovation, that is more acceptable in daily practice than other methods of artificial intelligence that seek optimal solutions based on simple but politicized criteria such as the total of empty hours ,to meet the requirements of teachers, etc.

Η παρούσα μεταπτυχιακή εργασία πραγματεύεται το πρόβλημα του σχεδιασμού του ωρολογίου προγράμματος μαθημάτων ενός εκπαιδευτικού ιδρύματος και πιο συγκεκριμένα ενός πανεπιστημίου. Λόγω της πολυπλοκότητας και της ύπαρξης πολυάριθμων μεταβλητών και παραμέτρων το πρόβλημα ανήκει στην κατηγορία των NP-complete προβλημάτων, γεγονός που κάνει την εξεύρεση της βέλτιστης λύσης μία πολύ δύσκολη υπόθεση. Η βιβλιογραφική ανασκόπηση έδειξε ότι έχουν προταθεί και εφαρμόζονται πολλές και διαφορετικές μεθοδολογίες επίλυσης του προβλήματος. Οι τεχνικές προέρχονται από πολλούς και διαφορετικούς τομείς όπως για παράδειγμα το μαθηματικό προγραμματικό, τον ακέραιο γραμμικό προγραμματισμό, τις μετα-ευρετικές μεθόδους, αλλά και από τον χώρο της Τεχνητής Νοημοσύνης. Η μέθοδος επίλυσης, που προτείνεται από την παρούσα εργασία, είναι η πολυκριτηριακή ανάλυση βασιζόμενη στον συναινετικό προγραμματισμό (compromise programming). Η εφαρμογή της μεθόδου σε δεδομένα προβλημάτων ωρολογίου προγραμματισμού, είχε πολύ ικανοποιητικά αποτελέσματα, καθώς προεκύψαν ποιοτικά ωρολόγια προγράμματα, που ικανοποιούσαν όλους τους περιορισμούς. / The timetabling problem constists in scheduling a sequence of lectures between teachers and students in a prefixed period of time, satisfying a set of constraints of various type. Due to the complexity and the existence of many variables and parameters, the problem belongs in the category of NP-complete problems, fact that makes the discovery of an optimal solution, a very difficult affair. The bibliographic search, showed that have been proposed and are applied many and different solving techniques, which are based on Mathematical programming (Integer Linear Programming), on Graph Colouring, on Meta-Heuristics Methods, on Multicriteria approaches, on Case-based approaches, but also belonging to Artificial Intelligence. In this paper, the multicriteria approach based on Compromise programming is suggested. The application of technique in timetable data of an educational institute, had very good results, and provided qualitative timetables, satisfying all constraints.

Το πρόβλημα του χρονοπρογραμματισμού είναι πολύπλευρο και δύσκολο στη σαφή αλγοριθμική του επίλυση. Ιδιαίτερα ο χρονοπρογραμματισμός εξετάσεων είναι ένα συνεχές πρόβλημα που, όπως αποδεικνύουμε, είναι πολύ δύσκολο στη γρήγορη και αποδοτική αντιμετώπισή του. Στην παρούσα διπλωματική αφού περιγράψουμε το πρόβλημα και τις ιδιαιτερότητες που παρουσιάζονται στο ελληνικό πανεπιστήμιο, αναλύουμε γενικότερα το θέμα του timetabling και τους βασικούς αλγόριθμους επίλυσης τέτοιων προβλημάτων. Ακολούθως προχωρούμε στην παρουσίαση της διαδικτυακής εφαρμογής χρονοπρογραμματισμού εξετάσεων που υλοποιήσαμε για χρήση από το τμήμα Ηλεκτρολόγων Μηχανικών και Τεχνολογίας Υπολογιστών του Πανεπιστημίου Πατρών. Η εφαρμογή αυτή αναπτύχθηκε με σύγχρονες τεχνικές και εργαλεία ανάπτυξης λογισμικού και, όντας ανοιχτού κώδικα, κατασκευάστηκε ως πλατφόρμα ανάπτυξης και σύγκρισης αλγορίθμων timescheduling. / The timescheduling problem is multifaceted and difficult to define an algorithmic solution. Especially the exams timetabling is a constant problem for universities and, as we prove, it is very difficult to quickly and efficiently deal with it.In this thesis, after describing the problem and the characteristics presented in the Greek university, we analyze the general issue of timetabling and the basic algorithms to solve such problems.Then we proceed to the presentation of the exam scheduling web application we implemented for use by the Department of Electrical and Computer Engineering, University of Patras. This application was developed with modern tools and techniques of software development and, being open source, was also built as a development and comparison platform for timescheduling algorithms.