FACULDADE DE ENGENHARIA DA UNIVERSIDADE DO PORTO
In eg a ed p oduc ion planning and
scheduling op imiza ion
Daniel Ca alho
Mes ado In eg ado em Engenha ia Elec o écnica e de Compu ado es
Supe iso : Ped o Amo im
Co-Supe iso : Edua do Cu cio
Augus 14, 2019
c
Daniel Ca alho, 2019
Resumo
Es e abalho p opõe um mé odo de solução i e a i a pa a abo da a in eg ação do planeamen o
ác ico (dimensionamen o de lo es) e ope acional (sequenciamen o) numa p odução indus ial com
se ups dependen es da sequência. Es e mé odo decompõe o p oblema da in eg ação em dois. No
p imei o sub-p oblema, planeamen o ác ico, o plano de p odução é op imizado sem e em con a
se ups necessá ios, usando um modelo ma emá ico. O sequenciamen o dos p odu os é depois
de inido usando es a égias de pesquisa local. O esul ado inal se á usado como eedback na
o mulação de eg as adicionais pa a complemen a em o modelo do p imei o sub-p oblema. De
seguida, o planeamen o ác ico é epe ido, conside ando as no as eg as de inidas an e io men e.
O algo i mo con inua i e a i amen e a é que as unções objec i o dos dois ní eis con i jam. Os
p incipais ganhos des e mé odo são o seu p ocedimen o in ui i o e ácil de implemen a , e o pouco
empo compu acional necessá io. De modo a analisa esul ados ob idos, dois expe imen os com-
pu acionais são p opos os. O p imei o pa a compa a o mé odo i e a i o com ou os mé odos
de solução encon ados na li e a u a pa a p oblemas simila es, nomeadamen e me a-heu is icas
e modelos de p og amação in ei a. Po im, a in es igação oi ocada num caso de uma indús-
ia de nu ição animal, onde o se up de p odução é dependen e da sequência e não- iangula . O
p opósi o do segundo expe imen o é a alia os e en uais ganhos des a abo dagem no planeamen o
de p odução nes a indús ia, usando os dados de uma emp esa eal. Os espec i os esul ados
demons a am que o mé odo i e a i o é uma boa solução pa a p oblemas de p odução ex ensi os,
nos quais um modelo MIP necessi a de empos compu acionais imp a icá eis, de i ado ao ele ado
núme o de a iá eis biná ias.
i
ii
Abs ac
This wo k p oposes an i e a i e solu ion me hod o add ess he in eg a ion o he ac ical (lo -
sizing) and ope a ional (scheduling) le els in p oduc ion planning wi h sequence dependen se ups.
This me hod b eaks he in eg a ed lo -sizing and scheduling p oblem in o wo. In he i s sub-
p oblem, a he ac ical le el, he p oduc ion plan is op imized wi h p oduc ion se ups dis ega ded
using a ma hema ical model. The p oduc ion scheduling solu ion is hen de ined using local sea ch
s a egies. The inal solu ion will se e as eedback o o mula e addi ional ules o complemen
he i s sub-p oblem model. A e ha , he ac ical le el is again op imized, conside ing he ules
de ined om he ope a ional le el. The algo i hm con inues i e a i ely un il he objec i e unc ions
om bo h le els con e ge. The main ad an ages o his me hod a e i ’s in ui i e and easy o
implemen p ocedu e, and he low compu a ional ime equi ed. In o de o analyze esul s, wo
compu a ional expe imen s a e p oposed. The i s is pe o med o compa e he solu ion me hod
p oposed wi h mixed-in ege p og amming models and me a-heu is ics om he li e a u e. Then
he esea ch will ocus on an animal eed indus y case, in which p oduc ion se up is sequence
dependen and non- iangula . The pu pose o he second expe imen is o e alua e he po en ial
gains o he p oduc ion planning in his indus y, using a eal company da ase . The espec i e
esul s showed ha he i e a i e me hod is a good solu ion o ex ensi e p oduc ion p oblems, in
which he MIP models equi e in ac able compu a ional imes, esul ing om he high numbe o
bina y a iables.
iii

i
Acknowledgemen s
Fi s ly I wan o hank bo h o my supe iso s. Edua do Cu cio, o he cons an suppo h ough-
ou all he de elopmen o his wo k. I’m g a e ul o always being willing o help me o keep
his hesis on ack, wi hou which his wo k would no exis . His p o essionalism and kindness in
my guiding p ocess will always inspi e me in my p o essional ca ee . I would also like o hank
p o esso Ped o Amo im, o helping me wi h impo an insigh s in he w i ing p ocess and key
ad ice in he s uc u e o his wo k.
Mo eo e , I exp ess my g a i ude o he all he co-au ho s ha con ibu ed o his wo k, pa -
icula ly, p o esso Luis Guima ães, ha helped me in he ea ly s age o his wo k, de ining he
p oblem add essed and he possible solu ion me hods.
I also wan o hank he ins i u ion INESC TEC, o p o iding me wi h a place o he de-
elopmen o his hesis, whe e I always ound an excellen wo king and iendly en i onmen .
Addi ionally I ha e o men ion FEUP, whe e e e yday I lea ned o be a be e pe son and o
making he las 5 yea s, he bes o my li e.
Las ly, I ha e o hank my amily, especially my pa en s, o all he con inuous pa ience and
suppo ha always kep me ocus in his wo k. I wan o also hank my close iends o always
being he e when I needed, in pa icula my college iends om FEUP, ha e e yday helped
keeping me in a good mood, no only du ing he mon hs o his wo k, bu h oughou all my
college jou ney, and which iendships will con inue o he las o my li e.
Daniel Ca alho
i
“The people who a e c azy enough o hink hey can change he wo ld
a e he ones who do”
S e e Jobs
ii
xi LIST OF TABLES

Abb e ia ions and symbols
ATSP Asyme ic a elling salesman p oblem
BRKGA Biased andom-key gene ic algo i hms
CLPS Capaci a ed lo -sizing p oblem
CSLP Con inuous se up lo -sizing p oblem
DLSP Disc e e lo -sizing and scheduling p oblem
FO Fix-and-Op imize
GA Gene ic Algo i hm
GLSP Gene al Lo -sing and Scheduling p oblem
HIER Hie a chical planning s a egy
ILSP I e a i e Lo -Sizing and Scheduling Planning
ILSPnR I e a i e Lo -Sizing and Scheduling Planning wi hou esolu ion
ILSPRI e a i e Lo -Sizing and Scheduling Planning wi h esolu ion
LS Local Sea ch
MA Meme ic Algo i hm
MIP Mixed in ege p og amming
PLSP P opo ional lo -sizing and scheduling p oblem
RF Relax-and-Fix
SA Simula ed Annealing
SC Supply chain
TS Tabu Sea ch
x
Chap e 1
In oduc ion
1.1 Con ex
P oduc ion planning is one o he mos challenging subjec s in ope a ions managemen , wi h g ea
impo ance in he company’s educ ion o cos . In a p oduc ion planning p oblem, he iming and
sizes o p oduc ion o de s mus be de e mined in o de o ul ill he ma ke demand and minimize
he associa ed cos s [4]. The wo main p oduc ion planning p oblems add essed in his wo k a e
lo -sizing and scheduling.
•Lo -sizing - de e mines he quan i ies o p oduc ion necessa y o sa is y de e minis ic p od-
uc demand o e a ini e planning ho izon.
•Scheduling - es ablishes he o de in which lo s a e p oduced wi hin a ime pe iod, accoun -
ing o he sequence-dependen se up ime and cos s.
1.1.1 Lo -Sizing and Scheduling in he Supply Chain
The supply chain (SC) o a manu ac u ing company is a ne wo k o o ganiza ions wi h he ol-
lowing main unc ions: acquisi ion o aw ma e ials, ans o ma ion o aw ma e ial in o inished
p oduc s, and dis ibu ion o he p oduc s o cos ume s, ha ing he goal o achie e high se ice
le el a low cos s. The planning p oblems ha ha e o be sol ed o achie e his pu poses co e a
wide ange o ime scales as desc ibed by [1]:
Long- e m - De e mines he s uc u e o he supply chain (e.g., acili y loca ion).
Medium- e m - Makes decisions such as he assignmen o p oduc ion a ge s o acili ies
and he anspo a ion om hem o wa ehouses o dis ibu ion cen e s. In he p oduc ion
s age, he lo -sizing p oblem is placed he e.
Sho - e m - Ca ied ou on a daily o weekly basis o de e mine he assignmen o asks
and hei sequence. In he p oduc ion le el, sho - e m planning is e e ed o as scheduling.
1
2In oduc ion
The p oduc ion planning (medium- e m) and scheduling (sho - e m) p oblems posi ions in
he supply chain, p e iously desc ibed, a e ep esen ed in Figu e 1.1.
Figu e 1.1: P oduc ion planning and scheduling posi ions in he supply chain [1].
1.1.1.1 Tac ical planning
The medium- e m planning in p oduc ion is also called ac ical planning, whe e i is decided he
p oduc s o be p oduced in each mac o-pe iod (e.g., days) and he amoun s necessa y o ul ill he
demand.
Figu e 1.2: Tac ical planning amewo k.
Decision: Wha p oduc s and how much should be p oduced in each one o he days?
Main objec i es:
1. Minimize in en o y cos s.
2. Minimize backlog cos s.
3. Minimize o e ime cos s.
1.1 Con ex 3
1.1.1.2 Ope a ional planning
The ope a ional planning (sho - e m) has he goal o ind he bes sequence o p oduc ion o
he p oduc s de ined p e iously in he ac ical planning. This p oblem is called scheduling, de-
ined as he ac o de e mine p io i ies and a anging ac i i ies wi h he pu pose o minimizing he
p oduc ion ime and cos s [5].
Figu e 1.3 ep esen s his ope a ional phase, he p e ious mac o-pe iods (days) a e di ided
in o mic o-pe iods (e.g., hou s) o plan he p oduc ion sequence.
Figu e 1.3: Ope a ional planning amewo k.
Decision: Wha is he bes he p oduc ion sequence in each one o he days?
Main objec i es:
1. Minimize he se up cos s.
In sequence-based manu ac u ing, a changeo e om one p oduc o ano he usually causes
se up cos s as well as se up imes which a e sequence-dependen . I hose hose se ups a e no
well managed i may esul in signi ican losses in p oduc ion capaci y, which may lead o unme
demands and cos ume dissa is ac ion. This p oblem is equen ly ound in dis inc indus ies like
animal eed, au omobile, chemical and elec onics.
This wo k will la e ocus on a case o an animal eed company, in which i is equen o
ha e he possibili y o con amina ion in he p oduc ion o wo consecu i e p oduc s om di e en
amilies, equi ing a cleaning ba ch in be ween hose p oduc s.
1.1.2 In eg a ed planning
P ima ily mos comme cial p oduc ion planning and con ol sys ems ied o cons uc easible
p oduc ion plans in a s ep-wise manne , so he manu ac u ing esou ce planning (MRP II) logic
was implemen ed. I can be di ided in 3 main phases, as desc ibed by [6].

4In oduc ion
∗Phase I: S a ing wi h he inal p oduc s, lo sizes a e compu ed le el by le el, igno ing
capaci y cons ain s.
∗Phase II: The esul s o he i s phase usually exceeds he capaci y in some pe iods. In his
phase some lo s a e shi ed o ind a plan ha mee s he capaci y limi s.
∗Phase III: The plan sequence decisions a e made and he o de s sen o he shop loo .
The MRP II concep , by ha ing Phase I, II and III disconnec ed, may p esen some p oblems:
long lead imes, high wo k-in-p og ess, and un ul illed o de s. So sophis ica ed app oaches a e
necessa y o sol e p oduc ion planning and scheduling p oblems.
S a egies o sol e his p oblem can be classi ied in 3 ca ego ies, illus a ed in he Figu e 1.4.
Ha ing one mas e and one sla e, he communica ion can be unidi ec ional om he mas e o
he sla e (Hie a chical), o wi h eedback (I e a i e). In he case ha his di ision does no exis ,
and he p oblem o mula ion e e s o all wo king pe iods, he solu ion will ha e all he necessa y
in o ma ion o bo h he lo -sizing and scheduling p oblem (Full-space).
Figu e 1.4: Solu ion s a egies o p oduc ion planning [1].
This s udy e iews hese h ee app oaches o he in eg a ion o medium- e m p oduc ion plan-
ning and sho - e m scheduling ha enable he c ea ion o be e p oduc ion plans han hose ob-
ained when sol ing he wo p oblems independen ly by in oducing he solu ion o he lo -sizing
p oblem in he scheduling planning le el.
The goal o his in eg a ion is o cons uc he p oduc ion plan o all he planning ho izon.
P oduc ion plans a e c ea ed wi h he objec i e o minimizing he o e all cos s consis ing mainly
o in en o y holding, se up, o e ime and backlog, while sa is ying he a ailable capaci y and
mee ing he demand in each ime pe iod.
In he Figu e 1.5 we can see a ep esen a ion o an in eg a ed planning solu ion ha will be
explo ed in his wo k.
1.2 Mo i a ion 5
Figu e 1.5: In eg a ed planning.
1.2 Mo i a ion
Se e al companies ace he p oblem o in eg a ing lo -sizing and scheduling in hei p oduc ion
planning o e a gi en planning ho izon, and he cons an complexi y g ow h in he indus y’s
p oduc ions has u ged a esea ch om he scien i ic communi y o c ea e new me hods, mo e
sophis ica ed, o a end he needs o he companies and keep compe i i eness. In many o hese
p oduc ion en i onmen s, swi ching be ween p oduc ion lo s igge s ope a ions wi h cos s o he
company, such as machine adjus men s and cleansing p ocedu es.
The decisions o lo -sizing and scheduling a e o en made sepa a ely, which can cause ope a-
ional cos s and comp omise he esponse o he demand deadlines hei quali y aking in o accoun
he ope a ional cos s and demand deadlines. So he e is an u ge in companies o in eg a e hese
phases. The e o e he wo main mo i a ions o his s udy a e he ollowing:
Scien i ic: De elopmen o e icien solu ion me hods o he lo -sizing and scheduling in eg a ion
p oblems, ound in he li e a u e.
P ac ical: Ob ain good solu ions o he p oduc ion planning ha conside ac ical and ope a ional
planning, ha a e aligned wi h he co po a e objec i es o he company.
6In oduc ion
1.3 Objec i es
This wo k conduc s a se ies o s udies on ma hema ical models and o he solu ion me hods o
in eg a ed lo -sizing and scheduling p oblem and apply hem in a eal case o a company o animal
eed. The ul ima e goal is o op imize he p oduc ion planning in o de o educe he company
cos s. Summa ily ou objec i es a e he ollowing:
•Ma hema ically modeling a eal op imiza ion p oblem o p oduc ion planning and schedul-
ing.
•De eloping and compa ing di e en solu ion me hods in e ms o solu ion quali y and com-
pu a ional complexi y.
•Assessing he alue o in eg a ion and he solu ion quali y ob ained o e he cu en planning
pe o med by an animal eed company.
1.4 Thesis s uc u e
This hesis is o ganized as ollowing. Chap e 2p esen s a li e a u e e iew on he subjec ha
s udies he cu en s a e o he a . The s udy ini ially ocuses on he ma hema ical models used
o ep esen his p oblem and hen explo es o he solu ion me hods based on heu is ics and me a-
heu is ics. In Chap e 3, he p oblem add essed and i s ma hema ical model a e de ined. The p o-
posed i e a i e solu ion me hod is p esen ed and de ailed in Chap e 4. Chap e 5 i s ly desc ibes
o he solu ion me hods commonly used o his planning p oblem ha a e used o benchma k he
i e a i e me hod p oposed. All me hods a e hen assessed wi h he ins ances ound in he li e a u e
and hei esul s a e compa ed, bo h in quali y and compu ing powe . S ill in Chap e 5, a eal
case o an animal eed company in B azil is s udied, ha ing a da ase and hei planning esul s,
he solu ions and gains om he a ious me hod p oposed a e analyzed. In he las chap e , he
conclusion o he wo k is p esen ed as well as p oposals o u u e wo k.
Chap e 2
Li e a u e e iew
This chap e is di ided in 3 sec ions. Fi s ly, a li e a u e e iew on lo -sizing and scheduling
p oblems is made, compa ing he a ious ma hema ical models used o ep esen i , pa icula ly
he la ge and small bucke models, ocusing hen on he hyb id models ha will be used on his
s udy. Secondly, i p esen s a s udy on o he solu ion me hods using heu is ics and me a-heu is ics.
The chap e concludes wi h an in es iga ion on hese solu ions me hods applied in he case o
animal eed indus y.
2.1 Mixed in ege p og amming models
Linea p og amming is a ma hema ical op imiza ion used o maximize (o minimize) a linea ob-
jec i e unc ion subjec o one o mo e cons ain s. An MIP model adds one addi ional condi ion
ha a leas one o he decision a iables can only ake on in ege alues. The use o in ege a i-
ables g ea ly expands he scope o use ul op imiza ion p oblems ha you can de ine and sol e. An
impo an special case is a decision a iable ha mus be ei he 0 o 1 a he op imal solu ion. Such
a iables a e called bina y in ege a iables and can be used o model yes/no decisions. Howe e ,
in ege a iables make an op imiza ion p oblem non-con ex, and he e o e a mo e di icul o
sol e. Memo y and solu ion ime may ise exponen ially as mo e in ege a iables a e added.
This li e a u e e iew speci ies he main lo -sizing and scheduling MIP models and hei a i-
an s. I was based on [6] ha summa izes he wo k in he ield and de ails he di e ences o
he lo -sizing and scheduling p oblems. They can be classi ied in o 2 majo ca ego ies [7], some
based on mic o-pe iods o sho - e m planning (small-bucke p oblems), and models which use
mac o-pe iods o medium- e m planning (la ge-bucke p oblems).
2.1.1 La ge-bucke p oblems
To ep esen he ac ical planning le el, [6] p esen he capaci a ed lo -sizing p oblem (CLSP)
which de e mines he lo sizes o p oduc ion bu no he sequence o he lo s. Se e al i ems may
be p oduced pe pe iod, ha ep esen s a big ime slo , ypically one week in he eal wo ld. The
planning ho izon is usually less han six mon hs. Nex we p esen he MIP model o his p oblem:
7
14 Li e a u e e iew
I is also necessa y o ha e ano he decision a iable o decide i sequence sis selec ed o
p oduc ion:
Ws∈ {0,1}= 1 i sequence sis selec ed o p oduc ion.
The subp oblem ela i e o he o mula ion o he p ede ined sequences can be sol ed wi h a
me aheu is ic me hod using local sea ch s a egies. Ano he solu ion me hod is p oposed by [11],
sol ing he subp oblem as a p ice collec ing a eling salesman [15]. A ne wo k is c ea ed ha
consis o a se o nodes, each ep esen ing a p oduc , and a c se s ep esen ing he p oduc ion
sequence o his p oduc s. This me hod is desc ibed wi h mo e de ail by [11] in Appendix B.
The model p oposed by [14] is hen ep esen ed as he ollowing:
min
J
∑
j=1
T
∑
=1
hjIj +∑
s∈S
c
scsWs(2.24)
Subjec o:
(2.13)
J
∑
j=1
pjxj +∑
s∈S
b
s sWs≤Cap ∀ (2.25)
∑
s∈S
Ws=1∀ (2.26)
∑
s∈S
jsWs=∑
s∈S
ljsWs∀j, (2.27)
xj ≤Mj∑
s∈S
gjsWs∀j, (2.28)
Objec i e unc ion (2.24) minimizes he o al expendi u e in holding cos s and se up cos s
incu ed om sequence selec ion. Cons ain s (2.13) ep esen he classical in en o y balances.
Capaci y cons ain s a e exp essed in (2.25). The use o one sequence in each mac o-pe iod is en-
su ed by (2.26). Cons ain s (2.27) gua an ee se up ca y-o e by linking he i s and las p oduc s
o consecu i e ime pe iods. Las ly, Cons ain s (2.28) only allows p oduc ion o p oduc s in he
sequence selec ed in pe iod .
2.2 Heu is ics and me aheu is ics
In his sec ion, solu ion me hods based on heu is ics and me aheu is ics a e e iewed. This me h-
ods can be applied in he in eg a ed lo -sizing and scheduling p oblem. We p esen hei unc ion-
ali y and how hey can be applied.

2.2 Heu is ics and me aheu is ics 15
2.2.1 Heu is ics
He e i s ly we desc ibe wo heu is ics, Relax-and- ix (RF) wi h Fix-and-Op imize(FO), and how
hey can be employed o sol e MIP models. Then i is p esen ed he local sea ch heu is ic ha
wo ks as base o some me aheu is ics ha will be shown nex .
2.2.1.1 Relax-and- ix (RF)
The Relax-and- ix me hod is a cons uc ion heu is ic used in he esolu ion o mixed-in ege p ob-
lems, which de ines an ini ial solu ion by sol ing se e al small MIP models. Ini ially, all bina y
a iables in he RF solu ion a e elaxed which means hey can ake any alue be ween 0 and 1.
Then a se o a iables X, acco ding o a window size Ws de ined, a e o ced o be in ege , while
he o he s a e kep elaxed, and he esul ing MIP is hen sol ed. Nex , he X a iables a e ixed
wi h he esul s and ano he se o in ege a iables a e op imized. This p ocess is epea ed un il
all a iables a e ixed [16].
This me hod was applied in a animal eed indus y by [17], men ioned be o e, whe e he
esul s a e discussed and compa ed wi h he classic MIP sol e s and wi h he cu en company’s
planning s a egy.
2.2.1.2 Fix-and-op imize (FO)
The ix-and-op imize heu is ic uses ano he app oach o esol e MIP models. I also ope a es in
an i e a i e ashion o sol e a se ies o sub-p oblems ha a e de i ed om he main MIP model.
In each i e a ion, mos bina y a iables a e se o a ix alue and he esul ing sub-p oblem is hen
sol ed by a MIP sol e . A di e en se o bina y a iables a e le " ee" o op imize in e e y
i e a ion un il all he a iables a e op imized [18].
2.2.1.3 Local sea ch
Local Sea ch (LS) is one o he oldes and simples heu is ics me hod. I s a s a a gi en ini ial
solu ion and a each i e a ion he algo i hm eplaces he cu en solu ion by a neighbo solu ion. A
neighbo is gene a ed by he applica ion o an ope a o ha pe o ms a small pe u ba ion o he
cu en solu ion. Th ee me hods can be used o choose he nex solu ion:
•Bes imp o emen (S eepes ascen ): All he neighbo s a e calcula ed and he bes solu ion
is chosen o eplace he cu en one.
•Fi s imp o emen : Neighbo s solu ions a e gene a ed un il one is be e han he cu en
solu ion ha hen eplaces i .
•Random Selec ion: A andom neighbo is selec ed om hose imp o ing he cu en selec-
ion.
16 Li e a u e e iew
This sea ch s ops when all candida e neighbo s a e wo se han he cu en solu ion, so a local
op imum is eached. In he case ha he objec i e unc ion is a minimizing one, LS may be seen
as a descen walk in he g aph ep esen ing he sea ch space. Nex i is p esen ed he pseudo-code
o he s eepes ascen LS a ian .
Algo i hm 1: LS (s eepes ascen ) pseudo-code.
Da a: s=s0;/∗Ini ialSolu ion ∗/
1while (Te mina ion C i e ia no sa is ied) do
2Gene a e (N(s)); /*Gene a ion o candida e neighbo s*/
3i (No be e neighbo ) hen
4S op;
5else
6s = s’; /* Bes neighbo s’ */
7end
8end
9Ou pu : Final solu ion, local op ima
In gene al, LS is an easy me hod o design and implemen , bu one o i s main disad an ages
is ha i no mally con e ges owa d local op imal solu ions. The e o e mo e complex me hods,
p esen ed below, a e needed o a oid ha he algo i hm ge s apped in local op ima.
2.2.2 Me aheu is ics
Me aheu is ics a e a highe -le el p ocedu e designed as s a egies o guide a sea ch p ocess ha
may p o ide a su icien ly good solu ion o an op imiza ion p oblem. Me aheu is ics wo k wi h a
se o solu ions which is usually oo la ge o be comple ely sampled.
An analysis on he a ious me hods was made by [19], among he me aheu is ics discussed
a e Tabu Sea ch; Simula ed Annealing; Gene ic Algo i hms; Meme ic Algo i hms ha will be
desc ibed below in mo e de ail. The e iew o he me aheu is ics in his sec ion is based on [9].
2.2.2.1 Tabu sea ch
Tabu sea ch (TS) is a me hod o sol e op imiza ion p oblems, i s ly p oposed by [20]. I wo ks
as a s eepes ascen LS algo i hm bu i uses a lis o s o e pas solu ions, i also accep s non-
imp o ing solu ions o escape om local op ima when all he neighbo s a e wo se han he cu en
solu ion.
To a oid cycles, TS disca ds he neighbo s ha ha e been p e iously isi ed, managing a
memo y o he solu ions ecen ly applied, which is called abu lis . The abu lis may be oo e-
s ic i e so an aspi a ion c i e ia is c ea ed in a way ha abu solu ions can e en ually be accep ed.
2.2 Heu is ics and me aheu is ics 17
Then he admissible solu ions a e he non- abu ones o ha hold he aspi a ion c i e ia. The TS
pseudo-code is p esen ed nex :
Algo i hm 2: TS pseudo-code.
Da a: s=s0;/∗Ini ialSolu ion ∗/
1Ini ialize he abu lis ;
2while (S opping c i e ia no sa is ied) do
3Find bes admissible neighbo s’;
4s = s’;
5Upda e abu lis , aspi a ion condi ions;
6end
7Ou pu : Bes solu ion ound
2.2.2.2 Simula ed annealing
The simula ed annealing (SA) concep , applied o op imiza ion p oblems, was i s in oduced by
[21]. SA is based on he p inciples o s a is ical mechanics, whe e he annealing p ocess equi es
hea ing and hen slowly cooling o ob ain a s ong c ys alline s uc u e. This analogy is ep esen ed
in he Table 2.1.
Table 2.1: Analogy be ween he physical sys em and he op imiza ion p oblem.
Physical Sys em Op imiza ion P oblem
Sys em s a e Solu ion
Molecula posi ions Decision a iables
Ene gy Objec i e unc ion
G ound s a e Global op imal solu ion
Me as able s a e Local op imum
Rapid quenching Local sea ch
Tempe a u e Con ol pa ame e
Ca e ul annealing Simula ed annealing
The algo i hms wo ks using an andom LS s a egy. A each i e a ion a andom neighbo is
gene a ed, and mo es ha imp o e he ac ual solu ion a e always accep ed. Howe e in SA, i he
neighbo is no be e i can be selec ed wi h a gi en p obabili y (2.29) ha depends on he cu en
empe a u e (T) and he di e ence o he ac ual solu ion (∆E). I he s a ing empe a u e (T0) is
e y high he sea ch will be like a andom LS. O he wise, i i is e y low, i will beha e like a i s
imp o emen a ian LS. Hence, a balance is needed be ween hese wo ex eme p ocedu es.
P(∆E,T) = e−∆E
T(2.29)
Accep ance p obabili y unc ion: Main elemen o SA ha enables non-imp o ing neigh-
bo s o be selec ed.
18 Li e a u e e iew
The cooling schedule: De ines he empe a u e a each s ep o he algo i hm. Essen ial o he
e iciency and e ec i eness o he algo i hm.
The ollowing algo i hm desc ibes he SA sea ch p ocess:
Algo i hm 3: SA pseudo-code.
Da a: s=s0/* Ini ial Solu ion*/
T=Tmax /* S a empe a u e*/
1while (s opping c i e ia no sa is ied ( T < Tmin)) do
2while (Equilib ium condi ion no sa is ied ( ixed empe a u e)) do
3Gene a e andom neighbo s’;
4∆E = (s’) - (s);
5i (∆E < 0) hen
6s = s’ /*accep he neighbo solu ion*/
7else
8Accep s’ wi h p obabili y (e−∆E
T);
9end
10 end
11 T = g(T); /*Tempe a u e upda e*/
12 end
13 Ou pu : Bes solu ion ound
2.2.2.3 Gene ic algo i hms (GA) me hods
Gene ic algo i hms a e a amily o compu a ional me hods inspi ed by he e olu ion heo y. These
algo i hms encode a po en ial solu ion o a speci ic p oblem on a simple ch omosome-like da a
s uc u e, and apply ecombina ion ope a o s o hese s uc u es in o de o op imize he solu ion.
Fi e main phases a e conside ed in a s anda d gene ic algo i hm [22]:
Ini ial Popula ion: The p ocess begins wi h a se o indi iduals which is called a popula ion.
Each indi idual ep esen s a solu ion o he p oblem and i is gene a ed andomly.
Fi ness sco e: The i ness unc ion de e mines how good a solu ion is. I gi es a i ness sco e
o each indi idual. The p obabili y ha an indi idual will be selec ed o ep oduc ion is based on
i s i ness sco e.
Selec ion: The idea o selec ion phase is o selec he i es indi iduals and le hem pass hei
genes o he nex gene a ion. Two pai s o indi iduals (pa en s) a e selec ed based on hei i ness
sco es. Indi iduals wi h high i ness ha e mo e chance o be selec ed o he c osso e .
C osso e : C osso e is he mos signi ican phase in a gene ic algo i hm. Fo each pai o
pa en s o be ma ed, a c osso e poin is chosen a andom om wi hin he genes. The indi idual
is c ea ed by exchanging he genes o he pa en s among hemsel es using a c osso e poin . Tha
new solu ion is hen added o he popula ion.
2.2 Heu is ics and me aheu is ics 19
Mu a ion: In ce ain new indi iduals o med, some o hei genes can be subjec ed o a mu-
a ion wi h a low p obabili y. Mu a ion occu s o main ain di e si y wi hin he popula ion and
p e en p ema u e con e gence.
The pseudo-code algo i hm wi h all his phases is p esen ed below:
Algo i hm 4: GA pseudo-code [23].
Da a: Se pop-size, max-gen, gen = 0, c oss- a e, mu a e- a e
1ini ialize popula ion;
2while maxgen ≥gen do
3e alua e i ness;
4 o i←1 o pop-size by 1do
5selec (pa en 1, pa en 2);
6i ( andom(0,1) ≤c oss- a e) hen
7child = c osso e (pa en 1, pa en 2);
8end
9i ( andom(0,1) ≤mu a e- a e) hen
10 child = mu a ion();
11 end
12 end
13 end
14 Ou pu : Bes solu ion ound.
A a ian o he GA a e biased andom-key gene ic algo i hms (BRKGA), in oduced by [2],
whe e one o he pa en s used o ma ing is biased o be o highe i ness, called he eli e indi-
iduals, a pe ac ion o he popula ion wi h he bes solu ions. The ansi ion p ocess om he
p e ious gene a ion o nex in he BRKGA me hod is ep esen ed in he Figu e 2.1. BRKGA also
uses an pa ame e ized uni o m c osso e , in which o each gene has he p obabili y (1 - pe) o
inhe i ing he alue om he eli e pa en ins ead o he non-eli e one. In his way, he o sp ing is
mo e likely o inhe i cha ac e is ics o he bes pa en .
A BRKGA heu is ic was p esen ed by [24] o he p oduc ion scheduling p oblem. The me h-
ods shown good esul s ge ing he bes -known solu ion o 73 % o he ins ances. The BRKGA’s
lowcha is ep esen ed in he Figu e 2.2, which is e y simila o he s anda d GA.

20 Li e a u e e iew
Figu e 2.1: T ansi ion be ween gene a ions in BRKGA [2].
Figu e 2.2: BRKGA’s lowcha [2].
2.2.2.4 Meme ic algo i hm
The e m ‘meme ic algo i hms’(MAs) was in oduced in he la e 80s o de ine a amily o me a-
heu is ics ha ha e as cen al heme he hyb idiza ion o di e en algo i hmic app oaches o a
gi en p oblem. The meme ic algo i hms can be iewed as a me ge be ween a popula ion-based
global algo i hm and a local sea ch made by each o he indi iduals. They a e a special kind o
gene ic algo i hms wi h a local hill climbing.
In a meme ic algo i hm he popula ion is ini ialized a andom o using a cons uc i e heu is ic.
Then, each indi idual makes a local sea ch o imp o e i s i ness. Like gene ic GA’s, indi iduals
wi h highe i ness a e mo e likely o be selec ed o pass hei genes o he nex gene a ion. The
2.3 Lo -sizing and scheduling in he animal eed indus y 21
ole o he local sea ch in meme ic algo i hms is o loca e he local op imum mo e e icien ly hen
gene ic algo i hms, using less andomness.
Algo i hm 5: Meme ic algo i hm pseudo-code [23].
Da a: Se pop-size, max-gen, gen = 0, c oss- a e, mu a e- a e
1ini ialize popula ion; while max-gen > gen do
2apply GA;
3apply local sea ch;
4gen = gen + 1;
5end
6apply inal local sea ch o bes ch omosome;
2.3 Lo -sizing and scheduling in he animal eed indus y
This wo k also add esses he p oduc ion planning o an animal eed company, in he s udied case,
he op imiza ion p oblem occu s in planning he schedule o a mixe ’s use.
P oduc changes a e equen in his indus y, ypically abou 30–40 pe week, and can be
g ouped in o se e al amilies. P oduc s wi hin he same amily do no con amina e each o he
and ha e negligible changeo e imes and iden ical p ocessing imes. A complica ing ea u e
o he animal eed indus y is ha some p oduc amilies can con amina e o he s i p oduced in
successi e ba ches so he p oduc ion line mus be cleaned, esul ing in subs an ial se up ime.
Thus, he p oduc ion scheduling in his indus y, has he objec i e o minimizing he amoun o
cleanings necessa y in he p oduc ion plan.
2.3.1 Non- iangula se up imes
T iangula sequence-dependen se up imes occu s when i is always as e o pe o m he se-
quence om p oduc p o di ec ly han ia a hi d p oduc q. Howe e , in he animal eed and
o he indus ies, ypically such cleanings can some imes be a oided by in oducing a single lo
o an in e media e p oduc om o he amily, be ween he wo p oblema ic p oduc s, since he
iangula inequali y does no hold. which is called non- iangula se up imes [3]. This concep
is ep esen ed in he Figu e 2.3.
Figu e 2.3: T iangula and non- iangula se up [3].
22 Li e a u e e iew
2.3.2 In eg a ion p oblem in animal eed indus ies
[17] conduc ed a esea ch on he p oduc ion planning o a B azilian animal eed compound com-
pany, ha wo ks wi h one mixe . To decide lo sizes and sequences in each pe iod, wo MIP
models we e designed based on he GLSP. The i s o independen sequences, whe e a cleaning
is made du ing non-p oduc i e ime be ween pe iods, he e o e no equi ing ini ial se up in he
beginning o he pe iod. The second o depeden sequences whe e he p oduc ion is ac i e 24h
a day, elimina ing he non-p oduc i e ime be ween pe iods. This las one being mo e complex
since he sequence has o be op imized o e mul iple pe iods a he han o e a single pe iod.
Ano he app oach was made by [25], whe e he p oduc ion sys em s udied was cons i u ed by
one mixe in he i s s age, a pelle ize , an ex ude and a bulk machine, wi h each one ha ing one
o mo e silos. The p oduc ion planning sequences he ba ches on he mixe and also assigns each
p oduc o a silo. He e a MIP model is o mula ed as an ex ension o he GLSP.
A mo e ex ensi e s udy on he in eg a ed lo sizing and scheduling p oblem in he animal eed
compound indus y is p esen ed by [26]. Using a case s udy in a company o he sec o , wo ap-
p oaches a e p oposed o model and sol e he p oblem. The i s is based on GLSP wi h sequence
dependen se up imes. The o he consis s o modeling he lo sequencing p oblem as an asy-
me ic a elling salesman p oblem (ATSP). Fo each me hod is p oposed wo company s a egies
ela ed o he cleaning o he p oduc ion line al eady men ioned be o e, he i s o Independen
Sequences, and he second wi h Dependen Sequences (se up ca yo e ). The ins ances p esen ed
in he appendix o [26] will be used in a compu a ional expe imen la e and hei espec i e esul s
compa ed o he me hod p oposed.
Chap e 3
P oblem De ini ion
The objec i e o his chap e is o p o ide a clea de ini ion on he p oblem ha is add essed by
his hesis. Fi s , all he pa ame e s needed o he lo -sizing and scheduling in eg a ion p oblem
a e p esen ed, ocusing hen on he speci ic case o an animal eed indus y.
3.1 In eg a ed p oduc ion planning
The in eg a ed p oduc ion planning conside ed in his wo k consis s o a se o N p oduc s, and
a planning ho izon o T mac o-pe iods, each one con aining N mic o-pe iods. E e y p oduc has
a p oduc ion ime ha , alongside he se up imes calcula ed, ha e o espec he capaci y( ime) o
each mac o-pe iod. The main decision o he planning is o decide he p oduc ion quan i ies Xjs
o each mic o-pe iod s, in o de o answe he demand ha is ep esen ed wi h a ma ix N×T ha
has he needs dj o e e y p oduc jin mac o-pe iod . The se up cos s and ime alues, be ween
each p oduc , a e ep esen ed by a ma ix N×N.
Table 3.1 p esen s an example o a p oduc ion plan solu ion o a imespan o 5 days, consid-
e ing 5 dis inc amilies (Fam) o p oduc s and showing he quan i y (Quan ) o be p oduced o
each p oduc .
Table 3.1: Example o a P oduc ion Plan.
O de Pe iod 1 Pe iod 2 Pe iod 3 Pe iod 4 Pe iod 5
Fam Quan Fam Quan Fam Quan Fam Quan Fam Quan
1 2 10 4 8 1 4 4 5 5 6
2 5 3 2 4 3 12 2 8 4 1
3 3 8 5 6 2 5 1 5 2 1
4 1 5 3 2 5 1 3 1 3 10
5 4 7 1 9 4 2 5 8 1 7
23
30 I e a i e me hod
4.3 Tac ical le el
Fi s ly, he ILSP uses a simple linea p og amming model, ep esen ed below, o sol e he ac ical
planning sub-p oblem. This ac ical model (ILSP-Tac ical) is based on he CLSP model p e iously
men ioned in sec ion 4.3. In he model i is conside ed he possibili y o ha ing backlog and
o e ime.
Da a:
j=1,.....,JNumbe o p oduc s
=1,.....,TNumbe o pe iods
C Capaci y ( ime) a ailable in pe iod .
O O e ime ( ime) a ailable in pe iod .
pjCapaci y consump ion ( ime) needed o p oduce one uni o p oduc j.
hjNon-nega i e holding cos s o p oduc j.
oc O e ime cos s o p oduc amily j.
bcjBacklog cos s o p oduc amily j.
dj Demand o p oduc jin pe iod .
Ij0Ini ial in en o y o p oduc ja he beginning o he planning ho izon.
Decision a iables (Model’s ou pu ):
Ij ≥0 In en o y o p oduc ja he end o pe iod .
Bj ≥0 Backlog o p oduc ja he end o pe iod .
O ≥0 O e ime used in pe iod .
qj ≥0 P oduc ion quan i y o i em jp oduced in pe iod .

4.4 Ope a ional le el 31
min
J
∑
j=1
T
∑
=1
(Ij hj+Bj bcj)+
T
∑
=1
O oc (4.1)
Subjec o:
Ij −1+Bj +qjs =Ij +Bj −1+dj ∀j, (4.2)
J
∑
j=1
pjqj ≤C +O ∀ (4.3)
O ≤O ∀ (4.4)
Fo he ILSP-Tac ical, he objec i e unc ion (4.1) akes in o accoun he h ee possible cos s in
he p oduc ion s udied: holding In en o y, backlog and o e ime. Cons ain s (4.2) ep esen he
ypical in en o y balances combined wi h he backlog possibili y. Capaci y o each mac o-pe iod
is con olled by cons ain s (4.3) and he maximum o e ime is limi ed in Cons ain s (4.4).
Fo a simple p oduc ion planning o 5 amilies o p oduc s and 3 mac o-pe iods, a ac ical
le el solu ion can be ep esen ed as:
Table 4.1: Example o ac ical le el solu ion.
Pe iod 1 Pe iod 2 Pe iod 3
Fam Quan Fam Quan Fam Quan
1 10 1 8 1 4
2 3 2 4 2 12
3 8 3 6 3 5
4 5 4 2 4 1
5 7 5 9 5 2
4.4 Ope a ional le el
A e ob aining an ac ical solu ion, he nex s ep o he ILSP is o op imize he p oduc ion se-
quence. Fi s , a good ini ial solu ion is gene a ed and hen local sea ch echniques a e used o
imp o e he solu ion. This p ocess is ep esen ed in Figu e 4.3.
32 I e a i e me hod
Figu e 4.3: Ope a ional le el algo i hm.
4.4.1 Gene a e ini ial solu ion
Fi s ly, he algo i hm 6gene a es ini ial solu ions o each mac o pe iod, conside ing a new pa-
ame e , se ups2j, ha ep esen s he sum o he se up cos s o a p oduc when i is he second
in e e y se up pai . This pa ame e will be impo an o choose he p oduc s in he making o an
ini ial good sequence solu ion.
The concep o he algo i hm is ha he p oduc om he i s pe iod in he ac ical le el
solu ion ha equi es he mos se ups, se ups2j, is chosen as he ini ial one, hen he nex p oduc
o be placed in he sequence is always he one ha c ea es he less se up cos s. This is epea ed
un il he o al p oduc ion sequence is de ined. Since in he cases add essed i is possible ha wo
p oduc s can no e e be p oduced consecu i ely, a new es ic ion is necessa y whe e, in he case
ha he las p oduc s in a pe iod ha e his condi ion, he sequence c ea ion is s opped. Then a
di e en p oduc om he ac ical solu ion is chosen as he ini ial one o again s a he algo i hm.
This s a egy was chosen in o de o educe he unning ime in he local sea ch phase since i
ep esen s an al eady good s a ing solu ion o i and equi es low unning ime.
4.4 Ope a ional le el 33
Algo i hm 6: Gene a e an ope a ional solu ion pseudo-code.
Da a:
1sci j; /*Ma ix o se up cos s om p oduc i o j*/
2se ups2j= sum(sci j); /* Sum o se up cos o p oduc j*/
3plan ; /*Tac ical plan wi h p oduc s o each pe iod */
4op ,s; /*Ope a ional plan wi h he sequence o he p oduc s o each pe iod */
5p ied ; /*lis o p oduc s al eady ied as he ini ial p oduc */
6while (size(p ied) < o al numbe o p oduc s do
7op0,0=j∈plan wi h max(se ups2j) i jno in p ied; /* Choose he p oduc ha
needs he mo e se ups o he ini ial one in he i s mac o-pe iod, ha has no been
ied ye */
8 o ←0 o Tby 1do
9 o s←0 o leng h(plan )by 1do
10 i (E e y p oduc le can’ be p oduced a e ops−1) hen
11 p ied .add(op0,0);
12 b eak; /* Go he nex i e a ion o he while cycle*/
13 else
14 op ,s=jin min(scps−1j) i j∈plan wi h plan and no in he solu ion
ye ; /* he nex p oduc o be chosen is he one ha c ea es he less
amoun o se up cos s o he p e ious p oduc */
15 end
16 end
17 end
18 b eak; /* The whole plan has been de ined*/
19 end
20 Ou pu : op /* Sequence o p oduc ion*/
Fo he special case o an animal eed indus y add essed in his wo k, one pa o he algo i hm
is modi ied. As men ioned be o e, in his p oduc ion sec o he se up cos s ep esen cleanings,
ha a e needed in he mixe i a p oduc is p oduced a e ano he speci ic ype ha con amina es
i .
The e o e in line 14, ins ead o choosing he minimum se up cos , we choose one p oduc
ha doesn’ equi e cleaning i possible. Howe e he e may be a ious si ua ions whe e he e a e
se e al p oduc s s ill o place in he sequence ha does no o ce a cleaning in he mixe . In o de
o be e op imize he sequence, a s a egy a ound he se up cos s was chosen o decide which
one o he p oduc s is o be placed. This is done using ano he pa ame e , se ups1j, ha now
ep esen s he sum o he se up cos s o a p oduc when i is he i s in e e y se up pai . The
p oduc chosen is he one ha c ea es he necessi y o cleaning in he less amoun o p oduc s s ill
o p oduce, min(se ups1j). The goal is ha mo e p oblema ic ypes o p oduc s a e placed a he
34 I e a i e me hod
end o he sequence, so less cleanings a e needed and hose p oduc s become easie o iden i y
la e o c ea e he eedback in o ma ion. Also being dependen sequences wi h se up ca yo e o
he nex pe iod, he las mixe s a e, o a p oblema ic p oduc , can be passed by o he nex pe iod
and a oid a cleaning, i ha same p oduc is o be p oduced in ha pe iod.
So line 14, used o decide he nex p oduc a e a p oduc i, is changed o:
op ,s=j∈plan ,wi h min(se ups1j)∀j ha scop ,s−1,j=0
4.4.2 Local sea ch heu is ic
A e ha , o op imize he ini ial solu ion, a local sea ch (LS) heu is ic is used o each mac o-
pe iod wi h he ollowing cha ac e is ics:
•Neighbo hood: Fo each i e a ion he neighbo s o he cu en solu ion a e e alua ed. To
c ea e each one o he neighbo s, wo p oduc s posi ions in he sequence a e swapped,
demons a ed in Figu e 4.4.
•Fi s imp o emen : In each i e a ion he i s neighbo ha imp o es he bes solu ion is
chose as he new solu ion. This i s imp o ing echnique was chosen, ins ead o he s eepes
descen one, since o ex ensi e p oduc ion p oblems, c ea ing all he neighbo hood o each
i e a ion quickly becomes in ac able.
•S opping c i e ia: The local sea ch ends when all he neighbo hood solu ions a e wo s
han he cu en one so a local op imum was eached.
In Figu e 4.4, i is demons a ed how he neighbou s a e de ined. Each a ow ep esen s a
swi ch be ween he wo p oduc s ha o igina es a di e en scheduling solu ion. Using a simple
example o a sequence wi h ou p oduc s, he i s one is swapped wi h e e y subsequen p oduc
a e i , hen he second is placed in e e y posi ion ahead o i and so on consecu i ely. The e o e
he e is no duplica ed posi ion swaps in he neighbo hood.
4.4 Ope a ional le el 35
Figu e 4.4: Neighbo hood c ea ion s a egy in Local Sea ch.
4.4.2.1 Non- iangula ins ances
In he case o non- iangula ins ances, an addi ional ype o neighbo solu ions a e o mula ed in
he local sea ch heu is ic. Fo each p oduc , a single lo wi h he minimum p oduc ion quan i y
allowed is placed in a di e en posi ion in o de o es i i is able o educe he se up cos s. This
is possible in he case o non- iangula p oduc ion se ups, since high se up cos s can be a oided
by p oducing an in e media e p oduc . This p ocess is ep esen ed in Figu e 4.5.
Figu e 4.5: Addi ional neighbo c ea ion s a egy o non- iangula ins ances.

36 I e a i e me hod
Ha ing he example in Table 4.1 as inpu o ope a ional le el, he ou pu o he algo i hm is
ep esen ed in Table 4.2.
Table 4.2: Example o ope a ional le el esul .
O de Pe iod 1 Pe iod 2 Pe iod 3
Fam Quan Fam Quan Fam Quan
1 2 10 4 8 1 4
2 5 3 2 4 3 12
3 3 8 5 6 2 5
4 1 5 3 2 5 1
5 4 7 1 9 4 2
4.5 Feedback om ope a ional le el o ac ical
As men ioned be o e, he in eg a ion o bo h le els o he ILSP comes wi h a eedback gi en
om he ope a ional phase o he nex i e a ion o he ac ical phase. A e he op imiza ion o he
sequence i is egis e ed he capaci y used and whe e in he plan s ill a e ound signi ican se up
cos s. This in o ma ion a e inco po a ed in he ac ical le el o he nex i e a ion.
The ope a ional le el, a he end o he scheduling op imiza ion, sends wo ype o eedback
back:
•Capaci y: Adding he se up imes in he ope a ional le el, he amoun o capaci y ime used
abo e he limi o ee ime in each pe iod is sen o he nex ac ical le el i e a ion.
•Se up cos s: The p oduc s ha c ea ed signi ican se up cos s, una oidable du ing he ope -
a ional le el, ha e an addi ional cos in he nex ac ical le el i e a ion.
The o mula ion o his ac ical le el inpu s a e desc ibed in de ail in he nex subsec ions.
4.5.1 Capaci y eedback
Al hough he ILSP- ac ical model p esen ed in sec ion 4.3 akes in o accoun he capaci y limi s
p esen ed in cons ain s 4.3, i does no acknowledge he se up imes needed since he sequence is
no being de ined. The e o e i is common ha he model es ima es ha he capaci y is espec ed
bu a e he sequence is op imized, adding he se up imes, ha can no longe be ue.
The capaci y eedback is accomplished by changing he cap and o limi s in he ILSP- ac ical
model. Ha ing he op imized sequence, ini ially he capaci y ime used o each pe iod is calcu-
la ed wi h he ollowing o mula ion:
used =∑
j
pjqj +∑
i
∑
j
s i jzi j ∀ (4.5)
4.5 Feedback om ope a ional le el o ac ical 37
Then i is egis e ed whe e used is in he capaci y limi s. The e a e 2 possible si ua ions ha
could ake place in each mac o-pe iod :
•used <cap :
I he capaci y used is less han he limi in mac o-pe iod , he new capaci y in he nex
i e a ion o he ac ical le el is inc eased and he o e ime bounda y is dec eased by he
same amoun .
new cap =cap + (cap -used )
new o =o - (cap -used )
•used >cap :
I he capaci y used exceeds he limi and equi es o e ime, he in e se o he p e ious case
happens, wi h he new capaci y and o e ime being adjus ed.
new cap =cap - (used -cap )
new o =o + (used -cap )
The goal o his app oach is o adjus he capaci y and o e ime limi s acco ding o he esul s
o he scheduling phase. The o al ime a ailable in he ac ical le el doesn’ change bu as he
po ions o he s anda d capaci y and he o e ime a y, he model ends o pu mo e p oduc s in
pe iods wi h less o e ime in o de o a oid o e ime cos s.
4.5.2 Se up cos s eedback
Fo he se up cos s eedback wo di e en app oaches we e de eloped. The i s , ILSPnR, allows
he ac ical phase o choose when o p oduce he p oduc s ha we e esul ing in high se up cos s.
The second, ILSPRde e mines he mac o-pe iods o he p oblema ic p oduc s ha educe he
se up cos s and o ces hem o be p oduced a hese pe iods in he ac ical le el.
4.5.2.1 ILSPnR - Feedback om se up cos s wi hou esolu ion
As men ioned be o e, a he end o he sequence op imiza ion in he ope a ional le el i is possible
se up cos s could no be a oided. The Table 4.3 shows an example o an op imized sequence ha
s ill p esen s a cleaning be ween p oduc 8 and 1.
Table 4.3: Example o a p oduc ion sequence wi h a cleaning.
Day O de
2 4 7 1 9 4 2 5 8 cleaning 1 7
Fo his i s p oposed me hod, ILSPnR, i is only analyzed in which pe iods an ine i able
expensi e se up cos s will occu o a p oduc j. In p oduc ions whe e all changeo e s equi e a
38 I e a i e me hod
se up cos , o de e mine his expensi e se up cos s a e he scheduling op imiza ion, all he se up
cos s a e so ed and he bigges hsc a e conside ed, whe e hsc is a small po ion o he o al numbe
o se up cos s. In p oduc ions wi h cons an se up cos s, as i is in he animal eed case analyzed
wi h he cleanings p ocess, all he se ups cos s a e he ope a ional le el a e conside ed.
To inco po a e his in o ma ion in he ac ical le el, a new p oduc ion cos pcj is added o he
ILSP-Tac ical model o p oduc s j ha p esen he conside ed hsc se ups o cleaning in pe iod .
This new pa ame e is upda ed a he end o e e y i e a ion i his big se up cos s a e ound:
pcj =sci j (4.6)
An addi ional a iable yj is c ea ed ha de e mines i p oduc jis being p oduced in pe iod
and he objec i e unc ion is also upda ed o add his new cos s:
yj ∈ {0,1}1, i p oduc jis p oduced in pe iod ( = 0 o he wise).
min∑
j
∑
(Ij hj+Bj bcj)+∑
O oc +∑
∑
j
yj pcj (4.7)
The e o e he ILSP-Tac ical model can s ill place he p oblema ic p oduc in he same pe iod i
pu ing i in any one o he o he s c ea es mo e cos s han he se up ones. Bu his s a egy enables
he model o acknowledge ine i able se up cos s.
4.5.2.2 ILSPR- Feedback om se up cos s wi h esolu ion
The p e ious me hod only de e mines whe e he ine i able hsc se ups a e and ge s ha in o ma ion
o he Tac ical Le el in o de o he model o ha e ha cos s in o conside a ion.
One s ep o wa d o his s a egy is he second me hod p oposed, ILSPR. I loca es in which
di e en mac o-pe iod he p oblema ic p oduc can be placed ha will c ea e he less cos s and
hen o ces he ac ical le el o ollow ha solu ion.
This is accomplished by using he local sea ch based algo i hm 7. The idea is ha o e e y
hsc se up o cleaning conside ed, he p oduc s ha a e causing he se up cos a e mo ed o e e y
possible posi ion in o he mac o-pe iods sequences, c ea ing new solu ions. The e alua ion o
he solu ion also akes in o accoun he capaci y, holding in en o y and backlog cos s, since he
p oduc s a e being mo ed o new mac o-pe iods and he ones ha imp o e he ini ial sequence is
s o ed in a lis . Then a s eepes ascen app oach is employed, in which he bes solu ion o he
lis eplaces he ini ial solu ion, and he pa ame e s o he se up a oided: p oduc ype, old mac o-
pe iod and new mac o-pe iod a e s o ed. This p ocess is epea ed o all he emaining hsc se up
cos s, conside ing he new bes solu ion as e e ence, un il all o hem a e esol ed o no be e
solu ion is ound.
4.5 Feedback om ope a ional le el o ac ical 39
Algo i hm 7: Find solu ions o high se up cos s pseudo-code.
Da a:
1Nhsc ←numbe o hsc se up cos s ound om i o jin mac o-pe iod ;
2sc se up cos wi h he pa ame e s: pe iod, i i s p oduc and jsecond p oduc ;
3osolu ion ,s; /*op imized sequence solu ion o each mac o-pe iod */
4nsolu ion ,s; /*new solu ion o each mac o-pe iod */
5Lsolu ions ←emp y lis o new solu ions, wi h he p oduc and posi ion changed;
6S P oduc ion sequence o mac o-pe iod ;
7while Nhsc > 0 do
8 o sc ←0 o Nhsc by 1do
9 o ←06=sc o Tby 1do
10 o s←0 o S by 1do
11 nsolu ion =osolu ion
12 dele e nsolu ionsc ,scs/* Take ou p oduc j om he pe iod sc whe e he is
c ea ing a hsc se up cos */
13 nsolu ion ,s=scj; /* Pu p oduc j om pe iod sc in pe iod and posi ion s
*/
14 i (nsolu ion. i ness < osolu ion. i ness) hen
15 Add [nsolu ion,j,sc , ] o Lsolu ions;
16 end
17 end
18 end
19 i lengh (Lsolu ions) = 0 hen
20 b eak; /*None o he p oduc s posi ion mo emen s imp o ed he solu ion */
21 S o e j,sc and o he bes solu ion in Lsolu ions;
22 osolu ion = bes solu ion in Lsolu ions; /* he new solu ion whe e he emaining hsc
se up cos s a e going o be analysed is he bes om he p e ious i e a ion*/
23 end
24 Ou pu : Se up cos s esol ed.
In he end o he algo i hm, he in o ma ion s o ed o each p oduc posi ion mo ed is passed
on o he ac ical le el. Fo his i is in oduced wo new a iables in he ILSP-Tac ical model:
maxqj maximum quan i y o p oduc j ha can be p oduced in pe iod .
minqj minimum quan i y o p oduc j ha needs o be p oduced in pe iod .
And an addi ional cons ain ha con ols he p oduc ion quan i ies:
46 Compu a ional Expe imen
Figu e 5.5: ILSP-Tac ical p oduc ion planning a e i s i e a ion.
The p oduc ion quan i ies ob ained by sol ing he ac ical le el a e used in he ope a ional
le el o ob ain he bes p oduc ion sequence. Figu e 5.6 p esen s he solu ion s uc u e o he
ope a ional le el conside ing cleaning se ups, p oduc ion capaci y and i s i ness.
The nex able ep esen i s ou pu o his i s i e a ion. I is also possible o see whe e
cleanings a e necessa y, he capaci y limi and he one used in each pe iod. Las ly i is also
p esen ed he i ness o he solu ion, he o al cos s p oduced by he ep esen ed p oduc ion plan.

5.2 Illus a i e example o ILSP 47
Figu e 5.6: Solu ion s uc u e a e he i s i e a ion.
5.2.2 Feedback esul s
A he end o each i e a ion, eedback om he inal solu ion o ope a ional le el is used in he
nex i e a ion. As desc ibed in Chap e 4, his eedback has wo ype o in o ma ion. The i s is
ela ed o capaci y, so in he example shown in Figu e 5.6, he eedback will ha e in o ma ion ha
bo h pe iods 3 and 4 a e he scheduling op imiza ion exceeded he capaci y limi and equi ed
o e ime, and, on he o he hand, pe iod 1 had a lo o ee ime. The second eedback a e on he
p oduc s ha caused high se up cos s in he p e ious i e a ion. The i s me hod p oposed, ILSPnR,
gi es eedom o he ac ical le el o decide whe e o mo e hose p oduc s and ILSPR o ces hese
p oblema ic p oduc s o be p oduced in he bes pe iod ound in he ope a ional le el.
The esul s o each me hod a e shown nex , o he sequence in Figu e 5.6. The solu ion o
ILSPnR in Figu e 5.7 shows ha he capaci y used in he pe iods ha e changed om he p e ious
i e a ion, and also ha p oduc 19 and 20 we e mo ed om pe iods 3 and 4, whe e hey we e
causing cleanings, o pe iod 2 since he p oduc ion in hese pe iods now had an associa ed se up
cos .
48 Compu a ional Expe imen
Figu e 5.7: Solu ion s uc u e a e he second i e a ion o he ILSPnR.
Fo he ILSPR, a new s a egy is employed o add ess p oblema ic p oduc s in a sequence. This
s a egy applies local sea ch o ind he bes pe iod o place a p oblema ic p oduc . Fo ins ance,
Figu e 5.8 shows ha p oduc 20 was c ea ing se up cleanings in bo h pe iods 3 and 4 and he
sea ch algo i hm concluded ha he plan could be imp o ed i ha p oduc is placed in pe iod 1.
Figu e 5.8: Solu ion s uc u e a e he second i e a ion o he ILSPR.
5.2 Illus a i e example o ILSP 49
5.2.3 Solu ion con e gence
Conside ing ha he ac ical le el does no accoun o se up cos s and imes, i s i s solu ion
can be conside ed as a lowe bound o he in eg a ed p oblem. Wi h he eedbacks om he
ope a ional phase, new in o ma ion ela ed o p oduc ion scheduling (capaci y and se up cos s) a e
added o he ac ical le el a he end o each i e a ion. The new in o ma ion aim a e alua ing he
eal cos s o he " elaxed" ac ical p oduc ion planning and i is expec ed ha a one poin bo h
ac ical and ope a ions solu ions con e ge.
The solu ion con e gence o bo h ILSPnR and ILSPR o he ins ance "mon h A" is depic ed in
Figu es 5.9 and 5.10.
Figu e 5.9: ILSPnR con e gence. Figu e 5.10: ILSPRcon e gence.
Bo h models each simila solu ions, bu he ILSPnR con e ges slowe han he ILSPRsince i
e alua es mo e possible solu ions o a oid se up cos s.
50 Compu a ional Expe imen
5.2.4 Final solu ion
Fo he ins ance p esen ed, he bes solu ion ound by he ILSPRme hod is depic ed in Figu e 5.11
Figu e 5.11: Final solu ion ob ained by he ILSPR o ins ance Mon h A.
5.3 Classical ins ances
Fo he i s compu a ional expe imen , he ins ances p esen ed in [11] we e used.
Fo all he ins ances, he pa ame e s alues a e gene a ed andomly using an uni o m dis i-
bu ion. The pa ame e s p esen ed nex a e c ea ed in he same way o each ins ance, using his
limi s:
•Demand: U[40-59] uni s
•Holding cos s: U[2-9] uni s
•Se up imes: U[5-10] uni s
•P ocessing ime: 1 ime uni
The se up cos s a e made p opo ional o se up imes by using a cos ac o θ. To de ine
he machine capaci y, wo pa ame e s Cu and Cu Va we e c ea ed. Cu es ablishes he a ge
u iliza ion o e he en i e planning ho izon and Cu Va he maximum de ia ion om he a ge
capaci y u iliza ion in each pe iod, his las one was de ined as 0.5. I is ensu ed ha he cumula i e
capaci y u iliza ion in any pe iod does no exceed Cu o unsu e p oblem easibili y.
The ins ances a e gene a ed conside ing he ollowing alues o each pa ame e :
•N=15
5.3 Classical ins ances 51
•T∈ {5,10,15}
•Cu ∈ {0.6,0.8}
•θ∈ {50,100}
Combining his pa ame e s, 12 di e en p oblem ypes we e o mula ed wi h he ollowing
designa ion: N−T−Cu −θ.
The solu ions me hods compa ed in his compu a ional expe imen a e:
•Full-space models: GLSP
•Hie a chical me hod: HIER
•Me aheu is ic: GA
•I e a i e Me hods: ILSPnR and ILSPR
Table 5.3 p esen s he esul s o he compu a ional expe imen o each one o he me hods,
he p oduc ion cos s o he bes solu ion ound and he espec i e unning ime(s). The GLSP
model used is a a ian o he one p esen ed in Sec ion 3.2, whe e nei he backlog o o e ime
is conside ed. Fo he capaci y limi in he HIER me hod, he capaci y educ ion is calcula ed
conside ing he a e age se up ime AVG and he numbe o p oduc s N, so he new capaci y is
calcula ed as ollows: cap −AV G −s ime ×N. Fo all he me hods, he unning ime was limi ed
o 1 hou .

52 Compu a ional Expe imen
Table 5.3: Resul s o he classic ins ances
Ins ances ILSP-nR ILSP-R HIER GA GLSP Li e a u e
solu ionCos Time Cos Time Cos Time Cos Time Cos Time Gap
15-5-0.6-50 15874 8 15687 16 15874 8 15399 83 14.605 3600 21% 17839
15-5-0.6-100 28192 77 28052 34 31872 13 27511 80 24586 3600 29% 29517
15-5-0.8-50 16024 28 15347 30 15926 11 17012 82 15.318 3600 19% 17814
15-5-0.8-100 27477 34 26734 54 29521 18 28823 80 24.210 3600 31% 30635
15-10-0.6-50 30534 199 31758 203 32625 53 33844 167 32.545 3600 41% 35270
15-10-0.6-100 60036 156 60739 156 63479 34 61993 148 52229 3600 52% 58268
15-10-0.8-50 30103 164 29968 244 30808 51 33510 143 32.002 3600 52% 35475
15-10-0.8-100 60856 97 54121 237 62657 21 61224 143 54.107 3600 63% 59197
15-15-0.6-50 48245 433 47420 670 48419 57 55427 202 53525 3600 60% 53061
15-15-0.6-100 83954 1096 86579 1604 93405 72 96774 210 76564 3600 58% 87509
15-15-0.8-50 46358 175 45299 559 46331 66 54881 217 47.946 3600 48% 53393
15-15-0.8-100 83644 703 79904 2275 91871 64 100486,1 212 79.625 3600 60% 88468
Fo he smalle ins ances, wi h less pe iods, he GLSP model eaches be e solu ions bu e-
qui es highe compu a ional imes. Howe e , once he ins ances ge mo e ex ensi e, wi h mo e
p oduc s and pe iods, he solu ions o he GLSP models ge wo s o he limi ed ime, as demon-
s a ed by he gap e olu ion h oughou he ins ances p esen ed in Figu e 5.12.
Figu e 5.12: Gap e olu ion o he GLSP model.
Compa ing he solu ions o ILSPRand ILSPnR, he p edic ed esul s a e con i med, wi h he
i s eaching be e solu ions bu aking mo e compu a ional ime. This compa ison is ep esen ed
in Figu e 5.13.
5.3 Classical ins ances 53
Figu e 5.13: Pe o mance compa ison be ween ILSPRand ILSPnR.
Figu e 5.14 depic s he pe o mance e olu ion ac oss all ins ances o he ILSPR, GLSP, and he
GA, using he de ia ion o he bes solu ion ound in all he me hods o each one. The espec i e
end line is hen shown in Figu e 5.15. The esul s show ha he i e a i e me hod solu ions ge
be e o he ins ances wi h mo e p oduc s and pe iods.
Figu e 5.14: Pe o mance compa ison o he GLSP, ILSPRand GA.
54 Compu a ional Expe imen
Figu e 5.15: T endline compa ison o compa ison o he GLSP, ILSPRand GA.
Figu e 5.16 p esen s he a e age de ia ion o he bes solu ion ound o all he me hods es ed,
and he a e age unning ime.
Figu e 5.16: A e age esul s o all me hods in he a iable se up cos s case
5.4 Animal eed ins ances
Fo he second expe imen al es , ins ances om [26] and om a eal company case we e used.
The ins ances ep esen p oblems o an animal eed company. In hese p oblems, se up imes a e
calcula ed based on cleaning necessi y, which consis s o wo alues: cleaning equi ed (se up
ime = 1.67) and no cleaning equi ed (se up ime = 0).
5.4 Animal eed ins ances 55
5.4.1 Li e a u e ins ances
The ins ances conside ed in his sec ion, consis o 26 p oduc ypes, and a planning ho izon o
4 weeks. wi h a less illed demand, whe e some p oduc s do no ha e eques s in a ious mac o-
pe iods.
The same me hods we e used in his expe imen , apa om he ull space MIP model GLSP.
Ins ead, he esul s om he GLSP model p oposed by [26] a e p esen ed. Fo his case, he capac-
i y educ ion o he HIER me hod is calcula ed as ollows: he capaci y ime limi is dec eased by
2 cleanings, cap −2×s ime, in he Tac ical Le el.
Table 5.4: Resul s o each me hod o he animal eed ins ances.
Ins ances ILSP-nR ILSP-R HIER GA GLSP
Resul Time Resul Time Resul Time Resul Time Resul Time
Mon h A 3521 10 3707 7 6276 25255 89 3519 360
Mon h B 17288 6 16870 17 18669 116875 79 16616 157
Figu e 5.17 p esen s he a e age esul s and unning ime o each solu ion me hod o he
animal eed ins ances.
Figu e 5.17: A e age esul s o all me hods conside ing he animal eed ins ances.
The GLSP model is able o con e ge and ind be e solu ions han he i e a i e me hod bu i
is exponen ially slowe . Fo hese ins ances, bo h ILSPRand ILSPnR p oduced simila solu ions,
wi h an signi ican imp o emen o he HIER and GA me hods.
5.4.2 Real animal eed company ins ance
A eal animal eed company was con ac ed in o de o unde s and how his p oduc ion planning
p oblems a e sol ed in he indus y. The company is based in B azil, and has a ex ensi e a ie y
62 Li e a u e animal- eed ins ance
Table A.2: P ocessing ime and holding in en o y cos o each p oduc
P oduc Holding cos P ocessing ime
am1 0,4 660
am2 0,4 170
am3 0,4 85,1
am4 0,4 151,2
am5 0,2 103,4
am6 0,4 110
am7 0,2 42,1
am8 0,2 44,3
am9 0,2 39,2
am10 0,2 48,8
am11 0,2 77,5
am12 0,2 59,1
am13 0,3 84,9
am14 0,3 92,2
am15 0,2 31,2
am16 0,2 43,2
am17 0,2 62,1
am18 0,4 59,2
am19 0,6 137,1
am20 0,6 102,6
am21 0,3 44,6
am22 0,2 44,3
am23 0,2 50,1
am24 0,2 52,5
am25 0,3 98,6
am26 0,2 69,2

Li e a u e animal- eed ins ance 63
Table A.3: Demand o each p oduc
P oduc Mon h A Mon h B
=1 =2 =3 =4 =1 =2 =3 =4
am1 0 0 0 0 0 0 0 0
am2 2 3 9 1 1 6 7 5
am3 9 16 9 25 12 41 20 16
am4 0 0 1 0 0 0 0 0
am5 25 15 2 5 6 6 12 10
am6 0 0 0 0 0 0 0 0
am7 15 16 12 11 43 44 52 51
am8 29 29 32 52 32 32 48 32
am9 40 32 32 52 32 40 48 32
am10 58 57 65 79 56 31 57 58
am11 2 6 6 5 0 0 0 0
am12 2 1 1 0 4 4 0 0
am13 0 1 1 1 0 0 0 0
am14 12 15 20 19 8 8 9 6
am15 1 1 0 0 0 0 0 0
am16 1 0 0 0 0 0 0 0
am17 10 3 3 3 11 11 4 0
am18 0 0 0 0 0 0 0 0
am19 0 1 1 4 0 0 0 0
am20 4 0 4 1 1 1 2 1
am21 35 38 46 47 56 38 73 36
am22 0 0 0 0 0 0 0 0
am23 0 0 0 0 0 0 0 0
am24 0 0 0 0 0 0 0 0
am25 0 0 0 0 0 0 0 0
am26 0 0 0 0 0 0 0 0
64 Li e a u e animal- eed ins ance
Appendix B
Real animal eed company ins ance
65
66 Real animal eed company ins ance
Table B.1: G oups and a ibu es o each p oduc
P oduc G oup A ibu es
123456789
82289 11 0 0 3 0 0 0 0 0 9
82286 11 0 0 3 0 0 0 0 0 0
82266 11 0 0 3 0 0 0 0 0 9
75356 11 0 0 3 0 0 0 0 0 0
82163 11 0 0 3 0 0 0 0 0 0
71443 12 0 0 3 0 0 0 0 0 0
71447 12 0 0 3 0 0 0 0 0 0
71473 12 0 0 3 0 0 0 0 0 0
82263 12 0 0 3 0 0 0 0 0 0
81811MD 15 1 0 3 0 0 6 0 0 0
81812ME 15 1 0 3 0 0 6 0 0 0
81811ME 15 1 0 3 0 0 6 0 0 0
81561MD 15 1 0 3 0 0 6 0 0 0
82174 10 0 0 0 0 0 0 0 0 0
82175 10 0 0 0 0 0 0 0 0 0
81812LN 15 0 0 3 0 0 0 0 0 9
71449 10 0 0 3 0 0 0 0 0 9
71479 10 0 0 3 0 0 0 0 0 9
82275-35 10 0 0 3 0 0 0 0 0 0
82275-17.5 10 0 0 3 0 0 0 0 0 0
82286PN 10 0 0 3 0 0 0 0 0 0
82981 14 0 0 3 0 0 6 0 0 0
82243 11 0 0 3 0 0 0 0 0 0
81811NR 15 0 0 3 0 0 6 0 0 0
81611CA 15 0 0 3 0 0 0 0 0 0
81861CA 15 0 0 3 0 0 6 0 0 0
82115 10 0 0 3 0 0 0 0 0 0
75356VG 10 0 0 0 0 0 0 0 0 0
82243MD 11 1 0 3 0 0 0 0 0 0
82051 14 0 0 0 0 0 6 0 0 0
82163PR 11 0 0 3 0 0 0 0 0 0
82326 11 0 0 3 0 0 0 0 0 0
82329-15 11 0 0 3 0 0 0 0 0 9
82329-30 11 0 0 3 0 0 0 0 0 9
71457DZ 12 0 0 0 0 0 0 0 0 0
82391 8 0 0 0 0 0 0 0 0 0
81812 15 0 0 3 0 0 6 0 0 0
81561CA 15 0 0 3 0 0 6 0 0 0
81711CA 15 0 0 3 0 0 6 0 0 0
82135 10 0 0 3 0 0 0 0 0 0
82138 10 0 0 3 0 0 0 0 0 0
82147PL 10 0 0 0 0 0 0 0 0 0
82176 10 0 0 0 0 0 0 0 0 0
82326AL 11 0 0 3 0 0 0 0 0 0
82263MD 12 1 0 3 0 0 0 0 0 0
81711ME 15 1 0 3 0 0 6 0 0 0
82021SL 14 0 0 0 0 0 0 0 0 0
82263AL 11 0 0 3 0 0 0 0 0 0
81531CA 15 0 0 3 0 0 6 0 0 0
81861ME 15 1 0 3 0 0 6 0 0 0
81611ME 15 1 0 3 0 0 6 0 0 0
Real animal eed company ins ance 67
Table B.2: Demand o each p oduc
P oduc Day 1 Day 2 Day 3 Day 4 Day 5
82289 0 0 500 0 475
82286 0 0 1500 1500 800
82266 2700 1800 0 0 33025
75356 240 0 0 200 1700
82163 0 0 660 0 0
71443 0 600 300 0 150
71447 0 2250 0 150 0
71473 0 650 0 0 0
82263 0 0 600 0 6450
81811MD 0 0 600 0 1100
81812ME 0 0 600 0 2725
81811ME 0 0 0 0 14150
81561MD 0 0 300 0 3300
82174 0 0 0 0 1300
82175 0 0 0 0 700
81812LN 950 0 0 0 0
71449 0 1840 0 0 0
71479 0 0 0 0 1220
82275-35 0 0 0 0 3255
82275-17.5 0 612 875 0 808
82286PN 0 0 0 0 1950
82981 0 0 0 0 450
82243 0 0 0 0 200
81811NR 0 0 0 0 8150
81611CA 0 0 0 0 600
81861CA 0 0 0 0 3900
82115 0 0 0 0 2360
75356VG 0 0 0 0 1180
82243MD 0 0 0 0 880
82051 0 0 0 0 7340
82163PR 0 0 0 0 300
82326 0 0 0 0 760
82329-15 0 0 0 0 2010
82329-30 0 0 0 0 1260
71457DZ 0 0 0 0 1200
82391 0 0 0 0 750
81812 0 0 0 0 500
81561CA 0 0 0 0 600
81711CA 0 0 0 0 5275
82135 0 0 0 0 600
82138 0 0 0 0 900
82147PL 0 0 0 1540 0
82176 0 0 0 0 280
82289 0 0 0 0 15380
82326AL 0 0 0 0 3500
82263MD 0 0 0 0 4150
81711ME 0 0 0 0 925
82021SL 0 0 0 0 150
82263AL 0 0 0 0 1675
81531CA 0 0 0 0 600

68 Real animal eed company ins ance
Figu e B.1: Company’s p oduc ion plan
Real animal eed company ins ance 69
Figu e B.2: ILSPnR solu ion
70 Real animal eed company ins ance
Re e ences
[1] Ch is os T Ma a elias and Cha les Sung. In eg a ion o p oduc ion planning and scheduling:
O e iew, challenges and oppo uni ies. Compu e s & Chemical Enginee ing, 33(12):1919–
1930, 2009.
[2] José Fe nando Gonçal es and Mau icio GC Resende. Biased andom-key gene ic algo i hms
o combina o ial op imiza ion. Jou nal o Heu is ics, 17(5):487–525, 2011.
[3] Alis ai Cla k, Masoumeh Mahdieh, and Soco o Rangel. P oduc ion lo sizing and schedul-
ing wi h non- iangula sequence-dependen se up imes. In e na ional Jou nal o P oduc ion
Resea ch, 52(8):2490–2503, 2014.
[4] An ónio A oso Menezes, Alis ai Cla k, and Be na do Almada-Lobo. Capaci a ed lo -
sizing and scheduling wi h sequence-dependen , pe iod-o e lapping and non- iangula se-
ups. Jou nal o Scheduling, 14(2):209–219, 2011.
[5] Dileep R Sule. P oduc ion planning and indus ial scheduling: examples, case s udies and
applica ions. CRC p ess, 2007.
[6] And eas D exl and Al Kimms. Lo sizing and scheduling—su ey and ex ensions. Eu opean
Jou nal o ope a ional esea ch, 99(2):221–235, 1997.
[7] Ka ina Copil, Ma in Wö belaue , He be Mey , and Ho s Tempelmeie . Simul aneous
lo sizing and scheduling p oblems: a classi ica ion and e iew o models. OR spec um,
39(1):1–64, 2017.
[8] Be nha d Fleischmann. The ehicle ou ing p oblem wi h mul iple use o ehicles.
Fo schungsbe ich Fachbe eich Wi scha swissenscha en, Uni e si ä Hambu g, 1990.
[9] Uday S Ka ma ka and Linus Sch age. The de e minis ic dynamic p oduc cycling p oblem.
Ope a ions Resea ch, 33(2):326–345, 1985.
[10] 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.
[11] Luis Guima ães, Diego Klabjan, and Be na do Almada-Lobo. Modeling lo sizing and
scheduling p oblems wi h sequence dependen se ups. Eu opean Jou nal o Ope a ional
Resea ch, 239(3):644–662, 2014.
[12] Be nha d Fleischmann and He be Mey . The gene al lo sizing and scheduling p oblem.
Ope a ions-Resea ch-Spek um, 19(1):11–21, 1997.
[13] Alis ai R Cla k and Simon J Cla k. Rolling-ho izon lo -sizing when se -up imes a e
sequence-dependen . In e na ional Jou nal o P oduc ion Resea ch, 38(10):2287–2307,
2000.
71