Student: Evaggelia Papadaki
Year: 2010
Affiliation: University of the Aegean
Level: Postgraduate
Thesis written in Greek
Press on the photo to see where is she now...
The subject of this thesis is the resource allocation problems in construction projects and especially the resource-constrained scheduling problems. The solution of this problem was based on genetic algorithms and simultaneously a better profile for the utilization of resources was suggested. The suggested genetic algorithm (programmed in matlab) was applied to a set of projects with 30 activities each, providing qualitative results.
Τίτλος στα ελληνικά: Κατανομή πόρων σε τεχνικά έργα με τη χρήση γενετικών αλγορίθμων
Περίληψη:
Στην παρούσα Διπλωματική εργασία μελετήθηκε το πρόβλημα προγραμματισμού πόρων με περιορισμούς διαθεσιμότητας (resource-constrained project scheduling problem-RCPSP), λόγω της υψηλής σπουδαιότητας που παρουσιάζουν τα προβλήματα αυτά στη διοίκηση των έργων. Το πρόβλημα αυτό καθώς και το πρόβλημα της εξομάλυνσης πόρων (resource leveling problem), εντάσσονται στην ευρύτερη κατηγορία των προβλημάτων κατανομής πόρων (resource allocation problems). Ο σωστός προγραμματισμός και η κατανομή των πόρων είναι μία απαραίτητη διαδικασία της διοίκησης έργων λόγω των αυστηρών περιορισμών που θέτουν τα διαθέσιμα κεφάλαια, η διαθεσιμότητα των πόρων και οι προθεσμίες ολοκλήρωσης των δραστηριοτήτων. Συνεπώς, καθίσταται αναγκαία η χρήση ευέλικτων και αποτελεσματικών μεθόδων προκειμένου να επιλύονται πολύπλοκα προβλήματα που πολλές φορές απαιτούν συντονισμένη χρήση πολλών πόρων σε πολλά έργα. Αυτό το πρόβλημα λοιπόν του προγραμματισμού πόρων με περιορισμούς διαθεσιμότητας, σε ένα μοναδικό έργο, επιχειρήθηκε να επιλυθεί στο πλαίσιο αυτής της Διπλωματικής εργασίας.
Από το παρελθόν μέχρι και σήμερα έχουν επινοηθεί ποικίλοι τρόποι επίλυσης του προβλήματος. Ωστόσο, οι παραδοσιακές, ευρεστικές, μέθοδοι κατανομής πόρων, είτε αδυνατούν να επιλύσουν σύνθετα και με μεγάλη έκταση προβλήματα, είτε τα αποτελέσματά τους διαφοροποιούνται ανάλογα με το εκάστοτε πρόβλημα. Παρόλα αυτά, μέθοδοι βασισμένες σε γενετικούς αλγορίθμους μπορούν να δώσουν λύση στα παραπάνω προβλήματα επιτυγχάνοντας τη βέλτιστη ή με μεγάλη πιθανότητα μία σχεδόν βέλτιστη λύση και μάλιστα σε λογικό υπολογιστικό χρόνο. Οι γενετικοί αλγόριθμοι στηριζόμενοι στους μηχανισμούς της φυσικής επιλογής και στη γενετική, ενεργούν πάνω σε ένα σύνολο λύσεων και προσπαθούν να παράγουν ολοένα και καλύτερες προσεγγίσεις σε μία λύση. Από τις σημαντικότερες ιδιότητες των αλγορίθμων αυτών είναι η ικανότητα που έχουν να διερευνούν το χώρο λύσεων σε πολλαπλές κατευθύνσεις ταυτόχρονα. Το γεγονός αυτό τους καθιστά κατάλληλους για την επίλυση προβλημάτων στα οποία ο χώρος αναζήτησης των λύσεων είναι υπερβολικά μεγάλος για να μπορέσει να εξερευνηθεί εξαντλητικά σε ένα εύλογο χρονικό διάστημα.
Στη χρήση γενετικών αλγορίθμων βασίστηκε η παρούσα εργασία για τον προγραμματισμό του προβλήματος σε περιβάλλον matlab. Κατά την υλοποίηση του αλγορίθμου, υιοθετήθηκαν τεχνικές και η βασική δομή των γενετικών αλγορίθμων από άρθρα της βιβλιογραφίας ενώ ταυτόχρονα προτάθηκε ένας τρόπος επιλογής της λύσης εκείνης που εξασφαλίζει ένα καλύτερο προφίλ στη χρησιμοποίηση των πόρων. Η εφαρμογή του αλγορίθμου πραγματοποιήθηκε σε ένα σετ έργων από μία βάση δεδομένων-PSPLIB, διαθέσιμη στο διαδίκτυο, επιβεβαιώνοντας την αποτελεσματικότητά του για την επίλυση των σύνθετων προβλημάτων προγραμματισμού πόρων με περιορισμούς διαθεσιμότητας, δίνοντας στο 79,2% των έργων τη βέλτιστη διάρκεια έργου, στο 16,7% απόκλιση από τη βέλτιστη διάρκεια ίση με μία χρονική μονάδα και τέλος σε ένα πολύ μικρό ποσοστό των έργων ίσο με 4,1%, απόκλιση δύο χρονικών μονάδων.
Contact