Issuu

tirant lo blanch

LOGÍSTICA DE PRODUCCIÓN Modelos y métodos de programación de operaciones

Jairo Rafael Montoya Torres Escuela Internacional de Ciencias Económicas y Administrativas Universidad de La Sabana Chía, Colombia

México D.F., 2015

Copyright ® 2015 Todos los derechos reservados. Ni la totalidad ni parte de este libro puede reproducirse o transmitirse por ningún procedimiento electrónico o mecánico, incluyendo fotocopia, grabación magnética, o cualquier almacenamiento de información y sistema de recuperación sin permiso escrito del autor y del editor. En caso de erratas y actualizaciones, la Editorial Tirant lo Blanch México publicará la pertinente corrección en la página web http://www.tirant.com/mex La utilización o mención en esta obra de marcas registradas o términos similares, incluso si estos son identificados como tales, no significa expresión alguna de la opinión del autor en cuanto estén sujetos o no a derechos de propiedad intelectual o comercial. Montoya Torres, Jairo Rafael Logística de producción: modelos y métodos de programación de operaciones / Jairo Rafael Montoya Torres – México: Universidad de La Sabana – Tirant lo Blanch, 2015. 160 pp.; 17 x 24 cm. Incluye bibliografía ISBN: 978-84-9086-653-5 (e-book) 1. Logística en los negocios. 2. Administración de la producción. 3. Producción industrial. I. Montoya Torres, Jairo Rafael. II. Universidad de La Sabana (Colombia) III. Tít. IV. Serie. CDD 658.5

Co-ChULS

Colección dirigida por:

Ana Belén Campuzano y Marcelo Pascual © Jairo Rafael Montoya Torres © TIRANT LO BLANCH MÉXICO EDITA: TIRANT LO BLANCH MÉXICO Leibnitz 14 Colonia Nueva Anzures Delegación Miguel Hidalgo CP 11590 MÉXICO D.F. Telf.: (55) 65502317 infomex@tirant.com http://www.tirant.com/mex/ http://www.tirant.es MAQUETA: Tink Factoría de Color © Universidad de La Sabana Campus del Puente del Común Km 7 Autopista Norte de Bogotá Chía, Cundinamarca, Colombia Tel. (57-1) 8615555 Ext. 45001 http://publicaciones.unisabana.edu.co publicaciones@unisabana.edu.co Si tiene alguna queja o sugerencia, envíenos un mail a: atencioncliente@tirant.com. En caso de no ser atendida su sugerencia, por favor, lea en www.tirant.net/index.php/empresa/politicas-de-empresa nuestro Procedimiento de quejas.

Acerca del autor Jairo R. Montoya Torres es Profesor Titular de la Escuela Internacional de Ciencias Económicas y Administrativas de la Universidad de La Sabana, Chía (Colombia). Entre 2007 y 2009, se desempeñó como director del programa de Administración de Mercadeo y Logística Internacionales; entre 2009 y 2010, lideró el diseño y la apertura del programa de Maestría en Gerencia de Operaciones de la Universidad de La Sabana, del cual fue director entre julio de 2010 y marzo de 2013. Entre los meses de marzo y octubre de 2013 fue Investigador Visitante en la Universidad de Leeds, Reino Unido, bajo la figura de Marie Curie International Incoming Fellow financiado en el marco de las Acciones PEOPLE del Séptimo Programa Marco de la Unión Europea. También ha sido Profesor Visitante en la École Nationale d’Ingénieurs de Metz y en la École Nationale Supérieure des Mines de Saint-Étienne (Francia). En noviembre de 2011 defendió satisfactoriamente el diploma posdoctoral de Habilitación para Dirigir Investigaciones (HDR, Habilitation à Diriger des Recherches) en la especialidad de Logística e Investigación de Operaciones ante el Institut National des Sciences Appliquées (INSA) de Lyon y la Université Claude Bernard de Lyon (Francia). Se graduó en noviembre de 2005 como Doctor (Magna Cum Laude) en la especialidad de ingeniería industrial de la École Nationale Supérieure des Mines y de la Université Jean Monnet, Saint-Étienne (Francia). Posee también los títulos de Master of Science in Industrial Engineering and Management del Institut National Polytechnique de Grenoble (Francia) (2002); y de ingeniero industrial (con honores) de la Universidad del Norte, Barranquilla (Colombia) (2000). Sus intereses en investigación se centran en las áreas de simulación y optimización de operaciones logísticas y de producción, evaluación ambiental, social y económica de decisiones logísticas y gestión sostenible de cadenas logísticas. Ha trabajado en empresas de manufactura y de servicios en Colombia y Francia, ejerciendo cargos con énfasis tanto investigativos como administrativos. Sus intereses en docencia incluyen la programación de operaciones y la optimización y simulación de sistemas logísticos y de producción. Ha sido Profesor Catedrático o Profesor Invitado en las universidades: École Nationale Supérieure des Mines de Saint-Étienne – Centre Microélectronique de Provence, Gardanne (Francia); Institut Universitaire de Technologie (IUT) de Saint-Étienne (Francia); Universidad Autónoma de Nuevo León, San Nicolás de los Garza (México); École Centrale Paris (Francia); Universidad de los Andes, Bogotá; Pontificia Universidad Javeriana, Bogotá; Escuela Colombiana de Ingeniería Julio Garavito, Bogotá; Universidad del Norte, Barranquilla (Colombia). En 2010, hizo parte del grupo de coeditores de los Proceedings of the 2010 Winter Simulation Conference (Baltimore, USA) y es coeditor del libro Hybrid Algorithms for Computing, Service and Manufacturing Systems: Routing and Scheduling Solutions, publicado por IGI Global (Estados Unidos). También ha sido editor-invitado para las revistas académicas Annals of

Operations Research, Int., Journal of Information Systems and Supply Chain Management, Journal of Intelligent Manufacturing, Int. Journal of Industrial and Systems Engineering, Journal of Cleaner Production, Int. Journal of Productivity and Performance Management y Logistique et Management. También ha publicado numerosos artículos de investigación en revistas académicas internacionales, varios capítulos de libros editados y artículos en memorias de conferencias internacionales de alto prestigio. Ha sido invitado como evaluador-par de artículos de investigación para revistas académicas internacionales y miembro de Comités Científicos Internacionales de Programa (IPC) y organizador y presidente de sesión en conferencias internacionales prestigiosas sobre simulación, logística y gestión de operaciones. También se encuentra en la lista de evaluadores-pares del Departamento Administrativo de Ciencia, Tecnología e Innovación (Colciencias) de Colombia.

Prefacio El contexto económico competitivo hace que las empresas de manufactura, pero también las de servicio, se vean confrontadas a la implementación constante de procedimientos formales que les permitan optimizar sus procesos. En particular, en lo referente a las operaciones de manufactura, la logística de producción juega un papel importante en cuanto al uso eficiente de los recursos. Esta eficiencia es comúnmente medida en términos monetarios a nivel estratégico, pero también en términos de indicadores globales de desempeño, a nivel táctico, o incluso en tasas de utilización de los recursos, a nivel operativo. Es en este nivel de toma de decisiones que se focaliza este libro, y en particular en los procesos de la logística de producción relacionados con la programación de actividades de producción. La programación de operaciones (scheduling en la literatura anglófona) consiste en la asignación óptima, o cuasi-óptima, de recursos para la realización de un conjunto de actividades. Fruto de las aplicaciones iniciales en problemas de manufactura, los recursos son comúnmente llamados “máquinas” y las actividades se llaman “tareas”, “trabajos” u “órdenes de producción”. Los modelos y procedimientos desarrollados para la programación de operaciones se han visto beneficiados por el auge y el desarrollo de los computadores.

Agradecimientos La idea de escribir un libro en español sobre logística de producción, y en particular sobre programación de operaciones, con énfasis en modelos y procedimientos de resolución, nació en el año 2000 cuando al trabajar en temas realacionados a nivel de investigación, observé que no existían libros de texto en español sobre este tema. Algunos años después del inicio del proyecto, y de varios manuscritos actualizados permanentemente a través de clases dictadas en pregrado y posgrado, la primera versión completa del manuscrito fue terminada de escribir durante una visita corta de investigación en el Center for Transportation and Logistics (CTL) del Masachussetts Institute of Technology (MIT), Cambridge, USA, gracias a la invitación extendida por el doctor Edgar E. Blanco, quien actualmente es Principal Research Director y Executive Director de la red SCALE para Latinoamérica del CTL-MIT. Este borrador fue empleado como material guía de clase en los años siguientes en la asignatura “Logística de producción”. A partir de los comentarios y las sugerencias de mejoramiento recibidos por parte de los estudiantes, se presenta la versión actual del texto de clase. Así pues, la recopilación de modelos y procedimientos de resolución presentados en este libro es fruto de la experiencia docente en el área. En este sentido, agradezco el aporte y las correcciones realizadas en las versiones preliminares del manuscrito por los estudiantes. Es necesario agradecer el aporte de algunos colegas. Entre ellos, agradezco a Mike Pinedo, Professor en Stern Business School New York University, USA, y Gonzalo Mejía, Profesor Asociado del Departamento de Ingeniería Industrial de la Universidad de los Andes, Bogotá (Colombia), por compartir conmigo sus diapositivas de clase. También es necesario agradecer las ideas y sugerencias diversas de Edgar Alfonso, Profesor Asociado de la Facultad de Ingeniería de la Universidad de La Sabana, Chía (Colombia) y de un gran colega, Carlos Paternina, Profesor Asociado y anterior director del Departamento de Ingeniería Industrial y del programa de Maestría en Ingeniería Industrial de la Universidad del Norte, Barranquilla (Colombia), quien ha apoyado mis ideas para la enseñanza de la programación de operaciones y ha sugerido en conversaciones formales e informales algunas ideas que han contribuido a la generación de varios artículos científicos.

Consideraciones para la lectura y uso del libro Para emplear este libro como texto guía de clase se presume que los estudiantes están familiarizados con los conceptos básicos de la optimización combinatoria y han tomado un curso sobre investigación de operaciones o matemáticas discretas. Se presumen igualmente conocimientos en algorítmica y programación de computadores, independientemente del lenguaje de programación. En los capítulos iniciales del libro se prevé la presentación de algunos conceptos básicos sobre la modelación matemática y la Teoría de la Complejidad Computacional. Se recomienda que el lector profundice en estos temas basándose en las referencias citadas en dichos capítulos.

Capítulo 1

Introducción

1.1. Definición de logística y de logística de producción La logística es un campo de las ciencias aplicadas dedicado a la resolución de problemas en el mundo de los negocios. Hoy en día, cuenta con más de cincuenta años de historia y se ha convertido en uno de los pilares clave de desarrollo de los negocios, aunque originalmente la logística proviene del ambiente militar y no de los negocios o la academia. Etimológicamente, la palabra logística parece provenir del griego logistikos que significa “saber calcular” o del latín logisticus que hace referencia al administrador o intendente en el ejército de la Antigua Roma. También pareciera tener orígenes en la palabra francesa loger, que significa “alojar, habitar”, dado que en los ejércitos napoleónicos existía el cargo de maréchal de logis, quien era un miembro del Estado Mayor encargado del acomodamiento o acantonamiento de las tropas en las diferentes campañas del ejército. En el contexto militar, la logística es la “parte del arte de la guerra que tiene por objeto proporcionar a las fuerzas armadas los medios necesarios para satisfacer adecuadamente las exigencias de la guerra”. En el ambiente empresarial, la logística apareció después de la Segunda Guerra Mundial, a partir de la reconversión de los especialistas militares en logística (optimización de operaciones). Tanto la definición del concepto de logística como las funciones que se llevan a cabo han evolucionado con el tiempo (figura 1.1), junto con la evolución de los mercados y de los sistemas industriales, yendo desde el simple “transporte de productos” hasta ser llamada una ciencia interdisciplinaria que combina la ingeniería, la micro-economía y la teoría organizacional. El concepto de la logística es un problema en sí mismo.

economía y la teoría organizacional. El concepto de la logística es un problema en sí mismo.

Figura 1.1. Línea de evolución de la logística

Distribución física de productos

1940

Hitos

“Ciencia” de la distribución física

1960

Revolución del mercadeo Magee (1960) Druker (1962)

JIT, producción, logística industrial, aprovisionamiento

1980

Supply chain management

1990

2000

Evolución en el tiempo

Fuente: adaptado de Klaus (2009).

Figura 1.1. Línea de evolución de la logística

La American Marketing Association (AMA) propuso en 1948 la primera definición formal Fuente: adaptado de Klaus (2009) de la logística: “La logística concierne el movimiento y la manutención de mercancías desde el punto de producción hasta el punto de consumo o de utilización”. Es importante notar que en esta definición 11 sólo se consideran las actividades físicas de la etapa de distribución. De su parte, el National Council of Physical Distribution Management (NCPDM), propone en 1962 la definición de logística como: Término empleado en la industria y el comercio para describir el gran espectro de actividades necesarias para obtener un movimiento eficiente de productos terminados desde la salida de la cadena de fabricación hasta el consumidor, y que en algunos casos incluye el movimiento de materias primas desde los proveedores hasta el inicio de la línea de fabricación. Estas actividades incluyen el transporte, almacenamiento, manutención, empaque, control de inventarios, localización de plantas, tratamiento de pedidos, los pronósticos del mercado y el servicio ofrecido al cliente.

En 1972, el NCPDM revisa la definición del concepto así: Término que describe la integración de dos o más actividades con el fin de planear, implementar y controlar un flujo eficiente de materias primas, de productos semiterminados y finales desde su punto de origen al punto de consumo. Estas actividades pueden incluir, sin que sea limitado, el tipo de servicio ofrecido a los clientes, los pronósticos de la demanda, la comunicación, el control de inventarios, la manutención de materias primas, tratamiento de pedidos, servicio posventa, localización de bodegas y fábricas, compras, empaque, tratamiento de mercancía devuelta, negociación y reutilización o desecho de elementos recuperados y el transporte.

El Council of Logistics Management incluye el aspecto de información: La logística es una parte de las actividades de una cadena logística. Concierne la planeación, la ejecución y el control de flujos eficientes de almacenamiento de productos, de gestión de la información relacionada con esas funciones desde el origen al punto de consumo para satisfacer las necesidades de los clientes.

El Logistics Institute de Canadá insiste en los aspectos financieros y de información: La logística es un conjunto de funciones relacionadas con los flujos de mercancías, de información y de recursos financieros entre proveedores y clientes desde la adquisición de materias primas hasta el reciclaje o desecho de productos terminados.

En la definición dada por la Asociación Colombiana de Logística (ACOLOG) se incluyen la información, la optimización y la relación entre gerencia y operación, haciendo así referencia a los niveles tanto estratégico como operativo en la toma de decisiones: Entiéndase por logística la función sistemática de optimización en el flujo de materiales y de información, integrando dos o más actividades gerenciales y operacionales dentro de la planeación, implementación y control desde el punto de origen hasta el destino final, con el propósito adecuado a las necesidades de consumidores y clientes.

Tomando como referencia una empresa focal, la definición dada por el Supply Chain Council hace referencia a: “La secuencia de etapas de producción y de distribución de un producto desde el proveedor del proveedor hasta los clientes de los clientes”. A partir de las definiciones anteriores, se observa que la cadena logística global tiene por misión controlar y optimizar todos los flujos físicos, financieros y de información relacionados con la interacción de actores vinculados a los procesos de producción y distribución de bienes o servicios, integrando los proveedores. La figura 1.2 esquematiza estas ideas.

J.R. MONTOYA TORRES

Figura 1.2. Caracterización de una cadena logística Sistema de producción Aprovisionamiento

Flujo de aprovisionamiento

Gestión de aprovisionamientos

Logística de aprovisionamiento

Flujo de información

Flujos físicos en la fábrica

Gestión de producción

Logística de producción

Pedido del cliente

Flujo de transporte

Gestión del transporte

Logística de distribución

Cadena logística global

En el contexto de la cadena logística presentada figura 1.2, este libro se centra Figura 1.2. Caracterización de en unala cadena logística en la logística de producción, la cual involucra todas las operaciones de apoyo a la actividades de fabricación de un bien o de producción de un servicio: planeación de operaciones, programación de la producción, gestión de inventarios, manutención y En el contexto de la cadena logística presentada en laEnfigura 1.2, este libro se transporte de producto en proceso, entre otras actividades. el contexto económico globalizado competencia desenfrenada,lalacual organización la producción, y muy centra en de la logística de producción, involucradetodas las operaciones particularmente la programación de las actividades, figuran incontestablemente dendedeapoyo a la de fabricación de un bien o de producción dede un tro aquéllas queactividades son más importantes y que impactan el desempeño del sistema producción. servicio: planeación de operaciones, programación de la producción, gestión Las siguientes secciones de este capítulo presentan los conceptos y correspondientes de inventarios, manutención y transporte de producto en proceso, entre otras definiciones formales de los diferentes aspectos de la logística de producción, con un actividades. contexto de económico competencia particular énfasisEn en laelprogramación operaciones.globalizado Los capítulos de siguientes de este libro extienden los conceptos y presentan diferentes modelos y métodos de solución de desenfrenada, la organización de la producción, y muy particularmente la varios problemas de programación de la producción. programación de las actividades, figuran incontestablemente dentro de

1.2. Definición de programación de operaciones La programación de operaciones, también conocida como programación de tareas (en inglés, scheduling), consiste en la organización y asignación de tiempos al uso de recursos para ejecutar todas las actividades (tareas u operaciones) requeridas para producir las salidas deseadas en los tiempos deseados y teniendo en cuenta las restricciones de tiempo y las relaciones entre las actividades y los recursos. Esta definición implica dos cosas importantes. Por un lado, si los recursos no son limitados, no existe el problema de programar las operaciones. Por otro lado, la programación de operaciones, en sí misma, es un proceso de toma de decisiones que tiene como objetivo la optimización de uno o varios criterios. Los recursos y las tareas pueden ser de diferentes tipos. Los recursos pueden ser las máquinas en un taller de manufactura, la pista de aterrizaje en un aeropuerto, los empleados en un proyecto de construcción, los procesadores en un equipo de cómputo, y así sucesivamente. En cuanto a las tareas, éstas pueden ser las operaciones de fabricación de un producto, las operaciones de despegue y aterrizaje de aviones en el aeropuerto, las etapas del proyecto de construcción, la ejecución de los programas de cómputo, etc. Como se mencionó anteriormente, la programación de tareas es un proceso de toma de decisiones que se presenta en prácticamente todos los sistemas productivos, ya sea de manufactura o de servicios, al igual que en los sistemas computacionales. La toma de decisiones en cuanto a la programación de tareas o actividades también se presenta en sistemas de transporte y distribución, y en otros tipos de sistemas productivos del área de servicios. La realización de un programa de ejecución de tareas puede ser difícil tanto desde el punto de vista técnico como desde la perspectiva de su implementación. Las dificultades en los aspectos técnicos son básicamente las mismas que se presentan al resolver los problemas de optimización combinatoria y modelamiento estocástico. A nivel de la implementación, la mayor dificultad radica tanto en el modelado de los problemas reales de programación de tareas como en la recolección de la información pertinente.

1.3. La programación de tareas en la empresa de manufactura La programación detallada de los diversos elementos de la función productiva es básica para ejercer el control y monitoreo de todo sistema productivo. La descripción que se presentará a continuación tiene particular aplicación para una empresa de manufactura. Una descripción similar podría hacerse para el caso de empresas dedicadas exclusivamente a los servicios. La función de producción puede considerarse como un proceso jerárquico, como se muestra en la figura 1.3. En primer lugar, se deben realizar los pronósticos de la demanda de ventas agregadas durante cierto horizonte de tiempo. Esos pronósticos constituyen los datos de entrada para determinar el plan agregado de producción, incluyendo los requerimientos en fuerza de trabajo. Este plan se traduce posteriormente en el plan maestro de producción, en el cual se programan las cantidades que se van a fabricar por producto y por periodo. Esta planeación es, en sí misma, un método para cumplir metas específicas de producción de artículos terminados para inventario. Como resultado se obtiene la emisión programada de requisiciones para los productos finales, los subensambles y los componentes. Por último, estas requisiciones deben traducirse en un conjunto de tareas con sus fechas de entrega asociadas, lo cual corresponde al nivel detallado de programación de trabajos. Así, a nivel del piso de fabricación, el control de la producción implica programar el personal y el equipo en cada uno de los centros de trabajo con el fin de cumplir los plazos de entrega.

equipo en cada uno de los centros de trabajo con el fin de cumplir los plazos de entrega. Figura 1.3. Esquema de jerarquía de decisiones para la programación de tareas Órdenes y datos históricos sobre la demanda Restricciones sobre la capacidad del sistema

Pronóstico de la demanda

Plan agregado de producción

Plan maestro de producción

Mantenimiento programado (preventivo)

Planeación de requerimientos de materiales

Programa detallado de producción

Programación de cantidades producidas por producto y por periodo Requerimientos de componentes y de producto final

Reprogramación de trabajos

Mantenimiento reactivo (no programado) y otros eventos aleatorios, pedidos urgentes, etc.

En la Figura práctica,1.3. no Esquema es posible establecer anticipadamente programa perfecto que de jerarquía de decisionesun para la programación de sea respetado completamente a lo largo de todo el horizonte de producción. La naturaleza tareas estocástica de los sistemas productivos hace que se presenten situaciones aleatorias, muy difíciles de predecir, las cuales provocan la reprogramación de algunas o todas las tareas aún no ejecutadas. En algunos ambientes de fabricación, la llegada “a última hora” urgentes perturba el programa de trabajo y hace que deban En de la pedidos práctica, no estambién posible establecer anticipadamente un programa reprogramarse algunas actividades. perfecto que sea respetado completamente a lo largo de todo el horizonte de

El requerimiento clave de cualquier sistema para programación de operaciones consiste producción. La naturaleza estocástica de los sistemas productivos hace que en que éste debe convertirse en una herramienta de apoyo al proceso de toma de decisiones, principalmente centrada en las actividades de corto plazo. El sistema debe ser utilizado en contexto dinámico, de tal forma que apoye en tiempo real el proceso deci19 sional. De esta forma, se requiere un vínculo directo con la base de datos empresarial, la cual debe ser actualizada en tiempo real según el desempeño de las funciones opera-

tivas. El sistema debe ser de fácil uso para quienes se encuentren directamente relacionados con él, y debe generar programas de trabajo factibles tomando en cuenta la o las funciones objetivo que la organización considere pertinentes. Estas funciones objetivo pueden estar directamente relacionadas con el servicio al cliente, el control del nivel de inventarios o de los tiempos de ejecución dentro del sistema,J.R. entre otras. La figura 1.4 MONTOYA TORRES presenta un esquema de un sistema de programación de operaciones. Figura 1.4. Esquematización de un sistema de programación de operaciones Entradas al proceso Datos acerca de las tareas y operaciones

Objetivos (funciones objetivo) Cumplir fechas de entrega Minimizar el tiempo de flujo Minimizar el inventario Minimizar la tardanza

Ruta (secuencia) de ejecución Tiempos de ejecución Fechas de disponibilidad Fechas de entrega Clientes Requerimientos de recursos

Toma de decisiones (Programación de las actividades)

Datos sobre el personal Disponibilidad Competencias Salario

Datos sobre los recursos físicos Disponibilidad Mantenimiento programado Fiabilidad Costos fijos y variables

Programa de ejecución de actividades para cada máquina Salidas del proceso

Fechas de inicio de ejecución Asignación de tareas a cada turno Asignación de tareas a cada recurso Físicos y empleados Diagramas de Gantt Evaluación de los objetivos

Figura 1.4. Esquematización de un sistema de programación de operaciones

1.4. Notación matemática En este libro se empleará la notación matemática utilizada en la mayoría de los libros y 1.4. Notación matemática T1 artículos académicos sobre programación de tareas. Sean J el conjunto de n trabajos y M el conjunto de m máquinas o recursos. Un trabajo se representa como j o Jj, mientras En este libro se empleará la notación matemática utilizada en la mayoría de que una máquina se denota como i o Mi. Se define la notación siguiente: los libros y artículos académicos sobre programación de tareas. Sean 𝐽𝐽 el

conjunto de 𝑛𝑛 trabajos y 𝑀𝑀 el conjunto de 𝑚𝑚 máquinas o recursos. Un trabajo

se representa como 𝑗𝑗 o 𝐽𝐽𝑗𝑗 , mientras que una máquina se denota como 𝑖𝑖 o 𝑀𝑀𝑖𝑖 . Se define la notación siguiente:

Número de máquinas o recursos en el sistema

Número de tareas

pij

Tiempo de procesamiento (processing time) en la máquina i del trabajo j. Si únicamente debe realizarse una operación, este tiempo se representa como pj .

Fecha de llegada o tiempo de disponibilidad del trabajo j en el sistema (release time).

Fecha de entrega del trabajo j (due date).

Peso o importancia relativa del trabajo j (weight).

Instante de inicio de ejecución del trabajo j (start time).

Instante de finalización o terminación del trabajo j (completion time).

Tiempo de permanencia en el sistema del trabajo j (flow time): Fj = Cj – rj .

Retraso del trabajo j con respecto a su fecha de entrega esperada (lateness). También se conoce como retraso algebraico: Lj = Cj – dj .

Tardanza del trabajo j (tardiness): Tj = max (0, Lj)

 Indicador de retraso: Uj   

Tj 

Los datos de un problema de programación de operaciones consisten en los trabajos y sus características, la descripción y las restricciones de los recursos y del procesamiento de los trabajos, y la función económica u objetivo que se debe optimizar.

1.5. Clasificación de problemas de programación de operaciones Los problemas de programación de operaciones o tareas son muy diferentes de un sistema a otro, por lo cual no existe un método universal que permita resolverlos todos de forma eficiente. Con el fin de facilitar el enfoque de solución que se va a adoptar, el problema bajo estudio puede ser modelado utilizando algunos de los modelos que se presentan en los capítulos de este libro. Una forma de identificar el modelo más cercano o apropiado consiste en realizar anticipadamente una clasificación de los mismos, basada en la naturaleza del sistema bajo estudio, incluyendo el número y las características de los recursos o máquinas, las características de las tareas y su ruta de ejecución a través de los recursos, y en la función o las funciones objetivo por optimizar. En la literatura académica, estos elementos han sido tradicionalmente representados a través de una

notación empleando tres campos de la forma α | β | γ. En esta notación, el campo α corresponde a la configuración del sistema bajo estudio. También puede indicarse si existen o no restricciones en cuanto al número de recursos o máquinas disponibles. El campo β corresponde a la descripción de las restricciones y características asociadas a los trabajos por realizar. En el campo γ se indica cuál es la función objetivo que se va a minimizar. A manera de ejemplo, si se tiene el problema 1|rj, prec|∑Cj, eso quiere decir que se minimizará el tiempo total de terminación de los trabajos ( ∑ C j ) en una configuración con un solo recurso (una máquina) cuando las tareas están disponibles en el sistema a instantes diferentes de tiempo ( r j ) y además existen relaciones de precedencia entre ellas (prec). Ahora, si se tiene por ejemplo F2||Cmax, se está haciendo referencia a un problema de minimización del makespan o lapso (Cmax) en una configuración de tipo flowshop con únicamente dos máquinas (F2), y no existen ni restricciones ni características particulares para las tareas (el campo β está vacío). A continuación se explicará más en detalle cuáles son los elementos que pueden aparecer en cada uno de los campos α, β y γ.

1.5.1. Configuración del sistema: campo α El campo α se utiliza para representar las características del sistema bajo estudio a través del número de recursos o máquinas disponibles. La configuración del sistema también permite determinar cuál será la ruta que seguirán los diferentes trabajos a través de los recursos. Las posibles configuraciones son: • Una máquina (1). En esta configuración únicamente se dispone de un recurso o máquina en el sistema. Por consiguiente, sólo es necesario ejecutar una sola operación para terminar el procesamiento o la realización de cada trabajo (figura 1.5). En este caso, el tiempo de procesamiento del trabajo j será denotado únicamente como pj.

recurso o mĂĄquina en el sistema. Por consiguiente, sĂłlo es necesario ejecutar una sola operaciĂłn para terminar el procesamiento o la realizaciĂłn de cada trabajo (figura 1.5). En este caso, el tiempo de procesamiento del trabajo đ?‘—đ?‘— serĂĄ denotado Ăşnicamente como p j Figura 1.5. ConfiguraciĂłn de sistema con una sola mĂĄquina Fila de espera

Recurso

Entrada de tareas

Salida de tareas

â€˘ MĂĄquinas o recursos en paralelo. Se dispone de un conjunto de m mĂĄquinas Figura 1.5. ConfiguraciĂłn de sistema con una sola mĂĄquina. o recursos en paralelo. A priori, sĂłlo se requiere de una operaciĂłn para terminar el procesamiento o la realizaciĂłn de cada trabajo, y todas las mĂĄquinas pueden ejecutar dicha operaciĂłn (figura 1.6). SegĂşn la velocidad de procesamiento de las ď‚ˇ MĂĄquinas paralelo.posibilidades: Se dispone de un conjunto de đ?‘šđ?‘š mĂĄquinas, ose recursos distinguen en las siguientes mĂĄquinas o recursos A de priori, sĂłlo es sela requiere detodos una los - MĂĄquinas idĂŠnticasen(P):paralelo. la velocidad ejecuciĂłn misma para

recursos en el sistema. En este caso, el tiempo de procesamiento p de la tarea j es independiente de la mĂĄquina.

operaciĂłn para terminar el procesamiento o la realizaciĂłn de cadaj trabajo, y todas las mĂĄquinas pueden ejecutar dicha operaciĂłn (figura 1.6). SegĂşn

- MĂĄquinas no homogĂŠneas: cada mĂĄquina tiene su propia velocidad de

la velocidad mĂĄquinas, se distinguen las Si ejecuciĂłn.de Estoprocesamiento puede deberse,de porlas ejemplo, a diferencias tecnolĂłgicas.

para la mĂĄquina i, su velocidad de procesamiento se denota como vi, se tiene entonces que el tiempo de procesamiento de la tarea j en la mĂĄquina es

siguientes posibilidades:

pj pij = v ď€ MĂĄquinas idĂŠnticas (P): la velocidad de ejecuciĂłn es la misma para i

- todos MĂĄquinas no relacionadas las mĂĄquinas no son idĂŠnticas y ademĂĄs los recursos en el (R): sistema. En este caso, el tiempo de el tiempo de procesamiento en la mĂĄquina i depende de la tarea que va a ser la tarea đ?‘—đ?‘— es independiente de la mĂĄquina. procesamiento procesada. AsĂ, psej de tiene una velocidad de procesamiento vij que depende del pj trabajo por realizar. Entonces, pij = v i

ademĂĄs el tiempo de procesamiento en la mĂĄquina đ?‘–đ?‘– depende de la tarea que va a ser procesada. AsĂ, se tiene una velocidad de

procesamiento vij que depende del trabajo por realizar. Entonces,

pij ď€˝

pj vij

Figura 1.6. ConfiguraciĂłn de sistema con tres mĂĄquinas en paralelo Recursos en paralelo

ď‚ˇ

J.R. MONTOYA TORRES

Fila de espera

Salida de

Entrada de

tareas Configuraciones especializadas (o M talleres especializados). Consiste tareas

en configuraciones especializadas en las cuales se tiene un conjunto de M đ?‘šđ?‘š recursos y la realizaciĂłn de cada trabajo radica en la ejecuciĂłn de

varias operaciones. SegĂşn la ruta que las tareas o los trabajos deben

â€˘ Configuraciones especializadas (o talleres Consiste en Figura 1.6. ConfiguraciĂłn de sistema con tres especializados). mĂĄquinas en paralelo seguir dentro del sistema, se distinguen las siguientes configuraciones: configuraciones especializadas en las cuales se tiene un conjunto de m recursos y la realizaciĂłn de cada trabajo radica en la ejecuciĂłn de varias operaciones. ď€ Flowshop (F). Se dispone de un conjunto de đ?‘šđ?‘š mĂĄquinas o recursos SegĂşn la ruta que las tareas o los trabajos deben seguir dentro del sistema, se en serie, tal como se muestra en la figura 1.7. Los trabajos estĂĄn distinguen las siguientes configuraciones: compuestos de đ?‘šđ?‘š operaciones y la ruta que estos deben seguir es

- Flowshop (F). Se dispone de un conjunto de m mĂĄquinas o recursos en serie, idĂŠnticasepara todos: mĂĄquina 1, despuĂŠs mĂĄquina 2, de m tal como muestra enprimero la figurala261.7. Los trabajos estĂĄnla compuestos operaciones y la ruta 3, que estos deben seguirhasta es idĂŠntica para todos: primero luego la mĂĄquina y asĂ sucesivamente la mĂĄquina đ?‘šđ?‘š. Gran la mĂĄquina 1, despuĂŠs la mĂĄquina 2, luego la mĂĄquina 3, y asĂ sucesivamente parte del trabajo desarrollado en la literatura considera el problema de

hasta la mĂĄquina m. Gran parte del trabajo desarrollado en la literatura consiflowshop de permutaciĂłn. Un programa de permutaciĂłn es un dera el problema de flowshop de permutaciĂłn. Un programa de permutaciĂłn programa el mismo mismoorden orden ejecuciĂłn las es un programaque queconserva conserva el de de ejecuciĂłn de lasdeoperaciones en todas las mĂĄquinas. operaciones en todas las mĂĄquinas.

Figura 1.7. ConfiguraciĂłn de sistema de tipo flowshop con dos mĂĄquinas Entrada de tareas

Salida de tareas

- Jobshop (J). Se tiene un conjunto de m mĂĄquinas o recursos. Los trabajos estĂĄn 1.7. compuestos de mde operaciones cada mĂĄquina ejecutar una opeFigura ConfiguraciĂłn sistema de ytipo flowshop condebe dos mĂĄquinas. raciĂłn de cada trabajo. A diferencia del flowshop, en la configuraciĂłn de jobshop la ruta de ejecuciĂłn de los trabajos es propia a cada uno de ellos y, por tanto, pueden ser distintas entre sĂ.