trabajo fin de grado - universidad de...

Equation Chapter 1 Section 1

Trabajo Fin de Grado

Grado en Ingeniería de Organización Industrial

Algoritmo genético para talleres de flujo híbrido con

ausencia de operaciones y minimización del

makespan. Influencia de las mejoras locales.

Autor: Manuel Burgos Martin

Tutor: Víctor Fernández Viagas

Dep. Organización Industrial y Gestión de Empresas I

Escuela Técnica Superior de Ingeniería

Universidad de Sevilla

Sevilla, 2017

3

Trabajo Fin de Carrera

Grado en Ingeniería de Organización Industrial

Algoritmo genético para talleres de flujo híbrido

con ausencia de operaciones y minimización del

makespan. Influencia de las mejoras locales.

Autor:

Manuel Burgos Martín

Tutor:

Víctor Fernández Viagas

Dep. de Organización Industrial y Gestión de Empresas I

Escuela Técnica Superior de Ingeniería

Universidad de Sevilla

Sevilla, 2017

5

Trabajo de Fin de Grado: Algoritmo genético para talleres de flujo híbrido con ausencia de operaciones y

minimización del makespan. Influencia de las mejoras locales.

El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros:

Presidente:

Vocales:

Secretario:

Acuerdan otorgarle la calificación de:

Sevilla, 2017

Autor: Manuel Burgos Martín

Tutor: Víctor Fernández Viagas

7

A mi familia

A mis amigos

A mis maestros

8

Agradecimientos

Este trabajo va dedicado a mis padres, los cuales me han ayudado estos años de carrera, a Alba, que me ha

aguantado y dado fuerzas mientras realizaba el proyecto y a todos mis profesores, en especial a mi tutor.

Manuel Burgos Martin

Sevilla, 2017

10

Resumen

En este trabajo de Fin de Grado, abordaremos el problema del taller de flujo híbrido, con la restricción de

ausencia de operaciones. Resolveremos el problema del taller aplicando un método de resolución aproximada.

En nuestro caso, hemos decidido usar un algoritmo genético básico, que constara de un cruce de dos puntos y

una mutación de intercambio. El objetivo de este tipo de problemas de programación de la producción consiste

en determinar la secuencia de entrada que nos proporcione el mejor valor para una función objetivo

determinada; en nuestro caso buscaremos reducir el makespan.

Se crearán cinco variantes distintas del algoritmo genético para resolver el problema, aplicando a cada una

distintos tipos de mejoras locales, para poder evaluar la influencia de dichas mejoras en los resultados finales

de los modelos. La primera variante no constará de ningún tipo de mejora local. El resto de variantes las

podemos dividir en dos grupos, aquellas en las que se aplica la mejora local al mejor individuo de la población

final tras cada iteración y aquellas en que se aplica la mejora a todos los individuos de dicha población. A su

vez, dentro de cada grupo habrá dos variantes, una que use una mejora local por inserción y otra variante que

use una mejora local por intercambio.

Los problemas a resolver han sido generados aleatoriamente a partir de distintos parámetros característicos

para los talleres híbridos con ausencia de operaciones. Para cada combinación de parámetros se han generado

diez instancias, formando al final una batería de problemas con 360 instancias.

11

Abstract

In this work of End of Degree, we will approach the problem of the hybrid flowshop, with the restriction of

missing operation. We will solve the workshop problem by applying an approximate resolution method. In our

case, we have decided to use a basic genetic algorithm, consisting of a two-points crossover and an exchange

mutation. The goal of this type of production scheduling problem is to determine the input sequence that gives

us the best value for a given objective function; In our case, we will seek to reduce the makespan.

Five different variants of the genetic algorithm will be created to solve the problem, applying to each one

different types of local search methods in order to be able to evaluate their influence on the final results of the

models. The first variant is the traditional genetic algorithm without local search. The other variants can be

divided into two groups: those in which the local search is applied to the best individual of the final population

(after each iteration); and, those in which the local search is applied to all the individuals of the population. In

addition, within each group there will be two variants, one that uses an insertion phase as local search and

another variant that uses exchange.

The problems to be solved have been generated randomly from different parameters characteristic for the

hybrid flowshop with missing operation. For each combination of parameters, ten instances have been

generated, forming at the end a benchmark composed of 360 instances.

13

ÍNDICE

Agradecimientos 8

Resumen 10

Abstract 11

Índice 13

Índice de Tablas 15

Índice de figuras 16

1 Introducción 18

2 Programación de la producción 20

2.1 Notación 21

2.1.1 Clasificación de los problemas de los problemas de programación 22

3 Metaheurísticas: los algoritmos genéticos 26

3.1 Tipos de metaheurísticas 26

3.2 Características de las metaheurísticas 27

3.3 Los algoritmos genéticos 28

3.3.1 Parámetros de los algoritmos genéticos 29

3.3.2 Operaciones de los algoritmos genéticos 30

4 Descripción del problema 39

4.1 El objetivo del makespan 40

5 Algoritmo genético propuesto 42

5.1 Elementos del algoritmo genético 42

5.1.1 Individuos 42

5.1.2 Población inicial 43

5.2 Cruce de dos puntos 43

5.3 Mutación de intercambio 45

5.4 Reducción 46

5.5 Poblaciones intermedias 46

5.6 Criterios de parade 47

5.7 Población final y elección de solución final 48

14

5.8 Mejoras locales 50

5.8.1 Mejora local de inserción a un individuo 50

5.8.2 Mejora local de inserción a todos individuos 51

5.8.3 Mejora local de intercambio a un individuo 54

5.8.4 Mejora local de intercambio a todos los individuos 55

6 Comparación de resultados 58

6.1 Generación de problemas 58

6.2 Análisis de los resultados en función de los parámetros 60

6.2.1 Análisis de resultados en función del número de trabajos 62

6.2.2 Análisis de resultados en función del número de etapas 63

6.2.3 Análisis de resultados en función del porcentaje de missing 65

7 Conclusiones 68

8 Bibliografía 70

9 Anexos 73

9.1 Anexo A: Resultados en Excel 73

9.2 Anexo B: Códigos en C 82

9.2.1 Código metodo I: “Normal” 82

9.2.2 Código metodo II: “Inserción1” 101

9.2.3 Código metodo III: “Inserción10” 122

9.2.4 Código metodo IV: “Intercambio1” 143

9.2.5 Código metodo IV: “Intercambio10” 164

15

ÍNDICE DE TABLAS

Tabla 6-1: Ejemplo datos para problema propuesto 59

Tabla 6-2: Resultados clasificados por parámetros 61

Tabla 6-3: Resultados en función numjobs 62

Tabla 6-4: Resultados en función del número de etapas 64

Tabla 6-5: Resultados en función del % de missing 65

Tabla 7-1: Resultados finales 69

16

ÍNDICE DE FIGURAS

Figura 2-1: Ilustración del missing. Elaboración propia 25

Figura 3-1: Ilustración cromosoma y gen. Elaboración propia 29

Figura 3-3: Ilustración ruta mínima [www.ingenieriaindustrialonline.com] 32

Figura 3-4: Cruce de un punto. Elaboración propia 35

Figura 3-5: Cruce de dos puntos. Elaboración propia 36

Figura 2-2: Esquema del Floswshop Hibrido Flexible [Fernández-Viagas,2015] 39

Figura 4-1: Ejemplo individuo. Elaboración propia. 42

Figura 4-2: Ejemplo padres para cruce. Elaboración propia. 44

Figura 4-3: Padre e Hijo en cruce. Elaboración propia. 44

Figura 4-4: Hijo realizado por cruce. Elaboración propia. 45

Figura 4-5: Ejemplo mutación por intercambio. Elaboración propia. 46

Figura 4-6: Diagrama de flujo para modelo propuesto I: “Normal” . Elaboración propia. 49

Figura 4-7: Ejemplo Inserción I. Elaboración propia. 50

Figura 4-8: Ejemplo Inserción II. Elaboración propia. 51

Figura 4-9: Ejemplo Inserción III. Elaboración propia. 51

Figura 4-10: Diagrama de flujo para modelo propuesto II: “Inserción1” . Elaboración propia. 52

Figura 4-11: Diagrama de flujo para modelo propuesto III: “Inserción10” . Elaboración propia. 53

Figura 4-12: Ejemplo Intercambio I. Elaboración propia. 54

17

Figura 4-13: Ejemplo Intercambio II. Elaboración propia. 54

Figura 4-14: Ejemplo Intercambio III. Elaboración propia. 55

Figura 4-15: Diagrama de flujo para modelo propuesto IV: “Intercambio1” . Elaboración propia. 56

Figura 4-16: Diagrama de flujo para modelo propuesto V: “Intercambio10” . Elaboración propia. 57

Figura 6-1: Gráfica resultados en función numjobs. Elaboración propia. 62

Figura 6-2: Gráfica resultados en función número etapas. Elaboración propia. 64

Figura 6-3: Gráfica resultados en función del % de missing. Elaboración propia. 66

18

1 INTRODUCCIÓN

a Programación y Control de la Producción, está inscrita dentro de la Organización de la Producción. Se

trata de un proceso que ha tomado un papel muy importante en el sector industrial, tratando de alcanzar

unos elevados grados de productividad mediante la reducción de costes, aumentando así su

competitividad. Además de invertir en mejorar para los procesos de producción, las empresas deberán dedicar

parte de sus recursos en modernizar los métodos de gestión.

De acuerdo con lo que dice Colin R. Reevest (1995), no es una opción realista buscar soluciones óptimas

para los problemas combinatorios complejos, dada la gran cantidad de tiempo que necesitan los

ordenadores actuales para llegar hasta ellos. Por ello, la mayoría de los investigadores se han centrado en

la búsqueda de soluciones mediante algoritmos genéticos aproximados o heurísticos. Uno de dichos

problemas es el estudiado por Colin R. Reevest denotado como el programa de programación en talleres

de flujo regular, en el que n trabajos tienen que ser procesados en el mismo orden por m máquinas. El

objetivo de éste es encontrar la secuencia de trabajos que minimicen el makespan, es decir, el tiempo de

salida del último trabajo en la máquina m. A partir de las ideas desarrolladas por Holland (1975), Colin R.

Reevest decidió aplicarlos al problema del permutation flowshop. También Ogbu y Smith, (1990) y Ogbu

y Smith, (1991) han mostrado que el método del recocido simulado (Simulated Annealing) da resultados

de gran calidad para el problema del flowshop.

Ante la multitud de elementos que intervienen en los procesos productivos, las metaheurísticas aparecen para

ayudar en la resolución de problemas complejos, demostrando que aportan soluciones próximas al óptimo,

empleando para ello tiempos computacionales muy competitivos frente a otros métodos.

Visto los estudios realizados por Colin (1995), Ogbu y Smith(1990), hemos decidido aplicar una

metaheurística, como son los algoritmos genéticos, para resolver el problema del taller de flujo híbrido con

ausencia de operaciones (hybrid flowshop with missing opperation)1, para ver si también se consiguen

resultados de buena calidad al igual que al aplicarlos al permutation flowshop. Aplicándole después, a nuestra

metaheurística, diferentes tipos de mejora local y compararlas entre ellas, pudiendo así observar que tipo de

mejora local se adecua mejor a diferentes problemas.

Comenzaremos este trabajo describiendo la programación de la producción y su papel dentro de la

organización de la producción en la sección 2.En la sección 3 describiremos los tipos de problemas dentro de

1 En este trabajo utilizaremos las dos notaciones indistintamente.

L

19

la programación de la producción y en concreto el nuestro, el hybrid . A continuación, en la sección 4,

trataremos el tema de las metaheurísticas y especialmente los algoritmos genéticos que hemos usado para

resolver nuestro Hybrid Flowshop y las mejoras locales aplicadas. Seguiremos explicando en la sección 5 las

distintas metaheurísticas que hemos decidido implementar para resolver nuestro problema y las mejoras que

les hemos aplicado a ellas. Por último, en las secciones 6 y 7, hemos extraído los resultados obtenidos al

aplicar nuestras distintas metaheurísticas y hemos realizado un análisis de estos resultados en función de

distintos parámetros.

20

2 PROGRAMACIÓN DE LA PRODUCCIÓN

omo ya hemos dicho en la introducción, dentro de la Organización de la Producción (Production

Management), la programación de la producción es una etapa clave, donde se toman las decisiones de

carácter operativo a corto plazo. Podemos definirla como “la asignación de un conjunto de recursos en un

periodo de tiempo, para llevar a cabo un conjunto de tareas” (Phanden et al., 2012). Por tanto, se define la

Organización de la Producción como el proceso industrial, en el que, a partir de la toma de múltiples

decisiones, se intenta asegurar la entrega al cliente de los productos deseados con el mínimo coste, el mínimo

tiempo de entrega y la máxima calidad.

Se ha intentado caracterizar la producción desde distintos enfoques, tomando como referencia el enfoque

usado por Juan Camilo López Vargas (2013) en su tesis, Metodología de programación de la producción en

un flowshop híbrido flexible, en ella enfoca la producción como un conjunto jerarquico de decisiones con tres

niveles: el nivel estratégico, en táctico y el operativo.

a) Planificación estratégica:

Al usar una visión jerárquica, solo utilizaremos la información más importante para cada nivel.

Comenzaremos el proceso de producción estableciendo la estrategia, en ella se establecerán los criterios en los

que el departamento de producción tendrá que invertir sus esfuerzos y determinar las decisiones a largo plazo.

Dada la fluctuación constante de los mercados actuales en los costes de los productos, es muy importante tener

una fiabilidad alta a la hora de cumplir pedidos en el menor tiempo posible, con unos inventarios lo mas

reducios posibles.

b) Programación táctica:

Una vez definidas las estrategias de producción, se pueden analizar los aspectos tácticos y operativos. En el

táctico, se definirán el tamaño de los pedidos y las capacidades de las que disponemos para un horizonte

temporal determinado. El alcanze de dicha planificación será a medio plazo ya que en ella se establecerán las

políticas referentes al personal.

C

21

c) Programación Operativa

En este nivel se tomarán las decisiones a corto plazo, éstas son las relacionadas principalmente con la

disponibilidad de los recursos para poder cumplir los presupuestos de producción y ejecutar los programas

establecidos en los otros niveles.

Los objetivos más comunes que se buscan conseguir en la programación de la producción se pueden clasificar

en tres grandes grupos (Naderi et al., 2010):

1. La utilización eficiente de los recursos que está relacionado con el tiempo máximo de terminación,

también llamado makespan.

2. La reducción de los tiempos de entrega, es decir, minimizar el tiempo de respuesta a las demandas,

minimizando el tiempo de proceso (WIP)

3. El cumplimiento de los plazos de entrega, cuyos medidores son la tardanza total y el número de

trabajos retrasados.

2.1 Notación

Para este punto hemos tomado como referencia la notación explicada por Michael L. Pinedo (2008). Al igual

que él, en todos nuestros problemas el número de trabajos y de máquinas será finito, denotando el número de

trabajos con la letra n, el número de máquinas con la letra m y el número de etapas con la letra c. Usaremos el

subíndice j para los trabajos, el subindice i para las máquinas. Por tanto, al usar el par (i, j) nos referimos a un

proceso u operación del trabajo j en la máquina i. Cada trabajo podrá tener varios datos asociados como son:

-Tiempo de proceso (𝑝𝑖𝑗). Esto representará el tiempo que necesitará el trabajo j en la máquina i para terminar

de ser procesado. El subíndice i puede ser omitido si el tiempo de proceso del trabajo j no depende de la

maquina en que sea procesado o solo puede ser procesado en una máquina.

-Fecha de llegada (𝑟𝑗). Es el instante en que el trabajo j llega al sistema y puede empezar a procesarse.

-Fecha de entrega (𝑑𝑗) . Es la fecha máxima que tenemos para tener finalizado el trabajo, se puede acabar de

procesar el trabajo más tarde de esta fecha, pero se incurrirá en una penalización.

22

-Peso (𝑤𝑗). Es un factor para priorizar unos trabajos ante otros, es decir, es un factor que nos indica que

trabajos tenemos mas prioridad por finalizar primero, ya sea porque cueste mucho mantenerlos en el taller o

por otras causas.

En cuanto a las variables, necesarias especialmente a la hora de calcular los objetivos son:

Tiempo de finalización: el tiempo de finalización del trabajo j en la máquina i lo denotaremos como

𝐶𝑖𝑗 . Y al tiempo que j está en el sistema, es decir el tiempo en que el trabajo termina de ser procesado

en la última máquina se le llamará 𝐶𝑗

Retraso del trabajo o lateness (𝐿𝑗 = 𝐶𝑗 − 𝑑𝑗): es la diferencia entre la fecha en que hemos terminado

el trabajo y la fecha de entrega de dicho trabajo. Será positivo cuando el trabajo se acaba después de

su fecha límite y negativo cuando se termina antes de tiempo.

Tardanza del trabajo j o tardiness (𝑇𝑗 = max(𝐿𝑗 , 0): la tardanza indica si un trabajo se ha acabado con

retraso o no, siendo la tardanza 1 si se retrasó el trabajo y 0 si no.

Adelanto del trabajo o earliness (𝐸𝑗 = max(0, −𝐿𝑗): sería el contrario de la tardanza. Siendo 1 si se

acaba el trabajo con adelanto y 0 si se retrasa el trabajo.

Tiempo de flujo del trabajo j o flowtime (𝐹𝑗 = 𝐶𝑗 − 𝑟𝑗): tiempo que el trabajo esta en el entorno.

2.1.1 Clasificación de los problemas de los problemas de programación

Una de las clasificaciones más usadas es la descrita por Pinedo (2008), propuesta por Graham (1979).

Clasifica los problemas según tres parámetros: α | β | γ. El primer parámetro α indica el entorno de la máquina

y contiene solo una entrada. El segundo parámetro β contiene detalles de las características de proceso, este

campo puede constar de ninguna, una o varias entradas. El tercer parámetro γ describe el objetivo que debe ser

minimizado, normalmente tendrá una sola entrada.

Como ya hemos dicho antes el parámetro α contiene la información del entorno del problema. Nos indica la

estructura del taller en el que estamos trabajando, es decir, la distribución de las máquinas en el taller. Hay

varios tipos de entornos como son:

23

Single Machine (1). Una única máquina que procesa todos los trabajos. Es el caso más simple de

todos los posibles entornos y es un caso especial de otros más complicados.

Máquinas idénticas en paralelo (𝑃𝑚). Hay m máquinas idénticas en paralelo, los trabajos necesitan

solo una operación y pueden ser procesados en cualquiera de las máquinas. En todas las máquinas el

trabajo tardará lo mismo en ser procesado.

Máquinas en paralelo con distintas velocidades (𝑄𝑚). Hay m máquinas en paralelo con diferentes

velocidades. La velocidad de cada máquina se denota como 𝑣𝑖, y el tiempo que pasará un trabajo en

una máquina para ser procesado (𝑝𝑖𝑗) será igual a 𝑝𝑖/𝑣𝑖.

Máquinas en paralelo no relacionadas (𝑅𝑚). Es un caso generalizado a partir del anterior. En este caso

todas las máquinas son diferentes y el tiempo de proceso de cada trabajo depende de la máquina en

que sea procesado sin ninguna relación entre ellas. El tiempo de procesado de cada trabajo se denotará

como 𝑝𝑖𝑗.

Flow shop (𝐹𝑚). En este tipo de taller hay m máquinas en serie y cada trabajo tiene que ser procesado

en cada una de las m máquinas, y todos ellos tienen la misma ruta, es decir, primero deben ser

procesados en la máquina 1, cuando termine de ser procesado pasará a la máquina 2 y así

sucesivamente. En el campo β nos podemos encontrar la restricción de Prmu, lo que indica que en

cada máquina el orden de los trabajos ha de ser el mismo.

Job shop (𝐽𝑚). Es un caso muy parecido al anterior, la diferencia es que en este caso cada trabajo tiene

su propia ruta, no todos siguen la misma y cada trabajo puede ser procesado en alguna máquina más

de una vez.

Openshop (𝑂𝑚). Es el caso más complejo de todos. Hay m máquinas en paralelo y cada trabajo tiene

que ser procesado por todas las máquinas. En algunos casos el tiempo de proceso en alguna máquina

puede ser cero. Los trabajos no tienen una ruta determinada, al resolver el problema habrá que

determinar la ruta de cada trabajo j, pudiendo tener cada trabajo una ruta distinta.

El parámetro β, contiene las características del proceso, es decir, tiene las restricciones que tenemos que tener

en cuenta a la hora de resolver nuestro modelo. Alguno de los tipos de restricciones que nos podemos

encontrar son:

Fechas de llegada y de entrega (𝑟𝑗, 𝑑𝑗): como ya hemos explicado antes son fechas de llegada y de

entrega de los trabajos. Si aparecen en el campo β habrá que tenerlas en cuenta a la hora de resolver el

problema.

24

Interrupciones (Prmp): indica que están permitidas las interrupciones, es decir, no es necesario

mantener un trabajo en una máquina una vez iniciado hasta su finalización, sino que, podemos

interrumpir el procesado en cualquier momento. Hay tres tipos de interrupciones:

Non-resumable: se pierde el trabajo hecho de la tarea interrumpida, y se empieza

otra vez cuando se reinicia.

Semi-resumable: se pierde parte del trabajo realizado, es decir, se reinicia

parcialmente (una proporción del trabajo ya realizado)

Resumable: se reinicia por donde se había dejado tras la interrupción

Precedencia en los trabajos (Prec): indica que hay relaciones de preferencia entre operaciones de

diferentes trabajos. Puede aparecer en entornos de single machine o de máquinas en paralelo, indica

que uno o más trabajos tienen que ser finalizados antes de poder comenzar a procesar otro. Hay varios

tipos de relaciones de precedencia:

Chains (en serie): si cada trabajo tiene como máximo un predecesor y un sucesor.

Intree: cada trabajo tiene como máximo un sucesor.

Outtree: cada trabajo tiene como máximo un predecesor.

Tree: los trabajos no tienen un límite de predecesores o sucesores. Siguen un

esquema de árbol que será dado antes de resolver el problema.

Tiempos de setup (Setup): indica que existen tiempos de setup que hay que esperar entre operaciones.

Se denota como 𝑠𝑗𝑘 y representa el tiempo de setup necesario para procesar el trabajo k después del

trabajo j; 𝑠0𝑘 será el tiempo de Setup del trabajo k si éste es el primer trabajo en ser procesado, y 𝑠𝑘0

será el tiempo de clean-up, es decir, el tiempo de setup posterior si k es el último trabajo de la

secuencia. Si en el campo β no aparece setup consideraremos todos los tiempos cero.

Bloqueo (Block): Si un trabajo acaba de ser procesado y el buffer de la siguiente máquina está lleno el

trabajo deberá esperar en la máquina en la que ha sido procesado hasta que haya suficiente etapa en el

buffer para él. Los buffers de las maquinas pueden ser iguales todos o dependientes de cada máquina.

Máquina no ociosa (nwt): Indica que los trabajos no tienen permitido esperar entre dos máquinas

sucesivas, no podremos empezar a procesar un trabajo hasta estar seguros que puede recorrer todo el

flowshop sin tener que esperar en ninguna máquina.

Recirculación (rcrc): indica que algunos trabajos deberán ser procesados más de una vez en la misma

máquina o centro de trabajo.

25

Missing: La gran mayoría de las investigaciones de programación de la producción para los

problemas de los talleres híbridos flexibles, suponen que cada trabajo tiene que ser procesado en todas

las etapas, es decir, no consideran la restricción de missing. Sin embargo, en la vida real hay muchos

entornos de producción en los que existe missing. Esto consiste en trabajos que pueden saltarse una o

varias etapas de la cadena de producción.

Figura 2-1: Ilustración del missing. Elaboración propia

Y, por último, el parámetro γ. Todo problema de programación de la producción buscará dar una solución al

problema, minimizando uno o varios objetivos. Algunas de las funciones objetivos más usadas son:

- Makespan (𝐶𝑚𝑎𝑥): el makespan es definido como el máximo tiempo de finalización de los trabajos de

un entorno, es decir, el tiempo en que el último trabajo abandona el sistema. Cuando menor sea el

makespan mejor utilización se les habrán dado a las máquinas.

- Máximo retraso (𝐿𝑚𝑎𝑥): Es definido como el máximo de los retrasos,max( 𝐿1,…, 𝐿𝑛). Mide la peor

violación de las fechas de entregas.

- Tiempo de finalización total ponderado (∑𝑤𝑗𝐶𝑗 ): es la suma ponderada de todos los tiempos de

finalización.

- Número de trabajos tardíos (∑𝑈𝑗): indica cuantos trabajos hemos entregado con algún retraso

respecto a su fecha de entrega.

26

3 METAHEURÍSTICAS: LOS ALGORITMOS

GENÉTICOS

os métodos heurísticos proporcionan soluciones en las que se tiene cierta confianza que son factibles y

cercanas a la optimalidad. Pueden ser muy generales o específicas, teniendo las más generales ventajas

como: la sencillez, la adaptabilidad, la robustez, etc…

A partir de la década de los 70 han aparecido métodos de solución de problemas llamados técnicas

metaheurísticas. Dichas técnicas son definidas por Osman y Kelly (1996) como: “métodos aproximados

diseñados para resolver problemas de optimización combinatoria, en los que los heurísticos clásicos no son

efectivos. Los metaheurísticos proporcionan un marco general para crear nuevos algoritmos híbridos,

combinando diferentes conceptos derivados de la inteligencia artificial, la evolución biológica y los

mecanismos estadísticos.” Las técnicas metaheurísticas son útiles para aquellos problemas en que las técnicas

exactas no resultan eficientes o no se pueden aplicar. Las metaheurísticas a diferencia de las heurísticas poseen

mecanismos para escapar de las soluciones óptimas locales y continuar en la búsqueda del óptimo global,

aunque ninguna metaheurística puede garantizar el óptimo global. Es decir, las metaheurísticas encuentran

soluciones muy superiores a las heurísticas con esfuerzos computacionales mayores pero aceptables desde el

punto de vista práctico.

3.1 Tipos de metaheurísticas

Las metaheurísticas se pueden clasificar de diversas formas. Una de las posibles clasificaciones, dado que las

metaheurísticas son usadas para plantear otros procedimientos heurísticos, es clasificarlas dependiendo de la

clase de procedimiento a los que se refieran:

a) Metaheurísticas para los procesos de relajación: Las metaheurísticas de relajación hacen referencia a

aquellos métodos que usan relajaciones del original, es decir, modifica el modelo original para que

éste sea más sencillo de resolver.

L

27

b) Metaheurísticas para los procesos constructivos: Las metaheurísticas constructivas, son aquellas en las

que los procedimientos tratan de obtener nuevas soluciones a partir del análisis y selección paulatina

de los componentes que forman dichas soluciones.

c) Metaheurísticas para las búsquedas de entorno: Las metaheurísticas de búsqueda son las más

importantes, establecen estrategias para recorrer el espacio de soluciones del problema transformando

iterativamente las soluciones de partida.

d) Metaheurísticas para los procedimientos evolutivos: Las metaheurísticas evolutivas están enfocadas

en procedimientos que comienzan en un conjunto de soluciones que van evolucionando sobre el

espacio de soluciones. Su aspecto fundamental consiste en la iteración entre los miembros, a

diferencia de otro métodos de búsqueda, que toman como patrón la información de cada solución por

separado.

e) Otros tipos: Otras metaheurísticas surgen combinando varias de distintos tipos, como las GRASP

(Greedy Randomized Adaptative Search Procedure) que une una fase constructiva con otra de

búsqueda de mejora.

3.2 Características de las metaheurísticas

Todas las técnicas metaheurísticas tienen una serie de características comunes:

- Son técnicas que no se detendrán cuando lleguen a la solución óptima ya que no saben diferenciar la

óptima de una óptima local. Debido a eso deberemos determinar los criterios de parada para indicar

cuando debe finalizar el algoritmo.

- Son algoritmos aproximativos, y por tanto no garantizan que se llegue a la solución óptima.

- A veces realizan malos movimientos, es decir, en estas técnicas no toda nueva solución es mejor que

la anterior en términos de la función objetivo. A veces incluso crean soluciones no factibles pero que

sirven como etapa intermedia para llegar a nuevas regiones que no han sido analizadas.

- Son por lo general sencillas, lo único necesario para comenzar es una muestra del campo en el que

buscaremos las soluciones, un punto en el que comenzar, es decir, una o varias soluciones iniciales, y

un procedimiento determinado que nos permita ir explorando todo el espacio de soluciones.

- Son muy genéricas, permitiendo así su aplicación a cualquier problema de optimización combinatorio.

28

Por ello es importante escoger una técnica que se adecue bien al problema considerado y que tengan

relación con este, para que sean lo más eficientes posibles.

- Las reglas de selección dependen del instante del proceso y de la historia de la técnica hasta dicho

instante. Así, en dos iteraciones determinadas en las que se obtiene la misma solución, la nueva

solución de la siguiente iteración no tiene por qué ser la misma en ambos casos.

3.3 Los algoritmos genéticos

Los algoritmos genéticos son técnicas de búsqueda basada en el comportamiento de los seres vivos, que junto

con otras técnicas conforman los llamados algoritmos evolutivos.

Fueron desarrollados por John Holland y Rechemberg, (1975), en la década de los 60, los cuales a partir del

comportamiento de la naturaleza crearon estos algoritmos de optimización. Su estructura se diseña a partir de

comportamientos de la propia naturaleza con la esperanza de que así se consigan resultados similares a la

capacidad de adaptación a un amplio número de ámbitos diferentes. Los algoritmos genéticos son muy

flexibles, es decir se pueden adaptar a multitud de diferentes casos tanto en ingeniería como en otros campos

como la química, la medicina o en el ámbito empresarial.

Nacen a partir de la biología y en concreto con Charles Darwin y su publicación El origen de las especies

(1859), en el que habla de los principios de la selección natural. A partir de las leyes de la naturaleza descritas

por Darwin podemos definir los fundamentos esenciales de los algoritmos genéticos.

En la naturaleza, son los cromosomas son los que contienen la información, es decir los genes. Los organismos

se agrupan en poblaciones, y los que estén mejor preparados para adaptarse son los que sobrevivirán y se

reproducirán. Algunos de estos supervivientes serán cruzados y se generara una nueva generación de

individuos. Los genes también pueden sufrir pequeñas modificaciones, denominadas mutaciones.

Los individuos, que son las posibles soluciones del problema, están formados por un grupo de parámetros a los

que llamaremos genes, dichos genes se pueden agrupar en forma de una secuencia de valores.

29

Figura 3-1: Ilustración cromosoma y gen. Elaboración propia.

3.3.1 Parámetros de los algoritmos genéticos

A continuación, pasaremos a describir los parámetros principales de los algoritmos genéticos:

3.3.1.1 Población

-Tamaño de la población

Una de las cuestiones que tendremos que valorar es el tamaño adecuado de la población. Parece lógico pensar

que cuánto más pequeña sea la población menor será la garantía de recorrer de forma adecuada el espacio de

búsqueda y dejar fuera de él posibles soluciones, mientras que si la población es demasiado grande tendremos

problemas relacionados con el costo computacional de resolver el problema, el cual será muy elevado.

Goldberg (1989), realizó un estudio teórico obteniendo como conclusión que el tamaño óptimo de la población

para secuencias de longitud l, con codificación binaria, crece exponencialmente según el tamaño de dicha

secuencia. Alander (1992), basándose en pruebas empíricas con los algoritmos genéticos sugirió que las

poblaciones con unas dimensiones entre l y 2l eran suficientes para resolver adecuadamente los problemas que

él había abordado.

30

-Población inicial

La población inicial será aquella de la que se parta en cada iteración y a la que se le irán aplicando

modificaciones hasta alcanzar nuestra solución final. Habitualmente, se generará la población inicial de forma

aleatoria, pudiendo contener cada gen uno de los posibles valores, teniendo todos una probabilidad uniforme.

Hay algunos estudios, aunque son pocos, en los que se preguntan si obteniendo la población inicial mediante

algún tipo de técnica se obtendrían mejores resultados. En ellos se llega a la conclusión que generando la

población inicial de forma no aleatoria se puede conseguir que converja antes, aunque eso puede llegar a ser

un problema ya que al converger demasiado pronto se podría no haber recorrido el espacio de soluciones

completamente, y caer en óptimos locales.

3.3.1.2 Probabilidad de cruce

Nos indicara la asiduidad con la que se producirán cruces en los padres, es decir, que se reproduzcan y se

formen nuevos individuos. En el caso que no halla cruce ya que la probabilidad así lo indique, hay dos

posibilidades dependiendo de cada autor, algunos si no hay reproducción no crean nuevos individuos y otros

deciden que los hijos sean copias exactas de los padres, aunque podría parecer redundante tener dos individuos

iguales al aplicarles la mutación tendremos dos nuevos individuos diferentes aumentando así el espacio de

búsqueda.

3.3.1.3 Probabilidad de mutación

Nos indica que porcentaje de individuos de nuestra población mutaremos. Si la probabilidad es de cero todos

los individuos tras la mutación serán los mismos.

3.3.2 Operaciones de los algoritmos genéticos

Tras determinar los parámetros de nuestro algoritmo genético, pasaremos a aplicar una serie de operadores a

nuestros individuos. Aunque los algoritmos genéricos son independientes del problema al que se están

aplicando, el proceso de resolución del problema ira contenido en él, eso hace a los algoritmos una

herramienta muy interesante ya que resultan de gran utilidad en multitud de entornos, aunque no esté

especializado en ninguno. Las soluciones compiten para ver cuál es la mejor, y las mejores irán guiando al

resto de soluciones de forma que vayan mejorando en una dirección concreta y al final solo las más adecuadas

sobrevivan.

31

Por tanto, la clave de un algoritmo genético estará en determinar de forma adecuada los parámetros del

problema, la manera de codificarlos y la forma en que aplicaremos los operadores.

Los individuos, que son las posibles soluciones, estarán formados por una serie de parámetros llamados genes,

estos estarán agrupados en forma de secuencias, a las que llamaremos cromosomas.

3.3.2.1 Codificación de las variables

Debemos hacer que los cromosomas contengan información acerca de la solución que representan. Para ello

hay varias formas de llevarla a cabo: la más extendida es creando una secuencia binaria, aunque también

podría realizarse con números enteros o caracteres, elegiremos una u otra opción dependiendo cual se adecue

más a nuestro tipo de problema.

A) Codificación binaria

Es la que fue usada en los inicios de los algoritmos, por ello es la más frecuente. Cada cadena de

cromosomas es una serie de unos y ceros. Tiene como ventaja que podemos incluir multitud de cromosomas

con solo unos pocos genes. Aunque para muchos problemas no es una buena codificación y en algunos casos

será necesario aplicar correcciones tras usar los operadores.

Este tipo es utilizado para problemas como el de la mochila. En el cual consideramos una mochila con un

volumen determinado y una lista de objetos, los cuales tendrán un peso y un beneficio asignado. El volumen

de la mochila será menor al total de los pesos de los objetos. Se intentará determinar qué conjunto de objetos

nos reportará mayor beneficio mientras su suma de pesos no sobrepase el volumen permitido.

B) Codificación numérica

En este caso utilizaremos series de números que indica la cardinalidad dentro de en una secuencia. Es utilizada

generalmente cuando necesitamos ordenar una serie de elementos. Aunque, al igual que en la binaria a veces

será necesario realizar correcciones tras el cruce o la mutación.

Un ejemplo en el que es muy útil aplicarla es en el problema del viajero. En él tenemos un conjunto de

ciudades que el viajero deberá visitar y las distancias existentes entre cada una.Se busca determinar la ruta que

deberá recorrer el comerciante para que iniciando la ruta en una ciudad pase por el resto de ellas, recorriendo el

32

mínimo número de kilómetros

Figura 3-2: Ilustración ruta mínima [www.ingenieriaindustrialonline.com]

C) Codificación por valor directo

Esta codificación la utilizaremos en casos de resolución de problemas en el que se requiera el uso de

valores de cifrado complicados como sería el uso de números reales, ya que codificar números reales en

binario sería muy complejo. Cada cromosoma representa una serie de valores, los cuales pueden ser

números, ya sean enteros o binarios, o caracteres. Es muy útil para casos específicos, aunque para

utilizarla normalmente será imprescindible determinar una serie de métodos de reproducción y mutación

específicos para el problema, lo cual aumentara la complejidad del algoritmo genético bastante.

Por ejemplo, una aplicación de esta codificación será en la resolución de problemas para la búsqueda de

pesos para las redes neuronales. En ellos trataremos de encontrar el peso de las neuronas para ciertas

entradas y así entrenar a la red para obtener la salida deseada. El valor del peso de las entradas vendrá

representado en el propio cromosoma.

D) Codificación en árbol

Este último tipo, se utiliza principalmente en el desarrollo de programas o expresiones para programación

genética. En este caso, cada cromosoma será un árbol con ciertos objetos.

En este método, los cambios aleatorios se podrían generar cambiando el operador, variando los valores de

33

los nodos de los árboles o sencillamente cambiando un árbol por otro.

3.3.2.2 Selección

En los algoritmos genéticos, necesitaremos seleccionar los individuos mejor preparados, es decir, los que

mejor solución aporten a nuestro problema, para que estos sean los que más se reproduzcan, al igual que en la

naturaleza, en la cual los más capacitados son los que sobreviven y crean unos descendientes más capaces.

Por tanto, una vez evaluados todos los individuos y obtenido el resultado que nos proporciona a nuestro

problema, crearemos una nueva población intentando que los buenos rasgos de los mejores pasen a dicha

población.

A continuación, nombramos algunas de las formas de cómo podremos realizar dicha selección, aunque hay

multitud de posibilidades, pueden ser:

1) Selección por rueda de ruleta: En este caso, crearemos una ruleta con los cromosomas de la

generación, y cada uno de ellos contendrá una porción de la ruleta relativa a su valor para la función

objetivo. Tras crear la ruleta, seleccionaremos aleatoriamente un cromosoma de ella. Los cromosomas

con mayor puntuación saldrán con mayor probabilidad, lo que puede dar problemas ya que, si uno

tiene el 85% de oportunidad de salir, los otros casi nunca serán escogidos y reduciremos la diversidad

de la muestra.

2) Selección por rango: En este método, haremos un ranking de los cromosomas dependiendo de su

aptitud, y a cada posición en el ranking le asignaremos un % de ruleta, dándole a los de mayor ranking

más proporción de la ruleta. Así conseguiremos solucionar el problema de que un solo cromosoma

tenga la mayoría de la ruleta y tendremos mucha más diversidad, aunque el principal incinveniente de

este caso es que se tarda mas en llegar a converger.

3) Selección elitista: En algunas circunstancias, tras aplicar los operadores podemos perder el

cromosoma mas adaptado. Aplicando esta selección conseguiremos evitar eso, ya que copiaremos

dicho cromosoma u otro de entre los mejores directamente a la nueva generación. El resto se realizará

de alguna de las formas vistas anteriormente. Una variación, es que copiemos el mejor cromosoma en

la nueva generación, solo si tras el cruce y la mutación no hayamos creado un cromosoma mejor.

34

4) Selección por torneo: Es uno de los procesos de selección de padres mas usados, consiste en tomar un

grupo de elementos al azar de la población, seleccionar al mejor de dicho grupo e ir repitiendo el

proceso, hasta que el número de individuos seleccionados coincida con el tamaño de la población.

5) Selección jerárquica: En esta los elementos irán atravesando varias fases de selección en cada

iteración. Las primeras rondas, evaluaran de forma rápida y no tan rigurosamente, pero conforme

avance y se llegue a fases mas avanzadas se volverá mas electiva, reduciendo así los tiempos

computacionales ya que en las primeras rondas eliminamos de manera rápida a la mayoría de los

individuos que se muestren poco capaces, y solo evaluaremos de forma más estricta, que requiere más

costos computacionales, a las soluciones más prometedoras.

3.3.2.3 Cruce o crossover

Se denomina cruce a la forma de crear un nuevo individuo a partir de dos padres. Los cruces podrán realizarse

de dos formas distintas: una tomando una estrategia destructiva, es decir, los descendientes sustituirán a los

padres en la población nueva, o por el contrario se puede tomar una no destructiva en la que los nuevos

individuos se trasladaran a la nueva generación si están mejor adaptados al problema que los individuos que

debe sustituir.

La idea en la que se basan los cruces es que, tomando dos individuos correctamente adaptados al problema, si

obtenemos un individuo que sea hijo de los dos, existe la posibilidad de que herede los genes causantes de la

buena adaptación de los padres. Al compartir los genes de los padres la descendencia, o por lo menos parte de

ella, debería adaptarse mejor que los padres, ya que tendrá los genes buenos de ambos. Aunque obtengamos

hijos peor adaptados, eso no evidencia que estemos retrocediendo en nuestra resolución ya que los genes de los

padres seguirán en ellos, aunque de forma más dispersa, y en posteriores cruces podrán volver a ser útiles y

obtener una futura descendencia mejor.

La elección del tipo de cruce, determinará en gran medida como va a evolucionar nuestra población.Hay

diversos tipos, algunos de los más importantes son:

1) Cruce básico o de un punto

Tomaremos el par de individuos que harán de padres, en uno de ellos seleccionaremos una posición, para

35

después permutar las secciones que estén a la derecha de dicha posición. Por tanto, los genes del padre 1 a la

izquierda del punto de corte forman parte del hijo 1 y los situados a la derecha formaran parte del hijo 2,

mientras que con el padre 2 ocurrirá lo opuesto.

Figura 3-3: Cruce de un punto. Elaboración propia.

2) Cruce multipunto

Se realizarán igual que el anterior, pero tomaremos varios puntos a la hora de cruzar. Es el usado en nuestro

algoritmo propuesto, pero con una pequeña modificación, ya que al ser los genes secuencias de trabajos, no

podrá haber dos genes con el mismo valor. Por tanto, tomaremos dos puntos de cruce, y los genes entre dichos

puntos en el padre 1 pasaran al hijo 1, e igual con el padre 2 y el hijo 2. Tras esto, rellenaremos los genes del

hijo 1, con los genes en el mismo orden en que estén colocados en el padre 2, pero saltándonos los genes

repetidos.

36

Figura 3-4: Cruce de dos puntos. Elaboración propia.

3) Cruce uniforme

En este caso, cada gen del hijo tiene una probabilidad de que pertenezca a un padre o al otro.

4) Cruce PMX o de mapeamiento parcial

Tomamos una sección del padre 1 y lo colocamos en el hijo, en igual orden y posición, después rellenamos

con la madre, de forma que se parezca lo máximo posible a esta.

3.3.2.4 Mutación

La mutación modifica aleatoriamente parte de un individuo para crear uno parecido, pero no igual, variando

uno o varios genes de manera aleatoria. La mutación nos permitirá, si estamos atrapados en un mínimo, salir

de éste dando un salto a un nuevo subespacio de soluciones y así ampliar la zona de búsqueda. El

inconveniente es que si tenemos una tasa de mutación muy alta podemos tener una deriva genética, es decir, se

homogeneizará mucho la población alrededor de un mínimo y acabaremos con muchas soluciones idénticas en

un mínimo, que puede que sea no muy bueno. Para solucionar esto, una buena estrategia sería aplicar un alto

índice de mutación al principio para diversificar mucho el espacio de búsqueda e ir reduciendo dicha tasa a

37

medida que vamos avanzando en el algoritmo.

Aunque podremos escoger elementos de la población que se esté usando y mutarlos para introducirlos

posteriormente en una nueva población, lo más común es usar la mutación conjuntamente con algún tipo de

cruce. Si se determina que hay un cruce, pasaremos a mutar uno o varios de los descendientes dependiendo de

la probabilidad de cruce. Al igual que en el comportamiento de la propia naturaleza, ya que al crearse cierta

transcendencia se obtienen leves diferencias en el paso de la carga genética de padres a hijos.

Algunos tipos de mutaciones son:

a. Mutación bit a bit: Hay una posibilidad de que se dé una mutación en algún bit, si

efectivamente se produce tomaremos dicho bit e invertiremos su valor.

b. Mutación multibit: en este caso cada bit tiene una probabilidad de mutar, pudiendo mutar

varios bits a la vez.

c. Mutación de gen: de la misma manera que en la bit a bit cada elemento tendrá una

probabilidad de mutar, pero a diferencia de esa se mutaran genes enteros.

d. Mutación multigen: de la misma forma que en la bit a bit, pero cambiaremos conjuntos de

genes en vez de un conjunto de bits.

e. Mutación de intercambio: habrá una cierta posibilidad de que haya mutación, de haberla, en

dicha mutación tomaremos dos bits o genes al azar, dependiendo del caso, y los

intercambiaremos.

f. Mutación de barajado: teniendo una probabilidad de mutación, si se realiza mutación

tomaremos un par de elementos, y serán mezclados aleatoriamente los elementos que se

encuentren entre ellos

38

3.3.2.5 Reducción

Una vez obtenidos, los individuos descendientes tras los cruces y/o mutaciones de una población, en un

periodo de tiempo determinado, seleccionaremos los λ individuos que formarán parte de la nueva población de

entre todos los resultantes. Los dos métodos usados generalmente para realizar la reducción son:

a) Reducción simple: Escogeremos los λ elementos que conformen parte de la población en un

instante t+1 determinado.

b) Reducción elitista: Una vez obtenidos todos los descendientes, elegir de entre ellos los λ

individuos más adaptados al problema.

39

4 DESCRIPCIÓN DEL PROBLEMA

l flow shop es considerada como un caso particular del job shop, en el que como hemos dicho antes, se

tratará de secuenciar una cantidad de n trabajos, todos con la misma ruta, en una serie de m máquinas. Se

trata de un problema NP-hard para más de dos máquinas. Para un número no muy grande de trabajos, el

número de secuencias posibles es muy elevado y evaluarlas todas no sería posible.

Un caso especial del flowshop sería el flowshop hibrido flexible, que posee un grupo de n trabajos con la

diferencia que hay c etapas y en cada una de ellas hay 𝑚𝑖 máquinas en paralelo. Al menos una de las etapas

tiene 𝑚𝑖 máquinas mayor que uno, y se busca optimizar el proceso para cierta función objetivo. La solución

del problema es la secuencia de trabajos a la entrada de cada máquina para minimizar la función objetivo.

Figura 4-1: Esquema del Floswshop Hibrido Flexible [Fernández-Viagas,2015].

En general, el flujo de productos tendrá una única dirección y cada trabajo tendrá que pasar por todas las

etapas antes de terminar de ser procesado. Todos los trabajos tendrán la misma ruta, es decir, deberán pasar

primero por la etapa 1, después por la etapa 2, hasta la etapa m. Como proponen Zandieh y Karimi (2013), el

concepto de flexibilidad de un flowshop indica que no todos los trabajos tendrán porque ser procesados en

todas las etapas, es decir, que algunos trabajos podrán saltarse alguna etapa. Esto no influye en lo que hemos

E

40

indicado anteriormente sobre las rutas, todos los trabajos seguirán teniendo la misma ruta, aunque algunos se

salten determinadas etapas.

Como hemos dicho en el apartado 2, el campo β nos indica las restricciones del taller en estudio, para nuestro

problema solo consideraremos la restricción de missing.

Adicionalmente este tipo de entornos conllevan las siguientes restricciones comunes:

- Todos los trabajos están disponibles al principio del horizonte de programación, no tienen fecha de

llegada.

- Todas las máquinas de una etapa son idénticas.

- Cada máquina solo puede procesar un trabajo en cada instante de tiempo, es decir, cada máquina tiene

que procesar los trabajos de uno en uno. Y cada trabajo solo puede ser procesado en una maquina a la

vez y solo en una maquina en cada etapa.

- Cada trabajo está compuesto por varias operaciones que deben ser ejecutadas en un orden predefinido

- Tampoco se puede interrumpir trabajos, una vez que se inicie un trabajo no se puede parar la maquina

hasta que haya finalizado con el trabajo en curso.

- Los tiempos de proceso son conocidos e independientes de la secuencia

- Las maquinas siempre que no estén procesando un trabajo están libres, no habrá tiempos de set-up, ni

necesitan ningún mantenimiento.

- El buffer entre máquinas es infinito, esto es el número de trabajos que acaban de salir de una máquina

y están esperando a ser procesados en otra.

- El tiempo de transporte entre máquina y máquina lo suponemos despreciable o igual entre todas las

máquinas, por tanto, no tendremos que tenerlo en cuenta a la hora de resolver el problema.

4.1 El objetivo del makespan

Hay multitud de objetivos que se pueden optimizar en el estudio de los flow shop híbridos, como pueden ser:

la reducción del WIP, maximizar el número de trabajos entregados a tiempo reducir la suma de penalizaciones

por entregas tardías. Pero uno de los más usados en la literatura, es la búsqueda de la utilización eficiente de

los recursos, medida mediante el makespan.

41

Se puede definir el makespan según Hojjati y Sahraeyan (2009) como, el tiempo que transcurre entre el inicio

del primer trabajo en la primera máquina y la terminación del último trabajo en la última máquina. También se

conoce como 𝐶𝑚𝑎𝑥 ya que por definición el makespan es igual al máximo tiempo de terminación de los

trabajos. Hekmatfar et al. (2011) consideran que minimizar el makespan, estaríamos maximizando la

utilización de las máquinas, ya que se reducen los tiempos en que las máquinas están ociosas.

42

5 ALGORITMO GENÉTICO PROPUESTO

n esta sección describiremos el algoritmo genético destinado a resolver nuestro problema de Hybrid

Flowshop con Missing Operation, explicando su funcionamiento y sus elementos, que clasificaremos

en individuos, población inicial, operadores de creación de nuevos individuos, poblaciones

intermedias, criterios de parada y la solución con su criterio de selección final.

5.1 Elementos del algoritmo genético

5.1.1 Individuos

Llamaremos individuos, a los elementos básicos del algoritmo genético. Los individuos tienen tantos

elementos como trabajos tenga nuestro problema, e indican, al mismo tiempo, el orden en el que irán entrando

en el taller. Es necesario remarcar que, dentro de cada individuo, no podrá estar repetido ninguno de los

trabajos antes mencionados, ni tampoco podrá faltar ninguno de ellos.

Figura 5-1: Ejemplo individuo. Elaboración propia.

E

Población inicial

Cuce de dos puntos

Mutación por intercambio

Mejora Local

43

Cada individuo tiene asignado un makespan, que indica el tiempo que tarda dicha cadena de trabajos en

procesarse en el taller, usando como secuencia inicial dicho individuo

Podemos distinguir tres tipos de individuos:

a) Individuos iniciales:

Son los individuos con los que se pone en marcha el algoritmo; son obtenidos de forma aleatoria a partir de un

número de trabajos, estando todos presentes y sin repetición de ninguno de ellos.

b) Individuos nuevos:

Son los individuos obtenidos a partir de los padres, antes citados, mediante crossover y mutación.

c) Individuos de salida o solución

Son aquellos individuos resultantes tras aplicar los procesos de crossover, mutación y reducción, es decir,

aquellos con menor makespan entre los nuevos individuos y los iniciales.

5.1.2 Población inicial

El número de individuos iniciales, que integrarán la población inicial, es un parámetro de nuestro algoritmo

que podemos modificar, siempre teniendo en cuenta que el tamaño de esta debe ser par. En nuestro caso,

hemos decidido que dicho tamaño sea de 10 individuos iniciales.

5.2 Cruce de dos puntos

Usaremos un cruce de dos puntos, para el cual partiremos de la población inicial, en nuestro caso formada por

los 10 individuos generados anteriormente, e iremos seleccionándolos por parejas de forma aleatoria. Cada

pareja tiene una probabilidad de cruce del 80%, así que, para cada pareja primero comprobaremos si se cruza o

no, si no se cruzan la pareja de padres no tendrá descendiente, si por el contrario si se cruzan daremos

44

comienzo al cruce, primero tomando como padre 1 un individuo y después repitiendo el proceso tomando

como padre 2 el otro individuo, así obtendremos dos hijos por cada pareja.

Los pasos del cruce de dos puntos son los siguientes:

1º- Seleccionamos la pareja de individuos a la cual queremos aplicar el cruce, y decidimos que individuo va a

ser el padre 1 y cual el padre 2.

Figura 5-2: Ejemplo padres para cruce. Elaboración propia.

Una vez decidido que individuo será cada padre, tomamos el padre 1 y dividimos dicho padre por don puntos.

Tomaremos los trabajos que se encuentren entre dichos puntos y con ellos generaremos el hijo 1, colocando en

el hijo 1 dichos trabajos en el mismo orden y en las mismas posiciones que en el padre 1.

Figura 5-3: Padre e Hijo en cruce. Elaboración propia.

45

A continuación, tomaremos el padre 2, e iremos tomando los trabajos de uno en uno en el orden en que están

colocados en el padre 2 y los colocaremos en las posiciones libres del hijo 1. Teniendo en cuenta que no

podemos repetir ningún trabajo. De esta manera ya tendremos formado el hijo 1.

Figura 5-4: Hijo realizado por cruce. Elaboración propia.

5.3 Mutación de intercambio

El otro método que usaremos para obtener nuevos individuos a partir de los que tenemos, es la mutación.

Iremos tomando uno a uno los individuos de la población actual, formada por los padres y por los hijos

obtenidos a partir de estos tras el cruce, y para cada uno comprobaremos la probabilidad de mutación, si sale

positiva procederemos a mutar al individuo y si no el individuo no mutará.

Dicha mutación consiste en tomar dos genes aleatoriamente del individuo, en nuestro caso dichos genes serán

dos posiciones, e intercambiar los trabajos de dichas posiciones. Tras esto, obtendremos un nuevo individuo

por cada individuo al que le apliquemos la mutación.

46

Figura 5-5: Ejemplo mutación por intercambio. Elaboración propia.

5.4 Reducción

Para nuestro problema, hemos decidido usar una reducción elitista, que como hemos explicado antes, consiste

en tomar de la población intermedia los λ individuos más adaptados y tomarlos como población inicial para la

siguiente iteración.

Tomaremos los 10 individuos mejor preparados ya que es el tamaño de nuestra población inicial, y como

criterio de adaptación tomaremos el makespan ya que es nuestra función objetivo, tomando así los 10

individuos con menor makespan de la población intermedia.

5.5 Poblaciones intermedias

Partiendo de nuestra población inicial explicada anteriormente, formada por 10 individuos, comenzaremos la

primera iteración, tras aplicarle a dicha población el cruce de dos puntos y la mutación, nuestra población

constara de los individuos iniciales, más aquellos resultantes tras dichas operaciones.

Una vez obtenida dicha población, evaluaremos todos los individuos y veremos el makespan de cada

individuo para nuestro problema, y tomaremos los 10 individuos con mejor makespan y con ellos formaremos

47

una nueva población que usaremos en la siguiente iteración como población inicial.

En cada iteración repetiremos este proceso para obtener la población inicial de la siguiente iteración.

5.6 Criterios de parade

Tendremos 3 criterios de parada que se evaluaran tras cada iteración, si se cumple alguno de los 3 criterios tras

dicha iteración y con de la población final de dicha iteración obtendremos la solución final.

Los tres criterios de parada serán:

a) Número de iteraciones: pondremos un número máximo de iteraciones que queremos que se

realicen. Si no se cumple ninguno de los otros dos criterios y se ha llegado al número máximo de

iteraciones pararemos el algoritmo.

b) Tiempo de ejecución: al iniciar el programa se comenzará a contar el tiempo que está

ejecutándose el algoritmo y tras cada iteración comprobaremos el tiempo que lleva ejecutándose y

comprobando si hemos superado el tiempo de ejecución.

c) Número de iteraciones sin mejorar solución actual: tras cada iteración comprobaremos si en dicha

iteración hemos mejorado la mejor solución obtenida en la anterior iteración, si la hemos

mejorado pondremos el contador a cero, sino aumentaremos el contador en 1 y comprobaremos si

hemos superado el número de iteraciones sin mejorar permitido.

Dichos criterios serán tres variables que determinaremos antes de comenzar el algoritmo, tendremos que tener

en cuenta nuestros objetivos y recursos disponibles. Para algunos casos, nos convendrá obtener la solución

óptima y para otros igual nos vale con una solución buena pero no necesariamente la óptima. Como es lógico,

obtener la solución óptima, nos llevara más tiempo, por tanto, tendremos que buscar un punto de equilibrio

entre ambos.

48

Para nuestro problema hemos decidido poner un numero de iteraciones y de iteraciones de no mejora muy alto

para que el programa no pare por ninguno de estos dos criterios. Y hemos calculado el tiempo de parada a

partir del tamaño del problema, es decir, para problemas más grandes (con mayor número de trabajos y etapas)

tendremos un tiempo de parada más alto que si el problema es más simple.

𝑇𝑚𝑎𝑥 =𝑁𝑢𝑚. 𝑡𝑟𝑎𝑏𝑎𝑗𝑜𝑠 ∗ 𝑁𝑢𝑚. 𝑒𝑡𝑎𝑝𝑎𝑠

2 ∗ 10

5.7 Población final y elección de solución final

Como ya hemos dicho, tras cada iteración obtendremos una población final de diez individuos, que serán los

mejores obtenidos hasta el momento. En la última iteración, tomaremos la población final de dicha iteración y

en ella buscaremos la mejor, es decir, aquella con menor makespan de entre todas, y esta será la solución final

de nuestro problema.

49

Figura 5-6: Diagrama de flujo para modelo propuesto I: “Normal”. Elaboración propia.

50

5.8 Mejoras locales

Anteriormente hemos explicado el funcionamiento del programa general, a parte de ese hemos añadido cuatro

variantes más añadiéndole en cada caso un tipo de mejora local a la población final de cada iteración. Así

podremos comparar resultados entre las variantes y ver para nuestro problema, cual obtiene mejores resultados

y comparar para que tamaños del problema funciona mejor una mejora local que otra.

Estas son las cuatro mejoras locales que hemos decidido implementar:

5.8.1 Mejora local de inserción a un individuo

Una vez obtenemos nuestra población final, al mejor individuo de dicha población, es decir el de menor

makespan, le aplicaremos una mejora local de inserción.

La mejora local consistirá en ir insertando cada trabajo en distintas posiciones obteniendo así nuevos

individuos y evaluaremos cada nuevo individuo quedándonos con el mejor tras insertar todos los trabajos en

todas las posiciones.

1º-Tomamos trabajo que vamos a insertar:

Figura 5-7: Ejemplo Inserción I. Elaboración propia.

51

2º- Insertamos en trabajo en la posición escogida:

Figura 5-8: Ejemplo Inserción II. Elaboración propia.

3º- Obtenemos el nuevo individuo y lo evaluamos, si es mejor que el mejor hasta el momento, lo guardamos

como el mejor, sino se desechara.

Figura 5-9: Ejemplo Inserción III. Elaboración propia.

4º-Iremos repitiendo el proceso para todos los trabajos en todas las posiciones y nos quedaremos con el mejor

que sustituirá a nuestro mejor individuo de la población final que habíamos obtenido.

5.8.2 Mejora local de inserción a todos individuos

Es el mismo tipo de mejora que la anterior solo que repetiremos el proceso para todos los individuos de

nuestra población final, en vez de solo aplicarle la mejora al mejor de todos.

52

Figura 5-10: Diagrama de flujo para modelo propuesto II: “Inserción1”. Elaboración propia.

53

Figura 5-11: Diagrama de flujo para modelo propuesto III: “Inserción10”. Elaboración propia.

54

5.8.3 Mejora local de intercambio a un individuo

Al igual que en la mejora de inserción tomaremos al mejor individuo de la población final y a este le

aplicaremos la mejora local.

En este caso, en vez de ir insertando trabajos iremos intercambiándolos, es decir, tomaremos un trabajo y lo

intercambiaremos con el primer trabajo de la secuencia y evaluaremos el nuevo individuo. Repetiremos el

proceso intercambiando nuestro trabajo con todos los demás y evaluando las nuevas soluciones, quedándonos

al final con el individuo que nos proporciones la mejor solución.

1º-Tomamos trabajo que vamos a intercambiar

Figura 5-12: Ejemplo Intercambio I. Elaboración propia.

2º- Intercambiamos el trabajo escogido con otro:

Figura 5-13: Ejemplo Intercambio II. Elaboración propia.

3º- Tras el intercambio obtendremos un nuevo individuo que evaluaremos y guardaremos como mejor, si

mejora al mejor actual que teníamos.

55

Figura 5-14: Ejemplo Intercambio III. Elaboración propia.

4º- Intercambiaremos el trabajo con todo el resto de trabajo y así iremos obteniendo nuevos individuos de los

cuales nos quedaremos con el mejor, tras intercambiarlo con todos pasaremos al siguiente trabajo y

volveremos a intercambiarlo con todos e iremos repitiendo el proceso hasta que lo hayamos hecho con todos.

5.8.4 Mejora local de intercambio a todos los individuos

Esta mejora consiste en repetir el mismo proceso que en anterior punto, pero haciéndolo para todos los

individuos no solo para el mejor de la población final.

56

Figura 5-15: Diagrama de flujo para modelo propuesto IV: “Intercambio1”. Elaboración propia.

57

Figura 5-16: Diagrama de flujo para modelo propuesto V: “Intercambio10”. Elaboración propia.

58

6 COMPARACIÓN DE RESULTADOS

n este capítulo procederemos a analizar los resultados obtenidos mediante los distintos métodos,

ayudándonos de gráficos que ayuden a visualizar los datos más destacados

6.1 Generación de problemas

La primera fase de los experimentos consiste en la generación aleatoria de una batería de problemas. Los

parámetros que se tuvieron en cuenta en para la generación fueron: el número de trabajos que tendremos que

procesar, el número de etapas por el que tendrán que pasar y el % de missing, es decir, el porcentaje de

operaciones que se saltaran los trabajos.

Los números de trabajos considerados fueron 20, 50 y 100. El número de etapas fue 5,10 y 20. Y los

porcentajes de missing tomados fueron 0%, 20%, 40% y 60%. Para cada combinación de parámetros se

generaron 10 instancias, por lo que el número total de problemas considerados fue de 360.

En la siguiente tabla se muestra un ejemplo de uno de los problemas generados:

E

59

Ejemplo: 10 trabajos, 10 etapas, 40% missing

Nº de

trabajos 10

Nº de maqs.

por etapa 2 1 1 3 1 3 1 4 3 3

Tiempos de

proceso

95 54 0 78 98 43 0 35 0 0

30 46 61 81 4 0 0 16 0 43

0 63 0 0 32 92 4 25 48 0

92 50 30 0 0 70 21 34 20 0

60 70 0 0 0 74 0 6 0 0

0 76 0 0 0 32 79 0 46 0

0 88 0 98 0 79 0 97 28 33

24 0 94 50 0 45 0 0 67 0

0 97 74 54 0 0 56 82 69 0

89 33 86 14 0 70 84 60 72 2

57 1 0 16 0 53 81 42 63 47

30 67 0 88 13 0 14 31 79 71

0 0 29 0 42 90 34 0 2 13

0 0 39 0 98 0 20 58 84 65

0 0 0 0 91 0 13 97 2 8

0 0 80 1 78 0 0 0 73 77

0 0 40 0 0 87 29 53 88 19

0 54 46 0 0 8 15 0 14 20

78 0 0 93 0 0 59 0 0 0

21 47 84 7 46 34 73 0 0 0

Tabla 6-1: Ejemplo datos para problema propuesto

60

Los tiempos de proceso asignados para cada uno de los trabajos en cada etapa fueron generados aleatoriamente

entre un intervalo de [0,100], siendo 0 el porcentaje de tiempos considerado por el % de missing.

6.2 Análisis de los resultados en función de los parámetros

En este apartado procederemos a analizar los resultados de los diferentes métodos que usamos buscando cual

se ajusta mejor a cada variante de los parámetros.

Para esto vamos a usar el DPRA, desvío porcentual relativo aceptable, aunque normalmente se le conoce por

su nombre en inglés, ARPD (Average relative percentage deviation). El ARPD es una medida estadística que

describe la propagación de los datos con respecto a la media y el resultado se expresa como un porcentaje.

El ARPD se calcula como:

ARPD = (𝐹 − 𝐹𝑏𝑒𝑠𝑡)/𝐹𝑏𝑒𝑠𝑡

Siendo F el resultado del método para el que estamos calculando el ARPD y 𝐹𝑏𝑒𝑠𝑡 el mejor resultado

encontrado de entre todos los métodos para el problema dado.

En la siguiente tabla recogemos todos los resultados obtenidos por los distintos métodos en función de los

distintos parámetros de los problemas. Los datos para cada caso son una media de los ARPD obtenidos para

las 10 instancias de cada tipo de problema.

61

numjobs etapas % missing NORMAL INSERCION1 INSERCION10 INTERCAMBIO1 INTERCAMBIO 10

20

5

0 1,28% 0,62% 0,03% 0,47% 0,38%

20 0,65% 1,18% 0,26% 1,03% 0,27%

40 1,04% 1,04% 0,66% 0,46% 0,05%

60 0,35% 0,65% 0,00% 0,00% 0,00%

10

0 1,27% 0,60% 0,37% 1,11% 0,28%

20 1,10% 1,01% 0,77% 2,61% 0,20%

40 1,04% 0,70% 0,28% 0,85% 0,33%

60 0,06% 0,00% 0,00% 0,00% 0,00%

20

0 1,37% 2,16% 0,62% 1,52% 0,88%

20 2,55% 1,39% 0,92% 2,83% 0,38%

40 1,71% 0,78% 0,34% 0,32% 0,13%

60 0,35% 0,16% 0,14% 0,14% 0,03%

50

5

0 0,82% 0,33% 0,28% 0,50% 0,21%

20 0,00% 0,08% 0,13% 0,08% 0,24%

40 0,35% 0,19% 0,25% 1,08% 0,09%

60 0,16% 0,12% 0,00% 0,00% 0,00%

10

0 0,95% 0,53% 1,20% 0,80% 1,28%

20 0,93% 0,46% 0,86% 1,10% 0,54%

40 0,36% 0,03% 0,09% 0,24% 0,02%

60 0,11% 0,02% 0,05% 0,11% 0,00%

20

0 1,02% 1,20% 2,03% 1,32% 1,94%

20 0,70% 1,65% 1,27% 1,62% 0,63%

40 1,07% 1,49% 1,07% 0,66% 0,59%

60 0,19% 0,86% 0,56% 0,54% 0,48%

100

5

0 0,03% 0,12% 1,48% 0,08% 1,27%

20 0,10% 0,03% 0,29% 0,00% 0,46%

40 0,61% 0,00% 1,06% 0,19% 1,19%

60 0,00% 0,00% 0,02% 0,00% 0,14%

10

0 0,14% 0,58% 4,07% 0,51% 3,40%

20 0,16% 0,53% 1,81% 0,29% 2,09%

40 0,18% 0,00% 1,74% 0,24% 1,48%

60 0,06% 0,00% 0,65% 0,02% 0,80%

20

0 0,16% 1,27% 4,44% 0,86% 4,95%

20 0,29% 1,68% 4,44% 1,11% 3,94%

40 0,36% 0,49% 2,92% 0,49% 2,75%

60 0,66% 0,61% 2,08% 0,78% 2,06%

Tabla 6-2: Resultados clasificados por parámetros

62

6.2.1 Análisis de resultados en función del número de trabajos

En este apartado analizaremos los resultados obtenidos por los distintos métodos para distintos valores del

número de trabajos, comparándolos entre ellos.

En la siguiente tabla tenemos los promedios de los ARPD para todos los métodos para los distintos tamaños

del problema:

A partir de los datos de la tabla hemos obtenido una gráfica que nos permite analizar más cómodamente los

resultados:

Figura 6-1: Gráfica resultados en función numjobs. Elaboración propia.

0.00%

0.50%

1.00%

1.50%

2.00%

2.50%

20

ARPD en funcion de numjobs

NORMAL INSERCION1 INSERCION10 INTERCAMBIO1 INTERCAMBIO 10

50 100

numjobs NORMAL INSERCION1 INSERCION10 INTERCAMBIO1 INTERCAMBIO 10

20 1,06% 0,86% 0,36% 0,95% 0,24%

50 0,55% 0,58% 0,65% 0,67% 0,50%

100 0,23% 0,44% 2,08% 0,38% 2,05%

Average 0,62% 0,63% 1,03% 0,67% 0,93%

Tabla 6-3: Resultados en función numjobs

63

Como podemos observar los métodos que mejoran localmente todas las soluciones finales de los problemas,

Insercion10 e Intercambio10, son los mejores para tamaños de poblaciones pequeños ya que al no haber

muchos trabajos llegan a una solución muy buena antes de que finalice el tiempo de ejecución, consiguiendo

de un 0,36% el método de Inserción10 y de un 0,24% el de Intercambio10, llegando a mejorar a los otros

métodos entre un 200% y un 300%. Conforme el número de trabajos aumenta empiezan a empeorar dichos

métodos, ya que al tener que mejorar todas las soluciones y al tener estos tantos trabajos, no les da tiempo a

llegar a una buena solución antes de terminar el tiempo de ejecución, consiguiendo para los problemas de 50

trabajos resultados muy parecidos al resto de métodos, pero para los problemas de 100 trabajos consiguen

resultados mucho peores.

Los métodos que solo mejoran una solución, Inserción1 y Intercambio1, como ya hemos dicho antes son

peores que los nombrados anteriormente para problemas pequeños ya que al ir mejorando solo una solución

por iteración, aunque cada iteración tarda mucho menos tiempo que en los casos anteriores no realizan

suficientes iteraciones en el tiempo de ejecución para llegar a soluciones tan buenas como los otros. Pero para

problemas de mayor tamaño al tardar menos tiempo cada iteración consiguen resultados de 0,44% y de 0,38%

mejorando a los métodos de mejora de 10 soluciones en casi un 400%.

El método Normal es el que mejores resultados consigue cuando los problemas de 100 trabajos, con lo que

podemos concluir que al poder realizar más número de iteraciones consigue diversificarse más aunque no

profundice tanto en ellas y obtiene mejores resultados.

6.2.2 Análisis de resultados en función del número de etapas

A partir de la tabla y la gráfica siguiente procederemos a analizar en función del segundo parámetro de nuestro

problema, el número de etapas.

Al igual que en el caso anterior hemos realizado una tabla con los promedios de los ARPD obtenidos tras

resolver los problemas:

64

A partir de los datos de la tabla hemos obtenido esta gráfica:

Figura 6-2: Gráfica resultados en función número etapas. Elaboración propia.

Como podemos ver en la gráfica con el número de etapas se da un caso análogo al anterior. El número de

0.00%

0.20%

0.40%

0.60%

0.80%

1.00%

1.20%

1.40%

1.60%

1.80%

2.00%

ARPD en funcion del numero etapas


5 10 20

etapas NORMAL INSERCION1 INSERCION10 INTERCAMBIO1 INTERCAMBIO

10

5 0,45% 0,36% 0,37% 0,32% 0,36%

10 0,53% 0,37% 0,99% 0,66% 0,87%

20 0,87% 1,15% 1,74% 1,02% 1,56%

Average 0,62% 0,63% 1,03% 0,67% 0,93%

Tabla 6-4: Resultados en función del número de etapas

65

etapas incide de la misma forma que el número de trabajos, aunque de forma más leve, no habiendo tanta

diferencia entre los resultados como en el caso anterior, ya que para 5 etapas consiguen los 5 métodos casi

idénticos resultados. Aunque a diferencia que en el caso anterior los resultados siempre van empeorando

conforme aumentamos el número de etapas, aunque los de mejora de 10 empeoran más rápido, los de mejora

de 1 y el normal también empeoran al aumentar el número de etapas no como con el número de trabajos que

conforme añadíamos más trabajos mejorábamos los resultados.

En resumen, los métodos Normal, Inserción1 e Intercambio1 consiguen resultados de 0,62%, 0,63% y de

0,67%, mejorando a los métodos de Inserción10 e Intercambio10 que consiguen 1,03% y 0,93%

respectivamente. Como podemos ver, aunque hay diferencias al igual que cuando variábamos el numero de

trabajos las diferencias son muchos menores.

6.2.3 Análisis de resultados en función del porcentaje de missing

Igual que en los anteriores casos hemos obtenido una tabla con los promedios de los problemas en función del

porcentaje de missing:

% missing NORMAL INSERCION1 INSERCION10 INTERCAMBIO1 INTERCAMBIO

10

0 0,78% 0,82% 1,61% 0,80% 1,62%

20 0,72% 0,89% 1,19% 1,18% 0,97%

40 0,75% 0,52% 0,93% 0,50% 0,74%

60 0,21% 0,27% 0,39% 0,18% 0,39%

Average 0,56% 0,56% 0,84% 0,62% 0,70%

Tabla 6-5: Resultados en función del % de missing

66

A partir de los datos de la tabla hemos realizado esta gráfica:

Figura 6-3: Gráfica resultados en función del % de missing. Elaboración propia.

Como podemos ver en la tabla, los métodos de Inserción10 e Intercambio10 siguen siendo los que peor

funcionan con una media del ARPD de 0,84% y 0,70%, mientras los otros 3 métodos tienen valores muy

parecidos siendo para el Normal, 0,56%, para el Insercion1, 0,56%, y para el de Intercambio1, 0,62%, que,

aunque es un poco peor que los otros dos hay muy poca diferencia entre ellos.

Para los problemas sin considerar missing, es decir, para los que el tanto por ciento de missing es cero, los tres

métodos más simples consiguen resultados casi idénticos (0,78%, 0,82% y 0,80%) mientras que los más

complejos consiguen resultados mucho peores, llegando a ser el doble que en los anteriores casos (1,61% y

1,62%).

0.00%

0.20%

0.40%

0.60%

0.80%

1.00%

1.20%

1.40%

1.60%

1.80%

ARPD en funcion del % missing


0 20 40 60

67

Conforme vamos aumentando el porcentaje de missing los resultados van convergiendo, aunque los métodos

más complejos siempre siguen siendo los peores. Excepto para el 20% de missing en el que el método de

Intercambio1 da los peores resultados junto con el método de Insercion10.

68

7 CONCLUSIONES

n este Trabajo de Fin de Grado se ha estudiado el problema de programación de la producción del

Hybrid Flowshop con missing operation. Para ello hemos realizado una metaheurística en C que

comienza con una secuencia inicial que nos indica el orden en que entran los trabajos al taller,

posteriormente se le aplican diversos operadores de los algoritmos genéticos como son en nuestro caso: el

cruce de dos puntos y una mutación de intercambio para obtener así diversas secuencias de entrada al

problema. Tras obtener las secuencias iniciales hemos resuelto el problema obteniendo el makespan para cada

una de ellas. Una vez que tenemos todas las soluciones nos quedamos con las mejores y seguimos repitiendo

el proceso hasta alcanzar alguno de los tres criterios de parada, en nuestro caso decidimos poner dos criterios

de parada, el número de iteraciones y el número de iteraciones en las que no mejoramos la solución inicial de

la iteración, con valores muy altos para que el programa solo parase por el criterio del tiempo de ejecución.

Una vez resuelto los problemas, mediante este método, se le aplican distintas mejoras locales a este para ver si

aplicando dichas mejoras podíamos conseguir mejores resultados en el mismo tiempo de ejecución. Para ello

decidimos aplicar las mejoras a las secuencias finales tras cada iteración, que son las usadas como secuencias

iniciales en la siguiente iteración, intentando así llegar a mejores resultados en menos tiempo. Las distintas

mejoras que hemos aplicados se pueden dividir en dos grupos, unas solo mejoran la mejor solución de la

iteración, así conseguimos profundizar en el camino de la óptima, reduciendo así la diversificación y los

tiempos de cálculo ya que se llegará a un óptimo de manera rápida al ir descartando el resto de caminos, pero

pudiendo caer así en óptimos locales al solo profundizar en un sentido. El otro grupo de métodos mejora todas

las soluciones tras cada iteración, consiguiendo diversificar mucho el espacio de búsqueda de soluciones, pero

al aumentar este la carga de trabajo será mucho mayor no consiguiendo profundizar tanto en todas las

direcciones como el resto de métodos.

En los capítulos 1,2 y 3 se contextualiza nuestro problema dentro de la Organización de la Producción y de la

Planificación de la Producción. También se han desarrollado los conocimientos teóricos necesarios para

entender los métodos aplicados en la resolución de los problemas, explicando las características de los

entornos de producción, los objetivos que buscamos mejorar con nuestro trabajo y las restricciones que se

tienen.

E

69

En el capítulo 4 se explican detalladamente los métodos que hemos implementado para resolver el problema,

acompañando las explicaciones con los diagramas de flujo correspondientes a cada método. Los códigos

usados para cada método se pueden ver en el Anexo B. Para finalizar en el capítulo 5 hemos analizado los

resultados según los diferentes parámetros del problema y comparando los ARPDs obtenidos para cada

método. Los resultados concretos para cada problema resuelto por los distintos métodos se pueden ver en el

Anexo A.

En esta tabla hemos representado los resultados finales para cada método, haciendo la media del ARPD

obtenido por cada uno de ellos:

Tabla 7-1: Resultados finales

A partir de esta gráfica y los resultados comentados en el apartado 5 podemos concluir que los métodos que

diversifican menos y mejoran los resultados en un solo sentido, o no aplican ninguna mejora, obtienen bastante

mejores resultados de media que aquellos métodos que se diversifican mucho y no son capaces de profundizar

en todo el espacio de búsqueda en el tiempo de ejecución determinado.

Cabe destacar que, aunque de media los métodos Inserción10 e Intercambio10 obtienen bastante peores

resultados que el resto de métodos, se observa que, para problemas de tamaño pequeño, es decir número de

trabajos y etapas reducidos, obtienen mejores resultados.

0.00%

0.20%

0.40%

0.60%

0.80%

1.00%

1.20%


70

8 BIBLIOGRAFÍA

F. A. Ogbu and D. K. Smith, “The application of the simulated annealing algorithm to the solution of the

n/m/Cmax flowshop problem”, 1990.

J. H. Holland, “Adaptation in Natural and Artificial Systems”. Univ. of Michigan Press, Ann Arbor, 1976.

F. A. Ogbu and D. K. Smith, “Simulated annealing for the permutation flow-shop problem”. 1991

C. R. Reeves, “An introduction to genetic algorithms” en Operational Research Tutorial Papers ,1991.

C. R. Reeves, “A genetic algorith for flowshop sequencing” en Computer and Operations Research, 1995.

M. Zandieh, and N. Karimi, “An adaptive multi-population genetic algorithm to solve the multi-objective

group scheduling problem in hybrid flexible flowshop with sequence-dependent setup times”, en Journal of

Intelligent Manufacturing, 2010

S. M. H. Hojjati, and A. Sahraeyan, “Minimizing makespan subject to budget limitation in hybrid flow shop”,

en International Conference on Computers & Industrial Engineering, 2009.

Juan C. Lopez, Jaime A. Giraldo and Jaime A. Arango, “Reducción del Tiempo de Terminación en la

Programación de la Producción de una Línea de Flujo Híbrida Flexible (HFS)”, versión online, 2005.

Saravanan, M., Sridhar, S. and Harikannan, N. “Application of meta-heuristics for minimization of makespan

in multi-stage hybrid flow shop scheduling problems with missing operations” en International Review of

mechanical engineering, 2014.

Rubén Ruiz and Jose Antonio Vázquez-Rodríguez, “The hybrid flow shop scheduling problem”, en European

Journey of Operational Research,2010.

71

Imma Ribas Vila and Ramon Companys Pascual, “Programación de la Producción en un sistema flow shop

híbrido sin esperas y tiempos de preparación dependientes de la secuencia”, Working Paper del Departament

d’Organització D’empreses de la Universitat Politècnica de Catalunya, 2010.

M.K. Marichelvam, “Performance evaluation of an improved hybrid genetic scatter search (IHGSS)

algorithm for multistage hybrid flow shop scheduling problems with missing operations”, en Int. J. Industrial

and Systems Engineering,2014.

Jose M Framinan, Rainer Leisten, Rubén Ruiz, “Manufacturing Scheduling Systems”, 2013.

Michael L. Pinedo, “Scheduling Theory, Algorithms and systems”, 2008.

Marcos Gestal, Daniel Rivero, Juan Ramón Rabuñal, Julián Dorado and Alejandro Pazos, “Introducción a los

Algoritmos Genéticos y la Programación Genética”,2010

Javier Santos García, “Organización de la Producción II Planificación de procesos productivos”,2010.

Chao-Tang Tseng, Ching-Jong Liao, Tai-Xiang Liao. “A note on two-stage hybrid flowshop scheduling with

missing operations”, in Computers & Industrial Engineering,2008.

Nakano, R., and Yamada, T. “Conventional genetic algorithm for job-shop problems”, en 4th International

Conference on Genetic Algorithms and their Applications,1991.

Osman, I. H. and Kelly J. P. “Meta-Heuristics: theory and applications”. Boston: Kluwer Academic, 1996.

Juan Camilo Lopez Vargas. “Metodología de Programación de Producción en un Flow Shop Híbrido

Flexible con el Uso de Algoritmos Genéticos para Reducir el Makespan. Aplicación en la Industria

Textil, Tesis de Maestría, 2013.

Jose M Framinan, Paz Perez-Gonzalez, Víctor Fernandez-Viagas “Tema 1: Introducción a la

Programación y Control de la Producción”, 2015

Jose M Framinan, Paz Perez-Gonzalez, Víctor Fernandez-Viagas “Tema 2: Programación de la Producción:

Introducción y Objetivos”, 2015

Jose M Framinan, Paz Perez-Gonzalez, Víctor Fernandez-Viagas “Tema 3: Modelos de Programación de la

72

Producción: Entornos”, 2015

Jose M Framinan, Paz Perez-Gonzalez, Víctor Fernandez-Viagas “Tema 4: Modelos de Programación de la

Producción: Restricciones”, 2015

73

9 ANEXOS

9.1 Anexo A: Resultados en Excel

En este Anexo recogeremos los resultados de las 5 variantes de nuestro método para los distintos problemas,

Usaremos las abreviaciones %m y I, para nombra el tanto por ciento de missing y el numero de instancias

respectivamente.

n k %

m

I NORMAL INSERCION 1 INSERCION 10 INTERCAMBIO

1

INERCAMBIO

10

MENOR

20 5 0 0 1174 5,0% 1118 0,00% 1118 0,00% 1118 0,00% 1118 0,00% 1118 20 5 0 1 723 3,9% 722 3,74% 696 0,00% 710 2,01% 705 1,29% 696 20 5 0 2 618 0,3% 621 0,81% 616 0,00% 621 0,81% 617 0,16% 616 20 5 0 3 1178 0,0% 1178 0,00% 1178 0,00% 1178 0,00% 1178 0,00% 1178 20 5 0 4 1163 0,0% 1163 0,00% 1163 0,00% 1163 0,00% 1163 0,00% 1163 20 5 0 5 1103 0,0% 1103 0,00% 1103 0,00% 1103 0,00% 1103 0,00% 1103 20 5 0 6 1179 0,0% 1179 0,00% 1179 0,00% 1179 0,00% 1179 0,00% 1179 20 5 0 7 830 3,0% 814 0,99% 806 0,00% 810 0,50% 822 1,99% 806 20 5 0 8 1287 0,3% 1291 0,62% 1287 0,31% 1283 0,00% 1283 0,00% 1283 20 5 0 9 920 0,3% 917 0,00% 917 0,00% 930 1,42% 920 0,33% 917 20 5 20 0 707 0,0% 707 0,00% 707 0,00% 719 1,70% 707 0,00% 707 20 5 20 1 433 0,0% 447 3,23% 436 0,69% 440 1,62% 436 0,69% 433 20 5 20 2 865 0,0% 865 0,00% 865 0,00% 865 0,00% 865 0,00% 865 20 5 20 3 445 0,5% 445 0,45% 443 0,00% 445 0,45% 444 0,23% 443 20 5 20 4 463 0,0% 463 0,00% 463 0,00% 463 0,00% 463 0,00% 463 20 5 20 5 518 0,2% 525 1,55% 517 0,00% 526 1,74% 524 1,35% 517 20 5 20 6 892 0,5% 888 0,00% 888 0,00% 892 0,45% 892 0,45% 888 20 5 20 7 549 3,8% 550 3,97% 539 1,89% 541 2,27% 529 0,00% 529 20 5 20 8 1005 0,0% 1005 0,00% 1005 0,00% 1026 2,09% 1005 0,00% 1005 20 5 20 9 550 1,7% 555 2,59% 541 0,00% 541 0,00% 541 0,00% 541 20 5 40 0 695 0,0% 695 0,00% 695 0,00% 695 0,00% 695 0,00% 695 20 5 40 1 576 0,0% 576 0,00% 576 0,00% 576 0,00% 576 0,00% 576 20 5 40 2 383 3,8% 383 3,79% 369 0,00% 386 4,61% 371 0,54% 369 20 5 40 3 678 0,0% 678 0,00% 678 0,00% 678 0,00% 678 0,00% 678 20 5 40 4 745 0,0% 745 0,00% 745 0,00% 745 0,00% 745 0,00% 745 20 5 40 5 649 0,0% 649 0,00% 649 0,00% 649 0,00% 649 0,00% 649 20 5 40 6 746 6,6% 746 6,57% 746 6,57% 700 0,00% 700 0,00% 700 20 5 40 7 724 0,0% 724 0,00% 724 0,00% 724 0,00% 724 0,00% 724 20 5 40 8 617 0,0% 617 0,00% 617 0,00% 617 0,00% 617 0,00% 617 20 5 40 9 735 0,0% 735 0,00% 735 0,00% 735 0,00% 735 0,00% 735 20 5 60 0 481 0,0% 481 0,00% 481 0,00% 481 0,00% 481 0,00% 481 20 5 60 1 232 0,0% 240 3,45% 232 0,00% 232 0,00% 232 0,00% 232 20 5 60 2 209 0,0% 209 0,00% 209 0,00% 209 0,00% 209 0,00% 209 20 5 60 3 416 0,0% 416 0,00% 416 0,00% 416 0,00% 416 0,00% 416 20 5 60 4 284 0,0% 284 0,00% 284 0,00% 284 0,00% 284 0,00% 284 20 5 60 5 762 0,0% 762 0,00% 762 0,00% 762 0,00% 762 0,00% 762 20 5 60 6 280 0,0% 280 0,00% 280 0,00% 280 0,00% 280 0,00% 280 20 5 60 7 236 3,5% 235 3,07% 228 0,00% 228 0,00% 228 0,00% 228 20 5 60 8 592 0,0% 592 0,00% 592 0,00% 592 0,00% 592 0,00% 592 20 5 60 9 478 0,0% 478 0,00% 478 0,00% 478 0,00% 478 0,00% 478

74

n k %

m

I NORMAL INSERCION 1 INSERCION 10 INTERCAMBIO

1

INERCAMBIO

10

MENOR

20 10 0 0 1508 4,3% 1508 4,29% 1446 0,00% 1508 4,29% 1481 2,42% 1446

20 10 0 1 1369 0,0% 1369 0,00% 1395 1,90% 1369 0,00% 1369 0,00% 1369

20 10 0 2 1445 0,0% 1445 0,00% 1445 0,00% 1445 0,00% 1445 0,00% 1445

20 10 0 3 1540 0,1% 1540 0,13% 1538 0,00% 1540 0,13% 1538 0,00% 1538

20 10 0 4 1550 2,0% 1520 0,00% 1520 0,00% 1525 0,33% 1520 0,00% 1520

20 10 0 5 1180 0,9% 1180 0,94% 1180 0,94% 1169 0,00% 1169 0,00% 1169

20 10 0 6 1174 1,3% 1159 0,00% 1159 0,00% 1159 0,00% 1159 0,00% 1159

20 10 0 7 1243 1,6% 1223 0,00% 1223 0,00% 1243 1,64% 1223 0,00% 1223

20 10 0 8 1304 0,0% 1313 0,69% 1315 0,84% 1313 0,69% 1309 0,38% 1304

20 10 0 9 1262 2,4% 1232 0,00% 1232 0,00% 1282 4,06% 1232 0,00% 1232

20 10 20 0 1066 0,0% 1066 0,00% 1066 0,00% 1066 0,00% 1066 0,00% 1066

20 10 20 1 1158 0,0% 1158 0,00% 1158 0,00% 1158 0,00% 1158 0,00% 1158

20 10 20 2 726 4,3% 741 6,47% 731 5,03% 733 5,32% 696 0,00% 696

20 10 20 3 1056 1,3% 1053 1,06% 1042 0,00% 1068 2,50% 1042 0,00% 1042

20 10 20 4 1150 0,3% 1147 0,09% 1146 0,00% 1147 0,09% 1147 0,09% 1146

20 10 20 5 1041 3,9% 1003 0,10% 1002 0,00% 1091 8,88% 1005 0,30% 1002

20 10 20 6 1164 1,1% 1165 1,22% 1165 1,22% 1168 1,48% 1151 0,00% 1151

20 10 20 7 1078 0,0% 1078 0,00% 1078 0,00% 1078 0,00% 1078 0,00% 1078

20 10 20 8 968 0,0% 968 0,00% 968 0,00% 968 0,00% 968 0,00% 968

20 10 20 9 698 0,0% 706 1,15% 708 1,43% 753 7,88% 709 1,58% 698

20 10 40 0 1003 2,8% 1003 2,77% 976 0,00% 1003 2,77% 1003 2,77% 976

20 10 40 1 762 0,0% 762 0,00% 762 0,00% 762 0,00% 762 0,00% 762

20 10 40 2 587 3,3% 587 3,35% 580 2,11% 585 2,99% 568 0,00% 568

20 10 40 3 985 0,0% 985 0,00% 985 0,00% 985 0,00% 985 0,00% 985

20 10 40 4 893 0,0% 893 0,00% 893 0,00% 893 0,00% 893 0,00% 893

20 10 40 5 768 0,0% 775 0,91% 773 0,65% 768 0,00% 772 0,52% 768

20 10 40 6 899 4,3% 862 0,00% 862 0,00% 884 2,55% 862 0,00% 862

20 10 40 7 740 0,0% 740 0,00% 740 0,00% 740 0,00% 740 0,00% 740

20 10 40 8 708 0,0% 708 0,00% 708 0,00% 708 0,00% 708 0,00% 708

20 10 40 9 891 0,0% 891 0,00% 891 0,00% 893 0,22% 891 0,00% 891

20 10 60 0 701 0,6% 697 0,00% 697 0,00% 697 0,00% 697 0,00% 697

20 10 60 1 475 0,0% 475 0,00% 475 0,00% 475 0,00% 475 0,00% 475

20 10 60 2 525 0,0% 525 0,00% 525 0,00% 525 0,00% 525 0,00% 525

20 10 60 3 382 0,0% 382 0,00% 382 0,00% 382 0,00% 382 0,00% 382

20 10 60 4 548 0,0% 548 0,00% 548 0,00% 548 0,00% 548 0,00% 548

20 10 60 5 687 0,0% 687 0,00% 687 0,00% 687 0,00% 687 0,00% 687

20 10 60 6 558 0,0% 558 0,00% 558 0,00% 558 0,00% 558 0,00% 558

20 10 60 7 687 0,0% 687 0,00% 687 0,00% 687 0,00% 687 0,00% 687

20 10 60 8 494 0,0% 494 0,00% 494 0,00% 494 0,00% 494 0,00% 494

20 10 60 9 532 0,0% 532 0,00% 532 0,00% 532 0,00% 532 0,00% 532

75

n k %m I NORMAL INSERCION 1 INSERCION 10 INTERCAMBIO

1

INERCAMBIO

10

MENOR

20 20 0 0 1848 0,9% 1884 2,84% 1832 0,00% 1929 5,29% 1841 0,49% 1832

20 20 0 1 1974 0,0% 2019 2,28% 1993 0,96% 2046 3,65% 1974 0,00% 1974

20 20 0 2 2056 3,3% 2029 1,96% 1990 0,00% 2041 2,56% 2053 3,17% 1990

20 20 0 3 2010 1,5% 1986 0,25% 1982 0,05% 1985 0,20% 1981 0,00% 1981

20 20 0 4 1820 1,6% 1923 7,37% 1853 3,46% 1791 0,00% 1801 0,56% 1791

20 20 0 5 2058 0,8% 2088 2,30% 2069 1,37% 2041 0,00% 2066 1,22% 2041

20 20 0 6 2100 1,0% 2083 0,19% 2079 0,00% 2100 1,01% 2085 0,29% 2079

20 20 0 7 1786 0,0% 1786 0,00% 1786 0,00% 1786 0,00% 1786 0,00% 1786

20 20 0 8 1925 1,2% 1903 0,00% 1909 0,32% 1927 1,26% 1947 2,31% 1903

20 20 0 9 1737 3,4% 1754 4,40% 1680 0,00% 1701 1,25% 1692 0,71% 1680

20 20 20 0 1574 8,3% 1523 4,75% 1476 1,51% 1566 7,70% 1454 0,00% 1454

20 20 20 1 1361 0,0% 1363 0,15% 1369 0,59% 1374 0,96% 1361 0,00% 1361

20 20 20 2 1494 1,7% 1498 1,97% 1469 0,00% 1542 4,97% 1503 2,31% 1469

20 20 20 3 1620 1,6% 1620 1,63% 1620 1,63% 1614 1,25% 1594 0,00% 1594

20 20 20 4 1460 1,7% 1449 0,98% 1508 5,09% 1503 4,74% 1435 0,00% 1435

20 20 20 5 1541 2,5% 1531 1,86% 1503 0,00% 1540 2,46% 1520 1,13% 1503

20 20 20 6 1651 0,2% 1648 0,00% 1648 0,00% 1665 1,03% 1648 0,00% 1648

20 20 20 7 1677 2,9% 1629 0,00% 1629 0,00% 1639 0,61% 1634 0,31% 1629

20 20 20 8 1846 2,3% 1829 1,39% 1804 0,00% 1837 1,83% 1804 0,00% 1804

20 20 20 9 1654 4,2% 1607 1,20% 1594 0,38% 1631 2,71% 1588 0,00% 1588

20 20 40 0 1234 6,0% 1164 0,00% 1164 0,00% 1172 0,69% 1164 0,00% 1164

20 20 40 1 1131 0,0% 1131 0,00% 1131 0,00% 1131 0,00% 1131 0,00% 1131

20 20 40 2 1380 0,7% 1387 1,17% 1371 0,00% 1387 1,17% 1371 0,00% 1371

20 20 40 3 1488 1,1% 1500 1,90% 1472 0,00% 1472 0,00% 1472 0,00% 1472

20 20 40 4 1059 1,3% 1059 1,34% 1067 2,11% 1045 0,00% 1045 0,00% 1045

20 20 40 5 1254 5,6% 1203 1,35% 1193 0,51% 1187 0,00% 1203 1,35% 1187

20 20 40 6 1297 0,0% 1297 0,00% 1297 0,00% 1297 0,00% 1297 0,00% 1297

20 20 40 7 1124 2,2% 1109 0,82% 1109 0,82% 1109 0,82% 1100 0,00% 1100

20 20 40 8 1428 0,1% 1444 1,26% 1426 0,00% 1434 0,56% 1426 0,00% 1426

20 20 40 9 1383 0,0% 1383 0,00% 1383 0,00% 1383 0,00% 1383 0,00% 1383

20 20 60 0 1061 0,9% 1052 0,00% 1052 0,00% 1052 0,00% 1052 0,00% 1052

20 20 60 1 957 1,2% 957 1,16% 957 1,16% 957 1,16% 946 0,00% 946

20 20 60 2 1011 0,0% 1011 0,00% 1011 0,00% 1011 0,00% 1011 0,00% 1011

20 20 60 3 784 0,0% 786 0,26% 786 0,26% 786 0,26% 786 0,26% 784

20 20 60 4 754 0,0% 754 0,00% 754 0,00% 754 0,00% 754 0,00% 754

20 20 60 5 848 0,6% 843 0,00% 843 0,00% 843 0,00% 843 0,00% 843

20 20 60 6 916 0,9% 910 0,22% 908 0,00% 908 0,00% 908 0,00% 908

20 20 60 7 791 0,0% 791 0,00% 791 0,00% 791 0,00% 791 0,00% 791

20 20 60 8 1003 0,0% 1003 0,00% 1003 0,00% 1003 0,00% 1003 0,00% 1003

20 20 60 9 833 0,0% 833 0,00% 833 0,00% 833 0,00% 833 0,00% 833

76


1

INERCAMBIO

10

MENOR

50 5 0 0 2392 0,0% 2393 0,04% 2392 0,00% 2392 0,00% 2392 0,00% 2392

50 5 0 1 2693 0,6% 2693 0,64% 2676 0,00% 2676 0,00% 2693 0,64% 2676

50 5 0 2 1037 2,5% 1025 1,28% 1012 0,00% 1029 1,68% 1014 0,20% 1012

50 5 0 3 2638 0,3% 2630 0,00% 2630 0,00% 2635 0,19% 2630 0,00% 2630

50 5 0 4 2578 0,0% 2580 0,08% 2578 0,00% 2578 0,00% 2578 0,00% 2578

50 5 0 5 2604 0,0% 2604 0,00% 2604 0,00% 2604 0,00% 2604 0,00% 2604

50 5 0 6 1440 1,3% 1432 0,77% 1431 0,70% 1432 0,77% 1421 0,00% 1421

50 5 0 7 1020 2,9% 991 0,00% 1012 2,12% 1014 2,32% 1004 1,31% 991

50 5 0 8 2841 0,5% 2841 0,50% 2827 0,00% 2827 0,00% 2827 0,00% 2827

50 5 0 9 2946 0,0% 2946 0,00% 2946 0,00% 2946 0,00% 2946 0,00% 2946

50 5 20 0 2205 0,0% 2205 0,00% 2205 0,00% 2205 0,00% 2205 0,00% 2205

50 5 20 1 2006 0,0% 2006 0,00% 2006 0,00% 2006 0,00% 2006 0,00% 2006

50 5 20 2 2203 0,0% 2203 0,00% 2203 0,00% 2203 0,00% 2203 0,00% 2203

50 5 20 3 2281 0,0% 2281 0,00% 2281 0,00% 2281 0,00% 2281 0,00% 2281

50 5 20 4 2247 0,0% 2247 0,00% 2247 0,00% 2247 0,00% 2247 0,00% 2247

50 5 20 5 2247 0,0% 2264 0,76% 2277 1,34% 2264 0,76% 2300 2,36% 2247

50 5 20 6 2534 0,0% 2534 0,00% 2534 0,00% 2534 0,00% 2534 0,00% 2534

50 5 20 7 1269 0,0% 1269 0,00% 1269 0,00% 1269 0,00% 1269 0,00% 1269

50 5 20 8 2052 0,0% 2052 0,00% 2052 0,00% 2052 0,00% 2052 0,00% 2052

50 5 20 9 1807 0,0% 1807 0,00% 1807 0,00% 1807 0,00% 1807 0,00% 1807

50 5 40 0 1578 0,0% 1578 0,00% 1578 0,00% 1578 0,00% 1578 0,00% 1578

50 5 40 1 1393 0,0% 1393 0,00% 1393 0,00% 1393 0,00% 1393 0,00% 1393

50 5 40 2 1344 0,0% 1344 0,00% 1344 0,00% 1344 0,00% 1344 0,00% 1344

50 5 40 3 978 3,2% 959 1,16% 948 0,00% 964 1,69% 948 0,00% 948

50 5 40 4 1828 0,3% 1822 0,00% 1822 0,00% 1822 0,00% 1822 0,00% 1822

50 5 40 5 2172 0,0% 2172 0,00% 2172 0,00% 2172 0,00% 2172 0,00% 2172

50 5 40 6 1416 0,0% 1416 0,00% 1416 0,00% 1416 0,00% 1416 0,00% 1416

50 5 40 7 1751 0,0% 1751 0,00% 1751 0,00% 1751 0,00% 1751 0,00% 1751

50 5 40 8 559 0,0% 563 0,72% 573 2,50% 610 9,12% 564 0,89% 559

50 5 40 9 1530 0,0% 1530 0,00% 1530 0,00% 1530 0,00% 1530 0,00% 1530

50 5 60 0 870 0,0% 870 0,00% 870 0,00% 870 0,00% 870 0,00% 870

50 5 60 1 933 0,0% 933 0,00% 933 0,00% 933 0,00% 933 0,00% 933

50 5 60 2 1454 0,0% 1454 0,00% 1454 0,00% 1454 0,00% 1454 0,00% 1454

50 5 60 3 1021 0,0% 1021 0,00% 1021 0,00% 1021 0,00% 1021 0,00% 1021

50 5 60 4 889 0,0% 889 0,00% 889 0,00% 889 0,00% 889 0,00% 889

50 5 60 5 652 1,2% 652 1,24% 644 0,00% 644 0,00% 644 0,00% 644

50 5 60 6 584 0,3% 582 0,00% 582 0,00% 582 0,00% 582 0,00% 582

50 5 60 7 893 0,0% 893 0,00% 893 0,00% 893 0,00% 893 0,00% 893

50 5 60 8 661 0,0% 661 0,00% 661 0,00% 661 0,00% 661 0,00% 661

50 5 60 9 847 0,0% 847 0,00% 847 0,00% 847 0,00% 847 0,00% 847

77


1

INERCAMBIO

10

MENOR

50 10 0 0 2738 0,0% 2747 0,33% 2747 0,33% 2754 0,58% 2742 0,15% 2738

50 10 0 1 2586 1,7% 2543 0,00% 2580 1,45% 2605 2,44% 2581 1,49% 2543

50 10 0 2 2923 1,1% 2890 0,00% 2926 1,25% 2899 0,31% 2943 1,83% 2890

50 10 0 3 2612 0,0% 2612 0,00% 2612 0,00% 2612 0,00% 2615 0,11% 2612

50 10 0 4 2913 1,3% 2875 0,00% 2896 0,73% 2875 0,00% 2903 0,97% 2875

50 10 0 5 1439 2,3% 1416 0,64% 1429 1,56% 1407 0,00% 1426 1,35% 1407

50 10 0 6 2831 0,0% 2831 0,00% 2831 0,00% 2831 0,00% 2831 0,00% 2831

50 10 0 7 2732 0,0% 2841 3,99% 2788 2,05% 2768 1,32% 2820 3,22% 2732

50 10 0 8 1686 3,1% 1635 0,00% 1708 4,46% 1672 2,26% 1688 3,24% 1635

50 10 0 9 2767 0,0% 2776 0,33% 2771 0,14% 2797 1,08% 2778 0,40% 2767

50 10 20 0 2267 2,1% 2226 0,23% 2244 1,04% 2221 0,00% 2221 0,00% 2221

50 10 20 1 1932 3,9% 1895 1,94% 1932 3,93% 1859 0,00% 1860 0,05% 1859

50 10 20 2 2157 0,0% 2157 0,00% 2157 0,00% 2157 0,00% 2157 0,00% 2157

50 10 20 3 2229 0,0% 2254 1,12% 2263 1,53% 2277 2,15% 2277 2,15% 2229

50 10 20 4 2191 1,9% 2151 0,00% 2157 0,28% 2196 2,09% 2191 1,86% 2151

50 10 20 5 2065 0,3% 2058 0,00% 2058 0,00% 2106 2,33% 2058 0,00% 2058

50 10 20 6 2039 0,4% 2031 0,00% 2031 0,00% 2039 0,39% 2031 0,00% 2031

50 10 20 7 2330 0,7% 2314 0,00% 2314 0,00% 2314 0,00% 2330 0,69% 2314

50 10 20 8 2189 0,0% 2189 0,00% 2189 0,00% 2189 0,00% 2189 0,00% 2189

50 10 20 9 1224 0,0% 1240 1,31% 1246 1,80% 1273 4,00% 1232 0,65% 1224

50 10 40 0 1757 0,0% 1757 0,00% 1757 0,00% 1757 0,00% 1757 0,00% 1757

50 10 40 1 1811 0,0% 1811 0,00% 1811 0,00% 1811 0,00% 1811 0,00% 1811

50 10 40 2 1704 0,4% 1698 0,00% 1709 0,65% 1709 0,65% 1698 0,00% 1698

50 10 40 3 1526 1,1% 1509 0,00% 1509 0,00% 1534 1,66% 1509 0,00% 1509

50 10 40 4 1542 0,9% 1529 0,00% 1529 0,00% 1529 0,00% 1529 0,00% 1529

50 10 40 5 1859 0,0% 1859 0,00% 1859 0,00% 1859 0,00% 1859 0,00% 1859

50 10 40 6 1687 0,9% 1677 0,30% 1676 0,24% 1672 0,00% 1676 0,24% 1672

50 10 40 7 1521 0,0% 1521 0,00% 1521 0,00% 1521 0,00% 1521 0,00% 1521

50 10 40 8 1663 0,4% 1657 0,00% 1657 0,00% 1657 0,00% 1657 0,00% 1657

50 10 40 9 2017 0,0% 2017 0,00% 2017 0,00% 2019 0,10% 2017 0,00% 2017

50 10 60 0 1309 0,0% 1309 0,00% 1309 0,00% 1309 0,00% 1309 0,00% 1309

50 10 60 1 834 1,1% 825 0,00% 829 0,48% 834 1,09% 825 0,00% 825

50 10 60 2 1547 0,0% 1547 0,00% 1547 0,00% 1547 0,00% 1547 0,00% 1547

50 10 60 3 1547 0,0% 1547 0,00% 1547 0,00% 1547 0,00% 1547 0,00% 1547

50 10 60 4 1250 0,0% 1250 0,00% 1250 0,00% 1250 0,00% 1250 0,00% 1250

50 10 60 5 1083 0,0% 1083 0,00% 1083 0,00% 1083 0,00% 1083 0,00% 1083

50 10 60 6 1088 0,0% 1088 0,00% 1088 0,00% 1088 0,00% 1088 0,00% 1088

50 10 60 7 1338 0,0% 1341 0,22% 1338 0,00% 1338 0,00% 1338 0,00% 1338

50 10 60 8 1189 0,0% 1189 0,00% 1189 0,00% 1189 0,00% 1189 0,00% 1189

50 10 60 9 1249 0,0% 1249 0,00% 1249 0,00% 1249 0,00% 1249 0,00% 1249

78


1

INERCAMBIO

10

MENOR

50 20 0 0 3178 0,9% 3214 2,06% 3187 1,21% 3149 0,00% 3160 0,35% 3149

50 20 0 1 3420 0,6% 3447 1,44% 3437 1,15% 3461 1,85% 3398 0,00% 3398

50 20 0 2 3427 0,0% 3469 1,23% 3427 0,00% 3455 0,82% 3499 2,10% 3427

50 20 0 3 3544 0,1% 3615 2,09% 3663 3,45% 3541 0,00% 3659 3,33% 3541

50 20 0 4 3462 1,4% 3472 1,67% 3496 2,37% 3415 0,00% 3517 2,99% 3415

50 20 0 5 3463 2,4% 3382 0,00% 3464 2,42% 3405 0,68% 3460 2,31% 3382

50 20 0 6 3293 2,3% 3301 2,55% 3333 3,54% 3219 0,00% 3354 4,19% 3219

50 20 0 7 3578 1,0% 3543 0,00% 3589 1,30% 3641 2,77% 3573 0,85% 3543

50 20 0 8 3378 1,5% 3327 0,00% 3393 1,98% 3373 1,38% 3370 1,29% 3327

50 20 0 9 3140 0,0% 3169 0,92% 3230 2,87% 3320 5,73% 3201 1,94% 3140

50 20 20 0 2779 1,2% 2821 2,69% 2782 1,27% 2834 3,17% 2747 0,00% 2747

50 20 20 1 2879 0,0% 2896 0,59% 2879 0,00% 2879 0,00% 2879 0,00% 2879

50 20 20 2 2867 0,0% 2904 1,29% 2922 1,92% 2867 0,00% 2882 0,52% 2867

50 20 20 3 2679 0,0% 2710 1,16% 2799 4,48% 2689 0,37% 2697 0,67% 2679

50 20 20 4 2779 0,0% 2779 0,00% 2779 0,00% 2779 0,00% 2779 0,00% 2779

50 20 20 5 2998 2,7% 3126 7,13% 2918 0,00% 3025 3,67% 2929 0,38% 2918

50 20 20 6 2633 3,0% 2558 0,04% 2577 0,78% 2590 1,29% 2557 0,00% 2557

50 20 20 7 2858 0,1% 2854 0,00% 2895 1,44% 2991 4,80% 2868 0,49% 2854

50 20 20 8 2766 0,0% 2841 2,71% 2802 1,30% 2830 2,31% 2883 4,23% 2766

50 20 20 9 2740 0,0% 2764 0,88% 2781 1,50% 2755 0,55% 2740 0,00% 2740

50 20 40 0 2063 1,5% 2052 0,98% 2055 1,13% 2032 0,00% 2063 1,53% 2032

50 20 40 1 2359 2,7% 2377 3,48% 2350 2,31% 2367 3,05% 2297 0,00% 2297

50 20 40 2 1907 0,2% 1907 0,21% 1903 0,00% 1903 0,00% 1906 0,16% 1903

50 20 40 3 2231 0,0% 2240 0,40% 2233 0,09% 2243 0,54% 2233 0,09% 2231

50 20 40 4 2202 0,0% 2255 2,41% 2229 1,23% 2229 1,23% 2229 1,23% 2202

50 20 40 5 2445 1,2% 2489 3,02% 2445 1,20% 2416 0,00% 2445 1,20% 2416

50 20 40 6 1711 0,3% 1706 0,00% 1734 1,64% 1736 1,76% 1710 0,23% 1706

50 20 40 7 2142 2,4% 2140 2,34% 2107 0,77% 2091 0,00% 2101 0,48% 2091

50 20 40 8 2356 0,0% 2356 0,00% 2356 0,00% 2356 0,00% 2356 0,00% 2356

50 20 40 9 1957 2,4% 1951 2,04% 1957 2,35% 1912 0,00% 1931 0,99% 1912

50 20 60 0 1621 0,0% 1630 0,56% 1621 0,00% 1621 0,00% 1621 0,00% 1621

50 20 60 1 1529 0,0% 1557 1,83% 1543 0,92% 1536 0,46% 1538 0,59% 1529

50 20 60 2 1395 0,0% 1457 4,44% 1440 3,23% 1457 4,44% 1440 3,23% 1395

50 20 60 3 1524 0,0% 1524 0,00% 1524 0,00% 1524 0,00% 1524 0,00% 1524

50 20 60 4 1338 0,0% 1338 0,00% 1338 0,00% 1338 0,00% 1338 0,00% 1338

50 20 60 5 1399 1,5% 1394 1,16% 1378 0,00% 1385 0,51% 1379 0,07% 1378

50 20 60 6 1194 0,0% 1201 0,59% 1207 1,09% 1194 0,00% 1201 0,59% 1194

50 20 60 7 1528 0,0% 1528 0,00% 1528 0,00% 1528 0,00% 1528 0,00% 1528

50 20 60 8 1099 0,0% 1099 0,00% 1099 0,00% 1099 0,00% 1099 0,00% 1099

50 20 60 9 1218 0,3% 1214 0,00% 1218 0,33% 1214 0,00% 1218 0,33% 1214

79


1

INERCAMBIO

10

MENOR

100 5 0 0 4478 0,0% 4478 0,00% 4546 1,52% 4478 0,00% 4512 0,76% 4478

100 5 0 1 5275 0,0% 5290 0,28% 5297 0,42% 5275 0,00% 5332 1,08% 5275

100 5 0 2 5094 0,0% 5094 0,00% 5116 0,43% 5094 0,00% 5105 0,22% 5094

100 5 0 3 2775 0,0% 2793 0,65% 2833 2,09% 2783 0,29% 2803 1,01% 2775

100 5 0 4 5090 0,0% 5097 0,14% 5200 2,16% 5100 0,20% 5284 3,81% 5090

100 5 0 5 4913 0,0% 4911 0,00% 5140 4,66% 4922 0,22% 5032 2,46% 4911

100 5 0 6 2518 0,0% 2517 0,00% 2578 2,42% 2519 0,08% 2570 2,11% 2517

100 5 0 7 4952 0,0% 4952 0,00% 4968 0,32% 4952 0,00% 4952 0,00% 4952

100 5 0 8 4894 0,2% 4882 0,00% 4894 0,25% 4882 0,00% 4894 0,25% 4882

100 5 0 9 5080 0,0% 5085 0,10% 5105 0,49% 5080 0,00% 5132 1,02% 5080

100 5 20 0 3949 0,0% 3949 0,00% 3949 0,00% 3949 0,00% 3949 0,00% 3949

100 5 20 1 3733 0,0% 3733 0,00% 3733 0,00% 3733 0,00% 3733 0,00% 3733

100 5 20 2 1955 0,5% 1951 0,26% 1974 1,44% 1946 0,00% 1982 1,85% 1946

100 5 20 3 3882 0,5% 3861 0,00% 3861 0,00% 3861 0,00% 3896 0,91% 3861

100 5 20 4 4091 0,0% 4091 0,00% 4091 0,00% 4091 0,00% 4091 0,00% 4091

100 5 20 5 1932 0,0% 1932 0,00% 1942 0,52% 1932 0,00% 1964 1,66% 1932

100 5 20 6 2184 0,0% 2184 0,00% 2191 0,32% 2184 0,00% 2184 0,00% 2184

100 5 20 7 4145 0,0% 4145 0,00% 4145 0,00% 4145 0,00% 4145 0,00% 4145

100 5 20 8 4236 0,0% 4236 0,00% 4262 0,61% 4236 0,00% 4244 0,19% 4236

100 5 20 9 4097 0,0% 4097 0,00% 4097 0,00% 4097 0,00% 4097 0,00% 4097

100 5 40 0 2734 0,0% 2734 0,00% 2751 0,62% 2734 0,00% 2744 0,37% 2734

100 5 40 1 2780 0,0% 2780 0,00% 2780 0,00% 2780 0,00% 2780 0,00% 2780

100 5 40 2 3014 0,1% 3011 0,00% 3011 0,00% 3011 0,00% 3014 0,10% 3011

100 5 40 3 3204 0,0% 3204 0,00% 3204 0,00% 3204 0,00% 3204 0,00% 3204

100 5 40 4 1299 3,1% 1260 0,00% 1320 4,76% 1273 1,03% 1335 5,95% 1260

100 5 40 5 3091 0,8% 3066 0,00% 3074 0,26% 3066 0,00% 3077 0,36% 3066

100 5 40 6 1500 2,1% 1469 0,00% 1539 4,77% 1479 0,68% 1540 4,83% 1469

100 5 40 7 1855 0,0% 1855 0,00% 1855 0,00% 1855 0,00% 1855 0,00% 1855

100 5 40 8 2787 0,0% 2787 0,00% 2791 0,14% 2791 0,14% 2796 0,32% 2787

100 5 40 9 3555 0,0% 3555 0,00% 3555 0,00% 3555 0,00% 3555 0,00% 3555

100 5 60 0 1884 0,0% 1884 0,00% 1884 0,00% 1884 0,00% 1884 0,00% 1884

100 5 60 1 2031 0,0% 2031 0,00% 2031 0,00% 2031 0,00% 2031 0,00% 2031

100 5 60 2 2158 0,0% 2158 0,00% 2158 0,00% 2158 0,00% 2158 0,00% 2158

100 5 60 3 840 0,0% 840 0,00% 842 0,24% 840 0,00% 852 1,43% 840

100 5 60 4 2144 0,0% 2144 0,00% 2144 0,00% 2144 0,00% 2144 0,00% 2144

100 5 60 5 1143 0,0% 1143 0,00% 1143 0,00% 1143 0,00% 1143 0,00% 1143

100 5 60 6 2514 0,0% 2514 0,00% 2514 0,00% 2514 0,00% 2514 0,00% 2514

100 5 60 7 1953 0,0% 1953 0,00% 1953 0,00% 1953 0,00% 1953 0,00% 1953

100 5 60 8 2227 0,0% 2227 0,00% 2227 0,00% 2227 0,00% 2227 0,00% 2227

100 5 60 9 1566 0,0% 1566 0,00% 1566 0,00% 1566 0,00% 1566 0,00% 1566

80


1

INERCAMBIO

10

MENOR

100 10 0 0 5182 0,0% 5216 0,66% 5424 4,67% 5245 1,22% 5474 5,63% 5182

100 10 0 1 5604 0,2% 5598 0,09% 5793 3,58% 5593 0,00% 5740 2,63% 5593

100 10 0 2 5749 0,0% 5778 0,50% 6228 8,33% 5772 0,40% 6136 6,73% 5749

100 10 0 3 5436 0,9% 5387 0,00% 5431 0,82% 5466 1,47% 5479 1,71% 5387

100 10 0 4 5053 0,0% 5161 2,14% 5426 7,38% 5066 0,26% 5304 4,97% 5053

100 10 0 5 5505 0,0% 5589 1,53% 5829 5,89% 5535 0,54% 5756 4,56% 5505

100 10 0 6 5173 0,0% 5214 0,79% 5376 3,92% 5173 0,00% 5278 2,03% 5173

100 10 0 7 5285 0,3% 5271 0,00% 5443 3,26% 5298 0,51% 5383 2,12% 5271

100 10 0 8 4908 0,0% 4915 0,14% 5017 2,22% 4936 0,57% 5000 1,87% 4908

100 10 0 9 5643 0,0% 5643 0,00% 5676 0,58% 5651 0,14% 5744 1,79% 5643

100 10 20 0 4107 0,1% 4117 0,39% 4164 1,54% 4101 0,00% 4183 2,00% 4101

100 10 20 1 3753 0,0% 3753 0,00% 3753 0,00% 3753 0,00% 3753 0,00% 3753

100 10 20 2 4035 0,2% 4028 0,00% 4060 0,79% 4035 0,17% 4055 0,67% 4028

100 10 20 3 4465 0,1% 4462 0,00% 4505 0,96% 4465 0,07% 4544 1,84% 4462

100 10 20 4 4558 0,4% 4542 0,00% 4747 4,51% 4552 0,22% 4740 4,36% 4542

100 10 20 5 4632 0,0% 4632 0,00% 4632 0,00% 4632 0,00% 4632 0,00% 4632

100 10 20 6 4356 0,0% 4356 0,00% 4372 0,37% 4372 0,37% 4372 0,37% 4356

100 10 20 7 3721 0,6% 3698 0,00% 3796 2,65% 3743 1,22% 3805 2,89% 3698

100 10 20 8 3965 0,2% 3956 0,00% 4063 2,70% 3956 0,00% 4089 3,36% 3956

100 10 20 9 4408 0,0% 4625 4,92% 4608 4,54% 4445 0,84% 4646 5,40% 4408

100 10 40 0 3581 0,0% 3581 0,00% 3600 0,53% 3581 0,00% 3600 0,53% 3581

100 10 40 1 3415 0,0% 3415 0,00% 3417 0,06% 3415 0,00% 3415 0,00% 3415

100 10 40 2 3442 0,3% 3433 0,00% 3459 0,76% 3442 0,26% 3516 2,42% 3433

100 10 40 3 3237 0,0% 3237 0,00% 3283 1,42% 3237 0,00% 3268 0,96% 3237

100 10 40 4 3195 1,5% 3147 0,00% 3214 2,13% 3147 0,00% 3251 3,30% 3147

100 10 40 5 3014 0,0% 3014 0,00% 3154 4,64% 3014 0,00% 3073 1,96% 3014

100 10 40 6 1622 0,1% 1621 0,00% 1649 1,73% 1621 0,00% 1652 1,91% 1621

100 10 40 7 3166 0,0% 3166 0,00% 3208 1,33% 3167 0,03% 3189 0,73% 3166

100 10 40 8 3320 0,0% 3320 0,00% 3320 0,00% 3320 0,00% 3320 0,00% 3320

100 10 40 9 1120 0,0% 1120 0,00% 1174 4,82% 1144 2,14% 1154 3,04% 1120

100 10 60 0 2321 0,0% 2321 0,00% 2352 1,34% 2321 0,00% 2343 0,95% 2321

100 10 60 1 2144 0,3% 2137 0,00% 2141 0,19% 2137 0,00% 2138 0,05% 2137

100 10 60 2 2099 0,0% 2099 0,00% 2099 0,00% 2099 0,00% 2099 0,00% 2099

100 10 60 3 2000 0,0% 2000 0,00% 2042 2,10% 2000 0,00% 2000 0,00% 2000

100 10 60 4 2386 0,0% 2387 0,04% 2387 0,04% 2386 0,00% 2422 1,51% 2386

100 10 60 5 2792 0,0% 2792 0,00% 2792 0,00% 2792 0,00% 2792 0,00% 2792

100 10 60 6 2387 0,0% 2386 0,00% 2407 0,88% 2386 0,00% 2401 0,63% 2386

100 10 60 7 2623 0,2% 2617 0,00% 2623 0,23% 2623 0,23% 2724 4,09% 2617

100 10 60 8 2377 0,0% 2377 0,00% 2377 0,00% 2377 0,00% 2377 0,00% 2377

100 10 60 9 2479 0,0% 2479 0,00% 2521 1,69% 2479 0,00% 2498 0,77% 2479

81


1

INERCAMBIO

10

MENOR

100 20 0 0 6115 0,0% 6189 1,21% 6315 3,27% 6147 0,52% 6421 5,00% 6115

100 20 0 1 6164 0,0% 6223 0,96% 6611 7,25% 6232 1,10% 6567 6,54% 6164

100 20 0 2 5981 0,0% 6149 2,81% 6285 5,08% 6054 1,22% 6388 6,80% 5981

100 20 0 3 6221 1,1% 6155 0,00% 6363 3,38% 6165 0,16% 6303 2,40% 6155

100 20 0 4 6081 0,0% 6099 0,35% 6368 4,77% 6078 0,00% 6451 6,14% 6078

100 20 0 5 6207 0,0% 6497 4,67% 6660 7,30% 6381 2,80% 6702 7,97% 6207

100 20 0 6 5202 0,0% 5235 0,63% 5307 2,02% 5216 0,27% 5331 2,48% 5202

100 20 0 7 6057 0,0% 6146 1,47% 6369 5,15% 6186 2,13% 6407 5,78% 6057

100 20 0 8 6467 0,0% 6467 0,00% 6583 1,79% 6493 0,40% 6650 2,83% 6467

100 20 0 9 6112 0,5% 6120 0,62% 6350 4,41% 6082 0,00% 6298 3,55% 6082

100 20 20 0 5280 1,4% 5208 0,00% 5383 3,36% 5222 0,27% 5394 3,57% 5208

100 20 20 1 4864 0,0% 4940 1,56% 5133 5,53% 4878 0,29% 5131 5,49% 4864

100 20 20 2 4904 0,2% 4893 0,00% 5045 3,11% 4926 0,67% 5006 2,31% 4893

100 20 20 3 4481 0,2% 4512 0,92% 4560 1,99% 4471 0,00% 4575 2,33% 4471

100 20 20 4 4675 0,0% 4740 1,39% 4788 2,42% 4694 0,41% 4866 4,09% 4675

100 20 20 5 4552 0,0% 4721 3,71% 4891 7,45% 4693 3,10% 4778 4,96% 4552

100 20 20 6 4664 0,0% 4710 0,99% 4936 5,83% 4708 0,94% 4837 3,71% 4664

100 20 20 7 4863 0,0% 4983 2,47% 5073 4,32% 5025 3,33% 5107 5,02% 4863

100 20 20 8 4859 0,0% 5061 4,16% 5139 5,76% 4960 2,08% 5076 4,47% 4859

100 20 20 9 4374 1,0% 4399 1,62% 4529 4,62% 4329 0,00% 4478 3,44% 4329

100 20 40 0 3899 0,0% 3899 0,00% 3983 2,15% 3899 0,00% 3961 1,59% 3899

100 20 40 1 3678 0,1% 3679 0,11% 3754 2,15% 3675 0,00% 3679 0,11% 3675

100 20 40 2 4135 1,8% 4063 0,00% 4187 3,05% 4126 1,55% 4193 3,20% 4063

100 20 40 3 3826 0,9% 3792 0,00% 3792 0,00% 3807 0,40% 3896 2,74% 3792

100 20 40 4 3781 0,5% 3778 0,37% 3869 2,79% 3764 0,00% 3925 4,28% 3764

100 20 40 5 3590 0,0% 3685 2,65% 3835 6,82% 3688 2,73% 3863 7,60% 3590

100 20 40 6 3676 0,0% 3676 0,00% 3759 2,26% 3676 0,00% 3695 0,52% 3676

100 20 40 7 3674 0,0% 3716 1,14% 3757 2,26% 3674 0,00% 3701 0,73% 3674

100 20 40 8 3612 0,4% 3599 0,00% 3691 2,56% 3599 0,00% 3739 3,89% 3599

100 20 40 9 3797 0,0% 3822 0,66% 3993 5,16% 3804 0,18% 3903 2,79% 3797

100 20 60 0 2641 0,0% 2641 0,00% 2641 0,00% 2641 0,00% 2641 0,00% 2641

100 20 60 1 2514 0,0% 2521 0,28% 2535 0,84% 2521 0,28% 2533 0,76% 2514

100 20 60 2 2614 1,2% 2582 0,00% 2760 6,89% 2660 3,02% 2697 4,45% 2582

100 20 60 3 2366 0,0% 2406 1,69% 2426 2,54% 2465 4,18% 2501 5,71% 2366

100 20 60 4 2506 0,0% 2513 0,28% 2572 2,63% 2514 0,32% 2517 0,44% 2506

100 20 60 5 2393 3,4% 2385 3,07% 2409 4,11% 2314 0,00% 2482 7,26% 2314

100 20 60 6 2855 1,6% 2811 0,00% 2879 2,42% 2812 0,04% 2840 1,03% 2811

100 20 60 7 2848 0,0% 2848 0,00% 2848 0,00% 2848 0,00% 2848 0,00% 2848

100 20 60 8 2756 0,4% 2768 0,80% 2783 1,35% 2746 0,00% 2773 0,98% 2746

100 20 60 9 3097 0,0% 3097 0,00% 3097 0,00% 3097 0,00% 3097 0,00% 3097

82

9.2 Anexo B: Códigos en C

9.2.1 Código metodo I: “Normal”

#include<stdio.h>

#include<stdlib.h>

#include<time.h>

#include<string>

#define M 10000

#define pc 80

#define pm 20

#define numpadres 10

#define numiteraciones 100000

#define numnomejoras 100000

int resolver(int numjobs,int numS,int maxmaq,int secuencia[100],int L[100], int tproceso[100][100]);

void transponerM (int numjobs, int numS,int tproceso[100][100]);

void ordenar2V(int tam,int v1[],int v2[]);

int buscarmayorv(int tamv ,int v[]);

int buscarmenor(int fila, int tamfila ,int matriz[100][100]);

int buscarmayorMatriz(int numS,int numjobs ,int v[100][100]);

void ordenarVsegunM(int tam,int fila, int Q[100][100],int tproceso[100][100], int v[]);

void creamatrizpadres(int numjobs,int matrizpadres[numpadres][100]);

void ordenpadre(int numjobs,int orden[numpadres]);

int crossover(int tam,int fila1,int fila2,int contposicion,int secuencias[numpadres*2][100]);

int mutacion(int tam,int fila,int contmutaciones, int secuencias[numpadres*4][100]);

int GA (int numjobs,int orden[],int matrizpadres[numpadres][100],int secuencias[numpadres*4][100]);

int todo(int tacumulado,char frase[100]);

int main()

{

int vJ[3]={20,50,100};

int vS[3]={5,10,20};

int vM[4]={0,20,40,60};

int vI[10]={0,1,2,3,4,5,6,7,8,9};

int cJ,cS,cM,cI;

83

int tacumulado=0;

int t;

char barra[2]="_";

char problem[13]="_problem.txt";

char frase[100];

char s1[10];

for(cJ=0;cJ<3;cJ++)

{

for(cS=0;cS<3;cS++)

{

for(cM=0;cM<4;cM++)

{

for(cI=0;cI<10;cI++)

{

memset (frase,'\0',100);

itoa(vJ[cJ],s1,10);

strcat(frase, s1);

strcat(frase, barra);

itoa(vS[cS],s1,10);

strcat(frase, s1);


itoa(vM[cM],s1,10);

strcat(frase, s1);


itoa(vI[cI],s1,10);

strcat(frase, s1);

strcat(frase, problem);

printf("%s \n",frase);

t = todo(tacumulado,frase);

tacumulado=t;


}

}

}

84

}

printf("%d FIN\n",tacumulado);

system ("pause");

}

//--------------------------------------PROGRAMA PRINCIPAL----------------------------

void transponerM (int numjobs, int numS,int tproceso[100][100])

{

int auxM[100][100];

int i,j;

for(i=0;i<numjobs;i++)

{

for(j=0;j<numS;j++)

{

auxM[i][j]=tproceso[i][j];

}

}


{

for(j=0;j<numS;j++)

{

tproceso[j][i]=auxM[i][j];

}

}

}

void ordenar2V(int tam,int v1[],int v2[])

{

int i,j;

int sec,temp;

for (j=tam-1;j>0;j--)

{

for (i=0;i<j;i++)

{

85

if (v1[i] > v1[i+1])

{

temp = v1[i];

sec=v2[i];

v1[i] = v1[i+1];

v2[i]=v2[i+1];

v1[i+1] = temp;

v2[i+1]=sec;

}

}

}

}

int buscarmenor(int fila, int tamfila ,int matriz[100][100])/*Lo hace bien*/

{

int menor=10000;

int i,posicion;

for(i=0;i<tamfila;i++)

{

if(menor>matriz[fila][i])

{

menor=matriz[fila][i];

posicion=i;

}

}

return posicion;

}

int buscarmayorv(int tamv ,int v[])

{

int mayor=0;

int i;

for(i=0;i<tamv;i++)

86

{

if(mayor<v[i])

{

mayor=v[i];

}

}

return mayor;

}

int buscarmayorMatriz(int numS,int numjobs ,int v[100][100])

{

int mayor=0;

int i;

int fila=numS-1;


{

if(mayor<v[fila][i])

{

mayor=v[fila][i];

}

}

return mayor;

}

void ordenarVsegunM(int tam,int fila, int Q[100][100],int tproceso[100][100], int jobs[])

{

int a,b;

int i,j,l;

int posicion,aux;

if(fila>0)

{


{

for (i=0;i<j ;i++)

87

{

if (Q[fila-1][i] >= Q[fila-1][i+1])

{

a=Q[fila-1][i];

Q[fila-1][i]=Q[fila-1][i+1];

Q[fila-1][i+1]=a;

b=jobs[i];

jobs[i]=jobs[i+1];

jobs[i+1]=b;

}

}

}

}

for(i=tam-1;i>=0;i--)

{

if(tproceso[fila][jobs[i]]==0)

{

posicion=i;

aux=jobs[i];

for(j=posicion;j>0;j--)

{

jobs[j]=jobs[j-1];

}

jobs[0]=aux;

}

}

}

int resolver(int numjobs,int numS,int maxmaq,int secuencia[100],int L[100], int tproceso[100][100])

{

int j,k,l,i;

int maq;

int jobs[numjobs];

88

int aux[100][100];

int aux1;

int posicion;

int makespan;

int t[100][100];

int Q[100][100];

for(k=0;k<numS;k++)

{

for(j=0;j<maxmaq;j++)

{

if(j<L[k])

{

t[k][j]=0;

}

else

{

t[k][j]=M;

}

}

}

for(k=0;k<numS;k++)

{

for(j=0;j<numjobs;j++)

{

Q[k][j]=0;

}

}


{

jobs[i]=secuencia[i];

}

89

for(k=0;k<numS;k++)

{

for(i=0;i<numS;i++)

{

for(l=0;l<numjobs;l++)

{

aux[i][l]=Q[i][l];

}

}

if(k!=0)

{


{

jobs[i]=i;

}

}

ordenarVsegunM(numjobs,k,aux,tproceso,jobs);

for (j=0;j<numjobs;j++)

{

maq = buscarmenor(k,maxmaq,t);

if(tproceso[k][jobs[j]]>0)

{

if(k==0)

{

t[k][maq]=t[k][maq]+tproceso[k][jobs[j]];

}

else

{

if(t[k][maq]>Q[k-1][jobs[j]])

{


}

90

else

{

t[k][maq]=Q[k-1][jobs[j]]+tproceso[k][jobs[j]];

}

}

}

if(k==0)

{

if(tproceso[k][jobs[j]]==0)

{

Q[k][jobs[j]]=Q[0][jobs[j]];

}

else

{

Q[k][jobs[j]]=t[k][maq];

}

}

else

{


{

Q[k][jobs[j]]=Q[k-1][jobs[j]];

}

else

{


}

}

}

}

makespan=buscarmayorMatriz(numS,numjobs,Q);

return makespan;

}

void creamatrizpadres(int numjobs,int matrizpadres[numpadres][100])

91

{

int i,j,k;

int num;

int repite=0;

for(i=0;i<numpadres;i++)

{


{

num = rand()% (numjobs) + 0;

repite=0;

for(k=0;k<j;k++)

{

if(matrizpadres[i][k]==num)

{

repite=1;

}

}

if(repite==0)

{

matrizpadres[i][j]=num;

}

if(repite==1)

{

j=j-1;

}

}

}

}

void ordenpadre(int numjobs,int orden[numpadres])

{

int num;

int k,j;

int repite;

92

for(j=0;j<numpadres;j++)

{

num = rand()% (numpadres) + 0;

repite=0;

for(k=0;k<j;k++)

{

if(orden[k]==num)

{

repite=1;

}

}

if(repite==0)

{

orden[j]=num;

}

if(repite==1)

{

j=j-1;

}

}

}

int crossover(int tam,int fila1,int fila2,int contposicion,int secuencias[numpadres*2][100])

{

int i,j,aux;

int P1,P2;

int posicion;

int esta;

int a;

int aux1[100];

int aux2[100];

a=rand()% 101 + 0;

93

if(a<=pc)

{

P1=rand()% (tam) + 0;

P2=rand()% (tam) + 0;

if(P1>P2)

{

aux=P1;

P1=P2;

P2=aux;

}

for(i=0;i<P1;i++)

{

aux1[i]=secuencias[fila1][i];

}

for(i=P2;i<tam;i++)

{


}

for(i=P1;i<P2;i++)

{

aux1[i]=-1;

}

posicion=P1;

esta=0;

for(i=0;i<tam;i++)

{

for(j=0;j<tam;j++)

{

if(secuencias[fila2][i]==aux1[j])

{

esta=1;

94

}

}

if(esta==0)

{

aux1[posicion]=secuencias[fila2][i];

posicion++;

}

esta=0;

}

P1=rand()% (tam) + 0;

P2=rand()% (tam) + 0;

if(P1>P2)

{

aux=P1;

P1=P2;

P2=aux;

}

for(i=0;i<P1;i++)

{


}

for(i=P2;i<tam;i++)

{


}

for(i=P1;i<P2;i++)

{

aux2[i]=-1;

}

posicion=P1;

95

esta=0;

for(i=0;i<tam;i++)

{

for(j=0;j<tam;j++)

{


{

esta=1;

}

}

if(esta==0)

{


posicion++;

}

esta=0;

}

for(i=0;i<tam;i++)

{

secuencias[numpadres+contposicion][i]=aux1[i];

}

contposicion++;

for(i=0;i<tam;i++)

{


}

contposicion++;

}

return contposicion;

}

int mutacion(int tam,int fila,int contmutaciones,int secuencias[numpadres][100])

{

int i;

96

int a,b;

int c;

int muta=0;

c=rand()% 101 + 0;

if(c<=pm)

{

muta=1;

a=rand()% (tam) + 0;

b=rand()% (tam) + 0;

for(i=0;i<tam;i++)

{

secuencias[numpadres+contmutaciones][i]=secuencias[fila][i];

}

secuencias[numpadres+contmutaciones][a]=secuencias[fila][b];

secuencias[numpadres+contmutaciones][b]=secuencias[fila][a];

}

return muta;

}

int GA(int numjobs,int orden[],int matrizpadres[numpadres][100],int secuencias[numpadres*4][100])

{

int i,j;

int fila1,fila2;


{


{

secuencias[i][j]=matrizpadres[orden[i]][j];

}

}

97

int contposicion=0;

for(i=0;i<numpadres;i=i+2)

{

fila1=i;

fila2=i+1;

contposicion=crossover(numjobs,fila1,fila2,contposicion,secuencias);

}

int contmutaciones=contposicion;

int muta=0;


{

muta=mutacion(numjobs,j,contmutaciones,secuencias);

contmutaciones=contmutaciones+muta;

}

return contmutaciones;

}

int todo(int tacumulado,char frase[100])

{

int numjobs;

int numS;

int tproceso[100][100];

int jobs[100];

int L[100];

int k,j,l,i;

int aux;

int secuencia[100];

int makespan;

int makespans[numpadres*4];

int matrizpadres[numpadres][100];

int orden[numpadres];

int secuencias[numpadres*4][100];

int posiciones[numpadres*4];

98

int salida=0;

/*LECTURA DE DATOS DEL PROBLEMA*/

FILE *datos=NULL;

datos=fopen(frase,"r");

if(datos==NULL)

printf("el fichero no existe");

fscanf(datos,"%d",&numjobs);

fscanf(datos,"%d",&numS);

for(i=0;i<numS;i++)

{

fscanf(datos,"%d",&L[i]);

}


{

for(j=0;j<numS;j++)

{

fscanf(datos,"%d",&tproceso[i][j]);

}

}

fclose(datos);

transponerM(numjobs,numS,tproceso);

int maxmaq;

maxmaq=buscarmayorv(numS,L);

/*FIN DATOS*/

int bestmakespan=M;

clock_t tiempo;

tiempo=clock();

99

double tmax=(double)(numjobs*numS)/(double)(10);

clock_t tiempoFinal=clock();

double tiempoTranscurrido=(double)(tiempoFinal-tiempo)/CLOCKS_PER_SEC;

int tam;

int contmutaciones=0;

creamatrizpadres(numjobs,matrizpadres);

for(k=0;k<numiteraciones && salida<numnomejoras && tiempoTranscurrido<tmax;k++)

{


{

orden[i]=0;

}

ordenpadre(numjobs,orden);

contmutaciones=GA(numjobs,orden,matrizpadres,secuencias);

tam=numpadres+contmutaciones;

for(i=0;i<tam;i++)

{


{

secuencia[j]=secuencias[i][j];

}

makespan=resolver(numjobs,numS,maxmaq,secuencia,L,tproceso);

makespans[i]=makespan;

}

for(i=0;i<tam;i++)

{

posiciones[i]=i;

}

100

ordenar2V(tam,makespans,posiciones);


{


{

matrizpadres[i][j]=secuencias[posiciones[i]][j];

}

}

if(makespans[0]<bestmakespan)

{

bestmakespan=makespans[0];

salida=0;

}

else

{

salida=salida+1;

}

tiempoFinal=clock();

tiempoTranscurrido=(double)(tiempoFinal-tiempo)/CLOCKS_PER_SEC;

printf("Iteracion %d:\n ",k);


{


{

printf("%d ",matrizpadres[i][j]);

}

printf(" :%d\n ",makespans[i]);

}

printf("\n");

}

FILE *resultados;

resultados= fopen("ResultadosNormal.txt","a");

fprintf(resultados, "%d\n", makespans[0]);

101

fclose(resultados);

return tmax;

}

9.2.2 Código metodo II: “Inserción1”

#include<stdio.h>

#include<stdlib.h>

#include<time.h>

#include<string>

#define M 10000

#define pc 80

#define pm 20
















int buscarNenM(int fila,int N,int numjobs,int matrizpadres[numpadres][100]);

void insercion (int tam,int secuencia[],int posinicio, int posfinal);

void mejoralocalinsercion (int fila,int numjobs,int makespans[100],int matrizpadres[100][100], int numS,int

maxmaq,int L[100], int tproceso[100][100]);


102

int main()

{

int vJ[3]={20,50,100};

int vS[3]={5,10,20};

int vM[4]={0,20,40,60};

int vI[10]={0,1,2,3,4,5,6,7,8,9};

int cJ,cS,cM,cI;

int tacumulado=0;

int t;

char barra[2]="_";


char s1[10];

char frase[100];

for(cJ=0;cJ<3;cJ++)

{

for(cS=0;cS<3;cS++)

{

for(cM=0;cM<4;cM++)

{


{


itoa(vJ[cJ],s1,10);

strcat(frase, s1);


itoa(vS[cS],s1,10);

strcat(frase, s1);


itoa(vM[cM],s1,10);

strcat(frase, s1);


itoa(vI[cI],s1,10);

strcat(frase, s1);


103



tacumulado=t;


}

}

}

}


system ("pause");

}



{

int auxM[100][100];

int i,j;


{

for(j=0;j<numS;j++)

{


}

}


{

for(j=0;j<numS;j++)

{


}

}

}


104

{

int i,j;

int sec,temp;


{

for (i=0;i<j;i++)

{

if (v1[i] > v1[i+1])

{

temp = v1[i];

sec=v2[i];

v1[i] = v1[i+1];

v2[i]=v2[i+1];

v1[i+1] = temp;

v2[i+1]=sec;

}

}

}

}


{

int menor=10000;

int i,posicion;


{


{


posicion=i;

}

}

return posicion;

}

105


{

int mayor=0;

int i;

for(i=0;i<tamv;i++)

{

if(mayor<v[i])

{

mayor=v[i];

}

}

return mayor;

}


{

int mayor=0;

int i;

int fila=numS-1;


{


{

mayor=v[fila][i];

}

}

return mayor;

}


{

int a,b;

int i,j,l;

106

int posicion,aux;

if(fila>0)

{


{

for (i=0;i<j ;i++)

{


{

a=Q[fila-1][i];


Q[fila-1][i+1]=a;

b=jobs[i];

jobs[i]=jobs[i+1];

jobs[i+1]=b;

}

}

}

}


{


{

posicion=i;

aux=jobs[i];


{

jobs[j]=jobs[j-1];

}

jobs[0]=aux;

}

}

107

}


{

int j,k,l,i;

int maq;

int jobs[numjobs];

int aux[100][100];

int aux1;

int posicion;

int makespan;

int t[100][100];

int Q[100][100];

for(k=0;k<numS;k++)

{


{

if(j<L[k])

{

t[k][j]=0;

}

else

{

t[k][j]=M;

}

}

}

for(k=0;k<numS;k++)

{


{

Q[k][j]=0;

}

}

108


{


}

for(k=0;k<numS;k++)

{

for(i=0;i<numS;i++)

{


{

aux[i][l]=Q[i][l];

}

}

if(k!=0)

{


{

jobs[i]=i;

}

}



{



{

if(k==0)

{


}

else

109

{


{


}

else

{


}

}

}

if(k==0)

{


{


}

else

{


}

}

else

{


{


}

else

{


}

}

}

}


110

return makespan;

}


{

int i,j,k;

int num;

int repite=0;


{


{


repite=0;

for(k=0;k<j;k++)

{


{

repite=1;

}

}

if(repite==0)

{


}

if(repite==1)

{

j=j-1;

}

}

}

}


{

111

int num;

int k,j;

int repite;


{


repite=0;

for(k=0;k<j;k++)

{

if(orden[k]==num)

{

repite=1;

}

}

if(repite==0)

{

orden[j]=num;

}

if(repite==1)

{

j=j-1;

}

}

}


{

int i,j,aux;

int P1,P2;

int posicion;

int esta;

int a;

int aux1[100];

int aux2[100];

112

a=rand()% 101 + 0;

if(a<=pc)

{

P1=rand()% (tam) + 0;

P2=rand()% (tam) + 0;

if(P1>P2)

{

aux=P1;

P1=P2;

P2=aux;

}

for(i=0;i<P1;i++)

{


}

for(i=P2;i<tam;i++)

{


}

for(i=P1;i<P2;i++)

{

aux1[i]=-1;

}

posicion=P1;

esta=0;

for(i=0;i<tam;i++)

{

for(j=0;j<tam;j++)

{


{

esta=1;

}

}

113

if(esta==0)

{


posicion++;

}

esta=0;

}

P1=rand()% (tam) + 0;

P2=rand()% (tam) + 0;

if(P1>P2)

{

aux=P1;

P1=P2;

P2=aux;

}

for(i=0;i<P1;i++)

{


}

for(i=P2;i<tam;i++)

{


}

for(i=P1;i<P2;i++)

{

aux2[i]=-1;

}

posicion=P1;

esta=0;

for(i=0;i<tam;i++)

{

for(j=0;j<tam;j++)

114

{


{

esta=1;

}

}

if(esta==0)

{


posicion++;

}

esta=0;

}

for(i=0;i<tam;i++)

{


}

contposicion++;

for(i=0;i<tam;i++)

{


}

contposicion++;

}


}


{

int i;

int a,b;

int c;

int muta=0;

c=rand()% 101 + 0;

if(c<=pm)

115

{

muta=1;



for(i=0;i<tam;i++)

{


}



}

return muta;

}


{

int i,j;

int fila1,fila2;


{


{


}

}

int contposicion=0;


{

fila1=i;

fila2=i+1;


116

}


int muta=0;


{



}


}


{

int numjobs;

int numS;


int jobs[100];

int L[100];

int k,j,l,i;

int aux;

int secuencia[100];

int makespan;






int salida=0;


FILE *datos=NULL;


if(datos==NULL)


117



for(i=0;i<numS;i++)

{


}


{

for(j=0;j<numS;j++)

{


}

}

fclose(datos);


int maxmaq;


/*FIN DATOS*/

int bestmakespan=M;

clock_t tiempo;

tiempo=clock();




int tam;




{

118


{

orden[i]=0;

}




for(i=0;i<tam;i++)

{


{


}



}

for(i=0;i<tam;i++)

{

posiciones[i]=i;

}



{


{


}

}

int fila=0;

mejoralocalinsercion(fila,numjobs,makespans,matrizpadres,numS,maxmaq,L,tproceso);

119


{


salida=0;

}

else

{

salida=salida+1;

}





{


{


}


}

printf("\n");

}

FILE *resultados;

resultados= fopen("ResultadosInsercion1.txt","a");


fclose(resultados);

return tmax;

}

int buscarNenM(int fila ,int N ,int numjobs ,int matrizpadres[numpadres][100] )

{

int i;

int posicion;

120


{

if(matrizpadres[fila][i]==N)

{

posicion=i;

}

}

return posicion;

}

void insercion(int tam,int secuencia[],int posinicio, int posfinal)

{

int aux;

int k,i;

if(posinicio>posfinal)

{

aux=secuencia[posinicio];

for(k=posinicio;k>posfinal;k--)

{

secuencia[k]=secuencia[k-1];

}

secuencia[posfinal]=aux;

}

else

{


for(k=posinicio;k<posfinal;k++)

{

secuencia[k]=secuencia[k+1];

}


}

}

121


maxmaq,int L[100], int tproceso[100][100])

{

int posicion;

int i,j,k,l,a,b;

int job;

int makespanbest,makespannuevo;

int secuencia[numjobs];

int secuenciabest[numjobs];

int cambio;

int aux[100];

makespanbest=makespans[fila];

cambio=0;

for(job=0;job<numjobs;job++)

{

posicion=buscarNenM(fila,job,numjobs,matrizpadres);

for(k=0;k<numjobs;k++)

{

if(k!=posicion)

{


{

aux[i]=matrizpadres[fila][i];

}

insercion(numjobs,aux,posicion,k);


{

secuencia[i]=aux[i];

}

makespannuevo=resolver(numjobs,numS,maxmaq,secuencia,L,tproceso);

if(makespannuevo<makespanbest)

122

{


{

secuenciabest[i]=secuencia[i];

}

makespanbest=makespannuevo;

cambio=1;

}

}

}

}

if(cambio==1)

{

makespans[fila]=makespanbest;


{

matrizpadres[fila][i]=secuenciabest[i];

}

}

}

9.2.3 Código metodo III: “Inserción10”

#include<stdio.h>

#include<stdlib.h>

#include<time.h>

#include<string>

#define M 10000

#define pc 80 //entre 0 y 100 no entre 0 y 1

#define pm 20 //entre 0 y 100 no entre 0 y 1





123













void insercion (int tam,int secuencia[],int posinicio, int posfinal);

void mejoralocalinsercion (int fila,int numjobs,int makespans[100],int matrizpadres[100][100], int numS,int maxmaq,int L[100], int tproceso[100][100]);


int main()

{

int vJ[3]={20,50,100};

int vS[3]={5,10,20};

int vM[4]={0,20,40,60};

int vI[10]={0,1,2,3,4,5,6,7,8,9};

int cJ,cS,cM,cI;

int tacumulado=0;

int t;

char barra[2]="_";


char s1[10];

char frase[100];

for(cJ=0;cJ<3;cJ++)

{

for(cS=0;cS<3;cS++)

{

for(cM=0;cM<4;cM++)

{

124


{

srand (time(NULL));


itoa(vJ[cJ],s1,10);

strcat(frase, s1);


itoa(vS[cS],s1,10);

strcat(frase, s1);


itoa(vM[cM],s1,10);

strcat(frase, s1);


itoa(vI[cI],s1,10);

strcat(frase, s1);




tacumulado=t;


}

}

}

}


system ("pause");

}



{

int auxM[100][100];

int i,j;


125

{

for(j=0;j<numS;j++)

{


}

}


{

for(j=0;j<numS;j++)

{


}

}

}


{

int i,j;

int sec,temp;


{

for (i=0;i<j;i++)

{

if (v1[i] > v1[i+1])

{

temp = v1[i];

sec=v2[i];

v1[i] = v1[i+1];

v2[i]=v2[i+1];

v1[i+1] = temp;

v2[i+1]=sec;

}

}

}

}


126

{

int menor=10000;

int i,posicion;


{


{


posicion=i;

}

}

return posicion;

}


{

int mayor=0;

int i;

for(i=0;i<tamv;i++)

{

if(mayor<v[i])

{

mayor=v[i];

}

}

return mayor;

}


{

int mayor=0;

int i;

int fila=numS-1;


127

{


{

mayor=v[fila][i];

}

}

return mayor;

}


{

int a,b;

int i,j,l;

int posicion,aux;

if(fila>0)

{


{

for (i=0;i<j ;i++)

{


{

a=Q[fila-1][i];


Q[fila-1][i+1]=a;

b=jobs[i];

jobs[i]=jobs[i+1];

jobs[i+1]=b;

}

}

}

}


{


128

{

posicion=i;

aux=jobs[i];


{

jobs[j]=jobs[j-1];

}

jobs[0]=aux;

}

}

}


{

int j,k,l,i;

int maq;

int jobs[numjobs];

int aux[100][100];

int aux1;

int posicion;

int makespan;

int t[100][100];

int Q[100][100];

for(k=0;k<numS;k++)

{


{

if(j<L[k])

{

t[k][j]=0;

}

else

{

t[k][j]=M;

129

}

}

}

for(k=0;k<numS;k++)

{


{

Q[k][j]=0;

}

}


{


}

for(k=0;k<numS;k++)

{

for(i=0;i<numS;i++)

{


{

aux[i][l]=Q[i][l];

}

}

if(k!=0)

{


{

jobs[i]=i;

}

}



{


130


{

if(k==0)

{


}

else

{


{


}

else

{


}

}

}

if(k==0)

{


{


}

else

{


}

}

else

{


{


}

131

else

{


}

}

}

}


return makespan;

}


{

int i,j,k;

int num;

int repite=0;


{


{


repite=0;

for(k=0;k<j;k++)

{


{

repite=1;

}

}

if(repite==0)

{


}

if(repite==1)

132

{

j=j-1;

}

}

}

}


{

int num;

int k,j;

int repite;


{


repite=0;

for(k=0;k<j;k++)

{

if(orden[k]==num)

{

repite=1;

}

}

if(repite==0)

{

orden[j]=num;

}

if(repite==1)

{

j=j-1;

}

}

}


{

133

int i,j,aux;

int P1,P2;

int posicion;

int esta;

int a;

int aux1[100];

int aux2[100];

a=rand()% 101 + 0;

if(a<=pc)

{

P1=rand()% (tam) + 0;

P2=rand()% (tam) + 0;

if(P1>P2)

{

aux=P1;

P1=P2;

P2=aux;

}

for(i=0;i<P1;i++)

{


}

for(i=P2;i<tam;i++)

{


}

for(i=P1;i<P2;i++)

{

aux1[i]=-1;

}

posicion=P1;

esta=0;

134

for(i=0;i<tam;i++)

{

for(j=0;j<tam;j++)

{


{

esta=1;

}

}

if(esta==0)

{


posicion++;

}

esta=0;

}

P1=rand()% (tam) + 0;

P2=rand()% (tam) + 0;

if(P1>P2)

{

aux=P1;

P1=P2;

P2=aux;

}

for(i=0;i<P1;i++)

{


}

for(i=P2;i<tam;i++)

{


}

for(i=P1;i<P2;i++)

{

135

aux2[i]=-1;

}

posicion=P1;

esta=0;

for(i=0;i<tam;i++)

{

for(j=0;j<tam;j++)

{


{

esta=1;

}

}

if(esta==0)

{


posicion++;

}

esta=0;

}

for(i=0;i<tam;i++)

{


}

contposicion++;

for(i=0;i<tam;i++)

{


}

contposicion++;

}


}


{

136

int i;

int a,b;

int c;

int muta=0;

c=rand()% 101 + 0;

if(c<=pm)

{

muta=1;



for(i=0;i<tam;i++)

{


}



}

return muta;

}


{

int i,j;

int fila1,fila2;


{


{


}

}

int contposicion=0;


137

{

fila1=i;

fila2=i+1;


}


int muta=0;


{



}


}


{

int numjobs;

int numS;


int jobs[100];

int L[100];

int k,j,l,i;

int aux;

int secuencia[100];

int makespan;






int salida=0;

138


FILE *datos=NULL;


if(datos==NULL)




for(i=0;i<numS;i++)

{


}


{

for(j=0;j<numS;j++)

{


}

}

fclose(datos);


int maxmaq;


/*FIN DATOS*/

int bestmakespan=M;

clock_t tiempo;

tiempo=clock();




139

int tam;




{


{

orden[i]=0;

}




for(i=0;i<tam;i++)

{


{


}



}

for(i=0;i<tam;i++)

{

posiciones[i]=i;

}



{


{


}

}

int fila;

140

for(fila=0;fila<numpadres;fila++)

{

mejoralocalinsercion(fila,numjobs,makespans,matrizpadres,numS,maxmaq,L,tproceso);

}


{


salida=0;

}

else

{

salida=salida+1;

}





{


{


}


}

printf("\n");

}

FILE *resultados;

resultados= fopen("ResultadosInsercion10.txt","a");


fclose(resultados);

return tmax;

}


{

141

int i;

int posicion;


{


{

posicion=i;

}

}

return posicion;

}

void insercion(int tam,int secuencia[],int posinicio, int posfinal)

{

int aux;

int k,i;

if(posinicio>posfinal)

{


for(k=posinicio;k>posfinal;k--)

{

secuencia[k]=secuencia[k-1];

}


}

else

{


for(k=posinicio;k<posfinal;k++)

{

secuencia[k]=secuencia[k+1];

}


}

}

142



{

int posicion;

int i,j,k,l,a,b;

int job;

int makespanbest,makespannuevo;

int secuencia[numjobs];

int secuenciabest[numjobs];

int cambio;

int aux[100];


cambio=0;


{



{

if(k!=posicion)

{


{

aux[i]=matrizpadres[fila][i];

}

insercion(numjobs,aux,posicion,k);


{

secuencia[i]=aux[i];

}



{


{


143

}


cambio=1;

}

}

}

}

if(cambio==1)

{



{


}

}

}

9.2.4 Código metodo IV: “Intercambio1”

#include<stdio.h>

#include<stdlib.h>

#include<time.h>

#include<string>

#define M 10000

#define pc 80

#define pm 20




144














void intercambioAconB(int fila,int posicion1,int posicion2,int numjobs,int matrizpadres[numpadres][100]);

void mejoralocalintercambio (int fila,int numjobs,int makespans[100],int matrizpadres[100][100], int numS,int

maxmaq,int L[100], int tproceso[100][100]);


int main()

{

int vJ[3]={20,50,100};

int vS[3]={5,10,20};

int vM[4]={0,20,40,60};

int vI[10]={0,1,2,3,4,5,6,7,8,9};

int cJ,cS,cM,cI;

int tacumulado=0;

int t;

char barra[2]="_";


char s1[10];

char frase[100];

for(cJ=0;cJ<3;cJ++)

{

for(cS=0;cS<3;cS++)

{

for(cM=0;cM<4;cM++)

145

{


{


itoa(vJ[cJ],s1,10);

strcat(frase, s1);


itoa(vS[cS],s1,10);

strcat(frase, s1);


itoa(vM[cM],s1,10);

strcat(frase, s1);


itoa(vI[cI],s1,10);

strcat(frase, s1);




tacumulado=t;


}

}

}

}


system ("pause");

}



{

int auxM[100][100];

int i,j;


146

{

for(j=0;j<numS;j++)

{


}

}


{

for(j=0;j<numS;j++)

{


}

}

}


{

int i,j;

int sec,temp;


{

for (i=0;i<j;i++)

{

if (v1[i] > v1[i+1])

{

temp = v1[i];

sec=v2[i];

v1[i] = v1[i+1];

v2[i]=v2[i+1];

v1[i+1] = temp;

v2[i+1]=sec;

}

}

}

}

int buscarmenor(int fila, int tamfila ,int matriz[100][100])

147

{

int menor=10000;

int i,posicion;


{


{


posicion=i;

}

}

return posicion;

}


{

int mayor=0;

int i;

for(i=0;i<tamv;i++)

{

if(mayor<v[i])

{

mayor=v[i];

}

}

return mayor;

}


{

int mayor=0;

int i;

int fila=numS-1;


{

148


{

mayor=v[fila][i];

}

}

return mayor;

}


{

int a,b;

int i,j,l;

int posicion,aux;

if(fila>0)

{


{

for (i=0;i<j ;i++)

{


{

a=Q[fila-1][i];


Q[fila-1][i+1]=a;

b=jobs[i];

jobs[i]=jobs[i+1];

jobs[i+1]=b;

}

}

}

}


{


{

149

posicion=i;

aux=jobs[i];


{

jobs[j]=jobs[j-1];

}

jobs[0]=aux;

}

}

}


{

int j,k,l,i;

int maq;

int jobs[numjobs];

int aux[100][100];

int aux1;

int posicion;

int makespan;

int t[100][100];

int Q[100][100];

for(k=0;k<numS;k++)

{


{

if(j<L[k])

{

t[k][j]=0;

}

else

{

t[k][j]=M;

}

150

}

}

for(k=0;k<numS;k++)

{


{

Q[k][j]=0;

}

}


{


}

for(k=0;k<numS;k++)

{

for(i=0;i<numS;i++)

{


{

aux[i][l]=Q[i][l];

}

}

if(k!=0)

{


{

jobs[i]=i;

}

}



{

151



{

if(k==0)

{


}

else

{


{


}

else

{


}

}

}

if(k==0)

{


{


}

else

{


}

}

else

{


{


}

152

else

{


}

}

}

}


return makespan;

}


{

int i,j,k;

int num;

int repite=0;


{


{


repite=0;

for(k=0;k<j;k++)

{


{

repite=1;

}

}

if(repite==0)

{


}

if(repite==1)

{

153

j=j-1;

}

}

}

}


{

int num;

int k,j;

int repite;


{


repite=0;

for(k=0;k<j;k++)

{

if(orden[k]==num)

{

repite=1;

}

}

if(repite==0)

{

orden[j]=num;

}

if(repite==1)

{

j=j-1;

}

}

}


{

int i,j,aux;

154

int P1,P2;

int posicion;

int esta;

int a;

int aux1[100];

int aux2[100];

a=rand()% 101 + 0;

if(a<=pc)

{

P1=rand()% (tam) + 0;

P2=rand()% (tam) + 0;

if(P1>P2)

{

aux=P1;

P1=P2;

P2=aux;

}

for(i=0;i<P1;i++)

{


}

for(i=P2;i<tam;i++)

{


}

for(i=P1;i<P2;i++)

{

aux1[i]=-1;

}

posicion=P1;

esta=0;

155

for(i=0;i<tam;i++)

{

for(j=0;j<tam;j++)

{


{

esta=1;

}

}

if(esta==0)

{


posicion++;

}

esta=0;

}

P1=rand()% (tam) + 0;

P2=rand()% (tam) + 0;

if(P1>P2)

{

aux=P1;

P1=P2;

P2=aux;

}

for(i=0;i<P1;i++)

{


}

for(i=P2;i<tam;i++)

{


}

for(i=P1;i<P2;i++)

{

156

aux2[i]=-1;

}

posicion=P1;

esta=0;

for(i=0;i<tam;i++)

{

for(j=0;j<tam;j++)

{


{

esta=1;

}

}

if(esta==0)

{


posicion++;

}

esta=0;

}

for(i=0;i<tam;i++)

{


}

contposicion++;

for(i=0;i<tam;i++)

{


}

contposicion++;

}


}

157


{

int i;

int a,b;

int c;

int muta=0;

c=rand()% 101 + 0;

if(c<=pm)

{

muta=1;



for(i=0;i<tam;i++)

{


}



}

return muta;

}


{

int i,j;

int fila1,fila2;


{


{


}

}

158

int contposicion=0;


{

fila1=i;

fila2=i+1;


}


int muta=0;


{



}


}


{

int numjobs;

int numS;


int jobs[100];

int L[100];

int k,j,l,i;

int aux;

int secuencia[100];

int makespan;






int salida=0;

159


FILE *datos=NULL;


if(datos==NULL)




for(i=0;i<numS;i++)

{


}


{

for(j=0;j<numS;j++)

{


}

}

fclose(datos);


int maxmaq;


/*FIN DATOS*/

int bestmakespan=M;

clock_t tiempo;

tiempo=clock();




160

int tam;




{


{

orden[i]=0;

}




for(i=0;i<tam;i++)

{


{


}



}

for(i=0;i<tam;i++)

{

posiciones[i]=i;

}



{


{


161

}

}

int fila=0;

mejoralocalintercambio (fila,numjobs,makespans,matrizpadres,numS,maxmaq,L,tproceso);


{


salida=0;

}

else

{

salida=salida+1;

}





{


{


}


}

printf("\n");

}

FILE *resultados;

resultados= fopen("ResultadosInterccambio1.txt","a");


fclose(resultados);

return tmax;

}

162


{

int i;

int posicion;


{


{

posicion=i;

}

}

return posicion;

}

void intercambioAconB(int fila,int posicion1,int posicion2,int numjobs,int matrizpadres[numpadres][100])

{

int aux;

int k;

aux=matrizpadres[fila][posicion1];

matrizpadres[fila][posicion1]=matrizpadres[fila][posicion2];

matrizpadres[fila][posicion2]=aux;

}



{

int posicion;

int i,k;

int job;

int makespanbest;

int makespannuevo;

int secuencia[100];

int secuenciabest[100];

int cambio;


163

makespannuevo=makespans[fila];

cambio=0;


{



{

if(k!=posicion)

{

intercambioAconB(fila,posicion,k,numjobs,matrizpadres);


{

secuencia[i]=matrizpadres[fila][i];

}



{


{


}


cambio=1;

}

intercambioAconB(fila,k,posicion,numjobs,matrizpadres);

}

}

}

if(cambio==1)

{



{


}

164

}

}

9.2.5 Código metodo IV: “Intercambio10”

#include<stdio.h>

#include<stdlib.h>

#include<time.h>

#include<string>

#define M 10000

#define pc 80

#define pm 20

















void intercambioAconB(int fila,int posicion1,int posicion2,int numjobs,int matrizpadres[numpadres][100]);

void mejoralocalintercambio (int fila,int numjobs,int makespans[100],int matrizpadres[100][100], int numS,int maxmaq,int L[100], int tproceso[100][100]);


int main()

165

{

int vJ[3]={20,50,100};

int vS[3]={5,10,20};

int vM[4]={0,20,40,60};

int vI[10]={0,1,2,3,4,5,6,7,8,9};

int cJ,cS,cM,cI;

int tacumulado=0;

int t;

char barra[2]="_";


char s1[10];

char frase[100];

for(cJ=0;cJ<3;cJ++)

{

for(cS=0;cS<3;cS++)

{

for(cM=0;cM<4;cM++)

{


{


itoa(vJ[cJ],s1,10);

strcat(frase, s1);


itoa(vS[cS],s1,10);

strcat(frase, s1);


itoa(vM[cM],s1,10);

strcat(frase, s1);


itoa(vI[cI],s1,10);

strcat(frase, s1);




166

tacumulado=t;


}

}

}

}


system ("pause");

}



{

int auxM[100][100];

int i,j;


{

for(j=0;j<numS;j++)

{


}

}


{

for(j=0;j<numS;j++)

{


}

}

}


{

int i,j;

int sec,temp;


167

{

for (i=0;i<j;i++)

{

if (v1[i] > v1[i+1])

{

temp = v1[i];

sec=v2[i];

v1[i] = v1[i+1];

v2[i]=v2[i+1];

v1[i+1] = temp;

v2[i+1]=sec;

}

}

}

}

int buscarmenor(int fila, int tamfila ,int matriz[100][100])

{

int menor=10000;

int i,posicion;


{


{


posicion=i;

}

}

return posicion;

}


{

int mayor=0;

int i;

for(i=0;i<tamv;i++)

168

{

if(mayor<v[i])

{

mayor=v[i];

}

}

return mayor;

}


{

int mayor=0;

int i;

int fila=numS-1;


{


{

mayor=v[fila][i];

}

}

return mayor;

}


{

int a,b;

int i,j,l;

int posicion,aux;

if(fila>0)

{


{

for (i=0;i<j ;i++)

{


169

{

a=Q[fila-1][i];


Q[fila-1][i+1]=a;

b=jobs[i];

jobs[i]=jobs[i+1];

jobs[i+1]=b;

}

}

}

}


{


{

posicion=i;

aux=jobs[i];


{

jobs[j]=jobs[j-1];

}

jobs[0]=aux;

}

}

}


{

int j,k,l,i;

int maq;

int jobs[numjobs];

int aux[100][100];

int aux1;

int posicion;

170

int makespan;

int t[100][100];

int Q[100][100];

for(k=0;k<numS;k++)

{


{

if(j<L[k])

{

t[k][j]=0;

}

else

{

t[k][j]=M;

}

}

}

for(k=0;k<numS;k++)

{


{

Q[k][j]=0;

}

}


{


}

for(k=0;k<numS;k++)

{

for(i=0;i<numS;i++)

{


{

aux[i][l]=Q[i][l];

171

}

}

if(k!=0)

{


{

jobs[i]=i;

}

}



{



{

if(k==0)

{


}

else

{


{


}

else

{


}

}

}

if(k==0)

{


{

172


}

else

{


}

}

else

{


{


}

else

{


}

}

}

}


return makespan;

}


{

int i,j,k;

int num;

int repite=0;


{


{


repite=0;

173

for(k=0;k<j;k++)

{


{

repite=1;

}

}

if(repite==0)

{


}

if(repite==1)

{

j=j-1;

}

}

}

}


{

int num;

int k,j;

int repite;


{


repite=0;

for(k=0;k<j;k++)

{

if(orden[k]==num)

{

repite=1;

}

}

174

if(repite==0)

{

orden[j]=num;

}

if(repite==1)

{

j=j-1;

}

}

}


{

int i,j,aux;

int P1,P2;

int posicion;

int esta;

int a;

int aux1[100];

int aux2[100];

a=rand()% 101 + 0;

if(a<=pc)

{

P1=rand()% (tam) + 0;

P2=rand()% (tam) + 0;

if(P1>P2)

{

aux=P1;

P1=P2;

P2=aux;

}

for(i=0;i<P1;i++)

{


175

}

for(i=P2;i<tam;i++)

{


}

for(i=P1;i<P2;i++)

{

aux1[i]=-1;

}

posicion=P1;

esta=0;

for(i=0;i<tam;i++)

{

for(j=0;j<tam;j++)

{


{

esta=1;

}

}

if(esta==0)

{


posicion++;

}

esta=0;

}

P1=rand()% (tam) + 0;

P2=rand()% (tam) + 0;

if(P1>P2)

{

aux=P1;

P1=P2;

P2=aux;

176

}

for(i=0;i<P1;i++)

{


}

for(i=P2;i<tam;i++)

{


}

for(i=P1;i<P2;i++)

{

aux2[i]=-1;

}

posicion=P1;

esta=0;

for(i=0;i<tam;i++)

{

for(j=0;j<tam;j++)

{


{

esta=1;

}

}

if(esta==0)

{


posicion++;

}

esta=0;

}

for(i=0;i<tam;i++)

{


}

contposicion++;

177

for(i=0;i<tam;i++)

{


}

contposicion++;

}


}


{

int i;

int a,b;

int c;

int muta=0;

c=rand()% 101 + 0;

if(c<=pm)

{

muta=1;



for(i=0;i<tam;i++)

{


}



}

return muta;

}


{

int i,j;

int fila1,fila2;

178


{


{


}

}

int contposicion=0;


{

fila1=i;

fila2=i+1;


}


int muta=0;


{



}


}


{

int numjobs;

int numS;


int jobs[100];

int L[100];

int k,j,l,i;

int aux;

int secuencia[100];

int makespan;

179






int salida=0;


FILE *datos=NULL;


if(datos==NULL)




for(i=0;i<numS;i++)

{


}


{

for(j=0;j<numS;j++)

{


}

}

fclose(datos);


int maxmaq;


/*FIN DATOS*/

180

int bestmakespan=M;

clock_t tiempo;

tiempo=clock();




int tam;




{


{

orden[i]=0;

}




for(i=0;i<tam;i++)

{


{


}



}

for(i=0;i<tam;i++)

{

posiciones[i]=i;

}



181

{


{


}

}

int fila;

for(fila=0;fila<numpadres;fila++)

{

mejoralocalintercambio (fila,numjobs,makespans,matrizpadres,numS,maxmaq,L,tproceso);

}


{


salida=0;

}

else

{

salida=salida+1;

}





{


{


}


}

printf("\n");

}

FILE *resultados;

182

resultados= fopen("ResultadosInterccambio10.txt","a");


fclose(resultados);

return tmax;

}

int buscarNenM(int fila ,int N ,int numjobs ,int matrizpadres[numpadres][100])

{

int i;

int posicion;


{


{

posicion=i;

}

}

return posicion;

}

void intercambioAconB(int fila,int posicion1,int posicion2,int numjobs,int matrizpadres[numpadres][100])

{

int aux;

int k;

aux=matrizpadres[fila][posicion1];

matrizpadres[fila][posicion1]=matrizpadres[fila][posicion2];

matrizpadres[fila][posicion2]=aux;

}



{

int posicion;

int i,k;

int job;

int makespanbest;

int makespannuevo;

int secuencia[100];

int secuenciabest[100];

183

int cambio;


makespannuevo=makespans[fila];

cambio=0;


{



{

if(k!=posicion)

{

intercambioAconB(fila,posicion,k,numjobs,matrizpadres);


{

secuencia[i]=matrizpadres[fila][i];

}



{


{


}


cambio=1;

}

intercambioAconB(fila,k,posicion,numjobs,matrizpadres);

}

}

}

if(cambio==1)

{


184


{


}

}

}

trabajo fin de grado - universidad de...

Documents