programación lineal entera

UNI VERSI DAD DEL Bu00cd O-BÍ O
FACULTAD DE I NGENI ERÍ A
DEPARTAM ENTO DE I NGENI ERÍ A I NDUSTRI AL

TESI S
Presentada para la obtención del grado de

M agíster en I ngeniería I ndustrial
Por:

Rodrigo Alex Gallardo Venegas
M inimización de la Tardanza Total en una M áquina con Tiempos
de Preparación Dependientes de la Secuencia M ediante M odelos
de Programación Lineal Entera Mixta

Director de Tesis:

Dr. Carlos Obreque Niñez

Departamento de I ngeniería I ndustrial

Concepción, Noviembre de 2011

2
RESUM EN
El propósito de esta tesis es el estudio, diseño y formulación de modelos de programación
lineal entera mixta para resolver el problema de secuenciación de tareas o trabajos en una
máquina, con tiempos de preparación dependientes de la secuencia y conel objetivo de
minimizar la tardanza total.
El problema de secuenciación consiste en asignar N trabajos, que están disponibles en el
tiempo cero, a una máquina. Cada trabajo tiene asociado un tiempo de procesamiento, un
tiempo de preparación que depende de la secuencia y una fecha de entrega, todos los datos
previamente conocidos. El objetivo del problema de secuenciación de trabajos esencontrar el
programa de producción que minimice la tardanza total, esto es, la suma de las diferencias
entre los tiempos de terminación y las fechas de entrega de cada trabajo.
Este es un problema NP-Hard y para resolverlo se formulan cuatro modelos de programación
lineal entera mixta. Para la formulación de tales modelos se consideró el problema de
secuenciación como uno de optimización deredes. También, como una extensión, se
presentan tres modelos de programación lineal entera mixta para el caso de una configuración
con dos o más máquinas paralelas idénticas y con tiempos de preparación dependientes de la
secuencia.
Todos los modelos de programación entera mixta, estudiados en esta tesis, se resuelven
utilizando el lenguaje AMPL y el solver CPLEX 9.0.0, en instancias test quefueron obtenidas
de la literatura.
Los resultados indican que, para el problema con una máquina, la formulación basada en el
problema del vendedor viajero dependiente del tiempo, presentó un mejor desempeño,
logrando soluciones óptimas en tiempos razonables, en instancias hasta 35 trabajos.

3

Í NDI CE
CAPÍ TULO 1: I NTRODUCCI ÓN

7

1.1 Objetivo General

9

1.2 ObjetivosEspecíficos

9

CAPÍ TULO 2: ANTECEDENTES GENERALES SOBRE PROBLEM AS DE
SECUENCI AM I ENTO DE TAREAS

10

2.1 Secuenciamiento de Tareas

10

2.2 Notación de los Problemas de Secuenciamiento

11

2.3 Ambientes de Trabajo

12

2.4 Características de Procesamiento y Restricciones

13

2.5 Objetivos de Desempeño

14

2.6 M étodos de Solución de los Problemas de Secuenciamiento deTareas

16

CAPÍ TULO 3: ANTECEDENTES BI BLI OGRÁFI COS

18

3.1 Descripción del Problema

18

3.2 Secuenciamiento de Tareas con el Objetivo de M inimizar la Tardanza Total ...

19

3.3 Secuenciamiento de Tareas con Tiempos de Preparación Dependientes de la
Secuencia

21

3.4 Secuenciamiento de Tareas con Tiempos de Preparación Dependientes de la
Secuencia con el Objetivo de Minimizar la Tardanza Total

24

CAPÍ TULO 4: FORM ULACI ÓN DE M ODELOS DE PROGRAM ACI ÓN
LI NEAL ENTERA

28

4.1 Formulación Basada en el Problema del Vendedor Viajero

30

4.2 Formulación Basada en el Problema del Vendedor Viajero Dependiente del
Tiempo

32

4

4.3 Formulación Basada en los Problemas del Vendedor Viajero Dependiente del
Tiempo y del Camino Hamiltoniano

354.4 Formulación Basada en Flujo M ulticommodity

38

4.5 Ejemplo de Aplicación del Problema 1| sij | Tj

40

..

4.6 Extensión de los modelos de programación lineal entera mixta para resolver el
problema de secuenciación en máquinas paralelas idénticas con tiempos de
preparación dependientes de la secuencia.

44

4.6.1 Formulación Basada en los M odelos del Vendedor Viajero...