A Practical Approach for Determining Rectangular Stock Sizes

In this paper we address the problem of determining what rectangular sizes should be stocked in order to satisfy a bill of materials composed of smaller rectangles. As is common in many manufacturing operations, the stock material will be cut using two-staged guillotine cutting patterns. We first generate a large number of stock sizes ideally suited to the bill of materials. Then we use a facility location algorithm to consolidate the stock sizes down to an acceptable number. Given the solution of what rectangular sizes to stock, a second program is used to map bills of materials into the stock rectangles. The effectiveness of our approach is demonstrated by generating stock sizes for a real-world bill of materials with 392 distinct order sizes and over 7700 order pieces.     

Analysis of optimal opportunistic replenishment policies for inventory systems by using a (s,S) model with a maximum issue quantity restriction

The analysis of optimal inventory replenishment policies for items having lumpy demand patterns is difficult, and has not been studied extensively although these items constitute an appreciable portion of inventory populations in parts and supplies types of stockholdings. This paper studies the control of an inventory item when the demand is lumpy. A continuous review (s,S) policy with a maximum issue quantity restriction and with the possibility of opportunistic replenishment is proposed to avoid the stock of these items being depleted unduly when all the customer orders are satisfied from the available inventory and to reduce ordering cost by coordinating inventory replenishments. The nature of the customer demands is approximated by a compound Poisson distribution. When a customer order arrives, if the order size is greater than the maximum issue quantity w, the order is satisfied by placing a special replenishment order rather than from the available stock directly. In addition, if the current inventory position is equal to or below a critical level A when such an order arrives, an opportunistic replenishment order which combines the special replenishment order and the regular replenishment order will be placed, in order to satisfy the customer's demand and to bring the inventory position to S. In this paper, the properties of the cost function of such an inventory system with respect to the control parameters s, S and A are analysed in detail. An algorithm is developed to determine the global optimal values of the control parameters. Indeed, the incorporation of the maximum issue quantity and opportunistic replenishment into the (s,S) policy reduces the total operating cost of the inventory system.     

The Cutting Stock Problem in the Flat Glass Industry

The cutting stock problem occurs where large rectangles of some material require cutting into smaller rectangles, in the most appropriate way, to satisfy an order book. A linear programming approach to the problem has been suggested by P. C. Gilmore and R. E. Gomory. An application of this approach in the glass industry is described which is shown to be inadequate since it only satisfies a wastage criterion. In practice, multiple criteria must be satisfied and two alternative approaches using linear programming and heuristic scheduling are proposed.     

An algorithm for the two-dimensional assortment problem

In this paper we consider the two-dimensional assortment problem. This is the problem of choosing from a set of stock rectangles a subset which can be used for cutting into a number of smaller rectangular pieces. Constraints are imposed upon the number of such pieces which result from the cutting.A heuristic algorithm for the guillotine cutting version of the problem is developed based on a greedy procedure for generating two-dimensional cutting patterns, a linear program for choosing the cutting patterns to use and an interchange procedure to decide the best subset of stock rectangles to cut.Computational results are presented for a number of test problems which indicate that the algorithm developed produces good quality results both for assortment problems and for two-dimensional cutting problems.     

Modeling multistage cutting stock problems

In multistage cutting stock problems (CSP) the cutting process is distributed over several successive stages. Every stage except the last one produces intermediate products. The list of intermediate products may be given or arbitrary. The goal is to minimize the total amount of material taken out of stock to cut finished products sufficient to meet customer demands. If the intermediate sizes are given, the column generation technique can be applied to multistage cutting problems. If the intermediate sizes are not given then another dimension is added to the problem complexity. We propose a special procedure for this case that dynamically generates both rows (intermediate sizes) and columns (patterns). We refer to this method as row-and-column generation. The method uses an auxiliary problem embedded into the frame of the revised simplex algorithm. It is a non-linear knapsack problem that can be solved efficiently. In contrast to the column generation method the developed technique cannot guarantee the optimal solution. However, the results of computational experiments are very promising and prove that the method is a valuable addition to the set of tools for modeling and solving multistage CSPs.     

An iterative sequential heuristic procedure to a real-life 1.5-dimensional cutting stock problem

This paper addresses a real-life 1.5D cutting stock problem, which arises in a make-to-order plastic company. The problem is to choose a subset from the set of stock rectangles to be used for cutting into a number of smaller rectangular pieces so as to minimize total production cost and meet orders. The total production cost includes not only material wastage, as in traditional cutting stock problems, but also production time. A variety of factors are taken into account, like cutter knife changes, machine restrictions, due dates and other work in progress limitations. These restrictions make the combinatorial structure of the problem more complex. As a result, existing algorithms and mathematical models are no longer appropriate. Thus we developed a new 1.5D cutting stock model with multiple objectives and multi-constraints and solve this problem in an incomplete enumerative way. The computational results show that the solution procedure is easy to implement and works very well.     

Optimising the cutting of wood fibre plates in the hardboard industry

Hardboard companies transform eucalyptus trunks into rectangular wood fibre plates basically by means of processes of disintegration and reconstitution of wood fibres. Such plates called hardboards are then cut into ordered items (smaller rectangles) to satisfy customer demands. In this paper, we present approaches to generate cutting patterns that minimize the cost or waste of material, considering different particular constraints associated with longitudinal and transversal saws, head cuts, book rotation and item unloading stations of the cutting machine. The methods are based on dynamic programming recursive formulas combined with greedy constructive heuristics and the primal simplex algorithm. To illustrate the application of these approaches, a case study was carried out in a Brazilian hardboard company. The results show that the approaches are able to produce better solutions than the ones currently used by the company.     

An integrated production and inventory model to dampen upstream demand variability in the supply chain

We consider a two-echelon supply chain: a single retailer holds a finished goods inventory to meet an i.i.d. customer demand, and a single manufacturer produces the retailer’s replenishment orders on a make-to-order basis. In this setting the retailer’s order decision has a direct impact on the manufacturer’s production. It is a well known phenomenon that inventory control policies at the retailer level often propagate customer demand variability towards the manufacturer, sometimes even in an amplified form (known as the bullwhip effect). The manufacturer, however, prefers to smooth production, and thus he prefers a smooth order pattern from the retailer. At first sight a decrease in order variability comes at the cost of an increased variance of the retailer’s inventory levels, inflating the retailer’s safety stock requirements. However, integrating the impact of the retailer’s order decision on the manufacturer’s production leads to new insights. A smooth order pattern generates shorter and less variable (production/replenishment) lead times, introducing a compensating effect on the retailer’s safety stock. We show that by including the impact of the order decision on lead times, the order pattern can be smoothed to a considerable extent without increasing stock levels. This leads to a situation where both parties are better off.     

Cutting circles and polygons from area-minimizing rectangles

A set of circles, rectangles, and convex polygons are to be cut from rectangular design plates to be produced, or from a set of stocked rectangles of known geometric dimensions. The objective is to minimize the area of the design rectangles. The design plates are subject to lower and upper bounds of their widths and lengths. The objects are free of any orientation restrictions. If all nested objects fit into one design or stocked plate the problem is formulated and solved as a nonconvex nonlinear programming problem. If the number of objects cannot be cut from a single plate, additional integer variables are needed to represent the allocation problem leading to a nonconvex mixed integer nonlinear optimization problem. This is the first time that circles and arbitrary convex polygons are treated simultaneously in this context. We present exact mathematical programming solutions to both the design and allocation problem. For small number of objects to be cut we compute globally optimal solutions. One key idea in the developed NLP and MINLP models is to use separating hyperplanes to ensure that rectangles and polygons do not overlap with each other or with the circles. Another important idea used when dealing with several resource rectangles is to develop a model formulation which connects the binary variables only to the variables representing the center of the circles or the vertices of the polytopes but not to the non-overlap or shape constraints. We support the solution process by symmetry breaking constraints. In addition we compute lower bounds, which are constructed by a relaxed model in which each polygon is replaced by the largest circle fitting into that polygon. We have successfully applied several solution techniques to solve this problem among them the Branch&Reduce Optimization Navigator (BARON) and the LindoGlobal solver called from GAMS, and, as described in Rebennack et al. [21], a column enumeration approach in which the columns represent the assignments. Good feasible solutions are computed within seconds or minutes usually during preprocessing. In most cases they turn out to be globally optimal. For up to 10 circles, we prove global optimality up to a gap of the order of 10^?8 in short time. Cases with a modest number of objects, for instance, 6 circles and 3 rectangles, are also solved in short time to global optimality. For test instances involving non-rectangular polygons it is difficult to obtain small gaps. In such cases we are content to obtain gaps of the order of 10%.     

Inventory control using a service constraint on the expected customer order waiting time

In this paper an analytical model is presented which permits the determination of the minimal inventory reorder point subject to (a) a maximum specified expected customer order waiting time or (b) a maximum specified probability of a customer order waiting more than a predetermined time span. The probability distribution of the customer order waiting time is determined for an arbitrary demand distribution (e.g. normal, gamma or exponential) and under stochastic replenishment lead time conditions by use of arguments from renewal theory. The results established can be used for the customer-oriented control of inventory policy as well as for the analysis of multi-echelon inventory systems.     

The determination of optimal partial fill policy for an inventory system with lumpy demand items

This paper presents a mathematical model developed for the synthesis of optimal replenishment policies for items that experience lumpy demands. In order to avoid disrupting the inventory system, a cutoff point of w units is introduced such that the system would only satisfy routinely customer orders with transaction sizes less than or equal to w units. For customer orders with transaction sizes larger than w units, the system would only supply the cutoff amount (w units). The excess units would be refused. The control discipline is the (s, S) inventory policy with continuous review, and the nature of the customer orders is approximated by a discrete stuttering Poisson distribution. The optimal values of the control parameters, w, s and S, are determined. The theoretical results obtained are illustrated with a numerical example.     

Stock Control Using the Stock Level Frequency Distribution

Stock level frequency distributions are derived for continuous review stock control policies in which the lead time demand is normally distributed. The percentage points of the distributions have been tabulated, and the table can be used to determine the reorder point that will meet a specified customer order quantity from stock with a specified probability. The results can also be used to determine the order up to point for a periodic review policy and the reorder point for a mixed policy.     

A hierarchical approach for one-dimensional cutting stock problems in the steel industry that maximizes yield and minimizes overgrading

In the steel industry, as hot steel products exit the producing facility, they are cut at primary saws (hotsaws) into shorter pieces. After these pieces cool, they are inspected for defects and either applied directly to customer orders or are further cut to ordered lengths at secondary saws (cold saws). In this case study, we will describe a hierarchical algorithm, DYNACUT_CS, that efficiently and effectively generates cutting patterns for material that is to be cut at cold saws. DYNACUT_CS strives to maximize yield over all the material cut and simultaneously tries to minimize overgrading (applying higher quality material than specified by the customer). An example will be given to illustrate how the algorithm works. This approach has been implemented for a variety of products at several different Bethlehem Steel Corporation facilities.     

A Note on Fixed and Minimum Order Quantity Stock Systems

It is often believed that the square root formula called the EOQ only applies to situations where customers demand small quantities at a fairly constant rate. This note shows that essentially the same formula can be derived for "lumpy" customer orders occurring at a variable rate. Also, as the EOQ is derived assuming that a fixed quantity is always ordered for replenishment it does not allow for the over-shoot when customer orders exceed the available stock. This note shows that when the EOQ is large relative to the average customer order the overshoot problem can be ignored. However, when the EOQ is small some tentative results involving exponentially distributed customer order quantities indicate that substantial savings can be made using a "minimum order quantity" policy.     

Evaluation of three production planning procedures for the use of recipe flexibility

Process industries often obtain their raw materials from mining or agricultural industries. These raw materials usually have variations in quality, which often lead to variations in the recipes used for manufacturing a product. Another reason for varying the recipe is to minimize production costs by using the cheapest materials that still lead to a satisfactory quality in the product. A third reason for using recipe flexibility is that it may occur that at the time of production not all materials for the standard recipe are available. In earlier research we showed under what conditions the use of this type of recipe flexibility should be preferred to the use of high materials stock to avoid materials shortages. We also showed that the use of recipe flexibility to account for material shortages can be justified if the material replenishment leadtime is long, the demand uncertainty is high and the required service level is high. In this paper we assume that these conditions are satisfied and we investigate three different production planning procedures that make use of recipe flexibility to cope with the uncertainty in demand and supply. We assume that the customer order leadtime is much smaller than the material replenishment leadtime, and therefore demand uncertainty is high. The optimal procedure optimizes material use over a planning horizon equal to the material replenishment leadtime, taking into account the customers orders and knowledge of the distribution function of future demand. The deterministic procedure also optimizes the material use over the material replenishment leadtime, but it assumes a deterministic demand level for unknown orders. The simplest, myopic procedure optimizes material use over only the accepted customer orders. These three procedures are investigated via an experimental design of computer simulations of an elementary small scale model of the production planning situation. The results show that the optimal procedure outperforms the other two procedures. Furthermore, for a realistic cost structure in feed industry under certain circumstances the use of the optimal procedure may lead to a 4% increase in profit. However, this improvement must be weighted against the cost incurred by the operational use of this complex procedure. Based on these considerations and the numerical results in this paper, we may expect that for some situations in practice the use of the simplest myopic procedure, optimizing material use only over the available customer orders, will be justified from an overall cost point of view.     

Fixed charge problems with identical fixed charges

The general problem considered by this paper is a special case of the fixed-charge problem. The further condition imposed is that all variables have the same associated fixed-charge. The problem is discussed in the context of a known commercial application, that being the cutting stock problem. The situation considered is that of cutting given numbers of small rectangles from large rectangular stock-plates. In many such situations major aims are to have low stock-plate usage and a low number of setups of the cutting equipment. These represent conflicting objectives capable of being combined by the use of fixed charges upon the setups but this paper presents an alternative approach incorporating direct manipulation of the number of setups involved in the solution. This approach is compared to a solution technique for the general fixed-charge problem.     

Capacitated replenishment and disposal planning for multiple products with resalable returns

We consider a replenishment and disposal planning problem (RDPP) that arises in settings where customer returns are in as-good-as-new condition. These returns can be placed into inventory to satisfy future demand or can be disposed of, in case they lead to excess inventory. Our focus is on a multi-product setting with dynamic demands and returns over a finite planning horizon with explicit replenishment and disposal capacities. The problem is to determine the timing of replenishment and disposal setups, along with the associated quantities for the products, so as to minimize the total costs of replenishment, disposal, and inventory holding throughout the planning horizon. We examine two variants of the RDPP of interest both of which are specifically motivated by a spare part kitting application. In one variant, the replenishment capacity is shared among multiple products while the disposal capacity is product specific. In the other variant, both the replenishment and disposal capacities are shared among the products. We propose a Lagrangian Relaxation approach that relies on the relaxation of the capacity constraints and develop a smoothing heuristic that uses the solution of the Lagrangian problem to obtain near-optimal solutions. Our computational results demonstrate that the proposed approach is very effective in obtaining high-quality solutions with a reasonable computational effort.     

Stock Rationing in a Continuous Review Two-Echelon Inventory Model

In this paper we consider a 1-warehouse, N-retailer inventory system where demand occurs at all locations. We introduce an inventory model which allows us to set different service levels for retailers and direct customer demand at the warehouse. For each retailer a critical level is defined, such that a retailer replenishment order is delivered from warehouse stock if and only if the stock level exceeds this critical level. It is assumed that retailer replenishment orders, which are not satisfied from warehouse stock, are delivered directly from the outside supplier, instead of being backlogged. We present an analytical upper bound on the total cost of the system, and develop a heuristic method to optimize the policy parameters. Numerical experiments indicate that our technique provides a very close approximation of the exact cost. Also, we show that differentiating among the retailers and direct customer demand can yield significant cost reductions.     

Order splitting in continuous review (Q,r) inventory models

A number of recent articles in the literature have argued the case, when lead time is variable, for splitting a replenishment order for Q between n suppliers by comparing this with the alternative of placing a single order for Q on one supplier. The split order compares favourably on the grounds that the arrival of the first component of a split order cannot be later than the arrival of an order from any one specified supplier. This note argues that an alternative comparison could be made with a policy of ordering Q/n from a single supplier (n times as often). It makes this comparison in the context of a continuous review (Q, r) inventory model but does so not by comparing aggregate costs but by fixing Q and the customer stock service level and comparing the average stock — an approach which is more appropriate to how many companies manage inventory in practice. We consider Poisson and deterministic demand processes, a general lead time distribution and both lost sales and backorder models.