Παρακαλώ χρησιμοποιήστε αυτό το αναγνωριστικό για να παραπέμψετε ή να δημιουργήσετε σύνδεσμο προς αυτό το τεκμήριο:
http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/18761
Τίτλος: | Φιλαλήθεις Αλγόριθμοι για την Ελαχιστοποίηση του Συνολικού Χρόνου Ολοκλήρωσης σε Ασυσχέτιστες Μηχανές |
Συγγραφείς: | Γιαννόπουλος, Εμμανουήλ Φωτάκης Δημήτριος |
Λέξεις κλειδιά: | Online Algorithms Online Scheduling Completion Time Promptness Algorithmic Mechanism Design Truthfulness |
Ημερομηνία έκδοσης: | 21-Ιου-2023 |
Περίληψη: | Στην παρούσα διπλωματική εργασία, θα μελετήσουμε Φιλαλήθεις Αλγόριθμους Χρονοδρομολόγη- σης Εργασιών σε Ασυσχέτιστες Μηχανές με σκοπό την Ελαχιστοποίηση του Βεβαρημένου Χρόνου Ολοκλήρωσης. Στο μοντέλο που μας ενδιαφέρει, οι εργασίες δηλώνουν οι ίδιες τους χρόνους επε- ξεργασίας τους, ενώ συμπεριφέρονται ως ιδιοτελείς οντότητες, στοχεύοντας στην ελαχιστοποίηση του δικού τους χρόνου ολοκλήρωσης. Σημειώνουμε ότι στη βιβλιογραφία υπάρχουν Φιλαλήθεις Αλγόριθμοι μόνο για την πιο απλή περίπτωση των Όμοιων Μηχανών. Η γενίκευση αυτών των Αλ- γορίθμων σε Ασυσχέτιστες Μηχανές δεν είναι εύκολη, καθώς στην περίπτωσή μας οι εργασίες, εκτός από το να δηλώσουν έναν μικρότερο από τον πραγματικό χρόνο επεξεργασίας για να επιτύ- χουν έναν καλύτερο χρόνο ολοκλήρωσης, έχουν το κίνητρο να δηλώνουν μεγαλύτερους από τους πραγματικούς χρόνους επεξεργασίας σε Μηχανές στις οποίες θέλουν να αποφύγουν να ανατε- θούν. Αρχικά, παραθέτουμε έναν Μη Φιλαλήθη βέλτιστο Δεσμευτικό Αλγόριθμο, καθώς και έναν Φιλαλήθη Αλγόριθμο του οποίου τον Λόγο Προσέγγισης δεν έχουμε καταφέρει να αναλύσουμε πλήρως. Υποστηρίζουμε τον παραπάνω αλγόριθμο με τη διεξαγωγή μιας πειραματικής διαδικα- σίας, με σκοπό τη σύγκριση της επίδοσής του με αυτή του καλύτερου επί του παρόντος Online Αλγόριθμου Χρονοδρομολόγησης, καθώς επίσης και με ένα κάτω όριο της βέλτιστης λύσης. |
URI: | http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/18761 |
Εμφανίζεται στις συλλογές: | Διπλωματικές Εργασίες - Theses |
Αρχεία σε αυτό το τεκμήριο:
Αρχείο | Περιγραφή | Μέγεθος | Μορφότυπος | |
---|---|---|---|---|
Thesis_Giannopoulos.pdf | Truthful Scheduling in Unrelated Machines to Minimize the Sum of Completion Times | 510.14 kB | Adobe PDF | Εμφάνιση/Άνοιγμα |
Όλα τα τεκμήρια του δικτυακού τόπου προστατεύονται από πνευματικά δικαιώματα.