یک الگوریتم چند جمله ای برای یک مشکل تعیین اندازه دسته تولید پشتیبانی ، برون سپاری و موجودی محدود

This paper addresses a real-life production planning problem arising in a manufacturer of luxury goods. This problem can be modeled as a single item dynamic lot-sizing model with backlogging, outsourcing and inventory capacity. Setup cost is included in the production cost function, and the production level at each period is unbounded. The holding, backlogging and outsourcing cost functions are assumed to be linear. The backlogging level at each period is also limited. The goal is to satisfy all demands in the planning horizon at minimal total cost. We show that this problem can be solved in O(T4 log T) time where T is the number of periods in the planning horizon.

1. Introduction This paper addresses a real-life production planning problem coming from a company of luxury goods, which is a single item capacitated lot-sizing problem over a finite planning horizon of T periods. A production plan should be established based on the forecast demand. The demand of each period can be satisfied by production, and/or through inventory from previous periods, as in classical industry, but also by backlogging from subsequent periods, or it can be partially or entirely outsourced, should this lead to cost savings. In fact, the customers of luxury goods are willing to wait for their favorite items in case of shortage. As a consequence, shortage does not mean lost sales. Outsourcing is also a common practice in luxury goods. Of course, backlogging and outsourcing also cost money and should be taken into account in the model. Furthermore, the inventory, backlogging and outsourcing levels are limited. The problem consists of determining the amount to be produced and outsourced in each period so that all demands are satisfied (not necessarily in time) and the total cost of production, inventory holding, backlogging and outsourcing is minimized. This problem can be modeled as a lot-sizing model with backlogging and outsourcing. Even though this problem comes from a company of luxury goods, it also arises in other industries with a high degree of monopoly. The capacitated lot-sizing problem with inventory capacity is usually known as a bounded/limited inventory model. Up to now, there are very few works on this aspect in the existing literature. In most of the studies, the inventory is often assumed to be unbounded. Nonetheless, for many real-life applications, bounded inventory models are relevant. Nowadays, outsourcing has become a common practice for those firms that deal with highly variable demands to reduce the cost. It is more and more popular both to customers and firms since in this way, the former can obtain what he wants while the latter can avoid the goodwill loss or lessen the cost. However, outsourcing decision (when and how much) is not always easy to make for firms. Many scientific issues still need to be addressed. Nevertheless, academic research on this aspect still is scarce. Some authors considered immediate lost sales models (Aksen et al., 2003, Sandbothe and Thompson, 1990 and Sandbothe and Thompson, 1993). Absi et al., 2011 and Aksen, 2007 considered models involving backlogging and lost sales. In the model considered by Aksen (2007), in case of shortage, the portion of the lost sales are input data while it is a decision variable in the model considered by Absi et al. (2011). It should be noticed that the inventory is unbounded in all these models. In this paper, we prefer talking about outsourcing instead of lost sales, since in the current increasingly competitive environment, all companies make their best to satisfy customer requirements and to avoid lost sales. Deliberate lost sales are unrealistic especially when demands are assumed to be deterministic. However, from the modeling point of view lost sales are equivalent to outsourcing a part or whole of the demand of customers for various reasons (e.g., for small quantities, outsourcing from subcontractors is cheaper than in-house production). Deliberate lost sales must be avoided. As we show hereafter, the model studied in this paper is the most general one ever investigated. The uncapacitated version of lot-sizing model was first introduced by Wagner and Whitin (1958), they presented an O(T2) dynamic programming method. Zangwill (1966) generalized their work to the backlogging case, and proposed a polynomial algorithm. Blackburn and Kunreuther, 1974 and Lundin and Morton, 1975 developed an O(T2) algorithm for the unbounded inventory model with time-varying linear production cost functions and concave holding/backlogging cost functions. Later, Morton (1978) gave an improved algorithm running in O(T2) time to avoid the inner search for an even more special case where there is unlimited inventory and the cost is linear and stationary over time. Aggarwal and Park, 1993, Federgruen and Tzur, 1991 and Wagelmans et al., 1992 improved the complexity to O(T) and provided simple forward algorithms in O(T log T) time for the problems with general non-stationary linear production, holding and backlogging cost functions. Ganas and Papachristos (2005) devised a new O(T2) algorithm for the uncapacitated lot-sizing problem with linear holding/backlogging cost functions, fixed ordering cost (independent of the quantity ordered), constant demand, and constant cost parameters. Lot-sizing models with production capacity have been studied by many authors. The computational complexity was investigated by Bitran and Yanasse, 1982 and Florian et al., 1980. Florian et al. (1980) assumed that production and holding cost functions were continuous, nondecreasing and time-varying. They showed that this problem was NP-hard for quite general objective functions and provided a pseudo-polynomial dynamic programming algorithm. Some research has been done to identify polynomially solvable special cases. Bitran and Yanasse (1982) studied the computational complexity of the problem with linear production and holding cost functions under constant production capacity. Florian and Klein (1971) proposed an O(T4) dynamic programming algorithm to solve the production planning problem with constant production capacity and concave production and inventory holding cost functions. Janannathan and Rao (1973) extended their results to a more general production cost function which was neither concave nor convex. Van Hoesel and Wagelmans (1996) proposed an O(T3) algorithm for a model with constant production capacity, concave production cost and linear holding cost functions. Baker, Dixon, Magazine, and Silver (1978) devised an O(2T) algorithm for the case of time-varying production capacity and setup cost, time-varying holding and production cost functions. Chung and Lin (1988) obtained an O(T2) dynamic programming algorithm for the problem with linear production and holding cost functions where setup cost and unit production cost are nonincreasing in time and the capacities are nondecreasing in time. Recently, for the same problem, Van den Heuvel and Wagelmans (2006) also proposed a more efficient algorithm based on the geometrical interpretation of a dynamic programming algorithm. Chen, Hearn, and Lee (1994) proposed an efficient pseudo-polynomial dynamic programming approach by a geometric argument for the model with linear production and holding cost functions and non-constant production capacities. Swoveland (1975) gave a pseudo-polynomial dynamic programming algorithm for the backlogging model with piecewise concave production and holding/backlogging cost functions. Shaw and Wagelmans (1998) developed a pseudo-polynomial algorithm whose running time linearly depends on the magnitude of the data, for piecewise linear production cost functions, general holding/backlogging cost functions and setup costs. Van Hoesel and Wagelmans (2001) developed fully polynomial approximation schemes for concave backlogging and production cost functions and arbitrary monotone holding cost functions. In production planning context, concave cost functions arise much more frequently than convex cost functions. Problems with convex cost functions are also much more complex. This perhaps explains why most of the papers deal with linear and/or concave functions. Lee and Nahmias (1993) indicated that concavity occurs when there are declining marginal production costs or other scale economies. Veinott (1964) developed a parametric algorithm for the problem with convex production and holding cost functions. Backlogging was not permitted in his model. He showed that an optimal plan could be obtained by satisfying each unit of demand in turn as cheaply as possible. Recently, Feng, Chen, Kumar, and Lin (2011) showed that a problem with convex inventory cost can be solved in O(T log T) time if the setup cost is nonincreasing and the production capacity is constant. The bounded inventory model has received little attention in the literature. Love (1973) gave an O(T3) algorithm that searched the extreme points of the solution space for the bounded inventory model with piecewise concave cost functions and backlogging. Gutiérrez, Sedeño-Noda, Colebrook, and Sicilia (2002) proposed a new characterization of an optimal production plan to reduce the computational effort of Love’s procedure but with a constant inventory bound and no backlogging, and developed an O(T3) dynamic programming algorithm. Later, they Gutiérrez, Sedeño-Noda, Colebrook, and Sicilia (2007) extended their own results to the backlogging case with time-varying inventory bound. The extended model of Wagner and Whitin (1958) by considering storage capacity was proved to be solvable in O(T2) time by Toczylowski (1995). Gutiérrez, Sedeño-Noda, Colebrook, and Sicilia (2008) claimed that the time complexity could be reduced to O(T log T) but Van den Heuvel, Gutiérriez, and Hwang (2011) gave a counterexample. Atamtürk and Küçükyavuz (2005) gave an O(T4) algorithm for the model without backlogging but with fixed charge linear production and inventory cost functions. The complexity can be reduced to O(T2 log T) when the inventory cost functions are linear. Chu and Chu (2007) provided an algorithm with O(T2) complexity for the inventory/backlogging models with fixed charge linear production cost functions and general concave holding/backlogging cost functions. For the single-item lot-sizing problem with outsourcing, very few papers have been published. Sandbothe and Thompson (1990) presented a capacitated lot-sizing model with stockouts, in which all cost parameters are time-independent. They proved necessary conditions for an optimal solution with constant costs and presented an O(T3) forward dynamic programming algorithm when production capacity is constant and an O(2T) algorithm for the model with time-varying production capacity for the first k + 1 periods with computable k. Later, Sandbothe and Thompson (1993) considered the same problem but with inventory capacities. A forward algorithm was proposed and the amount of computational effort was only multiplied by a factor of 4 in contrast to the computational complexity of the earlier model. Aksen et al. (2003) considered an uncapacitated single-item lot-sizing problem with outsourcing and proposed an O(T2) forward recursive dynamic programming algorithm with time-varying linear production, inventory and lost sales costs. Atamtürk and Hochbaum (2001) showed that the model with concave production and outsourcing cost functions, constant production capacity, unlimited outsourcing level and no backlogging can be solved in O(T5) time. They also investigated other polynomial solvable models with non-speculative cost functions. Chu and Chu (2007) developed an O(T2 log T) algorithm to solve the models with no backlogging, linear holding and outsourcing cost functions, fixed charge linear production cost functions. The problem considered in this paper involves inventory capacity. Furthermore, both outsourcing and backlogging are allowed. To the best of our knowledge, this is the first paper that simultaneously considers the outsourcing and backlogging decisions with inventory capacity. It extends the model of Chu and Chu (2007). In fact, when the limit of backlogging is set to zero we obtain the model of Chu and Chu (2007). Thereby, the complexity of the algorithm to solve this model should also be higher. We show that the model can be solved in O(T4 log T) time, if the production cost functions are linear but with a fixed cost component, and the holding/backlogging and outsourcing cost functions are linear. At present, production, holding, backlogging and outsourcing are common managerial policies for firms. The remainder of this paper is outlined as follows. Section 2 gives the mathematical formulation of the model under study, shows related properties. Section 3 presents mathematical description of subplans, and develops an algorithm to compute optimal subplans and to solve the global problem. Section 4 ends the paper with some concluding remarks.