نتایج چند وجهی برای فرمولاسیون MIP برنامه ریزی تولید زمان گسسته برای فرآیندهای پیوسته

We derive polyhedral results for discrete-time mixed-integer programming (MIP) formulations for the production planning of multi-stage continuous chemical processes. We express the feasible region of the LP-relaxation as the intersection of two sets. The constraints describing the first set yield the convex hull of its integer points. For the second set, we show that for integral data the constraint matrix is κ-regular, and that the corresponding polyhedron is integral if the length of the planning period is selected appropriately. We use this result to show that for rational data, integer variables can also assume integral values at the vertices of the polyhedron. We also discuss how these results provide insight and can be used to effectively address large-scale problems. Finally, we present computational results for a series of example problems.

The scheduling and production planning of multi-product facilities has received considerable attention in the process systems engineering (PSE) literature (Shah, 2005, Mendez et al., 2006, Sung and Maravelias, 2007 and Maravelias and Sung, 2009). The focus of most of the existing approaches is on the development of mixed-integer programming (MIP) formulations that are shown to solve well a class of problems. The quality of such MIP formulations is typically assessed from the computational requirements for the solution of a set of example problems. In general, it can be argued that the development of MIP models for the scheduling of chemical processes has been guided by empirical (computational) rather than theoretical results. This is in sharp contrast with efforts on production planning in the operations research (OR) community, where the development of reformulations and the derivation of theoretical results with respect to the structure and tightness of MIP formulations is the method of choice (Pochet & Wolsey, 2006). The advantage of this more rigorous approach is that these results and reformulations point the way to effective decomposition approaches. In this paper we follow the latter approach. We study the polyhedral properties of a discrete-time state-task network (STN) formulation (Kondili, Pantelides, & Sargent, 1993) for the production planning of multi-stage multi-product continuous processes. We decompose the problem into two subproblems and develop results regarding the tightness of the two subproblems. The central results concern the length of the time period: we determine the length that yields the tightest possible MIP formulation for the second subproblem. The paper is structured as follows. In the next section we review concepts and known results on polyhedral theory, total unimodularity, κ-regularity, and decomposition approaches. In Section 3, we formally define the production planning problem we consider in this paper, and present three MIP formulations. We then decompose the proposed formulation into two subproblems and develop polyhedral results for their LP-relaxations. In Section 5, we present a geometric illustration of our results and we discuss how they can be used to solve practical problems. Finally, in Section 6 we present computational results for a series of example problems.

We have studied discrete-time MIP formulations for the production planning of continuous chemical processes. We derived a number of theoretical results regarding the polyhedra defined by the LP-relaxation of two subsets of constraints. We showed that the selection of the length Δt of the time period leads to the κ-regularity of the constraint matrix of one subset of constraints and the integrality of the corresponding polytope. We also discussed how the proposed theoretical results can be used to effectively address practical applications. Finally, we studied the formulations of several example problems and showed that the selection of Δt has a profound effect on the tightness of the MIP formulation, and therefore the computational performance of the model.