An FPTAS for a single-item capacitated economic lot-sizing problem with monotone cost structure

We present a fully polynomial time approximation scheme (FPTAS) for a capacitated economic lot-sizing problem with a monotone cost structure. An FPTAS delivers a solution with a given relative error ɛ in time polynomial in the problem size and in 1/ɛ. Such a scheme was developed by van Hoesel and Wagelmans [8] for a capacitated economic lot-sizing problem with monotone concave (convex) production and backlogging cost functions. We omit concavity and convexity restrictions. Furthermore, we take advantage of a straightforward dynamic programming algorithm applied to a rounded problem.     

Solving the CLSP by a Tabu Search Heuristic

The multi-item, single-level, capacitated, dynamic lot-sizing problem, commonly abbreviated as CLSP, is considered. The problem is cast in a tight mixed-integer programming model (MIP); tight in the sense that the gap between the optimal value of MIP and that of its linear programming relaxation (LP) is small. The LP relaxation of MIP is then solved by column generation. The resulting feasible solution is further improved by adopting the corresponding set-up schedule and re-optimizing variable costs by solving a minimum-cost network flow (trans-shipment) problem. Subsequently, the improved solution is used as a starting solution for a tabu search procedure, with the worth of moves assessed using the same trans-shipment problem. Results of computational testing of benchmark problem instances are presented. They show that the heuristic solutions obtained are effective, in that they are extremely close to the best known solutions. The computational efficiency makes it possible to solve realistically large problem instances routinely on a personal computer; in particular, the solution procedure is most effective, in terms of solution quality, for larger problem instances.     

Efficient Solution of the Single-item,Capacitated Lot-sizing Problem with Start-up and Reservation Costs

A capacitated dynamic lot-sizing model, where the costs incurred are a start-up cost for switching the production facility on and another reservation cost for keeping the facility on, whether or not it is producing, is considered. The resulting scheduling problem is NP-hard. An efficient shortest path model of the uncapacitated version of the problem is developed. This model is then included, via a redefinition of variables, into a tight capacitated model; tight in the sense that sharp lower bounds can be produced from it. The lower bound problems are solved efficiently by recovering the shortest path structure through column generation, and effective upper bounds are generated by solving a small capacitated trans-shipment problem. The results of computational tests to verify the computational efficiency of the resulting solution scheme are presented.     

A single-item economic lot-sizing problem with a non-uniform resource: Approximation

We study a generalization of the classical single-item capacitated economic lot-sizing problem to the case of a non-uniform resource usage for production. The general problem and several special cases are shown to be non-approximable with any polynomially computable relative error in polynomial time. An optimal dynamic programming algorithm and its approximate modification are presented for the general problem. Fully polynomial time approximation schemes are developed for two NP-hard special cases: (1) cost functions of total production are separable and holding and backlogging cost functions are linear with polynomially related slopes, and (2) all holding costs are equal to zero.     

Algorithms for Capacitated,Multi-Item Lot-Sizing without Set-Ups

The multi-item lot-sizing problem considered here is concerned with finding the lot sizes over a horizon of discrete time periods to meet known future demand without incurring backlogs, such that the total cost of production and inventory holding is minimized. The capacity constraints arise because the production of each item consumes capacitated production resources at a given rate. Production is assumed to occur without set-ups. The problem is formulated as a capacitated trans-shipment problem. Use of modern, minimum-cost network flow algorithms, coupled with appropriate starting procedures, allows realistically large problem instances to be solved efficiently; thus obviating the need for specialized algorithms based on restrictive assumptions regarding cost structures.     

A hybrid tabu search based heuristic for the periodic distribution inventory problem with perishable goods

Most of the research on integrated inventory and routing problems ignores the case when products are perishable. However, considering the integrated problem with perishable goods is crucial since any discrepancy between the routing and inventory cost can double down the risk of higher obsolescence costs due to the limited shelf-life of the products. In this paper, we consider a distribution problem involving a depot, a set of customers and a homogeneous fleet of capacitated vehicles. Perishable goods are transported from the depot to customers in such a way that out-of-stock situations never occur. The objective is to simultaneously determine the inventory and routing decisions over a given time horizon such that total transportation cost is minimized. We present a new “arc-based formulation” for the problem which is deemed more suitable for our new tabu search based approach for solving the problem. We perform a thorough sensitivity analysis for each of the tabu search parameters individually and use the obtained gaps to fine-tune the parameter values that are used in solving larger sized instances of the problem. We solve different sizes of randomly generated instances and compare the results obtained using the tabu search algorithm to those obtained by solving the problem using CPLEX and a recently published column generation algorithm. Our computational experiments demonstrate that the tabu search algorithm is capable of obtaining a near-optimal solution in less computational time than the time required to solve the problem to optimality using CPLEX, and outperforms the column generation algorithm for solving the “path flow formulation” of the problem in terms of solution quality in almost all of the considered instances.     

A composite very large-scale neighborhood structure for the capacitated minimum spanning tree problem

The capacitated minimum spanning tree (CMST) problem is to find a minimum cost spanning tree in a network where nodes have specified demands, with an additional capacity constraints on the subtrees incident to a given source node s. The capacitated minimum spanning tree problem arises as an important subproblem in many telecommunication network design problems. In a recent paper, Ahuja et al. (Math. Program. 91 (2001) 71) proposed two very large-scale neighborhood search algorithms for the capacitated minimum spanning tree problem. Their first node-based neighborhood structure is obtained by performing multi-exchanges involving several trees where each tree contributes a single node. Their second tree-based neighborhood structure is obtained by performing multi-exchanges where each tree contributes a subtree. The computational investigations found that node-based multi-exchange neighborhood gives the best performance for the homogenous demand case (when all nodes have the same demand), and the tree-based multi-exchange neighborhood gives the best performance for the heterogeneous demand case (when nodes may have different demands). In this paper, we propose a composite neighborhood structure that subsumes both the node-based and tree-based neighborhoods, and outperforms both the previous neighborhood search algorithms for solving the capacitated minimum spanning tree problem on standard benchmark instances. We also develop improved dynamic programming based exact algorithms for searching the composite neighborhood.     

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.     

HOPS – Hamming-Oriented Partition Search for production planning in the spinning industry

In this paper, we investigate a two-stage lot-sizing and scheduling problem in a spinning industry. A new hybrid method called HOPS (Hamming-Oriented Partition Search), which is a branch-and-bound based procedure that incorporates a fix-and-optimize improvement method is proposed to solve the problem. An innovative partition choice for the fix-and-optimize is developed. The computational tests with generated instances based on real data show that HOPS is a good alternative for solving mixed integer problems with recognized partitions such as the lot-sizing and scheduling problem.     

Optimal solutions for the economic lot-sizing problem with multiple suppliers and cost structures

This paper considers a multi-supplier economic lot-sizing problem in which the retailer replenishes his inventory from several suppliers. Each supplier is characterized by one of three types of order cost structures: incremental quantity discount cost structure, multiple set-ups cost structure and all-unit quantity discount cost structure. The problem is challenging due to the mix of different cost structures. For all cases of the problem where each supplier is characterized by one of the first two cost structures, some optimality properties are proposed and optimal algorithms based on dynamic programming are designed. For the case where all suppliers are characterized by all-unit quantity discount cost structures, it is hard to design a polynomial time algorithm by the analyzed optimal properties. However, it is proved that one of its special cases can be solved in polynomial time.     

Lower and upper bounds for location-arc routing problems with vehicle capacity constraints

This paper addresses multi-depot location arc routing problems with vehicle capacity constraints. Two mixed integer programming models are presented for single and multi-depot problems. Relaxing these formulations leads to other integer programming models whose solutions provide good lower bounds for the total cost. A powerful insertion heuristic has been developed for solving the underlying capacitated arc routing problem. This heuristic is used together with a novel location–allocation heuristic to solve the problem within a simulated annealing framework. Extensive computational results demonstrate that the proposed algorithm can find high quality solutions. We also show that the potential cost saving resulting from adding location decisions to the capacitated arc routing problem is significant.     

An optimization framework for solving capacitated multi-level lot-sizing problems with backlogging

This paper proposes two new mixed integer programming models for capacitated multi-level lot-sizing problems with backlogging, whose linear programming relaxations provide good lower bounds on the optimal solution value. We show that both of these strong formulations yield the same lower bounds. In addition to these theoretical results, we propose a new, effective optimization framework that achieves high quality solutions in reasonable computational time. Computational results show that the proposed optimization framework is superior to other well-known approaches on several important performance dimensions.     

An integrated model for lot sizing with supplier selection and quantity discounts

Good inventory management is essential for a firm to be cost competitive and to acquire decent profit in the market, and how to achieve an outstanding inventory management has been a popular topic in both the academic field and in real practice for decades. As the production environment getting increasingly complex, various kinds of mathematical models have been developed, such as linear programming, nonlinear programming, mixed integer programming, geometric programming, gradient-based nonlinear programming and dynamic programming, to name a few. However, when the problem becomes NP-hard, heuristics tools may be necessary to solve the problem. In this paper, a mixed integer programming (MIP) model is constructed first to solve the lot-sizing problem with multiple suppliers, multiple periods and quantity discounts. An efficient Genetic Algorithm (GA) is proposed next to tackle the problem when it becomes too complicated. The objectives are to minimize total costs, where the costs include ordering cost, holding cost, purchase cost and transportation cost, under the requirement that no inventory shortage is allowed in the system, and to determine an appropriate inventory level for each planning period. The results demonstrate that the proposed GA model is an effective and accurate tool for determining the replenishment for a manufacturer for multi-periods.     

A Slope Scaling/Lagrangean Perturbation Heuristic with Long-Term Memory for Multicommodity Capacitated Fixed-Charge Network Design

This paper describes a slope scaling heuristic for solving the multicomodity capacitated fixed-charge network design problem. The heuristic integrates a Lagrangean perturbation scheme and intensification/diversification mechanisms based on a long-term memory. Although the impact of the Lagrangean perturbation mechanism on the performance of the method is minor, the intensification/diversification components of the algorithm are essential for the approach to achieve good performance. The computational results on a large set of randomly generated instances from the literature show that the proposed method is competitive with the best known heuristic approaches for the problem. Moreover, it generally provides better solutions on larger, more difficult, instances.     

An MIP-based interval heuristic for the capacitated multi-level lot-sizing problem with setup times

This paper considers the capacitated multi-level lot-sizing problem with setup times, a class of difficult problems often faced in practical production planning settings. In the literature, relax-and-fix is a technique commonly applied to solve this problem due to the fact that setup decisions in later periods of the planning horizon are sensitive to setup decisions in the early periods but not vice versa. However, the weakness of this method is that setup decisions are optimized only on a small subset of periods in each iteration, and setup decisions fixed in early iterations might adversely affect setup decisions in later periods. In order to avoid these weaknesses, this paper proposes an extended relax-and-fix based heuristic that systematically uses domain knowledge derived from several strategies of relax-and-fix and a linear programming relaxation technique. Computational results show that the proposed heuristic is superior to other well-known approaches on solution qualities, in particular on hard test instances.     

Nonconvex piecewise linear knapsack problems

This paper considers the minimization version of a class of nonconvex knapsack problems with piecewise linear cost structure. The items to be included in the knapsack have a divisible quantity and a cost function. An item can be included partially in the given quantity range and the cost is a nonconvex piecewise linear function of quantity. Given a demand, the optimization problem is to choose an optimal quantity for each item such that the demand is satisfied and the total cost is minimized. This problem and its close variants are encountered in manufacturing planning, supply chain design, volume discount procurement auctions, and many other contemporary applications. Two separate mixed integer linear programming formulations of this problem are proposed and are compared with existing formulations. Motivated by different scenarios in which the problem is useful, the following algorithms are developed: (1) a fast polynomial time, near-optimal heuristic using convex envelopes; (2) exact pseudo-polynomial time dynamic programming algorithms; (3) a 2-approximation algorithm; and (4) a fully polynomial time approximation scheme. A comprehensive test suite is developed to generate representative problem instances with different characteristics. Extensive computational experiments show that the proposed formulations and algorithms are faster than the existing techniques.     

Mixed integer programming model formulations for dynamic multi-item multi-level capacitated lotsizing

Recently there have been two new proposals to model the dynamic multi-item multi-level capacitated lotsizing problem by variable redefinitions based on either a shortest route or a simple plant location representation of the underlying decision problem. Here we will introduce an extended version of the well-known inventory and lotsize model followed by a new model formulation based on modeling the changes of end-of-period inventory levels explicitly. Secondly, we will compare the suitability of different model formulations when solving problem instances with up to 40 items and 16 periods utilizing state-of-the-art standard MIP software on a personal computer.     

Single item lot-sizing with non-decreasing capacities

We consider the single item lot-sizing problem with capacities that are non-decreasing over time. When the cost function is (i) non-speculative or Wagner–Whitin (for instance, constant unit production costs and non-negative unit holding costs) and (ii) the production set-up costs are non-increasing over time, it is known that the minimum cost lot-sizing problem is polynomially solvable using dynamic programming. When the capacities are non-decreasing, we derive a compact mixed integer programming reformulation whose linear programming relaxation solves the lot-sizing problem to optimality when the objective function satisfies (i) and (ii). The formulation is based on mixing set relaxations and reduces to the (known) convex hull of solutions when the capacities are constant over time. We illustrate the use and potential effectiveness of this improved LP formulation on a few test instances, including instances with and without Wagner–Whitin costs, and with both non-decreasing and arbitrary capacities over time. This work was partly carried out within the framework of ADONET, a European network in Algorithmic Discrete Optimization, contract no. MRTN-CT-2003-504438. This text presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian State, Prime Minister’s Office, Science Policy Programming. The scientific responsibility is assumed by the authors.     

On the inventory model with variable lead time and price–quantity discount

In this paper, we propose a mixed integer optimization approach for solving the inventory problem with variable lead time, crashing cost, and price–quantity discount. A linear programming relaxation based on piecewise linearization techniques is derived for the problem. It first converts non-linear terms into the sum of absolute terms, which are then linearized by goal programming techniques and linearization approaches. The proposed method can eliminate the complicated multiple-step solution process used in the traditional inventory models. In addition, the proposed model allows constraints to be added by the inventory decision-maker as deemed appropriate in real-world situations.