Optimization methods for production scheduling: models, algorithms and applications in IoT driven flexible manufacturing systems

Abstract

This PhD dissertation proposes novel optimization methods for solving numerous variants of the Flexible Job Shop Scheduling Problem (FJSSP). The FJSSP is an NP-hard optimization problem introduced by Brucker and Schlie (1990). The basic formulation of the FJSSP, is a generic, extensible and has been used to model a plethora of operational realities and realistic production processes that appear in various manufacturing environments (Li and Gao 2020). In addition, due to its difficulty, the FJSSP has been the main focus of multiple research efforts that aim to develop efficient algorithms (meta-heuristics) for producing high quality solutions in short computational times. The classical FJSSP is defined as follows: There is a set of jobs where each job consists of one or more operations/activities. Every operation can be processed by one or more machines with different processing times. Every operation may have at most one successor or predecessor operations that also belong to the same job. Also, every machine can execute only one operation at a time and no pre-emption is allowed. The goal is to minimize the makespan, i.e. the completion time of the latest operation. One of the FJSSP variants that this thesis focuses on is the FJSSP with arbitrary precedence graphs. This variant aims to generalize the FJSSP by considering arbitrary precedence graphs that are used to describe the precedence relationships between the operations of a job. For this problem, mixed integer as well as constraint programming (CP) models are presented. In addition, a novel evolutionary algorithm (EA) is proposed to solve the problem. This framework adopts a path relinking mechanism that is able to recombine more than two solutions during the evolution of the population. Search intensification is performed using a tabu search algorithm, that is equipped with efficient feasibility and makespan estimation methods. The latter, uses new heorems that extend previous theoretical results of the FJSSP literature Dauzere-Peres and Paulli (1997). Detailed computational experiments on well-known benchmark sets of the literature show that the EA outperforms the current state-of-the-art by producing 59 new best solutions for a total of 228 problem instances, while 61 improved lower bounds are reported. To further explore the impact of arbitrary precedence graphs on the quality of the generated production schedules, a thorough experimentation is performed on new small and large scale problem instances. The goal is to study the effect of the problem flexibility and the precedence graph density on the makespan but also the difficulty of producing good upper bounds. Next, in an effort to fill the gaps of the literature regarding problems with combinations of different resource types, the FJSSP with multiple resource constraints is studied. This problem includes renewable, non-renewable and cumulative resources in the form of tools, utilities, limited capacity buffers, WIP buffers as well as arbitrary material resources. To solve the problem, a CP-based evolutionary algorithm is proposed. This framework uses long-term memory structures to store information about single operation-to-machine assignments and operation pair-to-machine assignments encountered in high quality and diverse solutions during the search process. The proposed constraint extraction operators use this information to generate constraint expressions which are imposed to the CP solver in an effort to guide the search to promising regions of the solution space. A comprehensive experimental study on well-known benchmark sets of the literature showcases the efficiency and the high competence of the framework compared to the state-of-the-art. To that end, 34 new best solutions are reported for well-known benchmark sets of the FJSSP, the Blocking Job Shop Scheduling Problem (BJSSP) and the Unrelated Parallel Machine Scheduling with Resources (UPMR) literature. To study the effect of the different resource types on the makespan, detailed computational experiments have been performed on new small and large-scale problem instances. Another subject of this thesis is the integration of optimization methods in manufacturing systems. At first, the integration of an optimization service within a Cognitive Digital Twin (CDT) framework is presented. The optimization service is developed so as to provide solutions for the production scheduling problem of an automotive manufacturing facility. The optimization problem can be modeled as an FJSSP with renewable and cumulative resources that also considers scheduled and unscheduled maintenance activities. The goal is to minimize the effect of line or machine breakdown events on the delivery of the production orders by carefully scheduling maintenance activities. A CP model is proposed to solve the problem, while the design and the integration of the optimization module within the CDT framework is presented. To evaluate the performance and the effectiveness of the proposed solution method real and randomly generated data are used. A thorough experimental study is performed in an effort to measure the impact of maintenance activities and resource constraints to various production schedule metrics such as, the makespan, the total flow time and the total workstation idle time. Lastly, a Situation Aware Manufacturing System (SAMS) is presented. The SAMS aims to identify and react to disruption events that may occur in manufacturing environments by coupling Industry 4.0 technologies such as predictive analytics, simulation and optimization. The SAMS framework adopts a design science research (DSR) approach in an effort to enable the identification and handling of disruptive events, the enumeration of user requirements as well as the validation of its effectiveness in a practical level. Two instantiations of SAMS are presented that correspond to two real-life manufacturing environments from the electronics and the automotive manufacturing industries, respectively. A comprehensive experimental study showcases the efficiency and effectiveness of the proposed framework in both applications.

Αυτή η διδακτορική διατριβή προτείνει νέες μεθόδους βελτιστοποίησης για την επίλυση πληθώρας παραλλαγών του Προβλήματος Χρονοπρογραμματισμού σε Συστήματα Ευέλικτων Εργασιών (ΠΧΣΕΕ). Το ΠΧΣΕΕ είναι ένα πρόβλημα βελτιστοποίησης με NP-δυσκολία που εισήχθει από τον Brucker et. al. 1990. Η βασική διατύπωση του ΠΧΣΕΕ είναι γενική, επεκτάσιμη και έχει χρησιμοποιηθεί για την μοντελοποίηση πληθώρας λειτουργικών χαρακτηριστικών και ρεαλιστικών διεργασιών παραγωγής που εμφανίζονται σε μεγάλο αριθμό περιβαλλόντων παραγωγής (Li et. al. 2020). Επιπρόσθετα και λόγω της δυσκολίας του, το ΠΧΣΕΕ αποτελεί το κύριο αντικείμενο μελέτης πολλαπλών ερευνητικών εργασιών οι οποίες αποσκοπούν στην ανάπτυξη αποδοτικών αλγορίθμων (μετα-ευρετικοί αλγόριθμοι) για την παραγωγή υψηλής ποιότητας λύσεων σε μικρούς υπολογιστικούς χρόνους. Η κλασσική εκδοχή του ΠΧΣΕΕ ορίζεται ως εξής: Υπάρχει ένα σύνολο εργασιών, όπου κάθε εργασία αποτελείται από μια ή περισσότερες διαδικασίες/δραστηριότητες. Κάθε διαδικασία μπορεί να εκτελεστεί από μία ή περισσότερες μηχανές με διαφορετικούς χρόνους επεξεργασίας. Κάθε διαδικασία μπορεί να έχει το πολύ μια διάδοχη ή προκάτοχη διαδικασία. Ακόμη, κάθε μηχανή μπορεί να εκτελεί μία διαδικασία σε κάθε χρονική στιγμή, ενώ δεν επιτρέπεται η κατακερματισμένη εκτέλεση οποιασδήποτε διαδικασίας. Ο σκοπός είναι η ελαχιστοποίηση του χρόνου ολοκλήρωσης της αργότερης διαδικασίας. Μία από τις παραλλαγές του ΠΧΣΕΕ στην οποία επικεντρώνεται αυτή η διατριβή, είναι το ΠΧΣΕΕ με αυθαίρετους γράφους προτεραιοτήτων. Αυτή η παραλλαγή αποσκοπεί στην γενίκευση του ΠΧΣΕΕ θεωρώντας αυθαίρετους γράφους προτεραιοτήτων οι οποίοι μπορούν να χρησιμοποιηθούν για την περιγραφή των συσχετίσεων των σχέσεων διαδοχής μεταξύ των διεργασιών μιας εργασίας. Για αυτό το πρόβλημα παρουσιάζονται μοντέλα μικτού ακέραιου προγραμματισμού, καθώς και προγραμματισμού περιορισμών (ΠΠ). Επιπρόσθετα, για την επίλυση του προβλήματος, προτείνεται ένας καινοτόμος εξελικτικός αλγόριθμος (ΕΑ). Αυτό το σχήμα υιοθετεί έναν μηχανισμό διασύνδεσης διαδρομών που βοηθά στον ανασυνδυασμό δύο ή παραπάνω λύσεων κατά τη διαδικασία εξέλιξης του πληθυσμού των λύσεων. Η εντατικοποίηση της αναζήτησης πραγματοποιείται χρησιμοποιώντας έναν αλγόριθμο απαγορευμένης έρευνας που είναι εξοπλισμένος με αποδοτικές μεθόδους εκτίμησης κόστους καθώς και εφικτότητας μιας κίνησης. Πιο συγκεκριμένα, για την εκτίμηση της εφικτότητας μιας κίνησης παρουσιάζονται νέα θεωρητικά αποτελέσματα τα οποία αποτελούν προεκτάσεις προηγούμενων θεωρητικών αποτελεσμάτων για το ΠΧΣΕΕ (Dauzere-Perez et.al. 1997). Λεπτομερή υπολογιστικά πειράματα σε γνωστά προβλήματα δείχνουν ότι ο ΕΑ που αναπτύχθηκε ξεπερνά σε απόδοση τους μέχρι στιγμής καλύτερους αλγόριθμους της βιβλιογραφίας. Ο ΕΑ παρήγαγε 59 βελτιωμένες λύσεις σε ένα σύνολο 228 προβλημάτων, ενώ ταυτόχρονα παρουσιάζονται 61 βελτιωμένα κατώτατα όρια. Για την εξερεύνηση της επίδρασης των αυθαίρετων γράφων προτεραιοτήτων στη ποιότητα των παραγόμενων προγραμμάτων παραγωγής, παρουσιάζονται λεπτομερή πειράματα σε ένα μικρού και μεγάλου μεγέθους προβλήματα. Σκοπός είναι η μελέτη της επίδρασης της ευελιξιμότητας του προβλήματος καθώς και της πυκνότητας των αυθαίρετων γράφων στην αντικειμενική συνάρτηση καθώς και στην δυσκολία παραγωγής καλών ανώτατων ορίων. Στη συνέχεια, σε μια προσπάθεια να καλυφθούν βιβλιογραφικά κενά σχετικά με προβλήματα που μελετούν συνδυασμούς διαφορετικών ειδών πόρων, τίθεται υπό μελέτη το πρόβλημα ΠΧΣΕΕ με πολλαπλούς περιορισμούς πόρων. Αυτή η παραλλαγή περιλαμβάνει ανανεώσιμες, μη ανανεώσιμες και συσσωρευτικούς πόρους με τη μορφή εργαλείων, ωφελιμοτήτων, ρυθμιστών περιορισμένης χωρητικότητας, ρυθμιστών για εν εξελίξει εργασίες καθώς και αυθαίρετων υλικών πόρων. Για την επίλυση αυτού του προβλήματος, προτείνεται ένας εξελικτικός αλγόριθμος βασισμένος σε ΠΠ. Αυτό το αλγοριθμικό πλαίσιο χρησιμοποιεί δομές μνήμης μεγάλης διάρκειας για την αποθήκευση πληροφοριών σχετικών με την ανάθεση διεργασιών σε μηχανές καθώς και ζευγών διεργασιών σε μηχανές, εφόσον αυτές έχουν εντοπισθεί σε υψηλής ποιότητας και διαφορετικές λύσεις κατά τη διάρκεια της εξερεύνησης του χώρου των λύσεων. Ακόμη προτείνονται χειριστές εξαγωγής περιορισμών οι οποίοι χρησιμοποιούν αυτές τις πληροφορίες προκειμένου να δημιουργήσουν συγκεκριμένες εξισώσεις περιορισμών οι οποίες λαμβάνονται υπόψιν από τον εκάστοτε επιλύτη ΠΠ προκειμένου να καθοδηγηθεί η εξερεύνηση σε υποσχόμενες περιοχές του χώρου των λύσεων. Η εμπεριστατωμένη πειραματική μελέτη πάνω σε γνωστά προβλήματα της βιβλιογραφίας υποδεικνύει την αποδοτικότητα και την υψηλή ανταγωνιστικότητα του αλγοριθμικού σχήματος σε σύγκριση με τους καλύτερους αλγορίθμους της βιβλιογραφίας. Επιπρόσθετα, παρουσιάζονται 34 νέες βελτιωμένες λύσεις για βιβλιογραφικά προβλήματα του ΠΧΣΕΕ, του Φραγμένου Προβλήματος Χρονοπρογραμματισμού Συστημάτων Εργασιών (ΦΠΧΣΕ) και του Προβλήματος Χρονοπρογραμματισμού σε μη Συσχετισμένες Παράλληλες Μηχανές με Πόρους (ΠΧΣΠΧ). Για την μελέτη της επίδρασης των διαφορετικών ειδών πόρων στην αντικειμενική συνάρτηση, διεξάγονται λεπτομερή υπολογιστικά πειράματα σε νέα μικρού και μεγάλου μεγέθους προβλήματα. Ένα ακόμα αντικείμενο της παρούσας διατριβής είναι η ενσωμάτωση μεθόδων βελτιστοποίησης σε συστήματα παραγωγής. Αρχικά, παρουσιάζεται η ενσωμάτωση μιας διαδικασίας βελτιστοποίησης σε ένα πλαίσιο Γνωστικού Ψηφιακού Διδύμου (ΓΨΔ). Αυτή η μέθοδος βελτιστοποίησης αναπτύσσεται ούτως ώστε να παρέχει λύσεις για το πρόβλημα χρονοπρογραμματισμού μιας αυτοκινητοβιομηχανίας. Το συγκεκριμένο πρόβλημα βελτιστοποίησης μοντελοποιείται σαν ένα ΠΧΣΕΕ με ανανεώσιμους και συσσωρευτικούς πόρους όπου επίσης συνυπολογίζονται προγραμματισμένες και μη διεργασίες συντήρησης. Σκοπός είναι η ελαχιστοποίηση της επίδρασης βλαβών μηχανών ή γραμμών παραγωγής στην ολοκλήρωση παραγγελιών μέσω του προσεκτικού χρονοπρογραμματισμού των διεργασιών συντήρησης. Ένα μοντέλο ΠΠ προτείνεται για την επίλυση του προβλήματος, ενώ επίσης παρουσιάζεται τόσο ο σχεδιασμός όσο και η ενσωμάτωση της μεθόδου βελτιστοποίησης σε ένα γενικότερο πλαίσιο ενός ΓΨΔ συστήματος. Για την εκτίμηση της αποδοτικότητας και της επίδοσης της προτεινόμενης μεθόδου βελτιστοποίησης, πραγματοποιούνται πειράματα τόσο σε πραγματικά όσο και σε συνθετικά δεδομένα. Ακόμη, παρουσιάζεται λεπτομερή υπολογιστικά πειράματα προκειμένου να γίνει μελέτη της επίδρασης των διεργασιών συντήρησης και των περιορισμών πόρων σε πληθώρα μετρικών παραγωγής όπως ο αργότερος χρόνος ολοκλήρωσης του προγράμματος, ο συνολικός χρόνος ροής καθώς και ο συνολικός χρόνος αδράνειας των μηχανών. Τέλος, παρουσιάζεται ένα Σύστημα Παραγωγής με Επίγνωση Καταστάσεων (ΣΠΕΚ). Το ΣΠΕΚ στοχεύει στην αναγνώριση και αντίδραση σε διαταραχές που μπορούν να συμβούν σε πραγματικά περιβάλλοντα παραγωγής, χρησιμοποιώντας νέες τεχνολογίες της Βιομηχανίας 4.0 όπως προγνωστική ανάλυση, εξομοίωση και βελτιστοποίηση. Το ΣΠΕΚ υιοθετεί μια προσέγγιση Έρευνας Επιστήμης Σχεδιασμού (ΕΕΣ) σε μια προσπάθεια να ενεργοποίηση την αναγνώριση και την διαχείριση διαταραχών, την απαρίθμηση των απαιτήσεων του χρήση καθώς και την επικύρωση της αποτελεσματικότητάς του συστήματος σε πρακτικό επίπεδο. Δύο εκδοχές του ΣΠΕΚ παρουσιάζονται οι οποίες αντιστοιχούν σε δύο πραγματικά περιβάλλοντα παραγωγής από τους χώρους των ηλεκτρονικών και της αυτοκινητοβιομηχανίας. Μια λεπτομερής υπολογιστική μελέτη παρουσιάζει την αποτελεσματικότητα και την επάρκεια του συστήματος και στις δύο περιπτώσεις.