Scheduling variants in manufacturing and process industries

Abstract

This thesis investigates the design and application of combinatorial optimization techniques to complex scheduling and process industry problems. Conventional optimization models often face difficulties when integrating multiple real-world-inspired properties. To address the arising issues, we propose hybrid methods that, while not guaranteeing optimality, are efficient in tackling large-scale, complex, and practically relevant problems. These hybrid approaches combine elements from various optimization techniques, including exact methods such as Mixed-Integer Linear Programming (MILP) and Constraint Programming (CP), as well as metaheuristic algorithms like Genetic Algorithms (GA), Simulated Annealing (SA), and Local Search (LS), among others. We begin by addressing the Unrelated Parallel Machine Scheduling Problem (UPMS) with sequence-dependent and machine-dependent setup times, as well as a renewable resource constraint on simultaneous setups. In contrast to the traditional makespan objective, we focus on minimizing the total weighted tardiness, providing a practical framework for real-world applications. The proposed approach combines MILP, GA, SA, and CP to effectively handle the complexity of the problem. Our extensive experimentation demonstrates the efficiency of this framework on large-scale instances, incorporating both benchmark and real-world data. Additionally, to better capture the dynamics of real-world manufacturing environments, we explore parallel manufacturing processes across multiple stages. Specifically, we examine the Hybrid Flexible Flowshop Scheduling Problem (HFFS), where jobs must be scheduled over multiple stages with parallel machines and stage-skipping flexibility. Critical real-world factors, such as machine-dependent transportation times and limited capacity buffers, are also considered. Due to the problem's inherent complexity, this thesis develops and evaluates five metaheuristic approaches — GA, SA, Particle Swarm Optimization (PSO), LS, and Tabu Search (TS) —, coupled with a CP component, to assess their efficiency and solution quality on large-scale instances, consisting of over 300 jobs and 9 stages. The results provide valuable insights into the comparative performance of these methods and suggest potential hybridization strategies for improving results. In addition to scheduling optimization, we emphasize the critical need to manage residual by-products, such as wastewater, generated by industrial processes, and focus on the efficient management of water resources. To tackle these challenges, we approach the problem from a network perspective and propose a novel Mixed-Integer Non-Linear Program (MINLP), which is then both linearized into a MILP formulation and transformed into a CP formulation. The experimental instances are sourced from leading organizations in the field, ensuring a strong connection to real-world applications. Obtained results validate the overall efficiency of our framework in terms of optimality gap and computational time and show its applicability across various industries and offering a versatile solution to real-world challenges. The thesis concludes by outlining potential future research directions. First, the emphasis is placed on both scheduling problems presented: the UPMS and HFFS. For the UPMS, we highlight the need to explore job splitting strategies for both population-based and search-based algorithms to improve scheduling efficiency and flexibility. Towards a similar direction, we, also, provide dominance rules on the tardiness minimization problem, which may assist in avoiding visiting provably inferior solutions. For the HFFS, we provide ideas for hybridizing exact methods - MILP and CP -, aiming to enhance optimization performance and tackle these complex scheduling challenges more effectively.

Η παρούσα διατριβή εξετάζει το σχεδιασμό και την εφαρμογή τεχνικών συνδυαστικής βελτιστοποίησης σε σύνθετα προβλήματα χρονοδρομολόγησης (scheduling) και της βιομηχανίας επεξεργασίας (process industries). Τα παραδοσιακά μοντέλα βελτιστοποίησης συχνά αντιμετωπίζουν δυσκολίες κατά την ενσωμάτωση πολλών ιδιοτήτων που προέρχονται από τον πραγματικό κόσμο. Για την αντιμετώπιση αυτού του ζητήματος, προτείνονται ευέλικτες μέθοδοι, οι οποίες παρόλο που δεν εγγυώνται την βελτιστότητα, προσφέρουν υψηλή αποδοτικότητα στην αντιμετώπιση μεγάλων, σύνθετων και πρακτικά κρίσιμων προβλημάτων. Αυτές οι υβριδικές προσεγγίσεις συνδυάζουν στοιχεία από διάφορες τεχνικές βελτιστοποίησης: ακριβείς μεθόδους όπως ο Μικτός Ακέραιος Γραμμικός Προγραμματισμός (MILP) και ο Προγραμματισμός Περιορισμών (CP), καθώς και μεθευρετικούς αλγορίθμους, όπως οι Γενετικοί Αλγόριθμοι (GA), η Προσομοιώμενη Ανόπτηση (SA) και η Τοπική Αναζήτηση (LS), μεταξύ άλλων. Αρχικά, αναλύεται το πρόβλημα Χρονοδρομολόγησης Ασυσχέτιστων Παράλληλων Μηχανών (UPMS) με εξαρτώμενους από την ακολουθία και την μηχανή χρόνους προετοιμασίας (setup times), καθώς και περιορισμένους ανανεώσιμους πόρους. Αντί για τον απλότερο στόχο ελαχιστοποίησης της μέγιστης συνολικής διάρκειας (makespan), εστιάζουμε στη μείωση της συνολικής σταθμισμένης καθυστέρησης (total weighted tardiness), παρέχοντας ένα πρακτικό πλαίσιο για εφαρμογές στον πραγματικό κόσμο. Η προτεινόμενη προσέγγιση συνδυάζει MILP, GA, SA και CP για να διαχειριστεί αποτελεσματικά την πολυπλοκότητα του προβλήματος. Η εκτενής πειραματική διαδικασία υπογραμμίζει την αποδοτικότητα του σχεδιασθέντος πλαισίου σε μεγάλα στιγμιότυπα, ενσωματώνοντας τόσο δεδομένα αναφοράς (benchmark data) όσο και πραγματικά δεδομένα. Επιπλέον, για να αποτυπωθεί ακριβέστερα η δυναμική των πραγματικών περιβαλλόντων παραγωγής, εξετάζονται παράλληλες διαδικασίες παραγωγής σε πολλαπλά στάδια. Συγκεκριμένα, εξετάζεται το Πρόβλημα Υβριδικής Ευέλικτης Χρονοδρομολόγησης (HFFS), όπου ένα σύνολο εργασιών πρέπει να προγραμματιστεί σε διαφορετικά στάδια αποτελούμενα από παράλληλες μηχανές και τη δυνατότητα παράκαμψης σταδίων. Κρίσιμες ιδιότητες εμπνευσμένες από πραγματικά περιβάλλοντα, περιλαμβάνουν τους χρόνους μεταφοράς και την περιορισμένη χωρητικότητα των αποθηκευτικών χώρων στις μηχανές. Λόγω της σημαντικής πολυπλοκότητας του προβλήματος, η διατριβή αναπτύσσει και αξιολογεί πέντε μεθευρετικούς αλγορίθμους —GA, SA, Βελτιστοποίηση Σμήνους Σωματιδίων (PSO), LS και Αναζήτηση Tabu (TS) — συνδυαζόμενες με ένα στοιχείο CP, ώστε να αξιολογηθεί η αποδοτικότητά τους και η ποιότητα των λύσεων σε μεγάλα στιγμιότυπα που περιλαμβάνουν πάνω από 300 εργασίες και 9 στάδια. Τα αποτελέσματα προσφέρουν πολύτιμες πληροφορίες για τη συγκριτική απόδοση αυτών των μεθόδων και προτείνουν στρατηγικές υβριδοποίησης για τη βελτίωση των αποτελεσμάτων. Εκτός από τη βελτιστοποίηση της χρονοδρομολόγησης, τονίζεται η κρισιμότητα της διαχείρισης των υπολειπόμενων παραπροϊόντων, όπως τα απόβλητα, που παράγονται από βιομηχανικές διαδικασίες, αλλά και η αποτελεσματική διαχείριση των υδάτινων πόρων. Για την αντιμετώπιση αυτών των προκλήσεων, προσεγγίζεται το πρόβλημα από την σκοπιά του δικτύου και σχεδιάζεται ένα καινοτόμο Μικτό-Ακεραίο Μη Γραμμικό Πρόγραμμα (MINLP), το οποίο στη συνέχεια γραμμικοποιείται σε MILP, αλλά και μετασχη ματίζεται σε ένα μοντέλο CP. Τα πειραματικά δεδομένα προέρχονται από κορυφαίους οργανισμούς στον τομέα, διασφαλίζοντας την ισχυρή σύνδεση με τις εφαρμογές στον πραγματικό κόσμο. Τα αποτελέσματα καταδεικνύουν τη συνολική αποδοτικότητα της μεθόδου και ενθαρρύνουν την εφαρμοσιμότητά της σε διαφορετικές βιομηχανίες, προσφέροντας ένα ευέλικτο πλαίσιο για τις προκλήσεις του πραγματικού κόσμου. Η διατριβή ολοκληρώνεται παραθέτοντας πιθανές μελλοντικές ερευνητικές οδούς. Αρχικά, δίνεται έμφαση και στα δύο προβλήματα χρονοδρομολόγησης που παρουσιάστηκαν: το UPMS και το HFFS. Για το UPMS, τονίζεται η ανάγκη για εξερεύνηση στρατηγικών καταμερισμού εργασιών (job splitting) τόσο για πληθυσμιακές μεθόδους όσο και για αλγορίθμους αναζήτησης, με σκοπό τη βελτίωση της αποδοτικότητας και ευελιξίας του προγράμματος. Προς την ίδια κατεύθυνση, παρέχονται επίσης κανόνες κυριαρχίας (dominance rules) για το πρόβλημα της ελαχιστοποίησης της καθυστέρησης, οι οποίοι δύνανται να βοηθήσουν στην αποφυγή εξέτασης αποδεδειγμένα κατώτερων λύσεων. Για το HFFS, προτείνονται ιδέες για υβριδισμό ακριβών μεθόδων – MILP και CP – με στόχο την αύξηση της απόδοσης βελτιστοποίησης και την αποτελεσματικότερη αντιμετώπιση αυτών των σύνθετων προκλήσεων.