| Summary: | Η παρούσα εργασία έχει σαν στόχο την ανάλυση ενός προβλήματος
δρομολόγησης το οποίο στη βάση του έχει ως εξής: Δίνεται ακολουθία
διεργασιών που πρόκειται να δοθεί για επεξεργασία σε ένα σύνολο
μηχανών. Η κάθε διεργασία χαρακτηρίζεται από το χρόνο επεξεργασίας
της και θα πρέπει να δρομολογηθεί σε κάποια απ' τις μηχανές για
χρόνο τουλάχιστον ίσο με αυτό. Επιπλέον υπάρχει απαίτηση από ένα
υποσύνολο διεργασιών για επιτάχυνση. Το ζητούμενο είναι να δοθεί
αλγόριθμος που δρομολογεί τις διεργασίες στις μηχανές
ελαχιστοποιώντας κάποια μετρική απόδοσης, παράλληλα με την
εξυπηρέτηση όσο το δυνατόν περισσότερων αιτήσεων για επιτάχυνση.
Στα πλαίσια ενός εισαγωγικού κεφαλαίου δίνεται θεωρητικό υπόβαθρο
που αφορά σε προβλήματα και αλγορίθμους δρομολόγησης, σημειώνοντας
ιδιαίτερα τη διαφορά μεταξύ στατικών και δυναμικών αλγορίθμων.
Αντικείμενο της εργασίας αυτής γίνεται στη συνέχεια η μελέτη του
παραπάνω προβλήματος, σε περιβάλλον μιας μηχανής και σε παραλλαγές
του οι οποίες σχετίζονται με παραμέτρους, όπως για παράδειγμα,
προθεσμίες ολοκλήρωσης. Αποτέλεσμα της μελέτης αυτής είναι η
ανάπτυξη, αλλά και η αξιολόγηση αποτελεσματικών μεθόδων επίλυσης,
χρησιμοποιώντας γνωστά κριτήρια βελτιστοποίησης όπως ο χρόνος που
απαιτείται για την ολοκλήρωση των διεργασιών, αλλά και κάποιες νέες
μετρικές που συστήνονται και η ανάγκη τους επεξηγείται αναλυτικά.
Τέλος στο τρίτο κεφάλαιο γίνεται επισκόπηση προβλημάτων που αφορούν
δρομολόγηση σε περισσότερες από μία μηχανές. Τα προβλήματα αυτά ενώ
αποδεικνύονται ΝΡ-πλήρη, οι αποδείξεις παραλείπονται και δίδονται
παρατηρήσεις για την πολυπλοκότητα παραλλαγών τους. Η εργασία
κλείνει με μια παρουσίαση της υπολογιστικής μεθόδου του δυναμικού
προγραμματισμού, που γίνεται προσπάθεια να εφαρμοστεί σε προβλήματα
δρομολόγησης.
|
|---|
