Το πρόβλημα που μελετάται στην παρούσα εργασία αναφέρεται σε διάφορες μορφές στη βιβλιογραφία και έχει εφαρμογές τόσο στα οπτικά δίκτυα και συστήματα TDMA (Time Division Multiple Access), όσο και στην παράλληλη μετάδοση μηνυμάτων αλλά και σε ποικίλα άλλα δίκτυα επικοινωνίας. Για το σκοπό της έρευνάς μας υιοθετήσαμε τον ορισμό που αφορά γράφους και με τον ορισμό αυτό το πρόβλημα αναφέρεται στη βιβλιογραφία ως PREEMPTIVE BIPARTITE SCHEDULING (PBS). Στις διάφορες μορφές του έχει μελετηθεί κατά καιρούς από πολλούς ερευνητές και έχει αποδειχθεί ότι ανήκει στην κατηγορία των NP-Hard προβλημάτων ακόμα και για πολύ απλές μορφές δεδομένων εισόδου. Ένας τρόπος να περιγραφεί το πρόβλημα είναι ο ακόλουθος:Δεδομένου ενός συνόλου σταθμών εκπομπής μηνυμάτων (ένα σύνολο κόμβων V με n στοιχεία), ενός συνόλου δεκτών (ένα σύνολο κόμβων U με m στοιχεία) και ενός συνόλου μηνυμάτων που πρέπει να μεταδοθούν από το U στο V (το σύνολο ακμών Ε), καθένα από τα οποία έχει μία συγκεκριμένη διάρκεια (ακμές με βάρη), ζητείται αποδοτικό χρονοπρόγραμμα ώστε η συνολική διάρκεια από τη στιγμή εκκίνησης της πρώτης εκπομπής μέχρι την ολοκλήρωση της τελευταίας να είναι η ελάχιστη δυνατή. Κατά την επίλυση του προβλήματος έχουμε τη δυνατότητα να διακόπτουμε εκπομπές και να συνεχίζουμε τη μετάδοσή τους σε κάποια άλλη χρονική στιγμή, όμως ο χρόνος που θα χρειαστεί σε μία τέτοια περίπτωση το σύστημα για να επανέλθει σε κατάσταση κατάλληλη για την αναμετάδοση νέων δεδομένων δεν είναι μηδενικός και έτσι κάθε φορά που πρέπει ή που εμείς αποφασίζουμε να διακόψουμε μία εκπομπή, επιβαρύνεται ο συνολικός χρόνος μετάδοσης. Έτσι για την εύρεση βέλτιστου χρονοπρογράμματος απαιτείται να λάβει κανείς υπόψη του δύο παραμέτρους: τον συνολικό χρόνο εκπομπών και τον αριθμό των διακοπών.Προηγούμενη έρευνα είχε ως αποτέλεσμα το σχεδιασμό αλγορίθμων για την εύρεση λύσης η οποία να μην είναι χειρότερη από το διπλάσιο της βέλτιστης (ή σφάλμα 100%). Συνοπτικά οι κύριες συνεισφορές της διατριβής είναι: 1. Αλγόριθμοι πολυωνυμικού χρόνου που υπολογίζουν βέλτιστη λύση στις εξής περιπτώσεις: - Επιλύουν το πρόβλημα παράγοντας βέλτιστο χρονοπρόγραμμα στην περίπτωση που τα δεδομένα είναι ειδικής μορφής (μονότονοι γράφοι), - Εξασφαλίζουν το ελάχιστο πλήθος διακοπών και υπό την προϋπόθεση αυτή προσεγγίζεται ένα κάτω φράγμα για τον χρόνο εκπομπής , και τέλος- Ελαχιστοποιούν τον χρόνο εκπομπής και υπό την προϋπόθεση αυτή ελαχιστοποιούν τον αριθμό διακοπών. Για τον σχεδιασμό των 2 τελευταίων αποδείχθηκε ότι κάθε στιγμιότυπο του PBS μπορεί να μετασχηματιστεί σε στιγμιότυπο open shop και αντίστροφα.2. Ο καλύτερος μέχρι στιγμής πολυωνυμικός αλγόριθμος με πηλίκο προσέγγισης γνήσια μικρότερο του 2 για όλες τις τιμές των παραμέτρων εισόδου. Στην πραγματικότητα πρόκειται για μια οικογένεια αλγορίθμων που ονομάστηκε A-PBS(a). Μεταξύ των αλγορίθμων αυτών ξεχωρίζει ο A-PBS(d+1). Για τιμή την εύρεση της ιδανικής τιμής της παραμέτρου a=d+1 εισαγάγαμε πρωτοποριακή μέθοδο απόδειξης για τα δεδομένα της Θεωρητικής Πληροφορικής μέσω παραγώγων. Με τη μέθοδο αυτή αποδείχθηκε τόσο η τιμή του πηλίκου προσέγγισης όσο και η ανελαστικότητα (tightness) του A-PBS(d+1).Το πηλίκο προσέγγισης που αποδείχθηκε για τον A-PBS(d+1) είναι 2-1/(d+1) και επομένως, ανάλογα με τα δεδομένα μπορεί να έχει εγγυημένη απόδοση με μόλις 50% απόκλιση από τη βέλτιστη λύση για d=1. Έτσι επιτυγχάνεται βελτίωση έως και 50% σε σχέση με τον καλύτερο από προγενέστερους αλγορίθμους που επιχειρούν να λύσουν το πρόβλημα. Για d=0 ο ίδιος αλγόριθμος υπολογίζει βέλτιστη λύση τόσο του προβλήματος PBS όσο και του προβλήματος Preemptive Open Shop σε χρόνο πολυωνυμικό.3. Γρήγοροι ευριστικοί αλγόριθμοι που αντιμετωπίζουν τα μειονεκτήματα και βελτιώνουν τους καλύτερους αλγορίθμους που προτάθηκαν από άλλους ερευνητές στο παρελθόν. 4. Σχεδιασμός του καλύτερου μέχρι στιγμής αλγορίθμου όχι μόνο ως προς την ταχύτητα αλλά ταυτόχρονα και ως προς την προσέγγιση της βέλτιστης λύσης του οποίου η αποδοτικότητα αποδείχθηκε μέσω πειραμάτων σε σύγκριση με τους καλύτερους αλγορίθμους που έχουν προταθεί από άλλους ερευνητές.5. Συνδυασμός αποτελεσμάτων και σύνθεση μεθοδολογιών όλων των προηγούμενων αλγορίθμων σε έναν νέο (υβριδικό), τελικό αλγόριθμο που σε πειράματα με διάφορα δεδομένα εισόδου αποδίδει λύση με ελάχιστη απόκλιση από τη βέλτιστη. Οι επιδόσεις του αλγορίθμου αυτού έχουν επιβεβαιωθεί και σε περιπτώσεις που τα δεδομένα εισόδου ακολουθούν όχι μόνο τη συνήθη ομοιόμορφη κατανομή αλλά και άλλες κατανομές που συναντώνται συχνά σε δεδομένα εισόδου όπως κανονική και εκθετική.Για όλα τα ανωτέρω έγινε μελέτη πολυπλοκότητας καθώς και υλοποίηση με κώδικα για την επιβεβαίωση της αποδοτικότητας που προέκυψε από τη θεωρητική τους μελέτη.