Efficient Heuristics for MRP Lot Sizing with Variable Production/Purchasing Costs*

Two heuristics based on branch and bound (B&B) are developed to solve closed-loop material requirements planning (MRP) lot-sizing problems that have general product structures and variable costs. A “look ahead method'’(LAM) heuristic allows for variable production/purchasing costs and uses a single-level B&B procedure to rapidly improve lower bound values; thus, LAM efficiently uses computer-storage capacity and allows solution of larger problems. The “total average modification'’(TAM) heuristic uses B&B, applied level by level, and modified setup and carrying costs to solve the variable production/purchasing costs MRP lot-sizing problem. LAM and TAM are tested on problems and compared to heuristics in the literature. TAM may be used to solve large MRP lot-sizing problems encountered in practice.     

A Simple Heuristic for Lot Sizing with Setup Times

This paper presents an easily understood and computationally efficient heuristic algorithm for the capacitated lot sizing problem (CLSP), the single machine lot-sizing problem, with nonstationary costs, demands, and setup times. The algorithm solves problems with setup time or setup cost. A variation of the algorithm can solve problems when limited amounts of costly overtime are allowed. Results of experimentation indicate that the most significant effects on solution quality are due to the level of setup costs relative to holding costs and the size of the problems as determined by the number of items. Also affecting solution quality are tightness of the capacity constraint and variability of demand in a problem. When the capacity constraint is extremely tightly binding, it sometimes has difficulty finding solutions that do not require overtime.     

Integrative Cycle Scheduling Approach for a Capacitated Flexible Assembly System*

This study revisits the traditional single stage, multi-item, capacitated lot-sizing problem (CLSP) with a new integrative focus on problem structuring. Unlike past research, we develop integrative cycle scheduling approaches which simultaneously address lot-sizing, capacity, and sequencing issues. Our purposes are to (1) explore the effect of sequencing on inventory levels, (2) examine the problem of infeasibility in the economic lot scheduling problem (ELSP), and (3) provide a simple methodology of generating low-cost cycle schedules in an environment with discrete shipping, dynamic demands, limited capacity, zero setup cost, and sequence-independent setup times. Our procedures are compared to benchmark cycle scheduling approaches in terms of both inventory cost and computation time under different demand scenarios, using the operating data from a flexible assembly system (FAS) at the Ford Motor Company's Sandusky, Ohio plant.     

Concepts,Theory, and Techniques A JOINT LOT-SIZING RULE FOR FIXED LABOR-COST SITUATIONS

Many American firms are implementing just-in-time production in order to minimize inventories, reduce flow time, and maximize resource utilization. These firms recognize that, in the short run, setup costs really are fixed expenses and it is available capacity which is the critical factor in determining production-run quantities. We propose using available capacity to increase the number of setups and reduce lot-size inventories. This results in improved relevant cost performance. Sugimori, Kusunoki, Cho, and Uchikawa [16] in their paper on the Toyota kanban system developed a relationship for lead time but failed to use it for lot sizing. We use this relationship to develop the joint lot-sizing rule. The efficacy of our proposed rule is demonstrated by applying it to lot-size scheduling problems at the John Deere Engine Works [14]. Extensions of the proposed rule to undercapacity situations with material-wastage costs in the setup processes and to multistate production inventory systems also are discussed.     

A new MRP/GT lot sizing heuristic: A simulation study

This paper studies the lot-sizing problem in Material Requirements Planning/Group Technology (MRP/GT) systems. A GT production cell is designed to produce many families of components. A major setup is required when switching from manufacturing one family of components to another family, and a minor setup is needed when switching from manufacturing a component type to another component type within the same family. Inventory holding cost is incurred if inventory level is positive, and inventory shortage cost is incurred if inventory level is negative, that is, backordering. The objective of the proposed lot-sizing problem is to minimize the sum of major and minor setup costs, holding and shortage costs, and regular production cost, and to meet simultaneously the demand requirements. The proposed problem is modelled into a linear integer program, a heuristic method to solve the problem is proposed, and a simulation experiment conducted to evaluate the performance of the proposed heuristic and some existing heuristics. The computational results show that the proposed heuristic is useful to reduce the total cost significantly over a wide variety of simulated environments.     

Joint Lot Sizing and Scheduling of Multiple Items with Sequence-Dependent Setup Costs

The objective of this research is to investigate the effects of setup-cost estimating methods on the lot sizing and scheduling of multiple products in multiple periods. These initial setup cost estimators (ISCEs) are used to estimate sequence-independent initial setup costs from sequence-dependent setup costs. A search of the literature reveals that, although sequence-dependent setup costs are frequently found in practice and ISCEs are frequently used, there is a dearth of research concerning the effect of using ISCEs. After a review of the literature, a mixed integer formulation of the joint problem of lot sizing and scheduling is presented, followed by a discussion of the difficulty in solving the formulation. Next, the six ISCEs evaluated are presented. These ISCEs range from simple (select the minimum setup cost) to complex (use the branch-and-bound solution to a traveling salesman-type problem). Each ISCE is evaluated using a full factorial design with five independent variables: demand distribution (three levels), demand trend (three levels), setup to inventory level (six levels), setup distribution (three levels), and setup variability (two levels). Two hypotheses are researched. Do the more computationally complex ISCEs produce lower overall costs than do the simpler ISCEs? Does the reduction in total cost justify the additional computation cost? The results of this study demonstrate that it may be incorrect to use “conventional wisdom'’when selecting an ISCE.     

THE PERFORMANCE OF A SIMPLE INCREMENTAL LOT-SIZING RULE IN A MULTILEVEL INVENTORY ENVIRONMENT

A simple incremental cost approach to lot sizing was tested in a multilevel inventory environment. The incremental approach has not previously been tested in a large-scale study involving multiple product-structure levels. Using the Wagner-Whitin (WW) algorithm as a benchmark, the simple incremental rule (IPPA) was compared to three heuristic procedures (LFL, EOQ, and POQ) frequently used in material requirements planning (MRP) lot-sizing research. The incremental rule consistently generated lower total order/setup and carrying costs than the three heuristics across the 3,200 multilevel test situations examined. In many of the test situations, the incremental rule also outperformed the WW benchmark.     

Production and inventory control with chaotic demands

This study explores an efficient approach for identifying chaotic phenomena in demands and develops a production lot-sizing method for chaotic demands. Owing to the butterfly effect of chaotic demands, precise prediction of long-term demands is difficult. The experiments conducted in this study reveal that the maximal Lyapunov exponent is very effective in classifying chaotic and non-chaotic demands. A computational procedure of the Lyapunov exponent for production systems has been developed and some real world chaotic demands have been identified using the proposed chaos-probing index. This study proposes a modified Wagner–Whitin method that uses a forward focused perspective to make production lot-sizing decision under chaos demands for a single echelon system. The proposed method has been empirically demonstrated to achieve lower total production costs than three commonly used lot-sizing models, namely: lot-for-lot method, periodic ordering quantity, and Silver-Meal discrete lot-size heuristic under a fixed production horizon, and the conventional Wagner–Whitin algorithm under chaotic demands. Sensitivity analysis is conducted to compare changes in total cost with variations in look-ahead period, initial demand, setup cost and holding costs.     

求解大规模生产批量问题的启发式算法

企业资源优化模型是多物料、多层、受多种能力约束、有启动时间和启动成本的生产批量问题,该问题是NP完全问题,求解十分困难。为此我们提出了一个新的启发式方法,通过交互求解线性规划松弛问题并应用改进的Silver-Meal方法处理批量来近似求解生产批量问题,并第一次将影子价格引入Silver-Meal方法的批量决策,数值实验表明新算法在不同规模问题上的有较好的表现。     

An Experimental Analysis of Capacity-Sensitive Setup Parameters for MRP Lot Sizing

Most material requirements planning (MRP) systems apply standard costing (absorption costing) approaches to define setup costs that are used as fixed (time invariant) setup parameters in single-level lot-sizing methods. This paper presents a computationally simple approach for estimating more appropriate setup parameters based on estimates of work-center shadow prices. These setup parameters then are used in traditional single-level MRP lot-sizing procedures. The shadow price of capacity at each work center is calculated as the increase in the overall inventory carrying cost for each additional hour of capacity lost to setups. The opportunity cost of a setup for an order subsequently is determined based on the routing information for each order and is used by traditional MRP lot-sizing procedures to calculate lot sizes. A simulation experiment compares the performance period order quantity lot sizing with capacity-sensitive setup parameters with the fixed accounting-based setup parameters. The simulation replicates the planning and control functions of a typical MRP system. The results of the experiment show that capacity-sensitive setup parameters can make significant reductions in both carrying cost and lateness and can achieve many of the benefits of optimized production technology in the context of an MRP system.     

TOTAL SETUP LOT SIZING WITH QUANTITY DISCOUNTS*

Often, order quantity decisions are made by purchasers facing a price schedule of quantity discounts. Traditional solution procedures have consisted of the evaluation of total cost at numerous price-break points in search of the lowest total cost. This approach is tedious and not particularly informative, especially when one is faced with lengthy schedules. This paper presents a total setup lot-sizing model that reduces the computations required to find the least-total-cost quantity, given parameters from a supplier's price schedule. The parameters are first obtained by simple regression (graphical or computer) and in themselves can provide valuable insight for the purchaser's decision making. A total setup lot-sizing model is next developed to define a “critical interval” that contains the solution. The model and algorithm are tested under a variety of conditions. Their application offers the decision maker a convenient alternative to determine the best quantity to order from a tendered price schedule.     

Effects of Product Structure Complexity on Multi-level Lot Sizing*

As an input to the materials requirement planning (MRP) process, the product structure interacts with the lot-sizing rules to affect inventories, materials flow, and production costs. Despite engineering constraints, considerable latitude is still available to construct alternate product structures for the same product. An important concern of MRP managers and designers is the impact of product structure complexity on the cost performance of the lot-sizing rules. To date, there exists no detailed research that provides managers with guidelines that relate the lot-sizing rules to individual product structure parameters. We report on an extensive experiment to test the effects of individual product structure parameters on the relative cost performance of 11 lot-sizing rules. Three parameters—the number of items, number of levels, and commonality index—are proposed to characterise product structure complexity and used as factors in an experiment involving a large variety of product structures. The results indicate that all three parameters affect the relative cost differences but not the ranking of the rules. The overall best lot-sizing rule is Bookbinder and Koch's [11] rule.     

Coordinated deterministic dynamic demand lot-sizing problem: A review of models and algorithms

Due to their importance in industry and mathematical complexity, dynamic demand lot-sizing problems are frequently studied. In this article, we consider coordinated lot-size problems, their variants and exact and heuristic solutions approaches. The problem class provides a comprehensive approach for representing single and multiple items, coordinated and uncoordinated setup cost structures, and capacitated and uncapacitated problem characteristics. While efficient solution approaches have eluded researchers, recent advances in problem formulation and algorithms are enabling large-scale problems to be effectively solved. This paper updates a 1988 review of the coordinated lot-sizing problem and complements recent reviews on the single-item lot-sizing problem and the capacitated lot-sizing problem. It provides a state-of-the-art review of the research and future research projections. It is a starting point for anyone conducting research in the deterministic dynamic demand lot-sizing field.     

ECONOMIC ORDER QUANTITIES WITH QUANTITY DISCOUNTS: GRANDMA DOES IT BEST

We examine a new algorithm developed by Kuzdrall and Britney [5] for locating the optimal order quantity in the presence of quantity discounts. Their algorithm, based on a model for the supplier's formulation of the price schedule, involves a regression analysis to identify the supplier's variable cost per unit and the fixed cost that the supplier seeks to recover, followed by an iterative search for the optimum. The authors describe this method as a “convenient alternative to the aimless searching of traditional approaches” [5, p. 101]. We examine the allegation of superiority of their total setup lot-sizing model over the classical method and dispute their claim of superiority.     

Lot-sizing and scheduling in flat-panel display manufacturing process

In this paper, we consider a lot-sizing and scheduling problem arising in the real-world flat-panel display industry. This problem is formulated as a variant of the discrete lot-sizing and scheduling problem with a sequence-dependent setup. After describing the characteristics of the problem and analyzing its computational complexity, we propose an extended formulation based on a network structure. Even though the problem is NP-hard in general, we show that there exist special cases solvable in polynomial time. For the general cases, we demonstrate the tightness of the extended formulation by means of both polyhedral analysis and computational experiments with artificially generated data and real-world industry data. We also propose a relax-and-fix heuristic algorithm based on the extended formulation, which has been deployed in practice, with the corresponding computational results.     

Inventory Rationing for Multiple Class Demand under Continuous Review

We consider how a firm should ration inventory to multiple classes in a stochastic demand environment with partial, class‐dependent backlogging where the firm incurs a fixed setup cost when ordering from its supplier. We present an infinite‐horizon, average cost criterion Markov decision problem formulation for the case with zero lead times. We provide an algorithm that determines the optimal rationing policy, and show how to find the optimal base‐stock reorder policy. Numerical studies indicate that the optimal policy is similar to that given by the equivalent deterministic problem and relies on tracking both the current inventory and the rate that backorder costs are accumulating. Our study of the case of non‐zero lead time shows that a heuristic combining the optimal, zero lead time policy with an allocation policy based on a single‐period profit management problem is effective.     

Solving the Economic Lot-Scheduling Problem Using the Method of Prime Subperiods

In recent years the reported successes of Japanese production systems, particularly the just-in-time approach to inventory control, has caused managers to focus more of their attention on efficient decision-making procedures for determining production schedules that minimize inventory costs. One such potential area of attention is the economic lot-scheduling problem (ELSP), which occurs in a variety of manufacturing environments where machining operations are prevalent. The economic lot-scheduling problem addresses the determination of lot sizes for N products with constant demand (and cycled through one machine with a given production rate) to minimize setup and inventory costs. The most successful solution approaches to the ELSP have been based on the concept of a basic period that is of sufficient length for the production of all items, even though each item might not be produced during each repetition of the basic period. This paper proposes a heuristic approach to the solution of the ELSP (referred to as the method of prime subperiods), which is an extension of the basic period approaches. The procedure is described and demonstrated via an example and then tested using a set of six example problems previously employed in the literature related to the ELSP. The results indicate as good or superior performance by the proposed method of prime subperiods.     

Master Scheduling in Assemble-To-Order Environments: A Capacitated Multiobjective Lot-Sizing Model

Basic characteristics of an assemble-to-order environment make effective master scheduling extremely difficult. Limited resource capacities and dynamic customer end-item demand contribute to the complexity of the master production scheduling problem. To gain flexibility and responsiveness within this system, the master production schedule (MPS) focuses at the component level. This research proposes a master scheduling technique for manufactured components which combines a multiobjective capacitated multi-item/multi-stage lot-sizing model with an interactive multiple objective optimization solution procedure. To evaluate the model's performance as a realistic and practical master scheduling tool, this study focuses on the National Cash Register (NCR) electronics manufacturing facility in Columbia, South Carolina.     

A Comparative Analysis of the Relative Effectiveness of Four Dynamic Lot-Sizing Techniques on Return on Investment

The relative performance of dynamic lot-sizing techniques has been of considerable interest to researchers in recent years. While research has addressed performance in terms of cost-effectiveness, researchers have not determined the impact of dynamic lot-sizing techniques on return on investment (ROI) as it applies to finished goods' schedules. The purpose of this research is to explore the relative performance of four dynamic lot-sizing techniques with regard to ROI, namely the Wagner-Whitin, Incremental Part Period, Silver-Meal, and Groff techniques. Computer graphics are employed to analyze the relative ROI effectiveness.