bigdata_heuri.h

#ifndef BDHEURI_H
#define BDHEURI_H

#include <iostream>
#include <string>
#include <fstream>
#include <math.h>
#include <cstdlib>
#include <iomanip>

using namespace std;

#include "data.h"

/* -------------- construtivo ------------- */

struct bd_registro
{
  int   vmo=-1;              // maquina origem onde esta sendo realizada a acao   
  int   tp=-1;               // tipo (0-exec 1-read 2-write 3-re_exec 4-re_read 5-re_write)
  int   tk=-1;               // tarefa em questao
  int   dt=-1;               // dado sendo escrito ou lido
  int   vm=-1;               // vm destino da escrita ou origem da leitura
  int   tm=-1;               // tempo da execucao ou leitura ou escrita
  int   ti=-1;               // tempo inicial da acao na maquina 
};

struct bd_movimento
{
  double c   =-1;                // custo do movimento   
  int    t   =-1;                // tarefa
  int    m   =-1;                // maquina
  int*   r;                      // lista de 0 e 1 indicando se a tarefa que gera o dado de entrada vai ser reexecutada 
  int*   w;                      // lista das maquinas das escritas
};

struct bd_site
{
  int      mks=-1;              // makespam da maquina
  double   cst=-1;              // custo da maquina
  double   slw=-1;              // slowdown
};


/* ---------------- bl ----------------------*/

struct bd_elem
{
  int    ty   =-1;                // tipo (0- tarefa 1-dado)
  int    id   =-1;                // id da tarefa ou id do dado
  int    cp   =-1;                // copia numero cp (pois posso ter mais de uma mesma tarefa e dado)
  int    vm   =-1;                // VM onde a tarefa foi executada ou o dado foi escrito
  int*   es;                      // lista de elementos (dados) de escrita
  int    tes  =-1;                // tamanho da lista de elementos (dados) de escrita
  int*   le;                      // lista de elementos (dados) de leitura
  int    tle  =-1;                // tamanho da lista de elementos (dados) de leitura
  int*   les;                     // lista de dados de leitura que não estão nos elementos por serem estaticos
  int*   vms;                     // maquina onde foi lido o dado estatico
  int    tles =-1;                // tamanho da lista de dados de leitura que não estão nos elementos por serem estaticos
  int*   pred;                    // lista de elementos (tarefas) predecessores da tarefa elemento
  int    tpred=-1;                // tamanho da lista de elementos (tarefas) predecessores da tarefa elemento
  int*   suc;                     // lista de elementos (tarefas) sucessoras da tarefa elemento
  int    tsuc=-1;                 // tamanho da lista de elementos (tarefas) sucessoras da tarefa elemento
  
  int    elet =-1;                // elemento (tarefa) que escreveu o dado (se o elemento for dado)
  int    tfim =-1;                // tempo final da tarefa (exec+lei+esc) (se o elemento for tarefa)
  int    ord  =-1;                // indice da ordem que o elemento (tarefa) ocupa
};

struct bd_ord
{
  int    id    =-1;                // id da tarefa 
  int    cp    =-1;                // copia numero cp (pois posso ter mais de uma mesma tarefa)
  int    ele   =-1;                // indice do elemento desta tarefa
  int    TL_t  =-1;                // indice t da ultima escrita da tarefa na time line (TL[t][m]) (valores de uso temporario, só para passar da estrutura do construtivo para a estrutura da busca local)
  int    TL_m  =-1;                // indice m da ultima escrita da tarefa na time line (TL[t][m]) (valores de uso temporario, só para passar da estrutura do construtivo para a estrutura da busca local)
};


using namespace std;

   class BDHeuri{
      public:
     BDHeuri(Data*, int);
         ~BDHeuri();

	 bool construtivo(Data* data);                                                                           // metodo construtivo
	 double bl(Data* data, int* makespam, double* custof, double* ms_part, double* cs_part, int Maxtime);    // busca local
	 void heuristica(Data* data, int MaxIt, int Maxtime, int mDEPU, char * instance);                        // metodo heuristico

	 // estruturas para representar a solucao no construtivo
	 
	 int                FLAG=-1000;  // flag que indica qual metodo vai ser executado (-1: Guloso Puro 0: Guloso com Rexec 1:Multi-Start 2: Grasp)
	 int                MAX_LV_BK;   // nivel maximo do backtracking para realizar as reexecuções (tarefa reexec tarefa que reexec tarefa que ...)
	 int                bk_lv_max=-1;// nivel maximo do backtracking alcançado pela instancia 
	 struct bd_registro ** TL;       // linha do tempo da solucao corrente
	 struct bd_movimento * LC;       // lista de candidatos do construtico
	 int *              MS_M;        // tempo final corrente de cada maquina
	 int *              QTD_M;       // quantidade de operacoes de cada maquina (indice para a TL)
	 int **             FILE_MD;     // matriz de maquinas por dados que ela possui (se nao possui o dado eh -1)
	 int *              FILE_IN;     // vetor indexado por tarefas tendo a qdt de tarefas a serem lidas
	 int                MS;          // Makespam
	 double             CST;         // Custo financeiro
	 double             MS_PART;     // parcela referente ao Makespam na f.o.
	 double             CST_PART;    // parcela referente ao Custo financeiro na f.o.
	 double             FO;          // Custo da funcao objetivo
	 int *              TASK;        // quantas vezes a tarefa foi executada
	 int *              TASK_T_MIN;  // periodo em que todas as entradas estao disponiveis
	 int **             TASK_MAQ;    // indica se a tarefa ja foi executada na maquina (1) ou não (0)
	 int                NTASK;       // quantas tarefas diferentes ja foram executadas
	 int **             B_READ;      // maquina mais barata para ler um dado (mais proximo)
	 int **             B_WRITE;     // maquina mais barata para escrever um dado (mais proximo)
	 double*            CAP_M;       // espaco em disco usado da maquina	 
	 int *              DADO_T;      // periodo em que o dado apareceu no processamento em alguma maquina
	 clock_t            start_h;     // tempo inicial de processamento
	 
	 bool               DEPU;        // DEPURACAO
	 int                tcol = 13;   // tamanho das colunas na impressao da depuracao

	 // ---------------- estruturas para representar a solucao na busca local (bl) -------------------
	 struct bd_elem *    ELE;                // lista de elementos do workflow (tarefas e dados)
	 int                 max_elem_bl;        // tamanho maximo do numero de elementos na bl
	 int                 num_ELE;            // numero de elementos em ELE
	 struct bd_ord *     ORDER_T;            // lista (ordenada) de tarefas a serem consideradas
	 int                 max_order_bl;       // tamanho máximo do numero de tarefas na ordem (n*m)
	 int                 num_ORDER_T;        // numero de tarefas em ORDER_T
	 int *               altura_i_order;     // altura inicial da tarefa em ORDER_T
	 int *               altura_order;       // altura da tarefa em ORDER_T	 
	 // ----------------------------------------------------------------------------------------------
	 
	 // estruturas auxiliares temporarios na busca

	 int *              D_WRITE;             // qual maquina o dado vai ser escrito
	 int                SITE_WRITE;          // indice do site que esta sendo considerado para escrita
	 int *              D_REEXC;             // quais dados serao gerados por re-execucoes
	 int *              D_TASK;              // tarefas que serao re-executadas
	 int                MaxTam_D;            // maximo tamanho de D_REEXC e D_WRITE para nao explodir a enumeracao
	 int *              MS_M_t1;             // MS_M temporario
	 int *              MS_M_t2;             // MS_M temporario
	 double*            CAP_M_t1;            // CAP_M temporario
	 double*            CAP_M_t2;            // CAP_M temporario
	 int*               TASK_RXC;            // vetor de que marca se a tarefa ja foi reexecutada
	 int*               FILE_RXC;            // vetor de arquivos que foram gerados durante uma reexecucao
	 struct bd_site *   SITE_MIN_MAQ;        // lista de maquinas (uma por site) que contem a maquina com menor (mks,custo,slow) que ja foi considerada para realizar a alocação de uma tarefa durante o construtivo. Note que qualquer maquina neste site que tiver (mks,custo,slow) maior, levaria a uma solução pior e não precisa ser considerada
	 struct bd_site *   SITE_MIN_MAQ2;       // lista de maquinas (uma por site) que contem a maquina com menor (mks,custo,slow) que ja foi considerada para realizar a alocação de uma tarefa durante o construtivo. Note que qualquer maquina neste site que tiver (mks,custo,slow) maior, levaria a uma solução pior e não precisa ser considerada
	 
      private:

	 double     fobj(Data* data, int* makespam, double* custof, double* ms_part, double* cs_part); // calcula funcao objetivo
	 bool       atualiza_dados_gerados(Data* data, int* vet, int task, int i_pai_t, int maq);  // atualiza vetor de dados de entrada que vao ser gerados
	 int        shift_read(Data* data, int tam_D, int ti);                                     // Dada um configuracao 01 de D_REEXC (que determina que dados de entrada seram lidos e quais gerados) determinar qual o novo periodo minimo que a tarefa pode comecar as acoes
	 bool       ini_intvet_r(int* vet1, int* vet2, int tamV);                                  // inicializa vetor de inteiros para enumerar as leituras/reexecucao
	 bool       ini_intvet_w(int* vet, int tamV, Data* data);                                  // inicializa vetor de inteiros para enumerar as escritas
	 bool       inc_intvet_r(int* vet1, int* vet2, int i, int tamV1, int tamV2, int task, int maq, Data* data);        // funcao de iteracao de vetor inteiro (leitura)
	 bool       inc_intvet_w(int* vet, int i, int tamV, int maxval);                           // funcao de iteracao de vetor inteiro (escrita)
	 bool       inc_intvet_redux_r(int* vet1, int* vet2, int i, int tamV1, int tamV2, int task, int maq, Data* data);  // funcao de iteracao de vetor inteiro de leitura (enumeracao reduzida)
	 bool       inc_intvet_redux_w(int* vet, int tamV, int maxval, Data* data);                // funcao de iteracao de vetor inteiro de escrita (enumeracao reduzida)
	 bool       pos_inv_intvet_w(int* vet, int i, int tamV, int maxval);                       // achou posicao inviavel no vetor de enumeracao, incrementa aquela posicao e zera as da frente (escrita)
	 bool       pos_inv_intvet_redux_w(int* vet, int i, int tamV, int maxval);                 // trata posicao inviavel na enumeracao reduzida (escrita)
	 void       inicializa_estruturas(Data* data);                                             // inicializa estruturas da heuristica
	 void       atualiza_estruturas_escrita(Data* data, int n_d, int n_m, int d_time);         // atualiza B_READ dado que um novo dado d foi escrito na maquina m e que periodo ele estara disponivel
	 bool       imprime_estruturas(Data* data);                                                // imprime estruturas
	 bool       imprime_sol(Data* data);                                                       // imprime solucao
     bool       salva_best(Data* data, char * instance, double alfaMKS, double alfaCST);           // salva melhor solucao em arquivo
	 bool       imprime_best();                                                                // imprime melhor solucao que esta no arquivo
	 void       inicializa_LC(Data* data);                                                     // inicializa lista de candidatos
	 void       atualiza_LC(Data* data, int i, int m, double fo);                              // atualiza lista de candidatos
	 static int compLC(const void* pp, const void* qq);                                        // funcao de comparacao da lista de candidatos para o qsort
	 bool       exec_read_reexc(Data* data, int Task, int Maq, bool mov);                      // atualiza vetor de tempos para re-executar uma tarefa a partir do D_REEXC
	 bool       reexc(Data* data, int task, int maq, int Maq_stg,int level, bool mov);     // procedimento recurssivo para re-executar task em maq
	 bool       write(Data* data, int Task, int Maq, bool mov);                                // atualiza vetor de tempos para escrever dados de uma tarefa executada numa maquina (a partir do D_WRITE)

	 // acesso as estruturas
	 int        get_FILE_MD(int m, int d);
	 void       put_FILE_MD(int m, int d, int val);
	 int        get_B_READ(int m, int d);
	 void       put_B_READ(int m, int d, int val);
	 int        get_B_WRITE(int m, int d);
	 void       put_B_WRITE(int m, int d, int val);
	 
	 int _n;                  // quantidade de tarefas
	 int _m;                  // quantidade de maquinas
	 int _d;                  // quantidade de dados totais
	 int _t;                  // quantidade de periodos
	 int _t_max;              // quantidade de periodos maximo que uma solucao qualquer pode ter
	 int _a_max;              // quantidade maxima de acoes (exec, leit. esc.) uma maquina pode ter

	 // parametros do algoritmo
	 
	 int    TMAX_LC;               // tamanho maximo da lista de candidatos
	 int    max_sizeLC;            // tamanho maximo ALOCADO da lista de candidatos
	 double c_minLC;               // menor custo de uma solucao em LC
	 double c_maxLC;               // maior custo de uma solucao em LC
	 double alphaLC;               // alpha da LC
	 int    tamLC;                 // qtd de candidatos da LC
	 int    piorLC;                // indice o pior elemento da LC
	 int    melhorLC;              // indice do melhor elemento da LC
	 int    tipo_enum_lei;         // tipo de enumeracao da leitura 0-total (todas as combinacoes de leitura/re-exec) 1-reduzida (apenas um dado pode ser gerado por vez). Ambos os tipos sao limitados por MaxTam_D
	 int    tipo_enum_esc;         // tipo de enumeracao da escrita 0-total (todas as combinacoes de escritas nas maq.) 1-reduzida (todas as saidas vao para uma soh ma.). Ambos os tipos sao limitados por MaxTam_D
	 int    MaxTam_lei;            // ate esse tamanho de D_TASK, as combinacoes das tarefas a serem re-executadas sao enumeradas totalmente (tipo_enum_lei= 0), acima disso, de forma (reduzida tipo_enum_lei = 1)


	 /* ------------------------- Busca Local ------------------------ */
	 bool   TL_struct_bl(Data* data);                                                                                                           // carrega estruturas da busca local a partir da estruturas do construtivo
	 bool   imprime_struct_bl(Data* data);                                                                                                      // imprime estrutura de representacao da solucao da busca local
	 double fobj_bl(Data* data, int* makespam, double* custof, double* ms_part, double* cs_part, int flag);                                     // calcula funcao objetivo da busca local
	 bool   move_t_m_bl(Data* data,  double f_obj, int* makespam, double* custof, double* ms_part, double* cs_part, int Depu);                  // vizinhanca que tenta mudar a maquina de uma tarefa
	 bool   zero_cost_move(Data* data, double f_obj, int* makespam, double* custof, double* ms_part, double* cs_part, int Depu);                // realiza uma sequencia de movimentos de custo 0, para ter diversidade na solução
	 bool   move_2t_m_bl(Data* data, double f_obj, int* makespam, double* custof, double* ms_part, double* cs_part, int Depu);                  // vizinhanca que tenta mudar a maquina de duas tarefas que estão na mesma maquina 
	 bool   move_d_m_bl(Data* data,  double f_obj, int* makespam, double* custof, double* ms_part, double* cs_part, int Depu);                  // vizinhanca que tenta mudar a maquina de um dado 
	 bool   move_exec_esc_site_bl(Data* data, double f_obj, int* makespam, double* custof, double* ms_part, double* cs_part, int Depu);         //  vizinhanca que tenta mudar o site de uma execução/escrita 
	 bool   switch_m_bl(Data* data, double f_obj, int* makespam, double* custof, double* ms_part, double* cs_part, int Depu);                   // vizinhanca que tenta trocar a maquina de 2 elementos (dado ou tarefa)

	 void   calcula_altura_i_tarefas_ordem(Data* data, int ord);                                                                                // calcula a altura inicial das tarefas na ordem de tarefas
	 void   calcula_altura_f_tarefas_ordem(Data* data, int ord);                                                                                 // calcula a altura final das tarefas na ordem de tarefas
	 void   calcula_altura_ordem(Data* data, int Depu);                                                                                         // calcula a altura das tarefas na ordem de tarefas
	 bool   switch_t_bl(Data* data, double f_obj, int* makespam, double* custof, double* ms_part, double* cs_part, int Depu);                   // vizinhanca que tenta trocar a ordem das tarefas que podem ser executadas em paralelo */
	 double corrige_inconsistencia_com_struct_bl(Data* data, char * instance, int* makespam, double* custof, double* ms_part, double* cs_part); // corrige pequenas inconsistencias geradas na solucao do construtivo

   };
   
#endif