Proceedigs of the 15th IFAC Symposium on

Proceedigs
Proceedigs ofof the
the 15th
15th IFAC
IFAC Symposium
Symposium on
on
Information
Proceedigs Control
of the Problems
15th IFAC in Manufacturing
Symposium on
Information
Information Control
Control Problems
Problems in
in Manufacturing
Available
Manufacturingonline at [Link]
May 11-13, 2015.
Information Ottawa,
Control Canada
Problems in Manufacturing
May 11-13,
May 11-13, 2015.
2015. Ottawa,
Ottawa, Canada
Canada
May 11-13, 2015. Ottawa, Canada
ScienceDirect
IFAC-PapersOnLine 48-3 (2015) 1954–1959
Production
Production scheduling
scheduling to
to optimize
optimize the
the product
product
Production
assortment scheduling
in case of to optimize
constrained the product
capacity and
assortment
assortment in
in case
case of
of constrained
constrained capacity
capacity and
and
customer-driven
customer-driven substitution
substitution
customer-driven substitution
Elisa
Elisa Gebennini
Gebennini
∗ Luca Zeppetella ∗ Andrea Grassi ∗ Bianca Rimini ∗
∗∗ Luca Zeppetella ∗∗ Andrea Grassi ∗∗ Bianca Rimini ∗∗
Elisa
Elisa Gebennini ∗ Luca
Gebennini Luca Zeppetella
Zeppetella ∗ Andrea
Andrea Grassi
Grassi ∗ Bianca
Bianca Rimini
Rimini ∗
∗ Dipartimento di Scienze e Metodi dell’Ingegneria, Università degli Studi di
∗∗ Dipartimento di Scienze e Metodi dell’Ingegneria, Università degli Studi di
Dipartimento
∗ Dipartimento
Modena di Scienze
di Scienze ee Metodi
Metodi dell’Ingegneria,
dell’Ingegneria, Università
Università degli Studi
degli Studi di
di
Modena eee Reggio
Modena Reggio Emilia
Emilia Via
Via Amendola
Amendola 2,2, 42122
42122 Reggio
Reggio Emilia,
Emilia, Italy
Italy
Modena e Reggio
Reggio Emilia
Emilia
(e-mail:
(e-mail:
Via
Via Amendola
Amendola 2,
2, 42122
42122 Reggio
Reggio
[Link]@[Link])
[Link]@[Link])
Emilia,
Emilia, Italy
Italy
(e-mail:
(e-mail: [Link]@[Link])
[Link]@[Link])
[Link]@[Link])
(e-mail:
(e-mail: [Link]@[Link])
[Link]@[Link])
(e-mail:
(e-mail:[Link]@[Link])
(e-mail: [Link]@[Link])
[Link]@[Link])
(e-mail:
(e-mail:
(e-mail: [Link]@[Link])
[Link]@[Link])
[Link]@[Link]).
(e-mail: [Link]@[Link]).
(e-mail: [Link]@[Link]).
(e-mail: [Link]@[Link]).
Abstract: This
Abstract: This paper
paper deals
deals with
with the
the production
production scheduling
scheduling problemproblem by by considering
considering product product assortment
assortment
Abstract:
Abstract:
and demand This
This paper
paper
substitution deals
deals with
with
issues, the
the
along production
production
with capacityscheduling
scheduling
and problem
problem
production by
by considering
considering
constraints. product
product assortment
assortment
and
and demand
demand substitution issues, along with capacity and production constraints.
and
In this
In this study substitution
demand
study substitution
we distinguish
we distinguish issues,
issues, along
between
between
with
with capacity
alonglong-term
long-term capacity and
product
product
production
and assortment
production and
assortment constraints.
constraints.
and short-term product
short-term product assortment.
assortment.
In
In
The this
this
termstudy
study we
we
“long-term distinguish
distinguish
product between
between long-term
long-term
assortment” is used product
product
here toassortment
assortment
indicate theand
and short-term
short-term
whole set of product
product
alternative assortment.
assortment.
products
The
The term “long-term product assortment” is used here to indicate the whole set of alternative products
that term
The
that term
a
“long-term
“long-term
a company
company is able
is
product
product
able assortment”
to produce
to produce over aais
assortment”
over
used
islong
long here
here to
usedhorizon
horizon indicate
to of
of time. the
indicate
time. On whole
the
On whole
the other
the
set
set of
other of alternative
alternative
hand,
hand,
products
products
the “short-term
the “short-term
that
that
productaa company
company
assortment” is
is able
able to
to produce
produce
represents the over
over
products aa long
longthathorizon
horizon
the companyof
of time.
company [Link] On
Onablethe toother
theto offer hand,
other hand, its the
to its the “short-term
“short-term
customers at aa
product
product assortment”
assortment” represents
represents the
the products
products that
that the
the company is able
able to offer
offer to
to its customers
customers at
at aa
product
time.
time. We
We assortment”
assume
assume that,
that, represents
in
in general,
general, the
for
for products
reasons
reasons that
of
of the
capacity
capacity company
constraints
constraints is able
and
and to offer
operative
operative to its
costs,
costs, customers
the
the short-term
short-term at
time.
time. We
We assume
assume
product assortment
assortment is that,
that, in
in general,
general,
is aa subset
subset of for
for
of the reasons
reasons
the long-term of
of
long-term productcapacity
capacity constraints
constraints
product assortment.
assortment. Thus, and
and operative
operative
Thus, the costs,
costs,
the objective
objective is the
the
is to short-term
short-term
to optimize
optimize
product
product assortment is
product assortment
the production
the production is aa subset
schedule
schedule subset of
of the
the long-term
and, consequently,
and, long-term
consequently, product
product assortment.
the short-term
the short-term assortment.
product assortment
product
Thus,
Thus, the
assortment the byobjective
objective
by considering
considering
is
is to
to optimize
optimize
capacity
capacity
the
the
and production
production
production schedule
schedule
constraints, and,
and, consequently,
consequently,
customer-driven the
the short-term
short-term
demand product
product
substitution and assortment
assortment
production by
byandconsidering
considering
inventory capacity
capacity
costs. In
and
and production
production constraints,
constraints, linearcustomer-driven
customer-driven demand
demand substitution
substitution and
and production
production and
and inventory
inventory costs.
costs. In In
and production
particular, a constraints,
mixed-integer customer-driven
programming demandmodel substitution
is proposed and in production
a multi-period and inventory
and costs.
multi-product In
particular, aa mixed-integer
particular, mixed-integer linear programmingprogramming model is is proposed in in a multi-period and and multi-product
perspective.a mixed-integer linear
particular,
perspective. linear programming model model is proposed
proposed in aa multi-period
multi-period and multi-product
multi-product
perspective.
perspective.
The validity of the model is proved by discussing a real-world case study from the brewery industry.
The
The validity of the model is proved by discussing a real-world case study from the brewery industry.
The validity
validity of of the
the model
model is is proved
proved by by discussing
discussing aa real-world
real-world case case study
study fromfrom the the brewery
brewery industry.
industry.
© 2015, IFAC (International Federation of Automatic Control) Hosting by Elsevier Ltd. All rights reserved.
Production scheduling,
Keywords: Production
Keywords: scheduling, DemandDemand substitution,
substitution, ProductProduct assortment,
assortment, Linear Linear programming
programming
Keywords:
Keywords:
model Production
Production scheduling,
scheduling, Demand
Demand substitution,
substitution, Product
Product assortment,
assortment, Linear
Linear programming
programming
model
model
model
1. INTRODUCTION
1. INTRODUCTION that is
that is required,
required, especially
especially in in case
case of of unfiltered
unfiltered beers. beers. As As aa
1. INTRODUCTION
1. INTRODUCTION that is
that is required,
consequence,required, only especially
especially
a subset in
in
of case
case
beer of unfiltered
of
types unfiltered
are beers. atAs
beers.
available Astheaa
consequence,
consequence, only
only aa subset of
of beer
subsetfavorite beerbeertypes
types are available
areavailable,
available he/sheat
at the
the
This
This paper
paper deals
deals with
with the
the production
production scheduling
scheduling problem
problem (i.e.,
(i.e., consequence,
same time. If only
a a subset
customer’s of beer types is are
not available at the
This paper deals with the production scheduling problem (i.e., same
same time.
time. If
If aa customer’s
customer’s favorite
favorite beer
beer is
is not
not available,
available, he/she
he/she
This
the paper dealsofwith
the allocation
allocation the production
available production scheduling
resources problem
over time) (i.e., same
time) time. Ifaa adifferent
may choose
choose customer’s
different one,favorite
presumably beer isofofnot available,
a similar typehe/she
(e.g.,
the
by allocation of
the considering
allocation of
of
(i)
available
available
available
capacity
production
production
production
and production
resources
resources
resources
constraints
over
overontime)
over time)
one
may
may choose
choose a different
different one,
one, presumably
presumably of aaaissimilar
similar type
type (e.g.,
(e.g.,
by may
another hoppy a beer style one,
if presumably
the favorite of
type similar
a pale type
ale (e.g.,
beer).
by considering
by
hand,considering
considering
and (ii)
(i)
(i) capacity
(i) capacity
capacity
product
and
and production
and
assortment production
production
requirements
constraints
constraints
constraints
on the
on
on
one
one another
onother
one another
another
hoppy
hoppy
hoppy
beer
beer
beer
style
style
style
if
if
if
the
the
the
favorite
favorite
favorite
type
type
type
is
is
is
aa pale
a pale
pale
ale
ale
ale
beer).
beer).
beer).
hand, Thus, it it is
is important
important (i) (i) to
to meet
meet the the customer’s
customer’s expectations
expectations
hand, and
hand,
hand. and (ii)
and (ii) product
(ii) product assortment
product assortment requirements
assortment requirements on
requirements on the
on the other
the other Thus,
other Thus, it is
is important
important (i) to
to meet
meet the orcustomer’s
customer’s expectations
hand. Thus,
by
by it
offering
offering his/her favorite
his/her (i)
favorite product
product the or similar expectations
a similar
a one (e.g.,
one (e.g., a
hand.
hand. by
by offering
offering
similar taste his/her
his/her
in the favorite
favorite
brewery product
product
case) and or
or
(ii) a
atosimilar
similar
rotate one
the (e.g., aaa
oneproducts
(e.g.,
The case
The case isis that
that ofof aa company
company which which is is able
able to
to produce aa varietyvariety similar similar taste
taste in in the brewery
theproduct case)
case) and
breweryassortment and (ii)
(ii) to
to rotate
rotate the
the products
products
Thealternative
The
of case is
case is that
thatproducts
of aa company
of company
but, forwhich
which
reasonsis able
is able
of to produce
to produce
produce
capacity variety similar
a variety
a
limitations in
in the taste
the short-term
short-termin the brewery
product case)
assortment and (ii)
so to
so that
thatrotate
all the
all the
the products
products
of alternative
of alternative
alternative products
products but, for
but,afor
for reasons
reasons of capacity
of capacity
capacity limitations
limitations in
in the
the short-term
short-term
long-term product product
product assortment
assortment
product assortment
assortment can so
so
can be that
that all the
eventuallyproducts
all
be eventually the products
offered
of
and
and operative products
operative costs, only
costs, onlybut, a reasons
subset
subset of of
of those
those products
products limitations
can be
can be in in the
the long-term
long-term product assortment can be be eventually
eventually offered
offered
and
and operative
operative costs,
costs, only
only a
a subset
subset of
of those
those products
products can
can be
be in
to
to the
the long-term
customer.
customer. product
In
In this
this assortment
way,
way, the
the can
customer
customer is
is satisfied
satisfied offered
(or, at
(or, at
available
available at
at the
the same
same time.
time. Thus,
Thus, we
we can
can distinguish
distinguish between:
between: to the customer. In this way, the customer is satisfied (or,the
at
available at the same time. Thus, we can distinguish between: to the
least,
least, customer.
partially
partially In this
satisfied)
satisfied) way,
in
in the
the the
short
shortcustomer
term,
term, is
and
and satisfied
he/she
he/she (or,
has
has at
the
available at the same time. Thus, we can distinguish between: least, partially satisfied) in the short term, and he/she has the
long-term product
••• long-term product assortment:
assortment: the the whole
whole set set of
of alternative
alternative opportunityleast, partially
opportunity of satisfied)
of choosing
choosing among in the short
among aa wider
wider term, and he/she
variety
variety of products
of has the
products in
in
long-term
long-termthat
• products product
product
the assortment:
assortment:
company is the
the whole
able whole
to set
set of
produce alternative
of (according
alternative the opportunity
opportunity
long [Link]
of In choosing
choosing
such a among
among aa the
situation, wider
wider variety
variety
concept of of
of products
products in
“substitutable in
products
products
products
to its
that
that the
that
production the
company
company is
theresources);
company is able
is able to
able to produce
to produce (according the
produce (according
(according the long
the long term.
long
demand” term.
term.
plays
In
In
In
a
such
such aaa situation,
such
fundamental situation,
situation,
role.
the
the
the
We
concept
concept
concept
have to
of
of “substitutable
of
take “substitutable
“substitutable
into account
to
to its
its production
production resources);
resources); demand”
demand” plays
plays aaa fundamental
fundamental role.
role. We
We have
have to take
take into
to increase account
into because
account
••• to its production
short-term
short-term product
product resources);
assortment: the
assortment: the subset
subset of alternative demand”
of alternative that
that the plays
the demand
demand fundamental
of productrole.
of aa product We
in stock
in stock havemayto
may take
increase into account
because
short-term
• short-term
products that thatproduct
product
the companyassortment:
assortment:
company offers thethe subset
itssubset
to its customersof alternative
of alternative time. that
at aa time. that the
productdemand
the demand is in of
in some
some a product
of a product in
way aa substitutestock
in stock for
substitute may
may
for someincrease
increase because
other because
product
products
products the offers to customers at that
that product
product is
is in in some
some way
way aa substitute
substitute for some
some other
other product
product
products that that the
the company
company offers offers to to its
its customers
customers at at aa time.
time. that which product
is is
currently way
unavailable (McGillivray for some
and other
Silver, product
1978).
The problem is to dynamically optimize the short-term product which
which is
is currently
currently unavailable
unavailable (McGillivray
(McGillivray and
and Silver,
Silver, 1978).
1978).
The
The problem
problem is
is to
to dynamically
dynamically optimize
optimize the
the short-term
short-term product
product which is currently unavailable (McGillivray and Silver, 1978).
The problem
assortment is
under to dynamically
a given long-term optimize
productthe short-term
assortment product
by con- The literature about substitutable demand distinguishes be-
assortment
assortment
assortment
sidering
under
under aaaand
under
capacity
given
given
given
long-term product
product assortment
long-termconstraints,
long-term
production product assortment
assortment
economic
by
by con- The
con-
byissues
con- The literature
The
tween literature
literature
one-way
about
about
about
substitutable
substitutable
substitutable
substitution and two-way
demand
demand
demand
distinguishes
distinguishes
distinguishes
substitution. One-way
be-
be-
be-
sidering
sidering capacity
capacity and
and production
production constraints,
constraints, economic
economic issues
issues tween
tween one-way
one-way substitution
substitution and
and two-way
two-way substitution.
substitution. One-way
One-way
sidering capacity anddemand
and customer-driven
customer-driven production constraints, economic issues tween
substitution. one-way
substitution
substitution assumes
assumessubstitution
that and two-way
that products
products can be
can besubstitution.
ordered based One-way
based on anan
and
and customer-driven demand
and customer-driven demand substitution.
demand substitution.
substitution. substitution
substitution
attribute, suchassumes
assumes
as that or
that
quality products
products
speed can
of be ordered
canservice,
be ordered
orderedso based
based
that
on
on an
on
products an
As an example, let us consider a microbrewery. The company attribute,
attribute, such
such as
as quality
quality or
or speed
speed of
of service,
service, so
so that
that products
products
As
Asablean
an example,
example, let us
us consider
letdifferent
consider a microbrewery. The company attribute,
with higher
higher suchlevelsas quality
of thethe or speed of
attribute canservice,
substitute so that for products
products
As
is
is an
able example,
to producelet
to produce us consider
different typesaa of
types
microbrewery.
microbrewery.
of beer such
beer such as The ale
The
as pale
pale company
ale beers, with
company
beers, with higher
with higher
lower
levels
levels of
levels
levels
of
of thethe attribute
attribute
attribute
attribute.
can
can
can
This
substitute
substitute
substitute
kind of
for
for
for products
products
substitution
is
is able
able
lager to
to
beers produce
produce
or wheatdifferent
different
beers. types
types
Each of
of beer
beer such
such
production as
as pale
pale
of a ale
ale
beer beers,
beers,
type with
with lower
lower levels
levels of
of the
the attribute.
attribute. This
This kind
kind of
of substitution
substitution
lager
lager beers
beers or
or wheat
wheat beers.
beers. Each
Each production
production of of aaa beer
beer type
type withalsolower
is also calledlevels of the attribute.
“hierarchical substitution” This (see,
kind e.g.
(see, of substitution
e.g. Bitran andand
lager
requires
requires
beers or
aaa certain
certain wheat
amount
amount
beers.
of
Each production
of fermentation/maturation
fermentation/maturation of beer
timetype
time and is
and is also
is
Dasu,
called
also 1992;
calledBassok
called
“hierarchical
“hierarchical
“hierarchical
et al.,
substitution”
substitution”
substitution”
1999; Rao et (see,
(see,
al., e.g. Bitran
e.g.
2004). Bitran
Bitran
Accord-and
and
requires
requires
one or a
more certain
certain amount
amount
fermentation of
of
[Link]/maturation
fermentation/maturation
Moreover, high inventory time
time and
and
costs Dasu,
Dasu, 1992;
1992; Bassok
Bassok et
et al.,
al., 1999;
1999; Rao
Rao et
et al.,
al., 2004).
2004). Accord-
Accord-
one or
or more
more fermentation
one incurred fermentation tanks.
tanks. Moreover,
Moreover, high high inventory
inventory costs
costs ing Dasu,
ing to 1992;
to Stavrulaki Bassok
Stavrulaki (2011) et al., 1999;
(2011) one-way substitution Rao et al., 2004).
substitution is generally Accord-
generally not
one
are
are or more
incurred fermentation
as aa result
as result of oftanks.
the Moreover, high
the temperature-controlled
temperature-controlled inventory costs
storage
storage ing to
ing to Stavrulaki
Stavrulaki (2011) (2011) one-way substitution is
one-way substitution
one-way generally not
is generally
is not
not
are incurred as a result of the temperature-controlled
are incurred as a result of the temperature-controlled storage storage
2405-8963 ©
Copyright © 2015, IFAC (International Federation of Automatic Control)
2015 IFAC 2028Hosting by Elsevier Ltd. All rights reserved.
Copyright
Peer review©
Copyright 2015
©under IFAC
2015 responsibility
IFAC 2028
2028Control.
of International Federation of Automatic
Copyright © 2015 IFAC 2028
10.1016/[Link].2015.06.374
INCOM 2015
Elisa Gebennini et al. / IFAC-PapersOnLine 48-3 (2015) 1954–1959 1955
May 11-13, 2015. Ottawa, Canada

appropriate when the consumer is ultimately the one deciding We assume that the products of the long-term product assort-
whether to substitute or not. On the other hand, models that ment belong to the same category. Thus, if a product is not
allow two-way substitutability enable customers to substitute available because it is stocked-out, it is substituted by another
among products within the same category. An interesting study product or a lost sale occurs. In other words, for each couple
in the retailing sector was carried out by Yücel et al. (2009). of products of the long-term product assortment a substitution
Two-way substitution is the perspective that we adopt in this pa- rate can be defined. This is a most important concept because, in
per. Note that in case of hierarchical substitution an adaptation the context under analysis, we assume that not all the products
cost should be taken into consideration (Tripathy et al., 1999). of the long-term product assortment may be available at the
Such a cost can be seen as a more general substitution cost same time. This is due to capacity limitations and operative
in case of two-way substitution, as in the case under analysis costs that characterize the production process, as explained in
where products are not characterized through quality. more detail in the following paragraphs (limited number of
production resources, batch capacities, lead times, etc.).
Another interesting distinction that can be found in literature is
between stockout-based substitution and assortment-based sub- As a result, only a subset of products are available (not stocked-
stitution (see, e.g., Kök and Fisher, 2007; Yücel et al., 2009). out) and can be offered to the customers at a certain instant of
Stockout-based substitution occurs when the customer replaces time. This subset, that is supposed to vary over the planning
his/her favorite product with another one because it is stocked- horizon in order to guarantee a proper rotation of products,
out at the moment of the purchase decision; assortment-based is called short-term product assortment. The objective is to
substitution occurs when the favorite product is not in the as- schedule the production orders so that the short-term product
sortment (i.e., in the portfolio of products offered by the com- assortment is optimized over the planning horizon by consider-
pany). According to these definitions, the problem addressed ing set-up costs, inventory holding costs and substitution costs.
in this paper should refer to the stockout-based substitution.
However, in our case this distinction is not conclusive. This is In particular, the main assumptions and conventions of the
model proposed in this paper can be summarized as follows:
because the long-term assortment is given and it is supposed to
meet the customers’ preferences on the whole. The objective • Time is discrete, so that the planning horizon is decom-
is to optimize the short-term assortment, i.e., to choose the posed into time units (i.e., time periods of equal length).
products of the long-term assortment that must be available (not • The long-term product assortment (i.e., the whole set of
stocked-out) at a certain instant of time. Thus, both inventory products that can be produced over the planning horizon)
and assortment issues are jointly taken into consideration. is given and fixed. For each time unit, the short-term
The number of substitution attempts is another feature that product assortment is a subset of the long-term product
assortment. It is the subset of products that are available
differentiates the models involving demand substitution issues.
In general, since Kök (2003) shows that a multi attempts model to be sold to the customers in that time unit. Thus, the
can be approximated with a single attempt substitution model short-term product assortment of any time unit depends
on the quantity of each products that becomes available
with increased rates, most of the literature proposes single at-
tempt models. For example, Smith and Agrawal (2000) provide in that time unit (according to the production scheduling)
a multiperiod model for the product assortment problem under and the inventory levels.
• The short-term product assortment is supposed to vary
both assortment-based and stockout-based substitution, with
one substitution attempt only. On the contrary, in the present from one time unit to the next so that all the products can
study multiple substitution attempts are taken into account in be eventually offered to the customers. In other words, the
product rotation requirements must be satisfied over the
order to avoid any approximation error.
planning horizon.
In particular, by taking inspiration from Yücel et al. (2009) • The demand of all the products of the long-term product
which studied demand substitution in the retailing sector, we assortment is known and deterministic for each time unit.
developed a mixed-integer linear programming model able First, the demand of the products that are available in that
to include significant production issues. The objective is to time unit is satisfied (i.e., the products of the short-term
dynamically optimize the short-term product assortment by product assortment). Then, the remaining inventory can
introducing capacity and lead time constraints and product be used to satisfy the demand of the products that are
rotation requirements in a multi-period setting. The optimal stocked out. This demand is redistributed to the available
solution is generated by minimizing the sum of setup costs, products of the short-term product assortment according
inventory holding costs and substitution costs. to substitution rates. As in Yücel et al. (2009), a “dummy”
product is introduced in order to model lost sales.
The remainder of this paper is organized as follows. Section
• The substitution rates are known and fixed for each couple
2 describes the problem and the main assumptions. Section 3
of products (including the “dummy” product correspond-
presents the mathematical model. In section 4 the proposed
ing to lost sales). This assumption is common in stockout-
model is applied to a real world problem from the brewery
based substitution models (see, e.g., Netessine and Rudi,
industry. Conclusions are drawn in Section 5, where possible
2003). In this way we do not attempt to model the decision
extensions to the proposed model are also discussed.
process of the individual customer, but we consider the
aggregate customers’ behaviour. Then, according to Smith
2. PROBLEM STATEMENT and Agrawal (2000), we assume that customers choose
independently of each other and the substitution rates are
As introduced in the previous section, the long-term product independent of the total number of customers in any time
assortment is supposed to be given. It is the whole set of unit.
products that can be produced and offered to the customers on • Multi-level substitution is allowed. Thus, when a product
a planning horizon of several periods of time. is not available its demand is redistributed in a number of

2029
INCOM 2015
1956 Elisa Gebennini et al. / IFAC-PapersOnLine 48-3 (2015) 1954–1959
May 11-13, 2015. Ottawa, Canada

distribution attempts (see Yücel et al., 2009). In partic- • z jst : 1, if station s is occupied by product j in time unit t
ular, for each product we have to consider: (i) the first- (except for the first time unit when the production order is
choice demand incoming to the product, (ii) the substitu- launched); 0, otherwise.
tion demand incoming to the product, one for each level
of substitution and (iii) the substituted demand outgoing Input Data
from the product, one for each level of substitution.
• There is a given number of production resources or sta- • d jt : demand of product j in time unit t;
tions (e.g., fermentation tanks in the brewery case) that • I 0j : inventory level of product j at the beginning of the
might work in a parallel manner. Each station is charac- planning horizon;
terized by: • Cs : batch capacity of station s;
· batch capacity: at a certain time unit, either no prod- • LT j : production lead time (in number of time units) of
uct is produced or a certain product is in process and product j;
the quantity is exactly the batch capacity; • w jk : substitution rate, i.e., proportion of customers whose
· lead time: each product in process on a station re- preference is product j that are willing to replace product
quires a given number of time units (depending on j with product k (w j j = 0);
the specific product) before production is completed; • T r : maximum number of time units between two produc-
· single product per batch: if a product is in process on tion order of a given product (this parameter defines the
a certain station, that station is devoted to that product product rotation requirement);
until its production is completed (i.e., for a number of • csetup : unit setup cost;
time units equal to the lead time of that product). • chj : unit holding cost for product j;
• When a certain quantity of a product becomes available
• csub
m j : penalty cost of the m-th level of substitution from
either it is sold to the customer in that time unit or it
is stored. The timing convention used to mathematically product j (lost sales is represented as substitution to a
treat the products’ flows is as follows: the demand of each “dummy” product).
product is realized at the beginning of any time unit while
changes in the inventory levels occur at the end of the
time unit. The present formulation of the problem does not 3.2 Model formulation
include storage capacity constraints, but inventory holding
costs are taken into consideration. The problem can be formulated as follows:
• The following (linear) costs are considered:
· set-up costs;
· inventory holding costs;
min TC = TCP + TCH + TCS (1)
· substitution costs (related to the lower degree of sat-
isfaction of the customer). subject to
The objective is to minimize the sum of these costs over T J S
the planning horizon. TCP = ∑ ∑ ∑ y jst csetup , (2)
t=1 j=1 s=1
3. THE MODEL J I 0 + ∑S x
s=1 js1 + I j1
∑
j
TCH = chj +
j=1 2
In this section a mixed-integer linear programming model is
proposed for the problem described in Section 2. T J
I j,t−1 + ∑Ss=1 x jst + I jt h
+∑ ∑ cj, (3)
t=2 j=1 2
3.1 Notation
T M J J
The following notation is adopted: TCS = ∑ ∑ ∑ ∑ xsm jkt csub
mj , (4)
t=1 m=1 j=1 k=1
k�= j
Indexes M J S
• t = 1, . . . , T : time units along the planning horizon; x0 j1 + ∑ ∑ xsm jk1 + I j1 = I 0j + ∑ x js1 , ∀j, (5)
• j = 1, . . . , J: products of the long-term product assortment; m=1 k=1 s=1
k�= j
• s = 1, . . . , S: production stations; M J S
m = 1, . . . , M: levels (or attempts) of substitution (with
•
M ≤ J);
x0 jt + ∑ ∑ xsm jkt + I jt = I j,t−1 + ∑ x jst , ∀ j, ∀t > 1 ,
m=1 k=1 s=1
i�= j
Variables (6)
M J
• x jst : quantity of product j that becomes available from
station s at the beginning of time unit t;
x0 jt + ∑ ∑ xsmk jt = d jt , ∀ j, ∀t , (7)
m=1 k=1
• x0 jt : amount of satisfied demand of product j (without i�= j
substitution) in time unit t; xs1 jkt ≤ (dkt − x0kt ) w jk , ∀ j, k, with k �= j, ∀t , (8)
• xsm jkt : amount of product j used to satisfy the m-th level J J
of substitution from product k in time unit t.
• I jt : inventory level of product j at the end of time unit t;
xs2 jkt ≤ (dkt − x0kt − ∑ xs1rkt ) ∑ wrk w jr ,
r=1 r=1
• y jst : 1, if a production order of product j is scheduled and r�= j,k r�= j,k
launched on station s in time unit t; 0, otherwise; ∀ j, k, with k �= j, ∀t , (9)

2030
INCOM 2015
Elisa Gebennini et al. / IFAC-PapersOnLine 48-3 (2015) 1954–1959 1957
May 11-13, 2015. Ottawa, Canada

t−1 must have been scheduled LT j time units in advance.

∑ z jsτ = (LT j − 1) y js(t−LTj ) , ∀ j , ∀s , ∀t > LT j , Then, the quantity of product j that becomes available
τ =t−LTj +1 depends on the batch capacity related to that station;
(10) • constraint (15) represents the rotation requirement. For
J each product, at least one production order must be sched-
y jst ≤ 1 − ∑ z jst ,
 
∀ j , ∀s , ∀t , (11) uled every T r time units. This prevents that products that
j=1 are highly substitutable and/or with a low demand are
J never, or rarely, produced (with the objective of preserving
∑ y jst ≤ 1 , ∀s , ∀t , (12) the variety of products in the long term). If J is the total
j=1 number of products in the long-term product assortment,
J it is desirable to set T r ≤ J;
∑ z jst ≤ 1 , ∀s , ∀t , (13) • constraints (16)-(21) define non-negative and binary vari-
j=1 ables.
x jst = Cs y js(t−LTj ) , ∀ j , ∀s , ∀t > LT j , (14)
The objective function is in the form of a cost minimization.
t S The costs taken into account are the total setup cost (TCP), the
∑ ∑ y jsτ ≥ 1 , ∀ j , ∀t > T r , (15) total inventory holding cost (TCH) and the total substitution
τ =t−T r s=1
cost (TCS).
x jst ≥ 0 , ∀ j , ∀s , ∀t , (16)
I jt , ∀ j , ∀t , (17) The solution of the model provides the decision maker with:
x0 jt , ∀ j , ∀t , (18) • the schedule of the production orders over the planning
xsm jkt ≥ 0 , ∀ j , ∀ j, k (with k �= j) , ∀t , (19) horizon: variable y jst states, for each time unit, the pro-
y jst ∈ [0, 1] ∀ j , ∀s , ∀t , (20) duction orders that should be launched on the available
stations;
zist ∈ [0, 1] ∀ j , ∀s , ∀t . (21) • the short-term product assortment Jtshort-term for any time
unit t in the planning horizon:
S
where:
Jtshort-term = j ∈ J : ∑ x jst + I j(t−1) > 0 ,
 

• constraint (2) defines the total setup cost; s=1

• constraint (3) defines the total inventory holding cost, that, in words, represents the subset of products that are
where expected inventory is calculated as the average of available at the beginning of time unit t.
the initial and the final inventory levels for each time unit;
• constraint (4) defines the total substitution cost, where a 4. CASE STUDY
unit cost is paid for the demand portion satisfied by the
substitutive product. Lost sales are penalized by consider- The case study that inspired the study is taken from the brewery
ing a substitution cost also for the “dummy” product; industry. In particular, we consider a micro-brewery company
• constraints (5)-(6) guarantee the conservation of material operating as a batch fermentation plant (see, e.g., the classifica-
flow for each product and time unit; tions proposed by Prokpop and Votruba, 1979).
• constraint (7) states that the demand for a product is the
Beer production process is described in detail in Baldo et al.
sum of the satisfied demand and all the substitutions from (2014). Briefly, the main production phases are as follows:
that product to the other ones (including the “dummy”
product representing lost sales); • Mashing and lautering (wort preparation): the malt is
• constraints (8)-(9) represent the substitution inequalities. crushed in a malt mill to break apart the grain kernels. The
For any level of substitution, the amount of product j resulting grist is mixed with heated water for a process
that substitutes product k is less than or equal to a certain known as “mashing” where various temperature gradients
proportion of the unsatisfied demand of product k. This activate different enzymes depending upon the type of
proportion depends on the substitution rates. Substitution malt being used. After the mashing, the resulting liquid is
inequalities are written for each of the M levels of substi- strained from the grains in a process known as “lautering”.
tution. For the sake of clarity, as in Yücel et al. (2009), At this point the liquid is known as wort. Then, the wort
only the first two substitution inequalities are provided; is boiled with hops and sometimes other ingredients such
• constraints (10)-(11) guarantee that when a production as herbs or sugars. The boiling process serves to terminate
order is launched on a station, the station is occupied by enzymatic processes, precipitate proteins, concentrate and
that product until the production is completed (i.e., for sterilize the wort.
a number of time units equal to the product lead time) • Fermentation and maturation: the wort is then moved into
and no other production orders can be launched. Note that a temperature controlled fermentation tank where yeast is
variable y jst is 1 only when the production of product j added. The yeast converts the sugars from the malt into
begins on station s (i.e., the first time unit of the lead time). alcohol, carbon dioxide and other components through a
Variable z jst is set to 1 for all the time units of the lead time process called fermentation or glycolysis. The fresh (or
except the first one (where y jst = 1). “green”) beer is obtained. After fermentation, the green
• constraints (12)-(13) guarantee that when a product is in beer needs to be maturated for a period of days or even
process on a station, that station is devoted to that product weeks.
only; • Liquid bottling and/or storing: beer that has completely
• constraint (14) states that if a product j becomes available gone through all the production steps is called ready beer.
at a certain time t, the corresponding production order Liquid bottling or storing in storage tanks is the final stage

2031
INCOM 2015
1958 Elisa Gebennini et al. / IFAC-PapersOnLine 48-3 (2015) 1954–1959
May 11-13, 2015. Ottawa, Canada

of the production process. Note that, especially in case of production lead time (that in this case refers to the time for
unpasteurized and unfiltered beers, temperature controlled fermentation and maturation) equal to two time units.
storage is required.
Some additional assumptions are as follows: (i) time for the
Different types of beer can be produced according to different “mashing and lautering” phase is not considered (it takes a few
beer styles. However, they all basically go through the same hours); (ii) after the “mashing and lautering” phase, the fermen-
production phases as discussed above. Also the main ingredi- tation tank is instantaneously filled up; (iii) once the “fermenta-
ents are always the same in beer production: water, malt (barley tion and maturation” phase is completed, the fermentation tank
corn that goes through a germination controlled process), hop is instantaneously emptied; (iv) an unlimited storage capacity
(adding flavor, aroma and bitterness) and yeast (Saccharomyces is assumed to be available (i.e., bottling, packing and storing
Cerevisiae Species). Thus, it is reasonable to guess that the are considered as perfect processes). Note that assumptions (ii)
long-term product assortment can be extensive. and (iii) reduce the complexity related to filling and emptying
times. In this way, the so-called “tank capacity” reduces to a
Nevertheless, in the company under analysis not all the beer “batch capacity”. The unitary holding (inventory) costs of each
types can be produced at the same time. This is because the
item over one time period are defined by considering the types
fermentation and maturation phase (the bottleneck of the pro- of liquids similarly as in Baldo et al. (2014). The substitution
duction process) requires (i) a number of fermentation tanks cost is assumed to be a linear function of substitution level as in
devoted to the beer type in process (ii) a number of days or even
Yücel et al. (2009). The setup cost depends on the preparation
weeks for obtaining the ready beer. Moreover, inventory costs
time for mashing (the first phase of the production process).
are high because of the temperature-controlled storage required
at the end of the production process. Thus, at a certain instant of The problem has been solved by using ILOG CPLEX™12.6,
time only a subset of beer types might be available. This subset according to the mixed-integer programming formulation de-
constitutes the short-term product assortment at that time. scribed Section 3. The application of the model to this simpli-
fied instance generates a solution that can be discussed in terms
In the sequel, the proposed mathematical model is applied to of production schedule and short-term product assortment.
a small exemplifying instance. We consider a planning horizon
of 8 time units where each time unit corresponds to 2 weeks. The production schedule is depicted in Figure 1. Some interest-
The long-term product assortment is made up of three different ing considerations can be as follows:
beer types (called BT1, BT2 and BT3). The demand of each
• Products properly rotate over the planning horizon: the
beer type per time unit over the planning horizon is reported in
parameter T r was set to three time units, meaning that one
Table 1.
production order of each beer type must be launched every
Table 1. Demand per time unit [litres]. three periods at most.
• There are cases where some production resources remain
t 1 2 3 4 5 6 7 8 idle. For example, Tank 3 remains idle in time unit t = 3
BT1 2000 7000 2000 2000 1000 1500 1000 3000 even if an order of, e.g., BT1 could be launched. This
BT2 5000 1000 2000 1000 3000 2000 4000 0
might seem anomalous because, in general, the aim is
BT3 0 3000 1000 1000 500 400 0 1000
to saturate the production capacity in order to avoid any
stock-out. On the contrary, in this case there are substitute
For each couple of beer types and the lost sales (treated as a products so that it can be more convenient (by considering
“dummy” product as explained in previous sections) the matrix all the related costs) to avoid to keep a certain product in
of substitution rates is given in Table 2. stock in a certain time unit (since it can be substituted by
another product). In other words, it can be more conve-
Table 2. Substitution rate matrix. nient not to include that product in the short-term product
BT1 BT2 BT3 Lost Sales assortment of that time unit.
BT1 - 0.70 0.25 0.05
BT2 0.70 - 0.25 0.05
BT3 0.40 0.40 - 0.20

As it can be noted BT1 and BT2 are similar types of beer (e.g.,
they are both hoppy beers such as a Belgian-style Saison beer
and an American Pale Ale beer) so that it is reasonable to guess
that a customer who prefers BT1 would accept to buy BT2 in
the case the first one is not available, and vice versa. Thus, the
substitution rate for this couple of beer types assumes a high
value (equal to 0.7). On the other hand, BT3 is a different beer
type (e.g., a German-style Weisse beer) and this explains why a
lost sale is more likely to occur (with respect to BT1 and BT2)
in case of stock-out.
In this case study the production resources of interest are the Fig. 1. Optimal production schedule.
fermentation tanks (which act as the bottleneck of the produc-
tion process). In particular, we consider four fermentation tanks Hence, it can be interesting to discuss the short-term product
whose capacities are as follows: Tank1 - 4000 litres; Tank2 - assortment and the substitution demand for a particular time
2000 litres; Tank3 - 2000 litres; Tank4 - 1000 litres. For the unit, e.g., for time unit t = 5 (when a production order started
sake of simplicity, we assume that the beer types have the same in t = 3 is completed). Table 3 reports the beer types on the

2032
INCOM 2015
Elisa Gebennini et al. / IFAC-PapersOnLine 48-3 (2015) 1954–1959 1959
May 11-13, 2015. Ottawa, Canada

rows (where “LS” means “Lost Sales”) while on the columns Further extensions of the model could be related to the possibil-
we have the demand in t = 5 (taken from Table 1 and repeated ity of splitting the portfolio of products into different families of
here for the sake of clearness) and the optimal values of the substitute products. The introduction of additional production
following variables: stages could also lead to a more general and realistic model.
Finally, the proposed model can be applied to different contexts,
• The inventory level at the beginning of time unit t = 5 especially in the craft or artisan industries where, generally,
(i.e., the inventory level at the end of the previous time
lead times are long, capacity is limited and the customers’
unit, I j4 ). In the optimal solution there is no inventory at
decisions are driven not only by functional but also emotional
the beginning of time unit t = 5. factors so that they are more willing to accept different alterna-
• The quantity that becomes available in that time unit (de-
tive products when their first choice is not available.
pending on the scheduling of production orders), where
X j 5 = ∑s x j,s,t=5 according to the notation of Section 3. In
Figure 1 we can see that the production orders launched ACKNOWLEDGEMENTS
at time t = 3 on Tank1 (for beer type BT2) and Tank2 (for
beer type BT3) complete in the time unit of interest so We would like to express our thanks to “Giustospirito”, the
that 4000 litres of BT2 and 2000 litres of BT3 becomes microbrewery involved in this work ([Link]).
available in t = 5 (being the lead time equal to two time
units). Note that there is no inventory and no available REFERENCES
production for beer type BT1. Thus, BT1 is not in the Baldo, T.A., Santos, M.O., Almada-Lobo, B., and Morabito,
short-term product assortment in t = 5. R. (2014). An optimization approach for the lot sizing and
• The quantity that substitutes for beer type BT1 in t = 5, scheduling problem in the brewery industry. Computers &
where Xs j 1 5 = ∑m xsm, j, k=1,t=5 according to the notation Industrial Engineering, 72, 58–71.
of Section 3. The demand of BT1 is 1000 litres but it is Bassok, Y., Anupindi, R., and Akella, R. (1999). Single-period
not in the short-term product assortment in t = 5. Thus, multiproduct inventory models with substitution. Operations
we have to consider the possible substitutive products: Research, 47(4), 632–642.
according to the substitution rates, 700 litres comes from Bitran, G.R. and Dasu, S. (1992). Ordering policies in an
BT2, 250 litres from BT3 and 50 litres are lost sales. environment of stochastic yields and substitutable demands.
• The quantity that substitutes for beer type BT2 in t = Operations Research, 40(5), 999–1017.
5, where Xs j 2 5 = ∑m xsm, j, k=2,t=5 . Since the product is Kök, A.G. and Fisher, M.L. (2007). Demand estimation and as-
in the short-term product assortment and the available sortment optimization under substitution: Methodology and
quantity covers its demand, no substitution occurs. application. Operations Research, 55(6), 1001–1021.
• The quantity that substitutes for beer type BT3 in t = 5, Kök, A.G. (2003). Management of product variety in retail
where Xs j 3 5 = ∑m xsm, j, k=3,t=5 . As for BT2, the product operations. Ph.D. thesis, The Wharton School, University of
is available and no substitution occurs. Pennsylvania.
• The inventory level at the end of the time unit, I j5 . There is McGillivray, A.R. and Silver, E. (1978). Some concepts for
no inventory of BT1 (but a stock-out of 50 litres occurs as inventory control under substitutable demand. Infor, 16(1),
discussed above); the inventory level of BT2 is 300 litres 47–63.
(considering also the quantity used to satisfy a portion Netessine, S. and Rudi, N. (2003). Centralized and competitive
of the demand of BT1); the inventory level of BT3 is inventory models with demand substitution. Operations
1250 litres (considering also the quantity used to satisfy Research, 51(2), 329–335.
a portion of the demand of BT1). Prokpop, A. and Votruba, J. (1979). Computer-aided schedul-
Table 3. Optimal solution for t = 5. ing of multiproduct batch fermentation plants. Biotechnology
and Bioengineering, 21(9), 1689–1694.
d j5 I j4 Xj 5 Xs j 1 5 Xs j 2 5 Xs j 3 5 I j5 Rao, U.S., Swaminathan, J.M., and Zhang, J. (2004). Multi-
BT1 1000 0 0 0 0 0 0 product inventory planning with downward substitution,
BT2 3000 0 4000 700 0 0 300
stochastic demand and setup costs. IIE Transactions, 36(1),
BT3 500 0 2000 250 0 0 1250
LS - - - 50 0 0 -
59–71.
Smith, S.A. and Agrawal, N. (2000). Management of multi-
Similar solutions are obtained for each time unit of the planning item retail inventory systems with demand substitution. Op-
horizon demonstrating the ability of the proposed model to take erations Research, 48(1), 50–64.
into consideration both inventory and product assortment issues Stavrulaki, E. (2011). Inventory decisions for substitutable
in case of demand substitution. products with stock-dependent demand. International Jour-
nal of Production Economics, 129(1), 65–78.
5. CONCLUSIONS AND FURTHER RESEARCH Tripathy, A., Süral, H., and Gerchak, Y. (1999). Multidimen-
sional assortment problem with an application. Networks,
In this study a model for the production scheduling in case of 33(3), 239–245.
capacity and operative limitations and customer-driven demand Yücel, E., Karaesmen, F., Salman, F.S., and Türkay, M. (2009).
substitution is proposed. The discussion of a case study from Optimizing product assortment under customer-driven de-
the brewery industry has demonstrated that the proposed model mand substitution. European Journal of Operational Re-
could support the production planning especially when it is not search, 199(3), 759–768.
economically or technically suitable to have all the products of
the long-term product assortment at the same time. The subset
of products that can be offered to the customers at the same
time is here called short-term product assortment.

2033