Το πρόβλημα χρονοπρογραμματισμού κατανεμημένων ροών εργασιών βάσει μεταθέσεων με περιορισμούς ημερομηνιών τερματισμού εργασιών
Φόρτωση...
Ημερομηνία
Συγγραφείς
Κιοσσές, Δημήτριος
Kiosses, Dimitrios
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Πανεπιστήμιο Ιωαννίνων. Σχολή Πληροφορικής και Τηλεπικοινωνιών. Τμήμα Πληροφορικής και Τηλεπικοινωνιών
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
Ο χρονοπρογραμματισμός (scheduling, timetabling) είναι ένα ερευνητικό πεδίο με πολλές πρακτικές εφαρμογές στη βιομηχανία, στις μεταφορές, στον κατασκευαστικό κλάδο, στο λογισμικό των ηλεκτρονικών υπολογιστών και αλλού. Η δε σημασία της αποδοτικής επίλυσης προβλημάτων χρονοπρογραμματισμού έχει οδηγήσει στην ανάπτυξη πολλών τεχνικών αντιμετώπισης των σχετικών προβλημάτων.
Στην παρούσα διπλωματική θα εξεταστεί το γνωστό πρόβλημα χρονοπρογραμματισμού κατανεμημένων ροών εργασιών βάσει μεταθέσεων με περιορισμούς ημερομηνιών τερματισμού εργασιών (Distributed Permutation Flow-shop Scheduling Problem with Due Dates) και θα επιδιωχθεί η παραγωγή ανταγωνιστικών αποτελεσμάτων με τα State of the Art αποτελέσματα που εντοπίζονται στη βιβλιογραφία.
Η εργασία θα αναλύσει το πρόβλημα, θα μελετήσει τη βιβλιογραφία και θα εξετάσει διάφορες προσεγγίσεις επίλυσης του προβλήματος. Θα αναπτυχθεί κώδικας ικανός να πράξει ολοκληρωμένες λύσεις και θα χρησιμοποιηθούν οι απαραίτητες βιβλιοθήκες έτσι ώστε να επιτευχθούν λύσεις υψηλής ποιότητας για δημόσια διαθέσιμα προβλήματα.
Scheduling (timetabling) is a research field with many practical applications in industry, transport, construction and computer software. The importance of efficiently solving scheduling problems has led to the development of many techniques for dealing with the related problems. In this thesis, the well-known Distributed Permutation Flow-shop Scheduling Problem with Due Dates will be considered and will aim to produce competitive results with the State of the Art results found in the literature. The paper will analyze the problem, study the literature and examine various approaches to solving the problem. Code capable of generating complete solutions will be developed to achieve high quality solutions for publicly available problems.
Scheduling (timetabling) is a research field with many practical applications in industry, transport, construction and computer software. The importance of efficiently solving scheduling problems has led to the development of many techniques for dealing with the related problems. In this thesis, the well-known Distributed Permutation Flow-shop Scheduling Problem with Due Dates will be considered and will aim to produce competitive results with the State of the Art results found in the literature. The paper will analyze the problem, study the literature and examine various approaches to solving the problem. Code capable of generating complete solutions will be developed to achieve high quality solutions for publicly available problems.
Περιγραφή
Λέξεις-κλειδιά
Χρονοπρογραμματισμός, Κατανεμημένος προγραμματισμός, Προγραμματισμός ροής παραγωγής, Προθεσμίες εκτέλεσης, Μεταευρετικοί αλγόριθμοι, Προγραμματισμός παραγωγής, Scheduling (timetabling), Distributed scheduling, Flow-shop scheduling, Due dates, Production planning, Metaheuristic algorithms
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
Γλώσσα
el
Εκδίδον τμήμα/τομέας
Πανεπιστήμιο Ιωαννίνων. Σχολή Πληροφορικής και Τηλεπικοινωνιών. Τμήμα Πληροφορικής και Τηλεπικοινωνιών
Όνομα επιβλέποντος
Gogos, Christos
Εξεταστική επιτροπή
Τζάλλας, Αλέξανδρος
Καρβέλης, Πέτρος
Καρβέλης, Πέτρος
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Πληροφορικής και Τηλεπικοινωνιών
Πίνακας περιεχομένων
Περιεχόμενα
1. Εισαγωγή 9
2. Ιστορική Αναφορά 10
3. Περιγραφή του Προβλήματος 12
3.1 Κατηγορίες Χρονοπρογραμματισμού 12
3.1.1 Job Shop Problem 12
3.1.2 Flow Shop Problem 13
3.2 PFSP 14
3.3 DPFSP 15
4. Περιγραφή του Μοντέλου 18
4.1 Συμβολισμοί και περιορισμοί 18
4.1.1 Δείκτες 18
4.1.2 Παράμετροι 18
4.1.3 Μεταβλητή απόφασης 18
4.2 MILP 20
4.3 Αριθμητική απεικόνιση 21
5. Τρόποι Αντιμετώπισης Προβλήματος 23
5.1 Ευρετικές Μέθοδοι 23
5.1.1 Ο Αλγόριθμος NEH 23
5.1.1.1 Βελτιωμένος Αλγόριθμος NEH_F 27
5.1.3 Ο Αλγόριθμος TABOO Search 32
5.1.2 Ο Αλγόριθμος NEHedd 34
6. Ανάπτυξη και Υλοποίηση 36
6.1 Iterated Local Search (ILS) 37
6.2 Hybrid Local Search Greedy Algorithm (HYLG) 39
6.2.1 Random Subsequence Local Search 41
6.2.2 Random Single Point Local Search 43
6.2.2.1 Simulated Annealing (SA) 44
6.2.2.2 Κριτήριο Αποδοχής 44
6.3 MLL Based Mechanism 46
6.4 Hybrid Genetic Algorithm 48
6.4.1 Genetic Algorithm 48
6.4.2 Hybrid Genetic Algorithm For The DPFSP 49
6.4.2.1 Variable Neighborhood Descent (VND) 49
6.4.2.2 GA_LS 50
6.4.4.3 Αναπαράσταση Λύσης Και Αρχικοποιήσεις 51
6.4.4.3 Βιβλιοθήκη PYGAD 56
6.4.4 Λογισμικό επίλυσης προβλημάτων συνδυαστικής βελτιστοποίησης Google OR TOOLS 58
6.6 Σχεδιασμός Πειραμάτων 61
6.6.1 Δεδομένα 61
6.6.2 Εφαρμογή Αλγόριθμων 62
7 Αξιολόγηση και Ανάλυση Αποτελεσμάτων 64
7.1 Παρουσίαση Αποτελεσμάτων 64
7.2 Ανάλυση Αποτελεσμάτων 65
8 Συμπεράσματα και Μελλοντικές Προκλήσεις 73
9 Εκτέλεση Αλγόριθμων 74
9.1 Αρχεία και Φάκελοι του Κώδικα 74
9.2 Εκτέλεση του Κώδικα 75
9.3 Χαρακτηριστικά Συστήματος 75
9.4 Git Repository 75
Βιβλιογραφία 76
Εικόνες 79
Πίνακες 79
Κώδικες 80
Χορηγός
Βιβλιογραφική αναφορά
Ονόματα συντελεστών
Αριθμός σελίδων
89
Λεπτομέρειες μαθήματος
item.page.endorsement
item.page.review
item.page.supplemented
item.page.referenced
Άδεια Creative Commons
Άδεια χρήσης της εγγραφής: Attribution-NonCommercial-NoDerivs 3.0 United States