| Περίληψη: | Η διπλωµατική εργασία αποτελεί συνέχεια της µελέτης προβληµάτων χρονοπρογραµµατισµού µε αυστηρές προθεσµίες που ξεκίνησε η Αµαλία Στούµπου στην δικιά της διπλωµατική εργασία µε όνοµα "Προβλήµατα Επιτάχυνσης ∆ιεργασιών σε Grid Computing: Αλγόριθµοι και Πολυπλοκότητα". Εξετάζονται προβλήµατα δροµολόγησης διεργασιών σε περισσότερους από έναν, ίδιους µεταξύ τους, επεξεργαστές. ∆ίνονται αλγόριθµοι που λύνουν το πρόβληµα ελαχιστοποίησης του συνολικού χρόνου εκτέλεσης, µε αυστηρές προθεσµίες, αρχικά για 2 και στη συνέχεια για m επεξεργαστές. Οι αλγόριθµοι αυτοί έχουν ψευδοπολυωνυµική πολυπλοκότητα. Στη συνέχεια εξετάζονται προβλήµατα δροµολόγησης και επιτάχυνσης διεργασιών µε ίδιο χρόνο εκτέλεσης, σε περιβάλλοντα µε ίδιους µεταξύ τους επεξεργαστές και δίνονται πολυωνυµικοί αλγόριθµοι που τα λύνουν. Τέλος αναφέρονται συνοπτικά ορισµένα προβλήµατα του ευρύτερου χώρου προϐληµάτων χρονοπρογραµµατισµού που µπορούν να προσεγγιστούν ή να λυθούν µε τεχνικές που εφαρµόστηκαν για τη λύση των προηγούµενων προβληµάτων που αναφέρθηκαν.
|
|---|
