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

Μπεγλερίδου, Σταυρούλα

dc.contributor.advisor	Κορωνάκος, Γρηγόριος
dc.contributor.author	Μπεγλερίδου, Σταυρούλα
dc.date.accessioned	2026-03-19T10:29:27Z
dc.date.available	2026-03-19T10:29:27Z
dc.date.issued	2026-01
dc.identifier.uri	https://dione.lib.unipi.gr/xmlui/handle/unipi/19031
dc.description	Διαθέσιμο μετά τις 31/03/2029
dc.description.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. Για την εξέταση της επίδοσης τους εφαρμόζονται σε πραγματικά και σε συνθετικά δεδομένα, τα οποία έχουν χρησιμοποιηθεί για παρόμοιους σκοπούς στη βιβλιογραφία.	el
dc.format.extent	43	el
dc.language.iso	el	el
dc.publisher	Πανεπιστήμιο Πειραιώς	el
dc.rights	Αναφορά Δημιουργού 3.0 Ελλάδα	*
dc.rights	Αναφορά Δημιουργού - Παρόμοια Διανομή 3.0 Ελλάδα	*
dc.rights	Αναφορά Δημιουργού - Παρόμοια Διανομή 3.0 Ελλάδα	*
dc.rights	Αναφορά Δημιουργού - Παρόμοια Διανομή 3.0 Ελλάδα	*
dc.rights.uri	http://creativecommons.org/licenses/by-sa/3.0/gr/	*
dc.title	Παραλλαγές του αλγορίθμου BuildHull με χρήση τεχνικών παράλληλου προγραμματισμού	el
dc.title.alternative	Variants of the BuildHull algorithm using parallel programming techniques	el
dc.type	Master Thesis	el
dc.contributor.department	Σχολή Τεχνολογιών Πληροφορικής και Επικοινωνιών. Τμήμα Πληροφορικής	el
dc.description.abstractEN	Data Envelopment Analysis (DEA) is a non-parametric method for assessing the relative efficiency of decision-making units (DMUs) that transform inputs into outputs. DEA characterizes the Production Possibility Set (PPS) and identifies its boundary, known as the efficiency frontier, which is formed by efficient units and envelops inefficient ones. Efficiency scores are computed by solving a linear program (LP) for each DMU, which can lead to substantial computational cost in large-scale settings. To address this issue, Dulá (2011) proposed the BuildHull algorithm, which accelerates DEA evaluation by incrementally constructing the efficiency frontier through sequential LP feasibility tests, thereby reducing the number and size of LPs that must be solved. This dissertation further advances this line of research by proposing two parallel variants of the BuildHull algorithm. The first variant exploits data-level parallelism via MATLAB’s parfor construct, while the second adopts the Single Program Multiple Data (SPMD) paradigm using MATLAB’s spmd framework, enabling more flexible task allocation and inter-worker communication. Both approaches aim to by parallelize BuildHull algorithm. Their performance is evaluated using real and synthetic datasets commonly employed in DEA literature.	el
dc.contributor.master	Πληροφορική	el
dc.subject.keyword	Γραμμικά προβλήματα	el
dc.subject.keyword	Αλγορίθμος BuildHull	el
dc.subject.keyword	Επαναληπτικός βρόγχος	el
dc.subject.keyword	SPMD	el
dc.subject.keyword	Parfor	el
dc.subject.keyword	MATLAB	el
dc.subject.keyword	Περιβάλλουσα ανάλυση δεδομένων	el
dc.subject.keyword	ΠΑΔ	el
dc.subject.keyword	LP	el
dc.subject.keyword	DEA	el
dc.subject.keyword	DMU	el
dc.subject.keyword	Μονάδες απόφασης	el
dc.date.defense	2026-01

Αρχεία σε αυτό το τεκμήριο

Αρχεία	Μέγεθος	Τύπος	Προβολή
Δεν υπάρχουν αρχεία που να σχετίζονται με αυτό το τεκμήριο.

Αυτό το τεκμήριο εμφανίζεται στις ακόλουθες συλλογές

Τμήμα Πληροφορικής
Department of Informatics

Εμφάνιση απλής εγγραφής

Εκτός από όπου διευκρινίζεται διαφορετικά, το τεκμήριο διανέμεται με την ακόλουθη άδεια:
Αναφορά Δημιουργού 3.0 Ελλάδα