Ανάπτυξη υπερευρετικών αλγορίθμων για τον χρονοπρογραμματισμό έργων

Abstract

This doctoral thesis aims to develop hyper-heuristic algorithms for treating project management problems. The thesis is organized into eight chapters. Chapter 1 is an introduction to Project Management and Project Scheduling and describes the contribution of this study in these scientific research fields. In Chapter 2, the mathematical models defining the problems addressed in this thesis are presented. Each model includes a description of the objective function and the constraints that must be taken into account during the search process. Also, there are described the solution representation scheme and the schedule generation scheme used in this study. Chapter 3 describes the classic resource-constrained project scheduling problem, and the recent literature is referred. The extensions of the classic problem are illustrated, as well, including the resource leveling problem, and the resource availability cost problem/ resource investment problem. In addition, recent important studies are referred. Chapter 4 is an introduction to Hyper-heuristic algorithms, and the core idea is described. A summary of the problems that these algorithms have been applied and a literature review are presented. In Chapter 5, the algorithms developed for treating the classic resource-constrained project scheduling problem (resource allocation problem) are presented. Initially, a Greedy Randomized Adaptive Search Procedure-based hyper-heuristic presented and a genetic follows. The efficiency of these algorithms is tested either with solving example projects from the literature or performing computational analysis. Also, a particle swarm optimization-based hyper-heuristic is described and results from treating the dataset of the library PSPLIB are presented along with a comparison with the most known, important and recent algorithmic approaches. Chapter 6 includes the simulated annealing hyper-heuristic developed for treating the resource leveling problem and Chapter 7 illustrates a threshold accepting hyper-heuristic for the biobjective resource allocation and leveling problem. In Chapter 8, a tabu search hyper-heuristic is described for treating resource leveling problem with constrained resources and the resource availability cost problem/ resource investment problem.

Η διδακτορική διατριβή επιδιώκει να αναπτύξει υπερευρετικούς αλγορίθμους για την αντιμετώπιση προβλημάτων χρονοπρογραμματισμού έργων. Η διατριβή οργανώνεται σε οκτώ Κεφάλαια. Στο Κεφάλαιο 1 πραγματοποιείται εισαγωγή στη Διοίκηση Έργων και τον Χρονοπρογραμματισμό Έργων ενώ περιγράφεται η συμβολή της παρούσας διατριβής στα επιστημονικά πεδία που εντάσσεται. Στο Κεφάλαιο 2 παρουσιάζονται μαθηματικά μοντέλα ορισμού των προβλημάτων που αντιμετωπίζονται στην παρούσα διατριβή. Ο ορισμός κάθε προβλήματος περιλαμβάνει την περιγραφή της αντικειμενικής συνάρτησης αλλά και των περιορισμών που πρέπει να ληφθούν υπόψη κατά την επίλυση του κάθε προβλήματος. Επίσης, περιγράφονται οι τρόποι αναπαράστασης λύσης που χρησιμοποιήθηκαν στα πλαίσια της παρούσας διατριβής και αναλύεται ο τρόπος λειτουργίας του σχήματος με το οποίο μετασχηματίζονται τα διανύσματα προτεραιοτήτων που αναπαριστούν κάθε λύση σε χρονοπρογράμματα. Στο Κεφάλαιο 3 περιγράφεται η φύση του κλασικού προβλήματος προγραμματισμού έργων με περιορισμούς στη διαθεσιμότητα πόρου ενώ στη συνέχεια γίνεται αναλυτική περιγραφή της σχετικής διεθνούς βιβλιογραφίας όπου αναφέρονται οι σημαντικότεροι ακριβείς αλγόριθμοι που αναπτύχθηκαν για την εύρεση βέλτιστης λύσης για το πρόβλημα, καθώς και οι σημαντικότερες ευρετικές και μεταευρετικές προσεγγίσεις. Ακόμη περιγράφονται οι επεκτάσεις του κλασικού προβλήματος που αντιμετωπίζονται στα πλαίσια της παρούσας διατριβής όπως το πρόβλημα εξισορρόπησης πόρου και το πρόβλημα κόστους διαθεσιμότητας πόρου/ επένδυσης πόρου, καθώς και οι σημαντικότερες προσεγγίσεις που έχουν προταθεί στη βιβλιογραφία για την αντιμετώπιση των προβλημάτων αυτών. Στο Κεφάλαιο 4 πραγματοποιείται μια εισαγωγή στους υπερευρετικούς αλγορίθμους και περιγράφεται σύντομα η κεντρική ιδέα των προσεγγίσεων αυτών. Επίσης περιγράφεται γενικά ο τρόπος λειτουργίας των υπερευρετικών ως αλγόριθμοι υψηλού επιπέδου ενώ εισάγεται και η λογική που χρησιμοποιούν οι ευρετικές χαμηλού επιπέδου. Ακόμη γίνεται εκτενής αναφορά στη σχετική διεθνή βιβλιογραφία, καθώς και στα προβλήματα για την αντιμετώπιση των οποίων έχουν αναπτυχθεί υπερευρετικοί αλγόριθμοι. Στο Κεφάλαιο 5 παρουσιάζονται τρείς νέοι υπερευρετικοί αλγόριθμοι για το πρόβλημα προγραμματισμού έργων με περιορισμένους πόρους, το οποίο αποτελεί ένα από τα πιο σημαντικά προβλήματα που αντιμετωπίζουν οι διαχειριστές έργων. Αρχικά παρουσιάζεται ένας υπερευρετικός αλγόριθμος GRASP (Greedy Randomized Adaptive Search Procedure) (GRASP-HH) ο οποίος αποτελεί το ανώτερο επίπεδο μιας προσέγγισης πολλαπλών επιπέδων που αναπτύχθηκε στο περιβάλλον ενός λογισμικού διαχείρισης έργων και ενεργεί στις προτεραιότητες των δραστηριοτήτων. Στη συνέχεια περιγράφεται ένας γενετικός υπερευρετικός αλγόριθμος (GAH). Η εφαρμογή του αλγορίθμου σε μια σειρά από τυχαία προβλήματα που κατασκευάστηκαν με μια γνωστή γεννήτρια δικτύων από τη βιβλιογραφία, αποδεικνύει τη δυνατότητα του υπερευρετικού να πετυχαίνει αποτελέσματα αποδεκτής ποιότητας σε λογικό χρόνο. Στο τρίτο μέρος του κεφαλαίου, παρουσιάζεται ένας υπερευρετικός αλγόριθμος βασισμένος σε προσέγγιση βελτιστοποίησης σμήνους σωματιδίων (Particle Swarm Optimization) (PSO-HH). Η αποτελεσματικότητα του υπερευρετικού δοκιμάστηκε στο σύνολο προβλημάτων που περιλαμβάνονται στην πολύ γνωστή και ευρέως χρησιμοποιούμενη βιβλιοθήκη PSPLIB ενώ ταυτόχρονα πραγματοποιήθηκε σύγκριση της απόδοσης του υπερευρετικού με τους σημαντικότερους αλγορίθμους που εμφανίζονται στη διεθνή βιβλιογραφία. Στο Κεφάλαιο 6 παρουσιάζεται μία νέα αλγοριθμική προσέγγιση για την αντιμετώπιση του προβλήματος εξισορρόπησης πόρων (Resource Leveling Problem - RLP). Η διαδικασία αποτελείται από έναν υπερευρετικό αλγόριθμο προσομοιωμένης ανόπτησης ενώ υλοποιήθηκε στο περιβάλλον ενός ευρέως χρησιμοποιούμενου λογισμικού διαχείρισης έργων. Η μελέτη περίπτωσης, καθώς και η πειραματική ανάλυση σε τυχαία δίκτυα δραστηριοτήτων που παρουσιάστηκαν καταδεικνύουν τις δυνατότητές της προτεινόμενης προσέγγισης στην επίλυση σύνθετων προβλημάτων προγραμματισμού. Στο Κεφάλαιο 7 παρουσιάζεται ένας υπερευρετικός αλγόριθμος Αποδοχής Κατωφλίου για την επίλυση ταυτόχρονα των προβλημάτων κατανομής και εξισορρόπησης πόρων. Η προτεινόμενη προσέγγιση αποδείχθηκε αποδοτική για την επίλυση τόσο του προβλήματος κατανομής όσο και εξισορρόπησης πόρων. Ο υπερευρετικός πέτυχε καλύτερα αποτελέσματα κατά την εφαρμογή του σε ένα παράδειγμα έργου από τη βιβλιογραφία, σε σχέση με τον γενετικό αλγόριθμο που αρχικά αντιμετώπιζε το πρόβλημα. Επιπρόσθετα ο προτεινόμενος αλγόριθμος συγκρίνεται με δύο άλλες προσεγγίσεις σε ένα σύνολο τυχαίων έργων και αποδεικνύεται ο πιο αποδοτικός, δαπανώντας ταυτόχρονα τον μικρότερο υπολογιστικό χρόνο. Στο Κεφάλαιο 8 παρουσιάζεται ένας υπερευρετικός αλγόριθμος απαγορευμένης έρευνας (Tabu Search) για την επίλυση προβλημάτων εξισορρόπησης όπως το πρόβλημα εξισορρόπησης περιορισμένων πόρων με την αποδεκτή διάρκεια έργου να είναι ίση ή και μεγαλύτερη από την αρχική / ελάχιστη διάρκεια του έργου, καθώς και του αντίστοιχου προβλήματος κόστους διαθεσιμότητας πόρων. Η εφαρμογή του αλγορίθμου σε τρεις περιπτώσεις έργων έδειξε ότι η προτεινόμενη διαδικασία πετυχαίνει αξιόλογα αποτελέσματα στο χειρισμό προβλημάτων βελτιστοποίησης χρήσης πόρων.