| Περίληψη |
Στην παρούσα εργασία μελετούμε το πρόβλημα της ελαχιστοποίησης του συνολικού χρόνου περάτωσης n εργασιών σε μια μηχανή παρουσία χρόνων εξάρμωσης. Όλες οι εργασίες έχουν καλά καθορισμένους χρόνους επεξεργασίας, όχι κατ'ανάγκη ταυτοτικούς, είναι διαθέσιμες τη χρονική στιγμή μηδέν και κατανέμονται σε B διαφορετικές ομάδες. Για την προσαρμογή της μηχανής προκειμένου να υποδειχθεί εργασία διαφορετικής ομάδας από την τρέχουσα, απαιτείται χρόνος, ο οποίος χαρακτηρίζεται ως χρόνος εξάρμωσης. Στη μελέτη μας ασχολούμαστε κυρίως με την περίπτωση χρόνων εξάρμωσης ανεξαρτήτων ακολουθίας. Η εκτέλεση μιας εργασίας δε διακόπτεται ποτέ, ενώ δεν επιβάλλεται η διαδοχική εκτέλεση όλων των εργασιών που ανήκουν σε μια ομάδα. Το πρόβλημα του συνολικού χρόνου περάτωσης n εργασιών σε μια μηχανή, εμφανίζεται συχνά στο λεπτομερειακό προγραμματισμό παραγωγής. Οι αλγόριθμοι επίλυσης του προβλήματος που αναπτύσσονται στην παρούσα εργασία έχουν ενταχθεί σ'ένα διαλογικό σύστημα προγραμματισμού παραγωγής, στα πλαίσια του οποίου οι βέλτιστες ή σχεδόν βέλτιστες λύσεις που παράγουν ελέγχονται από το χρήσητ του συστήματος που αποφασίζει αν θα αποτελέσουν αυτές ή κάποιες τροποποιήσεις τους το τελικό πρόγραμμα παραγωγής. Για την επίλυση του πποβλήματος λαμβάνουμε υπο΄ψη την κατανομή εργασιών σε ομάδες και κατασκευάζουμε υποσύνολα αυτών, τα οποία εκτελούνται διαδοχικά σε κάποια βέλτιστη διάταξη. Τέτοια υποσύνολα τα ονομάζουμεπαρτίδες και τα διακρίνουμε σε πρωτογενείς (ΠΠ), δευτερογενείς (ΔΠ) και γενικευμένες (ΓΠ). Εξάγουμε προτάσεις σχετικές με τις παραπάνω οντότητες και χαρακτηριστικά των βέλτιστων λύσεων. Το πρόβλημα που μελετούμε είναι πολύ απλό όταν δεν έχουμε χρόνους εξάρμωσης ή είναι γνωστές οι μέγιστες ΓΠ που εμφανίζονται σε βέλτιστη λύση (λύνεται σε χρόνο Ο(nlogn)). Όταν έχουμε χρόνους εξάρμωσης το πρόβλημα δυσκολεύει αρκετά, αλλά η πλοκή του δεν έχει ακόμα προδιοριστεί. Η δική μας συνεισφορά στην επίλυση του προβλήματος συνίσταται στην κατασκευή τριών αλγορίθμων: ενός ακριβούς και δύο προσεγγιστικών. Ο ακριβής είναι αλγόριθμος δυναμικού προγραμματισμού που ακολουθεί κατά βάση τα σχήματα των Ψαραύτη και Monma και Potts. Περιορίζεται αρκετά από τις απαιτήσεις μνήμης κυρίως και χρόνου δευτερευόντως όταν ο αριθμός των ομάδων είναι μεγάλος. Η χρήση των προτάσεων που σχετίζονται με παρτίδες κατά την κατασκευή των καταστάσεων του προβλήματος ελαττώνει σημαντικά τις απαιτήσεις σε μνήμη, με αποτέλεσμα να είναι δυνατή η επίλυση προβλημάτων με μερικές εκαντοντάδες (200-300) εργασίες, κατανεμημένες σε μερικές δεκάδες (10-30) ομάδων. Για την επίλυση προβλμάτων μεγαλύτερου μεγέθους κατασκευάσαμε δύο προσεγγιστικούς αλγορίθμους. Ο πρώτος ξεκινώντας από μια αρχική λύση που έχει αρκετές από τις ιδιόττηες μιας κατηγορίας βελτίστων, συνενώνει ΔΠ σε ΓΠ αν κάτι τέτοιο βελτιώνει την αρχική λύση, φροντίζοντας παράλληλα να διατηρεί σε ισχύ ένα κανόνα σχετικό με τη βέλτιστη διάταξη μεγίστων ΓΠ. Ο αλγόριθμος αυτός είναι πολυωνυμικός και διαπιστώθηκε πειραματικά ότι δίνει λύσεις με χείριστη απόκλιση από το βέλτιστο μικρότερη του 2.4%. Πολλά από τα προβλήματα του πειραματικού δείγματος (~73%) λύθηκαν βέλτιστα, ενώ η μέση απόκλιση των υπολοίπων από το βέλτιστο είναι 0.18%. Την κατασκευή του δεύτερου προσεγγιστικού αλγορίθμου ενέπνευσε η μελέτη και υλοποίηση ενός αλγορίθμου των Ahn και Hyun για το ίδιο πρόβλημα, παράλληλα με την πειραματική μελέτη της συμπεριφοράς του πρώτου προσεγγιστικού αλγορίθμου. Ο καινούργιος αυτός αλγόριθμος είναι στην ουσία μια παράθεση i) του πρώτου προσεγγιστικού αλγορίθμου, ii) μιας διαδικασίας ανάλυσης των γενικευμένων παρτίδων που προκύπτουν από το (i) στις ΠΠ που τις απαρτίζουν, και (iii) του βήματος θέσει-μεταθέσεων που περιέχεται στον αλγόριθμο των Ahn και Hyun. Ο αλγόριθμος αυτός, δίνει βέλτιστη λύση στο σύνολο του δείγματος των προβλημάτων που κατασκευάστηκαν για την πειραματική μελέτη των προσεγγιστικών αλγορίθμων.
|
Το Πρόβλημα του Συνολικού Χρόνου Περάτωσης Ν Εργασιών σε μια Μηχανή με Χρόνους Εξάρμωσης
