Seminario: Elementos de Metaheurísticas edición segundo semestre 2004
Uso de Metaheurísticas en El Pptu
-
Upload
jjerezalo6079 -
Category
Documents
-
view
44 -
download
0
Transcript of Uso de Metaheurísticas en El Pptu
Instituto Superior Politécnico José Antonio Echeverría Facultad de Ingeniería Informática
Uso de metaheurísticas en el problema de planificación de trabajos uniformes
Trabajo de diploma en opción del título de Ingeniero Informático
Autor: Joel Jerez Alonso [email protected]
Director: M.Sc. David Paredes Miranda DIAISI - CUJAE
La Habana, 2013
Uso de metaheurísticas en el problema de planificación de trabajos uniformes
Joel Jerez
© ISPJAE, 2013
Aprobación del tema de tesis: Dr.C. Exiquio C. Leyva Pérez (CUJAE).
Dedicatoria: a mi sobrino Alejandro.
Agradecimientos: Al tutor, a mis padres, a Toni, y también a Rachel, Zaida, Néstor, Anita, Eric, Exiquio, Ivón, Anna, Leo, Yinet, PAM y SIGENU. Gracias a todos por su aporte, en la realización de esta tesis.
Reconnaissance: Je veux remercier à Christelle Gueret (Université d'Angers) pour son collaboration dans la réalisation de cette thèse.
CUJAE Ave. 127 y Carr. Ctral. Mtnez Prieto Marianao, La Habana, Cuba. Sitio: www.cujae.edu.cu
RESUMEN
V
Resumen
Con la presente tesis se estudia el Problema de Planificación de Trabajos
Uniformes conocido en inglés como Flow Shop Scheduling Problem. Este proble-
ma es aplicable en áreas donde se ejecuten varios trabajos que tengan el mismo
procedimiento. Dicho problema es valorado como intratable, y por lo tanto, puede
resolverse con el empleo de metaheurísticas.
Se pretende analizar el comportamiento del Escalador de Colinas y de la
Búsqueda Aleatoria en la solución del referido problema. Se realiza un conjunto de
experimentos con instancias de la literatura, para observar los resultados y tratar
de derivar el rendimiento de los algoritmos.
Palabras clave: optimización combinatoria, planificación de trabajos uniformes,
planificación de trabajos semi-uniformes, planificación de trabajos no-uniformes,
marca de tiempo, heurística, metaheurística, escalador de colinas, búsqueda
aleatoria, Biblioteca de Métodos de Planificación de Trabajos.
USO DE METAHEURÍSTICAS EN EL PPTU
VI
Abstract
The present work studies Flow Shop Scheduling Problem (FSSP). The
method of FSSP is applicable in areas where some jobs are executed with the
same procedure. The FSSP is valued like hard problem and to solve it they can be
used metaheuristic.
It is sought to analyze the behavior of Hill Climbing and Black-Box Optimi-
zation on the solution of this problem. A group of experiments with instances of the
literature will also be made to observe the results and to derive the benefit of the
algorithms.
Keywords: combinatorial optimization, flow shop scheduling, job shop scheduling,
open shop scheduling, makespan, heuristic, metaheuristic, hill climbing, black-box
optimization, Jobs Scheduling Methods Library.
ÍNDICE
VII
Índice
Resumen ................................................................................................................ V
Introducción ........................................................................................................... 1
1. Fundamentos teóricos ................................................................................... 5
1.1 Optimización............................................................................................... 5
1.1.1 Optimización combinatoria................................................................... 6
1.2 Heurísticas ................................................................................................. 8
1.2.1 Metaheurísticas ................................................................................... 9
1.2.1.1 Operadores de mutación ............................................................. 10
1.2.1.2 La Búsqueda Aleatoria ................................................................ 12
1.2.1.3 El Escalador de Colinas .............................................................. 13
1.2.1.4 BiCIAM ........................................................................................ 15
1.3 Problema de Planificación de Trabajos Uniformes ................................... 16
1.3.1 Definición ........................................................................................... 17
1.3.2 Descripción ........................................................................................ 18
1.3.3 Representación .................................................................................. 18
1.3.4 Ejemplo .............................................................................................. 19
1.3.5 Aplicaciones....................................................................................... 20
1.3.6 Otros problemas de planificación ....................................................... 20
1.4 Consideraciones parciales ....................................................................... 21
2. Propuesta de solución ................................................................................. 23
2.1 Módulo de problemas combinatorios ........................................................ 23
2.1.1 Operadores de mutación ................................................................... 26
2.1.1.1 Análisis de operadores ................................................................ 26
2.1.2 Función objetivo ................................................................................. 29
USO DE METAHEURÍSTICAS EN EL PPTU
VIII
2.2 Módulo de optimización ............................................................................ 31
2.3 Módulo de problemas de planificación ..................................................... 32
2.4 Mecanismo de carga de datos ................................................................. 33
2.5 Mecanismo controlador ............................................................................ 36
2.6 Proyecto de experimentación ................................................................... 37
2.7 Consideraciones parciales ....................................................................... 37
3. Análisis de los resultados ............................................................................ 38
3.1 Información del hardware ......................................................................... 38
3.2 Diseño de experimentos ........................................................................... 38
3.3 Ambiente de prueba ................................................................................. 39
3.3.1 Ficheros de salida .............................................................................. 39
3.4 Análisis del Escalador de Colinas ............................................................ 40
3.4.1 Uso de operadores ............................................................................ 41
3.4.2 Convergencia ..................................................................................... 43
3.5 Análisis de la Búsqueda Aleatoria ............................................................ 45
3.6 Comparación entre algoritmos ................................................................. 46
3.7 Consideraciones parciales ....................................................................... 46
Conclusiones ....................................................................................................... 48
Recomendaciones ............................................................................................... 49
Referencias bibliográficas .................................................................................. 50
Bibliografía ........................................................................................................... 55
Glosario de términos........................................................................................... 56
Apéndice A: Diagramas de clases de diseño ................................................... 57
INTRODUCCIÓN
1
Introducción
Los problemas de optimización combinatoria (POC) por lo general son
intratables, debido a la complejidad computacional que presentan. Una forma de
resolver un POC es con el empleo de metaheurísticas. Las metaheurísticas son
consideradas como los métodos recomendables para conseguir soluciones
eficientes a problemas complejos.
Dentro de los POC están los problemas de planificación. Los problemas de
planificación tienen notables aplicaciones en áreas de producción, y entre ellos
está el Problema de Planificación de Trabajos Uniformes (PPTU). El PPTU es un
POC de investigación de operaciones, que restringe la ejecución de todos los
trabajos con el mismo orden de procesamiento [1]. El PPTU se utiliza mayormente
en zonas de manufactura e industria química.
En la solución al PPTU clásico y sus variantes, algunos autores emplean
metaheurísticas como: la Búsqueda Tabú (en inglés Tabu Search) [2], los
Algoritmos Genéticos (en inglés Genetic Algorithm) [3-5], el Algoritmo de
Estimación de la Distribución (en inglés Estimation of Distribution Algorithm) [6],
Algoritmos de Búsqueda Local (en inglés Local Search Algorithm) [7, 8], y según
[8] también se ha utilizado el Recocido Simulado (en inglés Simulated Annealing) y
la Optimización basada en Colonia de Hormigas (en inglés Ant Colony Optimiza-
tion), pero no se ha encontrado referencia alguna respecto al Escalador de Colinas
(EC) que se conoce en inglés como Hill Climbing [9] y la Búsqueda Aleatoria (BA)
u Optimización de Caja-Negra tratada en inglés como Black-Box Optimization [10].
En el método de Búsqueda Tabú que se propone en [2] para resolver el
PPTU, se cuenta la cantidad de iteraciones en las que no se mejora la solución en
curso, considerando esta última como la posible mejor solución. Luego el algo-
ritmo se reinicia hasta llegar al máximo número de repeticiones.
USO DE METAHEURÍSTICAS EN EL PPTU
2
En [3] se propone un nuevo Algoritmo Genético en el que la planificación de
una población de soluciones de tamaño “n”, es generada de forma aleatoria, y
para lograrlo se realizan movimientos estratégicos para ser aplicados a la primera
solución disponible en cada etapa, con el fin de generar mejores soluciones.
En [11] se hace un estudio del Problema de Planificación de Trabajos Semi-
Uniformes (PPTS), que se conoce en inglés como Job Shop Scheduling Problem,
para evaluar el comportamiento del EC y de la BA en la solución del mismo. En
[11] se presenta un mecanismo de experimentación para probar los POC, con el
uso de una biblioteca de clases llamada BiCIAM que contiene algoritmos meta-
heurísticos. Y también se propone un módulo para cargar los datos localizados en
memoria externa.
Según [12] existe un teorema llamado “No Free Lunch”, que dice que los
algoritmos de búsqueda aplicados en la solución de determinado problema, se
comportan en promedio de manera semejante, por lo que no se puede decir que
uno es superior a otro. Es por ello que se decide utilizar algoritmos simples como
la BA y el EC para resolver el PPTU, debido a que para este último, no aparecen
estudios enfocados a dichas metaheurísticas.
Situación problemática
En la actualidad existen deficiencias para resolver el PPTU, principalmente
en problemas grandes. En la bibliografía revisada no aparece ningún análisis de
comportamiento de metaheurísticas en la solución al PPTU. Los estudios consul-
tados se enfocan habitualmente en comparar algoritmos, para exponer cual ofrece
el mejor resultado.
Problema
¿Cómo se comportarían el EC y la BA en la solución del PPTU?
INTRODUCCIÓN
3
Objeto de estudio
Se enmarca en la optimización combinatoria y las metaheurísticas.
Campo de acción
El PPTU y las metaheurísticas EC y BA.
Objetivo general
Evaluar el comportamiento del EC y de la BA en la solución al PPTU.
Objetivos específicos
Para resolver el objetivo general que se plantea, se exponen los siguientes
objetivos específicos con sus respectivas tareas asociadas:
1. Elaborar un resumen del PPTU:
- Buscar información acerca de este problema.
- Detallar las características del mismo.
2. Hacer una síntesis del EC y de la BA:
- Buscar información acerca de estas metaheurísticas.
- Detallar las características de las mismas.
3. Definir una solución para el PPTU:
- Crear las clases de diseño.
- Implementar el proyecto esbozado.
- Probar el código realizado.
4. Examinar el uso del EC y de la BA en el PPTU:
USO DE METAHEURÍSTICAS EN EL PPTU
4
- Preparar un mecanismo de experimentación que utilice la solución
propuesta con el objetivo anterior.
- Ejecutar las pruebas.
5. Confeccionar un resumen de los experimentos:
- Realizar una comparación teniendo en cuenta los resultados obtenidos
con el objetivo anterior.
- Analizar los resultados.
Aportes prácticos
Con esta tesis se propone un componente de software que resuelve el PPTU
con el uso de metaheurísticas, y que soluciona además el PPTS y el Problema de
Planificación de Trabajos No-Uniformes (PPTN), que se conoce en inglés como
Open Shop Scheduling Problem. Se mejora en alguna medida, el procedimiento
de los operadores de mutación y el mecanismo propuesto para la carga de datos
presentados en [11]. Se provee un análisis del comportamiento de metaheurísticas
en la solución al PPTU. Se proporciona además, un resultado experimental para la
toma de decisiones y futuras investigaciones.
El resto del documento está organizado de la siguiente manera: en el
Capítulo 1 se hace un estudio del estado del arte del PPTU y de metaheurísticas
para resolverlo; en el Capítulo 2 se expone la modelación (diseño) del componente
de software que soluciona el PPTU; y en el Capítulo 3 se muestran los resultados
alcanzados por las pruebas que se realizan al componente propuesto en el
Capítulo 2, con instancias del PPTU tomadas de la literatura.
ESTADO DEL ARTE
5
Capítulo
1. Fundamentos teóricos
En el presente capítulo se exponen los aspectos directamente relacionados
con el PPTU. Se definen los problemas de optimización (PO) y se concreta
especialmente en los POC. Se clasifican y se caracterizan los procedimientos
heurísticos y metaheurísticos, y se detallan algunos operadores de mutación.
Además se realiza una síntesis de los métodos EC y BA que se proponen como
formas de resolver el PPTU. Asimismo de BiCIAM que suministra estas metaheu-
rísticas. Se describe el PPTU presentándose una breve definición, ejemplo y otras
particularidades del mismo. Conjuntamente se explican otros problemas de planifi-
cación que existen en la literatura.
1.1 Optimización
En matemáticas, la optimización es el proceso de encontrar el mejor
elemento de un espacio de soluciones. Un PO se determina por la siguiente
definición.
Definición 1.1: Problema de optimización [13-16]
Sea:
F: función objetivo.
X: conjunto de variables, X = x1, x2, x3,…, xn.
Ω: conjunto de restricciones impuestas a X.
S: espacio de búsqueda para el cual están definidas F y Ω.
i. Obtener un x* para satisfacer que x* ∈ S: F(x*) ≤ F(x), ∀x ∈ S.
ii. Obtener un x* para satisfacer que x* ∈ S: F(x*) ≥ F(x), ∀x ∈ S.
USO DE METAHEURÍSTICAS EN EL PPTU
6
La solución x* está sujeta al objetivo de F, si lo que se desea es minimizar el
problema, la respuesta está dada por i, en caso contrario por ii (maximizar).
La función a optimizar F o función objetivo, trata de encontrar los valores
máximos o mínimos de un espacio de búsqueda o dominio. Cuando se quiere
maximizar F, los valores óptimos son los máximos y para minimizarla son los
mínimos.
Las variables son los elementos de un conjunto finito sobre las cuales se
desea tomar decisiones. Por ejemplo, se tiene un vector de datos X = x1, x2, x3,…,
xn, luego x1, x2, x3,…, xn se denominan variables de decisión. Los valores
específicos de estas últimas se llaman soluciones.
Las restricciones son limitaciones a las cuales están sometidas todas las
variables. Las restricciones también están definidas en el espacio de búsqueda de
la función objetivo. Una solución factible es aquella que cumple con todas las
restricciones.
Un óptimo local, es una solución factible xn de F mejor o igual que cualquier
otra solución próxima a ella. Un óptimo global es el óptimo local supremo (x*).
Por lo tanto, no existe mejor solución al óptimo global, y por ende es el valor que
más favorece a la función objetivo.
1.1.1 Optimización combinatoria
La optimización combinatoria es una rama de la optimización. La combi-
natoria analiza cuantas posibilidades existen de tomar los objetos de un dominio
finito, y dependiendo del problema, las operaciones pueden ser de variaciones,
combinaciones o permutaciones [17]. Las permutaciones son combinaciones
factibles de todos los elementos de un conjunto ordenado de “n” existentes. Luego
existen n! (n-factorial) maneras de organizar ese conjunto.
ESTADO DEL ARTE
7
Ej. ¿De cuántas formas se pueden organizar las vocales? Se sabe que
existen 5 vocales en el alfabeto, entonces hay 120 maneras de ordenarlas.
5! = 5 × 4 × 3 × 2 × 1 = 120: (A,E,I,O,U), (U,A,O,I,E),…, (O,E,A,U,I).
Los POC tratan de dar solución a problemas clasificados como “difíciles de
resolver” reduciendo el tamaño eficaz del espacio de búsqueda, usualmente
grande, para explorarlo eficientemente, sin tener que revisar todas las posibles
soluciones, en busca del óptimo global [14, 18]. Un POC se determina por la
siguiente definición.
Definición 1.2: Problema de optimización combinatoria [19]
Sea:
F: función objetivo.
X: conjunto de variables, X = x1, x2, x3,…, xn.
Ω: conjunto de restricciones impuestas a X.
D: conjunto de dominios variables, D = d1, d2, d3,…, dn.
S: espacio de búsqueda para el cual están definidas F y Ω.
i. Obtener un s* para satisfacer que s* ∈ S: F(s*) ≤ F(s), ∀s ∈ S.
ii. Obtener un s* para satisfacer que s* ∈ S: F(s*) ≥ F(s), ∀s ∈ S.
La solución s* está sujeta al objetivo de F, si lo que se desea es minimizar el
problema la respuesta está dada por i, en caso contrario por ii (maximizar). La
solución s* es el óptimo global y se dice que s* = (x1, v1),…, (xn, vn) | vi ∈ di.
Por la Definición 1.2, un estado se determina por el vector (xn, vn) donde xn
es la variable de decisión y vn es una permutación con evaluación xn. Luego, el
conjunto de todos los estados conforma el espacio de búsqueda (S).
Un PO clásico busca un elemento que cumpla con los requerimientos de
óptimo global, en cambio en un POC, el óptimo global es un estado que permite
ofrecer el mejor beneficio para la función objetivo (s*). Es preciso comentar que en
USO DE METAHEURÍSTICAS EN EL PPTU
8
determinadas ocasiones es imposible lograr el mejor estado, muchos problemas
son complejos y clasificados como “intratables”. En estos casos, los algoritmos
intentan encontrar un buen estado cerca al óptimo (~s*), que se le considera
solución aproximada.
Los POC se relacionan con la clase de complejidad NP1 [10, 20]. Los
problemas de la familia NP por lo general son intratables, debido a que no es
posible implementar un método exacto, que ofrezca la mejor solución en un tiempo
aceptable [10, 14, 21]. Los problemas P y NP-Completo (NP-C) pertenecen a la
clase NP. Los problemas NP-C se consideran como los más complejos [22].
Por la situación que se detalla en los dos párrafos anteriores, es que en la
literatura se sugiere el empleo de procedimientos heurísticos para resolver los
POC, con el objetivo de tratar de explorar el espacio de búsqueda con mejor
rendimiento, principalmente en instancias de problemas grandes.
El autor de la presente tesis aclara, que cuando se emplea el término
“optimizar”, se refiere a la optimización combinatoria y no a la clásica, porque el
campo de acción de la presente investigación está en el área de planificación, que
se relaciona con este tipo de problema.
1.2 Heurísticas
La palabra heurística proviene del término griego eureka, que significa “¡lo
encontré!”. Una heurística es un método que usa conocimiento para dar una
buena solución a determinado problema complejo de forma rápida. Muchos
autores definen el término heurística en diferentes maneras, de [23] se toma la
siguiente definición:
1 Es el acrónimo en inglés de Polinomio-de-tiempo No-Determinista (Non-Deterministic Polynomial-
time).
ESTADO DEL ARTE
9
“procedimiento para el que se tiene un alto grado de confianza en que
encuentran soluciones de alta calidad con un coste computacional razonable,
aunque no se garantice su optimalidad”
En [24] y otros, se expresan las siguientes razones para emplear heurísticas:
cuando el problema es tan complicado que no existe un método exacto para
resolverlo, o bien cuando existe ese método exacto, pero su uso es computacio-
nalmente costoso (Ej. los problemas NP). Las heurísticas son más flexibles que
los métodos exactos, debido a que se pueden agregar condiciones difíciles de
modelar. Las heurísticas ofrecen buenos estados en poco tiempo.
Una de las formas de clasificar a las heurísticas es que sean constructivas o
de búsqueda local [14, 21, 25, 26]. Las heurísticas constructivas parten de un
primer estado que posteriormente se va mejorando añadiendo nuevos comple-
mentos. Las heurísticas de búsqueda local, a partir de un estado inicial, en cada
iteración buscan un óptimo local mejor al estado actual, y de cumplirse esta
condición se efectúa un cambio por el nuevo estado encontrado. Al proceso de
cambiar un estado por otro mejor se le conoce como actualización del estado.
Es importante destacar que buscar un óptimo local no es recomendable,
porque es posible que el valor específico obtenido esté lejos del óptimo global.
Esta inconveniente dio lugar al nacimiento del término “metaheurística” cuyo
propósito general es mejorar sustancialmente las respuestas obtenidas por las
heurísticas tradicionales [14].
1.2.1 Metaheurísticas
La palabra metaheurística es la unión de heurística con el prefijo “meta” que
significa “a un nivel superior”. Las metaheurísticas son estrategias que guían las
heurísticas para obtener estados de alta calidad. De [11, 14, 27] se toma la
siguiente definición:
USO DE METAHEURÍSTICAS EN EL PPTU
10
“Los procedimientos metaheurísticos son una clase de métodos aproxi-
mados que están diseñados para resolver problemas difíciles de optimización
combinatoria, en los que los heurísticos clásicos no son efectivos (...) combinando
diferentes conceptos derivados de la inteligencia artificial, la evolución biológica y
los mecanismos estadísticos.”
Existen diversas formas de clasificar a las metaheurísticas, entre ellas las
más usuales son “basadas en trayectorias” o “basadas en poblaciones” [25, 27].
Las metaheurísticas basadas en trayectorias como literalmente se dice, están
determinadas por una trayectoria en la que por cada iteración, de ser posible, se
reemplaza el estado actual por uno mejor. Las metaheurísticas basadas en
poblaciones utilizan un subconjunto de soluciones denominado población, el cual
se va mejorando iterativamente.
Entre las metaheurísticas más populares se pueden mencionar: la Búsqueda
Tabú [28], el Recocido Simulado [29], el Escalador de Colinas [9, 30], los
Algoritmos Meméticos (en inglés Memetic Algorithms) [31], la Optimización basada
en Colonia de Hormigas (en inglés Ant Colony Optimization) [21], la Búsqueda
Aleatoria [5], el Procedimiento de Búsqueda Goloso, Aleatorio y Adaptativo (sus
siglas en inglés GRASP) [32], los Algoritmos Genéticos [33, 34], y los Algoritmos
de Estimación de la Distribución [35].
1.2.1.1 Operadores de mutación
El término operador en la presente investigación se emplea, como una
aplicación que lleva a cabo una operación específica sobre un número finito de
operandos. La referida operación específica, es la búsqueda de un estado mejor a
partir de un anterior. Y los operandos son los elementos que componen un estado
del problema a optimizar.
De [11] se toman los operadores que se detallan a continuación:
ESTADO DEL ARTE
11
Operador de Mutación Basado en Orden, OMBO (en inglés Order Based
Mutation Operator): se puede decir que es el operador más simple para
generar nuevos estados. Este operador toma dos operandos como parte de
una selección aleatoria en el estado y los intercambia.
Operador de Mutación Mono Objetivo, OMMO (en inglés Mono Objective
Mutation Operator): se toma un operando al azar y se intercambia con el
siguiente operando que cumplan una determinada característica.
Operador de Mutación por Cambio Enmarcado, OMCE (en inglés Frame
Shift Mutation Operator): está basado en el operador anterior, pero el
cambio se realiza con el primer operando obtenido y un nuevo operando
cualesquiera, tomado de forma aleatoria y que esté comprendido en el
marco formado por los dos primeros operandos.
Operador de Mutación por Sublista Revuelta, OMSR (en inglés Scramble
Sublist Mutation Operator): se toman dos operandos cualesquiera al azar.
Luego se mutan de forma estocástica y exhaustiva, los operandos com-
prendidos en el marco formado por los dos primeros.
Operador de Mutación por Translocalización, OMTL (en inglés Translo-
cation Mutation Operator): se intercambian dos subcadenas de operandos
con igual tamaño (k), k puede tomar valores entre 2 y la tercera parte de la
longitud (d) del estado. El primer operando de la primera subcadena está en
la posición “p”, p puede tomar valores entre 0 y (d – 2 × k). El primer
operando de la segunda subcadena se encuentra en la posición “q”, q está
entre (p + k) y (d – k).
Los operadores de mutación definen diferentes estados, y a estos últimos
que son generados por un mismo operador se les consideran soluciones vecinas.
En un POC, un óptimo local es un estado con una evaluación mejor a otras de sus
soluciones vecinas.
USO DE METAHEURÍSTICAS EN EL PPTU
12
1.2.1.2 La Búsqueda Aleatoria
La BA es una metaheurística sencilla (véase Algoritmo 1.1), basada en
trayectoria, y de búsqueda local, que se puede decir que es el método más simple
para explorar un espacio de búsqueda amplio, sin tener que analizar todas las
posibles soluciones. La BA realiza una búsqueda a ciegas o de caja negra (en
inglés black-box), teniendo como resultado la mejor de las soluciones revisadas
[20]. La BA se puede emplear tanto para un problema de minimización como para
uno de maximización.
Algoritmo 1.1: Procedimiento de la Búsqueda Aleatoria [20]
1 procedimiento BusquedaAleatoria
2 xa = solucionInicial
3 hacer
4 xc = solucionAleatoria
5 si xc esMejorQue xa entonces
6 xa = xc
7 fin si
8 hasta maximoDeIteraciones
9 retornar xa
10 fin BusquedaAleatoria
El Algoritmo 1.1 muestra el procedimiento de la BA donde xa es la solución
actual y xc es una solución candidata. El método inicia con un primer estado (L2)2,
y a partir de este último se trata de modificar la solución xc por una solución
aleatoria (L4). Si la evaluación de xc es mejor que la de xa (L5), entonces se
actualiza xa con la solución xc (L6). El método abandona la búsqueda cuando se
haya agotado el número de iteraciones asignado para dar una respuesta.
2 L2: sentencia o línea 2 del código del Algoritmo 1.1. En el resto del documento se entiende por
Ln, como la sentencia o línea “n” del procedimiento en cuestión.
ESTADO DEL ARTE
13
En la literatura se dice que muchas metaheurísticas obtienen mejores resul-
tados que la BA. Por lo general este método es rápido en cuanto a la ejecución del
mismo, pero es posible que demore en generar la solución final. Una limitante es
que no analiza el espacio de búsqueda completamente, por lo que se estarían
obviando soluciones que podrían ser vitales. Sin embargo, existe una posibilidad
de que entre las soluciones revisadas esté el óptimo global, que es el objetivo
fundamental de todo problema de optimización.
Por otra parte, se puede decir que no se tiene un dominio histórico, o sea,
que la solución escogida aleatoriamente es posible que se halla revisado con
anterioridad, y al no existir dicho control, puede que el método finalice el proceso
arrojando como respuesta, una solución bastante lejos del óptimo global.
1.2.1.3 El Escalador de Colinas
El EC es una metaheurística sencilla (véase Algoritmo 1.2), de propósito
general, basada en trayectoria, de búsqueda local [30] e inspirada en una
situación imaginaria de un alpinista que desea conocer la cima de una montaña y
para lograrlo utiliza información del terreno para escalar ascendentemente hasta
llegar a su meta [10]. El siguiente algoritmo muestra el procedimiento del EC
clásico (en inglés Any Ascent HillClimbing).
Algoritmo 1.2: Procedimiento del Escalador de Colinas [20]
1 procedimiento EscaladorDeColinas
2 xa = solucionInicial
3 hacer
4 v = vecindarioDeXa
5 xc = elMejorDeV
6 si xc esMejorQue xa entonces
7 xa = xc
8 fin si
USO DE METAHEURÍSTICAS EN EL PPTU
14
9 hasta condicionDeParada
10 retornar xa
11 fin EscaladorDeColinas
En el Algoritmo 1.2 xa es la solución actual y xc es una solución candidata.
Dicho procedimiento toma un estado inicial (L2) y luego entra en un ciclo (L3) para
obtener a xc con la selección del mejor estado de las soluciones vecinas de xa (L5)
por medio de un operador (L4). Si la evaluación de xc es mejor que la de xa (L6)
entonces se actualiza xa con la solución xc (L7). El ciclo de búsqueda termina con
la condición de parada (L9).
En [30] y otros, se exponen variantes de EC que se detallan a continuación:
Escalador de Colinas de Ascenso Mínimo, ECAM (Least Ascent Hill-
Climbing) [30, 36]: se toma una solución xc como parte de una selección
aleatoria en las soluciones vecinas de xa (L4-L5), luego se actualiza xa
como en el Algoritmo 1.2 (L6-L7). El proceso termina cuando por primera
vez se logra que xc sea mejor que xa (L7). De esta forma se reduce el costo
de buscar un óptimo local, y es posible que se obtenga una convergencia
más rápida que los demás EC.
Escalador de Colinas de Mejor Ascenso, ECMA (Steepest Ascent Hill-
Climbing) [10, 30]: a diferencia del método anterior, se toman varias
soluciones como parte de selecciones aleatorias en las soluciones vecinas
de xa (L4), la mejor de estas soluciones se le asigna a xc (L5), y se actualiza
xa como en el Algoritmo 1.2 (L6-L7). El proceso termina cuando no es
posible mejorar a xa.
Escalador de Colinas con Reiniciación, ECRI (Reverse Hill-Climbing) [20,
30]: como su nombre lo indica el método del EC se reinicia para obtener
más información. Por lo general el ECRI se representa con una función
recursiva.
ESTADO DEL ARTE
15
Los EC al igual que la BA, se puede emplear tanto para un problema de
minimización como para uno de maximización. Los EC utilizan soluciones que han
sido revisadas. La principal limitante de los EC es que convergen al óptimo local
más cercano, y como se había expuesto anteriormente “buscar un óptimo local no
es recomendable, porque es posible que el valor específico obtenido esté lejos del
óptimo global”. Sin embargo, de forma relativa en la solución de problemas
complejos, se ha logrado mejores resultados con algoritmos de EC ante otras
metaheurísticas, como se demuestra en [36].
Debe tenerse en cuenta que la limitante de los EC de dar un óptimo local, no
es tan inconveniente como se especula en la literatura. Existe una posibilidad de
que el óptimo local ofrecido por dicha metaheurística sea un óptimo global, y por la
simplicidad de los algoritmos de los EC se puede tener la mejor respuesta en el
menor tiempo posible.
1.2.1.4 BiCIAM
BiCIAM, es el acrónimo de “Biblioteca de Clases para la Integración de
Algoritmos Metaheurísticos” [37]. Esta biblioteca provee estrategias de búsqueda
aproximada aplicables en la solución de los POC. BiCIAM contiene las metaheu-
rísticas siguientes: el Escalador de Colinas (clásico y con reinicio), la Búsqueda
Aleatoria, el Recocido Simulado, la Búsqueda Tabú, Algoritmos Genéticos,
Estrategias Evolutivas y el Algoritmo de Estimación de la Distribución.
El paquete definition de BiCIAM se emplea para definir el problema a
optimizar y contiene las siguientes clases: Problem, Codification, Operator, State,
y ObjectiveFuntion.
La clase Problem de BiCIAM, permite modelar el problema a optimizar.
Problem requiere: una función objetivo, una codificación para entender la repre-
sentación del problema, un operador de mutación para generar las posibles
USO DE METAHEURÍSTICAS EN EL PPTU
16
soluciones que posteriormente se evalúan por la función objetivo y finalmente
saber si se trata de un problema de maximización o de minimización.
La clase ObjectiveFuntion de BiCIAM, modela la función objetivo de Problem,
y contiene el método Evaluation que debe ser redefinido, implementando en el
cuerpo del mismo las restricciones del problema en cuestión.
La clase abstracta Codification de BiCIAM, contiene los métodos necesarios
para manipular y validar los estados que se modelan con la clase State. Esta
última contiene una lista de objetos que abstrae la estructura del problema a
optimizar.
La clase Operator de BiCIAM, modela el operador de mutación que se
emplea en el proceso metaheurístico. Se debe redefinir el método generate-
RandomState para empezar con una solución inicial, y el método generated-
NewState para generar nuevas soluciones a partir de la anterior.
1.3 Problema de Planificación de Trabajos Uniformes
El autor de la presente tesis determina nombrar al término “makespan” de la
literatura como cualquiera de las siguientes tres formas: marca, marca de tiempo
o tiempo marca cuyo significado es el tiempo en que se logran completar todas
las operaciones de todos los trabajos, para un estado de un PPTU.
Un PPTU es un POC cuyo objetivo es obtener una combinación factible de
operaciones con la menor marca de tiempo posible. En el PPTU, las operaciones
de cada trabajo tienen un orden de ejecución, e inviolablemente un orden de
procesamiento en las máquinas. La primera operación del trabajo T tiene que
ejecutarse en la primera máquina, la segunda operación de T tiene que ejecutarse
en la segunda máquina, y así sucesivamente para todas las operaciones de T. En
el PPTU, todos los trabajos tienen el mismo procedimiento [1, 2, 5, 7, 38].
ESTADO DEL ARTE
17
A modo de ejemplo, se puede considerar una fábrica que necesita satisfacer
una demanda de camisas de diferentes tallas. Las tallas de las camisas pueden
ser: pequeña (S), mediana (M), larga (L) o extra-larga (XL). Entonces se entiende
por trabajo: hacer las camisas de talla K, donde K = S, M, L, XL. Para
confeccionar cada camisa, primero se pasa la tela por una máquina de cortar (C) y
después por una máquina de coser (P), todas las camisas pasan por C y P en ese
orden e indistintamente. Luego cada trabajo tiene dos operaciones. El propósito de
la fábrica es encontrar la manera de organizar todo el trabajo para entregar el lote
de camisas lo antes posible.
Del párrafo anterior, C y P son máquinas, que se pueden catalogar como
estaciones de trabajo. Pero, las personas que despachan maletas en un
aeropuerto, también son estaciones de trabajo. Por lo tanto, una máquina es una
estación de trabajo en la que se pueden ejecutar actividades. Las máquinas
pueden ser personas o aparatos mecánicos, y las referidas actividades son
operaciones. Luego, una operación es la actividad de un trabajo en una deter-
minada máquina.
1.3.1 Definición
Definición 1.3: Problema de Planificación de Trabajos Uniformes [1]
Sea:
M: conjunto de máquinas, M = m1, m2,…, mn, (m máquinas).
T: conjunto de trabajos, T = t1, t2, t3, t4, t5, t6,…, tn, (n trabajos).
O: conjunto de operaciones, O = o11, o12,…, o72, o73,…, oik, donde oik es la
operación del ti (i-ésimo trabajo) en la máquina k, (n × m operaciones).
pik: tiempo para procesar el ti en la máquina k.
vik: tiempo de espera en la máquina k antes de empezar el ti.
wik: tiempo de espera del ti después de finalizar el procesamiento en la máquina k
mientras se espera por disponibilidad de la máquina k+1.
USO DE METAHEURÍSTICAS EN EL PPTU
18
xij: variable de decisión booleana que toma valor 1 (true), si el trabajo j es
asignado a la i-ésima posición de la permutación, o valor 0 (false) en otro caso.
i. Obtener el estado de menor ∑ ∑
El objetivo de los PPTU es minimizar en la mayor medida posible, la marca de
tiempo Cmax para obtener un buen estado.
1.3.2 Descripción
En [1, 2, 5, 7, 38] el PPTU se describe de la siguiente manera: hay un
conjunto finito de “m” máquinas y un conjunto finito de “n” trabajos. Cada trabajo
tiene tantas operaciones como la cantidad de máquinas que existen. Todos los
trabajos ejecutan sus operaciones con igual orden en las máquinas. Cada
operación (θij) se ejecuta una vez, en una máquina y de forma ininterrumpida. No
hay restricción de prioridad entre operaciones de diferentes trabajos. Las opera-
ciones de un mismo trabajo deben ejecutarse de forma organizada, tal que θ(i+1)j
no puede comenzar hasta que θij se haya completado. Las máquinas no pueden
procesar dos operaciones a la vez.
1.3.3 Representación
El PPTU puede ser representado con permutaciones con repeticiones. Cada
repetición es una operación que indica la ocurrencia de un determinado trabajo en
la permutación. Todos los trabajos tienen la misma cantidad de repeticiones, y que
es igual al total de máquinas. La primera repetición del trabajo T, sugiere la
primera operación del trabajo T, la segunda repetición de T es la segunda
operación de T, y así sucesivamente para todas las repeticiones de todos los
trabajos.
Considérese un PPTU de tres trabajos para ser ejecutados en tres máquinas.
Por la Definición 1.3, se deben procesar 9 operaciones. Luego, una permutación
factible de repeticiones es: 3, 2, 3, 1, 2, 3, 1, 2, 1.
ESTADO DEL ARTE
19
También existen otras formas de representación que pueden ser empleadas
para comprender el PPTU, entre ellas están: las permutaciones sin repeticiones y
los grafos disyuntivos [11].
Las permutaciones sin repeticiones se inician con una serie numérica desde
1 hasta el total de operaciones. Con el ejemplo de las permutaciones con
repeticiones, se toma como asignación inicial los tres primeros elementos de la
permutación correspondiendo a las tres operaciones del primer trabajo, los
siguientes tres elementos son las del segundo trabajo, y así sucesivamente para
toda la permutación. Ej., se establece 1, 2, 3, 4, 5, 6, 7, 8, 9 para 1, 1, 1, 2, 2, 2,
3, 3, 3. La asignación inicial es para poder comprender nuevas permutaciones
generadas a partir de ella. Ej., teniendo la permutación sin repeticiones 4, 7, 1, 8,
5, 6, 2, 3, 9, el segundo elemento (7) indica la primera operación del trabajo 3, el
séptimo elemento (2) indica la segunda operación del trabajo 1, etc.
Los grafos disyuntivos están compuestos por un conjunto de nodos ponde-
rados que son considerados las operaciones de los trabajos, y cuyo peso es el
tiempo de ejecución. El camino crítico de un nodo es el camino dirigido para llegar
hasta él, y sugiere el tiempo de terminación de la operación para ese nodo. La
marca de tiempo de un problema representado con grafo disyuntivo, está dada por
el camino crítico del último nodo.
1.3.4 Ejemplo
Figura 1.1: planificación de un PPTU de 5x4
USO DE METAHEURÍSTICAS EN EL PPTU
20
En la Figura 1.1, se expone una instancia de un PPTU con cinco trabajos para
ser ejecutados en cuatro máquinas. En la sección “a”, está la tabla que tiene los
tiempos de procesamientos de cada trabajo en las diferentes máquinas. En la
sección “b”, se encuentra el Diagrama de Gantt en función del tiempo, presen-
tando el resultado del problema. Una iteración intermedia ofreció un estado factible
con marca de 36. El resultado final de la planificación, es el que se muestra con
marca de 34 unidades de tiempo para la permutación con repeticiones 3, 3, 5, 3,
5, 1, 3, 2, 1, 5, 5, 1, 4, 2, 2, 4, 1, 4, 2, 4.
1.3.5 Aplicaciones
El PPTU puede ser empleado en situaciones donde se ejecuten diferentes
trabajos que tengan el mismo procedimiento. En [39] se exponen los ejemplos
siguientes:
En empresas de impresión de libros, periódicos, etiquetas, etc., donde los
materiales utilizados para obtener esos objetos siguen el mismo patrón.
En laboratorios farmacéuticos para fabricar y envasar distintos tipos de
medicamentos como jarabes, pastillas, etc.
En fábricas de automóviles donde se construyen distintos modelos que
siguen la misma línea de ensamblaje.
1.3.6 Otros problemas de planificación
En la literatura, se expone el PPTS (Problema de Planificación de Trabajos
Semi-Uniformes), que es un caso particular del PPTU. El PPTS tiene que cumplir
las restricciones descritas en la sección 1.3.2, con excepción de la referida al
ordenamiento de las operaciones en las máquinas. En este problema, los trabajos
pueden tomar trayectorias diferentes, no necesariamente tienen que ejecutarse de
la misma manera [1]. La primera operación del trabajo T puede ejecutarse en la
ESTADO DEL ARTE
21
última máquina, la tercera operación de T puede ejecutarse en la segunda
máquina, etc.
También en la literatura está el PPTN (Problema de Planificación de Trabajos
No-Uniformes) que se determina por la situación detallada en el párrafo anterior. A
diferencia del PPTS, en el PPTN no existe orden de procesamiento entre las
operaciones de un mismo trabajo. En el PPTN se puede procesar cualquier
operación en cualquier tiempo. Las operaciones del PPTN no tienen asignación en
máquina, porque las operaciones pueden ser ejecutadas en cualquier máquina
que esté disponible, pero no se pueden ejecutar dos operaciones del mismo
trabajo concurrentemente [40, 41], aunque estén en diferentes máquinas.
1.4 Consideraciones parciales
Según la literatura, el método del EC clásico por lo general obtiene mejores
resultados que la BA.
Según la literatura, el método de la BA optimiza más rápido que el EC.
Según la literatura, la variante ECMA del EC obtiene mejores resultados
que el ECAM.
Para la mayoría de los POC es mejor usar metaheurísticas y no métodos
exactos. Hay situaciones en que es necesario una solución rápida aunque
no sea precisa, como ejemplos se pueden citar: una torre de control
aeronáutico, una estación espacial, un instituto de meteorología, etc. Los
POC son intratables, basta con una buena respuesta.
El resultado de un POC con uso de metaheurísticas, depende en parte del
operador de mutación utilizado, debido a que los operadores no actúan de
la misma manera.
USO DE METAHEURÍSTICAS EN EL PPTU
22
El PPTU es catalogado como difícil de resolver, por lo tanto, se puede
solucionar con metaheurísticas.
La representación de permutaciones con repeticiones, es más simple que
las permutaciones sin repeticiones y que los grafos disyuntivos, porque es
menos complejo contar repeticiones, a tener que actualizar la permutación
sin repeticiones cada vez que se realice un cambio, o tener que indagar en
una estructura de datos para el caso de los grafos disyuntivos.
PROPUESTA DE SOLUCIÓN
23
Capítulo
2. Propuesta de solución
Teniendo en cuenta [11], [42] y la presente investigación, por la exploración
en el área de planificación de trabajos y la compatibilidad en la forma de resol-
verse, se decide crear un componente de software en conjunto con [42], que
agrupa el PPTS, el PPTN y el PPTU. Dicho componente se nombra “BMPT”, que
es el acrónimo de “Biblioteca de Métodos de Planificación de Trabajos”.
En el presente capítulo se exponen los aspectos directamente relacionados
con el diseño de la BMPT. Se definen las piezas que son imprescindibles para la
optimización, tales como la función objetivo y los operadores. Se detallan patrones
que se toman en consideración para el diseño de la BMPT. Se explica un módulo
que unifica el PPTS, el PPTN y el PPTU. También se propone una mejora al
mecanismo de carga de datos y a los procedimientos de los operadores OMMO,
OMCE, OMSR y OMTL presentados por [11], para ser utilizados de una forma
más fácil y eficiente en otros componentes de software. Y se precisan las piezas
para experimentar las metaheurísticas EC y BA en el PPTU.
2.1 Módulo de problemas combinatorios
El autor de la presente tesis determina no utilizar BiCIAM debido a que: la
modelación de los POC no se corresponde con la Definición 1.2 (véase sección
1.1.1). BiCIAM ejecuta en el mejor de los casos, 58 instrucciones antes de la
optimización, la mayoría de las cuales son asignaciones que ocupan espacios de
memoria innecesarios. Según [30] el ECMA obtiene mejores resultados que el
ECAM, y en BiCIAM no está implementado dicho método. Además en [30] se
demuestra que el ECRI supera en resultados al ECMA y en BiCIAM no se cumple
con esto, por lo que es cuestionable la implementación de sus algoritmos. BiCIAM
USO DE METAHEURÍSTICAS EN EL PPTU
24
es en parte, un componente de software rígido que no favorece el principio de
diseño “Abierto-Cerrado” (en inglés Open-Close Principle), que indica que un
software debe quedar abierto para extensiones y cerrado para modificaciones, por
lo tanto, se descarta la posibilidad de redefinir las piezas necesarias, para cumplir
con la Definición 1.2 e implementar el ECMA. BiCIAM no cumple con el principio
de diseño “Diseñar hacia las interfaces y no hacia las implementaciones” las
clases Operator y ObjectiveFuntion de BiCIAM sólo tienen procedimientos y están
modeladas como clases comunes y no como interfaces. Este principio de diseño
favorece las interfaces porque estas últimas tienen a permanecer estables, en
cambio, las implementaciones pueden variar mucho. BiCIAM no cumple con el
principio de diseño “Hollywood” que regula la jerarquía entre clases, donde las
clases de más alto nivel interactúan con las de más bajo nivel y no viceversa. En
la vida real un problema no se sabe cómo se va a resolver, son las formas de
solución las que deben conocer el problema, tal es el caso para las clases
Problem y Operator de BiCIAM. Problem tiene una referencia de Operator que es
la que ofrece soluciones al problema, y por dicho principio no debe ser así.
El autor de la presente tesis considera que un POC debe ser modelado como
se detalla en la Definición 1.2, o sea, una función objetivo, las restricciones del
problema (que pueden ser incluidas en la función objetivo), un conjunto de
variables de decisión, un conjunto de dominios variables y por último un atributo
que funcione como bandera, para saber si se trata de maximización o de
minimización.
Por otra parte, un estado se debe interpretar como en la Definición 1.2, que
se obtiene por la combinación de una variable de decisión con un vector que se
corresponda a un dominio. Para el caso de los problemas de planificación, la
variable de decisión es el tiempo marca, y el referido vector puede ser una permu-
tación con repeticiones. Un operador debe tener métodos para elaborar la solución
inicial, y ofrecer una solución a partir de la anterior.
PROPUESTA DE SOLUCIÓN
25
Por los dos párrafos anteriores, se crea la interfaz denominada IObjective-
Function para modelar la función objetivo con un procedimiento de evaluación, que
tiene el mismo significado que el método Evaluation de la clase ObjectiveFunction
de BiCIAM. Se implementa una clase llamada CombinatorialProblem para modelar
los POC. CombinatorialProblem tiene una instancia de IObjectiveFunction, una
lista de objetos (en Java List<Object>) para las variables de decisión, una lista de
arreglos de objetos (en Java List<Object[ ]>) para los vectores de dominios
variables y finalmente el atributo problemType de la clase Problem de BiCIAM, que
se agrega a CombinatorialProblem con el mismo principio. Se define la interfaz
nombrada IOperator para los operadores con los métodos getInitialSolution, y
getRandomState para generar en ese orden, la solución inicial, y una solución
aleatoria a partir de una anterior. Se implementa la clase State para modelar los
estados generados por los operadores. State tiene un atributo genérico (en Java
Object) para la variable de decisión y un arreglo de objetos (en Java Object[ ])
para los vectores de dominios variables.
Para las metaheurísticas se define la interfaz IMetaheuristic con un procedi-
miento llamado optimize para ser utilizado por los algoritmos de búsquedas. El
método optimize recibe como parámetros: un operador, el problema a optimizar, y
la cantidad de iteraciones que sirve como condición de parada. Para la BA y el
ECMA se implementan las clases BlackBoxOptimization y SteepestAscentHill-
Climbing con realización de IMetaheuristic, para redefinir optimize con Algoritmo
1.1 y Algoritmo 1.2 (véase secciones 1.2.1.2 y 1.2.1.3) respectivamente.
En algunos casos, los algoritmos metaheurísticos requieren de un tiempo
desmedido para elaborar la respuesta final. Por esta razón está también en la
interfaz IMetaheuristic el método stopOptimization, con el propósito de garantizar
la parada dinámica del proceso de búsqueda, sin que esto conlleve a la pérdida de
la solución encontrada hasta el momento. Para las clases que tengan una relación
de realización con la interfaz IMetaheuristic, deben incluir un atributo bandera de
tipo booleano, que sirva como condición de parada del método optimize. Para las
USO DE METAHEURÍSTICAS EN EL PPTU
26
clases BlackBoxOptimization y SteepestAscentHillClimbing al referido atributo se
le denomina STOP. En la Figura A.2 (véase Apéndice A), se muestran las clases
descritas en la presente sección.
2.1.1 Operadores de mutación
Los operadores se necesitan para crear nuevos estados que posteriormente
se evalúan por la función objetivo. Para la BMPT se reimplementan los operadores
OMMO, OMCE, OMSR y OMTL descritos en la sección 1.2.1.1 expuestos por [11].
Todos los operadores propuestos con esta tesis por convenio con [42], implemen-
tan la interfaz IOperator que se detalla al inicio del presente epígrafe, y responden
a la representación de permutaciones con repeticiones.
El estudio de la eficiencia de los operadores de mutación en cuestión, parte
de la ilegibilidad y complejidad del código. Por lo general al diseñar un algoritmo,
se trata de que sea lo más simple posible para facilitar su comprensión, y de ser
necesario el mantenimiento del mismo.
2.1.1.1 Análisis de operadores
Para analizar los operadores OMMO, OMCE, y OMSR propuestos en [11] y
con la presente tesis, se consideran los siguientes factores: simplicidad, cantidad
de operaciones elementales y la calidad de las respuestas.
No se realiza el análisis con el OMTL porque no se puede asegurar que la
propuesta de [11] para este operador funcione correctamente, debido a que las
definiciones de “k”, “p” y “q” (véase OMTL en la sección 1.2.1.1) no son las
adecuadas. El OMTL tiene como principio mutar dos subcadenas de operandos de
igual tamaño k en una solución, donde p es la posición del primer elemento de la
primera subcadena, y q es la posición del primer elemento de la segunda
subcadena. En el OMTL de [11]: k = 3, p = random × (max – 2 × k + 1) y q =
random × (((max – k + 1) – (p + k)) + (p + k)), donde random es un número
PROPUESTA DE SOLUCIÓN
27
aleatorio, y max es la cantidad de operaciones. No tiene sentido que k forme parte
de las fórmulas para determinar p y q, debido a que k tiene un valor fijo que es
igual a 3. De esta forma queda p = random × (max – 5) y q = random × (max – 2).
En el peor de los casos q puede tomar valor (max – 2), y como k = 3 se ocasiona
un error de posición fuera de rango. También p y q pueden tomar valores iguales,
y por lo tanto no se logra mutar ni siquiera un elemento.
En el OMTL que se propone con la presente tesis, k toma valor entre 2 y la
tercera parte de la longitud (d) del estado, que permite intercambiar las cadenas
en proporción al total de operaciones, p está en el rango [0, (d – 2 × k)], y el
parámetro q en [(p + k), (d – k)]. Los elementos k, p y q toman valores de sus
rangos estocásticamente. De esta forma se garantiza que no se solapen las
subcadenas escogidas, que se mute la totalidad de los operandos, y lo más
importante, la no ocurrencia de un error de posición fuera de rango.
Ej., para la permutación 3, 2, 3, 1, 2, 3, 1, 2, 1 con el OMTL propuesto con
la presente tesis: d = 9, k = [2, 3] = 3, p = [0, 3] = 3 y q = [6, 6] = 6. Luego, p´ = 1,
2, 3 y q´ = 1, 2, 1, se intercambian ambas subcadenas para quedar lo siguiente:
3, 2, 3, 1, 2, 1, 1, 2, 3.
También es de importancia el uso adecuado de los recursos. O sea, tener
una noción de la memoria y el tiempo que se necesita para ejecutar el algoritmo.
No siempre el usuario posee un equipo de cómputo avanzado.
A la hora de medir el tiempo se cuenta la cantidad de operaciones elemen-
tales (OE) que son instrucciones del algoritmo que ejecuta el compilador. Son OE:
las aritméticas básicas (+, –, ×, /), las asignaciones a variables de tipos predefi-
nidos, los saltos (llamadas a funciones, retornos, etc.), las comparaciones (&&, ||,
==, >=, <=) y el acceso a estructuras indexadas (vectores, matrices, etc.).
USO DE METAHEURÍSTICAS EN EL PPTU
28
Tabla 2.1: Número de operaciones elementales de operadores3
Operaciones propuestos por [11] propuestos con esta tesis
OMMO OMCE OMSR OMMO OMCE OMSR
Accesos 15 22 8 6 6 4
Aritméticas 12 17 14 6 7 12
Asignaciones 31 23 20 13 14 15
Comparaciones 10 15 5 9 10 5
Saltos 30 22 18 13 14 21
Total 98 99 65 47 51 57
En Tabla 2.1, está la cantidad de OE que realizan los operadores OMMO,
OMCE, y OMSR propuestos por [11] y con la presente tesis respectivamente. El
número de OE de los operadores propuestos con la presente tesis es inferior a los
propuestos por [11].
De [43] se toma la instancia "car1” de 11 trabajos con 5 máquinas. Se eje-
cutan los operadores OMMO, OMCE, y OMSR propuestos por [11] para obtener
en ese orden, las marcas de tiempos 13713, 13379 y 14875, como promedio de
12 pruebas de 5000 iteraciones cada una. También se ejecuta la propuesta de la
presente tesis para dichos operadores en las mismas condiciones, para obtener
las marcas 8799, 8679 y 8716 respectivamente.
El OMMO que se propone con la presente tesis, toma un operando como
parte de una selección aleatoria en la permutación, y lo intercambia con el
siguiente operando que sea de la misma máquina. Si no se encuentra el segundo
operando, se reinicia la búsqueda en sentido contrario.
El OMCE que se propone con la presente tesis, selecciona un operando al
azar y busca el segundo operando que sea del mismo trabajo de igual modo que
en OMMO. Luego se toma estocásticamente un tercer operando cualesquiera que
3 Los datos de la tabla no son exactos.
PROPUESTA DE SOLUCIÓN
29
esté en el marco formado por los dos primeros y se intercambia con el primer
operando obtenido.
Se toman otros dos operadores que se proponen en [11]. Uno de ellos se
denomina RandomCombinationMutationOperator, que ofrece por cada iteración de
la metaheurística, un operador tomado de forma aleatoria del conjunto O = OMTL,
OMSR, OMMO, OMBO, OMCE. El otro operador se llama SecuencialCombina-
tionMutationOperator y su función es cambiar el operador de mutación en curso
por otro operador del conjunto O (en ese orden) cada 100 iteraciones.
2.1.2 Función objetivo
Sin subestimar otros elementos, se puede decir que la función objetivo es el
factor fundamental para todo problema, ya que estos se resuelven de manera
diferente. La función objetivo es la encargada de evaluar las restricciones para dar
una respuesta.
La BMPT necesita una función objetivo común para el PPTS, el PPTN y el
PPTU. En [11] se presenta un algoritmo que resuelve el PPTS, que puede ser
empleado de la misma forma en el PPTN y en el PPTU, porque estos problemas
de planificación sólo se diferencian en el procesamiento de las operaciones. El
Algoritmo 2.1 proporciona la evaluación (tiempo marca) de un estado entrado por
parámetros.
Algoritmo 2.1: Procedimiento de la Función Objetivo [11]
1 procedimiento Evaluacion(estado)
2 referencia = nueva Referencia
3 para i = 0 hasta estado->vector->longitud hacer
4 operacion = operacionActual
5 tiempo = 0
6 tpm = referencia->tiempoPrevioDeMaquina
7 tpt = referencia->tiempoPrevioDeTrabajo
USO DE METAHEURÍSTICAS EN EL PPTU
30
8 si tpt esMejorOIgualQue tpm entonces
9 tiempo = tpt + operacion->tiempo
10 sino
11 tiempo = tpm + operacion->tiempo
12 fin sino
13 referencia->actualizarTiempoMarca
14 referencia->actualizarTiempoDeTrabajo
15 referencia->actualizarTiempoDeMaquina
16 i++
17 fin para
18 retornar referencia->tiempoMarca
19 fin Evaluacion
El Algoritmo 2.1 empieza con la inicialización de la referencia (L2) que se
utiliza para controlar la ejecución de las operaciones (L13-L15), y finalmente
ofrecer el tiempo marca para el estado en cuestión (L18). Luego entra en un ciclo
(L3) para evaluar el estado entrado por parámetro con las restricciones del
problema a optimizar.
El método operacionActual (L4) espera un entero (int) que sugiere la posición
de la operación en curso. Para el caso del PPTS y el PPTU, dicho entero se usa
para contar la cantidad de repeticiones que ha tenido el trabajo actual, en aras de
satisfacer la restricción de ordenamiento de las operaciones de un mismo trabajo.
Y para el caso del PPTN, al referido entero sólo se toma para identificar el trabajo
en cuestión.
La clase Referencia (en inglés Reference) de la línea 2 del Algoritmo 2.1,
tiene dos estructuras (arreglos) de números. La primera estructura es el registro
de los tiempos de las operaciones en los trabajos. Cada nodo de esta estructura
corresponde a un trabajo, y por cada iteración del ciclo (L3), se actualiza el tiempo
de ejecución del mismo (L13-L15). Ej., para el estado 3, 2, 3, 1, 2, 3, 1, 2, 1, i = 2
(i empezando en 0), suponiendo que es un PPTU y que todas las operaciones
PROPUESTA DE SOLUCIÓN
31
demoran 3 unidades de tiempo en procesarse, el registro de trabajos es -1, 6, 6.
O sea, ninguna operación del trabajo 1, una operación del trabajo 2 que se ejecuta
después de concluir la primera operación del trabajo 3 (3, 2, -), y posteriormente
la segunda operación del trabajo 3 (3, 2, 3). La otra estructura corresponde al
registro de las operaciones en las máquinas, en este caso las máquinas son
nodos de igual forma que son los trabajos. Tomando el mismo ejemplo, el registro
de máquinas es 6, 6, -1. Esto se debe a que se han ejecutado las primeras
operaciones de los trabajos 2 y 3 (3, 2, -), la segunda operación del trabajo 3 (3,
2, 3), pero no se ha ejecutado la tercera operación de ningún trabajo.
2.2 Módulo de optimización
Patrón: Fachada (en inglés Facade).
Tipo: Estructural.
Descripción: Se define una interfaz unificada que representa al subsistema, y que
puede ser utilizada fácilmente en un nivel más alto [44, 45].
El patrón Fachada se puede utilizar cuando existe un número elevado de
dependencias entre clientes4 y las clases que componen un subsistema. La
interfaz que actúa como fachada permite reducir esas dependencias, haciendo
que los clientes se comuniquen con ella. También se favorece la independencia y
la portabilidad del subsistema.
Se implementa la clase Optimizer como fachada del Módulo de problemas
combinatorios (véase sección 2.1). Optimizer tiene un método llamado optimize
que invoca al método del mismo nombre de la metaheurística en cuestión, para
obtener el resultado final del algoritmo. Optimizer tiene por tanto, una relación de
asociación con multiplicidad 0-1 navegable hacia la interfaz IMetaheuristic, para
llevar a cabo el proceso de optimización, y por consiguiente tiene una referencia
4 clase que consume funcionalidades de otras clases.
USO DE METAHEURÍSTICAS EN EL PPTU
32
de la clase State, debido a que es la solución suministrada por la metaheurística, y
que se proporciona a las clases clientes.
2.3 Módulo de problemas de planificación
Patrón: Estrategia (en inglés Strategy).
Tipo: Conductual.
Descripción: Se define una familia de algoritmos encapsulados y por separados
para ser intercambiables. La estrategia permite a los algoritmos variar con inde-
pendencia del cliente que lo usa [44, 45].
El patrón Estrategia por lo general se utiliza, cuando se tiene un conjunto de
clases que sólo se diferencian por sus comportamientos. Este patrón separa las
partes que son variables de las que son fijas, para que puedan modificarse en
tiempo de ejecución. La Estrategia se debe emplear cuando es preciso tener
varias implementaciones del mismo algoritmo, o bien cuando un algoritmo utiliza
datos que no tienen por qué estar relacionados con los clientes.
El PPTS, el PPTN y el PPTU tienen las siguientes características que son
comunes: cantidad de trabajos, cantidad de máquinas y un conjunto de opera-
ciones. Sin embrago, estos problemas no se construyen de igual forma debido a
que las instancias contenidas en ficheros no son las mismas, porque no es igual la
asignación de las operaciones en las máquinas. Consecuentemente las opera-
ciones tienen diferentes normas de procesamiento (véase la sección 1.3.6).
De la Figura A.3 (véase Apéndice A), SchedulingProblem es la clase que
contiene el conjunto de atributos y métodos que son comunes para los problemas
de planificación, y se implementa tomando en consideración la Definición 1.3
(véase sección 1.3.1). La interfaz IStrategy contiene los métodos buildProblem y
getOperation que deben ser redefinidos para garantizar la objetividad de cada
problema en específico. Las clases JobFlowShop, y OpenShop implementan los
PROPUESTA DE SOLUCIÓN
33
métodos de IStrategy, que sugieren la construcción del problema y el procesa-
miento de las operaciones para el PPTS-PPTU y el PPTN respectivamente. La
clase SchedulingProblem es una generalización de CombinatorialProblem.
Se decide juntar el PPTS y el PPTU en una sola clase (JobFlowShop) porque
dichos problemas sólo se diferencian en el orden de procesamiento de las opera-
ciones de un mismo trabajo (véase la sección 1.3.6), y esta última restricción se
puede controlar con los datos almacenados en los ficheros.
2.4 Mecanismo de carga de datos
Para optimizar un problema, es necesario un módulo que sea capaz de
cargar los datos que están contenidos en ficheros, y ubicarlos en una estructura
interna. En [11] se presenta un módulo que resuelve esta situación, pero contiene
un número elevado de clases y por consiguiente varias dependencias.
El mecanismo de carga de datos propuesto por [11], se basa en el patrón
Constructor (en inglés Builder), que se utiliza para separar la construcción de un
objeto complejo de sus representaciones. También se emplea el Método Fábrica
(en inglés Factory Method) como complementación del Constructor, donde se
define una interfaz para crear un objeto, delegando la responsabilidad de
instanciación a las subclases [44, 45].
En [11], la clase DataBuilder especifica una interfaz abstracta para crear
partes de un objeto. La clase ArrayListDataBuilder construye partes del objeto
Data por implementación de la interfaz DataBuilder. La clase DataManager,
construye el objeto con el uso de DataBuilder. Y la clase Data, representa el objeto
complejo que debe ser construido.
En [11], la clase GenericFile define la interfaz de objetos que crea el Método
Fábrica. La clase TextFile implementa la interfaz GenericFile. La clase Creator,
define una implementación de los métodos fábricas que devuelven un objeto de
USO DE METAHEURÍSTICAS EN EL PPTU
34
tipo TextFile. La clase TextFileCreator redefine el Método Fábrica para devolver
una instancia de TextFile.
El autor de la presente tesis considera, que el hecho de leer ficheros es
sencillo, lo complejo puede ser en raras veces, el formato de estos ficheros. Un
problema guardado en ficheros con un formato simple, no tiene por qué seguir
demasiadas llamadas de funciones. Por lo general, los archivos de programas
tienen una estructura simple para que sean compatibles con las diferentes
versiones de un software propio, incluso en algunos casos para ser utilizado
también por otro software. Los archivos de programas pueden tener un alto
volumen de datos, pero eso no quiere decir que sean complejos. Todo el
mecanismo de carga de datos que propone [11], es para redefinir el método de
lectura de datos readDataFile de la clase TextFile.
No es eficiente crear una clase que tenga solamente un atributo, porque la
inicialización de la misma, ocupa espacio de memoria innecesario. De [11], la
clase Data, se puede reducir a un objeto, o sea que es posible modelarla como un
atributo. Usualmente en programación, la mayoría de las estructuras de datos se
basan en listas, por lo que es conveniente la conversión de Data a una lista de
objetos (en Java List<Object>).
Para manipular ficheros con diferentes formatos, no es preciso tener clases
por separadas para leer y construir, como es el caso de TextFile y ArrayListData-
Builder propuestas en [11]. Con el uso de una interfaz se puede abstraer la lectura
de datos en un solo algoritmo, teniendo de esta forma varias implementaciones del
mismo. Y por consiguiente se reduce el número de clases.
Para el mecanismo de carga de datos que se propone en conjunto con [42]
en el presente capítulo, considerando que existen diferentes archivos que pueden
almacenar las instancias de los problemas a optimizar, se decide emplear el
patrón Estrategia (véase la descripción en la sección 2.3) que permite con un
mismo procedimiento leer ficheros de diferentes formatos.
PROPUESTA DE SOLUCIÓN
35
En la Figura A.4 (véase Apéndice A), la clase DataLoader contiene la
estructura de datos para la instancia del problema, la interfaz IScanner tiene el
método getDataFromFile para cargar los datos, y las clases TextFileScanner,
XMLFileScanner y ExcelFileScanner implementan el referido método para leer
archivos de Texto (*.txt), estándares XML (*.xml), y Hojas de cálculo de Microsoft
Excel (*.xls) respectivamente.
En la Figura A.4, las imágenes que están vinculadas a las clases Text-
FileScanner, XMLFileScanner y ExcelFileScanner, muestran el formato5 que se
asume para comprender los distintos ficheros. Para TextFileScanner y Excel-
FileScanner6, los números de la primera fila indican la cantidad de trabajos y la
cantidad de máquinas. A partir de la segunda fila, cada fila es un trabajo que está
compuesto por operaciones, donde las operaciones son pares de números, que
significan la máquina en que debe ser procesada y el tiempo de ejecución de la
misma. Para XMLFileScanner, los atributos jobs y machines de la etiqueta
problem, indican la cantidad de trabajos y la cantidad de máquinas respectiva-
mente. Luego se encuentra el conjunto de todas las operaciones de todos los
trabajos, donde cada operación se representa por la etiqueta operation, en la que
los atributos machine y time sugieren en ese orden, la máquina en que debe ser
ejecutada y el tiempo de procesamiento de la misma.
Para leer archivos con un formato diferente al que está determinado, sólo
debe crearse una clase que implemente la interfaz IScanner y redefinir el método
getDataFromFile. Luego, se pasa como parámetro al constructor de DataLoader.
Por las características que tiene el mecanismo de carga de datos propuesto
en este capítulo, se decide separarlo de la BMPT, para que tenga la condición de
módulo independiente y pueda ser utilizado fácilmente en otras aplicaciones. Al
referido mecanismo se nombra dataloader.jar, que significa “cargador de datos”.
5 Se toma como ejemplo, la instancia de un PPTU de tres trabajos a ejecutar en tres máquinas.
6 Es necesario la inclusión de la biblioteca “poi.jar” para manipular los documentos de Microsoft
Excel.
USO DE METAHEURÍSTICAS EN EL PPTU
36
2.5 Mecanismo controlador
Finalmente, se unen todas las piezas propuestas en el presente capítulo para
completar la BMPT, y para ello se utiliza el siguiente patrón.
Patrón: Controlador.
Tipo: Responsabilidad.
Descripción: Se le asigna el trabajo de controlar piezas de un componente de
software a determinadas clases específicas [46].
El patrón Controlador se relaciona con el patrón Fachada. Las clases de
control permiten centralizar acciones de un componente de software, que no están
implementadas en el cuerpo de las mismas pero que se encuentran delegadas en
otras clases. Las clases controladoras no deben tener demasiadas responsabi-
lidades ni tampoco un alto acoplamiento.
Se decide implementar una clase de control denominada Manager que
permite la manipulación de la BMPT, y que admite además ser el único punto de
aplicación. La clase Manager tiene las siguientes responsabilidades: cargar la
instancia del problema que está contenida en un fichero, buscar en lo posible la
planificación más adecuada, y ofrecer al usuario la respuesta7 de forma gráfica
(Diagrama de Gantt). CombinatorialProblem en colaboración con DataLoader, que
es la que suministra los datos del fichero, conforman la instancia del problema a
optimizar. La clase Optimizer se encarga de brindar una solución al problema
cargado. Y la clase AnalysisPanel cumple con la tercera tarea de Manager.
Manager tiene por tanto, relaciones de asociación navegables hacia las clases
anteriormente mencionadas, con multiplicidad 0-1, para favorecer el principio de
diseño “Hollywood”.
7 También puede obtenerse como objeto, con el método getSolution, de la clase Optimizer.
PROPUESTA DE SOLUCIÓN
37
2.6 Proyecto de experimentación
Para el siguiente capítulo se crea un nuevo proyecto que permite probar las
metaheurísticas ECMA y BA en el PPTU. Se implementa la clase RUM que es la
responsable de llevar a cabo la ejecución de los experimentos, y cargar las
instancias de tipo PPTU suministradas por la literatura, con el uso del método
main. RUM tiene una referencia de la clase Manager de la BMPT. Se crea la clase
Tester para configurar las pruebas, y para que garantice además el registro en
memoria externa de todas las iteraciones del proceso de optimización. RUM tiene
una relación de asociación con la clase Tester.
2.7 Consideraciones parciales
La modelación de problemas combinatorios propuesta con la presente tesis,
mejora las deficiencias que presenta BiCIAM, en la definición de los POC,
las metaheurísticas, los operadores y los estados de la optimización.
El módulo que unifica el PPTS, el PPTN y el PPTU, permite la inclusión de
nuevos problemas de planificación (Ej. el PPTU híbrido).
El código fuente del OMBO, es más simple que el de los demás operadores
de mutación expuestos en la sección 1.2.1.1.
Con la reimplementación de los operadores OMMO, OMCE, OMSR y OMTL
en la presente tesis, se reduce el número de operaciones elementales a los
operadores del mismo tipo presentado por [11].
El mecanismo de carga de datos propuesto en la presente tesis, disminuye
el número de clases y de dependencias, y mejora en alguna medida la
eficiencia, al módulo del mismo tipo presentado por [11].
USO DE METAHEURÍSTICAS EN EL PPTU
38
Capítulo
3. Análisis de los resultados
En el presente capítulo se exponen los aspectos directamente relacionados
con los experimentos. Se detalla el diseño de los mismos tomando 15 instancias
de la literatura, y se caracteriza el ambiente de prueba. Asimismo se expone el
resultado obtenido de las pruebas que se realizan a los métodos del ECMA y de la
BA. Se hace un análisis con los resultados obtenidos y una comparación entre el
ECMA y la BA.
3.1 Información del hardware
Los experimentos se ejecutan en una computadora con las siguientes carac-
terísticas: procesador (CPU) Intel Core2 Duo 3.00 GHz, memoria instalada (RAM)
2.00 GB y sistema operativo Windows 8 Enterprise.
3.2 Diseño de experimentos
Pregunta: ¿Cuál es la mejor forma de planificar un PPTU?
Indicador de rendimiento: marca de tiempo (makespan).
Parámetros: I iteraciones por cada prueba; tamaño de entrada NxM de la
instancia PPTU, donde N es la cantidad de trabajos y M es la cantidad de
máquinas; la PC descrita en la sección anterior.
Factores: tamaño de entrada NxM.
Niveles: NxM = 11x5, 13x4, 12x5, 14x4, 10x6, 8x9, 7x7, 8x8, 20x5, 20x10,
20x20, 50x5, 50x10, 50x20, 100x5.
ANÁLISIS DE LOS RESULTADOS
39
Puntos de diseño: el método de la BA y todas las combinaciones del
ECMA con los operadores OMBO, OMMO, OMCE, OMSR, OMTL, OMCA y
OMCS. Se utilizan las instancias: car1 (11x5), car2 (13x4), car3 (12x5), car4
(14x4), car5 (10x6), car6 (8x9), car7 (7x7) y car8 (8x8) de [43]. También se
utilizan las instancias: ta001 (20x5), ta011 (20x10), ta021 (20x20), ta031
(50x5), ta041 (50x10), ta051 (50x20) y ta061 (100x5) de [47]. Para todas las
instancias se emplean 10000 iteraciones. Total: 120 puntos de diseño.
Pruebas: 10.
3.3 Ambiente de prueba
Se utiliza la herramienta Excel de Microsoft para soportar los experimentos
computacionales a los algoritmos ECMA y BA. Excel permite: guardar en memoria
externa los datos de las pruebas que se realizan, insertar fórmulas para medir el
rendimiento, y generar gráficos para analizar el comportamiento de los algoritmos
en cuestión.
También se utiliza el software Eclipse para la ejecución del proyecto de
experimentación expuesto en la sección 2.6 (véase Capítulo 2). Eclipse tiene una
licencia pública, y permite compilar en tiempo real, realizar pruebas unitarias,
refactorizar el código fuente y otras funcionalidades.
3.3.1 Ficheros de salida
Los ficheros de salida son Hojas de cálculo de Microsoft Excel (*.xls), que
contienen los reportes numéricos de las mediciones del indicador de rendimiento,
en forma de matriz. Para esta última, cada fila a partir de la segunda es una
iteración, y las columnas son las pruebas. La celda obtenida por la combinación
Fila-Columna, contiene el referido reporte numérico. En la primera fila de cada
fichero, está el tiempo de ejecución de cada prueba. Todos los experimentos se
guardan en archivos por separado.
USO DE METAHEURÍSTICAS EN EL PPTU
40
Para el análisis de los datos, se determina el promedio de todas las pruebas
del indicador de rendimiento por cada fila y para cada fichero. Luego, en una
columna separada, se fija el primero de estos promedios (del mismo fichero), y a
partir de este último se itera en dicha columna, para hallar el mínimo valor entre el
promedio fijo y el promedio en curso.
3.4 Análisis del Escalador de Colinas
¿Con cuáles operadores el ECMA obtiene los mejores y peores resultados?
¿Cómo influye el tamaño (NxM) de la instancia de un PPTU, en el rendimiento del
algoritmo del ECMA?
La siguiente tabla (véase Tabla 3.1) muestra el resultado promedio de las
pruebas que se hacen a los puntos de diseño que pertenecen al ECMA. Cada
celda formada por Instancia-Operador contiene un par de números. El número de
arriba indica el tiempo marca (redondeado por defecto) y el número de abajo
señala el tiempo de ejecución del algoritmo del ECMA (en segundos y redondeado
por defecto). Los campos marcados con asteriscos (*) son soluciones relevantes
de las pruebas realizadas.
Tabla 3.1: Salida de los puntos de diseño relacionados con el ECMA
Instancia OMBO OMMO OMCE OMSR OMTL OMCA OMCS
car1 8445 10113 9091 8223 8873 7892* 8082
2 2 2 2 2 2 2
car2 8343 10774 9184 8549 9119 8211 8170*
1 1 1 2 1 2 2
car3 9249 11839 10321 8773 9483 9236 8553*
2 2 2 2 2 2 2
car4 9504 12342 10162 9376 9874 9260 9059*
2 2 2 2 2 2 2
ANÁLISIS DE LOS RESULTADOS
41
car5 8606 10567 9747 8682 9097 8565* 8575
2 2 2 2 2 2 2
car6 10361 12680 11728 10028 10206 9835 9736*
3 3 3 4 3 4 4
car7 7813 9041 8546 7354 7440 7242* 7409
2 2 2 2 2 2 2
car8 9603 11424 10744 9410 9808 9297* 9641
3 3 3 3 3 3 2
ta001 1441 1947 1588 1534 1646 1440* 1469
7 6 6 6 6 7 7
ta011 2059* 2789 2179 2198 2387 2138 2150
22 22 24 25 24 25 25
ta021 2910* 3922 3307 3139 3444 2995 2988
97 98 96 98 97 97 98
ta031 3198 4550 3268 3802 3732 3171* 3224
37 36 36 38 36 37 37
ta041 4088* 5893 4443 4957 5573 4210 4274
149 144 143 148 146 146 149
ta051 6071* 7997 6684 7508 8134 6631 6673
605 586 589 593 593 593 588
ta061 6843* 9725 6877 7881 8426 7275 7248
159 143 144 146 147 146 146
3.4.1 Uso de operadores
De la Tabla 3.1 se deduce, que por lo general la metaheurística ECMA con
los operadores OMBO, OMSR, OMCA y OMCS obtiene los mejores resultados.
Con el OMBO y el OMSR se pueden conseguir buenas marcas de tiempo como se
obtuvo en las instancias car2, car5, ta001-ta061 y car1, car3, car4, car7, car8,
USO DE METAHEURÍSTICAS EN EL PPTU
42
ta001-ta021 respectivamente. Pero el ECMA tiene el mejor desempeño con el
OMCA para las instancias car1, car2, car4-car8, ta001-ta41 y con el OMCS para
car1-car7, ta001-ta41.
Por los ficheros de salida se tiene que el algoritmo del ECMA puede alcanzar
las marcas con valores mínimos de 7038, 7376, 8231, 8512, 7974, 8330, 6760,
8477, 1377, 1967, 2771, 3039, 3766, 5204 y 6835 con el OMCA para car1, car2,
car3, car4, car5, car6, car7, car8, ta001, ta011, ta021, ta031, ta041, ta051 y ta061
respectivamente. Con el OMCS puede conseguir las marcas con valores mínimos
de 7567, 7638, 7647, 8141, 8012, 8926, 6915, 8996, 1363, 1996, 2850, 2968,
4041, 6027 y 6919 para las mismas instancias y en ese orden. Y con el OMBO se
pueden obtener para dichas instancias las marcas con valores mínimos de 7779,
7638, 7824, 8423, 8171, 9707, 7122, 9146, 1339, 1967, 2764, 2985, 3878, 5494 y
6654.
Aunque el OMSR es beneficioso, también puede ofrecer, marcas de tiempo
no sugerentes, como se obtuvo en las pruebas que se realizan a las instancias
ta031-ta061.
Según los experimentos, el hecho de combinar operadores para el ECMA es
conveniente, ya que lo que hace mal un operador, otro lo puede arreglar. Si el
ECMA quedara atrapado en un óptimo local, con el cambio del operador se puede
salir de ese estancamiento. Al parecer la combinación aleatoria o la secuencia
definida de operadores influyen en la calidad de las respuestas, debido a que el
OMCA y el OMCS hacen competencia.
Del mismo modo en que se examinan los operadores que ofrecen las
mejores soluciones, se reconocen los operadores de menor rendimiento. De la
Tabla 3.1 se deriva que el OMMO, el OMCE y el OMTL dan los peores resultados.
Siendo el OMMO el que obtuvo el valor más malo del tiempo marca para el ECMA,
en casi todas las instancias. El OMCE proporciona malas marcas en las instancias
ANÁLISIS DE LOS RESULTADOS
43
car1-car8, y ta021. El OMTL presenta marcas desfavorables en car1-car5, car8,
ta021-ta061.
Por consiguiente, no conviene mutar operandos de un estado, respondiendo
a determinado criterio como el OMMO y el OMCE. Ambos operadores tratan de
concentrar los operandos, por máquinas en el OMMO y por trabajos en el OMCE.
Por tanto, según la experimentación, con las operaciones agrupadas por objetivo
no se aprovecha con eficiencia el uso de las máquinas. No obstante, se debería
cambiar los objetivos para estos operadores, y experimentar con la nueva configu-
ración para determinar si realmente dichos operadores son inconvenientes.
Por otra parte, si ya se tiene una solución buena, intercambiar subcadenas
de la solución en cuestión puede afectar la respuesta del algoritmo. Tal es el caso
del OMTL, que es el que cumple con este principio. Si el OMMO y el OMCE son
malos por agrupar, el OMTL es malo por separar las operaciones de los trabajos.
Si bien el OMMO, el OMCE y el OMTL califican como inapropiados, no se
puede decir que son absolutamente inconvenientes, ya que el OMCA y el OMCS
obtienen buenos resultados, y para ello utilizan parcialmente dichos operadores.
Además el OMCE obtuvo en ocasiones, marcas de tiempo aceptables en las
instancias ta001, ta011, ta031 y ta061.
3.4.2 Convergencia
Se puede decir que el algoritmo del ECMA converge, cuando en una determi-
nada iteración se obtiene una solución que no se mejora en lo adelante, y por lo
tanto, se supone como el resultado final del algoritmo.
Considérese un plano de dos dimensiones, en el que el eje de las Y sugiere
el tiempo marca, y el eje de las X la cantidad de operaciones (NxM). La ecuación
de la recta del plano XY se define por la función lineal Y = MX + N. La pendiente M
indica que cuando aumenta el valor de X en una unidad, aumenta el valor de Y en
M unidades. Los valores de Y y X son directamente proporcionales, por lo tanto,
USO DE METAHEURÍSTICAS EN EL PPTU
44
mientras mayor sea el número de operaciones que tenga la instancia del problema
a optimizar, más iteraciones se requieren para ofrecer una buena solución.
La siguiente tabla muestra la repetición de las pruebas con 20000, 25000,
30000, 35000 y 40000 iteraciones para las instancias ta021, ta031, ta041, ta051 y
ta061 respectivamente. Los valores de las celdas de la Tabla 3.2, tienen el mismo
significado que en la Tabla 3.1.
Tabla 3.2: Repetición de algunos puntos de diseño del ECMA
Instancia OMBO OMMO OMCE OMSR OMTL OMCA OMCS
ta021 2889 3922 3269 3100 3347 2950 2949
211 208 213 214 209 203 200
ta031 3193 4550 3268 3750 3609 3171 3155
93 96 101 104 105 135 124
ta041 4008 5893 4333 4822 5255 4083 4147
460 455 477 497 494 451 450
ta051 5761 7997 6504 7195 7717 6341 6419
2098 2057 2082 2320 2103 2160 2218
ta061 6755 9725 6826 7658 7983 7018 7005
618 600 587 612 595 610 595
Los tiempos marcas de la Tabla 3.2 son inferiores a los de la Tabla 3.1,
entonces se puede decir, que para el algoritmo del ECMA se necesitan iteraciones
en proporción con la cantidad de operaciones. Es importante destacar que el valor
de X (del ejemplo Y = MX + N), se afecta en parte por la cantidad de trabajos a
procesar. La instancia car1 (11x5) tiene más operaciones que la instancia car2
(13x4), asimismo las instancias ta021 (20x20) y ta031 (50x5). En las pruebas
realizadas, el ECMA con el OMCS obtiene las mejores soluciones en las iteracio-
nes 8466, 9663, 17255 y 24042 para car1, car2, ta021 y ta031 respectivamente.
ANÁLISIS DE LOS RESULTADOS
45
Lo anterior se debe a que el algoritmo del ECMA necesita más iteraciones,
cuando se tiene un considerable número de trabajos respecto al total de opera-
ciones. Por ejemplo, la instancia ta021 de 20 trabajos en 20 máquinas, tiene casi
el doble de operaciones (400) que la instancia ta031 de 50 trabajos en 5 máquinas
(250), pero para ta031 se necesitan más iteraciones, porque es más complejo
planificar 50 trabajos.
3.5 Análisis de la Búsqueda Aleatoria
La siguiente tabla (véase Tabla 3.3) muestra los datos de las pruebas que se
hacen a los puntos de diseño relacionados con la BA. La celda formada por
Instancia-Dato contiene un par de números que tiene el mismo significado que en
la Tabla 3.1 (Resultados de los puntos de diseño del ECMA). El número de arriba
es el tiempo marca (redondeado por defecto) y el número de abajo es el tiempo de
ejecución del algoritmo de la BA (en segundos y redondeado por defecto).
Tabla 3.3: Salida de los puntos de diseño relacionados con la BA
Instancia Dato Instancia Dato Instancia Dato
car1 12626
car2 12408
car3 14055
MR8 MR8 MR8
car4 13705
car5 12737
car6 15022
MR8 MR8 MR8
car7 10777
car8 13499
ta001 2254
MR8 MR8 1
ta011 3185
ta021 4389
ta031 4579
4 17 7
ta041 6257
ta051 9359
ta061 9407
27 107 27
8 Es el acrónimo de Muy Rápido, o sea, que se realiza en menos de 1 segundo.
USO DE METAHEURÍSTICAS EN EL PPTU
46
Aunque el comportamiento de la BA es irregular, es conveniente tener un
número de iteraciones en proporción a la cantidad de trabajos respecto al total de
operaciones, por la misma situación que se detalla en la sección 3.4.2.
De los ficheros de salida se tiene que el algoritmo de la BA puede alcanzar
marcas con valores mínimos de 9190, 9221, 10454, 10456, 9386, 11435, 7800,
10299, 1726, 2295, 3086, 3434, 4142, 5388 y 6692 para las instancias car1-ta061
respectivamente.
3.6 Comparación entre algoritmos
Se halla el promedio de las marcas con los operadores OMCA y OMCS del
ECMA obtenidas para cada instancia de la Tabla 3.1. El ECMA toma valores por
defecto de 7987, 8190, 8894, 9159, 8570, 9785, 7325, 9469, 1454, 2144, 2991,
3197, 4242, 6652 y 7261 para car1-ta061 respectivamente. Y para la BA se toman
los valores específicos de la Tabla 3.3. Por los datos anteriores, se puede decir
que generalmente el método del ECMA obtiene mejores resultados que la BA. Sin
embargo, de los valores mínimos posibles tomados de los ficheros de salida, se
tiene que la BA ofrece en la instancia ta051 un mejor resultado a los dados por el
ECMA con los operadores OMCS y OMBO, y del mismo modo para la instancia
ta061 ante el ECMA con el OMCA y el OMCS.
También se mide el tiempo de ejecución de los algoritmos del ECMA y de la
BA. Tomando en cuenta los valores de la Tabla 3.1 y la Tabla 3.3, se deduce que
el método de la BA responde al proceso de optimización, en un considerable
tiempo inferior al del ECMA.
3.7 Consideraciones parciales
Los operadores OMBO, OMCA y OMCS ofrecen los mejores resultados al
método del ECMA.
ANÁLISIS DE LOS RESULTADOS
47
El ECMA con los operadores OMMO, OMCE y OMTL obtiene malos valores
del tiempo marca, principalmente con el OMMO y con el OMTL.
El OMSR por lo general ofrece resultados moderados (ni bueno, ni malo) al
ECMA.
El operador OMMO presenta el peor rendimiento para el ECMA.
Para resolver un PPTU con los métodos del ECMA y de la BA, se necesitan
más iteraciones cuando se tiene un considerable número de trabajos
respecto al total de operaciones.
La BA actúa más rápido que el ECMA.
Por lo general el ECMA obtiene mejores resultados que la BA.
Existe una pequeña posibilidad, de que el método de la BA proporcione
mejores resultados que el ECMA.
USO DE METAHEURÍSTICAS EN EL PPTU
48
Conclusiones
El PPTU se puede solucionar con metaheurísticas.
La calidad de la respuesta de las metaheurísticas para el PPTU, depende
en parte del operador de mutación utilizado.
El PPTU con las metaheurísticas EC y BA obtiene soluciones razonables en
un tiempo aceptable.
El ECMA obtiene los mejores resultados con los operadores OMBO, OMCA
y OMCS.
Generalmente el ECMA obtiene mejores resultados que la BA.
La BA actúa más rápido que el ECMA.
RECOMENDACIONES
49
Recomendaciones
Incluir en la BMPT otros métodos de la literatura que resuelven PPTU y que
son antecedentes de la presente investigación (véase Introducción de la
tesis). Téngase en cuenta la compatibilidad de la representación del proble-
ma, que para la BMPT se utiliza las permutaciones con repeticiones.
Buscar o crear otros operadores aplicables a la BMPT. Compararlos con el
OMBO, el OMCA y el OMCS. De superar los nuevos operadores a estos
últimos en los criterios de la sección 2.1.1.1, incluir a los mismos en la
BMPT.
Definir una función matemática para cada algoritmo metaheurístico, que
permita determinar la cantidad aproximada de iteraciones, que se necesitan
para elaborar en lo posible, la solución más adecuada. Se pueden emplear
los elementos que se detallan en la sección 3.4.2, y las herramientas Excel
o AutoCAD.
Comparar los resultados obtenidos en el Capítulo 3 con otros métodos ya
aplicados en el PPTU.
USO DE METAHEURÍSTICAS EN EL PPTU
50
Referencias bibliográficas
1. Šeda, M., Mathematical Models of Flow Shop and Job Shop Scheduling
Problems. 2007: Brno.
2. Solimanpur, M., P. Vrat, and R. Shankar, A neuro-tabu search heuristic for
the fow shop scheduling problem. 2006, Indian Institute of Technology Delhi:
New Delhi.
3. Oguz, C. and B. Cheung, A genetic algorithm for flow-shop scheduling
problems with multiprocessor tasks. 2002, Hong Kong Polytechnic University-
Ecole Polytechnique de Montreal: Hong Kong-Montreal.
4. Reeves, C., A genetic algorithm for flowshop sequencing. Computer Ops
Res, 1995. 22: p. 5-13.
5. Stephen, C. and F. Stephen, Improving Genetic Algorithms by Search Space
Reductions. 2007, Carnegie Mellon University: Pittsburgh.
6. Salhi, A., Q. Zhang, and J. Rodríguez, An Estimation of Distribution
Algorithm with guided mutation for a complex flow shop scheduling problem.
2007, University of Essex-University of Nottingham: Colchester-Nottingham.
7. Dubois, J., M. López, and T. Stutzle, Effective Hybrid Stochastic Local
Search Algorithms for Biobjective Permutation Flowshop Scheduling. 2009,
IRIDIA, CoDE & Université Libre de Bruxelles: Bruxelles.
8. Stutzle, T., Applying Iterated Local Search to the Permutation Flow Shop
Problem, University of Technology: Darmstadt.
9. Juels, A. and M. Wattenberg, Stochastic Hill Climbing as a baseline method
for evaluating Genetic Algorithms. 1994, Dept. Computer Science, University
of California at Berkeley.
BIBLIOGRAFÍA
51
10. Rosete, A., Una solución flexible y eficiente para el trazado de grafos basada
en el escalador de colinas estocástico, in CEIS. 2000, CUJAE: La Habana. p.
26-31.
11. Mitchell, L., Comparación de algoritmos metaheurísticos en el Problema de
la Planificación de Tareas, in Facultad de Informática. 2012, CUJAE: La
Habana.
12. Paredes, D., Métricas para la predicción del comportamiento de los
algoritmos metaheurísticos en problemas de optimización combinatoria, in
Departamento de Inteligencia Artificial e Infraestructura de Sistemas
Informáticos. 2011, CUJAE: La Habana.
13. Rico, V., Optimización de Procesos, in XXI Seminario Anual de Ingeniería
Química. 2004, Instituto Tecnológico de Celaya.
14. Martí, R., Algoritmos Heurísticos en Optimización Combinatoria 2003,
Universidad de Valencia. Facultad de Ciencias Matemáticas.
15. Ivorra, C., Matemáticas II. Apuntes de teoría. 2011, Universidad de Valencia.
Facultad de Economía.
16. Ramos, A. and B. Vitoriano, Modelos matemáticos de optimización. 2007,
Universidad Pontificia Comillas: Madrid.
17. Stanley, R., Enumerative Combinatorics. Cambridge University Press, 1999.
18. Talbi, E.-G., ed. Parallel Combinatorial Optimization. Wiley series on parallel
and distributed computing, ed. A.Y. Zomaya. 2006, John Wiley & Sons, Inc.
19. Blum, C. and A. Roli, Metaheuristics in Combinatorial Optimization:
Overview and Conceptual Comparison. ACM Computing Surveys, 2003. Vol.
35(No. 3): p. 268–308.
USO DE METAHEURÍSTICAS EN EL PPTU
52
20. Paredes, D. and J. Fajardo, Biblioteca de clases para la unificación de
algoritmos mataheuristicos basados en un punto, in CEIS. 2008, CUJAE: La
Habana. p. 8.
21. Alonso, S., et al. (2003) La Metaheurística de Optimización Basada en
Colonias de Hormigas: Modelos y Nuevos Enfoques.
22. Agrawal, M., N. Kayal, and N. Saxena, PRIMES is in P. Annals of
Mathematics, 2004. Vol. 2: p. 781–793.
23. Santana, J.B., et al., Metaheurísticas: una revisión actualizada. 2004, Grupo
de Computación Inteligente. Departamento de Estadística, Investigación
Operativa y Computación. Universidad de la Laguna: Tenerife. p. 47.
24. Duarte, A., J. Pantrigo, and F. Gortázar, Metaheurísticas. 2008,
Departamento de Ciencias de la Computación. URJC.
25. Valero, F.L., Metaheurísticas avanzadas para problemas reales en redes de
telecomunicaciones, in Lenguajes y Ciencias de la Computación. 2008,
Universidad de Málaga.
26. Abreu, A.L.I., et al., Algoritmos metaheurísticos para la solución de
problemas de asignación. 2009, CEIS - CUJAE: La Habana.
27. Puris, A., Desarrollo de meta-heurísticas poblacionales para la solución de
problemas complejos, in Centro de Estudios de Informática, Departamento de
Ciencia de la Computación. 2010, Universidad Central “Marta Abreu” de Las
Villas: Santa Clara.
28. Fred Glover, B.M., Búsqueda Tabú. Revista Iberoamericana de Inteligencia
Artificial, 2003. 19: p. 20.
BIBLIOGRAFÍA
53
29. Kathryn A. Dowsland, B.A.D., Diseño de heurísticas y fundamentos del
recocido simulado. Revista Iberoamericana de Inteligencia Artificial, 2001: p.
34-52.
30. Jones, T., Evolutionary Algorithms, Fitness Landscapes and Search. 1995,
University of New Mexico: Albuquerque, New Mexico.
31. Cotta, C. and A.J. Fernández, Memetic Algorithms in Planning, Scheduling,
and Timetabling.
32. Mauricio G.C. Resende, J.L.G.V., GRASP: Greedy Randomized Adaptive
Search Procedures Revista Iberoamericana de Inteligencia Artificial, 2003.
19: p. 61-76.
33. Caarls, W., Genetic Algorithm Visualization, in Faculty of Science. 2002,
University of Amsterdam.
34. Gen, M. and R. Cheng, Genetic Algorithms and Engineering Optimization.
Wiley Series in Engineering Design and Automation, ed. H.R. Parsei. 2000:
John Wiley & Sons, Inc.
35. Larrañaga, P., J.A. Lozano, and H. Mühlenbein, Estimation of Distribution
Algorithms Applied To Combinatorial Optimization Problems. Inteligencia
Artificial, Revista Iberoamericana de Inteligencia Artificial, 2003(19): p. 149-
168.
36. Pelta, D.A., et al., Comparación de estrategias de resolución de problemas
de programación dinámicos combinatorios. 2011: Granada.
37. Alvarez, A. and Y. González, Biblioteca de Clases para la Integración de
Algoritmos Metaheurísticos, in DIAISI. 2009, CUJAE: La Habana.
USO DE METAHEURÍSTICAS EN EL PPTU
54
38. Di-Chio, C., M. Giacobini, and J. Hemert, Workshop on Evolutionary
Computation. 2008, University of Essex, University of Torino & University of
Edinburgh: Nápoles.
39. ALGOVIDEA. Aplicaciones Flow-shop. 2011 [cited 2012 October 12];
Available from: http://www.algovidea.cl.
40. Jurcik, K., Open Shop Scheduling to Minimize Makespan. 2009, Department
of Mathematical Sciences. Lakehead University: Thunder Bay, Ontario.
41. Louis, S. and Z. Xu, Genetic Algorithms for Open Shop Scheduling and Re-
Scheduling. 2007, University of Nevada: Nevada.
42. Herrera, A., Empleo de metaheurísticas en el Problema de Planificación de
Trabajos No-Uniformes, in Facultad de Informática. 2013, CUJAE: La Habana
(Trabajo no publicado).
43. Carlier, J., Ordonnancements a contraintes disjonctives. R.A.I.R.O.
Recherche operationelle/Operations Research, 1978. 12: p. 333-351.
44. Shalloway, A. and J. Trott, Design Patterns Explained. A New Perspective
on Object-Oriented Design. 2004: Addison Wesley.
45. Gamma, E., et al., Design Patterns, Elements Of Reusable Object Oriented
Software. 2002, Addison Wesley.
46. Canales, R., Patrones de GRASP. 2005.
47. Taillard, E., Bench-marks for basic scheduling instances. European Journal
of Operational Research, 1993. 64: p. 278-285.
BIBLIOGRAFÍA
55
Bibliografía
Frederick, H. y Lieberman, G. Introducción a la investigación de operaciones.
1999, V Edición: 32-38.
Johnson, R. Matemáticas Discretas. Vol. I: 166-173.
McGeoch, C. A Guide to Experimental Algorithmics. Amherst College. Cambridge
University Press, 2012: New York, ISBN 978-0-521-17301-8.
Orihuela, C. Matemáticas para economistas. 81-124.
Rosete, A., Metaheurísticas. Combinación con la Lógica Difusa Compensatoria
para el Descubrir Conocimiento, in Taller Eureka, ENDIO-EPIO, 2009:
Buenos Aires, Argentina.
USO DE METAHEURÍSTICAS EN EL PPTU
56
Glosario de términos
Cliente: clase que consume funcionalidades de otras clases.
Convergencia: propiedad de sucesiones matemáticas de aproximarse a un límite.
Estado: se determina por el vector (xn, vn) donde xn es la variable de decisión y vn
es una permutación con evaluación xn.
Estocástico: que se realiza de forma aleatoria.
Exhaustivo: que se realiza totalmente.
Factible: que se puede llevar a cabo.
Intratable o difícil de resolver: son tipos de problemas que se pueden resolver
en teoría, pero no en práctica.
Máquina: es una estación de trabajo en la que se pueden ejecutar actividades.
Marca, marca de tiempo o tiempo marca (makespan): sugiere el tiempo total en
que se logran completar todas las operaciones de todos los trabajos, para una
permutación de un PPTU.
Operación: es la actividad de un trabajo en una máquina.
Operador: aplicación encargada de generar nuevos estados.
PPTU: es el acrónimo de Problema de Planificación de Trabajos Uniformes (en
inglés Flow Shop Scheduling Problem), cuyo objetivo es obtener una combinación
factible de operaciones con la menor marca de tiempo posible.
ANEXOS
57
Apéndice A: Diagramas de clases de diseño
Figura A.2: diagrama de clases del Módulo de problemas combinatorios
USO DE METAHEURÍSTICAS EN EL PPTU
58
Figura A.3: diagrama de clases del Módulo de problemas de planificación
ANEXOS
59
Figura A.4: diagrama de clases del Mecanismo de carga de datos