A new mixed-integer programming (MIP) formulation is presented for the production planning of single-stage multi-product processes. The problem is formulated as a multi-item capacitated lot-sizing problem in which (a) multiple items can be produced in each planning period, (b) sequence-independent set-ups can carry over from previous periods, (c) set-ups can cross over planning period boundaries, and (d) set-ups can be longer than one period. The formulation is extended to model time periods of non-uniform length, idle time, parallel units, families of products, backlogged demand, and lost sales.
To remain viable in today's highly competitive economy, chemical firms must use advanced planning methods to optimize their supply chains, from procurement and manufacturing to distribution and sales (Chopey, 2006 and Grossmann, 2005). At the same time, product customization and diversification have led to larger numbers of final products, while the economic environment requires low inventories and higher utilization of existing units (Papageorgiou & Pantelides, 1996; Shobrys & White, 2002). Thus, different products are often produced in multi-product facilities, where limited resources are shared among competing tasks. Therefore, the economic impact of effective production planning methods can be significant. Furthermore, production planning is a hard optimization problem due to its combinatorial nature, and thus academically challenging.
The goal in production planning is to meet customer demand over a fixed time horizon divided into planning periods by optimizing the trade-off between economic objectives such as production cost and customer satisfaction level (Stadtler, 2005). The major decisions are production and inventory levels for each product in each planning period. To address production planning problems, research efforts have tried to adapt solution methods that have been successful for other applications. For some problems, however, the proposed approaches are insufficient because short-term decisions need to be taken into account to obtain good solutions. This can be accomplished by integrating production planning with detailed scheduling models. However, this leads to large optimization problems that are intractable for practical applications. Thus, despite all efforts that have gone into developing methods for the simultaneous production planning and scheduling of chemical plants, this remains a hard optimization problem (Crama, Pochet, & Wera, 2001; Kallrath, 2000; Pinto & Grossmann, 1998; Shapiro, 2004 and Shah, 2005).
In this paper we develop a mixed-integer programming (MIP) formulation for the multi-item capacitated lot-sizing problem for a single processing unit. The proposed formulation overcomes several limitations of previous approaches. Most existing methods assume that if an item is produced in two consecutive periods, then it requires a set-up in each period. Furthermore, set-ups are assumed to begin and finish within the same time period and therefore are required to be shorter than that planning period. In the proposed formulation we relax these assumptions by allowing: (a) set-ups to carry over from previous periods, (b) set-ups to cross over planning period boundaries, and (c) set-ups to be longer than one planning period. By allowing set-ups to carry over, redundant set-ups are not required whenever the last item in a time period is the same as the first item in the following time period. By allowing set-ups to cross over period boundaries, set-ups may begin in one period and finish in a later period, thus better utilizing capacity. By allowing set-ups to be longer than planning periods, we gain the flexibility to discretize the planning horizon into periods of shorter and/or non-uniform length.
This paper is arranged as follows: In Section 2 we describe the production planning problem of interest, we discuss previously proposed methods, and we give the problem statement. In Section 3 we present the assumptions, basic concepts, and properties underlying our approach. In Sections 4 and 5 we present our mathematical formulation. In Section 6 we illustrate the applicability of the proposed approach through four example problems.
This paper presents a MIP model for the capacitated lot-sizing problem with set-up carry over, set-up cross over, and set-up times that may be longer than a planning period. To our knowledge, it is the first to address this generalized problem. Our formulation determines for each time bucket what states are visited, which set-up is begun last, and whether that set-up is completed before the end of the time bucket. Timing is only assigned to set-ups that cross over time bucket boundaries. Since at most one set-up may cross over each time bucket boundary, the number of variables and constraints dedicated to timing is fewer than in fullspace methods based on slots or event points. Thus, the proposed model is computationally efficient and can be used for the solution of practical applications of medium size.
By simultaneously accounting for set-up carry over, set-up cross over, long set-ups, and time buckets of non-uniform length, the proposed formulation can yield solutions that are more efficient than traditional production planning models. Our formulation can be used for the production planning of (a) single-unit processes, (b) processes that can be represented by a single resource capacity (e.g. continuous production lines), (c) processes with a bottleneck unit or stage, and (d) multi-unit, single-stage processes. Furthermore, it can be used as a subproblem in decomposition approaches involving the production planning of structurally complex processes. This is a topic of future research. Finally, we have discussed extensions such as the modeling of idle time variations, parallel units, families of products, backlogging, and lost sales.
