A hierarchical approach for the capacitated lot-sizing and scheduling problem with a special structure of sequence-dependent setups

This research deals with the single machine multi-product capacitated lot-sizing and scheduling problem (CLSP) with sequence-dependent setup times and setup costs. The CLSP determines the production quantities and the sequence to satisfy deterministic and dynamic demand during multiple periods. The objective is to minimise the total sum of the inventory holding costs and the sequence-dependent setup costs. We consider a special form of sequence-dependent setup times where the larger product we produce next, the more setup time we need. As a solution approach, we propose a two-level hierarchical method consisting of upper-level planning and the lower-level planning. In the upper-level planning, we solve the lot-sizing problem with estimated sequence-independent setup times utilising the characteristic of the special structure of setup times. Then we solve the scheduling problem in the lower-level planning. The proposed method is compared with the single-level optimal CLSP solution and an existing heuristic developed for the uniform structure of setup times.     

Joint cell loading and scheduling approach to cellular manufacturing systems

A hierarchical multi-objective heuristic algorithm and pricing mechanism are developed to first determine the cell loading decisions, and then lot sizes for each item and to obtain a sequence of items comprising the group technology families to be processed at each manufacturing cell that minimise the setup, inventory holding, overtime and tardiness costs simultaneously. The linkage between the different levels is achieved using the proposed pricing mechanism through a set of dual variables associated with the resource and inventory balance constraints, and the feasibility status feedback information is passed between the levels to ensure internally consistent decisions. The computational results indicate that the proposed algorithm is very efficient in finding a compromise solution for a set of randomly generated problems compared with a set of competing algorithms.     

Effective allocation of idle time in the group technology economic lot scheduling problem

The group technology economic lot scheduling problem (GT-ELSP) addresses the issue of scheduling the products, classified into groups, on a single facility. The objective is to develop a schedule that minimises the sum of average inventory holding and setup costs over the infinite planning horizon. Previous research on this class of problems has assumed the cycle idle time to be equally divided among various sequence positions and has varied the frequency of production of individual products. We propose a heuristic that maintains constant frequency of products and varies the idle time among the sequence positions. We address the feasibility issue of the GT-ELSP and show that our heuristic, based on the time varying lot size approach, yields low-cost quality solutions that aid practical implementation. We tested our heuristic on a large set of randomly generated problems to assess its efficacy over the solutions of earlier proposed heuristics.     

Solution algorithms for dynamic lot-sizing in remanufacturing systems

We consider the problem of determining the lot sizes that satisfy the demands of remanufactured products over a given planning horizon with discrete time periods. Remanufacturing, in which used or end-of-life products are restored to like-new condition, typically consists of disassembly, reprocessing and reassembly processes, and hence the lot sizes are determined for each of the three processes. The objective is to minimise the sum of setup and inventory holding costs occurring at the three processes. To represent the problem mathematically, we suggest a mixed integer programming model by combining the existing ones for disassembly and assembly systems. After proving that the problem is NP-hard, we suggest two dynamic programming based heuristics, called the aggregation and the decomposition type heuristics in this paper. Computational experiments were done on various test instances, and the results show that the two heuristics give near-optimal solutions in a short amount of computation time. Also, the performances of the heuristics are compared according to different values of problem parameters.     

A Heuristic for a Class of Production Planning and Scheduling Problems

This paper describes a solution technique for a general class of problems referred to as aggregate planning and master scheduling problems. The technique is also applicable to multi-item single level capacitated lot sizing problems. The solution technique presented here is a heuristic that is practical for large problems e.g. 9 products and 36 periods. We have tested it for problems with varying number of time periods, number of products, setup costs, holding costs, overtime costs and capacity levels. For those problems that we could solve exactly using a branch and bound algorithm, the solutions produced by the heuristic were all within 1 % of optimality. For problems that we could not solve exactly, we are able to compute a lower bound on the optimal cost. Using the bound we are able to show that our heuristic solutions were within 2.93% of optimality on the average. Except for those problems having very high setup cost or problems with extreme seasonality, the algorithm produced solutions that were within 1 % of optimality on average.     

The general lotsizing and scheduling problem

The GLSP (GeneralLotsizing andSchedulingProblem) addresses the problem of integrating lotsizing and scheduling of several products on a single, capacitated machine. Continuous lotsizes, meeting deterministic, dynamic demands, are determined and scheduled with the objective of minimizing inventory holding costs and sequence-dependent setup costs. As the schedule is independent of predefined time periods, the GLSP generalizes known models using restricted time structures. Three variants of a local search algorithm, based onthreshold accepting, are presented. Computational tests show the effectiveness of these heuristic approaches and are encouraging for further extensions of the basic model.     

A heuristic approach for a multi-product capacitated lot-sizing problem with pricing

We address a multi-product capacitated lot-sizing problem with pricing. The objective is to maximise profit. The problem extends the multi-product capacitated lot-sizing problem (CLSP) found in the literature to include price as a decision variable, demand as a function of price, setup time, and more general holding costs. We present a heuristic procedure that can be used to solve large problem instances quickly with good solution quality. The results of computational testing are presented.     

The Dynamic Lot-Sizing Problem for Multiple Items Under Limited Capacity

This paper addresses the problem of scheduling the timing and quantities of production of n different products over m periods for a single production facility with a prespecified capacity. We assume that the demand is deterministic and can vary from one period to another and from one product to another. The objective is to minimize the sum of production setup and inventory holding costs. For medium-size problems, optimal solution algorithms do not yet exist and therefore heuristic solution algorithms are of interest. Most of the existing heuristics make use of the “forward-pass” concept in one way or the other. Forward pass means we begin by determining the lot sizes for earlier periods before moving to study the later periods. In this paper we study the forward-pass approach as well as a different solution approach which we call the four-step algorithm. We develop the feasibility conditions for pure forward-pass algorithms. Finally, we perform a comparative evaluation study.     

A simulated annealing approach to mixed-model sequencing with multiple objectives on a just-in-time line

This paper presents a Simulated Annealing based heuristic that simultaneously considers both setups and the stability of parts usage rates when sequencing jobs for production in a just-in-time environment. Varying the emphasis of these two conflicting objectives is explored. Several test problems are solved via the Simulated Annealing heuristic, and their objective function values are compared to solutions obtained via a Tabu Search approach from the literature. Comparison shows that the Simulated Annealing approach provides superior results to the Tabu Search approach. It is also found that the Simulated Annealing approach provides near-optimal solutions for smaller problems.     

An integrated preventive maintenance and production planning model with sequence‐dependent setup costs and times

This paper considers the integration of preventive maintenance and tactical production planning in a multiproduct production system, where setup costs and times are sequence dependent. A set of products needs to be produced in lots during a finite planning horizon, where preventive maintenance is conducted periodically at the end of some production periods and corrective maintenance is always performed when there is a failure. The system downtime—as caused by maintenance and setup—affects the system's available production capacity. We use a sequence‐oriented method to search for the optimal setup sequence and develop some steps to prune the searching tree. Our objective is to find the optimal preventive maintenance interval, production lot size, and production sequence in every period, by minimizing the sum of maintenance, production, inventory, and setup costs within the planning horizon. Numerical examples are presented to illustrate our model.     

Asynchronous teams for joint lot-sizing and scheduling problem in flow shops

The integrated production scheduling and lot-sizing problem in a flow shop environment consists of establishing production lot sizes and allocating machines to process them within a planning horizon in a production line with machines arranged in series. The problem considers that demands must be met without backlogging, the capacity of the machines must be respected, and machine setups are sequence-dependent and preserved between periods of the planning horizon. The objective is to determine a production schedule to minimise the setup, production and inventory costs. A mathematical model from the literature is presented, as well as procedures for obtaining feasible solutions. However, some of the procedures have difficulty in obtaining feasible solutions for large-sized problem instances. In addition, we address the problem using different versions of the Asynchronous Team (A-Team) approach. The procedures were compared with literature heuristics based on Mixed Integer Programming. The proposed A-Team procedures outperformed the literature heuristics, especially for large instances. The developed methodologies and the results obtained are presented.     

Multi Item Single Level Capacitated Dynamic Lotsizing Heuristics: A Computational Comparison (Part I: Static Case)

The multi item single level capacitated dynamic lotsizing problem consists of scheduling N items over a horizon of T periods. Demands are given and should be satisfied without backlogging. The objective is to minimize the sum of setup costs and inventory holding costs over the horizon subject to a constraint on total capacity in each period. Three simple heuristics from literature (Lambrecht and Vanderveken, Dixon and Silver, Dogramaci, Panayiotopoulos and Adam) are compared on a large set of test problems and their difference in performance is analyzed for various problem parameters.     

The impact of small lot ordering on traffic congestion in a physical distribution system

In recent years, some managers and researchers have advocated reducing lot sizes by decreasing setup costs, arguing that smaller lot sizes improve quality while reducing inventory levels and associated holding costs. However, smaller lot sizes result in an increased number of shipments which, in turn, exacerbates traffic congestion. This results in longer delivery times and, thereby, higher inventory levels. In this paper we study the relation between lot sizes and traffic congestion by constructing a model with numerous retailers who share a common congested delivery road. Using a numerical example, we illustrate the model's managerial implications with respect to several factors, including lot sizes, traffic congestion, and inventory levels. Our findings suggest that in a physical distribution system, if there are a relatively large number of retailers, no single retailer has an incentive to increase batch sizes because one retailer's effect on reducing traffic congestion will be negligible. If all retailers increase their lotsizes, however, traffic congestion will be reduced and all retailers will experience lower costs.     

A heuristic for production scheduling and inventory control in the presence of sequence-dependent setup times

The consideration of sequence-dependent setup times is one of the most difficult aspects of production scheduling problems. This paper reports on the development of a heuristic procedure to address a realistic production and inventory control problem in the presence of sequence-dependent setup times. The problem considers known monthly demands, variable production rates, holding costs, minimum and maximum inventory levels per product, and regular and overtime capacity limits. The problem is formulated as a Mixed-Integer Program (MIP), where subtour elimination constraints are needed to enforce the generation of job sequences in each month. By relaxing the subtour elimination constraints, the MIP formulation can be used to find a lower bound on the optimal solution. CPLEX 3.0 is used to calculate lower bounds for relatively small instances of this production problem, which are then used to assess the merit of a proposed heuristic. The heuristic is based on a simple short-term memory tabu search method that coordinates linear programming and traveling salesperson solvers in the search for optimal or near-optimal production plans.     

The G-group heuristic to solve the multi-product,sequencing, lot sizing and scheduling problem in flow shops

This paper presents a new heuristic to solve the problem of making sequencing, lot sizing and scheduling decisions for a number of products manufactured in a flow shop environment, so as to minimize the sum of setup and inventory holding costs while a given demand is fulfilled without backlogging. The proposed solution method first determines sequencing decisions then lot sizing and scheduling decisions are simultaneously determined. This heuristic, called the G-group method, divides the set of products into G groups and requires that products belonging to the same group have the same cycle time. Also, the cycle time of each group is restricted to be an integer multiple of a basic period. For each basic period of the global cycle, the products to be produced during this period and the production sequence to be used are chosen. Then, a non-linear program is solved to determine lot sizes and to construct a feasible production schedule. To evaluate its performance, the G-group method was compared to four other methods. Numerical results show that the proposed heuristic outperforms all these methods.     

Capacitated lot-sizing with sequence dependent setup costs

In this paper we consider a single-stage system where a number of different items have to be manufactured on one machine. Expenditures for the setups depend on the sequence in which items are scheduled on the machine. Holding costs are incurred for holding items in inventory. The demand of the items has to be satisfied without delay, i.e. shortages are not allowed. The objective is to compute a schedule such that the sum of holding and setup costs is minimized with respect to capacity constraints. For this problem which we call capacitated lot-sizing problem with sequence dependent setup costs (CLSD) we formulate a new model. The main differences between the new model and the discrete lot-sizing problem with sequence dependent setup costs (DLSDSD), introduced by Fleischmann, is that continuous lot-sizes are allowed and the setup state can be preserved over idle time. For the solution of the new model we present a heuristic which applies a priority rule. Since the priority values are affected by two significant parameters, we perform a local search in the parameter space to obtain low cost solutions. The solution quality is analyzed by a computational study. The comparison with optimal solutions of small instances shows that the solution quality of our heuristic is acceptable. The Fleischmann approach for the DLSPSD computes upper bounds for our new problem. On the basis of larger instances we show that our heuristic is more efficient to solve the CLSD.     

Setup cost reduction in an inventory model with finite-range stochastic lead times

Traditionally, upon solution, independent demand inventory models result in the determination of a closed form for the economic lot size. Generally, this is obtained from the result that holding costs and setup costs are constant and equal at the optimum. However, the experience of the Japanese indicates that this need not be the case. Specifically, setup cost may be reduced by investing in reduced setup times resulting in smaller lot sizes and increased flexibility. Various authors have investigated the impact of such investment on classical lot sizing formulas which has resulted in the derivation of modified relationships. A common assumption of this research has been that demand and lead time are deterministic. This paper extends this previous work by considering the more realistic case of investing in decreasing setup costs where lead time is stochastic. Closed form relationships for optimal lot size, optimal setup cost, optimal total cost, etc. are derived. Numerical results are presented for cases where lead times follow uniform and normal distributions. Sensitivity analysis is performed to indicate under what conditions investment is warranted.     

Joint lot-sizing and scheduling for multi-stage multi-product flow shops

Here we consider a multi-product flow shop under capacity constraints and develop an efficient heuristic procedure to determine joint lot sizes, production sequence and production schedule. We treat setup costs as fixed in the short run and thus independent of the number of setups. Loss of production capacity due to setup times is explicitly accounted for and the transfer of portions of a production lot between stages is permitted. The procedure is based on identifying the bottleneck workcentre and synchronizing production schedules at all other workcentres with the bottleneck workcentre such that product throughput requirements are met with minimal inventory costs. A compact procedure for constructing the Gantt charts is also presented. Conversion of the lot si2es and transfer batches into an information control system with kanbans is also presented.     

Strategic Allocation of Inspection Effort In A Serial, Multi-Product Production System

For a multi-stage production system, optimal location of inspection activities is an important consideration in minimizing the inspection-related and salvage costs. Set-up and inventory carrying costs also become important factors when several products are produced on the same line due to the product changeovers involved.

In this paper we discuss the effect of these additional costs (set-up and inventory carrying) on the inspection strategy, i.e., “all or none” versus partial inspection. We suggest a shortest path heuristic to determine the strategic location of inspection activities and the production lot sizes.     

Disaggregate Planning For Parallel Processors

Successful aggregate planning and effective production scheduling both rely heavily upon the availability of sound disaggregation procedures. This paper describes a large scale mathematical program that translates long range plans into operational assignments of labor, production and inventory among competing products and processes. The standard lot sizing problem, characterized by marginal tradeoffs between holding costs and setup costs, is constrained further as multiple processors compete for efficient assignments to individual products. The model's application in a major manufacturing corporation is described.