Βελτιστοποιηση Χρονοπρογραμματισμου Παραγωγης Με Χρηση Γενετικων Αλγοριθμων

Abstract

Ο όρος «χρονοπρογραμματισμός» έχει ορισθεί ως «...η κατανομή δεδομένων πόρων στη διάρκεια του χρόνου με σκοπό την ολοκλήρωση ενός συνόλου εργασιών.» (Baker [1974]). Το πρόβλημα χρονοπρογραμματισμού συνδυάζει επιστημονικές περιοχές τόσο διαφορετικές όπως είναι αυτές του σχεδιασμού παραγωγής (production planning), του computer design και της παραγωγής πλάνων (timetabling).Ειδικότερα, το πρόβλημα χρονοπρογραμματισμού παραγωγής είναι ένα από τα πιο πολύπλοκα συνδυαστικά προβλήματα που έχουν ποτέ διατυπωθεί. Αποτελεί ένα από τα σημαντικότερα θέματα που αφορούν ένα σύστημα παραγωγής και καθορίζει τη λειτουργικότητα και την απόδοσή του. Ο χρονικός προγραμματισμός παραγωγής θέτει το πρόβλημα του προγραμματισμού σε βραχυπρόθεσμη βάση των διατιθέμενων πόρων (ανθρώπινο δυναμικό, μηχανολογικός εξοπλισμός, οικονομικοί πόροι).Πολλοί διαφορετικοί αλγόριθμοι έχουν αναπτυχθεί στην προσπάθεια επίλυσης του προβλήματος χρονοπρογραμματισμού παραγωγής για όλους τους τύπους συστημάτων παραγωγής (συστήματα συνεχούς ροής, παραγωγής κατά παραγγελία, κατασκευής έργων). Στη συγκεκριμένη εργασία περιορίζουμε την ανάλυσή μας στο σύστημα παραγωγής κατά παραγγελία, περιγράφοντας τις διάφορες προσεγγίσεις επίλυσής του και δίνοντας έμφαση στην τεχνική των γενετικών αλγορίθμων.Τελικό σκοπός μας αποτελεί η ανάπτυξη μίας τεχνικής βελτιστοποίησης χρονοπρογραμματισμού παραγωγής σε σύστημα job-shop με τη χρήση γενετικών αλγορίθμων. Σε ένα απλό σύστημα 3*3 και με τη βοήθεια της τεχνικής που αναπτύχθηκε, επιτεύχθηκε μία ικανοποιητική βελτίωση της τιμής του κριτηρίου που είχαμε επιλέξει (χρόνος ολοκλήρωσης όλων των εργασιών).Scheduling is defined as "...the allocation of resources over time to perform a collection of tasks." (Baker [1974]). Scheduling problems combine areas as diverse as production planning, computer design and timetabling. More specifically, the production scheduling problem is one of the most difficult combinatorial problems ever formulated. It is one of the most important issues that concern a production system and it determines its functionalism and its performance. Production scheduling places the problem of planning in short-term base of allocated resources (human resources, mechanical equipment, economic resources). A lot of different algorithms have been developed in the effort of solution approaches of the production scheduling problem for all types of production systems (flow-shop, job-shop, projects). In the concrete work we limit our analysis in the job-shop production system, describing the different solution approaches and giving emphasis in the technique of genetic algorithms.Our final aim is the development of an optimization technique for the job-shop scheduling problem with the use of genetic algorithms. In a simple 3*3 system and with the help of the technique that was developed, was achieved a satisfactory improvement of the criterion value that we had selected (makespan).