یک ستون اکتشافی نسلی برای تعیین اندازه دسته تولید پویای توانا شده با تقاضای تصادفی تحت محدودیت نرخ پر شدگی

This paper deals with the dynamic multi-item capacitated lot-sizing problem under random period demands (SCLSP). Unfilled demands are backordered and a fill rate constraint is in effect. It is assumed that, according to the static-uncertainty strategy of Bookbinder and Tan [1], all decisions concerning the time and the production quantities are made in advance for the entire planning horizon regardless of the realization of the demands. The problem is approximated with the set partitioning model and a heuristic solution procedure that combines column generation and the recently developed ABCβ

We consider the stochastic version of the dynamic multi-item capacitated lot-sizing problem (CLSP). The problem is to determine production quantities to satisfy demands for multiple products over a finite discrete time horizon such that the sum of setup and holding costs is minimized, whereby a capacity constraint of a resource must be taken into consideration. In contrast to the deterministic CLSP, we assume that for every product k and period t the demand is a random variable D kt (k =1,2,…,K ; t =1,2,…,T ). The period demands are non-stationary (to permit dynamic effects such as seasonal variations, promotions, or general mixtures of known customer orders with random portions of period demands), which usually is the case in a material requirements planning (MRP) based environment. Demand that cannot be filled immediately from stock on hand is backordered. As the precise quantification of shortage penalty costs which involve intangible factors such as loss of customer goodwill is very difficult, if not impossible, we assume that management has specified a target service level. In particular, we assume that the fill rate criterion (ββ service level) is in effect, as this criterion is very popular in industrial practice (see Tempelmeier [2]). Industrial (MRP based) planning practice usually applies a forecasting procedure that provides a deterministic time series of expected future demands. Uncertainty is taken into consideration by reserving a fixed amount of inventory as safety stock (see Wortmann [3], Baker [4]). The amount of this reserve stock is usually computed with simple rules of thumb borrowed from stationary inventory theory, e.g. the standard deviation of the demand during the risk period is multiplied by a quantile of the standard normal distribution. In this way, it is almost impossible to meet targeted service levels. In addition, using time-independent safety stocks under dynamic conditions may result in significant cost penalties (see Tunc et al. [5]). It is obvious that apart from the MRP-inherent neglect of limited capacities this widely used approach completely ignores the impact that lot sizes have on the absorption of risk. For example, in a case when due to high setup costs large lot sizes are used which cover the demands of many periods, it probably will be optimal to use no safety stock at all. On the other hand, if setup times or costs are reduced through technical measures in order to reduce lot sizes and the associated cycle stock, the required safety stock will increase. In addition, which is even more problematic, the dynamic alteration of the materials requirements as a consequence of newly observed demand realizations according to the MRP planning process leads to random releases of production lots, as the actual timing and size of the required replenishments are the outcome of the demand process, which is random. The resulting increase of the variance of the production quantities may have some unwanted consequences. First, in multi-level bill-of-material structures (or supply chains), the random change of a production order of a parent item leads to random requirements for its predecessors. This may cause the rescheduling of the production orders for the predecessors, which is a problem if a predecessor comes from an external supplier. If production orders are rescheduled, then demand variations occur that are propagated upstream through the supply chain, and which must be accounted for through buffers. In the literature this issue is discussed as planning nervousness. Second, the random change of the timing or size of a production lot directly translates into random resource requirements. For a machine, this is usually not a problem as long as the capacity of the machine is not overloaded. If an overload occurs, however, with fixed machine capacities this implies that the production plan becomes infeasible. In this case the planned due dates will be missed. This is one of the biggest problems found in short-term production planning in industry. In addition, there may even be cases when due to technical constraints the production quantities are unchangeable. This is often true in the process industries. Finally, if the considered resource is a human operator, then it may be unfavorable or even prohibited by labor agreement to change the workload in a period. One countermeasure is the definition of a planning horizon with an unchangeable production plan (frozen schedule). This is what we study in the current paper. In the following, we assume that, according to the static-uncertainty strategy of Bookbinder and Tan [1], all decisions concerning the time and the production quantities are made in advance for the entire planning horizon, which is equivalent to using a frozen schedule. The unavoidable randomness of demand is accounted for through the appropriate sizing of the orders. Other than Bookbinder and Tan [1], we consider multiple products, a resource with limited capacity and a fill rate constraint. The rest of this paper is organized as follows. In Section 2 the relevant literature is reviewed. Next, in Section 3, the considered stochastic lot-sizing problem under a fill rate per cycle constraint as proposed by Tempelmeier and Herpers [6] is approximated with a set partitioning model. Then, in Section 4, we present a heuristic column generation procedure to solve the LP-relaxation of this model and combine this procedure with the ABCβABCβ heuristic proposed in Tempelmeier and Herpers [6] to solve the complete problem. The results of a numerical experiment are reported in Section 5. Finally, Section 6 contains some concluding remarks.

In this paper we introduced an approximate model for the single level capacitated lot-sizing problem with dynamic stochastic demand under a fill rate constraint. We proposed to combine a column generation procedure to solve the LP-relaxation of the model with the ABCβABCβ heuristic of Tempelmeier and Herpers [6] to solve the remaining problem. The quality of the solutions is compared to the results found with the application of the ABCβABCβ heuristic of Tempelmeier and Herpers [6] alone. It was found that the proposed heuristic is fast and that it provides solutions that are on the average superior to the ABCβABCβ heuristic. In addition, the set partitioning model has the significant advantage that due to the model structure it is able to easily include setup times. However, in this case, the solution requires a heuristic for the remaining problem that can also handle setup times. This will be a subject for further research.