Αλγόριθμοι Δρομολόγησης με Εκτίμηση της Χρονικής Διάρκειας των Εργασιών σε Πραγματικό Χρόνο

Abstract

Η κάτωθι διπλωματική εργασία μελετά το πρόβλημα Χρονοδρομολόγησης Εργασιών Υπό Αβε- βαιότητα σε μία μηχανή. Σκοπός των αλγορίθμων που αναπτύχθηκαν είναι η ελαχιστοποίηση μίας αντικειμενικής συνάρτησης η οποία είναι το άθροισμα των χρόνων αποπεράτωσης κάθε εργασίας. Πιο συγκεκριμένα, η κλάση των προβλημάτων Χρονοδρομολόγησης Εργασιών εί- ναι από τα πλέον πιο μελετημένα προβλήματα στον τομέα των Αλγορίθμων και της Επιχειρη- σιακής Έρευνας απαριθμώντας ποικίλες εφαρμογές, με γνωστότερη τον προγραμματισμό των χρονοδρομολογητών στα λειτουργικά συστήματα των υπολογιστών. Οι δύο μεγάλες κατηγορίες προβλημάτων Χρονοδρομολόγησης διαφέρουν στην εκ των προτέρων γνώση του ακριβούς με- γέθους των εργασιών. Σημειώνουμε ότι και οι δύο κατηγορίες έχουν μελετηθεί εκτενώς στην βι- βλιογραφία. Συνήθως, στην πλειοψηφία των αλγορίθμων που μελετούνται καθώς και στις πραγ- ματικές εφαρμογές ο χρονοδρομολογητής δεν γνωρίζει το ακριβές μέγεθος κάθε εργασίας. Σε σημερινές εφαρμογές, όμως, έχουν αναπτυχθεί αλγόριθμοι συμπίεσης εργασιών ή βελτιστοποίη- σης του εκτελέσιμου κώδικα που φέρουν, καθιστώντας πλέον εφικτή την δυνατότητα να δώσουν πληροφορία για το ακριβές μέγεθος της κάθε εργασίας. Ακολουθώντας αυτό το μοντέλο μελετή- θηκαν αρχικά οι κυριότεροι αλγόριθμοι χρονοδρομολόγησης για αγνώστου μεγέθους εργασίες. Κατόπιν, ορμώμενοι από ιδέες από τον τομέα των Αλγορίθμων καθοδηγούμενων από την Μηχα- νική Μάθηση συνδυάσαμε τους κλασικούς αλγορίθμους με νέους που μαθαίνουν το πραγματικό μέγεθος κάθε εργασίας κατά την διάρκεια της εκτέλεσης. Συνολικά, ο αλγόριθμος που κατα- σκευάστηκε είναι εύρωστος και συνεπής. Δηλαδή, διατηρεί καλή απόδοση όταν έχουμε μεγάλα σφάλματα καθώς και πλησιάζει τις επιδόσεις του βέλτιστου αλγορίθμου υπό την προϋπόθεση ότι τα σφάλματα είναι αρκούντως μικρά. Να σημειώσουμε ότι ο βέλτιστος αλγόριθμος έχει πρότερη γνώση του ακριβούς μεγέθους κάθε εργασίας.