Decision making in project management: multi objective extended resource constrained project scheduling

Abstract

A holistic approach is proposed for defining the resource constrained project scheduling problem (RCPSP). The doctoral thesis' aim is to give a formulation of the project scheduling problem where all deterministic aspects that have been previously explored in the relevant literature are covered. Our goal is to provide a way to model and solve project scheduling problems as they actually are, without compromises other than the assumption that the given inputs are realistic. An appropriate mathematical formulation along with a concise solution process, covering both the single and multi-objective case, are presented. Based on this model an adaptive evolutionary algorithm is implemented to solve the unified version of the problem along with and Add in for MS Project to provide an easy to use interface to the project managers. The efficiency of the proposed approach is compared to existing implementations through a number of experiments. The experiments are grouped in two classes: in the first one the best known results from each variation and extension of the single objective RCPSP are compared to the results given by the proposed algorithm and in the second one the multi-objective approach is compared to the single-objective results given in the same test cases appropriately adapted. Finally, the application of the proposed approach in real situations is illustrated through a case study on a medium sized project (200 activities) taken from the GIS domain.The results show that the usage of the holistic model doesn't affect the quality of results or the needed CPU-time when compared to the existing RCPSP formulations, whereas it adds the ability to describe more realistically any complex project scheduling problem. We overcome the raise of complexity and the infeasibilities by using penalty functions when relaxation of the constraints is needed. In the multi-objective case the algorithm is capable of providing multiple solution scenarios that are generated either based on the simple Pareto front or on a weighted approximation of it.

Στην παρούσα Διατριβή προτείνεται μια ολιστική προσέγγιση για τον ορισμό του προβλήματος προγραμματισμού έργων υπό συνθήκες περιορισμένων πόρων \selectlanguage{english}(RCPSP)\selectlanguage{greek}. Στόχος είναι η παροχή μιας ενιαίας εννοιολογικής έκφρασης του προβλήματος συμπεριλαμβάνοντας όλες τις διαφορετικές ντετερμινιστικές εκδοχές και παραλλαγές που απαντώνται στη βιβλιογραφία και έχουν πρακτική σημασία. Με βάση την ενιαία εννοιολογική προσέγγιση παρέχεται και η αντίστοιχη μαθηματική μοντελοποίηση του προβλήματος, όπως και η διαδικασία επίλυσης και οι απαιτούμενοι αλγόριθμοι για την υλοποίηση αυτής. Το πρόβλημα αντιμετωπίζεται ως βελτιστοποίηση ως προς μια ή περισσότερες μεταβλητές – στόχους. Απώτερος στόχος είναι η παροχή ενός τρόπου μοντελοποίησης και επίλυσης των προβλημάτων χρονοπρογραμματισμού όπως αυτά συναντώνται στην πράξη χωρίς άλλους συμβιβασμούς και τροποποιήσεις των δεδομένων για να ταιριάξουν στο μοντέλο πέρα από την υπόθεση ότι τα εισαγόμενα στοιχεία προσεγγίζουν ικανοποιητικά την πραγματικότητα και είναι ντετερμινιστικά.Στηριζόμενοι στο νέο ενιαίο μοντέλο, σχεδιάστηκε ένας υβριδικός αλγόριθμος, καλούμενος διαχειριστής (moderator), που προσαρμόζεται στο μέγεθος και τα χαρακτηριστικά του προς επίλυση προβλήματος και βελτιστοποιεί τόσο ως προς έναν όσο και ως προς πολλαπλούς στόχους, υπολογίζοντας Pareto βέλτιστες λύσεις και λαμβάνοντας ή μη υπόψη προτεραιότητες μεταξύ των αντικειμενικών στόχων.Αποδείχθηκε πειραματικά ότι η χρήση του προτεινόμενου αλγορίθμου αυξάνει την ακρίβεια και σε κάποιες περιπτώσεις υπολογίζει και καλύτερες λύσεις χωρίς να επηρεάζει αρνητικά το χρόνο επίλυσης του προβλήματος. Επομένως, έχουμε έναν αξιόπιστο τρόπο για την επίλυση προβλημάτων χρονοπρογραμματισμού έργων είτε πρόκειται για απλά και κλασσικά προβλήματα RCPSP είτε σύνθετους συνδυασμούς παραλλαγών και επεκτάσεων αυτού του τύπου προβλημάτων. Επιτυγχάνεται με αυτόν τον τρόπο η παροχή στους διευθυντές έργων ενός ευέλικτου μοντέλου το οποίο προσαρμόζεται στις ανάγκες τους αντί του ισχύοντος καθεστώτος όπου το πρόβλημα έπρεπε να προσαρμοστεί στο μοντέλο. Επιπλέον, παρέχεται και ένας διαφανής τρόπος επίλυσης του προβλήματος χωρίς ιδιαίτερα πολύπλοκα ή χρονοβόρα βήματα.Η αυξημένη πολυπλοκότητα και η υψηλή πιθανότητα ανυπαρξίας εφικτών λύσεων στις πιο πολύπλοκες περιπτώσεις αντιμετωπίζεται με χαλάρωση των περιορισμών όταν αυτό κρίνεται αναγκαίο και με βάση πάντοτε τις επιλογές του διευθυντή έργου. Στην περίπτωση των πολλαπλών στόχων παράγονται πολλαπλά εναλλακτικά σενάρια με βάση τις Pareto βέλτιστες λύσεις ή προσεγγίσεις αυτών, οι οποίες λαμβάνουν υπόψη και τα βάρη που ορίστηκαν για κάθε στόχο.