Ακριβείς Και Ευριστικοί Αλγόριθμοι Σχεδιασμού Και Βελτιστοποίησης Ροών Εργασιών Σε Περιβάλλον Υπολογιστικού Νέφους Με Πολλαπλές Μηχανές

Abstract

Οι μοντέρνες ροές εργασιών έχουν γίνει αρκετά μεγάλες και πολύπλοκες. Για κάθε εργασία είναι πιθανόν να υπάρχει η δυνατότητα εκτέλεσης σε διαφορετική μηχανή εκτέλεσης. Επομένως, μία ροή εργασιών έχει πολλά διαφορετικά πλάνα εκτέλεσης. Από όλα τα διαφορετικά πλάνα εκτέλεσης πουμπορούν να προκύψουν για ροή εργασιών κρίνεται σκόπιμο να βρεθούν τα βέλτιστα ως προς κάποια κριτήρια. Στην παρούσα διπλωματική εργασία, κατασκευάζεται ένας μετα-σχεδιαστής, ο οποίος έχει ως στόχο τον αυτόματο προσδιορισμό των βέλτιστων λύσεων κατά pareto ως προς τα κριτήρια τουχρόνου και του κόστους εκτέλεσης. Ο σχεδιαστής αυτός αρχικά διαβάζει την περιγραφεί μίας ροής εργασιών από ένα XML αρχείο και στη συνέχεια επιχειρεί την εύρεση των κατάλληλων πλάνων με δύο τρόπους, με τη χρήση μοντέλωνπου προσδιορίζουν το χρόνο και στο κόστος εκτέλεσης κάθε εργασίας σε κάθε μηχανή. Ο πρώτος χρησιμοποιεί έναν βέλτιστο αλγόριθμο που εγγυάται την εύρεση των καλύτερων λύσεων. Ο δεύτερος είναι ο προσεγγιστικός γενετικόςαλγόριθμος NSGA-II. Στόχος είναι η αξιολόγηση των δύο μεθόδων, από την οποία προέκυψε ότι μέγαλη επίδραση στην επίδοση και των δύο αλγορίθμων έχει το μέγεθος της ροής εργασίων, σε αντίθεση με το πλήθος των μηχανών όπου επηρεάζει κυρίως το βέλτιστο αλγόριθμο. Επίπλέον, υπάρχουν περίπτωσεις όπου ο προσεγγιστικός αλγόριθμος είναι σημαντικά πιο γρήγορος από τον βέλτιστο (μέχρι και 152 φορές), γεγονός που υποδεικνύει τη χρήση τουδεδομένης της μικρής απόστασης των λύσεων. Τέλος, διαπιστώνεται ότι χρησιμοποιώντας τον σχεδιαστή μπορεί να επιτευχθεί εντοπισμός καλύτερου πλάνου εκτέλεσης ως προς κάποιο κρίτηριο σε σχέση με το να εκτελούταν όλη τη ροή στην ίδια μηχανή εκτέλεσης.