propuesta para la programaciÓn de dos …148.204.210.201/tesis/439.pdf · director de tesis: m en...

1

SECCIÓN DE POSGRADO E INVESTIGACIÓN

PROPUESTA PARA LA PROGRAMACIÓN DE DOS LÍNEAS DE PRODUCCIÓN

A TRAVÉS DE UN ALGORITMO DE SECUENCIACIÓN

Que para obtener el grado de

MAESTRO EN INGENIERÍA INDUSTRIAL

Presenta: Ing. Israel Jiménez Sánchez

Director de Tesis: M en C. Javier Hernández Ávalos

Comité Tutorial:

Dr. Eduardo Gutiérrez González

Dr. Igor Antonio Rivera González

M en C. Isidro Marco A. Cristóbal Vázquez

M en C. Juan Carlos Gutiérrez Matus

México Distrito Federal Enero 2011

INDICE

4

Índice

Introducción……………………………………………………………………………………………………………………….............9

Metodología………………………………………………………………………………………………………………………………..13

Capitulo 1. Programación de la producción en la planta de aislamientos de la empresa Owens

Corning México.

1.1 Antecedentes OCM………………………………………………………………………………………………..……15

1.1.1 Filosofía Empresarial…………………………………………………………………………………..16

1.1.2 Proceso de Fabricación…………………………………………………………………….……..….18

1.2 Departamento de cadena de suministros de OCM…………………………………………….….…….20

1.2.1 Área de planeación y programación de producción………………….…….…..….….21

1.2.2 Mapeo de los procesos del área…………………………………………………….….…..…..22 1.2.3 Descripción del proceso de programación de la producción….……………….…..27 1.2.4 Estado actual del cumplimiento del proceso……………………….……….……..………39

Capítulo 2. Programación de tareas en líneas de producción paralelas.

2.1 Cadena de suministros……………………………………………………………………………………………….41

2.1.1 Administración de la cadena de suministros……………………….………………………..43

2.1.2 La importancia de la cadena de suministros………………………..…….…….……..…….45

2.1.3 Servicio al cliente……………………………………………….………………………….……………….50

2.2 Optimización de la secuenciación de trabajos………………………..……..…………………….54

2.2.1 Definición de un problema de programación……………..………………….……….55

2.2.1.1 Definición de un trabajo……………………………..…………..…………………55

2.2.1.2 Ambiente Máquina…………………………………………………..………………..52

2.2.1.3 Características de un trabajo……………………………..…………..………….57

2.2.1.4 Criterio de Optimización…………………………………………………..……..…58

2.2.2 Complejidad computacional…………………………..…………………..…………..……..59

2.2.3 Problemas de programación en máquinas paralelas…………….…..……………61

2.2.3.1 Máquina idénticas……………………………………………..………………………61

2.2.3.2 Máquinas uniformes…………………………………….…..……………………….63

2.2.4 Algoritmos de programación……………………………………………..……………….….67

2.2.4.1 Algoritmos Heurísticos……………………………………………….……..……….67

2.2.4.2 Técnicas de búsqueda local (Local Search)……………….………….……69

2.2.4.3 Simulated annealing…………………………………………….……………………70

2.2.4.4 Variable neighbourhood search VNS……………………………………….…75

2.2.5 Algoritmo de Optimización Branch and Bound………...………………..….………77

INDICE

5

2.2.6 Algoritmos para problemas con máquinas paralelas con tiempos de

secuencia dependientes…………………….…………………………………………………….79

Capítulo 3. Análisis y diseño del algoritmo de programación.

3.1 Restricciones del sistema de producción………………………………………………………………82

3.2 Diseño del algoritmo de programación de la producción…………………………………….88

3.3 Programación del algoritmo de secuenciación y construcción de su interfaz para su

aplicación………………………………………………………………………………………………………….101

Capítulo 4. Análisis de los resultados.

4.1 Evaluación del comportamiento del algoritmo……………………………….…………………110

4.2 Presentación de los resultados obtenidos……………………………….………………………...114

Conclusiones………………………………………………………………….…………………………………………………………117

Bibliografía…………………….………………………………………………………………………………………………………..119

Anexo………………………………………………………………………………………………………………………………………123

6

RESUMEN El presente proyecto de investigación aborda el problema de la secuenciación de trabajos en dos

líneas de producción de la Planta de Aislamientos de Owens Corning México. Debido a lo anterior,

se presenta una solución para atacar este problema de optimización de complejidad NP a través

del algoritmo heurístico de recocido simulado. También se estableció un modelo matemático que

represente las restricciones del sistema de producción, así como las matrices de los tiempos de

cambio generados entre cada familia de trabajos que deben ser secuenciados. La función objetivo

para este caso es la de minimizar el tiempo de procesamiento del último trabajo (Makespan). El

algoritmo de recocido simulado fue programado en lenguaje Visual Basic con una interfaz en Excel

para correr la pruebas de generación de secuencias. Para efectos del análisis de resultados se

compararon 52 semanas históricas de programación de la producción, las cuales fueron

generadas con el método que maneja la planta y evaluadas contra el método propuesto en este

proyecto que utiliza el recocido simulado. El algoritmo de recocido simulado logró una mejor

eficiencia al momento de minimizar la función objetivo; con esto se demostró que existe un

impacto en la reducción de los costos generados por los tiempos de cambio entre productos.

Durante las pruebas, el algoritmo manifestó tener tiempos de cómputo relativamente cortos, lo

que sugiere que pueda ser implementado en planta.

7

ABSTRACT

This research project considers the problem of sequencing jobs on two production lines of the

Owens Corning Plant in Mexico. The problem studied here is NP-complete and this research

proposes a simulated annealing method to find a feasible schedule for each job that is sequenced

in production lines and satisfying certain restrictions. The objective function is to minimize the

Makespan. The simulated annealing algorithm was programmed in Visual Basic language with an

interface on Excel to run the test sequence generation. For the analysis of the results was

compared 52 weeks of historical production scheduling, which were generated with the method

that handles the plant and evaluated against the method proposed in this project using simulated

annealing. The simulated annealing algorithm achieves better efficiency by minimizing the

objective function. The algorithm has short computation times that allow its implementation on

the plant.

8

AGRADECIMIENTOS Gracias a la coordinación de la Maestría en Ingeniería Industrial de la UPIICSA perteneciente al Instituto Politécnico Nacional por permitirme formar parte de su programa de estudios de posgrado. En general a todos los profesores de la SEPI pos su dedicación y contribución en el desarrollo profesional de los alumnos de esta sección. A los miembros del Comité Tutorial Dr. Eduardo Gutiérrez González, Dr. Igor Antonio Rivera González, M en C. Isidro Marco A. Cristóbal Vázquez, M en C. Juan Carlos Gutiérrez Matus por sus recomendaciones para mejorar el presente trabajo. Personalmente agradezco a mi Director de Tesis M en C Javier Hernández Ávalos por su apoyo incondicional durante el desarrollo de este proyecto de investigación y de mis estudios de posgrado.

INTRODUCCIÓN

9

Introducción.

Owens Corning (OC), es la compañía que inventó la fibra de vidrio. Es líder en el mundo en sistemas avanzados de desarrollo y producción de fibra de vidrio y de material de construcción, y se expande globalmente a través de los mercados competitivos, internacionales de hoy.

Owens Corning México, es una unidad estratégica de negocio de Owens dedicada a producir aislamientos termoacústicos y refuerzos para plásticos con base en fibra de vidrio. Es la plataforma que expande el mercado en América Latina. OC México, nació con el nombre de Vitro Fibras S.A. Fue producto de un joint venture en 1957 entre Owens Corning, una de las organizaciones líderes a nivel mundial en la fabricación y comercialización de fibra de vidrio y Grupo Vitro, dedicado a la industria del vidrio, siendo uno de los grupos líderes en nuestro país. Como resultado de esta sociedad, la empresa estuvo soportada por la tecnología de punta de ambas empresas.

OC México está localizada en la parte noreste de la Ciudad de México y cuenta con más de 750 colaboradores. Owens Corning es una organización con un claro propósito compartido. La razón principal de lo que se hace cada día en esta empresa debe de tener un gran impacto en los siguientes rubros: generar soluciones, transformar mercados, mejorar vidas.

Cabe destacar que en OC se trabaja con un enfoque de cadena de suministros para satisfacer su demanda de materia prima y para llevar sus productos a donde lo requieran su clientes, es por eso que creo importante trabajar bajo el enfoque de cadena de suministros la problemática de la empresa, ya que así se estará en sintonía con lo que pretende la organización. Bajo esta perspectiva es importante trabajar con una clara visión de lo que es una cadena de suministros. Por lo anterior la cadena de suministros se entiende como la compleja serie de procesos de intercambio o flujo de materiales y de información que se establece tanto dentro de cada organización o empresa como fuera de ella, con sus respectivos proveedores y clientes.

Actualmente la empresa es capaz de ofrecer en el mercado una variedad de más de 4000 productos principalmente aislantes térmicos y acústicos. Estos productos se dividen en 15 familias con diferentes características para satisfacer una amplia gama de necesidades de sus clientes. En la siguiente figura se detalla de una manera bastante simplificada el proceso de producción a través del cual el vidrio y los silicatos son trasformados en fibra de vidrio, para después poder formar los aislantes termoacústicos que son usados en el sector de la construcción y para hornos y tuberías de carácter industrial. Estos productos son la base de la fuerza del negocio de Owens Corning México y representan una gran parte del mercado al que van dirigidos sus productos.

INTRODUCCIÓN

10

Figura 1. Proceso de fabricación de la fibra de vidrio

El proceso de fabricación de la planta de aislamientos comienza con el pedido de las materias primas principales; que son arena sílices y vidrio reciclado, los cuales son colocados en contenedores, para pasar a la siguiente etapa. El segundo paso del proceso es colocar estas arenas y vidrio reciclado en una mezcladora donde son compactados y totalmente mezclados con homogeneidad.

Después de que han sido mezclados en su totalidad la materia prima es transportada al horno, donde los componentes son fundidos a altas temperaturas que oscilan entre los 1450 a 1470 grados centígrados; esto para dar las características a la fibra de vidrio que corresponden con las especificaciones. A continuación se divide este proceso en dos líneas de producción en las cuales se agregan arenas sílices y feldespatos para bridar características al producto dependiendo de sus especificaciones.

En el siguiente paso el vidrio fundido sale por los canales chorreadores de cada línea a temperatura elevada pasando de estos a la cama de formado donde se le adiciona un componente llamado binder, que es una mezcla de arenas sílices y químicos de los cuales no se tiene especificación en este momento. El binder se agrega para aumentar propiedades térmicas a la fibra de vidrio, a partir de este paso sale un producto al cual se le llama “lana sin curar” con la cual se realizan productos que requieren otros procesos del área de manufactura como lo es la tubería para calefacción.

Después de esto la mayor parte de la lana se pasa a través de una banda trasportadora por rodillos a una estufa de curado en la cual, a una temperatura dada, se le brindan propiedades térmicas a esta lana para la fabricación de productos como Aislhogar, Fácil flex, Celling board. Por otra parte la lana que no entra a la estufa se le llama lana sin curar, la cual se usa para fabricar productos manufacturados en los centros de fabricación de Mexicali y Monterrey.

INTRODUCCIÓN

11

Problemática

Después de haber detallado el proceso de fabricación de los productos de OC es importante mencionar que este proceso de fabricación a través de las dos líneas de producción, es de vital importancia para poder satisfacer de manera adecuada el nivel de servicio que se pretende dar a los clientes, es por eso que la empresa en su totalidad requiere que este proceso sea planeado de una manera adecuada.

Por otra parte el departamento de cadena de suministros dentro de su área de planeación y control de la producción es el encargado de programar y secuenciar las diferentes tareas o procesos que se deben efectuar en cada una de las líneas de producción de la empresa. Los procesos de transformación de materia prima son programados dependiendo de las características del producto, ya que algunos productos únicamente pueden ser producidos en la línea uno, otros solamente pueden ser procesados en la línea dos, pero ciertas clases de productos pueden ser producidos en ambas líneas de producción. Aunado a lo anterior la capacidad de extracción de las líneas de producción es de 35 toneladas diarias en tres turnos de trabajo.

Para una empresa como OC que opera en una economía de alto nivel es vital la buena dirección de las actividades relacionadas con la cadena de suministros, ya que son estas las que proporcionan el puente entre las actividades de producción y las de mercado.

La problemática que se pretende atacar en la empresa OC en este momento, es que la programación de la producción y la secuenciación de las dos líneas de producción con las cuales cuenta la planta de aislamientos, hoy en día se lleva a cabo a través de una forma empírica y manual, que de ninguna manera asegura la disminución de los tiempos de producción, así como la consolidación de la capacidad de producción de las líneas. Este problema tiene un efecto directo en el tiempo de entrega de los pedidos, ya que no se asegura de ninguna manera que el producto sea programado a tiempo para cumplir con su fecha de embarque. Esto para una empresa como Owens Corning tiene una repercusión directa con sus clientes, debido a que la empresa tiene como uno de sus compromisos establecidos satisfacer las necesidades de sus clientes, proporcionándoles el producto correcto, con el precio acordado y en el tiempo establecido. Por otra parte, la empresa también está comprometida con mejorar sus procesos, productos y servicios, por lo que la problemática cobra aun mayor relevancia.

La complejidad de los tiempos de secuencia dependientes radica en que dos líneas Mj (j = 1,2) tienen que procesar n trabajos Ji(i = 1, . . . , n), y entre cada par de trabajos ji, jk existe un tiempo de preparación de máquina; en general distintos. Por lo que se necesita programar una secuenciación para cada trabajo y asegurar la disponibilidad, esto para uno o más intervalos de tiempo y para las dos líneas de producción que están sujetas a restricciones de capacidad.

Para observar el comportamiento de los tiempos de entrega de los últimos meses en el año 2009 de la planta de aislamientos, se presenta en la siguiente tabla y grafico respectivo del comportamiento de esta variable en términos de porcentajes.

INTRODUCCIÓN

12

Tabla 1. Porcentaje de entregas a tiempo y con retraso de enero a septiembre de 2009.

Mes Ene Feb Mar Abr Mayo Jun Jul Ago Sep % total

En tiempo 90.01% 92.21% 85.03% 91.11% 85.34% 87.22% 90.59% 91.32% 86.16% 88.78%

Retraso 9.99% 7.79% 14.97% 8.89% 14.66% 12.78% 9.41% 8.68% 13.84% 11.22%

Grafico 1 Entregas a tiempo vs entregas con retraso

El objetivo de este proyecto es diseñar una propuesta para la programación de dos líneas de producción con tiempos de secuencia de producción dependientes, a través de un algoritmo, que permita mejorar el tiempo de producción, y la consolidación de la capacidad de producción de las líneas, además de impactar en la reducción de los tiempos de planeación por este rubro.

Alcances y limitaciones.

El alcance de este proyecto está enfocado a encontrar una solución factible en tiempo razonable de procesamiento de cómputo para resolver el problema de encontrar una mejor solución a la secuencia de trabajos en ambas líneas de producción en la planta de aislamientos de OC. A su vez es importante mencionar que al ser alrededor de 4000 productos los que se pueden producir en estas líneas, para efectos de pruebas y análisis de este proyecto se tomaran únicamente 96 productos de los que representan el mayor volumen de ventas y de producción. De esta forma es importante mencionar que el problema queda delimitado por 2 líneas de producción paralelas con tiempos secuencia de producción dependientes y 96 diferentes posibles trabajos.

0.00%10.00%20.00%30.00%40.00%50.00%60.00%70.00%80.00%90.00%

100.00%

Enero

Fe

bre

ro

Marz

o

Abril

Mayo

Junio

Julio

Agosto

Sep

PROPORCIÓN DE ENTREGAS A TIEMPO VS CON RETRASO

Late

On Time

METODOLOGÍA

13

Metodología.

La metodología que se desarrollará en este proyecto es una combinación tanto de metodologías

cuantitativas y cualitativas. Aunque cabe destacar que la parte cualitativa de la investigación es en

su mayor parte de apoyo y no el soporte principal de la tesis. Lo que se pretende en el desarrollo

de este proyecto es darle el mayor sustento con la implementación de la metodología cuantitativa

para el análisis de la problemática de fondo.

1. Se desarrollará un marco teórico que sustente la investigación a través de la recopilación y

análisis de casos, artículos de revistas científicas, libros y demás información que guarde

una relación con lo referente los algoritmos a la programación de las líneas de producción.

2. Se llevará a cabo un breve estudio del contexto en el cual se desempeña la empresa OC, que permita conocer de manera general a la organización y su forma de funcionamiento.

3. Se analizará de manera general la conformación del departamento encargado de la administración de la cadena de suministros. De manera más particular se estudiará el área de planeación y control de la producción, para conocer a fondo su estructura, forma o métodos para realizar la programación de las líneas de producción.

4. Se estudiará de forma detallada las restricciones a las cuales está sujeta la programación y secuenciación de las líneas de producción, ya que es de suma importancia para la construcción del algoritmo.

5. Se desarrollará un algoritmo de la forma de programación manual que hoy en día maneja

la empresa, a través del cual se pretende analizar su comportamiento, y si este algoritmo

se automatizará cual es su eficiencia respecto a los que posteriormente se propondrían.

6. Se estudiará los algoritmos de programación o secuenciación heurísticos de forma general,

además de estudiar y analizar a fondo los algoritmos que tengan características similares a

las del problema que se plantea en este proyecto en particular.

7. Se diseñará un algoritmo con base a los análisis anteriores que permita realizar la

programación de una forma factible.

8. Se evaluará el algoritmo mediante un proceso de comparación contra el método actual, lo

que permitirá medir los resultados obtenidos y analizar a fondo el comportamiento del

algoritmo de secuenciación.

9. Se presentaran los resultados obtenidos por el algoritmo.

METODOLOGÍA

14

Síntesis de Capítulos

Capítulo 1. Programación de la producción en la planta de aislamientos de la empresa Owens

Corning México

En el capítulo 1 se presenta la organización en la cual se desarrolla el proyecto de investigación,

que en este caso en particular es Owens Corning México. A demás se estudia la conformación del

departamento de cadena de suministros, en el cual se diseña la programación de las líneas de

producción en su área de planeación y control de la producción. Por otro lado se presenta un

estudio de las condiciones actuales del proceso de programación de la producción a demás de un

análisis de las áreas de oportunidad para mejorar este proceso.

Capítulo 2. Programación de tareas en líneas de producción paralelas

En el capítulo 2 se desarrolla el marco teórico de la investigación y sirve de enlace para conectar la

parte de cadena de suministros con el problema de la secuenciación en las líneas de producción.

En este capítulo se definen aspectos esenciales de la cadena de suministros, así como los

problemas de secuenciación de trabajos en máquinas desde la perspectiva de la optimización

combinatoria. También se presentan una serie de algoritmos como el recocido simulado y la

búsqueda de entorno variable, los cuales se presentan como alternativas para la solución de la

problemática.

Capítulo 3. Análisis y diseño del algoritmo de programación

En este capítulo se analiza la problemática y las restricciones del sistema de programación de la

producción. Por otro lado se desarrollan los algoritmos necesarios para programar la

secuenciación de de los trabajos en la líneas, teniendo como principal punto la implementación

del Recocido Simulado para la ejecución de dicha tarea. También se presenta una herramienta

programada en Visual Basic con interfaz en Excel, en la cual están contenidos los algoritmos

necesarios para secuenciar los trabajos de forma óptima.

Capítulo 4. Análisis de los resultados

En el desarrollo de este capítulo se presenta el análisis de los resultados obtenidos con la

implementación del recocido simulado. Este análisis se llevo a cabo comparando los resultados del

método actual de secuenciación de trabajos contra el método propuesto a través del Recocido

Simulado. Los resultado se comparan en dos aspectos el primero es la minimización del tiempo de

Setup y el segundo es el impacto en el costo por minimizar dichos tiempos.

CAPÍTULO 1

15

Capítulo 1. Programación de la producción en la planta de aislamientos de la empresa Owens

Corning México.

1.1 Antecedentes Owens Corning México (OCM).

Owens Corning México es una compañía estadounidense que se dedica a la producción de materiales de construcción. En México la compañía cuenta con una planta, la cual produce aislantes térmicos y acústicos en una gama de productos bastante amplia y diversa para diferentes tipos de necesidades de los clientes.

La planta con la que cuenta en México, es una unidad estratégica de negocio de Owens Corning Global, por lo que es la plataforma en América Latina para distribuir y diversificar los productos de la empresa en esta zona de mercado, además de exportar sus productos a regiones diferentes, como lo son Europa y Australia principalmente. Para poder incursionar en México la empresa tuvo que comprar a Vitro fibras S.A en 1995, con lo cual dio el primer paso para poder competir en esta región del mundo.

La empresa está localizada en la parte noreste de la Ciudad de México, cuenta con más de 750 colaboradores. Produce aislamientos termoacústicos y refuerzos para plásticos con base en fibra de vidrio y comercializa tejas. Debido a esto, la empresa en México está dividida de la siguiente forma: Planta de Aislamientos, Planta de Refuerzos y Centros de Distribución en Mexicali, Monterrey y San Luis Potosí.

La organización trabaja bajo un enfoque de cadena de suministros, por lo que mantiene todos sus procesos encaminados a la satisfacción del cliente. Los productos que ofrece la empresa son manejados bajo dos diferentes tipos de enfoque. Por un lado ofrece productos que son hechos a la medida de los clientes (make to order), los cuales son manejados bajo un sistema de cadena de suministros tipo Pull (Jalar). Los productos restantes son manejados desde la perspectiva de una estrategia tipo Push (Empujar). La preocupación principal de la empresa es que sus productos lleguen en la fecha de entrega prometida al cliente en la cantidad correcta.

Para poder sustentar sus objetivos, así como sus estrategias a mediano y largo plazo la organización cuenta con una filosofía empresarial, la cual mantiene como pilar par su negocio. Esta filosofía se encuentra dividida de acuerdo con la organización en tres diferentes rubros los cuales son: La visión, Propósitos, y Los objetivos de la empresa para con los clientes. A continuación se presenta una síntesis de estos factores organizacionales.

CAPÍTULO 1

16

1.1.1 Filosofía Empresarial

La visión de la empresa es ser un modelo de organización de alto desempeño y la mejor opción en costo; que produce de forma segura y consistente materiales aislantes termoacústicos de fibra de vidrio que superen las expectativas de los clientes y contribuyan con la eficiencia energética, creando un futuro sustentable.

Por otro lado la organización persigue los siguientes propósitos:

Generar Soluciones desde el punto de vista energético, la empresa pretende que sus productos sea reconocidos por su capacidad para ahorrar costos provenientes del gasto energético. Debido a lo anterior la empresa desarrolla constantemente mejoras a sus procesos y productos que puedan permitir una mejor eficiencia energética.

Transformar Mercados para Owens Corning es impulsar un cambio en la región de América Latina para que sus productos y servicios sean vistos como una gran alternativa para el ahorro de energía en países en vías de desarrollo. Esto principalmente por la gran oportunidad que representa para estos países mejorar sus sistemas energéticos en todos los sectores industriales y de servicios.

Mejorar Vidas bajo la perspectiva de la organización es que sus productos aporten una diferencia sustancial respecto a otros en la calidad de vida de los usuarios finales. Aunado a esto el nivel de servicio para el cliente está ligado a este propósito.

Lo anterior desde el punto de vista de esta empresa tiene la finalidad de impulsar a la organización a perseguir y crear nuevas oportunidades, creciendo y avanzando hacia productos de mejor calidad. Lo que da paso al tercer punto que reitera el compromiso de la empresa con el nivel de servicio que presta.

Los objetivos de la empresa para con los clientes son:

1. Mantener una satisfacción de los clientes superior al 80%: en este aspecto el departamento de servicio al cliente lleva un seguimiento mediante la elaboración de encuestas para evaluar el índice de satisfacción trimestralmente. Este índice de satisfacción es puesto en términos de porcentaje para determinar en qué nivel se están cumpliendo las expectativas que tienen los clientes de la empresa.

2. Índices del servicio al cliente superior al 90%: Este indicador se construye con la ayuda de tres factores de medición que lleva a cabo el departamento de cadena de suministros. El primero es el porcentaje de entregas a tiempo. El segundo factor es el nivel de cumplimiento en cantidad de producto requerida por el cliente. Por último se evalúa el índice de devoluciones por defectos de calidad. Con los tres anteriores factores es como se mide el nivel de servicio en esta organización.

CAPÍTULO 1

17

3. Mantener índices de calidad de 3000 partes por millón máximo: La empresa pretende que el nivel de productos defectuosos que salen de las líneas de proceso se mantenga bajo el nivel de los 3000 productos defectuosos por cada millón de piezas fabricadas.

4. Manejar una eficiencia neta superior al 80%: en la planta de fabricación se desea que la eficiencia de los procesos sea tal que los tiempos muertos generados por la operación y las probables fallas de los equipos no excedan el 20% del tiempo disponible para la transformación de la materia prima en producto terminado.

A lo largo de su presencia en México la empresa se ha caracterizado por tener un compromiso con los Sistemas de Calidad, así como por la normatividad necesaria para implementar dichos sistemas. Por otro lado la organización es reconocida en México por tener un buen ambiente laboral y por tener oportunidades de desarrollo para sus empleados. En seguida se presenta un breve historial de los logros que según la organización avalan su compromiso con la calidad y con la sociedad en general

Logros de la empresa

1995 Premio Nacional de Calidad en México dentro de la categoría de Empresa Industrial Grande. 1997 Sistema de calidad certificado bajo la Norma ISO-9002 por la empresa Quality Management Institute (QMI). 2003 Certificación ISO 9001:2000, por fabricación y comercialización de productos de refuerzos y aislamientos termo acústicos de fibra de vidrio. Premio Iberoamericano a la Calidad, otorgado por la Fundación Iberoamericana para la Gestión de la Calidad (FUNDIBEQ). 2004 Las acciones que pertenecían al Grupo Vitro de la empresa Vitro Fibras S.A. son vendidas a Owens Corning. Owens Corning México.

2006 La empresa es reconocida, por segunda ocasión consecutiva, por la revista Expansión como una de las mejores empresas para trabajar en México.

Todos los procesos tanto administrativos como productivos están certificados bajo la normatividad ISO. Los procesos de producción que se desarrollan en el siguiente punto son los de la planta de aislamientos en particular el proceso de fabricación de las dos líneas de producción con las que cuenta.

El presente proyecto se desarrolla específicamente en La planta de aislamientos (Building Materials) de OCM por lo que los puntos sucesivos están enfocados a detallar algunos aspectos de la forma en la que opera esta planta. Principalmente se estudiaran y se describirán su proceso de producción, la forma en la que está estructurado el departamento de cadena de suministros, además de conocer la forma en la que se planea y programa la producción de dicha planta.

CAPÍTULO 1

18

1.1.2 Proceso de fabricación.

La Figura 1.1 presenta, de manera simplificada, el proceso de producción a través del cual el vidrio y los silicatos son trasformados en fibra de vidrio, para después poder formar los aislantes termoacústicos que son usados en el sector de la construcción y para hornos y tuberías de carácter industrial. Estos productos son la base del negocio de Owens Corning México y representan una gran parte del la fuerza de ventas de la organización.

Figura 1.1. Proceso de fabricación de la fibra de vidrio

El proceso de fabricación de la planta de aislamientos comienza con el pedido de las materias primas principales; que son arena sílices y vidrio reciclado, los cuales son colocados en contenedores, para pasar a la siguiente etapa. El segundo paso del proceso es colocar estas arenas y vidrio reciclado en una mezcladora donde son compactados y totalmente mezclados con homogeneidad.

Después de que han sido mezclados en su totalidad la materia prima es transportada al horno, donde los componentes son fundidos a altas temperaturas que oscilan entre los 1450 a 1470 grados centígrados; esto para dar las características a la fibra de vidrio que corresponden con las especificaciones. A continuación se divide este proceso en dos líneas de producción en las cuales se agregan arenas sílices y feldespatos para bridar características al producto dependiendo de sus especificaciones.

En el siguiente paso el vidrio fundido sale por los canales chorreadores de cada línea a temperatura elevada pasando de estos a la cama de formado donde se le adiciona un componente llamado binder, que es una mezcla de arenas sílices y químicos de los cuales no se tiene especificación en este momento. El binder se agrega para aumentar propiedades térmicas a la fibra de vidrio, a partir de este paso sale un producto al cual se le llama “lana sin curar” con la cual se realizan productos que requieren otros procesos del área de manufactura como lo es la tubería para calefacción.

Después de esto la mayor parte de la lana se pasa a través de una banda trasportadora por rodillos a una estufa de curado en la cual, a una temperatura dada, se le brindan propiedades térmicas a esta lana para la fabricación de productos como Aislhogar, Fácil flex, Celling board. Por otra parte

CAPÍTULO 1

19

la lana que no entra a la estufa se le llama lana sin curar, la cual se usa para fabricar productos manufacturados en los centros de fabricación de Mexicali y Monterrey.

Productos que se distribuyen

La gama de artículos que distribuye la empresa correspondientes a la planta de aislamientos es de alrededor de 4000 productos, de los cuales aproximadamente 1200 productos son fabricados en las líneas de producción. La forma de dividir estos productos de acuerdo a sus características es por familias, por lo cual se tienen 11 diferentes agrupaciones que se presentan a continuación:

Air handling agrupa una gama de productos que sirven como aislantes térmicos para las instalaciones de aire acondicionado. En general estos productos tienen forma de manta de aislamiento fabricada con fibra de vidrio.

Metal Building Insulation (MBI) son productos en forma de rollo flexible de aislamiento térmico, fabricado con fibras de vidrio aglutinadas con resinas termofijas recubierta con polipropileno reforzado en una de sus caras. Los MBI son productos que pueden ser fabricados con las especificaciones que el cliente ordene en cuanto a dimensiones y resistencia térmica.

Aislhogar es una familia enfocada a proporcionar un aislamiento térmico y acústico para las casas. Los productos son fabricados con fibra de vidrio flexible en forma de placas cortadas a una medida estándar. Este tipo de aislamiento está diseñado para absorber el sonido, y evitar la trasferencia de calor.

Building Insulation poseen las características del MBI con la diferencia de que el rollo de fibra de vidrio no está recubierto por polipropileno reforzado.

Fácil flex son productos en forma de ducto flexible aislado con fibra de vidrio para aplicaciones de aire acondicionado. Está conformado por un núcleo de alambre helicoidal de acero encapsulado entre dos películas de poliéster, a través de la cual fluye el aire del sistema.

700 Series son piezas de aislamiento termoacústico fabricadas con fibra de vidrio inorgánicas aglutinadas con una resina adhesiva termoendurecible y moldeadas en piezas flexibles, semirígidas y rígidas de diversas densidades que soportan temperaturas de hasta 232 grados centígrados.

OEM Insulation son placas o colchas flexibles blancas de fibra de vidrio inorgánica aglutinadas con una resina termofija. Este producto es un aislante térmico, usado principalmente por manufactureros de estufas, refrigeradores y otros sistemas de calentamiento para mejorar sus propiedades térmicas.

RW son colchas termoaislantes de fibra mineral en color blanco, fabricadas a partir de arena sílice lubricadas con aceite mineral para protegerlas contra la abrasión, desarrolladas para soportar temperaturas de hasta 538 grados centígrados. Estas colchas poseen una conductividad térmica baja.

Celling board son piezas fabricadas en forma de paneles para la fácil instalación principalmente en los techos de oficinas y departamentos. Estos paneles poseen una capacidad para aislar tanto las transferencias térmicas como acústicas.

Foam son aislamientos térmicos de espuma rígida de poliestireno extruido en paneles manufacturados. Tiene una superficie lisa y una estructura de celdas cerradas con paredes que se interadhieren unas con otras sin dejar huecos. El producto se fabrica con diferentes resistencias a la presión.

CAPÍTULO 1

20

Glass pipe es un producto enfocado a proporcionar un aislamiento térmico para tuberías industriales que transportan fluidos, el producto está diseñado para poder colocarse en la parte exterior de las tuberías para mejorar su eficiencia térmica.

Asegurar la correcta producción en tiempo y forma de esta gama tan extensa de productos que se maneja en la planta es una tarea de relevante importancia. Esta tarea la lleva a cabo una de las áreas del departamento de cadena de suministros

1.2. Departamento de cadena de suministros de OCM

La planeación y control de la producción es una de las áreas principales del departamento de cadena de suministros de esta organización. En este punto se estudia las funciones, tareas y actividades que se llevan a cabo para que el área pueda cumplir y desarrollar su trabajo.

El departamento de cadena de suministros está conformado por una gerencia y cuatro jefaturas para cada una de las áreas y son: Almacén de producto terminado, Programación de la producción, Planeación y almacén de materia prima y Logística. En un segundo plano esta el área de compras la cual está dividida por las características de los insumos en tres diferentes tipos que son: materia prima, importaciones y refacciones. A continuación se presenta en la figura 1.2 el organigrama del departamento de SCM.

Figura 1.2. Organigrama del departamento de Cadena de Suministros.

Las funciones que cada una de las áreas debe realizar para sostener el flujo de la cadena de suministros de acuerdo con la descripción de puestos que la empresa proporciona son:

La gerencia de la cadena de suministros es la encargada de organizar, controlar y planear todas las actividades del departamento, así como de tomar decisiones a nivel estratégico para asegurar el flujo continuo del suministro para los clientes. También es encargado de supervisar las decisiones a nivel operativo que toman cada una de las áreas.

CAPÍTULO 1

21

Almacén de producto terminado administra los procesos de control, recepción, manejo, almacenamiento, preservación, segregación y despacho, además de participar en el aseguramiento de la integridad de los productos. Por otra parte debe asegurar que la participación del almacén de producto terminado influya en la confiabilidad de las entregas a tiempo para con los clientes.

Planeación y almacén general debe desarrollar y ejecutar los inventarios que permitan lograr los objetivos de ventas, servicio al cliente. El líder de esta área debe reportar directamente al gerente de cadena de suministros. Esta área debe estar enfocada al análisis de actividades al servicio y satisfacción del cliente en tiempo y cantidad correcta.

El área de logística busca alternativas de transporte, solicita y negocia tarifas de fletes. Es el encargado de proveer los recursos necesarios que permitan el cumplimiento de embarques y entregas al cliente. Lo anterior cumpliendo con las restricciones de costo, tiempo, calidad y forma mediante los servicios diversos de transportación, además debe reportar las actividades a la gerencia de cadena de suministros.

Por otro lado las aéreas involucradas con las compras (Nacional, Importaciones y Refacciones) deben asegurar que las compras de los insumos cumplan con el tiempo de entrega y cantidad, con el fin de asegurar el abasto de los requerimientos de la planta. Su principal actividad es realizar los pedidos de compra y llevar el seguimiento de los requerimientos solicitados. Por otro lado deben desarrollar estrategias de negociación para obtener descuentos y mejoras en tiempos de entrega de los proveedores.

1.2.1 Área de planeación y programación de la producción.

El área de programación de la producción es la encargada de programar los requerimientos de los clientes en cantidad y fecha límite de embarque. También debe asegurar y planear los recursos necesarios para las operaciones y dar seguimiento a las ordenes de producción. Para esto el líder del área debe generar estrategias que permitan programar y optimizar en la medida de lo posible los recursos para la gestión de los programas de producción y entregas a tiempo a los clientes.

Las principales funciones que debe realizar el líder de programación de la producción son:

1. Administrar las funciones del área en función de los estándares de seguridad, eliminación de desperdicio y programación en tiempo de los requerimientos.

2. Generar los programas de producción para la gestión de los productos requeridos por los clientes.

3. Creación y análisis de pronósticos. 4. Generar la planeación de los requerimientos de materiales (MRP) para asegurar que los

insumos de los productos estén en tiempo y forma durante el proceso de producción. 5. Manejar el sistema SAP para controlar y generar las órdenes de producción. 6. Generar la programación de la reposición de inventarios para el almacén de producto

terminado. 7. Optimizar los niveles de inventarios de acuerdo a la demanda. 8. Coordinar con los centros de distribución la planeación de sus requerimientos. 9. Mantenimiento de los parámetros de producción en el sistema SAP. 10. Generar información requerida para la toma de decisiones. 11. Generar mejoras para los procesos de programación de la producción.

CAPÍTULO 1

22

Para examinar de forma más detallada el proceso de programación de la producción en el siguiente punto se desarrolla un mapeo de procesos.

1.2.2 Mapeo de procesos del área de programación de la producción.

Este mapeo tiene como finalidad presentar de manera concreta la forma de llevar a cabo las tareas correspondientes para que el proceso se cumpla satisfactoriamente. Por otro lado se pretende encontrar áreas de mejora en el proceso actual. Los subsecuentes puntos desglosan de forma específica lo que se pretende.

1. Examinar críticamente la situación actual.

2. Definir cada paso del proceso (en un diagrama de flujo).

3. Definir (o validar) el objetivo del proceso.

4. Identificar qué interfaces (entradas / salidas) existen.

5. Agregar interfaces clave al diagrama de flujo (de ser necesario).

6. Determinar el grado de control de cada interface.

7. Identificar variables críticas (en relación al objetivo esperado del proceso y los factores críticos del cliente) y graficar su comportamiento.

8. Identificar las desviaciones actuales y potenciales en cada etapa del proceso.

9. Determinar cumplimiento contra otros requerimientos.

10. Determinar si el objetivo del proceso siempre es cumplido.

11. Definir cualquier problema encontrado en cada análisis de los puntos anteriores (cumplimiento del objetivo del proceso, control de las interfaces, variables críticas, desviaciones.

12. Definir recomendaciones para mejorar el proceso (para alcanzar el objetivo del proceso, para el control de las interfaces, para controlar las variables críticas, para controlar las desviaciones).

El primer paso es conocer la estructura del método de planeación y control de la producción, para poder llevar a cabo esta tarea se construyeron dos tablas las cuales contienen preguntas elementales del proceso actual. Las preguntas que se plantean en la tabla 1.1 tienen la finalidad de conocer al detalle la forma en la que funciona el método actual de programación de la producción, así como la relación que existe entre el sistema de administración de negoció (SAP) y la programación de la producción para la planta de aislamientos. Las preguntas de carácter secundario, que están contenidas en la tabla 1.2 son para verificar si existe una forma diferente actualmente de llevar a cabo dicho proceso, además de percatarse si existe una persona distinta al programador que pueda cumplir con las actividades que requiere el proceso de programación.

CAPÍTULO 1

23

EXAMEN CRÍTICO

DEL MÉTODO

ACTUAL. #

Propósito

1. ¿Qué se hace?

2. ¿Por qué es necesario?

Lugar

1. ¿Dónde se hace?

2. ¿Por qué ahí?

Secuencia

1. ¿Cuándo se hace?

2. ¿Por qué en esa etapa?

Persona

1. ¿Quién lo hace?

2. ¿Por qué esa persona?

Medio

1. ¿Cómo se hace?

2. ¿Por qué de ese modo?

1

Visualizar los Requerimientos de los Clientes.

Es el inicio del Proceso de Programación de la producción.

En Sistema SAP transacción VL06O.

Es el sistema de Administración del Negocio en OCM.

Diario y Semanal

Por los cambios y Necesidades que se presentan en el comportamiento de la demanda.

El Jefe de Programación de la Producción.

Es el responsable de la Gestión y Control de la producción.

En Sistema SAP transacción VL06O.

Es el sistema de Administración del Negocio en OCM.

Preguntas

primarias

2

Programar Requerimientos de los Clientes vs. Capacidades de Producción.

Son la Entrada al Proceso de Programación,

Se realiza en Formato de Excel diseñado por Programación.

El Sistema SAP en este momento tiene limitaciones en cuanto a definición de Capacidades reales de Producción vs. Demanda.

Diario y Semanal.

Por ser la más adecuada para el flujo del proceso.





3 Avisar a ATC Se realiza mediante correo electrónico.

Es el medio de comunicación interna.

Cuando no hay capacidad de producción para poder cumplir con los requerimientos de los clientes.

Es la necesaria para responder a los requerimientos.



Se realiza mediante correo electrónico.

Es el medio de comunicación interna.

4

Generar el Programa de Producción.

Es la salida del proceso de Programación con el cual se planifica y ejecuta la gestión de producción.



Diario y Semanal.




En Hojas de Cálculo Excel.


5 Generar Ordenes de Producción en SAP CO01

Se realiza en el Sistema SAP transacción CO01.

Diario y Semanal.

Por ser la más adecuada


En sistema SAP Transacción CO01.

CAPÍTULO 1

24

Con estas se ejecuta la gestión de producción y cumplimiento de la demanda requerida por los Clientes.

Es el sistema que tenemos para administración del negocio en OCM.

para el flujo del proceso. Es el responsable de la Gestión y Control de la producción.

6

Enviar Programa de Producción.

Para que las áreas involucradas estén enteradas de cómo se debe producir.

Se Emite vía correo Electrónico.

Es el medio con el cual nos comunicamos internamente.

Diario y Semanal.




Vía correo Outlook.

Es el medio con el cual nos comunicamos internamente.

7

Dar Seguimiento al Programa de producción.

Para Asegurar que lo que se planifico se cumpla.

Se realiza en sistema SAP transacción COOIS.

Es la transacción mediante la cual el sistema nos permite visualizar el cumplimiento de cada orden de producción.

Diario y Semanal.




En el sistema SAP y Hojas de Cálculo Excel.

Es el Sistema Transaccional y de Administración del Negocio.

8

Cerrar las Órdenes de Producción.

Para Asegurar que lo que se planifico se cumpla.

Se realiza en sistema SAP transacción COOIS.

Es la transacción donde se ejecutan el cierre de órdenes de producción.

Diario y Semanal. Por ser la más adecuada para

el flujo del proceso.


Es el responsable de la

Gestión y Control de la

producción.

En el sistema SAP

Es el Sistema Transaccional y de Administración del Negocio.

Tabla 1.1 Examen crítico del método actual Preguntas primarias

CAPÍTULO 1

25

La tabla 1.1 contiene todas las actividades que se llevan a cabo durante el proceso de programación de la producción y están enumeradas en la primera columna. Las actividades que componen este proceso se mencionan a continuación:

1. Visualizar los requerimientos de los clientes. 2. Programar los requerimientos de los clientes de acuerdo a la capacidad de producción. 3. Avisar al Departamento de Atención a Clientes si existe algún inconveniente de cumplir

con el pedido de acuerdo a la capacidad disponible. 4. Generar el programa de producción (Excel) 5. Generar las ordenes de producción (SAP) 6. Enviar el programa de producción a la Planta de Aislamientos. 7. Dar seguimiento al programa de producción. 8. Cerrar las órdenes de producción.

La tabla 1.1 está conformada por cinco columnas más, las cuales proporcionan información sobre diferentes aspectos del proceso de programación de la producción. El primero de ellos es el Propósito, ya que cada una de las actividades cumple con una finalidad que se debe conocer a través de este punto. El segundo aspecto es el Lugar donde se lleva a cabo cada una de las tareas. El tercero es la Secuencia el cual se refiere a la manera de realizar la programación y secuenciación de los pedidos de los clientes para las líneas de producción. El cuarto aspecto a considerar es la Persona que lleva a cabo el proceso en este caso solo una persona es la encargada de llevar a cabo todas las actividades correspondientes al proceso de programación de la producción. Por último se tiene el Medio a través del cual se realizan las actividades. En este proceso el principal medio es el sistema SAP, además del correo electrónico para la comunicación entre las áreas con las que se tiene relación dentro y fuera de la organización. El medio con el que se efectúa la programación de la producción es la hoja de cálculo de Excel.

Para cada uno de los cinco aspectos mencionados en el párrafo anterior se requiere responder dos preguntas para cada actividad como se observa en la primera fila de la tabla 1.1. Es a través de estas preguntas que se conoce el estado actual del proceso de programación de la producción y la forma en la que funciona este proceso de manera general.

En la siguiente tabla 1.2 se buscan alternativas para poder efectuar las actividades del proceso de forma diferente a la actual. Básicamente se trata de conocer los límites del proceso en los aspectos de: Propósito, Lugar, Secuencia, Persona y Medio. La tabla 1.2 posee la misma estructura de la tabla 1.1 con la variante de que únicamente se debe responder un solo cuestionamiento, el cual es esencialmente si existe una forma de que la actividad se haga de manera distinta en cada uno de los aspectos mencionados con anterioridad.

En la tabla 1.2 se observa que existen dos aspectos en los cuales hay una forma distinta de llevar a cabo las actividades del proceso, una de ellas es la persona que puede efectuar las tareas; en este caso puede ser el Planeador el que está capacitado para efectuar todas las actividades que requiere el proceso. Por otro lado en el aspecto del Medio en la actividad de la programación de la producción tiene un área de oportunidad, que radica en cómo se puede desarrollar una nueva forma de secuenciar la producción en las líneas.

CAPÍTULO 1

26

EXAMEN

CRÍTICO DEL

MÉTODO

ACTUAL.

#

Propósito

¿Qué más podría

hacerse?

Lugar

¿Dónde más podría

hacerse?

Secuencia

¿Cuándo más podría

hacerse?

Persona

¿Quién más podría hacerlo?

Medio

¿De qué otro modo podría

hacerse?

1 N/A N/A N /A El Planeador N/A

Preguntas

secundarias



4 N/A N/A N /A El Planeador Aplicar un método de

Optimización para La

secuenciación de los

productos.





N/A = No Aplica

Tabla 1.2 Examen crítico del método actual Preguntas Secundaria

CAPÍTULO 1

27

Al conocer mediante las tablas 1.1 y 1.2 el proceso de programación de la producción se puede

describir dicho proceso. En el siguiente punto se desarrolla esta descripción con la ayuda de un

diagrama de flujo.

1.2.3 Descripción del proceso de programación de la producción

Este punto presenta una explicación del proceso de programación de la producción de acuerdo al diagrama de flujo de la figura 1.3. En este diagrama se encuentran representadas todas las relaciones que existen entre el proceso de programación de la producción con otras áreas de la organización.

El proceso de programación de la producción como se muestra en el diagrama de flujo comienza con la entrada de pedidos al sistema por parte del departamento de atención a clientes (ATC), es en esta primera etapa de la programación donde se visualiza los requerimientos de los clientes para posteriormente programarlos en cada una de las líneas. En este punto se requiere verificar la capacidad de producción respecto a la demanda, ya que si la capacidad de las líneas se ve rebasada los requerimientos no podrán ser satisfechos conforme el cliente lo desea. En las primeras etapas del proceso la interacción más fuerte se lleva a cabo con atención a clientes.

Una vez que se confirma la capacidad para producir el requerimiento, es necesario interactuar con el área de planeación para verificar que las materias primas e insumos necesarios para producir el producto estén disponibles a la hora de fijar la fecha para su producción. En esta parte el almacén de materias primas es el que verifica la disponibilidad de los insumos para el producto. Si se cumple con los requisitos tanto de materia prima como de insumos se procede a generar un programa de producción que incluya los requerimientos que entraron al sistema.

En esta etapa de construcción del programa de producción se presentan diferentes interacciones con las demás áreas involucradas para poder cumplir con la entrega del producto. La primera interacción se da con el área de logística ya que se debe asegurar que el producto tenga una fecha de embarque y por consecuencia un transporte para poder cumplir con la entrega. Por otro lado el almacén de producto terminado tiene que estar enterado de la cantidad de material que se necesita almacenar en caso de ser necesario un tiempo de almacenamiento para el producto. Por último se debe verificar que el plan de mantenimiento no interfiera con las fecha de fabricación del producto para no generar retrasos en el tiempo de entrega al cliente.

A partir de que el programa ha sido elaborado se procede a generar las órdenes de producción en el sistema SAP. Estas órdenes posteriormente son enviadas junto con el programa al área de producción para poder ser incluidas en el proceso de fabricación de las líneas. A partir de este momento se procede a dar un seguimiento conjunto al programa junto con el área de producción para estar pendientes de los inconvenientes que puedan surgir al fabricar los productos y así poder ajustar el programa si es que se requiere. Una vez que el producto ha sido terminado se procede a cerrar las ordenes de producción en el sistema SAP.

En la parte final del proceso se notifica a atención a clientes que el producto está listo para ser embarcado si cumple con las características de calidad, de lo contario se notifica que tiene defectos de fabricación y no podrá embarcarse. Cundo se notifica a ATC cualquiera de estas dos posibles respuestas el proceso se da por terminado para cada una de las ordenes de producción en particular.

CAPÍTULO 1

28

Figura 1.3 Diagrama de flujo del proceso de programación de la producción.

Visualizar los requerimientos de

los clientes

1

Generar Programa de Producción

4

Hay Capacidad

Generar ordenes de Producción

5

Enviar Programa de Producción

6

Dar seguimiento al programa de

producción

7

Programar Pedidos de los clientes

vs. Cap. de producción Extracción

2

Centros de Fabricación

Escalation Process

ATC

Mantenimiento

ATC

Producción

Alamcen de PT

Logistica

Cerrar Ordenes de Producción

8

Compras

Avisar a ATC

3

Alamcen de MP

Calidad

Producción

Areas Involucradas

No

Si

Cumple

Si

NO

CAPÍTULO 1

29

En la figura 1.3 aparecen en forma de rectángulo punteado todas las áreas que tienen relación con el proceso de programación de la producción. Los rectángulos que aparecen con línea continua representan las actividades correspondientes a este proceso. El objetivo de cumplir de manera eficiente con todas y cada una de las actividades es programar los requerimientos de los clientes en cantidad y fechas requeridas, asegurando y optimizando los recursos para la gestión y planeación de las operaciones.

En este punto finaliza la primera etapa de valoración del proceso, con la información obtenida es posible remarcar algunos hallazgos encontrados. A continuación se presenta en la tabla 1.3 una síntesis de los problemas encontrados.

Tabla 1.3 Hallazgos 1

Las interfaces planteadas en el diagrama de flujo pueden ser vistas mediante la tabla 1.4, en la cual cada interface tiene tres elementos principales que son: entradas, la actividad que ocurre durante la interface y las salidas generadas al finalizar la relación entre el proceso y el área de interés. Existen un elemento de entrada que debe ser explicado con más profundidad; este elemento es el denominado Escalation Process y ocurre cuando el departamento de atención a clientes envía pedidos de clientes por fuera del sistema SAP vía correo electrónico, lo que genera una gama de pedidos que se comienzan a formar de manera informal, pero que tienen que ser tomados en cuenta por el programador. La tabla 1.4 está conformada por cinco columnas la primera contiene el proveedor del interface, en este caso el área con la que se interactúa. En las siguientes tres columnas se ubican los elementos que conforman las entradas, actividades y salidas. Por último en la última columna se ubica la interface que existe con el cliente, si es que esta se llega a dar en alguna fase del proceso.

En la tabla 1.5 se muestra el estudio del grado de control que se tiene en cada una de las interfaces. Este estudio tiene la finalidad de encontrar posibles deficiencias en el control de los elementos que componen las interfaces durante el proceso de programación de la producción. Esta tabla contiene nueve cuestionamientos sobre la forma de llevar a cabo estas interfaces y la manera en la que se controlan los elementos en cada una de estas. En la parte final de la tabla 1.5 aparecen enumerados del 1 al 9 los cuestionamientos antes mencionados, así mismo en estas tablas aparece abreviado en área de atención a clientes como ATC y las iniciales N/A son iguales a no aplica dicha sección para esta interface.

HALLAZGOS -1-

Actualmente el sistema SAP tiene limitantes en la parte de Capacidades de Producción ya que no trabaja con capacidades reales lo cual genera mucho re-trabajo y errores en la confirmación de fechas a clientes.

La programación de la producción se lleva a cabo en Excel sin la ayuda de ningún método de optimización que asegure una secuencia que minimice los tiempos muertos ocasionados por los cambios entre diferentes productos.

El sistema SAP como tal desde su implementación se dejo para trabajar bajo un criterio de reposición de stock que para el tipo de proceso que se maneja en la planta de aislamientos no es aplicable en algunos casos.

CAPÍTULO 1

30

Proveedor (Interface) Entrada Actividad Salida Cliente (Interface)

ATC (1) Pedidos de

Clientes y

Ordenes de

Cliente)

1. Visualizar los

requerimient

os de los

clientes.

N/A N/A

ATC (2) Escalation

Process

Centros de

Fabricación (3)

Requisiciones

de Compra

N/A N/A

Producción (4) Capacidades

por Centro de

trabajo

2. Programar

Requerimient

os

N/A N/A

3. Avisar a ATC Aviso de falta de

capacidad

ATC (5)

Mantenimiento

(6)

Planes de

Mantenimien

to

4. Generar

programa de

producción.

N/A N/A

Logística (7) Itinerarios de

Transporte

N/A

Almacenes PT

(8)

Confiabilidad

de

Inventarios

N/A

Compras (9) Entregas a

Tiempo.

5. Generar

Ordenes de

Producción

N/A N/A

Almacén de Materia Prima (10)

Inventarios

N/A N/A

6. Enviar

Programa de

Producción

Programa

de

producción

Producción

y áreas

involucrada

s (11)

Calidad (12) Información

de

detenciones

7. Seguimiento

al programa

N/A N/A

Tabla 1.4 Interfaces del proceso de programación de la producción

CAPÍTULO 1

31

GRADO DE

CONTROL

DE LAS

INTERFACES

Interface I II III IV V VI VII VIII IX X XI XII

ATC (1) Se confirman los

pedidos en sistema

SAP

Vía Sistema y

Correo electrónico

Formal

ATC Programación Si Si Si No Si Si No

ATC (2) Recibir la solicitud

de escalar el

pedido

Vía Sistema y

Correo electrónico

Formal

ATC Programación Si Si Si No Si Si No

Centros de Fabricación (3)

Se confirman las

Requisiciones en

SAP. ME5A

Vía Sistema y

Correo electrónico

Formal Centros de

Fabricación

Programación Si Si Si No Si Si No

Producción (4) Recibir

capacidades de

producción

Correo electrónico Formal Producción Programación de

la producción.

Si Si Si No Si Si No

Avisar a ATC (5) Informar de la falta

de capacidad de

producción.

Correo electrónico Formal Programación de

la producción

ATC Si Si Si Si No Si Si

Mantenimiento (6)

Recibir los planes

de Mantenimiento

Programado

Correo electrónico Formal Mantenimiento Programación Si Si Si Si No Si Si

Logística (7) Recibir los

Itinerarios de

Transporte y

Equipo

Correo electrónico Formal Logística Programación

Logística

Si Si Si Si No Si Si

Almacenes PT (8) Recibir los niveles

de inventarios de

Producto

Terminado.

Vía Sistema SAP Formal Almacén de PT Programación Si Si Si Si No Si Si

CAPÍTULO 1

32

Compras (9) Visualizar en

sistema SAP las

órdenes de

compra y

requisiciones.

Vía Sistema y

Correo electrónico

Formal Compras Programación Si Si Si Si No Si No

Almacene de Materia Prima (10)

Recibir los niveles

de inventarios de

Insumos.

Vía Sistema SAP Formal Almacén de PT Programación Si Si Si Si No Si No

Producción y área Involucradas (11)

Enviar el programa

de Producción

Correo electrónico Formal Programación Áreas Involucradas

Producción.

Si Si Si Si No Si Si

Calidad (12) Informar de las

detenciones fuera

de especificación

Correo electrónico Formal Calidad Programación Si Si Si Si No Si Si

Tabla 1.5 Grado de Control de las Interfaces

I. ¿QUÉ SE SUPONE QUE PASA EN LA INTERFASE? II. ¿CUÁL ES EL MEDIO DE COMUNICACIÓN? III. ¿ES UNA INTERFACE FORMAL O INFORMAL? IV. ¿QUIÉN ES EL TRANSMISOR? V. ¿QUIÉN ES EL RECEPTOR?

VI. ¿SE NECESITA? VII. ¿ES CORRECTO EL MEDIO? VIII. ¿ESTÁ BIEN DEFINIDO EL “MENSAJE”? IX. ¿CUMPLE “EL PRODUCTO” LAS ESPECIFICACIONES? X. ¿EXISTE ALGÚN PROBLEMA REAL? XI. ¿SE ENTIENDE LO QUE DEBE TRATARSE EN LA INTERFASE, TANTO POR EL TRANSMISOR COMO POR

EL RECEPTOR? XII. ¿ES EFICIENTE LA INTERFACE?

CAPÍTULO 1

33

A partir de los datos obtenidos con la construcción de las tablas 1.4 y 1.5 es posible conocer algunos elementos a considerar para controlar las interfaces y los resultados que se obtienen al momento de transmitir información con las áreas relacionadas. Los hallazgos de esta índole se presentan en la tabla 1.6 que contiene un resumen de las áreas de oportunidad en esta parte del proceso.

HALLAZGOS -2-

Mantener actualizadas las órdenes de Clientes en

Sistema en tiempo real así como las listas de pedidos.

Actualización de listas estándar de materiales en

sistema.

Mantener Actualización de Requisiciones y órdenes

de compra en sistema (SAP)

Avisar oportunamente de las detenciones de

producto y disposición final.

Contar con la información de los Insumos

oportunamente

No se comunican los cambios de extracción en horno.

Tener disponibilidad oportuna de Itinerarios

Cumplir en Tiempo los planes de Mantenimiento

Mejorar confiabilidad de inventarios

Cumplir y respetar la secuencia de la programación de

líneas y procesos de manufactura.

Mejorar los tiempos de respuesta y confiabilidad de los

Proveedores.

Tabla 1.6 Hallazgos en el grado de control de las interfaces

Como se observa en la tabla 1.6 existen áreas de interés que pueden ser atendidas para generar posibles mejoras en el manejo de la interfaces del proceso. Los problemas que se generan por la interacción del área de programación de la producción y las demás áreas con las que se tiene una relación constante son debidos a la calidad de información que se maneja y la falta de actualización en tiempo real de la información que se encuentra en el sistema SAP.

Una de las interfaces con la que se tiene mayor intercambio de información es el área de producción, es por esto que se maneja una fuerte relación en los indicadores de ambas áreas. En el siguiente punto se estudia los indicadores del proceso que actualmente el área de programación de la producción maneja para medir la eficiencia del proceso, así como para verificar que la secuencia planeada se cumpla al momento de llevarla a cabo. Por otro lado el indicador de entregas a tiempo es tomado en cuenta como parte de la evaluación de las secuencias de producción generadas.

CAPÍTULO 1

34

Indicadores del proceso

En el proceso de programación de la producción existe un indicador clave para medir el comportamiento del proceso, el cual es nombrado como BTS (Built to schedule). Este indicador se enfoca en verificar el porcentaje de productos que fueron programados para un día específico y que fueron producidos en el volumen correcto, en la mezcla correcta y en la secuencia correcta.

El porcentaje de cumplimiento de la producción en volumen, mediante la medición de esta variable se trata de llevar un control de la cantidad de volumen que se produce en realidad en las líneas contra lo que se programó. Esto ayuda a diferenciar el cambio que se tiene, debido a problemas de producción que atrasan el programa, lo cual reduce la capacidad de extracción diaria en las líneas. Esta variable se calcula de la siguiente forma:

*100

El porcentaje de cumplimiento de la secuencia de producción mide el nivel en el cual es respetado el programa de producción en cuanto a secuencia se refiere. Los cambios en la secuencia afectan el tiempo total de producción y genera retrasos con respecto a la fecha límite de entrega del producto. Es por esto que se trata de minimizar los cambios en la secuencia de programación de lo planeado a la secuencia real del proceso.

*100

El porcentaje de cumplimiento de la mezcla indica cuantas de las piezas producidas (no se puede exceder el número de piezas programadas) fueron construidas en el día correcto como porcentaje de las piezas construidas a volumen.

*100

El área de programación de la producción tiene como objetivo mantener los niveles de cumplimiento del BTS al menos en el 85% del cumplimiento del programa. Finalmente para calcular este índice se utiliza la siguiente fórmula:

Por otro lado también se toma en cuenta el porcentaje de entregas a tiempo como un indicador de apoyo para el BTS, debido a que el tiempo de producción repercute directamente en los tiempos de entrega a los clientes. A continuación se muestra en la tabla1.7 los gráficos de cumplimiento del BTS del 2008 y 2009; en este periodo de tiempo en BTS tuvo un comportamiento real del 76.6%, lo cual está por debajo de las expectativas de la organización de mantenerlo al menos en un 85%. El porcentaje de entregas a tiempo tiene un promedio durante los primeros 10 meses del 2009 de 88.78% y la empresa tiene un plan de cumplir con el 100% de nivel de entregas a tiempo.

CAPÍTULO 1

35

INDICADORES DEL

PROCESO

Indicador: BTS Indicador : Entrega a tiempo

Plan 85.0 %

Real 76.6 %

Plan 100 %

Real 95.0 %

I. Sí

II. Sí

III. Sí

BTS Acumulado 2008 & 2009

7 8 . 4 %

7 2 . 2 %

8 6 . 5 %

8 0 . 4 %

8 5 . 6 %

7 5 . 3 %

6 5 . 9 %

7 1. 2 %

8 2 . 3 %

7 5 . 1%

8 5 . 8 %

6 6 . 6 %

7 1. 1%

7 6 . 6 %

0.00

0.20

0.40

0.60

0.80

1.00

1.20

1.40

1.60

1.80

2.00

0.00

0.10

0.20

0.30

0.40

0.50

0.60

0.70

0.80

0.90

1.00

% Cumplimient o Volumen 1.00 0.98 0.97 0.95 0.957 0.895 0.825 0.865 0.932 0.90 0.94 0.78 0.87 0.91

% Cumlimient o Mezcla 0.98 0.95 0.96 0.94 0.948 0.890 0.828 0.864 0.930 0.90 0.94 0.83 0.88 0.91

% Sequencia 0.80 0.76 0.91 0.88 0.939 0.901 0.839 0.909 0.926 0.89 0.95 0.92 0.88 0.89

BTS 0.78 0.72 0.87 0.80 0.856 0.753 0.659 0.712 0.823 0.751 0.86 0.67 0.71 0.766

Target 0.85 0.85 0.85 0.85 0.85 0.85 0.85 0.85 0.85 0.85 0.85 0.85 0.85 0.85

12 1 2 3 4 5 6 7 8 9 10 11 12 Avg.

0.00%

10.00%

20.00%

30.00%

40.00%

50.00%

60.00%

70.00%

80.00%

90.00%

100.00%

Enero

Fe

bre

ro

Marz

o

Ab

ril

Mayo

Ju

nio

Julio

Agosto

Sep

PROPORCIÓN DE ENTREGAS A TIEMPO VS CON RETRASO 2009

Late

On Time

CAPÍTULO 1

36

I. Si

II. Sí

III. Sí

IV. N/A

V. N/A

VI N/A

VII. N/A

IV. N/A

V. N/A

VI N/A

VII. N/A

Indicador Indicador

I. ¿ESTÁN DEFINIDAS LAS VARIABLES CRÍTICAS? II. ¿SE DEFINIERON LOS RANGOS DE OPERACIÓN? III. ¿SE TIENE DEFINIDO UN MÉTODO DE MEDICIÓN? IV. ¿SE TIENE DEFINIDO UN MÉTODO DE MUESTREO? V. ¿ESTÁ DEFINIDO UN EQUIPO DE MEDICIÓN PARA LA VARIABLE? VI. ¿SE CALIBRA EL EQUIPO Y LOS PATRONES? VII. ¿SE IDENTIFICA EL EQUIPO CALIBRADO?

Tabla 1.7 Indicadores del proceso.

CAPÍTULO 1

37

Los hallazgos encontrados en el rubro de indicadores del proceso tienen que ver con la falta de

cumplimiento de los estándares de operación mínimos establecidos por la organización y que se

miden a través de estos indicadores. En la tabla 1.8 se muestran algunos puntos a considerar

dentro de esta sección.

Tabla 1.8 Hallazgos en Indicadores del proceso.

Para continuar con el análisis del estado actual del proceso se desarrollo la tabla 1.9, la cual

contiene una revisión de las desviaciones que existen actualmente en el proceso por falta de

control de las actividades que conciernen a la ejecución de la de programación de la producción.

HALLAZGOS -3-

Las interrupciones continúas de los procesos derivadas por los tiempos muertos.

No se ha logrado la meta en BTS

No se están generando los planes de acción para revertir la tendencia negativa del indicador BTS.

La secuencia no se cumplen por parte de la planta.

No se ha logrado cumplir con la meta de entregas a tiempo.

CAPÍTULO 1

38

DESVIACIONES

ACTUALES DEL

PROCESO

Actividad Mano de

Obra

Materiales Máquinas Métodos

1. Visualizar los requerimientos de los clientes

Cumple con el control

N/A N/A No se está dando mantenimiento a las órdenes de clientes así como al la lista de pedidos.

2.- Programar Requerimientos de

los Clientes vs. Capacidades de

Producción.


N/A N/A No se notifican los cambios de extracción a programación de la producción.

3.- Avisar a ATC Cumple con el control

N/A N/A N/A

4.- Se genera el Programa de

Producción.


N/A N/A Cumple con el control

5.- Generar Ordenes de Producción

en SAP CO01


N/A N/A Falta Mantenimiento a las PO´s y Requisiciones de compra en SAP. Nota: PO´s Ordenes de producción

6- Enviar Programa de Producción Cumple con el control


7.- Dar Seguimiento al programa de

producción


N/A N/A No se cumple con el programa de producción, y no existen planes de mejora.

8.- Cerrar las órdenes de

producción.



Tabla 1.9 Desviaciones actuales del proceso

CAPÍTULO 1

39

1.2.4 Estado actual del cumplimiento del proceso.

El objetivo del proceso de programación de la producción no siempre se cumple debido a las

variaciones que se generan durante el proceso de producción. Estas variaciones son provocadas

por fallas en las líneas principalmente. Las metas en el cumplimiento del programa no se han

alcanzado como se muestra en la medición histórica de los indicadores del proceso. El sistema SAP

no tiene una parametrización acorde a las necesidades de la empresa lo que influye directamente

en la planeación de las actividades del proceso. A demás debido a que la programación de las

líneas se hace de forma manual y sin la ayuda de algún método de optimización, no se asegura una

buena secuenciación de los trabajos que permita un mejor desempeño de las líneas. Las

alternativas de solución a los hallazgos de estudio de procesos son enlistadas a continuación.

Alternativas de solución a los hallazgos encontrados.

Realizar y mantener planes de mejora para incrementar la certidumbre de las operaciones; en

este momento el área de programación de la producción no ha generado planes de mejora que

le permitan desarrollar el proceso de una forma más eficiente. Si bien es cierto que se han

establecido por una parte indicadores de la eficiencia del proceso, que permiten conocer su

comportamiento histórico, no se han tomado medidas para llevarlo a cumplir con los parámetros

establecidos para su desempeño.

Mejorar la planeación de insumos vía sistema SAP; los insumos que aparecen en el sistema y que

son necesarios para la elaboración de los productos algunas veces aparecen en existencia en el

SAP, pero no existe el insumo de forma física en el almacén. El tiempo de actualización de las

entradas y salidas de insumos no se lleva a cabo en tiempo real, por lo que la información del

sistema genera incertidumbre en la planeación.

Mantenimiento a Listas (STD) de Materiales en SAP, ya que estas listas contienen la información

de todos los insumos que se requieren para generar una unidad de producto necesitan estar

actualizadas para establecer un control de la veracidad de la información que estas contienen.

Estas listas cuentan con información sobre las características específicas de cada producto, por

lo que dicha información necesita un seguimiento para asegurar que lo que entra en el sistema

son datos reales y consistentes con el proceso productivo.

Seguimiento y mantenimiento a órdenes de compra, requisiciones y órdenes planeadas en SAP

para centros de fabricación; Todas las ordenes que provienen de los centros de fabricación tanto

de Monterrey como de Mexicali son enviadas por fuera del sistema por lo que se conoce como

Escalation Process, lo que genera un mayor tiempo de procesamiento de la orden de pedido o

requerimiento. El sistema SAP es el sistema de administración de negocio que maneja OC

México, debido a esto es indispensable que todas las entradas se manejen a través de este

sistema, ya que si no se hace de esta forma genera retrasos en la capacidad de respuesta del área

de programación.

Desarrollo de una aplicación para la programación de la producción de las dos líneas de

producción, a través de un algoritmo de secuenciación; este proyecto está enfocado en

CAPÍTULO 1

40

desarrollar un algoritmo capaz de encontrar secuencias que minimicen el tiempo de cambio

entre productos, debido a que actualmente el área no maneja ningún método de optimización

para este aspecto de la programación de la producción.

Cumplir con los planes de mantenimiento; un elemento que afecta el cumplimiento de la

secuencia de producción y por consecuencia el deterioro del indicador BTS son los

mantenimientos no planeados. Estos mantenimientos que se realizan por fuera del plan son

ocasionados por fallas en el funcionamiento del horno y de las líneas de producción, por lo que

es necesario mejorar un programa de mantenimiento eficaz que permita mejorar la certidumbre

del proceso productivo.

CAPÍTULO 2

41

Capítulo 2. Programación de tareas en líneas de producción paralelas.

2.1 Cadena de suministros.

Para establecer un punto de partida se debe revisar las características que engloban el enfoque principal de estudio en este proyecto de investigación, que va encaminado desde la perspectiva de la cadena de suministros (SC Supply Chain) por sus siglas en ingles. Es debido a lo anterior que es importante revisar lo que abarca este concepto.

Nichols (1999) Sugiere que la cadena de suministros abarca todas las actividades relacionadas con el flujo y trasformación de bienes y servicios, desde la etapa de extracción de la materia prima hasta que el producto terminado llega al usuario final, así como los flujos de información relacionados con estos procesos. También explica que los materiales y la información fluyen en sentido ascendente y descendente en la cadena de suministros.

Por otra parte existen autores como Simchi Levi David (2003) que sugieren que la cadena de suministro, está conformada por proveedores, centros de manufactura, almacenes y centros de distribución, así también como las materias primas, trabajos en proceso, inventario, y productos terminados que fluyen a través de la cadena. Es importante retomar la visión que este autor tiene sobre la cadena de suministros ya que la considera como un sistema dinámico que evoluciona con el tiempo. De hecho, no sólo la demanda del cliente y capacidades de los proveedores cambian con el tiempo. La interacción entre cada una de las partes que componen la cadena de suministros también cambia constantemente. Esta visión enfatiza el hecho de que en un sistema que evoluciona como lo es la cadena de suministros, las partes que lo componen deben de estar preparadas para asimilar los constantes cambios que esta sufre.

Cadena extendida de suministros.

Según Ballou (2004) la cadena extendida de suministros se refiere a aquellos miembros del canal de suministros más allá de los proveedores o de los clientes inmediatos de una empresa. Pueden ser los proveedores de los proveedores inmediatos o los clientes de los clientes inmediatos y así hasta llegar a los puntos de origen de la materia prima o a los consumidores finales.

La logística en la cadena de suministros.

El Consejo de la Dirección Logística o (Council of Logistics Management CML) define a la logística como la parte del flujo de la cadena de suministros que planea, lleva a cabo y controla el flujo y almacenamiento eficientes y efectivos de bienes y servicios, así como de la información relacionada, desde el punto de origen hasta el punto de consumo, con el fin de satisfacer los requerimientos de los clientes.

CAPÍTULO 2

42

Componentes de un sistema típico de logística en la cadena de suministros.

En Administración de la Cadena de Suministros de Ballou (2004) se sugiere que separar la dirección de la logística de los negocios de la dirección de la cadena de suministros puede llegar a ser un poco complicado, ya que en algunos aspectos, promueven la misma misión. Esta misión es llevar los bienes o servicios adecuados al lugar adecuado, en el momento adecuado y en las condiciones deseadas, a la vez que se consigue la mayor contribución a la empresa.

Las actividades que se dirigen para conformar a la logística de los negocios pueden variar de una empresa a otra dependiendo de la estructura organizacional de cada una y de otros factores internos que pueden llegar a afectar este rubro, mas sin embrago Oak Brook (2000), IL: Council of Logistics Management hace referencia a que los componentes de un sistema típico de logística son: servicios al cliente, pronósticos de la demanda, comunicaciones de distribución, control de inventarios, manejo de materiales, procesamiento de pedidos, apoyo de partes y servicio, selección de la ubicación de fabricas y almacenamiento (Análisis de localización), compras, embalaje, manejo de bienes devueltos, eliminación de mercaderías aseguradas rescatada (desechos) y desperdicios, tráfico y transporte, almacenamiento y provisión.

En este aspecto Ballou (2004) proporciona una lista de actividades clave y actividades de apoyo que proporciona la logística a la cadena de suministros, a continuación se muestra dichas actividades de manera general y sintetizada:

Actividades Clave

1. Estándares del servicio al cliente. 2. Transporte. 3. Manejo de inventarios. 4. Flujos de información y procesamiento de pedidos.

Actividades de Apoyo

1. Almacenamiento. 2. Manejo de materiales. 3. Compras. 4. Embalaje de protección. 5. Cooperación con producción. 6. Mantenimiento de información.

En la siguiente figura 2.1 se muestra claramente como se organizan estos componentes, o actividades, dependiendo del punto donde puedan tener lugar en el canal de suministros. Esto se refiere a si son actividades de entrada o actividades de salida dentro de la cadena de suministros de una empresa.

CAPÍTULO 2

43

Figura 2.1 Modelo de dirección de la cadena de suministros. (Ballou, Logística Administración de la cadena de suministro, 5ta ed, Editorial Pearson Prentice Hall, 2004)

De acuerdo con la figura 2.1 todos los procesos logísticos que se llevan a cabo en una fuente de suministros son flujos de entrada para las fábricas encargadas de transformar dichos suministros en producto terminado. Las empresas encargadas de transformar esta materia prima, tienen que tomar en cuenta algunos procesos diferentes, como lo es el proceso de programación de los pedidos, a través del cual se planea y controla la capacidad de las plantas para poder cumplir con la cantidad de producto que los clientes le demandan. Otros procesos como el trasporte, mantenimiento de inventario, almacenamiento, manejo de materiales y el mantenimiento de la información no cambian independientemente de si se es una fuente de suministro o una fabrica. El flujo y los procesos de dirección de la cadena de suministros están enfocados siempre a las necesidades de los clientes finales.

2.1.1 Administración de la cadena de Suministros.

La administración de la cadena de suministros (SCM Supply Chain Management) por sus siglas en ingles es un concepto importante que las organizaciones de hoy en día deben tomar en cuenta, ya que como menciona Ballou (2004). Las empresas se han ocupado continuamente de las actividades de movimiento y almacenamiento (transporte e inventario). La novedad de este campo estriba en el concepto de dirección coordinada de las actividades relacionadas, en vez de la práctica histórica de manejarlas de manera separada, además del concepto de que la cadena de suministros añade valor a los productos o servicios esenciales para la satisfacción del cliente y para las ventas. Una vez que se ha enfatizado la importancia de una correcta administración de la cadena de suministros es necesario profundizar en la definición del concepto, para lo cual es necesario revisar la conceptualización que algunos autores importantes como Ballou (2004), Mentzer (2001) y Nichols (1999) le dan a la administración de la cadena de suministros.

CAPÍTULO 2

44

También Ballou (2004) deja en claro que el manejo de la cadena de suministros enfatiza las interacciones de la logística que tienen lugar entre las funciones de marketing, logística y producción en una empresa, y las interacciones que se llevan a cabo entre empresas independientes legalmente dentro del canal de flujo del producto.

A continuación se presentan dos perspectivas o definiciones diferentes de lo que es la Administración de la cadena de suministros:

Por una parte Mentzer (2001) sostiene que la administración de la cadena de suministros se define como la coordinación sistemática y estratégica de las funciones tradicionales del negocio y de las tácticas a través de estas funciones empresariales dentro de una compañía en particular, y a través de las empresas que participan en la cadena de suministros con el fin de mejorar el desempeño a largo plazo de las empresas individuales y de la cadena de suministros como un todo.

A su vez Nichols (1999) deja en claro que la cadena de suministros abarca todas las actividades relacionadas con el flujo y trasformación de bienes, desde la etapa de materia prima (extracción) hasta el usuario final y que la administración de la cadena de suministros es la integración de estas actividades mediante el mejoramiento de las relaciones de la cadena de suministros para alcanzar una ventaja competitiva sustentable.

Tal vez una definición que completa y sintetiza las anteriores es la de Simchi Levi David (2003) el cual argumenta que la administración de la cadena de suministros es una serie de herramientas utilizadas para integrar eficientemente, proveedores, manufactureros, almacenes y tiendas, de tal manera que las mercancías sean producidas y distribuidas en las cantidades correctas, en el lugar correcto y en el tiempo correcto, Lo anterior con el objetivo de minimizar los costos mientras se satisfacen los niveles de servicio requeridos. Por otra parte este mismo autor sostiene que su definición de administración de la cadena de suministros es similar a la definición de administración logística dada por el Council Of Logistics Management (2000), la cual menciona que la administración logística se define como el proceso de planeación, implementación y control de manera eficiente de los costos del flujo de efectivo, almacén de materias primas, inventario en proceso y de producto terminado y la información que fluye desde el punto de origen hasta el punto de consumo con el propósito de cumplir con los requerimientos del cliente.

El modelo de dirección de la cadena de suministros.

Para Ballou (2004) el modelo de dirección de la cadena de suministros visto como un conducto directo de transmisión, muestra la amplitud de la definición de la administración de la cadena de suministros. Mentzer (2001) Explica que es importante notar que la dirección de la cadena de suministros trata de la coordinación de los flujos de producto mediante funciones y a través de las compañías para lograr la ventaja competitiva y la productividad para empresas individuales en la cadena de suministros y para los miembros de la cadena de suministros de manera colectiva. A continuación se muestra la figura 2.2 para poder visualizar el modelo de dirección que propone Mentzer (2001) para la dirección de la cadena de suministros, así como los flujos que se dan en la interacción por parte de los procesos y actividades que conforman este modelo.

CAPÍTULO 2

45

Figura 2.2 Modelo de dirección de la cadena de suministros. (Fuente: Mentzer at al, “Defining Supply Chain Management”, Journal of Business Logistics, Vol. 22, Núm. 2 (2001), pág 19.)

De acuerdo con el modelo de la figura 2.2, las empresas que están inmersas en una cadena de suministros, deben de coordinar sus funciones de acuerdo a una planeación global de todas las actividades clave dentro del proceso de dirección de dicha cadena. A su vez entre las actividades y funciones debe existir una estrecha interrelación para no perder de vista el objetivo principal, que es la satisfacción del cliente. Por otro lado los flujos de información deben de estar abiertos entre cada una de las compañías, para poder agilizar la respuesta, en caso de algún cambio o problema surja de manera inesperada. Estos flujos de información deben de ser actualizados y revisados constantemente para que dicha información sea lo más confiable posible. Los flujos físicos de la cadena de suministros deben de ser integrados mediante una correcta estrategia de transporte y políticas de inventario.

2.1.2 La importancia de la cadena de suministros.

Es necesario enfatizar el sentido de relevancia que cobra la cadena de suministros en el momento que el producto o servicio es requerido por los clientes. Las necesidades de los clientes son parte fundamental para el soporte que da la cadena de suministros de cualquier bien o servicio que se distribuye a lo largo de la cadena.

Ballou (2004) Deja en claro que la cadena de suministro gira en torno a crear valor: valor para los clientes y proveedores de la empresa, y valor para los accionistas de la empresa. El valor en la cadena de suministros se expresa fundamentalmente en términos de tiempo y lugar. Los productos y servicios no tienen valor a menos que estén en posesión de los clientes cuándo (tiempo) y dónde (lugar) ellos deseen consumirlos. Una buena administración de la cadena de

CAPÍTULO 2

46

suministros visualiza cada actividad en la cadena como una contribución al proceso de añadir valor. Si solo se le puede añadir poco valor entonces, se podrá cuestionar si dicha actividad debe existir. Sin embargo, se añade valor cuando los clientes prefieren pagar más por un producto o un servicio que lo que cuesta ponerlo en sus manos. Por varias razones, para muchas empresas de todo el mundo, la logística se ha vuelto un proceso cada vez más importante al momento de añadir valor.

El alcance de la moderna cadena de suministros.

El enfoque y los alcances que hoy en día se dan a la cadena de suministros han cambiado la perspectiva de que las empresas son negocios aislados. Como lo menciona Ballou (2004) los defensores de la dirección de la cadena de suministros que ven el aérea más ampliamente que algunos responsables de la logística han estado promoviendo con gran fuerza la necesidad de colaboración entre los miembros del canal de suministros que están fuera del control inmediato del gerente de logística de una compañía, es decir, los miembros que son legalmente compañías separadas. En el siguiente diagrama se muestra la relación y los principales flujos a través de los cuales la cadena esta interconectada, esto para cumplir con sus funciones.

Figura 2.3. Alcance de la moderna cadena de suministros. (Fuente: Ballou, Logística Administración de la cadena de suministro, 5ta ed, Editorial Pearson Prentice Hall, 2004)

Para entender más afondo la figura 2.3 es esencial entender que la colaboración entre los miembros del canal vinculados mediante relaciones comprador-vendedor para alcanzar los beneficios costo-servicio, son imposibles de lograrse por los gerentes con una vista interna rígida de sus responsabilidades. Es importante tener en cuenta la anterior perspectiva, ya que como cita Ballou (2004) “Dirigir en este ambiente más amplio es el nuevo reto para el gerente de la logística contemporánea”.

La cadena de suministros desde el punto de vista estratégico.

Es necesario entender a la cadena de suministros como un aspecto del negocio a través del cual las empresas pueden generar y sustentar gran parte de sus estrategias. Cuando la dirección de una organización reconoce que la cadena de suministros afecta a una parte importante de los costos de una empresa y que el resultado de las decisiones que toma en relación con los procesos de la cadena de suministros reditúa en diferentes niveles de servicio al cliente, está en posición de usar esto de manera efectiva para penetrar nuevos mercados, para incrementar la cuota del mercado y

CAPÍTULO 2

47

para aumentar los beneficios. Para la selección adecuada de estas estrategias de la cadena de suministros es necesario como advierte (Ballou, 2004) un proceso creativo para desarrollar una adecuada estrategia corporativa, ya que los enfoques innovadores en la estrategia de la cadena de suministros pueden representar una ventaja competitiva.

Objetivos principales de una estrategia de cadena de suministros

De acuerdo con (Ballou, 2004) Una estrategia en la cadena de suministros cuenta con tres objetivos: reducción de costos, reducción de capital y mejora del servicio, los cuales se explican de manera más detallada a continuación.

La reducción de costos es una estrategia dirigida hacia lograr minimizar los costos variables asociados con el desplazamiento y el almacenamiento. La mejora estratégica por lo general es formulada al evaluar líneas de acción alternativas, como la selección entre diferentes ubicaciones de almacén o la selección entre modos de transporte alternativos. Los niveles de servicio por lo general se mantienen constantes mientras se buscan las alternativas del mínimo costo.

La reducción de capital es una estrategia dirigida hacia la minimización del nivel de inversión en el sistema logístico. La maximización del rendimiento sobre los activos logísticos es la motivación detrás de esta estrategia. El envío directo a los clientes para evitar almacenamiento, la selección de un enfoqué justo a tiempo en vez de almacenar inventarios, o la utilización de proveedores externos de servicios logísticos. Estas estrategias pueden dar por resultado costos variables más altos que en estrategias que requieren mayor nivel de inversión; sin embargo, el rendimiento sobre la inversión puede incrementarse.

Las estrategias de mejora del servicio por lo general reconocen que los ingresos dependen del nivel proporcionado del servicio de logística. Aunque los costos se incrementan rápidamente ante mayores niveles de servicio logístico al cliente, los mayores ingresos pueden compensar a los mayores costos.

Estrategias de sistemas Push, Pull, y Push-Pull.

Para Simchi Levi David (2003) las estrategias en cuanto a cadena de suministros se refiere son a menudo catalogadas en Push, Pull, y Push-Pull, esto debido a la revolución en los años 80´s de estos sistemas de manufactura, los cuales fueron divididos en estas tres categorías. Debido a esto es importante revisar las características de este tipo de enfoque estratégico para la cadena de suministros.

Estrategia Push (Empujar) en cadena de suministros.

Simchi Levi David (2003) explica que en una cadena de suministros basada en un sistema Push, las decisiones de producción y distribución se basan en pronósticos a largo plazo. Normalmente, las

bases de la demanda de la manufactura están basadas en pronósticos de los pedidos recibidos de los almacenes y de los minoristas. Por lo tanto, le lleva mucho más tiempo a una cadena de suministro "Push" para reaccionar ante la evolución de los mercados, lo que puede conducir a:

La obsolescencia del inventario de la cadena de suministro para ciertos productos que desaparecen del mercado.

La incapacidad para satisfacer los cambiantes patrones de la demanda

CAPÍTULO 2

48

Estrategia Pull (Jalar) en cadena de suministros.

Por otro lado Simchi Levi David (2003) sostiene que en una cadena de suministros basada en un sistema Pull, la producción y la distribución están basadas en demanda real de tal manera que se coordinen con las necesidades de demanda reales del cliente y no a través de pronósticos de la demanda. En un sistema Pull la empresa no mantiene ningún inventario y solo responde a órdenes de pedido reales y especificas. Esto es posible debido a los mecanismos que proporcionan un flujo de trasferencia de información sobre la demanda de los clientes son rápidos y eficientes. Los sistemas tipo Pull son muy atractivos ya que permiten:

Una disminución del tiempo de espera, que se logra a través de la capacidad para anticipar de una mejor manera los pedidos de los clientes.

Una disminución en el inventario en los almacenes de los minoristas, ya que los niveles de inventario en estas instalaciones aumentan con los plazos de entrega.

Una disminución en la variabilidad del sistema, y en particular la variabilidad a la que se enfrentan los manufactureros debido a la reducción del plazo de entrega.

La disminución de inventario de los manufactureros debido a la reducción de la variabilidad.

Estrategia Push-Pull en cadena de suministros.

Para Simchi Levi David (2003) en una estrategia Push-Pull algunas etapas de la cadena de suministros, por lo general las etapas iniciales son manejadas bajo un sistema Push mientras las etapas restantes emplean un sistema Pull. La interface entre las etapas manejadas con sistema Push y las etapas manejadas con sistema Pull es conocida como la frontera entre el Push-Pull.

Figura 2.4 Cadena de suministros Push-Pull (Simchi-Levi, Philip Kaminsky, Designing and Managing the supply chain, 2da ed, Editorial McGraw-Hil, 2003)

En la figura 2.4 anterior se muestra que en una estrategia combinada de cadena de suministros tipo Push-Pull las estrategias tipo Push siempre están más cerca, o son implantadas en las fases primarias de la trasformación de la materia prima. Por otra las estrategias tipo Pull siempre se encuentran más cercanas al cliente, debido a que en esta parte de la cadena de suministros es necesaria una mejor respuesta ante los cambios que ocurren en el mercado.

CAPÍTULO 2

49

La estrategia apropiada para la cadena de suministros dependiendo de las características del sistema.

Para identificar cual es la estrategia que mejor se adapta a la cadena de suministros de un producto Simchi Levi David (2003), propone el siguiente esquema (Figura 1-5) para realizar este análisis. Este diagrama se basa en la decisión de elegir una cadena diseñada para funcionar a través de una estrategia tipo Push, una tipo Pull, o una combinación de las anteriores.

Figura 2.5 Cadena de suministros Push-Pull (Simchi-Levi, Philip Kaminsky, Designing and Managing the supply chain, 2da ed, Editorial McGraw-Hil, 2003)

Del esquema anterior es indispensable destacar que la selección de las estrategias para los productos está basada en dos aspectos fundamentales, el primero es la incertidumbre en la demanda de los bienes o servicios y el segundo es la importancia de las economías de escala para el manejo del negocio. Dependiendo de la comparación y cruce de estos dos factores, a través del esquema de la Figura 2.5 se puede conocer el tipo de estrategia que es factible implementar para la cadena de suministros del producto. Por otra parte Simchi Levi David (2003) explica la segmentación del diagrama de la siguiente manera:

Cuadro 1: Representa industrias que se caracterizan por una alta incertidumbre en la demanda de los productos, además de que las economías de escala tanto en su sistema productivo como en su distribución no son importantes en este caso se sugiere un sistema Pull para el manejo de la cadena de suministros.

Cuadro 3: Representa productos que se caracterizan por una baja incertidumbre en la demanda y un manejo importante de las economías de escala. La demanda para estos productos es estable, mientras la reducción de los costos de transportación es una variable crítica de control dentro de los costos de la cadena de suministros. Por lo anterior una estrategia basada en un sistema Push es apropiada para este tipo de productos.

Cuadro 4: Representa productos caracterizados por una baja incertidumbre en la demanda, indicando un sistema Push para su manejo, por otro lado las bajas economías de escala que requiere sugieren un sistema Pull para la conducción de la cadena de

CAPÍTULO 2

50

suministros. En estos casos la estrategia más adecuada es una combinación Push-Pull, sin embrago es necesario analizar mas afondo este tipo de casos para poder tomar una correcta decisión.

Cuadro 2: Representa productos e industrias, los cuales tienen una elevada incertidumbre en la demanda, además de dar mucha importancia a las economías de escala para reducir costos de producción y de trasportación. En este caso se sugiere implementar una estrategia combinada Push-Pull analizando cuidadosamente que partes de la cadena trabajaran con un sistema Push y cuales lo harán a través de un sistema Pull.

2.1.3 Servicio al cliente.

Kyj (1994) dice que el servicio al cliente se refiere específicamente a la cadena de actividades orientadas a la satisfacción de las ventas, que en general inician con el ingreso del pedido y finalizan con la entrega del producto a los clientes, continuando con algunos casos como servicio o mantenimiento de equipo, u otros como soporte técnico.

De forma más simple, Heskett (1994) establece que el servicio logístico al cliente para muchas empresas es “La velocidad y confiabilidad con la que pueden estar disponibles los artículos ordenados (por los clientes)”.

Más recientemente Doctker (2000) menciona que, el servicio al cliente se ha denominado un proceso de satisfacción total el cual puede describirse como el proceso integral de cumplir con el pedido de un cliente. Este proceso incluye la recepción del pedido (ya sea manual o electrónica), administración del pago, recolección y empacado de los productos, envío del paquete, entrega del mismo, y proporcionar el servicio al cliente para el usuario final así como el manejo de posible devolución de los productos.

Ballou (2004) hace mención de que las estrategias de la cadena de suministros están enfocadas a cuatro aéreas principales de problemas: niveles de servicio al cliente, ubicación de instalaciones, decisiones de inventario y decisiones de transportación. Para tener la perspectiva de lo que implica un correcto nivel de servicio al cliente es necesario retomar el triangulo de planeación logística propuesto por Ballou y que se observa en la Figura 2.6, el cual enfatiza que todas las estrategias deben estar enfocadas a proporcionar un mejor nivel de servicio a los clientes. En la parte central de este diagrama se remarca que el objetivo principal de administrar una cadena de suministros es el servicio al cliente. Para cumplir dicho objetivo es necesario trabajar en desarrollar e implantar las tres estrategias elementales de administración de la cadena de suministros, las cuales son: estrategia de inventario, estrategia de localización y la estrategia de transporte. Cada una de estas estrategias tiene actividades clave que deben de realizarse de manera adecuada para poder cumplir con el objetivo. Dichas actividades están especificadas para cada una de las estrategias en la figura 2.6.

CAPÍTULO 2

51

Figura 2.6 Triángulo de la planeación en relación a las principales actividades de la Administración de la cadena de suministros. (Fuente: Ballou, Logística Administración de la cadena de suministro, 5ta ed,

Editorial Pearson Prentice Hall, 2004)

En mayor medida que cualquier otro factor, el nivel proporcionado de servicio logístico al cliente afectará en forma notable el diseño del sistema. Los bajos niveles de servicio permiten inventarios centralizados en sólo unas cuantas ubicaciones y también permiten el uso de formas de transporte menos costosas. Los altos niveles de servicio por lo general requieren justamente lo contrario. Sin embargo, cuando se presionan los niveles hacia sus límites superiores, los costos de logística se elevarán a una razón desproporcionada con respecto del nivel de servicio. Por ello la primera preocupación en la planeación estratégica de logística deberá ser el adecuado establecimiento de los niveles de servicio al cliente.

Elementos del servicio al cliente.

Un estudio detallado del servicio al cliente, patrocinado por el Council of Logistics Management, identifico los elementos del servicio al cliente de acuerdo con el momento en que ocurre la transacción entre el proveedor y el cliente. Estos elementos se agrupan en las categorías de presentación, transacción y postransacción como se observa más adelante en la Figura 2.7. Dicho diagrama fue propuesto por Bernard y Zinzer (1975) y se explica a continuación:

Los elementos de presentación establecen un ambiente adecuado para un buen servicio al cliente. Mediante una declaración escrita de la política del servicio al cliente, así como del tiempo en que serán entregados los bienes una vez que se levante el pedido, el procedimiento para manejar devoluciones y órdenes atrasadas, y los métodos de envío, el cliente conocerá el tipo de servicio que debe esperar.

Los elementos de transacción son aquellos que dan por resultado directo la entrega del producto al cliente. El establecimiento de los niveles de inventario, las formas de transportación y la implantación de procedimientos de pedidos son ejemplos de ello. Estos elementos, a su vez, afectan los tiempos de entrega, la precisión de cumplimiento de pedidos, la condición de los bienes por recibir y la disponibilidad de inventario.

CAPÍTULO 2

52

Los elementos postransacción se presentan después de la venta del producto pero deben planearse en las etapas de pretransacción y de transacción. Además representan al conjunto de servicios necesarios para mantener el producto en el campo y proteger a los clientes de productos defectuosos.

Figura 2.7 Elementos del servicio al cliente (Fuente: Bernard J; LaLonde y Paul H. Zinzer (1975))

Importancia relativa de los elementos del servicio al cliente.

Sterling y Lambert (1989) estudiaron con cierta profundidad la industria de los sistemas y mobiliario de oficina. Esta investigación mostro que la distribución física (DF/ servicio al cliente) es un componente integral y necesario de la mezcla de marketing y que presenta una importante oportunidad para que las empresas obtengan una ventaja diferencial en el mercado. En un estudio similar del mercado secundario del cristal para autos, Innis y Lalonde (1994) observaron que en particular, altos índices de satisfacción, frecuencia de entrega e información sobre disponibilidad de inventarios, fecha de envío proyectada y fecha de entrega proyectada al momento de colocar el pedido recibieron las más altas calificaciones entre la base de clientes al menudeo.

En resumen para Keebler y Manrodt (2000), los elementos de servicio logístico al cliente que se consideran como los más importantes debido a que tienen gran inferencia en la calidad y nivel de servicio al cliente, son los siguientes:

Entrega a tiempo.

Rapidez de atención a un pedido.

Condición del producto.

Documentación precisa.

CAPÍTULO 2

53

Tiempo ciclo de pedido

Los principales elementos del servicio al cliente que pueden controlar los responsables de logística se capturan dentro del concepto de tiempo del ciclo del pedido (o del servicio). El tiempo de ciclo del pedido puede definirse de acuerdo a Ballou (2004) como:

“El tiempo transcurrido entre el momento en que se levanta un pedido de cliente una orden de compra o una solicitud de servicio y el momento en el que el producto o servicio es recibido por el cliente.”

Para Ballou (2004) los elementos del tiempo ciclo de pedido son el tiempo de transmisión, el tiempo del procesamiento del pedido, el tiempo de ensamblado del pedido, la disponibilidad del inventario, el tiempo de producción y el tiempo de entrega. Estos elementos se controlan directa o indirectamente mediante la elección y el diseño de métodos de transmisión de pedidos, políticas de inventario-almacenamiento, procedimientos de procesamiento de pedidos, modos de transporte y métodos de programación.

Dentro de este aspecto del tiempo ciclo de pedido se menciona que el tiempo de producción es fundamental para cumplir con el nivel de servicio al cliente. Para poder analizar la forma de optimizar los tiempos de producción, a través de métodos de programación eficientes, en los siguientes puntos se estudia y analiza el problema de secuenciación de trabajos y algunos algoritmos que pueden ser utilizados para resolver dicho problema de forma factible.

CAPÍTULO 2

54

2.2 Optimización de la secuenciación de trabajos (Scheduling).

La secuenciación (scheduling) se refiere a la asignación de recursos escasos a las actividades con el objetivo de optimizar una o más medidas de desempeño. Dependiendo de la situación, los recursos y actividades pueden asumir muchas formas diferentes. Los recursos pueden ser las máquinas en una fábrica o las líneas de producción, dispositivos en un sistema informático etc. Hay variadas medidas de desempeño. Uno de los objetivos puede ser la minimización del tiempo de terminación del último trabajo procesado (Makespan), mientras que otro objetivo puede ser la reducción al mínimo del número de trabajos tardíos o realizados después de una fecha límite.

El estudio de la secuenciación se remonta a 1950. Los investigadores en el campo de la, ingeniería industrial, investigación de operaciones y la gestión de recursos se encontraron con el problema de la administración de las diversas actividades que ocurren en un taller. Una buena programación de algoritmos puede reducir el costo de producción en un proceso de fabricación, permitiendo a la compañía mantener su competitividad y mejorar su nivel de servicio. A partir de finales de 1960, científicos en el campo de la computación también encontraron problemas de secuenciación en el desarrollo de sistemas operativos. En aquellos días, los recursos de cómputo (como CPU, memoria) eran escasos. La utilización eficiente de estos recursos de cómputo puede reducir el costo de la ejecución de programas. Esto proporcionó una razón económica para el estudio de la secuenciación.

Los problemas de programación estudiados en la década de 1950 eran relativamente simples. Una serie de algoritmos eficientes fueron desarrollados para proporcionar soluciones óptimas. Las más notables son la obra de Jackson, Johnson, y Smith. Con el tiempo los problemas encontrados se volvieron más sofisticados, y los investigadores fueron incapaces de desarrollar algoritmos eficientes para ellos. La mayoría de los investigadores trataron de desarrollar métodos eficaces de Ramificación y Acotamiento (Branch and Bound) que son esencialmente los algoritmos de tiempo exponencial. Con el advenimiento de la teoría de la complejidad computacional con artículos como el de Karp (1972), los investigadores comenzaron a darse cuenta de que muchos de estos problemas pueden ser difíciles de resolver. En la década de 1970, muchos problemas de secuenciación fueron clasificados como NP-duros (Hard), de acurdo a la teoría de la complejidad computacional. Por otro lado como menciona Leung (2004) en la década de 1980, las investigaciones se llevaron a cabo en varias direcciones en el mundo académico. Una dirección fue el desarrollo y análisis de algoritmos de aproximación. Otra dirección fue la creciente atención prestada a problemas de programación estocástica. A partir de entonces, la investigación en la teoría de la programación se amplió a pasos agigantados. Después de casi 50 años, ahora hay un cuerpo impresionante de conocimientos en este campo.

CAPÍTULO 2

55

2.2.1 Definición de un problema de secuenciación de trabajos.

Para definir un problema de programación, se requiere conocer la notación básica de los modelos de secuenciación, para esto se toma las definiciones y conceptualización de los trabajos de Brucker (2007), Pinedo( 1995) y Leung( 2004). Supóngase que m máquinas Mj (j = 1, . . .,m) tienen que procesar n trabajos Ji(i = 1, . . . , n). Por lo que se necesita programar una secuenciación para cada trabajo y asegurar la disponibilidad, esto para uno o más intervalos de tiempo y para una o más máquinas. Una secuenciación puede ser representada a través de un grafico de Gantt, como se muestra en la siguiente figura 1.8. Los diagramas de Gantt pueden estar orientados por máquina 1-8 (a) o por trabajos figura 1.8 (b). El correspondiente problema de programación es encontrar una secuenciación capaz de satisfacer las restricciones del sistema.

Figura 2-8 Diagrama de Gantt para la orientación por Máquina y por Trabajo (Brucker Peter. Scheduling

Algorithms, 5ta Edición 2007, ed Springer.)

2.2.1.1 Definición de trabajo

La definición de un trabajo puede sustentarse de la siguiente forma, de acuerdo con Leung (2004), un trabajo se compone de un número de operaciones . Asociado con la operación hay un tiempo de procesamiento de . Si el trabajo consiste en una sola

operación ( ), podemos entonces identificar a con y se denota el requerimiento de procesamiento por . Por otra parte, hay una fecha de liberación , en la que la primera operación de pasa a estar disponible para la transformación que se ha especificado. Asociado con cada operación existe un conjunto de máquinas μij {M1, . . .,Mm}. Las operaciones

podrán ser procesadas en cualquiera de las máquinas μij. Por lo general, μij son conjuntos de un solo elemento o todos los μij, son iguales al conjunto de todas las máquinas. En el primer caso se tienen máquinas dedicadas. En el segundo caso, las máquinas están posicionadas en forma paralela. El caso general se presenta para poder solucionar problemas de manufactura flexible, donde las máquinas cuentan con diferentes herramientas. Esto significa que una operación puede ser procesada en cualquier máquina que está equipada con la herramienta adecuada. A este tipo

CAPÍTULO 2

56

de problemas de secuenciación (scheduling), se les conoce como problemas con Máquinas Multipropósito o por sus siglas en ingles (MPM Multi-Purpose-Machines). Por otro lado también es posible que todas las máquinas en el conjunto μij sean usadas simultáneamente por una operación Oij durante todo el periodo de procesamiento, los problemas de secuenciación de este tipo son denominados como Problemas de Secuenciación de Tareas con Multiprocesos (Multiprocessor Task Scheduling Problems).

Finalmente hay una función de costo fi(t), la cual mide el costo de terminar un trabajo Ji en un tiempo t. Una fecha limite di y un peso wi pueden ser usados para definir a fi. En general todos los datos pi, pij, ri, di, wi se asumen como variables enteras.

Las diferentes clases de problemas de secuenciación son clasificados en términos de tres diferentes campos α|β|γ, donde α específica el ambiente de las máquinas de producción, β

específica las características del trabajo y γ denota el criterio de optimización. Este criterio de clasificación fue introducido por Graham ( 1979) y se detalla en el siguiente punto.

2.2.1.2 Ambiente máquina (α).

El ambiente máquina esta caracterizado por una cadena α = α1α2 de dos parámetros. Los posibles valores de α1 son ø, P,Q, R, PMPM,QMPM,G,X, O, J, F. si α1 ∈ {ø, P,Q, R, PMPM,QMPM},donde ø denota el símbolo de vacio (luego, α = α2 si α1 = ø), entonces cada Ji consiste en una operación simple. Si α1 =ø cada trabajo debe ser procesado en una máquina dedicada especifica. Si α1 ∈ {P,Q,R}, entonces se tienen máquinas paralelas y cada trabajo puede ser procesado en cada una de las máquinas M1, . . .,Mm. Si α1 = P, entonces hay máquinas paralelas idénticas; así para el tiempo de procesamiento pij del trabajo Ji en Mj se tiene pij = pi para todas las máquinas Mj. Si α1 = Q, entonces se tienen máquinas paralelas uniformes, donde pij = p/sj en este caso sj es la velocidad de la máquina Mj. Finalmente, si α1 = R, entonces se tienen máquinas paralelas inconexas donde

pij = p/sj para un trabajo con velocidades dependientes sij de Mj. Si α1 = PMPM y α2 = QMPM,

entonces se tienen máquinas multipropósito con velocidades uniformes idénticas, respectivamente. Si α1 ∈ {G,X,O, J, F}, se tiene un modelo Multi-operacional, donde asociado con cada trabajo Ji

hay un conjunto de operaciones Oi1, . . .,Oi,ni. Las máquinas son dedicadas, y todos los μij son conjuntos de un solo elemento. Además hay relaciones de precedencia entre operaciones arbitrarias. Este modelo es llamado Taller general o en ingles (general shop). Si el tipo de ambiente máquina es el de un Taller general se denota α1 = G. Job shops, flow shops, open shops, y mixed shops son casos especiales del Taller general. Un Job shop que se denota por α1 = J, además en este tipo de ambiente máquina se tienen relaciones de precedencia especiales de la forma:

Oi1 → Oi2 → Oi3 → . . . → Oi,ni desde i = 1, . . . , n.

Por otro lado, se asume generalmente que μij ≠ μi,j+1 para j = 1, . . . , ni−1 . A un Job shop en el cual μij = μi,j+1 es posible, se le denomina como un Job shop con repetición de máquinas.

CAPÍTULO 2

57

Si el ambiente máquina resulta ser un Flow shop, este se denota por α1 = F. El flow shop es un caso especial de Job shop en el cual ni = m desde i = 1, . . . , n y μij = {Mj} para cada i = 1, . . . , n y j = 1, . . .,m. Por otro lado el Open shop se denota por α1 = O y tiene las mismas características del Flow shop, con la excepción de que no hay relaciones de precedencia entre operaciones. Un Mixed shop, esta denotado por α1 = X y es una combinación de características entre un Job shop y un Open shop. Por último El Permutation flow shop es un ambiente máquina en el cual los trabajos son procesados en el mismo orden en cada máquina, este tipo de ambiente máquina ha sido tratado de forma exitosa como se puede observar en el trabajo Ladhari y Haouari, (2005). La figura 1-9 muestra una secuencia factible para el Permutation flow shop. Si se tiene un problema de tipo Job shop se debe denotar β4 igual a ni ≤ 2. En este caso todos los trabajos tienen a lo más dos operaciones. Si α2 es igual a un número entero positivo 1, 2,. . ., entonces α2 denota el número de máquinas. Si α2 = k entonces k es arbitrario con un fijo número de máquinas. Si el número de máquinas es arbitrario se denota al conjunto α2 =ø.

Figura 2-9 Secuenciación factible para un Permutation flow shop (Brucker Peter. Scheduling Algorithms, 5ta

Edición 2006, ed Springer.)

2.2.1.3 Características de un trabajo (β)

Las características de un trabajo están especificadas por un conjunto β que contiene a lo más seis elementos β1, β2, β3, β4, β5 y β6. En seguida se especifica las características particulares de cada elemento de dicho conjunto.

β1 Indica si la interrupción (la división de trabajo) está permitida al momento de llevar a cabo la secuenciación de los trabajos. La interrupción de un trabajo u operación significa que el proceso puede ser interrumpido y se reanuda en un momento posterior incluso en otra máquina. Si la interrupción es permitida se denota a β1 = pmtn, de lo contrario β1 no aparece en β. β2 Describe las relaciones de precedencia entre trabajos. Estas relaciones de precedencia pueden ser representadas por un grafico G = (V,A) donde V = {1, . . . , n}corresponde a los trabajos y (i, k) ∈ A↔ Ji debe completarse antes de que Jk comience. En este caso se escribe Ji → Jk. Si G es un grafico β2 = prec. De no haber relaciones de precedencia entre los trabajos β2 no aparece en el conjunto β.

Por otra parte β3 define si hay o no fecha de liberación para los trabajos. Si β3 = ri, entonces la fechas de liberación pueden ser particulares para cada trabajo. Si ri = 0 para todos los trabajos, entonces β3 no debe aparecer en β.

CAPÍTULO 2

58

β4 especifica restricciones en el tiempo de procesamiento o en el número de operaciones. Si β4 es igual a pi = 1(pij = 1), entonces cada trabajo (operación) tiene un tiempo de procesamiento unitario. Esto se puede escribir de la siguiente forma pi =p(pij = p). Ocasionalmente el campo β4

puede contener características adicionales. El siguiente campo β5 detalla las características de la fecha límite de los trabajos. Si β5 = di,

entonces una fecha limite di es descrita para cada trabajo Ji. Por esto es que cada trabajo Ji debe terminarse a mas tardar en el tiempo di. En algunas aplicaciones de secuenciación, un conjunto de trabajos puede ser agrupado. Esta agrupación es un acumulado de trabajos, los cuales pueden ser procesados conjuntamente en una máquina. El tiempo de terminación de todos los trabajos está definido como el tiempo de procesamiento de todo el conjunto. Una agrupación de este tipo puede consistir desde un solo trabajo hasta n trabajos, adicionalmente existe un tiempo de preparación s para cada agrupación de trabajos. Se asume que estos tiempos de preparación para todas las agrupaciones son iguales y la secuencia es independiente. El objetivo en este tipo de problemas es encontrar una agrupación de trabajos, para después obtener una secuencia factible para ellos. Para los problemas de esta característica en particular, la longitud de la secuencia de la agrupación es igual a la suma del máximo tiempo de procesamiento de todos los trabajos de su conjunto. El elemento β6 se encarga de identificar si el problema a tratar posee las características especificadas anteriormente, de ser asi β6 = p-batch y esto indica un problema de agrupación de trabajos. De otra forma β6 no aparece en el conjunto β.

2.2.1.4 Criterio de optimización (γ). Para efectos de establecer una función de optimización se instaura un tiempo de terminación de un trabajo Ji por Ci y un costo asociado por fi(Ci). Hay esencialmente dos tipos de funciones de costo total

fmax(C) := max{fi(Ci)|i = 1, . . . , n} y

que por sus características se denominan como objetivo de cuello de botella y suma de objetivo respectivamente. El problema de programación es encontrar una secuencia factible la cual minimice el costo de la función total. Si la función fi no está especificada, se denota el conjunto γ = fmax . Sin embargo en la mayoría de los casos se consideran funciones especiales fi. Las funciones objetivo más comunes son la del tiempo de terminación del último trabajo procesado (Makespan) max {Ci|i =1, . . . , n}, tiempo total de flujo

, y la ponderación del flujo total de tiempo

, en estos casos

se escribe γ = Cmax, γ = y γ = respectivamente.

CAPÍTULO 2

59

Otras funciones objetivo dependen de fechas límite di, las cuales están asociadas con trabajos Ji. Se define para cada trabajo Ji: Li := Ci – di Demora (Lateness)

Ei := max{0, di − Ci} Prontitud (Earliness)

Ti := max{0, Ci − di} Tardanza (Tardiness)

Di := |Ci − di| Desviación Absoluta (Absolute deviation)

Si := Desviación Cuadrada (Squared deviation)

Ui :=

Penalización unitaria (Unit penalty)

2.2.2 Complejidad Computacional Los primeros trabajos en lo que a teoría de complejidad computacional como se menciona en Leung (2004) aparecen en la década de los setentas las investigaciones de Cook y el trabajo desarrollado por Rinnooy, en el cual clasifica los problemas de secuenciación de trabajos desde la perspectiva de la complejidad de computo que presenta solucionarlos son el punto de partida para estudiar dicha teoria. De acuerdo con los trabajos mencionados un problema de carácter computacional puede ser visto como una función h que procesa una entrada x en algún dominio dado a una salida h(x) en algún rango establecido. En el caso específico de la secuenciación de trabajos es de interés construir un algoritmo capaz de secuenciar los trabajos en cada una de las máquinas en un tiempo de cómputo factible. Esto para que calcule un h(x) para cada entrada x.

Para esto se define la longitud de entrada |x| como la longitud de alguna codificación de x. Aunado a esto se puede medir la eficiencia de un algoritmo por un límite superior T(n) sobre el número de pasos que el algoritmo necesita para procesar cada entrada x con |x| = n. En la mayoría de los casos puede ser difícil calcular una forma precisa de T. Por esta razón se remplaza la forma precisa de T por su forma de orden asintótico. De esta manera se expresa que T(n) ∈ O(g(n)), si hay constantes c >0 y enteras no negativas (n0) tal que T(n) ≤ cg(n) para todos los enteros n ≥ n0. La complejidad computacional está limitada por +4 , o de forma más simple . Clase P Se denomina a un problema con solución polinomial si existe un polinomio p tal que T (|x|) ∈ O(p(|x|)) para todas las entradas x del problema o por otra parte si hay una k tal que T(|x|) ∈

. Una importante clase de problemas de programación lineal y entera, los cuales poseen una cantidad fija en cuanto a número de variables se refiere, son denominados como problemas con solución polinomial, esto conforme a la investigación de Khachiyan y Lenstra. Por otro lado se le denomina un problema de decisión si el rango de salida es {sí o no}. A cada problema de secuenciación se puede asociar un problema de decisión, si se define un umbral k

CAPÍTULO 2

60

para la correspondiente función objetivo f. Este problema de decisión es: ¿Existe una secuenciación factible S tal que f(S) ≤ k?. La clase de todos los problemas de decisión que tienen solución polinomial es denotada por P. Clase NP Cuando un problema de secuenciación es formulado como un problema de decisión hay una importante asimetría entre las entradas y sus salidas que son “si” y las salidas que son “no”. Una respuesta “si” puede ser certificada por un pequeño monto de información: la secuenciación factible S con f(S) ≤ k. Dado este certificado, la respuesta “si” puede ser verificada en un tiempo polinomial. Este no es el caso para la respuesta de tipo “no”. En general, NP denota la clase de problemas de decisión donde cada entrada “si” tiene un certificado y, tal que |y| está limitado por un polinomio en |x|y hay un algoritmo de tiempo polinomial para verificar que y es una certificado valido de x. Todo problema de decisión que puede ser resuelto en un tiempo polinomial pertenece a NP, si se tiene un problema P y un algoritmo que calcule para cada entrada x una respuesta h(x) ∈ {si, no}en un número de pasos polinomial, entonces esta respuesta h(x) puede ser usada como un certificado. Este certificado puede ser verificado por el algoritmo. Este problema P es también NP lo cual implica que P ⊆NP. Uno de los mayores problemas abiertos en las matemáticas modernas como lo menciona Brucker (2007) es la discusión de que la clase P es igual a NP. Sin embargo existe una teoría desarrollada por Cook, Karp y Levin, la cual provee fuerte evidencia de que P ≠NP. A continuación se muestran los argumentos que presenta esta teoría con referencia a los problemas NP completo (complete) y NP duro (Hard). Lo principal para definir un problema NP completo es que se necesita una reducción. Para dos problemas de decisión P y Q se dice que P reduce a Q (denotado por P α Q) si existe una función de cálculo de tiempo polinomial g que transforme entradas para P en entradas para Q tal que x es una entrada “si” para P ↔ g(x) es una entrada “si” para Q.

Un problema de decisión Q se denomina NP completo si Q ∈ NP y para todos los demás problemas de decisión P ∈ NP, se tiene que P α Q. Por eso se dice que si cualquier problema Q de tipo NP completo puede ser resuelto en un tiempo polinomial, entonces todo problema NP puede ser resuelto en un tiempo polinomial y se tendría que P = NP. De ahí la importancia de los problemas NP completos en la teoría de la complejidad computacional. Por lo tanto un problema de optimización se denomina NP duro (Hard) si su correspondiente problema de decisión es NP completo.

CAPÍTULO 2

61

2.2.3 Problemas de programación en máquinas paralelas. En este punto se presentan algunos problemas con características de secuenciación de trabajos en máquinas paralelas. Estos problemas están ramificados en dos tipos, en el primer caso se trata con máquinas idénticas y en el segundo con máquinas uniformes. Para poder estudiar las particularidades de cada uno de estos casos se toman en cuenta las investigaciones de Brucker & Kravchenko ( 2004) y Idem(2005), en los puntos subsecuentes se retoman las definiciones de estos trabajos para el analisis y desarrollo de las ramificaciones que se desprenden de cada uno de los tipo de ambiente máquina que se tienen. 2.2.3.1 Máquinas Idénticas En el primer tipo de problema (P | pmtn | Cmax ) de esta vertiente se consideran n trabajos Ji(i = 1, . . . , n) con tiempos de procesamiento pi (i = 1, . . . , n) los cuales, tienen que ser procesados en m máquinas idénticas paralelas M1, . . .,Mm. Este tipo de problema puede ser resuelto en tiempo polinomial. De esta forma se tiene un problema con las siguientes características. El límite inferior para este problema está dado por:

Adicionalmente una secuencia puede ser construida en un tiempo O(n) si se conoce este límite, para esto se llena la capacidad de las máquinas sucesivamente secuenciando los trabajos en cualquier orden y dividiendo en dos los trabajos entre el límite de tiempo conocido. Después la segunda parte de los trabajos es secuenciada en la siguiente máquina desde el tiempo cero. En el segundo tipo de problema (P | pmtn; ri | Lmax ) la complejidad aumenta ya que presenta las siguientes características: asociado con cada trabajo Ji hay un tiempo de liberación ri y una fecha límite di con ri ≤ di. Para esto primero se tiene que encontrar una secuencia preparatoria en m máquinas idénticas tal que la máxima demora

sea mínima. Aunado a esto se debe de considerar el problema de decisión que implica tratar dicho problema: Dado algún limite de valor L debe existir una secuencia tal que:

Adicionalmente se desea encontrar una secuencia, si es que esta existe. Si y solo si

Todos los trabajos i deben terminar antes de las fechas límite modificadas y no pueden

empezar antes de las fechas de liberación r. Aunado a esto cada trabajo Ji debe ser procesado en

un intervalo asociado con Ji. A estos intervalos se les conoce como tiempo de ventana. El

problema general es encontrar una secuencia preparatoria para trabajos Ji(i = 1, . . . , n) en m

máquinas idénticas tal que todos los trabajos Ji son procesados en su tiempo de ventana [ri, di]. Lo anterior puede ser reducido a un problema de flujo máximo en una red estructurada de la siguiente forma:

CAPÍTULO 2

62

Sea t1 < t2 < . . . < tr una secuencia ordenada de todos los diferentes valores de ri y di. Para esto se considera los intervalos de longitud .

Se asocia un vértice con un trabajo Ji y un vértice para cada intervalo IK. Además se asocian dos vértices s y t. Entre estos vértices, hay arcos y capacidades para estos arcos, los cuales son definidos de la siguiente manera: De s se tiene un arco para cada vértice de Ji con capacidad pi y para cada vértice de IK se tiene un arco para t con capacidad mTK. Existe una arco de Ji a IK ↔ Ji puede ser procesado en IK, y ↔ ri ≤ tK y tK+1 ≤ di, conjuntamente la capacidad de este arco es TK. A continuación en la figura 2.10 se muestra la red construida con esta definición.

Figura 2.10 Red para el problema P | pmtn; ri | Lmax, (Brucker & Kravchenko ( 2004).

Por otro lado no es complicado probar que existe una secuencia respecto a todos los tiempos de ventana si y solo si el flujo máximo en N tiene el valor de

. Si este es el caso, el flujo xiK en

el arco (Ji, IK) corresponde con el periodo de tiempo en el cual el trabajo Ji es procesado en el intervalo de tiempo IK y se tiene que:

Y

entonces cada trabajo está completamente procesado y el monto total por tiempo de procesamiento en IK es de a lo mas mTK, la cual es la capacidad de las m máquinas. Además,

CAPÍTULO 2

63

Si existe un flujo máximo que satisfaga las Ecuaciones (1), (2) y (3), una solución factible para el problema de secuenciación con tiempo de ventana es construida por una secuenciación parcial de los trabajos JiK con tiempos de procesamiento xiK > 0 en los intervalos IK en m máquinas idénticas paralelas. Por cada K, hay esencialmente un problema Tipo 1, el cual tiene una solución con Cmax ≤ TK debido a las ecuaciones (2) y (3).

Debido a que la red N tiene a lo más O(n) vértices, el problema de flujo máximo puede ser resuelto en un tiempo . Además la secuencia respecto al tiempo de ventana puede ser construida en un tiempo . Es por esto que el problema del tiempo de ventana puede ser resuelto en pasos. Para resolver un problema de Tipo 2 en su totalidad, se aplica búsqueda binaria en diferentes

valores de L. Se asume que lo que implica que –

. Se busca un algoritmo el cual aproxime el valor de la solución con error absoluto ε,

en a lo mas

pasos. Por otro lado es conveniente asumir

que los trabajos están acomodados de tal manera que . 2.2.3.2 Máquinas Uniformes. En este punto se consideran problemas en los cuales n trabajos Ji(i = 1, . . . , n) deben ser procesados en m máquinas paralelas uniformes Mj(j = 1, . . .,m). Las máquinas tienen diferentes velocidades sj(j = 1, . . .,m). Cada trabajo Ji tiene un Tiempo de procesamiento pi(i = 1, . . . , n). La

ejecución del trabajo Ji en la máquina Mj requiere

unidades de tiempo. Si se tiene que sj = 1

desde j = 1, . . .,m, se asume m máquinas idénticas paralelas. Todos los problemas con máquinas idénticas paralelas son problemas de tipo NP duro, aunado a esto, si se remplazan las máquinas por máquinas uniformes también es considerado como un problema de tipo NP duro. A continuación se plantea un Tercer tipo de problema en máquinas paralelas (Q | pmtn | Cmax ) ,en el cual, un límite w debe ser establecido para el valor de la función objetivo del problema que se describe. Sea Pi = p1 + . . . + pi y Sj = s1 + . . . + sj , para i = 1, . . . , n y j = 1, . . .,m. Por otro lado se asume que n ≥ m. Si n < m, se tiene que considerar n máquinas más veloces. La condición necesaria para procesar todos los trabajos en el intervalo [0, T] es que Pn = p1 + . . . + pn ≤ s1T + . .

. + smT = SmT o Pn/Sm ≤ T. Similarmente se debe tener Pj /Sj ≤ T para j = 1, . . .,m−1por que Pj /Sj es un límite inferior en la longitud de una secuencia para los trabajos J1, . . . , Jj. Este

es un límite inferior para los valores de Cmax. Después se construye una secuencia la cual considere este límite para poder dar una solución a al problema. El algoritmo utilizado para darle solución es llamado el algoritmo de nivel (level algorithm). En síntesis este algoritmo funciona de la siguiente forma; se construye una secuencia parcial hasta el tiempo t, en la cual, el nivel pi(t) del trabajo i en el tiempo t es la porción de pi no

CAPÍTULO 2

64

procesada antes de t. Para este tiempo t el algoritmo de nivel llama a un procedimiento que asigna los trabajos a cada una de las máquinas. Las máquinas están corriendo con su asignación hasta que en algún momento s > t. Una nueva asignación queda ejecutada en el tiempo s, y el proceso se repite. En el Cuarto tipo de problema (Q | pmtn | Lmax) que se estudia, se trata de encontrar una secuencia factible, con la particularidad de que cada trabajo i procesado en máquinas uniformes paralelas depende de un tiempo de ventana [ri, di], que a su vez está definido por una fecha de liberación ri y una fecha limite di del trabajo i. En el primer paso para resolver este problema, se debe encontrar una secuencia factible respecto a los tiempos de ventana [ri, di]. En un segundo paso se aplica búsqueda binaria para encontrarle solución a la secuencia preparatoria de las máquinas. Después se debe encontrar una secuencia factible para todos los trabajos i y esto se resuelve al reducirlo a un problema de flujo de red que se describe a continuación. Sea t1 < t2 < . .

. < tr una secuencia ordenada de todos los diferentes valores de ri y di. Para esto se considera los intervalos de longitud . Después se expande la red mostrada en la figura 2-11(a), a partir de la siguiente definición: Sea IK un nodo de intervalo arbitrario como en la figura 2.10 y denotado por el conjunto Ji1, Ji2, . . . , Jis de nodos predecesores al nodo IK. Entonces se remplaza la subred definida por IK, Ji1, Ji2, . . . , Jis , la cual se muestra en la figura 2.11(a) por la red expandida mostrada en la figura 2.11(b).

(a)

(b)

Figura 2.11 Red expandida, (Brucker & Kravchenko ( 2004))

CAPÍTULO 2

65

Para poder construir esta red expandida se define sm+1 = 0, además se añaden vértices a IK, Ji1, Ji2, .

. . , Jis, los cuales son (K, 1), (K, 2),. . . , (K,m). Por otro lado para j = 1, . . .,m, hay un arco desde (K, j) a IK con capacidad j(sj − sj+1)TK y para todo ν = 1, . . . , s y j = 1, . . .,m hay un arco desde Jiν

a (K, j) con capacidad (sj − sj+1)TK. De esta forma para cada IK se tiene una expansión y se mantiene para cada arco de s a Ji su capacidad pi. Por otro lado los arcos de IK a t tienen una capacidad SmTK. A continuación se presenta un teorema exspuesto en la investigación Brucker & Kravchenko ( 2005) y que se retoma en esta investigación, para demostrar, que el problema (Q |

pmtn | Lmax) puede ser resuelto a través de flujo máximo de la red expandida en la figura 2-11(b). Teorema: La siguientes propiedades son equivalentes:

(a) Existe una secuencia factible. (b) En la red expandida existe un flujo de s a t con valor.

Prueba: (b) ⇒ (a): considere un flujo con valor en la red expandida y se denota por el

flujo total que va desde Ji hasta IK. Entonces

, esto es prueba suficiente

para demostrar que para cada subconjunto A ⊆ {1, . . . , n}se tiene :

Lo anterior significa que los tiempos de procesamiento x1K, . . . , xnK pueden ser secuenciados en IK para K = 2, . . . , r. Si se considera en la red expandida la sub red inducida por A y su correspondiente flujo parcial. La porción de este flujo parcial el cual pasa a través de (K, j) está limitada por:

min{j(sj − sj+1)TK, |A|(sj − sj+1)TK} = TK(sj − sj+1)min{j, |A|}

Entonces se tiene que:

La igualdad anterior puede ser vista de la siguiente forma. Si |A| > m se tiene que:

De otra manera:

CAPÍTULO 2

66

= S|A| = h(A) (b) ⇒ (a): Asume que existe una secuencia factible. Para i = 1, . . . , n y K = 2, . . . , r sea xiK el “monto de trabajo” a ser procesado a partir de un trabajo i en un intervalo IK de una secuencia factible. Entonces se tiene que para toda K = 2, . . . , r y los conjuntos arbitrarios A ⊆ {1, . . . , n}, la siguiente inecuación se cumple:

Además, para i = 1, . . . , n se tiene que

, debido a esto se demuestra que es posible

enviar xiK unidades de flujo de Ji a IK (i =1, . . . , n; K = 2, . . . , r) en la red expandida. Una condición para la existencia de tales flujos es que para un subconjunto arbitrario A ⊆ {1, . . . , n}y K = 2, . .

. , r el valor este limitado por el monto del corte mínimo en la red parcial con fuente Ji(i

∈ A) y con terminal en IK , con lo cual dicho valor esta dado por:

Si se usa la parte derecha de la ecuación (5) y la ecuación número (6) se obtiene la siguiente expresión

esta última expresión es la desigualdad que se desea obtener. Debido a que el flujo máximo de la red expandida puede ser calculado en pasos, una secuencia factible puede construirse en el mismo número de pasos para resolver el problema (Q |

pmtn; ri | Lmax). Labetoulle, Lawler, Lenstra, y Rinnooy Kan (1984) desarrollaron un algoritmo capaz de resolver este problema en O(n log n + mn) pasos.

CAPÍTULO 2

67

2.2.4 Algoritmos de programación. Un algoritmo de acuerdo a la definición de Hiller y Liberman (2002), puede ser visto como un procedimiento de solución sistematico que repite una serie de pasos fija, llamada iteración, hasta que se obtiene el resultrado deseado. Esta estructura de un algoritmo es detallada en la figura 2.12, en la que se presentan los pasos para poder resolver un problema de manera óptima.

Figura 2.12: Estructura de un Algoritmo (Hiller y Liberman (2002))

En la figura 2.12 se mencionan los tres pasos necesarios para que cualquier algoritmo funcione de forma correcta. En el primer paso que es la inicialización, se debe de formular una manera de encontrar una solución que sea factible y que no requiera de mucho esfuerzo para hallarla. En el segundo paso se realiza la prueba de optimalidad en la cual si el resultado de la iteración resulta ser el optimio el algoritmo termina , de no ser asi continua iterando. Por ultimo el proceso de iteración depende de que tan grande sea el problema y de que tan rapido la estructura del algoritmo permita encontrar la solución óptima. 2.2.4.1 Algoritmos Heurísticos. De acuerdo con Salazar (2001) se le llama algoritmo heurístico a cualquier algoritmo que con poco esfuerzo computacional proporcione una solución factible cuyo valor objetivo normalmente esté próximo al valor objetivo óptimo del problema original. Las soluciones obtenidas mediante dichos algoritmos se denominan soluciones heurísticas. Dado un valor , se llama algoritmo -aproximado a cualquier heurístico que produzca una solución cuyo costo de una solución óptima, verifique . Un algoritmo se dice de aproximación totalmente polinomial si para todo valor existe un algoritmo -aproximado cuya complejidad esta acotada por un polinomio en el tamaño de los datos de la instancia y en . Kelly y Walker (1959) hacen una distinción de dos formas básicas para poder generar una secuencia factible. Las formas básicas de acuerdo a esta investigación son denominadas en serie y en paralelo. En ambos procedimientos, una vez que una actividad o trabajo ha sido secuenciada nunca se vuelve a secuenciar. Para el caso de la secuencia en serie, esta comienza numerando los vértices de forma que para cada arco su vértice inicial tenga un número menor que su vértice final. Dicha forma de

CAPÍTULO 2

68

numeración tiene la propiedad de que si se secuencian dichas actividades en el orden correcto, dependiendo de su número, entonces ninguna actividad aparecerá antes que ninguna de sus predecesoras. Se puede construir una secuencia factible considerando los trabajos en dicho orden y secuenciando cada uno de ellos tan pronto como las relaciones de precedencia y las restricciones lo permitan. Cada algoritmo que realiza una secuencia en serie puede tener sus propias reglas y prioridades para secuenciar los trabajos. En la secuencia en paralelo se construye una secuencia factible programando hacia adelante en el tiempo. En cada momento de la programación de las tareas o trabajos se determina el conjunto que puede ser secuenciado de acuerdo con las restricciones de precedencia y de recursos. Este conjunto se ordena mediante una regla de prioridad y los trabajos se secuencian en ese orden, mientras no se rebase la capacidad de los recursos, y así sucesivamente. Cada regla de prioridad puede ser secuenciada por un algoritmo heurístico distinto. Por otra parte si las actividades reciben la prioridad independientemente de la secuencia ya existente, el algoritmo se denomina estático, en caso contrario se denomina dinámico. Las reglas que están basadas en las características de los trabajos en su gran mayoría son estáticas. Algunas otras como las que están basadas en medidas sobre la ruta crítica, pueden ser estáticas si estas medidas se efectúan una sola vez y son mantenidas durante la construcción de la secuencia, o dinámicas, si se actualizan teniendo en cuanta la secuencia parcial ya obtenida. Reglas Heurísticas de prioridad. En los años que se lleva implementado y desarrollando algoritmos heurísticos, se han propuesto una gran cantidad de reglas para la construcción de soluciones heurísticas de los problemas de secuenciación. Al gunas de ellas se diseñaron para los problemas de secuenciación en máquinas, en particular para el problema de Job shop. Estas reglas han sido descritas, clasificadas y comparadas en investigaciones como las de Davis y Patterson (1975), Cooper (1976) y Lawrence (1984). En un estudio llevado a cabo por Alvarez y Tamrit (1989) acerca de la eficiencia relativa de los principales algoritmos conocidos, se obtiene una clasificación de cuatro reglas que pueden considerarse las más eficientes y las cuales se describen a continuación.

1. MTS (Most Total Succesors). Esta regla heurística elige primero aquella actividad o trabajo con mayor número de sucesores, inmediatos o no, ya que el retaso de dicha actividad o trabajo retrasa a todos los demás.

2. GRPW (Greatest Rank Positional Weight). Esta regla selecciona los trabajos o actividades de acuerdo a su peso posicional, el cual es obtenido sumando a la duración del trabajo la duración de los trabajos sucesores:

CAPÍTULO 2

69

3. LTS ( Latest Start Time). Esta regla secuencia en primer lugar aquel trabajo que tiene un menor tiempo máximo de inicio (LST). El LST da una medida de la urgencia de empezar el trabajo ya que si este se secuencia en un tiempo posterior a su LST se producirá un retraso en el tiempo total de la ejecución de todos los trabajos:

4. LFT (Late Finish Time) Es similar a la anterior, pero tiene en cuanta la duración del trabajo:

2.2.4.2 Técnicas de Búsqueda Local (Local Search LS). En este punto se estudia las técnicas o algoritmos de búsqueda local, los cuales, son utilizados para resolver problemas de optimización discretos de acuerdo con Leung ( 2004). Un problema de optimización discreta desde la perspectiva de Salazar (2001), puede ser descrito de la siguiente forma: Dado un conjunto finito y una función , se tiene que encontrar una solución con:

En Brucker (2007) se define la búsqueda local como un procedimiento iterativo, el cual se mueve de una solución contenida en S a otras soluciones, tantas veces como sea necesario. Lo anterior a través, de una búsqueda sistemática en el conjunto S. Estos posibles movimientos de una solución s a la siguiente solución pueden ser restringidos. Para describir esta restricción se debe introducir una estructura de entorno (neighborhood structure) en . Para cada describe el subconjunto de soluciones que pueden ser alcanzadas en un paso, moviéndose desde . El conjunto es denominado como el entorno de . Una estructura de entorno puede ser representada mediante un grafico dirigido donde y

es denominado como el grafico de entorno de la estructura de entornos. Usualmente no es posible estructurar un grafico de entorno debido a que tiene un tamaño exponencial de acuerdo a Brucker (2007). Para poder tratar con esta dificultad, un conjunto con la siguiente modificación es implementado. Dado una solución , el entorno de ahora puede ser definido por:

.

Usando la definición anterior, un método de búsqueda local es descrito de la siguiente forma por Brucker (2007). En cada iteración se comienza con una solución y se selecciona (o

CAPÍTULO 2

70

en la modificación , lo cual implica que en este caso ). Basado en los valores y , se selecciona una solución inicial para la siguiente iteración. Una forma de selección simple es tomar la solución con el valor más pequeño de la función de costo. Este tipo de selección deriva en el método iterativo de mejora que se puede formular de la siguiente manera: El algoritmo de arriba terminara con alguna solución . En general, esta es únicamente un mínimo local con respecto al entorno y puede diferir considerablemente del mínimo global, de acuerdo a la opinión de Brucker (2007). Existen algunos algoritmos que evitan quedarse estancados en un mínimo local extendiendo la búsqueda de soluciones y variando los mecanismos de generación de soluciones vecinas. El algoritmo de recocido simulado (SA) propuesto por Kirkpatrick, Gelatt y Vecchi (1983) y el algoritmo de búsqueda de entorno variable (VNS) desarrollado en la investigación de Mladenovíc (1995), son algunos de los métodos que se han desarrollado para evitar el problema del estancamiento en mínimos locales de acuerdo con Leung ( 2004). En los siguientes puntos se desarrolla de manera detallada los algoritmos mencionados con anterioridad. 2.2.4.3 Algoritmo de Recocido Simulado (Simulated Annealing) SA. El algoritmo de recocido simulado basa su funcionamiento en la analogía del proceso metalúrgico, en el cual, para reblandecer un sólido, se le lleva a una temperatura elevada y luego se enfría lentamente hasta que las partículas por si solas se van colocando en el “estado fundamental del sólido”. Este proceso pasa por diferentes fases cada vez a menores temperaturas y para cada fase el sólido puede alcanzar el equilibrio térmico. La implementación del SA para la optimización combinatoria se presenta por primera vez en el trabajo de Kirkpatrick, Gelatt y Vecchi (1983). Esta investigación se retoma para desarrollar y analizar dicho algoritmo en el presente punto. Lo que pretende el SA es establecer una conexión entre este tipo de proceso termodinámico y la búsqueda de un mínimo global, la cual se basa en aceptar en forma limitada transiciones que no mejoren la función de costo usando un mecanismo no determinista. El núcleo del recocido simulado lo constituye el algoritmo de Metropolis propuesto por N. Metropolis en 1953. Lo que hace el algoritmo de Metropolis es generar un vecino, calcularle su energía (E, función de costo en problemas de optimización) y aceptar ese vecino si tiene menor energía o aceptarlo con mayor energía pero con cierta probabilidad que depende de la temperatura (T). A continuación se muestra el funcionamiento de este algoritmo. Donde denota la temperatura y la constante de Boltzmann. . .

CAPÍTULO 2

71

El equilibrio térmico está caracterizado por la distribución de Boltzmann, la cual da la probabilidad de que el sólido este en un estado con energía a temperatura y esta dada por:

donde es la variable estocástica denotando el estado actual del sólido, y es la función de partición definida como:

El algoritmo de recocido simulado se puede ver como una iteración de algoritmos de Metropolis. Si se baja la temperatura suficientemente lento se puede alcanzar el equilibrio térmico en cada temperatura. Esto se hace mediante la generación de varias transiciones en cada temperatura. Por otro lado la probabilidad de aceptación para el SA se expresa de la siguiente forma:

De acuerdo con el estudio desarrollado por Kirkpatrick, Gelatt y Vecchi (1983), se puede demostrar que bajando suficientemente lento el parámetro asociado a la temperatura y generando suficientes transiciones en cada temperatura se puede alcanzar la configuración óptima. La estructura del SA en pseudocodigo y exspuesta en Brucker(2007), se desarrolla a continuación:

donde denota el parámetro de control. Por otro lado una transición consiste en aplicación del mecanismo de generación, y aplicación del mecanismo de aceptación. Inicialmente valores grandes de aceptan cualquier estado, y cuando tiende a cero, se dejan de aceptar estados. La velocidad de convergencia del algoritmo está determinada por y .

CAPÍTULO 2

72

A partir del trabajo de Laarhoven y Aarts (1987), se obtiene la siguiente definición: Dada una instancia de un problema combinatorio y una estructura de vecinos adecuada, después de un número de transiciones suficientemente largo para un valor fijo de , aplicando el criterio de aceptación, el algoritmo de recocido simulado encuentra una solución con probabilidad igual a:

donde es una variable estocástica denotando la solución actual y

denota una constante de normalización. Si se tiene un problema de optimización combinatoria, una estructura de vecindad adecuada y una distribución estacionaria equivalente a la distribución de Boltzmann, entonces:

donde denota el conjunto de soluciones óptimas globales, y es la función

característica definida como:

Este resultado granatiza una convergenzia asintótica hacia el conjunto de soluciones óptimas del algoritmo de recocido simulado bajo la condición de que la distribución estacionaria para una cadena de Markov se obtenga para cada valor de . Para poder comprender este concepto se profundiza en la definicón de una cadena de Markov, lo anterior a partir de conceptos desarrollados en Hiller y Liberman (2002). Una cadena de Markov es una secuencia de eventos, donde la probabilidad del resultado de un evento depende sólo de los resultados del evento anterior. Por lo que si es una variable estocástica que denota el resultado del -ésimo evento. Entonces la transición de probabilidad en el -ésimo evento para cada par de resultados se define como:

A una matriz cuyos elementos estan dados por la fórmula de arriba se le denomina la matriz de transición. Por otro lado se denota a como la probabilidad del resultado en el -ésimo evento, osea: .

CAPÍTULO 2

73

Entonces : se define como:

Algunas de las propiedades de las cadenas de Markov son las siguientes:

Finita si se tiene un conjuto finito de resultados.

No homogenea si las probabilidades de transición dependen del número del evento .

Homogenea si las probabilidades de transición son independientes del nuemro del evento.

Irreducible si para cada par de soluciones existe una probabilidad positiva de alcanzar a partir de en un número finito de eventos.

En el algoritmo de recocido simulado, un evento coorresponde a una transición y los resultados posibles corresponden al conjunto de soluciones posibles. Las probabilidades de transición del SA estan definidas como:

donde: denota la probabilidad de generar una solución a partir de una solución .

Una distribución estacionaria de una cadena de Markov finita con matriz de transición para el SA se define como un vector cuyo -ésimo componente está dado por:

El SA requiere de un mecanismo de enfriamiento que especifique:

Para cada secuencia finita de valores del parametro de control: (1) un valor inicial , (2), una función de decremento, y (3) un valor final (condición de paro).

Un número finito de transiciones para cada valor del parámetro de control (longitud finita de cada cadena de Markov).

Mecanismo de enfriamiento propuesto por Kirkpatrick, Gelatt y Vecchi (1983):

Valor inicial del parámetro de control: empezar con un entero positivo pequeño e irlo multiplicando por un factor menor a 1 hasta que las transiciones generadas sean casi todas aceptadas.

Decremento del parametro de control: , donde es una constante cercana a 1 (0.8-0.99).

CAPÍTULO 2

74

Valor final del parámetro de control: terminar cuando la solución obtenida permanece igual en un número determinado de cadenas consecutivas.

Longitud de las cadenas de Markov: hacer una longitud fija (de otra forma cuando ).

Para aplicar el algoritmo SA de manera adecuada de acuerdo con Laarhoven y Aarts (1987) se requiere especificar tres componenetes:

1. La representación del problema :

Representar un espacio de solución.

Expresar la función de costo que represente adecuadamente el costo de las soluciones.

2. El mecanismo de transición:

Generar una nueva solución(simétrica).

Calcular diferencia de costo (se puede calcular tomando en cuenta las diferencias con la solución anterior.

Tomar decisión de aceptación.

3. El mecanismo de enfriamiento:

Valor inicial de .

Función de decremento.

Criterio de paro.

Longitud de las cadenas. Se han propuesto algunas variaciones al algoritmo de recocido simulado. Una de las variaciones mas conocidas es la aceptación por umbral (Treshold accepting), la cual fue propuesta idependientemente por Dueck y Scheuer (1990) y por Moscato y Fontanari (1990). De acuerdo con Dueck y Scheuer (1990), la aceptación por umbral propone aceptar un movimiento siempre y cuando rebase un cierto umbral ( ) determínistico y decreciente respecto a la iteración . La probabilidad de aceptación para esta modificación del SA se expresa de la siguiente manera:

aunque este metodo es mas rapido, se peierden las propiedades de convergencia hacia el mínimo global, de acuerdo con la opinion de Brucker(2007).

CAPÍTULO 2

75

El recocido Simulado es apmliamente utilizado para resolver problemas de optimización combinatoria en distintas vertientes, debido a su facil aplicación y adecuación a este tipo de problemas como se muestra en la invetigaciónes de Eglese (1990) y Koulamas (1994); en esta ultima se presenta al SA como una alternativa para resolver de forma factible el problema del ajente viajero. Tambien ha sido implementado de forma exitosa en la resolución de problemas de secuenciación de máquinas paralelas con tiempos de secuencia dependientes como se puede observar en los trabajos de Ventura (2000), Diaz Santillan (2001). Este algoritmo posee una gran capcidad de aplicación en diversas áreas del conocimiento un ejemplo de esto se puede observar en la investigación de Trevor (2003), en la cual se propone como solución para el ánalisis de invetigaciones de mercado. Lo anterior demuestra que recocido simulado es una técnica eficiente para atacar y resolver una gran diversidad de problemas de gran tamaño que representan una complejidad computo. 2.2.4.4 Algorimo de Busqueda de Entorno Variable (Variable Neighbourhood Search, VNS).

El algoritmo de Búsqueda de Entorno Variable (Variable Neighbourhood Search, VNS) es una metaheurística propuesta en los trabajos de Mladenovíc (1995) y Hansen, Mladenovíc (1997), la cual, está basada en un principio simple: cambiar de manera sistemática la estructura de entornos dentro de la búsqueda. Su desarrollo ha sido rápido, ya que se han realizado muchas modificaciones, esto principalmente para permitir la solución de problemas de gran tamaño. En algunas modificaciones que se han hecho de este algoritmo, se trata de mantener la simplicidad de su estructuran básica como se puede observar en la investigación realizada por Mladenovíc, Hansen y Pérez Brito (2001). Para desarrollar el estudio y análisis del VNS se retoma las investigaciones de Mladenovíc (1995) y Hansen, Mladenovíc (1997). A partir de dichos trabajos se conoce que el VNS está basado en tres hechos que se mencionan a continuación:

1. Un mínimo local con una estructura de entornos no lo es necesariamente con otra

2. Un mínimo global es mínimo local con todas las posibles estructuras de entornos

3. Para muchos problemas los mínimos locales con la misma o distinta estructura de entornos están relativamente cerca

además existen diferentes variaciones de VNS, las cuales se estudian a continuación. En el VNS descendente (greedy) o clásico la búsqueda consiste en reemplazar iterativamente la solución actual por el resultado de la búsqueda local, mientras se produzca una mejora. Si se lleva a cabo un cambio de estructura de entornos de forma determinística cada vez que se llega a un mínimo local, se obtiene la búsqueda de entorno variable de descendente o (Variable Neighbourhood Descent, VND). Los pasos del VND extraídos de Bringer, Hansen y Otros (2000) se muestran a continuación:

CAPÍTULO 2

76

La solución final proporcionada por el algoritmo es un mínimo local con respecto a todas las estructuras de entornos, y por lo tanto la probabilidad de alcanzar un mínimo global es mayor que si se usa una sola estructura. A demás del orden secuencial de las estructuras de entornos en El VND es posible desarrollar una estrategia anidada. La búsqueda de entorno variable reducida (Reduced Variable Neighbourhood Search RVNS) se obtiene si se seleccionan soluciones aleatorias , sin aplicarles a continuación un descenso. Los pasos para construir el RVNS son los siguientes:

La estructura general del RVNS se obtuvo de la investigación presentada por Mladenovic, Petrovic, Kovacevic-Vujcic, y Cangallovic (2004), y en la cual se demuestra que el algoritmo es útil para instancias muy grandes de en las que la búsqueda local es muy costosa. Por otro lado como condición de parada se usa generalmente el máximo número de iteraciones entre dos mejoras. La búsqueda de entorno variable básica (Basic Variable Neihgbourhood Search, BVNS) la cual se desarrolla por Hansen, Mladenovíc (1997), combina cambios determinísticos y aleatorios de estructura de entornos. Los pasos del BVNS se dan a continuación.

CAPÍTULO 2

77

La condición de parada puede ser, por ejemplo, el máximo tiempo de CPU permitido, el máximo número de iteraciones, o el máximo número de iteraciones entre dos mejoras. Frecuentemente los entornos sucesivos están anidados. La solución se genera al azar en el paso 2(a), esto para evitar caer en un estado cíclico que puede ocurrir si se utiliza cualquier regla determínistica. La búsqueda de entorno variable general (General Variable Neighbourhood Search, GVNS), se obtiene al cambiar el paso 2(b) del BVNS por el mismo paso del VND. Los pasos requeridos para ejecutar un GNVS se muestran a continuación.

Para todos los casos de VNS, se pueden estudiar variantes en cada uno de los pasos para mejorara las a características del algoritmo, dependiendo del problema que se quiera resolver. La búsqueda de entorno variable, es un algoritmo heurístico que permite tratar con problemas de optimización combinatoria, para darles una solución factible en tiempos relativamente cortos lo anterior de acuerdo a Bringer, Hansen, Mladenovic y Tillard (2000). 2.2.5 Algoritmo de Optimización Branch and Bound (Ramificación y Acotamiento). Hasta el momento únicamente se han estudiado algoritmos heurísticos, los cuales, permiten la resolución de problemas de optimización combinatoria de gran tamaño. Estos algoritmos son de gran utilidad si se desea resolver un problema de complejidad NP. Sin embargo existen problemas cuyas características de complejidad son de tipo P, lo que significa que estos pueden ser resueltos de forma óptima, en un tiempo de cómputo factible. A continuación se estudia el algoritmo de ramificación y acotamiento (Branch and Bound) que puede resolver este tipo de problemas con complejidad P de forma óptima. Es factible utilizar el algoritmo de ramificación y acotamiento para resolver un problema grande de optimización, pero el tiempo de cómputo que requiere es exponencial.

CAPÍTULO 2

78

Desde mediados de la década de los sesentas el algoritmo de ramificación y acotamiento ha sido implementado con éxito en problemas de secuenciación de trabajos, principalmente en problemas de tipo Flow Shop. Como prueba de lo anterior se tienen los trabajos desarrollados por Lomnicki (1965) e Ignall y Schrage (1965). Más recientemente se observan algunos trabajos como el Ladhari y Haouari (2005) donde se retoma este algoritmo para la optimización de una secuenciación de trabajos en un problema de Permutation Flow Shop. En síntesis de acuerdo a Salazar (2001) el algoritmo de ramificación y acotamiento comienza con una relajación del problema (no considerar restricciones de integralidad) y construye un árbol con soluciones enteras particionado el conjunto de soluciones factibles de modo que se descartan soluciones fraccionarias. Sin embargo, este solo hecho de descomponer nos puede llevar a un problema que no sea manejable por lo que se debe acotar el árbol de manera inteligente. Para poder explicar el funcionamiento de este algoritmo se recurre al trabajo de Brucker (2007) en el cual se asume que se tiene un problema de optimización discreta , el cual a su vez es descrito como un problema de minimización. Por otra parte también se consideran que existen subproblemas de , que están definidos por un subconjuntos de que pertenecen al conjunto de soluciones factibles de . Es conveniente identificar y sus subproblemas con el correspondiente subconjunto . Hay tres cosas que son necesarias para construir este algoritmo y que se mencionan a continuación:

1. Ramificación: es remplazado por pequeños problemas , de tal forma que

. Este proceso es denominado como ramificación (branching). La ramificación

es un proceso recursivo, en el cual es la base de otra ramificación. Todo el proceso es representado por un árbol. es la raíz del árbol, son los ramificaciones de . Los problemas de optimización discreta creados por el proceso de ramificación y acotamiento son denominados como subproblemas.

2. Límite inferior: Un algoritmo está disponible para calcular un límite inferior para los valores de todas las soluciones factibles de un subproblema.

3. Límite superior: Se calcula un límite superior del valor objetivo de . El valor objetivo de cualquier solución factible, será el que proveerá tal límite superior. Si el límite inferior de un subproblema es mayor o igual a , entonces este subproblema no puede proporcionar una mejor solución para . Por lo anterior no se necesita continuar ramificando desde el correspondiente nodo del árbol. Para detener el proceso de ramificación en los muchos nodos del árbol, el limite debe ser lo tan pequeño como sea posible. Además, al principio del algoritmo de ramificación y acotamiento se aplica algún heurístico para encontrar una buena solución con un valor pequeño de . Después de ramificar varias veces se de considerar una situación en la cual, el problema tenga solo una solución factible. Entonces el límite inferior del subproblema es igual al valor objetivo de esa solución y se remplaza por .

CAPÍTULO 2

79

A continuación se presenta los pasos del algoritmo de ramificación y acotamiento tomados de

Brucker (2007).

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

11)

12) Sino añade una rama(i) a Lista

Fin

2.2.6 Algoritmos para problemas con máquinas paralelas con tiempos de secuencia dependientes. En este punto se estudia dos trabajos que implementaron tanto el algoritmo de recocido simulado (SA) como el algoritmo de búsqueda de entorno variable (VNS) respectivamente, para dar solución a problemas de secuenciación en máquinas paralelas con tiempos de secuencia dependientes. A continuación se presentan una síntesis de estos dos trabajos y sus respectivos procedimientos de solución. Solución del problema de secuenciación de máquinas paralelas mediante VNS En el trabajo de Mateus, Martin (2007) se da una alternativa de solución para los problemas de secuenciación en máquinas paralelas con tiempos de secuencia dependientes usando el algoritmo de búsqueda de entorno variable. Para resolver este problema, en dicha investigación se implementaron tres diferentes tipos de estructura de entornos:

1. Cambio de trabajos: una máquina es seleccionada y todos los posibles cambios entre trabajos están considerados.

2. Cambio de trabajos entre dos diferentes máquinas: dos máquinas son seleccionadas y todos los cambios de trabajos entre estas máquinas están considerados.

3. Los trabajos que pueden ser transferibles de una máquina a otra: estos trabajos son seleccionados y todos los posibles movimientos de un trabajo de una máquina a cualquier otra están considerados.

Estas tres estructuras de entornos se utilizan en el algoritmo de BVNS para llegar a una solución sub-óptima factible. En este caso para dar una solución inicial factible se utiliza un algoritmo basado en la investigación de Nawaz y Ham (1983). La estructura de este algoritmo es la siguiente:

CAPÍTULO 2

80

Ordena los trabajos por sus fechas límite; Para cada trabajo (i) Haz MKS←INT-MAX; Para cada máquina (m) haz Para cada posición p en la máquina (m) Haz MKS_ = inserta un trabajo (i) en m en la posición (p); Si MKS´ < MKS entonces MKS ← MKS´; Fin Remueve i de m a la posición p; Fin Fin Fin Las soluciones aleatorias para correr el algoritmo BVNS son generadas por tres procedimientos distintos de generación de soluciones. La llamada de los procedimientos depende de la estructura de entornos, así para cada diferente entorno l se tiene un procedimiento. La estructura de estos procedimientos se expone a continuación:

1. Para

Se selecciona aleatoriamente una máquina

Se selecciona aleatoriamente dos trabajos y en la máquina

Cambiar los trabajos y 2. Para

Se selecciona aleatoriamente dos máquinas y

Se selecciona aleatoriamente un trabajo en y un trabajo en

Se cambian los trabajos y

3. Para

Se selecciona aleatoriamente un trabajo y una máquina , donde no pertenece a

Se selecciona aleatoriamente una posición valida en

Se trasfiere el trabajo a en la posición

Para efectos de tiempo computacional de acuerdo con este trabajo este método de VNS puede obtener buenos resultados en tiempos de cómputo relativamente cortos. Por otra parte proporciona una manera efectiva de atacar el problema de secuenciación de trabajos en máquinas paralelas.

CAPÍTULO 2

81

Solución del problema de secuenciación de máquinas paralelas mediante SA En la investigación llevada a cabo por Díaz-Santillan (2002) se resuelve el problema de secuenciación en máquinas paralelas mediante la implementación del algoritmo de recocido simulado. En dicho trabajo el objetivo es encontrar una secuencia capaz de minimizar el tiempo total por tardanza. Por lo que la función objetivo es minimizar la suma de la tardanza para los trabajos en máquinas y esta expresada por:

Mediante la implementación del SA se encuentra una solución factible para este problema, el cual necesita definir de manera adecuada los parámetros del algoritmo. Estos parámetros son:

El mecanismo de enfriamiento de la secuencia para esto se requiere especificar la temperatura inicial, la temperatura final y la función de reducción de temperatura

La búsqueda de la solución inicial mediante un mecanismo de generación.

Generara un mecanismo de perturbación, para encontrar nuevas soluciones. En esta investigación el mecanismo de enfriamiento esta parametrizado de la siguiente manera:

1. La temperatura inicial es de 0.9 2. La función de reducción de temperatura está dada por una progresión geométrica

expresada de la siguiente forma

Donde el valor de 3. El número de iteraciones utilizadas en cada temperatura es de 100.

En lo que a la generación de la solución inicial se refiere se obtiene mediante la implementación del siguiente algoritmo:

1) 2)

3)

En este caso en el mecanismo de perturbación la solución actual es transformada en otra mediante el siguiente mecanismo: Primero se escogen los trabajos en la solución inicial o la solución anterior dependiendo del caso con una diferencia positiva de ( Cj –dj) > 0 y se incrementa en uno el número de trabajos para ese lote. Segundo escoge los trabajos de la solución actual que hayan sido terminados después de su fecha limite (Cj –dj) < 0 y disminuye en uno el número de lotes de ese trabajo. Tercero haz una lista de prioridades de acuerdo a la fecha límite. El primer lote en la lista será asignado a la primera máquina disponible, el siguiente lote será asignado a la siguiente máquina disponible. Este procedimiento debe continuar hasta que todos los trabajos hayan sido asignados. Mediante los tres parámetros del SA propuestos en este proyecto de investigación fue posible resolver el problema de secuenciación en máquinas paralelas.

CAPÍTULO 3

82

Capítulo 3 Análisis y Diseño del algoritmo de programación.

3.1 Restricciones del sistema de producción.

La problemática a atacar en la planta de aislamientos, es la programación de la producción a

través de la secuenciación de los trabajos en dos líneas de producción; número con el que cuenta

la planta de aislamientos. Hoy en día, la planeación se lleva a cabo de una forma empírica y

manual, que de ninguna manera asegura la disminución de los tiempos de producción, así como la

consolidación de la capacidad de producción de las líneas. Esto para una empresa como Owens

Corning tiene una repercusión directa con sus clientes, debido a que la empresa tiene como

compromiso establecido, satisfacer las necesidades de sus clientes; proporcionándoles el producto

correcto, con el precio acordado y en el tiempo establecido. Por otra parte, la empresa también

está comprometida con mejorar sus procesos, productos y servicios, por lo que la problemática

cobra aun mayor relevancia.

En este punto se detalla el problema de secuenciación de tareas para la programación de dos

líneas de producción de la planta. Esta secuenciación está sujeta a ciertos parámetros de decisión

que se desarrollaran a continuación, los cuales, se deben tener en cuenta para programar las

líneas de producción de manera que se cumpla con las fechas de entrega de los productos para

con el cliente. Por otro lado la complejidad de la secuenciación de trabajos con tiempos de

secuencia dependientes radica en que estas dos líneas Mj (j = 1,2) tienen que procesar n trabajos

Ji(i = 1, . . . , n), y entre cada par de trabajos ji, jk existe un tiempo de preparación de máquina; en

general distintos. Es necesario programar una secuenciación para cada trabajo y asegurar la

disponibilidad, esto para uno o más intervalos de tiempo y para las dos líneas de producción que

están sujetas a restricciones de capacidad.

Capacidad de producción.

La capacidad de producción implantada en ambas líneas de producción tiene una extracción

promedio de 35 toneladas diarias, la cual se divide en tres turnos de producción por día. La planta

trabaja 7 días a la semana durante todo el año. El proceso de planeación de la producción tiene un

horizonte de 7 días, por lo que se necesita asegurar la planificación por semana.

Fecha Límite de Producción (Due date)

La programación de la secuenciación de las tareas está sujeta a una restricción de una fecha límite

de producción, ya que cada producto que se programa para ser producido en cualquiera de las dos

líneas de la planta de aislamientos está sujeto a una fecha de embarque. Por lo anterior la fecha

producción no puede ser mayor que la fecha de embarque. Para asegurar esto el departamento de

programación de la producción estableció que la fecha de producción en que un trabajo puede ser

procesado es un día antes de la fecha de embarque. A su vez esta fecha de embarque es fijada por

el departamento de logística de acuerdo a las rutas y el tiempo de entrega en el cual el cliente

CAPÍTULO 3

83

desea tener el producto en su poder. Esta regla que estableció el departamento de cadena de

suministros tiene como principal objetivo evitar que el almacén se sature de producto terminado y

por consecuencia tener demasiado material en inventario, que para ellos implicaría elevar los

costos por este rubro. Por lo anterior la fecha de producción se calcula de la siguiente manera:

Donde:

Tiempos de preparación de la líneas (Set-up time).

En un principio se planteo que existían alrededor de 4000 diferentes trabajos que se podían

procesar en ambas líneas y que el proyecto se enfocaría únicamente en trabajar con alrededor de

96 productos los cuales representan alrededor del 50% del volumen de producción; lo anterior

para hacer tratable este problema. A continuación se muestra en la figura 3.1 la grafica del

porcentaje de producción acumulado en el año 2009 por todos los productos programados en las

líneas.

Figura 3.1 Grafica de volumen de producción acumulado por producto.

Como se observa en la figura 3.1 aproximadamente 100 productos representan el 50% del

volumen de la producción histórica durante el año 2009. La regla del 80-20 en este caso estaría

dada por 270 productos que representan el 80% del volumen de ventas. La grafica de la figura 3.1

fue calculada a partir de los datos históricos de volúmenes de producción; una muestra de estos

datos aparece representada en la Tabla 3.1.

CAPÍTULO 3

84

# Producto MRP Toneladas % por

Producto %

Acumulado

1 Glass Wool - Pipe - MEX 497 276 2.36686391 2.36686391

2 DW75 AR EXPLA M 3.8 X 122 X 3048CM 1/RPB 070 154 1.32064145 3.68750536

3 Glass Wool - RW - MEX 497 137 1.17485636 4.86236172

4 AISLHGAR R-8 M 6.4X61X1524CM 2/RPB 174 137 1.17485636 6.03721808


6 TRS-10 M W10075180 3.8X44X69 CM 100/RPB 100 85 0.72892548 7.6751565

7 TRS10 221C3658P1 M2.5X48.3X124.8CM60/RPB 100 85 0.72892548 8.40408198

8 TRS40 164D2360P18M4.4X51.3X173.9CM 100 85 0.72892548 9.13300746

9 RF-3100 AR M 2.5X122X1524CM 1/PB 070 84 0.72034988 9.85335734


11 TRS-10 W10137230 M 5.1X26X50 CM 200/RPB 100 80 0.68604751 11.234028

12 TRS10 223C5090 p1 M2.5X45.3X49.5CM160/RP 100 78 0.66889632 11.9029243

13 TRS10 222D2783P2 M2.5X53.8X172.7CM 72/RP 100 76 0.65174513 12.5546694

14 ROTARY LINER R-4.2 1x47x100' 1RL (4) 070 75 0.64316954 13.197839

15 TRS-10 W10137227 M 3.8X47X174 CM 52/RPB 100 74 0.63459395 13.8324329

16 TRS-10 W10137233 M 3.8X54X66 CM 104/RPB 100 73 0.62601835 14.4584512

17 MBI R-10 M PR 7.6 X183X3048CM 1/RPB 060 72 0.61744276 15.075894

18 TRS-40 222D2786P1 M3.8X51.3X173.9CM 35/R 100 72 0.61744276 15.6933368

19 TRS-10 PB 3540-P3M 5.1X105X170 CM 25/RPB 100 72 0.61744276 16.3107795

20 TRS30 164D2360P19M4.4X51.3X174CM40/RPB 100 70 0.60029157 16.9110711 Tabla 3.1 Extracción la tabla de Cálculo de porcentajes acumulados de volumen de producción por producto

La tabla 3.1 es una muestra de los primeros veinte productos con mayor volumen de producción

acumulado durante el año 2009. Estos productos representan el 17% del volumen acumulado de

producción. En dicha tabla están contenidos los datos de toneladas procesadas para cada

producto, así como el porcentaje de producción de cada producto en específico y el porcentaje

acumulado para estos 20 productos de la lista.

Al momento de conocer el proceso de producción y trabajar con el equipo de ingeniería de

procesos de la planta para la construcción de la matriz de tiempos de cambio entre trabajos; se

encontró que los productos que pertenecen a una misma familia de producción, si se forma un

conjunto ordenado de estos no generan ningún tipo de cambio en las líneas. Por lo anterior se

puede construir una matriz de Set-up por línea de acuerdo a las familias de producción que son

sesenta y cinco, lo que permite formular un problema de menores dimensiones que el que se

planteo al comienzo de las investigación. Sin embargo, para que esto sea posible se debe de

considerar la construcción de una serie de instrucciones dentro del algoritmo que se propondrá

para secuenciar los trabajos, que se capaz de ordenar los trabajos por familia de producción; lo

CAPÍTULO 3

85

cual es bastante factible mediante un algoritmo simple de ordenación. A partir de este punto se

trabajara tomando en cuenta este nuevo factor de decisión para darle solución al problema.

Para poder secuenciar los trabajos se debe conocer el tiempo de preparación que requiere la línea

para poder producir un producto o una familia de productos en específico. En general cada familia

de trabajos tiene un tiempo de preparación único por lo que es necesario conocer el tiempo de

preparación que toma cambiar de una familia de trabajos a un trabajo , siendo .

Para esto se requiere tener una matriz que represente todas las posibles combinaciones que se

pueden dar en los tiempos de preparación de las líneas. Se requiere generar una matriz de

cambios (Setup time) tanto para la línea uno como para la línea dos. Las dimensiones de la matriz

están dadas por una matriz cuadrada de como se formula en la siguiente expresión:

La matriz de cambios de preparación (Setup) para la línea 1 tiene dimensiones de n=65, por otra parte las dimensiones de la matriz para la línea 2 son de n= 64, estas matrices contienen todos las familias de trabajos posibles que pueden realizarse en cada una de las líneas. Para obtener el

tiempo de preparación que toma pasar de un trabajo que pertenece a una familia a otro se deben sumar los tiempos de la preparación de spinners, espreas, secadores y velo. Aunado a esto hay productos de la familia de Air Handling que ensucian en demasía las bandas transportadoras debido al pigmento negro que llevan estos productos. Esto también causa un efecto de suciedad en las camas de formado por lo que pasar de un trabajo de estos a otro toma más de 30 minutos ya que este es el tiempo que se necesita para limpiar de forma correcta toda la línea. El tiempo de preparación de cada familia de trabajos está dado por la siguiente expresión:

Donde:

CAPÍTULO 3

86

A continuación se presenta un fragmento de las matrices de cambios de preparación para ambas

líneas en las cuales se muestra los para cada uno de los trabajos. Estas matrices fueron

construidas y calculadas por el equipo de ingeniería de procesos de OCM y consideran los factores

de tiempo de cambio mostrados en la formula de arriba.

1 2 3 4 5

# Familia 601001373 601001374 601003614 601000115 601001375

1 601001373 M 45 3 6 9

2 601001374 1 M 30 6 6

3 601003614 3 5 M 5 7

4 601000115 1 6 6 M 9

5 601001375 3 5 5 5 M

Tabla 3.2: Muestra de la matriz de cambios de preparación (Setup) para la Línea 1

1 2 3 4 5

# Familia 501000081 501000082 501000142 501000083 501000084

1 501000081 M 9 5 9 1

2 501000082 5 M 9 9 9

3 501000142 3 1 M 5 9

4 501000083 9 3 5 M 5

5 501000084 3 3 1 5 M

Tabla 3.3: Muestra de la matriz de cambios de preparación (Setup) para la Línea 2

Las tablas anteriores 3.2 y 3.3 están construidas en base al código que tienen las familias de

producción dentro del sistema de operaciones de la empresa. Un código de este tipo se construye

a partir de las características de los productos de una familia y son la forma de diferenciar los

diferentes tipos de productos que se manejan en la empresa.

Tiempo de producción de los trabajos.

En este caso el tiempo de procesamiento de los trabajos está conformado por dos diferentes

tiempos, uno es el tiempo de procesamiento de los trabajos , el cual depende de la capacidad

de extracción de las líneas por hora y de la cantidad en peso de cada trabajo que se procesa en

cada conjunto formada para una familia de productos. También depende del tiempo de cambio de

pasar de una familia de trabajos a una , lo cual está dado por la matriz de Set-up que tiene cada

una de las líneas. La siguiente expresión es la forma con la cual se calcula el tiempo total de

producción de una familia:

CAPÍTULO 3

87

Donde:

El tiempo de procesamiento de los trabajos a su vez requiere de una expresión que lo defina y se

calcula de la siguiente forma:

Donde:

Las líneas de producción tienen un flujo de extracción de 1.4583 toneladas por hora, la cual es una

constante para ambas líneas de producción. Como se había mencionado en puntos anteriores esto

limita la extracción diaria para cada línea a 35 toneladas diarias y a su vez la capacidad instalada en

la planta queda fija en 70 toneladas por día.

Función Objetivo.

La función objetivo para este problema es minimizar el tiempo total de flujo en cada una de las

líneas de producción (1,2), que a su vez, depende del tiempo de producción de las familias que se

vallan a programar para cada una de las líneas. La expresión de la función objetivo se presenta a

continuación:

Lo que se pretende a través de esta función es encontrar una secuencia de cambios entre familias

que permita minimizar el tiempo de procesamiento del último trabajo (Makespan) para cada una

de las líneas. Lo anterior debe de tomar en cuenta las restricciones que debe de cumplir el

procesos de programación de la producción.

CAPÍTULO 3

88

3.2 Diseño del algoritmo de programación para la secuenciación de las dos líneas de producción.

Para resolver el problema planteado en este proyecto de investigación, se desarrollaron una serie de algoritmos con la finalidad de dar soluciones factibles para la programación de la producción. Para esto se tomaron en cuenta las restricciones del sistema y las características de los trabajos que son procesados en las líneas. Los algoritmos y criterios de decisión que aquí se plantean van a ser implementados en una interfaz que permita que el usuario final pueda utilizarlos sin ningún tipo de inconveniente.

Existen tres características que se enlistan a continuación y se deben tomar en cuenta para desarrollar la interfaz y los algoritmos que permitan secuenciar los trabajos en las líneas:

1. Se requiere desarrollar una forma de balancear los trabajos en las líneas. En este aspecto es necesario considerar que hay trabajos que se pueden procesar únicamente en la línea 1 y por otro lado existen trabajos que solamente pueden ser procesados en la línea 2. Sin embargo hay trabajos que poseen la característica de que pueden ser procesados en ambas líneas de producción. Para desarrollar una serie de instrucciones que permitan balancear las líneas se consideran los factores expuestos con anterioridad, debido a que los únicos trabajos que pueden balancear la carga en las líneas son los que tienen la factibilidad de ser procesados en ambas.

2. Para poder programar los trabajos de ambas líneas se debe implementar algún algoritmo de secuenciación que sea capaz de obtener soluciones factibles para minimizar el tiempo de procesamiento de los trabajos. Para esto se debe tomar en cuenta que se tiene que encontrar una forma de generar soluciones iniciales, para que después el algoritmo sea capaz de procesarlas y tratar de generar mejores soluciones a partir de estas.

3. Por último el horizonte de planeación es de siete días por lo que la capacidad de producción es de 24 horas diarias sin considerar los tiempos por paro de máquinas debido a fallos o mantenimiento. Para esto se pretende diseñar un algoritmo que divida los trabajos si la capacidad en un día se ve rebasada debido a una posible carga de trabajo.

Es necesario construir una base de datos o catalogo de materiales que contenga las características de los trabajos que se procesan a diario en la planta de aislamientos, y que se presentan a continuación:

Código del producto o trabajo: dentro del ERP que maneja la empresa que es el SAP los productos manejan un código que los identifica y el cual sirve para procesar la información referente al producto. Debido a lo anterior se debe tener en cuenta este código para el momento en que se tenga que programar un pedido.

Descripción del producto, es necesaria para obtener las características del trabajo que va a ser procesado y secuenciado. La descripción de estos productos es de ayuda para identificar si el producto cumple o no con las características para pertenecer a una determinada familia de producción.

CAPÍTULO 3

89

Unidad de medida base del producto (UOM), se refiere básicamente a la presentación de venta que tiene el producto, por ejemplo si el producto viene en un paquete, en rollos o en placas. Esta unidad de medida del producto tiene un peso en kg.

Peso neto del producto (Peso UOM), el peso esta dado por unidad de medida base en kg; para poder convertir los pedidos que entren al programa de producción de piezas a kg se necesita conocer el peso neto de cada producto para calcular las toneladas que van a ser procesadas.

Familia de producción (MRP CC) a la que pertenece el trabajo es de utilidad para poder generar un acomodo de productos que pertenezcan a la misma familia. Las familias de producción tienen un código con el cual se diferencian unas de otras y que formara parte de la base de datos.

Línea en la que el producto puede ser procesado, ya sea que el producto pueda ser procesado en la línea 1 o línea 2 o en ambas, esto debe estar identificado en la base de datos.

Con la información contenida en el catalogo de materiales más los datos de la orden de pedido, que son cantidad y fecha de producción (estos dos últimos son procesados y asignados por el sistema SAP), se tiene todo lo necesario para generar la secuencia de producción para las líneas. Este catalogo fue construido con base en los datos del maestro de materiales del sistema SAP para la planta de aislamientos.

CAPÍTULO 3

90

Desarrollo de los algoritmos.

Para obtener un sistema que permita llevar a cabo la secuenciación de los trabajos, se dividió en dos secciones la solución del problema. La primera sección se encarga de balancear las líneas de producción y la segunda se encarga de secuenciar los trabajos para cada una de las líneas. En los siguientes puntos se detalla el diseño de los algoritmos utilizados para construir la solución que permita programar los trabajos de manera factible y en tiempos de cómputo relativamente cortos.

Algoritmo para el balanceo de las líneas.

En este punto se presenta el diseño del algoritmo para el balanceo de las cargas de trabajo en las líneas de producción. Para balancear las líneas se toman en cuenta aquellos trabajos que se pueden procesar en ambas, ya que los demás trabajos forzosamente tienen una línea de producción asignada debido a sus características de proceso. A continuación se presenta un pequeño fragmento de las listas de materiales (Tabla 3.3) que pueden ser procesados en la línea 1, línea 2 y aquellos que pueden ser producidos en ambas.

Código Producto Línea

444336 DW75 AR EXPLA M 3.8 X 122 X 3048CM 1/RPB 1

526766 TRS-30 164D2361P013 M 5.1x62.2x70.6CM 40 1

526767 TRS-40 164D2361P017 M 3.8x62.2x70.6CM 40 1

482405 AISLH R-7 EXP9 M 5.0X120X1500CM 1/RPB 1

488797 PINK 40 R M 10x120x1000 CM 1/PPBAG(4 2

446980 SAB R-11 UFD EXP1 M 24X96IN 17/PBBAU4 2

446979 SAB R-8 UFD EXP1 M 24X96IN 24/PBBAU4 2

445443 SAB R-6.35 UFD EXP1 M 24X96IN 30/PBBAU4 2

547389 AISLH R-7 EXPLA M 5.1X61X1524CM 2/RPBV 1,2

421713 AISLHGAR R-11 M 8.9X41X1524CM 3/RPB 1,2



Tabla 3.4 Fragmento de la lista de materiales.

En la tabla 3.4 se muestran doce productos de los cuales ocho de ellos tienen la característica de que únicamente pueden ser procesados en una sola línea, sin embargo los últimos cuatro productos tienen la característica de que pueden ser procesados en ambas líneas. Existen alrededor de 500 trabajos que poseen la característica de procesamiento 1,2 que permite balancear las cargas de trabajo.

El algoritmo de balanceo tiene que ser capaz de distinguir si los trabajos pertenecen al conjunto , que es el conjunto de trabajos que únicamente pueden ser procesados en la línea uno, que es el conjunto de trabajos que solo pueden ser procesados en la línea dos o pertenecen al conjunto que son los trabajos que pueden pertenecer a o a dependiendo de la carga acumulada en las líneas de producción. A continuación se presentan los pasos e instrucciones con las cuales, funciona el algoritmo de balanceo de líneas propuesto.

CAPÍTULO 3

91

Algoritmo 1

1) Haz una Lista de trabajos que vayan a ser secuenciados en el horizonte de tiempo (h) que contenga las siguientes características:

Tiempo de procesamiento

Fecha de producción

Familia de producción a la que pertenece 2) Cuenta el número total (n) de trabajos en la Lista 3) Haz un acomodo inicial de trabajos de acuerdo al siguiente criterio:

Para j=1 hasta n Si entonces acomódalo en la Sublista1 Si entonces acomódalo en la Sublista2 Si entonces acomódalo en la Sublista1,2

Fin j 4) Ordena de mayor a menor tiempo de procesamiento que tengan los trabajos 5) Para y se obtiene el tiempo total de carga:

Cuenta el número total (n) de trabajos en y y haz:

6) Para los trabajos de la lista Ordenada haz:

Para j=1 hasta n Si entonces Asigna a y haz Paso 5 Si entonces Asigna a y haz Paso 5 Fin j (cuando no existan trabajos en )

7) Finalizar Balanceo

Con la serie de instrucciones que se muestra arriba, se asegura el balanceo de las líneas de producción, lo que permite estructurar una serie de pasos para poder generar acomodos para cada una de las líneas de producción. Estos acomodos tienen la finalidad de generar conjuntos de trabajos que pertenezcan a la misma familia, así como ordenar los trabajos por fecha de producción. El siguiente algoritmo genera dichos acomodos:

Algoritmo 2

1) Para y balanceadas haz: 2) Ordena los trabajos por fecha de producción

3) Para cada trabajo en la fecha

Ordenarlos trabajos por familia de producción 4) Finalizar (cuando se reordenan y bajo estos criterios)

Al finalizar los pasos del algoritmo número dos, los trabajos se encuentran listos para ejecutar el algoritmo de secuenciación de trabajos. Para este paso se tomaran en cuenta las matrices de Set-up construidas para encontrar las secuencias de cambios entre los trabajos que sean capaces de encontrar un mínimo para la función objetivo. Un paso antes de secuenciar los trabajos se verifica

CAPÍTULO 3

92

si la capacidad de producción para no ha sido rebasada de ser así se aplica el

algoritmo desarrollado en el siguiente punto.

Método de división de trabajos.

Cuando la capacidad de producción en un día se vea rebasada por la carga de trabajo se

requiere de un mecanismo que permita dividir la carga a partir del trabajo y asignar estos trabajos a una fecha . También es posible que un trabajo tenga que ser dividido en dos partes

para satisfacer la restricción de capacidad teniendo que fijar la segunda parte del trabajo a una fecha . Para poder llevar a cabo esta tarea se diseñó el siguiente conjunto de instrucciones

que están representadas en el siguiente algoritmo.

Algoritmo 3

1) Para =1 hasta n :

2) Suma las toneladas que tienen que ser procesadas en la fecha

3) Si Carga 35 Toneladas entonces A partir del trabajo que provoca que la Carga haz: Divide el trabajo en

y de forma que:

La Carga hasta el trabajo sea para la fecha

4) Asigna los trabajos a la fecha

5) Fin

El algoritmo anterior simplemente verifica la capacidad de producción diaria, que es de 35 toneladas y la compara contra la carga acumulada para una fecha determinada. Si la carga acumulada es mayor que 35 toneladas entonces se genera un movimiento hacia delante de los trabajos que provocan que esta restricción no se cumpla.

Algoritmo para la secuenciación de los trabajos en línea.

Para efectos de este proyecto de investigación se implemento el algoritmo de recocido simulado (SA) para poder llevar a cabo la secuenciación de los trabajos. Este algoritmo requiere de tres estructuras clave para su funcionamiento. La primera es el desarrollo de un algoritmo que permita generar soluciones iniciales para la secuenciación de los trabajos. La segunda es establecer los parámetros del sistema de enfriamiento del recocido simulado. Por último generar un sistema que permita perturbar la solución inicial con la finalidad de encontrar mejores soluciones a partir de la inicial. En los siguientes puntos se plantean y desarrollan estos tres factores que inciden en el comportamiento del algoritmo SA.

Generación de la solución inicial.

La generación de la solución inicial en este caso es un mecanismo que permite encontrar mínimos locales para partir desde este punto a la búsqueda de una mejor solución. Encontrar esta solución primaria depende de una serie de instrucciones que busquen un acomodo mínimo para el conjunto de tiempos de set-up que se originan al momento de entrar productos de diferentes

CAPÍTULO 3

93

familias en una determinada fecha de producción. Visto desde la perspectiva de una red se intenta encontrar un acomodo entre los nodos que permita encontrar un flujo mínimo, aunque este sea un mínimo que no esté cerca del mínimo global. La siguiente estructura de red representa los elementos necesarios para construir una solución inicial.

Figura 3.2: Red representativa de la solución inicial para un flujo mínimo

Lo que se pretende es que el flujo que se genere en la red atreves de un acomodo primario en los trabajos de la familia hasta la familia sea una solución inicial factible. Aunado a esto cada nodo que representa a una familia de trabajos tiene una carga generada por un tiempo de procesamiento de los trabajos de esa familia. El tiempo de procesamiento no puede ser modificado, ya que es una constante que depende de la cantidad del trabajo que debe ser procesada en una determinada línea. Debido a lo anterior el conjunto formado por todas las posibles combinaciones de cambios entre familias es lo que da la pauta para encontrar un flujo mínimo en la red, que se puede representar de la siguiente forma:

Las instrucciones y métodos necesarios para construir la solución inicial en forma de algoritmo se detallan a continuación. Este método heurístico fue desarrollado para este proyecto de acuerdo a sus características y necesidades, pero puede ser implementado para otros problemas que requieran un mecanismo de generación de soluciones iniciales sencillo y practico.

Algoritmo 4

1) Para cada fecha de producción en el horizonte de tiempo (h):

2) Genera una matriz de tiempo de cambios (Set-up) a partir de la matriz general que

contiene todos los posibles cambios entre familias; de esta forma se tiene que:

3) Para f=1 hasta n (donde f es el número de fila de la matriz ) haz:

Declaración: R= f Para un valor k=1 hasta (n-1) haz: ((n-1) es el número de pasos necesarios para encontrar una solución a partir de f). Para cada R Encuentra el valor mínimo en R del conjunto de set-ups que pertenecen a esa fila. Si hay más de un valor igual al mínimo en R entonces escoge el primer valor de izquierda a derecha como mínimo y los demás mínimos hazlos M. Para cada valor (j) en R haz: Si entonces

CAPÍTULO 3

94

Si entonces haz todos los valores de la columna (C) donde se ubica j igual a M, excepto el valor j mínimo; asigna R=C (Para la siguiente iteración de R) FIN J FIN R

4) Fin f 5) Para los valores mínimos encontrados a partir de

Guarda en

6) Haz una Lista ordenada de las familias de acuerdo al acomodo obtenido a partir de 7) Si la iteración entonces compara

Si se cumple la desigualdad actualiza y la lista (L) Si no se cumple mantener y Lista (L)

8) Fin

Lo que este algoritmo (4) lleva a cabo, es encontrar a partir de cada renglón de la matriz un

acomodo como el de la figura 3.1, que permita la evaluación de un flujo mínimo factible . Para

después quedarse con la mejor solución encontrada a partir del conjunto , de esta forma se tiene que:

A esta solución se le debe aplicar un mecanismo de perturbación dentro del recocido

simulado. Este método de perturbación se estudia en el siguiente punto.

CAPÍTULO 3

95

Mecanismo de perturbación (generación de soluciones vecinas).

Para buscar mejores soluciones se diseñó un mecanismo de perturbación que permite generar nuevos acomodos a partir de soluciones obtenidas en iteraciones anteriores, o bien a partir de la solución de inicial. Lo que se pretende es que mediante una serie de pasos se pueda encontrar mejores flujos mínimos, esto en cuanto a tiempos de set-up se refiere y visto desde una perspectiva de una red. Para llevar a cabo la tarea anterior se requiere cambiar el arreglo de ordenamiento que tienen las familias de producción. Para ejemplificar estos conceptos se presenta la red de la figura 3.3.

Figura 3.3 Perturbación del arreglo en red del acomodo de trabajos.

Una posible perturbación se daría si se cambia de lugar a la familia que se ubica en el nodo número dos, por la familia que se encuentra en el nodo y a su vez la familia toma la posición en el nodo número dos como se muestra en la figura 3.3. Para medir este cambio se tendría que evaluar nuevamente esta solución y ver si efectivamente se genero una mejora con dicho cambio. El algoritmo que se diseñó para ejecutar esta tarea tiene la finalidad de que mediante una forma ordenada y lógica de instrucciones sea posible perturbar soluciones anteriores con la posibilidad de que se encuentre una mejor secuencia de los trabajos programados. A continuación se presenta el algoritmo que se diseñó y utilizo como mecanismo de perturbación en este proyecto.

Algoritmo 5

1) Para la iteración hasta 2) Encuentra el valor máximo de cambio de la solución inicial o anterior (Dependiendo

de la iteración)

3) Genera un número aleatorio r 4) desde i=1 hasta n 5) Si el arco = entonces ejecuta paso 5 o 6 dependiendo del valor de r

6) Si entonces Si el nodo i en la red es un nodo inicial haz: Cambia el nodo al nodo y viceversa de la siguiente forma:

CAPÍTULO 3

96

Si el nodo i en la red es un nodo intermedio haz: Cambia el nodo al nodo y viceversa de la siguiente forma:

Si el nodo i es el nodo final de la red haz: Cambia el nodo al nodo inicial y viceversa de la siguiente forma:

7) Si entonces

Si el nodo en la red es un nodo inicial haz: Cambia el nodo final por el nodo y viceversa de la siguiente forma:

Si el nodo en la red es un nodo intermedio haz: Cambia el nodo por el nodo y viceversa de la siguiente forma:

CAPÍTULO 3

97

Si el nodo i es el nodo final de la red haz: Cambia el nodo al nodo inicial y viceversa de la siguiente forma:

8) Fin i 9) Fin de iteraciones

El mecanismo de perturbación propuesto en el algoritmo 4 funciona a través de un motor de cambio aleatorio, que básicamente permite tomar la decisión de si se debe cambiar el nodo con el nodo anterior o con el nodo posterior en la red formada por las familias de trabajos que

entran en una fecha de producción . La probabilidad de llevar a cabo estos cambios está

controlada por la generación de números aleatorios entre (0,1) y está representada de la siguiente forma:

donde:

)= La probabilidad de cambio del nodo , si existe un arco con flujo saliendo de este

La probabilidad de hacer el cambio con el nodo

La probabilidad de hacer el cambio con el nodo

El mecanismo comienza buscando nodos donde exista un tiempo de Setup, que sea el valor más grande ( del conjunto . Lo anterior se lleva a cabo con la esperanza

de que cuando se reacomode el nodo que genera este tiempo de cambio máximo, se pueda encontrar un nuevo arreglo . Con la estructura del algoritmo de recocido simulado es

posible llegar a aceptar peores soluciones con la esperanza de encontrar una mejor. A continuación se presenta el algoritmo SA implementado para regular este mecanismo de perturbación, así como la definición de sus parámetros para esta investigación.

CAPÍTULO 3

98

Parametrización del algoritmo SA (Sistema de Enfriamiento).

El sistema a través del cual el algoritmo es capaz de aceptar las soluciones generadas por el mecanismo de perturbación, debe contener ciertos parámetros que permiten ir disminuyendo la probabilidad de aceptar peores soluciones, a medida que el número de iteraciones va aumentando. En seguida se propone la configuración del sistema de enfriamiento para el SA que se va a utilizar en este proyecto.

La función de reducción de temperatura en este trabajo está dada por una progresión geométrica como la propuesta en la investigación de Díaz-Santillán (2002). En la cual se establece la siguiente función:

Donde el valor de

La función necesita una temperatura inicial al momento de iterar por primera vez el algoritmo. El valor de esta temperatura es =1, ya que debe ser un número entero positivo y de un valor relativamente pequeño.

El total de iteraciones del algoritmo esta dado por el número total de temperaturas , que en esta caso es igual a 50, a su vez cada temperatura tiene permitido iterar 5 veces con el mismo valor de calculado por la función de reducción de temperatura. La probabilidad de aceptar peores soluciones (Probabilidad de Boltzman) también depende del valor que tome y que va disminuir a medida que el número de iteraciones aumenta. De esta forma el algoritmo de recocido simulado queda estructurado por completo en el algoritmo 6, el cual se presenta más adelante.

A pesar de que estos parámetros son los que estarán cargados al momento de iniciar la aplicación en la que están contenidos los algoritmos; se pretende que los parámetros se puedan variar al momento de inicializar dicha aplicación.

CAPÍTULO 3

99

Algoritmo 6

1) Balancea las líneas (Algoritmo 1 ,2) 2) Comienza SA para Línea=1 y 2

Selecciona solución inicial a partir del algoritmo 3 si la T=1 o 4 si la T>1

Selecciona Selecciona función de reducción de temperatura Selecciona número de iteraciones para cada temperatura =5 Selecciona el número de temperaturas =50

3) Repite: Contador de Temperaturas =0

4) Repite: Contador de iteraciones =0 Ejecuta mecanismo de perturbación (Algoritmo 4) y obtén una solución a partir de

Calcula

Si entonces

Genera un número aleatorio (0,1)

Si

entonces

5) Guarda la mejor solución hasta el momento Contador de iteraciones = Contador de iteraciones + 1

6) Hasta el número de iteraciones Contador de Temperaturas = Contador de Temperatura +1 Temperatura

7) Hasta el número de temperaturas ( Criterio de paro) 8) es la aproximación a la solución optima

9) Fin

En el algoritmo anterior están contenidas todas las instrucciones necesarias para poder establecer una secuencia factible para líneas de producción en las fechas de producción , en el

horizonte de planeación de siete días. A continuación en la figura 3.4 se presenta a manera de diagrama la estructura del Algoritmo 6.

CAPÍTULO 3

100

La forma general del algoritmo que permite secuenciar las líneas de producción, queda representado a través de la figura 3.4. En esta figura se puede observar los pasos a través de un diagrama de flujo que deben ser ejecutados para obtener un acomodo final.

Figura 3.4 Diagrama de flujo del algoritmo de secuenciación propuesto para la investigación.

En el siguiente punto se estudia la programación de estos algoritmos, así como la construcción de una interfaz que permita utilizarlos de manera adecuada. De esta forma se diseñaran los módulos y aplicaciones necesarias para hacer correr la aplicación que permita secuenciar las líneas de producción.

Balanceo de Líneas (1,2)

(Algoritmo 1 y 2)

Aplicación de Recocido

Simulado para (1,2)

Generación de inicial (Algoritmo 4)

Generación de , (Algoritmo 5)

Es

Calcula

Genera número aleatorio

Es

Si

No

Si

No

Depende de actual

Fin (Cuando =50)

Método de

división de

trabajos

(Algoritmo 3)

CAPÍTULO 3

101

3.3 Programación del algoritmo de secuenciación y Construcción de la interfaz para su

aplicación.

La programación del algoritmo de secuenciación, así como todas las series de instrucciones que se

requieren para soportar la interfaz, fueron programadas en lenguaje Visual Basic for Application

(VBA), en la sección de anexo se muestra el código de programación que requiere dicho algoritmo.

Lo anterior debido a que la interfaz que se pretende construir funcionará a través de Microsoft

Excel 2007. Esta interfaz tendrá que trabajar con la serie de datos contenidos en el catalogo de

materiales, el cual contiene la información necesaria para poder construir la secuencia de forma

adecuada. Por otro lado las matrices de cambio entre familias de producto, deben estar

contenidas en esta aplicación, para que el algoritmo pueda leer los tiempos de cambio requeridos

en las fechas de producción del horizonte de planeación.

La aplicación de Excel contiene nueve hojas de cálculo, cada una de estas tiene diferentes usos y

aplicaciones que en el desarrollo de este punto serán explicadas a detalle. Por el momento

únicamente se enumeran y se les asigna un nombre para su identificación:

1. Balance (Hoja1)

2. Línea 1 (Hoja2)

3. Línea 2 (Hoja3)

4. ReporteL1 (Hoja4)

5. ReporteL2 (Hoja5)

6. Solver (Hoja6)

7. MatrizST1 (Hoja7)

8. MatrizST2 (Hoja8)

9. CatalogoM (Hoja9)

Todas estas hojas de cálculo están contenidas en un libro de trabajo denominado SCHEDULER V10

(interfaz en Excel 2007). A su vez estas hojas contienen el código de programación necesario para

interrelacionarse entre ellas, con la finalidad de poder construir una solución factible de

secuenciación para ambas líneas de producción. A partir de este momento se analizará el

funcionamiento de cada una de las hojas enumeradas con anterioridad, así como la programación

requerida para su uso.

CAPÍTULO 3

102

Programación e implementación de los algoritmos 1 y 2 para el balanceo de líneas.

Las entradas de los trabajos que van a ser secuenciados tienen que ser colocadas en la hoja

denominada Balance. En esta hoja se capturan todas las entradas de los trabajos requeridos para

satisfacer las órdenes generadas por los clientes, o bien para la reposición del inventario de

seguridad de los productos que requieren de uno. A su vez es aquí donde se ejecutan los

algoritmos (1,2) que permiten balancear las cargas de trabajo y asignar cada trabajo a una línea

de producción , para posteriormente ser secuenciado. En la figura 3.5 se ejemplifica las

entradas que requiere el sistema para posteriormente trabajar la información.

Figura 3.5 Hoja de Balance: Entrada del código del producto.

De acuerdo a la figura 3.5 se explica el funcionamiento del método de entrada para los trabajos

. Este comienza cuando en la columna A, a partir de la fila 5 se introducen los códigos

de los trabajos que van a ser procesados. Una vez que el código ha sido cargado en una de estas

celdas; automáticamente, a través de formulas de búsqueda establecidas en la hoja, el sistema

jala la información del catalogo de materiales (contenido en la hoja CatalogoM) correspondiente a

las columnas de: Producto, MRP Controler, MRP CC, Base UOM, Peso UOM, Línea del producto 1 o

2(en caso de ser un producto que puede ser procesado en ambas aparecerá 1,2). Existen otros

campos que son parámetros de entrada que deben ser llenados de forma manual como lo son: la

columna H correspondiente a la cantidad de producto que se requiere procesar (QTY), ya que a

partir de esta se calculan las Toneladas a procesar (Columna I) y el tiempo (Columna J) que toma

procesar ese trabajo en horas; el otro campo que es necesario asignar es la fecha de producción

CAPÍTULO 3

103

(Columna K) que se fijo a través del sistema SAP. El límite de entradas permitidas al sistema es de

645 trabajos distintitos; desde la perspectiva de la hoja de balance se pueden asignar trabajos

desde la celda A5 hasta A650. En la parte superior de la hoja de balance se encuentran datos como

los de las celdas CargaL1 y CargaL2, los cuales, en su celda contigua muestran la carga de trabajo

que existe en cada una de las líneas respectivamente; lo anterior sin tomar en cuenta los trabajos

que pueden ser procesados en ambas líneas.

Una vez que todos los trabajos se encuentran referenciados en la hoja de Balance como se

muestra en la figura 3.5, es posible balancear las cargas de trabajo y asignar los trabajos a las

líneas de producción. Este proceso es puesto en marcha cuando se pulsa el botón que se ubica en

la parte superior izquierda de dicha hoja, el cual tiene como letrero “Balancear Líneas” y que se

muestra en la figura 3.6

Figura 3.6 Botones que ejecutan instrucciones: En la hoja Balance

Estos botones pueden ser observados en la figura 3.5 en un contexto global de la hoja de trabajo.

El botón con él letreo “Clear Carga” permite borrar todos los datos que puedan estar contenidos

en la hoja de Balance, esto para dejar lista la hoja para una nueva carga de información. Por otro

lado cuando es pulsado el botón “Balancear Líneas”, se comienza la ejecución de los algoritmos 1

y 2. Lo anterior permitirá asignar todos los trabajos a una línea en específico para que puedan ser

procesados.

CAPÍTULO 3

104

Al tiempo que se ejecutaron las instrucciones de los algoritmos 1,2 para balancear las cargas, en la parte derecha de la hoja de Balance aparecerá la carga debidamente balanceada como se observa en la figura 3.7 y con todos los trabajos asignados a cada una de las líneas. Este código de los algoritmos 1,2 también permite referenciar los trabajos a su hoja correspondiente; estas hojas tienen asignado el nombre de Línea 1 y Línea 2. Cuando los trabajos han sido fijados a sus respectivas hojas se les ordena primero por fecha, para después ordenarlos por familia de producción.

Figura 3.7 Asignación de cargas una vez ejecutado el método de balanceo de líneas

Cuando se ha ejecutado el método de balanceo de cargas a partir de la columna N de la hoja de Balance se obtiene una tabla como la que se observa en la figura 3.7, en la que aparecen todos los trabajos asignados a una línea de producción. La tabla 3.7 contiene los mismos parámetros de información que la tabla de la figura 3.6 con la diferencia de que en la 3.7 se pude observar en las celdas contiguas a Carga L1 y Carga L2 el balanceo de la carga de trabajo en horas que presenta cada una de las líneas respectivamente. Estos mismos datos aparecen ya ordenados de acuerdo a los criterios del algoritmo 2 en las hojas nombradas Línea 1 y Línea 2; a los trabajos asignados a estas hojas se les aplicara el recocido simulado para encontrar una secuencia factible para cada una de las líneas. En el siguiente punto se explica el funcionamiento de las hojas Línea 1 y Línea 2 y el código necesario para ejecutar el SA.

CAPÍTULO 3

105

Programación e implementación del Recocido Simulado (SA).

La ejecución del algoritmo de recocido simulado depende de los trabajos que una vez balanceados son asignados a las líneas estos trabajos se encuentran dentro de las hojas Línea 1 y Línea 2 respectivamente; estas hojas tienen una interrelación con las matrices de tiempo de cambio, las cuales, fueron construidas en las hojas MatrizST1 para la línea 1 y MatrizST2 para la línea 2. Por otro lado al momento de terminar la ejecución del algoritmo, este genera una tabla con el tiempo de cambio total de secuencia mínimo encontrado para cada una de las fechas en

el horizonte de planeación, además de crear otra tabla que contiene un informe de capacidad utilizada contra capacidad disponible. Lo anterior se puede observar en las hojas ReporteL1 y ReporteL2 respectivamente para cada una de las líneas. En la Figura 3.8 se muestra el formato general de las hojas Línea 1 y 2, ya que su estructura y funcionamiento es idéntico.

Figura 3.8 Formato de la hoja Línea 1 y 2

En la figura de arriba se muestra la información necesaria para ejecutar el algoritmo de recocido simulado para la secuenciación de cada una de las líneas. En la columna E (MRP CC) se encuentra referenciada la familia de trabajo a la que pertenecen los códigos de la columna B. Estos códigos por familia son utilizados para buscar en la respectiva matriz de cambio los tiempos necesarios para construir una matriz específica de cambios para cada fecha y a partir de esta obtener la

solución inicial factible y poder generar soluciones vecinas. Existen columnas que no aparecen en la figura 3.8, una de ellas es la columna A; en esta columna el usuario puede introducir el número de orden de pedido para cada uno de los trabajos . Esta orden es generada en el sistema SAP y el llenado de esta columna es de carácter opcional para el usuario. En el lado derecho de esta tabla se encuentra la columna M en la cual, se le asigna un horario estimado de producción a partir de el método de división de trabajos.

CAPÍTULO 3

106

En el formato general de las hojas “Línea” existen tres botones como se muestra en la parte superior de la figura 3.8, que permiten activar una serie de algoritmos e instrucciones. En la figura 3.9 se observa de forma detallada el diseño y la composición de estos botones.

Figura 3.9 Botones de Acción para las hojas Línea 1 y Línea 2

De acuerdo con la figura 3.9, el primer botón de derecha a izquierda con el letrero “Clear 1” desarrolla la función de borrar toda la información contenida en estas hojas de trabajo. El segundo botón en este sentido es el denominado “Scheduler L1” este botón tiene la función de ejecutar el algoritmo 3, además de generar el horario estimado de producción para todas las fechas en el

horizonte de planeación. Por último el botón con el nombre de “Optimización L1” permite iniciar el procedimiento requerido para llevar a cabo el SA. El orden de ejecución de los botones puede ser visualizado a través de la figura 3.10.

Figura 3.10 Diagrama de flujo para el orden de ejecución de los botones

De acuerdo al diagrama de la figura 3.10, el primero pasó que se debe llevar a cabo es el de la ejecución del algoritmo 3 a través de el botón Scheduler L1. El código de instrucciones que se ejecutan al momento de presionar este botón permite dividir los trabajos por día de acuerdo a la capacidad disponible en ambas líneas de producción.

De manera detallada este primer paso de ejecución confirma que la capacidad disponible en horas para cada fecha no sea rebasada y de ser así recorre el conjunto de trabajos que generan que

la restricción de capacidad no se cumpla a una fecha . Este algoritmo también contiene una

serie de instrucciones que le permiten proporcionar un horario de producción estimado para todos los trabajos que se encuentren dentro del horizonte de tiempo. Una vez que este código ha sido ejecutado se pueden ejecutar las instrucciones de SA.

1) Scheduler L1

2) Optimización L1

3) Clear L1

CAPÍTULO 3

107

El segundo botón que debe ser ejecutado es el de “Optimización L1”, este botón permite hacer un llamado al modulo que debe ejecutar el SA. Este modulo fue diseñado para cargar los parámetros de entrada que requiere el recocido simulado y se muestra en la figura 3.11

Figura 3.11 Modulo de Ejecución del Recocido Simulado

El modulo de recocido simulado que se muestra en la figura 3.11 tiene cargados todos los parámetros del sistema de enfriamiento, sin embargo la temperatura inicial, la función de reducción de temperatura, el número de iteraciones para cada temperatura y el número total de iteraciones pueden ser modificados por el usuario con la finalidad de poder encontrar variantes en el comportamiento del algoritmo en cuanto a generación de soluciones se refiere. Por otra parte la aplicación cuenta con dos botones de acción; el primero de derecha a izquierda es el botón con el letrero “Exit”, el cual permite salir del modulo después de haber ejecutado el recocido simulado. El segundo botón nombrado “Run Optimisation L1” al momento de presionarlo permite ejecutar las siguientes instrucciones:

1. Ejecuta la búsqueda de la solución inicial factible (Algoritmo 4) 2. Llama al recocido simulado para comenzar la búsqueda de mejores soluciones. 3. Ejecuta el mecanismo de perturbación (Algoritmo 5) 4. Encuentra la mejor solución factible 5. Termina la ejecución del SA 6. Genera reporte de la secuencia obtenida (En la hoja ReporteL1 o L2 dependiendo

de la línea)

Cuando comienza la ejecución del SA a partir del botón “Run Optimisation L1” en la parte inferior del modulo aparecerá una barra de progreso que indica el porcentaje de ejecución en la que se encuentra el algoritmo en todo momento. Cuando la barra indica el 100% se debe salir del modulo, para observar que todos los trabajos han sido secuenciados de forma satisfactoria en la respectiva hoja de Excel, en este caso Línea 1 o 2. En la figura 3.12 se muestra la imagen de la barra de progreso cuando el algoritmo está en plena ejecución.

CAPÍTULO 3

108

Figura 3.12 Barra de progreso del SA

Para ejecutar todos los cálculos requeridos por este modulo en la aplicación de Excel, existe una

hoja llamada “Solver”, la cual esta designada únicamente para el procesamiento de la información

requerida cuando se lleva a cabo el procedimiento de recocido simulado. En Solver no se deben

agregar datos de ninguna índole, ya que la hoja necesita estar siempre en blanco cuando se

ejecuten las instrucciones del modulo SA. Al finalizar las instrucciones correspondientes al

recocido simulado se habrá generado una secuencia factible para cada una de las líneas de

producción.

Al momento de finalizar las instrucciones anteriores todos los trabajos habrán sido secuenciados

y ordenados de acuerdo a la secuencia obtenida con la ejecución de SA. Lo anterior se verá

reflejado en las hojas Línea 1 y Línea 2. Es necesario volver a ejecutar el botón Scheduler L1 para

que asigne los horarios estimados de producción para cada uno de los trabajos, como se observa

en la figura 3.10 que muestra el orden de ejecución de los botones para esta aplicación. Los

reportes finales se muestran en las hojas Reporte L1 y Reporte L2 respectivamente para cada una

de las líneas. Estos reportes están compuestos de las tablas 3.4 y 3.5 que se muestran a

continuación.

La tabla 3.4, contiene la información correspondiente a los tiempos de cambio mínimo totales encontrados para cada fecha en el horizonte de planeación. En la primera columna aparecerá

la fecha de producción. En la segunda columna se observan los tiempos totales de secuencia encontrados para sus respectivas fechas de producción. La tercera columna es una constante del costo en el que incurre la planta al tener parada la línea un minuto, en este caso es de 19 dólares. Por último la cuarta columna se obtiene al multiplicar las celdas de la tercera columna con sus respectivas celdas de la segunda columna, para obtener así el valor del costo diario de los respectivos tiempos de cambio (Set –up). Al final se suma los costos de todos los días y se obtiene el costo mínimo total encontrado para un determinado horizonte de planeación.

CAPÍTULO 3

109

Fecha de Producción

Tiempo Total de Set-Up

(Min)

Costo (Dls) por Tiempo Muerto por

(Minuto)

Costo por Día

(Set-Up)

Total $1,258

06/11/2010 7 19 133

07/11/2010 21.2 19 402.8

08/11/2010 5.1 19 96.9

09/11/2010 9.2 19 174.8

10/11/2010 9.3 19 176.7

11/11/2010 14.3 19 271.7

12/11/2010 0.1 19 1.9 Tabla 3.4 Reporte de Tiempos de cambio mínimo encontrados

Esta aplicación también genera un reporte de capacidad de la línea de producción el cual se puede observar en la tabla 3.5. En este caso se muestra de ejemplo el resumen de capacidad de la línea 1, la cual se muestra a continuación.

Días Planeados de Producción

Capacidad Utilizada

(Hrs)

Toneladas Procesadas

Capacidad Disponible

(Hrs)

Toneladas Disponibles

(L1)

Resumen de Capacidad Disponible para Línea 1

06/11/2010 24 34.999 0 0

07/11/2010 24 35 0 0

08/11/2010 24 33.148 0 0

09/11/2010 24 34.81 0 0

10/11/2010 24 34.998 0 0

11/11/2010 22.478 32.781 1.522 2.22

12/11/2010 18.147 26.464 5.853 8.54 Tabla 3.5 Resumen de capacidad disponible en línea

La tabla 3.5 está compuesta de seis columnas y proporciona un resumen de capacidad utilizada contra la capacidad disponible. En la primera columna se encuentran ubicadas las fechas de producción correspondientes a un horizonte de tiempo en particular. En la segunda columna se indica la capacidad utilizada en horas para todos los días programados. Dentro de la tercera columna se ubican las toneladas que van a ser procesadas. Por otro lado en la cuarta columna se indica la disponibilidad en horas que existe en los días planeados, a su vez en la quinta columna se representa en toneladas disponibles dicha capacidad existente. Para poder evaluar el comportamiento de esta aplicación y los resultados que arroja, se desarrollara un análisis dentro del capítulo 4 de la investigación en curso.

CAPÍTULO 4

110

Capítulo 4. Análisis de los resultados.

4.1 Evaluación y análisis del comportamiento del algoritmo.

En términos prácticos la complejidad computacional está directamente relacionada con el tiempo de cómputo. Razón por la cual es de interés identificar los elementos que tienen influencia sobre dicho tiempo. Dichos elementos pueden ser de diversa naturaleza y dependen en gran medida del problema particular, es decir de la instancia. El tipo de elementos de los que se hará análisis en el presente punto están relacionados con las muestras tomadas de la programación de la producción con el método actual contra la programación realizada con el algoritmo de secuenciación. A su vez se pretende ver el impacto directo del algoritmo SA en los tiempos de Setup, así como en la configuración de los costos por dicho rubro. Se busca que los experimentos brinden información respecto a la comparación de dos métodos distintos de programación de la producción, teniendo como objetivo:

Comparar en igualdad de condiciones los dos métodos de programación existentes.

Definir el tiempo de computo promedio necesario para la aplicación del algoritmo SA

Definir si hay un impacto directo en la reducción del tiempo de Setup total con la implementación del SA.

Definir el impacto en los costos de preparación de máquinas.

El análisis anterior permite conocer si el algoritmo se desarrollara mejor que el método actual en un ambiente conocido mediante la toma de un muestreo de todo un año de programación. Para llevar a cabo la comparación se tomo una muestra de 52 semanas de programación, las cuales fueron procesadas con el método actual de programación. Para efectos de la comparación estos programas muestreados no incluyen los cambios generados en la programación por tiempo muerto por fallas en las líneas, ni el tiempo programado para el mantenimiento de las líneas. Por lo anterior las muestras se encuentran en su estado ideal tal y como el planeador lo programo en un inicio.

CAPÍTULO 4

111

Un aspecto que influye en los resultados que puede arrojar el algoritmo es la capacidad de procesamiento de cómputo, ya que las computadoras poseen diferentes características, las cuales pueden mejorar o empeorar el tiempo de procesamiento de la información. En este aspecto las características del equipo de cómputo utilizado para las pruebas se muestran a continuación en la tabla 4.1.

Procesador Intel Core Duo T2300 a 1.67 Ghz

Memoria (RAM) 1015 MB

Tipo de Sistema Sistema operativo de 32 bits

Sistema Operativo Windows Vista Home Premium Tabla 4.1 Características del Equipo de Pruebas

Las características del equipo de cómputo mostradas en la tabla 4.1 son las que se utilizaron para llevar a cabo las 52 corridas necesarias para poder comparar los resultados del Recocido Simulado contra el método actual. Por otra parte el método actual es completamente manual y no requiere de ningún algoritmo o instrucciones automatizadas para generarlo, por lo que su funcionamiento únicamente requiere de una tabla de cálculo (Excel) para poder generar el programa. Los resultados de los 52 procesos de ejecución del algoritmo SA consideran todos los trabajos programados para cada una de estas semanas, además para poder correr el algoritmo se ejecuto el proceso de balanceo de líneas para cada una de las muestras. Por otro lado las fechas de programación de la producción asignadas por el programador fueron respetadas en todo

momento. Para evaluar el desempeño del algoritmo se tomaron en cuenta los siguientes indicadores.

1. Tiempo total de Setup generado por SA para la Linea1.

2. Tiempo total de Setup generado por SA para la Linea2.

3. Tiempo de ejecución del SA para la Línea 1

4. Tiempo de ejecución del SA para la Línea 1

5. Costo en dólares por el Tiempo Total de Setup generado a través de SA.

Estos factores generan indicadores estadísticos del algoritmo que son necesarios para tener una perspectiva de evaluación del comportamiento del Recocido Simulado. Para efectos de esta investigación se calculo la media de los 5 indicadores propuestos con anterioridad y sus respectivas desviaciones estándar. A continuación se muestra un fragmento de la evaluación del algoritmo SA en la tabla 4.2.

CAPÍTULO 4

112

Semana de producción

Número de Trabajos a procesar

Tiempo de cambio L1 Simulated Annealing

(Min)

Tiempo de cambio L2 Simulated Annealing

(Min)

Tiempo de ejecución

del (SA) L1 (Seg)

Tiempo de ejecución del (SA) L2

(Seg)

Tiempo total de

ejecución del (SA)

(Seg)

Tiempo Total de Cambio

Simulated Annealing

Costo total de Set-up

en Dólares (SA)

1 110 123.3 10.5 43 36 79 133.8 $2,542.20

2 147 117.4 47.7 44.3 40.7 85 165.1 $3,136.90

3 124 99.9 2 45.6 25.7 71.3 101.9 $1,936.10

4 105 65 20.6 33.7 32.5 66.2 85.6 $1,626.40

5 140 100.4 33.2 43.4 36.3 79.7 133.6 $2,538.40

6 198 89.7 38 40.4 37.5 77.9 127.7 $2,426.30

7 142 104.2 43.7 36.3 34 70.3 147.9 $2,810.10

8 107 69.5 19.6 28.2 30.3 58.5 89.1 $1,692.90

9 136 73.4 38.6 28.6 29.8 58.4 112 $2,128.00

10 157 93.6 29.4 39.5 31.7 71.2 123 $2,337.00

11 148 123.7 29.5 39.3 32.1 71.4 153.2 $2,910.80

12 113 106.5 60.4 36.4 36.1 72.5 166.9 $3,171.10

13 104 60.9 56.1 28.5 29.6 58.1 117 $2,223.00

14 143 56.2 32.7 34.2 23.5 57.7 88.9 $1,689.10

15 72 39.3 34.6 31.6 37.2 68.8 73.9 $1,404.10

Tabla 4.2 Muestra extraída de la tabla de evaluación de resultados del SA.

La tabla 4.2 muestra un fragmento de los resultados obtenidos en la evaluación del algoritmo de Recocido Simulado. En la primera columna de dicha tabla está contenido el número de la semana evaluada. En la segunda columna de izquierda a derecha se encuentra el número de trabajos a procesar por semana. La tercera columna muestra el tiempo de Setup total obtenido para la línea 1 a partir de SA en minutos. En la cuarta columna se puede observar el tiempo de Setup total obtenido para la línea 1 a partir del algoritmo SA en minutos. La quinta y sexta columna indican el tiempo consumido por el algoritmo para evaluar las muestras; el tiempo de procesamiento se mide en segundos para ambas columnas. En la séptima columna se encuentra la suma del tiempo de Setup obtenido en las dos columnas anteriores, el cual indica el tiempo total de cómputo consumido por el Recocido Simulado. En la octava columna se muestra la suma de la tercera y cuarta columna y esta indica el tiempo total de Setup encontrado para cada una de las semanas evaluadas a través del SA. La última columna representa el costo de los tiempos de Setup obtenidos a partir de la secuenciación de cada semana.

CAPÍTULO 4

113

Los indicadores de las 52 corridas del algoritmo se presentan a continuación en la tabla 4.3. En esta tabla se muestran los totales anuales obtenidos a partir de la aplicación del algoritmo propuesto en esta investigación. Estos parámetros serán tomados en cuanta para compararlos contra sus similares obtenidos a partir del método que se está utilizando actualmente para llevar a cabo el proceso de programación de las líneas.

Indicadores de los trabajos procesados en 52 semanas Suma Promedio Desviación Estándar

Número de trabajos procesados 6979 134.21 28.172

Tiempo Total de Cambio L1 (Min) 4654.7 89.513 25.542

Tiempo Total de Cambio L2 (Min) 1985.2 38.176 21.175

Tiempo de Ejecución SA L1 (Seg) 1990.25 38.274 5.943

Tiempo de Ejecución SA L2 (Seg) 1760.56 33.856 5.483

Costo en Dólares $126,158.10 2426.11 704.43 Tabla 4.3 Indicadores del comportamiento del algoritmo SA

En la tabla 4.3 se pueden observar los resultados obtenidos de la evaluación del comportamiento del algoritmo como datos de análisis se toman en cuenta que el número total de trabajos procesados en el año es de 6979 con un promedio de 134.21 trabajos secuenciados por semana. El tiempo total de Setup tomando en cuenta las dos líneas es de 6639.9; el dato anterior se obtiene sumando el tiempo total de cambio en Línea 1 (4654.7) y el tiempo total de cambio en línea 2 (1985.2). El promedio de tiempo total de Setup por semana para la línea 1 es de 89.513 y para la línea 2 es de 38.176. Por otro lado el tiempo de ejecución acumulado en 52 semanas por las dos líneas de producción es de 3750.81 segundos, el cual se obtiene sumando los tiempo de ejecución para línea 1 y para la línea 2; el tiempo de cómputo promedio requerido para secuenciar los trabajos en la línea 1 fue de 38.274 segundos y para los trabajos de la línea 2 fue de 33.856 segundos. El costo total generado por tiempos de Setup en dólares es de $126,158.10 dólares; dicho costo se obtiene multiplicando el tiempo total de Setup anual que fue de 6639.9 minutos por el costo que tiene parar las líneas de producción por minuto, que de acuerdo con la empresa es de 19 dólares por minuto. Con estos datos obtenidos se puede realizar un análisis comparativo de acuerdo a los datos presentados en la tabla 4.3 con respecto al método actual de secuenciación, este análisis se lleva a cabo en el siguiente punto de estudio.

CAPÍTULO 4

114

4.2 Presentación de los resultados obtenidos.

Una vez que se conocen los resultados generados por el algoritmo de recocido simulado se

compararan con los resultados obtenidos con el método actual de secuenciación. Para llevar a

cabo esta tarea se recolectaron los tiempos totales de Setup consumidos por la programación

ideal que realizo el planeador de la producción. A continuación se muestra la tabla 4.4 en la cual

está contenida una muestra de las mismas semanas de programación que están incluidas en la

tabla 4.2. En la tabla 4.4 se muestran los tiempos totales de Setup para cada semana dependiendo

de la línea en la que fue secuenciada la corrida de producción.

Semana de producción

Número de Trabajos a procesar

Tiempo de cambio L1 Método Actual

Minutos

Tiempo de cambio L2 Método Actual

Minutos

Tiempo Total de Cambio Método Actual

Costo total de Set-up

en Dólares Método Actual

1 110 225 19.3 244.3 4641.7

2 147 239.4 30.3 269.7 5124.3

3 124 293.9 29.3 323.2 6140.8

4 105 171.2 45.9 217.1 4124.9

5 140 165.8 10.5 176.3 3349.7

6 198 207.4 90.2 297.6 5654.4

7 142 259.2 60.8 320 6080

8 107 179.3 41.4 220.7 4193.3

9 136 79.1 80.8 159.9 3038.1

10 157 285.4 38 323.4 6144.6

11 148 355 29 384 7296

12 113 165.9 136.8 302.7 5751.3

13 104 91 67.9 158.9 3019.1

14 143 103.5 28.7 132.2 2511.8

15 72 205.1 24.3 229.4 4358.6

Tabla 4.4 Muestra extraída de la tabla de evaluación de resultados del Método Actual.

En la tabla 4.4 se observa una muestra extraída de la evaluación de la evaluación de las 52

semanas a través del método actual. En la primera columna de izquierda a derecha se observa el

número de la semana de producción que fue evaluada. En la segunda columna se muestra la

cantidad total de trabajos procesados por semana procesados en la planta. En la tercera y cuarta

columna se puede observar el tiempo de Setup consumido por semana para cada una de las

respectivas líneas. En la quinta columna se muestra el tiempo total de Setup utilizado por semana;

CAPÍTULO 4

115

este dato se obtiene sumando los tiempos de Setup de ambas líneas de producción. Por último en

la sexta columna aparece el costo por semana de dicho tiempo total de Setup.

Con los datos obtenidos a partir de las 52 semanas de programación y tomando en cuenta los

mismos criterios de evaluación que se utilizaron en el recocido simulado se construyo la tabla 4.5

que presenta el desempeño del método actual de secuenciación. El único criterio que no aparece

en la tabla 4.5 es el tiempo de ejecución del algoritmo, ya que el reciente método no funciona con

ningún criterio automatizado de decisiones.

Indicadores de los trabajos procesados en 52 semanas Suma Promedio Desviación Estándar

Número de trabajos procesados 6979 134.21 28.172

Tiempo Total de Cambio L1 (Minutos) 10827.8 208.226 70.323


Costo en Dólares $272,663.30 5243.53 1584.455 Tabla 4.5 Indicadores del comportamiento del Método Actual

En la tabla 4.5 se pueden observar los resultados obtenidos de la evaluación del comportamiento del método actual, como datos de análisis se toman en cuenta que el número total de trabajos procesados en el año es de 6979 con un promedio de 134.21 trabajos secuenciados por semana. El tiempo total de Setup de este método, tomando en cuenta las dos líneas es de 14350.7 minutos; el dato anterior se obtiene sumando el tiempo total de cambio en Línea 1 (10827.8) y el tiempo total de cambio en línea 2 (3522.9). Por otro lado el promedio de tiempo total de Setup por semana para la línea 1 es de 208.226 y para la línea 2 es de 67.748. El costo total generado por tiempos de Setup en dólares es de $247,614.90 dólares; dicho costo se obtiene multiplicando el tiempo total de Setup anual que fue de 14350.7 minutos por el costo que tiene parar las líneas de producción por minuto. Estos resultados presentados en la tabla 4.5 son los que serán comparados con los resultados de la tabla 4.2.

CAPÍTULO 4

116

Para poder comparar los resultados generados por los dos métodos de secuenciación se presenta una tabla comparativa de los indicadores de comportamiento de ambos métodos. En la Tabla 4.6 se muestran el cuadro comparativo de dichos indicadores.

Indicadores de los trabajos procesados en 52 semanas

Método Actual Método Propuesto Recocido Simulado

Ahorro

Número de trabajos procesados 6979 6979 0



Costo en Dólares $272,663.30 $126,158.10 $146,505.2 Tabla 4.6 Comparación de Resultados obtenidos

El método propuesto a través del algoritmo de recocido simulado mostro en cada una de las 52

semanas un tiempo menor Total de Setup, comparado con el método actual. Lo anterior se puede

observar comparando los tiempos totales de cambio de las 52 semanas muestreadas y que se

observan en la tabla 4.6 la diferencia para el tiempo de Setup en la línea 1 es de 6173.1 minutos, lo

que representa una disminución del 57.02% respecto al método actual. Los tiempos de Setup de la

línea dos presentan un ahorro de 1537.7 minutos, lo cual representa una rebaja del 43.65%

comparando el método propuesto con el método actual. Debido a lo anterior el costo por el rubro

de Tiempos de Setup se ve minimizado en $146,505.2 dólares, lo anterior representa una

disminución en los costos por 53.74%, para las 52 semanas que se revisaron.

CONCLUSIONES

117

Conclusiones

En el desarrollo de este proyecto de investigación se diseño una herramienta para afrontar el

problema de la programación de la producción para dos líneas de proceso. Concretamente para

poder secuenciar los posibles cambios entre sesenta y cinco familias de trabajos distintas, en un

horizonte de planeación de siete días y tomando en cuenta las restricciones del sistema

productivo.

Con esta herramienta se modeló la problemática planteada mediante un algoritmo de balanceo de

líneas y el algoritmo de recocido simulado (Simulated Annealing), con los cuales se proporcionan

soluciones que permiten minimizar el tiempo de procesamiento del último trabajo (Makespan), en

tiempos de cómputo relativamente cortos. Por otro lado de acuerdo a los resultados obtenidos del

comportamiento de la herramienta, esta se presenta como una mejor alternativa para efectuar la

tarea de la programación de la producción en ambas líneas de la planta de aislamientos de OCM.

En cuanto a los objetivos de desarrollo de la investigación se tiene que:

1. Se detecto que el problema podía ser reducido a secuenciar los cambios entre 65 familias

de trabajos distintas, mas sin embargo la complejidad del problema no cambió, siendo

este un problema de tipo NP.

2. Se formulo y resolvió el problema de la secuenciación de trabajos en dos líneas de

producción en el caso particular de OCM.

3. Se implemento el algoritmo de recocido simulado y de balanceo de líneas para encontrar

las secuencias de los trabajos.

4. Se diseño una interfaz en Excel con programación en Visual Basic que contiene los

algoritmos necesarios para llevar a cabo la programación de las líneas.

5. Se demostró mediante la comparación histórica del método actual contra la propuesta

desarrollada en el actual trabajo, que este ultimo ofrece mejores secuencias de

producción, que permiten minimizar de forma eficiente los tiempos de cambio totales en

ambas líneas de producción.

6. Se encontró que la implementación del modelo propuesto en este trabajo tiene un

impacto en la reducción de los costos generados por los cambios en la secuencia de

producción.

CONCLUSIONES

118

7. Los tiempos de cómputo durante las pruebas demostraron ser factibles y cortos, lo que

permite su aplicación dentro de la empresa en un futuro.

En cuanto a trabajos futuros se refiere, se propone modelar el problema planteado en este trabajo

tomando en cuenta los tiempos muertos generados por el mantenimiento de los equipos. A

demás de considerar las probabilidades de falla de las líneas al momento de secuenciar los

trabajos.

También se puede considerar la implementación de diferentes algoritmos heurísticos para la

resolución del mismo problema y evaluar cuál de estos ofrece mejores resultados, en cuanto a

tiempo de cómputo y la minimización de tiempos de cambio en las líneas de producción. Es

posible proponer un estudio de las constantes del sistema de enfriamiento del recocido simulado

para definir cuales se adecuan mejor al problema de estudio en este trabajo.

BIBLIOGRAFÍA

119

Bibliografía

Alvarez, V., & Tamarit, J. (1989). Heuristics Algorithmsfor resource-constrained project scheduling:

a review and an empirical analysis. Advances in Project Scheduling .

Ballou. (2004). Logistica Administración de la cadena de suministro. México: Pearson Educación.

Bringer, P., Hansen, P., Mladenovic, N., & Tillard, E. (2000). Improvments and comparision of

heuristics for solving the multisource weber problem. Operation Research , 444-460.

Brucker, P. (2007). Scheduling Algorithms. NY: Springer .

Brucker, P., & Kravchenko, S. (2004). Scheduling jobs with equal processing times and time

window on identical parallel machine. OSM Reihe P, Heft 257, Universitat Osnabruck, Fachbereich

Mathematik/ Informatik .

Brucker, P., & SA, K. (2005). Scheduling jobs with release times on parallel machines to minimize

total tardiness. OSM Reihe P, Heft 258, Universitat Osnabruck, Fachbereich

Mathematik/Informatik .

Consejo de la Dirección Logística. (s.f.). Council of Logistics Management. Recuperado el 23 de 03

de 2010, de De las normas del Consejo de la Dirección Logistica: http://www.clm1.org

Cook, S. (1971). The complexity of theorem-proving procedures. Procedings of the 3rd Annual ACM

Symposium on Theory of Computing , 151-158.

Cooper, D. (1976). Heuristics for scheduling resource-constrained . Managmente Science 22 .

Davis, E., & Patterson, J. (1975). A comparison of heuristics and Optimal solution. Management

Science .

Doctker, J. (2000). "Basics of fulfillment", Proceceedings of the Council of Logistics Management.

Council of Logistics Management , 356.

Dueck, G., & Scheuer, T. (1990). A general purpose optimization algorithm superior to Simulated

Annealing. Journal of Computational Physics , 204-208.

Eglese, R. (1990). Simulated Annealing: A tool for operational Research . European Journal of

Operational Research , 271-281.

Frederick, H., & Liberman, G. (2002). Investigación de Operaciones. Mc Graw Hill.

Graham, R., Lawler, E., Lenstra, J., & Kan, A. R. (1979). Optimization and approximation in

deterministic sequencing and scheduling. A survey. Annals of Discrete Mathematics , 287-326.

BIBLIOGRAFÍA

120

Hansen, P., Mladenovic, & Brito, P. (2001). Variable neighborhood descomposition search. Journal

of Heuristics , 335-350.

Heskett, J. (1994). Controlling Customer Logistics Service. International Journal of Physical

Dsitribution and Logistics Management , 4.

Ignall, E., & Schrage, L. (1965). Application of the branch-and-bound algorithm to some flow shop

problems. Operation Research 13 , 400-412.

Innis, D., & LaLonde, B. (1994). Customer Service: The Key to Customer Satisfaction, Customer

Loyalty and Market Share. Journal of Business Logistics , 1-27.

Jackson, J. (1955). Scheduling a production line to minimize maximun tardiness. Management

Science Resarch Project, University of California, Los Angeles , 43.

Jay Sterling, D. L. (1989). Customer Service Research; Past, Present and Future. International

Journal of Physical Distribution and Material Management , 17.

John T Mentezer, W. D. (Vol 22 de 2001). Defining Supply Chain Managment. Journal of Business

Logistics , págs. 1-25.

Johnson, S. (1954). Optimal two and three-stage production schedules with setup times included.

Naval Resarch Logistic , 61-67.

Jose, S. G. (2001). Programación Matematica. España: Diaz de Santos, S.A.

Karp, R. (1972). Reducibility among combinatorial problems. Complexity of computer computations

(Proc. Sympos, IBM) , 85-103.

Keebler, J., & Manrodt, K. (2002). The State of Logistics Performance Mesurement. Council of

Logistics Management , 275-281.

Kelly, J., & Walker, M. (1959). Critical path Planning and Scheduling. Proceedings of the Eastern

Joint Computer Conference.

Khachiyan, L. (1979). A polynomial algorithm in linear programing. Doklasy Akademii Nauk SSSR ,

244.

Koulamas, C., Antony, S., & R, J. (1994). A survey of Simulated Annealing Aplications to Operations

Research Problems. Omega 22 , 41-56.

Kyj, L. K. (1994). Customer Service: Differentiation in International Markets. International Journal

of Physical Distribution and Logistics Management , 41.

Laarhoven, v., & Aarts. (1987). Simulated annealing: Theory and applications. D. Reidel Publishing

Company, Dordrecht .

BIBLIOGRAFÍA

121

Labetoulle, J., EL, L., Lenstra, J., & Kan, R. (1984). Preemptive scheduling of uniform machines

subject to release dates. Progress in combinatorial optimization (Academic Press, Torornto) , 245-

261.

Ladhari, T., & Haouari, M. (2005). A computational study of permutation flow shop problem based

on tight lower bound. Computers and Operation Research 32 , 1831-1847.

Lawrence, S. (1984). An experimental investigation of heuristic scheduling techniques. GSIA

Carnegie-Mellon, Pittsburg .

Lenstra, H. (1983). Integer programming with a fixed number of variables. Mathematics of

Operation Resarch , 538-548.

Leung, J. Y.-T. (2004). Handbook of Scheduling ( Algorithms, Models, and Performance analisis) .

New York: Chapman and Hall.

Levin, L. (1973). Universal sorting problems. Problemy Peredachi Informatsii , 265-266.

Lomnicki, Z. (1965). A branch and bound algorithm for the exact solution of three machine

scheduling problems. Operational Research Quarterly , 89-100.

Mateus, R., Martín, G. R., & Panos, M. ,. (2007). Solving parallel machines problems with

sequence-dependent setup times using variable neighbourhood search. Journal of Management

Mathematics , 101-115.

Mladenovic, N., Petrovic, J., Kovacevic-Vujcic, & Cangallovic, M. (2004). Solving spread spectrum

radar polyphase code design problem by tabu search and variable neighborhood search. European

Journal of Operation Research .

N, M. (1995). A variable neighborhood algorithm- a new metaheuristcs for combinatorial

optimizatión. Abstracs of Papers at Optimization Days , 112.

N, M., Rosenbluth, W., Rosenbluth, N., & Teller, M. (1953). Equation os State Calculations by Very

Fast Computing Machines. Chem. Phys , 21.

Nawaz, M. E., & Ham, I. (1983). A heuristic algorithm for the m-machines, n-job flow-shop

sequencing problem . Omega , 91-95.

Nichols, R. B. (1999). Introduccion to Supply Chain Managment. New York: Prentice Hall.

Oak Brook, IL: Council of Logistics Management). (s.f.). Careers in Logistics. 3.

P, H., & N, M. (207-226). Variable neighborhood search for the p-median. Science , 1997.

P, M., & Fontanari, J. (1990). Stochastic Versus Detrministic Update in Simulated Annealing.

Physics Letters A , 204-208.

BIBLIOGRAFÍA

122

Pinedo, M. (1995). Scheduling: Theory, Algorithms and Systems. N.J: Prentice Hall.

Radhakrishnan, & Ventura, J. (2000). Simulated annealing for parallel machine scheduling with

earliness_tardiness penalties and sequence dependent set-up times. International Journal of

Production Research , 2233-2252.

Rinnooy, K. (1976). Machine Scheduling Problems: Classification, Complexity and Computations.

Martinus Nijhoff, The Hague .

S, K., Jr, G., & MP, V. (1983). Optimizatión by Simulated Annealing. Science .

Simchi Levi David, P. K. (2003). Desisgning and Managing The Supply Chain (Concepts, Strategies,

and Case Studies). Mc Graw- Hill.

Smith, W. (1956). Various optimizers for single stage production. Naval Resarch Logistics , 59-66.

ANEXO

123

Anexo

Sintaxis del código requerido para la programación del Recocido Simulado

Algoritmos (1,2) en código Visual Basic

Private Sub CommandButton1_Click()

Comienza Algoritmo 1

Dim CuentaA As Range

Dim contadorB

Set CuentaA = Sheets(1).Range("A5:A30000")

contadorB = WorksheetFunction.CountA(CuentaA)

Cells(1, 2) = Val(contadorB)

n = Val(Cells(1, 2))

ActiveWorkbook.Worksheets("Balance").Sort.SortFields.Clear

ActiveWorkbook.Worksheets("Balance").Sort.SortFields.Add Key:=Range(Cells(5, 7), Cells(4 + n, 7)), _

SortOn:=xlSortOnValues, Order:=xlAscending, DataOption:=xlSortNormal

ActiveWorkbook.Worksheets("Balance").Sort.SortFields.Add Key:=Range(Cells(5, 10), Cells(4 + n, 10)), _

SortOn:=xlSortOnValues, Order:=xlDescending, DataOption:=xlSortNormal

With ActiveWorkbook.Worksheets("Balance").Sort

.SetRange Range(Cells(5, 1), Cells(4 + n, 11))

.Header = xlGuess

.MatchCase = False

.Orientation = xlTopToBottom

.SortMethod = xlPinYin

.Apply

End With

'Este ciclo FOR asigna los trabajos que pueden ser procesados en AMBAS LINEAS dependiendo de las cargas

'si la carga de trabajo en horas es mayor en alguna de las dos líneas asigna el siguiente trabajo

ANEXO

124

'a la línea con menos carga

For j = 0 To n - 1

Worksheets("Balance").Activate

Cells(5 + j, 14) = Val((Cells(5 + j, 1)))

Cells(5 + j, 15) = ((Cells(5 + j, 2)))

Cells(5 + j, 16) = ((Cells(5 + j, 3)))


Cells(5 + j, 18) = ((Cells(5 + j, 5)))





Cells(5 + j, 24) = DateValue((Cells(5 + j, 11)))

If Cells(5 + j, 7) = 1 Then

Cells(5 + j, 20) = 1

Suma1 = Suma1 + Cells(5 + j, 4)

Else

If Cells(5 + j, 7) = 2 Then

Cells(5 + j, 20) = 2

suma2 = suma2 + Cells(5 + j, 4)

Else

If Cells(5 + j, 7) = "1,2" Then

suma3 = Val(Cells(2, 23))

Suma4 = Val(Cells(3, 23))

If suma3 < Suma4 Then

Cells(5 + j, 20) = 1

End If

If suma3 >= Suma4 Then

ANEXO

125

Cells(5 + j, 20) = 2

End If

End If

End If

End If

Next j

'Reparte los trabajos a una hoja de Excel, dependiendo de la línea que se le asigno

'Declaración de variables

Comienza algoritmo 2

Dim Vector1 As Range

Dim contadorD

Set Vector1 = Sheets(1).Range("T5:T8000")

contadorD = WorksheetFunction.CountA(Vector1)

'El ciclo FOR identifica a que linea pertenecen los trabajos y los manda a la hoja (Linea 1 o Linea2)

'dependiendo de su estatus

For Each Celda In Sheets(1).Range(Cells(5, 20), Cells(4 + contadorD, 20))

If Celda.Value = 1 Then

Sheets("Linea 1").Range("B" & Rows.Count).End(xlUp)(2) = Celda.Offset(0, -6).Value

Sheets("Linea 1").Range("C" & Rows.Count).End(xlUp)(2) = Celda.Offset(0, -5).Value

Sheets("Linea 1").Range("D" & Rows.Count).End(xlUp)(2) = Celda.Offset(0, -4).Value

Sheets("Linea 1").Range("E" & Rows.Count).End(xlUp)(2) = Celda.Offset(0, -3).Value

Sheets("Linea 1").Range("F" & Rows.Count).End(xlUp)(2) = Celda.Offset(0, -2).Value

Sheets("Linea 1").Range("G" & Rows.Count).End(xlUp)(2) = Celda.Offset(0, -1).Value

Sheets("Linea 1").Range("H" & Rows.Count).End(xlUp)(2) = Celda.Offset(0, 0).Value

Sheets("Linea 1").Range("I" & Rows.Count).End(xlUp)(2) = Celda.Offset(0, 1).Value

Sheets("Linea 1").Range("J" & Rows.Count).End(xlUp)(2) = Celda.Offset(0, 2).Value

Sheets("Linea 1").Range("K" & Rows.Count).End(xlUp)(2) = Celda.Offset(0, 3).Value

Sheets("Linea 1").Range("L" & Rows.Count).End(xlUp)(2) = Celda.Offset(0, 4).Value

ANEXO

126

Else

If Celda.Value = 2 Then

Sheets("Linea 2").Range("B" & Rows.Count).End(xlUp)(2) = Celda.Offset(0, -6).Value

Sheets("Linea 2").Range("C" & Rows.Count).End(xlUp)(2) = Celda.Offset(0, -5).Value

Sheets("Linea 2").Range("D" & Rows.Count).End(xlUp)(2) = Celda.Offset(0, -4).Value

Sheets("Linea 2").Range("E" & Rows.Count).End(xlUp)(2) = Celda.Offset(0, -3).Value

Sheets("Linea 2").Range("F" & Rows.Count).End(xlUp)(2) = Celda.Offset(0, -2).Value

Sheets("Linea 2").Range("G" & Rows.Count).End(xlUp)(2) = Celda.Offset(0, -1).Value

Sheets("Linea 2").Range("H" & Rows.Count).End(xlUp)(2) = Celda.Offset(0, 0).Value

Sheets("Linea 2").Range("I" & Rows.Count).End(xlUp)(2) = Celda.Offset(0, 1).Value

Sheets("Linea 2").Range("J" & Rows.Count).End(xlUp)(2) = Celda.Offset(0, 2).Value

Sheets("Linea 2").Range("K" & Rows.Count).End(xlUp)(2) = Celda.Offset(0, 3).Value

Sheets("Linea 2").Range("L" & Rows.Count).End(xlUp)(2) = Celda.Offset(0, 4).Value

End If

End If

Next Celda

'Ordena los trabajos de la Línea 1 por Due date y después genera un Batch

'por familia, los elementos de este, se ordenan por espesor del producto de mayor a menor

ActiveWorkbook.Worksheets("Linea 1").Sort.SortFields.Clear

ActiveWorkbook.Worksheets("Linea 1").Sort.SortFields.Add Key:=Range("L2:L10000"), _


ActiveWorkbook.Worksheets("Linea 1").Sort.SortFields.Add Key:=Range("E2:E10000"), _


ActiveWorkbook.Worksheets("Linea 1").Sort.SortFields.Add Key:=Range("C2:C10000"), _


With ActiveWorkbook.Worksheets("Linea 1").Sort

.SetRange Range("B2:L10000")

.Header = xlGuess

.MatchCase = False

ANEXO

127



.Apply

End With

'Ordena los trabajos de la Línea 2 por Due date y después genera un Batch

'por familia, los elementos de este, se ordenan por espesor del producto de mayor a menor


ActiveWorkbook.Worksheets("Linea 2").Sort.SortFields.Add Key:=Range("L2:L10000"), _


ActiveWorkbook.Worksheets("Linea 2").Sort.SortFields.Add Key:=Range("E2:E10000"), _


ActiveWorkbook.Worksheets("Linea 2").Sort.SortFields.Add Key:=Range("C2:C10000"), _



.SetRange Range("B2:L10000")

.Header = xlGuess

.MatchCase = False



.Apply

End With

'Modulos para dar formato tanto a Linea 1 como Linea 2

'en este caso Mover1(Modulo1) y Mover2 (Modulo2) en la carpeta Módulos de VBAProject

Mover1

Mover2

Sheets(1).Select

End Sub

ANEXO

128

Algoritmos 3 en código VBA

Private Sub CommandButton1_Click()

'Scheduler V1 para Línea 1

'Algoritmo para la calendarización de los trabajos en Línea (1,2)

'1) Declaración y Dimensionamiento de Variables Iniciales


Dim cont1

Set Vector1 = Sheets(2).Range("B3:B30000")

cont1 = WorksheetFunction.CountA(Vector1) + 2

Li = 2

Ls = WorksheetFunction.CountIf(Range(Cells(3, 12), Cells(cont1, 12)), Cells(3, 12)) + 2

Sheets(4).Range("G3:K900").Clear

'2) Este Ciclo For determina cuantos días diferentes existen en el Horizonte de planeación

For Dd = 1 To cont1

Do Until Day(Cells(2 + Dd, 12)) <> Day(Cells(2 + (Dd + 1), 12))

suma = suma + 1

Exit Do

Loop

Next Dd

DiaF = cont1 - suma

'3) En esta parte (For Dia1 To Diaf) se delimita el algoritmo para correrlo desde el primer día en el horizonte

' de programación hasta el último día

For Dia1 = 1 To DiaF

'Declaración de valores iniciales para variables que son criticas

'en la ejecución de este Ciclo For

Suma1 = 0

Suma4 = 0

Suma5 = 0

ANEXO

129

Resta = 0

Resta1 = 0

Hora1 = 7

Hora2 = 7

Cont2 = WorksheetFunction.CountA(Range("B3:B30000")) + 10

'Este ciclo (For J) permite reconocer y variar el límite que existe entre cada uno de los Días

'dependiendo de la capacidad disponible (Hrs)

For j = Li To (Ls - 1)

'El bucle (Do) permite identificar si la capacidad por día ha sido rebasada y de ser asi

'reasignar los trabajos hacia adelante en el Horizonte de Tiempo

Do Until Suma4 > 24

Suma4 = Suma4 + Cells(1 + j, 11)

If Day(Cells(1 + (j - 1), 12)) = Day(Cells(1 + j, 12)) Then

Suma5 = Suma5 + Cells(1 + (j - 1), 11)

End If

If Suma4 > 24 Then

Resta = Suma4 - 24

Resta1 = Suma4 - Suma5

If Suma5 <> 24 Then

Range(Cells(1 + (j + 1), 1), Cells(cont1 + (j + 1), 12)).Select

Selection.Cut Destination:=Range(Cells(1 + (j + 2), 1), Cells(cont1 + (j + 2), 12))

Range(Cells(1 + (j + 2), 1), Cells(cont1 + (j + 2), 12)).Select

Cells(1 + (j + 1), 1) = Val(Cells(1 + j, 1))


Cells(1 + (j + 1), 3) = (Cells(1 + j, 3))

Cells(1 + (j + 1), 4) = (Cells(1 + j, 4))


Cells(1 + (j + 1), 6) = (Cells(1 + j, 6))


ANEXO

130


Cells(1 + (j + 1), 9) = Round(((Val(Cells(1 + j, 9))) * Resta) / (Resta1), 0)

Cells(1 + (j + 1), 10) = Round(((Val(Cells(1 + j, 10))) * Resta) / (Resta1), 3)

Cells(1 + j, 11) = (Resta1 - Resta)

Cells(1 + (j + 1), 11) = Resta

Cells(1 + (j + 1), 12) = DateAdd("d", 1, DateValue(Cells(1 + j, 12)))

Cells(1 + j, 9) = Round(((Val(Cells(1 + (j + 1), 9))) * (Resta1 - Resta)) / (Resta), 0)

Cells(1 + j, 10) = Round(((Val(Cells(1 + (j + 1), 10))) * (Resta1 - Resta)) / (Resta), 3)

End If

If Suma5 = 24 Then

Cells(1 + j, 12) = DateAdd("d", 1, DateValue(Cells(1 + (j - 1), 12)))

For A = j To (Ls - 1)

Cells(1 + A, 12) = DateValue(Cells(1 + j, 12))

Next A

End If

For i = 2 To Ls

If Day(Cells(1 + (j + i), 12)) = Day(Cells(1 + j, 12)) Then

Cells(1 + (j + i), 12) = DateValue(Cells(1 + (j + 1), 12))

End If

Next i

End If

Exit Do

Loop 'Finaliza el Bucle de instrucciones (Do)

'El siguiente conjunto de Controladores Lógicos (If) permiten establecer los horarios

'de producción

Hora1 = Hora1 + Cells(1 + j, 11)

If Hora1 > 24 Then

Hora1 = Hora1 - 24

End I

ANEXO

131

If Hora1 > 0 And Hora1 <= 12 Then

Mer = "am"

Else

Mer = "pm"

End If

If Day(Cells(1 + (j - 1), 12)) <> Day(Cells(1 + j, 12)) Then

Cells(1 + j, 13) = 7 & "am" & " a " & Round(Hora1, 2) & Mer

End If

If Day(Cells(1 + (j - 1), 12)) = Day(Cells(1 + j, 12)) Then

Hora2 = Hora2 + Cells(1 + (j - 1), 11)

If Hora2 > 24 Then

Hora2 = Hora2 - 24

End If

If Hora2 > 0 And Hora2 <= 12 Then

Ma = "am"

Else

Ma = "pm"

End If

Cells(1 + j, 13) = Round(Hora2, 2) & Ma & " a " & Round(Hora1, 2) & Mer

End If

Next j 'Finaliza (For J)

Cap1 = WorksheetFunction.SumIf(Range(Cells(Li + 1, 12), Cells(Cont2, 12)), Cells(Li + 1, 12), _

Range(Cells(Li + 1, 11), Cells(Cont2, 11))) 'da la capacidad utilizada por dia en Hrs

Cap2 = WorksheetFunction.SumIf(Range(Cells(Li + 1, 12), Cells(Cont2, 12)), Cells(Li + 1, 12), _

Range(Cells(Li + 1, 10), Cells(Cont2, 10))) ' da la capcidad utilizada por dia en Toneladas

'Conjunto de instrucciones que permiten identificar donde empieza el nuevo día de planeación

'y hasta donde terminan los trabajos para el nuevo día

ANEXO

132

b = WorksheetFunction.CountA(Range(Cells(3, 12), Cells(Li, 12)))

If Dia1 > 1 Then

Hb = WorksheetFunction.CountIf(Range(Cells(Li + 1, 12), Cells(Cont2, 12)), Cells((Li + 1), 12)) + b

Sa = WorksheetFunction.CountIf(Range(Cells(Li + 1, 12), Cells(Cont2, 12)), Cells((Li + 1), 12))

Ub = WorksheetFunction.CountIf(Range(Cells(3, 12), Cells(Cont2, 12)), Cells((Li + 1) + Sa, 12))

Else

Hb = WorksheetFunction.CountIf(Range(Cells(Li + 1, 12), Cells(Cont2, 12)), Cells((Li + 1), 12))

Ub = WorksheetFunction.CountIf(Range(Cells(3, 12), Cells(Cont2, 12)), Cells(((Li + 1) + Hb), 12))

End If

'Con el siguiente código se construye el Reporte para la Línea 1

Sheets(4).Cells(Li + 1, 7) = Cells(Li + 1, 12)

Sheets(4).Cells(Li + 1, 8) = Cap1

Sheets(4).Cells(Li + 1, 9) = Cap2

Sheets(4).Cells(Li + 1, 10) = 24 - Cap1

Ton1 = (24 * Cap2) / (Cap1)

CapTon = Round((Ton1 - Cap2), 2)

If CapTon > 0.1 Then

Sheets(4).Cells(Li + 1, 11) = CapTon

Else

Sheets(4).Cells(Li + 1, 11) = 0

End If

Li = Hb + 2 ' es donde empieza el nuevo Día1

Ls = (Li + Ub) 'es donde terminan los trabajos para ese nuevo Día1

Next Dia1 'Finaliza Ciclo (For Dia1)

FormatoL1

Formato1 'Formato (Modulo3 de VBA) para el Reporte L1

End Sub

ANEXO

133

Private Sub UserForm_Activate()

'Rutina que permite cargar los datos del sistema de enfriamiento

txtTI.Text = 1

txtFRT.Text = 0.9

txtNIT.Text = 5

txtNT.Text = 50

End Sub

Sub UpdateProgress(Pct)

'Rutina que ejecuta la barra de progreso

With AnnealingForm1

.FrameProgress.Caption = Format(Pct, "0%")

.LabelProgress.Width = Pct * (.FrameProgress.Width - 10)

.Repaint

End With

End Sub

Private Sub cmdExit_Click()

'Rutina que ejecuta la barra de progreso

End

End Sub

El siguiente programa es el núcleo del modulo ya que aquí están contenidas todas las

instrucciones requeridas para generar una secuencia factible. Esta parte del código es la que se

activa cuando el botón “Run Optimisation” es presionado.

Private Sub cmdOptimisation_Click()

'Programa Principal para SA

Close

Me.Height = 289.5

'Declaración de Variables para correr el Simulated Annealing

ANEXO

134

Dim TI As Double, FRT

Dim NIT As Integer, NT

TI = txtTI.Text

FRT = txtFRT.Text

NIT = txtNIT.Text

NT = txtNT.Text

Sheets(4).Range("A2:D100").Clear

'Declaración de Variables para Ejecutar el algoritmo en todos los días del horizonte de planeación


Dim cont1

Set Vector1 = Sheets(2).Range("B3:B30000")

cont1 = WorksheetFunction.CountA(Vector1) + 2

Li = 3

Dia2 = 2

Ls = WorksheetFunction.CountIf(Sheets(2).Range(Sheets(2).Cells(3, 12), Sheets(2).Cells(cont1, 12)), _

Sheets(2).Cells(3, 12)) + 2

'El siguiente ciclo (For) permite identificar cuantos dias hay en el Horizonte de Planeación

For Dd = 1 To cont1

Do Until Day(Sheets(2).Cells(2 + Dd, 12)) <> Day(Sheets(2).Cells(2 + (Dd + 1), 12))

suma = suma + 1

Exit Do

Loop

Next Dd

DiaF = cont1 - suma

'3) En esta parte (For Dia1 To Diaf) se delimita el algoritmo para correrlo desde el primer día en el horizonte

' de programación hasta el último día

For Dia1 = 1 To DiaF

'En esta parte (For s to Ls) reconoce los trabajos que tienen que ser procesados

ANEXO

135

'en cada uno de los días de producción

For s = Li To Ls

If Sheets(2).Cells((s + 1), 5) = Sheets(2).Cells(s, 5) And Sheets(2).Cells((s + 1), 5) <> _

Sheets(2).Cells((s - 1), 5) Then

Sheets(6).Cells(3 + s, 1) = Sheets(2).Cells(s, 5)

Sheets(6).Cells(2, s) = Sheets(2).Cells(s, 5)

Else

If Sheets(2).Cells(s, 5) <> Sheets(2).Cells((s + 1), 5) And Sheets(2).Cells(s, 5) <> _

Sheets(2).Cells((s - 1), 5) Then



End If

If Dia1 > 1 Then

If Sheets(2).Cells(s, 5) = Sheets(2).Cells(s - 1, 5) And Day(Sheets(2).Cells(s, 12)) <> _

Day(Sheets(2).Cells(s - 1, 12)) Then



End If

End If

If Sheets(2).Cells(s, 5) <> Sheets(2).Cells((s - 1), 5) Then



End If

End If

Li = Ls + 1

ActiveWorkbook.Worksheets("Solver").Sort.SortFields.Clear

ActiveWorkbook.Worksheets("Solver").Sort.SortFields.Add Key:=Range("A4:A1000"), _


With ActiveWorkbook.Worksheets("Solver").Sort

ANEXO

136

.SetRange Range("A4:A1000")

.Header = xlGuess

.MatchCase = False



.Apply

End With


ActiveWorkbook.Worksheets("Solver").Sort.SortFields.Add Key:=Range("B2:HZ2"), _



.SetRange Range("B2:HZ2")

.Header = xlGuess

.MatchCase = False

.Orientation = xlLeftToRight


.Apply

End With

For Columna = 1 To 65

Sheets(6).Cells(3, 1 + Columna) = Val(Columna)

Next Columna

Next s

Algoritmo 4

'Declaración de variables para la obtención de la solución inicial

Dim MatrizA As Range

Dim contadorA

Set MatrizA = Sheets(6).Range("A4:A30000")

contadorA = WorksheetFunction.CountA(MatrizA)

Sheets(6).Cells(1, 2) = "Matriz de " & Val(contadorA) & "x" & Val(contadorA)

ANEXO

137

n = Val(contadorA)

m = Val(contadorA)

'Comienza algoritmo 4

For Si = 1 To n

Sheets(6).Range(Sheets(6).Cells(4, 2 + n), Sheets(6).Cells(3 + n, 2 + n)).Clear

If Si = 1 Then

MinC = 1000

Else

If Solin < 0 Then

MinC = Ruta

Else

MinC = MinC

End If

End If

Ruta = 0

For C = 1 To n

For A = 0 To n - 1

For Each Cel In Sheets(6).Cells(3 + C, 2 + A)

Co1 = WorksheetFunction.Match(Sheets(6).Cells(3 + C, 1), Sheets(7).Range("A2:A100"), 0)

Co2 = WorksheetFunction.Match(Sheets(6).Cells(2, 2 + A), Sheets(7).Range("A2:BN2"), 0)

Cel.Value = WorksheetFunction.Index(Sheets(7).Range("A2:BN100"), Co1, Co2)

Next Cel

Next A

Next C

r = Si

'El siguiente ciclo For resuelve la matriz de Set up para cada una de las filas

For k = 1 To n - 1

Minimo = WorksheetFunction.Min(Sheets(6).Range(Sheets(6).Cells(3 + r, 2), Sheets(6).Cells(3 + r, 1 + n)))

ANEXO

138

CountM = WorksheetFunction.CountIf(Sheets(6).Range(Sheets(6).Cells(3 + r, 2), Sheets(6).Cells(3 + r, 1 + n)), Minimo)

If CountM > 1 Then

Sumaq = 0

For Mi = 0 To n - 1

If Sheets(6).Cells(3 + r, 2 + Mi) = Minimo Then

Sheets(6).Cells(3 + r, 2 + Mi) = Minimo + Sumaq

Sumaq = Minimo + Sumaq

End If

Next Mi

End If

Sheets(6).Cells(3 + r, 2 + n) = Val(k)

If k = 1 Then

Can = Minimo

End If

For Each Celda In Sheets(6).Range(Sheets(6).Cells(3 + r, 2), Sheets(6).Cells(3 + r, 1 + n))

If Celda.Value <> Minimo Then

Celda.Value = "M"

For j = 1 To n

For Each Celda1 In Sheets(6).Cells(3 + j, 1 + r)

Celda1.Value = "M"

Next Celda1

Next j

End If

Next Celda

For i = 1 To n

If Sheets(6).Cells(3 + r, 1 + i) = Minimo Then

r = Sheets(6).Cells(3, 1 + i)

Exit For

ANEXO

139

End If

Next i

Ruta = Ruta + Minimo

Min1 = Ruta - Minimo

Can = Ruta - Min1

Next k

Solin = Ruta - MinC

For F = 1 To n

If Sheets(6).Cells(3 + F, 2 + n) = 0 Then

Sheets(6).Cells(3 + F, 2 + n) = n

End If

If Solin <= 0 Then

Sheets(6).Cells(3 + F, 3 + n) = Sheets(6).Cells(3 + F, 1)

End If

Next F

If Solin <= 0 Then


ActiveWorkbook.Worksheets("Solver").Sort.SortFields.Add Key:=Range(Cells(4, 2 + n), Cells(3 + n, 2 + n)), _



.SetRange Range(Cells(4, 2 + n), Cells(3 + n, 3 + n))

.Header = xlGuess

.MatchCase = False



.Apply

End With

End If

For Ff = 1 To n

ANEXO

140

Sheets(6).Cells(3 + Ff, 2 + n) = Ff

Next Ff

If Solin <= 0 Then

Sheets(6).Cells(1, 6) = Ruta

End If

Sheets(6).Cells(1, 5) = Ruta

Sheets(6).Cells(1, 3) = r

Sheets(6).Cells(1, 4) = Minimo

Next Si 'termina solución inicial

Algoritmo SA (6)

'Comienza Recocido Simulado

For Fi = 1 To n

Sheets(6).Cells(3 + Fi, 5 + n) = Sheets(6).Cells(3 + Fi, 3 + n)

Next Fi

MinC = Sheets(6).Cells(1, 6)

CS = MinC

Tin = TI

For T = 1 To NT

For NumI = 1 To NIT

If T = 1 And NumI = 1 Then

For TC = 1 To n - 1

For Each CelTC In Sheets(6).Cells(3 + (TC + 1), 7 + n)

CoLL1 = WorksheetFunction.Match(Sheets(6).Cells(3 + TC, 5 + n), Sheets(7).Range("A2:A100") , 0)

CoLL2 = WorksheetFunction.Match(Sheets(6).Cells(3 + (TC + 1), 5 + n), Sheets(7).Range("A2:BN2"), 0)

CelTC.Value = WorksheetFunction.Index(Sheets(7).Range("A2:BN100") , CoLL1, CoLL2)

Next CelTC

Next TC

For Fin = 1 To n

Sheets(6).Cells(3 + Fin, 4 + n) = Sheets(6).Cells(3 + Fin, 7 + n)

ANEXO

141

Next Fin

End If

MaxST = WorksheetFunction.Max(Sheets(6).Range(Sheets(6).Cells(4, 7 + n), Sheets(6).Cells(3 + n, 7 + n)))

Algoritmo 5

'El siguiente ciclo for ejecuta el mecanismo de perturbación

For Rj = 1 To n

Dec = Rnd

If Rj <> n Then

If Sheets(6).Cells(3 + Rj, 7 + n) = MaxST Then

If Dec <= 0.5 Then

Sheets(6).Cells(3 + Rj, 6 + n) = Rj - 2

Else

Sheets(6).Cells(3 + Rj, 6 + n) = Rj + 2

End If

Else

Sheets(6).Cells(3 + Rj, 6 + n) = Rj

End If

Else

If Sheets(6).Cells(3 + Rj, 7 + n) = MaxST Then

If Dec <= 0.5 Then

Sheets(6).Cells(3 + Rj, 6 + n) = n - (n + 1)

Else

Sheets(6).Cells(3 + Rj, 6 + n) = Rj - 2

End If

Else

Sheets(6).Cells(3 + Rj, 6 + n) = Rj

End If

End If

Next Rj

ANEXO

142


ActiveWorkbook.Worksheets("Solver").Sort.SortFields.Add Key:=Range(Cells(4, 6 + n), Cells(3 + n, 6 + n)), _



.SetRange Range(Cells(4, 5 + n), Cells(3 + n, 6 + n))

.Header = xlGuess

.MatchCase = False



.Apply

End With

For CC = 1 To n - 1

For Each CelCC In Sheets(6).Cells(3 + (CC + 1), 7 + n)

CoL1 = WorksheetFunction.Match(Sheets(6).Cells(3 + CC, 5 + n), Sheets(7).Range("A2:A100") , 0)

CoL2 = WorksheetFunction.Match(Sheets(6).Cells(3 + (CC + 1), 5 + n), Sheets(7).Range("A2:BN2"), 0)

CelCC.Value = WorksheetFunction.Index(Sheets(7).Range("A2:BN100"), CoL1, CoL2)

Next CelCC

Next CC

CS0 = WorksheetFunction.Sum(Sheets(6).Range(Sheets(6).Cells(4, 7 + n), Sheets(6).Cells(3 + n, 7 + n)))

If CS0 < MinC Then

For JI = 1 To n

Sheets(6).Cells(3 + JI, 4 + n) = Sheets(6).Cells(3 + JI, 7 + n)

Sheets(6).Cells(3 + JI, 3 + n) = Sheets(6).Cells(3 + JI, 5 + n)

Next JI

MinC = CS0

End If

DeltaC = CS0 - CS 'Evaluación de la solución actual

If DeltaC < 0 Then

CS = CS0

ANEXO

143

Else

X = Rnd

Expo = WorksheetFunction.ExponDist(DeltaC, 1 / TI, True) 'Probabilidad de Boltzman

If X < Expo Then

CS = CS0

End If

End If

ContadorI = ContadorI + 1 'Contador Ti

If ContadorI = NIT Then

Tin = FRT * Tin

ContadorI = 0

End If

Next NumI

Next T 'Fin de Recocido Simulado

Sheets(6).Cells(1, 4 + n) = MinC

Sheets(6).Cells(1, 7 + n) = CS

For Nf = 1 To n

Sheets(6).Cells(3 + Nf, 8 + n) = Nf

Next Nf

'Las siguientes instrucciones ordenan los trabajos de acuerdo a la secuencia obtenida a partir del SA

For jj = Dia2 To (Ls - 1)

Busqueda = WorksheetFunction.VLookup(Sheets(2).Cells(1 + jj, 5), Sheets(6).Range(Sheets(6).Cells(4, 3 + n), _ Sheets(6).Cells(3 + n, 8 + n)), 6, False)

Sheets(2).Cells(1 + jj, 13) = Val(Busqueda)

If jj = (Ls - 1) Then 'Construye la hoja de reporte L1

Sheets(4).Cells(1 + jj, 1) = Sheets(2).Cells(1 + jj, 12)

Sheets(4).Cells(1 + jj, 2) = Sheets(6).Cells(1, 4 + n)

Sheets(4).Cells(1 + jj, 3) = 19

Sheets(4).Cells(1 + jj, 4) = 19 * Sheets(4).Cells(1 + jj, 2)

ANEXO

144

CostoT = CostoT + Sheets(4).Cells(1 + jj, 4)

End If

Next jj

Sheets(4).Cells(2, 1) = "Total"

Sheets(4).Cells(2, 4) = "$ " & CostoT


ActiveWorkbook.Worksheets("Linea 1").Sort.SortFields.Add Key:=Range(Cells(Dia2 + 1, 13), Cells(Ls, 13)), _SortOn:=xlSortOnValues, Order:=xlAscending, DataOption:=xlSortNormal

ActiveWorkbook.Worksheets("Linea 1").Sort.SortFields.Add Key:=Range(Cells(Dia2 + 1, 3), Cells(Ls, 3)), _



.SetRange Range(Cells(Dia2 + 1, 1), Cells(Ls, 13))

.Header = xlGuess

.MatchCase = False



.Apply

End With

Dia2 = Ls

Ls = WorksheetFunction.CountIf(Sheets(2).Range(Sheets(2).Cells(2, 12), Sheets(2).Cells(cont1, 12)), _

Sheets(2).Cells(Li, 12)) + (Li - 1) 'Identifica donde comienza el nuevo día dj

Sheets(6).Range("A1:BN100").Clear

PctDone = (Dia1 / DiaF)

Call UpdateProgress(PctDone) 'Llama a la barra de progreso

Next Dia1

ActiveWorkbook.Worksheets("ReporteL1").Sort.SortFields.Clear

ActiveWorkbook.Worksheets("ReporteL1").Sort.SortFields.Add Key:=Range("A3:A1000"), _


ANEXO

145

With ActiveWorkbook.Worksheets("ReporteL1").Sort

.SetRange Range("A3:D1000")

.Header = xlGuess

.MatchCase = False



.Apply

End With

Sheets(2).Range("M2:M1000").Clear

SetupR1

Close

End Sub

propuesta para la programaciÓn de dos …148.204.210.201/tesis/439.pdf · director de tesis: m en...

Documents