Ανάθεση προσωπικού σε ομάδες εργασίας και το πρόβλημα του σταθερού γάμου
Στη Θεωρία Γραφημάτων ο γάμος εκφράζεται μέσω προβλημάτων ταιριάσματος (matching problems) σε γραφήματα όπου οι ακμές αναπαριστούν συμβατότητα, δηλ., δύο κορυφές που συνδέονται με ακμή μπορούν να ταιριαστούν ή να "παντρευτούν". Ταίριασμα σε δοσμένο γράφημα είναι ένα υπογράφημά του στο οποί...
| Κύριος συγγραφέας: | |
|---|---|
| Άλλοι συγγραφείς: | |
| Μορφή: | Thesis |
| Γλώσσα: | Greek |
| Έκδοση: |
2019
|
| Θέματα: | |
| Διαθέσιμο Online: | http://hdl.handle.net/10889/12327 |
| id |
nemertes-10889-12327 |
|---|---|
| record_format |
dspace |
| institution |
UPatras |
| collection |
Nemertes |
| language |
Greek |
| topic |
Αλγόριθμοι SMP FCP Algorithms 511.5 |
| spellingShingle |
Αλγόριθμοι SMP FCP Algorithms 511.5 Ζαχαριά, Αθανασία Ανάθεση προσωπικού σε ομάδες εργασίας και το πρόβλημα του σταθερού γάμου |
| description |
Στη Θεωρία Γραφημάτων ο γάμος εκφράζεται μέσω προβλημάτων ταιριάσματος (matching problems) σε γραφήματα όπου οι ακμές αναπαριστούν συμβατότητα, δηλ., δύο κορυφές που συνδέονται με ακμή μπορούν να ταιριαστούν ή να "παντρευτούν". Ταίριασμα σε δοσμένο γράφημα είναι ένα υπογράφημά του στο οποίο κάθε κορυφή έχει βαθμό 1. Όταν στο ταίριασμα υπάρχουν όλες οι κορυφές του γραφήματος, το ταίριασμα καλείται πλήρες (perfect matching). Στόχος των προβλημάτων ταιριάσματος είναι η δημιουργία μέγιστου πλήθους συμβατών ζευγαριών. Επιπλέον, ένα ταίριασμα καλείται σταθερό (stable) όταν δεν υπάρχουν ζευγάρια που τα μέλη τους να προτιμούν το ένα το άλλο περισσότερο από τους συντρόφους τους στο ταίριασμα.
Στο πλαίσιο της παρούσας διπλωματικής εργασίας θα ασχοληθούμε με ένα ιδιαίτερο πρόβλημα ταιριάσματος: το Πρόβλημα του Σταθερού Γάμου (the Stable Marriage Problem - SMP). Στη βασική εκδοχή του προβλήματος, δίνονται δύο ισομεγέθη σύνολα αγοριών, Β, και κοριτσιών, G. Κάθε μέλος του συνόλου B (αντίστοιχα του G) διατηρεί τη δική του διαταγμένη λίστα προτιμήσεων για κάθε στοιχείο του συνόλου G (αντίστοιχα του B). Οι προτιμήσεις δεν είναι κατ΄ ανάγκη συμμετρικές και δεν μεταβάλλονται. Στόχος του προβλήματος είναι η δημιουργία σταθερού πλήρους ταιριάσματος, δηλ., η πραγματοποίηση σταθερού "γάμου" μεταξύ όλων των συμμετεχόντων.
Το Πρόβλημα του Σταθερού Γάμου έχει μελετηθεί εκτενώς στην βιβλιογραφία, κυρίως λόγω της ευρείας πρακτικής εφαρμογής του σε πολλούς διαφορετικούς τομείς. Επιπλέον, η ανάπτυξη του αλγορίθμου των Gale και Shapley [D. Gale, L. S. Shapley. College Admissions and the Stability of Marriage. American Mathematical Monthly, 69, pp. 9–14, 1962] για την επίλυσή του έφερε σημαντικές αλλαγές, ιδιαίτερα στους κλάδους των Οικονομικών, της Υγείας και της Πληροφορικής. Χαρακτηριστικές εφαρμογές εμπεριέχουν προβλήματα γνωριμιών, προβλήματα ανάθεσης, όπως π.χ., μαθητών σε σχολεία, ειδικευόμενων γιατρών σε νοσοκομεία, καθώς και προβλήματα ανάθεσης πόρων, όπως π.χ., κατανομή φορτίου κίνησης (load balancing) στο Διαδίκτυο και τον Παγκόσμιο Ιστό. Ωστόσο, η πιο αξιοπρόσεκτη, ίσως, εφαρμογή σχετίζεται με τον εντοπισμό κατάλληλων δοτών νεφρών για ασθενείς που χρήζουν μεταμόσχευσης.
Στόχος της παρούσας διπλωματικής εργασίας είναι αφενός η επισκόπηση της βιβλιογραφίας σχετικά με τη γραφοθεωρητική μελέτη και ανάλυση του Προβλήματος του Σταθερού Γάμου και η παρουσίαση σημαντικών υπαρχουσών εφαρμογών, και αφετέρου η ανάπτυξη αλγοριθμικών λύσεων/συστάσεων για το πρόβλημα ανάθεσης προσωπικού σε ομάδες εργασίας, με βάση αντίστοιχες προσεγγίσεις για το Πρόβλημα του Σταθερού Γάμου, και η θεωρητική και πειραματική μελέτη τους. |
| author2 |
Κακλαμάνης, Χρήστος |
| author_facet |
Κακλαμάνης, Χρήστος Ζαχαριά, Αθανασία |
| format |
Thesis |
| author |
Ζαχαριά, Αθανασία |
| author_sort |
Ζαχαριά, Αθανασία |
| title |
Ανάθεση προσωπικού σε ομάδες εργασίας και το πρόβλημα του σταθερού γάμου |
| title_short |
Ανάθεση προσωπικού σε ομάδες εργασίας και το πρόβλημα του σταθερού γάμου |
| title_full |
Ανάθεση προσωπικού σε ομάδες εργασίας και το πρόβλημα του σταθερού γάμου |
| title_fullStr |
Ανάθεση προσωπικού σε ομάδες εργασίας και το πρόβλημα του σταθερού γάμου |
| title_full_unstemmed |
Ανάθεση προσωπικού σε ομάδες εργασίας και το πρόβλημα του σταθερού γάμου |
| title_sort |
ανάθεση προσωπικού σε ομάδες εργασίας και το πρόβλημα του σταθερού γάμου |
| publishDate |
2019 |
| url |
http://hdl.handle.net/10889/12327 |
| work_keys_str_mv |
AT zachariaathanasia anathesēprosōpikouseomadesergasiaskaitoproblēmatoustatherougamou AT zachariaathanasia assigningpersonneltoworkinggroupsandthestablemarriageproblem |
| _version_ |
1771297149953245184 |
| spelling |
nemertes-10889-123272022-09-05T05:38:31Z Ανάθεση προσωπικού σε ομάδες εργασίας και το πρόβλημα του σταθερού γάμου Assigning personnel to working groups and the stable marriage problem Ζαχαριά, Αθανασία Κακλαμάνης, Χρήστος Κακλαμάνης, Χρήστος Καραγιάννης, Ιωάννης Παπαϊωάννου, Ευαγγελία Zacharia, Athanasia Αλγόριθμοι SMP FCP Algorithms 511.5 Στη Θεωρία Γραφημάτων ο γάμος εκφράζεται μέσω προβλημάτων ταιριάσματος (matching problems) σε γραφήματα όπου οι ακμές αναπαριστούν συμβατότητα, δηλ., δύο κορυφές που συνδέονται με ακμή μπορούν να ταιριαστούν ή να "παντρευτούν". Ταίριασμα σε δοσμένο γράφημα είναι ένα υπογράφημά του στο οποίο κάθε κορυφή έχει βαθμό 1. Όταν στο ταίριασμα υπάρχουν όλες οι κορυφές του γραφήματος, το ταίριασμα καλείται πλήρες (perfect matching). Στόχος των προβλημάτων ταιριάσματος είναι η δημιουργία μέγιστου πλήθους συμβατών ζευγαριών. Επιπλέον, ένα ταίριασμα καλείται σταθερό (stable) όταν δεν υπάρχουν ζευγάρια που τα μέλη τους να προτιμούν το ένα το άλλο περισσότερο από τους συντρόφους τους στο ταίριασμα. Στο πλαίσιο της παρούσας διπλωματικής εργασίας θα ασχοληθούμε με ένα ιδιαίτερο πρόβλημα ταιριάσματος: το Πρόβλημα του Σταθερού Γάμου (the Stable Marriage Problem - SMP). Στη βασική εκδοχή του προβλήματος, δίνονται δύο ισομεγέθη σύνολα αγοριών, Β, και κοριτσιών, G. Κάθε μέλος του συνόλου B (αντίστοιχα του G) διατηρεί τη δική του διαταγμένη λίστα προτιμήσεων για κάθε στοιχείο του συνόλου G (αντίστοιχα του B). Οι προτιμήσεις δεν είναι κατ΄ ανάγκη συμμετρικές και δεν μεταβάλλονται. Στόχος του προβλήματος είναι η δημιουργία σταθερού πλήρους ταιριάσματος, δηλ., η πραγματοποίηση σταθερού "γάμου" μεταξύ όλων των συμμετεχόντων. Το Πρόβλημα του Σταθερού Γάμου έχει μελετηθεί εκτενώς στην βιβλιογραφία, κυρίως λόγω της ευρείας πρακτικής εφαρμογής του σε πολλούς διαφορετικούς τομείς. Επιπλέον, η ανάπτυξη του αλγορίθμου των Gale και Shapley [D. Gale, L. S. Shapley. College Admissions and the Stability of Marriage. American Mathematical Monthly, 69, pp. 9–14, 1962] για την επίλυσή του έφερε σημαντικές αλλαγές, ιδιαίτερα στους κλάδους των Οικονομικών, της Υγείας και της Πληροφορικής. Χαρακτηριστικές εφαρμογές εμπεριέχουν προβλήματα γνωριμιών, προβλήματα ανάθεσης, όπως π.χ., μαθητών σε σχολεία, ειδικευόμενων γιατρών σε νοσοκομεία, καθώς και προβλήματα ανάθεσης πόρων, όπως π.χ., κατανομή φορτίου κίνησης (load balancing) στο Διαδίκτυο και τον Παγκόσμιο Ιστό. Ωστόσο, η πιο αξιοπρόσεκτη, ίσως, εφαρμογή σχετίζεται με τον εντοπισμό κατάλληλων δοτών νεφρών για ασθενείς που χρήζουν μεταμόσχευσης. Στόχος της παρούσας διπλωματικής εργασίας είναι αφενός η επισκόπηση της βιβλιογραφίας σχετικά με τη γραφοθεωρητική μελέτη και ανάλυση του Προβλήματος του Σταθερού Γάμου και η παρουσίαση σημαντικών υπαρχουσών εφαρμογών, και αφετέρου η ανάπτυξη αλγοριθμικών λύσεων/συστάσεων για το πρόβλημα ανάθεσης προσωπικού σε ομάδες εργασίας, με βάση αντίστοιχες προσεγγίσεις για το Πρόβλημα του Σταθερού Γάμου, και η θεωρητική και πειραματική μελέτη τους. In terms of Graph Theory, marriage is expressed as a matching problem. In the simplest form of a matching problem, we are given a graph where the edges represent compatibility, that is vertices connected by an edge can be paired together or married. Given a graph G=(V,E), a matching is a subgraph of G where very node has degree 1, so everybody can be married just to one person. When every node is involved in a matching, then it is called a perfect matching. The goal is to create the maximum number of compatible pairs. Furthermore, a matching is stable when it does not contain couples whose members prefer each other to their mates in the matching. In the context of this MSc thesis we will study a special matching problem known as the Stable Marriage Problem (SMP). In its basic version, we are given N boys and N girls, boys can only be paired to girls and vice versa, each boy (resp. girl) has his own ranked preference list of all the girls (resp. girls), the lists are complete and there are no ties and preferences are not necessarily symmetric and cannot change over time. The goal is to find a perfect matching that is stable. Τhe Stable Marriage Problem has been extensively studied in the literature, mainly due to its wide application in several areas. In addition, the algorithm suggested by Gale and Shapley [D. Gale, L. S. Shapley. College Admissions and the Stability of Marriage. American Mathematical Monthly, 69, pp. 9–14, 1962] brought about significant changes especially in the fields of Economics, Health and Computer Science. Indicative applications include dating problems, where the objective is to match compatible people together, assignment problems, e.g., matching students to schools or interns to hospitals, resource allocation problems, e.g., load balancing traffic on the Internet. However, maybe the most fascinating relevant application is about finding compatible kidney donors for patients needing a transplant. The objective of this MSc thesis is two-fold: on the one hand, we plan to review the relevant literature in terms of the graph-theoretic study and analysis of the Stable Marriage Problem and present important existing applications; on the other hand, we plan to suggest algorithmic solutions/recommendations for the problem of assigning personnel to working groups, based on approaches to the Stable Marriage Problem, also providing theoretical analysis and experimental evaluation. 2019-06-30T12:24:19Z 2019-06-30T12:24:19Z 2019-02-12 Thesis http://hdl.handle.net/10889/12327 gr 0 application/pdf |
