Παραλλαγές του αλγορίθμου BuildHull με χρήση τεχνικών παράλληλου προγραμματισμού

Abstract

Η Περιβάλλουσα Ανάλυση Δεδομένων-ΠΑΔ (Data Envelopment Analysis-DEA) αποτελεί μια μη-παραμετρική μέθοδο για την αξιολόγηση της σχετικής αποδοτικότητας μονάδων αποφάσεων. Η κάθε μονάδα απόφασης (Decision Making Unit - DMU) χρησιμοποιεί εισροές για την παραγωγή εκροών. Η ΠΑΔ εντοπίζει το σύνορο του συνόλου παραγωγικών δυνατοτήτων (Production Possibility Set-PPS) ενός συνόλου μονάδων απόφασης, το οποίο καλείται σύνορο αποδοτικότητας. Το σύνορο αποδοτικότητας (efficient frontier) ορίζεται από τις μονάδες που είναι αποδοτικές και περικλείει τις μη αποδοτικές. Η ΠΑΔ απαιτεί την επίλυση ενός γραμμικού προγράμματος (Linear Program-LP) για τον υπολογισμό της αποδοτικότητας κάθε μονάδας απόφασης. Ωστόσο, στην περίπτωση που η αξιολόγηση αφορά δεδομένα μεγάλης κλίμακας, το κόστος υπολογισμού είναι αρκετά υψηλό. Ο αλγόριθμος BuildHull που προτάθηκε από τον Dulá (2011) για την επιτάχυνση της αξιολόγησης μέσω ΠΑΔ. Ο αλγόριθμος βασίζεται στην σειριακή αξιολόγηση των μονάδων και αρχικά εντοπίζει τις μονάδες που συγκροτούν το σύνορο αποδοτικότητας. Έπειτα, το σύνολο των αποδοτικών μονάδων χρησιμοποιείται για τον σχηματισμό ενός γραμμικού προγράμματος που εφαρμόζεται επαναληπτικά για τον υπολογισμό της αποδοτικότητας των μην αποδοτικών μονάδων. Η παρούσα διατριβή στοχεύει στην περαιτέρω επιτάχυνση της αξιολόγησης προτείνοντας δύο νέες παραλλαγές του αλγορίθμου BuildHull, οι οποίες βασίζονται σε τεχνικές παράλληλου υπολογισμού. Ειδικότερα, η μια παράλληλη εκδοχή του αλγορίθμου BuildHull βασίζεται σε έναν παράλληλο βρόχο επανάληψης, χρησιμοποιώντας την υλοποίηση parfor() του MATLAB. Η δεύτερη εκδοχή, βασίζεται στο μοντέλο παράλληλου προγραμματισμού Μοναδικό Πρόγραμμα Πολλαπλά Δεδομένα (Single Program Multiple Data-SPMD), χρησιμοποιώντας την υλοποίηση spmd() του MATLAB. Για την εξέταση της επίδοσης τους εφαρμόζονται σε πραγματικά και σε συνθετικά δεδομένα, τα οποία έχουν χρησιμοποιηθεί για παρόμοιους σκοπούς στη βιβλιογραφία.