To effectively solve production planning problems in the process industry, short-term information such as detailed resource constraints and production cost must be taken into account. There are two broad strategies for integrating short-term information. The first strategy, used widely in the process systems engineering literature, begins with a “fullspace” model that integrates production planning with detailed scheduling. However, integrated models are large-scale mixed-integer programming (MIP) models that are intractable for practical applications. The second strategy begins with a basic production planning model such as the single-item lot-sizing problem or the multi-item capacitated lot-sizing problem, and complex structures are addressed by “superposition” of multiple basic models or by spatial decomposition (Pochet & Wolsey, 2006).

The main idea in the second strategy is to decompose a complex problem into simpler lot-sizing subproblems (LSPs) and use existing algorithms and reformulation results (Wolsey, 1997; Pochet & Wolsey, 2006). A key feature in this approach is that time buckets are more or less independent of each other with the exception of a few linking constraints such as material balance equations, thus providing opportunities for decomposition. Complex LSPs can be decomposed into smaller LSPs for which many decomposition schemes have been developed, including Lagrangean relaxation, column generation, and other methods (Brahimi et al., 2006; Trigeiro et al., 1989). Overall, the natural structure and simplicity of the LSP makes it ideal for decisions over longer time horizons. However, the development of decomposition methods that rely on simple LSPs is an area that has received little attention in the process systems engineering literature.

The goal of this work, is the development of a lot-sizing formulation that can be readily used for the solution of production planning problems in the chemical industry with sequence-independent setup times. To achieve this, we have to account for two features that are typically ignored in “traditional” LSPs: a) long setup times that are common in the production of fine chemicals and biotech products, and b) planning periods of non-uniform length that arise when multiple due/release times and/or parallel units are considered. To model long setups and planning periods of non-uniform length we have to simultaneously account for the following features:

a) Multiple items may be produced in a period.

b) An item does not require setup to be produced in a period if it is the first item in that period and also the last item in the previous period; we will refer to this as setup carry over.

c) A setup may begin in one period and end in a later period; we will refer to this as setup cross over.

d) Setup times may be longer than a time period.

We will refer to this problem as the General Capacitated Lot-Sizing Problem (GCLSP). To our knowledge, this problem has not been addressed in the literature.

In developing the proposed formulation, we derive a number of properties of that allow us to use a smaller number of binary variables. Specifically, we show that the production cost and the total setup time does not depend on the exact ordering of products within each time period, but only on the first and last product in each period. Thus, we do not employ slot-indexed or sequencing binary variables. Further, we show that setup cost and time can be calculated exactly using a reduced number of variables. We also identify a number of conditions that must be satisfied in an optimal solution, and add constraints to enforce these conditions, thus reducing the number of feasible solutions. We also propose a new time representation that enables us to accurately calculate the amount of setup time that crosses over into the next time bucket. Finally, we extend our formulation to account for item-disaggregated idle time, multiple parallel units, families of products, backlogged demand and lost sales.

To illustrate the flexibility and computational efficiency of the proposed formulation we present results for multiple examples. An example with 5 products, planning periods of non-uniform length and setup times that are longer than some planning periods is solved in less than five minutes of wall time. Examples with multiple products and parallel units are solved in less than 10 minutes. Examples with 10-15 products and 16-20 time buckets is solved in approximately 30 minutes. Our results that the GCLSP can be used for the effective solution of complex production planning problems in the chemical industry.

Wolsey, L. A. (1997). MIP modelling of changeovers in production planning and scheduling problems. European Journal of Operational Research, 99, 154-165.

Pochet, Y., & Wolsey, L. A. (2006). Production Planning by Mixed Integer Programming, New York: Springer.

Brahimi, N., Dauzere-Peres, S., Najid, N. M., & Nordli, A. (2006). Single item lot sizing problems. European Journal of Operational Research, 168, 1-16.

Trigeiro, W. W., Thomas, L. J., & McClain, J. O. (1989). Capacitated lot sizing with setup times. Management Science, 35, 353-366.

Extended Abstract Status: Not Uploaded