Ο σύγχρονος κόσμος των δικτύων και του internet απαιτεί πολύ υψηλές ταχύτητες διασυνδέσεων στα διάφορα δίκτυα. Ξεκινώντας ακόμα και από τα οικιακά δίκτυα και τα τοπικά δίκτυα (LAN), στα πανεπιστημιακά δίκτυα (campus networks), στα μητροπολιτικά δίκτυα (MAN), στα δίκτυα ευρύτερης περιοχής (WAN) και στα δίκτυα κορμού του internet (core networks). Σε όλα αυτά τα δίκτυα χρησιμοποιούνται κατά κόρον μεταγωγείς (switches) και δρομολογητές (routers) προκειμένου να μεταφέρουν την δικτυακή πληροφορία από την αφετηρία της στον προορισμό της διασχίζοντας πληθώρα άλλων δικτύων. Πυρήνα των μεταγωγέων και των δρομολογητών αποτελεί ο χρονοπρογραμματιστής, ένας αλγόριθμος δηλαδή υλοποιημένος στο hardware της εκάστοτε συσκευής, που αποφασίζει την προώθηση της πληροφορίας από την είσοδό της στην έξοδό της, αφού προηγουμένως έχει καθοριστεί με άλλο μηχανισμό η θύρα εξόδου της πληροφορίας. Η σημασία του χρονοπρογραμματιστή γίνεται φανερή από την πληθώρα προβλημάτων που πρέπει να επιλύσει. Επιλεκτικά, κάποια από τα προβλήματα είναι ο ανταγωνισμός εισόδων για την ίδια έξοδο, το ταίριασμα εισόδων – εξόδων, η ελάχιστη δυνατόν καθυστέρηση στην διερχόμενη πληροφορία, η σταθερότητα λειτουργίας, η μεγιστοποίηση της διαμεταγωγής (throughput), η δικαιοσύνη στην εξυπηρέτηση εισόδων και εξόδων, κ.α. Στην παρούσα διπλωματική παρουσιάζεται η οικογένεια αλγορίθμων χρονοπρογραμματισμού ROLM (Randomized On-Line Matching), η οποία υλοποιεί τυχαιότητα με αποδοτικό και αποτελεσματικό τρόπο. Οι επιδόσεις αυτές φαίνονται στη μικρή καθυστέρηση στην προώθηση πακέτων (packet forwarding), επιτυγχάνοντας έτσι υψηλή διαμεταγωγή (throughput) και στα χαρακτηριστικά δικαιοσύνης που προσφέρουν, σε σχέση με τις υπάρχουσες ανταγωνιστικές υλοποιήσεις, που δεν χρησιμοποιούν τυχαιότητα αλλά ντετερμινιστικές μεθόδους απόφασης. Τα αποτελέσματα αυτά οφείλονται στο βασικό αλγόριθμο της οικογένειας ROLM, τον Ranking, o οποίος υπολογίζει μέγιστο ταίριασμα εισόδων – εξόδων. Οι αλγόριθμοι αυτοί επιλέγουν τυχαία εισόδους για προώθηση στις εξόδους που ζητούν, επιλογή η οποία μπορεί να οδηγήσει σε χρονοπρογραμματιστές υψηλών ταχυτήτων, ταχύτητες που ορίζει η εκάστοτε τεχνολογία υλοποίησης και η ταχύτητα των συνδέσμων δικτύου. Ο αλγόριθμος Ranking υλοποιείται σε software και σε hardware (υλικό), στην πλατφόρμα FPSLIC της ATMEL. Η πλατφόρμα αυτή περιέχει έναν 8μπιτο επεξεργαστή, τον AVR, και ένα προγραμματιζόμενο πίνακα πυλών (FPGA) στην ίδια πλακέτα κατασκευασμένα με την ίδια τεχνολογία. Έτσι, οι μετρήσεις των δύο υλοποιήσεων είναι συγκρίσιμες. Το πρόγραμμα που αναπτύσσεται, τόσο για την software όσο και για την hardware υλοποίηση, δέχεται ως παράμετρο το μέγεθος του μεταγωγέα. Έτσι, μετρώνται και συγκρίνονται χαρακτηριστικά όπως η ταχύτητα, ο χρόνος απόφασης, η επιφάνεια και το πλήθος θυρών I/O, για μεταγωγείς μεγέθους τεσσάρων εισόδων και τεσσάρων εξόδων (4x4), 8x8, 16x16 και 32x32. / --

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

Σκοπός της διπλωματικής εργασίας είναι η ανάπτυξη εργαλείου το οποίο θα δέχεται ως είσοδο C πρόγραμμα και θα βρίσκει όλη τη πληροφορία η οποία σχετίζεται με την επαναχρησιμοποίηση των δεδομένων. Τα δεδομένα αφορούν πίνακες μέσα σε βρόχους. Η επαναχρησιμοποίηση δεδομένων χωρίζεται σε τρεις κατηγορίες: α) Εύρεση της επαναχρησιμοποίησης για κάθε πίνακα ξεχωριστά. β) Εύρεση της επαναχρησιμοποίησης στοιχείων πίνακα που χρησιμοποιούνται σε διάφορες εκφράσεις. γ) Εύρεση χρήσης στοιχείων μεταξύ διαφορετικών πινάκων στην ίδια έκφραση. Η εύρεση των χαρακτηριστικών της επαναχρησιμοποίησης χρησιμεύει για την εύρεση αποδοτικού χρονοπρογραμματισμού (scheduling) του προγράμματος το οποίο θα έχει καλύτερη τοπικότητα (data locality). Η επαναχρησιμοποίηση δεδομένων εφαρμόζεται στο πρόβλημα πολλαπλασιασμού πίνακα επί διάνυσμα. Συμβατικές και μη τεχνικές υλοποίησης του προβλήματος έχουν συγκριθεί με τη προτεινόμενη. Η σύγκριση πραγματοποιήθηκε με τον εξομοιωτή SimpleScalar στον οποίο μπορούμε να τροποποιήσουμε την αρχιτεκτονική και σε υπολογιστή Desktop Pentium 4. / -

Το βασικό θέμα της διπλωματικής εργασίας είναι η χρήση μεταευρετικών τεχνικών για την επίλυση ενός συνδυαστικού προβλήματος βελτιστοποίησης. Πιο συγκεκριμένα, ένας μεταευρετικός αλγόριθμος προσομοιωμένης ανόπτησης δημιουργήθηκε προκειμένου να αποκτηθεί το ελάχιστο κόστος λειτουργίας ενός κυκλικού δικτύου διανομής νερού. Η προσομοιωμένη ανόπτηση είναι μία στοχαστική μέθοδος βελτιστοποίησης που μπορεί να ανταποκριθεί καλά σε μεγάλης κλίμακας προβλήματα βελτιστοποίησης διακριτής ή συνδυαστικής μορφής, αλλά στο πρόβλημα που επιλύθηκε Αρχικά παρουσιάζονται τα χαρακτηριστικά και τα επιμέρους στοιχεία των δικτύων διανομής νερού μαζί με τους νόμους της φυσικής που τα διέπουν. Ειδικότερη προσοχή δίνεται στο πιο ακριβό στοιχείο, την αντλία. Στη συνέχεια παρουσιάζεται το EPANET, ένα πακέτο λογισμικού για τη μοντελοποίηση δικτύων ύδρευσης, μαζί με το programmers toolkit που θα επιτρέψει την αλληλεπίδραση μεταξύ Java και του λογισμικού μοντελοποίησης του δικτύου. Στο 6ο κεφάλαιο μία εφαρμογή προτείνεται, ο στόχος της οποίας είναι η ελαχιστοποίηση του κόστους και της κατανάλωσης της ηλεκτρικής ενέργειας. Η εφαρμογή μετά δοκιμάζεται στο πρόβλημα Van Zyl, ένα δίκτυο διανομής νερού μικρής κλίμακας που είναι κατάλληλο για δοκιμές εξαιτίας του γεγονότος ότι πολλές διαμορφώσεις προγράμματος λειτουργίας αντλιών είναι έγκυρες, παρέχοντας έτσι μία μεγάλη ποικιλία προγραμμάτων λειτουργίας. Η μέθοδος της προσομοιωμένης ανόπτησης παρουσιάζεται στη συνέχεια σταδιακά και τα αποτελέσματα απεικονίζονται με τη βοήθεια πινάκων και σχεδιαγραμμάτων. Το τελευταίο κεφάλαιο συζητά γενικά συμπεράσματα που αφορούν νέα πεδία προς αναζήτηση τα οποία θα μπορούσαν να βελτιώσουν τις μεθόδους βελτιστοποίησης των προβλημάτων χρονοπρογραμματισμού αντλιών δικτύων ύδρευσης / The main topic of this diploma thesis is the use of metaheuristics for solving a combinatorial optimization problem. In particular, a simulated annealing metaheuristic was developed to obtain the least cost operation of a looped water distribution network. Simulated annealing is a stochastic optimization method that can work well for large-scale optimization problems that are cast in discrete or combinatorial form, and with the problem solved. First of all water distribution systems’ characteristics and components are stated along with the laws of physics that govern them. Particular attention is given to the most expensive component of all, the pump. Then, EPANET, a public domain, water distribution system modeling software package is presented along with the programmers’ toolkit that will enable the interaction between Java and the network modeling software. In Chapter 6, one application is proposed, whose goal is to minimize electricity cost and consumption. The application will then be tested on the Van Zyl Test Problem, a water distribution system of small scale that is well suited for testing due to the fact that many pump configurations are valid, providing a vast range of configurations. The method of simulated annealing is then presented gradually, and the results will be depicted with the help of plots and tables. The final chapter also discusses general conclusions concerning new fields for research that could improve the optimization techniques for pump scheduling problems.

Η παρούσα διπλωματική εργασία, πραγματεύεται την υλοποίηση ενός περιβάλλοντος εξομοίωσης Grid δικτύων ως μια υπολογιστική πλατφόρμα πάνω στην οποία τίθενται σε σύγκριση κάποιοι scheduling αλγόριθμοι. Η τεχνολογία Grid προϋποθέτει την ύπαρξη ενός δικτύου που κάποιοι από τους κόμβους του διαθέτουν υπολογιστικούς πόρους ενώ κάποιοι χρήστες ζητούν πρόσβαση σε αυτούς. Για τον ομαλό διαμοιρασμό των πόρων απαιτούνται κάποιοι scheduling αλγόριθμοι οι οποίοι λαμβάνοντας υπόψη την διαθεσιμότητα των πόρων, δρομολογούν κατάλληλα τις εργασίες. Σκοπός της εργασίας είναι να παρουσιάσει αποτελέσματα και να συγκρίνει την απόδοση αλγορίθμων και αρχιτεκτονικών χρονοπρογραμματισμού, που μελετήσαμε πάνω στην υπολογιστική πλατφόρμα που υλοποιήθηκε. / This diploma thesis discus the implementation of a Grid network simulation environment, as computational platform in order to compare scheduling algorithms. The Grid technology presupposes a network where some of the nodes … computational resources and some users request access to them. For an efficient distribution of the network resources, some scheduling algorithms are necessary in order to route the tasks taking into consideration the availability of the resources. The objective of this master thesis is to present results and compare the efficiency of scheduling algorithms and architectures tested over the computational platform implemented.

Ο κύριος σκοπός της παρούσας εργασίας είναι να διερευνηθεί η χρήση ενός εναλλακτικού νέου γενετικού αλγορίθμου, που εφαρμόζεται στο ωράριο εργασίας και στον χρονοπρογραμματισμό των αστικών και υπεραστικών λεωφορείων στην Ελλάδα. Φαίνεται ότι η απόδοση επηρεάζεται από διάφορες παραμέτρους, όπως ισχυρούς ή ελαστικούς περιορισμούς, δεδομένου ενός συνόλου των οδηγών λεωφορείων, και ενός συνόλου δρομολογιών προς εκτέλεση. Πιο συγκεκριμένα, η μέθοδος που επιλέχθηκε για τη διεξαγωγή της παρούσας εργασίας είναι μια προσομοίωση των υπεραστικών λεωφορείων της πόλης της Πρέβεζας. Τέλος, τα αποτελέσματα της μελέτης δείχνουν ότι ο συνδυασμός των τεχνικών που παρουσιάστηκαν λειτουργεί αποτελεσματικά και να ξεπερνά όλα τα προηγούμενα μοντέλα σε μια απλή προσομοίωση. / The main target is to expand the usage of an alternative new generic algorithm, that is used in the timetable scheduling of urban and intercity buses in Greece. The performance is influenced by several factors. The method used is a simulation of the intercity buses of the city of Preveza. Finally, the results of the study shows that the combination of the techniques implemented works efficiently and overcomes the previous methods in a simple simulation.

- / The main topic of this thesis is the combination of metaheuristics and other methods for solving combinatorial optimization problems (COPs). In particular, focus is given in a special category of COPs known as timetabling problems. Timetabling problems belong in general to the class of NP-hard problems meaning that exact methods are usually unable to solve problem instances with sizes of practical importance. In the first three chapters optimization problems are analyzed and four major disciplines regarding optimization approaches are examined: Mathematical Programming, Artificial Intelligence, Computational Intelligence and Metaheuristics. Borders are not always clear between them while a recent trend is to hybridize approaches originating from the same or different disciplines. Even with the progress in optimization that occurred during the last decades programming successful optimization application still is an intricate mission. Nevertheless, software developing techniques, open source software and exploitation of the processing power of modern hardware can assist in constructing applications that are expected to be of much benefit for their users. Key ideas of achieving this are described in Chapter 4. The first application, presented in Chapter 5, is a pump scheduling system for a water distribution network. The objective is to achieve a way of operation for the pumps of each reservoir that results in diminished electricity cost. A model of the problem was constructed and the metaheuristic technique of genetic algorithms with the addition of several heuristics solved the problem. The second application, presented in Chapter 6, is the examination timetabling problem for Universities. Educational timetabling problems in general attract much interest from the scientific community. Our approach targeted various models of the examination timetabling problem and constituted by two major phases: construction and improvement. A number of metaheuristics were hybridized (Simulated Annealing, GRASP, VNS, Taboo Search and others) while certain sub-problems were solved using exact methods (Integer Programming). The results that we achieved in known datasets for evaluating the performance of such methods were most promising. In particular, for the publicly available datasets of the second International Timetabling Competition our approach achieved the best published score for 6 out of 8 datasets. The third application, presented in Chapter 7, is the construction of timetables for Greek high schools. A model of the problem that had publicly available problem instances and published results was used. Better results were able to be obtained by reformulating the problem and subsequently using a branch and cut approach implemented using entirely open source software. In summary, successful results of our approaches suggest that metaheuristics and hybridized metaheuristics with other metaheuristic or exact methods appears to be a promising research direction for handling complex combinatorial optimization problems.

Η διπλωµατική εργασία αποτελεί συνέχεια της µελέτης προβληµάτων χρονοπρογραµµατισµού µε αυστηρές προθεσµίες που ξεκίνησε η Αµαλία Στούµπου στην δικιά της διπλωµατική εργασία µε όνοµα "Προβλήµατα Επιτάχυνσης ∆ιεργασιών σε Grid Computing: Αλγόριθµοι και Πολυπλοκότητα". Εξετάζονται προβλήµατα δροµολόγησης διεργασιών σε περισσότερους από έναν, ίδιους µεταξύ τους, επεξεργαστές. ∆ίνονται αλγόριθµοι που λύνουν το πρόβληµα ελαχιστοποίησης του συνολικού χρόνου εκτέλεσης, µε αυστηρές προθεσµίες, αρχικά για 2 και στη συνέχεια για m επεξεργαστές. Οι αλγόριθµοι αυτοί έχουν ψευδοπολυωνυµική πολυπλοκότητα. Στη συνέχεια εξετάζονται προβλήµατα δροµολόγησης και επιτάχυνσης διεργασιών µε ίδιο χρόνο εκτέλεσης, σε περιβάλλοντα µε ίδιους µεταξύ τους επεξεργαστές και δίνονται πολυωνυµικοί αλγόριθµοι που τα λύνουν. Τέλος αναφέρονται συνοπτικά ορισµένα προβλήµατα του ευρύτερου χώρου προϐληµάτων χρονοπρογραµµατισµού που µπορούν να προσεγγιστούν ή να λυθούν µε τεχνικές που εφαρµόστηκαν για τη λύση των προηγούµενων προβληµάτων που αναφέρθηκαν. / This thesis is a continuation of the study of scheduling problems with strict deadlines that begun in the thesis "Προβλήµατα Επιτάχυνσης ∆ιεργασιών σε Grid Computing : Αλγόριθµοι και Πολυπλοκότητα" by Amalia Stoumpou. We study scheduling problems on more than one parallel processors. Algorithms are given that solve the problem of minimizing the makespan with strict deadlines, first for 2 and then for m processors. These algorithms are pseudopolynomial in complexity. We also study problems of scheduling and speedup of processes with the same execution time in parallel processor environments and we give pseudopolynomial algorithms that solve them. Finally, we mention briefly other problems that can be solved or approached using the techniques that we applied to solve the previous problems.

Η παρούσα εργασία αποσκοπεί στη μελέτη του προβλήματος του χρονοπρογραμματισμού γεγονότων, την τοποθέτηση δηλαδή των γεγονότων σε υποδοχείς χρόνου και χώρου, με τη χρήση Γενετικών Αλγορίθμων. Μελετήσαμε τo πρόβλημα του χρονοπρογραμματισμού στην Εκπαίδευση και ειδικότερα σε ένα Πανεπιστήμιο, που εμφανίζεται σε δύο εκδοχές: το πρόβλημα χρονοπρογραμματισμού εξετάσεων και το πρόβλημα χρονοπρογραμματισμού διαλέξεων, καθώς και τα αντίστοιχα πειράματα και τα αποτελέσματα αυτών. Χρησιμοποιώντας το λογισμικό FET που βασίζεται στους Γενετικούς Αλγόριθμους κατασκευάσαμε χρονοδιαγράμματα για το ωρολόγιο πρόγραμμα του Μεταπτυχιακού Προγράμματος του Διατμηματικού του Πανεπιστημίου Πατρών "Μαθηματικά των Υπολογιστών και των Αποφάσεων" των τμημάτων Μαθηματικών και Μηχανικών Η/Υ και Πληροφορικής και παρουσιάσαμε τα αποτελέσματα αυτών. / The aim of this paper is the study of the timetabling problem, meaning the allocation of events in time-slots and space-slots, using Genetic Algorithms. We studied the Education Timetabling problem for a University which appears in two versions, timetabling of exams and timetabling of lectures and its corresponding experiments and results. Using the open source free software FET which is based on the Genetic Algorithms, we scheduled timetables for the weekly program of Postgraduate Program of University of Patras "Mathematics of Computers and Decision" in which participate two departments, the department of Mathematics and the department of Engineering Computing and Information Technology and we presented the results of those.

Στην παρούσα εργασία γίνεται μια προσπάθεια συνολικής παρουσίασης των τεχνικών χρονοπρογραμματισμού έργου ακολουθώντας την πορεία εξέλιξής τους. Στο τρίτο κεφάλαιο απαντάμε στα βασικά ερωτήματα που αφορούν το τι περιλαμβάνει η έννοια του όρου έργο και διαχείριση έργου. Είναι πολύ σημαντικό πριν να προχωρήσουμε σε τεχνικές χρονοπρογραμματισμού ενός έργου να μπορούμε να αποκωδικοποιήσουμε τις ανάγκες του αλλά και τον τρόπο δόμησής του ώστε να υπολογίσουμε σωστά τις ανάγκες και τα κόστη σε χρόνο αλλά και σε πόρους, ώστε να φθάσουμε στην επίτευξη του τελικού σκοπού μέσα στο χρονικό ορίζοντα που έχουμε θέσει και χωρίς να έχουμε αποκλίσεις από τις προϋπολογισθείσες δαπάνες πόρων. Στη συνέχεια αναλύονται οι κλασικές τεχνικές χρονοπρογραμματισμού μέσα από παραδείγματα εφαρμογών. Στο τέταρτο κεφάλαιο γίνεται μια παρουσίαση των βασικότερων μεθόδων επίλυσης προβλημάτων συνδυαστικής βελτιστοποίησης και παρουσιάζονται οι προσεγγίσεις αντιμετώπισης μέσω τριών κατηγοριών αλγορίθμων που έχουν αναπτυχθεί τα τελευταία χρόνια. Αυτοί είναι: οι ακριβείς μέθοδοι μαθηματικού προγραμματισμού, οι ευρετικοί αλγόριθμοι και οι μεταευρετικοί αλγόριθμοι. Στη συνέχεια δίνεται έμφαση στην παρουσίαση των κυριότερων εκπροσώπων των ακριβών μεθόδων. Αναλύουμε τις ευρετικές και μεταευρετικές μεθόδους όπως αυτές έχουν παρουσιαστεί τα τελευταία χρόνια από τους ερευνητές. Οι ευρετικές μέθοδοι αποτελούν τη πηγή έμπνευσης θα λέγαμε για τη δημιουργία των μεταευρετικών αλγορίθμων οι οποίοι υπόσχονται ακόμα καλύτερη αντιμετώπιση του προβλήματος καθώς δίνουν μια απάντηση σε προβλήματα που θεωρούνταν αδύνατο να λυθούν αποτελεσματικά και να επιστρέψουν βέλτιστες λύσεις με τους ευρετικούς αλγόριθμους. Στο πέμπτο κεφάλαιο αναλύεται η φιλοσοφία, η εξέλιξη και ο τρόπος λειτουργίας των αλγόριθμων του μοντέλου της κοινωνίας των μυρμηγκιών και γίνεται παρουσίαση των διάφορων εκδόσεων τους των τελευταίων 3 δεκαετιών που αυτοί έχουν κάνει αισθητή της παρουσία τους στην έρευνα. Γίνεται επίσης παρουσίαση τους σε μορφή ψευδοκώδικα και διαγραμμάτων ροής. Κύριο μέρος του κεφαλαίου λαμβάνει η αντιμετώπιση του Προβλήματος του Περιοδεύοντας Πωλητή (Traveling Salesman Problem- TSP) που είναι το κυριότερο πρόβλημα χρονοπρογραμματισμού και πάνω στο οποίο στηρίζεται η εύρεση λύσεων και σε άλλα υπολογιστικά προβλήματα όπως αυτό της δρομολόγησης οχημάτων, χρονοπρογραμματισμού παραγωγής κα. Στο έκτο κεφάλαιο γίνεται παρουσίαση του τρόπου αντιμετώπισης του προβλήματος της εύρεσης της κρίσιμης διαδρομής σε ένα έργο και παρουσιάζεται ο αλγόριθμος που ακολουθείται. Παράλληλα, παρουσιάζεται μια μελέτη συμπεριφοράς του αλγορίθμου σε μεταβολές των μεταβλητών του. Στο έβδομο κεφάλαιο βλέπουμε κάποια γενικά συμπεράσματα και μελλοντικές κατευθύνσεις ενώ στο Παράρτημα Ι γίνεται παρουσίαση της θεωρίας των γράφων για να γίνει καλύτερα κατανοητή η χρήση τους και ο σπουδαίος ρόλος τους στην ανάπτυξη των αλγορίθμων χρονοπρογραμματισμού, ενώ στο Παράρτημα ΙΙ παρουσιάζεται αναλυτικά το πρόβλημα του πλανόδιου πωλητή. / -