مشکل تعیین اندازه دسته تولید پویا با هزینه تولید مارکووی زمان پیوسته

This paper develops a polynomial algorithm for obtaining dynamic economic lot sizes in a single product multiperiod production system with the objective of minimizing total production and inventory costs over T periods. It is assumed that production costs are linear, inventory costs are concave, setup costs are zero and backlogging is not permitted in all periods. Moreover, the unit production cost is a stochastic variable, which is evolved according to a continuous-time Markov process over the planning horizon. The model is formulated as a stochastic dynamic programming (DP) optimization with the state variable being unit production cost. Then, it is solved using the backward dynamic programming approach. To justify the application of the proposed model, two practical cases are presented.

The classical dynamic lot sizing problem specifies a discrete-time finite horizon single product inventory management problem subject to deterministic time-varying demand that must be satisfied. This problem has been the subject of extensive research since its introduction in the late 1950s until today. When the production cost and the inventory cost of each period are linear, several authors have presented theorems that can reduce the computational effort required in solving the problem. Wagner and Whitin (1958) and Zabel (1964) give results for the no-backlogging case, while Zangwill (1969) analyzes the backlog case. Many generalizations of the basic model have been considered including introducing bounds on inventory and/or production capacity, as well as generalizations to multiproduct settings. Brahimi et al. (2006), Karimi et al. (2003) and Maes and Wassenhove (1998) provide excellent reviews about single item lot sizing, multiproduct capacitated lot sizing and multi item single level capacitated dynamic lot sizing problems, respectively. In the last decade, three important papers, Aggarwal and Park (1993), Federgruen and Tzur (1991) and Wagelmans et al. (1992) improved the time complexity for obtaining an optimal solution from O(T2) to O(T log T), if T represents the length of the planning horizon. The existing materials in the area of stochastic lot sizing consider mainly demand as the uncertain parameter. Silver (1978) applies a heuristic to compute the actual lot size as the solution of a newsvendor problem. Bookbinder and Tan (1988) convert the stochastic problem to an equivalent deterministic problem that has the same form as the deterministic dynamic lot sizing problem. Sox (1997) developed an optimal algorithm for the single item dynamic lot sizing problem with random demand and non-stationary costs. Melo (1996) provides an excellent review about the stochastic lot sizing in production planning. Sox et al. (1999) survey the most current research literature on the stochastic lot scheduling problem, which deals with scheduling production of multiple products with stochastic demand. Recently, Haugen et al. (2001) used a meta-heuristic to solve stochastic lot sizing problems. This paper develops a polynomial algorithm for obtaining the optimal production scheduled for each period in single product multiperiod production systems with stochastic production (or purchasing) costs. The productions (purchases) must be made in markets characterized by significant cost (price) fluctuations. There is no assurance that the price tomorrow will be the same as that today. Examples of such commodities are rubber, sugar, copper, coffee and cereals. When the price is low the purchasing officer would like to buy to build up his stocks to meet at least part of the requirements for the periods when the price is high. When the price is high he will avoid purchasing and use his stocks to meet his current needs. Published paper in the field of stochastic price illustrating the use of operational research techniques is rare, see Kingsman (1986). To our knowledge, only Fabian et al. (1959) and Kingsman (1969) considered this type of problem, but in both of their studies prices in successive periods are independent, which is a restrictive assumption in many practical cases. In this study, we assume that the unit production cost (price) is a stochastic variable, which is evolved according to a continuous-time Markov process over the time horizon. So, the actual price in each period will be dependent on the price in the previous period. This assumption is different compared with the ones in Fabian et al. (1959), Kingsman (1969). Such an assumption also reflects better the price movement in practice and it is the main contribution of this paper. To justify the application of the proposed model, two practical cases are presented below. In both, the price is varying over the time horizon and in each period its change depends on the price in the previous period. First, consider the problem of purchasing oil by governments, according to the variations of oil price over the planning horizon. In this regard, oil price can be considered as low, medium and high levels or even more accurately in several levels. The length of planning horizon is dependent on the political situation of each country (normally 4 years). Clearly, the duration of time that the oil price remains at its present level, before proceeding to the next level, is not constant, rather it would be a random variable and can be considered to follow an exponential distribution. The government purchases oil in discrete points during the planning horizon. Moreover, if it seems that the price of oil, in any period, is relatively inexpensive, it might be a good decision to purchase oil in a high volume and store it for the next periods needs. To model this problem and to obtain the economic oil ordering size (number of million gallons) per period (possibly year), oil price can be supposed to evolve according to a proper continuous-time Markov process. In order to properly estimate the transition probabilities (we explain more about this in Section 2), we ignore the transitions of the oil price inside each level and only consider the transitions of the oil price from each level to other levels in this particular problem. In this regard, it is reasonable to assume that after remaining the oil price at any level for some time, which is stochastic, it will eventually transit to one of the other levels. In this problem, a transition matrix with zero diagonal elements can properly reflect the dynamic nature of oil price during the planning horizon. As long as we decrease the range of levels, the accuracy of the proposed model will be increased. Another important application arises in Iran where the unit production costs are influenced by the government which frequently fixes costs of basic raw materials. The cabinet, one or two times per year, decides about fixing the unit costs for a number of strategic raw materials like steel, wood, petroleum, etc., according to inflation in the country which is always upward. In this regard, the cabinet submits the corresponding bill to the parliament and the parliament's decision on fixing the unit costs or increasing them to one of the proposed unit costs, based on the cabinet's bill and the inflation rate, is final. Increasing the raw materials’ costs clearly increases the unit production costs, because for producing each product, the producer needs to purchase some related raw materials from the government and then makes the final product. Moreover, the duration of time that the raw materials’ costs remain at their present positions, before changing to some new positions, is not constant, rather it depends on the time interval for deciding about changing the raw materials’ costs by the government (the cabinet and the parliament). To model this problem in order to obtain the economic lot size in single product multiperiod production systems, the unit production cost can be supposed to evolve according to a proper continuous-time Markov process. When the state variables (values of the unit production cost) are sorted from the smallest to the largest one, an upper triangular transition matrix with a single absorbing state can properly reflect the dynamic nature of the unit production cost and its dependency on the government's decision in this particular problem in Iran. What makes a continuous-time Markov chain different from a Markov chain is that the amount of time it spends in each state, before proceeding to the next state, is exponentially distributed, instead of a constant deterministic value. In both practical cases, the amount of time to spend in each state is clearly a random variable. The cost (price) in each period is also dependent on the cost in the previous period. If the process of evolving the cost coefficient over the time horizon is memoryless, then it is possible to model the cost changes occurring at any time over the planning horizon including the beginning of each period, when the decisions about the economic lot sizes are actually made, and to derive the proper stochastic dynamic programming recursive functions. The only distribution which poses the memoryless property is exponential. Therefore, the above mentioned problems and many similar ones in production and business can be best modeled by continuous-time Markov processes. We think the memoryless assumption is quite reasonable. All price information in early periods is included in the last period, from which the current price will departure. Finally, the model is formulated as a stochastic DP optimization with the state variable being unit production cost, and the corresponding DP functional equation is derived. Then, it is solved in the backward DP way. We also discuss about the complexity of the proposed algorithm to solve the problem.

In this paper, we proposed a polynomial algorithm based on semi-Markovian decision processes to solve the dynamic lot sizing problem, in which the production and the inventory costs of each period are concave, and the unit production cost evolves according to a continuous-time Markov process over the planning horizon. As explained, we need to consider continues-time Markov process in our analysis, because we need the memoryless property of evolving the unit production cost over the time horizon to derive the DP functional Eq. (8). The main computational difficulty of the proposed algorithm is to compute φim(Δt)φim(Δt) by the inverse Laplace transformation in Eq. (4). The usual method for solving such equations is to approximate them by a discrete-time analog or determine the inverse Laplace transform numerically, in moderately large problems. Apart from the two cases mentioned in Section 1, this model can be applied in many practical production and business cases for instance in global supply chains. Due to the comparative advantages of different countries, nowadays firms are developing manufacturing and sourcing strategies in a global supply chain. Material purchasing, manufacturing and market often locate in different regions. One challenge is then to deal with financial risk. Firms have an impressing need to take into consideration of price and exchange rate fluctuation in production systems. The proposed model can be easily used to manage sourcing decision at the strategic and tactical level for purchasing decisions dealing with raw materials. The proposed model can be extended to some more general settings. For example, some other parameters of the model, like the unit holding cost per period, might also evolve according to continuous-time Markov processes. In this case, ht would be equal to ict+wt, where i is the inventory carrying cost rate and wt is the unit storage cost at the beginning of period t. It can be assumed that the unit storage cost evolves according to another continuous-time Markov process, which is independent of the continuous-time Markov process corresponding to the evolution of the unit production cost. There are two state variables in this new problem. The first is the unit production cost, the same as that of the original problem, and the second is the unit storage cost. Finally, the DP functional equation (8) can be extended to obtain the optimal production scheduled for each period, in this new problem. The proposed model can also be extended to solving the equipment replacement problem in dynamic setting. Suppose that the unit procurement cost of facility is changing over the time horizon according to a continuous-time Markov process. Then, the optimal strategy of replacement can be easily found by extending the proposed model in this paper. Hence the only difference between the dynamic economic lot size model and the standard equipment replacement model is the calculation of the costs, that is the maintenance and procurement costs.