Προσεγγιστικοί αλγόριθμοι δρομολόγησης παραλληλοποιήσιμων εργασιών - Τσεπενέκας, Λεωνίδας (Εθνικό Μετσόβιο Πολυτεχνείο. Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, 2016)
Μια τυπική υπόθεση στα κλασσικά προβλήματα χρονοδρομολόγησης είναι ότι οι εργασίες, χρησιμοποιούν μόνο μια επεξεραστική μονάδα για την εκτέλεσή τους. Παρόλα αυτά, υπάρχει πληθώρα προβλημάτων που εμφανίζονται σε πολλούς και διαφορετικούς τομείς, στα οποία η εν λόγω υπόθεση δεν είναι επαρκής για να μοντελοποιήσει τις ιδιαίτερες απαιτήσεις που παρουσιάζουν. Σε αυτές τις περιπτώσεις θα πρέπει να επεκτείνουμε το κλασικό μοντέλο, επιτρέποντας σε μια εργασία να εκτελείται ταυτόχρονα σε περισσότερους του ενός επεξεργαστές και μάλιστα ενιαία. Αυτό σημαίνει ότι η εργασία θα έχει κοινό χρόνο εκκίνησης και ολοκλήρωσης σε όλους τους επεξεργαστές που της έχουν ανατεθεί και μάλιστα ο χρόνος εκτέλεσης της θα είναι συνάρτηση αυτών. Στην αλγοριθμική βιβλιογραφία προβλήματα της παραπάνω μορφής συναντώνται ως malleable ή multiprocessor ή parallelizable job scheduling. ΄Οπως και στο κλασικό μοντέλο μιας εργασίας σε μια μηχανή, έτσι και εδώ υπάρχει η ανάγκη σχεδίασης αποδοτικών αλγορίθμων. Στη διπλωματική αυτή, μελετάμε το πρόβλημα της χρονοδρομολόγησης σε τέτοια μοντέλα από τη σκοπιά της θεωρίας δρομολόγησης και των προσεγγιστικών αλγορίθμων. Ξεκινάμε παρουσιάζοντας τα πιο γνωστά αποτελέσματα, επεκτείνοντας παράλληλα μερικά από αυτά. Η βασική συνεισφορά μας είναι η δημιουργία ενός μοντέλου για malleable job scheduling που γενικεύει την ιδέα του uniform machine scheduling και η παρουσίαση προσεγγιστικών αλγορίθμων σταθερού παράγοντα για αυτό.