A hybrid approach for the capacitated lot sizing problem with setup carryover

The capacitated lot sizing problem with setup carryover deals with the issue of planning multiple products on a single machine. A setup can be carried over from one period to the next by incorporating the partial sequencing of the first and last product. This study proposes a novel hybrid approach by combining Genetic Algorithms (GAs) and a Fix-and-Optimise heuristic to solve the capacitated lot sizing problem with setup carryover. Besides this, a new initialisation scheme is suggested to reduce the solution space and to ensure a feasible solution. A comparative experimental study is carried out using some benchmark problem instances. The results indicate that the performance of the pure GAs improves when hybridised with the Fix-and-Optimise heuristic. Moreover, in terms of solution quality, promising results are obtained when compared with the recent results in the literature.     

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.     

A comparison of mixed integer programming formulations of the capacitated lot-sizing problem

We propose a novel mixed integer programming formulation for the capacitated lot-sizing problem with set-up times and set-up carryover. We compare our formulation to two earlier formulations, the Classical and Modified formulations, and a more recent formulation due to Suerie and Stadtler. Extensive computational experiments show that our formulation consistently outperforms the Classical and Modified formulations in terms of CPU time and solution quality. It is competitive with the Suerie–Stadtler (S&S) formulation, but outperforms all other formulations on the most challenging instances, those with low-capacity slack and a dense jobs matrix. We show that some of the differences in the performance of these various formulations arise from their different use of binary variables to represent production or set-up states. We also show that the LP relaxation of our Novel formulation provides a tighter lower bound than that of the Modified formulation. Our experiments demonstrate that, while the S&S formulation provides a much tighter LP bound, the Novel formulation is better able to exploit the intelligence of the CPLEX solution engine.     

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.     

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 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.     

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.     

The economic lot scheduling problem: a content analysis

The paper at hand addresses the Economic Lot Scheduling Problem (ELSP), which is concerned with finding a feasible and cost-minimal production schedule for multiple items produced in lots on a single machine. The ELSP started to attract the attention of researchers in the 1950s, where the focus was primarily on the development of simple heuristics for solving the problem. Over the subsequent decades, this topic has frequently been addressed in the literature, with the subject of research being the development of new scheduling policies or solution procedures or extensions of the scope of the original model. To date, a large number of journal articles has been published on the ELSP and its model variants. To identify key research themes, publication patterns and opportunities for future research, the paper at hand applies a content analysis to a sample of 242 papers published on the Economic Lot Scheduling Problem. The results of the content analysis indicate that prior research on this topic had a strong focus on the development of solution methodologies, and that several aspects that are directly connected to lot sizing and scheduling have not attracted much attention in research on the ELSP yet, such as, for example, energy cost and sustainability.     

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 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.     

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.     

Lot sizing in capacitated production planning and control systems

Current production planning and control (PPC) systems often separate material requirements from capacity planning. As a result, practitioners often complain about the infeasibility of production schedules regarding capacity, which causes long and unpredictable lead times and poor customers service. This paper describes a hierarchically structured PPC system that explicitly considers production capacity at each stage of the planning process. The impact of the certainty of demand data on the integration of lot sizing and sequencing decisions is discussed. A decision model for lot sizing applicable to changing demand data is proposed. It distinguishes between resources that are critical or uncritical with respect to batching decisions. Several currently available solution procedures are discussed and compared that support lot sizing decisions in multi-level production systems subject to multiple capacity constraints, setup times and dynamic demand rates.     

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.     

On the feasibility of sequence-dependent economic lot scheduling problem

Most of the literature dealing with the determination of cyclic part input sequences in a flexible flow system is restricted in that it only searches for input sequences that are permutations of the minimal part set (MPS). This study is unique in that it investigates input sequences generated by integer programming (IP) formulations that balance or unbalance machine workloads to help maximize overall machine utilization (Stecke 1992). Also, this study integrates the input sequence determination decision with the part mix ratio determination, within the overall framework of a flexible approach to FMS operation over time. A simulation model of a flexible flow system was designed to study the effects on overall machine utilizations caused by utilizing alternative part mix ratios to help determine input sequences. The procedures used to determine the part mix ratios include IP formulations and those that are generated randomly, including the MPS mix ratios. Three different experimental settings are used to test these effects as well as (I) the robustness of the part input sequences that can be derived from the IP generated mix ratios, and (2) the relative importance of the part mix ratio decision in relation to the part input sequence determination. A new FMS physical design that can also be easily modelled to capture look-ahead capability proved to be simple and effective. Several significant conclusions regarding part mix ratios, pan input sequences, and look-ahead capability are revealed. These include: (1) the determination of the part mix ratios proved to be more significant in improving FMS performance than the determination of part input sequences; (2) the robust nature of the IP formulations was demonstrated; and (3) look-ahead capability provides equally high overall machine utilizations at lower levels of work-in-process. Future research areas are presented that would help validate and extend the observations found in this study.     

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.     

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.     

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.     

Hybrid genetic algorithm for group technology economic lot scheduling problem

The concept of group technology has been successfully applied to many production systems, including flexible manufacturing systems. In this paper we apply group technology principles to the economic lot scheduling problem, which has been studied for over 40 years. We develop a heuristic algorithm and a hybrid genetic algorithm for the group technology economic lot scheduling problem. Numerical experiments show that the developed algorithms outperform the existing heuristics.