SAGA_notebook.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dependencies"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "import optuna\n",
    "import copy\n",
    "import random\n",
    "import math\n",
    "import heuristics\n",
    "import importlib\n",
    "from tqdm import tqdm\n",
    "from matplotlib import pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<module 'heuristics' from 'd:\\\\esi-4\\\\SEMESTRE_2\\\\TOIA\\\\TPs\\\\TP5-hyperheuristique-Yartix\\\\heuristics.py'>"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "importlib.reload(heuristics)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Class to hold a taillard instance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Inst:\n",
    "    def __init__(self, jobs: int, machines: int, seed: int, ub: int, lb: int, matrix: list[list[int]]):\n",
    "        \"\"\"\n",
    "        Represents an instance of the scheduling problem.\n",
    "        \n",
    "        Args:\n",
    "            jobs (int): Number of jobs.\n",
    "            machines (int): Number of machines.\n",
    "            seed (int): Seed for random number generation.\n",
    "            ub (int): Upper bound.\n",
    "            lb (int): Lower bound.\n",
    "            matrix (list[list[int]]): Matrix representing job durations on machines.\n",
    "        \"\"\"\n",
    "        self.jobs = jobs\n",
    "        self.machines = machines\n",
    "        self.seed = seed\n",
    "        self.ub = ub\n",
    "        self.lb = lb\n",
    "        self.matrix = matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "function to load the instances of a taillard configuration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "def load_tai(nb_jobs, nb_machines):\n",
    "    with open(f\"content/tai{nb_jobs}_{nb_machines}.txt\", \"r\") as f:\n",
    "        lines = f.readlines()\n",
    "\n",
    "    instances: list[Inst] = []\n",
    "    i = 0\n",
    "    while i < len(lines):\n",
    "        params = [int(e) for e in lines[i+1].split()]\n",
    "        jobs = params[0]\n",
    "        machines = params[1]\n",
    "        seed = params[2]\n",
    "        ub = params[3]\n",
    "        lb = params[4]\n",
    "\n",
    "        matrix = [[int(e) for e in line.strip().split()] for line in lines[i+3:i+3+machines]]\n",
    "        instances.append(Inst(jobs, machines, seed, ub, lb, matrix))\n",
    "        i+=3+machines\n",
    "    \n",
    "    return instances"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Podium Bank data structure"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "class PodiumBank:\n",
    "    def __init__(self, size=10):\n",
    "        #the bank is sorted in an ascendant manner of the make span\n",
    "        self.bank = list()\n",
    "        self.size = size\n",
    "\n",
    "    \n",
    "    def insert(self, ms_hps): #make_span hyper_parameter_state tuple\n",
    "        if len(self.bank) == 0:\n",
    "            self.bank.append(ms_hps)\n",
    "        else:\n",
    "            insertion_index = -1\n",
    "            for i in range(len(self.bank)):\n",
    "                if ms_hps[0]<self.bank[i][0]:\n",
    "                    insertion_index = i\n",
    "            if insertion_index != -1:\n",
    "                self.bank = self.bank[:i] + [ms_hps] + self.bank[i:self.size-1]        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SAGA:\n",
    "    def __init__(self,\n",
    "                 tai_inst:Inst,\n",
    "                 init_type=['cds', 'palmer', 'neh', 'heuristics', 'heuristics_random', 'full_random'],\n",
    "                 selection_type=['roulette', 'rank', 'elitist', 'tournament', 'random'],\n",
    "                 crossover_type=['uniform', 'one_point', 'two_points', 'k_points'],\n",
    "                 replacement_type=['best_all', 'parents_replaced_by_offspring', 'worst_population_replaced_by_offspring', 'best_between_parents_and_offspring', 'roulette', 'rank', 'elitist', 'tournament', 'random'],\n",
    "                 population_size_mms=(20,50,1), #min_max_step\n",
    "                 pool_size_mms=(10,20, 1),\n",
    "                 crossover_rate_mms=(0.1, 0.9, 0.1),\n",
    "                 mutation_rate_mms=(0.1, 0.9, 0.1),\n",
    "                 num_iterations_mms=(200, 1000, 100),\n",
    "                 max_stagnation_mms=(50, 200, 50),\n",
    "                 k_points_mms=(1,3,1),\n",
    "                 variety_degree=1,\n",
    "                 num_hyper_params_neigh_window=1, #numeric hyper-parameters neighboring window size\n",
    "                 use_neh = True\n",
    "                ):\n",
    "        self.tai_inst = tai_inst\n",
    "        self.jobs_list = self.get_instance(tai_inst)\n",
    "        self.nb_jobs = len(self.jobs_list)\n",
    "        self.nb_machines = len(self.jobs_list[0])\n",
    "        self.seq_star = None\n",
    "        self.make_span_star = None\n",
    "        self.hyper_params = {\n",
    "            'init_type': init_type,\n",
    "            'selection_type': selection_type,\n",
    "            'crossover_type': crossover_type,\n",
    "            'replacement_type': replacement_type,\n",
    "            'population_size': [i for i in range(population_size_mms[0], population_size_mms[1]+1, population_size_mms[2])],\n",
    "            'pool_size': [i for i in range(pool_size_mms[0], pool_size_mms[1]+1, pool_size_mms[2])],\n",
    "            'crossover_rate': [crossover_rate_mms[0]+crossover_rate_mms[2]*i for i in range(int((crossover_rate_mms[1]-crossover_rate_mms[0])/crossover_rate_mms[2])+1)],\n",
    "            'mutation_rate': [mutation_rate_mms[0]+mutation_rate_mms[2]*i for i in range(int((mutation_rate_mms[1]-mutation_rate_mms[0])/mutation_rate_mms[2])+1)],\n",
    "            'num_iterations': [i for i in range(num_iterations_mms[0], num_iterations_mms[1]+1, num_iterations_mms[2])],\n",
    "            'max_stagnation': [i for i in range(max_stagnation_mms[0],max_stagnation_mms[1]+1,max_stagnation_mms[2])],\n",
    "            'k_points': [i for i in range(k_points_mms[0],k_points_mms[1]+1,k_points_mms[2])]\n",
    "        }\n",
    "        self.cat_hyper_params = ['init_type', 'selection_type', 'crossover_type', 'replacement_type']\n",
    "        self.num_hyper_params = ['population_size', 'pool_size', 'crossover_rate', 'mutation_rate', 'num_iterations', 'max_stagnation', 'k_points']\n",
    "        self.variety_degree = variety_degree\n",
    "        self.num_hyper_params_neigh_window = num_hyper_params_neigh_window\n",
    "        if use_neh:\n",
    "            self.neh_res = heuristics.NEH(self.tai_inst)()\n",
    "        else:\n",
    "            self.neh_res = random.sample(range(self.nb_jobs), self.nb_jobs)\n",
    "        self.palmer_res = heuristics.Palmer(self.jobs_list).optim()\n",
    "        self.cds_res = heuristics.cds_heuristic(np.array(self.jobs_list))\n",
    "\n",
    "\n",
    "\n",
    "    # genetic algorithm for flowshop utilities\n",
    "    def get_instance(self, tai_inst: Inst):\n",
    "        # Extract the jobs list from the given instance\n",
    "        \n",
    "        jobs_list = []\n",
    "        for i in range(len(tai_inst.matrix[0])):\n",
    "            jobs_list.append([])\n",
    "            for j in range(len(tai_inst.matrix)):\n",
    "                jobs_list[-1].append(tai_inst.matrix[j][i])\n",
    "        return jobs_list\n",
    "\n",
    "    def cumulate(self, job: list, previous_cumul=None):\n",
    "        # Calculate the cumulative completion times for a job\n",
    "            \n",
    "        res = [0] * len(job)\n",
    "        if previous_cumul == None:\n",
    "            res[0] = job[0]\n",
    "            for i in range(1, len(job)):\n",
    "                res[i] = res[i - 1] + job[i]\n",
    "        else:\n",
    "            res[0] = previous_cumul[0] + job[0]\n",
    "            for i in range(1, len(job)):\n",
    "                res[i] = max(res[i - 1], previous_cumul[i]) + job[i]\n",
    "        return res\n",
    "\n",
    "    def cumulate_seq(self, seq: list):\n",
    "        # Calculates the cumulative time for a sequence of jobs on machines.\n",
    "\n",
    "        cumulated = None\n",
    "        for i in seq:\n",
    "            cumulated = self.cumulate(self.jobs_list[i], cumulated)\n",
    "        return cumulated\n",
    "\n",
    "    def evaluate_makespan(self, schedule):\n",
    "        # Evaluates the makespan (completion time) of a given schedule.\n",
    "\n",
    "        cumulative = self.cumulate_seq(schedule)\n",
    "        return cumulative[-1]\n",
    " \n",
    "    def initialize_population(self, init_type, population_size):\n",
    "        \"\"\"\n",
    "        Initializes the population of individuals.\n",
    "        \n",
    "        Args:\n",
    "            init_type (str): Type of initialization method.\n",
    "            population_size (int): Size of the population.\n",
    "            \n",
    "        Returns:\n",
    "            list: Initialized population of individuals.\n",
    "        \"\"\"\n",
    "        \n",
    "        def perturb_sequence(sequence):\n",
    "            \"\"\"\n",
    "            Perturbs a sequence by swapping two random jobs.\n",
    "            \n",
    "            Args:\n",
    "                sequence (list): Sequence of jobs.\n",
    "                \n",
    "            Returns:\n",
    "                list: Perturbed sequence.\n",
    "            \"\"\"\n",
    "            perturbed_seq = sequence[:]\n",
    "            for _ in range(2):\n",
    "                i, j = random.sample(range(len(perturbed_seq)), 2)\n",
    "                perturbed_seq[i], perturbed_seq[j] = perturbed_seq[j], perturbed_seq[i]\n",
    "            return perturbed_seq\n",
    "\n",
    "        population = []\n",
    "        \n",
    "        if init_type == \"cds\":\n",
    "            cds_seq, _ = self.cds_res#heuristics.cds_heuristic(np.array(self.jobs_list))\n",
    "            population.append(cds_seq)\n",
    "            for _ in range(population_size - 1):\n",
    "                perturbed_seq = perturb_sequence(cds_seq)\n",
    "                population.append(perturbed_seq)\n",
    "\n",
    "        elif init_type == \"palmer\":\n",
    "            palmer_seq, _ = self.palmer_res#heuristics.Palmer(self.jobs_list).optim()\n",
    "            population.append(palmer_seq)\n",
    "            for _ in range(population_size - 1):\n",
    "                perturbed_seq = perturb_sequence(palmer_seq)\n",
    "                population.append(perturbed_seq)\n",
    "\n",
    "        elif init_type == \"neh\":\n",
    "            _, neh_seq = self.neh_res#heuristics.NEH(self.tai_inst)()\n",
    "            population.append(neh_seq)\n",
    "            for _ in range(population_size - 1):\n",
    "                perturbed_seq = perturb_sequence(neh_seq)\n",
    "                population.append(perturbed_seq)\n",
    "\n",
    "        elif init_type == \"heuristics\":\n",
    "            cds_size = population_size // 3\n",
    "            palmer_size = population_size // 3\n",
    "            neh_size = population_size - cds_size - palmer_size\n",
    "            \n",
    "            for _ in range(cds_size):\n",
    "                cds_seq, _ = self.cds_res#heuristics.cds_heuristic(np.array(self.jobs_list))\n",
    "                population.append(perturb_sequence(cds_seq))\n",
    "            \n",
    "            for _ in range(palmer_size):\n",
    "                palmer_seq, _ = self.palmer_res#heuristics.Palmer(self.jobs_list).optim()\n",
    "                population.append(perturb_sequence(palmer_seq))\n",
    "            \n",
    "            for _ in range(neh_size):\n",
    "                _, neh_seq = self.neh_res#heuristics.NEH(self.tai_inst)()\n",
    "                population.append(perturb_sequence(neh_seq))\n",
    "\n",
    "        elif init_type == \"heuristics_random\":\n",
    "\n",
    "            cds_seq, _ = self.cds_res#heuristics.cds_heuristic(np.array(self.jobs_list))\n",
    "            population.append(perturb_sequence(cds_seq))\n",
    "\n",
    "            palmer_seq, _ = self.palmer_res#heuristics.Palmer(self.jobs_list).optim()\n",
    "            population.append(perturb_sequence(palmer_seq))\n",
    "\n",
    "            _, neh_seq = self.neh_res#heuristics.NEH(self.tai_inst)()\n",
    "            population.append(perturb_sequence(neh_seq))\n",
    "\n",
    "            for _ in range(population_size - 3):\n",
    "                random_seq = random.sample(range(self.nb_jobs), self.nb_jobs)\n",
    "                population.append(random_seq)\n",
    "\n",
    "        elif init_type == \"full_random\":\n",
    "\n",
    "            for _ in range(population_size):\n",
    "                random_seq = random.sample(range(self.nb_jobs), self.nb_jobs)\n",
    "                population.append(random_seq)\n",
    "\n",
    "        else:\n",
    "            raise ValueError(\"Invalid initialization type\")\n",
    "\n",
    "        return population\n",
    "  \n",
    "    def select_parents(self, population):\n",
    "        \"\"\"\n",
    "        Selects parents from the population using tournament selection.\n",
    "        \n",
    "        Args:\n",
    "            population (list): Population of individuals.\n",
    "            \n",
    "        Returns:\n",
    "            tuple: Pair of selected parents.\n",
    "        \"\"\"\n",
    "        tournament = random.sample(population, 3)\n",
    "        tournament.sort(key=lambda x: self.evaluate_makespan(x))\n",
    "        return tournament[0], tournament[1]\n",
    "  \n",
    "    def crossover(self, crossover_type, parent1, parent2, crossover_rate, k_points=None):\n",
    "        \"\"\"\n",
    "        Performs crossover between two parents to produce offspring.\n",
    "        \n",
    "        Args:\n",
    "            crossover_type (str): Type of crossover operation.\n",
    "            parent1 (list): First parent.\n",
    "            parent2 (list): Second parent.\n",
    "            crossover_rate (float): Rate of crossover.\n",
    "            k (int, optional): Parameter for k-point crossover. Defaults to None.\n",
    "            \n",
    "        Returns:\n",
    "            tuple: Pair of offspring.\n",
    "        \"\"\"\n",
    "\n",
    "        def ensure_each_job_once(offspring):\n",
    "            \"\"\"\n",
    "            Ensures each job appears exactly once in the offspring.\n",
    "            \n",
    "            Args:\n",
    "                offspring (list): Offspring sequence.\n",
    "            \"\"\"\n",
    "            # Ensure offspring contains each job exactly once\n",
    "            job_count = {job: 0 for job in range(self.nb_jobs)}\n",
    "            for job in offspring:\n",
    "                job_count[job] += 1\n",
    "            for i, job in enumerate(offspring):\n",
    "                if job_count[job] > 1:\n",
    "                    for swap_job, count in job_count.items():\n",
    "                        if count == 0:\n",
    "                            offspring[i] = swap_job\n",
    "                            job_count[swap_job] += 1\n",
    "                            job_count[job] -= 1\n",
    "                            break\n",
    "\n",
    "        if random.random() < crossover_rate:\n",
    "            \n",
    "            if crossover_type == 'uniform':\n",
    "                k = None\n",
    "                mask = [random.choice([0, 1]) for _ in range(len(parent1))]\n",
    "                offspring1 = [gene1 if bit else gene2 for gene1, gene2, bit in zip(parent1, parent2, mask)]\n",
    "                offspring2 = [gene1 if bit else gene2 for gene1, gene2, bit in zip(parent2, parent1, mask)]\n",
    "\n",
    "            else:\n",
    "                if k_points is None or k_points < 1:\n",
    "                    raise ValueError(\"k must be >= 1 for one_point, two_points, and k_points crossovers\")\n",
    "                \n",
    "                if k_points is not None and k_points >= self.nb_jobs:\n",
    "                    raise ValueError(\"k in crossover must be less than the number of jobs\")\n",
    "\n",
    "                if ((crossover_type == 'one_point') or (k_points == 1)):\n",
    "                    k = 1\n",
    "                    points = [random.randint(1, len(parent1) - 1)]\n",
    "\n",
    "                elif ((crossover_type == 'two_points') or (k_points == 2)):\n",
    "                    k = 2\n",
    "                    points = sorted(random.sample(range(1, len(parent1)), 2))\n",
    "\n",
    "                elif crossover_type == 'k_points':\n",
    "                    points = sorted(random.sample(range(1, len(parent1)), k_points))\n",
    "\n",
    "                else:\n",
    "                    raise ValueError(\"Invalid crossover type\")\n",
    "\n",
    "                offspring1, offspring2 = parent1[:], parent2[:]\n",
    "                switch = False\n",
    "                for i in range(len(parent1)):\n",
    "                    if i in points:\n",
    "                        switch = not switch\n",
    "                    if switch:\n",
    "                        offspring1[i], offspring2[i] = offspring2[i], offspring1[i]\n",
    "\n",
    "            ensure_each_job_once(offspring1)\n",
    "            ensure_each_job_once(offspring2)\n",
    "            return offspring1, offspring2\n",
    "        \n",
    "        else:\n",
    "            return parent1[:], parent2[:]\n",
    "\n",
    "    def mutate(self, solution, mutation_rate):\n",
    "        \"\"\"\n",
    "        Mutates a solution with a given mutation rate.\n",
    "        \n",
    "        Args:\n",
    "            solution (list): Solution to mutate.\n",
    "            mutation_rate (float): Rate of mutation.\n",
    "            \n",
    "        Returns:\n",
    "            list: Mutated solution.\n",
    "        \"\"\"\n",
    "        if random.random() < mutation_rate:\n",
    "            i, j = random.sample(range(len(solution)), 2)\n",
    "            solution[i], solution[j] = solution[j], solution[i]\n",
    "        return solution\n",
    "\n",
    "    def select_reproduction_pool(self, selection_type, population, pool_size):\n",
    "        \"\"\"\n",
    "        Selects a pool of individuals for reproduction.\n",
    "        \n",
    "        Args:\n",
    "            selection_type (str): Type of selection method.\n",
    "            population (list): Population of individuals.\n",
    "            pool_size (int): Size of the pool.\n",
    "            \n",
    "        Returns:\n",
    "            list: Pool of selected individuals.\n",
    "        \"\"\"\n",
    "        \n",
    "        chosen = []\n",
    "\n",
    "        if selection_type == \"roulette\":\n",
    "            total_fitness = sum(self.evaluate_makespan(ind) for ind in population)\n",
    "            selection_probs = [self.evaluate_makespan(ind) / total_fitness for ind in population]\n",
    "            chosen = random.choices(population, weights=selection_probs, k=pool_size)\n",
    "\n",
    "        elif selection_type == \"rank\":\n",
    "            population_sorted = sorted(population, key=self.evaluate_makespan)\n",
    "            ranks = range(1, len(population_sorted) + 1)\n",
    "            total_rank = sum(ranks)\n",
    "            rank_weights = [rank / total_rank for rank in ranks]\n",
    "            chosen = random.choices(population_sorted, weights=rank_weights, k=pool_size)\n",
    "\n",
    "        elif selection_type == \"elitist\":\n",
    "            population_sorted = sorted(population, key=self.evaluate_makespan)\n",
    "            chosen = population_sorted[:pool_size]\n",
    "\n",
    "        elif selection_type == \"tournament\":\n",
    "            for _ in range(pool_size):\n",
    "                contenders = random.sample(population, 3)\n",
    "                chosen.append(min(contenders, key=self.evaluate_makespan))\n",
    "\n",
    "        elif selection_type == \"random\":\n",
    "            chosen = random.sample(population, pool_size)\n",
    "            \n",
    "        else:\n",
    "            raise ValueError(\"Invalid type\")\n",
    "\n",
    "        return chosen\n",
    "  \n",
    "    def replace_population(self, replacement_type, population, parents, offspring, population_size):\n",
    "        \"\"\"\n",
    "        Replaces the population with new individuals.\n",
    "        \n",
    "        Args:\n",
    "            replacement_type (str): Type of replacement method.\n",
    "            population (list): Current population.\n",
    "            parents (list): Parents generated during reproduction.\n",
    "            offspring (list): Offspring generated during reproduction.\n",
    "            population_size (int): Size of the population.\n",
    "            \n",
    "        Returns:\n",
    "            list: New population.\n",
    "        \"\"\"\n",
    "        \n",
    "        def select_population(selection_type, population, pool_size):\n",
    "            \"\"\"\n",
    "            Selects individuals for the next population.\n",
    "            \n",
    "            Args:\n",
    "                selection_type (str): Type of selection method.\n",
    "                population (list): Population of individuals.\n",
    "                pool_size (int): Size of the selection pool.\n",
    "                \n",
    "            Returns:\n",
    "                list: Selected individuals for the next population.\n",
    "            \"\"\"\n",
    "            return self.select_reproduction_pool(selection_type, population, pool_size)\n",
    "\n",
    "        if replacement_type == \"best_all\":\n",
    "            combined_population = population + offspring\n",
    "            combined_population.sort(key=lambda x: self.evaluate_makespan(x))\n",
    "            return combined_population[:population_size]\n",
    "\n",
    "        elif replacement_type == \"parents_replaced_by_offspring\":\n",
    "            population_without_parents = [ind for ind in population if ind not in parents]\n",
    "            return population_without_parents + offspring\n",
    "\n",
    "        elif replacement_type == \"worst_population_replaced_by_offspring\":\n",
    "            population_sorted = sorted(population, key=self.evaluate_makespan)\n",
    "            population_without_worst = population_sorted[:-len(offspring)]\n",
    "            return population_without_worst + offspring\n",
    "\n",
    "        elif replacement_type == \"best_between_parents_and_offspring\":\n",
    "            population_without_parents = [ind for ind in population if ind not in parents]\n",
    "            combined_sub_population = sorted(parents + offspring, key=self.evaluate_makespan)\n",
    "            return population_without_parents + combined_sub_population[:len(parents)]\n",
    "        \n",
    "        else:\n",
    "            return select_population(replacement_type, population + offspring, len(population))\n",
    "\n",
    "    def genetic_algorithm(self, init_type, selection_type, crossover_type, replacement_type, population_size, pool_size, crossover_rate, mutation_rate, num_iterations, max_stagnation, k_points=None):\n",
    "        \"\"\"\n",
    "        Executes the Genetic Algorithm to find the best solution.\n",
    "        \n",
    "        Args:\n",
    "            init_type (str): Type of initialization method.\n",
    "            selection_type (str): Type of parent selection method.\n",
    "            crossover_type (str): Type of crossover method.\n",
    "            replacement_type (str): Type of population replacement method.\n",
    "            population_size (int): Size of the population.\n",
    "            pool_size (int): Size of the reproduction pool.\n",
    "            crossover_rate (float): Rate of crossover.\n",
    "            mutation_rate (float): Rate of mutation.\n",
    "            num_iterations (int): Maximum number of iterations.\n",
    "            max_stagnation (int): Maximum number of iterations without improvement.\n",
    "            k_points (int, optional): Parameter for k-point crossover. Defaults to None.\n",
    "            \n",
    "        Returns:\n",
    "            tuple: Best solution and its makespan.\n",
    "        \"\"\"\n",
    "        \n",
    "        if pool_size > population_size:\n",
    "            raise ValueError(\"Pool size must be less than population size.\")\n",
    "\n",
    "        population = self.initialize_population(init_type, population_size)\n",
    "        population.sort(key=lambda x: self.evaluate_makespan(x))\n",
    "        \n",
    "        best_solution = population[0]\n",
    "        best_solution_fitness = self.evaluate_makespan(best_solution)\n",
    "        stagnation_count = 0\n",
    "\n",
    "        for i in range(num_iterations):\n",
    "            reproduction_pool = self.select_reproduction_pool(selection_type, population, pool_size)\n",
    "            offspring = []\n",
    "            parents = []\n",
    "\n",
    "            for _ in range(pool_size // 2):\n",
    "                parent1, parent2 = self.select_parents(reproduction_pool)\n",
    "                parents.extend([parent1, parent2])\n",
    "                child1, child2 = self.crossover(crossover_type, parent1, parent2, crossover_rate, k_points) \n",
    "                child1 = self.mutate(child1, mutation_rate)\n",
    "                child2 = self.mutate(child2, mutation_rate)\n",
    "                offspring.extend([child1, child2])\n",
    "\n",
    "            population = self.replace_population(replacement_type, population, parents, offspring, population_size)\n",
    "            population.sort(key=lambda x: self.evaluate_makespan(x))\n",
    "\n",
    "            current_best_solution = population[0]\n",
    "            current_best_solution_fitness = self.evaluate_makespan(current_best_solution)\n",
    "\n",
    "            if current_best_solution_fitness < best_solution_fitness:\n",
    "                best_solution = current_best_solution\n",
    "                best_solution_fitness = current_best_solution_fitness\n",
    "                stagnation_count = 0\n",
    "            else:\n",
    "                stagnation_count += 1\n",
    "\n",
    "            if max_stagnation is not None and stagnation_count >= max_stagnation:\n",
    "                break\n",
    "\n",
    "        return best_solution\n",
    "\n",
    "    #simulated annealing hyperheuristic utilities\n",
    "    def init_random_hps(self):\n",
    "        hps={\n",
    "            'init_type':np.random.choice(self.hyper_params['init_type'], 1)[0],\n",
    "            'selection_type':np.random.choice(self.hyper_params['selection_type'], 1)[0],\n",
    "            'crossover_type':np.random.choice(self.hyper_params['crossover_type'], 1)[0],\n",
    "            'replacement_type':np.random.choice(self.hyper_params['replacement_type'], 1)[0],\n",
    "            'population_size':np.random.choice(self.hyper_params['population_size'], 1)[0],\n",
    "            'pool_size':np.random.choice(self.hyper_params['pool_size'], 1)[0],\n",
    "            'crossover_rate':np.random.choice(self.hyper_params['crossover_rate'], 1)[0],\n",
    "            'mutation_rate':np.random.choice(self.hyper_params['mutation_rate'], 1)[0],\n",
    "            'num_iterations':np.random.choice(self.hyper_params['num_iterations'], 1)[0],\n",
    "            'max_stagnation':np.random.choice(self.hyper_params['max_stagnation'], 1)[0],\n",
    "            'k_points':np.random.choice(self.hyper_params['k_points'], 1)[0]\n",
    "        }\n",
    "        return hps\n",
    "\n",
    "    def generate_neigh_hps(self, hps):\n",
    "        #randomly selecting 'self.variety_degree' hyper_parameters to forcibly vary, the rest of the hyper_params can either vary or not\n",
    "        varied_keys = np.random.choice([key for key in self.hyper_params.keys()], self.variety_degree, replace=False)\n",
    "        #we create the new hyper-parameters dict\n",
    "        new_hps = dict()\n",
    "        #for each categorical hyper-param\n",
    "        for hyper_param in self.cat_hyper_params:\n",
    "            #if the hyper param is to be forcibly varied\n",
    "            if hyper_param in varied_keys:\n",
    "                neigh_space = list(self.hyper_params[hyper_param])\n",
    "                neigh_space.remove(hps[hyper_param])\n",
    "                new_hps[hyper_param] = np.random.choice(neigh_space, 1)[0]\n",
    "            else:\n",
    "                new_hps[hyper_param] = np.random.choice(self.hyper_params[hyper_param], 1)[0]\n",
    "        #for each numercial hyper-param\n",
    "        for hyper_param in self.num_hyper_params:\n",
    "            # we get its index in the range of possible values\n",
    "            hyper_param_value_index = self.hyper_params[hyper_param].index(hps[hyper_param])\n",
    "            # we get the bottom index of the neighboring window using self.num_hyper_param_neigh_windows\n",
    "            win_bottom_index = hyper_param_value_index-self.num_hyper_params_neigh_window\n",
    "            # we check if we didn't go below 0\n",
    "            if win_bottom_index < 0: win_bottom_index = 0\n",
    "            # we create the neighboring space\n",
    "            if hyper_param in varied_keys:\n",
    "                neigh_space = list(self.hyper_params[hyper_param])[win_bottom_index : hyper_param_value_index+self.num_hyper_params_neigh_window+1]\n",
    "                neigh_space.remove(hps[hyper_param])\n",
    "                new_hps[hyper_param] = np.random.choice(neigh_space, 1)[0]\n",
    "            else:\n",
    "                new_hps[hyper_param] = np.random.choice(self.hyper_params[hyper_param][win_bottom_index : hyper_param_value_index+self.num_hyper_params_neigh_window+1],1)[0]\n",
    "        return new_hps\n",
    "    \n",
    "\n",
    "    def optim(self,\n",
    "              T=1.0,\n",
    "              T_min=0.001,\n",
    "              alpha=0.9,\n",
    "              nb_iter=500,\n",
    "              init_method='random',\n",
    "              neigh_method='random',\n",
    "              length_palier=1,\n",
    "              jump_rate=0,\n",
    "              jump_ratio=1,\n",
    "              debug=False,\n",
    "              trace=False):      \n",
    "        #checking for hyper_params coherance\n",
    "        if jump_rate != 0 and jump_ratio>=1/alpha:\n",
    "            raise Exception(\"Y_exception: jump_ratio >= 1/alpha\")\n",
    "        #initializing the hyper_parameter_state hps randomly and computing the corresponding make_span_star\n",
    "        hps = self.init_random_hps()\n",
    "        loc_seq_star = current_seq = self.genetic_algorithm(**hps)\n",
    "        loc_make_span_star = current_make_span = self.evaluate_makespan(current_seq)\n",
    "        #showing some debug\n",
    "        if debug:\n",
    "            print('initial hps', hps)\n",
    "            print('initial make_span', current_make_span)\n",
    "        #preping the tracing\n",
    "        hps_trace = None\n",
    "        current_make_span_trace = None\n",
    "        loc_make_span_star_trace = None\n",
    "        temp_trace = None\n",
    "        if trace:\n",
    "            hps_trace = [hps]\n",
    "            current_make_span_trace = [current_make_span]\n",
    "            loc_make_span_star_trace = [loc_make_span_star]\n",
    "            temp_trace = [T]\n",
    "        #we initialize the temperature session at length_palier\n",
    "        temp_session = length_palier\n",
    "        #main loop\n",
    "        for _ in (t := tqdm(range(nb_iter))):\n",
    "            t.set_description(f\"Temperature {T}\")\n",
    "            #generate a random neighbour sequence\n",
    "            new_hps = self.generate_neigh_hps(hps)\n",
    "            #compute the energy difference\n",
    "            neigh_seq = self.genetic_algorithm(**new_hps)\n",
    "            neigh_make_span = self.evaluate_makespan(neigh_seq)\n",
    "            delta = current_make_span - neigh_make_span\n",
    "            #if the neighbour sequence is better, accept it\n",
    "            if delta > 0:\n",
    "                hps = new_hps\n",
    "                current_seq = neigh_seq\n",
    "                current_make_span = neigh_make_span\n",
    "                # we check if the newly obtained solution is better than the current best\n",
    "                if current_make_span < loc_make_span_star:\n",
    "                    loc_seq_star = current_seq\n",
    "                    loc_make_span_star = current_make_span\n",
    "            #if the neighbour sequence is worse, accept it with a probability that decreases with the temperature\n",
    "            elif np.random.random() < math.exp(delta/T):\n",
    "                    current_seq = neigh_seq\n",
    "                    current_make_span = neigh_make_span\n",
    "            #cooling\n",
    "            temp_session -= 1\n",
    "            if temp_session == 0:\n",
    "                if np.random.random() < jump_rate:\n",
    "                    T = T * jump_ratio\n",
    "                else:\n",
    "                    T = T * alpha\n",
    "                temp_session = length_palier\n",
    "            if trace:\n",
    "                hps_trace.append(hps)\n",
    "                current_make_span_trace.append(current_make_span)\n",
    "                loc_make_span_star_trace.append(loc_make_span_star_trace)\n",
    "                temp_trace.append(T)\n",
    "            if(T<=T_min): break\n",
    "\n",
    "        self.seq_star = loc_seq_star\n",
    "        self.make_span_star = loc_make_span_star               \n",
    "        return hps_trace, current_make_span_trace, loc_make_span_star_trace, temp_trace"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Demonstration on a small instance with strong hyper parameters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Temperature 0.00010449567633177853:  17%|█▋        | 87/500 [03:26<16:22,  2.38s/it] "
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "make_span_star 1297\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[<matplotlib.lines.Line2D at 0x129cae6d3d0>]"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAjAAAAGdCAYAAAAMm0nCAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjguNCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8fJSN1AAAACXBIWXMAAA9hAAAPYQGoP6dpAAAm90lEQVR4nO3dfVBVd2L/8c9Fci+K3isP5akCmtjo6lqSxSeSNZXRAV0f1jbR2WgN2ThaUzJN6kyCRCVkW4sjnVoTqSw7rnGzaZNmEumWrbti0EUjUYFen3YlOhKhkos6JvcqJoBwfn/scH57V7IrRIQvvl8zZybn+Xs8Ge97Loejw7IsSwAAAAYJ6e8BAAAA9BQBAwAAjEPAAAAA4xAwAADAOAQMAAAwDgEDAACMQ8AAAADjEDAAAMA4of09gL7S2dmppqYmjRgxQg6Ho7+HAwAAboNlWbp27ZoSEhIUEvLV37MM2oBpampSYmJifw8DAAD0QmNjo0aNGvWV6wdtwIwYMULSb/8A3G53P48GAADcjkAgoMTERPtz/KsM2oDp+rGR2+0mYAAAMMwfe/yDh3gBAIBxCBgAAGAcAgYAABiHgAEAAMYhYAAAgHEIGAAAYBwCBgAAGIeAAQAAxiFgAACAcQgYAABgHAIGAAAYh4ABAADGIWAAAIBxCBgAAGCcHgdMZWWlFixYoISEBDkcDpWWlgatz8/P1/jx4xUeHq6IiAjNnj1bR44cueU4P//5zzVt2jQNHTpUERERWrRoUdD6hoYGzZs3T8OGDVNMTIxefPFF3bx5s6fDBQAAg1CPA6alpUUpKSkqKirqdv2DDz6obdu26eTJkzp06JBGjx6tjIwMXb582d7mvffe0/Lly/X9739fx48f14cffqilS5fa6zs6OjRv3jy1tbXp8OHD2rVrl9544w3l5eX14hIBAMBg47Asy+r1zg6Hdu/efcu3J78rEAjI4/Fo3759mjVrlm7evKnRo0fr1Vdf1YoVK7rdZ8+ePZo/f76ampoUGxsrSSouLlZOTo4uX74sp9P5R8fWdV6/3y+3292r6wMAAHfX7X5+9+kzMG1tbSopKZHH41FKSookqba2VhcvXlRISIgefvhhxcfHa+7cuTp16pS9X1VVlSZNmmTHiyRlZmYqEAjo9OnT3Z6rtbVVgUAgaAIAAINTnwRMWVmZhg8frrCwMG3ZskXl5eWKjo6WJJ0/f17Sb5+VWb9+vcrKyhQREaGZM2fq6tWrkiSfzxcUL5LseZ/P1+05CwoK5PF47CkxMbEvLg0AAAwAfRIw6enp8nq9Onz4sObMmaMlS5bo0qVLkqTOzk5J0rp16/T4448rNTVVO3fulMPh0Lvvvtvrc+bm5srv99tTY2PjHbkWAAAw8PRJwISHh2vs2LGaPn26duzYodDQUO3YsUOSFB8fL0maMGGCvb3L5dL999+vhoYGSVJcXJyam5uDjtk1HxcX1+05XS6X3G530AQAAAanu/IemM7OTrW2tkqSUlNT5XK5VFdXZ69vb2/XJ598ouTkZElSWlqaTp48aX9rI0nl5eVyu91B4QMAAO5NoT3d4fr16zp37pw9X19fL6/Xq8jISEVFRWnjxo1auHCh4uPjdeXKFRUVFenixYtavHixJMntdmv16tV65ZVXlJiYqOTkZBUWFkqSvU1GRoYmTJig5cuXa/PmzfL5fFq/fr2ys7PlcrnuxHUDAACD9ThgqqurlZ6ebs+vWbNGkpSVlaXi4mKdOXNGu3bt0pUrVxQVFaUpU6bo4MGDmjhxor1PYWGhQkNDtXz5cn3xxReaNm2aKioqFBERIUkaMmSIysrK9OyzzyotLU3h4eHKysrSD37wg697vQAAYBD4Wu+BGch4DwwAAOYZEO+BAQAA6AsEDAAAMA4BAwAAjEPAAAAA4xAwAADAOAQMAAAwDgEDAACMQ8AAAADjEDAAAMA4BAwAADAOAQMAAIxDwAAAAOMQMAAAwDgEDAAAMA4BAwAAjEPAAAAA4xAwAADAOAQMAAAwDgEDAACMQ8AAAADjEDAAAMA4BAwAADAOAQMAAIxDwAAAAOMQMAAAwDgEDAAAMA4BAwAAjEPAAAAA4xAwAADAOAQMAAAwDgEDAACMQ8AAAADjEDAAAMA4BAwAADAOAQMAAIxDwAAAAOMQMAAAwDgEDAAAMA4BAwAAjEPAAAAA4xAwAADAOD0OmMrKSi1YsEAJCQlyOBwqLS0NWp+fn6/x48crPDxcERERmj17to4cOdLtsVpbW/XQQw/J4XDI6/UGrTtx4oRmzJihsLAwJSYmavPmzT0dKgAAGKR6HDAtLS1KSUlRUVFRt+sffPBBbdu2TSdPntShQ4c0evRoZWRk6PLly7ds+9JLLykhIeGW5YFAQBkZGUpOTlZNTY0KCwuVn5+vkpKSng4XAAAMQg7Lsqxe7+xwaPfu3Vq0aNFXbhMIBOTxeLRv3z7NmjXLXr5nzx6tWbNG7733niZOnKj//d//1UMPPSRJ2r59u9atWyefzyen0ylJWrt2rUpLS3XmzJnbGlvXef1+v9xud28vEQAA3EW3+/ndp8/AtLW1qaSkRB6PRykpKfby5uZmrVy5Um+++aaGDRt2y35VVVV67LHH7HiRpMzMTNXV1emzzz7r9lytra0KBAJBEwAAGJz6JGDKyso0fPhwhYWFacuWLSovL1d0dLQkybIsPf3001q9erUmT57c7f4+n0+xsbFBy7rmfT5ft/sUFBTI4/HYU2Ji4h28IgAAMJD0ScCkp6fL6/Xq8OHDmjNnjpYsWaJLly5Jkl5//XVdu3ZNubm5d/Scubm58vv99tTY2HhHjw8AAAaOPgmY8PBwjR07VtOnT9eOHTsUGhqqHTt2SJIqKipUVVUll8ul0NBQjR07VpI0efJkZWVlSZLi4uLU3NwcdMyu+bi4uG7P6XK55Ha7gyYAADA43ZX3wHR2dqq1tVWS9Nprr+n48ePyer3yer36n//5H0nSO++8o40bN0qS0tLSVFlZqfb2dvsY5eXlGjdunCIiIu7GkAEAwAAW2tMdrl+/rnPnztnz9fX18nq9ioyMVFRUlDZu3KiFCxcqPj5eV65cUVFRkS5evKjFixdLkpKSkoKON3z4cEnSAw88oFGjRkmSli5dqldffVUrVqxQTk6OTp06pa1bt2rLli29vlAAADB49DhgqqurlZ6ebs+vWbNGkpSVlaXi4mKdOXNGu3bt0pUrVxQVFaUpU6bo4MGDmjhx4m2fw+PxaO/evcrOzlZqaqqio6OVl5enVatW9XS4AABgEPpa74EZyHgPDAAA5hkQ74EBAADoCwQMAAAwDgEDAACMQ8AAAADjEDAAAMA4BAwAADAOAQMAAIxDwAAAAOMQMAAAwDgEDAAAMA4BAwAAjEPAAAAA4xAwAADAOAQMAAAwDgEDAACMQ8AAAADjEDAAAMA4BAwAADAOAQMAAIxDwAAAAOMQMAAAwDgEDAAAMA4BAwAAjEPAAAAA4xAwAADAOAQMAAAwDgEDAACMQ8AAAADjEDAAAMA4BAwAADAOAQMAAIxDwAAAAOMQMAAAwDgEDAAAMA4BAwAAjEPAAAAA4xAwAADAOAQMAAAwDgEDAACMQ8AAAADjEDAAAMA4PQ6YyspKLViwQAkJCXI4HCotLQ1an5+fr/Hjxys8PFwRERGaPXu2jhw5Yq//5JNPtGLFCo0ZM0ZDhw7VAw88oFdeeUVtbW1Bxzlx4oRmzJihsLAwJSYmavPmzb27QgAAMOj0OGBaWlqUkpKioqKibtc/+OCD2rZtm06ePKlDhw5p9OjRysjI0OXLlyVJZ86cUWdnp374wx/q9OnT2rJli4qLi/Xyyy/bxwgEAsrIyFBycrJqampUWFio/Px8lZSU9PIyAQDAYOKwLMvq9c4Oh3bv3q1FixZ95TaBQEAej0f79u3TrFmzut2msLBQ27dv1/nz5yVJ27dv17p16+Tz+eR0OiVJa9euVWlpqc6cOXNbY+s6r9/vl9vt7tmFAQCAfnG7n999+gxMW1ubSkpK5PF4lJKS8pXb+f1+RUZG2vNVVVV67LHH7HiRpMzMTNXV1emzzz7r9hitra0KBAJBEwAAGJz6JGDKyso0fPhwhYWFacuWLSovL1d0dHS32547d06vv/66/uZv/sZe5vP5FBsbG7Rd17zP5+v2OAUFBfJ4PPaUmJh4h64GAAAMNH0SMOnp6fJ6vTp8+LDmzJmjJUuW6NKlS7dsd/HiRc2ZM0eLFy/WypUrv9Y5c3Nz5ff77amxsfFrHQ8AAAxcfRIw4eHhGjt2rKZPn64dO3YoNDRUO3bsCNqmqalJ6enpeuSRR255ODcuLk7Nzc1By7rm4+Liuj2ny+WS2+0OmgAAwOB0V94D09nZqdbWVnv+4sWLmjlzplJTU7Vz506FhAQPIy0tTZWVlWpvb7eXlZeXa9y4cYqIiLgbQwYAAANYjwPm+vXr8nq98nq9kqT6+np5vV41NDSopaVFL7/8sj766CNduHBBNTU1euaZZ3Tx4kUtXrxY0v+Pl6SkJP3zP/+zLl++LJ/PF/Rsy9KlS+V0OrVixQqdPn1a77zzjrZu3ao1a9bcmasGAABGC+3pDtXV1UpPT7fnu6IiKytLxcXFOnPmjHbt2qUrV64oKipKU6ZM0cGDBzVx4kRJv/0m5dy5czp37pxGjRoVdOyu3+j2eDzau3evsrOzlZqaqujoaOXl5WnVqlW9vlAAADB4fK33wAxkvAcGAADzDIj3wAAAAPQFAgYAABiHgAEAAMYhYAAAgHEIGAAAYBwCBgAAGIeAAQAAxiFgAACAcQgYAABgHAIGAAAYh4ABAADGIWAAAIBxCBgAAGAcAgYAABiHgAEAAMYhYAAAgHEIGAAAYBwCBgAAGIeAAQAAxiFgAACAcQgYAABgHAIGAAAYh4ABAADGIWAAAIBxCBgAAGAcAgYAABiHgAEAAMYhYAAAgHEIGAAAYBwCBgAAGIeAAQAAxiFgAACAcQgYAABgHAIGAAAYh4ABAADGIWAAAIBxCBgAAGAcAgYAABiHgAEAAMYhYAAAgHEIGAAAYJweB0xlZaUWLFighIQEORwOlZaWBq3Pz8/X+PHjFR4eroiICM2ePVtHjhwJ2ubq1atatmyZ3G63Ro4cqRUrVuj69etB25w4cUIzZsxQWFiYEhMTtXnz5p5fHQAAGJR6HDAtLS1KSUlRUVFRt+sffPBBbdu2TSdPntShQ4c0evRoZWRk6PLly/Y2y5Yt0+nTp1VeXq6ysjJVVlZq1apV9vpAIKCMjAwlJyerpqZGhYWFys/PV0lJSS8uEQAADDYOy7KsXu/scGj37t1atGjRV24TCATk8Xi0b98+zZo1S7/5zW80YcIEHTt2TJMnT5Yk/eIXv9B3vvMd/d///Z8SEhK0fft2rVu3Tj6fT06nU5K0du1alZaW6syZM7c1tq7z+v1+ud3u3l4iAAC4i27387tPn4Fpa2tTSUmJPB6PUlJSJElVVVUaOXKkHS+SNHv2bIWEhNg/aqqqqtJjjz1mx4skZWZmqq6uTp999lm352ptbVUgEAiaAADA4NQnAVNWVqbhw4crLCxMW7ZsUXl5uaKjoyVJPp9PMTExQduHhoYqMjJSPp/P3iY2NjZom675rm1+X0FBgTwejz0lJibe6csCAAADRJ8ETHp6urxerw4fPqw5c+ZoyZIlunTpUl+cypabmyu/329PjY2NfXo+AADQf/okYMLDwzV27FhNnz5dO3bsUGhoqHbs2CFJiouLuyVmbt68qatXryouLs7eprm5OWibrvmubX6fy+WS2+0OmgAAwOB0V94D09nZqdbWVklSWlqaPv/8c9XU1NjrKyoq1NnZqWnTptnbVFZWqr293d6mvLxc48aNU0RExN0YMgAAGMB6HDDXr1+X1+uV1+uVJNXX18vr9aqhoUEtLS16+eWX9dFHH+nChQuqqanRM888o4sXL2rx4sWSpG984xuaM2eOVq5cqaNHj+rDDz/Uc889p+9973tKSEiQJC1dulROp1MrVqzQ6dOn9c4772jr1q1as2bNnbtyAABgrNCe7lBdXa309HR7visqsrKyVFxcrDNnzmjXrl26cuWKoqKiNGXKFB08eFATJ06093nrrbf03HPPadasWQoJCdHjjz+u1157zV7v8Xi0d+9eZWdnKzU1VdHR0crLywt6V0x/sSxLX7R39PcwAADod0PvGyKHw9Ev5/5a74EZyPrqPTA32m5qQt4v79jxAAAw1a9/kKlhzh5/F/IHDYj3wAAAAPSFO5tN94Ch9w3Rr3+Q2d/DAACg3w29b0i/nZuA6SGHw3HHvy4DAAA9w4+QAACAcQgYAABgHAIGAAAYh4ABAADGIWAAAIBxCBgAAGAcAgYAABiHgAEAAMYhYAAAgHEIGAAAYBwCBgAAGIeAAQAAxiFgAACAcQgYAABgHAIGAAAYh4ABAADGIWAAAIBxCBgAAGAcAgYAABiHgAEAAMYhYAAAgHEIGAAAYBwCBgAAGIeAAQAAxiFgAACAcQgYAABgHAIGAAAYh4ABAADGIWAAAIBxCBgAAGAcAgYAABiHgAEAAMYhYAAAgHEIGAAAYBwCBgAAGIeAAQAAxiFgAACAcXocMJWVlVqwYIESEhLkcDhUWlpqr2tvb1dOTo4mTZqk8PBwJSQk6KmnnlJTU1PQMT7++GN997vfVXR0tNxut7797W9r//79Qds0NDRo3rx5GjZsmGJiYvTiiy/q5s2bvbtKAAAwqPQ4YFpaWpSSkqKioqJb1t24cUO1tbXasGGDamtr9f7776uurk4LFy4M2m7+/Pm6efOmKioqVFNTo5SUFM2fP18+n0+S1NHRoXnz5qmtrU2HDx/Wrl279MYbbygvL6+XlwkAAAYTh2VZVq93dji0e/duLVq06Cu3OXbsmKZOnaoLFy4oKSlJV65c0Z/8yZ+osrJSM2bMkCRdu3ZNbrdb5eXlmj17tvbs2aP58+erqalJsbGxkqTi4mLl5OTo8uXLcjqdf3RsgUBAHo9Hfr9fbre7t5cIAADuotv9/O7zZ2D8fr8cDodGjhwpSYqKitK4ceP0k5/8RC0tLbp586Z++MMfKiYmRqmpqZKkqqoqTZo0yY4XScrMzFQgENDp06f7esgAAGCAC+3Lg3/55ZfKycnRk08+aVeUw+HQvn37tGjRIo0YMUIhISGKiYnRL37xC0VEREiSfD5fULxIsue7fsz0+1pbW9Xa2mrPBwKBvrgkAAAwAPTZNzDt7e1asmSJLMvS9u3b7eWWZSk7O1sxMTE6ePCgjh49qkWLFmnBggX69NNPe32+goICeTwee0pMTLwTlwEAAAagPgmYrni5cOGCysvLg36GVVFRobKyMr399tt69NFH9a1vfUv/9m//pqFDh2rXrl2SpLi4ODU3Nwcds2s+Li6u23Pm5ubK7/fbU2NjY19cGgAAGADueMB0xcvZs2e1b98+RUVFBa2/cePGb08cEnzqkJAQdXZ2SpLS0tJ08uRJXbp0yV7fFUITJkzo9rwul0tutztoAgAAg1OPn4G5fv26zp07Z8/X19fL6/UqMjJS8fHxeuKJJ1RbW6uysjJ1dHTYz6xERkbK6XQqLS1NERERysrKUl5enoYOHaof/ehHqq+v17x58yRJGRkZmjBhgpYvX67NmzfL5/Np/fr1ys7OlsvlukOXDgAATNXjX6M+cOCA0tPTb1melZWl/Px8jRkzptv99u/fr5kzZ0qSqqurtW7dOlVXV6u9vV0TJ05UXl6e5s6da29/4cIFPfvsszpw4IDCw8OVlZWlTZs2KTT09pqLX6MGAMA8t/v5/bXeAzOQETAAAJhnwLwHBgAA4E4jYAAAgHEIGAAAYBwCBgAAGIeAAQAAxiFgAACAcQgYAABgHAIGAAAYh4ABAADGIWAAAIBxCBgAAGAcAgYAABiHgAEAAMYhYAAAgHEIGAAAYBwCBgAAGIeAAQAAxiFgAACAcQgYAABgHAIGAAAYh4ABAADGIWAAAIBxCBgAAGAcAgYAABiHgAEAAMYhYAAAgHEIGAAAYBwCBgAAGIeAAQAAxiFgAACAcQgYAABgHAIGAAAYh4ABAADGIWAAAIBxCBgAAGAcAgYAABiHgAEAAMYhYAAAgHEIGAAAYBwCBgAAGIeAAQAAxulxwFRWVmrBggVKSEiQw+FQaWmpva69vV05OTmaNGmSwsPDlZCQoKeeekpNTU23HOfnP/+5pk2bpqFDhyoiIkKLFi0KWt/Q0KB58+Zp2LBhiomJ0YsvvqibN2/2+AIBAMDg0+OAaWlpUUpKioqKim5Zd+PGDdXW1mrDhg2qra3V+++/r7q6Oi1cuDBou/fee0/Lly/X97//fR0/flwffvihli5daq/v6OjQvHnz1NbWpsOHD2vXrl164403lJeX14tLBAAAg43Dsiyr1zs7HNq9e/ct3578rmPHjmnq1Km6cOGCkpKSdPPmTY0ePVqvvvqqVqxY0e0+e/bs0fz589XU1KTY2FhJUnFxsXJycnT58mU5nc4/OrZAICCPxyO/3y+3292r6wMAAHfX7X5+9/kzMH6/Xw6HQyNHjpQk1dbW6uLFiwoJCdHDDz+s+Ph4zZ07V6dOnbL3qaqq0qRJk+x4kaTMzEwFAgGdPn262/O0trYqEAgETQAAYHDq04D58ssvlZOToyeffNKuqPPnz0uS8vPztX79epWVlSkiIkIzZ87U1atXJUk+ny8oXiTZ8z6fr9tzFRQUyOPx2FNiYmJfXRYAAOhnfRYw7e3tWrJkiSzL0vbt2+3lnZ2dkqR169bp8ccfV2pqqnbu3CmHw6F333231+fLzc2V3++3p8bGxq99DQAAYGAK7YuDdsXLhQsXVFFREfQzrPj4eEnShAkT7GUul0v333+/GhoaJElxcXE6evRo0DGbm5vtdd1xuVxyuVx39DoAAMDAdMe/gemKl7Nnz2rfvn2KiooKWp+amiqXy6W6urqgfT755BMlJydLktLS0nTy5EldunTJ3qa8vFxutzsofAAAwL2px9/AXL9+XefOnbPn6+vr5fV6FRkZqfj4eD3xxBOqra1VWVmZOjo67GdWIiMj5XQ65Xa7tXr1ar3yyitKTExUcnKyCgsLJUmLFy+WJGVkZGjChAlavny5Nm/eLJ/Pp/Xr1ys7O5tvWQAAQM9/jfrAgQNKT0+/ZXlWVpby8/M1ZsyYbvfbv3+/Zs6cKem337jk5ubqzTff1BdffKFp06bpX//1XzVx4kR7+wsXLujZZ5/VgQMHFB4erqysLG3atEmhobfXXPwaNQAA5rndz++v9R6YgYyAAQDAPAPmPTAAAAB3GgEDAACMQ8AAAADjEDAAAMA4BAwAADAOAQMAAIxDwAAAAOMQMAAAwDgEDAAAMA4BAwAAjEPAAAAA4xAwAADAOAQMAAAwDgEDAACMQ8AAAADjEDAAAMA4BAwAADAOAQMAAIxDwAAAAOMQMAAAwDgEDAAAMA4BAwAAjEPAAAAA4xAwAADAOAQMAAAwDgEDAACMQ8AAAADjEDAAAMA4BAwAADAOAQMAAIxDwAAAAOMQMAAAwDgEDAAAMA4BAwAAjEPAAAAA4xAwAADAOAQMAAAwDgEDAACMQ8AAAADjEDAAAMA4BAwAADBOjwOmsrJSCxYsUEJCghwOh0pLS+117e3tysnJ0aRJkxQeHq6EhAQ99dRTampq6vZYra2teuihh+RwOOT1eoPWnThxQjNmzFBYWJgSExO1efPmng4VAAAMUj0OmJaWFqWkpKioqOiWdTdu3FBtba02bNig2tpavf/++6qrq9PChQu7PdZLL72khISEW5YHAgFlZGQoOTlZNTU1KiwsVH5+vkpKSno6XAAAMAiF9nSHuXPnau7cud2u83g8Ki8vD1q2bds2TZ06VQ0NDUpKSrKX79mzR3v37tV7772nPXv2BO3z1ltvqa2tTT/+8Y/ldDo1ceJEeb1e/cu//ItWrVrV0yEDAIBBps+fgfH7/XI4HBo5cqS9rLm5WStXrtSbb76pYcOG3bJPVVWVHnvsMTmdTntZZmam6urq9Nlnn3V7ntbWVgUCgaAJAAAMTn0aMF9++aVycnL05JNPyu12S5Isy9LTTz+t1atXa/Lkyd3u5/P5FBsbG7Ssa97n83W7T0FBgTwejz0lJibewSsBAAADSZ8FTHt7u5YsWSLLsrR9+3Z7+euvv65r164pNzf3jp4vNzdXfr/fnhobG+/o8QEAwMDR42dgbkdXvFy4cEEVFRX2ty+SVFFRoaqqKrlcrqB9Jk+erGXLlmnXrl2Ki4tTc3Nz0Pqu+bi4uG7P6XK5bjkmAAAYnO54wHTFy9mzZ7V//35FRUUFrX/ttdf0j//4j/Z8U1OTMjMz9c4772jatGmSpLS0NK1bt07t7e267777JEnl5eUaN26cIiIi7vSQAQCAYXocMNevX9e5c+fs+fr6enm9XkVGRio+Pl5PPPGEamtrVVZWpo6ODvuZlcjISDmdzqDfRJKk4cOHS5IeeOABjRo1SpK0dOlSvfrqq1qxYoVycnJ06tQpbd26VVu2bOn1hQIAgMGjxwFTXV2t9PR0e37NmjWSpKysLOXn5+tnP/uZJOmhhx4K2m///v2aOXPmbZ3D4/Fo7969ys7OVmpqqqKjo5WXl8evUAMAAEmSw7Isq78H0RcCgYA8Ho/8fn/QMzgAAGDgut3Pb/4tJAAAYBwCBgAAGIeAAQAAxiFgAACAcQgYAABgHAIGAAAYh4ABAADGIWAAAIBxCBgAAGAcAgYAABiHgAEAAMYhYAAAgHEIGAAAYBwCBgAAGIeAAQAAxiFgAACAcQgYAABgHAIGAAAYh4ABAADGIWAAAIBxCBgAAGAcAgYAABiHgAEAAMYhYAAAgHEIGAAAYBwCBgAAGIeAAQAAxiFgAACAcQgYAABgnND+HkBfsSxLkhQIBPp5JAAA4HZ1fW53fY5/lUEbMNeuXZMkJSYm9vNIAABAT127dk0ej+cr1zusP5Y4hurs7FRTU5NGjBghh8PRq2MEAgElJiaqsbFRbrf7Do8QXwf3ZmDivgxc3JuBiftyK8uydO3aNSUkJCgk5KufdBm038CEhIRo1KhRd+RYbreb/7EGKO7NwMR9Gbi4NwMT9yXYH/rmpQsP8QIAAOMQMAAAwDgEzB/gcrn0yiuvyOVy9fdQ8Hu4NwMT92Xg4t4MTNyX3hu0D/ECAIDBi29gAACAcQgYAABgHAIGAAAYh4ABAADGIWD+gKKiIo0ePVphYWGaNm2ajh492t9DuqcUFBRoypQpGjFihGJiYrRo0SLV1dUFbfPll18qOztbUVFRGj58uB5//HE1Nzf304jvTZs2bZLD4dALL7xgL+O+9J+LFy/qr//6rxUVFaWhQ4dq0qRJqq6uttdblqW8vDzFx8dr6NChmj17ts6ePduPIx78Ojo6tGHDBo0ZM0ZDhw7VAw88oH/4h38I+rd+uC+9YKFbb7/9tuV0Oq0f//jH1unTp62VK1daI0eOtJqbm/t7aPeMzMxMa+fOndapU6csr9drfec737GSkpKs69ev29usXr3aSkxMtD744AOrurramj59uvXII4/046jvLUePHrVGjx5t/fmf/7n1/PPP28u5L/3j6tWrVnJysvX0009bR44csc6fP2/98pe/tM6dO2dvs2nTJsvj8VilpaXW8ePHrYULF1pjxoyxvvjii34c+eC2ceNGKyoqyiorK7Pq6+utd9991xo+fLi1detWexvuS88RMF9h6tSpVnZ2tj3f0dFhJSQkWAUFBf04qnvbpUuXLEnWr371K8uyLOvzzz+37rvvPuvdd9+1t/nNb35jSbKqqqr6a5j3jGvXrll/9md/ZpWXl1t/8Rd/YQcM96X/5OTkWN/+9re/cn1nZ6cVFxdnFRYW2ss+//xzy+VyWf/xH/9xN4Z4T5o3b571zDPPBC37q7/6K2vZsmWWZXFfeosfIXWjra1NNTU1mj17tr0sJCREs2fPVlVVVT+O7N7m9/slSZGRkZKkmpoatbe3B92n8ePHKykpift0F2RnZ2vevHlBf/4S96U//exnP9PkyZO1ePFixcTE6OGHH9aPfvQje319fb18Pl/QvfF4PJo2bRr3pg898sgj+uCDD/Txxx9Lko4fP65Dhw5p7ty5krgvvTVo/zHHr+PKlSvq6OhQbGxs0PLY2FidOXOmn0Z1b+vs7NQLL7ygRx99VN/85jclST6fT06nUyNHjgzaNjY2Vj6frx9Gee94++23VVtbq2PHjt2yjvvSf86fP6/t27drzZo1evnll3Xs2DH93d/9nZxOp7Kysuw//+7+buPe9J21a9cqEAho/PjxGjJkiDo6OrRx40YtW7ZMkrgvvUTAwAjZ2dk6deqUDh061N9Duec1Njbq+eefV3l5ucLCwvp7OPgdnZ2dmjx5sv7pn/5JkvTwww/r1KlTKi4uVlZWVj+P7t71n//5n3rrrbf07//+75o4caK8Xq9eeOEFJSQkcF++Bn6E1I3o6GgNGTLklt+aaG5uVlxcXD+N6t713HPPqaysTPv379eoUaPs5XFxcWpra9Pnn38etD33qW/V1NTo0qVL+ta3vqXQ0FCFhobqV7/6lV577TWFhoYqNjaW+9JP4uPjNWHChKBl3/jGN9TQ0CBJ9p8/f7fdXS+++KLWrl2r733ve5o0aZKWL1+uv//7v1dBQYEk7ktvETDdcDqdSk1N1QcffGAv6+zs1AcffKC0tLR+HNm9xbIsPffcc9q9e7cqKio0ZsyYoPWpqam67777gu5TXV2dGhoauE99aNasWTp58qS8Xq89TZ48WcuWLbP/m/vSPx599NFbXjXw8ccfKzk5WZI0ZswYxcXFBd2bQCCgI0eOcG/60I0bNxQSEvxxO2TIEHV2dkrivvRafz9FPFC9/fbblsvlst544w3r17/+tbVq1Spr5MiRls/n6++h3TOeffZZy+PxWAcOHLA+/fRTe7px44a9zerVq62kpCSroqLCqq6uttLS0qy0tLR+HPW96Xd/C8myuC/95ejRo1ZoaKi1ceNG6+zZs9Zbb71lDRs2zPrpT39qb7Np0yZr5MiR1n/9139ZJ06csL773e/y67p9LCsry/rTP/1T+9eo33//fSs6Otp66aWX7G24Lz1HwPwBr7/+upWUlGQ5nU5r6tSp1kcffdTfQ7qnSOp22rlzp73NF198Yf3t3/6tFRERYQ0bNsz6y7/8S+vTTz/tv0Hfo34/YLgv/ee///u/rW9+85uWy+Wyxo8fb5WUlASt7+zstDZs2GDFxsZaLpfLmjVrllVXV9dPo703BAIB6/nnn7eSkpKssLAw6/7777fWrVtntba22ttwX3rOYVm/8ypAAAAAA/AMDAAAMA4BAwAAjEPAAAAA4xAwAADAOAQMAAAwDgEDAACMQ8AAAADjEDAAAMA4BAwAADAOAQMAAIxDwAAAAOMQMAAAwDj/D2c+oFWghdMnAAAAAElFTkSuQmCC",
      "text/plain": [
       "<Figure size 640x480 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "tai_inst = load_tai(20, 5)\n",
    "hh = SAGA(tai_inst[0],  variety_degree= 5)\n",
    "hps_trace, current_make_span_trace, loc_make_spane_star_trace, temp_trace = hh.optim(T_min=0.0001, trace=True)\n",
    "print('make_span_star', hh.make_span_star)\n",
    "plt.plot(range(1, len(current_make_span_trace)+1), current_make_span_trace)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Function to execute the neh, cds and palmer heuristics for comparison"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "def exec_heur(instances):\n",
    "    cds = []\n",
    "    palmer = []\n",
    "    neh = []\n",
    "    for instance in instances:\n",
    "        def get_instance(tai_inst:Inst):\n",
    "                jobs_list = []\n",
    "                for i in range(len(tai_inst.matrix[0])):\n",
    "                    jobs_list.append([])\n",
    "                    for j in range(len(tai_inst.matrix)):\n",
    "                        jobs_list[-1].append(tai_inst.matrix[j][i])\n",
    "                return jobs_list\n",
    "        jobs_list = get_instance(instance)\n",
    "        \n",
    "        cds.append(heuristics.cds_heuristic(np.array(jobs_list))[1])\n",
    "        \n",
    "        palmer.append(heuristics.Palmer(jobs_list).optim()[1])\n",
    "\n",
    "        neh.append(heuristics.NEH(instance)()[0])\n",
    "        \n",
    "    return cds, palmer, neh"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Function to execute simulated annealing alone for comparison (with hyper param tuning)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SimulatedAnnealing:\n",
    "    def __init__(self, tai_inst:Inst):\n",
    "        def get_instance(tai_inst:Inst):\n",
    "            jobs_list = []\n",
    "            for i in range(len(tai_inst.matrix[0])):\n",
    "                jobs_list.append([])\n",
    "                for j in range(len(tai_inst.matrix)):\n",
    "                    jobs_list[-1].append(tai_inst.matrix[j][i])\n",
    "            return jobs_list\n",
    "        self.tai_inst = tai_inst\n",
    "        self.jobs_list = get_instance(tai_inst)\n",
    "        self.nb_jobs = len(self.jobs_list)\n",
    "        self.nb_machines = len(self.jobs_list[0])\n",
    "        self.seq_star = None\n",
    "        self.make_span_star = None\n",
    "\n",
    "    # utility function that returns the gantt cumule based on a job execution times and a previous gantt cumule\n",
    "    def cumulate(self, job:list, previous_cumul=None):\n",
    "        res = [0] * len(job)\n",
    "\n",
    "        if(previous_cumul==None):\n",
    "            res[0] = job[0]\n",
    "            for i in range(1, len(job)):\n",
    "                res[i] = res[i-1] + job[i]\n",
    "        else:\n",
    "            res[0] = previous_cumul[0] + job[0]\n",
    "            for i in range(1, len(job)):\n",
    "                res[i] = max(res[i-1], previous_cumul[i]) + job[i]\n",
    "\n",
    "        return res\n",
    "\n",
    "    # utility function that computes the gantt cumule given only a job sequence (not used in the algorithm due to inneficiency\n",
    "    # dynamic programming with cumulate is used instead ...)\n",
    "    def cumulate_seq(self, seq:list):\n",
    "        cumulated = None\n",
    "        for i in seq:\n",
    "            cumulated = self.cumulate(self. jobs_list[i], cumulated)\n",
    "        return cumulated\n",
    "\n",
    "\n",
    "    #launching the optimization\n",
    "    def optim(self, debug=False, T=1.0, T_min=0.0001, alpha=0.9, nb_iter=10000, init_method='random', neigh_method='full', length_palier=1, jump_rate=0, jump_ratio=1.): \n",
    "        #making sure the jump ratio is not greater that the 1/alpha\n",
    "        if jump_rate != 0 and jump_ratio>=1/alpha:\n",
    "            raise Exception(\"Y_exception: jump_ratio >= 1/alpha\")\n",
    "        #initialize the current sequence and its make span\n",
    "        if init_method == 'random':\n",
    "            seq = np.random.choice(np.arange(0,self.nb_jobs), size=self.nb_jobs, replace=False)\n",
    "            make_span = self.cumulate_seq(seq)[-1]\n",
    "        elif init_method == 'palmer':\n",
    "            palmer = heuristics.Palmer(self.jobs_list)\n",
    "            seq, make_span = palmer.optim()\n",
    "        elif init_method == 'cds':\n",
    "            seq, make_span = heuristics.cds_heuristic(np.array(self.jobs_list))\n",
    "        else:#neh\n",
    "            make_span, seq = heuristics.NEH(self.tai_inst)()\n",
    "\n",
    "        #initialize the iteration counter\n",
    "        it = 1\n",
    "\n",
    "        #initialize the best sequence and its make span\n",
    "        self.seq_star = copy.deepcopy(seq)\n",
    "        self.make_span_star = make_span\n",
    "\n",
    "        #we initialize the temperature session at length_palier\n",
    "        temp_session = length_palier\n",
    "        #main loop\n",
    "        while T > T_min and it<=nb_iter:\n",
    "            #generate a random neighbour sequence\n",
    "            if neigh_method == 'full':\n",
    "                i, j = np.random.choice(np.arange(self.nb_jobs), size=2, replace=False)\n",
    "                seq_neigh = copy.deepcopy(seq)\n",
    "                seq_neigh[i], seq_neigh[j] = seq_neigh[j], seq_neigh[i]\n",
    "            else:#next\n",
    "                i = np.random.randint(0 , self.nb_jobs-1)\n",
    "                seq_neigh = copy.deepcopy(seq)\n",
    "                seq_neigh[i], seq_neigh[i+1] = seq_neigh[i+1], seq_neigh[i]\n",
    "                \n",
    "            #compute the make span of the neighbour sequence\n",
    "            make_span_neigh = self.cumulate_seq(seq_neigh)[-1]\n",
    "\n",
    "            #compute the energy difference\n",
    "            delta = make_span - make_span_neigh\n",
    "\n",
    "            #if the neighbour sequence is better, accept it\n",
    "            if delta > 0:\n",
    "                seq = copy.deepcopy(seq_neigh)\n",
    "                make_span = make_span_neigh\n",
    "                self.seq_star = copy.deepcopy(seq)\n",
    "                self.make_span_star = make_span\n",
    "\n",
    "            #if the neighbour sequence is worse, accept it with a probability that decreases with the temperature\n",
    "            else:\n",
    "                if random.random() < math.exp(delta/T):\n",
    "                    seq = copy.deepcopy(seq_neigh)\n",
    "                    make_span = make_span_neigh\n",
    "\n",
    "            #cooling\n",
    "            temp_session -= 1\n",
    "            if temp_session == 0:\n",
    "                if random.random() < jump_rate:\n",
    "                    T = T * jump_ratio\n",
    "                else:\n",
    "                    T = T * alpha\n",
    "                temp_session = length_palier\n",
    "\n",
    "            #incrementing it\n",
    "            it += 1\n",
    "            \n",
    "            #debug\n",
    "            if debug:\n",
    "                print(\"Iteration: \", it)\n",
    "                print(\"Temperature: \", T)\n",
    "                print(\"Sequence: \", seq)\n",
    "                print(\"Make span: \", make_span)\n",
    "            \n",
    "        return self.make_span_star, self.seq_star\n",
    "def exec_sa(instances, n_trials=10):\n",
    "\n",
    "    studies = []\n",
    "    optuna.logging.set_verbosity(optuna.logging.WARNING)\n",
    "\n",
    "    for i, instance in enumerate(instances):\n",
    "        study = optuna.create_study()\n",
    "        sa = SimulatedAnnealing(instance)\n",
    "        \n",
    "        def objective(trial):\n",
    "            T = trial.suggest_float(\"T\", 1, 10, step=1)\n",
    "            T_min = trial.suggest_categorical(\"T_min\", [0.001, 0.0001, 0.00001])\n",
    "            alpha = trial.suggest_float(\"alpha\", 0.5, 0.95, step=0.05)\n",
    "            nb_iter = trial.suggest_categorical(\"nb_iter\", [1000, 10000, 20000])\n",
    "            init_method = trial.suggest_categorical(\"init_method\", ['random', 'palmer', 'neh'])\n",
    "            neigh_method = trial.suggest_categorical(\"neigh_method\", ['full', 'next'])\n",
    "            length_palier = trial.suggest_categorical(\"length_palier\", [1, 5, 10, 20])\n",
    "            jump_rate = trial.suggest_categorical(\"jump_rate\", [0, 0.05, 0.1, 0.2])\n",
    "            jump_ratio = trial.suggest_categorical(\"jump_ratio\", [1.01, 1.03, 1.05])\n",
    "\n",
    "            return sa.optim(alpha=alpha, T=T, T_min=T_min, nb_iter=nb_iter, init_method=init_method, neigh_method=neigh_method, length_palier=length_palier, jump_rate=jump_rate, jump_ratio=jump_ratio)[0]\n",
    "\n",
    "        study.optimize(objective, n_trials, show_progress_bar=True)\n",
    "        studies.append(copy.deepcopy(study))\n",
    "\n",
    "    return studies"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Function to execute the genetic algorithm for comparison (with hyper param tuning)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "class GeneticAlgorithm:\n",
    "    def __init__(self, tai_inst: Inst):\n",
    "        # Initializes the Genetic Algorithm with a given instance of the scheduling problem.\n",
    "        \n",
    "        self.tai_inst = tai_inst\n",
    "        self.jobs_list = self.get_instance(tai_inst)\n",
    "        self.nb_jobs = len(self.jobs_list)\n",
    "        self.nb_machines = len(self.jobs_list[0])\n",
    "        self.seq_star = None\n",
    "        self.make_span_star = None\n",
    "\n",
    "        \n",
    "    def get_instance(self, tai_inst: Inst):\n",
    "        # Extract the jobs list from the given instance\n",
    "        \n",
    "        jobs_list = []\n",
    "        for i in range(len(tai_inst.matrix[0])):\n",
    "            jobs_list.append([])\n",
    "            for j in range(len(tai_inst.matrix)):\n",
    "                jobs_list[-1].append(tai_inst.matrix[j][i])\n",
    "        return jobs_list\n",
    "\n",
    "    \n",
    "    def cumulate(self, job: list, previous_cumul=None):\n",
    "        # Calculate the cumulative completion times for a job\n",
    "            \n",
    "        res = [0] * len(job)\n",
    "        if previous_cumul == None:\n",
    "            res[0] = job[0]\n",
    "            for i in range(1, len(job)):\n",
    "                res[i] = res[i - 1] + job[i]\n",
    "        else:\n",
    "            res[0] = previous_cumul[0] + job[0]\n",
    "            for i in range(1, len(job)):\n",
    "                res[i] = max(res[i - 1], previous_cumul[i]) + job[i]\n",
    "        return res\n",
    "\n",
    "    \n",
    "    def cumulate_seq(self, seq: list):\n",
    "        # Calculates the cumulative time for a sequence of jobs on machines.\n",
    "\n",
    "        cumulated = None\n",
    "        for i in seq:\n",
    "            cumulated = self.cumulate(self.jobs_list[i], cumulated)\n",
    "        return cumulated\n",
    "\n",
    "    \n",
    "    def evaluate_makespan(self, schedule):\n",
    "        # Evaluates the makespan (completion time) of a given schedule.\n",
    "\n",
    "        cumulative = self.cumulate_seq(schedule)\n",
    "        return cumulative[-1]\n",
    "\n",
    "    \n",
    "    def initialize_population(self, init_type, population_size):\n",
    "        \"\"\"\n",
    "        Initializes the population of individuals.\n",
    "        \n",
    "        Args:\n",
    "            init_type (str): Type of initialization method.\n",
    "            population_size (int): Size of the population.\n",
    "            \n",
    "        Returns:\n",
    "            list: Initialized population of individuals.\n",
    "        \"\"\"\n",
    "        \n",
    "        def perturb_sequence(sequence):\n",
    "            \"\"\"\n",
    "            Perturbs a sequence by swapping two random jobs.\n",
    "            \n",
    "            Args:\n",
    "                sequence (list): Sequence of jobs.\n",
    "                \n",
    "            Returns:\n",
    "                list: Perturbed sequence.\n",
    "            \"\"\"\n",
    "            perturbed_seq = sequence[:]\n",
    "            for _ in range(2):\n",
    "                i, j = random.sample(range(len(perturbed_seq)), 2)\n",
    "                perturbed_seq[i], perturbed_seq[j] = perturbed_seq[j], perturbed_seq[i]\n",
    "            return perturbed_seq\n",
    "\n",
    "        population = []\n",
    "        \n",
    "        if init_type == \"cds\":\n",
    "            cds_seq, _ = heuristics.cds_heuristic(np.array(self.jobs_list))\n",
    "            population.append(cds_seq)\n",
    "            for _ in range(population_size - 1):\n",
    "                perturbed_seq = perturb_sequence(cds_seq)\n",
    "                population.append(perturbed_seq)\n",
    "\n",
    "        elif init_type == \"palmer\":\n",
    "            palmer_seq, _ = heuristics.Palmer(self.jobs_list).optim()\n",
    "            population.append(palmer_seq)\n",
    "            for _ in range(population_size - 1):\n",
    "                perturbed_seq = perturb_sequence(palmer_seq)\n",
    "                population.append(perturbed_seq)\n",
    "\n",
    "        elif init_type == \"neh\":\n",
    "            _, neh_seq = heuristics.NEH(self.tai_inst)()\n",
    "            population.append(neh_seq)\n",
    "            for _ in range(population_size - 1):\n",
    "                perturbed_seq = perturb_sequence(neh_seq)\n",
    "                population.append(perturbed_seq)\n",
    "\n",
    "        elif init_type == \"heuristics\":\n",
    "            cds_size = population_size // 3\n",
    "            palmer_size = population_size // 3\n",
    "            neh_size = population_size - cds_size - palmer_size\n",
    "            \n",
    "            for _ in range(cds_size):\n",
    "                cds_seq, _ = heuristics.cds_heuristic(np.array(self.jobs_list))\n",
    "                population.append(perturb_sequence(cds_seq))\n",
    "            \n",
    "            for _ in range(palmer_size):\n",
    "                palmer_seq, _ = heuristics.Palmer(self.jobs_list).optim()\n",
    "                population.append(perturb_sequence(palmer_seq))\n",
    "            \n",
    "            for _ in range(neh_size):\n",
    "                _, neh_seq = heuristics.NEH(self.tai_inst)()\n",
    "                population.append(perturb_sequence(neh_seq))\n",
    "\n",
    "        elif init_type == \"heuristics_random\":\n",
    "\n",
    "            cds_seq, _ = heuristics.cds_heuristic(np.array(self.jobs_list))\n",
    "            population.append(perturb_sequence(cds_seq))\n",
    "\n",
    "            palmer_seq, _ = heuristics.Palmer(self.jobs_list).optim()\n",
    "            population.append(perturb_sequence(palmer_seq))\n",
    "\n",
    "            _, neh_seq = heuristics.NEH(self.tai_inst)()\n",
    "            population.append(perturb_sequence(neh_seq))\n",
    "\n",
    "            for _ in range(population_size - 3):\n",
    "                random_seq = random.sample(range(self.nb_jobs), self.nb_jobs)\n",
    "                population.append(random_seq)\n",
    "\n",
    "        elif init_type == \"full_random\":\n",
    "\n",
    "            for _ in range(population_size):\n",
    "                random_seq = random.sample(range(self.nb_jobs), self.nb_jobs)\n",
    "                population.append(random_seq)\n",
    "\n",
    "        else:\n",
    "            raise ValueError(\"Invalid initialization type\")\n",
    "\n",
    "        return population\n",
    "\n",
    "    \n",
    "    def select_parents(self, population):\n",
    "        \"\"\"\n",
    "        Selects parents from the population using tournament selection.\n",
    "        \n",
    "        Args:\n",
    "            population (list): Population of individuals.\n",
    "            \n",
    "        Returns:\n",
    "            tuple: Pair of selected parents.\n",
    "        \"\"\"\n",
    "        tournament = random.sample(population, 3)\n",
    "        tournament.sort(key=lambda x: self.evaluate_makespan(x))\n",
    "        return tournament[0], tournament[1]\n",
    "\n",
    "    \n",
    "    def crossover(self, crossover_type, parent1, parent2, crossover_rate, k_points=None):\n",
    "        \"\"\"\n",
    "        Performs crossover between two parents to produce offspring.\n",
    "        \n",
    "        Args:\n",
    "            crossover_type (str): Type of crossover operation.\n",
    "            parent1 (list): First parent.\n",
    "            parent2 (list): Second parent.\n",
    "            crossover_rate (float): Rate of crossover.\n",
    "            k (int, optional): Parameter for k-point crossover. Defaults to None.\n",
    "            \n",
    "        Returns:\n",
    "            tuple: Pair of offspring.\n",
    "        \"\"\"\n",
    "\n",
    "        def ensure_each_job_once(offspring):\n",
    "            \"\"\"\n",
    "            Ensures each job appears exactly once in the offspring.\n",
    "            \n",
    "            Args:\n",
    "                offspring (list): Offspring sequence.\n",
    "            \"\"\"\n",
    "            # Ensure offspring contains each job exactly once\n",
    "            job_count = {job: 0 for job in range(self.nb_jobs)}\n",
    "            for job in offspring:\n",
    "                job_count[job] += 1\n",
    "            for i, job in enumerate(offspring):\n",
    "                if job_count[job] > 1:\n",
    "                    for swap_job, count in job_count.items():\n",
    "                        if count == 0:\n",
    "                            offspring[i] = swap_job\n",
    "                            job_count[swap_job] += 1\n",
    "                            job_count[job] -= 1\n",
    "                            break\n",
    "\n",
    "        if random.random() < crossover_rate:\n",
    "            \n",
    "            if crossover_type == 'uniform':\n",
    "                k = None\n",
    "                mask = [random.choice([0, 1]) for _ in range(len(parent1))]\n",
    "                offspring1 = [gene1 if bit else gene2 for gene1, gene2, bit in zip(parent1, parent2, mask)]\n",
    "                offspring2 = [gene1 if bit else gene2 for gene1, gene2, bit in zip(parent2, parent1, mask)]\n",
    "\n",
    "            else:\n",
    "                if k_points is None or k_points < 1:\n",
    "                    raise ValueError(\"k must be >= 1 for one_point, two_points, and k_points crossovers\")\n",
    "                \n",
    "                if k_points is not None and k_points >= self.nb_jobs:\n",
    "                    raise ValueError(\"k in crossover must be less than the number of jobs\")\n",
    "\n",
    "                if ((crossover_type == 'one_point') or (k_points == 1)):\n",
    "                    k = 1\n",
    "                    points = [random.randint(1, len(parent1) - 1)]\n",
    "\n",
    "                elif ((crossover_type == 'two_points') or (k_points == 2)):\n",
    "                    k = 2\n",
    "                    points = sorted(random.sample(range(1, len(parent1)), 2))\n",
    "\n",
    "                elif crossover_type == 'k_points':\n",
    "                    points = sorted(random.sample(range(1, len(parent1)), k_points))\n",
    "\n",
    "                else:\n",
    "                    raise ValueError(\"Invalid crossover type\")\n",
    "\n",
    "                offspring1, offspring2 = parent1[:], parent2[:]\n",
    "                switch = False\n",
    "                for i in range(len(parent1)):\n",
    "                    if i in points:\n",
    "                        switch = not switch\n",
    "                    if switch:\n",
    "                        offspring1[i], offspring2[i] = offspring2[i], offspring1[i]\n",
    "\n",
    "            ensure_each_job_once(offspring1)\n",
    "            ensure_each_job_once(offspring2)\n",
    "            return offspring1, offspring2\n",
    "        \n",
    "        else:\n",
    "            return parent1[:], parent2[:]\n",
    "\n",
    "\n",
    "    def mutate(self, solution, mutation_rate):\n",
    "        \"\"\"\n",
    "        Mutates a solution with a given mutation rate.\n",
    "        \n",
    "        Args:\n",
    "            solution (list): Solution to mutate.\n",
    "            mutation_rate (float): Rate of mutation.\n",
    "            \n",
    "        Returns:\n",
    "            list: Mutated solution.\n",
    "        \"\"\"\n",
    "        if random.random() < mutation_rate:\n",
    "            i, j = random.sample(range(len(solution)), 2)\n",
    "            solution[i], solution[j] = solution[j], solution[i]\n",
    "        return solution\n",
    "\n",
    "\n",
    "    def select_reproduction_pool(self, selection_type, population, pool_size):\n",
    "        \"\"\"\n",
    "        Selects a pool of individuals for reproduction.\n",
    "        \n",
    "        Args:\n",
    "            selection_type (str): Type of selection method.\n",
    "            population (list): Population of individuals.\n",
    "            pool_size (int): Size of the pool.\n",
    "            \n",
    "        Returns:\n",
    "            list: Pool of selected individuals.\n",
    "        \"\"\"\n",
    "        \n",
    "        chosen = []\n",
    "\n",
    "        if selection_type == \"roulette\":\n",
    "            total_fitness = sum(self.evaluate_makespan(ind) for ind in population)\n",
    "            selection_probs = [self.evaluate_makespan(ind) / total_fitness for ind in population]\n",
    "            chosen = random.choices(population, weights=selection_probs, k=pool_size)\n",
    "\n",
    "        elif selection_type == \"rank\":\n",
    "            population_sorted = sorted(population, key=self.evaluate_makespan)\n",
    "            ranks = range(1, len(population_sorted) + 1)\n",
    "            total_rank = sum(ranks)\n",
    "            rank_weights = [rank / total_rank for rank in ranks]\n",
    "            chosen = random.choices(population_sorted, weights=rank_weights, k=pool_size)\n",
    "\n",
    "        elif selection_type == \"elitist\":\n",
    "            population_sorted = sorted(population, key=self.evaluate_makespan)\n",
    "            chosen = population_sorted[:pool_size]\n",
    "\n",
    "        elif selection_type == \"tournament\":\n",
    "            for _ in range(pool_size):\n",
    "                contenders = random.sample(population, 3)\n",
    "                chosen.append(min(contenders, key=self.evaluate_makespan))\n",
    "\n",
    "        elif selection_type == \"random\":\n",
    "            chosen = random.sample(population, pool_size)\n",
    "            \n",
    "        else:\n",
    "            raise ValueError(\"Invalid type\")\n",
    "\n",
    "        return chosen\n",
    "\n",
    "    \n",
    "    def replace_population(self, replacement_type, population, parents, offspring, population_size):\n",
    "        \"\"\"\n",
    "        Replaces the population with new individuals.\n",
    "        \n",
    "        Args:\n",
    "            replacement_type (str): Type of replacement method.\n",
    "            population (list): Current population.\n",
    "            parents (list): Parents generated during reproduction.\n",
    "            offspring (list): Offspring generated during reproduction.\n",
    "            population_size (int): Size of the population.\n",
    "            \n",
    "        Returns:\n",
    "            list: New population.\n",
    "        \"\"\"\n",
    "        \n",
    "        def select_population(selection_type, population, pool_size):\n",
    "            \"\"\"\n",
    "            Selects individuals for the next population.\n",
    "            \n",
    "            Args:\n",
    "                selection_type (str): Type of selection method.\n",
    "                population (list): Population of individuals.\n",
    "                pool_size (int): Size of the selection pool.\n",
    "                \n",
    "            Returns:\n",
    "                list: Selected individuals for the next population.\n",
    "            \"\"\"\n",
    "            return self.select_reproduction_pool(selection_type, population, pool_size)\n",
    "\n",
    "        if replacement_type == \"best_all\":\n",
    "            combined_population = population + offspring\n",
    "            combined_population.sort(key=lambda x: self.evaluate_makespan(x))\n",
    "            return combined_population[:population_size]\n",
    "\n",
    "        elif replacement_type == \"parents_replaced_by_offspring\":\n",
    "            population_without_parents = [ind for ind in population if ind not in parents]\n",
    "            return population_without_parents + offspring\n",
    "\n",
    "        elif replacement_type == \"worst_population_replaced_by_offspring\":\n",
    "            population_sorted = sorted(population, key=self.evaluate_makespan)\n",
    "            population_without_worst = population_sorted[:-len(offspring)]\n",
    "            return population_without_worst + offspring\n",
    "\n",
    "        elif replacement_type == \"best_between_parents_and_offspring\":\n",
    "            population_without_parents = [ind for ind in population if ind not in parents]\n",
    "            combined_sub_population = sorted(parents + offspring, key=self.evaluate_makespan)\n",
    "            return population_without_parents + combined_sub_population[:len(parents)]\n",
    "        \n",
    "        else:\n",
    "            return select_population(replacement_type, population + offspring, len(population))\n",
    "    \n",
    "\n",
    "    def genetic_algorithm(self, init_type, selection_type, crossover_type, replacement_type, population_size, pool_size, crossover_rate, mutation_rate, num_iterations, max_stagnation, k_points=None):\n",
    "        \"\"\"\n",
    "        Executes the Genetic Algorithm to find the best solution.\n",
    "        \n",
    "        Args:\n",
    "            init_type (str): Type of initialization method.\n",
    "            selection_type (str): Type of parent selection method.\n",
    "            crossover_type (str): Type of crossover method.\n",
    "            replacement_type (str): Type of population replacement method.\n",
    "            population_size (int): Size of the population.\n",
    "            pool_size (int): Size of the reproduction pool.\n",
    "            crossover_rate (float): Rate of crossover.\n",
    "            mutation_rate (float): Rate of mutation.\n",
    "            num_iterations (int): Maximum number of iterations.\n",
    "            max_stagnation (int): Maximum number of iterations without improvement.\n",
    "            k_points (int, optional): Parameter for k-point crossover. Defaults to None.\n",
    "            \n",
    "        Returns:\n",
    "            tuple: Best solution and its makespan.\n",
    "        \"\"\"\n",
    "        \n",
    "        if pool_size > population_size:\n",
    "            raise ValueError(\"Pool size must be less than population size.\")\n",
    "\n",
    "        population = self.initialize_population(init_type, population_size)\n",
    "        population.sort(key=lambda x: self.evaluate_makespan(x))\n",
    "        \n",
    "        best_solution = population[0]\n",
    "        best_solution_fitness = self.evaluate_makespan(best_solution)\n",
    "        stagnation_count = 0\n",
    "\n",
    "        for i in range(num_iterations):\n",
    "            reproduction_pool = self.select_reproduction_pool(selection_type, population, pool_size)\n",
    "            offspring = []\n",
    "            parents = []\n",
    "\n",
    "            for _ in range(pool_size // 2):\n",
    "                parent1, parent2 = self.select_parents(reproduction_pool)\n",
    "                parents.extend([parent1, parent2])\n",
    "                child1, child2 = self.crossover(crossover_type, parent1, parent2, crossover_rate, k_points) \n",
    "                child1 = self.mutate(child1, mutation_rate)\n",
    "                child2 = self.mutate(child2, mutation_rate)\n",
    "                offspring.extend([child1, child2])\n",
    "\n",
    "            population = self.replace_population(replacement_type, population, parents, offspring, population_size)\n",
    "            population.sort(key=lambda x: self.evaluate_makespan(x))\n",
    "\n",
    "            current_best_solution = population[0]\n",
    "            current_best_solution_fitness = self.evaluate_makespan(current_best_solution)\n",
    "\n",
    "            if current_best_solution_fitness < best_solution_fitness:\n",
    "                best_solution = current_best_solution\n",
    "                best_solution_fitness = current_best_solution_fitness\n",
    "                stagnation_count = 0\n",
    "            else:\n",
    "                stagnation_count += 1\n",
    "\n",
    "            if max_stagnation is not None and stagnation_count >= max_stagnation:\n",
    "                break\n",
    "\n",
    "        return best_solution\n",
    "\n",
    "    \n",
    "    def fit(self, \n",
    "            init_type = 'heuristics', \n",
    "            selection_type = 'random', \n",
    "            crossover_type = 'one_point', \n",
    "            replacement_type = 'best_all', \n",
    "            population_size = 20, \n",
    "            pool_size = 15, \n",
    "            crossover_rate = 0.8, \n",
    "            mutation_rate = 0.1, \n",
    "            num_iterations = 200,\n",
    "            max_stagnation = 10,\n",
    "            k_points = 1\n",
    "            ):\n",
    "        \n",
    "        self.seq_star = self.genetic_algorithm(init_type, selection_type, crossover_type, replacement_type, population_size, pool_size, crossover_rate, mutation_rate, num_iterations, max_stagnation, k_points)\n",
    "        self.make_span_star = self.evaluate_makespan(self.seq_star)\n",
    "        return self.make_span_star, self.seq_star\n",
    "def exec_ga(instances, n_trials=10):\n",
    "\n",
    "    studies = []\n",
    "    optuna.logging.set_verbosity(optuna.logging.WARNING)\n",
    "\n",
    "    for i, instance in enumerate(instances):\n",
    "        study = optuna.create_study()\n",
    "        ga = GeneticAlgorithm(instance)\n",
    "\n",
    "        def objective(trial):\n",
    "            init_type = trial.suggest_categorical(\"init_type\", ['cds', 'palmer', 'neh', 'heuristics', 'heuristics_random', 'full_random'])\n",
    "            selection_type = trial.suggest_categorical(\"selection_type\", ['roulette', 'rank', 'elitist', 'tournament', 'random'])\n",
    "            crossover_type = trial.suggest_categorical(\"crossover_type\", ['uniform', 'one_point', 'two_points', 'k_points'])\n",
    "            replacement_type = trial.suggest_categorical(\"replacement_type\", ['best_all', 'parents_replaced_by_offspring', 'worst_population_replaced_by_offspring', 'best_between_parents_and_offspring', 'roulette', 'rank', 'elitist', 'tournament', 'random'])     \n",
    "            population_size = trial.suggest_int(\"population_size\", 20, 50, step=10)\n",
    "            pool_size = trial.suggest_int(\"pool_size\", 10, 20, step=5)\n",
    "            crossover_rate = trial.suggest_float(\"crossover_rate\", 0.1, 0.9, step=0.1)\n",
    "            mutation_rate = trial.suggest_float(\"mutation_rate\", 0.1, 0.9, step=0.1)\n",
    "            num_iterations = trial.suggest_int(\"num_iterations\", 200, 1000, step=100)\n",
    "            max_stagnation = trial.suggest_int(\"max_stagnation\", 50, 200, step=50)\n",
    "            k_points = trial.suggest_int(\"k_points\", 1, 3, step=1)\n",
    "\n",
    "            return ga.fit(init_type, selection_type, crossover_type, replacement_type, population_size, pool_size, crossover_rate, mutation_rate, num_iterations, max_stagnation, k_points)[0]\n",
    "\n",
    "        study.optimize(objective, n_trials=n_trials, show_progress_bar=True)\n",
    "\n",
    "        studies.append(copy.deepcopy(study))\n",
    "    \n",
    "    return studies"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Function to compare the results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "css = [\n",
    "        {'selector': '', 'props': [('min-width', '110px')]},\n",
    "        {'selector': 'th', 'props': [('min-width', '110px')]}\n",
    "      ]\n",
    "\n",
    "def compare(instances, study_lsaga, study_ga, study_sa, cds, palmer, neh):\n",
    "\n",
    "    def highlight(s):\n",
    "        is_min = s == s.min()\n",
    "        is_max = s == s.max()\n",
    "        return ['color: green; font-weight: bold' if v else 'color: red; font-weight: bold' if w else '' for v, w in zip(is_min, is_max)]\n",
    "\n",
    "\n",
    "    # Define the data\n",
    "    instance_names = [f\"Instance {i+1}\" for i in range(len(instances))]\n",
    "\n",
    "    data = {\n",
    "                'SAGA' : study_lsaga,\n",
    "                'Genetic Algorithm' : [int(study.best_value) for study in study_ga],\n",
    "                'Simmulated annealing' : [int(study.best_value) for study in study_sa],\n",
    "                'CDS': cds,\n",
    "                'Palmer': palmer,\n",
    "                'NEH': neh,\n",
    "                'Upper bound': [instance.ub for instance in instances]\n",
    "           }\n",
    "\n",
    "    df = pd.DataFrame(data)\n",
    "    df.index = instance_names\n",
    "    styled_df = df.style.apply(highlight, axis=1, subset=df.columns[:-1])\n",
    "    return styled_df.set_table_styles(css)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Empirical Study\n",
    "\n",
    "In this section we will present the empirical and comparative study of our method only for the first 5 taillard configurations due to unfortunate time limitations on our side when preparing this study (the rest will be available on the drive)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Temperature 0.00515377520732012:  10%|█         | 50/500 [01:18<11:43,  1.56s/it] \n",
      "Temperature 0.00515377520732012:  10%|█         | 50/500 [00:55<08:15,  1.10s/it] \n",
      "Temperature 0.00515377520732012:  10%|█         | 50/500 [00:50<07:34,  1.01s/it] \n",
      "Temperature 0.00515377520732012:  10%|█         | 50/500 [01:00<09:01,  1.20s/it] \n",
      "Temperature 0.00515377520732012:  10%|█         | 50/500 [01:43<15:27,  2.06s/it] \n",
      "Temperature 0.00515377520732012:  10%|█         | 50/500 [00:23<03:34,  2.10it/s] \n",
      "Temperature 0.00515377520732012:  10%|█         | 50/500 [01:44<15:41,  2.09s/it]   \n",
      "Temperature 0.00515377520732012:  10%|█         | 50/500 [00:52<07:52,  1.05s/it] \n",
      "Temperature 0.00515377520732012:  10%|█         | 50/500 [00:42<06:22,  1.18it/s] \n",
      "Temperature 0.00515377520732012:  10%|█         | 50/500 [00:57<08:40,  1.16s/it] \n"
     ]
    }
   ],
   "source": [
    "instances_20_5 = load_tai(20,5)\n",
    "makes_spans_20_5 = []\n",
    "for instance in instances_20_5:\n",
    "    saga = SAGA(instance, variety_degree=4)\n",
    "    saga.optim(T_min=0.005)\n",
    "    makes_spans_20_5.append(saga.make_span_star)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "executing heursitics\n",
      "tuning simulated annealing\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Best trial: 0. Best value: 1286: 100%|██████████| 10/10 [00:00<00:00, 25.52it/s]\n",
      "Best trial: 1. Best value: 1377: 100%|██████████| 10/10 [00:00<00:00, 41.74it/s]\n",
      "Best trial: 6. Best value: 1122: 100%|██████████| 10/10 [00:00<00:00, 47.46it/s]\n",
      "Best trial: 5. Best value: 1331: 100%|██████████| 10/10 [00:00<00:00, 82.96it/s]\n",
      "Best trial: 1. Best value: 1252: 100%|██████████| 10/10 [00:00<00:00, 52.04it/s]\n",
      "Best trial: 2. Best value: 1224: 100%|██████████| 10/10 [00:00<00:00, 67.99it/s]\n",
      "Best trial: 2. Best value: 1251: 100%|██████████| 10/10 [00:00<00:00, 35.55it/s]\n",
      "Best trial: 3. Best value: 1206: 100%|██████████| 10/10 [00:00<00:00, 21.49it/s]\n",
      "Best trial: 7. Best value: 1257: 100%|██████████| 10/10 [00:00<00:00, 36.06it/s]\n",
      "Best trial: 1. Best value: 1136: 100%|██████████| 10/10 [00:00<00:00, 66.10it/s]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "tuning genetic algorithm\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Best trial: 0. Best value: 1297: 100%|██████████| 10/10 [00:06<00:00,  1.46it/s]\n",
      "Best trial: 2. Best value: 1366: 100%|██████████| 10/10 [00:08<00:00,  1.12it/s]\n",
      "Best trial: 0. Best value: 1098: 100%|██████████| 10/10 [00:06<00:00,  1.60it/s]\n",
      "Best trial: 9. Best value: 1323: 100%|██████████| 10/10 [00:10<00:00,  1.02s/it]\n",
      "Best trial: 9. Best value: 1250: 100%|██████████| 10/10 [00:13<00:00,  1.37s/it]\n",
      "Best trial: 5. Best value: 1210: 100%|██████████| 10/10 [00:05<00:00,  1.67it/s]\n",
      "Best trial: 9. Best value: 1251: 100%|██████████| 10/10 [00:04<00:00,  2.03it/s]\n",
      "Best trial: 1. Best value: 1213: 100%|██████████| 10/10 [00:36<00:00,  3.64s/it]\n",
      "Best trial: 4. Best value: 1255: 100%|██████████| 10/10 [00:09<00:00,  1.02it/s]\n",
      "Best trial: 0. Best value: 1122: 100%|██████████| 10/10 [00:10<00:00,  1.01s/it]\n"
     ]
    }
   ],
   "source": [
    "print(\"executing heursitics\")\n",
    "cds, palmer, neh = exec_heur(instances_20_5)\n",
    "print(\"tuning simulated annealing\")\n",
    "study_sa = exec_sa(instances_20_5)\n",
    "print(\"tuning genetic algorithm\")\n",
    "study_ga = exec_ga(instances_20_5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style type=\"text/css\">\n",
       "#T_e6067  {\n",
       "  min-width: 110px;\n",
       "}\n",
       "#T_e6067 th {\n",
       "  min-width: 110px;\n",
       "}\n",
       "#T_e6067_row0_col0, #T_e6067_row1_col0, #T_e6067_row1_col1, #T_e6067_row2_col0, #T_e6067_row2_col1, #T_e6067_row3_col0, #T_e6067_row4_col0, #T_e6067_row5_col0, #T_e6067_row5_col1, #T_e6067_row6_col0, #T_e6067_row6_col1, #T_e6067_row6_col2, #T_e6067_row7_col0, #T_e6067_row7_col2, #T_e6067_row8_col0, #T_e6067_row9_col0 {\n",
       "  color: green;\n",
       "  font-weight: bold;\n",
       "}\n",
       "#T_e6067_row0_col3, #T_e6067_row1_col4, #T_e6067_row2_col3, #T_e6067_row3_col4, #T_e6067_row4_col4, #T_e6067_row5_col4, #T_e6067_row6_col4, #T_e6067_row7_col3, #T_e6067_row8_col4, #T_e6067_row9_col4 {\n",
       "  color: red;\n",
       "  font-weight: bold;\n",
       "}\n",
       "</style>\n",
       "<table id=\"T_e6067\">\n",
       "  <thead>\n",
       "    <tr>\n",
       "      <th class=\"blank level0\" >&nbsp;</th>\n",
       "      <th id=\"T_e6067_level0_col0\" class=\"col_heading level0 col0\" >SAGA</th>\n",
       "      <th id=\"T_e6067_level0_col1\" class=\"col_heading level0 col1\" >Genetic Algorithm</th>\n",
       "      <th id=\"T_e6067_level0_col2\" class=\"col_heading level0 col2\" >Simmulated annealing</th>\n",
       "      <th id=\"T_e6067_level0_col3\" class=\"col_heading level0 col3\" >CDS</th>\n",
       "      <th id=\"T_e6067_level0_col4\" class=\"col_heading level0 col4\" >Palmer</th>\n",
       "      <th id=\"T_e6067_level0_col5\" class=\"col_heading level0 col5\" >NEH</th>\n",
       "      <th id=\"T_e6067_level0_col6\" class=\"col_heading level0 col6\" >Upper bound</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th id=\"T_e6067_level0_row0\" class=\"row_heading level0 row0\" >Instance 1</th>\n",
       "      <td id=\"T_e6067_row0_col0\" class=\"data row0 col0\" >1283</td>\n",
       "      <td id=\"T_e6067_row0_col1\" class=\"data row0 col1\" >1297</td>\n",
       "      <td id=\"T_e6067_row0_col2\" class=\"data row0 col2\" >1286</td>\n",
       "      <td id=\"T_e6067_row0_col3\" class=\"data row0 col3\" >1422</td>\n",
       "      <td id=\"T_e6067_row0_col4\" class=\"data row0 col4\" >1384</td>\n",
       "      <td id=\"T_e6067_row0_col5\" class=\"data row0 col5\" >1334</td>\n",
       "      <td id=\"T_e6067_row0_col6\" class=\"data row0 col6\" >1278</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_e6067_level0_row1\" class=\"row_heading level0 row1\" >Instance 2</th>\n",
       "      <td id=\"T_e6067_row1_col0\" class=\"data row1 col0\" >1366</td>\n",
       "      <td id=\"T_e6067_row1_col1\" class=\"data row1 col1\" >1366</td>\n",
       "      <td id=\"T_e6067_row1_col2\" class=\"data row1 col2\" >1377</td>\n",
       "      <td id=\"T_e6067_row1_col3\" class=\"data row1 col3\" >1424</td>\n",
       "      <td id=\"T_e6067_row1_col4\" class=\"data row1 col4\" >1439</td>\n",
       "      <td id=\"T_e6067_row1_col5\" class=\"data row1 col5\" >1377</td>\n",
       "      <td id=\"T_e6067_row1_col6\" class=\"data row1 col6\" >1359</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_e6067_level0_row2\" class=\"row_heading level0 row2\" >Instance 3</th>\n",
       "      <td id=\"T_e6067_row2_col0\" class=\"data row2 col0\" >1098</td>\n",
       "      <td id=\"T_e6067_row2_col1\" class=\"data row2 col1\" >1098</td>\n",
       "      <td id=\"T_e6067_row2_col2\" class=\"data row2 col2\" >1122</td>\n",
       "      <td id=\"T_e6067_row2_col3\" class=\"data row2 col3\" >1255</td>\n",
       "      <td id=\"T_e6067_row2_col4\" class=\"data row2 col4\" >1162</td>\n",
       "      <td id=\"T_e6067_row2_col5\" class=\"data row2 col5\" >1157</td>\n",
       "      <td id=\"T_e6067_row2_col6\" class=\"data row2 col6\" >1081</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_e6067_level0_row3\" class=\"row_heading level0 row3\" >Instance 4</th>\n",
       "      <td id=\"T_e6067_row3_col0\" class=\"data row3 col0\" >1302</td>\n",
       "      <td id=\"T_e6067_row3_col1\" class=\"data row3 col1\" >1323</td>\n",
       "      <td id=\"T_e6067_row3_col2\" class=\"data row3 col2\" >1331</td>\n",
       "      <td id=\"T_e6067_row3_col3\" class=\"data row3 col3\" >1418</td>\n",
       "      <td id=\"T_e6067_row3_col4\" class=\"data row3 col4\" >1420</td>\n",
       "      <td id=\"T_e6067_row3_col5\" class=\"data row3 col5\" >1402</td>\n",
       "      <td id=\"T_e6067_row3_col6\" class=\"data row3 col6\" >1293</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_e6067_level0_row4\" class=\"row_heading level0 row4\" >Instance 5</th>\n",
       "      <td id=\"T_e6067_row4_col0\" class=\"data row4 col0\" >1248</td>\n",
       "      <td id=\"T_e6067_row4_col1\" class=\"data row4 col1\" >1250</td>\n",
       "      <td id=\"T_e6067_row4_col2\" class=\"data row4 col2\" >1252</td>\n",
       "      <td id=\"T_e6067_row4_col3\" class=\"data row4 col3\" >1323</td>\n",
       "      <td id=\"T_e6067_row4_col4\" class=\"data row4 col4\" >1360</td>\n",
       "      <td id=\"T_e6067_row4_col5\" class=\"data row4 col5\" >1319</td>\n",
       "      <td id=\"T_e6067_row4_col6\" class=\"data row4 col6\" >1236</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_e6067_level0_row5\" class=\"row_heading level0 row5\" >Instance 6</th>\n",
       "      <td id=\"T_e6067_row5_col0\" class=\"data row5 col0\" >1210</td>\n",
       "      <td id=\"T_e6067_row5_col1\" class=\"data row5 col1\" >1210</td>\n",
       "      <td id=\"T_e6067_row5_col2\" class=\"data row5 col2\" >1224</td>\n",
       "      <td id=\"T_e6067_row5_col3\" class=\"data row5 col3\" >1312</td>\n",
       "      <td id=\"T_e6067_row5_col4\" class=\"data row5 col4\" >1344</td>\n",
       "      <td id=\"T_e6067_row5_col5\" class=\"data row5 col5\" >1342</td>\n",
       "      <td id=\"T_e6067_row5_col6\" class=\"data row5 col6\" >1195</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_e6067_level0_row6\" class=\"row_heading level0 row6\" >Instance 7</th>\n",
       "      <td id=\"T_e6067_row6_col0\" class=\"data row6 col0\" >1251</td>\n",
       "      <td id=\"T_e6067_row6_col1\" class=\"data row6 col1\" >1251</td>\n",
       "      <td id=\"T_e6067_row6_col2\" class=\"data row6 col2\" >1251</td>\n",
       "      <td id=\"T_e6067_row6_col3\" class=\"data row6 col3\" >1393</td>\n",
       "      <td id=\"T_e6067_row6_col4\" class=\"data row6 col4\" >1400</td>\n",
       "      <td id=\"T_e6067_row6_col5\" class=\"data row6 col5\" >1268</td>\n",
       "      <td id=\"T_e6067_row6_col6\" class=\"data row6 col6\" >1239</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_e6067_level0_row7\" class=\"row_heading level0 row7\" >Instance 8</th>\n",
       "      <td id=\"T_e6067_row7_col0\" class=\"data row7 col0\" >1206</td>\n",
       "      <td id=\"T_e6067_row7_col1\" class=\"data row7 col1\" >1213</td>\n",
       "      <td id=\"T_e6067_row7_col2\" class=\"data row7 col2\" >1206</td>\n",
       "      <td id=\"T_e6067_row7_col3\" class=\"data row7 col3\" >1345</td>\n",
       "      <td id=\"T_e6067_row7_col4\" class=\"data row7 col4\" >1290</td>\n",
       "      <td id=\"T_e6067_row7_col5\" class=\"data row7 col5\" >1262</td>\n",
       "      <td id=\"T_e6067_row7_col6\" class=\"data row7 col6\" >1206</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_e6067_level0_row8\" class=\"row_heading level0 row8\" >Instance 9</th>\n",
       "      <td id=\"T_e6067_row8_col0\" class=\"data row8 col0\" >1244</td>\n",
       "      <td id=\"T_e6067_row8_col1\" class=\"data row8 col1\" >1255</td>\n",
       "      <td id=\"T_e6067_row8_col2\" class=\"data row8 col2\" >1257</td>\n",
       "      <td id=\"T_e6067_row8_col3\" class=\"data row8 col3\" >1360</td>\n",
       "      <td id=\"T_e6067_row8_col4\" class=\"data row8 col4\" >1426</td>\n",
       "      <td id=\"T_e6067_row8_col5\" class=\"data row8 col5\" >1346</td>\n",
       "      <td id=\"T_e6067_row8_col6\" class=\"data row8 col6\" >1230</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_e6067_level0_row9\" class=\"row_heading level0 row9\" >Instance 10</th>\n",
       "      <td id=\"T_e6067_row9_col0\" class=\"data row9 col0\" >1121</td>\n",
       "      <td id=\"T_e6067_row9_col1\" class=\"data row9 col1\" >1122</td>\n",
       "      <td id=\"T_e6067_row9_col2\" class=\"data row9 col2\" >1136</td>\n",
       "      <td id=\"T_e6067_row9_col3\" class=\"data row9 col3\" >1164</td>\n",
       "      <td id=\"T_e6067_row9_col4\" class=\"data row9 col4\" >1229</td>\n",
       "      <td id=\"T_e6067_row9_col5\" class=\"data row9 col5\" >1227</td>\n",
       "      <td id=\"T_e6067_row9_col6\" class=\"data row9 col6\" >1108</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n"
      ],
      "text/plain": [
       "<pandas.io.formats.style.Styler at 0x129cd731910>"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "compare(instances_20_5, makes_spans_20_5, study_ga, study_sa, cds, palmer, neh)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [00:49<08:45,  1.15s/it] \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [01:43<18:18,  2.40s/it]  \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [01:59<21:05,  2.77s/it] \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [02:35<27:35,  3.62s/it]   \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [01:22<14:41,  1.93s/it]  \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [01:30<16:05,  2.11s/it]  \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [01:49<19:21,  2.54s/it] \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [03:21<35:43,  4.69s/it]  \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [01:54<20:13,  2.66s/it]  \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [01:49<19:24,  2.55s/it] \n"
     ]
    }
   ],
   "source": [
    "instances_20_10 = load_tai(20,10)\n",
    "makes_spans_20_10 = []\n",
    "for instance in instances_20_10:\n",
    "    saga = SAGA(instance, variety_degree=3)\n",
    "    saga.optim(T_min=0.01)\n",
    "    makes_spans_20_10.append(saga.make_span_star)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "executing heursitics\n",
      "tuning simulated annealing\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Best trial: 0. Best value: 1635: 100%|██████████| 10/10 [00:00<00:00, 19.96it/s]\n",
      "Best trial: 4. Best value: 1707: 100%|██████████| 10/10 [00:00<00:00, 28.72it/s]\n",
      "Best trial: 6. Best value: 1554: 100%|██████████| 10/10 [00:00<00:00, 38.72it/s]\n",
      "Best trial: 6. Best value: 1428: 100%|██████████| 10/10 [00:00<00:00, 30.64it/s]\n",
      "Best trial: 7. Best value: 1479: 100%|██████████| 10/10 [00:00<00:00, 36.57it/s]\n",
      "Best trial: 9. Best value: 1442: 100%|██████████| 10/10 [00:00<00:00, 28.66it/s]\n",
      "Best trial: 0. Best value: 1515: 100%|██████████| 10/10 [00:00<00:00, 25.31it/s]\n",
      "Best trial: 3. Best value: 1577: 100%|██████████| 10/10 [00:00<00:00, 25.99it/s]\n",
      "Best trial: 7. Best value: 1646: 100%|██████████| 10/10 [00:00<00:00, 29.17it/s]\n",
      "Best trial: 7. Best value: 1639: 100%|██████████| 10/10 [00:00<00:00, 14.81it/s]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "tuning genetic algorithm\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Best trial: 7. Best value: 1627: 100%|██████████| 10/10 [00:48<00:00,  4.88s/it]\n",
      "Best trial: 7. Best value: 1709: 100%|██████████| 10/10 [00:17<00:00,  1.77s/it]\n",
      "Best trial: 9. Best value: 1542: 100%|██████████| 10/10 [00:14<00:00,  1.44s/it]\n",
      "Best trial: 1. Best value: 1401: 100%|██████████| 10/10 [00:14<00:00,  1.42s/it]\n",
      "Best trial: 8. Best value: 1461: 100%|██████████| 10/10 [00:13<00:00,  1.37s/it]\n",
      "Best trial: 0. Best value: 1436: 100%|██████████| 10/10 [00:10<00:00,  1.04s/it]\n",
      "Best trial: 5. Best value: 1535: 100%|██████████| 10/10 [00:10<00:00,  1.01s/it]\n",
      "Best trial: 9. Best value: 1588: 100%|██████████| 10/10 [00:09<00:00,  1.03it/s]\n",
      "Best trial: 6. Best value: 1646: 100%|██████████| 10/10 [00:14<00:00,  1.47s/it]\n",
      "Best trial: 5. Best value: 1631: 100%|██████████| 10/10 [00:12<00:00,  1.21s/it]\n"
     ]
    }
   ],
   "source": [
    "print(\"executing heursitics\")\n",
    "cds, palmer, neh = exec_heur(instances_20_10)\n",
    "print(\"tuning simulated annealing\")\n",
    "study_sa = exec_sa(instances_20_10)\n",
    "print(\"tuning genetic algorithm\")\n",
    "study_ga = exec_ga(instances_20_10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style type=\"text/css\">\n",
       "#T_54181  {\n",
       "  min-width: 110px;\n",
       "}\n",
       "#T_54181 th {\n",
       "  min-width: 110px;\n",
       "}\n",
       "#T_54181_row0_col0, #T_54181_row1_col2, #T_54181_row2_col0, #T_54181_row3_col0, #T_54181_row4_col0, #T_54181_row5_col0, #T_54181_row6_col0, #T_54181_row7_col0, #T_54181_row8_col0, #T_54181_row9_col0 {\n",
       "  color: green;\n",
       "  font-weight: bold;\n",
       "}\n",
       "#T_54181_row0_col4, #T_54181_row1_col4, #T_54181_row2_col4, #T_54181_row3_col4, #T_54181_row4_col4, #T_54181_row5_col3, #T_54181_row6_col4, #T_54181_row7_col3, #T_54181_row8_col4, #T_54181_row9_col4 {\n",
       "  color: red;\n",
       "  font-weight: bold;\n",
       "}\n",
       "</style>\n",
       "<table id=\"T_54181\">\n",
       "  <thead>\n",
       "    <tr>\n",
       "      <th class=\"blank level0\" >&nbsp;</th>\n",
       "      <th id=\"T_54181_level0_col0\" class=\"col_heading level0 col0\" >SAGA</th>\n",
       "      <th id=\"T_54181_level0_col1\" class=\"col_heading level0 col1\" >Genetic Algorithm</th>\n",
       "      <th id=\"T_54181_level0_col2\" class=\"col_heading level0 col2\" >Simmulated annealing</th>\n",
       "      <th id=\"T_54181_level0_col3\" class=\"col_heading level0 col3\" >CDS</th>\n",
       "      <th id=\"T_54181_level0_col4\" class=\"col_heading level0 col4\" >Palmer</th>\n",
       "      <th id=\"T_54181_level0_col5\" class=\"col_heading level0 col5\" >NEH</th>\n",
       "      <th id=\"T_54181_level0_col6\" class=\"col_heading level0 col6\" >Upper bound</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th id=\"T_54181_level0_row0\" class=\"row_heading level0 row0\" >Instance 1</th>\n",
       "      <td id=\"T_54181_row0_col0\" class=\"data row0 col0\" >1602</td>\n",
       "      <td id=\"T_54181_row0_col1\" class=\"data row0 col1\" >1627</td>\n",
       "      <td id=\"T_54181_row0_col2\" class=\"data row0 col2\" >1635</td>\n",
       "      <td id=\"T_54181_row0_col3\" class=\"data row0 col3\" >1757</td>\n",
       "      <td id=\"T_54181_row0_col4\" class=\"data row0 col4\" >1790</td>\n",
       "      <td id=\"T_54181_row0_col5\" class=\"data row0 col5\" >1675</td>\n",
       "      <td id=\"T_54181_row0_col6\" class=\"data row0 col6\" >1582</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_54181_level0_row1\" class=\"row_heading level0 row1\" >Instance 2</th>\n",
       "      <td id=\"T_54181_row1_col0\" class=\"data row1 col0\" >1726</td>\n",
       "      <td id=\"T_54181_row1_col1\" class=\"data row1 col1\" >1709</td>\n",
       "      <td id=\"T_54181_row1_col2\" class=\"data row1 col2\" >1707</td>\n",
       "      <td id=\"T_54181_row1_col3\" class=\"data row1 col3\" >1854</td>\n",
       "      <td id=\"T_54181_row1_col4\" class=\"data row1 col4\" >1948</td>\n",
       "      <td id=\"T_54181_row1_col5\" class=\"data row1 col5\" >1797</td>\n",
       "      <td id=\"T_54181_row1_col6\" class=\"data row1 col6\" >1659</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_54181_level0_row2\" class=\"row_heading level0 row2\" >Instance 3</th>\n",
       "      <td id=\"T_54181_row2_col0\" class=\"data row2 col0\" >1522</td>\n",
       "      <td id=\"T_54181_row2_col1\" class=\"data row2 col1\" >1542</td>\n",
       "      <td id=\"T_54181_row2_col2\" class=\"data row2 col2\" >1554</td>\n",
       "      <td id=\"T_54181_row2_col3\" class=\"data row2 col3\" >1661</td>\n",
       "      <td id=\"T_54181_row2_col4\" class=\"data row2 col4\" >1729</td>\n",
       "      <td id=\"T_54181_row2_col5\" class=\"data row2 col5\" >1567</td>\n",
       "      <td id=\"T_54181_row2_col6\" class=\"data row2 col6\" >1496</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_54181_level0_row3\" class=\"row_heading level0 row3\" >Instance 4</th>\n",
       "      <td id=\"T_54181_row3_col0\" class=\"data row3 col0\" >1399</td>\n",
       "      <td id=\"T_54181_row3_col1\" class=\"data row3 col1\" >1401</td>\n",
       "      <td id=\"T_54181_row3_col2\" class=\"data row3 col2\" >1428</td>\n",
       "      <td id=\"T_54181_row3_col3\" class=\"data row3 col3\" >1547</td>\n",
       "      <td id=\"T_54181_row3_col4\" class=\"data row3 col4\" >1585</td>\n",
       "      <td id=\"T_54181_row3_col5\" class=\"data row3 col5\" >1551</td>\n",
       "      <td id=\"T_54181_row3_col6\" class=\"data row3 col6\" >1378</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_54181_level0_row4\" class=\"row_heading level0 row4\" >Instance 5</th>\n",
       "      <td id=\"T_54181_row4_col0\" class=\"data row4 col0\" >1451</td>\n",
       "      <td id=\"T_54181_row4_col1\" class=\"data row4 col1\" >1461</td>\n",
       "      <td id=\"T_54181_row4_col2\" class=\"data row4 col2\" >1479</td>\n",
       "      <td id=\"T_54181_row4_col3\" class=\"data row4 col3\" >1558</td>\n",
       "      <td id=\"T_54181_row4_col4\" class=\"data row4 col4\" >1648</td>\n",
       "      <td id=\"T_54181_row4_col5\" class=\"data row4 col5\" >1479</td>\n",
       "      <td id=\"T_54181_row4_col6\" class=\"data row4 col6\" >1419</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_54181_level0_row5\" class=\"row_heading level0 row5\" >Instance 6</th>\n",
       "      <td id=\"T_54181_row5_col0\" class=\"data row5 col0\" >1423</td>\n",
       "      <td id=\"T_54181_row5_col1\" class=\"data row5 col1\" >1436</td>\n",
       "      <td id=\"T_54181_row5_col2\" class=\"data row5 col2\" >1442</td>\n",
       "      <td id=\"T_54181_row5_col3\" class=\"data row5 col3\" >1591</td>\n",
       "      <td id=\"T_54181_row5_col4\" class=\"data row5 col4\" >1527</td>\n",
       "      <td id=\"T_54181_row5_col5\" class=\"data row5 col5\" >1509</td>\n",
       "      <td id=\"T_54181_row5_col6\" class=\"data row5 col6\" >1397</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_54181_level0_row6\" class=\"row_heading level0 row6\" >Instance 7</th>\n",
       "      <td id=\"T_54181_row6_col0\" class=\"data row6 col0\" >1494</td>\n",
       "      <td id=\"T_54181_row6_col1\" class=\"data row6 col1\" >1535</td>\n",
       "      <td id=\"T_54181_row6_col2\" class=\"data row6 col2\" >1515</td>\n",
       "      <td id=\"T_54181_row6_col3\" class=\"data row6 col3\" >1630</td>\n",
       "      <td id=\"T_54181_row6_col4\" class=\"data row6 col4\" >1735</td>\n",
       "      <td id=\"T_54181_row6_col5\" class=\"data row6 col5\" >1593</td>\n",
       "      <td id=\"T_54181_row6_col6\" class=\"data row6 col6\" >1484</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_54181_level0_row7\" class=\"row_heading level0 row7\" >Instance 8</th>\n",
       "      <td id=\"T_54181_row7_col0\" class=\"data row7 col0\" >1557</td>\n",
       "      <td id=\"T_54181_row7_col1\" class=\"data row7 col1\" >1588</td>\n",
       "      <td id=\"T_54181_row7_col2\" class=\"data row7 col2\" >1577</td>\n",
       "      <td id=\"T_54181_row7_col3\" class=\"data row7 col3\" >1766</td>\n",
       "      <td id=\"T_54181_row7_col4\" class=\"data row7 col4\" >1763</td>\n",
       "      <td id=\"T_54181_row7_col5\" class=\"data row7 col5\" >1688</td>\n",
       "      <td id=\"T_54181_row7_col6\" class=\"data row7 col6\" >1538</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_54181_level0_row8\" class=\"row_heading level0 row8\" >Instance 9</th>\n",
       "      <td id=\"T_54181_row8_col0\" class=\"data row8 col0\" >1626</td>\n",
       "      <td id=\"T_54181_row8_col1\" class=\"data row8 col1\" >1646</td>\n",
       "      <td id=\"T_54181_row8_col2\" class=\"data row8 col2\" >1646</td>\n",
       "      <td id=\"T_54181_row8_col3\" class=\"data row8 col3\" >1720</td>\n",
       "      <td id=\"T_54181_row8_col4\" class=\"data row8 col4\" >1836</td>\n",
       "      <td id=\"T_54181_row8_col5\" class=\"data row8 col5\" >1659</td>\n",
       "      <td id=\"T_54181_row8_col6\" class=\"data row8 col6\" >1593</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_54181_level0_row9\" class=\"row_heading level0 row9\" >Instance 10</th>\n",
       "      <td id=\"T_54181_row9_col0\" class=\"data row9 col0\" >1629</td>\n",
       "      <td id=\"T_54181_row9_col1\" class=\"data row9 col1\" >1631</td>\n",
       "      <td id=\"T_54181_row9_col2\" class=\"data row9 col2\" >1639</td>\n",
       "      <td id=\"T_54181_row9_col3\" class=\"data row9 col3\" >1884</td>\n",
       "      <td id=\"T_54181_row9_col4\" class=\"data row9 col4\" >1898</td>\n",
       "      <td id=\"T_54181_row9_col5\" class=\"data row9 col5\" >1702</td>\n",
       "      <td id=\"T_54181_row9_col6\" class=\"data row9 col6\" >1591</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n"
      ],
      "text/plain": [
       "<pandas.io.formats.style.Styler at 0x129cb034d90>"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "compare(instances_20_10, makes_spans_20_10, study_ga, study_sa, cds, palmer, neh)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "20 jobs 20 machines"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Temperature 0.00515377520732012:  10%|█         | 50/500 [04:09<37:27,  4.99s/it]   \n",
      "Temperature 0.00515377520732012:  10%|█         | 50/500 [01:55<17:21,  2.32s/it]   \n",
      "Temperature 0.00515377520732012:  10%|█         | 50/500 [03:17<29:33,  3.94s/it]   \n",
      "Temperature 0.00515377520732012:  10%|█         | 50/500 [01:57<17:39,  2.36s/it] \n",
      "Temperature 0.00515377520732012:  10%|█         | 50/500 [04:43<42:27,  5.66s/it]   \n",
      "Temperature 0.00515377520732012:  10%|█         | 50/500 [03:05<27:46,  3.70s/it]   \n",
      "Temperature 0.00515377520732012:  10%|█         | 50/500 [37:46<5:39:58, 45.33s/it]  \n",
      "Temperature 0.00515377520732012:  10%|█         | 50/500 [04:39<41:52,  5.58s/it]   \n",
      "Temperature 0.00515377520732012:  10%|█         | 50/500 [03:03<27:35,  3.68s/it]   \n",
      "Temperature 0.00515377520732012:  10%|█         | 50/500 [03:27<31:08,  4.15s/it]  \n"
     ]
    }
   ],
   "source": [
    "instances_20_20 = load_tai(20,20)\n",
    "makes_spans_20_20 = []\n",
    "for instance in instances_20_20:\n",
    "    saga = SAGA(instance, variety_degree=5)\n",
    "    saga.optim(T_min=0.005)\n",
    "    makes_spans_20_20.append(saga.make_span_star)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "executing heursitics\n",
      "tuning simulated annealing\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Best trial: 2. Best value: 2383: 100%|██████████| 10/10 [00:01<00:00,  9.99it/s]\n",
      "Best trial: 3. Best value: 2168: 100%|██████████| 10/10 [00:00<00:00, 15.07it/s]\n",
      "Best trial: 2. Best value: 2415: 100%|██████████| 10/10 [00:00<00:00, 16.24it/s]\n",
      "Best trial: 1. Best value: 2271: 100%|██████████| 10/10 [00:01<00:00,  7.98it/s]\n",
      "Best trial: 3. Best value: 2353: 100%|██████████| 10/10 [00:00<00:00, 15.01it/s]\n",
      "Best trial: 2. Best value: 2298: 100%|██████████| 10/10 [00:00<00:00, 12.56it/s]\n",
      "Best trial: 8. Best value: 2335: 100%|██████████| 10/10 [00:00<00:00, 16.97it/s]\n",
      "Best trial: 1. Best value: 2226: 100%|██████████| 10/10 [00:00<00:00, 14.42it/s]\n",
      "Best trial: 2. Best value: 2312: 100%|██████████| 10/10 [00:00<00:00, 11.16it/s]\n",
      "Best trial: 2. Best value: 2246: 100%|██████████| 10/10 [00:01<00:00,  6.51it/s]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "tuning genetic algorithm\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Best trial: 5. Best value: 2352: 100%|██████████| 10/10 [00:26<00:00,  2.62s/it]\n",
      "Best trial: 8. Best value: 2159: 100%|██████████| 10/10 [00:15<00:00,  1.51s/it]\n",
      "Best trial: 9. Best value: 2371: 100%|██████████| 10/10 [00:22<00:00,  2.23s/it]\n",
      "Best trial: 3. Best value: 2255: 100%|██████████| 10/10 [00:39<00:00,  3.94s/it]\n",
      "Best trial: 9. Best value: 2317: 100%|██████████| 10/10 [00:24<00:00,  2.40s/it]\n",
      "Best trial: 3. Best value: 2277: 100%|██████████| 10/10 [01:00<00:00,  6.05s/it]\n",
      "Best trial: 2. Best value: 2333: 100%|██████████| 10/10 [00:19<00:00,  2.00s/it]\n",
      "Best trial: 3. Best value: 2226: 100%|██████████| 10/10 [00:23<00:00,  2.38s/it]\n",
      "Best trial: 8. Best value: 2262: 100%|██████████| 10/10 [00:46<00:00,  4.68s/it]\n",
      "Best trial: 9. Best value: 2212: 100%|██████████| 10/10 [00:50<00:00,  5.05s/it]\n"
     ]
    }
   ],
   "source": [
    "print(\"executing heursitics\")\n",
    "cds, palmer, neh = exec_heur(instances_20_20)\n",
    "print(\"tuning simulated annealing\")\n",
    "study_sa = exec_sa(instances_20_20)\n",
    "print(\"tuning genetic algorithm\")\n",
    "study_ga = exec_ga(instances_20_20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style type=\"text/css\">\n",
       "#T_d8c8b  {\n",
       "  min-width: 110px;\n",
       "}\n",
       "#T_d8c8b th {\n",
       "  min-width: 110px;\n",
       "}\n",
       "#T_d8c8b_row0_col0, #T_d8c8b_row1_col0, #T_d8c8b_row2_col1, #T_d8c8b_row3_col0, #T_d8c8b_row4_col0, #T_d8c8b_row5_col0, #T_d8c8b_row6_col0, #T_d8c8b_row7_col0, #T_d8c8b_row7_col1, #T_d8c8b_row7_col2, #T_d8c8b_row8_col0, #T_d8c8b_row9_col1 {\n",
       "  color: green;\n",
       "  font-weight: bold;\n",
       "}\n",
       "#T_d8c8b_row0_col4, #T_d8c8b_row1_col4, #T_d8c8b_row2_col4, #T_d8c8b_row3_col4, #T_d8c8b_row4_col4, #T_d8c8b_row5_col4, #T_d8c8b_row6_col3, #T_d8c8b_row7_col4, #T_d8c8b_row8_col4, #T_d8c8b_row9_col4 {\n",
       "  color: red;\n",
       "  font-weight: bold;\n",
       "}\n",
       "</style>\n",
       "<table id=\"T_d8c8b\">\n",
       "  <thead>\n",
       "    <tr>\n",
       "      <th class=\"blank level0\" >&nbsp;</th>\n",
       "      <th id=\"T_d8c8b_level0_col0\" class=\"col_heading level0 col0\" >SAGA</th>\n",
       "      <th id=\"T_d8c8b_level0_col1\" class=\"col_heading level0 col1\" >Genetic Algorithm</th>\n",
       "      <th id=\"T_d8c8b_level0_col2\" class=\"col_heading level0 col2\" >Simmulated annealing</th>\n",
       "      <th id=\"T_d8c8b_level0_col3\" class=\"col_heading level0 col3\" >CDS</th>\n",
       "      <th id=\"T_d8c8b_level0_col4\" class=\"col_heading level0 col4\" >Palmer</th>\n",
       "      <th id=\"T_d8c8b_level0_col5\" class=\"col_heading level0 col5\" >NEH</th>\n",
       "      <th id=\"T_d8c8b_level0_col6\" class=\"col_heading level0 col6\" >Upper bound</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th id=\"T_d8c8b_level0_row0\" class=\"row_heading level0 row0\" >Instance 1</th>\n",
       "      <td id=\"T_d8c8b_row0_col0\" class=\"data row0 col0\" >2331</td>\n",
       "      <td id=\"T_d8c8b_row0_col1\" class=\"data row0 col1\" >2352</td>\n",
       "      <td id=\"T_d8c8b_row0_col2\" class=\"data row0 col2\" >2383</td>\n",
       "      <td id=\"T_d8c8b_row0_col3\" class=\"data row0 col3\" >2579</td>\n",
       "      <td id=\"T_d8c8b_row0_col4\" class=\"data row0 col4\" >2818</td>\n",
       "      <td id=\"T_d8c8b_row0_col5\" class=\"data row0 col5\" >2456</td>\n",
       "      <td id=\"T_d8c8b_row0_col6\" class=\"data row0 col6\" >2297</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_d8c8b_level0_row1\" class=\"row_heading level0 row1\" >Instance 2</th>\n",
       "      <td id=\"T_d8c8b_row1_col0\" class=\"data row1 col0\" >2122</td>\n",
       "      <td id=\"T_d8c8b_row1_col1\" class=\"data row1 col1\" >2159</td>\n",
       "      <td id=\"T_d8c8b_row1_col2\" class=\"data row1 col2\" >2168</td>\n",
       "      <td id=\"T_d8c8b_row1_col3\" class=\"data row1 col3\" >2285</td>\n",
       "      <td id=\"T_d8c8b_row1_col4\" class=\"data row1 col4\" >2331</td>\n",
       "      <td id=\"T_d8c8b_row1_col5\" class=\"data row1 col5\" >2197</td>\n",
       "      <td id=\"T_d8c8b_row1_col6\" class=\"data row1 col6\" >2100</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_d8c8b_level0_row2\" class=\"row_heading level0 row2\" >Instance 3</th>\n",
       "      <td id=\"T_d8c8b_row2_col0\" class=\"data row2 col0\" >2380</td>\n",
       "      <td id=\"T_d8c8b_row2_col1\" class=\"data row2 col1\" >2371</td>\n",
       "      <td id=\"T_d8c8b_row2_col2\" class=\"data row2 col2\" >2415</td>\n",
       "      <td id=\"T_d8c8b_row2_col3\" class=\"data row2 col3\" >2565</td>\n",
       "      <td id=\"T_d8c8b_row2_col4\" class=\"data row2 col4\" >2678</td>\n",
       "      <td id=\"T_d8c8b_row2_col5\" class=\"data row2 col5\" >2493</td>\n",
       "      <td id=\"T_d8c8b_row2_col6\" class=\"data row2 col6\" >2326</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_d8c8b_level0_row3\" class=\"row_heading level0 row3\" >Instance 4</th>\n",
       "      <td id=\"T_d8c8b_row3_col0\" class=\"data row3 col0\" >2253</td>\n",
       "      <td id=\"T_d8c8b_row3_col1\" class=\"data row3 col1\" >2255</td>\n",
       "      <td id=\"T_d8c8b_row3_col2\" class=\"data row3 col2\" >2271</td>\n",
       "      <td id=\"T_d8c8b_row3_col3\" class=\"data row3 col3\" >2415</td>\n",
       "      <td id=\"T_d8c8b_row3_col4\" class=\"data row3 col4\" >2629</td>\n",
       "      <td id=\"T_d8c8b_row3_col5\" class=\"data row3 col5\" >2316</td>\n",
       "      <td id=\"T_d8c8b_row3_col6\" class=\"data row3 col6\" >2223</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_d8c8b_level0_row4\" class=\"row_heading level0 row4\" >Instance 5</th>\n",
       "      <td id=\"T_d8c8b_row4_col0\" class=\"data row4 col0\" >2316</td>\n",
       "      <td id=\"T_d8c8b_row4_col1\" class=\"data row4 col1\" >2317</td>\n",
       "      <td id=\"T_d8c8b_row4_col2\" class=\"data row4 col2\" >2353</td>\n",
       "      <td id=\"T_d8c8b_row4_col3\" class=\"data row4 col3\" >2506</td>\n",
       "      <td id=\"T_d8c8b_row4_col4\" class=\"data row4 col4\" >2704</td>\n",
       "      <td id=\"T_d8c8b_row4_col5\" class=\"data row4 col5\" >2436</td>\n",
       "      <td id=\"T_d8c8b_row4_col6\" class=\"data row4 col6\" >2291</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_d8c8b_level0_row5\" class=\"row_heading level0 row5\" >Instance 6</th>\n",
       "      <td id=\"T_d8c8b_row5_col0\" class=\"data row5 col0\" >2250</td>\n",
       "      <td id=\"T_d8c8b_row5_col1\" class=\"data row5 col1\" >2277</td>\n",
       "      <td id=\"T_d8c8b_row5_col2\" class=\"data row5 col2\" >2298</td>\n",
       "      <td id=\"T_d8c8b_row5_col3\" class=\"data row5 col3\" >2422</td>\n",
       "      <td id=\"T_d8c8b_row5_col4\" class=\"data row5 col4\" >2572</td>\n",
       "      <td id=\"T_d8c8b_row5_col5\" class=\"data row5 col5\" >2364</td>\n",
       "      <td id=\"T_d8c8b_row5_col6\" class=\"data row5 col6\" >2226</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_d8c8b_level0_row6\" class=\"row_heading level0 row6\" >Instance 7</th>\n",
       "      <td id=\"T_d8c8b_row6_col0\" class=\"data row6 col0\" >2323</td>\n",
       "      <td id=\"T_d8c8b_row6_col1\" class=\"data row6 col1\" >2333</td>\n",
       "      <td id=\"T_d8c8b_row6_col2\" class=\"data row6 col2\" >2335</td>\n",
       "      <td id=\"T_d8c8b_row6_col3\" class=\"data row6 col3\" >2489</td>\n",
       "      <td id=\"T_d8c8b_row6_col4\" class=\"data row6 col4\" >2456</td>\n",
       "      <td id=\"T_d8c8b_row6_col5\" class=\"data row6 col5\" >2406</td>\n",
       "      <td id=\"T_d8c8b_row6_col6\" class=\"data row6 col6\" >2273</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_d8c8b_level0_row7\" class=\"row_heading level0 row7\" >Instance 8</th>\n",
       "      <td id=\"T_d8c8b_row7_col0\" class=\"data row7 col0\" >2226</td>\n",
       "      <td id=\"T_d8c8b_row7_col1\" class=\"data row7 col1\" >2226</td>\n",
       "      <td id=\"T_d8c8b_row7_col2\" class=\"data row7 col2\" >2226</td>\n",
       "      <td id=\"T_d8c8b_row7_col3\" class=\"data row7 col3\" >2362</td>\n",
       "      <td id=\"T_d8c8b_row7_col4\" class=\"data row7 col4\" >2435</td>\n",
       "      <td id=\"T_d8c8b_row7_col5\" class=\"data row7 col5\" >2278</td>\n",
       "      <td id=\"T_d8c8b_row7_col6\" class=\"data row7 col6\" >2200</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_d8c8b_level0_row8\" class=\"row_heading level0 row8\" >Instance 9</th>\n",
       "      <td id=\"T_d8c8b_row8_col0\" class=\"data row8 col0\" >2253</td>\n",
       "      <td id=\"T_d8c8b_row8_col1\" class=\"data row8 col1\" >2262</td>\n",
       "      <td id=\"T_d8c8b_row8_col2\" class=\"data row8 col2\" >2312</td>\n",
       "      <td id=\"T_d8c8b_row8_col3\" class=\"data row8 col3\" >2409</td>\n",
       "      <td id=\"T_d8c8b_row8_col4\" class=\"data row8 col4\" >2754</td>\n",
       "      <td id=\"T_d8c8b_row8_col5\" class=\"data row8 col5\" >2399</td>\n",
       "      <td id=\"T_d8c8b_row8_col6\" class=\"data row8 col6\" >2237</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_d8c8b_level0_row9\" class=\"row_heading level0 row9\" >Instance 10</th>\n",
       "      <td id=\"T_d8c8b_row9_col0\" class=\"data row9 col0\" >2226</td>\n",
       "      <td id=\"T_d8c8b_row9_col1\" class=\"data row9 col1\" >2212</td>\n",
       "      <td id=\"T_d8c8b_row9_col2\" class=\"data row9 col2\" >2246</td>\n",
       "      <td id=\"T_d8c8b_row9_col3\" class=\"data row9 col3\" >2439</td>\n",
       "      <td id=\"T_d8c8b_row9_col4\" class=\"data row9 col4\" >2633</td>\n",
       "      <td id=\"T_d8c8b_row9_col5\" class=\"data row9 col5\" >2352</td>\n",
       "      <td id=\"T_d8c8b_row9_col6\" class=\"data row9 col6\" >2178</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n"
      ],
      "text/plain": [
       "<pandas.io.formats.style.Styler at 0x129cad8bf50>"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "compare(instances_20_20, makes_spans_20_20, study_ga, study_sa, cds, palmer, neh)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "50 jobs 5 machines"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Temperature 0.00515377520732012:  10%|█         | 50/500 [01:10<10:34,  1.41s/it] \n",
      "Temperature 0.00515377520732012:  10%|█         | 50/500 [10:01<1:30:11, 12.03s/it] \n",
      "Temperature 0.00515377520732012:  10%|█         | 50/500 [05:33<50:03,  6.68s/it]   \n",
      "Temperature 0.00515377520732012:  10%|█         | 50/500 [03:16<29:27,  3.93s/it]   \n",
      "Temperature 0.00515377520732012:  10%|█         | 50/500 [02:56<26:27,  3.53s/it] \n",
      "Temperature 0.00515377520732012:  10%|█         | 50/500 [02:22<21:20,  2.84s/it] \n",
      "Temperature 0.00515377520732012:  10%|█         | 50/500 [03:29<31:27,  4.19s/it]  \n",
      "Temperature 0.00515377520732012:  10%|█         | 50/500 [02:12<19:54,  2.65s/it]  \n",
      "Temperature 0.00515377520732012:  10%|█         | 50/500 [01:54<17:08,  2.29s/it] \n",
      "Temperature 0.00515377520732012:  10%|█         | 50/500 [03:40<33:07,  4.42s/it]  \n"
     ]
    }
   ],
   "source": [
    "instances_50_5 = load_tai(50,5)\n",
    "makes_spans_50_5 = []\n",
    "for instance in instances_50_5:\n",
    "    saga = SAGA(instance, variety_degree=5)\n",
    "    saga.optim(T_min=0.005)\n",
    "    makes_spans_50_5.append(saga.make_span_star)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "executing heursitics\n",
      "tuning simulated annealing\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Best trial: 0. Best value: 2735: 100%|██████████| 10/10 [00:00<00:00, 13.02it/s]\n",
      "Best trial: 1. Best value: 2890: 100%|██████████| 10/10 [00:01<00:00,  9.95it/s]\n",
      "Best trial: 5. Best value: 2648: 100%|██████████| 10/10 [00:00<00:00, 10.80it/s]\n",
      "Best trial: 9. Best value: 2802: 100%|██████████| 10/10 [00:00<00:00, 13.82it/s]\n",
      "Best trial: 6. Best value: 2891: 100%|██████████| 10/10 [00:00<00:00, 17.83it/s]\n",
      "Best trial: 4. Best value: 2849: 100%|██████████| 10/10 [00:01<00:00,  9.36it/s]\n",
      "Best trial: 7. Best value: 2746: 100%|██████████| 10/10 [00:00<00:00, 14.60it/s]\n",
      "Best trial: 0. Best value: 2707: 100%|██████████| 10/10 [00:00<00:00, 12.53it/s]\n",
      "Best trial: 6. Best value: 2592: 100%|██████████| 10/10 [00:00<00:00, 10.73it/s]\n",
      "Best trial: 0. Best value: 2815: 100%|██████████| 10/10 [00:01<00:00,  8.51it/s]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "tuning genetic algorithm\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Best trial: 5. Best value: 2735: 100%|██████████| 10/10 [00:32<00:00,  3.21s/it]\n",
      "Best trial: 0. Best value: 2863: 100%|██████████| 10/10 [00:22<00:00,  2.22s/it]\n",
      "Best trial: 3. Best value: 2630: 100%|██████████| 10/10 [00:19<00:00,  1.92s/it]\n",
      "Best trial: 6. Best value: 2778: 100%|██████████| 10/10 [00:23<00:00,  2.40s/it]\n",
      "Best trial: 4. Best value: 2864: 100%|██████████| 10/10 [00:28<00:00,  2.87s/it]\n",
      "Best trial: 9. Best value: 2835: 100%|██████████| 10/10 [00:15<00:00,  1.54s/it]\n",
      "Best trial: 6. Best value: 2738: 100%|██████████| 10/10 [00:26<00:00,  2.67s/it]\n",
      "Best trial: 8. Best value: 2705: 100%|██████████| 10/10 [00:32<00:00,  3.27s/it]\n",
      "Best trial: 6. Best value: 2568: 100%|██████████| 10/10 [00:27<00:00,  2.76s/it]\n",
      "Best trial: 9. Best value: 2783: 100%|██████████| 10/10 [00:54<00:00,  5.45s/it]\n"
     ]
    }
   ],
   "source": [
    "print(\"executing heursitics\")\n",
    "cds, palmer, neh = exec_heur(instances_50_5)\n",
    "print(\"tuning simulated annealing\")\n",
    "study_sa = exec_sa(instances_50_5)\n",
    "print(\"tuning genetic algorithm\")\n",
    "study_ga = exec_ga(instances_50_5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style type=\"text/css\">\n",
       "#T_e0d72  {\n",
       "  min-width: 110px;\n",
       "}\n",
       "#T_e0d72 th {\n",
       "  min-width: 110px;\n",
       "}\n",
       "#T_e0d72_row0_col0, #T_e0d72_row0_col1, #T_e0d72_row0_col2, #T_e0d72_row1_col0, #T_e0d72_row2_col0, #T_e0d72_row3_col0, #T_e0d72_row4_col0, #T_e0d72_row4_col1, #T_e0d72_row5_col0, #T_e0d72_row6_col0, #T_e0d72_row7_col0, #T_e0d72_row8_col0, #T_e0d72_row8_col1, #T_e0d72_row9_col0 {\n",
       "  color: green;\n",
       "  font-weight: bold;\n",
       "}\n",
       "#T_e0d72_row0_col3, #T_e0d72_row1_col3, #T_e0d72_row2_col4, #T_e0d72_row3_col3, #T_e0d72_row4_col3, #T_e0d72_row5_col4, #T_e0d72_row6_col3, #T_e0d72_row7_col3, #T_e0d72_row8_col3, #T_e0d72_row9_col3 {\n",
       "  color: red;\n",
       "  font-weight: bold;\n",
       "}\n",
       "</style>\n",
       "<table id=\"T_e0d72\">\n",
       "  <thead>\n",
       "    <tr>\n",
       "      <th class=\"blank level0\" >&nbsp;</th>\n",
       "      <th id=\"T_e0d72_level0_col0\" class=\"col_heading level0 col0\" >LSAGA</th>\n",
       "      <th id=\"T_e0d72_level0_col1\" class=\"col_heading level0 col1\" >Genetic Algorithm</th>\n",
       "      <th id=\"T_e0d72_level0_col2\" class=\"col_heading level0 col2\" >Simmulated annealing</th>\n",
       "      <th id=\"T_e0d72_level0_col3\" class=\"col_heading level0 col3\" >CDS</th>\n",
       "      <th id=\"T_e0d72_level0_col4\" class=\"col_heading level0 col4\" >Palmer</th>\n",
       "      <th id=\"T_e0d72_level0_col5\" class=\"col_heading level0 col5\" >NEH</th>\n",
       "      <th id=\"T_e0d72_level0_col6\" class=\"col_heading level0 col6\" >Upper bound</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th id=\"T_e0d72_level0_row0\" class=\"row_heading level0 row0\" >Instance 1</th>\n",
       "      <td id=\"T_e0d72_row0_col0\" class=\"data row0 col0\" >2735</td>\n",
       "      <td id=\"T_e0d72_row0_col1\" class=\"data row0 col1\" >2735</td>\n",
       "      <td id=\"T_e0d72_row0_col2\" class=\"data row0 col2\" >2735</td>\n",
       "      <td id=\"T_e0d72_row0_col3\" class=\"data row0 col3\" >2883</td>\n",
       "      <td id=\"T_e0d72_row0_col4\" class=\"data row0 col4\" >2774</td>\n",
       "      <td id=\"T_e0d72_row0_col5\" class=\"data row0 col5\" >2745</td>\n",
       "      <td id=\"T_e0d72_row0_col6\" class=\"data row0 col6\" >2724</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_e0d72_level0_row1\" class=\"row_heading level0 row1\" >Instance 2</th>\n",
       "      <td id=\"T_e0d72_row1_col0\" class=\"data row1 col0\" >2848</td>\n",
       "      <td id=\"T_e0d72_row1_col1\" class=\"data row1 col1\" >2863</td>\n",
       "      <td id=\"T_e0d72_row1_col2\" class=\"data row1 col2\" >2890</td>\n",
       "      <td id=\"T_e0d72_row1_col3\" class=\"data row1 col3\" >3032</td>\n",
       "      <td id=\"T_e0d72_row1_col4\" class=\"data row1 col4\" >3014</td>\n",
       "      <td id=\"T_e0d72_row1_col5\" class=\"data row1 col5\" >2943</td>\n",
       "      <td id=\"T_e0d72_row1_col6\" class=\"data row1 col6\" >2834</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_e0d72_level0_row2\" class=\"row_heading level0 row2\" >Instance 3</th>\n",
       "      <td id=\"T_e0d72_row2_col0\" class=\"data row2 col0\" >2624</td>\n",
       "      <td id=\"T_e0d72_row2_col1\" class=\"data row2 col1\" >2630</td>\n",
       "      <td id=\"T_e0d72_row2_col2\" class=\"data row2 col2\" >2648</td>\n",
       "      <td id=\"T_e0d72_row2_col3\" class=\"data row2 col3\" >2714</td>\n",
       "      <td id=\"T_e0d72_row2_col4\" class=\"data row2 col4\" >2777</td>\n",
       "      <td id=\"T_e0d72_row2_col5\" class=\"data row2 col5\" >2712</td>\n",
       "      <td id=\"T_e0d72_row2_col6\" class=\"data row2 col6\" >2621</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_e0d72_level0_row3\" class=\"row_heading level0 row3\" >Instance 4</th>\n",
       "      <td id=\"T_e0d72_row3_col0\" class=\"data row3 col0\" >2770</td>\n",
       "      <td id=\"T_e0d72_row3_col1\" class=\"data row3 col1\" >2778</td>\n",
       "      <td id=\"T_e0d72_row3_col2\" class=\"data row3 col2\" >2802</td>\n",
       "      <td id=\"T_e0d72_row3_col3\" class=\"data row3 col3\" >2884</td>\n",
       "      <td id=\"T_e0d72_row3_col4\" class=\"data row3 col4\" >2860</td>\n",
       "      <td id=\"T_e0d72_row3_col5\" class=\"data row3 col5\" >2855</td>\n",
       "      <td id=\"T_e0d72_row3_col6\" class=\"data row3 col6\" >2751</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_e0d72_level0_row4\" class=\"row_heading level0 row4\" >Instance 5</th>\n",
       "      <td id=\"T_e0d72_row4_col0\" class=\"data row4 col0\" >2864</td>\n",
       "      <td id=\"T_e0d72_row4_col1\" class=\"data row4 col1\" >2864</td>\n",
       "      <td id=\"T_e0d72_row4_col2\" class=\"data row4 col2\" >2891</td>\n",
       "      <td id=\"T_e0d72_row4_col3\" class=\"data row4 col3\" >3038</td>\n",
       "      <td id=\"T_e0d72_row4_col4\" class=\"data row4 col4\" >2963</td>\n",
       "      <td id=\"T_e0d72_row4_col5\" class=\"data row4 col5\" >2929</td>\n",
       "      <td id=\"T_e0d72_row4_col6\" class=\"data row4 col6\" >2863</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_e0d72_level0_row5\" class=\"row_heading level0 row5\" >Instance 6</th>\n",
       "      <td id=\"T_e0d72_row5_col0\" class=\"data row5 col0\" >2831</td>\n",
       "      <td id=\"T_e0d72_row5_col1\" class=\"data row5 col1\" >2835</td>\n",
       "      <td id=\"T_e0d72_row5_col2\" class=\"data row5 col2\" >2849</td>\n",
       "      <td id=\"T_e0d72_row5_col3\" class=\"data row5 col3\" >3031</td>\n",
       "      <td id=\"T_e0d72_row5_col4\" class=\"data row5 col4\" >3090</td>\n",
       "      <td id=\"T_e0d72_row5_col5\" class=\"data row5 col5\" >2938</td>\n",
       "      <td id=\"T_e0d72_row5_col6\" class=\"data row5 col6\" >2829</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_e0d72_level0_row6\" class=\"row_heading level0 row6\" >Instance 7</th>\n",
       "      <td id=\"T_e0d72_row6_col0\" class=\"data row6 col0\" >2732</td>\n",
       "      <td id=\"T_e0d72_row6_col1\" class=\"data row6 col1\" >2738</td>\n",
       "      <td id=\"T_e0d72_row6_col2\" class=\"data row6 col2\" >2746</td>\n",
       "      <td id=\"T_e0d72_row6_col3\" class=\"data row6 col3\" >2978</td>\n",
       "      <td id=\"T_e0d72_row6_col4\" class=\"data row6 col4\" >2845</td>\n",
       "      <td id=\"T_e0d72_row6_col5\" class=\"data row6 col5\" >2800</td>\n",
       "      <td id=\"T_e0d72_row6_col6\" class=\"data row6 col6\" >2725</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_e0d72_level0_row7\" class=\"row_heading level0 row7\" >Instance 8</th>\n",
       "      <td id=\"T_e0d72_row7_col0\" class=\"data row7 col0\" >2700</td>\n",
       "      <td id=\"T_e0d72_row7_col1\" class=\"data row7 col1\" >2705</td>\n",
       "      <td id=\"T_e0d72_row7_col2\" class=\"data row7 col2\" >2707</td>\n",
       "      <td id=\"T_e0d72_row7_col3\" class=\"data row7 col3\" >2867</td>\n",
       "      <td id=\"T_e0d72_row7_col4\" class=\"data row7 col4\" >2826</td>\n",
       "      <td id=\"T_e0d72_row7_col5\" class=\"data row7 col5\" >2795</td>\n",
       "      <td id=\"T_e0d72_row7_col6\" class=\"data row7 col6\" >2683</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_e0d72_level0_row8\" class=\"row_heading level0 row8\" >Instance 9</th>\n",
       "      <td id=\"T_e0d72_row8_col0\" class=\"data row8 col0\" >2568</td>\n",
       "      <td id=\"T_e0d72_row8_col1\" class=\"data row8 col1\" >2568</td>\n",
       "      <td id=\"T_e0d72_row8_col2\" class=\"data row8 col2\" >2592</td>\n",
       "      <td id=\"T_e0d72_row8_col3\" class=\"data row8 col3\" >2784</td>\n",
       "      <td id=\"T_e0d72_row8_col4\" class=\"data row8 col4\" >2733</td>\n",
       "      <td id=\"T_e0d72_row8_col5\" class=\"data row8 col5\" >2683</td>\n",
       "      <td id=\"T_e0d72_row8_col6\" class=\"data row8 col6\" >2552</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_e0d72_level0_row9\" class=\"row_heading level0 row9\" >Instance 10</th>\n",
       "      <td id=\"T_e0d72_row9_col0\" class=\"data row9 col0\" >2782</td>\n",
       "      <td id=\"T_e0d72_row9_col1\" class=\"data row9 col1\" >2783</td>\n",
       "      <td id=\"T_e0d72_row9_col2\" class=\"data row9 col2\" >2815</td>\n",
       "      <td id=\"T_e0d72_row9_col3\" class=\"data row9 col3\" >3000</td>\n",
       "      <td id=\"T_e0d72_row9_col4\" class=\"data row9 col4\" >2915</td>\n",
       "      <td id=\"T_e0d72_row9_col5\" class=\"data row9 col5\" >2878</td>\n",
       "      <td id=\"T_e0d72_row9_col6\" class=\"data row9 col6\" >2782</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n"
      ],
      "text/plain": [
       "<pandas.io.formats.style.Styler at 0x25c2c8f5a10>"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "compare(instances_50_5, makes_spans_50_5, study_ga, study_sa, cds, palmer, neh)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "50 jobs 10 machines"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [09:55<1:45:26, 13.84s/it]  \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [04:32<48:19,  6.35s/it]   \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [04:31<48:06,  6.32s/it]   \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [09:43<1:43:26, 13.58s/it] \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [02:31<26:49,  3.52s/it] \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [04:27<47:19,  6.21s/it]  \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [05:56<1:03:08,  8.29s/it] \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [03:34<38:03,  5.00s/it]   \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [04:31<48:01,  6.30s/it]  \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [08:00<1:25:07, 11.18s/it] \n"
     ]
    }
   ],
   "source": [
    "instances_50_10 = load_tai(50,10)\n",
    "makes_spans_50_10 = []\n",
    "for instance in instances_50_10:\n",
    "    saga = LSAGA(instance, variety_degree=3)\n",
    "    saga.optim(T_min=0.01)\n",
    "    makes_spans_50_10.append(saga.make_span_star)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "executing heursitics\n",
      "tuning simulated annealing\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Best trial: 8. Best value: 3186: 100%|██████████| 10/10 [00:01<00:00,  5.50it/s]\n",
      "Best trial: 6. Best value: 3014: 100%|██████████| 10/10 [00:06<00:00,  1.55it/s]\n",
      "Best trial: 1. Best value: 2957: 100%|██████████| 10/10 [00:06<00:00,  1.53it/s]\n",
      "Best trial: 7. Best value: 3192: 100%|██████████| 10/10 [00:04<00:00,  2.36it/s]\n",
      "Best trial: 4. Best value: 3183: 100%|██████████| 10/10 [00:01<00:00,  6.60it/s]\n",
      "Best trial: 5. Best value: 3158: 100%|██████████| 10/10 [00:01<00:00,  6.53it/s]\n",
      "Best trial: 3. Best value: 3232: 100%|██████████| 10/10 [00:03<00:00,  3.01it/s]\n",
      "Best trial: 4. Best value: 3144: 100%|██████████| 10/10 [00:04<00:00,  2.06it/s]\n",
      "Best trial: 4. Best value: 2978: 100%|██████████| 10/10 [00:05<00:00,  1.92it/s]\n",
      "Best trial: 6. Best value: 3195: 100%|██████████| 10/10 [00:02<00:00,  3.86it/s]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "tuning genetic algorithm\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Best trial: 2. Best value: 3151: 100%|██████████| 10/10 [02:23<00:00, 14.35s/it]\n",
      "Best trial: 0. Best value: 2972: 100%|██████████| 10/10 [04:10<00:00, 25.07s/it]\n",
      "Best trial: 5. Best value: 2984: 100%|██████████| 10/10 [03:34<00:00, 21.45s/it]\n",
      "Best trial: 3. Best value: 3137: 100%|██████████| 10/10 [01:36<00:00,  9.70s/it]\n",
      "Best trial: 5. Best value: 3066: 100%|██████████| 10/10 [01:40<00:00, 10.05s/it]\n",
      "Best trial: 5. Best value: 3118: 100%|██████████| 10/10 [01:34<00:00,  9.40s/it]\n",
      "Best trial: 2. Best value: 3197: 100%|██████████| 10/10 [01:43<00:00, 10.32s/it]\n",
      "Best trial: 0. Best value: 3106: 100%|██████████| 10/10 [01:39<00:00,  9.93s/it]\n",
      "Best trial: 3. Best value: 2994: 100%|██████████| 10/10 [01:29<00:00,  8.97s/it]\n",
      "Best trial: 9. Best value: 3182: 100%|██████████| 10/10 [02:29<00:00, 14.90s/it]\n"
     ]
    }
   ],
   "source": [
    "print(\"executing heursitics\")\n",
    "cds, palmer, neh = exec_heur(instances_50_10)\n",
    "print(\"tuning simulated annealing\")\n",
    "study_sa = exec_sa(instances_50_10)\n",
    "print(\"tuning genetic algorithm\")\n",
    "study_ga = exec_ga(instances_50_10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style type=\"text/css\">\n",
       "#T_a9972  {\n",
       "  min-width: 110px;\n",
       "}\n",
       "#T_a9972 th {\n",
       "  min-width: 110px;\n",
       "}\n",
       "#T_a9972_row0_col0, #T_a9972_row1_col1, #T_a9972_row2_col0, #T_a9972_row3_col0, #T_a9972_row4_col1, #T_a9972_row5_col0, #T_a9972_row6_col0, #T_a9972_row7_col0, #T_a9972_row8_col2, #T_a9972_row9_col0 {\n",
       "  color: green;\n",
       "  font-weight: bold;\n",
       "}\n",
       "#T_a9972_row0_col4, #T_a9972_row1_col4, #T_a9972_row2_col4, #T_a9972_row3_col4, #T_a9972_row4_col4, #T_a9972_row5_col3, #T_a9972_row6_col3, #T_a9972_row7_col4, #T_a9972_row8_col4, #T_a9972_row9_col3 {\n",
       "  color: red;\n",
       "  font-weight: bold;\n",
       "}\n",
       "</style>\n",
       "<table id=\"T_a9972\">\n",
       "  <thead>\n",
       "    <tr>\n",
       "      <th class=\"blank level0\" >&nbsp;</th>\n",
       "      <th id=\"T_a9972_level0_col0\" class=\"col_heading level0 col0\" >LSAGA</th>\n",
       "      <th id=\"T_a9972_level0_col1\" class=\"col_heading level0 col1\" >Genetic Algorithm</th>\n",
       "      <th id=\"T_a9972_level0_col2\" class=\"col_heading level0 col2\" >Simmulated annealing</th>\n",
       "      <th id=\"T_a9972_level0_col3\" class=\"col_heading level0 col3\" >CDS</th>\n",
       "      <th id=\"T_a9972_level0_col4\" class=\"col_heading level0 col4\" >Palmer</th>\n",
       "      <th id=\"T_a9972_level0_col5\" class=\"col_heading level0 col5\" >NEH</th>\n",
       "      <th id=\"T_a9972_level0_col6\" class=\"col_heading level0 col6\" >Upper bound</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th id=\"T_a9972_level0_row0\" class=\"row_heading level0 row0\" >Instance 1</th>\n",
       "      <td id=\"T_a9972_row0_col0\" class=\"data row0 col0\" >3096</td>\n",
       "      <td id=\"T_a9972_row0_col1\" class=\"data row0 col1\" >3151</td>\n",
       "      <td id=\"T_a9972_row0_col2\" class=\"data row0 col2\" >3186</td>\n",
       "      <td id=\"T_a9972_row0_col3\" class=\"data row0 col3\" >3382</td>\n",
       "      <td id=\"T_a9972_row0_col4\" class=\"data row0 col4\" >3461</td>\n",
       "      <td id=\"T_a9972_row0_col5\" class=\"data row0 col5\" >3249</td>\n",
       "      <td id=\"T_a9972_row0_col6\" class=\"data row0 col6\" >3025</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_a9972_level0_row1\" class=\"row_heading level0 row1\" >Instance 2</th>\n",
       "      <td id=\"T_a9972_row1_col0\" class=\"data row1 col0\" >2987</td>\n",
       "      <td id=\"T_a9972_row1_col1\" class=\"data row1 col1\" >2972</td>\n",
       "      <td id=\"T_a9972_row1_col2\" class=\"data row1 col2\" >3014</td>\n",
       "      <td id=\"T_a9972_row1_col3\" class=\"data row1 col3\" >3263</td>\n",
       "      <td id=\"T_a9972_row1_col4\" class=\"data row1 col4\" >3313</td>\n",
       "      <td id=\"T_a9972_row1_col5\" class=\"data row1 col5\" >3145</td>\n",
       "      <td id=\"T_a9972_row1_col6\" class=\"data row1 col6\" >2892</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_a9972_level0_row2\" class=\"row_heading level0 row2\" >Instance 3</th>\n",
       "      <td id=\"T_a9972_row2_col0\" class=\"data row2 col0\" >2936</td>\n",
       "      <td id=\"T_a9972_row2_col1\" class=\"data row2 col1\" >2984</td>\n",
       "      <td id=\"T_a9972_row2_col2\" class=\"data row2 col2\" >2957</td>\n",
       "      <td id=\"T_a9972_row2_col3\" class=\"data row2 col3\" >3287</td>\n",
       "      <td id=\"T_a9972_row2_col4\" class=\"data row2 col4\" >3335</td>\n",
       "      <td id=\"T_a9972_row2_col5\" class=\"data row2 col5\" >3125</td>\n",
       "      <td id=\"T_a9972_row2_col6\" class=\"data row2 col6\" >2864</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_a9972_level0_row3\" class=\"row_heading level0 row3\" >Instance 4</th>\n",
       "      <td id=\"T_a9972_row3_col0\" class=\"data row3 col0\" >3135</td>\n",
       "      <td id=\"T_a9972_row3_col1\" class=\"data row3 col1\" >3137</td>\n",
       "      <td id=\"T_a9972_row3_col2\" class=\"data row3 col2\" >3192</td>\n",
       "      <td id=\"T_a9972_row3_col3\" class=\"data row3 col3\" >3393</td>\n",
       "      <td id=\"T_a9972_row3_col4\" class=\"data row3 col4\" >3511</td>\n",
       "      <td id=\"T_a9972_row3_col5\" class=\"data row3 col5\" >3214</td>\n",
       "      <td id=\"T_a9972_row3_col6\" class=\"data row3 col6\" >3064</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_a9972_level0_row4\" class=\"row_heading level0 row4\" >Instance 5</th>\n",
       "      <td id=\"T_a9972_row4_col0\" class=\"data row4 col0\" >3072</td>\n",
       "      <td id=\"T_a9972_row4_col1\" class=\"data row4 col1\" >3066</td>\n",
       "      <td id=\"T_a9972_row4_col2\" class=\"data row4 col2\" >3183</td>\n",
       "      <td id=\"T_a9972_row4_col3\" class=\"data row4 col3\" >3375</td>\n",
       "      <td id=\"T_a9972_row4_col4\" class=\"data row4 col4\" >3427</td>\n",
       "      <td id=\"T_a9972_row4_col5\" class=\"data row4 col5\" >3222</td>\n",
       "      <td id=\"T_a9972_row4_col6\" class=\"data row4 col6\" >2986</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_a9972_level0_row5\" class=\"row_heading level0 row5\" >Instance 6</th>\n",
       "      <td id=\"T_a9972_row5_col0\" class=\"data row5 col0\" >3079</td>\n",
       "      <td id=\"T_a9972_row5_col1\" class=\"data row5 col1\" >3118</td>\n",
       "      <td id=\"T_a9972_row5_col2\" class=\"data row5 col2\" >3158</td>\n",
       "      <td id=\"T_a9972_row5_col3\" class=\"data row5 col3\" >3400</td>\n",
       "      <td id=\"T_a9972_row5_col4\" class=\"data row5 col4\" >3318</td>\n",
       "      <td id=\"T_a9972_row5_col5\" class=\"data row5 col5\" >3246</td>\n",
       "      <td id=\"T_a9972_row5_col6\" class=\"data row5 col6\" >3006</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_a9972_level0_row6\" class=\"row_heading level0 row6\" >Instance 7</th>\n",
       "      <td id=\"T_a9972_row6_col0\" class=\"data row6 col0\" >3175</td>\n",
       "      <td id=\"T_a9972_row6_col1\" class=\"data row6 col1\" >3197</td>\n",
       "      <td id=\"T_a9972_row6_col2\" class=\"data row6 col2\" >3232</td>\n",
       "      <td id=\"T_a9972_row6_col3\" class=\"data row6 col3\" >3530</td>\n",
       "      <td id=\"T_a9972_row6_col4\" class=\"data row6 col4\" >3457</td>\n",
       "      <td id=\"T_a9972_row6_col5\" class=\"data row6 col5\" >3270</td>\n",
       "      <td id=\"T_a9972_row6_col6\" class=\"data row6 col6\" >3107</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_a9972_level0_row7\" class=\"row_heading level0 row7\" >Instance 8</th>\n",
       "      <td id=\"T_a9972_row7_col0\" class=\"data row7 col0\" >3104</td>\n",
       "      <td id=\"T_a9972_row7_col1\" class=\"data row7 col1\" >3106</td>\n",
       "      <td id=\"T_a9972_row7_col2\" class=\"data row7 col2\" >3144</td>\n",
       "      <td id=\"T_a9972_row7_col3\" class=\"data row7 col3\" >3371</td>\n",
       "      <td id=\"T_a9972_row7_col4\" class=\"data row7 col4\" >3382</td>\n",
       "      <td id=\"T_a9972_row7_col5\" class=\"data row7 col5\" >3219</td>\n",
       "      <td id=\"T_a9972_row7_col6\" class=\"data row7 col6\" >3039</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_a9972_level0_row8\" class=\"row_heading level0 row8\" >Instance 9</th>\n",
       "      <td id=\"T_a9972_row8_col0\" class=\"data row8 col0\" >2982</td>\n",
       "      <td id=\"T_a9972_row8_col1\" class=\"data row8 col1\" >2994</td>\n",
       "      <td id=\"T_a9972_row8_col2\" class=\"data row8 col2\" >2978</td>\n",
       "      <td id=\"T_a9972_row8_col3\" class=\"data row8 col3\" >3251</td>\n",
       "      <td id=\"T_a9972_row8_col4\" class=\"data row8 col4\" >3414</td>\n",
       "      <td id=\"T_a9972_row8_col5\" class=\"data row8 col5\" >3096</td>\n",
       "      <td id=\"T_a9972_row8_col6\" class=\"data row8 col6\" >2902</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_a9972_level0_row9\" class=\"row_heading level0 row9\" >Instance 10</th>\n",
       "      <td id=\"T_a9972_row9_col0\" class=\"data row9 col0\" >3169</td>\n",
       "      <td id=\"T_a9972_row9_col1\" class=\"data row9 col1\" >3182</td>\n",
       "      <td id=\"T_a9972_row9_col2\" class=\"data row9 col2\" >3195</td>\n",
       "      <td id=\"T_a9972_row9_col3\" class=\"data row9 col3\" >3429</td>\n",
       "      <td id=\"T_a9972_row9_col4\" class=\"data row9 col4\" >3404</td>\n",
       "      <td id=\"T_a9972_row9_col5\" class=\"data row9 col5\" >3223</td>\n",
       "      <td id=\"T_a9972_row9_col6\" class=\"data row9 col6\" >3091</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n"
      ],
      "text/plain": [
       "<pandas.io.formats.style.Styler at 0x25c2d408c10>"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "compare(instances_50_10, makes_spans_50_10, study_ga, study_sa, cds, palmer, neh)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Partial Conclusion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "From these first 5 configurations studies, it appears that our proposed hyper heuristic shows promising results as it has often outperformed the other heuristics for the different instances. We can also notice that for the instances where it didn't perform as the best algorithm, it still ranked pretty well in the overall ranking.\n",
    "\n",
    "These results seem to encourage the idea of using a simulated annealing meta heuristic for the top level with a learning mecanism for the neighbor selection during exploration as proposed in our method. But still, further exploration with the rest of the taillard configurations remains necessary to fully asses tha quality of our solution. \n",
    "\n",
    "Also, as during these demos the hyper-parameters of the top level weren't fine tuned (as it would have taken more time than allowed for this first study), it seems reasonable to expect a significant improvement if the simulated annealing hyper-parameters were studied more thoroughly, especially for the variety-degree hyper-parameter (the minimum number of dimensions in the GA hyper-parameters space to change at neighbor generation) and the length_palier hyper-parameter (the number of iterations during which the temperature remains constant, by default =1)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Rest of the taillard instances\n",
    "Not tested here, check the drive https://drive.google.com/drive/u/1/folders/1FpiJVshdQ7XhWyE0hgdxPd6e_h764wQe"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "50 jobs 20 machines"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [06:26<1:08:31,  9.00s/it] \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [18:28<3:16:20, 25.78s/it]  \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [05:07<54:31,  7.16s/it]  \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [16:29<2:55:11, 23.00s/it]  \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [02:56<31:13,  4.10s/it] \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [04:56<52:29,  6.89s/it]   \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [07:18<1:17:36, 10.19s/it] \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [04:48<51:03,  6.70s/it]   \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [07:09<1:16:08, 10.00s/it] \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [04:24<46:51,  6.15s/it]   \n"
     ]
    }
   ],
   "source": [
    "instances_50_20 = load_tai(50,20)\n",
    "makes_spans_50_20 = []\n",
    "for instance in instances_50_20:\n",
    "    saga = LSAGA(instance, variety_degree=5)\n",
    "    saga.optim(T_min=0.01)\n",
    "    makes_spans_50_20.append(saga.make_span_star)\n",
    "with open(\"lsaga_makes_spans_50_20.txt\",\"w\") as f:\n",
    "    for make_span in makes_spans_50_20:\n",
    "        f.write(str(make_span)+'\\n')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "executing heursitics\n",
      "tuning simulated annealing\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Best trial: 3. Best value: 4091: 100%|██████████| 10/10 [00:03<00:00,  3.16it/s]\n",
      "Best trial: 0. Best value: 4007: 100%|██████████| 10/10 [00:04<00:00,  2.23it/s]\n",
      "Best trial: 2. Best value: 3877: 100%|██████████| 10/10 [00:01<00:00,  5.33it/s]\n",
      "Best trial: 0. Best value: 4006: 100%|██████████| 10/10 [00:06<00:00,  1.44it/s]\n",
      "Best trial: 6. Best value: 3851: 100%|██████████| 10/10 [00:06<00:00,  1.48it/s]\n",
      "Best trial: 2. Best value: 3910: 100%|██████████| 10/10 [00:03<00:00,  2.93it/s]\n",
      "Best trial: 6. Best value: 3945: 100%|██████████| 10/10 [00:05<00:00,  1.83it/s]\n",
      "Best trial: 4. Best value: 4035: 100%|██████████| 10/10 [00:02<00:00,  3.45it/s]\n",
      "Best trial: 2. Best value: 3999: 100%|██████████| 10/10 [00:06<00:00,  1.53it/s]\n",
      "Best trial: 0. Best value: 3982: 100%|██████████| 10/10 [00:04<00:00,  2.38it/s]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "tuning genetic algorithm\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Best trial: 6. Best value: 4053: 100%|██████████| 10/10 [01:06<00:00,  6.65s/it]\n",
      "Best trial: 2. Best value: 3952: 100%|██████████| 10/10 [01:26<00:00,  8.69s/it]\n",
      "Best trial: 8. Best value: 3866: 100%|██████████| 10/10 [01:52<00:00, 11.22s/it]\n",
      "Best trial: 3. Best value: 3960: 100%|██████████| 10/10 [04:07<00:00, 24.75s/it]\n",
      "Best trial: 8. Best value: 3841: 100%|██████████| 10/10 [02:00<00:00, 12.09s/it]\n",
      "Best trial: 7. Best value: 3890: 100%|██████████| 10/10 [01:01<00:00,  6.17s/it]\n",
      "Best trial: 6. Best value: 3888: 100%|██████████| 10/10 [01:58<00:00, 11.82s/it]\n",
      "Best trial: 5. Best value: 3891: 100%|██████████| 10/10 [05:26<00:00, 32.62s/it]\n",
      "Best trial: 8. Best value: 3953: 100%|██████████| 10/10 [05:11<00:00, 31.11s/it]\n",
      "Best trial: 7. Best value: 3916: 100%|██████████| 10/10 [05:46<00:00, 34.64s/it]\n"
     ]
    }
   ],
   "source": [
    "print(\"executing heursitics\")\n",
    "cds, palmer, neh = exec_heur(instances_50_20)\n",
    "print(\"tuning simulated annealing\")\n",
    "study_sa = exec_sa(instances_50_20)\n",
    "print(\"tuning genetic algorithm\")\n",
    "study_ga = exec_ga(instances_50_20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style type=\"text/css\">\n",
       "#T_44e34  {\n",
       "  min-width: 110px;\n",
       "}\n",
       "#T_44e34 th {\n",
       "  min-width: 110px;\n",
       "}\n",
       "#T_44e34_row0_col0, #T_44e34_row1_col0, #T_44e34_row2_col0, #T_44e34_row2_col1, #T_44e34_row3_col0, #T_44e34_row4_col0, #T_44e34_row5_col0, #T_44e34_row6_col1, #T_44e34_row7_col1, #T_44e34_row8_col0, #T_44e34_row9_col1 {\n",
       "  color: green;\n",
       "  font-weight: bold;\n",
       "}\n",
       "#T_44e34_row0_col3, #T_44e34_row1_col4, #T_44e34_row2_col4, #T_44e34_row3_col3, #T_44e34_row4_col4, #T_44e34_row5_col4, #T_44e34_row6_col4, #T_44e34_row7_col4, #T_44e34_row8_col4, #T_44e34_row9_col3 {\n",
       "  color: red;\n",
       "  font-weight: bold;\n",
       "}\n",
       "</style>\n",
       "<table id=\"T_44e34\">\n",
       "  <thead>\n",
       "    <tr>\n",
       "      <th class=\"blank level0\" >&nbsp;</th>\n",
       "      <th id=\"T_44e34_level0_col0\" class=\"col_heading level0 col0\" >LSAGA</th>\n",
       "      <th id=\"T_44e34_level0_col1\" class=\"col_heading level0 col1\" >Genetic Algorithm</th>\n",
       "      <th id=\"T_44e34_level0_col2\" class=\"col_heading level0 col2\" >Simmulated annealing</th>\n",
       "      <th id=\"T_44e34_level0_col3\" class=\"col_heading level0 col3\" >CDS</th>\n",
       "      <th id=\"T_44e34_level0_col4\" class=\"col_heading level0 col4\" >Palmer</th>\n",
       "      <th id=\"T_44e34_level0_col5\" class=\"col_heading level0 col5\" >NEH</th>\n",
       "      <th id=\"T_44e34_level0_col6\" class=\"col_heading level0 col6\" >Upper bound</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th id=\"T_44e34_level0_row0\" class=\"row_heading level0 row0\" >Instance 1</th>\n",
       "      <td id=\"T_44e34_row0_col0\" class=\"data row0 col0\" >4036</td>\n",
       "      <td id=\"T_44e34_row0_col1\" class=\"data row0 col1\" >4053</td>\n",
       "      <td id=\"T_44e34_row0_col2\" class=\"data row0 col2\" >4091</td>\n",
       "      <td id=\"T_44e34_row0_col3\" class=\"data row0 col3\" >4319</td>\n",
       "      <td id=\"T_44e34_row0_col4\" class=\"data row0 col4\" >4272</td>\n",
       "      <td id=\"T_44e34_row0_col5\" class=\"data row0 col5\" >4164</td>\n",
       "      <td id=\"T_44e34_row0_col6\" class=\"data row0 col6\" >3875</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_44e34_level0_row1\" class=\"row_heading level0 row1\" >Instance 2</th>\n",
       "      <td id=\"T_44e34_row1_col0\" class=\"data row1 col0\" >3914</td>\n",
       "      <td id=\"T_44e34_row1_col1\" class=\"data row1 col1\" >3952</td>\n",
       "      <td id=\"T_44e34_row1_col2\" class=\"data row1 col2\" >4007</td>\n",
       "      <td id=\"T_44e34_row1_col3\" class=\"data row1 col3\" >4216</td>\n",
       "      <td id=\"T_44e34_row1_col4\" class=\"data row1 col4\" >4303</td>\n",
       "      <td id=\"T_44e34_row1_col5\" class=\"data row1 col5\" >4020</td>\n",
       "      <td id=\"T_44e34_row1_col6\" class=\"data row1 col6\" >3715</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_44e34_level0_row2\" class=\"row_heading level0 row2\" >Instance 3</th>\n",
       "      <td id=\"T_44e34_row2_col0\" class=\"data row2 col0\" >3866</td>\n",
       "      <td id=\"T_44e34_row2_col1\" class=\"data row2 col1\" >3866</td>\n",
       "      <td id=\"T_44e34_row2_col2\" class=\"data row2 col2\" >3877</td>\n",
       "      <td id=\"T_44e34_row2_col3\" class=\"data row2 col3\" >4203</td>\n",
       "      <td id=\"T_44e34_row2_col4\" class=\"data row2 col4\" >4210</td>\n",
       "      <td id=\"T_44e34_row2_col5\" class=\"data row2 col5\" >3877</td>\n",
       "      <td id=\"T_44e34_row2_col6\" class=\"data row2 col6\" >3668</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_44e34_level0_row3\" class=\"row_heading level0 row3\" >Instance 4</th>\n",
       "      <td id=\"T_44e34_row3_col0\" class=\"data row3 col0\" >3908</td>\n",
       "      <td id=\"T_44e34_row3_col1\" class=\"data row3 col1\" >3960</td>\n",
       "      <td id=\"T_44e34_row3_col2\" class=\"data row3 col2\" >4006</td>\n",
       "      <td id=\"T_44e34_row3_col3\" class=\"data row3 col3\" >4256</td>\n",
       "      <td id=\"T_44e34_row3_col4\" class=\"data row3 col4\" >4233</td>\n",
       "      <td id=\"T_44e34_row3_col5\" class=\"data row3 col5\" >4063</td>\n",
       "      <td id=\"T_44e34_row3_col6\" class=\"data row3 col6\" >3752</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_44e34_level0_row4\" class=\"row_heading level0 row4\" >Instance 5</th>\n",
       "      <td id=\"T_44e34_row4_col0\" class=\"data row4 col0\" >3801</td>\n",
       "      <td id=\"T_44e34_row4_col1\" class=\"data row4 col1\" >3841</td>\n",
       "      <td id=\"T_44e34_row4_col2\" class=\"data row4 col2\" >3851</td>\n",
       "      <td id=\"T_44e34_row4_col3\" class=\"data row4 col3\" >4180</td>\n",
       "      <td id=\"T_44e34_row4_col4\" class=\"data row4 col4\" >4376</td>\n",
       "      <td id=\"T_44e34_row4_col5\" class=\"data row4 col5\" >3878</td>\n",
       "      <td id=\"T_44e34_row4_col6\" class=\"data row4 col6\" >3635</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_44e34_level0_row5\" class=\"row_heading level0 row5\" >Instance 6</th>\n",
       "      <td id=\"T_44e34_row5_col0\" class=\"data row5 col0\" >3873</td>\n",
       "      <td id=\"T_44e34_row5_col1\" class=\"data row5 col1\" >3890</td>\n",
       "      <td id=\"T_44e34_row5_col2\" class=\"data row5 col2\" >3910</td>\n",
       "      <td id=\"T_44e34_row5_col3\" class=\"data row5 col3\" >4238</td>\n",
       "      <td id=\"T_44e34_row5_col4\" class=\"data row5 col4\" >4312</td>\n",
       "      <td id=\"T_44e34_row5_col5\" class=\"data row5 col5\" >3957</td>\n",
       "      <td id=\"T_44e34_row5_col6\" class=\"data row5 col6\" >3698</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_44e34_level0_row6\" class=\"row_heading level0 row6\" >Instance 7</th>\n",
       "      <td id=\"T_44e34_row6_col0\" class=\"data row6 col0\" >3921</td>\n",
       "      <td id=\"T_44e34_row6_col1\" class=\"data row6 col1\" >3888</td>\n",
       "      <td id=\"T_44e34_row6_col2\" class=\"data row6 col2\" >3945</td>\n",
       "      <td id=\"T_44e34_row6_col3\" class=\"data row6 col3\" >4134</td>\n",
       "      <td id=\"T_44e34_row6_col4\" class=\"data row6 col4\" >4306</td>\n",
       "      <td id=\"T_44e34_row6_col5\" class=\"data row6 col5\" >3988</td>\n",
       "      <td id=\"T_44e34_row6_col6\" class=\"data row6 col6\" >3716</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_44e34_level0_row7\" class=\"row_heading level0 row7\" >Instance 8</th>\n",
       "      <td id=\"T_44e34_row7_col0\" class=\"data row7 col0\" >3942</td>\n",
       "      <td id=\"T_44e34_row7_col1\" class=\"data row7 col1\" >3891</td>\n",
       "      <td id=\"T_44e34_row7_col2\" class=\"data row7 col2\" >4035</td>\n",
       "      <td id=\"T_44e34_row7_col3\" class=\"data row7 col3\" >4283</td>\n",
       "      <td id=\"T_44e34_row7_col4\" class=\"data row7 col4\" >4318</td>\n",
       "      <td id=\"T_44e34_row7_col5\" class=\"data row7 col5\" >4064</td>\n",
       "      <td id=\"T_44e34_row7_col6\" class=\"data row7 col6\" >3709</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_44e34_level0_row8\" class=\"row_heading level0 row8\" >Instance 9</th>\n",
       "      <td id=\"T_44e34_row8_col0\" class=\"data row8 col0\" >3921</td>\n",
       "      <td id=\"T_44e34_row8_col1\" class=\"data row8 col1\" >3953</td>\n",
       "      <td id=\"T_44e34_row8_col2\" class=\"data row8 col2\" >3999</td>\n",
       "      <td id=\"T_44e34_row8_col3\" class=\"data row8 col3\" >4219</td>\n",
       "      <td id=\"T_44e34_row8_col4\" class=\"data row8 col4\" >4547</td>\n",
       "      <td id=\"T_44e34_row8_col5\" class=\"data row8 col5\" >4022</td>\n",
       "      <td id=\"T_44e34_row8_col6\" class=\"data row8 col6\" >3765</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_44e34_level0_row9\" class=\"row_heading level0 row9\" >Instance 10</th>\n",
       "      <td id=\"T_44e34_row9_col0\" class=\"data row9 col0\" >3919</td>\n",
       "      <td id=\"T_44e34_row9_col1\" class=\"data row9 col1\" >3916</td>\n",
       "      <td id=\"T_44e34_row9_col2\" class=\"data row9 col2\" >3982</td>\n",
       "      <td id=\"T_44e34_row9_col3\" class=\"data row9 col3\" >4264</td>\n",
       "      <td id=\"T_44e34_row9_col4\" class=\"data row9 col4\" >4197</td>\n",
       "      <td id=\"T_44e34_row9_col5\" class=\"data row9 col5\" >3991</td>\n",
       "      <td id=\"T_44e34_row9_col6\" class=\"data row9 col6\" >3777</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n"
      ],
      "text/plain": [
       "<pandas.io.formats.style.Styler at 0x1f2ffb72090>"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "compare(instances_50_20, makes_spans_50_20, study_ga, study_sa, cds, palmer, neh)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "100 jobs 5 machines"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [02:35<27:35,  3.62s/it]  \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [01:42<18:14,  2.40s/it] \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [02:29<26:26,  3.47s/it]  \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [12:51<2:16:42, 17.95s/it] \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [02:32<27:03,  3.55s/it] \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [03:40<39:01,  5.12s/it]  \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [02:11<23:13,  3.05s/it] \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [03:12<34:10,  4.49s/it]   \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [05:46<1:01:21,  8.06s/it] \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [03:55<41:44,  5.48s/it]   \n"
     ]
    }
   ],
   "source": [
    "instances_100_5 = load_tai(100,5)\n",
    "makes_spans_100_5 = []\n",
    "for instance in instances_100_5:\n",
    "    saga = LSAGA(instance, variety_degree=5)\n",
    "    saga.optim(T_min=0.01)\n",
    "    makes_spans_100_5.append(saga.make_span_star)\n",
    "with open(\"lsaga_makes_spans_100_5.txt\",\"w\") as f:\n",
    "    for make_span in makes_spans_50_20:\n",
    "        f.write(str(make_span)+'\\n')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "executing heursitics\n",
      "tuning simulated annealing\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Best trial: 0. Best value: 5505: 100%|██████████| 10/10 [00:04<00:00,  2.44it/s]\n",
      "Best trial: 1. Best value: 5316: 100%|██████████| 10/10 [00:03<00:00,  3.11it/s]\n",
      "Best trial: 6. Best value: 5287: 100%|██████████| 10/10 [00:05<00:00,  1.76it/s]\n",
      "Best trial: 6. Best value: 5044: 100%|██████████| 10/10 [00:04<00:00,  2.11it/s]\n",
      "Best trial: 3. Best value: 5311: 100%|██████████| 10/10 [00:03<00:00,  3.28it/s]\n",
      "Best trial: 0. Best value: 5174: 100%|██████████| 10/10 [00:04<00:00,  2.04it/s]\n",
      "Best trial: 1. Best value: 5305: 100%|██████████| 10/10 [00:04<00:00,  2.46it/s]\n",
      "Best trial: 9. Best value: 5148: 100%|██████████| 10/10 [00:04<00:00,  2.09it/s]\n",
      "Best trial: 6. Best value: 5506: 100%|██████████| 10/10 [00:02<00:00,  4.37it/s]\n",
      "Best trial: 3. Best value: 5347: 100%|██████████| 10/10 [00:04<00:00,  2.29it/s]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "tuning genetic algorithm\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Best trial: 4. Best value: 5493: 100%|██████████| 10/10 [01:11<00:00,  7.16s/it]\n",
      "Best trial: 0. Best value: 5316: 100%|██████████| 10/10 [01:02<00:00,  6.26s/it]\n",
      "Best trial: 7. Best value: 5221: 100%|██████████| 10/10 [01:29<00:00,  8.98s/it]\n",
      "Best trial: 7. Best value: 5043: 100%|██████████| 10/10 [00:42<00:00,  4.27s/it]\n",
      "Best trial: 2. Best value: 5255: 100%|██████████| 10/10 [00:25<00:00,  2.58s/it]\n",
      "Best trial: 7. Best value: 5145: 100%|██████████| 10/10 [00:47<00:00,  4.74s/it]\n",
      "Best trial: 1. Best value: 5283: 100%|██████████| 10/10 [01:26<00:00,  8.66s/it]\n",
      "Best trial: 0. Best value: 5144: 100%|██████████| 10/10 [00:36<00:00,  3.67s/it]\n",
      "Best trial: 9. Best value: 5492: 100%|██████████| 10/10 [02:44<00:00, 16.40s/it]\n",
      "Best trial: 7. Best value: 5367: 100%|██████████| 10/10 [01:12<00:00,  7.24s/it]\n"
     ]
    }
   ],
   "source": [
    "print(\"executing heursitics\")\n",
    "cds, palmer, neh = exec_heur(instances_100_5)\n",
    "print(\"tuning simulated annealing\")\n",
    "study_sa = exec_sa(instances_100_5)\n",
    "print(\"tuning genetic algorithm\")\n",
    "study_ga = exec_ga(instances_100_5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style type=\"text/css\">\n",
       "#T_a4272  {\n",
       "  min-width: 110px;\n",
       "}\n",
       "#T_a4272 th {\n",
       "  min-width: 110px;\n",
       "}\n",
       "#T_a4272_row0_col0, #T_a4272_row0_col1, #T_a4272_row1_col0, #T_a4272_row2_col0, #T_a4272_row3_col0, #T_a4272_row4_col1, #T_a4272_row5_col0, #T_a4272_row6_col0, #T_a4272_row6_col1, #T_a4272_row7_col0, #T_a4272_row8_col0, #T_a4272_row9_col0 {\n",
       "  color: green;\n",
       "  font-weight: bold;\n",
       "}\n",
       "#T_a4272_row0_col4, #T_a4272_row1_col3, #T_a4272_row2_col3, #T_a4272_row3_col3, #T_a4272_row4_col3, #T_a4272_row5_col4, #T_a4272_row6_col3, #T_a4272_row7_col3, #T_a4272_row8_col3, #T_a4272_row9_col3 {\n",
       "  color: red;\n",
       "  font-weight: bold;\n",
       "}\n",
       "</style>\n",
       "<table id=\"T_a4272\">\n",
       "  <thead>\n",
       "    <tr>\n",
       "      <th class=\"blank level0\" >&nbsp;</th>\n",
       "      <th id=\"T_a4272_level0_col0\" class=\"col_heading level0 col0\" >LSAGA</th>\n",
       "      <th id=\"T_a4272_level0_col1\" class=\"col_heading level0 col1\" >Genetic Algorithm</th>\n",
       "      <th id=\"T_a4272_level0_col2\" class=\"col_heading level0 col2\" >Simmulated annealing</th>\n",
       "      <th id=\"T_a4272_level0_col3\" class=\"col_heading level0 col3\" >CDS</th>\n",
       "      <th id=\"T_a4272_level0_col4\" class=\"col_heading level0 col4\" >Palmer</th>\n",
       "      <th id=\"T_a4272_level0_col5\" class=\"col_heading level0 col5\" >NEH</th>\n",
       "      <th id=\"T_a4272_level0_col6\" class=\"col_heading level0 col6\" >Upper bound</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th id=\"T_a4272_level0_row0\" class=\"row_heading level0 row0\" >Instance 1</th>\n",
       "      <td id=\"T_a4272_row0_col0\" class=\"data row0 col0\" >5493</td>\n",
       "      <td id=\"T_a4272_row0_col1\" class=\"data row0 col1\" >5493</td>\n",
       "      <td id=\"T_a4272_row0_col2\" class=\"data row0 col2\" >5505</td>\n",
       "      <td id=\"T_a4272_row0_col3\" class=\"data row0 col3\" >5602</td>\n",
       "      <td id=\"T_a4272_row0_col4\" class=\"data row0 col4\" >5749</td>\n",
       "      <td id=\"T_a4272_row0_col5\" class=\"data row0 col5\" >5538</td>\n",
       "      <td id=\"T_a4272_row0_col6\" class=\"data row0 col6\" >5493</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_a4272_level0_row1\" class=\"row_heading level0 row1\" >Instance 2</th>\n",
       "      <td id=\"T_a4272_row1_col0\" class=\"data row1 col0\" >5299</td>\n",
       "      <td id=\"T_a4272_row1_col1\" class=\"data row1 col1\" >5316</td>\n",
       "      <td id=\"T_a4272_row1_col2\" class=\"data row1 col2\" >5316</td>\n",
       "      <td id=\"T_a4272_row1_col3\" class=\"data row1 col3\" >5548</td>\n",
       "      <td id=\"T_a4272_row1_col4\" class=\"data row1 col4\" >5316</td>\n",
       "      <td id=\"T_a4272_row1_col5\" class=\"data row1 col5\" >5379</td>\n",
       "      <td id=\"T_a4272_row1_col6\" class=\"data row1 col6\" >5268</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_a4272_level0_row2\" class=\"row_heading level0 row2\" >Instance 3</th>\n",
       "      <td id=\"T_a4272_row2_col0\" class=\"data row2 col0\" >5212</td>\n",
       "      <td id=\"T_a4272_row2_col1\" class=\"data row2 col1\" >5221</td>\n",
       "      <td id=\"T_a4272_row2_col2\" class=\"data row2 col2\" >5287</td>\n",
       "      <td id=\"T_a4272_row2_col3\" class=\"data row2 col3\" >5452</td>\n",
       "      <td id=\"T_a4272_row2_col4\" class=\"data row2 col4\" >5325</td>\n",
       "      <td id=\"T_a4272_row2_col5\" class=\"data row2 col5\" >5306</td>\n",
       "      <td id=\"T_a4272_row2_col6\" class=\"data row2 col6\" >5175</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_a4272_level0_row3\" class=\"row_heading level0 row3\" >Instance 4</th>\n",
       "      <td id=\"T_a4272_row3_col0\" class=\"data row3 col0\" >5032</td>\n",
       "      <td id=\"T_a4272_row3_col1\" class=\"data row3 col1\" >5043</td>\n",
       "      <td id=\"T_a4272_row3_col2\" class=\"data row3 col2\" >5044</td>\n",
       "      <td id=\"T_a4272_row3_col3\" class=\"data row3 col3\" >5273</td>\n",
       "      <td id=\"T_a4272_row3_col4\" class=\"data row3 col4\" >5049</td>\n",
       "      <td id=\"T_a4272_row3_col5\" class=\"data row3 col5\" >5114</td>\n",
       "      <td id=\"T_a4272_row3_col6\" class=\"data row3 col6\" >5014</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_a4272_level0_row4\" class=\"row_heading level0 row4\" >Instance 5</th>\n",
       "      <td id=\"T_a4272_row4_col0\" class=\"data row4 col0\" >5267</td>\n",
       "      <td id=\"T_a4272_row4_col1\" class=\"data row4 col1\" >5255</td>\n",
       "      <td id=\"T_a4272_row4_col2\" class=\"data row4 col2\" >5311</td>\n",
       "      <td id=\"T_a4272_row4_col3\" class=\"data row4 col3\" >5484</td>\n",
       "      <td id=\"T_a4272_row4_col4\" class=\"data row4 col4\" >5317</td>\n",
       "      <td id=\"T_a4272_row4_col5\" class=\"data row4 col5\" >5328</td>\n",
       "      <td id=\"T_a4272_row4_col6\" class=\"data row4 col6\" >5250</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_a4272_level0_row5\" class=\"row_heading level0 row5\" >Instance 6</th>\n",
       "      <td id=\"T_a4272_row5_col0\" class=\"data row5 col0\" >5140</td>\n",
       "      <td id=\"T_a4272_row5_col1\" class=\"data row5 col1\" >5145</td>\n",
       "      <td id=\"T_a4272_row5_col2\" class=\"data row5 col2\" >5174</td>\n",
       "      <td id=\"T_a4272_row5_col3\" class=\"data row5 col3\" >5203</td>\n",
       "      <td id=\"T_a4272_row5_col4\" class=\"data row5 col4\" >5274</td>\n",
       "      <td id=\"T_a4272_row5_col5\" class=\"data row5 col5\" >5200</td>\n",
       "      <td id=\"T_a4272_row5_col6\" class=\"data row5 col6\" >5135</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_a4272_level0_row6\" class=\"row_heading level0 row6\" >Instance 7</th>\n",
       "      <td id=\"T_a4272_row6_col0\" class=\"data row6 col0\" >5283</td>\n",
       "      <td id=\"T_a4272_row6_col1\" class=\"data row6 col1\" >5283</td>\n",
       "      <td id=\"T_a4272_row6_col2\" class=\"data row6 col2\" >5305</td>\n",
       "      <td id=\"T_a4272_row6_col3\" class=\"data row6 col3\" >5561</td>\n",
       "      <td id=\"T_a4272_row6_col4\" class=\"data row6 col4\" >5376</td>\n",
       "      <td id=\"T_a4272_row6_col5\" class=\"data row6 col5\" >5351</td>\n",
       "      <td id=\"T_a4272_row6_col6\" class=\"data row6 col6\" >5246</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_a4272_level0_row7\" class=\"row_heading level0 row7\" >Instance 8</th>\n",
       "      <td id=\"T_a4272_row7_col0\" class=\"data row7 col0\" >5137</td>\n",
       "      <td id=\"T_a4272_row7_col1\" class=\"data row7 col1\" >5144</td>\n",
       "      <td id=\"T_a4272_row7_col2\" class=\"data row7 col2\" >5148</td>\n",
       "      <td id=\"T_a4272_row7_col3\" class=\"data row7 col3\" >5387</td>\n",
       "      <td id=\"T_a4272_row7_col4\" class=\"data row7 col4\" >5263</td>\n",
       "      <td id=\"T_a4272_row7_col5\" class=\"data row7 col5\" >5204</td>\n",
       "      <td id=\"T_a4272_row7_col6\" class=\"data row7 col6\" >5106</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_a4272_level0_row8\" class=\"row_heading level0 row8\" >Instance 9</th>\n",
       "      <td id=\"T_a4272_row8_col0\" class=\"data row8 col0\" >5487</td>\n",
       "      <td id=\"T_a4272_row8_col1\" class=\"data row8 col1\" >5492</td>\n",
       "      <td id=\"T_a4272_row8_col2\" class=\"data row8 col2\" >5506</td>\n",
       "      <td id=\"T_a4272_row8_col3\" class=\"data row8 col3\" >5758</td>\n",
       "      <td id=\"T_a4272_row8_col4\" class=\"data row8 col4\" >5606</td>\n",
       "      <td id=\"T_a4272_row8_col5\" class=\"data row8 col5\" >5588</td>\n",
       "      <td id=\"T_a4272_row8_col6\" class=\"data row8 col6\" >5454</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_a4272_level0_row9\" class=\"row_heading level0 row9\" >Instance 10</th>\n",
       "      <td id=\"T_a4272_row9_col0\" class=\"data row9 col0\" >5338</td>\n",
       "      <td id=\"T_a4272_row9_col1\" class=\"data row9 col1\" >5367</td>\n",
       "      <td id=\"T_a4272_row9_col2\" class=\"data row9 col2\" >5347</td>\n",
       "      <td id=\"T_a4272_row9_col3\" class=\"data row9 col3\" >5708</td>\n",
       "      <td id=\"T_a4272_row9_col4\" class=\"data row9 col4\" >5427</td>\n",
       "      <td id=\"T_a4272_row9_col5\" class=\"data row9 col5\" >5388</td>\n",
       "      <td id=\"T_a4272_row9_col6\" class=\"data row9 col6\" >5328</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n"
      ],
      "text/plain": [
       "<pandas.io.formats.style.Styler at 0x1f296c78c90>"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "compare(instances_100_5, makes_spans_100_5, study_ga, study_sa, cds, palmer, neh)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "100 jobs 10 machines"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [10:24<1:50:35, 14.52s/it] \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [20:21<3:36:26, 28.42s/it] \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [25:56<4:35:41, 36.19s/it]  \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [20:02<3:33:01, 27.97s/it] \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [05:31<58:44,  7.71s/it]   \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [10:18<1:49:34, 14.39s/it] \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [04:37<49:10,  6.46s/it]   \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [12:10<2:09:26, 16.99s/it] \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [06:47<1:12:13,  9.48s/it] \n",
      "Temperature 0.01077526366430583:   9%|▊         | 43/500 [08:12<1:27:16, 11.46s/it] \n"
     ]
    }
   ],
   "source": [
    "instances_100_10 = load_tai(100,10)\n",
    "makes_spans_100_10 = []\n",
    "for instance in instances_100_10:\n",
    "    saga = LSAGA(instance, variety_degree=3)\n",
    "    saga.optim(T_min=0.01)\n",
    "    makes_spans_100_10.append(saga.make_span_star)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "executing heursitics\n",
      "tuning simulated annealing\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Best trial: 5. Best value: 5955: 100%|██████████| 10/10 [00:11<00:00,  1.18s/it]\n",
      "Best trial: 7. Best value: 5536: 100%|██████████| 10/10 [00:08<00:00,  1.12it/s]\n",
      "Best trial: 5. Best value: 5803: 100%|██████████| 10/10 [00:06<00:00,  1.56it/s]\n",
      "Best trial: 2. Best value: 6015: 100%|██████████| 10/10 [00:14<00:00,  1.41s/it]\n",
      "Best trial: 7. Best value: 5766: 100%|██████████| 10/10 [00:11<00:00,  1.16s/it]\n",
      "Best trial: 3. Best value: 5383: 100%|██████████| 10/10 [00:12<00:00,  1.21s/it]\n",
      "Best trial: 5. Best value: 5744: 100%|██████████| 10/10 [00:09<00:00,  1.10it/s]\n",
      "Best trial: 3. Best value: 5881: 100%|██████████| 10/10 [00:06<00:00,  1.62it/s]\n",
      "Best trial: 0. Best value: 6014: 100%|██████████| 10/10 [00:09<00:00,  1.08it/s]\n",
      "Best trial: 8. Best value: 5987: 100%|██████████| 10/10 [00:06<00:00,  1.48it/s]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "tuning genetic algorithm\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Best trial: 2. Best value: 5885: 100%|██████████| 10/10 [03:25<00:00, 20.58s/it]\n",
      "Best trial: 5. Best value: 5503: 100%|██████████| 10/10 [02:59<00:00, 17.93s/it]\n",
      "Best trial: 3. Best value: 5781: 100%|██████████| 10/10 [01:43<00:00, 10.36s/it]\n",
      "Best trial: 3. Best value: 5966: 100%|██████████| 10/10 [02:20<00:00, 14.04s/it]\n",
      "Best trial: 3. Best value: 5636: 100%|██████████| 10/10 [03:27<00:00, 20.73s/it]\n",
      "Best trial: 4. Best value: 5409: 100%|██████████| 10/10 [02:54<00:00, 17.43s/it]\n",
      "Best trial: 2. Best value: 5744: 100%|██████████| 10/10 [01:39<00:00,  9.92s/it]\n",
      "Best trial: 3. Best value: 5776: 100%|██████████| 10/10 [01:32<00:00,  9.24s/it]\n",
      "Best trial: 5. Best value: 5979: 100%|██████████| 10/10 [02:21<00:00, 14.14s/it]\n",
      "Best trial: 2. Best value: 5959: 100%|██████████| 10/10 [02:04<00:00, 12.44s/it]\n"
     ]
    }
   ],
   "source": [
    "print(\"executing heursitics\")\n",
    "cds, palmer, neh = exec_heur(instances_100_10)\n",
    "print(\"tuning simulated annealing\")\n",
    "study_sa = exec_sa(instances_100_10)\n",
    "print(\"tuning genetic algorithm\")\n",
    "study_ga = exec_ga(instances_100_10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style type=\"text/css\">\n",
       "#T_fcaed  {\n",
       "  min-width: 110px;\n",
       "}\n",
       "#T_fcaed th {\n",
       "  min-width: 110px;\n",
       "}\n",
       "#T_fcaed_row0_col1, #T_fcaed_row1_col0, #T_fcaed_row2_col0, #T_fcaed_row3_col0, #T_fcaed_row4_col1, #T_fcaed_row5_col2, #T_fcaed_row6_col0, #T_fcaed_row7_col0, #T_fcaed_row8_col0, #T_fcaed_row8_col1, #T_fcaed_row9_col1 {\n",
       "  color: green;\n",
       "  font-weight: bold;\n",
       "}\n",
       "#T_fcaed_row0_col3, #T_fcaed_row1_col4, #T_fcaed_row2_col4, #T_fcaed_row3_col3, #T_fcaed_row4_col4, #T_fcaed_row5_col4, #T_fcaed_row6_col4, #T_fcaed_row7_col4, #T_fcaed_row8_col3, #T_fcaed_row9_col3 {\n",
       "  color: red;\n",
       "  font-weight: bold;\n",
       "}\n",
       "</style>\n",
       "<table id=\"T_fcaed\">\n",
       "  <thead>\n",
       "    <tr>\n",
       "      <th class=\"blank level0\" >&nbsp;</th>\n",
       "      <th id=\"T_fcaed_level0_col0\" class=\"col_heading level0 col0\" >LSAGA</th>\n",
       "      <th id=\"T_fcaed_level0_col1\" class=\"col_heading level0 col1\" >Genetic Algorithm</th>\n",
       "      <th id=\"T_fcaed_level0_col2\" class=\"col_heading level0 col2\" >Simmulated annealing</th>\n",
       "      <th id=\"T_fcaed_level0_col3\" class=\"col_heading level0 col3\" >CDS</th>\n",
       "      <th id=\"T_fcaed_level0_col4\" class=\"col_heading level0 col4\" >Palmer</th>\n",
       "      <th id=\"T_fcaed_level0_col5\" class=\"col_heading level0 col5\" >NEH</th>\n",
       "      <th id=\"T_fcaed_level0_col6\" class=\"col_heading level0 col6\" >Upper bound</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th id=\"T_fcaed_level0_row0\" class=\"row_heading level0 row0\" >Instance 1</th>\n",
       "      <td id=\"T_fcaed_row0_col0\" class=\"data row0 col0\" >5887</td>\n",
       "      <td id=\"T_fcaed_row0_col1\" class=\"data row0 col1\" >5885</td>\n",
       "      <td id=\"T_fcaed_row0_col2\" class=\"data row0 col2\" >5955</td>\n",
       "      <td id=\"T_fcaed_row0_col3\" class=\"data row0 col3\" >6198</td>\n",
       "      <td id=\"T_fcaed_row0_col4\" class=\"data row0 col4\" >6161</td>\n",
       "      <td id=\"T_fcaed_row0_col5\" class=\"data row0 col5\" >6027</td>\n",
       "      <td id=\"T_fcaed_row0_col6\" class=\"data row0 col6\" >5770</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_fcaed_level0_row1\" class=\"row_heading level0 row1\" >Instance 2</th>\n",
       "      <td id=\"T_fcaed_row1_col0\" class=\"data row1 col0\" >5428</td>\n",
       "      <td id=\"T_fcaed_row1_col1\" class=\"data row1 col1\" >5503</td>\n",
       "      <td id=\"T_fcaed_row1_col2\" class=\"data row1 col2\" >5536</td>\n",
       "      <td id=\"T_fcaed_row1_col3\" class=\"data row1 col3\" >5851</td>\n",
       "      <td id=\"T_fcaed_row1_col4\" class=\"data row1 col4\" >5889</td>\n",
       "      <td id=\"T_fcaed_row1_col5\" class=\"data row1 col5\" >5569</td>\n",
       "      <td id=\"T_fcaed_row1_col6\" class=\"data row1 col6\" >5349</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_fcaed_level0_row2\" class=\"row_heading level0 row2\" >Instance 3</th>\n",
       "      <td id=\"T_fcaed_row2_col0\" class=\"data row2 col0\" >5764</td>\n",
       "      <td id=\"T_fcaed_row2_col1\" class=\"data row2 col1\" >5781</td>\n",
       "      <td id=\"T_fcaed_row2_col2\" class=\"data row2 col2\" >5803</td>\n",
       "      <td id=\"T_fcaed_row2_col3\" class=\"data row2 col3\" >6029</td>\n",
       "      <td id=\"T_fcaed_row2_col4\" class=\"data row2 col4\" >6119</td>\n",
       "      <td id=\"T_fcaed_row2_col5\" class=\"data row2 col5\" >5857</td>\n",
       "      <td id=\"T_fcaed_row2_col6\" class=\"data row2 col6\" >5677</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_fcaed_level0_row3\" class=\"row_heading level0 row3\" >Instance 4</th>\n",
       "      <td id=\"T_fcaed_row3_col0\" class=\"data row3 col0\" >5878</td>\n",
       "      <td id=\"T_fcaed_row3_col1\" class=\"data row3 col1\" >5966</td>\n",
       "      <td id=\"T_fcaed_row3_col2\" class=\"data row3 col2\" >6015</td>\n",
       "      <td id=\"T_fcaed_row3_col3\" class=\"data row3 col3\" >6408</td>\n",
       "      <td id=\"T_fcaed_row3_col4\" class=\"data row3 col4\" >6329</td>\n",
       "      <td id=\"T_fcaed_row3_col5\" class=\"data row3 col5\" >6044</td>\n",
       "      <td id=\"T_fcaed_row3_col6\" class=\"data row3 col6\" >5791</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_fcaed_level0_row4\" class=\"row_heading level0 row4\" >Instance 5</th>\n",
       "      <td id=\"T_fcaed_row4_col0\" class=\"data row4 col0\" >5670</td>\n",
       "      <td id=\"T_fcaed_row4_col1\" class=\"data row4 col1\" >5636</td>\n",
       "      <td id=\"T_fcaed_row4_col2\" class=\"data row4 col2\" >5766</td>\n",
       "      <td id=\"T_fcaed_row4_col3\" class=\"data row4 col3\" >6018</td>\n",
       "      <td id=\"T_fcaed_row4_col4\" class=\"data row4 col4\" >6070</td>\n",
       "      <td id=\"T_fcaed_row4_col5\" class=\"data row4 col5\" >5807</td>\n",
       "      <td id=\"T_fcaed_row4_col6\" class=\"data row4 col6\" >5468</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_fcaed_level0_row5\" class=\"row_heading level0 row5\" >Instance 6</th>\n",
       "      <td id=\"T_fcaed_row5_col0\" class=\"data row5 col0\" >5395</td>\n",
       "      <td id=\"T_fcaed_row5_col1\" class=\"data row5 col1\" >5409</td>\n",
       "      <td id=\"T_fcaed_row5_col2\" class=\"data row5 col2\" >5383</td>\n",
       "      <td id=\"T_fcaed_row5_col3\" class=\"data row5 col3\" >5751</td>\n",
       "      <td id=\"T_fcaed_row5_col4\" class=\"data row5 col4\" >5870</td>\n",
       "      <td id=\"T_fcaed_row5_col5\" class=\"data row5 col5\" >5508</td>\n",
       "      <td id=\"T_fcaed_row5_col6\" class=\"data row5 col6\" >5303</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_fcaed_level0_row6\" class=\"row_heading level0 row6\" >Instance 7</th>\n",
       "      <td id=\"T_fcaed_row6_col0\" class=\"data row6 col0\" >5706</td>\n",
       "      <td id=\"T_fcaed_row6_col1\" class=\"data row6 col1\" >5744</td>\n",
       "      <td id=\"T_fcaed_row6_col2\" class=\"data row6 col2\" >5744</td>\n",
       "      <td id=\"T_fcaed_row6_col3\" class=\"data row6 col3\" >6202</td>\n",
       "      <td id=\"T_fcaed_row6_col4\" class=\"data row6 col4\" >6442</td>\n",
       "      <td id=\"T_fcaed_row6_col5\" class=\"data row6 col5\" >5744</td>\n",
       "      <td id=\"T_fcaed_row6_col6\" class=\"data row6 col6\" >5599</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_fcaed_level0_row7\" class=\"row_heading level0 row7\" >Instance 8</th>\n",
       "      <td id=\"T_fcaed_row7_col0\" class=\"data row7 col0\" >5750</td>\n",
       "      <td id=\"T_fcaed_row7_col1\" class=\"data row7 col1\" >5776</td>\n",
       "      <td id=\"T_fcaed_row7_col2\" class=\"data row7 col2\" >5881</td>\n",
       "      <td id=\"T_fcaed_row7_col3\" class=\"data row7 col3\" >6146</td>\n",
       "      <td id=\"T_fcaed_row7_col4\" class=\"data row7 col4\" >6168</td>\n",
       "      <td id=\"T_fcaed_row7_col5\" class=\"data row7 col5\" >5938</td>\n",
       "      <td id=\"T_fcaed_row7_col6\" class=\"data row7 col6\" >5623</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_fcaed_level0_row8\" class=\"row_heading level0 row8\" >Instance 9</th>\n",
       "      <td id=\"T_fcaed_row8_col0\" class=\"data row8 col0\" >5979</td>\n",
       "      <td id=\"T_fcaed_row8_col1\" class=\"data row8 col1\" >5979</td>\n",
       "      <td id=\"T_fcaed_row8_col2\" class=\"data row8 col2\" >6014</td>\n",
       "      <td id=\"T_fcaed_row8_col3\" class=\"data row8 col3\" >6349</td>\n",
       "      <td id=\"T_fcaed_row8_col4\" class=\"data row8 col4\" >6081</td>\n",
       "      <td id=\"T_fcaed_row8_col5\" class=\"data row8 col5\" >6089</td>\n",
       "      <td id=\"T_fcaed_row8_col6\" class=\"data row8 col6\" >5875</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_fcaed_level0_row9\" class=\"row_heading level0 row9\" >Instance 10</th>\n",
       "      <td id=\"T_fcaed_row9_col0\" class=\"data row9 col0\" >5962</td>\n",
       "      <td id=\"T_fcaed_row9_col1\" class=\"data row9 col1\" >5959</td>\n",
       "      <td id=\"T_fcaed_row9_col2\" class=\"data row9 col2\" >5987</td>\n",
       "      <td id=\"T_fcaed_row9_col3\" class=\"data row9 col3\" >6439</td>\n",
       "      <td id=\"T_fcaed_row9_col4\" class=\"data row9 col4\" >6259</td>\n",
       "      <td id=\"T_fcaed_row9_col5\" class=\"data row9 col5\" >6022</td>\n",
       "      <td id=\"T_fcaed_row9_col6\" class=\"data row9 col6\" >5845</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n"
      ],
      "text/plain": [
       "<pandas.io.formats.style.Styler at 0x1f297626fd0>"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "compare(instances_100_10, makes_spans_100_10, study_ga, study_sa, cds, palmer, neh)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "200 jobs 10 machines"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Temperature 0.38742048900000015:   2%|▏         | 9/500 [08:27<7:41:04, 56.34s/it]\n"
     ]
    },
    {
     "ename": "KeyboardInterrupt",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
      "Cell \u001b[1;32mIn[29], line 5\u001b[0m\n\u001b[0;32m      3\u001b[0m \u001b[38;5;28;01mfor\u001b[39;00m instance \u001b[38;5;129;01min\u001b[39;00m instances_200_10:\n\u001b[0;32m      4\u001b[0m     saga \u001b[38;5;241m=\u001b[39m LSAGA(instance, variety_degree\u001b[38;5;241m=\u001b[39m\u001b[38;5;241m5\u001b[39m)\n\u001b[1;32m----> 5\u001b[0m     \u001b[43msaga\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43moptim\u001b[49m\u001b[43m(\u001b[49m\u001b[43mT_min\u001b[49m\u001b[38;5;241;43m=\u001b[39;49m\u001b[38;5;241;43m0.01\u001b[39;49m\u001b[43m)\u001b[49m\n\u001b[0;32m      6\u001b[0m     makes_spans_200_10\u001b[38;5;241m.\u001b[39mappend(saga\u001b[38;5;241m.\u001b[39mmake_span_star)\n",
      "Cell \u001b[1;32mIn[6], line 583\u001b[0m, in \u001b[0;36mLSAGA.optim\u001b[1;34m(self, T, T_min, alpha, nb_iter, init_method, neigh_method, length_palier, jump_rate, jump_ratio, debug, trace)\u001b[0m\n\u001b[0;32m    581\u001b[0m new_hps \u001b[38;5;241m=\u001b[39m \u001b[38;5;28mself\u001b[39m\u001b[38;5;241m.\u001b[39mgenerate_neigh_hps(hps, T)\n\u001b[0;32m    582\u001b[0m \u001b[38;5;66;03m#compute the energy difference\u001b[39;00m\n\u001b[1;32m--> 583\u001b[0m neigh_seq \u001b[38;5;241m=\u001b[39m \u001b[38;5;28;43mself\u001b[39;49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mgenetic_algorithm\u001b[49m\u001b[43m(\u001b[49m\u001b[38;5;241;43m*\u001b[39;49m\u001b[38;5;241;43m*\u001b[39;49m\u001b[43mnew_hps\u001b[49m\u001b[43m)\u001b[49m\n\u001b[0;32m    584\u001b[0m neigh_make_span \u001b[38;5;241m=\u001b[39m \u001b[38;5;28mself\u001b[39m\u001b[38;5;241m.\u001b[39mevaluate_makespan(neigh_seq)\n\u001b[0;32m    585\u001b[0m delta \u001b[38;5;241m=\u001b[39m current_make_span \u001b[38;5;241m-\u001b[39m neigh_make_span\n",
      "Cell \u001b[1;32mIn[6], line 432\u001b[0m, in \u001b[0;36mLSAGA.genetic_algorithm\u001b[1;34m(self, init_type, selection_type, crossover_type, replacement_type, population_size, pool_size, crossover_rate, mutation_rate, num_iterations, max_stagnation, k_points)\u001b[0m\n\u001b[0;32m    429\u001b[0m     child2 \u001b[38;5;241m=\u001b[39m \u001b[38;5;28mself\u001b[39m\u001b[38;5;241m.\u001b[39mmutate(child2, mutation_rate)\n\u001b[0;32m    430\u001b[0m     offspring\u001b[38;5;241m.\u001b[39mextend([child1, child2])\n\u001b[1;32m--> 432\u001b[0m population \u001b[38;5;241m=\u001b[39m \u001b[38;5;28;43mself\u001b[39;49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mreplace_population\u001b[49m\u001b[43m(\u001b[49m\u001b[43mreplacement_type\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43mpopulation\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43mparents\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43moffspring\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43mpopulation_size\u001b[49m\u001b[43m)\u001b[49m\n\u001b[0;32m    433\u001b[0m population\u001b[38;5;241m.\u001b[39msort(key\u001b[38;5;241m=\u001b[39m\u001b[38;5;28;01mlambda\u001b[39;00m x: \u001b[38;5;28mself\u001b[39m\u001b[38;5;241m.\u001b[39mevaluate_makespan(x))\n\u001b[0;32m    435\u001b[0m current_best_solution \u001b[38;5;241m=\u001b[39m population[\u001b[38;5;241m0\u001b[39m]\n",
      "Cell \u001b[1;32mIn[6], line 386\u001b[0m, in \u001b[0;36mLSAGA.replace_population\u001b[1;34m(self, replacement_type, population, parents, offspring, population_size)\u001b[0m\n\u001b[0;32m    383\u001b[0m     \u001b[38;5;28;01mreturn\u001b[39;00m population_without_parents \u001b[38;5;241m+\u001b[39m combined_sub_population[:\u001b[38;5;28mlen\u001b[39m(parents)]\n\u001b[0;32m    385\u001b[0m \u001b[38;5;28;01melse\u001b[39;00m:\n\u001b[1;32m--> 386\u001b[0m     \u001b[38;5;28;01mreturn\u001b[39;00m \u001b[43mselect_population\u001b[49m\u001b[43m(\u001b[49m\u001b[43mreplacement_type\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43mpopulation\u001b[49m\u001b[43m \u001b[49m\u001b[38;5;241;43m+\u001b[39;49m\u001b[43m \u001b[49m\u001b[43moffspring\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[38;5;28;43mlen\u001b[39;49m\u001b[43m(\u001b[49m\u001b[43mpopulation\u001b[49m\u001b[43m)\u001b[49m\u001b[43m)\u001b[49m\n",
      "Cell \u001b[1;32mIn[6], line 364\u001b[0m, in \u001b[0;36mLSAGA.replace_population.<locals>.select_population\u001b[1;34m(selection_type, population, pool_size)\u001b[0m\n\u001b[0;32m    352\u001b[0m \u001b[38;5;28;01mdef\u001b[39;00m \u001b[38;5;21mselect_population\u001b[39m(selection_type, population, pool_size):\n\u001b[0;32m    353\u001b[0m \u001b[38;5;250m    \u001b[39m\u001b[38;5;124;03m\"\"\"\u001b[39;00m\n\u001b[0;32m    354\u001b[0m \u001b[38;5;124;03m    Selects individuals for the next population.\u001b[39;00m\n\u001b[0;32m    355\u001b[0m \u001b[38;5;124;03m    \u001b[39;00m\n\u001b[1;32m   (...)\u001b[0m\n\u001b[0;32m    362\u001b[0m \u001b[38;5;124;03m        list: Selected individuals for the next population.\u001b[39;00m\n\u001b[0;32m    363\u001b[0m \u001b[38;5;124;03m    \"\"\"\u001b[39;00m\n\u001b[1;32m--> 364\u001b[0m     \u001b[38;5;28;01mreturn\u001b[39;00m \u001b[38;5;28;43mself\u001b[39;49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mselect_reproduction_pool\u001b[49m\u001b[43m(\u001b[49m\u001b[43mselection_type\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43mpopulation\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43mpool_size\u001b[49m\u001b[43m)\u001b[49m\n",
      "Cell \u001b[1;32mIn[6], line 321\u001b[0m, in \u001b[0;36mLSAGA.select_reproduction_pool\u001b[1;34m(self, selection_type, population, pool_size)\u001b[0m\n\u001b[0;32m    318\u001b[0m     chosen \u001b[38;5;241m=\u001b[39m random\u001b[38;5;241m.\u001b[39mchoices(population_sorted, weights\u001b[38;5;241m=\u001b[39mrank_weights, k\u001b[38;5;241m=\u001b[39mpool_size)\n\u001b[0;32m    320\u001b[0m \u001b[38;5;28;01melif\u001b[39;00m selection_type \u001b[38;5;241m==\u001b[39m \u001b[38;5;124m\"\u001b[39m\u001b[38;5;124melitist\u001b[39m\u001b[38;5;124m\"\u001b[39m:\n\u001b[1;32m--> 321\u001b[0m     population_sorted \u001b[38;5;241m=\u001b[39m \u001b[38;5;28msorted\u001b[39m(population, key\u001b[38;5;241m=\u001b[39m\u001b[38;5;28mself\u001b[39m\u001b[38;5;241m.\u001b[39mevaluate_makespan)\n\u001b[0;32m    322\u001b[0m     chosen \u001b[38;5;241m=\u001b[39m population_sorted[:pool_size]\n\u001b[0;32m    324\u001b[0m \u001b[38;5;28;01melif\u001b[39;00m selection_type \u001b[38;5;241m==\u001b[39m \u001b[38;5;124m\"\u001b[39m\u001b[38;5;124mtournament\u001b[39m\u001b[38;5;124m\"\u001b[39m:\n",
      "Cell \u001b[1;32mIn[6], line 87\u001b[0m, in \u001b[0;36mLSAGA.evaluate_makespan\u001b[1;34m(self, schedule)\u001b[0m\n\u001b[0;32m     84\u001b[0m \u001b[38;5;28;01mdef\u001b[39;00m \u001b[38;5;21mevaluate_makespan\u001b[39m(\u001b[38;5;28mself\u001b[39m, schedule):\n\u001b[0;32m     85\u001b[0m     \u001b[38;5;66;03m# Evaluates the makespan (completion time) of a given schedule.\u001b[39;00m\n\u001b[1;32m---> 87\u001b[0m     cumulative \u001b[38;5;241m=\u001b[39m \u001b[38;5;28;43mself\u001b[39;49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mcumulate_seq\u001b[49m\u001b[43m(\u001b[49m\u001b[43mschedule\u001b[49m\u001b[43m)\u001b[49m\n\u001b[0;32m     88\u001b[0m     \u001b[38;5;28;01mreturn\u001b[39;00m cumulative[\u001b[38;5;241m-\u001b[39m\u001b[38;5;241m1\u001b[39m]\n",
      "Cell \u001b[1;32mIn[6], line 81\u001b[0m, in \u001b[0;36mLSAGA.cumulate_seq\u001b[1;34m(self, seq)\u001b[0m\n\u001b[0;32m     79\u001b[0m cumulated \u001b[38;5;241m=\u001b[39m \u001b[38;5;28;01mNone\u001b[39;00m\n\u001b[0;32m     80\u001b[0m \u001b[38;5;28;01mfor\u001b[39;00m i \u001b[38;5;129;01min\u001b[39;00m seq:\n\u001b[1;32m---> 81\u001b[0m     cumulated \u001b[38;5;241m=\u001b[39m \u001b[38;5;28;43mself\u001b[39;49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mcumulate\u001b[49m\u001b[43m(\u001b[49m\u001b[38;5;28;43mself\u001b[39;49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mjobs_list\u001b[49m\u001b[43m[\u001b[49m\u001b[43mi\u001b[49m\u001b[43m]\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43mcumulated\u001b[49m\u001b[43m)\u001b[49m\n\u001b[0;32m     82\u001b[0m \u001b[38;5;28;01mreturn\u001b[39;00m cumulated\n",
      "Cell \u001b[1;32mIn[6], line 73\u001b[0m, in \u001b[0;36mLSAGA.cumulate\u001b[1;34m(self, job, previous_cumul)\u001b[0m\n\u001b[0;32m     71\u001b[0m     res[\u001b[38;5;241m0\u001b[39m] \u001b[38;5;241m=\u001b[39m previous_cumul[\u001b[38;5;241m0\u001b[39m] \u001b[38;5;241m+\u001b[39m job[\u001b[38;5;241m0\u001b[39m]\n\u001b[0;32m     72\u001b[0m     \u001b[38;5;28;01mfor\u001b[39;00m i \u001b[38;5;129;01min\u001b[39;00m \u001b[38;5;28mrange\u001b[39m(\u001b[38;5;241m1\u001b[39m, \u001b[38;5;28mlen\u001b[39m(job)):\n\u001b[1;32m---> 73\u001b[0m         res[i] \u001b[38;5;241m=\u001b[39m \u001b[38;5;28mmax\u001b[39m(res[i \u001b[38;5;241m-\u001b[39m \u001b[38;5;241m1\u001b[39m], previous_cumul[i]) \u001b[38;5;241m+\u001b[39m job[i]\n\u001b[0;32m     74\u001b[0m \u001b[38;5;28;01mreturn\u001b[39;00m res\n",
      "\u001b[1;31mKeyboardInterrupt\u001b[0m: "
     ]
    }
   ],
   "source": [
    "instances_200_10 = load_tai(200,10)\n",
    "makes_spans_200_10 = []\n",
    "for instance in instances_200_10:\n",
    "    saga = LSAGA(instance, variety_degree=5)\n",
    "    saga.optim(T_min=0.01)\n",
    "    makes_spans_200_10.append(saga.make_span_star)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"executing heursitics\")\n",
    "cds, palmer, neh = exec_heur(instances_200_10)\n",
    "print(\"tuning simulated annealing\")\n",
    "study_sa = exec_sa(instances_200_10)\n",
    "print(\"tuning genetic algorithm\")\n",
    "study_ga = exec_ga(instances_200_10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "200 jobs 20 machines"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "instances_200_20 = load_tai(200,20)\n",
    "makes_spans_200_20 = []\n",
    "for instance in instances_20_20:\n",
    "    saga = LSAGA(instance, variety_degree=3)\n",
    "    saga.optim(T_min=0.01)\n",
    "    makes_spans_200_20.append(saga.make_span_star)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"executing heursitics\")\n",
    "cds, palmer, neh = exec_heur(instances_200_20)\n",
    "print(\"tuning simulated annealing\")\n",
    "study_sa = exec_sa(instances_200_20)\n",
    "print(\"tuning genetic algorithm\")\n",
    "study_ga = exec_ga(instances_200_20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "500 jobs 20 machines"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "instances_500_20 = load_tai(500,20)\n",
    "makes_spans_500_20 = []\n",
    "for instance in instances_500_20:\n",
    "    saga = LSAGA(instance, variety_degree=3)\n",
    "    saga.optim(T_min=0.01)\n",
    "    makes_spans_500_20.append(saga.make_span_star)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"executing heursitics\")\n",
    "cds, palmer, neh = exec_heur(instances_500_20)\n",
    "print(\"tuning simulated annealing\")\n",
    "study_sa = exec_sa(instances_500_20)\n",
    "print(\"tuning genetic algorithm\")\n",
    "study_ga = exec_ga(instances_500_20)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "aivenv",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}