(61c) Improving the Integrality Gap Using a Novel Continuous-Time Scheduling Formulation Applied to a Challenging Industrial Benchmark Problem

The problem of short-term scheduling for multiproduct/multipurpose batch plants has received a considerable amount of attention during the last two decades. The purpose of scheduling is to determine the most efficient way to produce a set of desired products in a certain amount of time given a set of limited resources, some processing equipment, and processing recipes. The tasks to be scheduled usually take place in multiproduct and multipurpose batch plants, in which a wide variety of different products can be manufactured via the same recipe or different recipes by sharing limited resources, such as equipment, material, time, and utilities. These process scheduling problems are inherently combinatorial in nature due to the many discrete decisions involved, such as equipment assignment and task allocation over time. Given the computational complexity arising from the combinatorial nature of process scheduling problems, it is of crucial importance to develop effective mathematical formulations to model the manufacturing processes and to explore efficient solution approaches for such problems. Mixed Integer Linear Programming (MILP), because of its rigor, flexibility and extensive modeling capability, has become one of the most widely explored methods for process scheduling problems. Applications of MILP-based scheduling methods range from the simplest single-stage, single-unit multiproduct processes to the most general multipurpose processes [2,3].

In this work, a novel mathematical framework is proposed for the efficient reduction of the integrality gap in short-term scheduling problems for multipurpose and multiproduct batch plants. A number of preprocessing steps are performed and used along with a unit-specific event-based continuous-time formulation for short-term scheduling including several new, tightening constraints. The mathematical framework is applied to a challenging benchmark problem in batch process scheduling, originally proposed by [1] with additional results found in [9]. This batch process involves several complicating features in flow structure, operational flexibility, as well as finite intermediate storage restrictions. A variation of the problem is studied using the full set of inventory, with the objective of minimizing the makespan. We apply the continuous-time formulation proposed by Floudas and coworkers [3]-[8] and further explore the special structures of the problem. Several problem instances are investigated, each with a different demand structure, and the computational results demonstrate the effectiveness of the proposed formulation.

[1]- H. Westenberger and J. Kallrath. "Formulation of a Job Shop Problem in Process Industry." Working paper, Bayer AG, Leverkusen and BASF AG, Ludwigshafen, Germany, 1994. [2]- C.A. Floudas and X. Lin. "Mixed Integer Linear Programming in Process Scheduling: Modeling, Algorithms, and Applications." Ann. Oper. Res. 139 (2005): 131-162. [3]- C.A. Floudas and X. Lin. "Continuous-Time versus Discrete-Time Approaches for Scheduling of Chemical Processes: A Review." Comput. Chem. Engng. 28 (2004): 2109-2129. [4]- M.G. Ierapetritou and C.A. Floudas. "Effective Continuous-Time Formulation for Short-Term Scheduling: 1. Multipurpose Batch Processes." Ind. Eng. Chem. Res. 37 (1998): 4341-4359. [5]- M.G. Ierapetritou and C.A. Floudas. "Effective Continuous-Time Formulation for Short-Term Scheduling: 2. Continuous and Semi-continuous Processes." Ind. Eng. Chem. Res. 37 (1998): 4360-4374. [6]- M.G. Ierapetritou, T.S. Hene, and C.A. Floudas. "Effective Continuous-Time Formulation for Short-Term Scheduling: 3. Multiple Intermediate Due Dates." Ind. Eng. Chem. Res. 38 (1999): 3446-3461. [7]- X. Lin and C.A. Floudas. "Design, Synthesis and Scheduling of Multipurpose Batch Plants via an Effective Continuous-Time Formulation." Comput. Chem. Engng. 25 (2001): 665-674. [8]- S.L. Janak, X. Lin, and C.A. Floudas. "Enhanced Continuous-Time Unit-Specific Event Based Formulation for Short-Term Scheduling of Multipurpose Batch Processes: Resource Constraints and Mixed Storage Policies." Ind. Eng. Chem. Res. 43 (2004): 2516-2533. [9]- S. Wang and M. Guignard. "Redefining Event Variables for Efficient Modelling of Continuous-Time Batch Processes." Ann. Oper. Res. 116 (2002): 113-126.