Your browser does not support JavaScript!

Αρχική    Αλγόριθμοι Παρεμβολής για το Πρόβλημα Ροϊκής Παραγωγής  

Αποτελέσματα - Λεπτομέρειες

Προσθήκη στο καλάθι
[Προσθήκη στο καλάθι]
Κωδικός Πόρου uch.csd.msc//1993kopidakis
Τίτλος Αλγόριθμοι Παρεμβολής για το Πρόβλημα Ροϊκής Παραγωγής
Άλλος τίτλος Interpolation Algorithms for the Flowshop Scheduling Problem
Συγγραφέας Κοπιδάκης, Ιωάννης
Περίληψη Στην εργασία αυτή μελετούμε τον αιτιοκρατικό προγραμματισμό Ν εργασιών σε γραμμή ροϊκής παραγωγής Μ μηχανών με χρόνους εξάρμωσης ανεξάρτητους ακολουθίας. Κάθε εργασία αναλύεται σε Μ επιμέρους κατεργασίες και κάθε κατεργασία εκτελείται σε διαφορετική μηχανή. Η σειρά εκτέλεσης των κατεργασιών είναι ίδια για όλες τις εργασίες. Οι Ν εργασίες κατανέμονται σε Β ομάδες και μεταξύ δύο διαδοχικών ομοειδών εργασιών δεν απαιτείται εξάρμωση της μηχανής. Αντιμετωπίζουμε δύο διαφορετικά προβλήματα: την ελαχιστοποίηση του συνολικού χρόνου εκτέλεσης του προγράμματος και την ελαχιστοποίηση της μέγιστης καθυστέρησης των εργασιών ως προς τις προθεσμίες παράδοσής τους. Το πρώτο πρόβλημα συναντάται συχνά στη σχετική βιβλιογραφία και ανήκει στην κατηγορία των δύσκολων συνδυαστικών προβλημάτων, ενώ πολλοί ευρηματικοί αλγόριθμοι έχουν κατά καιρούς προταθεί για την κατά προσέγγιση επίλυσή τους. Ως κατάλληλο αλγοριθμικό σχήμα και για τα δύο προβλήματα επιλέξαμε τη διαδικασία παρεμβολής εργασιών, η οποία κατασκευάζει σταδιακά το τελικό πρόγραμμα σε Ν βήματα, ερευνώντας πάντα προς την κατεύθυνση με την καλύτερη τιμή του κριτηρίου βελτίστου. Για τον προγραμματισμό εργασιών με προθεσμίες παράδοσης αναπτύσσουμε τη διαδικασία εφικτής παρεμβολής, η οποία επιδιώκει τον εντοπισμό εφικτών ως προς τις προθεσμίες προγραμμάτων με μικρό συνολικό χρόνο εκτέλεσης, ή, όταν αυτό δεν είναι δυνατόν, την κατασκευή προγραμμάτων με μικρές καθυστερήσεις εργασιών. Μ' αυτόν τον τρόπο η διαδικασία πραγματοποιεί δικριτηριακό προγραμματισμό ως προς την ελαχιστοποίηση της μέγιστης καθυστέρησης και του συνολικού χρόνου εκτέλεσης, παρέχοντας απόλυτη προτεραιότητα στο πρώτο κριτήριο έναντι του δευτέρου. Στη συνέχεια προτείνουμε δύο νέους μηχανισμούς βελτίωσης των λύσεων που ενσωματώνονται στη διαδικασία παρεμβολής: την αποθήκευση συνόλου μερικών διατάξεων ανά στάδιο και την επαναληπτική εκτέλεση της παρεμβολής με τυχαίες ουρές προγραμματισμού. Για την αξιολόγηση της απόδοσης των βελτιωμένων αλγορίθμων παρεμβολής πραγματοποιήσαμε συστηματικές δοκιμές με τυχαία προβλήματα δαιφόρων μεγεθών. Συνολικά παρήχθησαν 2730 τυχαία προβλήματα και 24660 λύσεις από τις παραλλαγές των αλγορίθμων (κάθε πρόβλημα λύθηκε με 9 περίπου διαφορετικούς τρόπους). Για το πρόβλημα της ελαχιστοποίησης του συνολικού χρόνου εκτέλεσης προγράμματος, συγκρίναμε τους αλγορίθμους παρεμβολής με τον αποδοτικότερο γνωστό ευρηματικό αλγόριθμο. Οι βελτιώσεις που πέτυχαν ήταν κατά μέσο όρο της τάξης του 20%-25%, ενώ σε ορισμένες περιπτώσεις έφτασαν το 45%. Παρόλ' αυτά οι αποκλίσεις από τις βέλτιστες λύσεις παρέμειναν σημαντικές, γεγονός που επιβεβαιώνει την αυξημένη δυσκολία του προβλήματος. Από τις παραπάνω μετρήσεις, κρισιμότερος παράγοντας για την ποιότητα των λύσεων αποδείχθηκε ο αριθμός των μηχανών (Μ), λόγω της εμφάνισης νεκρών χρόνων κατά την εκτέλεση. Οι δοκιμές που πραγματοποιήθηκαν για το πρόβλημα της ελαχιστοποίησης των καθυστερήσεων αφορούσαν το εφικτό των λύσεων και την αποτελεσματικότητα των δύο νέων μηχανισμών. Τέλος, παραθέτουμε τα συμπεράσματα της μελέτης μας για την απόδοση των αλγορίθμων παρεμβολής για το πρόβλημα ροϊκής παραγωγής, εντοπίζουμε περιπτώσεις μειωμένης απόδοσής τους για εργασίες με προθεσμίες και προτείνουμε τρόπους αντιμετώπισής τους. Εξετάζουμε, επίσης τη δυνατότητα εφαρμογής των αλγορίθμων παρεμβολής και σε άλλα αιτιοκρατικά προβλήματα διάταξης εργασιών.
Ημερομηνία έκδοσης 1993-12-01
Ημερομηνία διάθεσης 1997-06-2
Συλλογή   Σχολή/Τμήμα--Σχολή Θετικών και Τεχνολογικών Επιστημών--Τμήμα Επιστήμης Υπολογιστών--Μεταπτυχιακές εργασίες ειδίκευσης
  Τύπος Εργασίας--Μεταπτυχιακές εργασίες ειδίκευσης
Εμφανίσεις 140

Ψηφιακά τεκμήρια
No preview available

Προβολή Εγγράφου
Εμφανίσεις : 4

No preview available

Προβολή Εγγράφου