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

Abstract

Μια τυπική υπόθεση στα κλασσικά προβλήματα χρονοδρομολόγησης είναι ότι οι εργα-σίες, χρησιμοποιούν μόνο μια επεξεραστική μονάδα για την εκτέλεσή τους. Παρόλα αυτά,υπάρχει πληθώρα προβλημάτων που εμφανίζονται σε πολλούς και διαφορετικούς τομείς, σταοποία η εν λόγω υπόθεση δεν είναι επαρκής για να μοντελοποιήσει τις ιδιαίτερες απαιτήσειςπου παρουσιάζουν. Σε αυτές τις περιπτώσεις θα πρέπει να επεκτείνουμε το κλασικό μον-τέλο, επιτρέποντας σε μια εργασία να εκτελείται ταυτόχρονα σε περισσότερους του ενόςεπεξεργαστές και μάλιστα ενιαία. Αυτό σημαίνει ότι η εργασία θα έχει κοινό χρόνο εκκίνη-σης και ολοκλήρωσης σε όλους τους επεξεργαστές που της έχουν ανατεθεί και μάλισταο χρόνος εκτέλεσης της θα είναι συνάρτηση αυτών. Στην αλγοριθμική βιβλιογραφία προ-βλήματα της παραπάνω μορφής συναντώνται ως malleable ή multiprocessor ή parallelizablejob scheduling.Οπως και στο κλασικό μοντέλο μιας εργασίας σε μια μηχανή, έτσι και εδώ υπάρχει ηανάγκη σχεδίασης αποδοτικών αλγορίθμων. Στη διπλωματική αυτή, μελετάμε το πρόβληματης χρονοδρομολόγησης σε τέτοια μοντέλα από τη σκοπιά της θεωρίας δρομολόγησης καιτων προσεγγιστικών αλγορίθμων. Ξεκινάμε παρουσιάζοντας τα πιο γνωστά αποτελέσματα,επεκτείνοντας παράλληλα μερικά από αυτά. Η βασική συνεισφορά μας είναι η δημιουργίαενός μοντέλου για malleable job scheduling που γενικεύει την ιδέα του uniform machinescheduling και η παρουσίαση προσεγγιστικών αλγορίθμων σταθερού παράγοντα για αυτό