Αλγόριθμοι χρονοδρομολόγησης καθοδηγούμενοι από δεδομένα για την ελαχιστοποίηση του χρόνου ολοκλήρωσης

Abstract

Στην συγκεκριμένη εργασία εξετάζουμε το πρόβλημα της ελαχιστοποίησης του χρόνου ολοκλήρωσης εργασιών με άμεσες αποφάσεις ("promptness") όπως αυτό ορίστηκε στο [23]. Πιο συγκεκριμένα, εξετάζουμε το σενάριο όπου οι εργασίες φτάνουν σταδιακά (online) και ο αλγόριθμος καλείται να λάβει αποφάσεις για την σειρά εκτέλεσης τους άμεσα, λαμβάνοντας υπόψη χρονικούς περιορισμούς. Εμπνευσμένοι από την βιβλιογραφία του σχεδιασμού αλγορίθμων καθοδηγούμενων από δεδομένα (data-driven algorithm design, [26]), επιγκεντρωνόμαστε στην επέκταση της συγκεκριμένης δουλειάς των Alon , Feldman και Fiat εξετάζοντας το πρόβλημα πέραν της ανάλυσης χειρότερης περίπτωσης. Συγκεκριμένα, προτείνουμε την μοντελοποίηση του προβλήματος ως ένα πρόβλημα μάθησης και παρέχουμε έναν αποδοτικό αλγόριθμο για την επίλυση αυτού. Υιοθετώντας μια προσέγγιση παρόμοια με την εργασία [27], τελικά αποδεικνύουμε ότι ο προτεινόμενος online αλγορίθμος παρέχει και ένα τρόπο ένα λύσουμε το offline πρόβλημα με σταθερό λόγο προσέγγισης ενώ ο ίδιος ο online αλγόριθμος πετυχαίνει σταθερό c-regret.