442d

Optimization models for batch scheduling can be classified based on four main aspects: time representation, material balances, event representation and objective function (Méndez et al., Comput. Chem. Eng. 2006, 30, 913). Time representation is probably the most important issue and optimization approaches can be classified into discrete and continuous-time formulations, the latter receiving most of the attention in recent years. In terms of material balances, the handling of batches and batch sizes gives rise to two types of model categories. Those based on unified frameworks for process representation like the STN or RTN can simultaneously deal with the optimal set of batches (number and size), the allocation and sequencing of resources, and the timing of tasks. Alternatively, there are models that assume that the number of batches of each size is known in advance, which can be regarded as one of the approaches for detailed production scheduling, widely used in industry, which decomposes the whole problem in two stages, batching and batch scheduling.

For event representation models can rely on single or multiple, unit specific time grids with a pre-specified number of event points or, alternatively, on immediate or global precedence relationships. When relying on time grids, there is a clear incentive to develop models requiring fewer event points in the hope of making them computationally more efficient. A well known example results from shifting from single to multiple time grid based models. Finally, the objective function selected usually has a direct effect on the computational effort and some functions can be very hard to implement for some event representations.

This paper builds on recent work by the authors (Castro et al., Ind. Eng. Chem. Res. 2006, 45, 6210) who have compared different event representation models for the batch scheduling of multistage batch plants with sequence dependent changeovers. Now, however, instead of considering that the number of batches for the production of a given order is known in advance, we solve the simultaneous batching and scheduling problem for single stage plants. A new RTN-based multiple time grid formulation is proposed that considers the number of batches of a product to produce, as explicit integer variables. It features aggregated tasks that include all the required batches of a particular order, where only one will need to be executed in a particular equipment unit. When compared to the traditional STN/RTN approach that implicitly determines the number of batches by the number of processing tasks that are executed, fewer tasks will be generally needed and since each requires one time interval, fewer event points will be required to achieve global optimal solutions.

In addition to the traditional RTN approach, the new formulation is compared to a continuous-time model with global precedence sequencing variables and to a constraint programming model. A bounding model (Erdirik-Dogan & Grossmann, Optimal Production Planning Models for Parallel Batch Reactors with Sequence-dependent Changeover, to appear in AIChE Journal) using immediate precedence sequencing variables that does not use timing variables and can thus be viewed as a less constrained version of a pure scheduling model is also part of the comparison. Starting with a scenario of total production flexibility that is translated into the ability of producing different batches of the same product in multiple units, the formulations are then simplified to the cased where all batches of a product are produced in the same unit. This study is conducted for the objectives of revenue maximization and makespan minimization.

The performance of the different approaches is evaluated through the solution of 4 example problems ranging from 5 products in 2 units to 10 products in 4 units, with data taken from a real industrial plant. For revenue maximization, each problem is solved for three different values of the time horizon. Overall, a total of 128 computer runs were made. The results have shown that the new formulation is the best performer for the scenario of maximum plant flexibility. The model with immediate precedence sequencing variables is the fastest but while it assumes a single cyclic schedule in each unit (that can be broken) two or more cyclic schedules per unit may result. In such cases, subtour elimination constraints can be added and the problem solved iteratively to find a feasible schedule at the likely expense of removing the global optimal solution from the feasible space. When compared to the traditional approach, the computational effort of the new formulation was typically one order of magnitude lower, which in practice indicates that the new formulation can tackle larger problems.

In terms of studying the effect of considering a less flexible production mode on model simplification, restricting all batches of a product to a single unit allows for a reduction in the number of variables and/or constraints and/or the use of tighter constraints, which make the model simpler and generally faster. The drawback is that worse solutions than those obtained for the more flexible mode may result. It was particularly interesting to find out that the models reacted differently, with the model with global precedence sequencing variables catching up with the new approach for revenue maximization and the constraint programming model overcoming the other two for makespan minimization.

See more of #442 - Planning and Scheduling II (10C15)

See more of Computing and Systems Technology Division

See more of The 2007 Annual Meeting

See more of Computing and Systems Technology Division

See more of The 2007 Annual Meeting