programación de la producción
Post on 17-Nov-2015
10 Views
Preview:
DESCRIPTION
TRANSCRIPT
-
8
INGENIATOR | REVISTA VIRTUAL DE LOS PROGRAMAS DE INGENIERA|UNIVERSIDAD DE SAN BUENAVTURA, SECCIONAL
CARTAGENA | Vol.3, N4, enero junio del 2012 | ISSN 2027-9396 (en lnea) | CARTAGENA, COLOMBIA | PP. 8-23
ANLISIS DE MEJORAMIENTO EN LA PROGRAMACIN DE LA
PRODUCCIN DE UN TALLER DE FABRICACIN DE PAPEL Y CARTN Y
DERIVADOS
Arias, E . l , Licero, N2, Martnez, D.2, Rodrguez, A.3
'Qumico de la universidad de Cartagena, Estudiante de Maestra Ingeniera Industrial de
la Universidad Tecnolgica de Bolvar, Cartagena
ejaca@hotmail. Com
2Ingeniero industrial universidad tecnolgica de Bolvar Cartagena, instructor centro para
la industria petroqumica - Sena, Cartagena
nliceroarzuza@misena. edu. Co
3Ingeniero industrial de la universidad Simn Bolvar Barranquilla, instructor centro para
la industria petroqumica - Sena, Cartagena
dmartinezsierra@misena. edu. Co
4Ingeniero Qumico de la universidad del Atlntico Barranquilla,
Estudiante de Maestra Ingeniera Industrial de la Universidad Tecnolgica de Bolvar,
Cartagena
acromatu@gmail.com
Recibido 29 de febrero de 2012
Aceptado 28 de Junio de 2012
RESUMEN
La programacin de trabajos es una labor diaria de las empresas del sector de productos y
servicios donde se busca optimizar uno o varios objetivos. Se propone mejorar el tiempo
total de ejecucin de todas las tareas. En este documento se presenta los resultados
obtenidos a travs de las diferentes reglas de despacho y la tcnica de optimizacin
Johnson. Este trabajo est basado en datos de un caso real de la industria de fabricacin
de papel cartn y derivados. Por tanto, el problema flow-shop se refiere a una
configuracin enfocada al producto, considera el makespan como funcin objetivo a ser
minimizada, resolver el problema significa determinar la permutacin que entregue el
menor valor de makespan. Se presenta los resultados obtenidos, una programacin
siguiendo diferentes reglas de despacho y aplicando algoritmo de Johnson, para comparar
cual ofrece mejor solucin en cuanto makespan (Cmax).
Palabras Claves: algoritmo de Johnson, flow-shop, heurstica, productividad, reglas de
despacho, secuencias de trabajos
mailto:acromatu@gmail.com
-
9
INGENIATOR | REVISTA VIRTUAL DE LOS PROGRAMAS DE INGENIERA|UNIVERSIDAD DE SAN BUENAVTURA, SECCIONAL
CARTAGENA | Vol.3, N4, enero junio del 2012 | ISSN 2027-9396 (en lnea) | CARTAGENA, COLOMBIA | PP. 8-23
ABSTRACT
The work schedule is a daily work of the companys products and services which seek to
optimize one or more goals. It aims to improve the total execution time of all tasks. This
paper presents the results obtained from the different dispatching rules and the optimization
technique Johnson. This work is based on data from a real case of the papermaking industry
and cardboard products. Therefore the flow-shop problem refers to a product-focused
settings, consider the make span as objective function to be minimized, the problem
involves determining the permutation that delivers the lowest value of make span. We
present the results, a schedule according to different dispatching rules and applying
Johnson algorithm to compare which offers better solution as make span (Cmax).
Keywords: algorithm Johnson, flow-shop, heuristic, productivity, rule of dispatch, works
sequence,
1. INTRODUCCIN
La productividad tambin conocida como efectividad es la relacin entre la produccin
obtenida por un sistema de produccin o servicios y los recursos utilizados para obtenerla.
La preocupacin de una empresa debe ser aumentar su productividad lo cual es posible
produciendo ms con menos recursos, una de las maneras de lograr esto es haciendo una
continua revisin de la forma como se realiza la programacin de sus trabajos.
Desde hace varios aos, las empresas y organizaciones del mundo tienen la necesidad de
contar con una herramienta comn para cumplir a sus clientes. Hoy en da estas mismas
organizaciones le quieren seguir demostrando al mundo su compromiso con el cliente a
travs de una programacin efectiva de la produccin.
Mediante la realizacin del presente trabajo, se quiere efectuar un anlisis de mejoramiento
de la programacin de la produccin a una empresa de fabricacin de papel, cartn
ondulado, envases y empaques que permita optimizar el uso de los recursos, de manera
que alcance los objetivos globales de produccin.
Este sub sector muestra una tendencia creciente en el periodo comprendido entre 2005 y
2008, tanto en unidades vendidas al pasar de 383. 258. 258 en el 2005 a 1.064.058.809 en
el 2008 (Superintendencia de Sociedades, 2010), como en nmero de compradores
minoristas; adems se resalta el hecho que los costos y gastos variables mantuvieron unas
cifras estables en este periodo de tiempo.
En los ltimos aos se ha podido establecer como factores caractersticos de este sector los
siguientes:
Aumento del volumen demandado.
-
10
INGENIATOR | REVISTA VIRTUAL DE LOS PROGRAMAS DE INGENIERA|UNIVERSIDAD DE SAN BUENAVTURA, SECCIONAL
CARTAGENA | Vol.3, N4, enero junio del 2012 | ISSN 2027-9396 (en lnea) | CARTAGENA, COLOMBIA | PP. 8-23
Aumento de los ciclos de vida de los productos. Con objeto de aumentar las ventas no se han variado muchos los diseos convirtindose en un componente de aceptacin ante
la opcin de usar materiales en un producto que no contamina el medio ambiente
Poca variedad y poca personalizacin de la oferta. Por ser este un mercado maduro, la poca competencia ha hecho que las empresas disminuyan la oferta lo que finalmente ha
incidido en pocos nmeros de formatos y acabados.
Disminucin de los plazos de entrega. Al disminuir la diferencia entre los propios productos se ha intentado mejorar el servicio mediante la reduccin de los plazos de
entrega.
Estos factores han afectado a la forma de aprovisionamiento, ahora el cliente realiza
pedidos pequeos y frecuentes, lo cual supone un reto en el equilibrio almacenamiento-
produccin, y por tanto a la programacin de la produccin como elemento fundamental en
dicho equilibrio. Una forma de favorecer este equilibrio es ayudando a flexibilizar el
sistema productivo; proporcionando tcnicas y herramientas de programacin de la
produccin que permitan la incorporacin de los pedidos en el momento de producirse la
necesidad, sin que ello suponga una perturbacin en el proceso de programacin de la
produccin previamente establecido.
En este contexto, este trabajo presenta el comportamiento de las reglas de despacho ms
conocidas en la literatura, con el fin de poder analizar su comportamiento ante las medidas
de prestaciones propuestas en funcin de los factores tpicos de la industria de fabricacin
de papel, cartn ondulado, envases y empaques.
Se considera como una parte del problema, el sistema flow-shop , que se caracteriza porque
todos los productivos siguen la misma secuencia de trabajos y para ello se podra numerar
todas las secuencias posibles y elegir aquellas que optimizan alguna medida de desempeo
mediante la incorporacin de una regla de despacho. Aqu se propone como alternativa de
solucin del problema disminuir el lapso de tiempo (minimizar el tiempo de ocio) mediante
la aplicacin del algoritmo de Johnson.
2. ESTADO DEL ARTE
2.1 EL PROBLEMA DE FLOW SHOP
En el problema del Flow Shop tenemos un conjunto de n trabajos o tareas, (1,. . ., n) que
deben procesarse en m mquinas o estaciones (1, . . . , m). En un taller de flujo el orden de
los trabajos en las mquinas es el mismo, esto es, primero la mquina 1, despus la 2 y as
hasta la mquina m. El objetivo es encontrar una secuenciacin de los trabajos en las
mquinas de tal manera que se optimice algn criterio dado. El criterio ms utilizado en la
literatura es la minimizacin del tiempo de flujo total o makespan de la secuencia (Cmax).
Los tiempos de proceso de los trabajos en las mquinas se definen como pij , donde i = 1, .
-
11
INGENIATOR | REVISTA VIRTUAL DE LOS PROGRAMAS DE INGENIERA|UNIVERSIDAD DE SAN BUENAVTURA, SECCIONAL
CARTAGENA | Vol.3, N4, enero junio del 2012 | ISSN 2027-9396 (en lnea) | CARTAGENA, COLOMBIA | PP. 8-23
. . , n y j = 1, . . . ,m. Para este problema existen una serie de simplificaciones (Baker
(1974)):
Cada trabajo i puede ocupar, como mucho, una mquina j al mismo tiempo.
Cada mquina m puede procesar, a lo sumo, un trabajo i a la vez.
El proceso de un trabajo i en una mquina j no se puede interrumpir.
Todos los trabajos son independientes entre s y se encuentran disponibles en el instante 0.
Los tiempos de cambio de partida de los trabajos en las mquinas son independientes de la secuencia y estn incluidos en los tiempos de proceso.
Las mquinas se encuentran continuamente disponibles.
Se permite almacenar producto en curso.
Para resolver el problema del Flow Shop se han propuesto diferentes tcnicas y
metodologas con el fin de encontrar la secuencia ptima cumpliendo con los diferentes
objetivos como la inexistencia de tiempos muertos de fabricacin, reduccin de tiempo de
cambio y ajustes de las maquinas, anulacin de retrasos entre otros, teniendo en cuenta las
restricciones propias de cada situacin especfica como la velocidad de proceso de las
maquinas, capacidad de recursos humanos y materiales etc.
Desde la publicacin del artculo de Johnson en 1954, el estudio terico del Flow Shop ha
constituido uno de los tpicos ms investigados en la teora de la programacin. Su inters
no viene motivado nicamente por su inters prctico, sino por la aparente simplicidad a la
hora de plantear y la consideracin de que an hoy da, constituye un problema difcil de
resolver. (Lahdari, 2004) Es bien conocido que el cado de dos mquinas en el caso del
Flow Shop puede ser resuelto utilizando las reglas de Johnson, que genera una
programacin ptima en O (n log n) pasos.
El problema se clasifica como F//Cmax siguiendo la notacin // de Graham et al.
(1979) y es NP-Completo cuando m 3 (Garey et al., 1976). En general, hay un total de
(n!) m secuencias posibles. Normalmente el problema se simplifica no permitiendo que un
trabajo pase a otro (job passing), o lo que es lo mismo, la secuencia inicial de los trabajos se
mantenga para todas las mquinas. De esta manera slo existen n! secuencias posibles. En
este caso el problema se conoce como taller de flujo de permutacin o n/m/P/Fmax
(Pinedo, 1995). Este trabajo se centra en este ltimo tipo de problema.
En la literatura existen ya comparativas de tcnicas de resolucin para este problema, por
ejemplo, en Ponnambalam et al. (2001), se evalan 5 heursticas diferentes, pero solo
contra 21 sencillos problemas test. Turner y Booth (1987) comparan dos heursticas
conocidas con un conjunto de 350 problemas aleatorios. En el trabajo de Byung Park et al.
(1984), se comparan 16 heursticas con un conjunto de 1500 problemas generados
aleatoriamente de un tamao de hasta 30 trabajos y 20 mquinas. Dannenbring (1977)
evalu 11 mtodos con 1580 problemas, tambin aleatorios. Finalmente, Ashour (1970),
hizo una comparativa de mtodos exactos para el Flow Shop de permutacin.
-
12
INGENIATOR | REVISTA VIRTUAL DE LOS PROGRAMAS DE INGENIERA|UNIVERSIDAD DE SAN BUENAVTURA, SECCIONAL
CARTAGENA | Vol.3, N4, enero junio del 2012 | ISSN 2027-9396 (en lnea) | CARTAGENA, COLOMBIA | PP. 8-23
Todas estas comparativas tienen varios inconvenientes; no se utilizan sets de datos
estndares y/o los sistemas informticos utilizados no son los mismos, por lo que los
resultados no son comparables ni generalizables. Las comparativas se hacen con tan solo
unos pocos mtodos y normalmente son siempre los mismos. Adicionalmente, no existe
ninguna comparativa actual que nos permita evaluar los ltimos mtodos aparecidos para
el problema. Tambin es difcil encontrar comparativas en las que se incluyan mtodos
metaheursticos avanzados como Simulated Annealing o Algoritmos Genticos.
Matemticamente, se podra hablar de un problema que requiere encontrar la permutacin
de las tareas para ser resuelto. Este tipo de problemas de secuenciamiento de sistemas de
manufactura es clasificado de NP-hard, Un problema NP-hard se presenta cuando un
algoritmo que intenta solucionarlo, aumenta su tiempo de ejecucin, en el peor de los casos,
de forma exponencial al tamao del problema. (Johnson,1954) El reto est en encontrar
algoritmos que exploren favorablemente la estructura matemtica del problema, para que
sean capaces de obtener una respuesta para la mayora de las instancias del mismo, en
tiempos de ejecucin relativamente pequeos.
2.2 ALGORITMO DE JOHNSON
El algoritmo de Johnson (1954) es la primera heurstica conocida para el PFSP, que se basa
en la siguiente regla: el trabajo i precede al trabajo j si min{pi1, pj2} < min{pj1, pi2} Este
algoritmo proporciona una solucin ptima para el PFSP con 2 mquinas y puede
generalizarse para el caso general con m mquinas agrupando las m mquinas en dos
mquinas virtuales.
El algoritmo de Johnson es una forma de encontrar el camino ms corto entre todos los
pares de vrtices de un grafo dirigido disperso. Permite que las aristas tengan pesos
negativos, si bien no permite ciclos de peso negativo. Funciona utilizando el algoritmo de
Bellman-Ford para hacer una transformacin en el grafo inicial que elimina todas las aristas
de peso negativo, permitiendo por tanto usar el algoritmo de Dijkstra en el grafo
transformado. Su nombre viene de Donald B. Johnson, quien fuera el primero en publicar la
tcnica en 1977. El algoritmo de Johnson consiste en los siguientes pasos:
Primero se aade un nuevo nodo q al grafo, conectado a cada uno de los nodos del grafo por una arista de peso cero.
En segundo lugar, se utiliza el algoritmo de Bellman-Ford, empezando por el nuevo vrtice q, para determinar para cada vrtice v el peso mnimo h(v) del camino de q a v.
Si en este paso se detecta un ciclo negativo, el algoritmo concluye.
Seguidamente, a las aristas del grafo original se les cambia el peso usando los valores calculados por el algoritmo de Bellman-Ford: una arista de u a v con tamao w(u, v), da
el nuevo tamao w(u, v) + h(u) h(v)
-
13
INGENIATOR | REVISTA VIRTUAL DE LOS PROGRAMAS DE INGENIERA|UNIVERSIDAD DE SAN BUENAVTURA, SECCIONAL
CARTAGENA | Vol.3, N4, enero junio del 2012 | ISSN 2027-9396 (en lnea) | CARTAGENA, COLOMBIA | PP. 8-23
Por ltimo, para cada nodo se usa el algoritmo de Dijkstra para determinar el camino ms corto entre s y los otros nodos, usando el grafo con pesos modificados.
En el grafo con pesos modificados, todos los caminos entre un par de nodos s y t tienen la
misma cantidad h(s) h(t) aadida a cada uno de ellos, as que un camino que sea el ms
corto en el grafo original tambin es el camino ms corto en el grafo modificado y
viceversa. Sin embargo, debido al modo en el que los valores h(v) son computados, todos
los pesos modificados de las aristas son no negativos, asegurando entonces la optimalidad
de los caminos encontrados por el algoritmo de Dijkstra. Las distancias en el grafo original
pueden ser calculadas a partir de las distancias calculadas por el algoritmo de Dijkstra en el
grafo modificado invirtiendo la transformacin realizada en el grafo.
Hay que establecer la secuencia que cumpliendo las fechas de entrega de los pedidos
implique el menor tiempo total de los mismos. Existen distintas tcnicas para ello
aplicamos la regla de Johnson para N pedidos y 2 mquinas. Es un mtodo heurstico que
pretende minimizar el tiempo necesario para obtener todos los pedidos, as como el tiempo
ocioso de las mquinas.
Cuando hay ms de dos Mquinas el Algoritmo de Johnson no funciona excepto en
ocasiones especiales.
Un caso Especial se da cuando la mquina intermedia est dominada, por la primera o por
la tercera mquina. Una Mquina est Dominada cuando su tiempo de proceso ms largo es
menor o igual que el tiempo de proceso ms corto de las otras mquinas
Figura 1. Etapas del Algoritmo de Johson
Fuente: wikipedia. 2010
En la imagen de la izquierda tiene dos aristas negativas y no contiene ciclos negativos. En
la segunda imagen se muestra el nuevo vrtice q con peso 0 hacia todos los nodos. En la
tercera imagen, se muestra el rbol de caminos mnimos calculado con el algoritmo de
Bellman-Ford con q como vrtice inicial, y los valores h(v) calculados para cada otro nodo
como la longitud del camino ms corto entre q y ese nodo. A modo de ilustracin, en dicha
imagen solo aparecen los caminos que se tomaran para determinar cada valor h(v). Ntese
-
14
INGENIATOR | REVISTA VIRTUAL DE LOS PROGRAMAS DE INGENIERA|UNIVERSIDAD DE SAN BUENAVTURA, SECCIONAL
CARTAGENA | Vol.3, N4, enero junio del 2012 | ISSN 2027-9396 (en lnea) | CARTAGENA, COLOMBIA | PP. 8-23
que todos estos valores h(v) no son positivos, porque q tiene una arista de unin con cada
nodo de peso 0, y por tanto el camino ms corto no puede ser mayor que ese valor. En la
parte derecha se muestra el grafo modificado, hecho reemplazando el peso de cada arista
w(u, v) por w(u, v) + h(u) h(v). En este grafo modificado, todos los pesos de las aristas
son positivos y el camino ms corto entre dos nodos cualesquiera usa la misma secuencia
de aristas que en el camino ms corto entre los mismos dos nodos en el grafo original. El
algoritmo concluye aplicando el algoritmo de Dijkstra para cada uno de los cuatro nodos
originales en el grafo modificado (cuarta imagen).
2.3 REGLAS DE DESPACHOS
Esta metodologa consiste en planificar primeramente las operaciones cronolgicamente
prximas y luego aquellas ms lejanas. Cada vez que una mquina se desocupa, se asigna
una prioridad a cada una de las operaciones que estn disponibles para ser procesadas.
Segn explica Vepsalainen & Morton (1987), esta prioridad puede depender de los
siguientes elementos:
El tiempo de procesamiento de la operacin: si este tiempo sube, la prioridad de la operacin baja.
La ponderacin de la orden correspondiente: mayores ponderaciones obtendrn prioridades ms altas.
La proximidad de la fecha de entrega de la orden: fechas cercanas implicarn mayor prioridad.
La disponibilidad de la operacin: si la operacin no est inmediatamente lista para ser procesada entonces baja su prioridad.
Aquella operacin que obtiene la ms alta prioridad es elegida o despachada como el
siguiente trabajo en la mquina correspondiente, procedindose en forma anloga hasta
programar todas las operaciones.
Esta tcnica est ampliamente difundida en la Industria porque es fcil de entender e
implementar. No slo es utilizada por las personas encargadas de la planificacin, sino
tambin por la mayora de los sistemas de programacin automticos. Sin embargo, las
soluciones generadas son de muy baja calidad en problemas de tamao realista. De hecho,
esta metodologa es apodada como miope, pues slo considera informacin inmediata,
ignorando el horizonte total de planificacin.
Las reglas de despacho permiten definir las prioridades entre los trabajos que se encuentran
en un taller. Pueden ser sencillas, basadas en un dato del producto, como el tiempo de
procesamiento o la fecha de entrega; tambin se pueden obtener a travs de clculos entre
diferentes variables (como la holgura). Se encuentran Infinidad de reglas de despacho para
secuenciar trabajos entre estas tenemos:
-
15
INGENIATOR | REVISTA VIRTUAL DE LOS PROGRAMAS DE INGENIERA|UNIVERSIDAD DE SAN BUENAVTURA, SECCIONAL
CARTAGENA | Vol.3, N4, enero junio del 2012 | ISSN 2027-9396 (en lnea) | CARTAGENA, COLOMBIA | PP. 8-23
EDD (Earliest Due Date). Los trabajos se programan dependiendo del que tenga menor fecha de entrega. Minimiza el Lmax (retardo mximo).
dJ dk o dj dj+1 donde dJ, dk = son las fecha de entrega del trabajo j o trabajo k
FCFS (First Come First Served). Los trabajos se programan dependiendo del orden de llegada: Primeros en Entrar Primeros en Servir.
LPT (Longest Processing Time First). Los trabajos se programas dependiendo del que tenga mayor tiempo de procesamiento.
pJ pk o pj pj+1 donde pJ, pk = tiempo de procesamiento trabajo en la
Mquina j o mquina k
MS (Minimum Snack). Los trabajos se programan dependiendo del que tenga menor retardo o snack.
Snack = Max (dJ - pJ -t, 0)
WSPT (Weighted Shortest Processing Time First). Los trabajos se programan dependiendo del que tenga mayor relacin entre el peso o prioridad y tiempo de
procesamiento. Esta regla de despacho es ptima para
o
+
+
Dnde: wJ o wk = peso del trabajo j o del trabajo k
pJ pk = tiempo de procesamiento trabajo en la maquina j o k
= tiempo de terminacin de trabajos total ponderado.
SPT (Shortest Processing Time First). Los trabajos se programas dependiendo del que tenga menor tiempo de procesamiento. Sirve para minimizar la tardanza ponderada
y la suma de los Cj (tiempos de flujo), sea y
pJ pk o pj pj+1
Donde pJ, pk = tiempo de procesamiento de trabajo en la maquina j maquina k
Pm = maquinas idnticas en paralelo
wjTj = tardanza total ponderada Cj = tiempo de terminacin total
CRj (Critical Ratio). Los trabajos se programan dependiendo del que tenga menor razn crtica (CR). Cuando hay ms de un trabajo retardado, se secuencia primero el de
menor tiempo de proceso.
wjCj||1
jjTwPm || jCPm ||
-
16
INGENIATOR | REVISTA VIRTUAL DE LOS PROGRAMAS DE INGENIERA|UNIVERSIDAD DE SAN BUENAVTURA, SECCIONAL
CARTAGENA | Vol.3, N4, enero junio del 2012 | ISSN 2027-9396 (en lnea) | CARTAGENA, COLOMBIA | PP. 8-23
CRj=
Donde pJ = tiempo de procesamiento de trabajo en la maquina j
dj = son las fecha de entrega del trabajo j
3. DEFNICIN DEL PROBLEMA
3.1 PROBLEMA DE SECUENCIAMIENTO DE LAS TAREAS EN LNEA
En general en un problema de Scheduling intervienen los siguientes elementos: trabajos,
disponibilidad, fecha de entrega, tiempo de proceso, prioridad, tiempo de alistamiento
(setup), operaciones, patrones de flujo y maquinas.
Los objetivos que pueden buscarse pueden ser: minimizar el tiempo de flujo total,
minimizar la tardanza total, minimizar el tiempo mximo de terminacin(makespan),
minimizar la tardanza mxima, minimizar el nmero de trabajos retrasados , minimizar el
retraso mximo. El problema flow-shop se refiere a una configuracin enfocada al
producto, tal como se muestra en la figura 4
Por tanto el problema de flow-shop permutacional considera el makespan como funcin
objetivo a ser minimizada, resolver el problema significa determinar la permutacin que
entregue el menor valor de makespan.
Cuando una programacin define tiempos ociosos, minimizar el lapso, equivale a
minimizar los tiempos ociosos. El Lapso debe ser tan grande como la suma de los tiempos
de proceso en cualquiera de las mquinas.
Figura 2. Secuencia de produccin lineal
Fuente: Autores
No se sabe que trabajo debe ser primero y su tiempo de proceso en la mquina 1, determina
el tiempo ocioso en la mquina 2.El tiempo ocioso en la mquina 2 debe ser como mnimo
el tiempo de proceso ms pequeo en la mquina 1 y el tiempo ocioso en la Mquina 1
n
i
n
i
iimx ppmxC1 1
21
* ,
-
17
INGENIATOR | REVISTA VIRTUAL DE LOS PROGRAMAS DE INGENIERA|UNIVERSIDAD DE SAN BUENAVTURA, SECCIONAL
CARTAGENA | Vol.3, N4, enero junio del 2012 | ISSN 2027-9396 (en lnea) | CARTAGENA, COLOMBIA | PP. 8-23
debe ser cmo mnimo el tiempo de proceso ms pequeo de la mquina 2, lo que lleva al
intervalo ms apropiado para que se de el Lapso.
Si un trabajo tiene un tiempo de proceso corto en la Mquina 1, se debe ir al inicio,
mientras que si es un tiempo de proceso corto en la Mquina 2, se debe ir al final. Para eso
utilizaremos el Algoritmo de Johnson.
El algoritmo de Johnson Requiere una serie de pasos:
Se colocan todos los trabajos en una lista, as como el tiempo que requiere cada uno de esos trabajos en cada una de las mquinas.
Seleccionamos aquel pedido que menor tiempo de ejecucin tenga. Si este tiempo de ejecucin corresponde a la primera mquina, el pedido se programa primero, y si el
pedido corresponde a la segunda mquina el pedido se programa el ltimo.
Una vez seleccionado uno de los trabajos lo eliminamos de la lista y repetimos este proceso, pero siempre trabajando hacia el centro de la secuencia.
La Regla de Johnson para N pedidos y 3 mquinas. El algoritmo se basa en la creacin de 2 mquinas ficticias, M4 y M5, donde el tiempo en M4, el tiempo de ejecucin para
el pedido i ser igual a la suma de M1 y M2; y el tiempo en M5 ser igual a la suma de
M2 y M3. Y se aplica el mismo procedimiento que antes. Para que la regla sea vlida
es necesario que los tiempos menores de la primera y la ltima mquina de su ruta no
sean inferiores al mxima tiempo de la mquina intermedia.
N pedidos y M mquinas. Hay una serie de algoritmos que se basan en la tcnica anterior.
Otras tcnicas.
4. METODOLOGIA
Para este estudio y sus respectivos datos fueron obtenidos de un taller de fabricacin de
papel, cartn y derivados, el cual se utilizaron 28 trabajos y 2 mquinas; las ordenes de
trabajo utilizadas son del mes de noviembre. De manera aclaratoria se hizo la
programacin tomando como da 1 el da 10 de noviembre y como da final 16 de
diciembre, las unidades de tiempo tomada esta expresa en horas, considerando 8 horas de
trabajo diarias. El software utilizado para realizar los clculos es el Lekin vs 2.4, DEV C++
vs 4.9
5. RESULTADOS
La tabla 1 resume las rdenes de trabajo pendiente en el mes de noviembre.
n
i
iini
n
i
iinimx ppppmxC1
21,1
1
12,1
* min,min
2,11,1 ,** ininiji pmnpmnmnp
-
18
INGENIATOR | REVISTA VIRTUAL DE LOS PROGRAMAS DE INGENIERA|UNIVERSIDAD DE SAN BUENAVTURA, SECCIONAL
CARTAGENA | Vol.3, N4, enero junio del 2012 | ISSN 2027-9396 (en lnea) | CARTAGENA, COLOMBIA | PP. 8-23
Tabla 1. Ordenes de trabajo Noviembre 2010,
Trabajo Cliente
Da
Entreg
a
Hora
s
Cantida
d
Minuto
s
Hora
s
t
p
Fecha
de
entreg
a
1 UNAB 27 216 24.000 800 13 i 06-dic
2 UNAB 27 216 18.000 600 10 i 06-dic
3 Fondcomfenalco 20 160 12.000 400 7 i 29-nov
4 Patacon con Todo 17 136 20.000 667 11 i 26-nov
5 Frutin Ice 24 192 20.000 667 11 i 03-dic
6 Aguas de Monteria 24 192 5.000 167 3 b 03-dic
7 Aguas de Monteria 24 192 4.000 133 2 b 03-dic
8 Uninorte 27 216 26.000 867 14 i 06-dic
9 Dunord Cafeteria 27 216 14.000 467 8 i 06-dic
10 Dunord Cafeteria 27 216 20.000 667 11 i 06-dic
11 CBI Colombia 24 192 20.000 667 11 b 03-dic
12 CBI Colombia 24 192 20.000 667 11 b 03-dic
13 Jackeline De Leon 27 216 30.000 1.000 17 b 06-dic
14 Jackeline De Leon 27 216 20.000 667 11 b 06-dic
15 Frappe No. 01 31 248 40.000 1.333 22 i 10-dic
16 Frappe No. 02 31 248 15.000 500 8 i 10-dic
17 Alm Fuller 27 216 60.000 2.000 33 i 06-dic
18
YMG
Distribuciones 24 192 20.000 667 11 b 03-dic
19
YMG
Distribuciones 24 192 20.000 667 11 b 03-dic
20 Coco Ice 36 288 12.000 400 7 i 15-dic
21 Maria Grau 24 192 4.000 133 2 b 03-dic
22 Irotama Hoteles SA 36 288 16.000 533 9 b 15-dic
23 Servihoteles 31 248 20.000 667 11 i 10-dic
24 Servihoteles 31 248 15.000 500 8 b 10-dic
25 Pizzerias Margarita 32 256 8.000 267 4 b 11-dic
26 Dist Colombia 26 208 60.000 2.000 33 b 05-dic
27
Inter Nal de
Negocios 36 288 60.000 2.000 33 i 15-dic
28
Inter Nal de
Negocios 36 288 60.000 2.000 33 i 15-dic
Total
Vasos 663.000
Fuente: Autores.
-
19
INGENIATOR | REVISTA VIRTUAL DE LOS PROGRAMAS DE INGENIERA|UNIVERSIDAD DE SAN BUENAVTURA, SECCIONAL
CARTAGENA | Vol.3, N4, enero junio del 2012 | ISSN 2027-9396 (en lnea) | CARTAGENA, COLOMBIA | PP. 8-23
b: Vasos blancos; i: Vasos Impresos
Tiempo de proceso litogrfico litogficos: 4 das
(Tiempo que se toma litografa en hacer llegar el trabajo la fbrica)
Tiempo de proceso de fabricacin: 30 piezas/min
(Promedio de produccin por unida de tiempo-diario)
Despus de introducir los datos al sofware Lekin se obtuvieron en el software las siguientes
secuencias de trabajos
5.1 PROGRAMACIN DE SECUENCIAS DE TRABAJOS
Al analizar la programacin de las rdenes de trabajo de la empresa para el mes de
noviembre de 2010, consideramos diferentes reglas de despacho obteniendo los siguientes
resultados:
Figura 6. Regla de Despacho SPT
Figura 7. Regla de Despacho EDD
Figura 8. Regla de Despacho MS
-
20
INGENIATOR | REVISTA VIRTUAL DE LOS PROGRAMAS DE INGENIERA|UNIVERSIDAD DE SAN BUENAVTURA, SECCIONAL
CARTAGENA | Vol.3, N4, enero junio del 2012 | ISSN 2027-9396 (en lnea) | CARTAGENA, COLOMBIA | PP. 8-23
Figura 9. Regla de Despacho FCFS
Figura 10. Regla de Despacho WSPT
Figura 11. Regla de Despacho CR
Figura 12. Regla de Despacho LPT
Un resumen de los datos obtenidos para cada una de las reglas de despacho, muestra lo
siguiente:
-
21
INGENIATOR | REVISTA VIRTUAL DE LOS PROGRAMAS DE INGENIERA|UNIVERSIDAD DE SAN BUENAVTURA, SECCIONAL
CARTAGENA | Vol.3, N4, enero junio del 2012 | ISSN 2027-9396 (en lnea) | CARTAGENA, COLOMBIA | PP. 8-23
Tabla 3. Resumen de Resultados
Dnde:
Cmax: Tiempo mximo de terminacin
Tmax: Tardanza mxima
Uj : Numero de trabajos tardos
Cj: Tiempo de terminacin total
Tj: Tardanza total
wjCj: Tiempo de terminacin
ponderado
TjCj: Tardanza ponderada
Se observa que la programacin con mnimo Cmax, fue la realizada por la regla de
despacho EDD (programacin por trabajos con menor tiempo de entrega), siendo adems la
que presenta menor tardanza total. Sin embargo podra elegirse la obtenida por la regla de
despacho SPT, la cual muestra un Cmax bajo en comparacin con las dems y muestra
menor nmero de trabajos tardos. A continuacin se muestra comparaciones graficas para
cada una de las reglas de despacho, y ser la administracin de la empresa quien elige la
regla de despacho a utilizar dependiendo el objetivo que busque.
Las secuencias programadas para las maquina siguiendo la regla SPT, es la siguiente
Secuencia Mquina 1
Trabajos : 1-7-21-6-25-24-22-11-12-14-18-19-13-26-3-20-9-16-2-4-5-10-23-8-15-17-27-
27-28.
Secuencia Mquina 2
Trabajos : 7-21-6-25-24-22-11-3-12-14-20-18-19-9-1-13-16-2-26-4-5-10-23-8-15-17-27-
28.
5.2 PROGRAMACIN SIGUIENDO ALGORITMO DE JONSON
Se realiz un algoritmo que permitiera comparar el Cmax y secuencia calculada tomando
datos de manera aleatoria y otra siguiendo el algoritmo de Jonson, dando como resultado:
-
22
INGENIATOR | REVISTA VIRTUAL DE LOS PROGRAMAS DE INGENIERA|UNIVERSIDAD DE SAN BUENAVTURA, SECCIONAL
CARTAGENA | Vol.3, N4, enero junio del 2012 | ISSN 2027-9396 (en lnea) | CARTAGENA, COLOMBIA | PP. 8-23
Se observa que el Cmax calculado con el algoritmo de Johnson es menor que el calculado
tomando datos de manera aleatoria, inclusive que el programado en el software Lekin con
las reglas de despacho descritas anteriormente.
6. CONCLUSINES
Se ha resuelto el problema de secuencia miento de tareas flow-shop utilizando el algoritmo
de Johnson el cual nos brinda un mejor resultado que las reglas de despachos usualmente
utilizadas, estos resultados son de gran inters para empresas del mismo sector, lo cual
garantiza obtener soluciones factibles a los mltiples problemas de secuenciamiento, ; En
los ltimos aos se han desarrollado heursticas que se pueden implementar para resolver
un problema de minimizar el tiempo mximo de terminacin u otros objetivos como la
tardanza ponderada total en una mquina, En trabajos futuros se podra aplicar la
metodologa propuesta al problema de jop-shop utilizando reglas de despachos , algoritmo
de johnson y otros, otro aspecto seria comprobar o aplicar diversas tipos de meta heursticas
en ambientes tipo taller complejo.
7. AGRADECIMIENTOS
Debo dar las gracias a la Universidad Tecnolgica de Bolvar y a Jaime Acedo Chedid por
la asesora y realizacin en este trabajo. Los errores en este documento corresponden a los
autores, y as debe ser atribuido sin perjudicar a las personas e institucin mencionadas.
8. REFERENCIAS
Ashour, S. (1970). An experimental investigation and comparative evaluation of flow-shop
scheduling techniques. Operations Research, 18(3):541549.
Baker, K. R. (1974). Introduction to Sequencing and Scheduling. John Wiley & Sons, New
York.
-
23
INGENIATOR | REVISTA VIRTUAL DE LOS PROGRAMAS DE INGENIERA|UNIVERSIDAD DE SAN BUENAVTURA, SECCIONAL
CARTAGENA | Vol.3, N4, enero junio del 2012 | ISSN 2027-9396 (en lnea) | CARTAGENA, COLOMBIA | PP. 8-23
Byung Park, Y., Pegden, C. D., y Enscore, E. E. (1984). A survey and evaluation of static
flowshop scheduling heuristics. International Journal of Production Research, 22(1):127
141.
Dannenbring, D. G. (1977). An evaluation of flow shop sequencing heuristics. Management
Science, 23(11):11741182.
Garey, M., Johnson, D., y Sethi, R. (1976). The complexity of flowshop and jobshop
scheduling. Mathematics of Operations Research, 1(2):117129.
Garey, Michael R. and Johnson, David S. (1979). Computers and Intractability: A guide to
the theory of NP-Completeness., W.H. Freeman and Company, New York
Graham, R., Lawler, E., Lenstra, J., y Rinnooy Kan, A. (1979). Optimization and
approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete
Mathematics, 5:287326
Johnson S. M. (1954). Optimal two and three stage production. Naval Research Logistics
Quaterly, (1):6167
Lahdari, T. y Haouari, M.. A Computacional study of the permutation flow shop problem
based on a tight lower bound. Computers & Operations Research. Article in Press,
Corrected Proof.
Pinedo, Michael. (1995). Scheduling: Theory, Algorithms, and Systems., Englewood
Cliffs, Prentice Hall, N.J.
Ponnambalam, S. G., Aravindan, P., y Chandrasekaran, S. (2001). Constructive and
improvement flow shop scheduling heuristics: an extensive evaluation. Production
Planning and Control, 12(4):335.
Ponnambalam, S. G., Aravindan, P., y Chandrasekaran, S. (2001). Constructive and
improvement flow shop scheduling heuristics: an extensive evaluation. Production
Planning and Control, 12(4):335.
Superintendencia de Sociedades base de datos, SIREM (sistema de informacin y riesgo
empresarial) [online] Disponible: http://sirem.supersociedades.gov.co/SIREM/index.jsp.
2010
Turner, S. y Booth, D. (1987). Comparison of heuristics for flow shop sequencing.
OMEGA, The International Journal of Management Science, 15(1):7578.
Vepsalainen, A. & Morton, T. (1987) Priority Rules for Job Shops with Weighted
Tardiness Cost,Management Science, Vol. 33, No. 8, 1035-1047
http://sirem.supersociedades.gov.co/SIREM/index.jsp
top related