Optimization-based techniques for production scheduling of continuous and batch processes

Abstract

During the last few years, the significant advances of cutting-edge technologies led to a fourth industrial revolution, referred to as Industry 4.0. At the dawn of the new era of industrialization, modern production environments attempt to integrate various decisional and physical aspects of production processes into automated and decentralized systems. Two of the main decision levels in these systems, are production planning and scheduling, which constitute a major component for the efficient operation of the process industries. Especially in the current competitive globalized market, production planning and scheduling are of vital importance to most industries, since profit margins are miniscule. Therefore, efficient usage of resources has a critical role in the viability and sustainability of all industries. Additionally, efficiency targets are increasingly being adapted with sustainable production goals towards a green and circular economy. In addition to cost savings, further objectives must be considered, such as the reduction of greenhouse gas emissions, the increased usage of renewable energy sources and the reduction of waste. These objectives can be achieved by exploiting recent advances of computer-aided optimization tools and methodologies. During the last 30 years plethora of research contributions have been published by the scientific community in the field of production scheduling optimization. However, the practical implementation of optimization-based scheduling frameworks in real-life industrial applications is limited. In most industries, the optimization of production scheduling constitutes an extremely challenging and time-consuming task, since the majority of decision-makers prefer to generate scheduling solutions manually, or use simulation-based software, resulting to suboptimal solutions. This thesis proposes systematic mathematical frameworks for the optimization of a wide variety of complex production planning and scheduling problems. The optimization-based solutions are based on mixed integer linear programming (MILP) frameworks. However, a main drawback of MILP models is their inability to handle efficiently large problem instances, since the model size increases exponentially with the problem size. To face this challenge, novel MILP-based solution algorithms have been also investigated for the solution of real-life industrial problems.More specifically, the first chapter considers the scheduling problem of a real-life large-scale industrial facility of packaged consumer goods. The problem under consideration is mainly focused on the packing stage which constitutes the major production bottleneck. Two precedence-based MILP mathematical models are proposed to describe explicitly the continuous process of the plant. The models rely on allocation, timing and sequencing constraints. Additional constraints, referring to the production/formulation stage of the plant, are also imposed in order to ensure the generation of feasible production schedules. Furthermore, two MILP-based decomposition algorithms are proposed for the efficient solution of large-scale problem instances. The applicability of the proposed approaches is illustrated by solving several real-life industrial problem instances of a multinational consumer goods industry under consideration. The results lead to nearly optimal scheduling in reasonable solution times, comparing favorably with manually derived schedules by the production engineers.The second chapter addresses the scheduling problem of continuous make-and-pack industries, including flexible intermediate storage vessels, aiming to provide better synchronisation of the production stages. A novel continuous-time, precedence-based, MILP model is developed for the problem under consideration. Extending previously proposed precedence-based MILP models, multiple campaigns of the same recipe can be stored simultaneously in a storage tank. Explicit resource constraints related to the generation and recycling of byproduct are introduced, to achieve a better utilization of the available resources. Several case studies, inspired by a large-scale consumer goods industry have been solved, to illustrate the applicability of the proposed frameworks. Although global optimal solutions cannot be guaranteed, good quality schedules are obtained, while the utilisation of intermediate buffers leads to a better synchronisation of the production stages and increased productivity.The final chapter of the thesis presents an integrated planning and scheduling framework for the optimal contract selection problem of Contract Manufacturing Organizations (CMOs) under uncertainty in pharmaceutical industry. During the last 20 years a growing number of pharmaceutical companies outsource part of their operations to reduce operational cost and mitigate their risk exposure. Contract Manufacturing Organizations (CMOs) utilize their facilities to manufacture products for multinational pharmaceutical companies on a contract basis. Considering a multistage, multiproduct, batch facility of a secondary pharmaceutical industry, an aggregated MILP planning model, including material balances and allocation constraints is firstly proposed. Using a rolling horizon approach, the production targets are then provided to a precedence-based MILP scheduling model to define batch-sizing and sequencing decisions in detail. To model demand uncertainty, a scenario-based approach is proposed, considering the Value-at-Risk (VaR) and Conditional Value-at-Risk (CVaR) measures. Since large number of scenarios introduces significant challenges to computations, a scenario reduction framework is integrated to reduce the total solution time, when considering large-scale problem instances. The proposed methodology increases the profitability of CMOs, by selecting the optimal contract combinations, depending on their risk tolerance, while considering the availability and optimal utilization of underlying production resources.

Το σύγχρονο βιομηχανικό περιβάλλον χαρακτηρίζεται από υψηλή αστάθεια, λόγω των ολοένα και ταχύτερα μεταβαλλόμενων οικονομικών και πολιτικών συνθηκών σε παγκόσμια κλίμακα. Έτσι, παρατηρείται μία ισχυρή κλιμάκωση του ανταγωνισμού μεταξύ των επιχειρήσεων, οι οποίες επικεντρώνονται ολοένα και περισσότερο στη διαρκή βελτίωση των διαδικασιών λήψης αποφάσεων. Η ολοένα αυξανόμενη ζήτηση, σε συνδυασμό με τον υψηλό αριθμό τελικών προϊόντων, καθιστούν την κάλυψη πολλαπλών παραγγελιών μία σημαντική πρόκληση. Συνεπώς, για την επιτυχή ικανοποίηση των αναγκών των πελατών, είναι ιδιαίτερα σημαντική η αποτελεσματική χρήση του εξοπλισμού και η αποδοτική αξιοποίηση όλων των διαθέσιμων πόρων της παραγωγικής μονάδας, με απώτερο στόχο τη μείωση του κόστους παραγωγής. Την ίδια στιγμή, οι βιομηχανίες οφείλουν να συμμορφώνονται με τις ολοένα και πιο αυστηρές περιβαλλοντικές νομοθετικές ρυθμίσεις και να εντείνουν τις προσπάθειές τους για μείωση του ενεργειακού αποτυπώματος και των εκπομπών ρύπων. Με βάση τα παραπάνω, παρατηρείται μία σταδιακά εντεινόμενη προσπάθεια αυτοματοποίησης των διαδικασιών λήψης αποφάσεων, σε όλα τα ιεραρχικά επίπεδα, βασιζόμενη στην προοδευτικά αυξανόμενη χρήση νέων υπολογιστικών εργαλείων και τεχνολογιών αιχμής. Ο χρονοπρογραμματισμός της παραγωγής αποτελεί ένα ζωτικής σημασίας επίπεδο λήψης αποφάσεων και διαδραματίζει σημαίνοντα ρόλο στην απόδοση μίας βιομηχανικής μονάδας. Αφορά την κατανομή των πόρων μεταξύ ανταγωνιστικών δραστηριοτήτων σε συγκεκριμένες χρονικές περιόδους, έχοντας ως στόχο τη βελτιστοποίηση ενός ή περισσότερων αντικειμενικών στόχων. Για τη βελτιστοποίηση του χρονοπρογραμματισμού παραγωγής καθίσταται απαραίτητη η μελέτη του συνόλου των διεργασιών που λαμβάνουν χώρα και οι αλληλεπιδράσεις τους με το ευρύτερο βιομηχανικό περιβάλλον. Τα τελευταία 30 χρόνια έχει προταθεί ένα ευρύ φάσμα μεθόδων για την αντιμετώπιση αυτών των συνδυαστικών προβλημάτων, ωστόσο η πλειονότητα τους επικεντρώνεται κυρίως σε προβλήματα που δεν αποτυπώνουν την βιομηχανική πραγματικότητα. Τα προβλήματα χρονοπρογραμματισμού των σύγχρονων βιομηχανιών περιλαμβάνουν πληθώρα τελικών προϊόντων και μηχανολογικού εξοπλισμού, ενώ η παραγωγική διαδικασία καθίσταται ιδιαίτερα περίπλοκη. Συνήθως τα προβλήματα αυτά υπόκεινται σε πολλαπλούς τεχνικούς και λειτουργικούς περιορισμούς, με αποτέλεσμα να χαρακτηρίζονται από εξαιρετικά υψηλή υπολογιστική πολυπλοκότητα και ως εκ τούτου δεν μπορούν να επιλυθούν σε χρόνους αποδεκτούς από την βιομηχανία. Σήμερα, στις περισσότερες βιομηχανικές μονάδες, το πρόγραμμα παραγωγής λαμβάνονται χειροκίνητα με τη μέθοδο της δοκιμής και σφάλματος, από εξειδικευμένους μηχανικούς παραγωγής, βασιζόμενοι κυρίως στην εμπειρία τους και τη χρήση περιορισμένου αριθμού βοηθητικών εργαλείων, όπως λογισμικά προσομοίωσης. Ως εκ τούτου, κρίνεται αναγκαία η ανάπτυξη νέων υπολογιστικών τεχνικών, οι οποίες θα οδηγούν σε υψηλής ποιότητας λύσεις σε σύντομο χρόνο, και κατά συνέπεια θα αποτελέσουν τη βάση για την ανάπτυξη αποτελεσματικών υπολογιστικών εργαλείων που θα συμβάλλουν σημαντικά στη βέλτιστη λήψη αποφάσεων. Με βάση τα παραπάνω, η παρούσα διατριβή επικεντρώνεται στην ανάπτυξη νέων μαθηματικών μοντέλων και τεχνικών, τα οποία λαμβάνουν υπόψιν όλα τα απαραίτητα χαρακτηριστικά ρεαλιστικών βιομηχανικών μονάδων, όσο και στην ανάπτυξη νέων αλγορίθμων για την επίλυση πολύπλοκων προβλημάτων μεγάλης κλίμακας, σε αποδεκτό από τη βιομηχανία υπολογιστικό χρόνο.Ο προγραμματισμός παραγωγής αποτελεί ένα μόνο τμήμα της ιεραρχικής διαδικασίας λήψης αποφάσεων και περιλαμβάνει ένα μέρος των αποφάσεων που λαμβάνονται σε μία βιομηχανική μονάδα. Ένα ιδιαιτέρως σημαντικό επίπεδο αποφάσεων αποτελεί επίσης ο μακροχρόνιος σχεδιασμός παραγωγής (Planning). Σε αντίθεση με το χρονοπρογραμματισμό παραγωγής, όπου μελετάται συνήθως ένας χρονικός ορίζοντας έως και 2-3 εβδομάδων, ο σχεδιασμός της παραγωγής πραγματεύεται τη μελέτη ενός μακροχρόνιου χρονικού ορίζοντα, ο οποίος είναι σύνηθες να κυμαίνεται από μερικές εβδομάδες έως και 5 ή 10 έτη. Σε αυτό το επίπεδο, λαμβάνονται κυρίως στρατηγικές και οικονομικές αποφάσεις της εταιρείας, σχετικά με το σχεδιασμό και τη δυναμικότητα της βιομηχανικής μονάδας, τον προγραμματισμό για την αγορά προμηθειών και την παράδοση των παραγγελιών κτλ. Συνήθως, οι αποφάσεις του σχεδιασμού παραγωγής αποτελούν δεδομένα εισόδου για το ιεραρχικό επίπεδο του χρονοπρογραμματισμού. Η ταυτόχρονη μελέτη των δύο επιπέδων αποφάσεων (σχεδιασμός και χρονοπρογραμματισμός παραγωγής), παρουσιάζει σημαντικά πλεονεκτήματα έναντι της επιμέρους μελέτης των δύο προβλημάτων και μπορεί να οδηγήσει σε λύσεις οι οποίες στην πράξη αποδεικνύονται πιο αποτελεσματικές και περισσότερο εφαρμόσιμες. Μάλιστα, σε αρκετές βιομηχανικές μονάδες η επιμέρους μελέτη και επίλυση των δύο προβλημάτων μπορεί να οδηγήσει σε λύσεις οι οποίες είναι μη εφικτές στα κατώτερα επίπεδα λήψης αποφάσεων, όπως το επίπεδο του χρονοπρογραμματισμού παραγωγής. Στον αντίποδα, ένα σημαντικό μειονέκτημα που παρουσιάζουν οι ενοποιημένες προσεγγίσεις για την παράλληλη μελέτη των δύο προβλημάτων, είναι η ανάγκη για χρήση αυξημένου αριθμού μεταβλητών και περιορισμών, κάτι που επιφέρει υψηλότερη πολυπλοκότητα και καθιστά το ενοποιημένο πρόβλημα δύσκολα επιλύσιμο.Λόγω της μεγάλης διάρκειας που απαιτείται για την ανάπτυξη νέων φαρμάκων και του υψηλού κόστους των κλινικών δοκιμών, το πρόβλημα του ενοποιημένου σχεδιασμού και χρονοπρογραμματισμού παραγωγής είναι ιδιαίτερα σημαντικό για τις φαρμακευτικές βιομηχανίες. Επιπλέον, κατά τη διάρκεια των τελευταίων 20 ετών, λόγω του έντονου ανταγωνισμού, παρατηρείται στη φαρμακευτική βιομηχανία μια αυξανόμενη τάση για υπογραφή συμβάσεων μεταξύ μεγάλων πολυεθνικών εταιρειών και εξωτερικών συνεργατών για την ανάθεση της παραγωγής των προϊόντων τους (Contract Manufacturing). Αυτό επιτρέπει στις φαρμακευτικές βιομηχανίες να επικεντρωθούν σε μεγαλύτερο χαρτοφυλάκιο προϊόντων χωρίς να αυξάνουν τις δαπάνες που συνδέονται με την κατασκευή νέων εγκαταστάσεων. Ωστόσο, η ζήτηση των φαρμακευτικών προϊόντων είναι ιδιαίτερα μεταβλητή, καθώς μπορεί να επηρεασθεί σημαντικά από απροσδόκητες παρενέργειες ή από τη χαμηλή δραστικότητα των νέων φαρμάκων. Ως εκ τούτου, οι εξωτερικοί συνεργάτες (Contract Manufacturing Organizations) οφείλουν να επιλέγουν το βέλτιστο συνδυασμό συμβολαίων/προϊόντων, ώστε να μεγιστοποιήσουν τα κέρδη τους λαμβάνοντας όμως υπόψιν και το υποκείμενο ρίσκο. Στη βιβλιογραφία, εκτενής αριθμός ερευνητικών εργασιών περιορίζεται κυρίως στη μελέτη των επιμέρους προβλημάτων του χρονοπρογραμματισμού ή του μακροχρόνιου σχεδιασμού παραγωγής της φαρμακευτικής βιομηχανίας. Ωστόσο, δεν εντοπίζεται κάποια εργασία η οποία να επικεντρώνεται στη μελέτη του ενιαίου προβλήματος του σχεδιασμού και χρονοπρογραμματισμού παραγωγής υπό αβεβαιότητα σε φαρμακευτικές βιομηχανίες και ειδικότερα, σε βιομηχανικές μονάδες που λειτουργούν κατ' ανάθεση παραγωγής φαρμακευτικών προϊόντων άλλων εταιρειών (Contract Manufacturing Organizations). Τα παραπάνω δημιουργούν ένα ερευνητικό κενό μεγάλου ενδιαφέροντος, ιδιαιτέρως λόγω των τελευταίων εξελίξεων και της κρίσης της φαρμακευτικής εφοδιαστικής αλυσίδας. Έτσι, στο τελευταίο τμήμα της διδακτορικής διατριβής μελετάται το ενιαίο πρόβλημα του σχεδιασμού και του χρονοπρογραμματισμού παραγωγής, σε βιομηχανικές μονάδες φαρμάκων υπό αβεβαιότητα της ζήτησης. Μελετάται επίσης το πρόβλημα της βέλτιστης επιλογής συμβολαίων για την παραγωγή προϊόντων σε βιομηχανικές μονάδες φαρμάκων, οι οποίες λειτουργούν κατ' ανάθεση παραγωγής φαρμακευτικών προϊόντων άλλων εταιρειών (Contract Manufacturing Organizations).Όλα τα προτεινόμενα μοντέλα και οι αλγόριθμοι επίλυσης υλοποιήθηκαν με χρήση του λογισμικού GAMS και του επιλυτή CPLEX. Αναλυτικότερα, η συνεισφορά της παρούσας διδακτορικής διατριβής συνοψίζεται παρακάτω.Αρχικά, μελετάται το πρόβλημα του βέλτιστου χρονοπρογραμματισμού παραγωγής σε βιομηχανίες πολλαπλών σταδίων παραγωγής, που περιλαμβάνουν διεργασίες συνεχούς λειτουργίας. Ειδικότερα, αναπτύχθηκαν δύο μαθηματικά μοντέλα Μεικτού-Ακεραίου Γραμμικού Προγραμματισμού (MILP) για την ελαχιστοποίηση του συνολικού χρόνου εναλλαγών (changeover minimization). Τα προτεινόμενα μαθηματικά μοντέλα αλληλουχίας (precedence-based), επικεντρώνονται στο στάδιο της συσκευασίας βιομηχανικών μονάδων καταναλωτικών αγαθών και βασίζονται σε μια σειρά από λογικούς αλλά και τεχνικούς περιορισμούς. Επιπλέον περιορισμοί, που αφορούν το συνεχές στάδιο παραγωγής των ενδιάμεσων προϊόντων, καθώς και περιορισμοί για τους χρόνους παράδοσης των προϊόντων, συμπεριλαμβάνονται προκειμένου να διασφαλισθεί η κατασκευή ρεαλιστικών προγραμμάτων παραγωγής. Για την επίλυση προβλημάτων προγραμματισμού παραγωγής μεγάλης κλίμακας σε βιομηχανικές μονάδες συνεχούς λειτουργίας, αναπτύχθηκαν επίσης δύο αλγόριθμοι βελτιστοποίησης. Ο στόχος των αλγορίθμων επίλυσης είναι η διάσπαση του αρχικού προβλήματος σε μικρότερα και ευκολότερα επιλύσιμα υποπροβλήματα (decomposition-based algorithm). Για την αξιολόγηση των προτεινόμενων μαθηματικών μοντέλων, και των αλγορίθμων επίλυσης, εξετάστηκαν διάφορα σενάρια ζήτησης και κατασκευάστηκαν προγράμματα παραγωγής για πάνω από 130 τελικά προϊόντα που παράγονται εβδομαδιαίως. Οι μελέτες υλοποιήθηκαν με τη χρήση ρεαλιστικών δεδομένων μιας βιομηχανικής μονάδας καταναλωτικών προϊόντων της εταιρείας Procter and Gamble (P&G). Τα αποτελέσματα αποδεικνύουν πως οι προτεινόμενοι αλγόριθμοι βελτιστοποίησης και τα μαθηματικά μοντέλα οδηγούν σε σημαντική μείωση του χρόνου εναλλαγών και συνεπώς σε αύξηση της παραγωγικότητας της μονάδας.Επιπλέον μελετήθηκε ο βέλτιστος χρονοπρογραμματισμός παραγωγής σε βιομηχανίες συνεχούς λειτουργίας με δυνατότητα ενδιάμεσης αποθήκευσης και ανακύκλωσης παραπροϊόντων. Προτείνεται ένα νέο μαθηματικό μοντέλο Μεικτού-Ακεραίου Γραμμικού Προγραμματισμού (MILP), το οποίο αποτελείται από μια σειρά λογικών και τεχνικών περιορισμών, που σχετίζονται με την αλληλουχία των προϊόντων, τη διαθεσιμότητα των συσκευών, τους χρόνους παράδοσης των προϊόντων κ.α. Επιπλέον, το μαθηματικό μοντέλο βασίζεται σε συνεχή αναπαράσταση του χρονικού ορίζοντα, ενώ οι περιορισμοί των ισοζυγίων μάζας ικανοποιούνται μέσω της χρήσης ενός νέου συνόλου δυαδικών μεταβλητών. Τέλος, περιλαμβάνονται περιορισμοί για ρεύματα ανακύκλωσης των παραπροϊόντων, τα οποία παράγονται κατά τη διάρκεια των διεργασιών καθαρισμού των συσκευών. Παράλληλα, αναπτύχθηκε ένας αλγόριθμος βελτιστοποίησης (decomposition-based algorithm), για την επίλυση προβλημάτων χρονοπρογραμματισμού παραγωγής, βιομηχανικών μονάδων μεγάλης κλίμακας. Μελετήθηκαν προβλήματα μεγάλης κλίμακας, χρησιμοποιώντας ρεαλιστικά δεδομένα, από μία βιομηχανική μονάδα καταναλωτικών προϊόντων. Από την αξιολόγηση των εξαγόμενων λύσεων, συμπεραίνεται πως το προτεινόμενο μαθηματικό μοντέλο σε συνδυασμό με τις στρατηγικές επίλυσης, οδηγούν σε λύσεις που βελτιώνουν το συγχρονισμό μεταξύ των σταδίων παραγωγής, ενώ παράλληλα αυξάνουν την αποδοτικότητα του εξοπλισμού και τη χρήση των πρώτων υλών, μειώνουν το συνολικό κόστος και ελαχιστοποιούν τη παραγωγή παραπροϊόντων.Στο τελευταίο τμήμα της διδακτορικής διατριβής μελετάται η βελτιστοποίηση του ενιαίου προβλήματος του σχεδιασμού και χρονοπρογραμματισμού παραγωγής σε βιομηχανικές μονάδες φαρμάκων υπό αβεβαιότητα. Αρχικά προτείνεται ένα μοντέλο Μεικτού-Ακέραιου Γραμμικού Προγραμματισμού (MILP), για το επιμέρους πρόβλημα του βραχυχρόνιου χρονοπρογραμματισμού παραγωγής σε μονάδες διαλείπουσας λειτουργίας. Το μαθηματικό μοντέλο, το οποίο βασίζεται σε συνεχή αναπαράσταση του χρονικού ορίζοντα, αποτελείται από μια σειρά περιορισμών, οι οποίοι σχετίζονται με την αλληλουχία των προϊόντων, τη δυναμικότητα των συσκευών, κ.α. Επιπροσθέτως, αναπτύχθηκε ένα μοντέλο Μεικτού-Ακέραιου Γραμμικού Προγραμματισμού (MILP), για το πρόβλημα του μακροχρόνιου σχεδιασμού παραγωγής σε βιομηχανικές μονάδες διαλείπουσας λειτουργίας. Το μαθηματικό μοντέλο, απαρτίζεται από μια σειρά περιορισμών, οι οποίοι σχετίζονται με τη διαθεσιμότητα και τη δυναμικότητα των συσκευών, τα ισοζύγια μάζας των υλικών, την αποθηκευτική δυναμικότητα της βιομηχανικής μονάδας κ.α. Για την επίλυση προβλημάτων μεγάλης κλίμακας, προτάθηκε ένας επαναληπτικός αλγόριθμος, ο οποίος βασίζεται στην τεχνική του κυλιόμενου ορίζοντα (rolling horizon). Παράλληλα, για τη μελέτη της αβεβαιότητας έγινε χρήση των εργαλείων μέτρησης κινδύνου, Value-at-risk (VaR) και Conditional Value-at-Risk (CVaR). Οι προτεινόμενες μαθηματικές τεχνικές εφαρμόστηκαν σε προβλήματα σχεδιασμού και χρονοπρογραμματισμού παραγωγής υπό αβεβαιότητα της ζήτησης, σε βιομηχανικές μονάδες παραγωγής φαρμάκων. Ειδικότερα, μελετήθηκε το πρόβλημα της βέλτιστης επιλογής συμβολαίων για την παραγωγή προϊόντων σε βιομηχανικές μονάδες φαρμάκων, οι οποίες λειτουργούν παράγοντας προϊόντα άλλων εταιρειών με εξωτερική ανάθεση (Contract Manufacturing Organizations). Μελετήθηκαν προβλήματα μεγάλης κλίμακας τα οποία περιλαμβάνουν πολλαπλά στάδια παραγωγής και μεγάλο αριθμό προϊόντων. Από την αξιολόγηση των εξαγόμενων λύσεων, συμπεραίνεται πως τα προτεινόμενα μαθηματικά μοντέλα, σε συνδυασμό με τις στρατηγικές επίλυσης, οδηγούν σε βέλτιστες λύσεις, λαμβάνοντας αποτελεσματικά υπόψιν το υποκείμενο ρίσκο.