Η παρούσα εργασία έχει σαν στόχο την ανάλυση ενός προβλήματος δρομολόγησης το οποίο στη βάση του έχει ως εξής: Δίνεται ακολουθία διεργασιών που πρόκειται να δοθεί για επεξεργασία σε ένα σύνολο μηχανών. Η κάθε διεργασία χαρακτηρίζεται από το χρόνο επεξεργασίας της και θα πρέπει να δρομολογηθεί σε κάποια απ' τις μηχανές για χρόνο τουλάχιστον ίσο με αυτό. Επιπλέον υπάρχει απαίτηση από ένα υποσύνολο διεργασιών για επιτάχυνση. Το ζητούμενο είναι να δοθεί αλγόριθμος που δρομολογεί τις διεργασίες στις μηχανές ελαχιστοποιώντας κάποια μετρική απόδοσης, παράλληλα με την εξυπηρέτηση όσο το δυνατόν περισσότερων αιτήσεων για επιτάχυνση. Στα πλαίσια ενός εισαγωγικού κεφαλαίου δίνεται θεωρητικό υπόβαθρο που αφορά σε προβλήματα και αλγορίθμους δρομολόγησης, σημειώνοντας ιδιαίτερα τη διαφορά μεταξύ στατικών και δυναμικών αλγορίθμων. Αντικείμενο της εργασίας αυτής γίνεται στη συνέχεια η μελέτη του παραπάνω προβλήματος, σε περιβάλλον μιας μηχανής και σε παραλλαγές του οι οποίες σχετίζονται με παραμέτρους, όπως για παράδειγμα, προθεσμίες ολοκλήρωσης. Αποτέλεσμα της μελέτης αυτής είναι η ανάπτυξη, αλλά και η αξιολόγηση αποτελεσματικών μεθόδων επίλυσης, χρησιμοποιώντας γνωστά κριτήρια βελτιστοποίησης όπως ο χρόνος που απαιτείται για την ολοκλήρωση των διεργασιών, αλλά και κάποιες νέες μετρικές που συστήνονται και η ανάγκη τους επεξηγείται αναλυτικά. Τέλος στο τρίτο κεφάλαιο γίνεται επισκόπηση προβλημάτων που αφορούν δρομολόγηση σε περισσότερες από μία μηχανές. Τα προβλήματα αυτά ενώ αποδεικνύονται ΝΡ-πλήρη, οι αποδείξεις παραλείπονται και δίδονται παρατηρήσεις για την πολυπλοκότητα παραλλαγών τους. Η εργασία κλείνει με μια παρουσίαση της υπολογιστικής μεθόδου του δυναμικού προγραμματισμού, που γίνεται προσπάθεια να εφαρμοστεί σε προβλήματα δρομολόγησης. / The purpose of the present study is to analyze a scheduling problem, the def- inition of which is: We are given a sequence of tasks that are to be processed on a set of machines. Each task is characterized by its running time and has to be scheduled on a machine, for at least its running time. In addition, there are speedup requests from a subset of tasks. The scheduling algorithm is asked to produce a schedule that minimizes an objective function in par- allel with serving as many as possible speedup requests. The introduction gives a theoretical background concerning scheduling prob- lems and algorithms, with an emphasis on the di_erence between static and dynamic algorithms. The objective of the second chapter, is to study the problem above, in its many variations, with a reference to parameters like the number of the machines, deadlines etc. The result of this study, is the development and the evaluation of two algorithms, using objective functions like makespan, and also some new ones that arise in the essay and their need is analyzed. The thesis closes with a consideration of already known schedul- ing problems and its variants, that have been proved to be NP-complete.

Η χρήση επαναληπτικών τεχνικών προσαρμοστικής ισοστάθμισης διαύλου αποτελεί μια σχετικά πρόσφατη και πολλά υποσχόμενη μέθοδο αντιμετώπισης του φαινομένου της διασυμβολικής παρεμβολής που εισάγεται από το κανάλι λόγω του φαινομένου της πολυδιόδευσης. Ο αλγόριθμος που έχει επικρατήσει στις περισσότερες προσαρμοστικές εφαρμογές είναι ο ελαχίστων μέσων τετραγώνων (LMS). Διακρίνεται για την απλότητά του, έχει όμως φτωχές ιδιότητες σύγκλισης. Η μέθοδος των αναδρομικών ελαχίστων τετραγώνων (RLS) είναι επίσης αρκετά διαδεδομένη και κατέχει υπερέχουσες ιδιότητες σύγκλισης. Ωστόσο παρουσιάζει μεγάλη υπολογιστική πολυπλοκότητα και αυξημένες απαιτήσεις σε μνήμη. Στα πλαίσια της εργασίας αυτής εγίνε μια προσπάθεια ανάλυσης των τεχνικών που βασίζονται στη μέθοδο των συζυγών παραγώγων (Conjugate Gradient), χρησιμοποιούνται σε προβλήματα προσαρμοστικού φιλτραρίσματος και πιο ειδικά στο πρόβλημα της προσαρμοστικής ισοστάθμισης διαύλου. Οι τεχνικές αυτές επεξεργάζονται τα δεδομένα και ανά μπλοκ. Είναι ικανές να παρέχουν ιδιότητες σύγκλισης συγκρίσιμες με αυτές της (RLS) μεθόδου, εισάγοντας υπολογιστική πολυπλοκότητα ενδιάμεσων απαιτήσεων μεταξύ των μεθόδων LMS και RLS χωρίς να παρουσιάζουν προβλήματα αριθμητικής ευστάθειας. / The use of iteration methods for adaptive equalization has received considerable attention during the past several decades. The Least Mean Squares (LMS) method, which has found widespread use owing to its simplicity, has poor convergence properties. The Recursive Least Squares (RLS) method possess superior convergence properties, but it is computationally intensive and has high storage requirements for matrix manipulations. In this MSc thesis the technique of conjugate gradients is applied for the adaptive filtering problem. Conjugate gradient algorithms for adaptive filtering applications suitable for efficient implementation has been developed and has been applied for the design of an adaptive transversal equalizer. Low cost block algorithms using the preconditioned conjugate gradient method are also discussed. The algorithms are capable of providing convergence comparable to RLS schemes at a computational complexity between the LMS and the RLS methods and does not suffer from any known instability problems.