Μοντελοποίηση και επίλυση σύνθετων προβλημάτων προγραμματισμού εργασιών με χρήση χρονισμένων αυτομάτων: εφαρμογή σε δυναμικά δίκτυα παραγωγής

Abstract

The thesis aims at developing an integrated innovative approach for solvingproduction scheduling problems by exploiting the computational capabilities of finiteautomata and more specifically of a new extension of them, called timed automata.The characteristics and capabilities of timed automata in conjunction with thedevelopment of tools which allow the accurate modelling of complex systems basedon the principles of the automata theory were the main reasons for examining, inthe framework of the thesis, whether such a modern approach could be appliedeffectively on problems related to job and task scheduling.In the above context, the thesis proposes an integrated approach for modellingproduction scheduling problems based on the visualization of the several discretestates of a production system. Particular emphasis is given to the development ofmodels of production systems with complex structures, which significantly differfrom the usual production systems’ structures on which the majority of schedulingapproaches are focused.More specifically, in the context of the thesis, a comprehensive study is presentedbased on existing applications of timed automata on production schedulingproblems, while a new innovative approach is being proposed for modelling complexproduction systems in order to solve scheduling problems by utilising automatatheory optimisation algorithms. A major innovation of the thesis is the addition ofseveral types of costs to the timed automata models developed for solving jobscheduling problems. This way it is possible to address and optimally solve problemsthat the objective function includes not only time but also cost elements involved inthe production process, such as processing costs, transportation costs, storage costs,production switching costs etc.In the above framework, several timed automata models have been developedwhich can be used as templates for building automata networks able to deal withcomplex cases like preemptive job scheduling problems and scheduling of jobs withalternative production routes. The optimization criteria that can be used to solveproblems using the proposed approach are not limited to the usual time-relatedcriteria but they involve a variety of cost elements, providing the possibility offinding optimal schedules that minimize either total production cost or specific typesof costs, depending on the case or the problem.The proposed approach is extended and adapted appropriately to addressscheduling problems in Dynamic Manufacturing Networks (DMN) environments. Theinnovative approach, presented in the thesis, addresses the problem of the limited coordination between producers belonging in a manufacturing network, taking intoaccount several types of production and logistics costs, in order to optimize theoperation and the production plans of the whole network.The proposed approach has been applied successfully, in the context of the thesis,on a real manufacturing network case. More specifically, the manufacturing networkexamined is a network formed by a Greek Original Equipment Manufacturer (OEM),producing heating boilers, and by its main suppliers. The timed automata approachhas been applied on real scheduling problems of this network and the results werevery promising since the production plans produced were significantly better thanthe plans which were initially formed by the OEM.By examining the approach proposed in the thesis, and by taking into account theexisting trend of utilising automata networks in manufacturing environments forsolving several types of problems, it can be concluded that the thesis has significantvalue not only in the research field but also in practice. The continuous developmentof automata modelling tools in conjunction with the fact that the proposed approachprovides an easy-to-apply method for modelling complex production systems andsolving scheduling problems guarantee that the outcomes of the thesis can befurther exploited both in research and commercial level.

Η παρούσα διδακτορική διατριβή έχει ως αντικείμενο την ανάπτυξη μιας ολοκληρωμένης καινοτομικής προσέγγισης για την επίλυση προβλημάτων χρονικού προγραμματισμού παραγωγής με αξιοποίηση των υπολογιστικών δυνατοτήτων που παρέχουν τα αυτόματα πεπερασμένων καταστάσεων με χρόνους (χρονισμένα αυτόματα). Η διατριβή εδράζεται σε ένα επιστημονικό πεδίο το οποίο έχει αρχίσει να αναπτύσσεται την τελευταία μόλις δεκαετία και η έρευνα για την περαιτέρω αξιοποίησή του βρίσκεται σε πλήρη εξέλιξη. Οι δυνατότητες που παρέχουν τα χρονισμένα αυτόματα σε συνδυασμό με την ανάπτυξη εργαλείων που επιτρέπουν τη μοντελοποίηση σύνθετων συστημάτων με βάση τις αρχές της θεωρίας αυτομάτων, αποτέλεσαν την αφορμή για να ελεγχθεί κατά πόσο θα μπορούσε μια τέτοια σύγχρονη προσέγγιση να εφαρμοστεί αποτελεσματικά στην αντιμετώπιση προβλημάτων του άπτονται του χρονικού προγραμματισμού εργασιών.Στο παραπάνω πλαίσιο, η παρούσα διατριβή προτείνει μια ολοκληρωμένη προσέγγιση για τη μοντελοποίηση προβλημάτων χρονικού προγραμματισμού εργασιών η οποία βασίζεται στην απεικόνιση των διακριτών καταστάσεων στις οποίες περιέρχεται ένα παραγωγικό σύστημα κατά την εκτέλεση των διεργασιών του. Ιδιαίτερη έμφαση δόθηκε στην μοντελοποίηση σύνθετων παραγωγικών συστημάτων που αποκλίνουν των κλασικών παραγωγικών δομών στις οποίες επικεντρώνεται η πλειοψηφία των προσεγγίσεων χρονοπρογραμματισμού εργασιών. Πιο συγκεκριμένα, στο πλαίσιο της διατριβής, πραγματοποιήθηκε εκτενής μελέτη των εφαρμογών των χρονισμένων αυτομάτων σε προβλήματα της παραγωγής και αναπτύχθηκε μια νέα προσέγγιση για τη μοντελοποίηση παραγωγικών συστημάτων σύνθετης δομής και για την βέλτιστη επίλυση προβλημάτων χρονοπρογραμματισμού με αξιοποίηση αλγορίθμων προσπελασιμότητας. Σημαντική καινοτομία της διατριβής αποτελεί τόσο η δυνατότητα που παρέχει η προτεινόμενη προσέγγιση για την επίλυση σύνθετων προβλημάτων που δε μπορούν να προσεγγισθούν από κλασικές μεθόδους δρομολόγησης εργασιών σε κέντρα εργασίας όσο και η προσθήκη στα μοντέλα των αυτομάτων του στοιχείου του κόστους. Με τον τρόπο αυτό έγινε εφικτή η αντιμετώπιση και βέλτιστη επίλυση προβλημάτων στα οποία ο στόχος βελτιστοποίησης δεν είναι συνάρτηση αποκλειστικά του χρόνου αλλά και μιας σειράς διαφορετικών τύπων κόστους που υπεισέρχονται στην παραγωγική διαδικασία, όπως τα καθαρά κόστη κατεργασίας,τα κόστη μεταφοράς και αποθήκευσης, τα κόστη καθυστέρησης παράδοσης αλλά και ειδικές περιπτώσεις όπως τα κόστη διακοπής και επανεκκίνησης μιας γραμμής παραγωγής. Σε αυτό τον άξονα αναπτύχθηκαν μοντέλα χρονισμένων αυτομάτων με κόστη, τα οποία επιτρέπουν τη μοντελοποίηση και επίλυση προβλημάτων ανεξάρτητα της δομής του παραγωγικού συστήματος και των περιορισμών που τη διέπουν, όπως προβλημάτων με παράλληλες μηχανές / γραμμές παραγωγής, με εναλλακτικά φασεολόγια ή με εργασίες που μπορούν να διακόπτονται και να επανακάμπτουν.Τα δε κριτήρια βελτιστοποίησης τα οποία μπορούν να χρησιμοποιηθούν για την επίλυση των προβλημάτων με την προτεινόμενη προσέγγιση δεν περιορίζονται στα κριτήρια χρονικής διάστασης, όπως ο συνολικός χρόνος ολοκλήρωσης των εργασιών, αλλά αντίθετα εμπλέκουν ποικίλα στοιχεία κόστους, παρέχοντας τη δυνατότητα εξεύρεσης βέλτιστων χρονοπρογραμμάτων τα οποία περιορίζουν είτε το συνολικό παραγωγικό κόστος είτε επιλεγμένα στοιχεία κόστους, ανάλογα με το πρόβλημα. Στη συνέχεια της διατριβής, η προτεινομένη προσέγγιση επεκτάθηκε και προσαρμόστηκε κατάλληλα για την αντιμετώπιση του προβλήματος του χρονικού προγραμματισμού σε δυναμικά δίκτυα παραγωγής. Η καινοτόμος πρόταση της διατριβής αντιμετωπίζει τα δεδομένα προβλήματα συντονισμού μεταξύ των παραγωγικών μονάδων των επιχειρήσεων που συμμετέχουν σε ένα δυναμικό δίκτυο παραγωγής και μοντελοποιεί τα στοιχεία κόστους που πρέπει να ληφθούν υπόψη προκειμένου να βελτιστοποιηθεί η λειτουργία του όλου δικτύου. Έτσι, η προτεινόμενη από τη διατριβή προσέγγιση παρέχει τη δυνατότητα αξιοποίησης των ισχυρών υπολογιστικών πλεονεκτημάτων των χρονισμένων αυτομάτων για την αποτελεσματική επίλυση προβλημάτων προγραμματισμού ανάθεσης εργασιών και εκτέλεσης παραγωγικών διεργασιών σε επίπεδο δικτύου συνεργαζόμενων επιχειρήσεων.Η προτεινόμενη προσέγγιση εφαρμόστηκε με απόλυτη επιτυχία, στο πλαίσιο της διατριβής, σε μια πραγματική περίπτωση παραγωγικού δικτύου βάσει στοιχείων τα οποία διατέθηκαν από βιομηχανική επιχείρηση κατασκευής λεβήτων θέρμανσης η οποία δραστηριοποιείται στον ελληνικό χώρο και έχει δομήσει ένα συνεργατικό δίκτυο με τους βασικούς προμηθευτές της. Εξετάζοντας στο σύνολό της την προσέγγιση που αναπτύσσεται στην παρούσα διατριβή, σε συνδυασμό με τις σύγχρονες τάσεις στον τομέα της παραγωγής που αξιοποιούν συστήματα αυτομάτων για την αντιμετώπιση διαφόρων ζητημάτων βελτιστοποίησης ή/και αυτομάτου ελέγχου, προκύπτει το συμπέρασμα ότι η πρόταση της διατριβής έχει σημαντική αξία όχι μόνο σε ερευνητικό αλλά και σε πρακτικό επίπεδο. Η συνεχής εξέλιξη των εργαλείων μοντελοποίησης αυτομάτων,σε συνδυασμό με το γεγονός ότι προσεγγίσεις, όπως η προτεινόμενη, συνδυάζουν την αποτελεσματικότητα και τη σχετική ευκολία μοντελοποίησης με την αυξημένη ευελιξία η οποία χαρακτηρίζει τις σύγχρονες παραγωγικές μονάδες, παρέχουν τα εχέγγυα για περαιτέρω αξιοποίηση των ερευνητικών αποτελεσμάτων και συμπερασμάτων της διατριβής όχι μόνο σε ερευνητικό αλλά και σε εμπορικό /επιχειρησιακό επίπεδο.