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

Abstract

The aim of this doctoral thesis is to develop a Decision Support System (DSS) for addressing project scheduling problems. In DSS, both new scheduling models and new computational methods are included. The algorithms used into the DSS were chosen after extensive computational analysis of their performance. The doctoral thesis is divided into nine chapters. In Chapter 1 the concept of the project is defined and the important role of project management in project successful realization is explained. The concept of the DSS is defined, its structure is described and project management oriented DSS are reported. Finally, the DSS structure developed in this thesis is outlined. In Chapter 2 concepts of single-objective and multi-objective optimization are introduced and basic concepts relating to their complexity are mentioned, and the main features of heuristics and metaheuristics algorithms are described. Specific reference is made to Pareto metaheuristics algorithms for addressing multi-objective problems, especially to the three Pareto metaheuristics algorithms PAES, PESA2 and NSGA2, which are used in most of the problems of the thesis. Chapter 3 describes in detail the computational analysis applied for the evaluation of algorithms. The factors taken into account in the computational analysis are specified, the construction of the reference dataset in assessing algorithms is described, the criteria for evaluating the algorithms are analyzed, and the statistical techniques used to extract the conclusions. Chapter 4 focuses on the problem of the time/cost trade-off in a project whose activities can be performed with discrete time/cost combinations. The general form of the problem is resolved by the three Pareto metaheuristics algorithms, while algorithms for the three specific cases of the problem arc proposed -minimizing the direct cost of the project under a given duration of the project, minimizing project duration under a given budget, and minimizing the overall cost of the project. Chapter 5 proposes a model to optimize the quality of project scheduling with discrete time/cost combinations. The problem is formulated as a multi-objective optimization problem with three objective functions, the goal being the time/cost/robustness trade-off of the schedule, and is solved by the three Pareto algorithms. Chapter 6 presents a new model for resource leveling. The problem is treated as multi-objective -minimizing simultaneously resource leveling and the duration of the project, and is resolved by the three Pareto metaheuristics. Chapter 7 is devoted to the construction of the activity-on-arc representation of a project that is given the activity-on-node representation of a project, construct its activity-on-arc representation. The solution procedure is based on an algorithm known from literature for solving the NP-hard dummy-arc problem, i.e. an activity-on-arc representation of a project that has the minimum number of dummy arcs given that it has the minimum number of nodes. For the solution of the resulting set covering problem two variants of a Greedy Randomized Adaptive Search Procedure (GRASP) are proposed. Chapter 8 describes and compares three approaches for dealing with stochastic networks: the Monte Carlo simulation, the PERT method and the modelization of project scheduling via fuzzy sets. Chapter 9 contains the conclusions and issues for further research. Appendix describes the Decision Support System, which was coded in Visual Basic 6.0 and operates under Microsoft Project.

Στα πλαίσια της διδακτορικής διατριβής αναπτύσσεται ένα Σύστημα Υποστήριξης Αποφάσεων (ΣΥΑ) για την αντιμετώπιση προβλημάτων του χρονοπρογραμματισμού έργων. Στο ΣΥΑ, αφενός, ενσωματώνονται νέα μοντέλα του χρονοπρογραμματισμού έργων και, αφετέρου, χρησιμοποιούνται νέες υπολογιστικές μέθοδοι. Οι αλγόριθμοι που ενσωματώθηκαν στο ΣΥΑ επελέγησαν ύστερα από εκτενή στατιστική ανάλυση της επίδοσής τους. Η διατριβή οργανώνεται σε εννέα κεφάλαια. Στο Κεφάλαιο 1 ορίζεται η έννοια του έργου και αιτιολογείται ο σημαντικός ρόλος της διαχείρισης των έργων στην επιτυχή υλοποίησή τους. Ορίζονται τα ΣΥΑ, περιγράφεται η δομή τους και καταγράφονται όσα έχουν αναπτυχθεί ειδικά για τη διαχείριση έργων. Τέλος, αναφέρονται συνοπτικά οι δυνατότητες του ΣΥΑ που αναπτύχθηκε στα πλαίσια της διατριβής. Στο Κεφάλαιο 2 εισάγονται τα προβλήματα μονο- και πολυσκοπικής βελτιστοποίησης, καθώς και βασικές έννοιες που αφορούν την πολυπλοκότητά τους, και περιγράφονται τα βασικά χαρακτηριστικά των ευρετικών και μεταευρετικών αλγορίθμων. Ιδιαίτερη αναφορά γίνεται στους Pareto μεταευρετικούς αλγορίθμους που εφαρμόζονται στην αντιμετώπιση πολυσκοπικών προβλημάτων, ειδικά στους πολυσκοπικούς αλγορίθμους PAES, PESA2 και NSGA2 που χρησιμοποιούνται στην πλειονότητα των προβλημάτων της διατριβής. Στο Κεφάλαιο 3 περιγράφεται αναλυτικά η διαδικασία της υπολογιστικής ανάλυσης που εφαρμόσθηκε για την αξιολόγηση των αλγορίθμων. Καθορίζονται οι παράγοντες που λαμβάνονται υπόψη στην υπολογιστική ανάλυση, περιγράφεται η διαδικασία δημιουργίας των δικτύων αναφοράς στα οποία αξιολογούνται οι αλγόριθμοι, αναλύονται τα κριτήρια αξιολόγησης των αλγορίθμων και οι χρησιμοποιούμενες στατιστικές τεχνικές για την εξαγωγή των συμπερασμάτων. Το Κεφάλαιο 4 επικεντρώνεται στο πρόβλημα της αντιστάθμισης χρόνου/κόστους σε ένα έργο που οι δραστηριότητες του μπορούν να εκτελεστούν με διακριτούς συνδυασμούς χρόνου/κόστους. Η γενική μορφή του προβλήματος επιλύεται με τους τρεις πολυσκοπικούς αλγορίθμους, ενώ αναπτύσσονται αλγόριθμοι για τις τρεις ειδικές περιπτώσεις του προβλήματος -ελαχιστοποίηση του άμεσου κόστους με δεδομένο περιορισμό στη χρονική διάρκεια του έργου, ελαχιστοποίηση της χρονικής διάρκειας με δεδομένο προϋπολογισμό, και ελαχιστοποίηση του συνολικού κόστους του έργου. Στο Κεφάλαιο 5 προτείνεται ένα μοντέλο για τη βελτιστοποίηση της ευρωστίας του χρονοδιαγράμματος έργου με διακριτούς συνδυασμούς χρόνου/κόστους. Το πρόβλημα διατυπώνεται ως πολυσκοπικό πρόβλημα βελτιστοποίησης με τρεις αντικειμενικές συναρτήσεις, και στόχο την αντιστάθμιση χρόνου/κόστους/ευρωστίας του χρονοδιαγράμματος, και επιλύεται με τους τρεις πολυσκοπικούς αλγορίθμους. Στο Κεφάλαιο 6 παρουσιάζεται ένα μοντέλο για την αντιστάθμιση της εξομάλυνσης της διακύμανσης της χρήσης ενός πόρου του έργου και της χρονικής του διάρκειας. Το πρόβλημα αντιμετωπίζεται για πρώτη φορά ως πολυσκοπικό -ελαχιστοποίηση της διακύμανσης των πόρων και της χρονικής διάρκειας του έργου- και επιλύεται με τους τρεις πολυσκοπικούς αλγορίθμους. Το Κεφάλαιο 7 αφιερώνεται στον σχεδίασμά του δικτύου με τις δραστηριότητες στα τόξα. Το πρόβλημα είναι πολυπλοκότητας NP-hard, μετατρέπεται στο set covering πρόβλημα με έναν γνωστό αλγόριθμο από τη βιβλιογραφία, και επιλύεται με δύο παραλλαγές ενός αλγορίθμου GRASP. Στο Κεφάλαιο 8 περιγράφονται και συγκρίνονται τρεις μέθοδοι που χρησιμοποιούνται για την επίλυση στοχαστικών δικτύων, η Monte Carlo προσομοίωση, η μέθοδος PERT και μια μέθοδος που εφαρμόζει ασαφείς αριθμούς. Το Κεφάλαιο 9 περιέχει τα συμπεράσματα και προτείνονται θέματα για περαιτέρω έρευνα. Στο Παράρτημα περιγράφεται το Σύστημα Υποστήριξης Αποφάσεων, το οποίο αναπτύχθηκε σε γλώσσα προγραμματισμού Visual Basic 6.0 και λειτουργεί στο περιβάλλον του Microsoft Project.