Πλοήγηση ανά Επιβλέπων "Mourtos, Ioannis"

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Α Β Γ Δ Ε Ζ Η Θ Ι Κ Λ Μ Ν Ξ Ο Π Ρ Σ Τ Υ Φ Χ Ψ Ω

Τώρα δείχνει 1 - 3 από 3

Logic-based Benders decomposition for transportation and manufacturing problems
(23-01-2024) Αυγερινός, Ιωάννης; Avgerinos, Ioannis; Athens University of Economics and Business, Department of Management Science and Technology; Kritikos, Emmanouil; Androutsopoulos, Konstantinos; Giannikos, Ioannis; Emiris, Dimitrios; Kaparis, Konstantinos; Papavasiliou, Anthony; Mourtos, Ioannis
Η παρούσα διατριβή εξετάζει την Αποσύνθεση Logic-Based Benders, μια σύγχρονη μέθοδο διαχωρισμού, προερχόμενη από την κλασσική Αποσύνθεση Benders. Καθώς ένα μεγάλης κλίμακας πρόβλημα βελτιστοποίησης δεν μπορεί να επιλυθεί απευθείας με τις τυπικές μεθόδους ακριβείας, είναι εύλογος ο διαχωρισμός του σε δύο υπομέρη, καθένα από τα οποία μπορεί να λυθεί βέλτιστα πιο εύκολα. Τα δύο υπομέρη ανταλλάσσουν γνώση επαναληπτικά, χρησιμοποιώντας γραμμικές ανισότητες που ονομάζονται Τομές Benders.Η ευελιξία της μεθόδου μας επιτρέπει να διαχειριζόμαστε περίπλοκα προβλήματα μεγάλης κλίμακας, προερχόμενα από πραγματικά περιβάλλοντα μεταφοράς και βιομηχανίας. Με αφορμή τέτοιες περιπτώσεις, δείχνουμε διαφορετικές προσεγγίσεις της μεθόδου για να υπολογίσουμε σχεδόν βέλτιστες λύσεις σε εύλογο χρόνο για προβλήματα βιομηχανικής κλίμακας, δηλαδή για εκατοντάδες παραγγελίες προς παραγωγή ή παράδοση. Πέρα από την πρακτική συνεισφορά της διατριβής, που αποτελείται από τη συγκέντρωση αποδοτικών σχημάτων LBBD για τα υπό εξέταση προβλήματα, η τεχνική συνεισφορά αφορά τη δημιουργία έγκυρων και ισχυρών τομών Benders, που μπορούν να χρησιμοποιηθούν για γενικευμένες κατηγορίες προβλημάτων βελτιστοποίησης. Οι περιπτώσεις αυτές αφορούν προβλήματα ακέραιων μη δυαδικών μεταβλητών ή την απαλοιφή γειτονιών πολλαπλών λύσεων με χρήση μίας τομής, χωρίς απώλεια της βελτιστότητας.Κυριάρχο θέμα της διατριβής αποτελεί η εφαρμοσιμότητα της μεθόδου, όπως απδεικνύεται από την επιτυχημένη εφαρμογή της στα προβλήματα που παρουσιάζονται. Βασικό θέμα συζήτησης αποτελεί επίσης η περιγραφή του θεωρητικού υποβάθρου και της ανάπτυξης της μεθόδου κατά τις τελευταίες δεκαετίες, ξεκινώντας από τις βασικές αρχές του Ακέραιου Προγραμματισμού και καταλήγοντας στη σύγχρονη συναφή βιβλιογραφία. Τέλος, αναδεικνύονται υποσχόμενες προεκτάσεις, όπως η αξιοποίηση της μεθόδου για τη γραμμικοποίηση μη-γραμμικών προβλημάτων ή ως μηχανισμός επίλυσης στοχαστικών προβλημάτων, ως προοπτικές για μελλοντική έρευνα.
Optimisation under preferences for matchings and circulations: combinatorial and polyhedral aspects
(31-10-2023) Σάμαρης, Μιχαήλ; Samaris, Michail; Athens University of Economics and Business, Department of Management Science and Technology; Eirinakis, Pavlos; Thilikos, Dimitrios; Giannopoulou, Archontia; Magos, Dimitrios; Markakis, Evangelos; Papadopoulos, Charis; Mourtos, Ioannis
Σε αυτή τη διδακτορική διατριβή εξετάζονται διάφορα προβλήματα βελτιστοποίησης υπό προτιμήσεις που ορίζονται με όρους Θεωρίας Γραφημάτων. Μελετάμε τα προβλήματα αυτά από συνδυαστική, πολυεδρική και αλγοριθμική άποψη. Αυτό που αναφέρουμε ως προτιμήσεις αντιπροσωπεύει εκφρασμένες επιλογές ή πιθανές αποφάσεις για ένα άτομο σε μια διάταξη που απαντά ποια είναι καλύτερη από την άλλη. Πολλά από τα προβλήματα που μελετάμε έχουν χρησιμοποιηθεί για να αναπαραστήσουν πραγματικές καταστάσεις λήψης αποφάσεων για άτομα ή οργανισμούς. Πρώτον, το πρόβλημα του Ευσταθούς Ταιριάσματος (SM), το πρόβλημα του πολλά-προς-πολλά Ευσταθούς Ταιριάσματος (MM) και το πρόβλημα της Ευσταθούς Κατανομής (SA) παρουσιάζονται μαζί με μερικά σημαντικά συνδυαστικά και πολυεδρικά αποτελέσματα σχετικά με αυτά. Δίνεται μια ελαχιστική πολυεδρική περιγραφή για τα SM, MM και την μη περιορισμένη περίπτωση του SA μέσω ενός αφινικού μετασχηματισμού του πολυτόπου διάταξης της διάταξης των περιστροφών τους. Για την μη περιορισμένη περίπτωση του SA είναι η πρώτη φορά που δίνεται μια ελάχιστική περιγραφή. Για να δειχθεί αυτός ο μετασχηματισμός αποδεικνύουμε διάφορα συνδυαστικά αποτελέσματα για τα πρoβληματα αυτά. Στη συνέχεια, αυτή η διατριβή προτείνει έναν νέο τρόπο χαλάρωσης του κριτηριού της Ευστάθειας στο SM, ορίζοντας το Πρόβλημα ασταθούς ταιριάσματος, όπου κάθε ζεύγος έχει μία τιμή κέρδους εάν συμμετέχει στο ταίριασμα και μια τιμή κόστους εάν το μπλοκάρει. Η εύρεση ενός ταιριάσματος που μεγιστοποιεί τη συνάρτηση το κέρδος από τα ζευγάρια που συμμετέχουν σε αυτό μείον το κόστος από τα ζευγάρια που το μπλοκάρουν είναι NP-δύσκολο. Αν η τιμή κέρδους και η τιμή κόστους ταυτίζονται για κάθε ζευγάρι οι περιπτώσεις όπου είτε αυτή η συνάρτηση περιορίζεται στο (0, 1) είτε είναι αύξουσα ως προς τις προτιμήσεις επιλύονται σε πολυωνυμικό χρόνο. Αντίθετα, εάν η συνάρτηση περιορίζεται σε δύο γενικές τιμές (α, β), το πρόβλημα παραμένει NP-hard. Μια άλλη περίπτωση που αποδεικνύεται ότι το πρόβλημα αυτο είναι πολυωνυμικά επιλύσιμο είναι όταν το σύνολο των ζευγαριών διαμερίζεται σε αυτά που μπορούν να αποτελούν μέρος της αντιστοίχισης εξόδου αλλά δεν επιτρέπεται να το μπλοκάρουν (η τιμή κόστους τους είναι +∞) και σε εκείνα που μπορούν να μπλοκάρουν ενα ταίριασμα με κάποιο κόστος, αλλά δεν μπορεί να είναι μέρος του (η τιμή κέρδους τους είναι −∞). Αυτή η διατριβή εξετάζει επίσης μια νέα γενίκευση ενός-προς-πολλά του Παρέτο βέλτιστου ταιριάσματος όπου δεν υπάρχει ανώτατο όριο για το πόσοι συμμετέχοντες μπορούν να λάβουν ένα συγκεκριμένο αγαθό, αλλά υπάρχουν ζεύγη συμμετεχόντων που δεν μπορούν να λάβουν το ίδιο αγαθό. Από μια άλλη οπτική γωνία, αυτή η παραλλαγή του προβλήματος μπορεί να θεωρηθεί ως πρόβλημα χρωματισμού σε ένα γράφημα μεσα απο λίστα προτιμήσεων. Παρόλο που ο μηχανισμός της Σειριακής Δικτατορίας επιστρέφει ένα Παρέτο βέλτιστο χρωματισμό, μέσω αντιπαραδείγματος δείχνουμε οτι το αντίστροφο δεν ισχύει και ότι υπάρχουν Παρέτο βέλτιστοι χρωματισμοί που δεν μπορούν να ληφθούν από την Σειριακή Δικτατορία. Πλέον το πρόβλημα του να αποφασίσουμε εάν ενας δεδομένος χρωματισμός είναι Πάρετο βέλτιστος δεν είναι πλέον εύκολο, αλλά γίνεται coNP-δύσκολο. Σε ορισμένες ειδικές περιπτώσεις παραμένει πολυωνυμικά επιλύσιμο. Το τελευταίο πρόβλημα που μελετήθηκε σε αυτή τη διατριβή είναι ένα προβλημα ανταλλακτικών αγορών με αδιαίρετα αγαθά οπου οι συμμετέχοντες εκφράζουν προτιμήσεις και το κεντρικό κριτήριο που είναι ζητούμενο σε μια ανταλλαγή είναι η Παρέτο βελτιστότητα. Επιστρέφεται μια λύση από τον μηχανισμο Top Trading Cycle και παρέχεται επίσης ένας συνδυαστικός χαρακτηρισμός των Παρέτο βέλτιστων λύσεων. Αυτός ο χαρακτηρισμός οδηγεί άμεσα σε έναν εύκολο τρόπο αναγνώρισης εάν μια δεδομένη ανταλλαγή είναι Παρέτο βέλτιστη. Επιπλέον, αποδεικνύεται ότι εάν υπάρχει συνάρτηση βάρους για την εύρεση πιθανής ανταλλαγής, η ανταλλαγή μέγιστου βάρους είναι NP-δύσκολο. Εάν το βάρος είναι συνάρτηση αύξουσα ως προς τις προτιμήσεις τότε το πρόβλημα λύνεται σε πολυωνυμικό χρόνο.
Scheduling variants in manufacturing and process industries
(20-02-2025) Βατικιώτης, Σταύρος; Vatikiotis, Stavros; Athens University of Economics and Business, Department of Management Science and Technology; Androutsopoulos, Konstantinos; Zachariadis, Emmanouil; Eirinakis, Pavlos; Kaparis, Konstantinos; Kasapidis, Grigorios; Repoussis, Panagiotis; Mourtos, Ioannis
Η διατριβή εξετάζει τη σχεδίαση και εφαρμογή τεχνικών συνδυαστικής βελτιστοποίησης σε σύνθετα προβλήματα χρονοδρομολόγησης και βιομηχανίας επεξεργασίας. Τα παραδοσιακά μοντέλα βελτιστοποίησης συχνά δυσκολεύονται στην ενσωμάτωση πολλών παραμέτρων από τον πραγματικό κόσμο, γεγονός που απαιτεί ευέλικτες μεθόδους. Αυτές οι μέθοδοι, αν και δεν εγγυώνται τη βελτιστότητα, προσφέρουν αποδοτικές λύσεις σε σύνθετα προβλήματα. Οι υβριδικές προσεγγίσεις που προτείνονται συνδυάζουν ακριβείς τεχνικές, όπως ο Μικτός Ακέραιος Γραμμικός Προγραμματισμός (MILP) και ο Προγραμματισμός Περιορισμών (CP), με μεθευρετικούς αλγορίθμους, όπως οι Γενετικοί Αλγόριθμοι (GA), η Προσομοιώμενη Ανόπτηση (SA) και η Τοπική Αναζήτηση (LS). Αυτή η σύνθεση παρέχει τη δυνατότητα για καλύτερη διαχείριση της πολυπλοκότητας των βιομηχανικών προβλημάτων, δίνοντας έμφαση στην αποδοτικότητα και τη βιωσιμότητα των λύσεων.Αναλύεται το πρόβλημα Χρονοδρομολόγησης Ασυσχέτιστων Παράλληλων Μηχανών (UPMS) με εξαρτώμενους χρόνους προετοιμασίας και περιορισμένους ανανεώσιμους πόρους. Αντί για την ελαχιστοποίηση της μέγιστης συνολικής διάρκειας, η έμφαση δίνεται στη μείωση της συνολικής σταθμισμένης καθυστέρησης, παρέχοντας μια πιο πρακτική λύση για εφαρμογές στη βιομηχανία. Η προτεινόμενη προσέγγιση συνδυάζει MILP, GA, SA και CP για να βελτιστοποιήσει τα αποτελέσματα και να διαχειριστεί την πολυπλοκότητα του προβλήματος.Επιπλέον, εξετάζεται το Πρόβλημα Υβριδικής Ευέλικτης Χρονοδρομολόγησης (HFFS), όπου απαιτείται προγραμματισμός εργασιών σε στάδια με παράλληλες μηχανές και περιορισμούς. Οι πέντε αλγόριθμοι (GA, SA, PSO, LS, TS) συνδυάζονται με CP και αξιολογούνται για μεγάλα στιγμιότυπα, επιτυγχάνοντας βελτιώσεις στην αποδοτικότητα και την ποιότητα των λύσεων.Τέλος, η διατριβή προτείνει τη χρήση ενός Μικτού-Ακεραίου Μη Γραμμικού Προγράμματος (MINLP) για τη διαχείριση υπολειμμάτων και υδάτινων πόρων, προσφέροντας μια καινοτόμο προσέγγιση για την αντιμετώπιση αυτών των προκλήσεων. Τα πειραματικά αποτελέσματα αποδεικνύουν την αποδοτικότητα της μεθόδου και τη δυνατότητα εφαρμογής της σε διάφορες βιομηχανίες, προσφέροντας αξιόπιστες λύσεις για την επίλυση πρακτικών προβλημάτων στον τομέα της παραγωγής και της βιομηχανίας.