LOT-SIZING IN CAPACITATED MULTI-STAGE SERIAL SYSTEMS

The lot-sizing problem in capacitated multi-stage systems with a serial product structure is addressed. This is a complex optimization problem that is part of the decision set in material requirements planning (MRP) systems. The mathematical model that describes the problem uses the concept of echelon stock and includes lead times. Setup times are taken into account, which implies that the problem of finding a feasible solution is NP-Complete. This paper proposes a heuristic method that provides a production plan in order to minimize inventory, production, and setup costs. The heuristic starts from a solution for the uncapacitated problem, which is given by the sequential application of the Wagner-Whitin algorithm. Feasibility is then attempted by shifting production amounts between periods. Computational tests conducted in 1,800 instances with up to 40 components and 18 periods have shown that feasible solutions were obtained in 83.7% of the instances. For the infeasible instances, on average, the heuristic is able to find solutions with very low capacity excess. The solutions' quality is evaluated through a lower bound provided by Lagrangean relaxation and on average the gap is less than 10%.     

USING SHORT-TERM DEDICATION FOR SCHEDULING MULTIPLE PRODUCTS ON PARALLEL MACHINES

In a multiproduct, parallel machine environment, it may be beneficial to dedicate one or more of the machines to a single product for consecutive time periods. However, previous lot-sizing and scheduling models usually do not allow for such short-term dedication. This paper presents a mixed-integer programming model that allows for short-term dedication in scheduling parallel machines serving multiple products with dynamic demands. It also describes a Lagrangian-based algorithm for solving such scheduling problems. An experiment verifies the effectiveness of the algorithm and demonstrates the importance of allowing for short-term dedication. Capacity utilization, one of six factors investigated, greatly affects the use of dedication. A strong interaction effect between the number of machines and the number of products is also seen with respect to the usefulness of short-term dedication. A measure of estimated production frequency incorporates these two factors along with magnitudes of periodic demands. This measure has a strong relationship with the amount of short-term dedication used in solutions. Operations managers employing parallel machines could use the experimental results in deciding whether to use short-term dedication to reduce costs.     

AN IMPROVED IMPLEMENTATION OF THE WAGNER-WHITIN ALGORITHM

We have developed an improved implementation of the Wagner-Whitin algorithm for economic lot-sizing problems based on the planning-horizon theorem and the Economic-Part-Period concept. For many rigorous test conditions, this algorithm is about twice as fast and requires only half the array storage capacity of the previously fastest algorithm. Its execution time is approximately linear in the number of periods in the planning-horizon.     

A TECHNIQUE TO MINIMIZE OVERTIME IN THE CAPACITATED MRP PROBLEM

Since the development of early versions of material requirements planning (mrp) systems, it has been known that a weak link in this technique is the failure to consider the available capacity at the time the lot sizes for individual items are calculated. Ignoring the available capacity may result in infeasible production plans, i.e., those that can only be accomplished with the use of overtime. We present a technique to search for feasible production plans by means of minimizing the total overtime. The technique is based on modifying periodic-order-quantity (poq) lot sizes within a tabu search framework. Computational experiments with the largest problem structure reported in the literature show that the procedure is effective in determining lot sizes for individual items that either minimize or eliminate overtime. Additional experiments reveal that, with appropriate calibration of search parameters, the procedure is also able to deal with more general cost functions (e.g., those that include holding and setup costs).