تجزیه لاگرانژ زمانی و مکانی در تولید مشکلات برنامه ریزی چنددوره ای چندسایتی با تغییرات وابسته به توالیتجزیه لاگرانژ زمانی و مکانی در تولید چند سایت، چند دوره برنامه ریزی مشکلات با تغییرات وابسته به توالی

We address in this paper the optimization of a multi-site, multi-period, and multi-product planning problem with sequence-dependent changeovers, which is modeled as a mixed-integer linear programming (MILP) problem. Industrial instances of this problem require the planning of a number of production and distribution sites over a time span of several months. Temporal and spatial Lagrangean decomposition schemes can be useful for solving these types of large-scale production planning problems. In this paper we present a theoretical result on the relative size of the duality gap of the two decomposition alternatives. We also propose a methodology for exploiting the economic interpretation of the Lagrange multipliers to speed the convergence of numerical algorithms for solving the temporal and spatial Lagrangean duals. The proposed methods are applied to the multi-site multi-period planning problem in order to illustrate their computational effectiveness.

The optimal planning of a network of manufacturing sites and markets is a complex problem. It involves assigning which products to manufacture in each site, how much to ship to each market and how much to keep in inventory to satisfy future demand. Each site has different production capacities and operating costs, while demand for products varies significantly across markets. Production and distribution planning is concerned with mid to long-term decisions usually involving several months, adding a temporal dimension to the spatial distribution given by the multi-site network. The production of each product can involve a setup or cleaning time that in some cases is sequence-dependent. When setups and sequence-dependent transitions are included, the optimal planning problem becomes a mixed-integer linear programming (MILP) problem. The computational expense of solving large-scale MILP problems can be decreased by using decomposition techniques. This paper presents temporal and spatial Lagrangean decompositions that allow the independent solution of time periods, production sites, and markets. The importance of choosing between alternative Lagrangean relaxations of the same planning model is discussed by Gupta and Maranas (1999). Jackson and Grossmann (2003) use temporal decomposition for solving a multi-site, multi-period planning problem. They report that temporal decomposition provides a tighter bound on the full space solution and has faster dual convergence than spatial decomposition. Wu and Ierapetritou (2006) also implement Lagrangaen decomposition on a multi-period scheduling problem. These authors propose to use the Nelder–Mead approach as an alternative to subgradient method for updating the multipliers. Temporal decomposition using this approach results in a significant reduction in computational time. Neiro and Pinto (2006) use temporal Lagrangean decomposition to solve a multi-period MINLP planning problem under uncertainty concerning a petroleum refinery. They find that this decomposition scheme helps overcome the exponential increase in solution time that occurs with the full space model. In a problem similar to the one presented in this paper, Chen and Pinto (2008) use Lagrangean-based decomposition techniques for solving the temporal decomposition of a continuous flexible process network. They use subgradient methods to solve the decomposed problem and find that temporal decomposition strategies result in a reduction of computational time of several orders of magnitude. From the papers mentioned above, it is evident that temporal decomposition is an efficient solution approach for multi-period planning problems. It has been found to provide a tighter bound on the optimal solution and to have better convergence properties than Lagrangean spatial decomposition in multi-site problems. However, there is no rigorous proof and generalization of the observed result. One objective of this paper is to compare the bounds obtained through Lagrangean temporal and spatial decompositions for a class of MILP problems derived from the lot-sizing problem with setup and sequence-dependent changeover times (Pochet & Wolsey, 2006). The second objective is to use the economic interpretation of the Lagrange multipliers to provide a reduced dual search space and accelerate the convergence of the optimal multipliers. This paper is organized as follows. Section 2 presents the details of the MILP formulation for the production planning problem. Section 3 describes the implementation of temporal and spatial decomposition of the MILP problem in Section 2. In Section 4 we review some important theoretical concepts and in Section 5 we introduce a result where the dual gap of temporal decomposition is found to be at least as small as the dual gap for spatial decomposition. Sections 6 and 7 contain our novel approach for exploiting the economic interpretation of the Lagrange multipliers to reduce the search space for the optimal multipliers. Section 8 presents four numerical examples of increasing size and complexity for the multi-site multi-period planning problem where the theoretical result is confirmed, and where the economic interpretation of the multipliers is used to speed the convergence of numerical algorithms for solving the decomposed problem. Finally, Section 9 presents our conclusions and ideas for future work.

We have presented a theoretical result that explains the observation made in previous works that temporal decomposition provides tighter bounds than spatial decomposition in some types of production planning problems. We have presented the theoretical result in the context of a multi-site, multi-period, multi-product planning problem with sequence-dependent changeovers. The changeovers that we considered are modeled using sequencing constraints that yield a mixed-integer linear programming (MILP) problem. Our result indicates that the optimal duality gap in temporal decomposition will always be at least as small as the one obtained using spatial decomposition. In the second part of this paper we have proposed a method to obtain bounds on the optimal value of the Lagrange multipliers of temporal and spatial decomposition. The technique is based on an economic interpretation of the Lagrange multipliers from duality theory. We have presented numerical results for four examples. The first two are used to give some numerical evidence that the optimal solution of the temporal dual is at least as tight as in the spatial dual. The cutting plane algorithm was used to solve these two examples. Applying the economic bounds on the multipliers speeds the convergence of this algorithm, particularly when solving the spatial dual. The third and fourth examples consist of larger planning problems and were solved using the subgradient method. The results indicate that the decomposition strategies are efficient for larger problems, and that the bound provided by temporal decomposition was confirmed to be tighter than the bound from spatial decomposition. The economic bounds enhanced the convergence of spatial decomposition in larger problems with loose initial bounds.