ROLLING HORIZON POLICIES FOR MULTI -STAGE STOCHASTIC ASSEMBLE -TO-ORDER PROBLEMS Daniele Giovanni Gioia Edoardo Fadda Paolo Brandimarte

2025-05-03 0 0 677.14KB 21 页 10玖币

侵权投诉

ROLLING HORIZON POLICIES FOR MULTI-STAGE STOCHASTIC

ASSEMBLE-TO-ORDER PROBLEMS

Daniele Giovanni Gioia∗

, Edoardo Fadda, Paolo Brandimarte

Department of Mathematical Sciences "Giuseppe Luigi Lagrange",

DISMA, Politecnico di Torino, Corso Duca degli Abruzzi 24,

Turin (TO), Italy.

{daniele.gioia, edoardo.fadda, paolo.brandimarte}@polito.it

ORCID: 0000-0001-8979-4174, 0000-0002-5599-6349, 0000-0002-6533-3055.

ABSTRACT

Assemble-to-order approaches deal with randomness in demand for end items by producing com-

ponents under uncertainty, but assembling them only after demand is observed. Such planning

problems can be tackled by stochastic programming, but true multistage models are computationally

challenging and only a few studies apply them to production planning. Solutions based on two-stage

models are often short-sighted and unable to effectively deal with non-stationary demand. A further

complication may be the scarcity of available data, especially in the case of correlated and seasonal

demand. In this paper, we compare different scenario tree structures. In particular, we enrich a

two-stage formulation by introducing a piecewise linear approximation of the value of the terminal

inventory, to mitigate the two-stage myopic behavior. We compare the out-of-sample performance

of the resulting models by rolling horizon simulations, within a data-driven setting, characterized

by seasonality, bimodality, and correlations in the distribution of end item demand. Computational

experiments suggest the potential beneﬁt of adding a terminal value function and illustrate interesting

patterns arising from demand correlations and the level of available capacity. The proposed approach

can provide support to typical MRP/ERP systems, when a two-level approach is pursued, based on

master production and ﬁnal assembly scheduling.

Keywords stochastic programming

end-of-horizon effect

scenario tree generation

assemble-to-order production

data-driven optimization

History This is an Author’s Original Manuscript of an article published by Taylor & Francis in the International

Journal of Production Research on 21.11.2023, available online:

https://doi.org/10.1080/00207543.2023.

2283570

Any citation must refer to its published version.

1 Introduction

In the manufacturing domain, demand uncertainty is one of the main contributors to the difﬁculty of production planning

problems, alongside production yield, quality, and machine reliability. A wide array of buffering tools has been devised

to ease the difﬁculty of demand forecasting, including safety stocks (Gonçalves, Sameiro Carvalho, and Cortez 2020)

and delaying assembly, in order to postpone product differentiation and take advantage of risk pooling effects (a

well-known success story for this approach is the HP DeskJet case, see Lee and Billington (1993), Aviv and Federgruen

(2001)). The latter idea is exploited in Assemble-To-Order (ATO) manufacturing environments, where the long lead

time to manufacture or procure components makes a pure Make-To-Order approach not feasible, so that components

must be ordered under demand uncertainty. Yet, if ﬁnal assembly is relatively fast, we do not need to stock end items,

and ﬁnal assembly can be carried out after demand for end items is observed.

∗Corresponding author

arXiv:2210.00491v3 [math.OC] 22 Nov 2023

D.G. Gioia et al. ArXiv Preprint - Rolling horizon policies for multi-stage ATO November 23, 2023

In the context of typical Manufacturing Resource Planning (MRP) systems, as well as their descendants Enterprise

Resource Planning (ERP) systems, this is reﬂected by a two-level approach. A Master Production Schedule (MPS) is not

deﬁned for end items in the bills of materials, but rather for basic modules that are made to stock, according to forecasts

of dependent demand, and then used according to a Final Assembly Schedule (FAS), driven by actual independent

demand (Proud and Deutsch 2021). However, traditional MRP/ERP systems may struggle with the complexity of ﬁnite

capacity planning, which compounds with demand uncertainty. The typical approach is to introduce safety stocks,

and to plan according to a rolling horizon strategy. The aim of this paper is to provide practical support to this kind

of endeavor by prescriptive analytics, based on optimization models. We do so within a simpliﬁed setting, where

bills of materials are ﬂat and comprise two levels, basic modules/components, and end items, corresponding to the

aforementioned MPS and FAS levels.

If a single assembly period is considered, the optimization problem can be formalized as a two-stage stochastic linear

programming model, where at the ﬁrst stage components (modules) are produced (under capacity constraints and subject

to uncertainty on the demand of end items), while in the second one demand is observed and end items are assembled.

Two-stage ATO models can be tackled with a limited computational effort (Brandimarte, Fadda, and Gennaro 2021)

and may provide optimal solutions also in the multistage setting, if demand is independent and identically distributed

(i.i.d.) across different time periods (Gerchak and Henig 1986). Nevertheless, a longer planning horizon is necessary

when the i.i.d. assumption does not apply, possibly due to predictable variability in demand, like a seasonal demand

spike that cannot be met by the available production capacity and requires careful planning of inventory buffers. In

this setting, the power and ﬂexibility of multistage Stochastic Programming (SP) models may play a signiﬁcant role,

but their application is hindered by two issues: the lack of reliable information about probability distributions of the

underlying risk factors and the exponential growth of the scenario tree. While the ﬁrst issue can be tackled by adopting

a data-driven approach, the second one could actually prevent the adoption of such techniques. Indeed, the literature

shows that a considerable research effort has been devoted to proper scenario tree generation, in terms of scenario

sampling and choice of its structure, i.e., breadth (branching factors) and depth (number of periods). In particular,

limiting the number of periods may greatly reduce the size of the tree, at the price of a potential adverse effect in terms

of myopia.

The nasty effects of truncated decision horizons are well-known even in a multiperiod deterministic setting. In Grinold

(1983), issues related with the truncation of inﬁnite-horizon problems are thoroughly analyzed. The addition of a

terminal value is proposed by Fisher, Ramdas, and Zheng (2001) to overcome end-of-horizon effects. A terminal state

value is also a key ingredient in stochastic dynamic programming (Brandimarte 2021), and the integration of SP with

stochastic control is proposed by Konicz et al. (2015) for a ﬁnancial application (see also Myers, Ziemba, and Cariño

(1998)). Nevertheless, while in the ﬁnancial domain there is a remarkable body of knowledge concerning the value of

terminal states for asset–liability management problems, much less is available in the manufacturing domain.

The contribution of this work is twofold. First, we propose a computational methodology for approximating the value

of residual components in inventory, adding an end-of-horizon term to the objective function, to counteract the myopia

of models with short horizons. Second, we study the performance of different model formulations in an ATO context

characterized by challenging demand features, such as bimodality, seasonality, and correlations, also considering the

impact of available capacity for component production. We assume that only a limited amount of historical data is

available. More in detail, we compare the following families of models:

• A plain two-stage stochastic linear programming model.

• A two-stage stochastic model enhanced with an estimate of the value of residual component inventory.

•

A set of multi-stage stochastic models characterized by different types of scenario trees, varying in breadth

and depth.

• A set of deterministic models, buffering against demand uncertainty by different levels of safety stocks.

We test these models in a realistic environment, by simulating the production system within a rolling horizon framework.

Only the decisions in the ﬁrst time period are implemented, and the models are repeatedly solved after observing the

new demand. Simulations are run out-of-sample, whereas the in-sample scenarios used in the models rely only on a

ﬁxed limited amount of demand observations. Computational experiments show that including an estimate of the value

of the residual inventory can greatly improve the performance of the two-stage model, making it the best among those

we tested. Moreover, we show that considering a longer planning horizon can be detrimental in terms of performance,

and not only from a computational time point of view.

Since the problem is characterized by several parameters, we present in this paper only the most interesting results that

we have obtained. Nevertheless, the open-source code is available at

https://github.com/DanieleGioia/ATO

, to

properly guarantee reproducibility and enable interested readers to carry out further experiments.

D.G. Gioia et al. ArXiv Preprint - Rolling horizon policies for multi-stage ATO November 23, 2023

The paper is organized as follows. In Section 2 we review the literature about ATO problems and rolling horizon

policies, and position the paper within the context of approximate dynamic programming. In Section 3 we describe the

mathematical models used in the computational experiments. Then, in Section 4 we introduce the general experimental

setting, and in Section 5 we present the results of several computational experiments. Finally, Section 6 discusses

conclusions and future research directions.

2 Literature review and paper positioning

Some early references on ATO problems date back to the 80s (Wemmerlöv 1984; Collier 1982). However, a relevant

part of this literature is actually oriented towards continuous- or periodic-review inventory control models within a

supply chain management framework, where the aim is to replenish inventory and allocate components, rather than

ﬁnite-capacity production planning. With the aim of building analytical models, a commonly adopted tool is stochastic

modeling, often dealing with a single end item or just a very few. Examples of such approaches are Fang, So, and Wang

(2008), where a game-theoretic framework is used to investigate pricing and procurement strategies, and Fu, Hsu, and

Lee (2006), where outsourcing is also considered and an analytical framework is applied to characterize properties of

the optimal solution for a problem involving a single end item. Stochastic control is applied in (Plambeck and Ward

2006), to cope with customer order sequencing. We refer to (Atan et al. 2017; Song and Zipkin 2003) for a review of

this stream of literature.

On the contrary, we tackle discrete-time, multi-item, ﬁnite-capacity ATO production planning problems. The Bills

of Materials (BoM) are ﬂat and include only two levels, end items and components (modules), which correspond to

the two-level MPS/FAS approach, common in MRP systems. We assume components are manufactured under ﬁnite

capacity constraints and ﬁnal assembly is not a bottleneck, so we do not consider assembly capacity and cost. Demand

is uncertain and backordering is not possible. Hence, unsatisﬁed demand is lost, with an adverse impact on the overall

objective, which we assume is to maximize expected proﬁt.

In more recent years, the literature on deterministic mathematical programming models for ﬁnite-capacity production

planning includes papers dealing with demand uncertainty, where both stochastic programming and robust optimization

are applied. A recent review is Bindewald, Dunke, and Nickel (2023). While some works consider single-level

production planning, others deal with multi-level problems, where product structures are represented by bills of

materials. However, ATO problems feature a different information structure, as we may make assembly decisions after

observing demand.

Since in this paper we focus on stochastic programming models with recourse, we ﬁrst discuss the related literature.

Then, we provide some references on deterministic approaches based on safety stocks, which is more akin to standard

practice in MRP systems and is used as a benchmark in our computational experiments. Finally, we present our work

within the more general framework of sequential decisions under uncertainty and approximate dynamic programming.

2.1 Approaches based on stochastic programming

Most of the literature concerning the application of stochastic programming models to ﬁnite-capacity production

planning under demand uncertainty deals with extensions of classical lot-sizing models, possibly involving multiple

levels. Aloulou, Dolgui, and Kovalyov (2014) provide a review of non-deterministic lot sizing models.

One of the ﬁrst papers applying stochastic programming on ATO system is Jönsson, Jörnsten, and Silver (1993), where

the problem is formulated as a stochastic integer programming model. Fairly small problem instances are solved by

progressive hedging and scenario aggregation. After almost 30 years of improvements in commercial solvers, even

some realistic size instances can likely be solved to near optimality by off-the-shelves software, at least in a two-stage

case. Two-stage models are tackled by Brandimarte, Fadda, and Gennaro (2021) and then extended by Fadda, Gioia,

and Brandimarte (2023) to introduce risk aversion. Per se, two-stage models are limited to newsvendor-like models.

However, they may be applied within approximation and decomposition schemes. In fact, truly multistage models are

quite difﬁcult to deal with, due to the explosion of the scenario tree. For instance, Englberger, Herrmann, and Manitz

(2016) deal with a multi-period problem, but they apply a two-stage approach by freezing some decisions made at

the ﬁrst stage. In the literature, this approach leads to static-dynamic approaches, which have also been applied to

production planning involving the assembly of components. For instance, Thevenin, Adulyasak, and Cordeau (2022)

apply a static-dynamic approach, with an emphasis on solution methods based on stochastic dual dynamic programming.

Thevenin, Adulyasak, and Cordeau (2021) adopt a similar modeling framework, but focus on the application of practical

heuristics and testing by simulation. Speciﬁc solution approaches for ATO systems are adopted by DeValve, Pekeˇ

c, and

Wei (2020), who apply newsvendor-based decomposition and rounding approaches; they apply sophisticated solution

and analysis tools, whereas the demand structure is rather simple. Borodin et al. (2016) apply chance-constrained

D.G. Gioia et al. ArXiv Preprint - Rolling horizon policies for multi-stage ATO November 23, 2023

stochastic programming, as they place emphasis on the replenishment of components from suppliers, under random

lead times. van Jaarsveld and Scheller-Wolf (2015), too, deal with component replenishment and allocation, rather than

ﬁnite-capacity production. See also Huang and de Kok (2015). Nonås (2009) adopts stochastic programming, providing

analytical insights for small-scale component replenishment problems, limited to just a few (three) end items.

Unlike, e.g., DeValve, Pekeˇ

c, and Wei (2020) and Thevenin, Adulyasak, and Cordeau (2022), we deliberately steer

away from ad-hoc solution approaches, as they may be fragile when dealing with general models. Since we aim at

providing support to two-level master production scheduling, we prefer to use standard solvers. Furthermore, we insist

on complex demand patterns. We allow for seasonality and deal with realistic issues related to ATO system, where some

end items may be variations on a basic family. Hence, we shall cope with intra-family demand, which needs a better

approach than just pairwise correlations. Differently from DeValve, Pekeˇ

c, and Wei (2020) and Borodin et al. (2016),

we do not consider component replenishment from suppliers, but ﬁnite capacity production. This results in challenging

issues, especially when there are demand peaks, possibly due to seasonality, that must be suitably addressed.

Our problem setting is more related with, e.g., Englberger, Herrmann, and Manitz (2016) and Thevenin, Adulyasak, and

Cordeau (2021). However, we consider a different information structure, related to two-level, rather than single-level

master production scheduling. On the other hand, we disregard lot sizing issues associated with setup costs and times.

We do not use sophisticated scenario generation strategies as in Thevenin, Adulyasak, and Cordeau (2022), like

quasi-Monte Carlo sampling, as we rely on a data-driven approach whereby probability distributions are unknown

and only a few data are available. Furthermore, we do not evaluate performance in terms of in-sample computational

efﬁciency, but rather in terms of actual expected proﬁt estimated by realistic out-of-sample, rolling horizon simulations

(where the true demand distributions are used).

2.2 Approaches based on deterministic models and safety stock buffers

The practical strategy adopted in typical MRP systems relies on deterministic planning, integrated with the use of

safety stocks as a hedging tool, within a rolling horizon process. This is reﬂected in academic research based on the

application of simulation models and optimization heuristics to set safety stocks.

The problem of sizing safety stocks has been considered in several papers and a recent literature review is provided by

Gonçalves, Sameiro Carvalho, and Cortez (2020), who analyze a set of 95 articles published from 1977 to 2019 and

show that 65% of them apply analytical techniques, often within an inventory control framework, and do not contain

references to realistic applications. On the contrary, simulation seems to play a key role in practice, often with reference

to MRP systems. Simulation-based optimization is adopted by Gansterer, Almeder, and Hartl (2014) and Seiringer

et al. (2021), as well as by Zhao, Lai, and Lee (2001) to evaluate the performance of MRP systems. A deterministic

optimization model is proposed by Ziarnetzky, Mönch, and Uzsoy (2020), using safety stocks to buffer against demand

uncertainty. They use simulation to assess actual performance within a rolling horizon framework, which is what we

also do in our computational experiments.

2.3 Paper positioning and relationships with approximate dynamic programming

The distinguishing feature of our work is the integration of stochastic programming models for ATO with tools to ease

end-of-horizon effects (Grinold 1983; Fisher, Ramdas, and Zheng 2001). We should note that this kind of issue has been

addressed in the ﬁnancial domain Myers, Ziemba, and Cariño (1998); Konicz et al. (2015) too. However, in ﬁnance we

essentially have to deal with one commodity, namely, wealth. In an ATO environment, the matter is more complicated,

due to the relationships among components used for the same end item. Finding an exact expression of the terminal

value function is impractical. Nevertheless, experience with rollout algorithms (Bertsekas 2020) shows that even a

rough approximation may be remarkably effective in improving performance. A useful strategy for this aim is to resort

to separable approximations as proposed, e.g., by Simão et al. (2009), which is what we pursue in this paper.

The comparison of solutions based on different scenario tree structures has been tackled for ﬁnancial portfolio choice

problems by, e.g., Birge, Blomvall, and Ekblom (2022); Blomvall and Shapiro (2006). However, ﬁnancial and

manufacturing domains are deeply different. While in the ﬁnancial domain care must be taken to avoid building a

tree allowing arbitrage opportunities, which places additional requirements on the shape of the scenario tree, in the

production ﬁeld there are no such problems. Moreover, in ﬁnance, there is an abundance of data, which is a much scarcer

commodity in manufacturing, requiring a data-driven approach. These differences motivate a speciﬁc investigation

within a manufacturing setting.

In principle, the problem that we address in the paper could be solved exactly by stochastic dynamic programming,

which is the reference approach to cope with sequential decisions under uncertainty. It is well-known, however, that

the curse of dimensionality precludes its application to most practical size problems. Nevertheless, concepts from

D.G. Gioia et al. ArXiv Preprint - Rolling horizon policies for multi-stage ATO November 23, 2023

dynamic programming may be fruitfully applied to devise high-quality approximate solution strategies. Powell (2022)

classiﬁes different key approaches relying, e.g., on value function or policy function approximations, cost function

approximations, and lookahead strategies, which may be useful to put alternative approaches to ATO production

planning into a common perspective. Standard approximate dynamic programming approaches relying purely on value

or policy function approximations do not look promising. On the one hand, the interactions among different components

through the bills of materials result in a complicated value function. On the other one, a policy function mapping the

system state into component production decisions should cope with capacity constraints coupling different components.

Furthermore, pure multistage stochastic programming models, which introduce a lookahead by a scenario tree are

limited by the exponential growth of the tree. Hence, the essential contribution of our paper is to integrate a lookahead

approach, based on scenario trees, with a value function approximation. As discussed by Bertsekas (2022), this is the

key idea in many successful approaches to dynamic decisions. A ﬁnal strategy categorized by Powell (2022) is the

approximation of a stochastic problem by a deterministic one, introducing buffers to hedge against uncertainty. In order

to devise a competing approach, we do so by using safety stocks.

3 Model formulations

In this section, we introduce our model formulations of the ATO problem. Let

I={1, . . . , I}

be the set of components,

J={1, . . . , J}

the set of end items, and

M={1, . . . , M}

the set of production resources (e.g., machines). Moreover,

let us deﬁne the following parameters:

•Cicost of component i∈ I.

•Pjselling price of end item j∈ J.

•Kjlost sale penalty of end item j∈ J.

•Hiinventory holding cost of component i∈ I.

•Lmproduction availability (time) of machine m∈ M.

•Tim time required to produce one component i∈ I on machine m∈ M.

•Gij

amount of component

i∈ I

required for assembling end item

j∈ J

, commonly known as gozinto factor

when describing a BoM.

•¯

iinitial inventory of component i.

In order to formulate a stochastic model, we have to represent demand uncertainty. The standard choice in the SP

literature is a scenario tree. Following the notation in Brandimarte (2006), we deﬁne:

•N

, the set of nodes of the scenario tree and

N+=N \ {0}

. Node

is the root node, where here-and-now

decisions are made.

•p(n), the parent of node n∈ N+.

•π[n], the unconditional probability of node n(π[0] = 1).

•d[n]

j, the demand for end item jat node n∈ N.

We deﬁne as branching factor the number of children (immediate successor nodes) of each node at a given level of the

tree. For example, by repeating three times a branching factor 2, the vector

[2,2,2]

identiﬁes a binary tree over four

time periods, including the current time corresponding to the root node, which results in eight scenarios. A scenario is

a sequence of nodes from the root node to a leaf node, i.e., a realization of the underlying stochastic process. All of

the nodes at the same level are associated with the same time instant. For each node

n∈ N

, we deﬁne the following

decision variables (restricted to non-negative integers):

•x[n]

i∈Z+, the amount of components i∈ I produced at node n∈ N.

•I[n]

i∈Z+, the available inventory of components i∈ I at node n∈ N.

•y[n]

j∈Z+, the amount of end items j∈ J assembled at node n∈ N.

•l[n]

j∈Z+, the lost sales of end item j∈ J at node n∈ N.

It is important to clarify the event sequence taking place at each discrete time instant. At each node, we ﬁrst observe the

new demand for end items. Then, we satisfy the demand using the components available in the inventory, and we pay

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

ROLLINGHORIZONPOLICIESFORMULTI-STAGESTOCHASTICASSEMBLE-TO-ORDERPROBLEMSDanieleGiovanniGioia∗,EdoardoFadda,PaoloBrandimarteDepartmentofMathematicalSciences"GiuseppeLuigiLagrange",DISMA,PolitecnicodiTorino,CorsoDucadegliAbruzzi24,Turin(TO),Italy.{daniele.gioia,edoardo.fadda,paolo.brandimarte}@polito.i...

展开>> 收起<<

ROLLING HORIZON POLICIES FOR MULTI -STAGE STOCHASTIC ASSEMBLE -TO-ORDER PROBLEMS Daniele Giovanni Gioia Edoardo Fadda Paolo Brandimarte.pdf

共21页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

ROLLING HORIZON POLICIES FOR MULTI -STAGE STOCHASTIC ASSEMBLE -TO-ORDER PROBLEMS Daniele Giovanni Gioia Edoardo Fadda Paolo Brandimarte

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: