Student: Vassilis Lampridis
Year: 2013
Affiliation: National Technical University of Athens
Level: Undergraduate
Thesis written in Greek
Press on the photo to see more about Vassilis...
Thesis supervision was assisted by PhD Candidate Ms Elena Rokou.
...
Τίτλος στα ελληνικά: Χρήση γενετικών αλγορίθμων για την επιλογή βέλτιστης στρατηγικής προγραμματισμού έργου: Εφαρμογή σε προβλήματα με περιορισμένους πόρους, πολλαπλούς τρόπους εκτέλεσης και στοχαστική διάρκεια των εργασιών
Περίληψη:
Στόχος της παρούσας διπλωματικής εργασίας είναι η ανάπτυξη αλγορίθμων για την επιλογή βέλτιστης στρατηγικής προγραμματισμού έργου. Η εργασία εστιάζει στην περίπτωση του προγραμματισμού έργου με περιορισμένους πόρους, πολλαπλούς τρόπους εκτέλεσης κάθε εργασίας, και στοχαστική διάρκεια εκτέλεσης κάθε τρόπου. Η βελτιστοποίηση γίνεται με χρήση γενετικού αλγορίθμου. Στην εργασία χρησιμοποιούνται μέθοδοι που έχουν αναπτυχθεί για τη βελτιστοποίηση έργου με μοναδικό τρόπο εκτέλεσης εργασιών και στοχαστική διάρκεια καθώς και μέθοδοι για την βελτιστοποίηση έργου με πολλαπλούς τρόπους εκτέλεσης εργασιών και ντετερμινιστική διάρκεια οι οποίες συνδυάστηκαν κατάλληλα για την αντιμετώπιση του υπό μελέτη προβλήματος.
Πραγματοποιήθηκε βιβλιογραφική αναζήτηση για την βηματική κατανόηση και εμβάθυνση στα χαρακτηριστικά του προβλήματος και παράλληλα υλοποίηση των σχετικών αλγορίθμων του αντίστοιχου βήματος, με την εξής σειρά:
1) Προγραμματισμός έργου με περιορισμένους πόρους, μοναδικό τρόπο εκτέλεσης και ντετερμινιστική διάρκεια εργασιών, σχήματα παραγωγής χρονοδιαγραμμάτων και απλές ευρετικές μέθοδοι.
2) Γενετικοί αλγόριθμοι για τον προγραμματισμό έργου με περιορισμένους πόρους, μοναδικό τρόπο εκτέλεσης και ντετερμινιστική διάρκεια εργασιών.
3) Προγραμματισμός έργου με περιορισμένους πόρους, πολλαπλούς τρόπους εκτέλεσης και ντετερμινιστικές διάρκειες εργασιών, προσαρμογή των γενετικών αλγορίθμων σε πολλαπλούς τρόπους εκτέλεσης.
4) Προγραμματισμός έργου περιορισμένους πόρους, πολλαπλούς τρόπους εκτέλεσης και στοχαστικές διάρκειες εργασιών, στρατηγικές προγραμματισμού έργου.
Η στρατηγική που αναπτύσσεται για τον προγραμματισμό έργου με τα παραπάνω χαρακτηριστικά είναι λίστα με ζεύγη εργασιών – τρόπων εκτέλεσης. Οι εργασίες προγραμματίζονται με τη σειρά που βρίσκονται στη λίστα, με τον τρόπο εκτέλεσης που περιέχεται στο ζεύγος της αντίστοιχης εργασίας. Η γενετική κωδικοποίηση που χρησιμοποιείται στον γενετικό αλγόριθμο έχει την μορφή λίστας με ζεύγη εργασιών – τρόπων εκτέλεσης, και για την εξαγωγή της στρατηγικής χρησιμοποιείται διαδικασία αναδιάταξης της λίστας εργασιών – τρόπων εκτέλεσης. Ο γενετικός αλγόριθμος υλοποιεί τις λειτουργίες διασταύρωσης, μετάλλαξης και επιλογής που παρουσιάζονται στη βιβλιογραφία για τον προγραμματισμό έργου με πολλαπλούς τρόπους εκτέλεσης εργασιών.
Η υπολογιστική διερεύνηση γίνεται στις συλλογές έργων της βιβλιοθήκης έργων PSPLIB για 30 εργασίες, με μοναδικό και πολλαπλούς τρόπους εκτέλεσης. Μελετάται η μεταβολή της προσδοκώμενης διάρκειας έργου και της τυπικής απόκλισης της διάρκειας έργου για διαφορετικές στατιστικές κατανομές διάρκειας εργασιών και για διαφορετικές τυπικές αποκλίσεις των κατανομών.
Παράλληλο αποτέλεσμα με την υπολογιστική διερεύνηση του προβλήματος είναι η ανάπτυξη μια βιβλιοθήκης λογισμικού για το προγραμματισμό έργου, δομημένης κατάλληλα, ώστε να μπορεί να εφαρμοστεί σε ένα εύρος προβλημάτων προγραμματισμού έργου. Η ανάπτυξη έγινε σε γλώσσα προγραμματισμού .NET C#.
Contact