QÜESTIIÓ, Vol 16, 1,2,3
pp.
77-98, 1992
,
HEURISTICA
COMPLEMENTARIA
A
ENFOQUES
DUALES
PARA
LA
, ,
PLANIFICACION
DE
LA
PRODUCCION
S.
LOZANO,
J.
LARRAÑETA
y L.
ONIEVA
Es e abajo p esen a una heu ís ica
de
a ios pasos pa a
la
ob ención
de
soluciones admisibles al p oblema
de
plani icación
de
la
p oducción
con limi aciones
de
capacidad, a
pa i
de
las soluciones ap oxima-
das que p opo cionan los mé odos duales basados en
la
elajación del
p oblema. La heu ís ica es complemen a ia a
la
aplicación
de
dichos
mé odos, buscando soluciones admisibles de i adas
de
las p opo cio-
nadas po
la
solución a
la
elajación.
Complemen a y
heu is ic
o
dual
app oaches
o
he
capaci-
a ed
lo -sizing
p oblem.
Keywo ds:
Plani icación de
la
p oducción, limi aciones de capa-
cidad, elajación Lag angiana, p ecio de los ecu sos,
iempos de
pues a
a pun o, soluciones heu ís icas.
-Escuela
Supe io
de
Ingenie os
Indus iales
de
Se illa.
A da.
Reina
Me cedes
s/n.
41012 Se illa.
-A icle
ebu
el
no emb e
de
1991.
-Accep a
el
juny
de
1992.
77
l.
INTRODUCCIÓN
La de e minación del plan de allado
de
p oducción supone
la
ijación de las
can idades que se
han
de ab ica
de
cada uno de los ipos de p oduc os en los
pe iodos conside ados
de
o ma que los cos es de ope ación que dependen de
es a decisión sean mínimos. La
li e a u a
sob e p oducción o ece soluciones
ope a i as azonables al p oblema cuando la ep esen ación de los cos es y del
consumo
de
la capacidad disponible
da
luga a modelos lineales (La añe a e
al.
[9]}.
Si las limi aciones
de
capacidad no
ac úan
es
posible ealiza
la
plani i-
cación indi idual
de
cada uno
de
los p oduc os,
po
lo que
la
conside ación de los
cos es ijos no supone un inc emen o ap eciable de complejidad, esol iéndose el
p oblema median e p og amación dinámica (Wagne y Whi in [22]). Pe o si
es
necesa io inclui cos es ijos y limi aciones de capacidad,
el
modelo esul an e
es
N
P-comple o
(Flo ian
e
al.
[7]), po lo que
la
op imización es sólo aplica-
ble a si uaciones en las que in e ienen muy pocos p oduc os. El en oque que
apa ece como más uc í e o en
el
caso gene al
es
la
elajación del modelo a
un
p oblema lineal, que se abo da median e p ocedimien os duales, ap oximando
sucesi amen e los p ecios in e nos
de
los ecu sos. (Onie a
e
al.
[19],
Lozano e
al.
[11]).
En
el
apa ado
2 se ecoge explíci amen e
el
modelo analizado, desc ibiendo
las ca ac e ís icas de las soluciones a los en oques duales en el
apa ado
3. La
heu ís ica se p esen a en
el
apa ado 4 y su in eg ación con los en oques duales en
el 5. El
apa ado
6 incluye las expe iencias compu acionales ealizadas aplicando
la
heu ís ica a un conjun o
de
p oblemas.
2.
TERMINOLOGÍA,
NOTACIÓN
Y
MODELO
La no ación
es
la siguien e:
N -núme o
de
a ículos
i
-índice
co espondien e a cada a ículo (i =
1,
2,
...
,
N)
L -núme o
de
pe iodos en
el
ho izon e
de
plani icación
-índice
co espondien e a cada pe iodo
(
=
1,
2,
...
, L)
Zi
-unidades p oducidas del a ículo i en
el
pe iodo
l¡
-unidades
de
in en a io del p oduc o i al inal del pe iodo
78
D;
-unidades de
demanda
del
p oduc o
i en
el
pe iodo
s; -cos e ijo en
el
que se incu e
po
inicia
un
lo e de ab icación de i
p;
-cos e a iable de ab icación del
p oduc o
i
h; -cos e a iable
de
man enimien o del s ock del
p oduc o
i
K
-capacidad disponible en
el
pe iodo
a;
-capacidad consumida
po
inicia
la
ab icación de i
b;
-consumo ma ginal
de
capacidad
po
unidad
ab icada de i
Con es os elemen os,
un
modelo que ecoge el
p oblema
de encon a
un
plan
óp imo
de p oducción que minimice los cos es o ales de ab icación e in en a io
es,
N L
Min
LL
(s;8(x; ) + p;X; +
h;l; )
i=1
=1
suje o a
Ii, -1
+
Xi -
l;
=
D;
i =
1,
..
.
,N;
=
1,
.
..
,L
N
L(a;8(x; )+b;x; )
~
I<
=
1,
...
,L
i=1
Xi
2:
0,
;
2:
0,
J;o
= 0
ep esen ando
8(x) = {
~
si x
>O
si x
=O
La
p oducción global en
el
ho izon e de iempo conside ado es,
pa a
cada
p oduc o
i, la
demanda
o al
en
el
mismo. Debido a ello,
el
cos e a iable
o al
es cons an e, independien emen e
de
las decisiones que se omen,
po
lo que
puede sup imi se del modelo.
En
el
análisis del modelo se conside a
el
subconjun o de las o mas de p o-
ducción compues as
po
secuencias dominan es. Se de inen és as como las que
sa is acen
la
p opiedad Xi ·
Ii, -
1 = O
pa a
cada
.
Co esponden a planes de
p oducción en los que,
+•
x; =
¿nik
s
=o,
1,
2,
...
k=
79
cub iendo cada lo e
la
demanda de un núme o comple o de pe iodos. Además,
los lo es se ab ican en pe iodos que se inician sin in en a io. Las secuencias
dominan es ienen
la
p opiedad de se óp imas cuando las limi aciones de capa-
cidad no ac úan. En
el
caso de que
lo
hagan, una p opiedad de las soluciones
óp imas
es
(Zangwill
[23])
0:::::
Xi ) ·
0:::::
Ii, -d
·
H
=
O,
siendo
H
la
holgu a
de capacidad del pe iodo . Las secuencias dominan es son un subconjun o de
las o mas de p oduci que sa is acen es a p opiedad. Además,
la
esolución
ap oximada del p oblema que nos ocupa median e los mé odos duales descon-
side a las limi aciones
de
capacidad como es icción explíci a, pe mi iendo su
ansg esión. La solución óp ima del modelo ap oximado sa is ace las limi acio-
nes
de
capacidad, pe o con una conside ación ap oximada de los consumos de
capacidad asociados a las pues as a pun o de las se ies de p oducción. Dado
que exis en L pe iodos, el núme o máximo de secuencias dominan es
pa a
cada
a ículo
es
de
F =
2L-l.
Cada
secuencia de ine
una
o ma de p oducción y un
in en a io esul an e en odo
el
ho izon e:
Xij =
(Xijl,
Xij2, · ·
·,
XijL) =
(Xij )
indica la secuencia dominan e de p oducción j
(=
1,
2,
...
,
2L-l)
aplicada al a ículo i
l;;
(I;;¡,l;;2,···•lijL)=(I;j )
indica
el
in en a io
en
cada uno
de
los pe iodos,
que esul a de emplea la secuencia de p oducción
z;;.
Esc ibiendo
el
modelo con es os elemen os esul a,
donde
N F
Min
LLc¡;O;;
i=lj
=1
N F
suje o a
LLmi; O;;
$
I<
=
1,
2,
...
,
L.
i=lj=l
F
¿:o¡;=1
i=1,2,
...
,N.
j=l
O¡;=
O,
1
pa a
cada
i,j.
L
e;; = L (s;ó(x;; ) + p;z;; + h¡l;; )
=l
es el cos e de p oducción e in en a io
de
la secuencia x;; en odo
el
ho izon e;
T lij
=
a¡Ó(Xij )
+ b¡Xij
80
el consumo de capacidad de
la
secuencia
X;j
en el pe iodo
;
()¡i son a iables de
decisión bina ias indicando el empleo, ó no, de
la
secuencia
Xij.
Es e
modelo de a iables en e as esul a de g andes dimensiones, cons ando
de
N+
L es icciones y
N·
2L-l
a iables bina ias.
La
elajación
con inua
del modelo con
B;j
2:
O se analiza como
la
ap oxi-
mación a
la
solución del p oblema de plani icación con cos es ijos y limi aciones
de capacidad. Es e plan eamien o del p oblema ue in oducido
po
Manne
[16)
y
ha
se ido como modelo base
pa a
los es udios pos e io es.
La
ex ensión del
p oblema a
la
conside ación explíci a de
es uc u as
de ab icación mul ini el
con un "cuello de bo ella" en o ma de limi aciones de capacidad ue
modelada
po
Billing on e
al.
[1),
y ep esen a
una
ex ensión del modelo
aquí
conside-
ado, si bien
la
heu ís ica que se desc ibe en es e
abajo
es aplicable
ambién
a
la
ob ención del plan de p oducción
de
dicho cuello de bo ella.
3.
SOLUCIONES
APROXIMADAS
Han sido nume osos los en oques empleados
pa a
abo da
la
esolución del
modelo desc i o. El p ime o de ellos co esponde a
in en a
desde el inicio solu-
ciones heu ís icas simples que den luga a planes admisibles. Las limi aciones de
capacidad desaconsejan
la
posibilidad de aplica mé odos ales como el
"Pa
Pe-
iod Balancing" (Eisenhu
[5])
o el de "Mínimos Cos es Medios" (Sil e y Meal
[20])
al p oblema. Los p opues os
po
Lamb ech y Vande eken
[8)
y Dixon
y Sil e
[2)
conside an explíci amen e las limi aciones de capacidad. Pos e io -
men e
Maes y Van Wassenho e
[13,
14)
e undie on las p opues as con enidas en
es as heu ís icas o mulándolas de o ma simpli icada con lo que las necesidades
compu acionales disminuyen. Su p ocedimien o es some e el
p oblema
a
una
ba e ía
de es e
ipo
de heu ís icas simples y selecciona
la
mejo de las soluciones
ob enidas con ellas.
Pa a
si uaciones en las que las limi aciones de capacidad
son poco es ic as (es o es, las componen es ijas de los cos es y de los consumos
de capacidad de ecu sos son educidas) se ob ienen soluciones acep ables.
O o
en oque
ha
sido
abo da
el modelo de p og amación lineal
con inua
de
Manne
median e
p ocedimien os p imales. His ó icamen e ue el p ime en oque,
y en él se incluyen las p opues as de Dzielinski e
al.
[3),
Dzielinski y Gomo y
[4),
Lasdon y Te jung
[10),
pudiendo conside a se ambién
en e
ellas
la
de Newson
[18)
o
81

Más ecien emen e se
han
aplicado p ocedimien os duales que analizan
la
elajación Lag angiana del p oblema. Las es icciones elajadas son las de ca-
pacidad, que se inco po an a la unción obje i o
median e
la
impu ación
de p e-
cios a los ecu sos empleados. Thizy y Van Wassenho e
[21)
aplican el mé odo
del subg adien e a
la
esolución del Lag angiano. Onie a e al.
[19]
y Lozano
e
al.
[11]
aplican el
mé odo
p imal dual, ex endiendo dicho p ocedimien o a
si uaciones mul ini el con
un
·"cuello
de
bo ella" en Lozano e al.
[12).
El análisis dual iene a ias
en ajas
sob e los o os p ocedimien os (Fishe
[6])
pe o, y en es e aspec o es igual a los mé odos p imales,
la
solución inal
ob enida
no
da
luga , necesa iamen e, a
una
solución admisible.
Con
el
mé odo
p imal dual se esuel e en
cada
i e ación
un
subp oblema
p imal
educido en el
que se iden i ican las can idades p oducidas en
cada
pe iodo. Y lo que es
más
signi ica i o, el g ado de inadmisibilidad de dicho plan.
En
pa icula ,
indica
cual es el exceso u holgu a de capacidad en
cada
pe iodo, ac ualizando en con-
sonancia
la
impu ación de p ecios a los ecu sos.
La
solución
óp ima
del
dual
con iene
un
plan
de p oducción admisible desde el
pun o
de
is a
de
la
ela-
jación con ínua del p oblema.
Pe o
la
es imación de los iempos de
pues a
a
pun o
se lle a a cabo median e
la
linealización de los mismos.
En
la
implemen-
ación
p ác ica
dicha linealización no se co esponde con
la
ealidad,
po
lo que
la
solución
óp ima
del modelo puede se inadmisible
pa a
el
p oblema
o iginal, al
inclui és e las pues as a
pun o
comple as.
Po
ello, odos los mé odos,
ya
sean
p imales o duales, que
abo dan
el p oblema de
la
plani icación de
la
p oducción
con cos es ijos y iempos de
pues a
a
pun o
median e
el modelo
ap oximado
de
Manne
[16)
equie en de
la
inco po ación de algún p ocedimien o que modi ique
la
solución
ap oximada
disponible.
Es a
egla heu ís ica
ha
de ene en
cuen a
explíci amen e el consumo disc e o de
la
capacidad al inicia las se ies de p o-
ducción
pa a
la
ob ención de soluciones admisibles. Asimismo,
ha
de alo a
explíci amen e los cos es a
pa i
de
la
conside ación explíci a de
la
componen e
ija de los mismos.
Thizy y Van Wassenho e
[21)
p opusie on como egla heu ís ica esol e , en
cada
i e ación de su mé odo dual, un modelo de
anspo e.
La
solución dis-
ponible del p oblema dual p opo ciona en
cada
i e ación los pe iodos en que
se inician se ies de p oducción
pa a
cada
uno de los p oduc os. Fijados los
componen es ijos de los cos es
Si
y de los consumos de ecu sos
ai
asociados a
los lanzamien os de
la
p oducción, y e aluada
la
capacidad disponible es an e,
esul a
un
p oblema con ínuo en las can idades a p oduci en dichos pe iodos
pa a
sa is ace
la
demanda. Pe o ija a p io i los pe iodos en los que se
a
a
p oduci conduce en muchos casos a
la
inadmisibilidad del plan de p oducción,
pues el modelo de
anspo e
esul an e es ecuen emen e inadmisible. Además,
el núme o de a iables que·in e ienen en el modelo de
anspo e
es O( N L2
),
82
con lo que su
amaño
y
iempo
de
esolución
aumen an
signi ica i amen e con
el núme o de pe iodos.
La
heu ís ica
p opues a
en
la
siguien e sección
abo da
es os aspec os.
4.
HEURÍSTICA
Como hemos señalado,
el
p oblema de plani icación de
la
p oducción con
cos es ijos y limi aciones de capacidad
es
N
?-comple o.
Los
mé odos
de eso-
lución, sal o
pa a
p oblemas de muy educidas dimensiones, son de
ipo
ap oxi-
mado. En pa icula , odos los basados en
la
o mulación de Manne [16].
Cuando
exis en iempos
de
pues a
a pun o,
la
búsqueda de
una
solución admisible
-aún
cuando no sea
un
plan de p oducción e icien e--
ya
es
de
po
sí N
?-comple o
(Maes
e
al.
[15]). Es
po
ello imp escindible dispone de
una
egla heu ís ica.
En
los mé odos duales se
pa e
de los p ecios in e nos>. asociados al consumo
de los ecu sos, si bien
es
posible ija dichos alo es
a bi a iamen e
"a
p io i".
Aplicando
el
algo i mo de Wagne -
Whi in
[22]
empleando como cos es
L
c¡i
+
l:mij A
=l
que ienen en cuen a los cos es p opios de p oducción
C¡j
más un
é mino
aso-
ciado a la alo ación del consumo de los ecu sos, se esuel e el
p oblema
de
plani icación desconside ando las limi aciones
de
capacidad. Las secuencias de
p oducción ob enidas y los in en a ios esul an es sa is acen
Xij(i) ·l;j(i), -l
=O.
Con
ellas se o man las
ablas
de p oducción
Xi
y de in en a ios l; , que indican
pa a
las secuencias de p oducción iden i icadas
la
can idad
p oducida
de
cada
a ículo en
cada
uno de los pe iodos del ho izon e y sus in en a ios esul an es,
e aluándose el ec o
de
capacidades disponibles
Si
Z
> O
pa a
odo
,
la solución
ob enida
es
admisible.
En
caso con a io
ha
de modi ica se el plan de p oducción median e
la
heu ís ica.
La
heu ís ica que se p opone puede aplica se
po
sí misma, ijando los p ecios
in e nos de los ecu sos>. a bi a iamen e, o mejo en conjunción con
un
mé odo
83
de selección de los mismos. En los mé odos duales,
al
como en el mé odo p imal-
dual (Onie a e
al.
[19],
Lozano e
al.
[11],
[12]) se pueden emplea los p ecios
in e nos
>.
p oceden es de las soluciones admisibles del p oblema dual que se
ob ienen en
cada
i e ación. Así, cada i e ación del mé odo p imal-dual supone
una
aplicación de
la
egla heu ís ica.
La
egla heu ís ica cons a de es bloques:
Bloque
I.
Las eglas del p ime bloque pa icionan los lo es ab icados en el úl imo
pe iodo en el que exis e inadmisibilidad, e asándola en
la
medida de lo posible
hacia el pe iodo pos e io en
el
que
la
holgu a sea máxima, con el in de que
la
si uación esul an e no sea des a o able. El e aso se lle a a cabo inc emen ando
los cos es lo menos posible.
1°
Sea = max{ ': Z ' < 0}. Se iden i ica con el pe iodo
más
a dío en el que
se p esen a inadmisibilidad. Ob iamen e, si Z ' > O
pa a
odos los pe iodos,
la
solución ob enida
es
admisible. FIN.
2°
Sean=
{i:
Xi
·li
> 0}. Es
el
conjun o de a ículos que p oducen en exceso
de
la
demanda
del pe iodo conside ado . Son a ículos
pa a
los que se puede
con empla el e aso de su p oducción, man eniendo
la
admisibilidad.
3° 3.1 Si n =
0,
no se puede e asa la p oducción.
I
a 8 {segundo bloque).
3.2 Se o denan los a ículos en o den c ecien e{no dec ecien es si hay empa-
es) del indicado de inc emen o de cos es
s¡{a¡ +
1)
b¡h¡
La
acionalidad de es e c i e io p o iene del hecho de que al
ompe
un lo e se
incune
en un cos e de lanzamien o adicional y se
aho a
el
cos e de man enimien o debido al e aso de
la
p oducción. Se incluyen
ambién los consumos de ecu so
a¡
y
b¡
con
la
inalidad de libe a
la
máxima
can idad del mismo en
el
pe iodo , comp ome iendo
la
meno
can idad posible del pe iodo al que se e asa ( éase el
pun o
5° de
es e bloque). La inclusión de
la
unidad elimina
la
degene ación cuando
a¡
=
O.
Obsé ese que al no depende el c i e io de o denación de
la
solución conc e a de
pa ida,
dicha o denación puede hace se a p io i
una
sola ez. Obsé ese ambién que el c i e io a o ece el doble obje i o
de
la
heu ís ica: minimiza
el
consumo de ecu sos y el inc emen o de
los cos es.
84
4° 4.1 Si l; =
O,
elimina i de n y ol e a 3°.
P oba
con el siguien e a ículo.
4.2 Sea T = min{ ': ' > ,
li '
= 0},
el
pe iodo
has a
el que se abas ece
la
demanda
del a ículo i con
el
lo e p oducido en el pe iodo .
5° Sea
( ,
T) el pe iodo
pa a
el
que se ob iene
la
máxima
holgu a de capaci-
dad; i.e., max{ Z ': < ' <
T}.
Es el pe iodo
candida o
al que
e asa
el
exceso de p oducción del a ículo i en . Si
ZT
:::;
a;, el e aso p oduci ía
inadmisibilidad en
T,
en cuyo caso, elimina i de
l
e Í a 3°.
6°
Re asa
al pe iodo
la
p oducción de
la
can idad
A • {
[ZT-
a;
(1-
8(x;T
))]
. I }
u = mln b ) mln i '
i
:S '<T
Ac ualiza las a iables del plan
de
p oducción y los indicado es de consumo
de ecu sos:
Z
{::==
Z + bib.
ZT
{::==
ZT-
bib.-a;
(1-
8(x;T))
Xi
{::==
Xi
-b.
XiT
{::==
XiT
+ b.
li '
{::==
li ' -b.
pa a
' = , +
1,
...
,
T-
l.
La
can idad
b. a
aspasa
es á
limi ada
po
la
holgu a del pe iodo T y los
in en a ios e asados
has a
dicho pe iodo. El co che e signi ica
"pa e
en-
e a",
ga an izando median e
el
edondeo
hacia
abajo
la admisibilidad en el
pe iodo
T.
7°
Si
Z
2:
O,
se
ha
eliminado
la
inac!misibilidad en
.
I a 1°.
Si
Z <
O,
se
ha
de con inua ompiendo lo es en
.
I
a 4°.
Obsé ese que el conjun o
de
eglas del bloque 1 inalizan:
-Al alcanza
la
admisibilidad (pun o 7°).
-
Al
ago a se
el
conjun o
ele
a ículos cuya p oducción
pueda
a asa se
(pun o
3.1). En es e caso se aplican las eglas del bloque
11.
Bloque
II.
Las eglas del segundo bloque
adelan an
la
p oducción a pe iodos an e io es
en los que
haya
holgu a
de
capacidad sin c ea nue as pues as a
pun o
(po
ya
exis i en ellos ab icación de lo es).
85
Pa a
mejo mos a
el
ca ác e complemen a io de
la
heu ís ica p opues a
y los mé odos duales, en
la
igu a 1 se ecoge
la
e olución del Lag angiano
jun o
con
la
de
la
mejo solución p opo cionada po
la
heu ís ica, a medida que
i e a
el mé odo p imal-dual aplicado al p oblema que se
ha
denominado MARS-
TEN
l.
Se
obse a que
la
co a in e io p opo cionada po el Lag angiano con-
e ge monó onamen e a su óp imo (el de
la
elajación con inua). Simé icamen e,
las soluciones de
la
heu ís ica an mejo ando p og esi amen e a medida que se
apoya en las secuencias de p oducción más ap opiadas, las cuales su gen al asig-
na
mejo los p ecios in e nos de los ecu sos escasos.
Función
ObJe i o
49500
49300
49100
48900
48700
48500
48300
48100
47900
47700
E olución
de
la
heu ís ica
Lag anglano
+ Heu s lca
4750()~,---~--------~--~--- ---.----~--~--- ---.--
1 5 g 13
17
21
25 29 33 37
4i
N• I e aciones
Figu a
l.
92

7.
REFERENCIAS
(1]
Billing on,
P.;
McClain,
J.
y
Thomas,
L.
(1983).
"Ma hema i-
cal
P og amming
App oaches o
Capaci y-Cons ained
MRP
Sys ems:
Re iew, Fo mula ion
and
P oblema
Reduc ion". Managemen Science,
Vol.
29,
1126-1141.
(2]
Dixou,
P.S.
y
Sil e ,
E.A.
(1981). "A Heu is ic Solu ion P ocedu e
o he
Mul i-i em
Single-Le e! Limi ed
Capaci y
Lo -Sizing
P oblem".
J.
o
Ope a ions M anagemen , Vol. 2, 23-29.
(3]
Dzieliuski,
B.P.;
Bake ,
C.T.
y
Manne,
A.S.
(1963). "Simula ion
Tes s
o
Lo Size
P og amming".
Managemen Science, Vol. 9, 229-258.
(4]
Dzieliuski,
B.P.
y
Gomo y,
R.E.
(1965).
"Op imal
P og amming
o
Lo Sizes, In en o y
and
Labo Alloca ions". Managemen Science, Vol.
11,
874-890.
(5]
Eisenhu ,
P.S.
(1975). "A Dynamic Lo Sizing
Algo i hm
wi h
Capa-
ci y
Cons ain s".
AIIE
T ansac ions, Vol.7, 170-176.
(6]
Fishe ,
M.L.
(1981).
"The
Lag angean Relaxa ion
Me hod
o Sol ing
ln ege
P og amming
P oblems". Managemen Science, Vol.
27,
1-18.
[7]
Flo iau,
M.;
Leus a,
J
.K.
y
Rinooy
Kan,
A.H.G.
(1980). "De-
e minis ic
P oduc ion
Planning: Algo i hms
and
Complexi y". Mana-
gamen Science, Vol.
26,
669-679.
[8]
Lamb ech ,
M.R.
y
Vande eken,
H.
(1979). "Heu is ic
P ocedu e
o he Single-Ope a ion Mul i-i em Loading
P oblem".
AIIE
T ansac-
ions, Vol.
11,
319-326.
[9]
La añe a,
J.;
Onie a,
L.
y
Lozano,
S.
(1988) Mé odos Mode nos
de
Ges ión
de
P oducción. Alianza Edi o ial.
[10]
Lasdon,
L.S.
y
Te jung,
R.C.
{1971). "An E icien
Algo i hm
o
Mul i-i em Scheduling". Ope a ions Resea ch, Vol.
19,
946-969.
[11]
Lozano,
S.;
La añe a,
J.
y
Ouie a,
L.
(1991).
"P imal-Dual
Ap-
p oach · o
he
Single Le e! Capaci
a ed
Lo -Sizing
P oblem".
Eu opean
J.
o
Ope a ional Resea ch, Vol.
51,
354-366.
[12]
Lozano,
S.;
La añe a,
J.
y
Onie a,
L.
(1991). "Plani icación Mul-
ini el con Limi aciones de
Capacidad".
Qües iió, Vol.
15.
[13]
Maes,
J.
y
Van
Wassenho e,
L.
(1986). "A simple Heu is ic o
he
Mul i-i em Single-Le e!
Capaci a ed
Lo -Sizing
P oblem".
Ope a ions
Resea ch Le e s, Vol. 4, 265-273.
(14]
Maes,
J.
y
Van
Wassenho e,
L.
(1986). "Mul i-i em Single-Le e} Ca-
paci a ed
Dynamic Lo -Sizing Heu is ics: A
Compu a ional
Compa ison
(Pa
1:
S a ic
Case)".
IEE
T ansac ions, Vol.
18,
114-123.
93
[15]
Maes,
J.;
McClain,
J.O.
y
Van
Wassenho e,
L. (1991). "Mul ile el
Capaci a ed Lo sizing Complexi y and
LP-based
Heu is ics". Eu opean
J.
o
Ope a ional Resea ch, Vol. 53, 131-148.
[16]
Manne,
A.S.
(1958). "P og amming o Economic Lo Sizes". Mana-
gemen Science, Vol. 4, 115-135.
[17]
Ma s en,
R.E.
(1975). "The
Use
o he
BOXSTEP Me hod in Disc e e
Op imiza ion". Ma hema ical P og amming S udy, Vol. 3, 127-144.
[18]
Newson,
E.F.
(1975). "Mul i-i em Lo Size Scheduling by Heu is ic.
Pa
1:
Wi h
Fixed Resou ces". Managemen Science, Vol. 21, 1186-
1193.
[19]
O
nie a,
L.;
Lozano,
S.;
La aiie a,
J.
y
Ruiz,
R.
(1987). "Mé odo
P imal Dual
pa a
Modelos de Plani icación con Cos es Cónca os y Li-
mi aciones de Capacidad". Qües iió, Vol.
11,
117-133.
[20]
Sil e ,
E.A.
y
Meal,
H.
(1973). "A Heu is ic o Selec ing Lo -Size
Quan i ies o he Case o a De e minis ic Time-Va ying Demand
Ra e
and Disc e e Opo uni ies o Replenishmen ". P oduc ion and In en-
o y Managemen , Vol.
12,
64-74.
[21]
Thizy,
J
.M.
y
Van
Wassenho e,
L. (1985). "Lag angean Relaxa-
ion o he Mul i-i em Capaci a ed Lo -Sizing P oblem: A Heu is ic
Implemen a ion".
IIE
T ansac ions, Vol.
17,
308-313.
[22]
Wagne ,
H.M.
y
Whi in,
T.M.
(1958). "A Dynamic Ve sion o
he
Economic Lo Size M o del". M anagemen S cien
ce,
Vol. 5, 89-96.
[23]
Zangwill.
W.I.
(1968). "Minimun Con a e Cos Flows in Ce ain
Ne wo ks". Managemen Science,
Vol.
14,
429-450.
ENGLISH
SUMMARY:
COMPLEMENTARY
HEURISTIC
TO
DUAL
APPROACHES
TO
THE
CAPACITATED
LOT-SIZING
PROBLEM
S.
Lozano, J. La añe a y
L.
Onie a
l.
INTRODUCTION
The
single le e! capaci a ed lo -sizing p ciblem (SLCLSP) consis s in de e -
mining he quan i ies and iming o p oduc ion ba ches in o de
o
sa is y known
94
o expec ed ex e na! equi emen s while incu ing in mínimum cos s.
No
back-
logging is allowed.
The e
a e limi s on he
amoun
o
esou ce a ailable in each
pe íod.
This
p oblem is known
o
be N
?-Comple e
[7].
2.
MODEL
FORMULATION
Le :
N -Numbe
o
i ems
L -Numbe
o
pe iods
Zi
-
P oduc ion
o
í em
i in pe iod
l¡ -ln en o y
o
i em
i in pe iod
D¡ -
Demand
o
i em
i in pe iod
s¡
-Se up cos o i em i
p¡ -Ma ginal p oduc ion cos o i em i
h¡
-Uni holding cos o í em i
I<
-A ailable capaci y in pe iod
a¡
-Se up ime o i em i
b¡
-Capaci y abso p ion coe icien o
í em
i
The
ma hema ical
model
is:
whe e
N L
Min
¿¿
(s¡6(xi ) +
PiXi
+ h¡l¡ )
i=l
=l
subjec o
Ii, -1
+
Xi -
li =
Di
i = 1,
...
,
N;
=
1,
..
.
,L
N
2::::
(a¡c5(xi ) +
b¡Xi ):::;
/{1 =
1,
...
, L
i=l
Xi
2:
O,
[¡,
2:
O,
/¡o
= O
6(:z:)
= {
~
95
si x
>O
si
:e=
O
This p oblem can be e o mula ed in e ms o dominan schedules. Such
schedules a e he ones o whoch he ollowing holds:
+s
Xi
=
¿nik
S =
0,
1,
2,
...
k=
This
is
known as Manne's
[16]
o mula ion:
whe e
N F
Min
¿¿c;;B;;
i=lj=l
N F
subjec o
LLmij Bij
~
K =
1,
2,
...
, L.
i=li=l
F
¿oij
= 1 i =
1,
2,
...
,
N.
j=l
B;i
=O,
1
L
Cij
¿ (s;b(Xij ) + p¡Xij + h¡Jij )
=l
iij
a¡b(Xij ) + b;Xij
3.
APPROXIMATE
SOLUTIONS
The
p e ious linea p og am
is
di icul o sol e because o he big numbe
o a iables in ol ed.
I
has been sol ed using specialized la ge scale algo i hms
([3],
[4],
[10],
[18]). Ano he p ac ica! app oach is o use p imal heu is ics
{[5],
[20],
[8],
[2],
[13],
[14]).
Howe e , a mo e p omising app oach
is
o use a dual app oach ([21],
[19],
[11],
[12]). This app oach consis s in elaxing he capaci y cons ain s, com-
pu ing adequa e shadow p ices.
The
uncapaci a ed elaxed p oblem can be
independen ly sol ed o each i em.
The solu ion o Manne's o mula ion assumes a linea app oxima ion o he
se up consump ion o capaci y. Thus, he esul ing p oduc ion plan usually is
96
un easible. The e o e,
i
is necessa y
o
de ise a manne
o
look o easibili y
by mino modi ica ion o he solu ion.
4.
HEURISTIC
This
sec ion
desc ~bes
a heu is ic aimed
a
ob aining a easible p oduc ion
plan.
I
can be used in p oblems wi h se up imes. Recall
ha
in his case, e en
o
ind such a solu ion is N
P-comple e
(15].
The
heu is ic consis s in educing he capaci y equi emen s in hose pe iods
in which insu icien capaci y exis s. S a ing wi h
he
las pe iod,
he
p e ious
pe iod in which in easibili y occu s is de ec ed
and
h ee
a emp s
a e
made
o
elimina e i .
I
hese
a emp s
a e success ul, hen he closes p e ious pe iod
showing in easibili y is conside ed nex and he p ocess is epea ed.
I
he
algo-
i hm
ails
o
elimina e he in easibili y in any o hese pe iods,
i
s ops.
I ,
in
u n,
pe iod O
is
eached, a easible p oduc ion plan has been ound.
The
h ee
a emp s
a e called Blocks
1,
II and III because
ha
is he o de in which hey
a e applied.
Block 1 spli s lo s c ea ing new se ups in la e pe iods wi hou in oducing
new in easibili ies. I ems a e conside ed in non-dec easing o de
o
he
ollowing
a io.
This
a io penalizes he cos and ime due
o
he new se ups
and
a ou s
holding cos sa ings and in easibili y educ ion.
As
a consequence, his ou ine
makes
be e
use o he a ailable capaci y
s¡(a¡ +
1)
b;h;
o
he
la e pe iods o he ho izon. Such unused can be
impo an
depending
on he deg ee o ba ching o he solu ion. An example o his si ua ion is
he
o en ound ini e-ho izon e ec which consis s in
ha
he la es pe iods se ups
a e a ely cos e ec i e.
Block
11
shi s p oduc ion o ea lie pe iods in which a se up al eady exis s
and
enough slack is a ailable.
l ems
a e conside ed in non-dec easing o de
o
he a io
h¡ b;
which penalizes holding cos inc ease
and
a ou s in easibili y
educ ion. These shi s lead
oan
inc ease in holding cos s hough no addi ional
se up cos s a e incu ed. E en se ups can be sa ed in he easible pe iod i en i e
lo s a e shi ed.
97

Block
111
also shi s p oduc ion o ea lie pe iods wi h slack capaci y
bu
c ea ing new se ups. I ems a e conside ed in non-dec easing o de o he a io
s¡h¡(a¡ + 1)
b¡
which penalizes se up and holding cos inc ease, and esou ce consump ion due
o
he new se ups, a ou ing in easibili y educ ion. E e y shi inc eases
bo h
se up and holding cos s. The e o e, his ou ine is in oked only
i
blocks 1 and
II ail o elimina e all he in easibili y in he gi en pe iod.
5.
INTEGRATION
WITH
DUAL
APPROACHES
The
p oposed heu is ic
is
a pe ec complemen o dual app oaches since he
la e
upda e
he esou ce p ices in e e y i e a ion gene a ing a cos e ec i e
solu ion (composed o dominan schedules) which, un o una ely, is no easible.
The
heu is ic makes mino adjus men s o such solu ions in o de o imp o e i s
easibili y. In pa icula ,
i
has been in eg a ed wi h a p imal dual app oach
[11]
and he subg adien me hod
[21].
Also, dual app oaches p o ide lowe bounds on he op imal solu ion, which
can be used o assess he quali y o he solu ion ob ained by he heu is ic.
6.
COMPUTATIONAL
EXPERIENCES
The
heu is ic, appended o he p imal dual and subg adien me hods, has
been applied o se e a! p oblems, compa ing he solu ion ob ained o hose p o-
ided
by
o he heu is ics
([8],
[13]).
The esul s a e included in able
l.
They
show he me i o his heu is ic app oach.
98