Η παρούσα εργασία έχει σαν στόχο την ανάλυση ενός προβλήματος
δρομολόγησης το οποίο στη βάση του έχει ως εξής: Δίνεται ακολουθία
διεργασιών που πρόκειται να δοθεί για επεξεργασία σε ένα σύνολο
μηχανών. Η κάθε διεργασία χαρακτηρίζεται από το χρόνο επεξεργασίας
της και θα πρέπει να δρομολογηθεί σε κάποια απ' τις μηχανές για
χρόνο τουλάχιστον ίσο με αυτό. Επιπλέον υπάρχει απαίτηση από ένα
υποσύνολο διεργασιών για επιτάχυνση. Το ζητούμενο είναι να δοθεί
αλγόριθμος που δρομολογεί τις διεργασίες στις μηχανές
ελαχιστοποιώντας κάποια μετρική απόδοσης, παράλληλα με την
εξυπηρέτηση όσο το δυνατόν περισσότερων αιτήσεων για επιτάχυνση.
Στα πλαίσια ενός εισαγωγικού κεφαλαίου δίνεται θεωρητικό υπόβαθρο
που αφορά σε προβλήματα και αλγορίθμους δρομολόγησης, σημειώνοντας
ιδιαίτερα τη διαφορά μεταξύ στατικών και δυναμικών αλγορίθμων.
Αντικείμενο της εργασίας αυτής γίνεται στη συνέχεια η μελέτη του
παραπάνω προβλήματος, σε περιβάλλον μιας μηχανής και σε παραλλαγές
του οι οποίες σχετίζονται με παραμέτρους, όπως για παράδειγμα,
προθεσμίες ολοκλήρωσης. Αποτέλεσμα της μελέτης αυτής είναι η
ανάπτυξη, αλλά και η αξιολόγηση αποτελεσματικών μεθόδων επίλυσης,
χρησιμοποιώντας γνωστά κριτήρια βελτιστοποίησης όπως ο χρόνος που
απαιτείται για την ολοκλήρωση των διεργασιών, αλλά και κάποιες νέες
μετρικές που συστήνονται και η ανάγκη τους επεξηγείται αναλυτικά.
Τέλος στο τρίτο κεφάλαιο γίνεται επισκόπηση προβλημάτων που αφορούν
δρομολόγηση σε περισσότερες από μία μηχανές. Τα προβλήματα αυτά ενώ
αποδεικνύονται ΝΡ-πλήρη, οι αποδείξεις παραλείπονται και δίδονται
παρατηρήσεις για την πολυπλοκότητα παραλλαγών τους. Η εργασία
κλείνει με μια παρουσίαση της υπολογιστικής μεθόδου του δυναμικού
προγραμματισμού, που γίνεται προσπάθεια να εφαρμοστεί σε προβλήματα
δρομολόγησης. / The purpose of the present study is to analyze a scheduling problem, the def-
inition of which is: We are given a sequence of tasks that are to be processed
on a set of machines. Each task is characterized by its running time and
has to be scheduled on a machine, for at least its running time. In addition,
there are speedup requests from a subset of tasks. The scheduling algorithm
is asked to produce a schedule that minimizes an objective function in par-
allel with serving as many as possible speedup requests.
The introduction gives a theoretical background concerning scheduling prob-
lems and algorithms, with an emphasis on the di_erence between static and
dynamic algorithms. The objective of the second chapter, is to study the
problem above, in its many variations, with a reference to parameters like
the number of the machines, deadlines etc. The result of this study, is the
development and the evaluation of two algorithms, using objective functions
like makespan, and also some new ones that arise in the essay and their need
is analyzed. The thesis closes with a consideration of already known schedul-
ing problems and its variants, that have been proved to be NP-complete.
| Identifer | oai:union.ndltd.org:upatras.gr/oai:nemertes:10889/983 |
| Date | 10 October 2008 |
| Creators | Στούμπου, Αμαλία |
| Contributors | Κοσμαδάκης, Σταύρος, Stoumpou, Amalia, Γαλλόπουλος, Ευστράτιος, Ζαρολιάγκης, Χρήστος, Κοσμαδάκης, Σταύρος |
| Source Sets | University of Patras |
| Language | gr |
| Detected Language | Greek |
| Type | Thesis |
| Rights | 0 |
| Relation | Η ΒΥΠ διαθέτει αντίτυπο της διατριβής σε έντυπη μορφή στο βιβλιοστάσιο διδακτορικών διατριβών που βρίσκεται στο ισόγειο του κτιρίου της. |
Page generated in 0.0023 seconds