A framework for modelling setup carryover in the capacitated lot sizing problem

This paper addresses the single-level capacitated lot sizing problem (CLSP) with setup carryover. Specifically, we consider a class of production planning problems in which multiple products can be produced within a time period and significant setup times are incurred when changing from one product to another. Hence, there might be instances where developing a feasible schedule becomes possible only if setups are carried over from one period to another. We develop a modelling framework to formulate the CLSP with setup times and setup carryovers. We then extend the modelling framework to include multiple machines and tool requirements planning. The need for such a model that integrates both planning and lot sizing decisions is motivated by the existence of a similar problem in a paper mill. We apply the modelling framework to solve optimally, an instance of the paper mill's problem.     

Single machine multi-product capacitated lot sizing with sequence-dependent setups

In production planning in the glass container industry, machine-dependent setup times and costs are incurred for switch overs from one product to another. The resulting multi-item capacitated lot-sizing problem has sequence-dependent setup times and costs. We present two novel linear mixed-integer programming formulations for this problem, incorporating all the necessary features of setup carryovers. The compact formulation has polynomially many constraints, whereas the stronger formulation uses an exponential number of constraints that can be separated in polynomial time. We also present a five-step heuristic that is effective both in finding a feasible solution (even for tightly capacitated instances) and in producing good solutions to these problems. We report computational experiments.     

A note on modelling the capacitated lot-sizing problem with set-up carryover and set-up splitting

The capacitated lot-sizing problem with set-up carryover and set-up splitting (CLSP-SCSS) is formulated as a mixed integer linear program. We define set-up carryover as the production of a product that is continued over from one period to another without incurring an extra set-up. Set-up splitting occurs when the set-up for a product is started at the end of a period and completed at the beginning of the next period. We allow product dependent set-ups. Initial experimentation highlights the importance of including set-up splitting in the CLSP model. In 12 out of the 18 problem instances tested, our model yielded better solutions or removed infeasibility when compared with a CLSP model without set-up splitting.     

Integrating run-based preventive maintenance into the capacitated lot sizing problem with reliability constraint

A joint model for integrating run-based preventive maintenance (PM) into the capacitated lot sizing problem (CLSP) is proposed, in which the production system is subject to deterioration with usage and PM operations are implemented to restore the system. In this model, both production and PM operations are restricted by the system's maximum capacity, and the system reliability has to be maintained above a threshold value throughout the planning horizon. By linearisation of the reliability constraints, the problem is formulated as a mixed-integer linear programming. An explanatory example is given to illustrate the advantage of the joint model comparing with the interval-based PM policy in terms of system's overall cost. A three-stage heuristic is proposed to solve this integrated model, which includes a Lagrangian-based heuristic for the CLSP. The numerical experiments are conducted to evaluate the performance of the developed heuristics and the computational results show that the heuristics can provide good feasible solutions for the corresponding models. The discussion of the results is finally given in detail.     

The capacitated lot sizing problem with setup carry-over

Although there is a significant amount of literature on the capacitated lot sizing problem, there has been insufficient consideration of planning problems in which it is possible for a lot size, or production run, to continue over consecutive time periods without incurring multiple setups. While there are papers that consider this feature, they typically restrict production to at most one product in each period. We present a set of mixed integer linear programs for the capacitated lot sizing problem that incorporate setup carry-over without restricting the number of products produced in each time period. Efficient reformulations are developed for finding optimal solutions, and a Lagrangian decomposition heuristic is provided that quickly generates near-optimal solutions. The computational results demonstrate that incorporating setup carry-over has a significant effect on both cost and lot sizes.     

The capacitated lot sizing problem with overtime decisions and setup times

The Capacitated Lot Sizing-Problem (CLSP) consists of planning the lot sizes of multiple items over a planning horizon with the objective of minimizing setup and inventory holding costs. In each period that an item is produced a setup cost is incurred. Capacity is limited and homogeneous. Here, the CLSP is extended to include overtime decisions and capacity consuming setups. The objective function consists of minimizing inventory holding and overtime costs. Setups incur costs implicitly via overtime costs, that is, they lead to additional overtime costs when setup times contribute to the use of overtime capacity in a certain period. The resulting problem becomes more complicated than the standard CLSP and requires methods different from the ones proposed for the latter. Consequently, new heuristic approaches are developed to deal with this problem. Among the heuristic approaches are the classical HPP approach and its modifications, an iterative approach omitting binary variables in the model, a Genetic Algorithm approach based on the transportation-like formulation of the single item production planning model with dynamic demand and a Simulated Annealing approach based on shifting family lot sizes among consecutive periods. Computational results demonstrate that the Simulated Annealing approach produces high quality schedules and is computationally most efficient.     

A note on capacitated lot sizing with setup carry over

The “capacitated lot sizing problem with setup carry over” is based on the well known “capacitated lot sizing problem” and incorporates the possibility of preserving a setup state between successive periods. The approach at hand is to decompose the problem using Lagrangean relaxation. Subproblems are to be solved optimally employing dynamic programming techniques. Subgradient optimization guides the approach to heuristic solutions of the original problem. The present paper shows that this algorithm does not necessarily provide the optimal solution to the subproblems. The algorithm's flaw is corrected such that it allows to solve the subproblems optimally.     

A dynamic method for the production lot sizing with machine failures

This paper presents a dynamic method to deal with two economic lot sizing models with exponential machine failures. Its main difference from the static method is that the machine failure is separately treated from the perspective of failure realisation. The optimal lot size is derived through the equation between the incurred average cost and the marginal cost, which has to be performed for each lot due to the random failures. In the first no-resumption model, the simulation shows that two methods have the similar performance as the lot number increases. For the resumable model, we propose a zero-inventory resumption policy that always resumes the production after each machine failure but delays the resumption until the on-hand inventory is depleted. The simulation result indicates that the new policy by the dynamic method outperforms the initial abort/resume policy, and it also shows the convergence as the production continues.     

A dynamic lot sizing problem with multiple customers: customer-specific shipping and backlogging costs

This paper considers a dynamic lot sizing problem faced by a producer who supplies a single product to multiple customers. Characterized by their backorder costs as well as shipping costs, a customer with a high backorder cost has a greater need for the product than a customer with a low backorder cost. We show that the general problem with time-varying customer-dependent backlogging and shipping costs is NP-hard in the strong sense. We then develop an efficient dynamic programming algorithm for an important instance of the problem when there is no speculative motive for backlogging. We also establish forecast horizon results for the case of stationary production and shipping costs, which help the decision maker determine a proper forecast horizon in a rolling-horizon planning process.     

A time-varying lot sizes approach for the economic lot scheduling problem with returns

We consider the economic lot scheduling problem with returns by assuming that each item is returned by a constant rate of demand. The goal is to find production frequencies, production sequences, production times, as well as idle times for several items subject to returns at a single facility. We propose a heu ristic algorithm based on a time-varying (TV) lot sizes approach. The problem is decomposed into two distinct portions: in the first, we find a combinatorial part (production frequencies and sequences) and in the second, we determine a continuous part (production and idle times) in a specific production sequence. We report computational results that show that, in many cases, the proposed TV lot sizes approach with consideration of returns yields a relatively minor error.     

Mathematical models for capacitated multi-level production planning problems with linked lot sizes

Various mixed-integer programming models have been proposed for solving the capacitated multi-level lot sizing problem with linked lot sizes. It would be of value for researchers and practitioners to know which of these models is the most efficient under different circumstances. To investigate the comparative efficiencies associated with these models, this paper therefore demonstrates theoretically the relationships between these models when the integrality requirement is relaxed for any subset of binary setup and setup-carryover variables, shows the relative effectiveness of these models in obtaining lower bound solutions associated with linear programming relaxations, and evaluates the relative computational resources and the time needed when using these models through intensive computational tests. These theoretical and numerical results are expected to provide significant guidelines for choosing an effective formulation for different situations.     

Capacitated dynamic lot sizing with capacity acquisition

One of the fundamental problems in operations management is determining the optimal investment in capacity. Capacity investment consumes resources and the decision, once made, is often irreversible. Moreover, the available capacity level affects the action space for production and inventory planning decisions directly. In this article, we address the joint capacitated lot-sizing and capacity-acquisition problems. The firm can produce goods in each of the finite periods into which the production season is partitioned. Fixed as well as variable production costs are incurred for each production batch, along with inventory carrying costs. The production per period is limited by a capacity restriction. The underlying capacity must be purchased up front for the upcoming season and remains constant over the entire season. We assume that the capacity acquisition cost is smooth and convex. For this situation, we develop a model which combines the complexity of time-varying demand and cost functions and of scale economies arising from dynamic lot-sizing costs with the purchase cost of capacity. We propose a heuristic algorithm that runs in polynomial time to determine a good capacity level and corresponding lot-sizing plan simultaneously. Numerical experiments show that our method is a good trade-off between solution quality and running time.     

Stochastic economic lot sizing and scheduling problem with pitch interval,reorder points and flexible sequence

This paper presents a solution for a class of the stochastic economic lot sizing scheduling problem that is typical of the replenishment pull system proposed by the lean manufacturing approach. In this class, lots of any product are produced in fixed intervals called pitch. The proposed solution uses flexible production sequences and reorder points that are compatible with the concepts of supermarket and level production. It adopts the queuing discipline obtained from a fluid model that approximates the stochastic process of arrival and production orders. Given the queuing discipline, an iterative algorithm returns a near-optimal solution for the system. The proposed approach allows us possible to differentiate inventory cost and service levels by product, and the stock required is lower than that required by the discipline ‘first stock out, first out’. The algorithm is fast and stable, allowing its frequent use in real-world instances.     

Multi-period lot sizing and job shop scheduling with compressible process times for multilevel product structures

This paper presents mathematical modelling of joint lot sizing and scheduling problem in job shop environment under a set of working conditions. The main feature of the problem is to deal with flexible machines able to change their working speeds, known as process compressibility. Furthermore, produced items should be assembled together to make final products. In other words, the products have a multilevel structure, shown with bill of materials. As the problem is proved to be strongly NP-hard, it is solved by a memetic algorithm here. Computational experiences on the data of ‘Mega Motor’ company are reported. Also, further experiences on random test data confirm the performance of the proposed method with less than 5.02% optimality gap while solving the problems in very shorter times than CPLEX 12.0.     

An optimal integrated lot sizing and maintenance strategy for multi-machines system with energy consumption

This paper proposes an integrated model for multi-machines dynamic lot sizing aiming to produce a single item, considering the energy consumption during the production horizon. The objective is to find, firstly, the optimal lot size as well as the number of machines that satisfy a random demand under given service level and secondly, maintenance plan depended to production planning to minimise the total production, energy and maintenance costs. In fact, the problem of energy consumption is one of the most evoked topics especially with the decision of many governments to reduce theirs (For example France is willing to reduce the total consumption by 20% by 2020). The keys of this study are to consider, firstly, the correlation between the forecasting of demand, the variation of the working machines as well as their production rates under energy constraint and secondly the correlation between the production cadences and the maintenance strategy of all machines.     

A hybrid genetic algorithm for flowshop lot streaming with setups and variable sublots

Lot streaming is the process of splitting a given lot or job to allow the overlapping of successive operations in flowshops or multi-stage manufacturing systems to reduce manufacturing lead time. Recent literature shows that significant lead time improvement is possible if variable sublots, instead of equal or consistent sublots, are used when production setup time is considered. However, lot streaming problems with variable sublots are difficult to solve to optimality using off-shelf optimisation packages even for problems of small and experimental sizes. Thus, efficient solution procedures are needed for solving such problems for practical applications. In this paper, we develop a mathematical programming model and a hybrid genetic algorithm for solving n-job m-machine lot streaming problems with variable sublots considering setup times. The preliminary computational results are encouraging.     

Stochastic lot sizing for maximisation of shareholder wealth in make-to-order manufacturing

Current research in production planning focuses mainly on optimising operational objectives, taking little consideration of the primary principle of corporate governance and investor interests. Such approaches often overlook the critical roles of the cost structure and financial position of a firm, rendering the optimisation results unreliable. This paper studies stochastic lot sizing optimisation in make-to-order manufacturing, with an aim to maximise the full investor interests, well known as shareholder wealth. It presents a relatively simple yet reliable lead time model based on probability theory and stochastic processes. Moreover, the impacts of macroeconomic factors are examined to seek potential drivers for shareholder wealth. Theoretical optimality properties are proved to validate the effectiveness of the proposed model in dealing with batch production planning. Numerical examples and analytical results are presented to illustrate the significance of considering such economic and financial constraints and shareholder wealth. These results highlight that the proposed model can help improve shareholder wealth, and that it is a useful tool for examining the potential challenges and opportunities of shareholder wealth creation in production planning.     

Heuristics for the N-product,M-stage,economic lot sizing and scheduling problem with dynamic demand

This paper presents a new composite heuristics approach for solving the N-product, M-stage lot sizing and scheduling problem with dynamic demands and limited production capacity. The first phase of these composite heuristics aims at finding a feasible solution. This solution is such that for each period and for each product, the lot size equals the net demand of the considered period plus the demand of a number of upcoming periods. If capacity does not satisfy all demands of a given period, we try to find earlier periods where we can produce the missing units. The second phase is an improvement procedure which recursively attempts to move back each lot, provided that it is both more economical to do so and capacity feasible. We also provide two variants of this heuristic to handle the case where production capacity can be increased by using overtime. Overtime is a usual practice in real life which, in many cases, allows a reduction of the overall cost. The first variant constructs the initial solution without recourse to overtime and introduces overtime only during the solution improvement phase. The second one considers overtime during both the first and second phases. The performance of the proposed heuristics is numerically assessed and the most efficient ones are identified.     

A note on “The general lot sizing and scheduling problem”

Fleischmann and Meyr (1997) develop a model for the lot sizing problem with sequence dependent setup costs. In this note we show that this model is limited to the case where production state between two consecutive periods is conserved only if the available capacity of the preceding period exceeds the minimum batch quantity. We generalize the model by modification.This complete issue was revised and published online in November 2004. The previous version contained a false date. Correspondence to: Haldun Süral