This file was downloaded from BI Open Archive, the institutional repository (open access) at BI Norwegian Business School http://brage.bibsys.no/bi.
It contains the accepted and peer reviewed manuscript to the article cited below. It may contain minor differences from the journal's pdf version.
Brahimi, N., Absi, N., Dauzèré-Pérès, S., & Nordli, A. (2017). Single-item dynamic lot- sizing problems: An updated survey. European Journal of Operational Research, 263(3), 838-863 DOI: https://doi.org/10.1016/j.ejor.2017.05.008
Copyright policy of Elsevier, the publisher of this journal.
The author retains the right to post the accepted author manuscript on open web sites operated by author or author's institution for scholarly purposes, with an
embargo period of 0-36 months after first view online.
http://www.elsevier.com/journal-authors/sharing-your-article#
This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
Single-Item Dynamic Lot-Sizing Problems: An Updated Survey
Nadjib Brahimi1 Nabil Absi2 St´ephane Dauz`ere-P´er`es2,3 Atle Nordli3
1 Department of Supply Chain Management Rennes School of Business
F-35065 Rennes, France E-mail: [email protected]
2Department of Manufacturing Sciences and Logistics, CMP Ecole des Mines de Saint-Etienne, CNRS UMR 6158 LIMOS,
F-13541 Gardanne, France
E-mail: [email protected], [email protected]
3Department of Accounting, Auditing and Business Analytics BI Norwegian Business School,
0484 Oslo, Norway Email: [email protected]
Abstract
Following our previous paper (Brahimi, N., Dauz`ere-P´er`es, S., Najid, N. M., and Nordli, A. Single item lot sizing problems. European Journal of Operational Research, 168(1):1-16, 2006), we present an updated and extended survey of Single-Item Lot-Sizing Problems with focus on publications from 2004 to 2015. 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.
Keywords: Production; Planning; Lot Sizing; Single Item; Dynamic Demand
1. Introduction
Since the publication of the seminal work of Wagner and Whitin (1958) in 1958, a lot of research has been conducted on the Single-Item Lot-Sizing Problem (SILSP) and its extensions. The SILSP is interesting in itself to model some tactical production and distribution planning problems, e.g. when planning the replenishment of one raw material with fixed and variable ordering and transportation costs. It is also important to efficiently solve the SILSP because it appears as a subproblem in the solution procedures of many complex lot-sizing problems such as capacitated multi-item problems.
Extensions of the SILSP include production capacity, remanufacturing, backlogging, lost sales, demand and production time windows, bounded inventory, perishability, etc. The large number of publications on the SILSP and the large variety of its applications and extensions call for a literature review to put together all the relevant references and classify them. This will allow researchers in the field to more easily identify research trends and gaps to be filled in lot sizing in particular and in production and distribution planning in general. This survey is an extension and an update of a previous survey published by three of the authors inEuropean Journal of Operational Research in 2006 (Brahimi et al.
(2006)). Since this survey was published, there has been a growing interest in the study of the SILSP.
There were at least 100 publications on the SILSP and its extensions in the past 8 years. The objective
of this paper is to update the previous literature review and enrich it with the new research in the area. To avoid repetition and for space reasons, most of the references and details in (Brahimi et al.
(2006)) are omitted.
The SILSP can be defined as a planning problem in which there is time-varying demand for a single product over a planning horizon of T periods. The objective is to determine periods where production will take place and the quantities that have to be produced in these periods. The total production should satisfy the demands while minimizing the total costs. The basic costs are the unit production cost pt (where t= 1, .., T is the period); the setup cost st, which is a fixed cost incurred if a production process is started in a period t, and the unit inventory holding cost ht. Extensions might include, for example, a capacity limitationCt or inventory bound Imax.
The classification of lot-sizing problems can be done based on several criteria or characteristics such as: Nature of data (deterministic or stochastic), nature of the time scale (continuous or discrete), number of machines, number of production stages (levels), capacity constraints and their nature (fixed or variable), length of production periods, etc. In addition to the classifications proposed in (Brahimi et al. (2006), in their book, Pochet and Wolsey (2006) discuss models for different lot sizing and production planning problems.
This paper focuses on discrete time models. For surveys on continuous time models, we invite the reader to consult Holmbom and Segerstedt (2014), for example. There are also some surveys on discrete time lot-sizing problems. The majority of these surveys deal with multi-item and multi-level problems, some of which are cited here in chronological order: Bahl et al. (1987), Karimi et al. (2003), Pochet and Wolsey (2006), Jans and Degraeve (2008), Buschk¨uhl et al. (2010), Diaz-Madro˜nero et al.
(2014).
In this paper, we restrict ourselves to the single-item dynamic lot-sizing problem and its extensions.
This survey is an update of previously published survey (Brahimi et al. (2006)). It is motivated by several recent extensions of the single-item lot-sizing problem such as: Remanufacturing, stochastic versions, bounded inventories, carbon emission constraints, minimum order quantities, batch sizes, etc.
We do not claim to have an exhaustive list of papers in the area of the single-item lot-sizing problem and its extensions. Since the number of references in this area is huge, we apologize in advance if we missed any relevant publication. Through this work we wanted to give a general overview of studied problems and their importance. Papers are not classified in a chronological order but cited when needed in the closely linked section.
By looking closely at all surveyed papers since 1958, we found that more than 50% of the papers were published during the last 10 years. Furthermore, the main journals publishing on this topic, totaling more than 50% of all publications, are European Journal of Operational Research, Manage- ment Science,Operations Research,International Journal of Production Economics, andInternational Journal of Production Research.
The paper is organized as follows. Section 2 deals with basic formulations of the classical single- item lot-sizing problem. Section 3 gives a quick overview of used solution methods. In Section 4 we propose a classification of single-item lot-sizing problems and a quantitative analysis of the bib- liography. Section 5 deals with papers addressing assumption on demands such as backlogging, lost sales, time windows, stochastic demand, elastic demand and profits. In Section 6, we address resource constraints such as capacity, inventory, lot-sizes constraints. Section 7 regroups single-item lot-sizing problems with complex structures like multi-level, multi-echelon and remanufacturing structures. Sec- tion 8 addresses single-item lot-sizing problems that integrate other decision levels such as scheduling, warehouse location, transportation, vehicle routing, etc. Section 9 gathers several extensions such as pricing, cost structures, co-production, environmental issues, stochastic parameters, etc. The last section concludes the paper and provides some promising research directions.
2. Formulations of the basic problem
Traditionally, Mixed Integer Programming (MIP) formulations are not directly used to solve the uncapacitated SILSP. But, as already mentioned, the SILSP is very often solved as a sub-problem in
several algorithms for more complex lot-sizing problems, which are often modeled as Mixed Integer Programs. This is why we present the different MIP formulations of the uncapacitated SILSP. Also, some authors derive Dynamic Programming (DP) algorithms using some structural properties of these formulations.
First, we introduce a general model that does not make any assumptions on the shape of production and inventory holding costs, then we present straightforward compact formulation that provides a weak linear relaxation. We then briefly discuss two reformulations and an extended formulation with the so-called (l, S)-inequalities.
Let T be the length of the planning horizon and dt be the deterministic demand in period t (t= 1, .., T). ftp(.) and fth(.) are respectively the production cost and the holding cost functions at period t (t = 1, .., T). The goal is to decide when to produce and how much to produce in order to satisfy demands and minimize the total production and holding costs. The decision variables are: Xt, the quantity to be produced in period t and It, the inventory level at the end of period t (t = 1, .., T).
We assume, without loss of generality, that the stock at the beginning and the stock at the end of the planning horizon are zero.
2.1. A general model
The most general formulation of the uncapacitated SILSP that does not make any assumptions on the structure of functionsftp(.) and fth(.) can be written as follows:
Minimize
T
X
t=1
(ftp(Xt) +fth(It)) (1)
Subject to:
It−1+Xt=dt+It ∀t (2)
It, Xt≥0 ∀t (3)
The objective function (1) minimizes the total production and holding costs over the horizon of T periods. Constraints (2) are the inventory balance equations. They express that the entering stock (It−1) added to the current period production (Xt) are used to satisfy the demand (dt), and what remains is kept in stock at the end of the period (It). Constraints (3) define the continuous production variables Xt and inventory levels It.
In this section, we limit the discussion to functionsftp(.) andfth(.) of the form: ftp(xt) =stδ(x(t))+
ptxtandfth(It) =htIt, whereptis the unit production cost in each periodt,htis the unit holding cost in each periodt,stis the fixed setup cost incurred once in a period if production occurs, andδ(x(t)) = 1 ifxt>0 and zero otherwise. This is actually the most frequently encountered form of these functions in the lot-sizing literature. Moreover, there is a special case where the unit production and holding costs satisfy the conditionpt−1+ht−1 ≥ptfor all periods, i.e. it is always optimal to produce as late as possible (ignoring setup costs). In the literature, this is often referred as the casewithout speculative motives to hold inventory or the casewith Wagner-Whitin costs. The uncapacitated SILSP with no speculative motives is known to be solvable in O(T). Note that there are many practical instances having such cost structure (Wolsey (1995)). Finally, and to simplify the presentation, we replace functionδ(x(t)) with a binary decision variableYt.
2.2. Aggregate formulation (AGG)
Let dτ t = dτ +dτ+1 +...+dt. Using the simplified production and holding cost functions, the followingaggregate (AGG) formulation can be written:
Minimize
T
X
t=1
(stYt+ptXt+htIt) (4)
Subject to:
It−1+Xt=dt+It ∀t (5)
Xt≤YtdtT ∀t (6)
Yt∈ {0,1} ∀t (7)
It, Xt≥0 ∀t (8)
This formulation is called aggregate in contrast with disaggregated formulations such as facility location problem based formulation and the shortest path problem based formulation, to which we refer as FAL and SHP, respectively. In FAL and SHP formulations production variables are split and presented in a less intuitive way than the variablesXtabove. The objective function (4) minimizes the sum of the setup, production and inventory holding costs. Constraints (5) are the inventory balance equations. Constraints (6) relate the continuous production variablesXtto the binary setup variables Yt. Constraints (7) and (8) define the decision variables.
In the above formulation, using the fact thatIt=Pt
τ=1Xτ−Pt
τ=1dτ, t= 1, ...T and combining this with constraintIt≥ 0 (∀t) and constraints (5), one can derive a formulation without inventory variables.
2.3. Strong Formulations
FAL and SHP formulations (see Brahimi et al. (2006) and the references therein for details) are considered as tight formulations because their LP relaxations have optimal solutions in which the variables Y are integer. Some fast dynamic programming algorithms were drived based on these formulations in the 1990s.
FAL and SHP are reformulations of the problem as the original variables (production variables in this case) are replaced with new variables. By adding valid inequalities to AGG formulation, it is possible to develop strong formulations with the original decision variables. Barany et al. (1984) introduced (l, S) inequalities defined as:
X
t∈S
Xt+X
t∈S¯
dtlYt≥d1l (9)
wherel∈ {1, . . . , T},S⊆ {1, . . . , l}and ¯S ={1, . . . , l} \S.
Barany et al. (1984) showed that combining (4)-(8) with the (l, S)-inequalities (9) provides a complete polyhedral description of the convex hull of the uncapacitated SILSP. The new formulation would contain an exponential number of valid inequalities. However, they can be used in a cutting plane approach to solve the problem.
3. Complexity and solution approaches
Most of the literature of the basic SILSP and its extensions has been on exact solution methods.
Such methods include dynamic programming, polyhedral approaches, branch-and-cut and branch-and- bound algorithms. Nevertheless, heuristic methods such as simple construction heuristics, approxima- tion algorithms, and some improvement heuristics have also been developed. These have played an important role in developing heuristics for more complex lot-sizing problems.
It is worth mentioning that it is possible to derive a closed-form expression for the optimal solution of the very special case of the SILSP where demand is constant (Ganas and Papachristos (2005)). Some studies focused on classifying SILSPs based on their computational complexity.
In what follows, we start with the presentation of the complexity of the SILSP; then we present the most popular solution methods, first exact methods and then heuristics.
3.1. Complexity
The basic uncapacitated SILSP is an “easy” problem that can be solved in O(TlogT) in general and in O(T) with some assumptions, in particular without speculative motives to hold inventory.
However, some of the extensions of the SILSP are NP-hard. In addition to complexity studies presented in Brahimi et al. (2006) on the capacitated SILSP, recent studies include Akbalik and Rapine (2013) for the problems with constraints on batch sizes, and Guan (2011) for stochastic problems. Details about these studies will be presented in the corresponding section of each extension.
3.2. Dynamic Programming
The first exact algorithm developed for the uncapacitated SILSP is the dynamic programming algorithm proposed by Wagner and Whitin (1958) (WW). It is a forward dynamic programming algorithm that runs in O(T2). Using the the Zero Inventory Ordering (ZIO) property, the search space is reduced to at mostT(T + 1)/2.
A natural consequence of the ZIO property is: There exists an optimal solution in which ifXt>0, then Xt = Pt+k
i=tdi for some k ≥ 0, i.e. each production period satisfies the demands of k+ 1 consecutive periods starting from periodt.
Let G(k) be the minimum cost of the subproblem from periods 1 up tok. In such a solution, if t is the last period in which production occurs, thenXt=dt,k. Thus, the recursive equation is:
G(k) = min
1≤t≤k{G(t−1) +st+ptdt,k+
k−1
X
τ=t
hτdτ+1,k} (10)
Then, initializing G(0) to 0 and calculating G(k) for k= 1, . . . , T leads to the value G(T) of the optimal solution. This is done in O(T2) if the values G(1), G(2), . . . , G(T) are evaluated in the simplest way. Finally, by starting fromG(T) and going backward, the corresponding optimal solution is derived in O(T) additional time.
Some researchers attempted to improve the WW algorithm through various efficient implemen- tations (Zabel (1964), Bahl and Taj (1991)). However, these implementations do not improve the complexity of the WW algorithm.
By the end of the 1980’s, three groups of researchers independently developed three different dynamic programming algorithms each of which can solve the classical WW problem in O(TlogT) (See Brahimi et al. (2006)).
We will also see in Sections 5–8 that dynamic programming is extensively used to solve different extensions of the SILSP.
3.3. Branch-and-bound methods and dual algorithms
Unlike dynamic programming, very few researchers developed Branch-and-Bound (B&B) proce- dures for the SILSP. For the SILSP with capacity constraint, B&B algorithms were developed by Erenguc and Tufekci (1987), Erenguc and Aksoy (1990), and Lotfi and Yoon (1994). In Chung et al.
(1994), an exact algorithm that combines B&B and dynamic programming was presented. Finally, developing good bounds for capacitated SILSPs improves the performance of branch-and-bound al- gorithms. Hardin et al. (2007) propose procedures to quickly generate upper and lower bounds for a special class of capacitated SILSPs.
Two different efficient dual-based optimization algorithms are proposed in van Hoesel et al. (1991) and Levi et al. (2006). The algorithm in van Hoesel et al. (1991) is based on the formulation proposed
by Barany et al. (1984). The primal-dual algorithm in Levi et al. (2006) is quite simple and is derived from a primal-dual algorithm proposed for the more complex joint replenishment problem.
3.4. Valid inequalities and branch-and-cut methods
The polyhedral structure of SILSPs was considerably studied in the literature. The first purpose is to directly use MIP solvers on extended formulations; that is formulations with added valid in- equalities. The second purpose of these studies is to solve the problem using branch-and-cut (B&C) algorithms. A lot of research was carried out on the development of different types of valid inequalities for different classes of SILSPs. The earliest research on this topic is the paper of Barany et al. (1984) on the uncapacited SILSP. Other studies include, for example, Wolsey (1989) who presents families of strong valid inequalities for the uncapacited SILSP with startup costs. Di Summa and Wolsey (2010), Escalante et al. (2011), K¨u¸c¨ukyavuz and Pochet (2009), Pochet and Wolsey (1993) and van Vyve (2006) develop extended formulations whose LP relaxation solves the lot-sizing problem. Pereira and Wolsey (2001) define facets and prove that the face of optimal solutions is found inO(T2). Loparic et al. (2003) use knapsack inequalities as strong valid inequalities for some capacitated SILSPs. Read- ers interested in this topic can refer to the book of Pochet and Wolsey (2006). Valid inequalities that are developed for SILSPs can be used to strengthen the LP relaxation of richer and harder lot-sizing problems such as those dealing with multiple items.
3.5. Simple Heuristics
The simplest way to solve the uncapacitated SILSP is the lot-for-lot procedure where production at each period is equal to the demand at that period. Another simple heuristic to the uncapacitated SILSP is based on the Economic Order Quantity (EOQ) formula. TheEOQ is calculated based on the demand, holding cost and setup cost that are averaged over theT periods of the planning horizon.
If the production must be positive at a given periodt(Xt>0), thenXt=EOQ. Another alternative is to setXt=dtτ (τ ≥t) such thatdt,τ is the closest value to EOQ.
The heuristic proposed by Silver and Meal (1973) is a forward method that requires determining the average cost per period as a function of the number of periods whose demand is to be produced in the current period, and stopping the computation when this function first increases. The Least Unit Cost heuristic is a modified version of the Silver and Meal heuristic which minimizes the cost per unit of demand. Finally, one of the most popular heuristics is the Part Period Balancing algorithm (DeMatteis (1968), Wemmerl¨ov (1983)). It consists in setting the horizon (number of periods) on which to order to the number of periods that most closely matches the total holding cost with the setup cost over that period. A new heuristic was proposed in van den Heuvel and Wagelmans (2009) with a similar worst case ratio. van den Heuvel and Wagelmans (2010) proved that a worst case ratio of 2 is actually the best possible result for any myopic heuristic. Reviews and comparisons of these heuristics and others are presented in Benli et al. (1988), Nydick and Weiss (1989), Coleman (1992), Vachani (1992), and Baciarello et al. (2013).
Knowing that there exist fast exact algorithms in O(TlogT) to solve the uncapacitated SILSP, one might claim that simple heuristics are of limited interest in practice, even though their complexity is usually O(T). Actually heuristics have at least three advantages. Firstly, they can be used for academic purposes to introduce students to production planning concepts. Secondly, heuristics are used in practical applications to directly solve single-item problems or complex industrial problems as they can be more easily adapted. Many heuristics are integrated into some ERP (Enterprise Resource Planning) systems (see for example Bahl and Neelam (2009)). As a third advantage, Blackburn and Millen (1980) showed that at least some of the simple heuristics (including the Silver and Meal heuristic) are more efficient than the Wagner-Whitin algorithm for rolling horizon problems. This is an important point as most real applications are dynamic in nature and new solutions have to be computed frequently as more accurate information (e.g. on demand) becomes available. However, it seems that this last advantage of heuristics is no longer relevant as Stadtler (2000) showed that exact solution procedures used with adjusted data perform at least as well as simple heuristics.
Simple heuristics are mainly used to solve harder problems such as multi-item lot-sizing problems.
To the best of our knowledge, there are very few applications of these heuristics to solve the SILSP extensions presented in this paper. The relevant references will be presented in the adequate sections below.
3.6. Approximation methods
Few theoretical results have been published on approximation methods applied to uncapacitated single-item lot-sizing problems. As discussed in Section 3.5, van den Heuvel and Wagelmans (2009) and van den Heuvel and Wagelmans (2010) provide worst case error bounds for different heuristics for the uncapacitated SILSP.
Fully polynomial approximation schemes for the capacitated SILSP are discussed in Section 6.1.2 and in Section 9.1 for the stochastic SILSP.
3.7. Other heuristics
The single-item lot-sizing problem is considered as a relatively “easy” problem since most of its difficult variants are NP-hard in the ordinary sense, and can be solved with pseudo-polynomial time algorithms. This can explain why there are very few publications on the application of advanced heuristics such as meta-heuristics to solve these problems. Hence, the few advanced heuristics that can be met are mostly developed for extensions of the SILSP. For example, Lagrangian relaxation-based heuristics were developed by Zhang et al. (2012) and Brahimi and Dauz`ere-P´er`es (2015) to solve the capacitated SILSP with remanufacturing and production time windows, respectively. Tabu search was used by Armentano et al. (2011) on an integrated lot-sizing and distribution problem. Parsopoulos et al. (2015) investigate the performance of Differential Evolution algorithm on the uncapacitated SILSP with remanufacturing. Finally, goal programming was used by Choudhary and Shankar (2014) to solve a SILSP with multiple suppliers.
4. Classification
The classification of lot-sizing problems can be based on several criteria such as those presented in Haase (1994) and Brahimi (2004). These criteria are summarized in Table 1.
Table 1: A classification of lot-sizing problems
Parameter Classifications
Information degree Deterministic*, stochastic*.
Horizon finite*, infinite.
Time scale discrete (small time periods, large time periods*), continuous Number of items single item*, multi item.
Number of levels single level*, multi level* (serial, in-tree, general, ...).
Relevant costs setup related (startup*, reservation*), inventory related (holding*, back- order*, lost sales*),
capacity related (regular hours*, overtime*, sub-contracting*).
Resource constraints number (single resource*, multi resource*), type (constant*, variable*).
Service Policy demand satisfied on-time*, backorder*, lost sales*, sub-contracting*.
Time consuming activi- ties
setup time (ST) (minor ST, major ST), processing time (zero, con- stant*, variable), lead time, transportation time.
Objectives minimize costs*, maximize service level, smoothing of production load, maximize profit*.
(*) Classification corresponding to the problems considered in this survey.
Inspired by this classification, the papers in this survey were grouped by category. Since a large part of the studies deals with assumptions on demands (such as backlogging, lost sales, time windows, stochastic demand, elastic demand and profits), the related papers are reviewed in Section 5. Other important extensions deal with resource constraints (such as capacity, inventory, lot-size constraints).
Articles dealing with this topic are grouped in Section 6. Generally SILSPs with complex structures (such as multi-level, multi-echelon and remanufacturing) are NP-Hard. Papers dealing with these extensions are analyzed in Section 7. Lot-Sizing problems combined with other decisions (such as scheduling, warehouse location, transportation, vehicle routing, etc.) are considered in Section 8. In Section 9, we grouped all remaining relevant extensions (such as pricing, cost structures, co-production, environmental issues, stochastic parameters, etc.) that do not fit within one of the previous categories.
5. Assumptions on demands
As mentioned in the previous sections, several assumptions are made for the classical single-item uncapacitated lot-sizing problem. The strongest assumptions are related to demand. In fact, usually the demand is supposed deterministic and should be satisfied entirely on time without having the possibility to lose it or to postpone it to later periods. In real-life problems, these assumptions are not realistic in many cases. For example, generally when the capacity is not sufficient to satisfy the entire demand, several options can be considered. The demand can be backlogged to future periods or partially/totally lost. The demand can also be considered as a stochastic variable following a given distribution or represented by a scenario tree. Some studies addressed profit maximization rather than demand satisfaction, while others considered elastic demands (i.e. demand is a variable). In this section, we survey the papers addressing these assumptions.
5.1. Backlogging
Backlogging is one of the first extensions of the classical uncapacitated SILSP. The SILSP with backlogging was first studied by Zangwill (1969). Backlogging can be due to two situations, either the cost of making and storing the product is not profitable or capacity constraints are not sufficient to satisfy demand on time. In both situations, the backlogged quantities are modeled using new flow variables that are in the opposite direction of inventory flow variables. More formally, to generalize the classical uncapacitated SILSP, we introduce a new non negative continuous variableZtthat represents the accumulated backlog at the end of period t. A backlogging cost bt is associated with each unit backlogged from periodt−1 to periodt. The classical model for the uncapacitated SILSP can be easily generalized by replacing Constraints (5) with Constraints (11), adding the cost componentPT
t=1btZt
to the objective function and introducing the non negative variableZt withZ0 = 0. The SILSP with backlogging is denoted SILSP-B.
It−1−Zt−1+Xt=dt+It−Zt∀t∈ {1, . . . , T} (11) Similarly to the uncapacitated SILSP, the extreme optimal solutions have the structure of a span- ning tree. Zangwill (1969) shows that the problem can be solved optimally in O(T2) by generalizing the algorithm of Wagner and Whitin (1958). Analogously to the uncapacitated SILSP, this dynamic programming recursion can be represented as a shortest path problem (see Pochet and Wolsey (2006)).
Using techniques similar to the ones used for the uncapacitated SILSP, the complexity was reduced toO(TlogT) by several authors (see Brahimi et al. (2006)). This complexity reduces toO(T) when there are no speculative motives for late production (see Section 2.1 for inventory), i.e. if both pt−1+ht−1 ≥ptand pt+bt−1 ≥pt−1 for all periods.
In a recent study, K¨u¸c¨ukyavuz and Pochet (2009) identify valid inequalities that subsume all previously known valid inequalities for the uncapacitated SILSP-B. They show that these inequalities are enough to describe the convex hull of solutions.
Several studies extended the uncapacitated SILSP-B and showed that the problem generally re- mains polynomially solvable. Absi et al. (2011) extend the uncapacitated SILSP with production time
windows by considering backlogging costs, and show that the problem can be solved optimally with an O(T2) dynamic programming algorithm. For the uncapacitated SILSP-B with demand time windows, Hwang (2007) proposes anO(T3) dynamic programming algorithm to solve the problem under the non- speculative cost structure. For the general cost structure, he proposes anO(max[T2, nT]) algorithm, wherenis the number of time windows with positive demands. Chu et al. (2013) generalize the unca- pacitated SILSP-B by considering outsourcing and inventory capacity. The backlogging level at each period is supposed to be limited. The authors show that this problem can be solved in O(T4logT).
van Vyve (2007) proposes an O(T3) algorithm to optimally solve the single-item lot-sizing problem with constant batch size and backlogging. van Vyve (2006) presents two linear-programming extended formulations of the constant-capacity lot-sizing problem with backlogging. The first one addresses the problem with a general cost function and hasO(T3) variables and constraints. The second deals with the problem when there are no speculative motives and has O(T2) variables and O(T3) constraints.
An O(T3) algorithm is proposed by Ou (2012) to solve a SILSP-B with time independent capacity.
Generally, backlogging costs are not easy to evaluate. In fact, in addition to the penalties due to late deliveries several other costs should be considered. The loss of customer goodwill is one of these components and it is not easy to quantify (Aksen (2007)). Additional costs related to the expedition of the late demand could be considered.
5.2. Lost sales
Lost sales is generally considered as an alternative to backlogging but they can also be considered together. In fact, a demand can be postponed for a given number of periods, but if the delivery date is too late the demand can be lost. Similarly to backlogging, lost sales can be due to two situations.
Either capacity constraints are not sufficient to fulfill the demand or the cost of producing and storing the product is not profitable. The model should decide which demand to satisfy and which demand to lose. Aksen et al. (2003) proposed aO(T2) algorithm to solve this problem. To generalize the classical SILSP, a new non negative continuous variableRtis introduced that represents the unmet demand at the end of each periodt. A unitary lost sales costltis associated with each unit of lost sales at period t. The classical model for the uncapacitated SILSP can easily be generalized by replacing inventory balance constraints (Constraints (5)) with constraintsIt−1+Xt+Rt=dt+It∀t∈ {1, . . . , T}, adding the cost component PT
t=1ltRt to the objective function and introducing the non negative lost sales variableRt. The SILSP with lost sales is denoted by SILSP-LS.
The uncapacitated SILSP-LS can be represented using a fixed charge network. Similarly to the uncapacitated SILSP, the extreme optimal solutions have the structure of a spanning tree (see Aksen et al. (2003) for more details). Loparic et al. (2001) studied the uncapacitated SILSP with sales instead of lost sales and lower bounds on stocks. The objective is to maximize the income of sales rather than minimizing the cost of lost sales. They showed that the problem can be solved in polynomial time using dynamic programming. They also provide two extended formulations as well as a complete description of the convex hull of solutions.
Several studies extended the uncapacitated SILSP-LS and showed that the problem generally remains polynomially solvable. Absi et al. (2011) extend the uncapacitated SILSP with production time windows by considering lost sales costs. They show that the problem can be solved optimally with an O(T2) dynamic programming algorithm. Berk et al. (2008) study the uncapacitated SILSP with capacity constraints and lost sales for a warm/cold process. They also used dynamic programming to solve this problem. Recently, several authors studied the uncapacitated SILSP-LS with bounded inventory (Liu et al. (2007), Hwang et al. (2013), Liu and Tu (2008)). Some authors addressed outsourcing which can be modeled as lost sales (Chu and Chu (2007), Chu et al. (2013)). SILSPs with outsourcing are surveyed in Section 6.4.
Evaluating the cost of lost sales is even harder than estimating the backlog cost. In fact, in addition to the loss of revenue, this cost should integrate the loss of customer goodwill. The cost of lost sales is not easy to evaluate since it should represent the impact of a low service level on future demands.
If lost sales lead to outsourcing, the related cost is easier to estimate since it represents the loss of
profit. How to estimate backlog and lost sales costs is not well addressed in the literature except for few publications (e.g. Oral et al. (1972), Liberopoulos et al. (2010)).
5.3. Time windows
Lot-sizing problems with time windows were introduced by Lee et al. (2001) for demand or delivery time windows and by Dauz`ere-P´er`es et al. (2002) for production time windows.
The demand/delivery time windows problem in Lee et al. (2001) is characterized by the fact that demand time windows are fixed by customers and considered as grace periods during which demand can be satisfied with no penalty; i.e. no inventory or backlogging costs are incurred when demands are completed within their time windows. Such a situation can be seen in third party logistics and vendor managed inventory settings (e.g. Jaruphongsa et al. (2004)).
Lee et al. (2001) assume special conditions on costs and study two cases: With and without backlogging. For the no-backlogging problem, an O(T2) algorithm is proposed. When backlogging is allowed, the problem is solved inO(T3). For problems with more general structures, Hwang (2007) proposes a fast algorithm in O(max[T2, nT]) wheren is the number of time windows.
Dauz`ere-P´er`es et al. (2002) show the importance of production time windows by considering con- straints on the availability of demands with different applications such as remanufacturing (van den Heuvel and Wagelmans (2008)), bounded inventory (Wolsey (2006)), major and minor demands (Hwang and Jaruphongsa (2008)), and raw material availability (Brahimi et al. (2015)). The SILSP with production time windows consists of processing customer demands which are not necessarily available at the first period of the planning horizon. A time window demanddt1,t2 is characterized by the fact that production cannot start before its release periodt1 and must be delivered not later than its due date t2. Besides the general case calledcustomer specific (CS) problem, a special case called thenon-customer specific (NCS) problem is distinguished.
Dauz`ere-P´er`es et al. (2002) also identified some interesting properties of the problem and suggested dynamic programming algorithms to solve the uncapacitated case using an exponential time algorithm for the CS problem and an O(T4) algorithm for the NCS problem. Later, Wolsey (2006) further analyzed the two cases and proposed improved algorithms, in particular, an O(T2) algorithm for the NCS problem. The CS problem was also solved by Hwang (2007) using an O(T4) algorithm. The equivalence between lot-sizing problems with production time windows, the lot-sizing problem with bounded inventory, the lot-sizing problem with remanufacturing options, and the lot-sizing problem with cumulative capacities is discussed in van den Heuvel and Wagelmans (2008). Extensions of the SILSP with production time windows include backlogging, lost sales and early production (Absi et al.
(2011)) and production capacity (Brahimi and Dauz`ere-P´er`es (2015)).
5.4. Others: Stochastic and elastic demands
Most of the lot-sizing literature focuses on problems with deterministic demands. However, produc- tion planning decisions are often based on forecasts which may contain errors that affect the solution procedure to use. Thus, considering demand as a stochastic parameter can be more realistic in prac- tice. In addition to demand, other parameters were also considered as stochastic in different studies.
Lot-sizing models with different stochastic parameters (especially demand and costs) are surveyed in Section 9.1.
In lot-sizing models with elastic demand, the demand is a function of the unit price of the product.
Thus, the unit price is a decision variable to be determined, demand is not known in advance, and can be increased or decreased by varying the unit price. More details on this problem are given in Section 9.2.
6. Constraints on resources
The assumption that there is an infinite amount of available resources is not realistic in many practical cases. Thus new constraints need to be added to uncapacitated SILSPs to handle scarcity of
machine/worker time, storage space, and technological characteristics of some resources (such as the maximum amount that can be handled by a machine at a time).
6.1. Production capacity constraints
In most practical situations, capacity cannot be assumed infinite. Capacitated SILSPs are harder than their uncapacitated counterparts. However, there are some “easy” cases. Most NP-completeness results and first polynomial time algorithms for capacitated SILSPs were presented in Bitran and Yanasse (1982) who proposed a four-field notation to classify these problems. With each problem is associated a quadrupleα/β/γ/δ, whereα,β,γ andδ specify the special structures of the setup cost, unitary holding cost, unitary production cost and capacity, respectively. The values taken by α, β, γ and δ are G, C, ND, NI and Z which correspond to General structure, Constant, Non-Decreasing, Non-Increasing and Zero, respectively. For example, the notation NI/ND/C/G indicates a family of problems where, over time, the setup costst is non-increasing, the holding costht is non-decreasing, the production costpt is constant and the capacityCt is not restricted to any pre-specified structure.
6.1.1. Polynomial cases
The complexity of the capacitated SILSP mainly depends on the capacity parameter structure (variable or time independent). The following problems were solved in polynomial times either in Bi- tran and Yanasse (1982) or in other publications until 2005 (See Brahimi et al. (2006))): NI/G/NI/ND, NI/G/NI/C, C/Z/C/G, ND/Z/ND/NI, G/G/G/C. Algorithms in O(TlogT) were proposed to solve Z/G/G/G and NI/G/G/C problems by Kovalyov and Pesch (2014) and Feng et al. (2011), respectively.
New polynomial algorithms were developed for extensions or special cases of capacitated SILSPs, for instance with stepwise production cost or batch production (see Section 6.3.2), with backlogging (see Section 5.1), or with reservation costs (see Section 9.4).
6.1.2. Other results and solution approaches
In general, the capacitated SILSP is NP-hard even for the following special cases (Florian et al.
(1980) and Bitran and Yanasse (1982)): C/Z/NI/NI, C/Z/ND/ND, ND/Z/Z/ND, NI/Z/Z/NI, C/G/Z/NI and C/C/ND/NI. However, the hardest versions of the problem, including problem G/G/G/G, are actually NP-hard in the weak sense. Consequently, pseudo-polynomial time algorithms were developed to solve these problems. Recently, fast pseudo-polynomial algorithms for the most general problem (G/G/G/G) were proposed by van den Heuvel and Wagelmans (2006) and Chen et al. (2008).
Mathematical programming formulations of the uncapacitated SILSP can rather easily be extended to the capacitated case. For example, in the aggregate formulation (AGG) (see Section 2.2), it is enough to replace constraints (6) with Xt ≤ min{Ct, dtT}Yt (∀t). More general forms of capacity constraints were also studied. Chubanov et al. (2008) propose a model in which variables Xt are interpreted as the amount of a resource used for production. Then they introduce a function gt(Xt) which corresponds to the total number of manufactured units of the product given that Xt units of the resource were used. This model allows the formulation of different SILSP extensions with non- uniform resource capacities or resources with imperfect yield. Extended versions of these formulations were developed and were successfully solved by MIP solvers (see for example Pochet and Wolsey (2006)). Another application of these formulations is the Lagrangian heuristic presented by Brahimi and Dauz`ere-P´er`es (2015) which exploits the mathematical program to generate better bounds.
Other exact solution approaches for the capacitated SILSP include branch-and-cut algorithms and the development of strong formulations to be solved by a MILP solver (Akbalik and Penz (2009), Akbalik and Pochet (2009), Atamt¨urk and Mu˜noz (2004)). Valid inequalities are usually derived by analyzing continuous 0-1 knapsack problems.It is also worth noting the combined dynamic- programming/B&B algorithm proposed by Chung et al. (1994).
In recent studies, Chubanov et al. (2006), Chubanov et al. (2008) and Ng et al. (2010) propose FPTAS for the capacitated SILSP with backlogging and with monotone cost structure. The running times of both procedures are not very relevant in practice. Finally, Chubanov and Pesch (2012)
develop an FPTAS for a capacitated SILSP where demands can take negative values in which case they correspond to supplies.
Another similar research stream, which seems to be less explored, is the consideration of approxi- mation formulations such as the ones proposed by Bitran and Matsuo (1986), Coleman and McKnew (1995), and Hardin et al. (2007). The latter focuses on the G/Z/Z/G problem. These formulations are supposed to be easier to solve and give acceptable error bounds or even optimal solutions in many cases (see Coleman and McKnew (1995)).
6.2. Inventory constraints
This section focuses on problems with special inventory characteristics, in particular problems with bounded storage capacity and/or perishable inventory.
6.2.1. Inventory capacity
Love (1973) was the first author to address the uncapacitated SILSP with inventory bounds.
Modeling this problem is straightforward; a lower bound and an upper bound are set for inventory variables. Love (1973) showed that the problem can be solved using anO(T3) dynamic programming algorithm by decomposing the problem into regeneration intervals. Guti´errez et al. (2001) propose a dynamic programming algorithm with the same complexity (O(T3)) but it runs faster than the algorithm of Love (1973). This complexity is reduced to O(T2) in Toczylowski (1995), Liu (2008).
Onal et al. (2012) showed that Liu’s¨ O(T2) algorithm was not correct. They proposed a fix to Liu’s algorithm which runs in O(T2) time. When all costs are linear and production variables are integer, this complexity is reduced toO(TlogT).
Atamt¨urk and K¨u¸c¨ukyavuz (2005) identify facet defining inequalities for the uncapacitated SILSP with bounded inventory. They considered two models: A first model with linear cost on inventory and a second model with linear and fixed costs on inventory. Atamt¨urk and K¨u¸c¨ukyavuz (2008) develop an O(T2) dynamic programming algorithm to solve the uncapacitated SILSP with inventory bounds and fixed costs on inventory. van Vyve and Ortega (2004) study the uncapacitated SILSP with fixed costs on inventory. They present an O(TlogT) dynamic programming algorithm and the convex hull of integer solutions. Gade and K¨u¸c¨ukyavuz (2011) complete these results and exhibit several challenges.
Several authors considered inventory bounds with other characteristics such as: backlogging (Hwang and van den Heuvel (2012)), lost sales (Hwang et al. (2013), Liu and Tu (2008), Liu et al. (2007), Loparic et al. (2001)), outsourcing (Chu and Chu (2007), Chu et al. (2013)), capacity constraints (Eren- guc and Aksoy (1990), Akbalik et al. (2015)), delivery time windows (Jaruphongsa et al. (2004)). In a recent study, van den Heuvel and Wagelmans (2008) showed that the following lot-sizing problems are equivalent to the lot-sizing problem with inventory bounds: the lot-sizing problem with a reman- ufacturing option, the lot-sizing problem with production time windows, and the lot-sizing problem with cumulative capacities. Absi and Kedad-Sidhoum (2009) studied safety stocks which is a soft version of lower bounds on inventories. The lower bound on stock is a target level rather than a strong constraint. The authors developed a polynomial time dynamic programming algorithm for the uncapacitated single-item version.
A survey of heuristics applied to dynamic demand lot-sizing with limited warehouse capacity is presented in Minner (2009).
6.2.2. Perishable inventory
The uncapacitated SILSP with perishable inventory considers a deterioration rate for the product in stock. Inventory holding costs depend on how long a product remains in the inventory. This is, for instance, the case for food, pharmaceuticals, chemicals and blood.
Several papers consider inventory deterioration and perishability in continuous time lot-sizing models (e.g. Ghare and Shrader (1963)). This subject was studied for discrete time models by Friedman and Hoch (1978) and Rajagopalan (1992). Nahmias (1982) extensively discusses the issue of perishability. Hsu (2000) develops a dynamic programming algorithm to solve the uncapacitated
SILSP with perishable inventory. The algorithm is based on a graph representation of the problem and runs inO(T4). Readers interested in this topic can refer to Pahl and Voß (2014) who propose a recent state-of-the-art review on production and supply chain planning models that consider deterioration and lifetime constraints.
Recently, ¨Onal et al. (2015) consider the uncapacitated and capacitated SILSP where each item has a deterministic expiration date. They study four mechanisms to allocate items to the consumers.
They show that the problem can be solved in polynomial time with all allocation mechanisms in the uncapacitated case, and become NP-hard for two allocation mechanisms in the capacitated case with time-invariant capacity. Dynamic programming algorithms, of complexity O(T2), O(T3) or O(T4) depending on the assumptions, are proposed for the polynomial problems. Finally, the two level lot sizing problem with perishable items was studied in ¨Onal (2016). He shows that determining optimal procurement (at the first level) and transfer (at the second level) plan is NP-hard, and presents polynomial algorithms for special cases.
6.3. Constraints on lot sizes 6.3.1. Minimum order quantities
There are at least two situations where problems with Minimum Order Quantity (MOQ) are relevant. The first situation is when a MOQ is imposed by the supplier or by some technical constraints (see for example Lee (2004)). The second situation, noticed by researchers interacting with companies, occurs when production managers prefer to impose a MOQ restriction instead of estimating setup costs (Okhrin and Richter (2011)). Hence, a MOQ is an alternative approach for reaching economies of scale.
Recently, Absi et al. (2016) showed that the uncapacitated SILSP with MOQ is NP-Hard.
Anderson and Cheah (1993) study a multi-item lot-sizing problem with MOQ and setup times.
They developed a Lagrangian relaxation heuristic which decomposes the problem into a set of sub- problems including single-item lot-sizing problems with minimum batch sizes. They propose a forward dynamic programming algorithm to solve these single-item problems. The authors do not specify the time complexity of their algorithm which might be exponential in the worst case. Special cases of the SILSP with minimum lot size were solved by Okhrin and Richter (2011) and Okhrin and Richter (2011). Okhrin and Richter (2011) considered the uncapacitated single-item lot-sizing problem with time independent MOQ for which they developed anO(T2). Okhrin and Richter (2011) propose an O(T3) algorithm to solve a special case of the problem where upper and lower bounds on production levels in addition to unit production and holding costs are constant. Hellion et al. (2012) extended this work by considering a problem with concave production and holding costs. They propose an exact algorithm to solve this problem inO(T6). Recently, Park and Klabjan (2015) studied the polyhedral structure of some SILSPs with constant MOQs and with constant and infinite production capacity.
They also propose a polynomial time algorithm for the the SILSP with constant capacities and time- independent MOQs. Park and Klabjan (2015) can also be considered as an excellent recent literature review of lot-sizing problems with production bounds.
6.3.2. Lot sizing with constant batch sizes or step-wise production costs
In the single-item lot-sizing problem with constant batch sizes or step-wise production costs (SICLSP-SW), production is made in constant batches of sizevt (which correspond to a vehicle size, for example) and there is a fixed cost (ft) per batch. The number of batches is an integer decision variable denoted byZt. Thus, the costs are step-wise, i.e. piece-wise linear with discontinuous steps.
Ct denotes the production capacity at periodt.
Minimize
T
X
t=1
(stYt+ptXt+ftZt+htIt) (12)
Subject to:(5)and
Xt≤Ct×Yt ∀t (13)
Xt≤vtZt ∀t (14)
Yt≤Zt ∀t (15)
Zt≤ dCt
vt
eYt ∀t (16)
I0=IT = 0 ∀t (17)
Yt∈ {0,1} ∀t (18)
Zt≥0 and integer ∀t (19)
It, Xt≥0 ∀t (20)
The objective function (12) minimizes the classical production and inventory costs plus the cost related to the number of batches. Constraints (5) and (13) are respectively the classical inventory balance equations and capacity constraints. Constraints (14) relate production variables and batch variables while Constraints (15) and (16) relate setup variables and batch variables. Constraints (17)-(20) define the decision variables.
van Vyve (2007) considers the SICLSP-SW without setup costs. He develops polynomial time algorithms for cases with and without backlogging. Akbalik and Pochet (2009) propose a new class of valid inequalities called mixed flow cover inequalities and developed cutting plane algorithms. Akbalik and Rapine (2012) consider the SICLSP-SW with constant capacities and developed a polynomial time algorithm that runs in O(T4) for the case where production capacity is a multiple of the batch size and anO(T6)-time algorithm for the case with arbitrary time-independent capacity.
Lot-sizing problems with constant batch sizes are directly related to problems with more general cost structures (ex. problems with non-linear production costs). The link between the two is detailed in Section 9.3. A similar problem is the integrated lot-sizing and vehicle dispatching problem studied by Lippman (1969) and Alp et al. (2003), for example, and for which more details are presented in Section 8.2.
The more general case where batch size can vary over time is studied by Akbalik and Rapine (2013). They propose a classification of uncapacitated SILSP with time-dependent batch sizes to identify NP-hard and different polynomial cases of the problem.
6.4. Subcontracting and/or outsourcing
It seems that the borderline between subcontracting and outsourcing is not very clear in the Operations Management literature. In lot sizing, both terms were used interchangeably. It is still important to recall a definition which is commonly used in Operations Management textbooks such as Stevenson (2014) where subcontracting enables the company to acquire temporary capacity while outsourcing is a contract with another company to provide some goods or services on a regular basis.
Chu et al. (2013) consider the uncapacitated SILSP with outsourcing/subcontracting, backlogging and limited inventory capacity. The backlogging level at each period is supposed to be limited.
The authors show that this problem can be solved in O(T4logT). Huang et al. (2008) introduce a polynomial time algorithm for a SILSP with outsourcing, backlogging, and non-decreasing inventory capacity. Wang et al. (2011) propose a dynamic programming algorithm that runs in O(T2) to solve a SILSP with remanufacturing and outsourcing without backlogging.
7. Complex structures
7.1. Multiple levels
In production planning with multi-stage, multi-level or multi-echelon systems, the product can be produced and/or stored at different stages. Transportation costs and times from one stage to another can be considered or ignored. These problems can occur in different supply chain structures: Serial systems, single-source multi-destination systems, multi-sourcing systems, or more general structures.
Serial supply chain systems occur when value is added to a product in a sequence of production facilities. Zangwill (1969) propose a dynamic programming algorithm that runs inO(LT4) to solve a serial multi-stage problem withT time periods andLlevels (L >2) and without capacity constraints.
The same algorithm runs in O(T3) when L = 2 and production capacities are constant. Kaminsky and Simchi-Levi (2003) work on a three-level model in which the first and third levels are production stages, and the second level is a transportation stage. While production stages are capacitated, the transportation stage is supposed to have an infinite capacity. In Lee et al. (2003), several structural properties and a polynomial time algorithm is presented for a two-level problem with a stepwise transportation cost function. van Hoesel et al. (2005) propose a polynomial time (O(T7)) dynamic programming algorithm to solve a two-level and multi-level problems with constant capacities. Melo and Wolsey (2010) solve an uncapacitated two-level lot-sizing problem in O(T2logT) and propose an extended formulation with O(T3 variables and O(T2) equality constraints. Zhang et al. (2012) consider the multi-echelon lot-sizing problem in series without capacity constraints where the output of an intermediate echelon has also its own external demand. For the version with two levels, they propose an O(T4) dynamic programming algorithm to solve the problem optimally and gave a tight compact extended formulation. A hierarchy between the alternative formulations is also established.
Denizel et al. (2010) consider the two-level and three-level uncapacitated serial lot-sizing problems.
They propose a strong formulation based on the shortest path representation, together with O(T3) andO(T4) dynamic programming algorithms to solve the two-level and three-level lot-sizing problems, respectively.
In a single-source multi-destination system, there is one single facility which distributes the product to a set of destination facilities to add value to the product or to sell it to the consumer. The basic problem is mostly known as the one-warehouse multi-retailer (OWMR) problem. In the OWMR problem, there is a single warehouse which orders from its supplier to replenish a set of retailers.
Each retailer faces its own external demands. The products can be inventoried at the warehouse or at the retailers. Replenishing the retailers from the warehouse and replenishing the warehouse from the supplier incur fixed ordering costs. Other costs include the per-unit purchasing and inventory holding costs. The OWMR problem consists of determining the quantities to be ordered in each time period from the warehouse and from the retailers. The OWMR problem is an extension of the Joint Replenishment Problem (JRP) and it is NP-hard (Arkin et al. (1989)). In the latter, inventory cannot be kept in the warehouse. This relationship was used by Arkin et al. (1989) to show that the OWMR problem is NP-hard. Recent reviews of the rich literature on the JRP can be found in Khouja and Goyal (2008) for the static demand models and in Robinson et al. (2009) for the dynamic demand case, where the namecoordinated lot-sizing problem is used instead of joint replenishment problem. A recent literature review of the OWMR problem can be found in Solyalı and S¨ural (2012), who present strong formulations and classifications for variants of the OWMR problem with dynamic demands. A special problem close to both OWMR and JRP is the one studied by Anily and Tzur (2005).
The multi-sourcing lot-sizing problem models several real-life situations such as multiple parallel machines, multiple transportation modes, or supplier selection (Aissaoui et al. (2007)). The multi- sourcing uncapacitated SILSP (MS-SILSP) is a direct generalization of the uncapacitated SILSP. It is defined by a given number of sources M from which we can order the single product. With each sourcemis associated a time dependent setup costfmtand a time dependent unitary production cost pmt. The storage is done in a unique depot. Production variables (xmt) and setup variables (ymt) are indexed bymandt. The goal is to minimize the total production and setup costs as well as inventory costs. The flow conservation constraints and production constraints are modeled as follows:
st−1+
M
X
m=1
xmt=dt+st∀t∈ {1, . . . , T} (21)
xmt ≤
T
X
t0=t
dt0
!
ymt∀t∈ {1, . . . , T} ∀m∈ {1, . . . , M} (22) To the best of our knowledge, the MS-SISLP was not addressed in the literature most probably because of its simplicity. Solving this problem is a direct generalization of the improved version of the Wagner and Whitin algorithm. It can be solved with an O(M T logT) dynamic programming algorithm. Several studies addressed more general versions of the MS-SISLP. Akbalik and Penz (2009) addressed the MS-SISLP with constant capacities and integer production variables. They solved the problem optimally using a pseudo-polynomial dynamic programming algorithm. Recently, Absi et al.
(2013) addressed the multi-sourcing lot-sizing problem with different carbon emission constraints. In a case study, de Toledo and Shiguemoto (2005) consider a lot-sizing problem of a single item in several production centers without capacity constraints.
A more general supply chain structure was addressed by Yilmaz and C¸ atay (2006) who consider a single-item, multi-supplier, multi-producer, and multi-distributor production/distribution network.
They propose relaxation-based heuristics to solve the problem. Finally, in a case study paper, Brahimi and Khan (2014) introduce a MIP formulation, solved using a commercial solver, for an extended single-item three-stage problem in the lube oil industry. The problem also integrates warehouse location decisions and allows different vehicles with different capacities to be used.
7.2. Remanufacturing
The last decades have seen the birth of several concepts associated with the development of green supply chains or sustainable supply chains. One of the most common concept is reverse logistics, which includes all processes that support the return of used products for recycling or reuse, such that disassembly, remanufacturing and refurbishing. Remanufacturing is the set of disassembly and recovery operations to repair a product so that it is equivalent to the original product. Generally, a remanufactured product must meet the same client expectations as new products. Guide et al.
(1999) presented the general scheme of remanufacturing systems including remanufacturing or reuse of components from the disassembly of returned products.
The uncapacitated SILSP with a remanufacturing option (SILSP-R) is defined with known quan- tities of returned products in each period. These products can be remanufactured and considered as new ones. Customer demand can be satisfied from two sources (manufactured and remanufactured products). The goal is to determine when production takes place and when remanufacturing takes place and how many products are manufactured and how many are remanufactured. The objective is to minimize the classical total cost plus remanufacturing costs and holding costs for returned prod- ucts. Teunter et al. (2006) consider two variants of the uncapacitated SILSP with a remanufacturing option. In the first one, manufacturing and remanufacturing have separate setup cost (SILSP-Rs).
In the second one, manufacturing and remanufacturing have a joint setup cost (SILSP-Rj). Teunter et al. (2006) introduce an aggregate MIP formulation of SILSP-Rs. In addition to customer demand dt, additional parameters are required for each periodt: the number of returns, the unit holding costs for serviceables (product delivered to customers) and returns, the setup costs for manufacturing and remanufacturing, and the unit production costs for manufacturing and remanufacturing. Moreover, it is necessary to differentiate the inventory of serviceables from the inventory of returns, the number of manufactured items from the number of remanufactured items, the manufacturing setup from the remanufacturing setup. For the problem variant with joint setups (SILSP-Rj), the MIP model can be slightly modified.
Richter and Sombrutzki (2000) were among the first researchers who considered remanufacturing in the uncapacitated SILSP with stationary costs. They made the strong assumption that the number
of returned products is sufficient to satisfy all demands. They solved the problem using a Wagner and Whitin like algorithm. Richter and Weber (2001) enriched the previous model by considering variable manufacturing and remanufacturing costs. Golany et al. (2001) studied the same problem in which it is possible to dispose returned products. They showed that the problem is NP-hard for general concave costs and solved it in O(T3) when all costs are linear. Yang et al. (2005) showed that the same problem is NP-hard even with time-invariant costs. Teunter et al. (2006) showed that the SILSP-Rj with stationary costs can be solved with an O(T4) dynamic programming algorithm.
Recently, Fazle Baki et al. (2014) showed that the SILSP-Rs is NP-Hard. Retel Helmrich et al. (2014) showed that the general SILSP-Rj is NP-Hard and that the SILSP-Rs is NP-Hard even if all costs are stationary.
Teunter et al. (2006) propose modifications of classical heuristics (Silver-Meal, Least Unit Cost, and Part Period Balancing) to solve the SILSP-R. Recently, Schulz (2011) proposes an improvement of the modified Silver-Meal heuristic for the SILSP-Rs.
Pan et al. (2009) studied special cases of the capacitated lot-sizing problem with production, disposal, and remanufacturing. With only disposal or remanufacturing the problem can be converted into a capacitated lot-sizing problem. When disposal and remanufacturing capacities are considered, they propose a pseudo-polynomial time algorithm. For the uncapacitated production and capacitated remanufacturing case, they propose an exponential time algorithm. Zhang et al. (2012) deal with a capacitated lot-sizing problem in which the demands for manufactured and remanufactured products are distinct, share the same production resources but have different setup costs. They use a Lagrangian relaxation approach of capacity constraints to solve the problem. In Parsopoulos et al. (2015), the performance of a Differential Evolution (DE) algorithm is investigated.
8. Integrating other decisions
It has been shown in many recent studies that coordinated models integrating production planning with other types of decisions in companies (e.g. distribution, scheduling, etc.) generates higher profits or reduces costs. A survey of integrated models with single-item lot-sizing problems is presented below.
8.1. Scheduling
The goal in scheduling problems is to assign and sequence jobs (or tasks) on one or multiple ma- chines to minimize operational objectives such as the maximum completion time of all jobs (makespan) or the sum of the delays (compared to given due dates) of the jobs. In a production setting, jobs are often lots whose quantities are decided by solving lot-sizing problems. Most integrated lot-sizing and scheduling problems are multi-item problems since the complexity of integrating scheduling decisions is often due either to the setup times between two consecutive lots of different items (as in the Dis- crete Lot-sizing and Scheduling Problem, DLSP, see Fleischmann (1990)) or to the series of operations (route) for each lot that must be sequenced on multiple machines (as in the job-shop lot-sizing and scheduling problem, see Lasserre (1992)).
To our knowledge, the only papers that consider single-item integrated lot-sizing and scheduling problems, more precisely the single-item DSLP, are the ones of Gavish and Johnson (1990), van Hoesel et al. (1994) and van Eijl and van Hoesel (1997). The single-item lot-sizing problems surveyed in the previous sections are usually tactical problems that consider the production planning of one product in relatively long time periods (e.g. days or weeks), while the DLSP considers micro-periods (e.g.
hours). Each time period usually has three states: Fully used for a setup, fully used for a production, or unused (off). Although the problem is not called single-item DLSP, Gavish and Johnson (1990) propose an approximation scheme, based on a dynamic programming algorithm, that converges to solution that is less than or equal to units of the optimal objective function. van Hoesel et al.
(1994) introduce two approaches to solve the problem. The first approach is based on a strong linear programming formulation whose solutions are integer for some conditions. The second approach is a dynamic programming algorithm that runs inO(T +DlogD) whereD is the cumulative demand on
