Κατανομή πόρων σε τεχνικά έργα με τη χρήση γενετικών αλγορίθμων (EL)

Παπαδάκη, Ευαγγελία - Πέτρος

Πανεπιστήμιο Αιγαίου. Σχολή Επιστημών της Διοίκησης. Τμήμα Μηχανικών Οικονομίας και Διοίκησης. Οικονομική και Διοίκηση για Μηχανικούς. (EL)

Στην παρούσα Διπλωματική εργασία μελετήθηκε το πρόβλημα προγραμματισμού πόρων με περιορισμούς διαθεσιμότητας (resource-constrained project scheduling problem-RCPSP), λόγω της υψηλής σπουδαιότητας που παρουσιάζουν τα προβλήματα αυτά στη διοίκηση των έργων. Το πρόβλημα αυτό καθώς και το πρόβλημα της εξομάλυνσης πόρων (resource leveling problem), εντάσσονται στην ευρύτερη κατηγορία των προβλημάτων κατανομής πόρων (resource allocation problems). Ο σωστός προγραμματισμός και η κατανομή των πόρων είναι μία απαραίτητη διαδικασία της διοίκησης έργων λόγω των αυστηρών περιορισμών που θέτουν τα διαθέσιμα κεφάλαια, η διαθεσιμότητα των πόρων και οι προθεσμίες ολοκλήρωσης των δραστηριοτήτων. Συνεπώς, καθίσταται αναγκαία η χρήση ευέλικτων και αποτελεσματικών μεθόδων προκειμένου να επιλύονται πολύπλοκα προβλήματα που πολλές φορές απαιτούν συντονισμένη χρήση πολλών πόρων σε πολλά έργα. Αυτό το πρόβλημα λοιπόν του προγραμματισμού πόρων με περιορισμούς διαθεσιμότητας, σε ένα μοναδικό έργο, επιχειρήθηκε να επιλυθεί στο πλαίσιο αυτής της Διπλωματικής εργασίας. Από το παρελθόν μέχρι και σήμερα έχουν επινοηθεί ποικίλοι τρόποι επίλυσης του προβλήματος. Ωστόσο, οι παραδοσιακές, ευρεστικές, μέθοδοι κατανομής πόρων, είτε αδυνατούν να επιλύσουν σύνθετα και με μεγάλη έκταση προβλήματα, είτε τα αποτελέσματά τους διαφοροποιούνται ανάλογα με το εκάστοτε πρόβλημα. Παρόλα αυτά, μέθοδοι βασισμένες σε γενετικούς αλγορίθμους μπορούν να δώσουν λύση στα παραπάνω προβλήματα επιτυγχάνοντας τη βέλτιστη ή με μεγάλη πιθανότητα μία σχεδόν βέλτιστη λύση και μάλιστα σε λογικό υπολογιστικό χρόνο. Οι γενετικοί αλγόριθμοι στηριζόμενοι στους μηχανισμούς της φυσικής επιλογής και στη γενετική, ενεργούν πάνω σε ένα σύνολο λύσεων και προσπαθούν να παράγουν ολοένα και καλύτερες προσεγγίσεις σε μία λύση. Από τις σημαντικότερες ιδιότητες των αλγορίθμων αυτών είναι η ικανότητα που έχουν να διερευνούν το χώρο λύσεων σε πολλαπλές κατευθύνσεις ταυτόχρονα. Το γεγονός αυτό τους καθιστά κατάλληλους για την επίλυση προβλημάτων στα οποία ο χώρος αναζήτησης των λύσεων είναι υπερβολικά μεγάλος για να μπορέσει να εξερευνηθεί εξαντλητικά σε ένα εύλογο χρονικό διάστημα. Στη χρήση γενετικών αλγορίθμων βασίστηκε η παρούσα εργασία για τον προγραμματισμό του προβλήματος σε περιβάλλον matlab. Κατά την υλοποίηση του αλγορίθμου, υιοθετήθηκαν τεχνικές και η βασική δομή των γενετικών αλγορίθμων από άρθρα της βιβλιογραφίας ενώ ταυτόχρονα προτάθηκε ένας τρόπος επιλογής της λύσης εκείνης που εξασφαλίζει ένα καλύτερο προφίλ στη χρησιμοποίηση των πόρων. Η εφαρμογή του αλγορίθμου πραγματοποιήθηκε σε ένα σετ έργων από μία βάση δεδομένων-PSPLIB, διαθέσιμη στο διαδίκτυο, επιβεβαιώνοντας την αποτελεσματικότητά του για την επίλυση των σύνθετων προβλημάτων προγραμματισμού πόρων με περιορισμούς διαθεσιμότητας, δίνοντας στο 79,2% των έργων τη βέλτιστη διάρκεια έργου, στο 16,7% απόκλιση από τη βέλτιστη διάρκεια ίση με μία χρονική μονάδα και τέλος σε ένα πολύ μικρό ποσοστό των έργων ίσο με 4,1%, απόκλιση δύο χρονικών μονάδων.

masterThesis

Κατανομή πόρων (EL)

Γενετικοί αλγόριθμοι (EL)

Project management (EL)

Resource allocation (EL)

Resource scheduling (EL)

Προγραμματισμός πόρων (EL)

Διοίκηση έργων (EL)

Genetic algorithms (EL)

Πανεπιστήμιο Αιγαίου

Ιδρυματικό Αποθετήριο Ελλάνικος (Hellanicus)

Γκρίζα Βιβλιογραφία

Μεταπτυχιακές διατριβές

Τμήμα Μηχανικών Οικονομίας και Διοίκησης

Οικονομική και Διοίκηση για Μηχανικούς

2011

http://hdl.handle.net/11610/14646

2015-11-19T10:57:30Z

Χίος