Φιλαλήθεις Αλγόριθμοι για την Ελαχιστοποίηση του Συνολικού Χρόνου Ολοκλήρωσης σε Ασυσχέτιστες Μηχανές

Abstract

Στην παρούσα διπλωματική εργασία, θα μελετήσουμε Φιλαλήθεις Αλγόριθμους Χρονοδρομολόγη- σης Εργασιών σε Ασυσχέτιστες Μηχανές με σκοπό την Ελαχιστοποίηση του Βεβαρημένου Χρόνου Ολοκλήρωσης. Στο μοντέλο που μας ενδιαφέρει, οι εργασίες δηλώνουν οι ίδιες τους χρόνους επε- ξεργασίας τους, ενώ συμπεριφέρονται ως ιδιοτελείς οντότητες, στοχεύοντας στην ελαχιστοποίηση του δικού τους χρόνου ολοκλήρωσης. Σημειώνουμε ότι στη βιβλιογραφία υπάρχουν Φιλαλήθεις Αλγόριθμοι μόνο για την πιο απλή περίπτωση των Όμοιων Μηχανών. Η γενίκευση αυτών των Αλ- γορίθμων σε Ασυσχέτιστες Μηχανές δεν είναι εύκολη, καθώς στην περίπτωσή μας οι εργασίες, εκτός από το να δηλώσουν έναν μικρότερο από τον πραγματικό χρόνο επεξεργασίας για να επιτύ- χουν έναν καλύτερο χρόνο ολοκλήρωσης, έχουν το κίνητρο να δηλώνουν μεγαλύτερους από τους πραγματικούς χρόνους επεξεργασίας σε Μηχανές στις οποίες θέλουν να αποφύγουν να ανατε- θούν. Αρχικά, παραθέτουμε έναν Μη Φιλαλήθη βέλτιστο Δεσμευτικό Αλγόριθμο, καθώς και έναν Φιλαλήθη Αλγόριθμο του οποίου τον Λόγο Προσέγγισης δεν έχουμε καταφέρει να αναλύσουμε πλήρως. Υποστηρίζουμε τον παραπάνω αλγόριθμο με τη διεξαγωγή μιας πειραματικής διαδικα- σίας, με σκοπό τη σύγκριση της επίδοσής του με αυτή του καλύτερου επί του παρόντος Online Αλγόριθμου Χρονοδρομολόγησης, καθώς επίσης και με ένα κάτω όριο της βέλτιστης λύσης.