Hybrid heuristics for the multi-stage capacitated lot sizing and loading problem

The multi-stage capacitated lot sizing and loading problem (MCLSLP) deals with the issue of determining the lot sizes of product items in serially-arranged manufacturing stages and loading them on parallel facilities in each stage to satisfy dynamic demand over a given planning horizon. It is assumed that regular time capacity decisions have already been made in the tactical level and allocated to the stages, but it is still an important decision problem whether to augment regular time capacity by overtime capacity. Each item may be processed on a technologically feasible subset of existing facilities with different process and setup times on each facility. Since the solution of the MCLSLP requires the design of a powerful algorithm, simulated annealing (SA) and genetic algorithms (GA) are integrated to enhance their individual performances. Furthermore, these global optimisation methods are incorporated into a Lagrangean relaxation scheme, hence creating a hybrid solution methodology. Numerical results obtained using these methods confirm the mutual benefits of integrating different solution techniques.     

A multi-class multi-level capacitated lot sizing model

When demand loading is higher than available capacity, it takes a great deal of effort for a traditional MRP system to obtain a capacity-feasible production plan. Also, the separation of lot sizing decisions and capacity requirement planning makes the setup decisions more difficult. In a practical application, a production planning system should prioritize demands when allocating manufacturing resources. This study proposes a planning model that integrates all MRP computation modules. The model not only includes multi-level capacitated lot sizing problems but also considers multiple demand classes. Each demand class corresponds to a mixed integer programming (MIP) problem. By sequentially solving the MIP problems according to their demand class priorities, this proposed approach allocates finite manufacturing resources and generates feasible production plans. In this paper we experiment with three heuristic search algorithms: (1) tabu search; (2) simulated annealing, and (3) genetic algorithm, to solve the MIP problems. Experimental designs and statistical methods are used to evaluate and analyse the performance of these three algorithms. The results show that tabu search and simulated annealing perform best in the confirmed order demand class and forecast demand class, respectively.     

Solving the capacitated lot-sizing problem with backorder consideration

In this research, we formulate and solve a type of the capacitated lot-sizing problem. We present a general model for the lot-sizing problem with backorder options, that can take into consideration various types of production capacities such as regular time, overtime and subcontracting. The objective is to determine lot sizes that will minimize the sum of setup costs, holding cost, backorder cost, regular time production costs, and overtime production costs, subject to resource constraints. Most existing formulations for the problem consider the special case of the problem where a single source of production capacity is considered. However, allowing for the use of alternate capacities such as overtime is quite common in many manufacturing settings. Hence, we provide a formulation that includes consideration of multiple sources of production capacity. We develop a heuristic based on the special structure of fixed charge transportation problem. The performance of our algorithm is evaluated by comparing the heuristic solution value to lower bound value. Extensive computational results are presented.     

MIP models for production lot sizing problems with distribution costs and cargo arrangement

This study presents mixed integer programming (MIP) models for production lot sizing problems with distribution costs using unit load devices such as pallets and containers. Problems that integrate production lot sizing decisions and loading of the products in vehicles (bins) are also modelled, in which constraints such as weight limits, volume restrictions or the value of the cargo loaded in the bins are considered. In general, these problems involve a trade-off between production, inventory and distribution costs. Lot sizing decisions should take into account production capacity and product demand constraints. Distribution decisions are related to the loading and transport of products in unit load devices. The MIP models are solved by the branch-and-cut method of an optimization package and the results show that these approaches have the potential to address different practical situations.     

Pricing,relaxing and fixing under lot sizing and scheduling

We present a novel mathematical model and a mathematical programming based approach to deliver superior quality solutions for the single machine capacitated lot sizing and scheduling problem with sequence-dependent setup times and costs. The formulation explores the idea of scheduling products based on the selection of known production sequences. The model is the basis of a matheuristic, which embeds pricing principles within construction and improvement MIP-based heuristics. A partial exploration of distinct neighborhood structures avoids local entrapment and is conducted on a rule-based neighbor selection principle. We compare the performance of this approach to other heuristics proposed in the literature. The computational study carried out on different sets of benchmark instances shows the ability of the matheuristic to cope with several model extensions while maintaining a very effective search. Although the techniques described were developed in the context of the problem studied, the method is applicable to other lot sizing problems or even to problems outside this domain.     

Capacitated dynamic lot sizing problems in closed-loop supply chain

In this paper, we address the capacitated dynamic lot sizing problem arising in closed-loop supply chain where returned products are collected from customers. These returned products can either be disposed or be remanufactured to be sold as new ones again; hence the market demands can be satisfied by either newly produced products or remanufactured ones. The capacities of production, disposal and remanufacturing are limited, and backlogging is not allowed. A general model of this problem is formulated, and several useful properties of the problem are characterized when cost functions are concave. Moreover, this problem is analyzed and solved to optimality using dynamic programming algorithms under different scenarios. It is shown that the problem with only disposal or remanufacturing can be converted into a traditional capacitated lot sizing problem and be solved by a polynomial algorithm if the capacities are constant. A pseudo-polynomial algorithm is proposed for the problem with both capacitated disposal and remanufacturing. The problem with capacitated production and remanufacturing and the problem with uncapacitated production and capacitated remanufacturing are also analyzed and solved. Through numerical experiments we show that the proposed algorithms perform well when solving problems of practical sizes. From the experimental results also indicates that it is worthwhile to expand the remanufacturing capacity only when returned products exist in a relatively long planning horizon, and production capacities have little effect on the remanufacturing plan when the demand is mainly satisfied by the production.     

Reformulation and a Lagrangian heuristic for lot sizing problem on parallel machines

We consider the capacitated lot sizing problem with multiple items, setup time and unrelated parallel machines. The aim of the article is to develop a Lagrangian heuristic to obtain good solutions to this problem and good lower bounds to certify the quality of solutions. Based on a strong reformulation of the problem as a shortest path problem, the Lagrangian relaxation is applied to the demand constraints (flow constraint) and the relaxed problem is decomposed per period and per machine. The subgradient optimization method is used to update the Lagrangian multipliers. A primal heuristic, based on transfers of production, is designed to generate feasible solutions (upper bounds). Computational results using data from the literature are presented and show that our method is efficient, produces lower bounds of good quality and competitive upper bounds, when compared with the bounds produced by another method from the literature and by high-performance MIP software.     

A Lagrangian-based heuristic for the capacitated lot-sizing problem in parallel machines

This paper addresses the capacitated lot-sizing problem involving the production of multiple items on unrelated parallel machines. A production plan should be determined in order to meet the forecast demand for the items, without exceeding the capacity of the machines and minimize the sum of production, setup and inventory costs. A heuristic based on the Lagrangian relaxation of the capacity constraints and subgradient optimization is proposed. Initially, the heuristic is tested on instances of the single machine problem and results are compared with heuristics from the literature. For parallel machines and small problems the heuristic performance is tested against optimal solutions, and for larger problems it is compared with the lower bound provided by the Lagrangian relaxation.     

An approach for integrated scheduling and lot-sizing

In this paper a non time discrete approach is developed for an integrated planning procedure, applied to a multi-item capacitated production system with dynamic demand. The objective is to minimize the total costs, which consist of holding and setup costs for one period. The model does not allow backlog. Furthermore, a production rate of zero or full capacity is the only possibility. The result is a schedule, lot-sizes and the sequences for all lots. The approach is based on a specific property of the setup cost function, which allows for replacement of the integer formulation for the number of setup activities in the model. In a situation where the requirements for the multi-item continuous rate economic order quantity, the so-called economic production lot (EPL) formula, are fulfilled, both the EPL as well as the presented model results are identical for the instances dealt with. Moreover, with the new model problems with an arbitrary demand can be solved.     

On the equivalence of strong formulations for capacitated multi-level lot sizing problems with setup times

Several mixed integer programming formulations have been proposed for modeling capacitated multi-level lot sizing problems with setup times. These formulations include the so-called facility location formulation, the shortest route formulation, and the inventory and lot sizing formulation with (?, S) inequalities. In this paper, we demonstrate the equivalence of these formulations when the integrality requirement is relaxed for any subset of binary setup decision variables. This equivalence has significant implications for decomposition-based methods since same optimal solution values are obtained no matter which formulation is used. In particular, we discuss the relax-and-fix method, a decomposition-based heuristic used for the efficient solution of hard lot sizing problems. Computational tests allow us to compare the effectiveness of different formulations using benchmark problems. The choice of formulation directly affects the required computational effort, and our results therefore provide guidelines on choosing an effective formulation during the development of heuristic-based solution procedures.     

A Lot-sizing Model for Just-in-time Manufacturing

We consider the problem of determining lot sizes of multiple items that are manufactured by a single capacitated facility. The manufacturing facility may represent a bottleneck processing activity on the shop floor or a storeroom that provides components to the shop floor. Items flow from the facility to a downstream facility, where they are assembled according to a specified mix. Just-in-time (JIT) manufacturing requires a balanced flow of items, in the proper mix, between successive facilities. Our model determines lot sizes of the various items based on available capacity and four attributes of each item: demand rate, holding cost, set-up time and processing time. Holding costs for each item accrue until the appropriate mix of items is available for shipment downstream. We develop a lot-sizing heuristic that minimizes total holding cost per time unit over all items, subject to capacity availability and the required mix of items.     

Improved lower bounds for the capacitated lot sizing problem with setup times

We present new lower bounds for the capacitated lot sizing problem, applying decomposition to the network reformulation. The demand constraints are the linking constraints and the problem decomposes into subproblems per period containing the capacity and setup constraints. Computational results and a comparison to other lower bounds are presented.     

The convex hull of two core capacitated network design problems

The network loading problem (NLP) is a specialized capacitated network design problem in which prescribed point-to-point demand between various pairs of nodes of a network must be met by installing (loading) a capacitated facility. We can load any number of units of the facility on each of the arcs at a specified arc dependent cost. The problem is to determine the number of facilities to be loaded on the arcs that will satisfy the given demand at minimum cost.This paper studies two core subproblems of the NLP. The first problem, motivated by a Lagrangian relaxation approach for solving the problem, considers a multiple commodity, single arc capacitated network design problem. The second problem is a three node network; this specialized network arises in larger networks if we aggregate nodes. In both cases, we develop families of facets and completely characterize the convex hull of feasible solutions to the integer programming formulation of the problems. These results in turn strengthen the formulation of the NLP.Research of this author was supported in part by a Faculty Grant from the Katz Graduate School of Business, University of Pittsburgh.     

Capacitated Lot Sizing for Injection Moulding: A Case Study

This paper considers the medium-term production smoothing problem for the injection moulding department of a Belgian firm. The problem is formulated as a series of one machine capacitated dynamic lot sizing problems, which are then solved by heuristic procedures. Computational results for real-life data are presented. It follows that the capacitated lot sizing approach succeeds in smoothing production such that subcontracting, which was often necessary with the E.O.Q. approach used by the firm, could be avoided in the future. Moreover, total set-up and inventory costs are reduced by about 20%.     

Multi-plant production planning in capacitated self-configuring two-stage serial systems

This research deals with a capacitated master production planning and capacity allocation problem for a multi-plant manufacturing system with two serial stages in each plant. We consider both cases in which a decoupling buffer is allowed or not between the two stages. Peculiar to the system considered is the capability of dynamically self-configuring its layout when buffering is disallowed, in the sense that, for each production run, different parallel machines in the second stage are grouped together and serially connected to a machine in the first stage. Although setup times and costs are considered negligible in our model, yet binary setup variables are introduced in order to account for minimum lot-sizes. The resulting mixed {0,1} linear programming model is solved by means of LP-based heuristic algorithms. The proposed modeling and solution procedure has been applied to problem instances originating from a real-world application, showing good results in practice.     

Capacitated lot-sizing with extensions: a review

The capacitated lot-sizing problem (CLSP) is a standard formulation for big bucket lot-sizing problems with a discrete period segmentation and deterministic demands. We present a literature review on problems that incorporate one of the following extensions in the CLSP: back-orders, setup carry-over, sequencing, and parallel machines. We illustrate model formulations for each of the extensions and also mention the inclusion of setup times, multi-level product structures and overtime in a study. For practitioners, this overview allows to check the availability of successful solution procedures for a specific problem. For scientists, it identifies areas that are open for future research.      

A Profit-maximizing Plant-loading Model with Demand Fill-rate Constraints

This paper discusses a new formulation of a class of plant product-mix loading problems which are characterized by capacitated production facilities, demand fill-rate requirements, fixed facility costs, concave variable production costs and an integrated network structure which encompasses inbound supply and outbound distribution flows. In particular, we are interested in assigning product lines and volumes to a set of capacitated plants under the demand fill-rate constraints. Fixed costs are incurred when a product line is assigned to a plant. The variable production-cost function also exhibits concavity with respect to each product-line volume. Thus both scale economies and plant focus effect are considered explicitly in the model. The model also can be used to determine which market to serve in order to best allocate the firm's resources. The problem formulation leads to a concave mixed-integer mathematical programme. Given the state of the art of non-linear programming techniques, it is often not possible to find global optima for reasonably sized problems. We develop an optimization algorithm within the framework of Benders' decomposition for the case of a piecewise linear concave cost function. Our algorithm generates optimal solutions efficiently.     

A new lot sizing and scheduling heuristic for multi-site biopharmaceutical production

Biopharmaceutical manufacturing requires high investments and long-term production planning. For large biopharmaceutical companies, planning typically involves multiple products and several production facilities. Production is usually done in batches with a substantial set-up cost and time for switching between products. The goal is to satisfy demand while minimising manufacturing, set-up and inventory costs. The resulting production planning problem is thus a variant of the capacitated lot-sizing and scheduling problem, and a complex combinatorial optimisation problem. Inspired by genetic algorithm approaches to job shop scheduling, this paper proposes a tailored construction heuristic that schedules demands of multiple products sequentially across several facilities to build a multi-year production plan (solution). The sequence in which the construction heuristic schedules the different demands is optimised by a genetic algorithm. We demonstrate the effectiveness of the approach on a biopharmaceutical lot sizing problem and compare it with a mathematical programming model from the literature. We show that the genetic algorithm can outperform the mathematical programming model for certain scenarios because the discretisation of time in mathematical programming artificially restricts the solution space.     

Capacitated lot sizing and scheduling with parallel machines and shared buffers: A case study in a packaging company

The aim of this work is to propose a solution approach for a capacitated lot sizing and scheduling real problem with parallel machines and shared buffers, arising in a packaging company producing yoghurt. The problem has been formulated as a hybrid Continuous Set-up and Capacitated Lot Sizing Problem (CSLP–CLSP). A new effective two stage optimisation heuristic based on the decomposition of the problem into a lot sizing problem and a scheduling problem has been developed. An assignment of mixture to buffers is made in the first stage, and therefore the corresponding orders are scheduled on the production lines by performing a local search. Computational tests have been performed on the real data provided by the company. The heuristic exhibits near-optimal solutions, all obtained in a very short computational time.     

GRASP heuristic with path-relinking for the multi-plant capacitated lot sizing problem

This paper addresses the independent multi-plant, multi-period, and multi-item capacitated lot sizing problem where transfers between the plants are allowed. This is an NP-hard combinatorial optimization problem and few solution methods have been proposed to solve it. We develop a GRASP (Greedy Randomized Adaptive Search Procedure) heuristic as well as a path-relinking intensification procedure to find cost-effective solutions for this problem. In addition, the proposed heuristics is used to solve some instances of the capacitated lot sizing problem with parallel machines. The results of the computational tests show that the proposed heuristics outperform other heuristics previously described in the literature. The results are confirmed by statistical tests.