Four equivalent lot-sizing models

doi:10.1016/j.orl.2007.12.003

Operations Research Letters

Volume 36, Issue 4, July 2008, Pages 465-470

https://doi.org/10.1016/j.orl.2007.12.003 Get rights and content

Abstract

We study the following lot-sizing models that recently appeared in the literature: a lot-sizing model with a remanufacturing option, a lot-sizing model with production time windows, and a lot-sizing model with cumulative capacities. We show the equivalence of these models with a classical model: the lot-sizing model with inventory bounds.

Introduction

Recently, a number of new lot-sizing models appeared in the literature. In turns out that the models are equivalent to a classical lot-sizing model, the lot-sizing model with bounded inventory (LSB). The three models that turn out to be equivalent with the LSB model are:

1.
the lot-sizing model with a remanufacturing option,
2.
the lot-sizing model with production time windows,
3.
the lot-sizing model with cumulative capacities.

In this paper we will show the equivalence between the models by reformulating them in a specific form.

The remainder of the paper is organized as follows. In Section 2 we will describe the LSB model, give a mathematical formulation and reformulate this model in the specific form. In Section 3 we will consider the recent models in the order of publication date and discuss the equivalence with the LSB model. In Section 4 we provide an overview of the complexity results for the different models.

Section snippets

Lot-sizing with bounded inventory

The lot-sizing model with bounded inventory (LSB) can be described as follows (see [5]). Given a finite and discrete time horizon and a deterministic (known) demand in each time period, find the production plan that satisfies the demand and minimizes total cost. The costs include fixed setup cost for each period with positive production, unit production cost for each item produced, and unit holding cost for each item held in stock. So far the problem is equivalent to the classical lot-sizing

Three models equivalent to the LSB model

In the remainder of the paper we will show that the three other lot-sizing models can be formulated as $[{LSB}^{″}]$ and have bounds $(L, U)$ satisfying Property 1, which implies that they are equivalent to the LSB model. In fact, Property 1 is used by [9] to show the equivalence between the lot-sizing model with a remanufacturing option and the LSB model and by [12] to show the equivalence between the lot-sizing model with production time windows and the LSB model.

Complexity results

In this section we summarize some complexity results for the ‘different’ problems. As already mentioned, [5] developed an $O (T^{3})$ time algorithm for the LSB model with concave cost functions. Recently, Liu [4] considered the LSB model with lot-sizing cost and, using a similar approach to [10], developed an $O (T^{2})$ time algorithm for general cost parameters and an $O (T)$ algorithm for the case of non-speculative motives (also called Wagner–Whitin cost), i.e., $c_{t} \geq c_{t + 1}$ for $t = 1, \dots, T - 1$ in model $[{LSB}^{″}]$ .

References (12)

T. Liu
Economic lot sizing problem with inventory bounds
European Journal of Operational Research
(2008)
K. Richter et al.
Remanufacturing planning for the reverse Wagner/Whitin models
European Journal of Operational Research
(2000)
K. Richter et al.
The reverse Wagner/Whitin model with variable manufacturing and remanufacturing cost
International Journal of Production Economics
(2001)
F.Z. Sargut et al.
Lot-sizing with non-stationary cumulative capacities
Operations Research Letters
(2007)
A. Atamtürk et al.
Lot sizing with inventory bounds and fixed costs: Polyhedral study and computation
Operations Research
(2005)
A. Atamtürk, S. Küçükyavuz, An O(n2) algorithm for lot sizing with inventory bounds and fixed costs, Operations...

There are more references available in the full text version of this article.

Cited by (26)

A branch-and-cut algorithm for an assembly routing problem
2020, European Journal of Operational Research
Citation Excerpt :
Atamtürk and Küçükyavuz (2008) propose an O(n2) dynamic programming algorithm. Van Den Heuvel and Wagelmans (2008) show that the problem is equivalent to the LSP with a remanufacturing option, the LSP with production time windows, and the LSP with cumulative capacities. Di Summa and Wolsey (2010) consider a variable upper bound on the initial inventory and give valid inequalities and extended formulations to describe the convex hull.
We consider an integrated planning problem that combines production, inventory and inbound transportation decisions in a context where several suppliers each provide a subset of the components necessary for the production of a final product at a central plant. We provide a mixed integer programming formulation of the problem and propose several families of valid inequalities to strengthen the linear programming relaxation. We propose two new algorithms to separate the subtour elimination constraints for fractional solutions. The inequalities and separation procedures are used in a branch-and-cut algorithm. Computational experiments on a large set of generated test instances show that both the valid inequalities and the new separation procedures significantly improve the performance of the branch-and-cut algorithm.
Single-item dynamic lot-sizing problems: An updated survey
2017, European Journal of Operational Research
Citation Excerpt :
For problems with more general structures, Hwang (2007b) proposes a fast algorithm in O(max [T2, nT]) where n is the number of time windows. Dauzère-Pérès, Brahimi, Najid, and Nordli (2002) show the importance of production time windows by considering constraints on the availability of demands with different applications such as remanufacturing (van den Heuvel & Wagelmans, 2008), bounded inventory (Wolsey, 2006), major and minor demands (Hwang & Jaruphongsa, 2008), and raw material availability (Brahimi, Absi, Dauzère-Pérès, & Kedad-Sidhoum, 2015a). The SILSP with production time windows consists of processing customer demands which are not necessarily available at the first period of the planning horizon.
Following our previous paper (Brahimi, Dauzère-Pérès, Najid, & Nordli, 2006), we present an updated and extended survey of Single-Item Lot-Sizing Problems with focus on publications from 2004 to 2016. Exact and heuristic solution procedures are surveyed. A concise and comprehensive summary of different extensions of the problem is given. The classification of the extensions is based on different characteristics such as resource limitations, assumptions on demand and cost structure. The large number of surveyed papers shows the increased interest of researchers in lot-sizing problems in general and in single-item problems in particular. The survey and the proposed classification should help researchers to identify new research topics, to propose relevant problems and/or novel solution approaches.
A polynomial time algorithm for convex cost lot-sizing problems
2015, Operations Research Letters
This paper provides a polynomial-time algorithm for economic lot-sizing problems with convex costs in the production and inventory quantities. The resulting algorithm is based on a primal–dual approach that takes advantage of the problem’s special structure. This approach improves upon existing results in the literature, which are either pseudo-polynomial or focus on special cases. We apply the approach to a production planning problem with price-dependent supply, leading to an improved bound on the algorithm’s running time for a special case.
A polynomial time algorithm for the single-item lot sizing problem with capacities, minimum order quantities and dynamic time windows
2014, Operations Research Letters
This paper deals with the single-item capacitated lot sizing problem with concave production and storage costs, considering minimum order quantity and dynamic time windows. The frequency constraints on the production lots are modeled by dynamic time windows. Between two consecutive production lots, there are at least $Q$ periods and at most $R$ periods. This paper presents an optimal algorithm in $O ({(T - Q)}^{2} \frac{(R - Q) T^{4}}{Q^{3}})$ , which is bounded by $O (T^{7})$ .
A Lagrangian relaxation based approach for the capacitated lot sizing problem in closed-loop supply chain
2012, International Journal of Production Economics
Citation Excerpt :
NCD and LSreturned are equivalent. Follows from Heuvel and Wagelmans (2008). □
This paper investigates the capacitated lot sizing problem in closed-loop supply chain considering setup costs, product returns, and remanufacturing. We formulate the problem as a mixed integer program and propose a Lagrangian relaxation-based solution approach. The resulting Lagrangian subproblems are then solved by polynomial time algorithms. Compared to existing solution methods in the literature, our Lagrangian relaxation based approach is advantageous in that it naturally provides a lower bound on the optimal objective function value, which allows us to assess the quality of solutions found. Numerical experiments using synthesized data demonstrate that our approach can find quality solutions efficiently.
Stochastic lot-sizing problem with inventory-bounds and constant order-capacities
2010, European Journal of Operational Research
In this paper, we study the stochastic version of lot-sizing problems with inventory bounds and order capacities. Customer demands, inventory bounds, and costs are subject to uncertainty and dependent with each other throughout the finite planning horizon. Two models in stochastic programming are developed: the first one has inventory-bound constraints, and the second one has both inventory-bound and order-capacity constraints. We explore structural properties of the two models and develop $O (n^{2})$ and $O (n^{2} T \log n)$ dynamic programming algorithms for them, respectively. Our model also generalizes the deterministic lot-sizing problem with inventory bounds. For some cases, when applied to the deterministic versions, our algorithms outperform existing deterministic algorithms.

View all citing articles on Scopus

View full text

Four equivalent lot-sizing models

Abstract

Introduction

Section snippets

Lot-sizing with bounded inventory

Three models equivalent to the LSB model

Complexity results

European Journal of Operational Research

European Journal of Operational Research

International Journal of Production Economics

Operations Research Letters

Lot sizing with inventory bounds and fixed costs: Polyhedral study and computation

Operations Research