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

Abstract

Σε αυτή την εργασία, ορίζουμε φορμαλιστικά την έννοια της Δεσμευτικότητας, την οποία εμπνευστήκαμε από πρόσφατες δουλειές σε Άμεση Χρονοδρομολόγηση σε Παράλληλες Μηχανές. Από όσο ξέρουμε, είμαστε οι πρώτοι που χαρακτηρίζουν με ακρίβεια αυτή την έννοια. Δεσμευτικότητα είναι η υπόσχεση ενός άμεσου αλγόριθμου δρομολόγησης να προσδιορίσει τον χρόνο ολοκλήρωσης μιας δουλειάς κατά την άφιξή της. Η δεσμευτικότητα είναι τόσο ισχυρή ιδιότητα που απαιτεί ένα πλήρως προκαθορισμένο πρόγραμμα για την επίτευξή της. Εισάγουμε ένα μοντέλο για το πρόβλημα της Χρονοδρομολόγησης σε Παράλληλες Μηχανές το οποίο υποθέτει μία πολυωνυμική κατανομή μηκών και είναι κοντά στο άμεσο μοντέλο. Για αυτό το μοντέλο, περιγράφουμε έναν ασυμπτωτικά βέλτιστο αλγόριθμο. Περιορίζοντας το μοντέλο ώστε να έχει έναν σταθερό αριθμό από δουλειές κάθε δευτερόλεπτο και υποθέτοντας αριθμό μηχανών τουλάχιστον τόσες όσο ο αριθμός των δουλειών επί το μέσο μήκος, αποδεικνύουμε πλήρως δεσμευτικούς αλγορίθμους. Αυτοί οι αλγόριθμοι είναι ξανά ασυμπτωτικά βέλτιστοι. Αυτό είναι βελτίωση σε σχέση με το γενικό κάτω φράγμα \Omega(\log L_{max}) για δεσμευτικούς αλγορίθμους, όπου L_{max} είναι το μέγιστο μήκος δουλειών. Επιπλέον, αναβαθμίζουμε αυτό το μοντέλο υποθέτοντας ότι ο αριθμός των δουλειών είναι τυχαία μεταβλητή. Αυτό χειροτερεύει την προσέγγιση κατά έναν προσθετικό παράγοντα ίσο με τη ρίζα της διακύμανσης διά τον μέσο αριθμό δουλειών. Ξανά, αλλάζοντας το μοντέλο και υποθέτοντας περιοδικότητα του αριθμού δουλειών, έχουμε ένα προσθετικό παράγοντα στη προσέγγιση Ο(\frac{h}{T}), όπου h η περίοδος και T ο αριθμός των χρονικών στιγμών. Ακόμη, προσθέτουμε φιλαλήθεια σε κλασικούς αλγορίθμους που μετατρέπουν προεκτοπιστικά προγράμματα σε μη προεκτοπιστικά. Τέλος, σχεδιάζουμε έναν αλγόριθμο που είναι μερικώς δεσμευτικός και έχει σταθερή προσέγγιση για αρκετά μεγάλη χαλάρωση. Ύστερα, χρησιμοποιούμε τις ιδέες της δεσμευτικότητας/φιλαλήθειας στο Πρόβλημα του Πλανόδιου Επιδιορθωτή (Travelling Repairman Problem ή TRP). Δείχνουμε έναν μερικώς δεσμευτικό αλγόριθμο με σταθερή προσέγγιση που βασίζεται σε γνωστούς αλγορίθμους για το άμεσο TRP. Το κύριο αποτέλεσμά μας είναι ότι κάθε πλήρως δεσμευτικός αλγόριθμος για το άμεσο TRP έχει προσέγγιση τουλάχιστον \Omega(\frac{TSP_{tour}}{\Delta}), όπου TSP_{tour} το μήκος της βέλτιστης περιοδείας για το Πρόβλημα Πλανόδιου Πωλητή και \Delta η διάμετρος του χώρου. Τέλος, σχεδιάζουμε έναν αλγόριθμο που πετυχαίνει αυτό το κάτω φράγμα για μετρικές σε δέντρα.