| Περίληψη |
Η κατανομή των διαθέσιμων πόρων (πρώτες ύλες, μηχανές κ.α) μίας βιομηχανικής επιχείρησης, με στόχο την ελαχιστοποίηση του κόστους παραγωγής των αγαθών, λέγεται Προγραμματισμός Παραγωγής. Κάθε πρόβλημα βέλτιστης διάταξης εργασιών σε μία ή περισσότερες μηχανές, που εμφανίζεται στον Προγραμματισμό Παραγωγής, ονομάζεται πρόβλημα Χρονικού Προγραμματισμού. Η παρούσα εργασία ασχολείται με την επίλυση ενός τέτοιου προβλήματος. Συγκεκριμένα, του προβλήματος εκείνου που, δοθέντων Ν εργασιών, που πρέπει να εκτελεστούν σε μία μηχανή, χωρισμένων σε Β ομάδες, έτσι ώστε μεταξύ των εκτελέσεων δύο εργασιών που ανήκουν σε διαφορετικές ομάδες να μεσολαβεί ένα χρονικό διάστημα που η μηχανή μένει ανενεργή (χρόνος εξάρμωσης), ζητείται η ελαχιστοποίηση δύο κριτηρίων απόδοσης : του αθροίσματος των χρόνων αποπεράτωσης των εργασιών και της μέγιστης καθυστέρησης. Τα πλουκριτηριακά προβλήματα Χρονικού Προγραμματισμού αποτελούν ρεαλιστικότερη απεικόνιση της πραγματικότητας από τα προβλήματα ενός κριτηρίου, γιατί στην πράξη ζητούνται συνήθως προγράμματα (διατάξεις εργασιών) με μία γενικά καλή συμεριφορά, ως προς διάφορα κριτήρια. Η γενικότερη λύση ενός πολυκριτηριακού προβλήματος είναι ο υπολογισμός του συνόλου των αποδοτικών λύσεων, δηλαδή εκείνων για τις οποίες δεν υπάρχει κάποια άλλη με καλύτερη τιμή σε ένα κριτήριο και όχι χειρότερη στα υπόλοιπα. Αυτό είναι το ζητούμενο και στο πρόβλημα που πραγματεύεται η παρούσα εργασία. Η εύρεση μιας αποδοτικής λύσης ανάγεται στην επίλυση του προβλήματος ελαχιστοποίησης του αθροίσματος των χρόνων αποπεράτωσης δοθέντος ότι, ως προς κατάλληλα μετατοπισμένες δεξιότερα στον άξονα του χρόνου (από τις αρχικές του τιμές) προθεσμίες, δε θα καθυστερήσει καία εργασία. Αντίθετα από άλλα προβλήματα Χρονικού Προγραμματισμού με χρόνους εξάρμωσης, το τελευταίο πρόβλημα δεν είναι διατεταγμένων ομάδων, δηλαδή δεν είναι γνωστή η διάταξη των εργασιών σε κάθε ομάδα από την αρχή, με αποτελέσμα η πλοκή του να μην είναι εκθετική ως προς τον αριθμό των ομάδων, Β, αλλά ως προς τον αριθμό των εργασιών, Ν. Αφού παρουσιάσουμε αναλυτικά τα όσα είπαμε παραπάνω, στη συνέχεια της εργασίας παρουσιάζουμε μεθόδους επίλυσης προβλημάτων Χρονικού Προγραμματισμού που έχουν χρησιμοποιηθεί σε άλλες εργασίες (κυρίως μεθόδους υπολογισμού κάτω φράγματος για ένα κοινό σχήμα διαμερισμού και φραγής) και εξηγούμε γιατί καθεμιά από τις μεθόδους αυτές δεν μπορεί να εφαρμοστεί στο πρόβλημά μας. Οι βαθύτεροι λόγοι γι αυτό είναι πάντα η ύπαρξη των χρόνων εξάρμωσης και το γεγονός ότι το πρόβλημα δεν είναι διατεταγμένων ομάδων. Στη συνέχεια επιχειρούμε μία συγκριτική παρουσίαση των κλασσικότερων αλγορίθμων Δυναμικού Προγραμματισμού, και αναλύουμε τα προτερήματα και τα μειονεκτήματα τους έναντι του γενικού αλγορίθμου διαμερισμού και φραγής που συνήθως χρησιμοποιείται. Αμέσως μετά αναλύουμε τους λόγους που μας ώθησαν στην επιλογή του Δυναμικού Προγραμματισμού για την επίλυση του προβλήματός μας και παρουσιάζουμε τους δύο αλγορίθμους Δυναμικού Προγραμματισμού που υλοποιήσαμε. Έπειτα παρουσιάζουμε τα αποτελέσματα που πήραμε από την εκτέλεση εκτεταμένων πειραμάτων και εξηγούμε την παρατηρούμενη επίδραση του πλήθους των εργασιών, Ν, του πλήθους των ομάδων, Β, της θέσης που κατέχει κάποια αποδοτική λύση ανάμεσα στις υπόλοιπες και διάφορων παραμέτρων του προβλήματος, στον απαιτούμενο χρόνο επίλυσής του. Το μέγεθος των προβλημάτων κάθε αποδοτική λύση των οποίων υπολογίζεται σε χρόνο ενός λεπτού (μέχρι λίγο περισσότερες από 20 εργασίες) είναι μικρότερο του μεγέθους των προβλημάτων που σε άλλες εργασίες, που ασχολούνται με προβλήματα Χρονικού Προγραμματισμού χωρίς χρόνους εξάρμωσης, λύνονται στον ίδιο χρόνο (συνήθως γύρω στις 30 εργασίες, χωρίς να λείπουν και λίγες περιπτώσεις που φτάνουν στις 50), αλλά κρίνεται ικανοποιητικό αν συγκριθεί με τις επιδόσεις αλγορίθμου, που παρουσιάζεται σε πρόσφατα δημοσιευμένη εργασία, για την επίλυση τπυ προβλήματος που προκύπτει εάν από το δικό μας αφιαρέσουμε το κριτήριο της μέγιστης καθυστέρησης και που η λύση του αποτελεί μία από τις αποδοτικές λύσεις του δικού μας προβλήματος. Τελειώνοτας, παρουσιάζουμε μία γενική ιδέα που μπορεί να ακολουθεί ένας ευρηματικός αλγόριθμος, ο οποίος πολύ ταχύτερα από τον ακριβή θα λύνει προσεγγιστικά το δικριτηριακό μας πρόβλημα. Παρουσιάζουμε, επίσης, μία γενίκευση του αλγορίθμου Δυναμικού Προγραμματισμού που χρησιμοποιήσαμε για τον υπολογισμό μιας αποδοτικής λύσης, που λύνει απευθείας, με μεγαλύτερη όμως υπολογιστική πλοκή, το αρχικό δικριτηριακό πρόβλημα.
|
Δικριτηριακός Προγραμματισμός Μιας Μηχανής με Χρόνους Εξάρμωσης
