Operational production planning and sheduling in the pulp and paper industry
Full text
Luis Gon¸calo Rod igues Reis Figuei a
PORTO
FEUP FACULDADE DE ENGENHARIA
UNIVERSIDADE DO PORTO
DEPARTAMENTO DE ENGENHARIA E GESTÃO INDUSTRIAL
U.
Ope a ional P oduc ion Planning and
Scheduling in he Pulp and Pape Indus y
Submi ed o Faculdade de Engenha ia da Uni e sidade do Po o in pa ial ul illmen o
he equi emen s o he deg ee o Doc o o Philosophy in Indus ial Enginee ing and
Managemen , supe ised by Be na do Almada-Lobo, Associa e P o esso o Faculdade de
Engenha ia da Uni e sidade do Po o
Depa men o Indus ial Enginee ing and Managemen
Faculdade de Engenha ia da Uni e sidade do Po o
2014
This esea ch was pa ially suppo ed by he PhD g an SFRH/BD/80109/2011 awa ded
by he Po uguese Founda ion o Science and Technology and by he p i a e company
Eu opa&c K a Viana, S.A. unde he p ojec Decision suppo sys em o he in eg a ed
planning o pulp, pape and ene gy, suppo ed by he Na ional S a egic Re e ence
F amewo k (NSRF).
“Things should be made as simple as possible, bu no any simple .”
Albe Eins ein
Acknowledgmen s
Fi s and o emos , I would like o hank my ad iso Be na do Almada-Lobo. He is he
eason I ha e decided o en ol in a PhD p ojec igh a e inishing my mas e ’s deg ee. The
oppo uni y o wo k and lea n om Be na do has been ex emely aluable o me. He can
be highly suppo i e and mo i a ing, bu a he same ime p o ides us and he equi ed
eedom o g ow and imp o e in di e en dimensions. I am hank ul o his guidance,
op imism, pa ience and abo e all o his iendship.
I would like o exp ess a wo d o app ecia ion and g a i ude o Ma is ela San os, Reinaldo
Mo abi o and Ch is ian Almede o ha ing welcomed me in hei uni e si ies and p o id-
ing hei aluable insigh s.
I am hank ul o Eu opa&c K a Viana, S.A. o belie ing in he p ojec , suppo ing
i and in es ed ime in mul iple mee ings a he plan . In pa icula , I would like o ac-
knowledge Má io Ama al, o he oppo uni y o collabo a e on an indus ial p oblem ha
is so in e es ing, and Ped o Campos, Ma co Mou a, Balbina Fe nandes, Raquel Simões
and Rica do Mendes, o hei inpu s and alida ions.
I owe also hanks o my colleagues and iends o FEUP/INESC, B azil and Ge many,
o he pleasan a mosphe e ha has e e su ounded me. Thei chee was essen ial o
my mo ale. Specially, I wan o hank Ma cos, Ped o, Má io and Luís, who ha e di ec ly
con ibu ed o my wo k. Fo Luís a e y indeb ed wo d o g a i ude o helping me li e ally
om he beginning o he end o his p ojec .
Finally I would like o acknowledge he commi men o my amily o my well-being
and he alues hey ha e ins illed on me. Thank you João and F ancisco o helping me
being who I am. Thank you Mãe and Pai, o you uncondi ional suppo .
ii
Abs ac
P oduc ion planning is especially impo an o capi al in ensi e indus ies, whe e he high
in es men s in capaci y ha e o be dilu ed in he p oduc ion o ypically low p o i ma -
gin p oduc s. The e o e he u iliza ion o he ins alled p oduc i e capaci y needs o be
maximized, while he equipmen is ope a ed e icien ly and he ma ke equi emen s a e
sa is ied.
The ope a ional p oduc ion planning is essen ial o adap medium- e m plans acco d-
ing o he ac ual s a e o he sys em a each ime. This ac i i y conside ably depends on
he speci ic indus y and is pa icula ly impo an in highly s ochas ic p oduc ion en i on-
men s. This hesis hus ocus on he sho - e m planning in a pa icula indus y, he pulp
and pape (P&P), in o de o g asp and inco po a e he speci ici ies o he p oduc ion p o-
cess and hence de elop use ul quan i a i e models and me hods. These models need o be
accu a e enough o p o ide de ailed and ealis ic plans.
The P&P indus y is no only capi al, bu also ene gy in ensi e and he p ice o pa-
pe p oduc s is de e mined by he ma ke , which may squeeze p o i ma gins. In addi ion,
he plan s a e subjec o p ocess a iabili y and dis u bances. The e o e, he ope a ional
planning is a c i ical ac i i y. The planning ask poses a a ie y o challenges, since he
complex p oduc ion low is cha ac e ized by shi ing bo lenecks, sequence-dependen se-
ups and he a iabili y inhe en o he p ocess.
The s udy conduc ed in he hesis is d i en by a eal-wo ld case o a P&P p oduce ,
which no only p o ides aluable inpu s ega ding he challenges o be add essed, bu also
allows assessing he p ac ical impac o he scien i ic con ibu ions. The hesis explo es
bo h eac i e and p oac i e planning app oaches o he s ochas ic p oduc ion sys em. On
he eac i e side, ealis ic models and e icien me hods a e p oposed and a decision sup-
po sys em is implemen ed in he company. On he p oac i e pe spec i e, he powe ul
simula ion-op imiza ion combina ion is s udied in dep h and a amewo k is de ised o
ackling p oduc ion planning and scheduling p oblems.
Al hough he p ima y ocus o he hesis is he P&P indus y, o he con inuous p ocess
indus ies may also bene i om he con ibu ions he e p o ided.
ix
Resumo
O planeamen o da p odução é especialmen e impo an e em indús ias de capi al in ensi o,
onde os al os in es imen os em capacidade p odu i a êm de se diluídos na p odução de
p odu os ca ac e izados po ma gens de luc o eduzidas. A u ilização da capacidade p odu-
i a ins alada de e assim se maximizada, enquan o o equipamen o de e á se manuseado
de o ma e icien e e os equisi os do me cado sa is ei os.
O planeamen o ope acional da p odução é essencial pa a adap a os planos de médio-
p azo à ealidade do sis ema p odu i o em cada momen o. Es a ac i idade depende consi-
de a elmen e da indús ia especí ica abo dada e é pa icula men e impo an e em ambien es
p odu i os al amen e es ocás icos. Es a ese p ocu a po isso oca -se no planeamen o de
cu o-p azo numa indús ia pa icula , a he pas a e papel (P&P), de o ma a comp eende
e inco po a as especi icidades do p ocesso p odu i o e, assim, desen ol e modelos e mé-
odos quan i a i os de ele ância e u ilidade p á ica. É necessá io que es es modelos sejam
su icien emen e iéis à ealidade pa a que disponibilizem planos de alhados e ealis as.
A indús ia de P&P é não só de capi al in ensi o, mas ambém de uso in ensi o de
ene gia, enquan o o p eço do papel é de e minado no me cado (le ando po ezes ao es-
magamen o das ma gens de luc o). Pa a além disso, as áb icas ap esen am a iabilidade
no p ocesso e dis ú bios. O planeamen o ope acional é en ão uma ac i idade c í ica. Es-
as a e as colocam uma sé ie de desa ios, is o o luxo de p odução se ca ac e izado po
ga galos dinâmicos, p epa ações do equipamen o dependen es da sequência de p odu os e
a a iabilidade ine en e ao p ocesso.
O es udo ealizado nes a ese é mo i ado po um caso eal de um p odu o de P&P, que
não só en iquece o abalho com in o mação ela i a aos desa ios a abo da , mas ambém
pe mi e a alia o impac o p á ico das con ibuições cien í icas. A ese explo a abo dagens
eac i as e p oac i as ao planeamen o da p odução des e sis ema es ocás ico. Na pe spec-
i a eac i a, modelos ealis as e mé odos de solução e icien e são p opos os e um sis ema
de apoio à decisão é implemen ado na emp esa. Rela i amen e à abo dagem p oac i a, a
pode osa combinação simulação-op imização é es udada em p o undidade e um mé odo
pa a abo da o planeamen o e escalonamen o da p odução é p opos o.
Embo a o oco p incipal seja a indús ia de P&P, ou as indús ias de p ocesso con ínuo
pode ão bene icia das con ibuições aqui p opos as.
2 Chap e 1. Mo i a ion and amewo k
con ibu ing no only o he P&P indus y, bu also o o he simila (con inuous) p ocess
indus ies, such as chemicals, indus ial me als (e.g. i on, s eel), oil e ining and sewage
ea men .
The emainde o his chap e is o ganized as ollows. Sec ion 1.1 p o ides some con-
ex o he P&P indus y and he case s udy, speci ically in wha conce ns he main chal-
lenges o he p oduc ion planning and he cu en p ac ice. Then, Sec ion 1.2 p esen s he
esea ch ques ions and objec i es ela ed o hose challenges and he me hodology ollowed
in he PhD p ojec . Finally, he las sec ion gi es an o e iew o he hesis, by desc ibing
he chap e s composing his documen .
1.1. Pape indus y and case s udy
The pulp and pape (P&P) indus y is no only capi al in ensi e, bu also ene gy in ensi e.
In addi ion, he p ice o pape p oduc s is de e mined by he ma ke , which may squeeze
p o i ma gins. The e o e, companies need o maximize he u iliza ion o hei equipmen ,
keeping p oduc ion cos s as low as possible, while ying o p o ide a good cus ome se -
ice. E ec i e p oduc ion planning is hus impe a i e. Howe e , he planning p ocess
poses a a ie y o challenges, bo h o p ac ical and scien i ic ields. This sec ion s a s
wi h a b ie desc ip ion o he p oduc ion p ocess and case s udy speci ici ies. Then, he
ope a ional planning is depic ed.
1.1.1 P oduc ion p ocess and speci ici ies
The P&P indus y con e s ib ous aw ma e ials in o pulp, pape and pape -boa d. In a i s
s ep aw ma e ials a e p ocessed in o pulp (in he diges e ) and in a second s ep di e en
pape g ades a e p oduced ou o his pulp (in he pape machine). These wo s eps can be
pe o med on sepa a e plan s o combined in o an in eg a ed mill. Figu e 1.1 illus a es he
p oduc ion p ocess o an in eg a ed P&P mill. I should be no ed ha a each s age he e
can be one o se e al esou ces in pa allel and he equipmen may wo k in con inuous o
ba ch p oduc ion.
wa e
pape machine winde
jumbos bu e
ecycled pulp ank
i gin pulp ank
ecycled pulp mill
diges e
wood chips plan
bleach plan
weak black
liquo ank
concen a ed
black liquo ank
e apo a o eco e y boile
eco e y plan
pape mill pulp mill
Figu e 1.1: The in eg a ed pulp, pape and eco e y plan .
1.1. Pape indus y and case s udy 3
The ques o imp o emen s in p ocess e iciency, esou ce consump ion, was es p o-
duc ion and ene gy balance has led companies o an in eg a ion o hei p ocesses and
in oduc ion o closed loops. Acco dingly, in eg a ed P&P mills ep esen 65% o he in-
dus y (CEPI,2013) and a e mo e capable o achie ing high le els o bo h ene gy and
economic e iciency, due o:
•ene gy conse a ion p ojec s (e.g. di ec use o s eam in he pape d ying p ocess);
•absence o addi ional p ocesses (e.g. pulp d ying);
•ma e ial closed loops (e.g. ecycling o pape machine se up loss and im loss)
which allow educing was e p oduc ion and he ene gy spen on i ;
• igh ly in eg a ed equipmen , which educes he equi ed capaci y.
Ne e heless, an in eg a ed P&P mill like ha o ou case s udy poses se e al chal-
lenges:
•impo an sequence-dependen se ups, which b eak p oduc ion s abili y and cause
wea o equipmen ;
• a iable p oduc ion a es, cons ained o maximum and minimum alues, and wi h
a ia ion cos s o limi a ions;
• igh ly in eg a ed p oduc ion and s o age capaci y and dis inc p oduc ecipes, which
esul in mul iple and shi ing bo lenecks;
•complex p oduc ion sys em wi h se ial, di e gen , con e gen and loop lows;
•p ocess a iabili y and dis u bances, p opaga ing h ough mul iple s ages.
The company o he case s udy p oduces wo main a ian s o k a line (KLB and
VLB), which is a ype o pape o he co uga ed ca dboa d boxes ma ke . Bo h p oduc s
( ha essen ially di e in hei quan i ies o i gin and ecycled ib es) may be p oduced in
a se o di e en g ammage alues. Fo he sake o simplici y, he ea e he e m “g ade”
is used o he combina ion o he hickness o he pape ( ela ed o i s g ammage) and he
p opo ion o i gin and ecycled ib es in he mix u e. The company p o ides o i s clien s
a o al o 29 di e en g ades.
All he p oduc ion s ages depic ed in Figu e 1.1 a e pe o med on si e, wi h he excep-
ion o bleaching, which is no necessa y o his ype o pape . In each s age he e is only
one p oduc ion esou ce and hey wo k in con inuous. In addi ion o he a o emen ioned
challenges, his pape company has o deal wi h mul iple dis ibu ion channels, which in-
clude he schedule o con aine s o ship deli e ies. All he p oduc ion is made o o de
(MTO), which pu s p essu e on p oduc ion o deli e he equi ed amoun s in he sho es
possible lead- ime.
4 Chap e 1. Mo i a ion and amewo k
1.1.2 Planning and scheduling
In o de o minimize se ups and maximize capaci y u iliza ion, o de s a e accep ed based
on a s anda d sequence o p oduc ion which is epea ed in cycles. In his way o de s can be
accep ed well in ad ance. Looking a he a ailable slo s in he p oduc ion sequence, man-
age s commi o a due da e (a ailable- o-p omise). A he ope a ional le el, he p oduc ion
sequence is adap ed acco ding o he e ol ing s a e o he sys em.
The ope a ional p oduc ion planning is ypically a manual p ocess which ollows a
hie a chical scheme:
• he op-le el ocuses on he pape machine, dealing wi h he sizing and scheduling
o pape campaigns o ul il cu en demand and backlog;
• he base-le el ies o schedule and con ol all he o he p oduc ion esou ces, subjec
o he inpu om he op-le el.
Each le el elies only on sp eadshee s and he inpu s o eedback om he o he le el.
No only his p ocess equi es mul iple i e a ions o p oduce a easible plan, bu i is also
sub-op imal. Mo eo e , i does no allow o a ca e ul ade-o be ween he di e en ob-
jec i es, gi en he e y limi ed ime a ailable a his ope a ional le el.
In addi ion, he sys em is subjec o p ocess a iabili y (e.g. in p oduc ion yield) and
dis u bances (e.g. equipmen ailu es). Dis u bances in one p ocess end o p opaga e o
o he p ocesses, esul ing in p oduc ion losses, unnecessa y a e changes (which u he
cause quali y dis u bances and undesi ed wea on equipmen ) and inc ease o he en i on-
men al load o he mill. The e o e, planne s need also o conside slacks in hei plans,
in o de o accommoda e his unce ain y (p oac i e planning). Also, in he p esence o
dis u bances a quick plan mus be gene a ed ( eac i e planning).
1.2. Resea ch objec i es
This esea ch in ends o gi e new insigh s in o he esolu ion o he ope a ional p oduc-
ion planning p oblem in he P&P indus y. As men ioned be o e, a case s udy is used o
mo i a e and iden i y he main challenges o his p oblem and also o assess he pe o -
mance o he models and me hods p oposed. San os and Almada-Lobo (2012) had al eady
app oached his case s udy, by p oposing an in eg a ion o he pulp, pape and chemical
eco e y p ocesses, in o de o conside he mul iple bo lenecks o he sys em. The model
howe e was oo complex o exac sol e s and e en he app oxima e me hod p oposed
only achie ed solu ions o mode a e quali y. On he o he hand, al hough used o gene a e
and alida e some plans, he model was no used by p ac i ione s and he e o e i did no
add ess all he ele an indus ial issues. Fu he mo e, i did no conside any unce ain y
in he p ocess. Tha wo k is hus he s a ing poin o his hesis, which aims a con ibu ing
o bo h he li e a u e and p ac ice, in wo main b anches: eac i e and p oac i e planning.
1.2. Resea ch objec i es 5
B anch 1 – Reac i e planning
Reac i e planning ocuses on gene a ing good quali y plans in a sho pe iod o ime. These
me hods can be used o ace g ea dis up ions, as well as si ua ions which de ia e only
sligh ly om he o iginal plan. As in bo h cases, especially in he o me , he a ailable
ime o de ise a plan is e y sho , he models and me hods assume all pa ame e s o be
de e minis ic. In his con ex wo objec i es we e de ined:
1. De elop an e icien solu ion me hod o sho - e m planning and scheduling p ob-
lems
As he me hod p oposed by San os and Almada-Lobo (2012) could no gene a e good
quali y solu ions in easible ime, he i s objec i e is o de elop an e icien solu ion
me hod ha can be used o ackle ha p oblem. The me hod should be lexible
enough o deal wi h speci ic issues o he p oblem, bu also gene al so as o app oach
o he lo -sizing and scheduling p oblems. Me aheu is ics a e gene al amewo ks
ha can include speci ic heu is ics o e en exac me hods. The o me ake ad an age
o he p oblem s uc u e o inc ease he e iciency o he me hod, whe eas he la e
keep i s gene ali y. The e o e di e en componen s o he me aheu is ic can be used
o add ess dis inc ea u es o he p oblem, p o iding he lexibili y in adap ing o
mul iple p oblems. A me aheu is ic is hus o be de eloped and i s pe o mance
assessed. In pa icula , he ollowing ques ions a e o be answe ed:
•Wha decisions should be sol ed op imally and wha should be de e mined
heu is ically?
•How should campaigns be manipula ed?
•How can disc e e speed a es be add essed?
2. De elop a ma hema ical model o be used in p ac ice, as well as an app op ia e
solu ion app oach wi h he equi ed p e- and pos -op imiza ion phases
The e icien esolu ion o he a o emen ioned p oblem is an impo an ma e , since
many lo -sizing and scheduling p oblems will sha e simila ea u es. Howe e , o
alida e i s sui abili y o he speci ic case s udy i has o be es ed in p ac ice. Also,
he model needs o be ex ended, adap ed o e en e o mula ed, in o de o deal wi h
he indus ial issues o a p ac ical implemen a ion. The second objec i e hus aims
a o mula ing a ma hema ical model o be inco po a ed in a decision suppo sys em
(DSS), which will help manage s in hei planning ac i i ies. The solu ion app oach
also needs o be e ised (conside ing he new ea u es) and upg aded wi h p e- and
pos -op imiza ion s eps. The DSS will be he in e ace used o es and assess he
model and me hod in p ac ice.
This objec i e includes he ollowing esea ch ques ions:
•Wha indus ial ea u es ha e o be conside ed in a model o be used in p ac-
ice?
6 Chap e 1. Mo i a ion and amewo k
•How should (con inuous) p oduc ion campaigns be in e sec ed wi h (disc e e)
due da es?
•How can such a model be app oached and inco po a ed in a DSS? How o
implemen he in e aces wi h use s and exis ing sys ems?
B anch 2 – P oac i e planning
The second b anch o his disse a ion ocuses on p oac i e app oaches. Dealing wi h
unce ain y is a complex issue, especially when he de e minis ic p oblem is al eady in-
ac able. The e o e, i is impe a i e o de ise in elligen ways o modelling and sol ing
hese complex sys ems. Simula ion is no only able o easily add ess unce ain y, bu also
accu a e ep esen a ions o di e en ypes o unce ain y. Fo ins ance, s ochas ic p o-
g amming allows assigning p obabili y dis ibu ion o ce ain pa ame e s. Simula ion on
he o he hand can emula e dis u bances (wi h speci ic s a ing and ending imes) wi h no
ma hema ical sophis ica ion o complexi y. The e o e, simula ion-op imiza ion (S-O) ap-
pea s as a powe ul app oach, since i can combine he ease o simula ion o dealing wi h
complexi y and he ocus o op imiza ion in inding good quali y solu ions. Two main
objec i es we e hus de ined:
1. S udy and classi y he di e en ways o combining simula ion and op imiza ion and
ela e hem o p oblem cha ac e is ics
Simula ion and op imiza ion can be combined in nume ous ways and he selec ion
o he app op ia e design can ha e a huge impac on he e iciency o he me hod.
Tha choice will en i ely depend on he cha ac e is ics o he p oblem o be ackled.
The e o e, he i s objec i e o his second esea ch line is o s udy S-O me hods and
he way hey ela e o p oblem cha ac e is ics. Since he li e a u e in S-O does no
ha e a classi ica ion ha co e s he ull spec um o hese me hods, his hesis seeks
also o p opose a axonomy wi h he mos ele an classi ying dimensions.
The main esea ch ques ions associa ed wi h his objec i e a e hen he ollowing:
•Wha a e he key dimensions in which S-O me hods should be classi ied?
•Wha ypes o p oblems a e bes add essed by each S-O design?
2. Design and de elop a simula ion-op imiza ion amewo k o p oduc ion planning
and scheduling p oblems unde unce ain y
A e ha ing an o e iew o he ull spec um o S-O me hods, he objec i e is o
de elop an S-O amewo k ha is sui able o p oduc ion planning and scheduling
p oblems. Acco ding o he gene al analysis pe o med in he p e ious objec i e,
some S-O designs will be immedia ely dis ega ded, while o he may need u he
a en ion.
The aim he e is o explo e he ollowing ques ions:
•Wha ea u es should be kep in op imiza ion and wha could be ans e ed o
simula ion?
1.3. Thesis synopsis 7
•Wha me hod should be used o app oach he op imiza ion pa ?
•Wha ype o simula ion is mos app op ia e?
•How should he in e ac ion be designed (wha eedback and when should sim-
ula ion p o ide o op imiza ion)?
Figu e 1.2 shows he o e all s uc u e o he hesis, aming he ou main objec i es in
he wo a o emen ioned esea ch lines. I should be no ed howe e ha he app oaches p o-
posed o eac i e planning can also add ess p oac i e issues and ice- e sa. Fo ins ance,
conside ing slacks in eac i e models will help accommoda ing unce ain ies. Also, an
e icien me aheu is ic add essing unce ain y may s ill be able o p oduce solu ions o ea-
sonable quali y in easible ime (quickly eac ing o a dis up ion). Ne e heless, a p oac i e
app oach will be ocused on de e mining app op ia e slacks, while a eac i e me hod will
be mo e e icien i i does no expend so much e o ackling unce ain y. The e o e,
di e en me hods should be used o eac i e and p oac i e planning and bo h should be
applied acco ding o he s a e o he sys em.
Ope a ional P oduc ion Planning and Scheduling o Con inuous P&P Mills
Reac i e Planning P oac i e Planning
De elop E icien Solu ion Me hod (O1)
De elop P ac ice-D i en Ma hema ical
Model, Solu ion App oach and DSS (O2)
S udy Hyb id Simula ion-Op imiza ion
Me hods (O3)
Design and De elop
Simula ion-Op imiza ion F amewo k (O4)
Figu e 1.2: Resea ch objec i es.
1.3. Thesis synopsis
The chap e s o his hesis consis o a collec ion o pape s. Each pape (o chap e ) is
aligned wi h each o he esea ch objec i es p e iously de ined. This sec ion p o ides an
o e iew o he main aspec s co e ed by hese a icles.
Chap e 2app oaches he planning and scheduling ha appea s a he P&P indus y
wi h a hyb id app oxima e me hod. A a iable neighbou hood sea ch (VNS) is hyb idized
wi h an exac linea p og amming sol e and a speci ic heu is ic o deal wi h he bina y
a iables ela ed o he disc e e diges e ’s speed a es. The mul iple neighbou hood s uc-
u es we e speci ically designed o op imize lo -sizing and scheduling p oblems, including
he disc e e, con inuous se up, p opo ional and gene al lo -sizing and scheduling p oblems
(DLSP, CSLP, PLSP and GLSP, espec i ely). Those s uc u es ocus on he se up pa e n,
adding / emo ing /mo ing en i e campaigns o / om ce ain posi ions o he schedule.
Then, he exac sol e and he speci ic heu is ic a e used o decode hese pa e ns in o inal
8 Chap e 1. Mo i a ion and amewo k
plans, so ha hey can be p ope ly assessed. While he heu is ic is speci ic o cases whe e
he speed a e is de ined by a disc e e g id (due o ope a ional cons ain s o modelling
issues), he sol e is gene ic and allows o an easy inco po a ion o any linea cons ain .
Mo eo e , i ully op imizes con inuous a iables, which is impo an when he e is s ill a
deg ee o eedom a e he bina y a iables ha e been ixed. The esul ing me hod shows
a e y in e es ing pe o mance on eal wo ld sized ins ances and seems o be p omising o
o he lo -sizing and scheduling p oblems.
In Chap e 3 he ma hema ical model and solu ion me hod a e e ised o be inco po-
a ed in a DSS o be used in p ac ice. The model is ex ended o deal wi h a a ie y o
issues, such as di e en p io i y le els o o de s, a iable p oduc ion a es in all uni s,
scheduled s oppages and ixed campaigns. This las ea u e mo i a ed also he e o mula-
ion o ime slo s, so ha a easible plan could always be gene a ed. The con inuous slo s
a e able o c oss he disc e e pe iods used o demand ul ilmen , which a oids ha ing o
(heu is ically) de e mine he numbe o slo s o each campaign. Like he p e ious model,
i conside s he sequence-dependen se up imes and cos s o he pape machine and he
in eg a ion wi h he o he s ages. The e o e, an e icien solu ion me hod is e en mo e nec-
essa y. Howe e , he new o mula ion o ime slo s equi ed including addi ional bina y
a iables, which would comp omise he pe o mance o he VNS, since he decoding p o-
cedu e would become d as ically mo e complex. The e o e, a MIP-based heu is ic was
de eloped, which p o ides good enough solu ions o p ac ical use. The me hod comp ises
a main op imiza ion phase and a pos -op imiza ion s ep. The o me gene a es an ini ial
solu ion and imp o es i , sol ing sub-MIP’s, i s in a o wa d pass and hen wi h a biased
selec ion. The pos -op imiza ion smoo hs p oduc ion a es by ixing slo s leng hs. This
sepa a ion is conduc ed o a oid non-linea i y. Addi ionally, he chap e desc ibes he in-
e aces o he DSS wi h he exis ing sys ems in he company and wi h he inal use s, as
well as impo an p e- and pos -p ocessing s eps. The sys em is used no only o gene a e
op imized plans, bu also o es and assess manually de ised plans.
Chap e s 4and 5 hen ocus on p oac i e planning. The o me conduc s a gene al
s udy o simula ion-op imiza ion me hods, whe eas he la e discusses an S-O amewo k
o p oduc ion planning and scheduling p oblems.
In Chap e 4 he ull spec um o S-O me hods is e iewed, in o de o p o ide an
o e iew o a p ope classi ica ion o hese me hods. The key classi ying dimensions
a e iden i ied. The pu pose o simula ion in he whole p ocedu e appea s o be he mos
ele an , since i dis inguishes he main s eams o esea ch in S-O. The Simula ion com-
muni y ypically uses simula ion models o gi e eedback wi h espec o he quali y o he
solu ions being simula ed. The Op imiza ion communi y ends o use simula ion combined
wi h analy ical models, so as o ake ad an age o he p oblem s uc u e, whe e simula-
ion’s ou pu is used o enhance o complemen he op imiza ion model. O he key dimen-
sions conce n he hie a chical s uc u e ha ela es simula ion wi h op imiza ion, he sea ch
me hod and he way he p obabili y space is explo ed. E e y ca ego y o each dimension
is ela ed o speci ic p oblem cha ac e is ics, hus p o iding insigh s ega ding he ypes o
p oblems ha a e bes app oached by each S-O design.
Chap e 5s a s om he p e ious gene al s udy and explo es S-O me hods in he con-
ex o a p oduc ion planning and scheduling p oblem. The p oblem is inspi ed by he
Bibliog aphy 9
case s udy and gene alized keeping jus he mos ele an ea u es. In pa icula , only wo
s ages (and he ank in be ween) a e conside ed. As p e iously discussed, he p oduc ion
sys em o he case s udy is subjec o a a ie y o unce ain ies, bo h in he o m o p o-
cess a iabili y and as dis u bances. To p ope ly model hose occu ences, disc e e-e en
simula ion is applied. The de e minis ic analy ical model appea s o be use ul o he op i-
miza ion o con inuous a iables, while a me aheu is ic, based on ha p oposed in Chap e
2, is de eloped o in elligen ly manipula ing he disc e e a iables. The combina ion o
simula ion and op imiza ion is hen discussed in i s main dimensions, namely he pu pose
o simula ion and he hie a chical s uc u e.
Finally, Chap e 6summa izes he mos subs an ial esul s ob ained wi h his hesis and
gi es di ec ions o u u e esea ch.
Bibliog aphy
CEPI. Key s a is ics – eu opean pulp and pape indus y 2012. Technical epo , June 2013.
Be nha d Fleischmann, He be Mey , and Michael Wagne . Ad anced planning. In Ha -
mu S ad le and Ch is oph Kilge , edi o s, Supply Chain Managemen and Ad anced
Planning, pages 81–106. Sp inge Be lin Heidelbe g, 2008.
Ma is ela Oli ei a San os and Be na do Almada-Lobo. In eg a ed pulp and pape mill
planning and scheduling. Compu e s &Indus ial Enginee ing, 63(1):1–12, 2012. ISSN
0360-8352.
Chap e 2
Solu ion app oach o p oduc ion
planning and scheduling
A hyb id VNS app oach o he sho - e m p oduc-
ion planning and scheduling: A case s udy in he pulp
and pape indus y
Gonçalo Figuei a∗·Ma is ela Oli ei a San os†·Be na do Almada-Lobo∗
Published in Compu e s &Ope a ions Resea ch, 2013
h p://dx.doi.o g/10.1016/j.co .2013.01.015
Abs ac Ma hema ical o mula ions o p oduc ion planning a e inc easing complex-
i y, in o de o imp o e hei ealism. In sho - e m planning, he desi able le el o de ail
is pa icula ly high. Exac sol e s ail o gene a e good quali y solu ions o hose com-
plex models on medium and la ge-sized ins ances wi hin easible ime. Mo i a ed by a
eal-wo ld case s udy in he pulp and pape indus y, his pape p o ides an e icien solu-
ion me hod o ackle he sho - e m p oduc ion planning and scheduling in an in eg a ed
mill. Decisions on he pape machine se up pa e n and on he p oduc ion a e o he pulp
diges e (which is cons ained o a maximum a ia ion) complica e he p oblem. The ap-
p oach is buil on op o a mixed in ege p og amming (MIP) o mula ion de i ed om he
mul i-s age gene al lo sizing and scheduling p oblem. I combines a Va iable Neighbou -
hood Sea ch p ocedu e which manages he se up- ela ed a iables, a speci ic heu is ic o
de e mine he diges e ’s p oduc ion speeds and an exac me hod o op imize he p oduc ion
and low mo emen decisions. Di e en s a egies a e explo ed o speed-up he solu ion
p ocedu e and al e na i e a ian s o he algo i hm a e es ed on ins ances based on eal
da a om he case s udy. The algo i hm is benchma ked agains exac p ocedu es.
Keywo ds Mul i-s age lo sizing and scheduling ·P oduc ion a es ·Pulp and pape in-
dus y ·Mixed in ege p og amming ·Va iable Neighbo hood Sea ch ·Hyb id me hods
∗INESC TEC, Faculdade de Engenha ia, Uni e sidade do Po o, Po o, Po ugal
†Uni e sidade de São Paulo - Ins i u o de Ciências Ma emá icas e de Compu ação, São Ca los-SP, B asil
18 Chap e 2. Solu ion app oach o p oduc ion planning and scheduling
0,00 0,50 1,00 1,50 2,00 2,50 3,00 3,50 4,00 4,50 5,00
0 1 2 3 4 5
186
170
140
125
115
R115
R140
Time (days)
Pape machine's schedule
11.5
12.0
12.5
13.0
13.5
14.0
Diges e 's speed ( pm)
Figu e 2.2: Pa ial p oduc ion plan: synch oniza ion be ween he diges e and he pape
machine.
2.3.2 Solu ion ep esen a ion and decoding
The algo i hm p oposed in his pape combines heu is ic and exac me hods in a GVNS
design (see Algo i hm 11 in Subsec ion 2.3.3 o he high le el p ocedu e). Each solu ion is
ep esen ed by he se up pa e n (encoding), i.e. he numbe o subpe iods assigned o each
pape g ade and hei sequence (which is he in o ma ion gi en by he se up a iables Yjs) –
see Figu e 2.4 o g aphical ep esen a ions. The GVNS i e a es h ough di e en pa e ns
and uses a decoding p ocedu e o ansla e each pa e n in o a inal p oduc ion plan (as
ha ep esen ed in Figu e 2.2, wi h subpe iods o di e en leng h and p oduc ion decisions
ela ed o he o he esou ces). Figu e 2.3 illus a es his gene al algo i hm s uc u e. The
decoding p ocedu e is a combina ion o an exac me hod and a speci ic heu is ic ( he Speeds
Cons ain Heu is ic –SCH). The exac me hod op imizes he con inuous a iables, so ha
good quali y solu ions a e no inco ec ly ejec ed and he algo i hm keeps i s simplici y
and lexibili y o cope wi h u he model ex ensions and modi ica ions. The heu is ic is
used o de e mine he diges e ’s speeds. The comple e decoding is p esen ed in Algo i hm
12.
Figu e 2.3: Gene al s uc u e o he hyb id algo i hm.
2.3. Hyb id VNS app oach 19
The Decode unc ion decodes g adually he solu ion while he objec i e alue is be e
han ha o he incumben ( inc), in o de o sa e compu a ional ime. This is pa icula ly
impo an in local sea ch, whe e he numbe o neighbou s o e alua e can be e y la ge.
I he solu ion is wo se han he incumben , i is ejec ed by conside ing i as in easible. In
he shaking p ocedu e o he GVNS, howe e , as he solu ion can de e io a e, an in ini y is
assigned o inc so ha wo se solu ions a e no ejec ed.
Decode s a s by calling an exac sol e o op imize he linea p og amming (LP) p ob-
lem ha esul s om ixing he se up pa e n Yand elaxing he speed a ia ion cons ain s
(line 1). This elaxa ion is achie ed by emo ing (2.3)–(2.6) and eplacing he diges e ’s
p oduc ion ou pu cons ain s (2.9) by he ollowing:
Xdig
s≤α· dig
max ·Nss∈[S].(2.1)
Xdig
s≥α· dig
min ·Nss∈[S].(2.2)
The new cons ain s jus impose uppe and lowe bounds on he diges e ’s ou pu (and
he e o e o i s speeds), lea ing he choice o he speed as a con inuous decision a iable.
In ac , he speed is now an implici a iable de ined by Vdig
s=Xdig
s/(α·Ns).
To ensu e ha he diges e ’s speeds sa is y he maximum a ia ion cons ain s (2.4),
he SCH is called o check, co ec and ix he speeds (line 3). In SCH (de ailed in Sec ion
2.3.6), he LP is sol ed again o upda e he alues o he con inuous a iables, acco ding o
he modi ied speeds. I he solu ion e u ns as in easible, he sol e is called o de ini ely
alida e he se up pa e n (sol ing he ixed MIP wi h he o iginal cons ain s un il a i s
solu ion is ound – line 5). The sol e is d as ically mo e demanding in e ms o compu a-
ional ime (o e 100 imes, acco ding o some p elimina y es ing) and he SCH enables a
quick alida ion o he easibili y o he majo i y o he neighbou solu ions.
Algo i hm 1: Decode(Y, inc)
1x0←Sol e (Y,RelaxSpeeds,Op imali y)
2i (x0)< inc hen
3x00 ←SCH(x0)
4i x00 is in easible hen
5x00 ←Sol e (Y,IncludeSpeeds,Fi s Sol)
6i x00 is easible and (x0)< inc hen
7x←x0
8else
9x←in
10 else
11 x←in
12 e u n x
The g adual decoding o solu ions is e lec ed no only in he numbe o s eps pe -
o med in Algo i hm 12, bu also in he i s LP sol ing p ocedu e. In ac , in ha p oce-
du e a speed-up s a egy called Dual Re-op imiza ion is used. This echnique in e up s he
LP op imiza ion p ocedu e (which is sol ed wi h he dual algo i hm), in case he solu ion
20 Chap e 2. Solu ion app oach o p oduc ion planning and scheduling
ge s wo se han he incumben (Mey ,2002;Guima aes e al.,2012).
2.3.3 GVNS design
The GVNS design is p esen ed in Algo i hm 11. A solu ion is ini ialized by Cons uc i eHeu is ic
and hen a se ies o Shake and VND execu ions y o imp o e his solu ion by explo ing
di e en egions o he space. In he shaking phase, he sea ch shi s o he nex neighbou -
hood i an imp o emen is no achie ed (line 10) and i e u ns o he i s one, o he wise
(line 8). Neighbou hoods a e sequenced in inc easing o de o he s eng h o he co -
esponding mo es. In his way, small pe u ba ions a e applied a e a local op imum is
ob ained, so ha i s close egion is well explo ed. Then, he sea ch di e si ica es mo e o
explo e di e en egions. The algo i hm ends a e he las neighbou hood has been ied
in shaking. A ime limi is also imposed (and checked h oughou he algo i hm). The inal
se up pa e n is exac ly decoded, unning he sol e un il op imali y wi h he Y a iables
ixed (line 11).
Algo i hm 2: GVNS(kmax,k0
max)
1x←Cons uc i eHeu is ic()
2k←1
3while k≤kmax do
4x0←Shake(x,k)
5x00 ←VND(x0,k0
max)
6i (x00)< (x) hen
7x←x00
8k←1
9else
10 k←k+1
11 x←Sol e (Y(x),IncludeSpeeds,Op imali y)
In he sea ch pe o med by he GVNS, c i ical cons ain s a e elaxed and hei iola ion
is penalized in he e alua ion unc ion, so ha he Cons uc i eHeu is ic is always
able o gene a e an ini ial solu ion. The VND is hen expec ed o co ec his iola ion,
which is ela ed o backlog co e ing (cons ain s (2.22)) and he i gin pulp and black
liquo s ank le els (cons ain s (2.15), (2.31) and (2.35)).
The neighbou hood s uc u es o be used in VND a e e y b oad in his case (as we
will see in he nex subsec ion). Mo eo e , as he e alua ion o each neighbou equi es
calling he expensi e Decode unc ion, he VND design (see Algo i hm 22) is ocused on
speeding-up he neighbou hood sea ch.
The neighbou hood sea ch is applied o each p oduc ion cycle, one a a ime ( he e i-
ica ion in lines 6-7allows no o epea cycles al eady explo ed since he las mo e). Also,
when an imp o emen mo e is ound, i is immedia ely selec ed and implemen ed ( i s -
imp o emen s a egy), a oiding an exhaus i e explo a ion o neighbou hoods. In addi ion,
o ind imp o ing solu ions mo e quickly, he neighbou s a e anked acco ding o hei like-
lihood o imp o ing he incumben solu ion (line 8). Since he las anked mo es a e no so
likely o imp o e, i is p obably no wo h (and is e en imp ac ical on eal-sized p oblem
2.3. Hyb id VNS app oach 21
ins ances) o explo e he en i e neighbou hoods. Thus, a gi en pa ame e (psi) de e mines
he pe cen age o he size o each neighbou hood i o be explo ed. I may also balance
he di e en neighbou hood educed sizes. The change o neighbou hoods is pe o med
in a cyclic way: he sea ch con inues in he same neighbou hood while i inds imp o -
ing solu ions and mo es o he ollowing o he wise (excep when he las neighbou hood
is explo ed – see lines 15-21). The VND is execu ed un il he numbe o non-imp o ing
consecu i e i e a ions (k00) eaches he numbe o neighbou hoods (k0
max).
Algo i hm 3: VND(x0,k0
max)
1k00 ←0
2while k00 <k0
max do
3k←1
4x00 ←x0
5 o c←1 o dCedo
6i c=c0+1and x0=x00 hen
7b eak
8So (Nc
k0(Y(x0)))
9while (x)≥ (x0)and k≤lpsk0· |Nc
k0(Y(x0))|mdo
10 x←Decode(Y, (x0)),Y∈Nc
k0(Y(x0))
11 k←k+1
12 i (x)< (x0) hen
13 x0←x
14 c0←c
15 i (x)< (x00) hen
16 k00 ←0
17 else
18 k00 ←k00 +1
19 k0←k0+1
20 i k0>k0
max hen
21 k0←1
22 e u n x0
The neighbou hood s uc u es conside compound mo es, i.e., each mo e is composed
o di e en pa ial mo es. The anking p ocedu e is hen pe o med o each o hese pa ial
mo es. The exac impac on he changeo e s cos is e alua ed and he changes in in en o y
and backlogging a e es ima ed, hus p o iding an indica o o he quali y o he mo e. In
o de o a oid p ema u e con e gence, a s ochas ic selec ion is applied, choosing andomly
in each i e a ion one o he p % bes anked mo es o be e alua ed. The de e minis ic
a ian is also es ed.
Finally, an ea ly ejec ion s a egy is implemen ed in o de o u he educe compu a-
ional ime. The s a egy consis s on examining mo es easibili y ega ding backlog co -
e ing cons ain s. In ac , i he only p oduc ion un o a g ade wi h backlog o ul il in a
gi en cycle is emo ed (and no o he un o ha g ade is inse ed), he mo e will esul in
an in easible solu ion and hus, i can be ejec ed be o e execu ing he Decode p ocedu e.
The ollowing subsec ions explo e in mo e de ail he di e en ing edien s o he algo-
i hm (neighbou hood s uc u es, Cons uc i eHeu is ic and SCH).
22 Chap e 2. Solu ion app oach o p oduc ion planning and scheduling
2.3.4 Neighbou hood s uc u es
A neighbou o an incumben solu ion xis ob ained by sligh ly changing he se up pa e n
and decoding i (see line 10 o Algo i hm 22). We ha e de ined ou di e en ypes o
neighbou hood s uc u es, which sha e a common ea u e: he o al numbe o subpe iods
keeps cons an , which is impo an when he LP model is sol ed. Figu e 2.4 illus a es he
neighbou hood s uc u es, each wi h an example o a mo e applied o a gi en se up pa e n.
I is impo an o no e ha ime is disc e ized in subpe iods, which a e he decoding
p ocedu e may ha e di e en leng hs.
115
125
140
170
186
Incumben
(a) Subpe RemIns( 1, 2)
0 5 10 15
115
125
140
170
186
Time (subpe iods)
Neighbou
inse 1 subpe iod
emo e
1
2
1
2
115
125
140
170
186
Incumben
(b) RunRemIns( 1, 2)
0 5 10 15
115
125
140
170
186
Time (subpe iods)
Neighbou
emo e
1
inse KLB125
2
115
125
140
170
186
Incumben
(c) RunInsSubpe Rem( 1,[R2])
0 5 10 15
115
125
140
170
186
Time (subpe iods)
Neighbou
emo e
emo e
inse KLB140
1
2,2
2,2
2,1
2,1
115
125
140
170
186
Incumben
(d) RunRemSubpe Ins( 1,[R2])
0 5 10 15
115
125
140
170
186
Time (subpe iods)
Neighbou
1
emo e
inse 2 subpe iods
2
2
Legend:
KLB
VLB
Figu e 2.4: Illus a ion o he neighbou hood s uc u es.
Gi en a se o p oduc ion uns =1,...,Rand a se o g ades j=1,...,K, le j( ) deno e
he g ade being p oduced on un ,s( ) be i s numbe o subpe iods and o( ) i s posi ion in
he sequence. The de ini ion o he neighbou hood s uc u es hen ollow:
•S ubpe RemIns( 1, 2) (Figu e 2.4(a)) consis s on emo ing one subpe iod om a
un 1(in which s( 1)>1, so ha he un i sel is no emo ed) and inse ing ano he
one in o a un 2, such ha 2, 1.
•RunRemIns( 1, 2) (Figu e 2.4(b)) emo es a comple e p oduc ion un 1and inse s
ano he un 2, such ha s( 2)=s( 1)∧(j( 2),j( 1)∨o( 2),o( 1)).
•RunInsS ubpe Rem( 1,[R2]) (Figu e 2.4(c)) inse s a p oduc ion un 1and consec-
u i ely emo es single subpe iods (in a o al o s( 1)) om a se [R2] o any uns
2.3. Hyb id VNS app oach 23
2∈[R]∪ { 1}, such ha s( 2)>1.
•RunRemS ubpe Ins( 1,[R2]) (Figu e 2.4(d)) emo es a p oduc ion un 1and con-
secu i ely inse s single subpe iods (in a o al o s( 1)) in o a se [R2] o any uns
2∈[R]∪ { 1}, such ha ∃ 2, 1.
The i s neighbou hood (based on S ubpe RemIns( 1, 2)) is he smoo hes and only
explo es he dis ibu ion o p oduc ion subpe iods among he exis ing uns. The o he h ee
a e e y b oad in he sense ha hey ex end adi ional neighbou hoods (such as ans e ,
spli ing and agg ega ion o uns).
Some p elimina y es s we e pe o med in o de o selec he neighbou hood s uc u es
o he local sea ch phase, as well as hei sequence. The esul s led o he selec ion o he
las h ee, in he o de hey we e p esen ed he e.
Fo he shaking phase, six de i ed neighbou hoods a e used in he ollowing o de :
h ee neighbou hoods based on S ubpe RemIns( 1, 2), consis ing o one, wo and h ee
andom mo es o ha ype, espec i ely; h ee o he based on RunRemIns( 1, 2), consis -
ing o one, wo and h ee andom mo es, espec i ely.
2.3.5 Cons uc i e heu is ic
Finding an ini ial solu ion o his p oblem consis s on de e mining a se up pa e n o he
pape machine, which is hen decoded by Decode unc ion (as seen in Subsec ion 2.3.2).
The cons uc i e heu is ic p oposed he e can be di ided in wo main s eps: sequencing
g ades and assigning a numbe o p oduc ion subpe iods o each g ade. To make i simple,
only one un is conside ed pe g ade and pe cycle, a his s age. The p ocedu e is sepa a ely
execu ed o each cycle and decodes in each i e a ion he pa ial solu ion, composed o
all he conside ed se up a iables (whose in eg ali y was elaxed in he beginning o he
algo i hm). Algo i hm 18 exhibi s he main p ocedu e.
In each cycle, sequencing is execu ed by consecu i ely choosing, among he g ades
wi h demand o backlog o ul il in ha cycle, he one (wi hin he same p oduc ype) o
he ollowing g ade ei he in ascending o descending o de . Fo ins ance, g ades may s a
inc easing he g ammage alue wi hin a gi en p oduc ype (e.g. KLB). Then, a changeo e
o ano he ype (VLB) is pe o med, s a ing a he highes alue ( o he shi o be smoo h)
and dec easing un il he lowes . Finally, i e u ns o he o iginal ype (KLB), i he e a e
any g ades le , s a ing a he lowes and con inuing in ascending o de . In his way, he
amoun o ime los in se ups is ela i ely small. The i s se up pa e n in Figu e 2.4(a) is an
illus a i e example o a sequence o pape uns s a ing in ascending o de . The p ocedu e
can be execu ed in he opposi e way (s a ing wi h dec easing g ades), which will lead o
he mi o ed sequence. Bo h sequences (de ined by o de l,l={1,2}) a e gene a ed (see
line 5) and e alua ed in he Cons uc i eHeu is ic and he one ha p o ides he bes
esul s is selec ed (lines 16-17). As his sequencing p ocedu e is de e minis ic and may
lead owa ds p ema u e con e gence, a s ochas ic a ian is also implemen ed.
Fo each o he gene a ed sequences, he assignmen o subpe iods o pape g ades has
o be de e mined. The heu is ic s a s assigning an amoun o subpe iods ha gua an ees
24 Chap e 2. Solu ion app oach o p oduc ion planning and scheduling
he backlog co e age o he co esponding cycle (lines 6-7). F om ha assignmen , h ee
di e en cases may occu :
•The numbe o assigned subpe iods is he same as he o al a ailable o schedule and
hus, he p ocedu e has inished;
•The assigned subpe iods a e mo e han hose a ailable and consequen ly some sub-
pe iods ha e o be emo ed om p oduc ion uns;
•The e a e s ill subpe iods o be assigned, equi ing a p ocedu e o de e mine he
addi ional assignmen .
The assignmen o subpe iods in he i s s ep ( o ul il backlog) is pe o med assuming
ha all supe iods ha e equal leng hs. The e o e, he emo al o subpe iods in he second
case does no necessa ily esul in an in easible solu ion, since he slack o some pape
g ades can be used by o he g ades adjus ing he leng h o he subpe iods. Hence, an
i e a i e p ocedu e is execu ed, whe e in each i e a ion a subpe iod is emo ed om he
g ade wi h he g ea es slack (line 9).
When he numbe o assigned subpe iods is less han he o al a ailable ( hi d case), a
u ili y measu e ujis used o de e mine he po ion o he emaining subpe iods o assign
o each g ade (line 12). The g ea e he p oduc ion needs (conside ing demand, backlog
and in en o y on he one hand, and he al eady assigned subpe iods on he o he hand) and
he as e he p oduc ion a e o a gi en g ade a e, he highe he u ili y will be. Howe e ,
he numbe o subpe iods o assign is cons ained by he ac ual p oduc ion equi emen s
SaddReqj. Then, i he e a e s ill subpe iods o be assigned, an i e a i e p ocedu e is used,
choosing in each i e a ion he g ade wi h he g ea es p oduc ion needs.
2.3.6 Speeds Cons ain Heu is ic (SCH)
The Speeds Cons ain Heu is ic has o check, co ec and ix he speed alues ha esul
om he op imiza ion o he i s LP (in which he speed a iables and cons ain s we e e-
mo ed) – see Algo i hm 12. The SCH i e a es h ough subpe iods, compa ing he diges e ’s
speed o ha o he p e ious subpe iod. The main s eps a e p esen ed in Algo i hm 13.
In o de o ge mo e con ol o e he beha iou o he speed pa e n, he (guiding) ob-
jec i e unc ion is sligh ly modi ied. The i gin pulp p oduc ion ou pu o ea ly subpe iods
is a ou ed o e he ou pu o hose ha ollow. The e o e, a i s only he speed shi
uppe limi may be iola ed and hen, when one o he downs eam anks (ei he he i gin
pulp o he weak black liquo ) ge s ull, he speed may be ab up ly educed.
The co ec ion o he uppe limi iola ion becomes i ial: i is jus necessa y o educe
he speed alue o he p e ious speed inc emen ed by he maximum a ia ion (see line 4).
The same is no ue o he lowe limi , since inc easing he speed alue will necessa ily
esul in o e low o he ank le els (as he diges e ’s p oduc ion was being maximized),
unless he speed has been educed in a p e ious subpe iod. In case o o e low, he speeds
o p e ious subpe iods ha e also o be educed. Thus, a e a se o consecu i e subpe iods
2.3. Hyb id VNS app oach 25
Algo i hm 4: Cons uc i eHeu is ic()
1x0←in
2 o l←1 o 2do
3Relax in eg ali y o Y
4 o c←1 o dCedo
5Sequencing(c,o de l)
6SassignCalcj←a e agen|S |
cap | ∈[Tc]o·pj·IG−
j, 1c−1(x)+s k j, whe e k,j∈[K] and kis
be o e jin he sequence
7Sassignj←lSassignCalcjm,j∈[K]
8while PjSassignj>|Scyclec|do
9k←a gmaxnSassignj−SassignCalcj|j∈[K]o
10 Sassignk←Sassignk−1
11 i PjSassignj<|Scyclec| hen
12 Sassign0
j←minnjuj·|Scyclec| − PjSassignjk,SaddReqjo,j∈[K]
13 I e a i ely assign he emaining subpe iods acco ding o p oduc ion needs
14 De e mine Yacco ding o he de ined sequence and subpe iods assignmen
15 x←Decode(Y, (x0))
16 i (x)< (x0) hen
17 x0←x
18 e u n x0
{si,...,s }whe e he speed educ ion has been iola ed, he i e a i e p ocedu e is in e -
up ed and he p e ious speeds a e educed un il all he cumula i e o e low has been elim-
ina ed (line 9). The i e a ion hen es a s a e all he assessed speeds ha e been ounded
down o he nex alue o he g id, in o de o gua an ee disc e e alues (which is impo an
o he esul s o be compa able o hose ob ained when sol ing he comple e MIP exac ly).
A he end, he speeds a e ixed (in addi ion o he se up pa e n) and he sol e is called o
upda e he con inuous a iables (in an LP).
Algo i hm 5: SCH(x)
1while ∃s∈S:|Vdig
s−Vdig
s−1|>∆·Φdo
2 o s←1 o Sdo
3i Vdig
s>Vdig
s−1+ ∆ ·Φand he e is no speed educ ion o co ec hen
4Vdig
s←Vdig
s−1+ ∆ ·Φ
5else i Vdig
s<Vdig
s−1−∆·Φ hen
6Vdig
s←Vdig
s−1−∆·Φ
7Upda e siand s
8i he e is any speed educ ion o co ec and ( he speed educ ion in s does no need
co ec ion o s=S) hen
9Laye Remo al(si,s )
10 b eak
11 Round down all he assessed speeds
12 x0←Sol e (Y(x),FixSpeeds,Op imali y)
13 e u n x0
26 Chap e 2. Solu ion app oach o p oduc ion planning and scheduling
9,5
10
10,5
11
11,5
12
12,5
13
13,5
14
0 20 40 60 80 100 120
Diges e 's speed ( pm)
Time (hou s)
O iginal pa e n
Co ec ed pa e n 1
(a) Fi s co ec ion
9,5
10
10,5
11
11,5
12
12,5
13
13,5
14
0 20 40 60 80 100 120
Diges e 's speed ( pm)
Time (hou s)
Co ec ed pa e n 1
Co ec ed pa e n 2
Co ec ed pa e n 3
(b) Laye emo al
Figu e 2.5: Speed pa e n co ec ion p ocedu e.
The educ ion o he p e ious speeds consis s on an i e a i e p ocedu e based on he
idea o ‘laye emo al’. This p ocedu e is illus a ed in Figu e 2.5b. In Figu e 2.5a he
speed pa e n s a s a i s maximum alue (13.5 pm in his case) and ab up ly dec eases
in a gi en subpe iod, due o one o he anks being comple ely illed. The e o e, a co ec-
ion is made o he speed pa e n in o de o elimina e he iola ions o he smoo h speed
shi s (co ec ed pa e n 1) – see line 6in Algo i hm 13. Howe e , his adjus men causes
a iola ion in he ank le els. Thus, he speed pa e n has o be lowe ed, i.e., laye s ha e
o be emo ed, as in he co ec ed pa e n 2 (whe e one laye was emo ed) and he co -
ec ed pa e n 3 (whe e wo laye s we e emo ed). The laye emo al p ocedu e has o be
execu ed un il he a ea benea h he co ec ed pa e n and abo e he o iginal pa e n ( ha
co esponds o addi ional con en inside he anks) is less han he a ea abo e he o me
and unde he la e ( ha co esponds o he con en ha is emo ed om he anks). The
speed educ ions do no ha e o be pe o med h ough en i e laye s ( his would lead o un-
necessa y ex a educ ions). Hence, hey a e execu ed subpe iod by subpe iod, in a o wa d
mo e.
2.4. Compu a ional es s and esul s
In his sec ion we p esen he expe imen al esul s ha alida e he solu ion me hod design
and show how i beha es o a a ied se o ins ances. We s a by p esen ing how he com-
pu a ional es s we e designed. Then, he inal esul s, which compa e di e en a ian s
o he p oposed me hod, he MIP-based heu is ic (MIPBH) by San os and Almada-Lobo
(2012) and IBM ILOG Cplex 12.1 ( o he comple e MIP), a e exhibi ed. All he me hods
we e implemen ed in C++, compiled using GCC and un on an In el Xeon CPU E5504
@ 2.0 GHz, wi h 3 Gb o andom access memo y. Cplex was also used as he LP sol e
(wi hin ou algo i hm) and i was limi ed o one h ead in all me hods o ha e a ai com-
pa ison.
2.4. Compu a ional es s and esul s 27
2.4.1 Tes s design
2.4.1.1 Ins ances
A se o di e en ins ances we e gene a ed based on eal da a om he company o he
case s udy. The aim he e is on he one hand o es he me hods on ins ances as close as
possible o eal-wo ld da a and, on he o he hand, o compa e and analyse hei beha iou
on a a ie y o scena ios, which should ep esen di e en planning sys ems and s a egies.
Also, i is impo an o assess he obus ness ega ding di e en momen s in ime and KPIs
(Key Pe o mance Indica o s) policies.
The con igu a ion se o es classes is de ined by all he combina ions o T={8,15}
(whe e he numbe o pe iods pe cycle |Tc|is 5 o 10, espec i ely, co esponding o 1.5
cycles), |S |={3,4}and K={8,16}. I is impo an o no e ha in spi e o he o al numbe o
g ades o he s udied company being 29, only abou a hal o hem has demand o backlog
o ul il in each p oduc ion cycle and he e o e is conside ed o be p oduced in ha cycle.
The ins ance class ha ma ches he company’s eali y is de ined by: T=15 (|Tc|=10 and
C=1.5) and K=16. The numbe o subpe iods is ye o be de ined and i will depend on
he quali y o he inal p oduc ion plans ( he ade-o be ween he accu acy o he model
and he e iciency o he me hod is o be assessed in p ac ice).
Fo each class, 10 di e en ins ances we e gene a ed, a ying some pa ame e s ha
appea o be mo e dynamic, namely demand in ensi y, ini ial ank le els and company’s
KPIs. Fo he demand in ensi y (which is de ined he e as he equi ed ime o p oduce all
demand and backlog – excluding se ups – di ided by he o al a ailable ime), a uni o m
dis ibu ion U[0.65,0.85] was used. Rega ding he ini ial ank le els, a uni o m U[0.8,1.2]
was mul iplied by he o iginal alues. I any o he lowe o uppe bounds we e iola ed,
he co esponding alue was co ec ed o ha bound. The KPIs ( ep esen ed by wi– see
3.4.4) we e andomly a ied be ween hal and double o he o iginal alues p o ided by
he decision make , bu conside ing he same p obabili y o being less o g ea e han hose
alues. The e o e, ei he U[0.5,1] o U[1,2] we e used wi h a p obabili y o 50% each.
2.4.1.2 Algo i hm a ian s and gene al pa ame e s
Va ian s o he main p ocedu e o ou algo i hm men ioned in Sec ion 5.4 a e es ed he e.
We choose no o combine a ian s, in o de o ha e a easonably small amoun o me hods
o es . S ill, he po en ial bene i s o each al e na i e design can be assessed by compa ing
he esul s o he co esponding a ian o hose o he S anda d Algo i hm. The al e na i e
a ian s a e as ollows:
•De Mo es uses a de e minis ic s a egy o he sequence o neighbou solu ions o be
e alua ed. Ins ead o choosing andomly one o he p % bes anked mo es in each
i e a ion (whe e p was chosen o be 10, based on p elimina y es s), i selec s he
absolu e bes .
•RelaxBCo allows empo a ily some iola ion o he backlog co e ing cons ain
(2.22) in he middle o he algo i hm’s p ocedu e, in o de o make he change o
34 Chap e 2. Solu ion app oach o p oduc ion planning and scheduling
K. Schumache and J. Sa haye. India’s pulp and pape indus y: P oduc i i y and ene gy
e iciency. Technical epo , LBNL-41843, 1999.
Appendix 2.A In eg a ed P&P ma hema ical o mula ion
The p esen a ion o he MIP model is di ided in o ou pa s: one o each o he h ee
main p oduc ion s eps ( ela ed o pulp mill, pape mill and chemicals eco e y plan ) and
he las dedica ed o he objec i e unc ion. The indices, pa ame e s and decision a iables
a e de ined along he p esen a ion o he model.
2.A.1 Pulp mill
Pa ame e s, indices and se s:
Index o pe iod ( ∈[T]={1,...,T})
sIndex o subpe iod (s∈[S]={1,...,S})
[S ] Se o subpe iods sbelonging o pe iod
ΦMinimum possible speed a ia ion (in pm)
∆Maximum possible speed s ep
VNumbe o speeds, ha is equal o dig
max− dig
min
Φ+1
dig
max dig
minMaximum (minimum) speed o he diges e (in pm)
Index o diges e ’s o a ion speed ( ∈[V]={1,...,V})
sp Value o he speed indexed by (e.g. sp1= dig
min)
cap Capaci y o pe iod (in hou s)
Nmin Minimum subpe iod leng h (in hou s)
αDiges e ’s con e sion pa ame e om pm o onnes
Ydig
,0
1 i he diges e is unning a speed a he beginning o he planning ho izon,
0 o he wise
x ecy
max x ecy
min Maximum (minimum) p oduc ion a e o he ecycled pulp plan (in onnes pe hou )
k ecy
cap Capaci y coe icien o ecycled ib e plan
I i g
0I ecy
0Ini ial in en o y o i gin ( ecycled) pulp a he beginning o he planning ho izon (in onnes)
I i g
max I i g
min Uppe (lowe ) bounds on he i gin pulp s ocked in he espec i e ank (in onnes)
I ecy
max I ecy
min Uppe (lowe ) bounds on he ecycled pulp s ocked in he espec i e ank (in onnes)
Decision a iables:
Ydig
s
1 i he diges e uns a speed in subpe iod s,
0 o he wise
NsLeng h o subpe iod s(in hou s)
Nh s Time ha he diges e wo ks a speed in subpe iod s(in hou s)
Xdig
sOu pu o he diges e in subpe iod s(in onnes o i gin pulp)
X ecy
sOu pu o he ecycled pulp mill in subpe iod s(in onnes o ecycled pulp)
I i g
s(I ecy
s) In en o y o i gin ( ecycled) pulp in he espec i e ank a he end o mic o-pe iod s(in onnes)
O i g
s(O ecy
s) Ou pu o i gin ( ecycled) pulp ank in mic o-pe iod s(in onnes)
IS ecy
sQuan i y o pulp ed back o he ecycled pulp mill du ing he pape g ade changeo e in s(in onnes)
X
Ydig
s =1,s∈[S] (2.3)
2.A. In eg a ed P&P ma hema ical o mula ion 35
Ydig
s ≤
min( +∆,V)
X
w=max( −∆,0)
Ydig
w,s−1, ∈[V],s∈[S] (2.4)
Nh s ≤cap ·Ydig
s , ∈[V],s∈[S] (2.5)
Ns=X
Nh s,s∈[S] (2.6)
X
s∈[S ]
Ns=cap , ∈[T] (2.7)
Ns≥Nmin,s∈[S] (2.8)
Xdig
s=α·X
sp ·Nh s,s∈[S] (2.9)
X ecy
s≥x ecy
min ·Ns,s∈[S] (2.10)
X ecy
s≤x ecy
max ·Ns,s∈[S] (2.11)
X
s∈[S ]
X ecy
s≤k ecy
cap ·x ecy
max ·cap , ∈[T] (2.12)
Xdig
s+I i g
s−1=O i g
s+I i g
s,s∈[S] (2.13)
X ecy
s+I ecy
s−1+IS ecy
s=O ecy
s+I ecy
s,s∈[S] (2.14)
I i g
min ≤I i g
s≤I i g
max,s∈[S] (2.15)
I ecy
min ≤I ecy
s≤I ecy
max ,s∈[S] (2.16)
The diges e uns a he same speed h oughou each subpe iod s(cons ain s (2.3)).
Na u ally, he speed o he diges e in subpe iod sis implici ly de e mined by Vdig
s=P sp ·
Ydig
s . Cons ain s (2.4) ensu e a smoo h shi o he speed o he diges e be ween wo
consecu i e subpe iods. The wo king speed o he diges e and he leng h o each subpe iod
s(which is common o all esou ces) a e de ined by cons ain s (2.5) and (2.6). The sizes o
he mic o-pe iods o he same pe iod al oge he canno exceed he capaci y o he espec i e
pe iod (cons ain s (2.7)), bu each o hem has a minimum alue (cons ain s (2.8)), so ha
he diges e keeps i s speed du ing a leas a gi en amoun o ime. The amoun o i gin
pulp in subpe iod sis p opo ional o he speed o he diges e and o he leng h o s, as in
cons ain s (2.9).
The p oduc ion o he ecycled pulp plan (whe e he was e collec ed is e ined) in each
subpe iod, X ecy
s, is limi ed o lowe (x ecy
min ) and uppe bounds (x ecy
max) o p oduc ion a e.
Addi ionally, he whole p oduc ion in a pe iod canno exceed k ecy
cap o he o al capaci y o
he co esponding pe iod. These cons ain s a e exp essed in (2.10)-(2.12).
Bo h he i gin and ecycled pulp anks ha e limi ed s o age capaci y and mus be illed
wi h s ock o e a minimum limi (cons ain s (2.15) and (2.16)). The in en o y balancing
equa ions o i gin and ecycled pulp a e gi en by cons ain s (2.13) and (2.14). In he
case o ecycled pulp anks, i is necessa y o conside he eco e y o he pape loss du ing
g ade changeo e s and he cu ing s age (see cons ain s (2.14)).
36 Chap e 2. Solu ion app oach o p oduc ion planning and scheduling
2.A.2 Pape mill
Pa ame e s, indices and se s:
j,kIndices o pape g ades (j,k∈[K]={1,...,K})
j1Common i s pape g ade o all he cycles
cIndex o cycle (c∈[C−]={1,...,bCc} o c∈[C+]={1,...,dCe}, whe e C is he numbe
o cycles, which can be non-in ege )
[Tc] Se o pe iods belonging o cycle c(T=d|Tc| ·Ce,c∈[C−])
[Scyclec] Se o subpe iods sbelonging o cycle c
1cFi s pe iod o cycle c
s1cFi s subpe iod o cycle c
slk j Pape los (se up cos ) in a changeo e om g ade k o j(in onnes)
s k j Time los (se up ime) in a changeo e om g ade k o j(in hou s)
b i g
j1−b i g
jPe cen age o i gin ( ecycled) pulp used in he p oduc ion o pape g ade j
jPe cen age o wa e in pape g ade j
pjMinimum p ocessing ime o p oduce one onne o pape g ade j
MjLa ge numbe o each pape g ade j
mjMinimum lo size o pape g ade j
Dj Demand o pape g ade jin pe iod (in onnes)
ιA e age im loss (in pe cen age)
Yj0
1 i he pape machine is se up o g ade ja he beginning o he planning ho izon,
0 o he wise.
Decision a iables:
Zk js
1 i a changeo e om g ade k o j akes place a he beginning o subpe iod s,
0 o he wise.
Yjs
1 i he pape machine is se up o g ade jin subpe iod s,
0 o he wise.
Xjs Quan i y o pape g ade jp oduced in subpe iod s(in onnes)
IG+
j, In en o y o pape g ade ja he end o pe iod (in onnes)
IG−
j, Quan i y o pape g ade jbacklogged a he end o pe iod (in onnes)
X
j
b i g
j·1− j·
Xjs +X
k
slk j ·Zk js
=O i g
s,s∈[S] (2.17)
X
j
1−b i g
j·1− j·
Xjs +X
k
slk j ·Zk js
=O ecy
s,s∈[S] (2.18)
X
j
X
k
1− j·slk j ·Zk js +X
j
ι·Xjs =IS ecy
s,s∈[S] (2.19)
X
j
pj·Xjs +X
k
s k j ·Zk js
=Ns,s∈[S] (2.20)
(1−ι)·X
s∈[S ]
Xjs +IG+
j, −1−IG−
j, −1−Dj =IG+
j −IG−
j ,j∈[K], ∈[T] (2.21)
(1−ι)·X
s∈[Scyclec]
Xjs ≥IG−
j, 1c−1,j∈[K],c∈[C−] (2.22)
Xjs ≤Mj·Yjs,j∈[K],s∈[S] (2.23)
2.A. In eg a ed P&P ma hema ical o mula ion 37
Xjs ≥mj·Yjs −Yj,s−1,j∈[K],s∈[S] (2.24)
X
j
Yjs ≤1,s∈[S] (2.25)
Yj1,s1c=1,c∈[C+] (2.26)
X
k
Zjks =Yj,s−1,j∈[K],s∈[S] (2.27)
X
k
Zk js =Yjs,j∈[K],s∈[S] (2.28)
Cons ain s (2.17) and (2.18) keep ack o he usage o i gin and ecycled pulp, e-
spec i ely, du ing p oduc ion and se up asks in each subpe iod (whe e wa e is added o
i ). In he P&P mill, he amoun o pape los du ing g ade swi cho e s and eels cu ing is
ed back in o he ecycled pulp mill and is aced by cons ain s (2.19).
I should be emembe ed ha he e is a common ime g id o all p oduc ion esou ces.
Cons ain s (2.20) de ine he size o each mic o-pe iod as a unc ion o he p oduc ion
and se up imes o he pape machine pe o med in ha subpe iod. These equi emen s,
oge he wi h (2.6), synch onize he ime g id o he diges e wi h ha o he pape machine
in each subpe iod.
Cons ain s (2.21) ep esen he balance o in en o y o pape g ade jin pe iod . The
ini ial in en o y o each g ade is null IG+
j,0=0∀j. The e m (1−ι)·Ps∈[S ]Xjs deduc s he
im loss ou o he o e all quan i y p oduced. Cons ain s (2.22) ensu e ha in each cycle,
he ini ial backlog o each g ade is ul illed un il he end o ha cycle.
Cons ain s (2.23) es ablish ha p oduc ion o g ade joccu s in subpe iod si he
machine is se up o ha g ade in subpe iod s. In ha case, cons ain s (2.24) o ce a
minimum lo size o he whole un. F om (2.25) a mos one g ade can be p oduced pe
subpe iod. Cons ain s (2.26) impose ha he i s g ade o each cycle is always he same
and hus, hey c ea e he pe cep ion o cycles (which is impo an o planne s). Finally,
cons ain s (2.27) and (2.28) ela e he changeo e a iables o he se up s a e a iables.
38 Chap e 2. Solu ion app oach o p oduc ion planning and scheduling
2.A.3 Reco e y plan
Pa ame e s:
Iliquo
0Ini ial in en o y o weak black liquo (in m3)
Iliquo
max Iliquo
min Maximum (minimum) in en o y o weak black liquo in he bu e (in m3)
Ce ap Capaci y o he e apo a o o p ocess he black liquo (in m3pe hou )
ρRa io be ween diges e ’s pulp and weak black liquo p oduc ion
βCon e sion pa ame e om weak black liquo o concen a ed black liquo
Ic.liq
0Ini ial in en o y o concen a ed black liquo (in m3)
Ic.liq
max Ic.liq
min Maximum (minimum) holding s ock o concen a ed black liquo in he bu e (in m3)
C .boile
s eam Capaci y o he eco e y boile o p oduce s eam (in onnes pe hou )
σCon e sion ac o o concen a ed black liquo o s eam
C .boile
bu n Bu ning capaci y o he eco e y boile (in m3pe hou )
Decision a iables:
Xliquo
sQuan i y o weak black liquo p oduced by he diges e in subpe iod s(in m3)
Oliquo
sQuan i y o weak black liquo e apo a ed in subpe iod sby he e apo a o (in m3)
Iliquo
sIn en o y o weak black liquo a he end o subpe iod s(in m3)
Xc.liq
sQuan i y o concen a ed black liquo p oduced in subpe iod s(in m3)
Ic.liq
sIn en o y o concen a ed black liquo a he end o subpe iod s(in m3)
Oc.liq
sQuan i y o concen a ed black liquo o be bu n (in m3)
Xs eam
sQuan i y o s eam p oduced in he eco e y boile (in onnes)
Xliquo
s=ρ·Xdig
s,s∈[S] (2.29)
Xliquo
s+Iliquo
s−1=Oliquo
s+Iliquo
s,s∈[S] (2.30)
Iliquo
min ≤Iliquo
s≤Iliquo
max ,s∈[S] (2.31)
Oliquo
s≤Ce ap ·Ns,s∈[S] (2.32)
Xc.liq
s=β·Oliquo
s,s∈[S] (2.33)
Xc.liq
s+Ic.liq
s−1=Oc.liq
s+Ic.liq
s,s∈[S] (2.34)
Ic.liq
min ≤Ic.liq
s≤Ic.liq
max ,s∈[S] (2.35)
Oc.liq
s≤C .boile
bu n ·Ns,s∈[S] (2.36)
Xs eam
s=σ·Oc.liq
s,s∈[S] (2.37)
Xs eam
s≤C .boile
s eam ·Ns,s∈[S] (2.38)
The amoun o weak black liquo , Xliquo
s, exp essed in m3, is p opo ional o he di-
ges e ’s i gin pulp ou pu , and is gi en by cons ain s (2.29). The bu e be ween he
diges e and he e apo a o is cons ained by lowe and uppe bounds (cons ain s (2.31)).
Cons ain s (2.32) es ablish he e apo a o ’s capaci y and he in en o y balance equa ions
on he weak black liquo a e gi en by (2.30). The ou pu o he e apo a ion p ocess is
he concen a ed black liquo , Xc.liq
s ha is p opo ional o he inpu Oliquo
s, as gi en by
cons ain s (2.33).
The mass balance equa ions o he concen a ed black liquo ank a e gi en by con-
s ain s (2.34), while he s o age capaci y o he bu e is de ined by (2.35). Cons ain s
2.A. In eg a ed P&P ma hema ical o mula ion 39
(2.36) ensu e ha he bu ning capaci y is limi ed in each subpe iod. Finally, he s eam
gene a ed by he eco e y boile is p opo ional o he amoun o d y solid con en ha is
bu n a each ime, as indica ed in (2.37). The s eam ou pu canno exceed an uppe limi –
see cons ain s (2.38).
2.A.4 Objec i e unc ion and o e all model
Ob j =X
j
X
λ1·IG+
j +X
j
X
λ2·IG−
j +X
j
X
k
X
s
λ3·slk j ·Zk js −X
s
λ4·Xs eam
s
−X
s
λ5·Oliquo
s−X
s
λ6·X ecy
s−X
s
λ7·Xdig
s
(2.39)
Exp ession (2.39) ep esen s he weigh ed sum o he objec i e unc ion. I s coe i-
cien s (λi’s) we e de e mined based on he p e e ences o he decision-make . To make
his p ocess easie , he ollowing exp ession was used: Piwi·Fi/Fmax
i, whe e wi’s a e
he weigh s o be pa ame ized, Fi’s a e he sub- unc ions and Fmax
i’s a e he maximum
alues hese unc ions can ake. The e o e, he sub- unc ions a e no malized and hence,
easie o be weigh ed. The weigh s o be applied o he ou pu low a iables ( he las
ou e ms) should inc ease as we go downs eam he p oduc ion p ocess, so ha s ages
close o he o e all mill’s ou pu a e no hinde ed by ups eam s ages. The e o e, a ac-
o o 2 was applied be ween he weigh s o wo consecu i e s ages and hence, we ha e:
w4=2·w5=4·w6=4·w7. The alues o he λi’s can be de e mined by di iding he
co esponding wi’s by he Fmax
i’s.
The o e all model hen eads:
min Ob j
subjec o (2.3)–(2.38),
Ns,Nh s,Xdig
s,X ecy
s,I i g
s,I ecy
s,O i g
s,O ecy
s,IS ecy
s,Xjs,IG+
j, ,IG−
j, ,Xliquo
s,Oliquo
s,
Iliquo
s,Xc.liq
s,Ic.liq
s,Oc.liq
s,Xs eam
s≥0,
Ydig
s ,Zk js,Yjs ∈ {0,1}.
Chap e 3
Decision suppo sys em o
p oduc ion planning and scheduling
A decision suppo sys em o he ope a ional p o-
duc ion planning and scheduling o an in eg a ed pulp
and pape mill
Gonçalo Figuei a∗·Ped o Amo im∗·Luís Guima ães∗·Má io Amo im Lopes∗
·Be na do Almada-Lobo∗
Submi ed o Compu e s &Chemical Enginee ing, 2014
Abs ac P oduc ion planning and scheduling in he p ocess indus y in gene al and in
he pulp and pape (P&P) sec o in pa icula can be e y challenging. Mos p ac i ione s,
howe e , add ess hose ac i i ies elying only on sp eadshee s, which is ime-consuming
and sub-op imal. The li e a u e has epo ed some decision suppo sys ems (DSSs) ha
a e a om he s a e-o - he-a wi h espec o op imiza ion models and me hods, and se -
e al esea ch wo ks ha do no add ess indus ial issues. We con ibu e o educe ha
gap by de eloping and desc ibing a DSS ha esul ed om se e al i e a ions wi h a P&P
company and a ho ough e iew o he p ocess sys ems enginee ing li e a u e. The DSS
inco po a es ele an indus ial ea u es (which mo i a ed he de elopmen o a speci ic
model), exhibi s impo an echnical de ails (such as he connec ion o exis ing sys ems
and use - iendly in e aces) and shows how op imiza ion can be in eg a ed in eal wo ld
applica ions, enhanced by key p e- and pos -op imiza ion p ocedu es.
Keywo ds Decision Suppo Sys em ·Lo -sizing and Scheduling ·MIP-based heu is ics
·Pulp and Pape Indus y ·Con inuous P oduc ion
3.1. In oduc ion
The pulp and pape (P&P) indus y is highly capi al in ensi e, which means ha in es -
men s in capaci y can ep esen e y long- e m decisions. Fo ins ance, he modi ica ion
o a single pape machine equi es a planning ho izon o a leas i e yea s (Ma el e al.,
∗INESC TEC, Faculdade de Engenha ia, Uni e sidade do Po o, Po o, Po ugal
42 Chap e 3. Decision suppo sys em o p oduc ion planning and scheduling
2005). Pape p oduc s a e commodi ies, wi h hei p ice de e mined in he ma ke and cha -
ac e ized by small ma gins. Hence, companies mus di e en ia e hemsel es by imp o ing
cus ome sa is ac ion indica o s, while keeping p oduc ion cos s as low as possible. Fu -
he mo e, he P&P p oduc ion p ocess is also ene gy in ensi e. P oducing one onne o
pape equi es 5–17 GJ o p ocess hea , depending on he pape ype and on he echnology
applied (Szabó e al.,2009). The P&P indus y uses 84% o he uel ene gy consumed by
he o es p oduc s indus y as a whole and i is one o he la ges p oduce s o g eenhouse
gas (GHG) emissions. The e o e, i is o pa icula in e es in he con ex o en i onmen al
discussions.
These h ee main ac o s (capi al in ensi y, ene gy in ensi y and compe i i e ma ke )
make he p oduc ion planning an essen ial ac i i y in he ques o imp o emen s in ope -
a ional e iciency and consequen ly economic gains. Howe e , he planning p ocess poses
a a ie y o challenges, bo h o p ac ical and scien i ic ields. I hese challenges a e suc-
cess ully add essed, companies can achie e ue compe i i e ad an age.
In mos cases, p oduc ion planning is add essed manually by p ac i ione s, e en in
mode n mills wi h sophis ica ed au oma ed sys ems. Tha applies no only o he P&P in-
dus y, bu o he p ocess indus y in gene al (see Ha junkoski e al. (2014)). Companies
may use ad anced ools o pa icula asks, such as he planning o he pape eels’ cu -
ing, bu when app oaching he o e all planning ac i i y (e.g. size and sequence o pape
campaigns, p oduc ion a es, e c.) mos p ac i ione s ely only on sp eadshee s. This man-
ual p ocess is ime-consuming, sub-op imal (as only ew al e na i es a e conside ed) and
comple ely dependen on he planne s’ expe ise.
The e o e, he e is hus he need o op imiza ion-based ools ha suppo decision
making in he ope a ional p oduc ion planning o hese mills. Some decision suppo sys-
ems (DSS) o his pa icula indus y we e epo ed in he li e a u e (e.g. Mu hy e al.
(1999); Respício and Cap i o (2008)). Al hough conside ing ele an indus ial ea u es
and p ac ical issues, he unde lying app oaches a e a om he s a e-o - he-a in p oduc-
ion planning. On he o he hand, mo e esea ch-o ien ed wo ks do no add ess he issues
o an indus ial implemen a ion.
Ou wo k helps closing he gap be ween esea ch and p ac ice, p oposing an op imiza ion-
based DSS, which imp o es on manual planning and con ibu es o he li e a u e in he
ollowing ways:
•explo ing desi able cha ac e is ics o analy ical models and me hods;
•iden i ying ele an indus ial ea u es and how hey should be included in he solu-
ion app oach;
•ex ending models o he li e a u e, conside ing p ac ical cons ain s and objec i es;
•exhibi ing impo an da a p ocessing in bo h p e- and pos -op imiza ion phases;
•illus a ing equi ed connec ions o exis ing sys ems and desi able aspec s in he use
in e ace.
We s a by desc ibing he indus ial sys em and he planning challenge in Sec ion 3.2.
This mo i a es he discussion in Sec ion 5.6.1 on he di e en app oaches in he li e a u e
3.2. The challenge 43
o he ope a ional p oduc ion planning. In ha sec ion we explo e some desi able cha ac-
e is ics o op imiza ion models and iden i y ele an ea u es o indus ial p ac ice. Based
on ha , we choose an app op ia e ma hema ical model and ex end i in o de o include he
iden i ied p ac ical issues. Ou o mula ion is p esen ed in Sec ion 3.4. Sec ion 5.4 mo i-
a es and explo es he solu ion me hod o an e icien ye simple and lexible esolu ion o
his complex p oblem. Sec ion 3.6 de ails he in eg a ion o he op imiza ion in he deci-
sion suppo sys em, desc ibing p e- and pos -op imiza ion s eps, as well as he in e aces
o he exis ing in o ma ion sys ems and o he inal use . The usage o he sys em is also
discussed. In Sec ion 5.7 we compa e a plan ob ained wi h he sys em o one manually
gene a ed by p oduc ion planne s and gi e u he de ails o he pe o mance and usage o
he sys em by he company. Finally, he las sec ion summa izes he bene i s o ou DSS,
discusses i s applicabili y o o he en i onmen s and shows possible di ec ions o u he
imp o emen .
3.2. The challenge
The P&P p oduc ion p ocess is illus a ed in Figu e 5.1. The a iables depic ed in his
Figu e will be in oduced la e in Sec ion 3.4. In a i s s ep, bo h i gin and ecycled
pulps a e p oduced ou o wood and ecycled pape , espec i ely. These pulps a e hen
s o ed in anks, wai ing o being pulled by he pape machine. The machine can p oduce
di e en ypes o pape . Each ype (o g ade) is cha ac e ized by i s g ammage (measu ed
in g/m2) and pulp mix u e. The con igu a ion o he machine o p oduce a di e en g ade is
sequence-dependen . Each se up leads o a loss in he p oduc ion p ocess in e ms o ime
and quan i y o a lowe quali y pape p oduced (as he machine is ne e idle and he pape
p oduced will no be homogeneous no sa is y comple ely he cus ome equi emen s). The
was ed pape (se up loss) is ed again in o he ecycled pulp mill and a loss pulp ank.
The mas e eel ha esul s a he end o he pape machine, he jumbo, is cu in o
smalle eels. The was ed pape in he cu ing s age ( im loss) is also ed back o he
p oduc ion p ocess. Cus ome s place o de s o eels o di e en wid hs and g ades. The
o de s may ha e di e en p io i y le els. The maximum p io i y is gi en o hose ha a el
by ship, since he company has o schedule con aine s in ad ance and commi o a gi en
due da e. Then, he emaining is di ided in o no mal and p io i y o de s.
In pa allel, a by-p oduc o he diges e ’s pulping p ocess, he weak black liquo , is
concen a ed and bu n o p o ide high-p essu e s eam and egene a e he spen chemicals
applied in he pulping s age. The s eam can ei he be used o he pape d ying p ocess o
be led o coun e -p essu e u bines which p oduce elec ical ene gy o be sold a e wa ds.
In o he companies, he pape mill can be physically dis an om he pulp and eco -
e y plan s. Howe e , in eg a ed plan s, like ou case s udy, ep esen 65% o he indus y
(CEPI,2013) and a e mo e capable o achie ing high le els o bo h ene gy and economic
e iciency, due o:
•ene gy conse a ion (e.g. di ec use o s eam in he pape d ying p ocess);
•absence o addi ional p ocesses (e.g. pulp d ying);
50 Chap e 3. Decision suppo sys em o p oduc ion planning and scheduling
ime o each campaign is limi ed o he espec i e bucke – see (3.3)–(3.5). When hese
cons ain s a e ac i e (Yjs =1), clea ly Us a
js =Ss a
sand Uend
js =Send
s.
Recall ha he p oduc ion esou ces ha e he slo s independen o he ime pe iod’s
bounda ies. Now, he in e sec ion be ween slo s and ime pe iods is assu ed by a iables
E. Na u ally, he i s slo akes place in ime pe iod one (E11 =1) and he las in he las
pe iod (ETS =1).
slo smax ·T·(1−E s)≥
−1
X
0=1
S
X
s0=s+1
E 0s0, ∈[T] {1},s∈[S] {S}(3.6)
E −1,s+E +1,s≤E s +1, ∈[T] {1,T},s∈[S] (3.7)
The p ope assignmen o slo s o ime pe iods is es ablished by (3.6). Gi en ha a slo s
is assigned o pe iod , a subsequen slo can no be assigned o any p eceden ime pe iod,
which gua an ees he o de co ec ness o he slo s. In case he slo spans om pe iod −1
o pe iod +1, hen (3.7) ensu es ha pe iod is also c ossed by he same slo .
3.4.2 P oduc ion sys em
He e we ocus on he pulp plan and pape mill o he P&P manu ac u ing sys em ( ecall
Figu e 5.1).
Pa ame e s
Vdig
min Vdig
maxMinimum (maximum) a e o he diges e (in pm)
αcon e sion ac o o diges e ’s h oughpu ( om pm o onnes
pe hou )
I i g
min I i g
maxMinimum (maximum) le el o i gin pulp s ocked in he anks (in
onnes)
jPe cen age o wa e in pape g ade j
ljA e age im loss (in pe cen age)
b i g
jPe cen age o i gin pulp used in he p oduc ion o pape g ade j
b i g
loss Pe cen age o i gin pulp in he loss pulp
slk j Pape los in a changeo e om g ade k o j(in onnes)
s k j Time los in a changeo e om g ade k o j(in onnes)
pmin
jminimum ime (a machine’s maximum a e) o p oduce one
onne o pape g ade j(in hou s)
pmax
jmaximum ime (a machine’s minimum a e) o p oduce one
onne o pape g ade j(in hou s)
Decision a iables
X i g
sP oduc ion o i gin pulp in slo s(in onnes)
O i g
sAmoun o i gin pulp ed in o he pape machine in slo s(in
onnes)
I i g
sIn en o y o i gin pulp a he end o slo s(in onnes)
3.4. Ma hema ical model 51
Xloss
sP oduc ion o loss pulp in slo s(in onnes)
Oloss
sAmoun o loss pulp used in slo s(in onnes)
Xj s P oduc ion o pape g ade jin pe iod and slo s(in onnes)
Zk js
1 i a changeo e om g ade k o joccu s a he beginning o slo s
0 o he wise
In wha conce ns he pulp p oduc ion, he amoun o i gin pulp p oduced by he di-
ges e in each slo is bounded by i s speed limi s, acco ding o (3.8). P oduced pulp is
s ocked in anks and hen ed in o he pape machine (3.9). In (3.10), his s ock is also lim-
i ed o lowe and uppe bounds. The eade is e e ed o San os and Almada-Lobo (2012)
o a ho ough analysis o he cons ain s o hese wo a eas.
α·Vdig
min ·Ns≤X i g
s≤α·Vdig
max ·Ns,s∈[S] (3.8)
X i g
s+I i g
s−1=O i g
s+I i g
s,s∈[S] (3.9)
I i g
min ≤I i g
s≤I i g
max,s∈[S] (3.10)
The equi emen s o he ecycled pulp and eco e y plan a e simila o hose ha ap-
pea in he i gin pulp plan , and he e o e will no be p esen ed he e (such as he minimum
and maximum p oduc ion o ecycled pulp, liquo s and s eam, he in en o y balance o e-
cycled and loss pulps and liquo s, and he in en o y limi s o ecycled and loss pulps and
liquo s).
X
j
Yjs =1,s∈[S] (3.11)
X
k
Zjks =Yj,s−1,j∈[K],s∈[S] (3.12)
X
k
Zk js =Yjs,j∈[K],s∈[S] (3.13)
Xj s ≤cap ·Yjs,j∈[K], ∈[T],s∈[S] (3.14)
pmin
j·Xj s ≤cap ·E s,j∈[K], ∈[T],s∈[S] (3.15)
X
j
b i g
j·1− j·
X
Xj s +X
k
slk j ·Zk js
=O i g
s+b i g
loss ·Oloss
s,s∈[S] (3.16)
Xloss
s=X
j
X
k
1− j·slk j ·Zk js +X
j
X
1− j· lj·Xj s,s∈[S] (3.17)
X
pmin
j·Xj s +X
k
s k j ·Zk js ≤Uend
js −Us a
js ,j∈[K],s∈[S] (3.18)
X
pmax
j·Xj s +X
k
s k j ·Zk js ≥Uend
js −Us a
js ,j∈[K],s∈[S] (3.19)
Rega ding he pape p oduc ion, om (3.11) a mos one g ade can be p oduced pe slo .
52 Chap e 3. Decision suppo sys em o p oduc ion planning and scheduling
Cons ain s (3.12) and (3.13) link he g ade changeo e a iables o he se up s a e a iables
on he pape machine. A g ade jis only p oduced in a gi en bucke in case he machine
has been app op ia ely se up o (3.14). Na u ally, a iable Xj s only akes posi i e alues
in case slo sc osses pe iod , as ensu ed by equa ions (3.15). No e ha he p oduc ion
quan i y (Xj s) is desc ibed pe pe iod, i.e., he po ion o he slo s ha c osses pe iod is
aken in o accoun o de ine he quan i y ha mee s he demand o ha pe iod. The i gin
pulp used by he pape machine, de ined in (3.16, comes om he i gin pulp s o ed in
anks oge he wi h (pa o ) he pulp ha is eco e ed om he p oduc ion losses due o
he g ade se up changeo e s and im sub-p ocess – which a e compu ed in (3.17).
Finally, acco ding o (3.18)-(3.19) he ime con ined o he se up and p oduc ion ope -
a ions o each g ade on he pape machine in each slo is gi en by he leng h o he slo ,
whe e he machine ope a es wi hin i s minimum and maximum speed limi s. No e ha in
case g ade jis no assigned o slo s, om (3.3), Uend
js =Us a
js and he e o e no ope a ions
ake place. The de ini ion o he consump ion o ecycled pulp is also modeled in a way
simila o he consump ion o he i gin pulp p esen ed be o e, and i is no p esen ed he e.
3.4.3 Demand ul ilmen
Demand is ul illed a he end o he disc e e pe iods. The ollowing equa ions look a he
in e sec ion o he con inuous p oduc ion slo s wi h hose disc e e pe iods.
Pa ame e s
dj Demand o pape g ade jin pe iod (in onnes)
Ij0Ini ial in en o y o pape g ade j(in onnes)
IBj0Ini ial backlog o pape g ade j(in onnes)
Decision a iables
Ws a
j s S a ing ime o slo s o g ade jin pe iod
Wend
j s Ending ime o slo s o g ade jin pe iod
Ij In en o y o pape g ade ja he end o pe iod (in onnes)
IBj Backlog o pape g ade ja he end o pe iod (in onnes)
pmin
j·Xj s ≤Wend
j s −Ws a
j s ,j∈[K], ∈[T],s∈[S] (3.20)
pmax
j·Xj s ≥Wend
j s −Ws a
j s ,j∈[K], ∈[T],s∈[S] (3.21)
Wend
j s ≤min ·cap;Uend
js +hcap ·(1−E s),j∈[K], ∈[T],s∈[S] (3.22)
Ws a
j s ≥max
( −1)·cap;Us a
js +X
k
s k j ·Zk js −hcap ·(1−E s)
,j∈[K], ∈[T],s∈[S]
(3.23)
X
Wend
j s −Ws a
j s +X
k
s k j ·Zk js =Uend
js −Us a
js ,j∈[K],s∈[S] (3.24)
X
s1− lj·Xj s +Ij, −1−IBj, −1=dj +Ij −IBj ,j∈[K], ∈[T] (3.25)
3.4. Ma hema ical model 53
+ 1 - 1
𝑎 𝑊
𝑗𝑡𝑠
𝑠𝑡𝑎𝑟𝑡 = 𝑡 − 1 ∙ 𝑐𝑎𝑝 ; 𝑊
𝑗𝑡𝑠
𝑒𝑛𝑑 = 𝑡 ∙ 𝑐𝑎𝑝
𝑐 𝑊
𝑗𝑡𝑠
𝑠𝑡𝑎𝑟𝑡 = 𝑡 − 1 ∙ 𝑐𝑎𝑝 ; 𝑊
𝑗𝑡𝑠
𝑒𝑛𝑑 = 𝑈
𝑗𝑠
𝑒𝑛𝑑
𝑏 𝑊
𝑗𝑡𝑠
𝑠𝑡𝑎𝑟𝑡 = 𝑈
𝑗𝑠
𝑠𝑡𝑎𝑟𝑡 + 𝑠𝑒𝑡𝑢𝑝; 𝑊
𝑗𝑡𝑠
𝑒𝑛𝑑 = 𝑡 ∙ 𝑐𝑎𝑝
𝑑 𝑊
𝑗𝑡𝑠
𝑠𝑡𝑎𝑟𝑡 = 𝑈
𝑗𝑠
𝑠𝑡𝑎𝑟𝑡 + 𝑠𝑒𝑡𝑢𝑝; 𝑊
𝑗𝑡𝑠
𝑒𝑛𝑑 = 𝑈
𝑗𝑠
𝑒𝑛𝑑
se up = 𝑘𝑠𝑡𝑘𝑗 ∙ 𝑍𝑘𝑗𝑠
𝑊
𝑗𝑡𝑠
𝑠𝑡𝑎𝑟𝑡
𝑊
𝑗𝑡𝑠
𝑒𝑛𝑑
𝑈
𝑗𝑠
𝑠𝑡𝑎𝑟𝑡
Figu e 3.5: P oduc ion window o a slo de ini ion in each ime pe iod.
Va iables Ws a
j s and Wend
j s de ine he espec i e p oduc ion windows, which in u n limi
he p oduc ion amoun s (Xj s) – see equi emen s (3.20)–(3.21). These a iables a e uppe
bounded by (3.22) and lowe bounded by (3.23). Figu e 3.5 p o ides some examples o
explain how hese cons ain s wo k and o show di e en p oduc ion windows de ini ions.
In case 3.5(a), he slo c oss en i ely pe iod , and he e o e he p oduc ion window bounds
in pe iod ma ch ha pe iod’s bounda ies. In case he slo ends in he middle o ime pe iod
, cases 3.5(c) and (d), he ending da e o he p oduc ion window is he same o he ending
ime o he slo . No e ha he p oduc ion window is con ained wi hin he slo , as i disca ds
he se up ime. In case slo sdoes no in e sec pe iod (i.e. Es =0), equi emen s (3.22)
and (3.23) a e non-ac i e. The ela ion be ween he p oduc ion window o g ade jin slo s
and he slo leng h is es ablished in (3.24) – he slo con ains he p oduc ion window and he
se up imes consumed in a g ade changeo e . Then, he ul ilmen o demand is ob ained
by (3.25), which allows backlogging o de s o be me in la e pe iods.
3.4.4 Objec i e unc ion
Gi en ha on he one hand he sys em wo ks wi h an MTO policy and on he o he hand
he plan ope a es con inuously on a 24/7 basis (no idle o ex a imes), o de s may backlog
a some poin s in ime. The goal o he ope a ional p oduc ion planning and scheduling
is hen o minimize ha backlog a he minimum possible cos . Ope a ional cos s include
g ade se up, p oduc ion and holding cos s. P oduc ion cos s a e mainly ela ed o dilu ing
he cos s o he capi al in ensi e equipmen , which is achie ed by maximizing i s u iliza ion
(some imes p oducing beyond ixed o de s). The se up cos s, which a e sequence depen-
den , conce n no only he ime and p oduc los in ha p ocess, bu also he wea impu ed
o equipmen . Equa ion (5.17) ep esen s a cos unc ion ha agg ega es hese main objec-
i es.
54 Chap e 3. Decision suppo sys em o p oduc ion planning and scheduling
Pa ame e s
bc Cos o backlogging one onne o pape pe pe iod
hc Cos o holding one onne o pape in s ock pe pe iod
sck j Se up cos o changing om g ade j o k
po Bene i (nega i e cos ) o p oducing pape
minX
j
X
bc ·IBj +X
j
X
hc ·Ij +X
j
X
k
X
s
sck j ·Zk js −X
j
X
X
s
po ·Xj s
(3.26)
O he objec i es a e conside ed in he comple e model. The d i e o he P&P com-
pany is no only o p oduce pape , bu also o gene a e and sell ene gy based on he s eam
p oduced (which is somehow p opo ional o he h oughpu o he diges e ). The e o e,
any plan also aims a maximizing he p oduc ion o s eam. Fu he e ms o his objec i e
unc ion a e e ealed in Subsec ion 3.4.6, whe e some p ac ical issues a e add essed.
3.4.5 Valid inequali ies
A ew se s o alid inequali ies a e he eby in oduced o s eng hen he a o emen ioned
ma hema ical o mula ion.
X
s
E s ≥1, ∈[T] (3.27)
X
E s ≥1,s∈[S] (3.28)
X
s
E s ≤slo smax, ∈[T] {T}(3.29)
Zj js ≤1−Zjku,j,k∈[K] : k,j,s,u∈[S] : u>s(3.30)
Zj js ≤ET s,j∈[K],s∈[S] (3.31)
Each ime pe iod is in e sec ed by a leas one slo , as poin ed ou by (3.27). Clea ly,
each slo has o be assigned o a leas one ime pe iod (3.28). The maximum numbe o
slo s pe pe iod is ein o ced by (3.29). Two consecu i e non-emp y slo s p oduce di e en
g ades. In case he e is no need o use all he p e-de ined slo s, he null slo s should be
placed a he end o he ho izon. Requi emen s (3.30) and (3.31) o ce he he phan om
g ade changeo e s (Zj js) o be mo ed o he end.
3.4.6 P ac ical cons ain s
In o de o be used in p ac ice, he model p esen ed abo e needs o inco po a e eal-wo ld
ex ensions. Some o he new ea u es a e ela ed o cus ome s o maximize hei sa is ac-
ion, o he ha e o do wi h he hu dles o managing he esou ces in he smoo hes way
3.4. Ma hema ical model 55
possible.
3.4.6.1 Sales equi emen s
To conside di e en ypes o o de s wi h di e en p io i y le els i is necessa y o disag-
g ega e p oduc ion, in en o y and backlog a iables. In ha way i is possible o in oduce
di e en penal ies o backlogging speci ic o de s. The su ixno m o he new a iables
e e s o he no mal p io i y le el, whe eas ship o ship o de s and p io o he highes p i-
o i y o de s. Gi en ha mul iple ships can be scheduled wi hin he planning ho izon, an
index m∈[M] is in oduced o hem. Fo ins ance, a iable Xship
j m deno es he amoun o
g ade jp oduced in pe iod o be dis ibu ed in ship m. The la es p oduc ion ime o an
o de o mee he depa u e o ship mis gi en by ddm.
Ij0=Ino m
j0+Ip io
j0+X
m
Iship
jm ,j∈[K] (3.32)
X
s1− lj·Xj s =Xno m
j +Xp io
j +X
m
Xship
j m ,j∈[K], ∈[T] (3.33)
ddm
X
=1
Xship
j m +Iship
jm −IBship,ini
jm =dship
jm −IBship
jm ,j∈[K],m∈[M] (3.34)
Ino m
jT −IBno m
jT =dno m
j,T+1+Ino m
j,T+1−IBno m
j,T+1,j∈[K] (3.35)
The disagg ega ion o he ini ial in en o y is pe o med by (3.32), whe e i is allo-
ca ed o no mal, p io i y o ship o de s ( he h ee p io i y le els desc ibed in Sec ion 3.2).
Cons ain s (3.33) disagg ega e p oduc ion. No e howe e ha he e is also agg ega ion,
ega ding he di e en slo s ha c oss he pe iod, since a his poin we jus need o know
he comple ed amoun s a he end o each pe iod.
The demand ul ilmen equa ions o no mal and p io i y o de s a e simila o con-
s ain s (3.25), hence hey a e no de ailed he e. On he o he hand, o ships hey a e
sligh ly di e en – see (3.34). Indeed, each ship mhas a single due da e (ddm). Thus, de-
mand ul ilmen is no checked in each pe iod, bu only in he ship’s due da e. The e o e,
p oduc ion is summed om he i s pe iod un il he due da e and no in en o y is le a e
ha since he e is no o he chance o ul il ha demand.
Finally, in (3.35) he ul ilmen o demand beyond he planning ho izon is e i ied.
Gi en ha he machine is ne e idle and pape is no made o s ock, i all he demand
wi hin he ho izon has been me , u u e demand should be conside ed. All his demand
is hen agg ega ed in an addi ional e m co esponding o pe iod T+1. Na u ally, no
ul illing his demand will ha e a lowe penal y in he objec i e unc ion.
3.4.6.2 Pape campaigns
He e, we desc ibe some cons ain s ela ed o ope a ional issues in execu ing pape cam-
paigns. Pa ame e s Nmin and Nmax de ine he lowe and uppe bounds o he leng h (in
ime uni s) o each g ade campaign, espec i ely. Fu he mo e, LVLB
min e e s o he minimum
56 Chap e 3. Decision suppo sys em o p oduc ion planning and scheduling
p oduc ion amoun o each VLB- ype campaign, |KVLB| o he numbe o VLB g ades, and
dis min o he minimum dis ance be ween campaigns o he same g ade.
Zjks =0,s∈[S],j∈[K],k∈hKna
ji(3.36)
Ns≤Nmax ·X
k
X
j,k
Zk js,s∈[S] (3.37)
Ns≥Nmin −Nmax ·X
j
Zj js,s∈[S] (3.38)
1− lj·X
Xj s ≥Lmin ·Yjs −Zj js,j∈[K],s∈[S] (3.39)
X
j∈[KVLB]X
s+|KVLB|−1
X
s0=s
Xj s0≥LVLB
min ·X
k<[KVLB]
X
j∈[KVLB]
Zk js,j∈[K],s∈[S] : s≤S− |KVLB|+1
(3.40)
s+dis min
X
s0=s
Yjs0−Zj js0≤1+ ioldis ,j∈[K],s∈[S] : s≤S−dis min (3.41)
The i s cons ain s ega d sequences ha canno be execu ed. In ou case, quali y “A”
g ades should no be p oduced a e basic ones. Indeed, i hey do no mee he equi ed
quali y le el, bu he e is a basic quali y campaign ollowing, hey can s ill be used as basic
quali y p oduc s and he “A” quali y has ano he oppo uni y o be p oduced. The e o e,
o each g ade j, he e is a lis o o bidden g ades [Kna
j], which co espond o he be e
quali y e sions (i any).
Cons ain s (3.37) and (3.38) de ine maximum and minimum leng hs o campaigns,
which should be espec ed o he sake o plan ’s s abili y. No e ha o all ic i ious
changeo e s (Zj js), he leng h is ze o. Minimums a e also de ined in e m o he amoun s
p oduced (Lmin and LVLB
min ) – see (3.39) and (3.40). The o me applies a minimum lo o
indi idual campaigns, whe eas he la e does ha o a se o campaigns o he same ype
(VLB g ades).
Finally, (3.41) o ces a minimum dis ance (dis min) be ween campaigns o he same
g ade. The iola ion o his so cons ain ( ioldis ) is penalized in he objec i e unc ion.
This issue is somehow a oided wi h se up cos s. Howe e , hese cons ain s p o ide a mo e
explici penaliza ion o p oducing he same g ade wice in a sho pe iod o ime. This ype
o cons ain s help be e ailo ing he plans o mee indus ial equi emen s, which would
o he wise need non-linea cos unc ions.
Figu e 3.6 p o ides an example o a plan ha does no comply wi h he ope a ional
cons ain s he e desc ibed. The co ec ed e sion o he plan is ha ep esen ed in Figu e
3.2. No e ha he i s pa is ixed, since hose campaigns we e al eady p og ammed in
he cu ing s age. The i s campaign, which seems no o comply wi h he minimum lo
size, is indeed in p og ess. The abo e cons ain s a e hus only applied a e he las ixed
campaigned.
3.4. Ma hema ical model 57
VLB165
VLB140
VLB115
KLB115
KLB125
KLB135
KLB135A
KLB170
KLB186
KLB200
KLB225
KLB270
KLB275
long campaign
small lo size
small join lo size
undesi able sequence
Fixed Schedule
Op imize Schedule
oo close
ime
g ades
pape campaign
Figu e 3.6: Example o a plan no ollowing he ope a ional equi emen s.
3.4.6.3 P oduc ion a es
The p oduc ion a es o all esou ces should be as smoo h as possible o a oid la ge ene gy
expendi u es and wea o he equipmen . He e we illus a e how he diges e ’s a es can be
smoo hed in he op imiza ion p ocess. Va iables Vdig
sin oduce he speed o he diges e in
slo s.
Vdig
s−Vdig
s−1=δdig+
s−δdig−
s,s∈[S] (3.42)
X i g
s=α·Vdig
s·Ns,s∈[S] (3.43)
The a es a ia ions a e assessed wi h equa ions (3.42). Minimizing he a iables δdig+
s
and δdig−
sin he objec i e unc ion will smoo h a es a ia ions. The o me a iable will
hen assess he a es’ inc ease, whe eas he la e will assess hei dec ease. These equa ions
equi e an explici a iable o he diges e ’s a e (Vdig
s), as opposed o he implici de ini ion
in cons ain s (3.8). Tha esul s in a non-linea o mula ion, since he a e a iable is
mul iplied by he slo ’s leng h – see (3.43). The e o e, in o de o a oid he complexi y
o he non-linea o mula ion, hese cons ain s a e only added in a pos -op imiza ion s ep
whe e he slo s a e ixed.
3.4.6.4 Recommended ank le els
In p ac ice, he s ock should no app oach he physical limi s o he ank, since i may
igge ope a ional di icul ies and would lea e he sys em mo e ulne able o dis u bances.
Fo hose easons, ecommended le els (below he capaci y uppe limi and abo e han he
lowe limi ) a e es ablished. The s ock may in some poin s in ime ange be ween he
desi able and physical limi s, bu he iola ion om he ecommend le els is penalized
in he objec i e unc ion. The s ock o i gin pulp in he ank in slo sis now gi en by
I i g
s+I i g, ec+
s−I i g, ec−
s, whe e a iables I i g, ec+
sdeno e he amoun o s ock abo e he
58 Chap e 3. Decision suppo sys em o p oduc ion planning and scheduling
ecommended uppe limi , and I i g, ec−
s he amoun o s ock below he ecommended lowe
limi . In addi ion, pa ame e I i g
slack−(I i g
slack+) e e s o he slack be ween he uppe (lowe )
ecommended le el and he uppe (lowe ) physical limi .
Equa ions (3.9)–(3.10) should hen be eplaced by he ollowing:
I i g
min +I i g
slack−≤I i g
s≤I i g
max −I i g
slack+,s∈[S] (3.44)
I i g
min ≤I i g
s+I i g, ec+
s−I i g, ec−
s≤I i g
max,s∈[S] (3.45)
X i g
s+I i g
s−1+I i g, ec+
s−1−I i g, ec−
s−1=O i g
s+I i g
s+I i g, ec+
s−I i g, ec−
s,s∈[S] (3.46)
Equa ions (3.44) o ce he egula a iable (I i g
s) o espec he ecommended le els,
while ex a le el a iables (I i g, ec+
sand I i g, ec−
s) a e included in he physical limi s e i i-
ca ion and ma e ial balance equa ions – cons ain s (3.45) and (3.46), espec i ely.
3.4.6.5 Fixed schedule
A c i ical ea u e o he model, and one o he mos impo an easons ha led o he choice
o CGLSP as he basic o mula ion, is he possibili y o ixing p oduc ion amoun s wi hou
he need o heu is ically de ine he numbe o slo s needed o each campaign. Indeed,
as slo s a e able o c oss pe iods, only one slo is equi ed pe campaign. The e o e, bo h
he sequence o campaigns and hei lo sizes can be easily ixed. The o me is a simple
assignmen (Yjs =1, o he espec i e g ade and slo ), while he la e is ep esen ed in
cons ain s (3.47). These cons ain s a e essen ial o eeze campaigns in he DSS ha ha e
al eady been p og ammed in he cu ing s age, i.e. ha e cu ing pa e ns op imized o
hem.
X
Xj s =X ix
s,s∈[S]<p odS,j∈[K] : Yjs =1 (3.47)
X ix
sis he amoun o be p oduced in slo sand p odS is he numbe o slo s wi h ixed
p oduc ion. This la e pa ame e has o be aken in o accoun in some o he cons ain s
p e iously p esen ed.
3.4.6.6 S oppages
Finally, in his las subsec ion we show he way s oppages we e modelled. These s oppages
can occu in di e en p oduc ion esou ces, such as he diges e and he pape machine. We
conside all he s oppages’ s a ing and ending imes as pa ame e s s ops a
and s ops a
,
whe e is he index o he s oppage. Then, we use bina y a iables Ps a
s and Pend
s o s a e
i s oppage s a s a he beginning o ends a he end o slo s.
3.5. Solu ion me hod 59
s ops a
−hcap ·1−Ps a
s ≤Ss a
s≤s ops a
+hcap ·1−Ps a
s , ∈[R],s∈[S]
(3.48)
s opend
−hcap ·1−Pend
s ≤Send
s≤s opend
+hcap ·1−Pend
s , ∈[R],s∈[S]
(3.49)
X
s
Ps a
s =1, ∈[R] (3.50)
X
s
Pend
s =1, ∈[R] (3.51)
s
X
s0=1
Ps a
s0≥
s
X
s0=1
Pend
s0, ∈[R],s∈[S] (3.52)
Cons ain s (3.48) and (3.49) align he s a ing and ending imes o slo s wi h he s a -
ing and ending imes o s oppages, espec i ely. Then, (3.50) and (3.51) ensu e ha only
one slo is aligned wi h he s a and/o he end o each s oppage. The las cons ain s o bid
he end o a s oppage o occu be o e i s s a .
Va iables Ps a
s and Pend
s a e hen used o cons ain he ou pu o he co esponding
esou ces. In he case o he diges e , o ins ance, equa ions (3.8) would include hese
a iables o enable o disable he maximum and minimum p oduc ion a es.
3.5. Solu ion me hod
The solu ion s a egy ollowed is based on a heu is ic solu ion o he p oblem’s ma hema -
ical o mula ion. The easons behind his choice come bo h om p ac ical implica ions
and algo i hmic aspec s. Fi s and o emos he la ge scale and complexi y o he model
desc ibed in he p e ious sec ion o a egula eal-wo ld ins ance p ohibi ed he use o a
comme cial sol e on he comple e model o mula ion gi en i s di icul y in e en inding a
easible solu ion in he ime limi imposed by he DSS usage. The model su e s om i s
compu a ional in ac abili y especially when he numbe o slo s de ined inc eases. Second,
heu is ics based on ma hema ical p og amming echniques, also known as ma heu is ics,
a e a powe ul amewo k o explo e he p oblem’s s uc u e and ake ad an age o oday’s
compu a ional and comme cial sol e s powe . Ma heu is ics ade-o he solu ion qual-
i y ob ained by sol ing he comple e model o mula ion in a comme cial sol e wi h he
solu ion sea ch e iciency o heu is ics and me a-heu is ics. Mo eo e , hese algo i hms
yield subs an ial ad an ages when compa ed o adi ional heu is ics, as hey equi e less
pa ame e s and consequen ly a much lowe e o in pa ame e unning, and can adap o
changes in he ma hema ical o mula ion wi h limi ed o ze o adjus men s. Ma heu is ics
o en p o ide quasi-op imal solu ions o a a ie y o p oblems and o he majo i y o
he companies ha ing a e y good solu ion is su icien as op imali y can ha e a ma ginal
imp o e o a high addi ional e o .
The ma heu is ic designed o he pu pose o gene a ing good quali y solu ions o his
66 Chap e 3. Decision suppo sys em o p oduc ion planning and scheduling
• eac i e scheduling – in he p esence o a dis u bance si ua ion which causes a se i-
ous dis up ion o he o iginal plan, eco e om ha dis u bance using an app op ia e
sequence o campaigns (some imes no ob ious o plan manage s);
•wha -i -analysis – suppo ing planning in hie a chically uppe le els by checking he
e ec i eness o p ac ical ules, expanding s o age and p oduc ion capaci ies, chang-
ing weigh s o di e en objec i es and scheduling main enance.
3.7. Resul s
In his sec ion we s a by looking a he usage o he sys em du ing a pe iod o ou mon hs
and hen del e in o one plan gene a ed by he sys em and i s di e ences o he manually
gene a ed coun e pa . In he end, a plan conside ing a long s oppage is analysed.
3.7.1 O e all esul s o he sys em’s usage
P oduc ion planne s and manage s a e no willing o wai mo e han 15 o 20 minu es
o an op imized plan in no mal condi ions. When acing an ope a ional issue, such as a
dis u bance, ha ime can be educed o 5 o 10 minu es. Wi h ha ime limi , s a e-o -
he-a sol e s like Cplex a e no e en able o ind a solu ion o a egula ins ance. The
ocus he e is hus much mo e on easibili y and imp o emen o e cu en p ac ice han
i is on op imali y. Fo ha eason, a conside able amoun o cons ain s a e elaxed (and
pu as so cons ain s) so ha ou cons uc i e heu is ic is always able o ind an ini ial
solu ion. Then, he MIP-based heu is ic imp o es ha solu ion o a poin ha i sa is ies
plan ’s manage s.
Ou sys em was made a ailable online o he company o use. Va ious i e a ions we e
pe o med wi h he use s in o de o ine une all he pa ame e s and in oduce addi ional
cons ain s o he ma hema ical model, such ha he esul ing plans mee hei equi e-
men s. Table 3.2 con ains in o ma ion abou 22 uns execu ed du ing ou mon hs a e
hose i e a ions. In spi e o he o al numbe o g ades being 29, he numbe o g ades wi h
demand o backlog o sa is y a each momen is educed o 16/17. This shows he impo -
ance o he p e-p ocessing s eps desc ibed in he p e ious sec ion. The maximum numbe
o campaigns (i.e. slo s) is se o 35 ( o an ho izon o 15 days) and he model can use hem
all o lea e some emp y. The ixed ( ozen) campaigns a e dependen on wha was al eady
scheduled in he cu ing s age and addi ional conside a ions manage s migh wan o ake.
The able epo s he imp o emen s achie ed o e he ini ial solu ion in uns execu ed
by he planne s. We can see ha hose alues a e highly a iable. Essen ially, hey will
depend on whe he he ini ial solu ion is al eady good o no , and on he ime limi gi en,
which is de ined by he use in e e y un. Ne e heless, an a e age imp o emen o 34%
was ob ained, wi h an a e age unning ime o 11 minu es, which shows he abili y o he
heu is ic in co ec ing and imp o ing p oduc ion plans in sho pe iods o ime.
To alida e he quali y o hose plans, hey need o be compa ed o hose manually
gene a ed by he company. In his ega d, he sys em can also help. Indeed, he sys em can
be used no only o op imize a plan om sc a ch, bu also o es ce ain schedules by ixing
3.7. Resul s 67
Table 3.2: Company’s usage o he sys em om June o Sep embe 2014.
# Da e G ades Fixed campaigns To al campaigns Imp o o e ini sol Time (min)
1 09/06/2014 17 4 35 75% 13
2 17/06/2014 17 7 34 81% 12
3 19/06/2014 17 9 28 26% 8
4 20/06/2014 17 8 33 51% 10
5 20/06/2014 17 20 27 5% 4
6 27/06/2014 17 10 30 29% 10
7 04/07/2014 17 14 28 0% 7
8 09/07/2014 16 7 35 4% 10
9 14/07/2014 16 3 31 1% 18
10 18/07/2014 17 4 35 45% 12
11 18/07/2014 17 27 28 3% 2
12 22/07/2014 17 9 32 8% 11
13 24/07/2014 17 4 30 6% 12
14 24/07/2014 17 7 31 7% 15
15 24/07/2014 17 13 29 63% 9
16 29/07/2014 17 5 30 87% 18
17 06/08/2014 17 5 30 93% 14
18 06/08/2014 16 5 32 46% 16
19 27/08/2014 17 9 33 55% 11
20 03/09/2014 17 7 29 6% 10
21 15/09/2014 16 6 31 18% 15
22 25/09/2014 17 9 29 48% 14
A g – 17 9 31 34% 11
he sequence and amoun s o pape campaigns. The able clea ly shows ha he company
has applied hese wo usages, compa ing he ou pu o bo h (e.g. uns 4 and 5, wi h a e y
di e en numbe o ixed campaigns - un 4 e e s o he op imum plan and un 5 o he
so-called manual solu ion). When ixing mos campaigns, he algo i hm is na u ally much
as e o inish. Howe e , ha should no be a eason o no le ing he sys em op imize he
plans, since jus p o iding he ini ial sequence gua an ees a good solu ion in a ew minu es,
in case he sequence is good, and gi es he oppo uni y o imp o e on ha solu ion.
The plan o un 4 ( aking ull ad an age o he DSS) ou pe o ms ha o un 5 (manual
plan) by 59% o he op imized. Rega ding uns 10 (op imized one) and 11 (manual), ha
imp o emen was o 71%. These alues a e un easonably high since some so cons ain s
we e iola ed in he company’s plans, whe eas ou sys em has add essed hem. A mo e
insigh ul compa ison is pe o med in he nex subsec ion, whe e we look a he schedules
and he main KPIs.
3.7.2 Op imized plan s. manual plan – an example
Two p oduc ion plans, one op imized by he sys em and he o he manually de ined (al-
hough s ill gene a ed by he sys em), a e now examined. Figu es 3.14 and 3.15 depic
hese wo plans, in pa icula he schedule o campaigns and he i gin pulp s ock le el.
As usual he ini ial pa o he plans is ixed. The di e ences hus s a in he middle,
whe e he op imized plan includes KLB275A and KLB170A (which we e igno ed by he
manual plan) and an addi ional campaign o KLB225, on he descending pa o he o he
68 Chap e 3. Decision suppo sys em o p oduc ion planning and scheduling
sequence. No e ha plans end o ollow his smoo h ascending and descending pa e n o
g ades, in o de o a oid cos ly se ups. Then, he cycle o he i gin pulp le el is ex ended
in he op imized plan, o p oduce a la ge amoun o KLB170 and a oid a u he cam-
paign o his g ade. A e ha , he VLB campaigns ha e o s a in o de o ise he i gin
pulp le el again. Indeed, hese g ades inco po a e conside ably mo e ecycled ib es and
hence a e used o balance he KLB g ades, which ha e he opposi e composi ion - mo e
i gin ibe s. The manual plan ends wi h low KLB g ades, which we e no epea ed in he
op imized plan.
To be e unde s and he di e en planning app oaches, we need o look a hei im-
pac on he main KPIs. The ela i e imp o emen o he op imized plan o e he manual
coun e pa is gi en in Table 3.3.
Table 3.3: Compa ison o he manual and op imized plans, wi h espec o main KPIs.
Backlog Se ups P oduc ion S ock O e all
-6.4% -10.0% -1.8% -2.6% -7.4%
F om hose igu es, one may conclude ha he addi ional campaigns in he op imized
plan helped imp o ing he backlog in mo e han 6%. Mo eo e , he smoo he g ade
changeo e s and absence o he second wa e o KLB g ades a he end o he manual
plan p o ided a educ ion o 10% in se up cos s. Fu he mo e, in en o y was educed by
almos 3%. The only ad an age o he manual plan is a 2% addi ional p oduc ion. The
op imiza ion me hod made a ade-o when ex ending he p oduc ion cycle, which o ced
a sligh educ ion o he pape machine’s a e, bu allowed a be e ul ilmen o demand
and imp o emen o ope a ional cos s. This kind o ade-o s a e ha d o g asp in manual
planning and p ac i ione s a e o ced o use simple ules, such as a gi en p oduc ion cycle,
o gene a e easible plans. S ill, when p og amming s oppages o equipmen main enance
o when s oppages a ise in dis u bance si ua ions, i is mo e di icul o de ise ules. In
hose cases, he DSS can b ing addi ional alue.
3.7.3 Plan conside ing s oppages
To end his sec ion, a plan conside ing a long s oppage in he whole plan is inspec ed. The
plan is illus a ed in Figu e 3.16, whe e he s oppage o he pape machine is ep esen ed
as ano he pape g ade. The pape machine s ops a e he diges e in o de o consume
all he pulp le in he anks. A he s a -up he diges e is ac i a ed be o e he machine
o c ea e some in en o y o pulp. The machine s a s wi h VLB165, which consumes
signi ican ly mo e ecycled han i gin pulp. In his way he pulp in en o y con inues
o ise un il eaching a le el whe e he KLB p oduc s (which consume mo e i gin pulp)
can be p oduced.
Planning a s oppage akes he esou ces o hei ac ual limi s. The e o e, he a es
ha e o be ca e ully managed. In he gene a ion o he illus a ed plan, some simpli ying
assump ions we e made, such as he abili y o he p oduc ion a es o ise om (o all o)
ze o ins an ly. The aim he e was jus o ob ain a ough idea o wha he plan would be.
3.8. Conclusions and u u e wo k 69
Ne e heless, he sys em allows conside ing maximum a es a ia ions, as well as easily
ede ining maximum and minimum a es. Hence, a e his ini ial plan manage s could
gene a e a mo e accu a e one by u he cus omizing he sys em inpu s.
3.8. Conclusions and u u e wo k
The DSS epo ed in his pape has been de eloped o help a P&P company deal wi h he
a ious challenges o hei p oduc ion planning and scheduling ac i i ies. Companies in
his sec o ha e o di e en ia e hemsel es by p o iding he bes cus ome se ice a min-
imum cos , since pape p ices a e de e mined by he ma ke . The e o e, mul iple c i e ia
ha e o be conside ed and p ope ly weigh ed when de ising a p oduc ion plan. Howe e ,
manage s do no ha e he ime a he ope a ional le el o pe o m a ho ough e alua ion
o plans, which mus sa is y a mul i ude o complex cons ain s. Hence, he DSS suppo s
he au oma ic gene a ion o plans wi h di e en le els o cus omiza ion (e.g. ixing he
sequence and/o amoun s o pape campaigns).
Se e al i e a ions wi h he company we e pe o med in o de o include a se o essen-
ial ea u es o hei planning asks and o design use - iendly in e aces. The immedia e
upda es (due o he “So wa e as a Se ice” se up), in-place edi ing, di ec copy-pas e om
and o Excel, inpu alida ion p ocedu es, au oma ic connec ion o exis ing sys ems and
sepa a ion o plan gene a ion and ine uning in e aces a e examples o echnical de ails
ha we e c ucial o he usabili y o he sys em. On he o he hand, he op imiza ion model
p o ided he equi ed lexibili y in inco po a ing ope a ional cons ain s, such as ixing
campaigns and scheduling s oppages. The me hod hen makes use o he model o gene a e
good quali y solu ions in he sho pe iods o ime a ailable a he ope a ional le el.
As u u e wo k, he e a e addi ional ea u es ha can be included, such as imp o ing
he in e ac i i y o he inal schedules o p o iding mo e cus omiza ion o he inpu da a.
These enhancemen s should be done acco ding o company’s ac ual needs. In addi ion, he
modula design o he sys em, as well as he gene al-pu pose o he op imiza ion me hod,
would acili a e i s adap a ion o ex ension o o he simila plan s.
In scien i ic e ms, he o mula ion may s ill be s eng hened by addi ional alid in-
equali ies o e o mula ions. Compa ing he o mula ions o Ka imi and McDonald (1997)
and Cama go e al. (2012) could gi e some insigh s in his ega d. Mo eo e he acili y
plan loca ion e o mula ion could also imp o e he model’s sol abili y (Amo im e al.,
2011). Ano he impo an aspec o be examined is he impac o he so cons ain s in he
op imiza ion pe o mance and how ha could be add essed by he heu is ic me hod. The
la e could also be imp o ed wi h espec o he neighbo hoods used, possibly allowing i
o add/ emo e campaigns o/ om ce ain posi ions, as sugges ed by Figuei a e al. (2013).
Finally, as compu a ional powe inc eases and he e iciency o he me hods imp o e,
he p oduc ion planning p oblem can in eg a e mo e de ails o o he ac i i ies (up o down-
s eam in he supply chain) o add ess impo an issues, such as p ocess a iabili y and
dis u bances. The la e may ha e an impo an impac on he p oduc ion sys em and he e-
o e i s conside a ion in a p oac i e planning app oach is highly ele an .
70 Bibliog aphy
Bibliog aphy
R. Akki aju, P. Keskinocak, S. Mu hy, and F. Wu. An agen -based app oach o scheduling
mul iple machines. Applied In elligence, 14(2):135–144, 2001.
P. Amo im, T. Pin o-Va ela, B. Almada-Lobo, and A. Ba bósa-Pó oa. Compa ing models
o lo -sizing and scheduling o single-s age con inuous p ocesses: Ope a ions esea ch
and p ocess sys ems enginee ing app oaches. Compu e s and Chemical Enginee ing,
52:177–192, 2013.
Ped o Amo im, Ca los H An unes, and Be na do Almada-Lobo. Mul i-objec i e lo -sizing
and scheduling dealing wi h pe ishabili y issues. Indus ial &Enginee ing Chemis y
Resea ch, 50(6):3371–3381, 2011.
V. Cama go, F. Toledo, and B. Almada-Lobo. Th ee ime-based scale o mula ions o he
wo-s age lo sizing and scheduling in p ocess indus ies. Jou nal o he Ope a ional
Resea ch Socie y, 63:1613–1630, 2012.
Ped o M Cas o, Ii o Ha junkoski, and Ignacio E G ossmann. New con inuous- ime
scheduling o mula ion o con inuous plan s unde a iable elec ici y cos . Indus ial
&enginee ing chemis y esea ch, 48(14):6701–6714, 2009.
CEPI. Key s a is ics – eu opean pulp and pape indus y 2012. Technical epo , June 2013.
MH Co eia, J.F. Oli ei a, and J.S. Fe ei a. In eg a ed esolu ion o assignmen , sequenc-
ing and cu ing p oblems in pape p oduc ion planning. In e na ional Jou nal o P o-
duc ion Resea ch, 50(18):5195–5212, 2012.
And eas D exl and Knu Haase. P opo ional lo sizing and scheduling. In e na ional Jou -
nal o P oduc ion Economics, 40(1):73–87, 1995.
Muge E di ik-Dogan and Ignacio E G ossmann. Simul aneous planning and scheduling o
single-s age mul i-p oduc con inuous plan s wi h pa allel lines. Compu e s &Chemical
Enginee ing, 32(11):2664–2683, 2008.
Gonçalo Figuei a, Ma is ela Oli ei a San os, and Be na do Almada-Lobo. A hyb id ns
app oach o he sho - e m p oduc ion planning and scheduling: A case s udy in he
pulp and pape indus y. Compu e s &Ope a ions Resea ch, 40(7):1804–1818, 2013.
B. Fleischmann and H. Mey . The gene al lo sizing and scheduling p oblem. OR Spec um,
19:11–21, 1997. ISSN 0171-6468.
Nicolas Gold, And ew Mohan, Clai e Knigh , and Malcolm Mun o. Unde s anding
se ice-o ien ed so wa e. So wa e, IEEE, 21(2):71–77, 2004.
Ii o Ha junkoski, Ch is os Ma a elias, Pe e Bonge s, Ped o Cas o, Sebas ian Engell, Ig-
nacio G ossmann, John Hooke , Ca los Méndez, Guido Sand, and John Wassick. Scope
o indus ial applica ions o p oduc ion scheduling models and solu ion me hods. Com-
pu e s &Chemical Enginee ing, 62:161–193, 2014.
Bibliog aphy 71
I ekha A Ka imi and Cono M McDonald. Planning and scheduling o pa allel semi-
con inuous p ocesses. 2. sho - e m scheduling. Indus ial &Enginee ing Chemis y
Resea ch, 36(7):2701–2714, 1997.
Uday S Ka ma ka and Linus Sch age. The de e minis ic dynamic p oduc cycling p ob-
lem. Ope a ions Resea ch, 33(2):326–345, 1985.
May-Fong Lim and IA Ka imi. Resou ce-cons ained scheduling o pa allel p oduc ion
lines using asynch onous slo s. Indus ial &enginee ing chemis y esea ch, 42(26):
6832–6842, 2003.
Ch is os T Ma a elias. Mixed- ime ep esen a ion o s a e- ask ne wo k models. Indus ial
&enginee ing chemis y esea ch, 44(24):9129–9145, 2005.
Alain Ma el, Na ee Rizk, Sophie D’Amou s, and Hanen Bouch iha. Synch onized
p oduc ion-dis ibu ion planning in he pulp and pape indus y. In And e Lange in
and Diane Riopel, edi o s, Logis ics Sys ems: Design and Op imiza ion, pages 323–350.
Sp inge US, 2005. ISBN 978-0-387-24977-3.
Sesh Mu hy, Rama Akki aju, Richa d Goodwin, Pina Keskinocak, John Rachlin, F ede -
ick Wu, James Yeh, Robe Fuh e , San hosh Kuma an, Alok Agga wal, Ma in S u zen-
becke , Ranga Jaya aman, and Robe Daigle. Coope a i e mul iobjec i e decision sup-
po o he pape indus y. In e aces, 29:5–30, 1999. ISSN 0092-2102.
S. Pol onie e, K. Poldi, F. Toledo, and M. A enales. A coupling cu ing s ock-lo sizing
p oblem in he pape indus y. Annals o Ope a ions Resea ch, 157:91–104, 2008. ISSN
0254-5330.
A. Respício and M.E. Cap i o. Ma ke ing-p oduc ion in e ace h ough an in eg a ed dss.
Jou nal o Decision Sys ems, 17(1):119–132, 2008.
N. Rizk, A. Ma el, and S. D’Amou s. Synch onized p oduc ion-dis ibu ion planning in a
single-plan mul i-des ina ion ne wo k. Jou nal o he Ope a ional Resea ch Socie y, 59
(1):90–104, 2008.
Ma is ela Oli ei a San os and Be na do Almada-Lobo. In eg a ed pulp and pape mill
planning and scheduling. Compu e s &Indus ial Enginee ing, 63(1):1–12, 2012. ISSN
0360-8352.
L. Szabó, A. So ia, J. Fo ss öm, J.T. Ke änen, and E. Hy önen. A wo ld model o he
pulp and pape indus y: Demand, ene gy consump ion and emission scena ios o 2030.
En i onmen al Science &Policy, 12(3):257–269, 2009.
Joakim Wes e lund, Ma ias Häs backa, Sebas ian Fo ssell, and Tapio Wes e lund. Mixed-
ime mixed-in ege linea p og amming scheduling model. Indus ial &enginee ing
chemis y esea ch, 46(9):2781–2796, 2007.
72 Chap e 3. Decision suppo sys em o p oduc ion planning and scheduling
Figu e 3.12: Web in e ace o he DSS o ine- uning s uc u al (no equen ly changed)
pa ame e s.
Bibliog aphy 73
Figu e 3.13: Ou pu Excel ile wi h ables and cha s de ailing he p oduc ion plan (com-
ple e able, e olu ion o inal p oduc s s ock /backo de s, pape campaigns and machine’s
p oduc ion a e, espec i ely).
74 Chap e 3. Decision suppo sys em o p oduc ion planning and scheduling
VLB165
VLB140
VLB115
KLB115
KLB125
KLB135
KLB135A
KLB170
KLB186
KLB200
KLB225
KLB275
0
200
400
600
pape campaign ank le el
g ades
i gin pulp ank
ime
Figu e 3.14: Manual plan – gene a ed by he sys em, ixing he sequence and size o pape
campaigns (g ades on he le and i gin pulp on he igh axis).
VLB165
VLB140
VLB115
KLB115
KLB125
KLB135
KLB135A
KLB170
KLB170A
KLB186
KLB200
KLB225
KLB275
KLB275A
0
200
400
600
pape campaign ank le el
g ades
i gin pulp ank
ime
Figu e 3.15: Op imized plan – gene a ed by he sys em, op imizing he sequence and size
o pape campaigns (g ades on he le and i gin pulp on he igh axis).
Bibliog aphy 75
S oppage
VLB165
VLB140
VLB115
KLB115
KLB125
KLB135
KLB170
0.0
5.0
10.0
pm
0
200
400
600
800
pape campaign ank le el
g ades / diges e ’s a e
i gin pulp ank
ime
diges e ’s a e
Figu e 3.16: Plan conside ing a long long s oppage – pape g ades (ba s) and diges e ’s
a e (dashed line) ep esen ed on he le axis and i gin pulp ank (solid line) on he igh
axis.
82 Chap e 4. Simula ion-op imiza ion axonomy
whe e RXi ,RI+
i and RI−
i a e he obse ed p oduc ion, in en o y and sho age amoun s,
and ci ,hi and qi a e he p oduc ion, in en o y and sho age cos s, espec i ely;
•g(θ)=G(θ,ω) would include cons ain s such as he in en o y balance equa ions
RXi (θ,ω)+RI+
i( −1)(θ,ω)+RI−
i (θ,ω)−RI+
i (θ,ω)=di i=1...3 =1...T
(4.5)
whe e di is he demand;
•Θinco po a es non-nega i i y and o he a p io i cons ain s, such as he o al a ail-
able bu e posi ions
4
X
b=2
Sb≤Npos (4.6)
•ωis he se o alues ob ained o he (s ochas ic) p ocessing imes in a gi en eal-
iza ion.
No e he di e ence be ween Xi and RXi . The o me is he p ede ined amoun , whe eas
he la e is ha obse ed in he simula ion (which will also depend on he bu e sizes S
and he s ochas ic e ec s ω). The e is a wide a ie y o me hods app oaching his p oblem.
Some o he mos impo an a e ollowing p esen ed.
S a is ical Selec ion Me hods (SSM)
Conside he bu e space alloca ion p oblem s a ed abo e (second a ian ). I he numbe
o possible solu ions is no e y high (le say each bu e can ha e one, wo o h ee spaces,
esul ing in 27 combina ions), hen all hose combina ions can be e alua ed in o de o de-
e mine he op imal solu ion. Howe e , he solu ion space is no he only o be explo ed. In
ac , he p oblem is s ochas ic and hus one eplica ion should no be enough o accu a ely
e alua e he pe o mance o each solu ion. The e o e, he numbe o eplica ions o each
solu ion (i.e. he way he p obabili y space is explo ed) is also o be de e mined. S a is ical
Selec ion Me hods, which include he well-known Ranking and Selec ion (R&S) and Mul-
iple Compa ison P ocedu es (MCP), ocus on his aspec . These me hods compa e and
selec solu ions applying s a is ical analysis, so ha a gi en con idence is achie ed in ha
p ocess. The solu ion sea ch ypically consis s o an exhaus i e enume a ion and is hus
limi ed o a ela i ely small se o solu ions (Θ) wi h disc e e inpu a iables, such as in his
bu e space alloca ion p oblem. A he end, R&S p o ides he bes solu ion, while MCP
quan i y he di e ences in pe o mance ( (θ)) among he solu ions. T adi ional p ocedu es
(he e e e ed o as SSMa) can be enhanced ( o SSMb) by he me hod o common andom
numbe s (CRN) which induces a posi i e co ela ion among he solu ions (Swishe e al.,
2003). In p ac ical e ms CRN a ou s a ai e compa ison be ween solu ions, esul ing in
a educ ion in he necessa y numbe o eplica ions.
4.2. S-O me hods 83
Me aheu is ics (MH)
To explo e la ge o in ini e solu ion spaces (such as la ge ins ances o he bu e space al-
loca ion o he lo sizing p oblem), “ ue” sea ch algo i hms a e needed. Me aheu is ics a e
high le el amewo ks ha combine basic heu is ics in o de o e icien ly and e ec i ely
explo e he sea ch space (Blum and Roli,2003). These algo i hms may be single-solu ion
based (e.g. simula ed annealing (Alkhamis e al.,1999)), popula ion-based (e.g. gene ic
algo i hms (T uong and Azadi a ,2003)) o se -based (e.g. nes ed pa i ions (Shi and Óla -
sson,2000)) and can ackle bo h combina o ial (MHa) and con inuous op imiza ion (MHb).
They we e o iginally de eloped o add ess de e minis ic p oblems, e en hough he al-
go i hm i sel may be s ochas ic. Ne e heless, me aheu is ics ha e also been applied o
s ochas ic simula ion op imiza ion, whe e he e alua ion o solu ions is pe o med (mul i-
ple imes o each) by he simula ion model (Óla sson,2006). Indeed, gi en hei lexibili y
o ackle any ype o solu ion space and hei abili y o quickly achie e good quali y so-
lu ions, hese me hods domina e he op imiza ion ou ines o he disc e e-e en simula ion
so wa e.
Memo y-based Me aheu is ics (MMH)
The di e ence o he p e ious is ha while mo ing in he solu ion space, hese me hods
cons uc and memo ize a pe cep ion o he landscape. This memo y s uc u e is ypically
a p obabili y dis ibu ion on he space o solu ions which p o ides an es ima e o whe e he
bes solu ions a e loca ed. The gene a ion o he ollowing solu ions hen uses his dis i-
bu ion o pe o m a biased selec ion owa ds p omising egions. Some examples include
Swa m In elligence (e.g. an colony op imiza ion (Do igo and Blum,2005)), Es ima ion
o Dis ibu ion Algo i hms (La añaga and Lozano,2002), C oss-En opy Me hod (Rubin-
s ein and K oese,2004) and Model Re e ence Adap i e Sea ch (Hu e al.,2008). These
me hods a e also known as model-based me hods, as opposed o he p e ious me hods,
which a e ins ance-based (Fu e al.,2005), and may wo k ei he wi h disc e e (MMHa) o
con inuous a iables (MMHb).
Random Sea ch (RS)
RS is e y close o MH (and may e en be seen as he same me hod), whe e a neighbou hood
can be de ined o each incumben solu ion. Howe e , he nex mo e is p obabilis ically
chosen, based on a gi en p obabili y dis ibu ion. These me hods ha e also been o iginally
designed o con en ional de e minis ic p oblems, bu ha e been ex ended a e wa ds o
he s ochas ic se ing. In he la e , an addi ional ea u e has o be de ined: how he bes
solu ion is selec ed. Possible al e na i es include he incumben solu ion a he end o he
p ocedu e, he mos isi ed solu ion and he solu ion wi h he bes sample mean. The choice
is closely ela ed o he app oach o dealing wi h noise in he s ochas ic se ing, which can
ange om expending a signi ican amoun o compu e e o on each poin isi ed (RSa)
o deciding on how o p oceed based only on limi ed in o ma ion (RSb). Fu he de ails on
RS a e gi en by And adó i (2006) and ecen wo k is epo ed by Hong e al. (2010) and
Xu e al. (2013).
84 Chap e 4. Simula ion-op imiza ion axonomy
S ochas ic App oxima ion (SA)
In con as o he p e ious me hod, SA is a g adien -based p ocedu e and is he e o e a -
ge ed a con inuous a iables (such as he lo sizing decisions o he p oblem desc ibed
be o e). Unde app op ia e condi ions, con e gence owa ds local op ima can be gua an-
eed and i s a e is d ama ically enhanced wi h he a ailabili y o di ec g adien s, which
a e p oblem-speci ic. Thei absence is sol ed by compu ing nai e es ima ions, such as i-
ni e di e ences o simul aneous pe u ba ions. SA ypically uses a sho simula ion un in
each i e a ion, bu can also pe o m g adien s eps a in e als du ing a (single) long un
(Single-Run Op imiza ion – see Su i and Leung (1987)). Fo a comp ehensi e discussion
on SA see Kushne and Yin (2003).
Sample-Pa h Op imiza ion (SPO)
SPO (Gu kan e al.,1994;Plambeck e al.,1996) is based on he idea o going ou a
enough along he sample pa h ( o ha e a good es ima e o he limi unc ion), ixing i o
e e y solu ion and sol ing he esul ing p oblem applying de e minis ic op imiza ion. In
ou illus a i e p oblem a la ge se o p ocessing imes would be sampled and used in a
long simula ion un. Applying he same se o p ocessing imes o e e y solu ion ( he CRN
me hod ex ended o he whole domain) makes i a de e minis ic p oblem, which should be
easie o sol e. Indeed, he exis ence o e ec i e me hods o cons ained de e minis ic
op imiza ion can be exploi ed he e. In spi e o he ypical implemen a ions (he e deno ed
by SPOa) being g adien -s ep me hods, SPO is a gene al p ocedu e and can be applied o
many SE and AME me hods.
Me amodel-based Me hods
Ins ead o i e a ing h ough di e en solu ions and unning simula ions o e alua e each
o hem, ano he app oach is o i s pe cei e he landscape in mul iple poin s (using sim-
ula ion) and hen app oxima e a me amodel o hose poin s. De e minis ic op imiza ion
me hods can hen be applied o he ob ained objec i e unc ion, which is inexpensi e o
compu e. This is he idea behind Me amodel-based Me hods. A signi ican ad an age o
hese me hods, as Ba on and Meckesheime (2006) ad oca e, is he “ educ ion in p edic-
ion a iance by ex ending he e ec o he law o la ge numbe s o e all poin s in he
i ing design”. Howe e , “ his ad an age comes a a cos : bias ha is in oduced when he
me amodel ails o cap u e he ue na u e o he esponse su ace”.
Two main s a egies exis : Global Me amodel-based Me hods (GMM) and Local Me amodel-
based Me hods (LMM). The o me a e ypically plain SO sequen ial p ocedu es and e-
qui e a global op imiza ion s a egy. The la e , which include he well-known Response
Su ace Me hodology (RSM) – see Khu i and Mukhopadhyay (2010), al e na e be ween
model cons uc ion ( om simula ion esponses) and de e minis ic op imiza ion. Fo bo h,
solu ions may be e alua ed wi h single (GMMaand LMMa) o mul iple ealiza ions/ eplica ions
(GMMband LMMb).
4.2. S-O me hods 85
G adien Su ace Me hods (GSM)
Combining echniques is equen ly a p omising a enue o esea ch. One o hese ui -
ul esul s is he GSM, which combines RSM and SA. P oposed by Ho e al. (1992), his
me hod implici ly u ilizes a second-o de design o he i ing su ace (in RSM), by consid-
e ing he g adien su ace modelled by a i s -o de design. Howe e , only a single eplica e
is used o ob ain each es ima e. The p ocedu e swi ches o a pu e SA when he op imum is
app oached (Fu,1994).
Su oga e Managemen F amewo k (SMF)
The e a e app oaches ha make also use o me amodels (o su oga e models), bu do no
apply a de e minis ic sea ch di ec ly on hem. Ins ead, he su oga e model is used jus
o guide he sea ch, sc eening ou poo solu ions, which do no ge o be e alua ed by
simula ion, o e en selec ing only high-quali y solu ions o examina ion. The la e is he
case o SMF. This me hodology was p oposed by Booke e al. (1999) and is buil on op
o pa e n sea ch me hods – see To czon (1997). SMF c ea es a g id o poin s o se e as
a basis o he ecalib a ion o a su oga e model. The poin s a e chosen o be spa ially
dispe se, in o de o imp o e he accu acy o he app oxima ion, bu a he same ime be
p omising solu ions. The su oga e model hen p edic s poin s a which imp o emen s
a e expec ed. The ecalib a ion p ocedu e may use single (SMFa) o mul iple e alua ions
(SMFb) in each poin . The o e all me hod does no equi e he exis ence o de i a i es and
s ill con e ges owa ds local op ima.
Re e se Simula ion Technique (RST)
The idea o RST is o speci y in ad ance desi ed a ge alues o anges o alues o pa -
icula simula ion a iables and un he model wi h expe sys ems guiding hose a iables
owa ds hei co esponding a ge s (Wild and Pigna iello,1994). Fo ins ance, in ou lo
sizing p oblem we could speci y ha he ime each machine mspends on each p oduc i
in each day could no be highe han a gi en pe cen age o he o al a ailable ime o
ha day. I his sha e was eached, hen he machine would shi o ano he p oduc . The
adjus men s hus occu du ing he simula ion execu ion. RST appea s o be an in e es ing
app oach o gene a e an ini ial solu ion o easonable quali y. Bo h con inuous (RSTa) and
disc e e a iables (RSTb) can be add essed by his me hod. In Lee e al. (1997) he au ho s
epo an RST algo i hm ha inds he s eady s a e o a sys em and an op imal s a e.
App oxima e Dynamic P og amming (ADP)
The pa ame ic op imiza ion p oblem de ined in he beginning o his sec ion can be ex-
ended o a con ol op imiza ion p oblem (o en called dynamic op imiza ion), which may
be s a ed as: min
U(·)EhPT
=1C(V( ,ω),U(V, ))i, whe e V( ,ω) is he s a e o he sys em and
U(V, ) is he co esponding con ol ac ion. The solu ion o his p oblem is no a ini e di-
mensional ec o (like θ), bu a unc ion (U(V, )). The op imal con ol may be sol ed ia
dynamic p og amming (DP). Howe e , acco ding o Gosa i (2003), s ochas ic DP “su e s
86 Chap e 4. Simula ion-op imiza ion axonomy
om he cu ses o modelling and dimensionali y”. The au ho s a es also ha “ hese wo
ac o s ha e inspi ed esea che s o de ise me hods ha gene a e op imal o nea -op imal
solu ions wi hou ha ing o compu e o s o e ansi ion p obabili ies”. ADP (also known
as ein o cemen lea ning o neu o-dynamic p og amming, in he a i icial in elligence and
con ol heo y communi ies, espec i ely) is one such me hod. Combining DP and simula-
ion, ADP is based on a lea ning agen which selec s ac ions acco ding o i s knowledge o
he en i onmen . The la e esponds by an immedia e ewa d ( he ein o cemen signal).
This p ocedu e is simila o RST (in he sense ha he e is an agen con olling he sys em
o e he simula ion), bu he e he agen lea ns and imp o es i s ac ions o e he p ocess.
Fo a b ie e iew o ADP see Powell (2009).
Re ospec i e Simula ion Response Op imiza ion (RSRO)
All he a o emen ioned me hods (wi h he excep ion o RST) deal wi h s ochas ic p oblems
pe o ming ei he one o mul iple ealiza ions o each solu ion. A di e en app oach,
which is he essence o RSRO (Healy and Sch uben,1991), is o conside one common
ealiza ion o e e y solu ion. No e he di e ence o SPO, whe e he la e ixes a long
sample pa h (i.e. mul iple ealiza ions o each solu ion). In he bu e space alloca ion
p oblem, RSRO would simula e he sys em wi h an in ini e (o e y la ge) numbe o spaces
un il he o al numbe o used spaces eached he eal a ailabili y. This would be ac ually
he op imal solu ion o ha ealiza ion i he objec i e was o minimize he ime o bu e
exhaus ion, bu no necessa ily a good solu ion o o he scena ios. Hence, he me hod
is epea ed o a numbe o ealiza ions. Each ealiza ion esul s in a dis inc solu ion.
The e o e, he expec ed alue o he ele an pe o mance measu e canno be e alua ed.
Ins ead, i p o ides o ins ance he solu ion wi h he maximum likelihood o being op imal
( he poo beha iou when i is no op imal is no assessed hough). Like RST, RSRO seems
o be app op ia e o gene a ing good solu ions o u he e alua ion and e inemen . The
mos na u al use o RSRO applies exac me hods (RSROa), al hough heu is ics can also
be used. The RSRO app oach should no be mis aken o he mo e ecen e ospec i e
op imiza ion (Pasupa hy,2010), he la e being close o SPO.
4.2.2 Solu ion Gene a ion app oaches
Using simula ion o e alua e di e en solu ions (as in e e y me hod o he p e ious sec ion)
can be e y compu a ionally in ensi e. Fo some pa icula p oblems, he eedback om
simula ion may no e en be impo an o he choice o he solu ion. In hose cases analy ical
models can be o mula ed and sol ed and hei solu ions simula ed (op imiza ion-based
simula ion), in o de o compu e all he a iables o in e es . The pu pose o simula ion
he e is no o e i y he ad an age o one solu ion o e ano he , bu simply o compu e
some a iables and hence be pa o he whole solu ion gene a ion (SG).
The lo sizing p oblem desc ibed in he beginning o his sec ion could be o mula ed
4.2. S-O me hods 87
as:
min
T
X
=1
3
X
i=1ci ·Xi +hi ·I+
i +qi ·I−
i (4.7)
s. . Xi +I+
i( −1) +I−
i −I+
i =di i=1...3 =1...T,(4.8)
3
X
i=1
pim ·Xi ≤capm m=1...4 =1...T,(4.9)
Xi ,I+
i ,I−
i ≥0i=1...3 =1...T,(4.10)
whe e pim is he p ocessing ime (he e assumed de e minis ic) o p oduc ion machine m,
capm i s capaci y in pe iod and he emaining e minology is he same as ha used in
he p e ious subsec ion. Bu e spaces a e assumed o be in ini e. No e ha p oduc ion,
in en o y and sho age amoun s a e all decision a iables, no obse a ions o simula ion.
Simula ion is hen used o compu e mo e ealis ic alues o hese a iables.
In o de o close he gap be ween p ede ined and simula ed alues, i would be impo -
an o educe he p oduc ion capaci ies (capm ) in he analy ical model, since he e will
be wai ing imes be ween ope a ions which a e only conside ed in simula ion. I de ining
hese capaci y educ ions appea s o be di icul and c i ical o he o e all op imiza ion,
his SG app oach migh no be he bes choice. Howe e , i he analy ical model is able
o gene a e good solu ions, his should be he bes app oach, especially when simula ion is
e y expensi e, since i only needs o un once. The op imiza ion p ocess can be pe o med
ei he be o e o du ing ha simula ion un. These wo schemes a e desc ibed below.
Solu ion Comple ion by Simula ion (SCS)
In his i s me hod simula ion is used o compu e some a iables, which will comple e o
co ec he solu ion gene a ed by op imiza ion. In ou example he model s a ed by (4.7)–
(4.10) is sol ed o he en i e ho izon, esul ing in ce ain p oduc ion (Xi ), in en o y (I+
i )
and sho age (I−
i ) amoun s. This solu ion is ed o simula ion, which gi es mo e accu-
a e alues o hese a iables. The li e a u e applies SCS o di e en ypes o p oblems.
B iggs (1995) app oached he p oblem o mass ac ical ai bo ne ope a ions. The analy ical
model gene a es a solu ion unde ideal condi ions. Simula ion hen conside s he inhe -
en a iabili y and p o ides he expec ed, bes and wo s ou comes. O he applica ions o
SCS somehow hyb idize i wi h SE me hods. Fo ins ance, Lim e al. (2006) de e mine a
p oduc ion-dis ibu ion plan wi h an analy ical model and simula e ha plan o ob ain mo e
ealis ic alues. Howe e , i he plan is no accep able, he eplenishmen policy is changed
and simula ion is un again. T uong and Azadi a (2003) embed an SCS in o an MH o
sol e a supply chain design p oblem. Thei gene ic algo i hm de e mines some quali a-
i e decisions. Each ch omosome is decoded by an SCS me hod, whe e i s an analy ical
model is sol ed o de e mine o he decisions and hen simula ion is used o e alua e he
comple e solu ion. The popula comme cial op imiza ion module Op Ques also allows
applying his ype o hyb idiza ion.
88 Chap e 4. Simula ion-op imiza ion axonomy
I e a i e Op imiza ion-based Simula ion (IOS)
Ins ead o a simply sequen ial p ocedu e, op imiza ion may be called du ing simula ion ex-
ecu ion. Fo ins ance he abo e analy ical model can be sol ed in a olling-ho izon basis,
simula ing one pe iod ( ) a a ime, upda ing he in en o ies and sho ages o ha pe iod
and sol ing he analy ical model om ha pe iod un il he end o he ho izon. The new
solu ion is hen e-p imed in simula ion, which ad ances ano he pe iod ( o +1). In his
way he ou pu o op imiza ion should be close o ha o simula ion, since he o me
keeps ack o he la e o e he ho izon. This i e a i e p ocess is applied by Sub amanian
e al. (2000). Howe e , in hei case op imiza ion is no called in a pe iodic scheme, bu
in an e en -d i en basis. Whene e he simula ion module encoun e s a need o a con ol
ac ion, i momen a ily suspends i sel and communica es he s a e o he sys em o he op i-
miza ion module, which esol es i . This app oach may esemble RST. Howe e , he e he
op imiza ion phase is based on an analy ical model and does no need simula ion o e alu-
a e i s ac ions. In ac , RST ob ains eedback om simula ion, whe eas IOS only ecei es
eed o wa d. Fu he mo e he need o adjus men s does no esul om he speci ica ion
o a ge s.
4.2.3 Analy ical Model Enhancemen app oaches
Solu ion Gene a ion me hods can be e y e icien , bu i he eedback om simula ion
p o es o be impo an , hey may no be e ec i e. The e o e, as men ioned abo e, hey
o en end up being hyb idized wi h Solu ion E alua ion me hods. Ano he possibili y is o
enhance he analy ical model using he simula ion esul s. This analy ical model enhance-
men (AME) can be conduc ed in di e en ways.
S ochas ic P og amming De e minis ic Equi alen (SPDE)
Conside he lo sizing p oblem p e iously s a ed, bu wi h only one machine. The wai -
ing imes issue is now simple o add ess. The only di icul aspec ha emains is he
unce ain y o p ocessing imes. In his si ua ion, s ochas ic p og amming appea s o be
app op ia e. S ill, since ma hema ically manipula ing p obabili y dis ibu ions can be di i-
cul , one may eso o Mon e Ca lo simula ion o pe o m he sampling o scena ios, which
a e la e embedded in a single analy ical model. The inal model is hen he same as be o e,
bu whe e cons ain s (4.9) a e eplaced by:
3
X
i=1
piw ·Xi ≤cap =1...T w =1...W,(4.11)
whe e w ep esen s a gi en scena io, o which all p ocessing imes piw a e sampled om
hei co esponding dis ibu ions. This model is called a la ge-scale de e minis ic equi a-
len , since in oducing he scena io index may inc ease he numbe and size o cons ain s
by mul iples. The gene al p ocedu e is known as sample a e age app oxima ion (SAA –
see Kleyweg e al. (2002)) and includes SPO (which ixes a long sample pa h), bu also he
agg ega ion o ealiza ions o mul iple pa hs. The me hod s a s wi h a gi en sample size,
4.2. S-O me hods 89
which inc eases un il equi ed con idence and a iance le els a e achie ed. An example is
gi en in San oso e al. (2005). These SPDE app oaches ypically equi e some assump ions
/simpli ica ions o be made, when compa ed o S-O using disc e e-e en simula ion. Ne -
e heless, he wo k by Sch uben (2000) may change his scena io (see Subsec ion 4.2.4).
Recu si e Op imiza ion-Simula ion App oach (ROSA)
I he SPDE me hod was applied o he o iginal sys em, consis ing o ou machines, i
would p obably ail o p o ide a good solu ion, since i would no conside wai ing imes.
In hose cases he ou pu o a disc e e-e en simula ion model should be help ul o assess
hose pa ame e s and hus co ec ly es ima e a p ope capaci y educ ion o he analy ical
model. Tha is he idea behind ROSA. This app oach was i s ly p oposed by Nolan and
So e eign (1972) and consis s o unning al e na ely a ( ypically linea ) de e minis ic an-
aly ical model, such as (4.7)–(4.10), and a ( ypically s ochas ic disc e e-e en ) simula ion
model. Simula ion uses he solu ion gene a ed by op imiza ion and compu es pa icula
pe o mance measu es (in ou case, h oughpu imes). The alues o hese measu es a e
hen in oduced again in o he analy ical model, e ining i s pa ame e s (e.g. capaci y e-
duc ions, p ocessing imes). The i e a i e p ocess ends a e a s opping c i e ion is me
(e.g. con e gence o he solu ion, pa ame e s, objec i e). I should be no ed ha e en i he
p ocessing imes we e de e minis ic, simula ion would s ill be needed, due o he wai ing
imes.
The e a e se e al implemen a ions o his app oach, applying di e en s opping c i e ia
and e inemen s a egies. The a ian s in Albey and Bilge (2011), Bang and Kim (2010)
and Almede e al. (2009) a e some in e es ing examples. The i s wo ackle pu e de-
e minis ic p oblems (ROSAa), whe eas he las one app oaches a s ochas ic en i onmen
(ROSAb). In he la e case esul s om mul iple simula ion uns ha e o be agg ega ed
( ypically by quan iles, which may e lec di e en isk-a e se le els). Some au ho s ha e
c i icized hese i e a i e p ocedu es, claiming ha con e gence can be p oblema ic (I dem
e al.,2008). S ill, mos o he s udies ha e ound con e gence in p ac ice a e a ew i e -
a ions. Aca e al. (2009) p opose a ROSA amewo k close o SE me hods. The au ho s
de ine an analy ical model wi h an op imis ic objec i e unc ion. Simula ion e alua es each
solu ion gene a ed (unde mo e ealis ic condi ions) and co ec s he objec i e unc ion o
ha pa icula solu ion. This ROSA a ian is one o he ew S-O me hods ha is op imal.
Ne e heless, i is gea ed o disc e e solu ion spaces.
Func ion Es ima ion based App oach (FEA)
An al e na i e o he i e a i e p ocedu e o ROSA is he ini ial es ima ion o (o en nonlin-
ea ) unc ions ha desc ibe he ela ionship be ween pa icula inpu and ou pu a iables.
In ou lo sizing p oblem he ela ionship be ween lo sizes X and p oduc ion lead- imes
l (X ), which include p ocessing and wai ing imes, is no i ial and needs simula ion o be
es ima ed. By pe o ming a se o simula ions, his dependency can be cha ac e ized and
included in he analy ical model, speci ically in he capaci y cons ain s:
l (X )≤capm m=1...4 =1...T,(4.12)
90 Chap e 4. Simula ion-op imiza ion axonomy
All he o he cons ain s and he objec i e unc ion emain he same. In his way, he
me hod is no dependen on he con e gence be ween simula ion and op imiza ion, like
ROSA. Howe e , his comes a he cos o a mo e di icul analy ical model o be sol ed.
An example o FEA is implemen ed by Asmundsson e al. (2006). The au ho s conduc an
ini ial simula ion s udy o speci y he nonlinea ela ionship be ween he expec ed wo k-
in-p og ess and he expec ed h oughpu . This ela ionship is ep oduced in wha a e called
“clea ing unc ions”. The inal analy ical o mula ion inco po a es an app oxima ion o
hese conca e unc ions by ou e linea iza ion.
Op imiza ion-based Simula ion wi h I e a i e Re inemen (OSIR)
ROSA assumes ha once he decisions a e made, hey canno be e ised. Howe e , in
p ac ice hey o en can. I ha is o be conside ed, SPDE o ins ance has o be ex ended
o a mul i-s age s ochas ic p og am. This inc eases conside ably he scale o he model
o be sol ed, which easily becomes in ac able. An al e na i e is p oposed by Jung e al.
(2004), who app oach a supply chain managemen p oblem unde demand unce ain y. The
au ho s ha e de ised a amewo k simila o IOS, bu ha pe o ms e inemen s o he an-
aly ical model. The la e is hus sol ed in olling-ho izon wi hin he simula ion model
(op imiza ion-based simula ion). This p ocedu e is epea ed mul iple imes, pe o ming
(e e y ni e a ions) he app op ia e e inemen s o he sa e y s ock le els, in o de o accom-
moda e he unce ain y o demand. The e inemen p ocess, howe e , is no s aigh o wa d
in hei case. Indeed, unlike he de e minis ic p oblems whe e capaci y educ ions di ec ly
esul om simula ed wai ing imes, in his s ochas ic p oblem he igh adjus men s a e o
be de e mined. Fo his pu pose, he au ho s apply a g adien -based sea ch. Thei me hod
can hus be seen as an IOS embedded in an SA me hod. The inpu a iables o he la e
a e he e inemen pa ame e s in he o me ( he sa e y s ocks).
4.2.4 Me hods ela ed o S-O
Be o e concluding his sec ion, we would like o make a e e ence o me hods ha a e
closely ela ed o S-O, bu may no be exac ly a hyb idiza ion be ween simula ion and
op imiza ion. Sch uben (2000) p oposed modelling sample pa hs om e en ela ionship
g aphs, which a e used o simula e disc e e e en sys ems (DES) as he solu ions o ma h-
ema ical p og amming (MP) models. In Chan and Sch uben (2008) he au ho s p o ide a
p ocedu e ha gene a es hese op imiza ion models di ec ly om he explici e en ela-
ionships and examine se e al examples and po en ial applica ions. The objec i e o he
MP models, as in he simula ion, is simply o execu e e en s as ea ly as possible. Hence,
hey a e seen as simula ion models. The solu ion o each MP model ep esen s a single
simula ion un. This p ocedu e does no i in he S-O de ini ion gi en in Sec ion 5.1, since
i does no combine simula ion and op imiza ion. Ins ead, i eplaces he o me by he
la e . Thus, i can be called “simula ion by op imiza ion” (SbO).
SbO has wo main ad an ages o e con en ional simula ion. Fi s , linea p og amming
duali y can be used o pe o m sensi i i y analysis, which is simple han he adi ional
way o compu ing sample pa h de i a i es. Mo eo e , as Chan and Sch uben (2008) ex-
4.3. S-O axonomy: a new uni ied amewo k 91
plain, he solu ion ob ained om linea p og amming may p o ide mo e in o ma ion o a
single simula ion un because o he pe u bed sample pa hs can be eached om he cu en
sample pa h by some addi ional compu a ion (pi o s), which may be easie han unning a
new simula ion.
The o he key ad an age is ela ed o he applica ion o his app oach o S-O. SbO
p omo es a deepe in eg a ion be ween simula ion and op imiza ion. Indeed, he cons ain s
ha desc ibe he sys em dynamics can be embedded wi hin an op imiza ion model ha also
de e mines decisions (in addi ion o simula ing he sys em). I he concep o SAA is also
applied, a single op imiza ion model can be enough o pe o m he whole S-O. This can be
seen as an SPDE, bu less es ic ed by assump ions ha o e simpli y he p oblem.
Ne e heless, SbO has a majo issue o be add essed: compu a ional ime. I one SbO
un can p o ide mo e in o ma ion han one con en ional simula ion un, i is also ue
ha i may consume signi ican ly mo e ime. The MP model may ha e in ege a iables
which highly inc ease he compu a ional bu den. To o e come his di icul y, Al ie i and
Ma a (2012) p opose app oxima e ep esen a ions o simula ion, based on ime bu e s.
In Al ie i and Ma a (2013), he au ho s apply a ime-based decomposi ion algo i hm o
u he educe he compu a ional e o .
4.3. S-O axonomy: a new uni ied amewo k
The p oposed amewo k o classi ying simula ion-op imiza ion me hods is composed o
ou dimensions:
1. Simula ion Pu pose,
2. Hie a chical S uc u e,
3. Sea ch Me hod and
4. Sea ch Scheme.
The i s wo a e ela ed o he in e ac ion be ween simula ion and op imiza ion, whe eas
he o he wo conce n he sea ch algo i hm design. In he ollowing subsec ions we desc ibe
all he ca ego ies o each dimension and combine he ou dimensions, wo by wo. The
wo ma ices ha esul a e hen used o classi y all he p e iously e iewed me hods.
4.3.1 In e ac ion be ween simula ion and op imiza ion
The ca ego ies o Simula ion Pu pose co espond o he main s eams o esea ch in S-O:
•E alua ion Func ion (EF) – i e a i e p ocedu es ha use simula ion o e alua e solu-
ions and hence guide he sea ch, alida ing i s mo es;
•Su oga e Model Cons uc ion (SMC) – me hods which apply simula ion o he
cons uc ion o a su oga e model, which is ei he used o guide he sea ch o is
di ec ly sea ched;
98 Chap e 4. Simula ion-op imiza ion axonomy
4.4.4 Sea ch scheme
The selec ion o he sea ch scheme is mainly ela ed o he ela i e di icul y in a elling
in bo h solu ion and p obabili y spaces and o he ade-o be ween con e gence and di-
e si ica ion. The e o e, i i is ha de o mo e in he solu ion space, ei he DR1S o CR1S
should be he co ec choice. This is he case o app oaches like ROSA, whe e each i e -
a ion equi es he en i e esolu ion o an analy ical model. The di e ence be ween DR1S
and CR1S is ha he o me ocuses mo e on di e si ica ion whe eas he la e p o ide
as e con e gence. On he o he hand, i mo ing in he p obabili y space appea s o be
mo e di icul (o non-exis en , in he case o de e minis ic p oblems), hen 1RMS would
be mo e app op ia e. This is he ounda ion o he RSRO app oach: o p oblems such
as he well-known News endo p oblem (see Ruszczynski and Shapi o (2003)), i can be
mo e con enien o conside all he solu ions be o e changing he ealiza ion. Finally, i
mo ing in bo h spaces is simila in e ms o e o , hen 1R1S may be he bes op ion.
This is he app oach o some me hods which a e e y ocused on di e si ica ion issues in
s ochas ic se ings, such as SA and RSb. In SMC me hods (such as LMM o GMM) g ea e
di e si ica ion is achie ed wi h DR1S and 1R1S. Bo h ob ain a g ea e a ie y o ealiza-
ions and he la e allows simula ing mo e solu ions. The e is hus a end o dec easing
di e si ica ion (o inc easing con e gence) along he axis o his dimension, as sugges ed
in Figu e 4.4. Ne e heless, he e is ano he aspec ha should be aken in o conside a-
ion when choosing he sea ch scheme: he use o a iance educ ion echniques (VRTs) o
SSM ideas, which equi e DR1S/CR1S schemes.
VRTs a e me hods ha aim a educing he a iance o esul s o a gi en numbe o
eplica ions. This means ha o he same con idence le el, he applica ion o VRTs may
allow educing he numbe o eplica ions and hence, he compu a ional e o . Se e al
VRTs exis , such as he common andom numbe s (Sch uben,2010), an i he ic a ia es
(Hamme sley and Mo on,1956), con ol a ia es (Glynn and Szech man,2000), impo -
ance sampling (Glynn and Igleha ,1989) and s a i ied sampling (McKay e al.,2000).
The i s is he mos simple and widely used VRT and consis s on applying he same se s
o andom numbe s eams o e e y solu ion. I his is applied o he comple e op imiza ion
p ocedu e, we a e in he p esence o CR1S. S ill, i can be applied o each i e a ion sepa-
a ely, wi hin a DR1S scheme. Fo ins ance, in a single-solu ion based MH all neighbou s
in a gi en i e a ion would be e alua ed wi h he same ealiza ions, bu hese would change
in he ollowing i e a ions.
In addi ion o VRTs, SSM p inciples may be applied in SE app oaches. The idea o
disca ding simula ion eplica ions o solu ions which quickly p o e (s a is ically) o be o
poo quali y is e y a ac i e. I is no necessa y hough ha he s a is ical p oo in ol es
a good con idence le el (such as 90% o highe ). Indeed, i may e en be desi able wo king
wi h a low le el, in o de o p omo e di e si ica ion in he sea ch p ocedu e. S ill, solu ions
o oo low quali y would be quickly ejec ed, sa ing compu a ional ime.
4.5. Conclusion and u u e lines o esea ch 99
Op imiza ion highly depends on simula ionaOSI
Bo h need each o he ecu en lybASO
One needs he o he oncecSSO
Simula ion highly depends on op imiza iondSOI
How equen ly does one componen need he eedback o he o he ?2Hiea chical S uc u e
How di icul is i o concei e a p io i a use ul analy ical model?1
How expensi e is simula ion?1.1
Imp ac icable/impossiblea
P ac icable, bu he model needs o be u he enhancedbAME
P ac icable, e en be o e any simula ion eedbackcSG
Modes a.a EF
Ve y expensi ea.b SMC
Simula ion Pu pose
How ha d is i o a el in bo h solu ion and p obabili y spaces
and how impo an is con e gence/di e si ica ion in he o me ?
4Sea ch Scheme
Disc e e decision spacea
Con inuous decision spaceb
Simple combina o ial p oblema.a E
Di icul combina o ial p oblema.b DH
Linea (o simple nonlinea ) p oblemb.a E
Wha a e he op imiza ion p oblem cha ac e is ics?3Sea ch Me hod
Complex nonlinea p oblem and exis ence o de i a i esb.b DBH
Complex nonlinea p oblem and inexis ence o de i a i es OCHb.c
Mixed decision spacec
Simple combina o ial linea (o simple nonlinea ) p oblemc.a E
Di icul combina o ial linea (o simple nonlinea ) p oblemc.b DH + E
Di icul combina o ial complex nonlinea p oblem DH + CHc.d
Simple combina o ial complex nonlinea p oblemc.c E + CH
Same di icul y and/o di e si ica ion is e y impo an a1R1S
Mo e di icul in solu ion space and/o di e si ica ion is impo an bDR1S
Mo e di icul in solu ion space and/o con e gence is c i icalcCR1S
Mo e di icul in he p obabili y space (o de e minis ic p oblem)d1RMS
Figu e 4.4: E iden connec ions be ween he p oblem cha ac e is ics and he classi ying
dimensions and ca ego ies.
4.5. Conclusion and u u e lines o esea ch
In he S-O esea ch ield he dicho omy be ween “simula ion-based” and “op imiza ion-
based” app oaches is anishing. Some o he main s eams o me hods may in some si ua-
ions appea qui e simila , as p e iously shown. Thus, he choice o he main app oach may
no be s aigh o wa d and equi e he conside a ion o me hods ha a e di e en in spi i .
100 Chap e 4. Simula ion-op imiza ion axonomy
Indeed, he bounda ies o hese me hods can be uzzy. Some ca ego iza ion is impo an
hough. I is also c ucial ha i co e s all S-O app oaches, so ha a comp ehensi e iew is
ob ained. Tha was he aim o ou axonomy.
The classi ica ions used so a in he li e a u e ocused on pa icula s eams o me h-
ods and ypically u ilized one single c i e ion. We p opose a classi ica ion which ela es
mul iple dimensions and pe spec i es in an a emp o g asp he essence o S-O me hods
and disco e new oppo uni ies o he c oss- e iliza ion o ideas and he explo a ion o
new app oaches. Two new key c i e ia we e conside ed, which g ea ly con ibu ed o he
discussion. The o ganiza ion o c i e ia in wo ma ices allowed he examina ion o bo h
he in e ac ion be ween simula ion and op imiza ion and he sea ch design. We we e also
able o explo e he cha ac e is ics o each me hod and dis inguish i ually all o hem in
a leas one dimension. Addi ionally, common ends along di e en axes we e iden i ied.
The discussion o each classi ying dimension has esul ed in some guidelines which can be
used when selec ing app op ia e S-O designs o gi en p oblems.
The a ie y o me hods e iewed in Sec ion 4.2 e eals an immense ange o possibil-
i ies o combining simula ion and op imiza ion. Some me hods ha e a clea ly speci ied
p ocedu e, while o he s a e mo e gene al app oaches. Ne e heless, esea ch ac i i ies in
his p omising a ea a e likely o inc ease signi ican ly in he nea u u e. We p o ide he e
some di ec ions o u he esea ch:
•Embedding ideas om RSbin o MH amewo ks. The o me a e e y ocused on he
s ochas ici y issues, mo ing simul aneously in bo h solu ion and p obabili y spaces.
The la e con ain a la ge a ie y o di e si ica ion and in ensi ica ion s a egies. An
in e es ing amewo k is p oposed by And adó i and P udius (2009), whe e explo-
a ion, exploi a ion and es ima ion a e ca e ully balanced. Ano he example is he
wo k o Xu e al. (2010) whose me hod consis s o a global-sea ch phase, ollowed
by a local sea ch phase, and ending wi h a “clean-up” (selec ion o he bes ) phase.
Ne e heless, hese app oaches a e s ill in hei in ancy.
•Applying VRTs in DR1S/CR1S schemes. As p e iously discussed, hese echniques
may allow educing compu a ional e o when pe o ming simula ion eplica ions.
Con a y o wha migh appea , VRTs can be applied no only in SE app oaches, bu
also in AME. Indeed, e en when he aim o simula ion is no e alua ing solu ions, he
eedback o he o me may ake ad an age o a educed a iance o be e enhance
he analy ical model.
•Using SSM p inciples in o he SE app oaches. As opposed o he p e ious poin , his
idea can only be employed in SE app oaches. The inc ease o e iciency ha esul
om SSM may imp o e he pe o mance o DH me hods, such as RS and MH. This
p omising combina ion is being explo ed bo h in he li e a u e (e.g. Óla sson (2004))
and in p ac ice (e.g. by Op Ques ). Ne e heless, he e a e s ill some ques ions
o be answe ed. Fo ins ance, Almede and Ha l (2013) show ha in hei case a
s a is ical selec ion wi h 95% o con idence pe o ms wo se han a sample a e age
o 10 eplica ions, since di e si ica ion is spoiled in he o me . The e o e, he choice
o a good con idence le el is s ill an open ques ion.
4.A. Lis o ac onyms 101
•Filling gaps in he ma ices. Two ob ious gaps in he In e ac ion ma ix exis : SMC-
SOI and AME-OSI. The o me could be some kind o hyb idiza ion be ween GMM
and ADP, whe e du ing simula ion a global me amodel would be cons uc ed (ins ead
o simply ein o cing a unc ion). The la e migh esul in a p og essi e e inemen
s a egy, whe e an analy ical model would be e ined du ing i s esolu ion. Rega ding
he Sea ch Design ma ix blanks, CR1S schemes could be an in e es ing app oach
o me aheu is ics wi h di icul con e gence (which is mo e likely in he s ochas ic
se ing).
To conclude, ou axonomy ully classi ies any S-O me hod, including hyb idiza ions.
The e o e, i can con ibu e o a be e communica ion in he scien i ic communi y. Fu u e
e iews can use he dimensions he e desc ibed o classi y addi ional S-O me hods o ex end
hem o pa icula s eams o esea ch. Fo ins ance, in ROSA app oaches i may be
impo an o dis inguish di e en e inemen s a egies and s opping c i e ia. Mo e in-
dep h s udies may also allow be e cha ac e izing he ela ionship be ween S-O p oblems
and me hods (o s a egies). The e is a wide a enue o esea ch in simula ion-op imiza ion,
pa icula ly ega ding he s udy o speci ic applica ion ields.
Appendix 4.A Lis o ac onyms
Gene al: Simula ion-op imiza ion me hods:
OR Ope a ions Resea ch SSM S a is ical Selec ion Me hods
SO Simula ion Op imiza ion R&SRanking and Selec ion
S-O Simula ion-Op imiza ion MCP Mul iple Compa ison P ocedu es
SbO Simula ion by Op imiza ion MH Me aheu is ics
DES Disc e e E en Sys em GA Gene ic Algo i hm
MP Ma hema ical P og amming MMH Memo y-based Me aheu is ics
Simula ion pu poses: RS Random Sea ch
SE Solu ion E alua ion SA S ochas ic App oxima ion
EF E alua ion Func ion SPO Sample Pa h Op imiza ion
SMC Su oga e Model Cons uc ion GMM Global Me amodel-based Me hods
AME Analy ical Model Enhancemen LMM Local Me amodel-based Me hods
SG Solu ion Gene a ion RSM Response Su ace Me hodology
Hie a chical s uc u es: GSM G adien Su ace Me hods
OSI Op imiza ion wi h Simula ion-based I e a ions SMF Su oga e Managemen F amewo k
ASO Al e na e Simula ion-Op imiza ion ADP App oxima e Dynamic P og amming
SSO Sequen ial Simula ion-Op imiza ion RST Re e se Simula ion Technique
SOI Simula ion wi h Op imiza ion-based I e a ions RSRO Re ospec i e Simula ion Response Op imiza ion
Sea ch me hods: SPDE S ochas ic P og amming De e minis ic Equi alen
EExac SAA Sample A e age App oxima ion
CH Con inuous-space Heu is ic ROSA Recu si e Op imiza ion-Simula ion App oach
DBH De i a i e-Based Heu is ic FEA Func ion Es ima ion based App oach
OCH O he Con inuous-space Heu is ic OSIR Op imiza ion-based Simula ion I e a i e Re inemen
DH Disc e e-space Heu is ic SCS Solu ion Comple ion by Simula ion
Sea ch schemes: IOS I e a i e Op imiza ion-based Simula ion
1R1S One ealiza ion o each solu ion S ochas ic echniques:
DR1S Di e en ealiza ions o each solu ion VRT Va iance Reduc ion Technique
CR1S Common ealiza ions o each solu ion CRN Common Random Numbe s
1RMS One ealiza ion o mul iple solu ions
102 Bibliog aphy
Bibliog aphy
Ya uz Aca , Suk an N. Kadipasaoglu, and Jamison M. Day. Inco po a ing unce ain y
in op imal decision making: In eg a ing mixed in ege p og amming and simula ion o
sol e combina o ial p oblems. Compu e s &Indus ial Enginee ing, 56(1):106–112,
2009.
E inç Albey and Ümi Bilge. A hie a chical app oach o ms planning and con ol wi h
simula ion-based capaci y an icipa ion. In e na ional Jou nal o P oduc ion Resea ch,
49(11):3319–3342, 2011.
A ianna Al ie i and And ea Ma a. Ma hema ical p og amming o mula ions o app ox-
ima e simula ion o mul is age p oduc ion sys ems. Eu opean Jou nal o Ope a ional
Resea ch, 219(3):773–783, 2012.
A ianna Al ie i and And ea Ma a. Ma hema ical p og amming ime-based decomposi ion
algo i hm o disc e e e en simula ion. Eu opean Jou nal o Ope a ional Resea ch, 231
(3):557–566, 2013.
Talal M Alkhamis, Mohamed A Ahmed, and Vu Kim Tuan. Simula ed annealing o dis-
c e e op imiza ion wi h es ima ion. Eu opean Jou nal o Ope a ional Resea ch, 116(3):
530–544, 1999.
Ch is ian Almede and Richa d F. Ha l. A me aheu is ic op imiza ion app oach o a eal-
wo ld s ochas ic lexible low shop p oblem wi h limi ed bu e . In e na ional Jou nal
o P oduc ion Economics, 145(1):88–95, 2013. ISSN 0925-5273.
Ch is ian Almede , Ma ga e ha P eusse , and Richa d Ha l. Simula ion and op imiza ion
o supply chains: al e na i e o complemen a y app oaches? OR Spec um, 31:95–119,
2009.
A. Amme i, W. Hachicha, H. Chabchoub, and F. Masmoudi. A comp ehensi e li e a u e
e iew o mono-objec i e simula ion op imiza ion me hods. Ad ances in P oduc ion
Enginee ing &Managemen , 6:291–302, 2011.
S. And adó i . Chap e 20 an o e iew o simula ion op imiza ion ia andom sea ch. In
Shane G. Hende son and Ba y L. Nelson, edi o s, Simula ion, olume 13 o Handbooks
in Ope a ions Resea ch and Managemen Science, pages 617–631. Else ie , 2006.
Sig ún And adó i and And ei A. P udius. Balanced explo a i e and exploi a i e sea ch
wi h es ima ion o simula ion op imiza ion. INFORMS J. on Compu ing, 21(2):193–
208, 2009. ISSN 1526-5528.
Jay Ap il, F ed Glo e , James P. Kelly, and Manuel Laguna. Simula ion-based op imiza-
ion: p ac ical in oduc ion o simula ion op imiza ion. In P oceedings o he 2003 Win-
e Simula ion Con e ence, pages 71–78, 2003. ISBN 0-7803-8132-7.
Bibliog aphy 103
J. Asmundsson, R.L. Ra din, and R. Uzsoy. T ac able nonlinea p oduc ion planning mod-
els o semiconduc o wa e ab ica ion acili ies. Semiconduc o Manu ac u ing, IEEE
T ansac ions on, 19(1):95–111, 2006.
Fa had Azadi a . Simula ion op imiza ion me hodologies. In P oceedings o he 31s
con e ence on Win e simula ion: Simula ion—a b idge o he u u e-Volume 1, pages
93–100, 1999.
June-Young Bang and Yeong-Dae Kim. Hie a chical p oduc ion planning o semiconduc-
o wa e ab ica ion based on linea p og amming and disc e e-e en simula ion. IEEE
T ansac ions on Au oma ion Science and Enginee ing, 7(2):326–336, 2010.
Je y Banks, John S. Ca son, Ba y L. Nelson, and Da id M. Nicol. Disc e e-E en Sys em
Simula ion. P en ice Hall, 3 edi ion, 2000.
Russell R. Ba on and Ma in Meckesheime . Chap e 18 me amodel-based simula ion op-
imiza ion. In Shane G. Hende son and Ba y L. Nelson, edi o s, Simula ion, olume 13
o Handbooks in Ope a ions Resea ch and Managemen Science, pages 535–574. Else-
ie , 2006.
C. Blum and A. Roli. Me aheu is ics in combina o ial op imiza ion: O e iew and con-
cep ual compa ison. ACM Compu . Su ., 35:268–308, 2003. ISSN 0360-0300.
A. J. Booke , J. E. Dennis, P. D. F ank, D. B. Se a ini, V. To czon, and M. W. T osse . A
igo ous amewo k o op imiza ion o expensi e unc ions by su oga es. S uc u al
and Mul idisciplina y Op imiza ion, 17:1–13, 1999.
Da id D B iggs. A hyb id analy ical/simula ion modeling app oach o planning and op i-
mizing mass ac ical ai bo ne ope a ions. Technical epo , DTIC Documen , 1995.
Yolanda Ca son and Anu Ma ia. Simula ion op imiza ion: me hods and applica ions. In
P oceedings o he 1997 Win e Simula ion Con e ence, pages 118–126, 1997.
Wai Kin Vic o Chan and Lee Sch uben. Op imiza ion models o disc e e-e en sys em
dynamics. Ope a ions Resea ch, 56(5):1218–1237, 2008.
Ma co Do igo and Ch is ian Blum. An colony op imiza ion heo y: A su ey. Theo e ical
Compu e Science, 344(2):243–278, 2005.
M. C. Fu. Simula ion op imiza ion. In P oceedings o he 2001 Win e Simula ion Con e -
ence, olume 1, pages 53–61, 2001.
M. C. Fu, F. W. Glo e , and J. Ap il. Simula ion op imiza ion: a e iew, new de elopmen s,
and applica ions. In P oceedings o he 2005 Win e Simula ion Con e ence, pages 83–
95, 2005.
Michael C. Fu. Op imiza ion ia simula ion: A e iew. Annals o Ope a ions Resea ch,
53:199–247, 1994.
104 Bibliog aphy
Michael C. Fu. Fea u e a icle: Op imiza ion o simula ion: Theo y s. p ac ice. IN-
FORMS J. on Compu ing, 14(3):192–215, 2002.
Pe e W. Glynn and Donald L. Igleha . Impo ance sampling o s ochas ic simula ions.
Managemen Science, 35(11):1367–1392, 1989.
Pe e W. Glynn and Robe o Szech man. Some new pe spec i es on he me hod o con ol
a ia es. In K.T. Fang, F.J. Hicke nell, and H. Niede ei e , edi o s, Mon e Ca lo and
Quasi-Mon e Ca lo Me hods 2000, page 27–49. Sp inge -Ve lag, 2000.
Abhiji Gosa i. Simula ion-Based Op imiza ion: Pa ame ic Op imiza ion Techniques and
Rein o cemen Lea ning. Kluwe Academic Publishe s, 2003.
G.A. G ay, K. Fowle , and J.D. G i in. Hyb id op imiza ion schemes o simula ion-based
p oblems. P ocedia Compu e Science, 1(1):1349–1357, 2010. ISSN 1877-0509.
G. Gu kan, A. Y. Ozge, and T. M. Robinson. Sample-pa h op imiza ion in simula ion. In
P oceedings o he 1994 Win e Simula ion Con e ence, pages 247–254, 1994.
J. M. Hamme sley and K. W. Mo on. A new mon e ca lo echnique: an i he ic a ia es.
Ma hema ical P oceedings o he Camb idge Philosophical Socie y, 52(03):449–475,
1956.
J. Han, J. A. Mille , and G. A. Sil e . Sop : On ology o simula ion op imiza ion o
scien i ic expe imen s. In P oceedings o he 2011 Win e Simula ion Con e ence, pages
2909–2920, 2011.
F Hanssmann, G Di u , W Fische , and S Rame . Analy ical sea ch models o op imum
seeking in simula ions. Ope a ions Resea ch Spek um, 2(2):91–97, 1980.
Ke in Healy and Lee W. Sch uben. Re ospec i e simula ion esponse op imiza ion. In
P oceedings o he 1991 Win e Simula ion Con e ence, pages 901–906, 1991.
Y. Ho, Leyuan Shi, Liyi Dai, and Wei-Bo Gong. Op imizing disc e e e en dynamic sys-
ems ia he g adien su ace me hod. Disc e e E en Dynamic Sys ems, 2:99–120, 1992.
L Je Hong, Ba y L Nelson, and Jie Xu. Speeding up compass o high-dimensional
disc e e op imiza ion ia simula ion. Ope a ions Resea ch Le e s, 38(6):550–555, 2010.
Jiaqiao Hu, Michael C Fu, and S e en I Ma cus. A model e e ence adap i e sea ch me hod
o s ochas ic global op imiza ion. Communica ions in In o ma ion &Sys ems, 8(3):
245–276, 2008.
D.F. I dem, N.B. Kaca , and R. Uzsoy. An expe imen al s udy o an i e a i e simula ion-
op imiza ion algo i hm o p oduc ion planning. In P oceedings o he 2008 Win e
Simula ion Con e ence, pages 2176–2184, 2008.
June Young Jung, Ga y Blau, Joseph F. Pekny, Gin a as V. Reklai is, and Da id E e sdyk.
A simula ion based op imiza ion app oach o supply chain managemen unde demand
unce ain y. Compu e s &Chemical Enginee ing, 28(10):2087–2106, 2004.
Bibliog aphy 105
And é Khu i and Siuli Mukhopadhyay. Response su ace me hodology. Wiley In e disci-
plina y Re iews: Compu a ional S a is ics, 2(2):128–149, 2010.
Jack P.C. Kleijnen, Wim an Bee s, and Inneke an Nieuwenhuyse. Cons ained op i-
miza ion in expensi e simula ion: No el app oach. Eu opean Jou nal o Ope a ional
Resea ch, 202(1):164–174, 2010.
A.J. Kleyweg , A. Shapi o, and T. Homem-De-Mello. The sample a e age app oxima ion
me hod o s ochas ic disc e e op imiza ion. SIAM Jou nal on Op imiza ion, 12(2):479–
502, 2002.
Ha old J Kushne and Geo ge Yin. S ochas ic app oxima ion and ecu si e algo i hms and
applica ions, olume 35. Sp inge , 2003.
Ped o La añaga and Jose A Lozano. Es ima ion o dis ibu ion algo i hms: A new ool o
e olu iona y compu a ion, olume 2. Sp inge , 2002.
Young Hae Lee, Kyoung Jong Pa k, and Yun Bae Kim. Single un op imiza ion using he
e e se-simula ion me hod. In P oceedings o he 1997 Win e Simula ion Con e ence,
pages 187–193, 1997.
Seok Jin Lim, Suk Jae Jeong, Kyung Sup Kim, and Myon Woong Pa k. A simula ion
app oach o p oduc ion-dis ibu ion planning wi h conside a ion gi en o eplenishmen
policies. The In e na ional Jou nal o Ad anced Manu ac u ing Technology, 27:593–
603, 2006.
M. D. McKay, R. J. Beckman, and W. J. Cono e . A compa ison o h ee me hods o
selec ing alues o inpu a iables in he analysis o ou pu om a compu e code. Tech-
nome ics, 42(1):55–61, 2000. ISSN 0040-1706.
Richa d L. Nolan and Michael G. So e eign. A ecu si e op imiza ion and simula ion
app oach o analysis wi h an applica ion o anspo a ion sys ems. Managemen Science,
18(12):B676–B690, 1972.
S. Óla sson. Two-s age nes ed pa i ions me hod o s ochas ic op imiza ion. Me hodology
And Compu ing In Applied P obabili y, 6(1):5–27, 2004.
Sigu du Óla sson. Chap e 21 me aheu is ics. In Shane G. Hende son and Ba y L. Nel-
son, edi o s, Simula ion, olume 13 o Handbooks in Ope a ions Resea ch and Manage-
men Science, pages 633–654. Else ie , 2006.
R. Pasupa hy and S. G. Hende son. A es bed o simula ion-op imiza ion p oblems. In
P oceedings o he 2006 Win e Simula ion Con e ence, pages 255–263, 2006.
Raghu Pasupa hy. On choosing pa ame e s in e ospec i e-app oxima ion algo i hms o
s ochas ic oo inding and simula ion op imiza ion. Ope a ions Resea ch, 58(4-Pa -1):
889–901, 2010.
106 Bibliog aphy
Hen i Pie e al and Jean Luc Pa is. F om ‘simula ion op imiza ion’ o ‘simula ion con igu-
a ion’o sys ems. Simula ion Modelling P ac ice and Theo y, 11(1):5–19, 2003.
E ica L. Plambeck, Bo -Ruey Fu, S ephen M. Robinson, and Rajan Su i. Sample-pa h
op imiza ion o con ex s ochas ic pe o mance unc ions. Ma hema ical P og amming,
75:137–176, 1996.
Wa en B Powell. Wha you should know abou app oxima e dynamic p og amming. Na al
Resea ch Logis ics (NRL), 56(3):239–249, 2009.
Reu en Y Rubins ein and Di k P K oese. The c oss-en opy me hod: a uni ied app oach o
combina o ial op imiza ion, Mon e-Ca lo simula ion and machine lea ning. Sp inge ,
2004.
And zej Ruszczynski and Alexande Shapi o. S ochas ic p og amming models. In
A. Ruszczynski and A. Shapi o, edi o s, S ochas ic P og amming, olume 10 o Hand-
books in Ope a ions Resea ch and Managemen Science, pages 1–64. Else ie , 2003.
Nikolaos V. Sahinidis. Op imiza ion unde unce ain y: s a e-o - he-a and oppo uni ies.
Compu e s &Chemical Enginee ing, 28:971–983, 2004.
Tjende a San oso, Shabbi Ahmed, Ma c Goe schalckx, and Alexande Shapi o. A s ochas-
ic p og amming app oach o supply chain ne wo k design unde unce ain y. Eu opean
Jou nal o Ope a ional Resea ch, 167(1):96–115, 2005.
Lee W. Sch uben. Ma hema ical p og amming models o disc e e e en sys em dynamics.
In P oceedings o he 32nd con e ence on Win e simula ion, pages 381–385, 2000.
Lee W. Sch uben. Common Random Numbe s. John Wiley & Sons, Inc., 2010. ISBN
9780470400531.
J. G. Shan hikuma and R. G. Sa gen . A uni ying iew o hyb id simula ion/analy ic
models and modeling. Ope a ions Resea ch, 31(6):1030–1052, 1983.
Leyuan Shi and S. Óla sson. Nes ed pa i ions me hod o s ochas ic op imiza ion. Me hod-
ology and Compu ing in Applied P obabili y, 2(3):271–291, 2000.
Dha mashanka Sub amanian, Joseph F Pekny, and Gin a as V Reklai is. A simula ion-
op imiza ion amewo k o add essing combina o ial and s ochas ic aspec s o an &d
pipeline managemen p oblem. Compu e s &Chemical Enginee ing, 24(2):1005–1011,
2000.
Rajan Su i and Ying Ta Leung. Single un op imiza ion o a siman model o closed loop
lexible assembly sys ems. In P oceedings o he 1987 Win e Simula ion Con e ence,
pages 738–748, 1987.
James R. Swishe , Sheldon H. Jacobson, and En e Yücesan. Disc e e-e en simula ion
op imiza ion using anking, selec ion, and mul iple compa ison p ocedu es: A su ey.
ACM T ans. Model. Compu . Simul., 13(2):134–154, 2003.
Bibliog aphy 107
Eylem Tekin and Ihsan Sabuncuoglu. Simula ion op imiza ion: A comp ehensi e e iew
on heo y and applica ions. IIE T ansac ions, 36(11):1067–1081, 2004.
Vi ginia To czon. On he con e gence o pa e n sea ch algo i hms. SIAM J. on Op imiza-
ion, 7(1):1–25, 1997.
Tu Hoang T uong and Fa had Azadi a . Simula ion op imiza ion in manu ac u ing analy-
sis: simula ion based op imiza ion o supply chain con igu a ion design. In P oceedings
o he 2003 Win e Simula ion Con e ence, pages 1268–1275, 2003.
Rosema y H. Wild and Joseph J. Pigna iello, J . Finding s able sys em designs: a e e se
simula ion echnique. Commun. ACM, 37(10):87–98, 1994.
Jie Xu, Ba y L Nelson, and JEFF Hong. Indus ial s eng h compass: A comp ehensi e
algo i hm and so wa e o op imiza ion ia simula ion. ACM T ansac ions on Modeling
and Compu e Simula ion (TOMACS), 20(1):1–29, 2010.
Jie Xu, Ba y L Nelson, and L Je Hong. An adap i e hype box algo i hm o high-
dimensional disc e e op imiza ion ia simula ion p oblems. INFORMS Jou nal on Com-
pu ing, 25(1):133–146, 2013.
114 Chap e 5. Simula ion-op imiza ion o p oac i e planning and scheduling
o e he eac o and machine ime g ids). The de ined ime slo s a e hen used o de e -
mine eac o ’s p oduc ion, which also depends on i s (maximum and minimum) a es and
a yield ac o – see (5.3). The ma e ial balance is es ablished by (5.4), whe eas i s s o age
limi a ions a e en o ced by (5.5).
5.3.2 Second s age (machine)
Indices and pa ame e s:
j,kIndices o p oduc s (j,k∈[K]={1,...,K})
slk j P oduc los in a changeo e om p oduc k o j
s k j Time los in a changeo e om p oduc k o j
bjPe cen age o ma e ial in p oduc j
pjMinimum p ocessing ime o p oduc j
Vmach
min Machine’s minimum a e ( ela i e o i s maximum)
MjUppe bound on he lo size o p oduc j
mjMinimum lo size o p oduc j
dj Demand o p oduc jin pe iod
l Va iable p oduc ion loss
Yj0
1 i he machine is se up o p oduc ja he beginning o he planning ho izon,
0 o he wise.
I+
0Ini ial in en o y o o p oduc j
I−
0Ini ial backlog o o p oduc j
Decision a iables:
Yjs
1 i he machine is se up o p oduc jin slo s,
0 o he wise.
Zk js
1 i a changeo e om p oduc k o j akes place a he beginning o slo s,
0 o he wise.
Xjs Quan i y o p oduc jp oduced in slo s
I+
j, In en o y o p oduc ja he end o pe iod
I−
j, Quan i y o p oduc jbacklogged a he end o pe iod
X
j
bj·
Xjs +X
k
slk j ·Zk js
=Oma
s,s∈[S] (5.6)
Vmach
min ·Ns≤X
j
pj·Xjs +X
k
s k j ·Zk js
≤Ns,s∈[S] (5.7)
(1− l)·X
s∈[S ]
Xjs +I+
j, −1−I−
j, −1=dj +I+
j −I−
j ,j∈[K], ∈[T] (5.8)
Xjs ≤Mj·Yjs,j∈[K],s∈[S] (5.9)
X
j
Yjs =1,s∈[S] (5.10)
5.3. Mixed in ege p og amming model 115
X
k
Zjks =Yj,s−1,j∈[K],s∈[S] (5.11)
X
k
Zk js =Yjs,j∈[K],s∈[S] (5.12)
The p oduc ion o inal p oduc s is linked o ma e ial consump ion wi h cons ain s
(5.6) and cons ained by machine’s minimum and maximum a es wi h (5.7). No e he
sequence-dependen se up imes and losses in hese equa ions. Indeed, du ing change o e s
he machine keeps pulling ma e ial om he ank. The p oduc s p ocessed on his s age
migh inco po a e o he ma e ials a he han ha s ocked in he ank (e.g. di e en ypes
o pulp, in he pulp and pape indus y). Pa ame e bjgi es enough lexibili y o ep esen
di e en en i onmen s. The p ocessing ime pjused in (5.7) co esponds o machine’s
maximum a e. The e o e, he igh -hand side includes only he leng h o he slo , while
he le -hand side mul iplies i by he minimum a e (as a pe cen age o he maximum).
Cons ain s (5.8) model he demand sa is ac ion, whe e p oduc ion su e s an addi ional
loss (beyond se up losses), which depends on he amoun p oduced. Cons ain s (5.9) link
p oduc ion o se ups, (5.10) en o ce only one p oduc pe pe iod, and (5.11) and (5.12) link
se ups o changeo e s, gua an eeing he consis ency o he p oduc ion sequence h oughou
he ho izon.
5.3.3 Ra es a ia ion
Pa ame e s:
V eac
0Ra e o he eac o a he beginning o he planning ho izon
Vmach
0Ra e o he machine a he beginning o he planning ho izon
Decision a iables:
V eac
sRa e o he eac o in slo s
δ eac+
sδ eac−
sPosi i e (nega i e) a ia ion o eac o ’s a e in slo s
Vmach
sRa e o he machine in slo s
δmach+
sδmach−
sPosi i e (nega i e) a ia ion o machine’s a e in slo s
Xma
s=α·V eac
s·Ns,s∈[S] (5.13)
V eac
s−V eac
s−1=δ eac+
s−δ eac−
s,s∈[S] (5.14)
X
j
pj·Xjs +X
k
s k j ·Zk js
=Vmach
s·Ns,s∈[S] (5.15)
Vmach
s−Vmach
s−1=δmach+
s−δmach−
s,s∈[S] (5.16)
To measu e a es a ia ion (δ eac+
s,δ eac−
s,δmach+
sand δmach−
s), he implici o mula ion
in equa ions (5.3) and (5.7) is no su icien . Explici decision a iables (V eac
sand Vmach
s)
a e needed. Howe e , hose equa ions become non-linea , since he explici a e a iables
a e mul iplied by slo s’ leng hs – see cons ain s (5.13) and (5.15). This issue has o be
add essed by he solu ion me hod (see nex sec ion).
116 Chap e 5. Simula ion-op imiza ion o p oac i e planning and scheduling
5.3.4 Objec i e unc ion
Pa ame e s:
bc Backlog cos pe uni and pe iod
sck j Se up cos o changing om p oduc k o j
c Cos o changing eac o ’s p oduc ion a e
mc Cos o changing machine’s p oduc ion a e
po Bene i (nega i e cos ) o p oducing inal p oduc s
minX
j
X
bc ·I−
j +X
j
X
k
X
s
sck j ·Zk js +X
s
c ·δ eac+
s+δ eac−
s
+X
s
mc ·δmach+
s+δmach−
s−X
j
X
s
po ·Xjs
(5.17)
The objec i e is o minimize a cos unc ion which comp ises he o de s backlog cos s,
machine sequence-dependen se up cos s and penal ies o changing p oduc ion a es (which
cause wea o equipmen and b eak plan ’s s abili y in he eac o and machine). In addi ion,
he maximiza ion o he plan ’s ou pu is p omo ed wi h a nega i e e m. This las c i e ia
seeks o make he mos o ins alled (capi al in ensi e) equipmen , educing he indus ial
cos pe p oduc uni .
5.4. Solu ion me hod: VND-LP
The p oblem o mula ed in he p e ious sec ion has bo h bina y and con inuous a iables
and is u he complica ed by nonlinea i y ( he mul iplica ion o he slo s’ leng hs by p o-
duc ion a es). Gi en ha o la ge eal-wo ld ins ances exac sol e s ail o p oduce good
quali y solu ions wi hin easonable ime, e en o a linea ized e sion o he model, we ely
on heu is ic me hods.
The solu ion me hod is based on ha p oposed by Figuei a e al. (2013b). We combine
a me aheu is ic which ocuses on he bina y a iables and an exac sol e o he con in-
uous pa . The me aheu is ic hus i e a es h ough di e en se up pa e ns ( he solu ion
ep esen a ion, consis ing only o he se up and changeo e a iables) and o each pa e n
(each solu ion isi ed), i calls he exac sol e o decode he pa e n in o a inal plan. To
a oid he nonlinea i y o his p oblem, he decoding is pe o med in wo s eps:
1. he linea p og amming (LP) sol e is called wi hou he a es a ia ion pa – equa-
ions (5.13)-(5.16);
2. he a es a ia ion pa is added o he model, he slo s’ leng hs Nsa e ixed ( o he
alues ob ained in s ep 1) and i is sol ed again.
This decoding p ocedu e is mo e expensi e han ha o Figuei a e al. (2013b), bu also
mo e accu a e. Ne e heless, he numbe o solu ions isi ed will be educed. Two o he
ac o s will also con ibu e o his educ ion. Fi s , simula ion will consume addi ional ime.
Second, he use o he dual eop imiza ion p ocedu e will no longe be possible, since he
5.5. Disc e e-e en simula ion model 117
VND
Decode
Sol e
Op imiza ion Algo i hm
LP
se up pa e n
Figu e 5.2: Op imiza ion algo i hm: he VND i e a es h ough di e en se up pa e ns,
whe eas an exac sol e is called o op imize he con inuous a iables o a linea p og am.
solu ion o he analy ical pa may wo sen, e en o be e (mo e obus ) plans. The e o e,
he pe u ba ion o he o iginal a iable neighbou hood sea ch (VNS) is disca ded he e and
he me hod emains a a iable neighbou hood descen (VND). This me hod is s ill able o
escape om local op ima, since i al e na es be ween di e en neighbou hood s uc u es.
Figu e 5.2 exhibi s he main blocks o he algo i hm.
5.5. Disc e e-e en simula ion model
The analy ical model p e iously p esen ed does no accoun o p ocess a iabili y o dis-
u bances, since all he pa ame e s a e de e minis ic. These s ochas ic elemen s a e ad-
d essed now in a simula ion model, which is used o analyse he dynamics o he imple-
men a ion o p oduc ion plans. These dynamics, mainly hose wi h espec o dis u bances,
canno be p ope ly e alua ed wi h (s a ic) Mon e Ca lo simula ions. The e o e, we chose
o build a dynamic simula ion model.
In dynamic models, ime can be ep esen ed in a con inuous o disc e e manne . The
p ocess indus ies a e cha ac e ized by con inuous ma e ials, whose s a e changes con inu-
ously along he ime, especially in con inuous sys ems like he one s udied he e. Howe e ,
a he le el o de ail equi ed (and desi able) by he planning p ocess, he sys em can be
seen as changing i s s a e a disc e e poin s in ime and hence, modelled by a disc e e-e en
app oach.
In ou model, e en s can be p oduc ion o de s o be execu ed, dis u bances beginning
o ending, uni s changing hei a e o p ocesses changing hei yield. These e en s hen
modi y he s a e o he p oduc ion uni s (en i ies), which is accomplished when he p oduc-
ion ask (ac i i y) is execu ed. The s a e o an en i y may consis o a gi en quan i y o a
speci ic p oduc being p oduced, a speci ied p oduc ion a e o simply a ce ain in en o y
le el.
A gene al o e iew o he simula ion p ocess is p o ided in Figu e 5.3. A e , eading
he plan, p oduc ion o de s (each co esponding o a ime slo o he op imiza ion model)
a e gi en one a a ime, i s o he machine and hen o he eac o . Du ing his ime, dis-
u bances may appea in he machine. In ha case, he comple ion ime o he cu en slo
118 Chap e 5. Simula ion-op imiza ion o p oac i e planning and scheduling
P oduce he amoun o slo sin
he machine (subjec o
dis u bances and a iabili y)
Compu e eac o ’s p oduc ion
du ing ha window (subjec o
dis u bances and a iabili y)
s< S?
s← 1
s← s+ 1
E alua e objec i e unc ion and
anks iola ion
Compu e ank le els in e e y
ansi ion o s a e (e en )
Yes
No
Read p oduc ion plan
Figu e 5.3: Simula ion p ocess lowcha .
will be ex ended, since he amoun s o be p oduced a e ixed, o p ope ly sa is y demand.
The ope a ion o he eac o uses hose ime pe iods (in o de o keep synch oniza ion), o
which gi en p oduc ion a es a e o be ollowed. Dis u bances may also a ise in he eac-
o . In addi ion, bo h he p oduc ion and consump ion o he ma e ial ha lows be ween
he wo p oduc ion uni s is subjec o a iabili y. The e o e, each pe iod was di ided in o
sub-pe iods, independen ly o he ime slo s, whe e hose s ochas ic pa ame e s assume pa -
icula alues. A he end o each i e a ion, he ank le els a e compu ed o e e y elapsed
e en . Thus, whene e a dis u bance s a ed o ended o a s ochas ic pa ame e changed i s
alue, he ank le el is e alua ed. In his way, we make su e ha any ank iola ion is aken
in o accoun . These iola ions, along wi h all he objec i es ha may ha e been impac ed
(such as p oduc ion and backlog), a e hen e u ned a he end o he simula ion.
To model he a iabili y and dis u bances, he ollowing pa ame e s we e used:
• eac o ’s p oduc ion yield and machine’s consump ion a e (αiand bji, espec i ely
– whe e iis he sub-pe iod);
• ime be ween ailu es and ime o epai o he eac o and machine ( b eac, eac,
b mach and mach, espec i ely).
In he p esence o s ochas ic pa ame e s, he simula ion model has o un mul iple imes
5.6. Hyb idizing simula ion and op imiza ion 119
and he esul s ha e o be agg ega ed, so ha one can ha e a ce ain con idence on hem.
The con idence le el is na u ally co ela ed o he numbe o simula ion eplica ions. How-
e e , he e a e echniques o educe he a iance o esul s wi hou inc easing he num-
be o simula ions (see Subsec ion 5.6.4). This is pa icula ly impo an o simula ion-
op imiza ion algo i hms, whe e he simula ion is execu ed i e a i ely.
The model was implemen ed in C++, since i was o mode a e complexi y. A gene al
pu pose p og amming language like C++ allows o a e y high compu a ional pe o -
mance, when compa ed o comme cial simula ion packages. In addi ion, i gi es mo e
lexibili y in he model implemen a ion. Fo ins ance, one has con ol o e he sampling
om he dis ibu ions, hence enabling he applica ion o a iance educ ion echniques.
5.6. Hyb idizing simula ion and op imiza ion
5.6.1 Simula ion pu pose
The simula ion model can be hyb idized wi h op imiza ion in di e en ways. The main S-
O app oaches o he li e a u e we e iden i ied and classi ied by Figuei a and Almada-Lobo
(2014). The mos dis inc i e aspec is he pu pose o simula ion in he whole p ocedu e.
The au ho s di ided his dimension in ou ca ego ies:
•E alua ion Func ion (EF), whe e simula ion e alua es e e y single solu ion isi ed
by an op imiza ion algo i hm;
•Su oga e Model Cons uc ion (SMC), whe e simula ion e alua ions a e used o c e-
a e a su oga e (analy ical) model;
•Analy ical Model Enhancemen (AME), whe e simula ion eedback is applied on he
e inemen o ex ension o a p oblem-speci ic analy ical model;
•Solu ion Gene a ion (SG), whe e simula ion compu es pa o he solu ion, using
op imiza ion o o he compu a ions.
The selec ion o he app op ia e app oach s ongly depends on he cha ac e is ics o
he p oblem. Fo small solu ion spaces and inexpensi e simula ions, EF should be he
igh choice, since i will always ely on mo e accu a e simula ion e alua ions o selec a
solu ion. As we mo e o he o he app oaches, he numbe o simula ions (and hence he
compu a ional ime) ends o dec ease and he conside a ion o assump ions ends o g ow.
SMC assumes he landscape o solu ions can be ep esen ed by some analy ical model,
AME assumes ha model is known a p io i (bu needs some e inemen s) and SG ha he
model is comple ely known.
In ou case he analy ical model needs he eedback om simula ion o gene a e obus
plans, he e o e SG is no sui able. On he o he hand, an EF design would esul in an
ex emely la ge amoun o simula ions. In spi e o he simula ion uns being e y as , hey
would be called hund eds o housands o imes in eal wo ld ins ances. Mo eo e , using
simula ion as he e alua ion unc ion o he VND (see Figu e 5.4a) would gi e eedback jus
o he op imiza ion o he se up pa e ns. Indeed, in o de o conside s ochas ic elemen s
120 Chap e 5. Simula ion-op imiza ion o p oac i e planning and scheduling
VND
Decode
Sol e
S-O Algo i hm
Simula ion
LP
se up pa e n
(a)
VND
Heu is ic
S-O Algo i hm
Simula ion
se up pa e n
con inuous
a iables
(b)
Figu e 5.4: Using simula ion as he e alua ion unc ion o : (a) he VND; (b) he whole
op imiza ion p ocess.
in he op imiza ion o he con inuous a iables, simula ion has o be inco po a ed in ha
op imiza ion (see Figu e 5.4b). The issue o his second app oach is ha all he linea
ela ionships be ween inpu and ou pu a iables a e los and he e icien LP sol e can
no longe be applied, being eplaced by a heu is ic. The same would happen wi h SMC
me hods, which in addi ion would no use he p oblem-speci ic neighbou hood s uc u es
o he VND.
The e o e, enhancing he linea p og amming model wi h he simula ion’s eedback
seems o be he mos app op ia e app oach. One key aspec o hese AME me hods is
he choice o he pa ame e s o be e ined in he analy ical model. Indeed, hey do no
ha e necessa ily o co espond o he s ochas ic pa ame e s lis ed in he p e ious sec ion,
especially because he e is no di ec co espondence o he TBFs and TTRs in he analy ical
model. The impac o hese dis u bances (and o he p ocess a iabili y) will be p ima ily
on he ank le el. Only i i eaches one o he limi s, hen i will o ce he p oduc ion
uni s o change hei a es (o e en o s op). Thus, we conside slacks in he ank, so ha
he sys em is able o accommoda e some a iabili y and dis u bances, wi hou he need o
d as ic ac ions. The conside a ion o slacks is indeed an indus ial p ac ice. Howe e , he e
hose slacks will be op imized wi h he simula ion’s eedback.
5.6.2 Re inemen p ocess
Depending on he p oblem and on he pa ame e s o be e ined, he e inemen p ocess can
be mo e o less complex. Fo ins ance, Albey and Bilge (2011) app oached a de e minis ic,
ye complex, p oduc ion sys em and used simula ion o check i he capaci y conside ed in
he analy ical model was app op ia e. In his case he e inemen is s aigh o wa d: he
capaci y is changed o ma ch he simula ion esul .
S ochas ic p oblems usually equi e a mo e sophis ica ed p ocess. Almede e al.
(2009) agg ega ed he simula ion esul s o mul iple eplica ions no by a e age, bu by
quan iles o 50, 70 and 90%. The 90%-quan ile esul ed be e o mos o he ins ances,
5.6. Hyb idizing simula ion and op imiza ion 121
bu in a ew o hem he 70% appea ed as mo e sui able. The S-O algo i hm was no able
howe e o al e na e be ween hese alues o e alua e he bes e inemen s a egy. The
quan ile was a ixed inpu pa ame e .
Jung e al. (2004) on he o he hand de ised an ou e op imiza ion laye , which applied
a g adien sea ch p ocedu e o e ine he sa e y s ock le els used in he analy ical model.
The e inemen o he sa e y s ocks o he di e en p oduc s and acili ies was pe o med
in an agg ega ed way, i.e. all he pa ame e s we e changed simul aneously in a speci ic
di ec ion (ei he inc easing o dec easing).
In ou case, we apply a heu is ic p ocess which e ines he uppe and lowe ank slacks
independen ly. Acco ding o he iola ions obse ed in he simula ion, one o he slacks
may inc ease while he o he dec eases. In his way, he slacks co ec ly weigh he a i-
abili y and dis u bances occu ing up and downs eam.
5.6.3 S-O s uc u es
The e inemen p ocess may be execu ed a di e en momen s. Th ee al e na i es a e he e
iden i ied (illus a ed in Figu e 5.5):
• e ining a he beginning o he op imiza ion (a pu e sequen ial p ocedu e);
• e ining a he end o he op imiza ion, in an i e a i e p ocess;
• e ining du ing op imiza ion (p og essi e e inemen ).
The i s s uc u e is he mos simple. Once he simula ion p ocess (including mul iple
eplica ions) is inished, i is no called again, gi ing way o he op imiza ion. This p oce-
du e is compu a ionally less expensi e han he o he app oaches. Howe e , i he op imal
slacks a e dependen on he solu ion (namely he p oduc ion sequence), he sequen ial ap-
p oach may no be e ec i e. In ha case ei he he i e a i e o he p og essi e me hods
would be mo e sui able. The la e seeks o sa e compu a ional ime by pe o ming simul-
aneously he con e gence o a solu ion and he e inemen o he analy ical model.
5.6.4 Va iance educ ion
In o de o inc ease he con idence on he simula ion esul s wi hou inc easing he numbe
o simula ions (which esul s in highe compu a ional e o ), a iance educ ion (VR) ech-
niques a e applied. We combine he e wo o hese echniques: La in hype cube sampling
(LHS) (McKay e al.,2000) and an i he ic a ia es (AV) (Hamme sley and Mo on,1956).
The i s echnique consis s o de ining ns a a o each o he ms ochas ic pa ame e s,
whe e all he s a a ha e he same p obabili y o occu ence. Then, nscena ios a e gene -
a ed, each sampling om a dis inc s a um o each pa ame e . Fo ins ance, o n=2 and
m=3, wo scena ios could be c ea ed as ollows:
1. sampling om he second, i s and second s a a o he i s , second and hi d pa-
ame e s, espec i ely;
122 Chap e 5. Simula ion-op imiza ion o p oac i e planning and scheduling
VND
Decode
Sol e LP
se up pa e n
Simula ion
S-O Algo i hm
e ine
(a)
VND
Decode
Sol e
S-O Algo i hm
Simula ion
LP
se up pa e n
e ine
solu ion
(b)
VND
Decode
Sol e
S-O Algo i hm
Simula ion
LP
se up pa e n
(c)
Figu e 5.5: Using simula ion o e ine he LP, gi ing eedback o he whole op imiza ion
p ocess: (a) a he beginning; (b) i e a i ely; (c) p og essi ely.
2. sampling om he i s , second and i s s a a o he i s , second and hi d pa ame-
e s, espec i ely.
In his way we ensu e he scena ios a e well dis ibu ed in he p obabili y space and he
sample is mo e ep esen a i e. LHS has he ad an age o e he s anda d s a i ied sampling
o esul ing in only nscena ios ( a he han n·m, i all he combina ions we e conside ed).
On op o LHS, we apply AV, which es ablishes he use o symme ic andom seeds in
he sampling p ocess. This means ha o e e y sample pa h ob ained, i s an i he ic pa h is
also conside ed, hus equi ing he de ini ion o an e en numbe o s a a in LHS.
5.7. Case s udy and p elimina y expe imen s
This sec ion desc ibes a case s udy whe e he p oposed S-O me hod is applied. Fi s , he
p ocessing o he inpu da a is p esen ed and hen, he esul s o p elimina y expe imen s
a e exposed. These expe imen s seek o pe o m a i s assessmen o he S-O me hod
p oposed.
The case s udy is conduc ed on an in eg a ed pulp and pape mill. These plan s com-
p ise mul iple p oduc ion s ages and a complex p oduc ion low s uc u e. We ocus on he
wo mos c i ical p oduc ion esou ces: he pulp diges e and he pape machine, as well as
he in e media e ank in be ween. This simpli ied sys em was indeed he inspi a ion o he
p oblem desc ibed in Sec ion 5.2. Bo h p oduc ion uni s a e subjec o dis u bances and he
p ocess is cha ac e ized by high a iabili y.
We s a ed by collec ing da a om he plan ega ding all he unce ain y in he p ocess.
Then, di e en p obabili y dis ibu ions we e app oxima ed o he da a. The p ocedu e
consis ed o he ollowing s eps:
1. gene al cha ac e izing he unde lying dis ibu ion, by compu ing summa y desc ip-
i e s a is ics and his og ams;
5.8. Conclusions and u he esea ch 123
p oduc ion
yield (α)
machine ailu es
(TBF)
machine ailu es
(TTR)
Figu e 5.6: App oxima ion o p obabili y dis ibu ions o eal da a o p ocess a iabili y
and dis u bances.
2. selec ing a se o candida e dis ibu ions and i ing hem o he da a using he me hod
o maximum likelihood;
3. de e mining which o he i ed dis ibu ions bes ep esen s he da a using Kolmogo o -
Smi no es s.
The inal p obabili y dis ibu ions and he his og ams o he o iginal da a a e illus a ed
in Figu e 5.6. These dis ibu ions we e hen in oduced in he simula ion model and he
a e age alues ( ega ding p ocess a iabili y) we e used in he analy ical model.
In o de o ha e a i s alida ion o he e ec i eness o he S-O me hod in gene a ing
obus plans, a compa ison is conduc ed ela i e o a non-p oac i e app oach. Figu e 5.7
shows he pe o mance o bo h me hods in he main KPIs. By sac i icing pa icula objec-
i es, such as he o de s backlog, he S-O algo i hm is able o gene a e plans ha in he
simula ion esul in less o e and unde lows o he ank le el. These iola ions in p ac ice
would imply he adap a ion o he plan, pa icula ly he execu ion o ab up changes o p o-
duc ion a es and consequen ly loss o p oduc i i y. The e o e, he penaliza ion gi en o
he ank iola ion (in he objec i e unc ion) co esponds o hose adap a ion cos s. O e -
all, he me hod was able o imp o e by 89% he ank iola ion. Ne e heless, i would be
impo an o ex end his compu a ional s udy o mo e p oduc ion se ings, in o de o ob ain
a be e unde s anding o he impac o he S-O me hod.
The p oduc ion plan used in hese expe imen s is illus a ed in Figu e 5.8. The non-
p oac i e app oach does no conside slacks in he ank le el and hence akes ad an age
o he wide limi s o con ac he p oduc ion cycle. The S-O me hod on he o he hand,
ex ends he g ades cycle, esul ing in a smoo he a ia ion o he ank le el, which does
no app oach he limi s. Ope a ing wi h hese slacks in he ank le el, he sys em is mo e
p epa ed o accommoda e possible dis u bances ha may occu ei he ups eam (in he
diges e ) o downs eam (in he pape machine).
5.8. Conclusions and u he esea ch
Simula ion-op imiza ion appea s o be a e y p omising ool o app oach planning and
scheduling p oblems subjec o p ocess a iabili y and dis u bances. Disc e e-e en sim-
130 Chap e 6. Conclusions and u u e wo k
and was able o ind easonable solu ions much as e . The p oposed me hod can be easily
adap ed o app oach o he small bucke lo -sizing and scheduling p oblems (linea con-
s ain s a e inco po a ed wi hou any equi ed modi ica ion), bu will be especially ele an
o p oblems wi h independen con inuous decisions (i.e., a e he bina y a iables ha e
been ixed, con inuous decisions s ill need o be op imized), such as he gene al lo -sizing
and scheduling p oblem (GLSP) and he p opo ional lo -sizing and scheduling p oblem
(PLSP). The me hod is a signi ican con ibu ion o he li e a u e, since no only i ou pe -
o med he exis ing app oaches in ha speci ic p oblem, bu also con ains no el ideas o
me aheu is ics app oaching hese small-bucke p oblems.
The second objec i e o he hesis is he de elopmen o a decision suppo sys em
(DSS) o be used in p ac ice. Fo ha pu pose, he ma hema ical model is comple ely e-
o mula ed. The main issue is he conside a ion o ixed campaigns. This is one o he
mos impo an equi emen s, since he i s campaigns o be p oduced ha e been p e i-
ously op imized o he cu ing s age. Mo eo e , i gi es he DSS he abili y o es manu-
ally de ised campaigns o wo k as a hyb id (conside pa o a manual plan and op imize
he emaining). The inco po a ion o his ea u e sugges s he use o a con inuous ime
o mula ion whe e p oduc ion slo s can c oss disc e e ime pe iods. In his way, one cam-
paign is ep esen ed by jus one slo , hus a oiding he need o heu is ically de e mine he
numbe o slo s o each campaign. O he impo an indus ial ea u es include di e en
p io i y le els o o de s, a iable p oduc ion a es in all uni s and scheduled s oppages.
The new o mula ion needs less bina y a iables o se ups, bu in oduces addi ional ones
o he in e sec ion o he ime g ids. The e o e, he adap a ion o he p oposed VNS is
no s aigh o wa d and hence, a MIP-based heu is ic is applied. The me hod is w apped
by p e- and pos -p ocessing s eps, which essen ially deal wi h he agg ega ion and disag-
g ega ion o p oduc ion o de s, and includes a pos -op imiza ion phase, whe e p oduc ion
a es a e smoo hed. When compa ed o manual plans, he sys em’s plans ha e shown all
he desi able cha ac e is ics and p o ed o be supe io in he mos ele an KPIs. The DSS
is cu en ly in unc ion in he case s udy company. The main con ibu ion o his DSS is
ela ed o b idging he gap be ween esea ch and p ac ice, by b inging mo e insigh s om
he indus y (in e ms o ope a ional issues), in es iga ing he abili y o he exis ing mod-
els in he li e a u e o deal wi h hose issues and showing how s a e-o - he-a models and
me hods can be applied in p ac ice. Mo eo e , i includes ea u es which a e essen ial o
eac i e planning (and we e no conside ed by he p e ious me hod), such as he possibili y
o modelling s oppages (which can be used o cha ac e ize dis u bance si ua ions o sched-
uled main enance) and ixing campaigns (indispensable o olling-ho izon amewo ks).
F om he a o emen ioned wo k wo esea ch pape s ha e esul ed:
•G. Figuei a, M.O. San os, B. Almada-Lobo. A hyb id VNS app oach o he sho -
e m p oduc ion planning and scheduling: A case s udy in he pulp and pape indus-
y. Compu e s &Ope a ions Resea ch, 40(70):1804–1818, 2013.
•G. Figuei a, P. Amo im, L. Guima ães, M.A. Lopes, B. Almada-Lobo. A decision
suppo sys em o he ope a ional p oduc ion planning and scheduling o an in e-
g a ed pulp and pape mill. Submi ed o Compu e s &Chemical Enginee ing, 2014.
131
In he p oac i e pe spec i e, simula ion-op imiza ion (S-O) me hods appea o be p omis-
ing. Howe e , he exis ence o a a as li e a u e on hese me hods and he lack o a com-
p ehensi e classi ica ion mo i a ed an in-dep h s udy o his ield. Mos o he wo k on S-O
na u ally esul s om wo main disconnec ed communi ies, which con ibu e wi h di e -
en me hods and app oaches. The Simula ion communi y ends o ely mo e on simula ion
models and hence uses hem as e alua ion (o i ness) unc ions o an op imiza ion algo-
i hm, o a mos o e alua e mul iple solu ions which se e o app oxima e a me amodel.
The Op imiza ion communi y on he o he hand is mo e willing o o mula e a p io i an-
aly ical models which a e speci ic o he p oblem, hus aking ad an age o i s s uc u e.
Simula ion is hen used o enhance o complemen hose models. The pu pose o simu-
la ion is wha dis inguishes he main S-O app oaches. The second key dimension is he
hie a chical s uc u e ha ela es simula ion wi h op imiza ion. The ma ix ha esul s
om combining hese wo dimensions allows o pu he main S-O me hods in pe spec i e,
which may help u he unde s anding hei di e ences and simila i ies, as well as iden i-
ying possible designs no explo ed ye . O he wo dimensions, mo e ela ed o he sea ch
design, also imp o e he comp ehension o he di e en me hods. The i s (sea ch me hod)
is indeed e y close o he way he li e a u e has been classi ying S-O app oaches, while
he second (sea ch scheme) complemen s i by examining he al e na ion be ween he so-
lu ion and p obabili y spaces. Explo ing each o hese dimensions, di e en S-O designs
a e ela ed o speci ic p oblem cha ac e is ics. The s udy hus con ibu es o he li e a u e
wi h a axonomy ha con ains key dimensions dis ega ded by p e ious classi ica ions, gen-
e al guidelines conce ning he use o S-O me hods o di e en p oblems, insigh s in o he
c oss- e iliza ion o he ideas applied in dis inc S-O me hods and a s anda d o a be e
communica ion in he S-O communi y.
The o e iew o S-O me hods pa es he way o an app oach o p oac i e p oduc ion
planning and scheduling. The main S-O designs a e discussed in he con ex o hese p ob-
lems and a no el combina ion o simula ion and op imiza ion is p oposed, whe e he ana-
ly ical model is e ined du ing he op imiza ion p ocess. The analy ical model is de e min-
is ic, bu conside s he main ea u es o he p oblem, like he p e ious eac i e app oaches.
Simula ion is hen esponsible o e alua ing how plans beha e in a s ochas ic en i on-
men , subjec o p ocess a iabili y and dis u bances. The la e a e accu a ely modelled
wi h e en s o hei s a and end. This disc e e-e en simula ion model p o ides eedback
on he slacks used in he in e media e ank, so ha he op imiza ion algo i hm is able o
gene a e good quali y and obus solu ions. The main con ibu ion o his chap e is an S-O
amewo k ha is applicable o a ange o planning and scheduling p oblems, especially in
mul i-s age scena ios, whe e he bo leneck may shi be ween s ages.
The s udy on S-O has esul ed in wo esea ch a icles and in wo p oceedings:
•G. Figuei a, B. Almada-Lobo. Hyb id simula ion–op imiza ion me hods: A axon-
omy and discussion. Simula ion Modelling P ac ice and Theo y, 46:118–134, 2014.
•G. Figuei a, B. Almada-Lobo. Simula ion-op imiza ion o planning and scheduling
o wo-s age con inuous sys ems subjec o a iabili y and dis u bances. Wo king
pape , 2014.
132 Chap e 6. Conclusions and u u e wo k
•G. Figuei a, B. Almada-Lobo. Robus P oduc ion Planning and Scheduling o a Pulp
Diges e and a Pape Machine. Compu e Aided Chemical Enginee ing, 33:499-504,
2014.
•G. Figuei a, M. Fu lan, B. Almada-Lobo. P edic i e p oduc ion planning in an in e-
g a ed pulp and pape mill. IFAC P oceedings Con e ence on Manu ac u ing Mod-
elling, Managemen , and Con ol, 371–376, 2014.
Ongoing esea ch is compa ing he pe o mance o he p oposed S-O me hod o o he
a ian s, which call simula ion a di e en poin s in he algo i hm. Running simula ion only
a he beginning can be mo e s aigh o wa d and e icien . Howe e , he p ope alues o
he model’s pa ame e s o be e ined (in his case, he ank slacks) may depend on he
solu ion being simula ed. The e o e, he alues ob ained wi h he ini ial solu ion will no
be alid o he inal one. An i e a i e p ocedu e should be able o add ess ha issue, bu
can be ime consuming. The p og essi e e inemen s a egy aims a combining he bes
o bo h wo lds, con e ging o a solu ion wi h inc easing model’s accu acy. Ne e heless,
i s e ec i eness should be alida ed by compa ing o he a o emen ioned al e na i es using
di e en p oblem se ings. The ea u es o he p oblem ha a ou a gi en s a egy should
also be iden i ied. In addi ion, s a is ical selec ion me hods should be applied, in o de o
alida e sea ch mo es and possibly educing he numbe o simula ions.
Wi h espec o eac i e app oaches, he comp ehensi e o mula ion p oposed he e,
when app oached wi h he MIP-based heu is ic, is al eady p o iding solu ions ha a e good
enough o p ac ice. S ill, he e is a long way o go un il a easonable op imali y gap can be
achie ed. Indeed, e en he linea elaxa ion is p oblema ic o cu en comme cial sol e s.
The VNS p oposed could no be applied di ec ly, due o he addi ional bina y a iables ha
eme ged om p ac ical equi emen s. The e o e, i would be necessa y o include in he
VNS a heu is ic o deal wi h ha issue o adap he MIP-based heu is ic o inco po a e some
o he ideas o he VNS, such as adding/ emo ing campaigns o/ om ce ain posi ions. On
he o he hand, he o mula ion may s ill be s eng hened wi h addi ional alid inequali ies
o e o mula ions. In addi ion, he model can s ill be enhanced wi h espec o eac i e
planning. In a se ious dis u bance si ua ion, he ixed campaigns may no longe be ha d
cons ain s. Reac i e planning should hen weigh he cos o adap ing he o iginal plan o
con e ge he sys em owa ds ecommended ope a ing le els.
Finally, he coo dina ion o p oac i e and eac i e app oaches is also a ele an subjec
o u u e esea ch. De e mining he pe iodici y o he e en s ha should igge eac-
i e app oaches and whe he he e is enough ime o p ope ly look a p e en i e issues a e
impo an ques ions o be in es iga ed. The ade-o be ween solu ion quali y and compu-
a ional ime is always p esen , bu i is also cons an ly e ol ing o e ime.
133