Integration of modeling and solution approaches for flow shop scheduling in the chemical industry
Roderich Wallrath is a PhD student in the Department of Sustainable Process Technology. Promotors are prof.dr.ing. M.B. Franke and prof.dr.ir. E. Zondervan from the Faculty of Science & Technology.
The chemical industry is at the beginning of the production chain and is, therefore, of fundamental importance to the global economy. The optimization of chemical processes has an enormous economic and sustainability impact. Process optimization has always been a key subject in chemical engineering. However, process optimization is difficult, especially for chemical batch processes in the well-known multipurpose or multiproduct flow shop setup. Constraints of chemical plants such as limited secondary resources, intermediate storage, sequence-dependent changeovers, processing recipes, and lot-sizing must be considered, and the production decisions influence each other across several process stages. The goal of finding optimal production schedules is generally an NP-hard problem. Flow shop scheduling has, therefore, attracted many researchers, and new models and solution approaches have been developed over several decades. This thesis proposes new models and solution approaches to improve the accuracy and computational efficiency.
In Chapter 2, a mixed-integer linear programming (MILP) model for hybrid flow shops is developed, utilizing a time-bucket formulation to represent time accurately. This formulation allows the incorporation of various real-world constraints, exemplified through an industrial case study of a make-and-fill plant in agrochemical production. In particular, lot-sizing, changeover times, and personnel resource constraints are modeled relatively simply yet accurately. Computational experiments on randomized instances reveal that the MILP model’s lower bounds are loose. This leads to large reported optimality gaps, although good solutions are already found early in the solution process. The model is applied to a one-month production data set, and a workflow is suggested in which the MILP results are reconciled with a validated, highfidelity discrete-event simulation (DES) model. Compared to an expert-generated production schedule, a 17% reduction in machine hours and an improvement in the on-time delivery of production orders can be achieved.
In Chapter 3, MILP flow shop models with makespan minimization objective are considered. Strengthening inequalities that improve the link between the makespan variable and natural date variables of jobs are derived. The inequalities stem from the mathematical description of a single machine polyhedron. They are implemented for a linear-ordering, time-indexed, and position-based MILP formulation of the nonpermutation flow shop problem. Based on the Taillard benchmark set (Taillard n.d.), it is demonstrated that these inequalities lead to tighter linear programming (LP) relaxations. The lower bounds of the linear-ordering formulation exceed the bestknown bounds in the literature for flow shop sizes up to 50 jobs and five machines or 20 jobs and 20 machines. For the linear-ordering and time-indexed formulation, the inequalities improve the solution speed.
In Chapter 4, MILP and DES are integrated to combine the strengths of rigorous optimization and high-fidelity modeling for flow shop scheduling with makespan minimization objective. This integration can be achieved through Benders decomposition, where the DES model acts as a subproblem, providing detailed, constraint-compliant results. Concurrently, the MILP Benders master problem guides the search process with fewer constraints. Comparative studies on randomized instances show that the Benders-DES algorithm outperforms a genetic algorithm by at least an order of magnitude with respect to solution time and number of DES evaluations. In a real-world hybrid flow shop case study from pharmaceutical production, it performs comparably to the originally suggested constraint programming model.
In Chapter 5, the Benders-DES algorithm is further examined by applying it to the hybrid flow shop with lot-sizing decisions from Chapter 2. Three algorithmic modifications are suggested, and their impact on solution quality and speed is analyzed. A warm-up phase, in which Benders cuts are sampled randomly, improves the initial performance. Smoothening cuts, which cut off fragile solutions, lead to more robust solutions. Re-initialization of the Benders master problem with cuts from previous runs that remain valid leads to faster convergence. Solving the case study presented in Chapter 2 shows that the Benders-DES algorithm is a powerful alternative to traditional simulation-optimization approaches, offering similar performance while requiring less modeling effort.
In Chapter 6, the Benders-DES-algorithm is applied to distributed flow shops. It is assumed that a MILP, DES, and data-driven neural network model exists for the individual flow shop subproblems. Based on literature instances (Naderi and Ruiz n.d.), it is shown that the algorithm can be used to optimize heterogeneous models and report optimality gap information. Despite a remaining optimality gap of more than 29%, the Benders-DES algorithm is a promising concept for integrating preexisting, heterogeneous models in chemical companies.
In conclusion, this thesis advances flow shop models and solution algorithms for process scheduling in the chemical industry. Improvements to MILP models are presented, and a bridge to DES models is built using an integrative Benders-DES algorithm. New workflows and use cases are suggested for the application of these methods.
