Προβλήματα επιτάχυνσης διεργασιών : αλγόριθμοι και πολυπλοκότητα
Η διπλωµατική εργασία αποτελεί συνέχεια της µελέτης προβληµάτων χρονοπρογραµµατισµού µε αυστηρές προθεσµίες που ξεκίνησε η Αµαλία Στούµπου στην δικιά της διπλωµατική εργασία µε όνοµα "Προβλήµατα Επιτάχυνσης ∆ιεργασιών σε Grid Computing: Αλγόριθµοι και Πολυπλοκότητα". Εξετάζονται προβλήµατα...
| Κύριος συγγραφέας: | |
|---|---|
| Άλλοι συγγραφείς: | |
| Μορφή: | Thesis |
| Γλώσσα: | Greek |
| Έκδοση: |
2015
|
| Θέματα: | |
| Διαθέσιμο Online: | http://hdl.handle.net/10889/8330 |
| id |
nemertes-10889-8330 |
|---|---|
| record_format |
dspace |
| spelling |
nemertes-10889-83302022-09-05T14:08:03Z Προβλήματα επιτάχυνσης διεργασιών : αλγόριθμοι και πολυπλοκότητα Φίλος Ράτσικας, Αλέξης Κοσμαδάκης, Σταύρος Κοσμαδάκης, Σταύρος Γαλλόπουλος, Ευστράτιος Ζαρολιάγκης, Χρήστος Filos Ratsikas, Alexis Χρονοπρογραμματισμός Προθεσμίες Ψευδοπολυωνυμικός Δυναμικός προγραμματισμός Scheduling Deadlines Pseudopolynomial Dynamic programming 005.434 Η διπλωµατική εργασία αποτελεί συνέχεια της µελέτης προβληµάτων χρονοπρογραµµατισµού µε αυστηρές προθεσµίες που ξεκίνησε η Αµαλία Στούµπου στην δικιά της διπλωµατική εργασία µε όνοµα "Προβλήµατα Επιτάχυνσης ∆ιεργασιών σε Grid Computing: Αλγόριθµοι και Πολυπλοκότητα". Εξετάζονται προβλήµατα δροµολόγησης διεργασιών σε περισσότερους από έναν, ίδιους µεταξύ τους, επεξεργαστές. ∆ίνονται αλγόριθµοι που λύνουν το πρόβληµα ελαχιστοποίησης του συνολικού χρόνου εκτέλεσης, µε αυστηρές προθεσµίες, αρχικά για 2 και στη συνέχεια για m επεξεργαστές. Οι αλγόριθµοι αυτοί έχουν ψευδοπολυωνυµική πολυπλοκότητα. Στη συνέχεια εξετάζονται προβλήµατα δροµολόγησης και επιτάχυνσης διεργασιών µε ίδιο χρόνο εκτέλεσης, σε περιβάλλοντα µε ίδιους µεταξύ τους επεξεργαστές και δίνονται πολυωνυµικοί αλγόριθµοι που τα λύνουν. Τέλος αναφέρονται συνοπτικά ορισµένα προβλήµατα του ευρύτερου χώρου προϐληµάτων χρονοπρογραµµατισµού που µπορούν να προσεγγιστούν ή να λυθούν µε τεχνικές που εφαρµόστηκαν για τη λύση των προηγούµενων προβληµάτων που αναφέρθηκαν. This thesis is a continuation of the study of scheduling problems with strict deadlines that begun in the thesis "Προβλήµατα Επιτάχυνσης ∆ιεργασιών σε Grid Computing : Αλγόριθµοι και Πολυπλοκότητα" by Amalia Stoumpou. We study scheduling problems on more than one parallel processors. Algorithms are given that solve the problem of minimizing the makespan with strict deadlines, first for 2 and then for m processors. These algorithms are pseudopolynomial in complexity. We also study problems of scheduling and speedup of processes with the same execution time in parallel processor environments and we give pseudopolynomial algorithms that solve them. Finally, we mention briefly other problems that can be solved or approached using the techniques that we applied to solve the previous problems. 2015-02-05T16:18:39Z 2015-02-05T16:18:39Z 2014-07-14 2015-02-05 Thesis http://hdl.handle.net/10889/8330 gr 0 application/pdf |
| institution |
UPatras |
| collection |
Nemertes |
| language |
Greek |
| topic |
Χρονοπρογραμματισμός Προθεσμίες Ψευδοπολυωνυμικός Δυναμικός προγραμματισμός Scheduling Deadlines Pseudopolynomial Dynamic programming 005.434 |
| spellingShingle |
Χρονοπρογραμματισμός Προθεσμίες Ψευδοπολυωνυμικός Δυναμικός προγραμματισμός Scheduling Deadlines Pseudopolynomial Dynamic programming 005.434 Φίλος Ράτσικας, Αλέξης Προβλήματα επιτάχυνσης διεργασιών : αλγόριθμοι και πολυπλοκότητα |
| description |
Η διπλωµατική εργασία αποτελεί συνέχεια της µελέτης προβληµάτων χρονοπρογραµµατισµού µε αυστηρές προθεσµίες που ξεκίνησε η Αµαλία Στούµπου στην δικιά της διπλωµατική εργασία µε όνοµα "Προβλήµατα Επιτάχυνσης ∆ιεργασιών σε Grid Computing: Αλγόριθµοι και Πολυπλοκότητα". Εξετάζονται προβλήµατα δροµολόγησης διεργασιών σε περισσότερους από έναν, ίδιους µεταξύ τους, επεξεργαστές. ∆ίνονται αλγόριθµοι που λύνουν το πρόβληµα ελαχιστοποίησης του συνολικού χρόνου εκτέλεσης, µε αυστηρές προθεσµίες, αρχικά για 2 και στη συνέχεια για m επεξεργαστές. Οι αλγόριθµοι αυτοί έχουν ψευδοπολυωνυµική πολυπλοκότητα. Στη συνέχεια εξετάζονται προβλήµατα δροµολόγησης και επιτάχυνσης διεργασιών µε ίδιο χρόνο εκτέλεσης, σε περιβάλλοντα µε ίδιους µεταξύ τους επεξεργαστές και δίνονται πολυωνυµικοί αλγόριθµοι που τα λύνουν. Τέλος αναφέρονται συνοπτικά ορισµένα προβλήµατα του ευρύτερου χώρου προϐληµάτων χρονοπρογραµµατισµού που µπορούν να προσεγγιστούν ή να λυθούν µε τεχνικές που εφαρµόστηκαν για τη λύση των προηγούµενων προβληµάτων που αναφέρθηκαν. |
| author2 |
Κοσμαδάκης, Σταύρος |
| author_facet |
Κοσμαδάκης, Σταύρος Φίλος Ράτσικας, Αλέξης |
| format |
Thesis |
| author |
Φίλος Ράτσικας, Αλέξης |
| author_sort |
Φίλος Ράτσικας, Αλέξης |
| title |
Προβλήματα επιτάχυνσης διεργασιών : αλγόριθμοι και πολυπλοκότητα |
| title_short |
Προβλήματα επιτάχυνσης διεργασιών : αλγόριθμοι και πολυπλοκότητα |
| title_full |
Προβλήματα επιτάχυνσης διεργασιών : αλγόριθμοι και πολυπλοκότητα |
| title_fullStr |
Προβλήματα επιτάχυνσης διεργασιών : αλγόριθμοι και πολυπλοκότητα |
| title_full_unstemmed |
Προβλήματα επιτάχυνσης διεργασιών : αλγόριθμοι και πολυπλοκότητα |
| title_sort |
προβλήματα επιτάχυνσης διεργασιών : αλγόριθμοι και πολυπλοκότητα |
| publishDate |
2015 |
| url |
http://hdl.handle.net/10889/8330 |
| work_keys_str_mv |
AT philosratsikasalexēs problēmataepitachynsēsdiergasiōnalgorithmoikaipolyplokotēta |
| _version_ |
1771297220447961088 |
