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.     

An O(T) algorithm for the capacitated lot sizing problem with minimum order quantities

This paper explores a single-item capacitated lot sizing problem with minimum order quantity, which plays the role of minor set-up cost. We work out the necessary and sufficient solvability conditions and apply the general dynamic programming technique to develop an O(T³) exact algorithm that is based on the concept of minimal sub-problems. An investigation of the properties of the optimal solution structure allows us to construct explicit solutions to the obtained sub-problems and prove their optimality. In this way, we reduce the complexity of the algorithm considerably and confirm its efficiency in an extensive computational study.     

Economic lot sizing problem with inventory bounds

This paper studies a economic lot sizing (ELS) problem with both upper and lower inventory bounds. Bounded ELS models address inventory control problems with time-varying inventory capacity and safety stock constraints. An O(n²) algorithm is found by using net cumulative demand (NCD) to measure the amount of replenishment requested to fulfill the cumulative demand till the end of the planning horizon. An O(n) algorithm is found for the special case, the bounded ELS problem with non-increasing marginal production cost.     

A reformulation for the stochastic lot sizing problem with service-level constraints

We study the stochastic lot-sizing problem with service level constraints and propose an efficient mixed integer reformulation thereof. We use the formulation of the problem present in the literature as a benchmark, and prove that the reformulation has a stronger linear relaxation. Also, we numerically illustrate that it yields a superior computational performance. The results of our numerical study reveals that the reformulation can optimally solve problem instances with planning horizons over 200 periods in less than a minute.     

A polynomial time algorithm to solve the single-item capacitated lot sizing problem with minimum order quantities and concave costs

This paper deals with the single-item capacitated lot sizing problem with concave production and storage costs, and minimum order quantity (CLSP-MOQ). In this problem, a demand must be satisfied at each period t over a planning horizon of T periods. This demand can be satisfied from the stock or by a production at the same period. When a production is made at period t, the produced quantity must be greater to than a minimum order quantity (L) and lesser than the production capacity (U). To solve this problem optimally, a polynomial time algorithm in O(T⁵) is proposed and it is computationally tested on various instances.     

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.     

Valid inequalities and facets of the capacitated plant location problem

Recently, several successful applications of strong cutting plane methods to combinatorial optimization problems have renewed interest in cutting plane methods, and polyhedral characterizations, of integer programming problems. In this paper, we investigate the polyhedral structure of the capacitated plant location problem. Our purpose is to identify facets and valid inequalities for a wide range of capacitated fixed charge problems that contain this prototype problem as a substructure.The first part of the paper introduces a family of facets for a version of the capacitated plant location problem with a constant capacity for all plants. These facet inequalities depend on the capacity and thus differ fundamentally from the valid inequalities for the uncapacited version of the problem.We also introduce a second formulation for a model with indivisible customer demand and show that it is equivalent to a vertex packing problem on a derived graph. We identify facets and valid inequalities for this version of the problem by applying known results for the vertex packing polytope.This research was partially supported by Grant # ECS-8316224 from the National Science Foundation's Program in Systems Theory and Operations Research.     

A cutting plane approach to capacitated lot-sizing with start-up costs

We consider a mixed integer model for multi-item single machine production planning, incorporating both start-up costs and machine capacity. The single-item version of this model is studied from the polyhedral point of view and several families of valid inequalities are derived. For some of these inequalities, we give necessary and sufficient facet inducing conditions, and efficient separation algorithms. We use these inequalities in a cutting plane/branch and bound procedure. A set of real life based problems with 5 items and up to 36 periods is solved to optimality.     

Polynomial cases of the economic lot sizing problem with cost discounts

In this paper we study the economic lot sizing problem with cost discounts. In the economic lot sizing problem a facility faces known demands over a discrete finite horizon. At each period, the ordering cost function and the holding cost function are given and they can be different from period to period. There are no constraints on the quantity ordered in each period and backlogging is not allowed. The objective is to decide when and how much to order so as to minimize the total ordering and holding costs over the finite horizon without any shortages. We study two different cost discount functions. The modified all-unit discount cost function alternates increasing and flat sections, starting with a flat section that indicates a minimum charge for small quantities. While in general the economic lot sizing problem with modified all-unit discount cost function is known to be NP-hard, we assume that the cost functions do not vary from period to period and identify a polynomial case. Then we study the incremental discount cost function which is an increasing piecewise linear function with no flat sections. The efficiency of the solution algorithms follows from properties of the optimal solution. We computationally test the polynomial algorithms against the use of CPLEX.     

A dynamic lot sizing model with exponential machine breakdowns

This paper addresses the dynamic lot sizing model with the assumption that the equipment is subject to stochastic breakdowns. We consider two different situations. First we assume that after a machine breakdown the setup is totally lost and new setup cost is incurred. Second we consider the situation in which the cost of resuming the production run after a failure might be substantially lower than the production setup cost. We show that under the first assumption the cost penalty for ignoring machine failures will be noticeably higher than in the classical lot sizing case with static demand. For the second case, two lot sizes per period are required, an ordinary lot size and a specific second (or resumption) lot size. If during the production of a future period demand the production quantity exceeds the second lot size, the production run will be resumed after a breakdown and terminated if the amount produced is less than this lot size. Considering the results of the static lot sizing case, one would expect a different policy. To find an optimum lot sizing decision for both cases a stochastic dynamic programming model is suggested.     

Solving the capacitated location-routing problem

This is a summary of the main results presented in the author’s Ph.D thesis, available at http://prodhonc.free.fr/homepage. This thesis, written in French, was supervised by Christian Prins and Roberto Wolfler-Calvo, and defended on 16 October 2006 at the Université de Technologie de Troyes. Several new approaches are proposed to solve the capacitated location-routing problem (CLRP): heuristic, cooperative and exact methods. Their performances are tested on various kinds of instances with capacitated vehicles and capacitated or uncapacitated depots.      

Valid inequalities for MIPs and group polyhedra from approximate liftings

In this paper, we present an approximate lifting scheme to derive valid inequalities for general mixed integer programs and for the group problem. This scheme uses superadditive functions as the building block of integer and continuous lifting procedures. It yields a simple derivation of new and known families of cuts that correspond to extreme inequalities for group problems. This new approximate lifting approach is constructive and potentially efficient in computation. J.-P. P. Richard was supported by NSF grant DMI-348611.     

Formulations and valid inequalities for the node capacitated graph partitioning problem

We investigate the problem of partitioning the nodes of a graph under capacity restriction on the sum of the node weights in each subset of the partition. The objective is to minimize the sum of the costs of the edges between the subsets of the partition. This problem has a variety of applications, for instance in the design of electronic circuits and devices. We present alternative integer programming formulations for this problem and discuss the links between these formulations. Having chosen to work in the space of edges of the multicut, we investigate the convex hull of incidence vectors of feasible multicuts. In particular, several classes of inequalities are introduced, and their strength and robustness are analyzed as various problem parameters change.     

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.     

Dynamic lot sizing for multiple products with a new joint replenishment model

This paper studies a new multi-product dynamic lot sizing problem, where the inventories of all products are replenished jointly with the same quantity whenever a production occurs. Such problems may occur in poultry and some chemical industries. We first introduce the general problem that allows for demand rejection with lost sales cost, and prove that the problem is NP-hard. Then we study a special case where all demands have to be satisfied immediately, and show that it can be solved in polynomial time. Finally, we develop two heuristic algorithms for the general problem. Through computational experiments, we demonstrate the effectiveness of the heuristics and investigate some insights related to the decision of lost sales.     

Heuristic solution approaches for the cumulative capacitated vehicle routing problem

Cumulative capacitated vehicle routing problem (CCVRP) is an extension of the well-known capacitated vehicle routing problem, where the objective is minimization of sum of the arrival times at nodes instead of minimizing the total tour cost. This type of routing problem arises when a priority is given to customer needs or dispatching vital goods supply after a natural disaster. This paper focuses on comparing the performances of neighbourhood and population-based approaches for the new problem CCVRP. Genetic algorithm (GA), an evolutionary algorithm using particle swarm optimization mechanism with GA operators, and tabu search (TS) are compared in terms of required CPU time and obtained objective values. In addition, a nearest neighbourhood-based initial solution technique is also proposed within the paper. To the best of authors’ knowledge, this paper constitutes a base for comparisons along with GA, and TS for further possible publications on the new problem CCVRP.     

Multi-level lot sizing and job shop scheduling with compressible process times: A cutting plane approach

This paper proposes an integer linear programming formulation for a simultaneous lot sizing and scheduling problem in a job shop environment. Among others, one of our realistic assumptions is dealing with flexible machines which enable the production manager to change their working speeds. Then, a number of valid inequalities are developed based on problem structures. As the valid inequalities can help in reducing the non-optimal parts of the solution space, they are dealt with as some cutting planes. The proposed cutting planes are used to solve the problem in (i) cut-and-branch, and (ii) branch-and-cut approaches. The performance of each cutting plane is investigated with CPLEX 12.2 on a set of randomly-generated test data. Then, some performance criteria are identified and the proposed cutting planes are ranked by TOPSIS method.