En ique C. DIEZ DE CASTRO
Uni e sidad H ispalense
UN PROCEDIMIENTO HEURISTICO
PARA LA RESOLUCION DEL
PROBLEMA DEL TALLER
El p oblema del alle como odos los p oblemas de secuencia-
ción son de g an complejidad. Los p ocedimien os de esolución no
son áciles de aplica . Po ello p esen amos un p ocedimien o sencillo
que pe mi a sal a los incon enien es an e io es.
I) INTRODUCCION
De los cinco p ocesos básicos que componen la adminis ación
(Plani icación, O ganización, di ección, do ación de Pe sonal y con
ol), el más impo an e, p ima io y que p e alece sob e los demás es el
de plani icación.
Todo p oceso plani icado implica la cons i ución de una se ie de
líneas posibles de acción y la selección o elección de una de ellas, es
deci , compo a una oma de decisiones.
Pa a e ec ua la elección en e las di e en es al e na i as posee
mos es c i e ios álidos (1):
a) LA EXPERIMENTACION.- Consis e en p oba las di e en es
al e na i as seleccionando aquella que nos p opo cione me
jo es esul ados.
Sin emba go, al como a i ma Newman (2) la écnica expe
imen al debe ía se u ilizada como un úl imo ins umen o
una ez que se hayan p obado o as écnicas de plani ica
ción.
b) LA EXPERIENCIA.- Es un ac o muy impo an e que combi
nado con la in uición puede consegui esul ados muy sa is
ac o ios.
c) INVESTIGACION Y ANALISIS.- Es el c i e io más e ec i o y
usado pa a selecciona al e na i as. Una de las ap oximacio
nes mas comple as de in es igación y análisis en la oma de
decisiones la cons i uye la in es igación Ope a i a, ambién
denominada análisis ope acional o “Ciencia de la Adminis
ación”. 57
No obs an e, la In es igación Ope a i a a la ho a de oma
decisiones no pasa de se una ecomendación, una ayuda
pa a que el esponsable de la oma de decisiones pueda es
coge un camino mejo que le lle e a alcanza los obje i os
de la emp esa (3).
Conscien es de la g an impo ancia que ep esen an los
c i e ios empí icos, in ui i os y de in es igación y análisis
pa a oma decisiones, hemos p ocu ado diseña un modelo,
pa a la esolución del p oblema del alle , que enga inclui
dos odos los c i e ios ci ados an e io men e.
II) PROBLEMA DEL TALLER: ENUNCIADO.- (4 a 9)
También denominado “p oblema de secuencias”, “machine se
quencing” o “Job shop scheduling”.
El p oblema del alle in es iga una secuencia óp ima (o en su de
ec o lo más p óxima posible) pa a p ocesa “n” a ículos en “m” má
quinas, siendo el óp imo aquella secuencia que minimiza el iempo o
al de ejecución ( iempo necesa io pa a ealiza odas las ope aciones
(10) que compo an los a ículos).
Respe ando las siguien es condiciones:
A) Rela i as a las máquinas:
1o) Podemos elegi lib emen e la secuencia de ope aciones en
cada máquina.
2o) Ninguna máquina puede ealiza dos a eas simul áneamen
e.
B) Rela i as a ios a ículos:
3o) Las ope aciones eque idas po un a ículo ienen que se
ealizadas en unas máquinas especí icas.
4o) Las ope aciones son ealizadas en un o den écnicamen e
p esc i o.
5o) Hay ope aciones que pueden ealiza se consecu i amen e;
o as, sin emba go, ienen que ealiza se necesa iamen e de
una mane a secuencial.
6o) Se usan iempos de e minís icos.
7o) El iempo de p oceso es independien e de la secuencia.
8o) Se asigna a cada ope ación un iempo ini o. Es deci , el
iempo necesa io pa a que se ealice la a ea y, pa a que ca
da pa de ope aciones, que se deban se e ec uadas conse
cu i amen e, engan un e aso mínimo en e el comienzo de
la p ime a y de la segunda.
9o) Cada ope ación debe se lle ada a cabo an es de las a eas
que le siguen.
58
C) O as conside aciones:
10°) Los iempos de anspo e, inicio y inal de ac i idad son
conside ados desp eciables o bien pa e del iempo de a a
mien o.
11°) No exis en cancelaciones.
12°) No se iene en cuen a las a e ías de las máquinas y la ue 
za humana se conside a cons an e.
Es e p oblema se inse a, po lo an o, den o de la clase de p o
blemas que cons i uyen el p oblema cen al del o denamien o, una ez
aducidas las es icciones disyun i as en desigualdades de po en
cial.
El que no se p oduzcan o se den las condiciones mencionadas an
e io men e, no impide la esolución del p oblema. Sin emba go, la
complejidad del mismo aumen a en mayo o meno medida si no se
espe an.
Hay que ene en cuen a que pa a “m” máquinas y “n” a ículos
exis en (n)m combinaciones.
NOTAS:
1o) Un a ículo pa a su e minación necesi a, gene almen e, se
p ocesado en odas las máquinas. En caso con a io, pa a
es as si uaciones c ea emos una ope ación ic icia de du a
ción “0”.
2o) Pa a los a ículos hay una indi e encia en el o den de ealiza
ción de l'as a eas en cada máquina, (así po la máquina 1
deben pasa “n” a ículos, pe o puede hace lo p ime amen e
la ope ación co espondien e al p ime a ículo, al segundo o
al enésimo; en segundo luga , puede ejecu a se cualquie a
de las n-1 a eas es an es, y así sucesi amen e). Es a ca ac
e ís ica, nos mues a que el p oblema es al amen e combi
na o io.
3o) P oblema combina o io según N. Agin (11) es “aquel que se
le a ibuyen unos alo es disc e os núme icos a cie o con
jun o ini o de a iables, de al mane a que sa is aga un con
jun o de es icciones y eduzca al mínimo la unción obje i
o de dichas a iables”.
Los p oblemas de alle podemos clasi ica los, a su ez en dos i
pos dis in os:
TIPO I.- Los a ículos se p ocesan en las máquinas en un o den co
mún. Una ez ijado el o den de paso de los a ículos en una máquina,
ese mismo o den se sigue pa a las es an es máquinas.
TIPO II.- Cada a ículo iene un o den di e en e de paso po las má
quinas. Es e o den iene especi icado po el p oblema.
59
Ill) METODOS DE RESOLUCION
Debido a la ex ao dina ia complejidad del p oblema, una solu
ción ob enida median e una écnica que nos o ien e hacia una secuen
cia óp ima o p óxima ai óp imo sin ene que p oba la o alidad o la
mayo ía de ales soluciones iene un alo conside able.
Exis en pa a es e p oblema es ipos de mé odos:
A) METODOS DE SIMULACION.- Es os mé odos se u ilizan co
mo un ins umen o auxilia en la esolución de p oblemas de
na u aleza combina o io. Así, Kau mann (12) señala que
“cuando no se conoce un algo i mo (13) de op imización, o
al a un mé odo heu ís ico acep able pa a mejo a una solu
ción inicial se puede u iliza un mé odo de simulación”.
La simulación ué la p ime a ía po la que se in en ó la
esolución del p oblema del alle . Su alidez es discu ible, y
la apa ición de o os mé odos más e inados pos e ga on su
empleo en la esolución del p oblema que nos ocupa.
B) METODOS HEURISTICOS.- Es os mé odos se u ilizan cuando
no se conoce ningún algo i mo de op imización, y exis e la
necesidad p ác ica de encon a una solución bien si uada
en elación al óp imo (que e iden emen e no se conoce). Se
pa e de una solución ac ible (la que sa is ace las es iccio
nes) y se a mejo ando median e el mé odo, sin ene la se
gu idad de que se con e ge hacia el subconjun o de solucio
nes óp imas (14).
Es e concep o de Kau mann puede se complemen ado
con el de Ba e sby (15): “ ales mé odos se u ilizan cuando
no se puede ob ene la mejo solución po no conoce se un
mé odo analí ico adecuado o si se conoce po no se écni
camen e ealizable”.
A nues o juicio la mejo de inición de mé odo heu ís ico
la encon amos en Kau mann (16): Se a a de un mé odo
que no se puede acep a del odo igu osamen e, pe o que
p opo ciona esul ados su icien es pa a la p ác ica.
C) METODOS DE OPTIMIZACION.- Con es os mé odos, se in en a
consegui una economía ela i a, es deci , que la p oximidad del óp i
mo alcanzada nos epo e un mayo bene icio que el cos e u ilizado pa
a dicho in.
Los mé odos de op imización consis en, según Kau mann (17), en
sepa a el conjun o de soluciones en dos pa es, una de las cuales
con iene con oda segu idad el subconjun o de soluciones óp imas y
la o a no, con lo cual se a pasando de unos subconjun os a o os me
no es has a ob ene median e es e c ibado el subconjun o óp imo. Se
puede ope a ambién siguiendo el p ocedimien o de descomposición
imponiendo solamen e que en la pa e seleccionada haya con oda se
gu idad alguna (o algunas) solución óp ima, pe o pudiendo habe algu
nas, ambién, en la pa e desechada; de es a o ma, al inal no se en
d á, al ez, el’ subconjun o óp imo en e o, pe o si algunos de sus ele
men os que es lo que habi ualmen e se busca.
60
Las soluciones mas ele an es po cada mé odo de esolución y
pa a los di e en es ipos se elacionan a con inuación (18):
METODO TIPO I TIPO II
-Á) SIMULACION Ramboz (19) Rowe-Jachson (20)
B) HEURISTICOS Johnson (21)
Palme (22)
C) OPTIMOS Lomnichi (23)
Ignall-Sch age (24) Bowman (25)
Manne (26)
G eenbe g (27)
IV) PROCEDIMIENTO PROPUESTO PARA LA RESOLUCION DEL PRO
BLEMA DE TALLER DEL TIPO II.
Es un p ocedimien o heu ís ico consis en e en la cons ucción de
una a bo escencia. Pa a su elabo ación nos apoya emos en esul ados
ob enidos median e la ealización de un conjun o de diag amas de
Gan . Es os diag amas es a án compues os po un núme o de ba as
igual al núme o de a ículos conside ados en el p oblema. Cada ba a
lle a á ma cado el iempo empleado en las sucesi as máquinas po el
a ículo y, po supues o, en el o den de ejecución ecnológicamen e
p esc i o po el p oblema.
ALGORITMO.- Cons a de es ases:
A) COMIENZO.- Sumamos las du aciones de las a eas co es
pondien es a cada a ículo. El alo mas al o ob enido lo
asignamos al nudo inicial que cons i uye la co a aiz de la
a bo escencia.
B) DESARROLLO.- Una es icción disyun i a implica dos al e 
na i as: que un abajo p eceda a o o en una máquina ó, ca
so con a io, sea con inuación del mismo. La solución del
p oblema del alle se consigue con la eliminación de las
es icciones disyun i as y su conse ación en desigualda
des de po encial. La con e sión se puede hace de dos o 
mas:
1. °) Empí icamen e, p e io examen de enido del p oblema, pode
mos elegi una de las al e na i as que indica una es icción
disyun i a sin ene que p oba cual de las dos es la mejo .
Rep esen amos el p oblema en un diag ama de ba as que
con empla es a es icción. El alo de iempo esul an e en
el g á ico cons i uye la co a de una ama descenden e desde
el nudo p e io.
Cuando la elección en base al exámen del p oblema no es
cla a, p ocede emos a ealiza la a a és de la segunda o 
ma.
2. °) A pa i del nudo de co a meno hacemos dos amas descen
den es. Cada ama ep esen a una al e na i a de una es ic
ción disyun i a. P ocedemos a su ep esen acióh y ob en
ción de co as.
61

Repe imos i e a i amen e es e apa ado B) has a que al
cancemos el inal del p oblema (apa ado C).
C) FINAL.- La solución del p oblema se hab á alcanzado cuan
do lleguemos a un nudo que ep esen e una solución ac i
ble ( odas las es icciones disyun i as han sido ans o ma
das en desigualdades de po encial) y el alo de la co a co
espondien e, sea la meno de la a bo escencia.
En el anexo I p esen amos un caso ilus a i o.
V) CONSIDERACIONES.
Respec o al p ocedimien o aquí desc i o con iene es ablece las
siguien es pun ualizaciones:
a) Solo es álido pa a p oblemas de dimensión educida.
b) Pa a el desa ollo del p ocedimien o y ob ención de una so
lución sa is ac o ia, juega un papel undamen al la in uición
y expe iencia en la esolución de p oblemas de es e ipo. No
ecomendamos su u ilización en aquellas pe sonas no e sa
das y no conocedo as del p oblema.
c) Es ácil comp ende que el deshace empí icamen e una es
icción disyun i a ocasiona á, si la decisión adop ada es
e ónea, una solución más o menos alejada del óp imo, se
gún sea la ascendencia de dicha decisión.
d) Las decisiones empí icas, indudablemen e, educen en g an
medida la complejidad del p oblema, su p edominio es á en
elación di ec a con la dimensión del p oblema a esol e .
ANEXO 1.- CASO ILUSTRATIVO.
T es a ículos deben se p ocesados en máquinas. El a ículo 1 de
be se p ocesado p ime o en la máquina 3 y pos e io men e en la 2. El
a ículo 2 debe, en p ime luga , se a ado en la máquina 2 y a con i
nuación en la 1. El a ículo 3 sigue en las máquinas el siguien e o den:
máquina una- es-dos.
Los iempos de ealización se dan en el siguien e cuad o.
ARTICULOS MAQUINA 1 MARQUINA 2 MAQUINA 3
1308
2730
3543
62
A) COMIENZO.-
A ículo 1
” 2
RAIZ
B) DESARROLLO
MAQUINA 1
a) A ículo 1 y 2 an es que el 3.
A ículo 1
” 2
” 3
63
b) A ículo 1 an es que a ículo 2.
c) A ículo 2 an es que el a ículo 1.
i
-------------
1
-------------
1
-------------
1
-------------
1
0 5 10 15 20
A1 an es
MAQUINA 2
A ículo 2 an es a ículo 3
A1 an es A3
A2 ” A3
A2 an es A1
A3 an es A3
MAQUINA 1
MAQUINA 2
64
MAQUINA 3.- A ículo 1 an es que a ículo 3.
A ículo 1 M3 M1
M2 M1
M1 M3 M2
10 15
MAQUINA 1
MAQUINA 2
MAQUINA 3
SOLUCION: O den de paso de los a ículos po las máquinas.
Máquina 1.- A ículo 3-2-1
Máquina 2.- ” 2-3
Máquina 3.- ” 1-3
■¿S E B E .65