روشهای دقیق برای مشکل تعیین اندازه دسته تولید ایجاد شده تک آیتمی با ماشین های جایگزین و هزینه های تولید خطی تکه ای و عاقلانه

In this paper, we study a special case of the capacitated lot sizing problem (CLSP), where alternative machines are used for the production of a single-item. The production cost on each machine is assumed to be piece-wise linear with discontinuous steps (step-wise costs). The over-produced finished products can be stored in an unlimited storage space to satisfy future demand. The aim is to achieve optimal production planning without backlogging. This problem can be seen as an integration of production and transportation activities in a multi-plant supply chain structure, where finished goods are sent directly from the plants to the distribution center using capacitated vehicles. For this problem, which we show to be NP-hard, we propose an exact pseudo-polynomial dynamic programming algorithm which makes it NP-hard in the ordinary sense. We also give three mixed integer linear programming (MILP) formulations that we have found in the literature for the simplest case of the CLSP. These formulations are adapted to the multi-machine case with a step-wise cost structure, to which some valid inequalities have been added to improve their efficiency. We then compare the computational time of the dynamic program to that of one MILP which we selected among MILP formulations based on its lower computational time and its lower and upper bound quality.

A special case of the single-item capacitated lot sizing problem (CLSP) is studied in this paper. For the production activity, we consider the use of multiple alternative machines, having different production capacities and different production costs. All the machines can produce the same type of product, respecting a certain batch size. If the quantity to be produced in a period on a machine is not a multiple of a batch, a fractional batch (which is not fully loaded) can be produced. Batch production has been used by Pochet and Wolsey (1993) and by Lippman (1969). The term batch size, which means the maximum number of units that can be produced in a batch, is used by Belvaux and Wolsey (2001). Another feature of this problem is in the structure of the production cost generated by each machine. This cost is assumed to be step-wise (piece-wise linear with discontinuous steps), where each step has a length of the batch size produced in a time period on a specific machine. Even if the batch is not fully loaded (fractional batch), the fixed cost per batch is paid. We denote this problem MMSW-CLSP (multi-machine, step-wise CLSP) in the remainder of this paper. Because of the discontinuous cost structure and the possibility of production on different machines, optimization of this production planning problem becomes more difficult compared to that on a classical CLSP. This problem can be seen as a combined production and transportation planning on a multi-plant supply chain structure. Plants can be interpreted as machines and the batches produced in each period as capacitated vehicles transporting the finished products from the plant to the distribution center (DC). There is no storage space in the plants and all finished goods are sent directly to the DC at the end of a production period. Over-produced finished goods are stored in the DC, which is assumed to be uncapacitated. Customer demand is to be satisfied without backlogging. More detailed information on the studies carried out in integrated supply chain management can be found in the following reviews; Sarmiento and Nagi (1999), Erengüç et al. (1999), and Geunes and Pardalos (2003). There are also many firms trying to integrate the planning decisions of their chain's independently managed activities. For instance, Geunes and Pardalos (2003) gave some examples of firms using optimization tools in their supply chain management to optimize it. This problem has two large domains of application: an alternative machine production environment, where batch production takes place; and in a multi-plant structure with a possible transportation activity using capacitated vehicles. For details of more complex production systems, with multiple lines, multiple items, multiple echelons, etc., Pochet and Wolsey (2006) decomposition of their problem into sub-problems will be of interest. If the hypotheses made and the cost structures assumed for their sub-problems are similar to ours, they will be able to use the methods we propose in this paper. We first present relevant literature on the CLSP, particularly the most interesting surveys. Pochet and Wolsey (2006) provide a comprehensive literature survey, particularly on the mixed integer programming approach to solve extensions of this problem. Another interesting review on the single-item LSP can be found in Brahimi et al. (2006). The survey written by Jans and Degraeve (2008), which focuses on modeling various industrial extensions of single-level dynamic lot sizing problems, is also germain to this discussion. Jans (2006) studied the parallel machine lot sizing problem and proposed new constraints to strengthen the mixed integer linear programming (MILP) formulation. For this problem, which is different from ours, the author uses identical machines with constant capacities and costs, and studies the multi-product case. In the same paper, interesting references on the multi-machine lot sizing problem and its industrial applications can be found. We now provide a detailed literature on LSP with piece-wise costs, which is more related to the problem studied in this paper. To our knowledge, the first study on the integration of the fixed cost per batch into the inventory control policy can be found in Lippman (1969). The author introduced the idea of regeneration intervals, in which a fractional batch can be produced. The production cost is assumed to be concave and step-wise, and some properties of an optimal solution are given. Swoveland (1975) considered single-item production planning, where production and holding/backorder costs are assumed to be piece-wise concave. Optimal schedule properties and a dynamic programming algorithm are given. Li et al. (2004) studied two variants of the dynamic economic lot sizing problem. First, the production is considered as a multiple of a fixed batch size, backlogging is allowed and cost parameters are considered to vary with time. Second, a general form of product order cost is studied. Polynomial time algorithms are given for these two cases. The batch production assumption made by the authors is different from ours, as they only allow a production quantity that is multiple of the batch size. The total demand over the horizon is thus assumed to be a multiple of the batch size, for the purposes of feasible production planning. Shaw and Wagelmans (1998) proposed a pseudo-polynomial dynamic programming algorithm for the single-item CLSP with piece-wise linear cost. For the case with a production cost having only one set-up component, the complexity is OO(View the MathML sourceT2d¯), with TT being the number of periods and View the MathML sourced¯ being the average demand. This is a significant improvement over the dynamic programming algorithm proposed by Florian et al. (1980) with a complexity in OO(View the MathML sourceT2P¯d¯), where View the MathML sourceP¯ is the average production capacity. There are also studies on the mixed integer linear programming approach to solve the piece-wise linear cost LSP, as a variant of supply chain planning problems. Diaby and Martel (1993) studied a multi-echelon distribution system to determine optimal purchasing and shipping quantities. They assumed a general piece-wise linear ordering cost and linear holding costs. They formulated the problem as an MILP, and use a Lagrangean relaxation to solve it. Chan et al. (2002) studied a special class of the piece-wise linear ordering cost LSP. This function arises with transportation performed with less-than-truckload carriers. They showed that the problem is NP-hard, and construct the best zero inventory ordering policy. Pochet and Wolsey (1993) proposed extended formulations for the constant batch production problem. A fractional production is also possible if the quantity produced is not a multiple of the constant batch size. They study the cases where matrices are totally unimodular: the production capacity is first assumed to be constant and a set-up cost is paid for a positive amount produced; second, the production capacity is assumed to be a multiple of some batch size, and a fixed cost is generated for each batch produced. Akbalik and Pochet (2009) studied a single-machine version of the problem studied in this paper, using similar assumptions on the capacity and cost configurations. Unlike our approach here, in which we propose pseudo-polynomial time dynamic programming algorithm, Akbalik and Pochet (2009) used the polyhedral approach to solve the MILP associated with a single-machine step-wise CLSP. They introduced a new class of valid inequalities for this case. In this paper, we give three MILP formulations to solve the MMSW-CLSP. These formulations are adapted from the literature of the single-item CLSP. For some instances, the execution time for finding the optimal solution using these formulations can be extensive, and so we propose an efficient way of computing optimal production quantities using a two-step pseudo-polynomial dynamic program. This paper is organized as follows. In Section 2, a detailed description of the problem is given, including all the hypotheses made. Three different mixed integer linear programming formulations are given for the MMSW-CLSP, followed by a complexity result of the problem. In Section 3, a pseudo-polynomial dynamic programming algorithm is given. Some computational experiments are reported in Section 4, and, finally, some concluding remarks are made in Section 5.

The problem we have studied in this paper can be seen as a generalization of the single-item CLSP with a more complicated capacity and cost structure due to machine-dependent capacity limitation and piece-wise cost structure on each machine. The problem consists of finding an optimal production planning strategy while minimizing production and storage costs. The same problem can also be interpreted as an integrated production and transportation planning problem in a multi-plant system without lead-times, where finished products are sent directly from the plants to the distribution center using capacitated vehicles. We have provided a proof of NP-hardness to show that the decision problem associated with the MMSW-CLSP optimization problem with only one period is NP-complete. We have also given a reference from the literature to show that the MMSW-CLSP optimization problem with only one machine is NP-hard. Unlike classical CLSP, a difficulty arises in computing total production and holding costs, which consists in assigning some feasible production quantity to a finite number of machines, in each period. For this computation, we found a pseudo-polynomial dynamic programming algorithm that can be computed independently from the rest of the general algorithm. The general algorithm itself decodes the optimal production quantity and the storage level in each time period. Different ways of computing this general algorithm can be found in the literature of the single-item CLSP, which is also formulated by a pseudo-polynomial dynamic program. So, for the total cost computation in the entire chain, there exists a pseudo-polynomial time dynamic program which consists of two independent algorithms. The complexity of MMSW-CLSP is thus NP-hard, but only in the ordinary sense. We formulated the same problem by mixed integer linear programs. We found three MILP formulations in the CLSP literature, which we adapted to MMSW-CLSP. We implemented them using a standard solver Cplex and tested under different cost and capacity configurations, in order to choose the most efficient in terms of execution time. To compare efficiency, we looked at their Gap values after 1 min, with the addition of aggressive cuts from the Cplex solver, some valid inequalities, and both of these. We also compared the linear relaxation and the best integer values found at the top node. We then compared the execution time of the most efficient MILP, which was AGG with the addition of valid inequalities and aggressive cuts, to that of the dynamic program. We gave instances where each method is more efficient. The execution time of MILPs is quite unpredictable and can be influenced by all the problem parameters. However, for some specific instances, we could observe similar values, and interpreted these values by grouping them in the tables. One can easily predict the execution time of the dynamic programming algorithm looking at its complexity. In particular, when production capacities are small to medium sized and cost configurations are hard for MILPs (i.e. Cost1 or Cost5), use of the dynamic programming algorithm can be highly advantageous, mainly because DP does not depend on cost configurations. However, for larger instances (large production capacities, a large number of periods and machines), the dynamic programming algorithm can take longer and even return memory errors. The influence of different parameters on these methods can be found in Section 4. The perspectives that can be considered are the following: an attempt can be made to reduce MILP execution time, using the various extended formulations or valid inequalities proposed by Pochet and Wolsey (2006) for some extensions of the lot sizing problem. Better formulations may be found by exploring the problem structure. Also, dynamic program recursion may be improved with new dominance rules related to the problem. For the general part, to our knowledge it is difficult to find any efficient optimality properties because of the complicated cost structures involved. However, for the multi-machine production assignment part, it is certainly possible to have some dominance properties for the production assignment on the machines. For instance, if the fixed cost per batch and the unit production cost of a machine are higher than those of the second machine, the decision not to produce on the second machine directly implies the non-production on the first. In this current version of the paper, we did not present any dominance properties to make it possible to reduce the complexity of the dynamic programming algorithm. This constitutes a perspective for future research.