Athens University Economics and Business (AUEB)
Scheduling variants in manufacturing and process industries
Abstract
dc:descriptionThis 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.
Degree
thesis:*- Grantor dc:publisher
- Athens University Economics and Business (AUEB)
- Year dc:date
- 2025
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Vatikiotis, Stavros
- Βατικιώτης, Σταύρος
Subjects
dc:subject × 18- Βελτιστοποίηση
- Αλγόριθμοι Χρονοδρομολόγησης
- Μεταευρετικοί αλγόριθμοι
- Optimization
- Scheduling algorithms
- Metaheuristic algorithms
- Μαθηματικά
- Φυσικές Επιστήμες
- Έλεγχος και Βελτιστοποίηση
- Άλλες Επιστήμες Μηχανικού και Τεχνολογίες
- Επιστήμες Μηχανικού και Τεχνολογία
- Μηχανική και Τεχνολογίες, άλλοι τομείς
- Mathematics
- Natural Sciences
- Control and Optimization
- Other Engineering and Technologies
- Engineering and Technology
- Engineering and Technologies, miscellaneous
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/58537