• Author / Uploaded
• Ivan Dario Rodriguez

Citation preview

FACULTAD DE INGENIERÍA Y CIENCIAS BÁSICAS

PROYECTO GRUPAL

Institución Universitaria Politécnico Grancolombiano

PROYECTO ALGORITMO DE SECUENCIA MULTI- MAQUINA.

Presentado por:

JOHN DAYRON FERNANDEZ CASTAÑEDA VICTOR MANUEL LEGUIZAMON GAONA BRANDON ESTIVEN GUZMAN GOMEZ IVAN DARIO RODRIGUEZ AGUILAR JOSE DAVID AGUILAR CRUZ VELANDIA LOPEZ DANIEL ANDRES IILIRIANO QUINTERO GRANADOS

Tutor: JULIAN TELLO

INSTITUCIÓN UNIVERSITARIA POLITÉCNICO GRANCOLOMBIANO FACULTAD DE INGENIERÍA Y CIENCIAS BÁSICAS PROGRAMA VIRTUAL BOGOTÁ COLOMBIA 2019

FACULTAD DE INGENIERÍA Y CIENCIAS BÁSICAS

PROYECTO GRUPAL

Institución Universitaria Politécnico Grancolombiano

Contenido 1. INTRODUCCIÓN ........................................................................................................ 3

2.

1.1.

OBJETIVO PRINCIPAL ....................................................................................... 4

1.2.

OBJETIVOS SECUNDARIOS.............................................................................. 4

1.3.

CRONOGRAMA DE ACTIVIDADES .................................................................... 5

MARCO TEÓRICO – SECUENCIACIÓN DE MÁQUINAS .......................................... 6 2.1.

TIPOS PRINCIPALES DE PROBLEMAS EN SECUENCIACIÓN DE MÁQUINAS 6

2.2. ALGORITMOS PRINCIPALES PARA SECUENCIACIÓN EN PROBLEMAS MONO-MÁQUINA .......................................................................................................... 8 2.3. ALGORITMOS PRINCIPALES PARA SECUENCIACIÓN EN PROBLEMAS MULTI-MÁQUINA......................................................................................................... 10 3.

SOLUCIÓN DEL ESTUDIO DE CASO ........................ Error! Bookmark not defined. 3.1. MODELOS DE INVENTARIOS A APLICAR EN LA CATEGORÍA A ............ Error! Bookmark not defined.

4.

CONCLUSIONES Y RECOMENDACIONES ............... Error! Bookmark not defined. 4.1.

CONCLUSIONES ................................................. Error! Bookmark not defined.

4.2.

RECOMENDACIONES ......................................... Error! Bookmark not defined.

BIBLIOGRAFÍA ................................................................... Error! Bookmark not defined. ANEXOS............................................................................. Error! Bookmark not defined.

FACULTAD DE INGENIERÍA Y CIENCIAS BÁSICAS

PROYECTO GRUPAL

Institución Universitaria Politécnico Grancolombiano

1. INTRODUCCIÓN Sobre los años 1890 el capataz era quien realizaba una programación de los diferentes trabajos, en este tiempo las empresas de manufactura empiezan a amplificar los productos, esto implicaría más complejidad en los diferentes procesos, por lo tanto gracias a Frederick Taylor se separa la planeación de la ejecución, de esta manera dentro del proceso de planeación nace la programación de tareas y comienza el desarrollo formal de la técnica CPM en Du Pont, con la finalidad de generar programación automática con la ayuda de una computadora, que con los años seria mejorado por IBM quien desarrollo el primer sistema de información de producción. Más adelante, mediante la programación de tareas proceso conocido como Scheduling, se buscan estrategias que ayuden a disminuir el tiempo requerido para completar los procesos de elaboración desde el inicio hasta el final (Makespan), y de esta manera contribuir con las dificultades que presentan muchos empresarios frente al tema de producción y obtención de productos finales. En los siguientes escritos conoceremos los tipos principales de problemas de secuenciación, los diferentes algoritmos para secuencia de tareas tanto de mono maquina como multi máquina, el cual se implementará para resolver un problema de Scheduling analizado en el caso de estudio, de tal manera que sea el más apropiado mediante su comprobación. Para comprender mejor el tema se ha realizado un análisis a un par de máquinas que hacen parte de la elaboración de productos (torneado y fresado) en un proceso de producción y a continuación.

FACULTAD DE INGENIERÍA Y CIENCIAS BÁSICAS

PROYECTO GRUPAL

Institución Universitaria Politécnico Grancolombiano

1.1. OBJETIVO PRINCIPAL Desarrollar e implementar una correcta planeación para que la secuenciación de trabajos mecanizados sea la óptima, mejorando así los tiempos de trabajo y minimizando el costo de los recursos requeridos para satisfacer la demanda durante el periodo de operación.

1.2. OBJETIVOS SECUNDARIOS  Implementar estrategias que permitan una mejora en los tiempos de manufactura.  Implementación de algoritmos que reduzcan los tiempos de entrega de cada una de las tareas.

 Minimizar los tiempos muertos de las máquinas.

FACULTAD DE INGENIERÍA Y CIENCIAS BÁSICAS

PROYECTO GRUPAL

Institución Universitaria Politécnico Grancolombiano

1.3. CRONOGRAMA DE ACTIVIDADES. SEMANA ACTIVIDAD 1 Descargar el archivo “estudio de caso” y material de apoyo para la elaboración del proyecto grupal.

Planeación de la actividad y establecimiento de objetivos, roles y funciones en el equipo de trabajo.

Investigación, desarrollo y elaboración de cronograma de actividades; para la primera entrega correspondiente al tema planteado.

identificación y definición de los parámetros principales del problema a resolver. Desarrollo de la segunda entrega correspondiente a la investigación, detallando criterios, opiniones y socialización grupal. Análisis y seguimiento en aplicación del algoritmo para el problema sugerido en el estudio de caso mediante técnicas apropiadas y secuencias obtenida para resolverlo. Desarrollo de la Tercera entrega correspondiente a la investigación, detallando criterios, opiniones y socialización grupal.

2

3

4

5

6

7

FACULTAD DE INGENIERÍA Y CIENCIAS BÁSICAS

PROYECTO GRUPAL

Institución Universitaria Politécnico Grancolombiano

2. MARCO TEÓRICO – SECUENCIACIÓN DE MÁQUINAS 2.1. TIPOS PRINCIPALES DE PROBLEMAS EN SECUENCIACIÓN DE MÁQUINAS Las máquinas, el personal, los vehículos de transporte y zonas de actividad, tienen una capacidad y una habilidad de procesado mientras que son muchas las tareas que dentro del sistema necesitan de uno o varios de esos recursos. En la mayoría de ocasiones estos recursos deben desarrollarse en un orden determinado, para poder ser entregada al actor principal, el cliente. Todo es posible en un problema de secuenciación. Cuando el volumen de tareas y recursos es algo elevado, el uso de la secuenciación es determinante para asegurar la competitividad de una empresa, asegurando una reducción drástica de los costes y aumento de los recursos que se pueden ofrecer. El objetivo del trabajo es saber cómo ajustar la distribución de demanda proveniente de la carga de máquinas que propone el trabajo basado para un horizonte temporal reservado para las mismas. Para la consecución del objetivo se deben clasificar computacionalmente los problemas; uniendo los criterios sobre una única máquina. Los problemas sobre una única máquina son los más sencillos y muchos de estos problemas son subproblemas componentes; al haber hecho dicho estudio máquina por máquina, podemos empezar a analizar los siguientes problemas:     

Minimizar el máximo coste. Minimizar el coste total. Suma ponderada de tiempos completos. Suma ponderada de tardanzas. Número ponderado de trabajos tardíos.

Se deben plantear modelos de programación lineal con una serie de características: Modelos simples, con el menor número de restricciones y variables. Con el volumen de datos que se tiene, se debe de evitar ante todo variables con demasiadas dimensiones, lo que significaría tener grandes matrices de datos donde la información realmente útil está dispersa. Genérico para el entorno planteado. En cualquier planta productiva la demanda es variable y se necesita un modelo que pueda adaptarse fácilmente a la actividad variable semanal de la planta

FACULTAD DE INGENIERÍA Y CIENCIAS BÁSICAS

PROYECTO GRUPAL

Institución Universitaria Politécnico Grancolombiano

cuyos objetivos sean la reducción del máximo tiempo de finalización de todas las máquinas pero que a la vez tenga en cuenta todas aquellas operaciones que no pertenezcan a la cadena crítica del máximo, las cuales han de ser secuenciadas lo antes posible.

El método genérico es una técnica de computación evolutiva, común en la resolución de problemas de optimización, cuyo proceso está basado en las ideas de la evolución natural. Cada uno de los diferentes operadores que configuran los algoritmos genéticos ha sido adaptado al problema, mediante la realización de un programa formalizado con la herramienta informática Visual Basic y que recibe el nombre el nombre de “Secuencia de Fabricación”. Los resultados computacionales obtenidos demuestran que el algoritmo genético propuesto logra explorar el espacio de búsqueda de forma eficaz, acortando los tiempos de resolución del problema. Además, se introduce un estudio preliminar de un caso especial de flujo regular de permutación, en el que las máquinas no están disponibles al inicio del horizonte de planificación, en el caso particular de minimización del makespan para el que se demuestra la optimalidad en el caso de dos máquinas, y la complejidad para el caso de más de dos máquinas En fabricación, cuando todos los trabajos deben pasar por todas las máquinas, y el orden de paso por éstas es el mismo para todos los trabajos, se dice que el entorno es de flujo regular o flowshop. Además, el caso en el que los trabajos son secuenciados de forma que pasen en el mismo orden por todas las máquinas se denomina flujo regular de permutación o permutación flowshop. En la mayor parte de los entornos de fabricación reales las máquinas no suelen estar disponibles en todo el horizonte del proceso de los trabajos, es decir, existen restricciones de disponibilidad de las máquinas. Los intervalos de no disponibilidad pueden ser estocásticos, si no se conoce el momento en el que la máquina no va a estar disponible, ni cuántas veces se producirá. Este caso es producido por rotura de la máquina. El caso determinista, es el caso contrario al anterior, y el intervalo puede estar prefijado en cualquier instante del período de planificación. Este caso se da para las tareas de mantenimiento de las máquinas, que pueden ser coordinadas con la planificación, permitiendo localizar el instante de inicio del intervalo en la planificación, o no coordinado, en caso en el que el instante de inicio está fijo.

Downloads/Dialnet-EstudioDeAlgoritmosDinamicosParaElProblemaDeSecuen-2265546%20(2).pdf https://riunet.upv.es/bitstream/handle/10251/9312/tesisUPV3454.pdf

FACULTAD DE INGENIERÍA Y CIENCIAS BÁSICAS

PROYECTO GRUPAL

Institución Universitaria Politécnico Grancolombiano

ftp://tesis.bbtk.ull.es/ccppytec/cp3.pdf

2.2. ALGORITMOS PRINCIPALES PARA SECUENCIACIÓN EN PROBLEMAS MONO-MÁQUINA Durante los últimos años, se han llevado a cabo diferentes investigaciones en cuanto al modelos de secuenciación utilizados en la programación, fabricación y distribución de los productos y general de igual manera en la prestación de servicios. Como se cita en varias citas oficiales de varios conocedores de la materia; los cuales se han dedicado a este estudio, han dado a conocer los principales algoritmos y problemas más influyentes en este campo. Dentro de los principales escenarios en el campo de la secuenciación (Programación) existe varios tipos: Estáticos (Off-line) y Dinámicos (On-Line); los cuales nos ayudan a tomar decisiones en la ejecución de tareas, teniendo en cuenta información obtenida al instante de la realización de la tarea. En la temática vista hasta este momento se hace referencia a los diferentes aspectos de la secuenciación basado en reglas fundamentales como lo son los STP (Shortest Processing Time) y FIFO (Firts IN, Firts Out). Estas Reglas son analizadas respectos a su competitividad para el peor de los casos y, posteriormente, se desarrolla una serie de pruebas basadas en la simulación.

Para la solución de problemas en una sola máquina, existe un algoritmo muy conocido: El Algoritmo Moore y Hodgson. Este algoritmo tiene como objetivo principal lograr la disminución de los trabajaos atrasados. Cuando términos de negociación existen clausulas o penalizaciones por conceptos de atrasos; este algoritmo se torna muy importante y llega a tener la solución para cumplir con la fecha pactada y no incurrir en este tipo de faltas.

Para desarrollar este algoritmo es esencial llevar a cabo cuatro pasos fundamentales:  Ordenar los trabajos de acuerdo a la regla de prioridad EDD  Seleccionar el primer trabajo (i) atrasado en la secuencia actual, sino hay trabajo atrasado proseguir al paso número cuatro.  Considere los trabajos 1 al i, rechace el primer trabajo con el mayor tiempo de proceso, vuelva al paso dos.

FACULTAD DE INGENIERÍA Y CIENCIAS BÁSICAS

Institución Universitaria Politécnico Grancolombiano

PROYECTO GRUPAL

 Forme la secuencia que resulta de tomar la secuencia actual y colocar los trabajos rechazados al final.

Ejemplo: Trabajo 1 2 3 4 5 6

Tiempo de Proceso Fecha de Entrega 3 4 1 1 4 17 7 12 2 5 6 20

Se lleva a cabo el paso uno:

Trabajo 2 1 5 4 3 6

Tiempo de Proceso Fecha de Entrega 1 1 3 4 2 5 7 12 4 17 6 20

Paso dos: Seleccionar el primer trabajo (i) atrasado en la secuencia actual, sino hay trabajo atrasado proseguir al paso número cuatro. Paso tres: Considere los trabajos 1 al i, rechace el primer trabajo con el mayor tiempo de proceso, vuelva al paso dos.

Trabajo 2 1 5 4

Tiempo de Proceso 1 3 2 7

Fecha de Entrega 1 4 5 12

Fecha de Entrega Efectiva

Retraso Dias 1 3 10 14

0 0 0 0

FACULTAD DE INGENIERÍA Y CIENCIAS BÁSICAS

Institución Universitaria Politécnico Grancolombiano

PROYECTO GRUPAL

3 6

4 6

17 20

20 23

0 19

Paso cuatro: Forme la secuencia que resulta de tomar la secuencia actual y colocar los trabajos rechazados al final. En este caso sería igual a 23 días “Makespan” Mostrando la secuencia: 1 2

2 5

3 5

4 4

5 4

6 4

7 4

8 4

9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 4 4 3 3 3 3 6 6 6 6 6 6 1 1 1

2.3. ALGORITMOS PRINCIPALES PARA SECUENCIACIÓN EN PROBLEMAS MULTIMÁQUINA Cuando se trata de problemas de secuenciación planteado para mas de dos centros o maquinas; se debe recurrir al Algoritmo de “Jhonson”. Este algoritmo es heurístico (solución de problemas mediante la creatividad o del pensamiento lateral o divergente). El algoritmo de Johnson se concentra en disminuir el tiempo total requerido para el numero de trabajos en el taller, conocido también como “Makespan” Para llevar a cabo este algoritmo debemos tener en cuenta los siguientes pasos:  Se anota el tiempo de operación de cada una de las maquinas.  Se elige el tiempo más breve.  Si el tiempo mínimo proviene de la maquina 1 coloque el trabajo en la primera posición disponible. Si el tiempo mínimo proviene de la maquina 2, coloque el trabajo en la ultima posición que no esté ocupada.  Repita hasta secuenciar todos los trabajos. La secuencia obtenida minimizara el Makespan.

Trabajo

Tiempo de proceso en Maquina A

Tiempo de proceso en Maquina B

FACULTAD DE INGENIERÍA Y CIENCIAS BÁSICAS

PROYECTO GRUPAL

Institución Universitaria Politécnico Grancolombiano

1 2 3 4 5 SECUENCIA

4 1 9 4 8

2 5 6 7 3

2-4-3-5-1

Este algoritmo estén el menor tiempo posible detenidas. La secuencia obtenida procesará primero en la maquina 1 los trabajos que deben pasar por la maquina 2 y luego los trabajos que deben pasar por la maquina 1. Al mismo tiempo la maquina 2 procesará en primer lugar los procesos que solo deben pasar por la maquina 2 y después los que provienen de la maquina 1. Para tener una idea más clara del flujo de los trabajos con el algoritmo de Johnson, los dividimos en las siguientes categorías:

   

Tipo 1: Trabajos que se procesan en la M1 Tipo 2: Trabajos que se procesan en la M2 Tipo 12: Trabajos que se procesan primero en la M1 y Luego en la M2 Tipo 21: Trabajos que se procesan primero en M2 y luego en la M2

Otro objetivo importante de este algoritmo es el de evitar al máximo los tiempos muertos y que los trabajos llegaran a las maquinas antes de ser solicitados. Por este motivo las maquinas procesan primero los trabajos que visitaran luego otras máquinas.

FACULTAD DE INGENIERÍA Y CIENCIAS BÁSICAS

PROYECTO GRUPAL

Institución Universitaria Politécnico Grancolombiano

1. SOLUCIÓN DEL ESTUDIO DE CASO ENTREGA 3: indique cuál algoritmo de secuenciación aplicaría para el problema del estudio de caso, y justificando el por qué. Debe aplicar el algoritmo y hallar las medidas de desempeño básicas para comparar su solución obtenida, con una solución obtenida bajo alguna regla de despacho básica.

2. CONCLUSIONES Y RECOMENDACIONES ENTREGA 3: Mencione las conclusiones y recomendaciones relacionadas con la aplicación de los algoritmos de secuenciación y con la selección de dichos algoritmos.

2.1.CONCLUSIONES …

2.2.RECOMENDACIONES …

FACULTAD DE INGENIERÍA Y CIENCIAS BÁSICAS

PROYECTO GRUPAL

Institución Universitaria Politécnico Grancolombiano

BIBLIOGRAFÍA

Diaz, R. (mayo de 2019). PROGRAMACION DE LA PRODUCCION, COMPRA E INVENTARIOS. Obtenido de Planificar el nivel óptimo de inversión en inventarios.: https://prezi.com/nyboig_xifgg/programacion-de-la-produccion-compra-einventarios/ Marín, I. F.-B. (diciembre 2003 (Plan 94)). Programación de la secuencia de fabricación en una máquina con tiempos de preparación variables, Obtenido de https://upcommons.upc.edu/bitstream/handle/2099.1/3638/31132-1.pdf Villalobos2, J. P. (mayo de 2019). Simulación y los A. G. . Obtenido de https://comunidad.udistrital.edu.co/ses/files/2014/10/Simulaci%C3%B3n-y-los-A.G.-para-un-problema-de-scheduling-en-sistemas-de-flujo-flexible.pdf Downloads/Dialnet-EstudioDeAlgoritmosDinamicosParaElProblemaDeSecuen2265546%20(2).pdf https://riunet.upv.es/bitstream/handle/10251/9312/tesisUPV3454.pdf ftp://tesis.bbtk.ull.es/ccppytec/cp3.pdf

FACULTAD DE INGENIERÍA Y CIENCIAS BÁSICAS

PROYECTO GRUPAL

Institución Universitaria Politécnico Grancolombiano