Χρονοπρογραμματισμός σε συστήματα απευθείας επικοινωνίας πολλών καναλιών

Abstract

Το πρόβλημα του χρονοπρογραμματισμού επικοινωνιών μεταξύ δύο ομάδων κόμβων πάνω από κάποια πεπερασμένου αριθμού κανάλια, απαιτεί την σύγκριση των διαφορετικών αλγορίθμων. Στη συγκεκριμένη εργασία υλοποιούνται και συγκρίνονται δύο τέτοιοι αλγόριθμοι που δίνουν λύση στο παραπάνω πρόβλημα. Ο πρώτος, κατασκευάζει χρονοπρόγραμμα βρίσκοντας μια ακολουθία από διμερή ταιριάσματα και είναι ο πιο απλός ανάμεσα σε άλλους που έχουν προταθεί από τους Παπαδημητρίου και Crescenzi, ενώ ο δεύτερος κατασκευάζει χρονοπρόγραμμα με την χρήση του Open Shop αλγορίθμου. Ο αλγόριθμος αυτός προέρχεται από άλλη επιστημονική περιοχή και συγκεκριμένα χρησιμοποιείται στο χρονοπρογραμματισμό διεργασιών σε πολλούς επεξεργαστές. Εξετάζεται η συμπεριφορά της εφαρμογή του στο συγκεκριμένο πρόβλημα, προτείνονται και υλοποιούνται διάφορες ιδέες για βελτιώσεις του. Αναλυτικά στα κεφάλαια που ακολουθούν περιέχουν: Κεφάλαιο πρώτο: Διατυπώνεται το πρόβλημα και αναλύονται οι διάφορες έννοιες οι οποίες χρησιμοποιούνται. Κεφάλαιο δεύτερο: Περιγράφεται και αναλύεται ο πρώτος αλγόριθμος με την χρήση διμερών ταιριασμάτων. Κεφάλαιο τρίτο: Περιγράφεται και αναλύεται ο δεύτερος αλγόριθμος χρονοπρογραμματισμού. Κεφάλαιο τέταρτο: Αναλύονται η υλοποίηση των αλγορίθμων που πραγματοποιήθηκε και οι προδιαγραφές των δοκιμών που πραγματοποιήθηκαν καθώς και η ερμηνεία των αποτελεσμάτων. Κεφάλαιο πέμπτο: Περιλαμβάνει την περιγραφή και τεκμηρίωση της υλοποίησης.