bigdata_heuri.cpp

#include "bigdata_heuri.h"

#define INFINITY_COST 99999999

//Inicializador
BDHeuri::BDHeuri(Data* data, int flag)
{
  // flag que indica qual metodo vai ser executado (-1: Guloso Puro 0: Guloso com Rexec 1:Multi-Start 2: Grasp)
  FLAG=flag;
  
  // dimensoes
  _n     = data->n;
  _m     = data->m;
  _d     = data->d;
  _t     = data->t;
  _t_max = _t;

  // numero de acoes maximas em uma mesma maquina
  if (5*(_n + _d) < _t)
    _a_max = 5*(_n + _d);
  else
    _a_max = _t;
    
  // tamanho do vetor da LC
  max_sizeLC = 1000;
    
  // aloca
  TL  = new struct bd_registro * [_a_max];
  for ( int i = 0; i < _a_max; i++ ) {
    TL[i] = new struct bd_registro [_m];
  }

  LC  = new struct bd_movimento [max_sizeLC];
  for ( int i = 0; i < max_sizeLC; i++ ) {
    LC[i].r   = new int [data->max_in];
    LC[i].w   = new int [data->max_out];
  }

  SITE_MIN_MAQ  = new struct bd_site [data->num_site];
  SITE_MIN_MAQ2 = new struct bd_site [data->num_site];
 
  MS_M       = new int [_m];
  MS_M_t1    = new int [_m];
  MS_M_t2    = new int [_m];
  QTD_M      = new int [_m];
  D_WRITE    = new int [data->max_out];
  D_REEXC    = new int [data->max_in];
  D_TASK     = new int [data->max_in];

  FILE_MD  = new int * [_m];
  for ( int i = 0; i < _m; i++ ) {
    FILE_MD[i] = new int [_d];
  }

  TASK_MAQ = new int * [_n];
  for ( int i = 0; i < _n; i++ ) {
    TASK_MAQ[i] = new int [_m];
  }

  FILE_IN = new int [_n];

  TASK       = new int [_n];
  TASK_T_MIN = new int [_n];
  TASK_RXC   = new int [_n];
    
  B_READ  = new int * [_m];
  for ( int i = 0; i < _m; i++ ) {
    B_READ[i] = new int [_d];
  }

  B_WRITE  = new int * [_m];
  for ( int i = 0; i < _m; i++ ) {
    B_WRITE[i] = new int [_d];
  }

  CAP_M     = new double [_m];
  CAP_M_t1  = new double [_m];
  CAP_M_t2  = new double [_m];
  
  DADO_T   = new int [_d];
  FILE_RXC = new int [_d];

  /* ------- bl ----------- */
  max_elem_bl  = ((_n + _d)*_m);
  max_order_bl = (_n * _m);
  
  ELE      = new struct bd_elem [max_elem_bl];
  for (int i = 0; i < max_elem_bl; i++)
    {
      ELE[i].es   = new int [data->max_out];
      ELE[i].le   = new int [data->max_in];
      ELE[i].les  = new int [data->max_in];
      ELE[i].vms  = new int [data->max_in];
      ELE[i].pred = new int [max_order_bl];
      ELE[i].suc  = new int [max_order_bl]; 
    }
  
  ORDER_T        = new struct bd_ord  [max_order_bl];
  altura_i_order = new int [max_order_bl];
  altura_order   = new int [max_order_bl];
  /* ----------------------- */
}

BDHeuri::~BDHeuri()
{
  //desaloca
  for ( int i = 0; i < _a_max; i++ )
    delete [] TL[i];

  delete [] TL;

  for ( int i = 0; i < max_sizeLC; i++ )
    {
      delete [] LC[i].w;
      delete [] LC[i].r;
    }
  delete [] LC;

  delete [] SITE_MIN_MAQ;
  delete [] SITE_MIN_MAQ2;
  
  delete [] MS_M;
  delete [] MS_M_t1;
  delete [] MS_M_t2;
  delete [] QTD_M;
  delete [] D_WRITE;
  delete [] D_REEXC;
  delete [] D_TASK;

  for ( int i = 0; i < _m; i++ )
    delete [] FILE_MD[i];
  delete [] FILE_MD;

  for ( int i = 0; i < _n; i++ )
    delete [] TASK_MAQ[i];
  delete [] TASK_MAQ;

  delete [] FILE_IN;

  delete [] TASK;
  delete [] TASK_T_MIN;
  delete [] TASK_RXC;

  for ( int i = 0; i < _m; i++ )
    delete [] B_READ[i];
  delete [] B_READ;

  for ( int i = 0; i < _m; i++ )
    delete [] B_WRITE[i];
  delete [] B_WRITE;

  delete [] CAP_M;
  delete [] CAP_M_t1;
  delete [] CAP_M_t2;

  delete [] DADO_T;
  delete [] FILE_RXC;

  /* ------- bl ----------- */
  delete [] ELE;
  for (int i = 0; i < max_elem_bl; i++)
    {
      delete [] ELE[i].es;
      delete [] ELE[i].le;
      delete [] ELE[i].les;
      delete [] ELE[i].vms;
      delete [] ELE[i].pred;
      delete [] ELE[i].suc;
    }
  
  delete [] ORDER_T;
  delete [] altura_i_order;
  delete [] altura_order;
  /* ----------------------- */
}



//FILE_MD
int BDHeuri::get_FILE_MD(int m, int d)
{
  return FILE_MD[m][d];
}
void BDHeuri::put_FILE_MD(int m, int d, int val)
{
  FILE_MD[m][d] = val;
}

//B_READ
int BDHeuri::get_B_READ(int m, int d)
{
  return B_READ[m][d];
}
void BDHeuri::put_B_READ(int m, int d, int val)
{
  B_READ[m][d] = val;
}

//B_WRITE
int BDHeuri::get_B_WRITE(int m, int d)
{
  return B_WRITE[m][d];
}
void BDHeuri::put_B_WRITE(int m, int d, int val)
{
  B_WRITE[m][d] = val;
}


// funcao objetivo
double BDHeuri::fobj(Data* data, int* makespam, double* custof, double* ms_part, double* cs_part)
{
  int      mksp=-1;
  double   cost=0;
  double   obj=0;

  for ( int m = 0; m < _m; m++ )
    {
      if (MS_M[m] > mksp)
      	mksp = MS_M[m];

      cost += MS_M[m] * data->m_cost[m];
    }
  * makespam = mksp;
  * custof   = cost;
  * ms_part  = ((data->alfa_t * mksp)/ data->max_time_wkf /*data->t*/);
  * cs_part  = ((data->alfa_b * cost) / data->max_cost_wkf /*data->c_max*/);
  obj        =  (* ms_part) + (* cs_part);

  return obj;
}


// atualiza vetor de dados de entrada que vao ser gerados
// vet --> D_REEXC
// Soh gera o dado se ele nao tiver na  maquina de armazenamento do site
bool BDHeuri::atualiza_dados_gerados(Data* data, int* vet, int task, int i_pai_t, int maq)
{
  int  t_dad, dw_dad;
  bool vaigerar=false;
  int  Maq_site, Maq_stg;
    
  // Site da Maquina que esta sendo executada a tarefa E Maquina de armazenamento do site da maquina que esta executando a tarefa
  Maq_site = data->m_site[maq];
  Maq_stg  = data->vm_st_site[Maq_site];
  
  t_dad = data->t_in[task][i_pai_t];
  
  for(int dw_dad, d=0; d < data->d_out_tam[t_dad]; d++)
    {
      dw_dad   = data->d_out[t_dad][d];
      
      if (get_FILE_MD(Maq_stg,dw_dad) == -1)
	{
	  for(int d2=0; d2 < data->d_in_tam[task]; d2++)
	    if (data->d_in[task][d2] == dw_dad)
	      {
		vet[d2]  = 1;
		vaigerar = true;
		break;
	      }
	}
      
    }

  return vaigerar;
}

// 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
int BDHeuri::shift_read(Data* data, int tam_D, int ti)
{
  int min_time=0;
  int Depu=0;

  if (Depu) cout<<"                 ---- shift_read---- de t"<<ti<<endl;
  // percorre os dados de entrada a serem lidos (nao re-executados)
  for(int dl, d=0; d < data->d_in_tam[ti]; d++)
    {
      // dados lidos
      if (D_REEXC[d]==0)
	{
  	  dl       = data->d_in[ti][d];         // dado a ser lido
	  if (DADO_T[dl] > min_time)
	    {
	      min_time = DADO_T[dl];
	    }
	  if (Depu) cout<<"                    dado d"<<dl<<" aparece em tempo "<<DADO_T[dl]<<endl;
	  if (DADO_T[dl] == -1) { cout<<"**ERRO ERRO ERRO** leu dado "<<dl<<" que nao existia"<<endl; abort();}
	}
    }
  return min_time;
}


// inicializa vetor de inteiros para enumerar as leituras/reexecucao
bool BDHeuri::ini_intvet_r(int* vet1, int* vet2, int tamV)
{
  for(int i=0; i < tamV; i++)
    {
      vet1[i]=0;
      vet2[i]=0;
    }

  return true;
}


// inicializa vetor de inteiros para enumerar as escritas
// encontra a primeira maquina do site inicial para tentar escrever
// vet  -> D_WRITE
bool BDHeuri::ini_intvet_w(int* vet, int tamV, Data* data)
{
  SITE_WRITE = 0;

  for ( int j = 0; j < tamV; j++ )
    vet[j]=data->vm_st_site[SITE_WRITE];

  return true;
}

// incrementa vetor de inteiros (sequencia de valores) para enumerar a leitura/reexecucao
// retorna FALSE se acabou de iterar (tamanho eh tamV ou MaxTam_D)
// Ex: 0 0 0 0 -> 0 0 0 1 -> 0 0 1 0 -> 0 0 1 1 -> 0 1 0 0 -> 0 1 0 1 -> ...
// vet1 ---> D_TASK
// vet2 ---> D_REEXC
bool BDHeuri::inc_intvet_r(int* vet1, int* vet2, int i, int tamV1, int tamV2, int task, int maq, Data* data)
{
  bool resp=false;
  bool vaigerar;
  
  if ((i < tamV1) and (i < MaxTam_D))
    {
      resp=inc_intvet_r(vet1, vet2, i+1, tamV1, tamV2, task, maq, data);
      if (not resp)
	{
	  if (vet1[i] == 1)
	    {
	      vet1[i]=0;
	    }
	  else
	    {
	      vet1[i]++;

	      // -------------------------- Atualiza D_REEXC -------------------------
	      for(int d=0; d < tamV2; d++)
		vet2[d]=0;

	      for(int t=0; t < tamV1; t++)
		if (vet1[t] == 1)
		  {
		    vaigerar = atualiza_dados_gerados(data, vet2, task, t, maq);

		    // a task a ser re-executada nao precisa, pois a propria maquina ja tem todos os arquivos que esta tarefa gera
		    if (vaigerar == false)
		      {
			//cout<<"nao precisa D_TASK = "; for(int d=0; d < data->t_in_tam[task]; d++) if (D_TASK[d]==1) { cout<<data->t_in[task][d]<<", "; } cout<<". pois task "<<data->t_in[task][t]<<" eh desnecessaria "<<endl;
			//cout<<"nao precisa D_TASK = "; for(int d=0; d < data->t_in_tam[task]; d++) { cout<<D_TASK[d]<<", "; } cout<<". pois task na pos "<<t<<" eh desnecessaria "<<endl;

			// zera o vetor de tarefas da posicao atual ate o final, inutilizando esta configuracao
			for (int j=t; (j<tamV1) and (j<MaxTam_D); j++)
			  vet1[j]=0;

			return false;
		      }
		  }
	      // ----------------------------------------------------------------------

	      return true;
	    }// else
	      
	}//if (not resp)
      
    }//if ((i < tamV1) and (i < MaxTam_D))
    
  return resp;
}


// incrementa vetor de inteiros (sequencia de valores) para enumerar a leitura/reexecucao
// Ex 4 maq: 0 0 0 0 -> 0 0 0 1 -> 0 0 0 2 -> 0 0 0 3 -> 0 0 1 0 -> 0 0 1 1 -> 0 0 1 2 -> ... 
// retorna FALSE se acabou de iterar (tamanho eh tamV ou MaxTam_D)
bool BDHeuri::inc_intvet_w(int* vet, int i, int tamV, int maxval)
{
  bool resp=false;
  
  if ((i < tamV) and (i < MaxTam_D))
    {
      resp=inc_intvet_w(vet, i+1, tamV, maxval);
      if (not resp)
	{
	  if (vet[i] == maxval)
	    vet[i]=0;
	  else
	    {
	      vet[i]++;
	      return true;
	    }
	}
    }
  return resp;
}



// incrementa vetor de inteiros (sequencia de valores), mas nao enumera todas as combinacoes,
// agora apenas faz cada posicao isoladamente ser alterada
// Ex: 0 0 0 0 0 -> 1 0 0 0 0 -> 0 1 0 0 0 -> 0 0 1 0 0 -> ... -> 0 0 0 0 1 -> 1 1 1 1 1 
// retorna FALSE se acabou de iterar (tamanho eh tamV ou MaxTam_D)
bool BDHeuri::inc_intvet_redux_r(int* vet1, int* vet2, int i, int tamV1, int tamV2, int task, int maq, Data* data)
{
  int t_dad;

  // condicao de parada 1: nao tem tarefas para serem re-executadas
  if (tamV1 == 0)
    return false;

  // condicao de parada 2: ultimo elemento -> 1 1 1 1 1
  if (tamV1 == 1)
    {
      if (vet1[0]==1)
	return false;
    }
  else
    if (tamV1 >= 2)
      if (vet1[0]==1 and vet1[1]==1)
	return false;

  //proximo a ser incrementado
  while ((i < tamV1) and (i < MaxTam_D))
    {
      if (vet1[i] != 0)
	{
	  vet1[i] = 0;
	  if ((i+1 < tamV1) and (i+1 < MaxTam_D))
	    {
	      vet1[i+1] = 1;

	      // -------------------------- Atualiza D_REEXC -------------------------
	      for(int d=0; d < tamV2; d++)
		vet2[d]=0;

	      atualiza_dados_gerados(data, vet2, task, i+1, maq);
	      // ----------------------------------------------------------------------
	      
	      return true;
	    }
	  // ultimo elemento alcancou 1
	  else
	    {
	      // ultima possibilidade, re-executa todo mundo
	      // 0 0 0 0 1 -> 1 1 1 1 1 
	      for (int j=0; (j<tamV1) and (j<MaxTam_D); j++)
		vet1[j]=1;

	      // -------------------------- Atualiza D_REEXC -------------------------
	      for(int d=0; d < tamV2; d++)
		vet2[d]=0;
	      
	      for(int t=0; t < tamV1; t++)
		atualiza_dados_gerados(data, vet2, task, t, maq);
	      // ----------------------------------------------------------------------
	      
	      return true;
	    }
	}
      
      i++;
      
    }// while ((i < tamV1) and (i < MaxTam_D))
  
  // vetor nulo inicial, vai para o segundo elemento
  vet1[0]++;

  // -------------------------- Atualiza D_REEXC -------------------------
  for(int d=0; d < tamV2; d++)
    vet2[d]=0;

  atualiza_dados_gerados(data, vet2, task, 0, maq);
  // ----------------------------------------------------------------------
  
  return true;
}


// incrementa vetor de inteiros (sequencia de valores), mas nao enumera todas as combinacoes,
// joga todas as saidas numa maquina soh por vez
// Ex: 0 0 0 0 -> 1 1 1 1 -> 2 2 2 2 -> ...
// retorna FALSE se acabou de iterar (tamanho eh tamV ou MaxTam_D)
// vet  -> D_WRITE
bool BDHeuri::inc_intvet_redux_w(int* vet, int tamV, int maxval, Data* data)
{
  SITE_WRITE++;
  
  if (SITE_WRITE < data->num_site)
    {
      for ( int j = 0; j < tamV; j++ )
	vet[j]=data->vm_st_site[SITE_WRITE];

      return true;
    }
  else
    return false;
	
}



// achou posicao inviavel no vetor de enumeracao
// incrementa aquela posicao e zera as da frente (-1 pois ainda vai ser incrementado)
bool BDHeuri::pos_inv_intvet_w(int* vet, int i, int tamV, int maxval)
{
  // pois na proxima iteracao se os posteriores tiverem no valor maximo, o elemento da posicao i vai ser iterado
  for (int j=i+1; (j<tamV) and (j<MaxTam_D); j++)
    vet[j]=maxval;

  return true;
}


// na iteracao reduzida nao faz nada em caso de inviabilidade na posicao
bool BDHeuri::pos_inv_intvet_redux_w(int* vet, int i, int tamV, int maxval)
{
  return true;
}



// inicializa estruturas da heuristica
void BDHeuri::inicializa_estruturas(Data* data)
{
  for ( int m = 0; m < _m; m++ )
    {
      MS_M[m]  = 0;
      CAP_M[m] = 0;
      QTD_M[m] = 0;
    }
  
  for ( int m = 0; m < _m; m++ )
    for ( int d = 0; d < _d; d++ )
      put_FILE_MD(m,d,-1);

  for ( int maq, ind, d = 0; d < _d; d++ )
    {
      for (int ind=0; ind < data->d_st_or_tam[d]; ind++)
	{
	  maq             = data->d_st_or[d][ind];
	  put_FILE_MD(maq,d,0);
	  CAP_M[maq]     +=  data->d_size[d];
	}
    }
  MS=0;
  
  for ( int i = 0; i < _n; i++ )
    TASK_T_MIN[i] = -1;
  
  for ( int d = 0; d < _d; d++ )
    DADO_T[d] = -1;
  
  for(int d=0; d < _d; d++)
    if (data->d_st_or_tam[d] > 0)
      {
	//dado estatico
	for ( int i = 0; i < _n; i++ )
	  for(int d2=0; d2 < data->d_in_tam[i]; d2++)
	    if (data->d_in[i][d2] == d)
	      TASK_T_MIN[i] = 0;
	
	DADO_T[d]=0;
      }
  
  // para toda tarefa obrigatoria (na heuristica todas sao obrigatorias)
  for ( int i = 0; i < _n; i++ )
    {
      FILE_IN[i]    = data->d_in_dd_tam[i];
      TASK[i]       = 0;
    }
  NTASK=0;
  
  for ( int m = 0; m < _m; m++ )
    for ( int d = 0; d < _d; d++ )
      {
	put_B_READ(m,d,-1);
	put_B_WRITE(m,d,-1);
      }
  
  int b_t_djp;
  for ( int m = 0; m < _m; m++ )
    for(int ind,d=0; d < _d; d++)
      {
	b_t_djp = INFINITY_COST;
	for (int ind=0; ind < data->d_st_or_tam[d]; ind++)
	  {
	    if (data->t_djp(d,m,data->d_st_or[d][ind]) < b_t_djp)
	      {
		b_t_djp      = data->t_djp(d,m,data->d_st_or[d][ind]);
		put_B_READ(m,d,data->d_st_or[d][ind]);  
	      }
	  }
      }
  
  for ( int m = 0; m < _m; m++ )
    for(int ind,d=0; d < _d; d++)
      {
	b_t_djp = INFINITY_COST;
	for ( int m2 = 0; m2 < _m; m2++ )
	  {
	    if (get_FILE_MD(m2,d) == -1)
	      {
		if (data->t_djp(d,m,m2) < b_t_djp)
		  {
		    b_t_djp       = data->t_djp(d,m,m2);
		    put_B_WRITE(m,d,m2);  
		  }
	      }
	  }
      }
   
  
  FO = MS = CST = -1;
  
  for ( int t = 0; t < _a_max; t++ )
    for ( int m = 0; m < _m; m++ )
      TL[t][m].vmo = TL[t][m].tp = TL[t][m].tk = TL[t][m].dt = TL[t][m].vm = TL[t][m].tm = TL[t][m].ti = -1 ;

  
  for ( int i = 0; i < _n; i++ )
    for ( int m = 0; m < _m; m++ )
      TASK_MAQ[i][m] = 0;
}



// atualiza estruturas dado que um novo dado d foi escrito na maquina m e dispoivel no periodo t
void BDHeuri::atualiza_estruturas_escrita(Data* data, int n_d, int n_m, int d_time)
{
  bool so_uma=true;
  
  for ( int m = 0; m < _m; m++ )
    {
      // o dado nao existia
      if (get_B_READ(m,n_d) == -1)
	{
	  // ----------- atualiza B_READ
	  put_B_READ(m,n_d,n_m);
	
	  if (so_uma)
	    {
	      // ----------- atualiza TASK_T_MIN
	      for ( int i = 0; i < _n; i++ )
		for(int d=0; d < data->d_in_tam[i]; d++)
		  if ((data->d_in[i][d] == n_d) and (TASK_T_MIN[i] < d_time))
		    {
		      TASK_T_MIN[i] = d_time;
		      break;
		    }
	      
	      // ----------- atualiza FILE_IN
	      for (int i = 0; i < _n; i++ )
		{
		  // checa se o dado eh de entrada da tarefa
		  for(int d=0; d < data->d_in_tam[i]; d++)
		    {
		      if (data->d_in[i][d] == n_d)
			{
			  FILE_IN[i]--;
			  break;
			}
		    }
		}

	      //---------- atualiza DADO_T
	      DADO_T[n_d] = d_time;
	      
	      so_uma = false;
	    }
	  // ---------------------------
	  
	}// if (get_B_READ(m,n_d) == -1)
      else
	// ----------- atualiza B_READ
	if (data->t_djp(n_d,m,n_m) < data->t_djp(n_d,m,get_B_READ(m,n_d)))
	  put_B_READ(m,n_d,n_m);

      // tem que escolher agora outra maquina para ser o melhor destino para gravar
      if (get_B_WRITE(m,n_d) == n_m)
	{
	  double b_t_djp = INFINITY_COST;
	  for ( int m2 = 0; m2 < _m; m2++ )
	    {
	      if (get_FILE_MD(m2,n_d) == -1)
		{
		  if (data->t_djp(n_d,m,m2) < b_t_djp)
		    {
		      b_t_djp         = data->t_djp(n_d,m,m2);

		      // ----------- atualiza B_WRITE
		      put_B_WRITE(m,n_d,m2);  
		    }
		}
	    }
	}// if (get_B_WRITE(m,n_d) == n_m)
      
    }// for ( int m = 0; m < _m; m++ )
}

// inicializa a lista de candidatos
void BDHeuri::inicializa_LC(Data* data)
{
  for ( int i = 0; i < TMAX_LC; i++ )
    {
      LC[i].c  = INFINITY_COST;
      LC[i].t  = -1;
      LC[i].m  = -1;

      for ( int m = 0; m < data->max_in; m++ )
	LC[i].r[m] =-1;

      for ( int m = 0; m < data->max_out; m++ )
	LC[i].w[m]   =-1;
    }

  c_minLC  = INFINITY_COST;
  c_maxLC  = -1;
  tamLC    = 0;
  piorLC   = -1;
  melhorLC = -1;
}



// atualiza lista de candidatos
void BDHeuri::atualiza_LC(Data* data, int i, int m, double fo)
{
  bool aDEPU = false;
  
  // primeiro elemento
  if (tamLC == 0)
    {
      c_minLC  = fo;
      c_maxLC  = fo;
      piorLC   = 0;
      melhorLC = 0;
 
      LC[0].c   = fo;
      LC[0].t   = i;
      LC[0].m   = m;
      for(int d2=0; d2 < data->d_in_tam[i]; d2++)
	LC[0].r[d2] = D_TASK[d2];
      for(int d2=0; d2 < data->d_out_tam[i]; d2++)
	LC[0].w[d2] = D_WRITE[d2];
      tamLC++;
    }
  else
    {  
      // lista nao esta cheia
      if (tamLC < TMAX_LC)
	{
	  if (fo < c_minLC)
	    {
	      c_minLC  = fo;
	      melhorLC = tamLC;
	    }
	  if (fo > c_maxLC)
	    {
	      c_maxLC = fo;
	      piorLC  = tamLC;
	    }
	  
	  LC[tamLC].c   = fo;
	  LC[tamLC].t   = i;
	  LC[tamLC].m   = m;
	  for(int d2=0; d2 < data->d_in_tam[i]; d2++)
	    LC[tamLC].r[d2] = D_TASK[d2];
	  for(int d2=0; d2 < data->d_out_tam[i]; d2++)
	    LC[tamLC].w[d2] = D_WRITE[d2];
	  tamLC++;
	}
      // lista cheia, checa o pior elemento da lista
      else
	{
	  // melhor que o pior elemento, troca
	  if (fo < c_maxLC)
	    {
	      if (fo < c_minLC)
		{
		  c_minLC  = fo;
		  melhorLC = piorLC;
		}
	      
	      LC[piorLC].c   = fo;
	      LC[piorLC].t   = i;
	      LC[piorLC].m   = m;
	      for(int d2=0; d2 < data->d_in_tam[i]; d2++)
		LC[piorLC].r[d2] = D_TASK[d2];
	      for(int d2=0; d2 < data->d_out_tam[i]; d2++)
		LC[piorLC].w[d2] = D_WRITE[d2];

	      //encontra novo pior movimento
	      c_maxLC = -1;
	      for ( int i2 = 0; i2 < TMAX_LC; i2++ )
		if (LC[i2].c >  c_maxLC)
		  {
		    c_maxLC = LC[i2].c;
		    piorLC  = i2;
		  }
	    }
	}
    }

  if (aDEPU) { cout<<"------- LC ("<<tamLC<<") -------- ["<<c_minLC<<" , "<<c_maxLC<<"] best = "<<melhorLC<<" worst = "<<piorLC<<endl; for ( int i = 0; i < TMAX_LC; i++ ) cout<<i<<") "<<LC[i].c<<", "; cout<<"--------------------------------"<<endl; }
}


// funcao de comparacao de elementos da lista de candidatos para o qsort
int BDHeuri::compLC(const void* pp, const void* qq)
{
    bd_movimento vpp,vqq;
    
    vpp=*(bd_movimento*) pp;
    vqq=*(bd_movimento*) qq;

    if (vpp.c < vqq.c)
      return -1;
    else
      if (vpp.c > vqq.c)
	return 1;
      else
	return 0;
}



// atualiza vetor de tempos para re-executar uma tarefa a partir do D_REEXC
// Task     - tarefa que disparou o processo com o objetivo de ter o dado de entrada gerado
// Maq      - maquina em que as duplicacoes devem ocorrer
// mov      - indica se eh movimento (true) ou se eh checagem de vizinho apenas (false)
// Vai alterando MS_M[Maq] e CAP_M[Maq]

bool BDHeuri::exec_read_reexc(Data* data, int Task, int Maq, bool mov)
{
  int   dl, tdl, cdl, br, min_lx;
  bool  viavel;
  int   Maq_stg, Maq_site;

  // Site da Maquina que esta sendo executada a tarefa E Maquina de armazenamento do site da maquina que esta executando a tarefa
  Maq_site = data->m_site[Maq];
  Maq_stg  = data->vm_st_site[Maq_site];
      
  // inicializacao
  for(int i=0; i < _n; i++)
    TASK_RXC[i] = 0;
  for(int d=0; d < _d; d++)
    FILE_RXC[d] = 0;
  
  min_lx = shift_read(data, data->d_in_tam[Task], Task);
  if (DEPU) cout<<"   shift de leitura = +"<<min_lx<<endl;
			
  if (MS_M[Maq] < min_lx)
    MS_M[Maq] = min_lx;

  // ------ faz primeiro as re-execucoes para gerar os dados ----------
  for(int d=0; d < data->d_in_tam[Task]; d++)
    if ((D_REEXC[d]==1) && (FLAG != 0))
      {
	dl       = data->d_in[Task][d];         // dado a ser lido
	tdl      = data->d_out_t[dl];           // tarefa a ser duplicada local na maquina Maq

	/* Se tdl ja tiver sido executado em Maq retorne inviavel (false) */
	if (TASK_MAQ[tdl][Maq] == 1)
	  {
	    //cout<<endl<<"---- tarefa a ser re-exec "<<tdl<<" na maq"<<Maq<<" ja foi executada na maquina"<<endl;
	    return false;
	  }
	
	if (TASK_RXC[tdl] == 0)
	  {
	    // Erros
	    if (tdl == -1)                      { cout<<"ERRO (R) dado "<<dl<<" nao tem tarefa que o gere ERRO"<<endl; exit(0);}
	    if (get_FILE_MD(Maq_stg, dl) != -1) { cout<<"ERRO (R) dado a ser gerado "<<dl<<" ja existe na maquina ERRO"<<endl; exit(0);}
	    if ((TASK[tdl]==0) and (data->t_ob[tdl] == 1))
	      { cout<<"ERRO (R) Task="<<Task<<", tentando re-executar tarefa "<<tdl<<" que eh obrigatoria e ainda nao foi executada ERRO (talvez existam duas tarefas gerando o mesmo arquivo de saida o que eh inconsistente do arquivo de entrada)"<<endl; exit(0);}
	    
	    //re-exec tarefa  na maquina maq
	    viavel = reexc(data, tdl, Maq, Maq_stg, 0, mov);
	    if (!viavel)
	      return false;
	  }
	
      }//if (D_REEXC[d]==1) && (FLAG != 0)


  // ------ faz agora a leitura dos dados gerados das reexecucoes
  for(int d=0; d < data->d_in_tam[Task]; d++)
    if ((D_REEXC[d]==1) && (FLAG != 0))
      {
	dl         = data->d_in[Task][d];         // dado a ser lido
	tdl        = data->d_out_t[dl];           // tarefa a ser duplicada local
	cdl        = data->t_djp (dl,Maq,Maq_stg);
	if (mov)
	  {
	    TL[QTD_M[Maq]][Maq].vmo = Maq;
	    TL[QTD_M[Maq]][Maq].tp  = 1;
	    TL[QTD_M[Maq]][Maq].tk  = Task;
	    TL[QTD_M[Maq]][Maq].dt  = dl;
	    TL[QTD_M[Maq]][Maq].vm  = Maq_stg;
	    TL[QTD_M[Maq]][Maq].tm  = cdl;
	    TL[QTD_M[Maq]][Maq].ti  = MS_M[Maq];
	    QTD_M[Maq]++;
	    if (QTD_M[Maq] >= _a_max) {cout<<"ERRO tamanho de TL passou _a_max = "<<_a_max<<endl; exit(0);}
	  }
	MS_M[Maq] += cdl;
	if (DEPU) cout<<"      r"<<Task<<"("<<dl<<")<"<<Maq_stg<<"\t="<<cdl<<endl;
      }//if (D_REEXC[d]==1) && (FLAG != 0)

  // teste de limite de periodos
  if (MS_M[Maq] >= _t_max)
    {
      if (DEPU) cout<<"            cfg. inv. passou  tempo maximo t_max, MS_M[Maq] = "<<MS_M[Maq]<<endl;
      return false;
    }
  
  // ------ faz depois as leituras dos dados que nao foram gerados por reexecucoes ----------
  for(int d=0; d < data->d_in_tam[Task]; d++)
    if (D_REEXC[d]==0)
      {
	dl       = data->d_in[Task][d];         // dado a ser lido
	
	// checa se foi gerado localmente por alguma re-execucao, entao ele esta local
	if (FILE_RXC[dl] == 1)
	  br   = Maq_stg;
	// senao pega a melhor maquina para ler o dado
	else
	  br   = get_B_READ(Maq, dl);     
	cdl = data->t_djp (dl,Maq, br);
	if (mov)
	  {
	    TL[QTD_M[Maq]][Maq].vmo = Maq;
	    TL[QTD_M[Maq]][Maq].tp  = 1;
	    TL[QTD_M[Maq]][Maq].tk  = Task;
	    TL[QTD_M[Maq]][Maq].dt  = dl;
	    TL[QTD_M[Maq]][Maq].vm  = br;
	    TL[QTD_M[Maq]][Maq].tm  = cdl;
	    TL[QTD_M[Maq]][Maq].ti  = MS_M[Maq];
	    QTD_M[Maq]++;
	    if (QTD_M[Maq] >= _a_max) {cout<<"ERRO tamanho de TL passou _a_max.  "<<_a_max<<endl; exit(0);}
	  }
	MS_M[Maq] += cdl;
	if (DEPU) cout<<"      r"<<Task<<"("<<dl<<")<"<<br<<"\t="<<cdl<<endl;
	if (br == -1) {cout<<"ERRO (R) arquivo de entrada "<<dl<<" nao existe ERRO"<<endl; exit(0);}
	
      }// if (D_REEXC[d]==0)
    
  // considera execucao
  if (mov)
    {
      TL[QTD_M[Maq]][Maq].vmo = Maq;
      TL[QTD_M[Maq]][Maq].tp  = 0;
      TL[QTD_M[Maq]][Maq].tk  = Task;
      TL[QTD_M[Maq]][Maq].tm  = data->t_ij(Task,Maq);
      TL[QTD_M[Maq]][Maq].ti  = MS_M[Maq];
      QTD_M[Maq]++;
      if (QTD_M[Maq] >= _a_max) {cout<<"ERRO tamanho de TL passou _a_max.  "<<_a_max<<endl; exit(0);}
    }
  MS_M[Maq] += data->t_ij(Task,Maq);
  if (DEPU) cout<<"      x"<<Task<<"\t="<<data->t_ij(Task,Maq)<<endl;

  // teste de limite de periodos
  if (MS_M[Maq] >= _t_max)
    {
      if (DEPU) cout<<"            cfg. inv. passou  tempo maximo t_max, MS_M[Maq] = "<<MS_M[Maq]<<endl;
      return false;
    }
  else
    return true;
}

// procedimento recurssivo para re-executar task em maq
// Vai alterando MS_M[maq] e CAP_M[maq]
bool BDHeuri::reexc(Data* data, int task, int maq, int Maq_stg, int level, bool mov)
{
  int   dl2, br2, tdl2, cd2;
  bool  viavel;

  viavel = true;

  if (level > MAX_LV_BK-1)
    {
      if (DEPU) cout<<"            cfg. inv., passou nivel maximo de backtracking de reexecucao = "<<MAX_LV_BK<<endl;
      return false;
    }
  if (level > bk_lv_max)
    bk_lv_max = level;
    
  if (TASK_RXC[task] == 0)
    {
      // ****************** leitura da entrada da tarefa duplicada **********************
      for(int d2=0; d2 < data->d_in_tam[task]; d2++)
	{
	  dl2   = data->d_in[task][d2];     // dado a ser lido pela tarefa duplicada
	  
	  // ------ melhor maquina para ler o dado ------
	  // checa se foi gerado localmente por alguma re-execucao, entao ele esta local
	  if (FILE_RXC[dl2] == 1)
	    br2   = Maq_stg;
	  else
	    {
	      // AQUI ESTAMOS LIMITANDO DIZENDO QUE O DADO A SER LIDO PELA TAREFA A SER REEXECUTADA DEVE LER O DADO JA EXISTENTE, MESMO SE FOR NUMA MAQUINA DISTANTE, SÓ FAÇO A REEXECUCAO RECURSIVA DO PAI DA TAREFA A SER REEXEC. SE O DADO NÃO FOR GERADO. NÃO ESTOU CONSIDERANDO DA HIPOTESE DA REEXECUÇÃO RECURSIVA SER MELHOR QUANDO O DADO JA EXISTE NO WORKFLOW.
	      
	      // senao, pega a melhor maquina para ler ele
	      br2   = get_B_READ(maq,dl2);    
	      
	      // se nao tem o dado de entrada da tarefa a ser re-executada entao temos que reexecutar quem gera ela
	      if (br2 == -1)
		{
		  tdl2   = data->d_out_t[dl2];       // tarefa que gera este dado
		  viavel = reexc(data, tdl2, maq, Maq_stg, level+1, mov);

		  // evitar backtracking maior que o limite maximo
		  if (viavel == false)
		    return false;
		  
		  // o dado foi gerado, atualiza estruturas
		  FILE_RXC[dl2] = 1;
		  br2           = Maq_stg;
		}
	      // dado de entrada existe, atualiza o shift de tempo 
	      // ########################################### Alteracao para shift de tempo dos dados de entrada das tarefas reexecutadas ##################################
	      else
		{
		  if (MS_M[maq] < DADO_T[dl2])
		    {
		      //cout<<"MS_M foi de "<<MS_M[maq]<<" para "<<DADO_T[dl2]<<endl;
		      MS_M[maq] = DADO_T[dl2];
		    }
		  if (DADO_T[dl2] == -1) { cout<<"**ERRO ERRO ERRO** leu dado na reexec "<<dl2<<" que nao existia"<<endl; abort();}
		}
	      // ##########################################################################################################################################################
	    }// else
	  
	  cd2        = data->t_djp (dl2,maq,br2);    // custo de leitura do dado a partir da melhor maquina
	  if (mov)
	    {
	      TL[QTD_M[maq]][maq].vmo = maq;
	      TL[QTD_M[maq]][maq].tp  = 4;
	      TL[QTD_M[maq]][maq].tk  = task;
	      TL[QTD_M[maq]][maq].dt  = dl2;
	      TL[QTD_M[maq]][maq].vm  = br2;
	      TL[QTD_M[maq]][maq].tm  = cd2;
	      TL[QTD_M[maq]][maq].ti  = MS_M[maq];
	      QTD_M[maq]++;
	      if (QTD_M[maq] >= _a_max) {cout<<"ERRO tamanho de TL passou _a_max.  "<<_a_max << endl; exit(0);}
	    }
	  
	  MS_M[maq] += cd2;
	  if (DEPU) cout<<string(level, ' ')<<"                    *r"<<task<<"("<<dl2<<")<"<<br2<<"\t="<<cd2<<endl;
	  
	}// for(int d2=0; d2 < data->d_in_tam[task]; d2++)
      
      
      // *************** execucao da tarefa duplicada *************************
      cd2        = data->t_ij(task,maq);
      if (mov)
	{
	  TL[QTD_M[maq]][maq].vmo = maq;
	  TL[QTD_M[maq]][maq].tp  = 3;
	  TL[QTD_M[maq]][maq].tk  = task;
	  TL[QTD_M[maq]][maq].tm  = cd2;
	  TL[QTD_M[maq]][maq].ti  = MS_M[maq];
	  QTD_M[maq]++;
	  if (QTD_M[maq] >= _a_max) {cout<<"ERRO tamanho de TL passou _a_max.  "<<_a_max<<endl; exit(0);}
      	}
      MS_M[maq] += cd2;
      if (DEPU) cout<<string(level, ' ')<<"                    *x("<<task<<")"<<" = "<<data->t_ij(task,maq)<<endl;
      
      // *************** escrita da tarefa duplicada *************************
      for(int d2=0; d2 < data->d_out_tam[task]; d2++)
	{
	  dl2           = data->d_out[task][d2];     // dado a ser escrito pela tarefa duplicada
	  cd2           = data->t_djp (dl2,maq,Maq_stg);
	  if (mov)
	    {
	      put_FILE_MD(Maq_stg, dl2, (MS_M[maq] + cd2));
	      atualiza_estruturas_escrita(data, dl2, Maq_stg, (MS_M[maq] + cd2));
	      
	      TL[QTD_M[maq]][maq].vmo = maq;
	      TL[QTD_M[maq]][maq].tp  = 5;
	      TL[QTD_M[maq]][maq].tk  = task;
	      TL[QTD_M[maq]][maq].dt  = dl2;
	      TL[QTD_M[maq]][maq].vm  = Maq_stg;
	      TL[QTD_M[maq]][maq].tm  = cd2;
	      TL[QTD_M[maq]][maq].ti  = MS_M[maq];
	      QTD_M[maq]++;
	      if (QTD_M[maq] >= _a_max) {cout<<"ERRO tamanho de TL passou _a_max.  "<<_a_max<<endl; exit(0);}
	    }
	  CAP_M[Maq_stg]   += data->d_size[dl2];
	  MS_M[maq]        += cd2;
	  FILE_RXC[dl2] = 1;
	  if (DEPU) cout<<string(level, ' ')<<"                    *w"<<task<<"("<<dl2<<")>"<<Maq_stg<<"\t="<<cd2<<endl;
	  
	  // inviavel gravar os arquivos na maquina
	  if (CAP_M[Maq_stg] > data->m_cap[Maq_stg])
	    {
	      viavel = false;
	      if (DEPU) cout<<string(level, ' ')<<"                       --- nao cabe (conf. inv.)"<<endl;
	      break;
	    }
	}
      
      // marca como reexecutado
      if (viavel)
	TASK_RXC[task] = 1;
      
    }// if (TASK_RXC[task] == 0)

  // teste de limite de periodos
  if (MS_M[maq] >= _t_max)
    {
      if (DEPU) cout<<"            cfg. inv. passou  tempo maximo t_max, MS_M[Maq] = "<<MS_M[maq]<<endl;
      return false;
    }
    
  return viavel;
}




// atualiza vetor de tempos para escrever dados de uma tarefa executada numa maquina (a partir do D_WRITE)
// Task     - tarefa que disparou o processo com o objetivo de ter o dado de saida gravado
// Maq      - maquina em que a tarefa eh executada
// mov      - indica se eh movimento (true) ou se eh checagem de vizinho apenas (false)
// Vai alterando MS_M[Maq] e CAP_M[Maq]
bool BDHeuri::write(Data* data, int Task, int Maq, bool mov)
{
  int p;
  
  for(int dw, d2=0; d2 < data->d_out_tam[Task]; d2++)
    {
      dw   = data->d_out[Task][d2];    // dado a ser escrito pela tarefa

      // maquina de escrita do dado (se maq=-1), entao escreve na maquina mais perto que nao tenha o arquivo)
      if (D_WRITE[d2] != -1)
	p = D_WRITE[d2];
      else
	p = get_B_WRITE(Maq,dw);

       // se o arquivo nao existe na maquina e nao passa a capacidade
      if ((get_FILE_MD(p,dw)==-1) and (CAP_M[p] + data->d_size[dw] <= data->m_cap[p]))
	{
	  if (mov)
	    {
	      put_FILE_MD(p, dw, (MS_M[Maq] + data->t_djp (dw,Maq,p)));
	      atualiza_estruturas_escrita(data, dw, p, (MS_M[Maq] + data->t_djp (dw,Maq,p)));

	      TL[QTD_M[Maq]][Maq].vmo = Maq;
	      TL[QTD_M[Maq]][Maq].tp  = 2;
	      TL[QTD_M[Maq]][Maq].tk  = Task;
	      TL[QTD_M[Maq]][Maq].dt  = dw;
	      TL[QTD_M[Maq]][Maq].vm  = p;
	      TL[QTD_M[Maq]][Maq].tm  = data->t_djp (dw,Maq,p);
	      TL[QTD_M[Maq]][Maq].ti  = MS_M[Maq];
	      QTD_M[Maq]++;
	      if (QTD_M[Maq] >= _a_max) {cout<<"ERRO tamanho de TL passou _a_max.  "<<_a_max<<endl; exit(0);}
	    }
	  MS_M[Maq]  += data->t_djp (dw,Maq,p);
	  CAP_M[p]   += data->d_size[dw];
	  if (DEPU) cout<<"      w"<<Task<<"("<<dw<<")>"<<p<<"\t="<<data->t_djp (dw,Maq,p)<<endl;
	}
      else
	{
	  if (DEPU) if ((get_FILE_MD(p,dw)!=-1))                         cout<<"            cfg. inv. em W o arq "<<dw<<"ja existe em "<<p<<endl;
	  if (DEPU) if ((CAP_M[p] + data->d_size[dw] >= data->m_cap[p])) cout<<"            cfg. inv. em W o arq "<<dw<<" nao coube na maquina "<<p<<" de capacidade "<<data->m_cap[p]<<", total de "<<CAP_M[p]+data->d_size[dw]<<endl;

	  // vai para a proxima combinacao viavel
	  if (tipo_enum_esc == 0)
	    pos_inv_intvet_w(D_WRITE, d2, data->d_out_tam[Task], _m-1);
	  else
	    pos_inv_intvet_redux_w(D_WRITE, d2, data->d_out_tam[Task], _m-1);
	  
	  return false;
	}// else
    }//for(int dw, p, d2=0; d2 < data->d_out_tam[Task]; d2++)
				    
  // checa se a solucao passou do limite maximo de 2 x t_max
  if (MS_M[Maq] >= _t_max)
    {
      if (DEPU) cout<<"            cfg. inv. passou o tempo maximo t_max, MS_M[Maq] = "<<MS_M[Maq]<<endl;
      return false;
    }

  return true;
}







// metodo construtivo
bool BDHeuri::construtivo(Data* data)
{
  int         mks;                      // makespam
  double      mks_part;                 // parcela do makespam na f.o.
  double      cst, cst_part;            // custo financeiro
  double      fo,fo_maxRLC;             // funcao objetivo
  bool        fim_r, fim_w;             // termino do laco enumerativo de veto
  bool        viavel_w, viavel_r;       // se uma atribuicao eh viavel
  int         b_ind, b_t, b_m;          // variaveis do melhor movimento
  int         MS_M_x, MS_M_rx, MS_M_w;  // valores temporarios de makespam
  double      CAP_M_rx;                 // valores temporarios de capacidade
  int         min_lx;                   // tempo minimo para comecar acao de uma tarefa segundo as leituras e re-execucoes
  int         tam_RLC;                  // tamanho da lista de candidados restrita
  int         sorteio;                  // candidato a movimento sortiado
  int         qtd_mv;                   // qtd de possiveis movimentos (alocaçoes) para cada tarefa obrigatoria
    
  if (DEPU) cout<<"----------------------------------- construtivo ----------------------------- "<<endl;

  // -------- inicializacao de estruturas
  inicializa_estruturas(data);
  //if (DEPU) imprime_estruturas(data);

  // ---------------------------------- inicializa busca ---------------------------
  while (NTASK < data->nob)
    {
      // inicializa lista de candidatos
      inicializa_LC(data);
      
      // para cada tarefa ainda nao executada e obrigatoria
      for ( int i = 0; i < data->n; i++ )
	if ((TASK[i]==0) and (data->t_ob[i] == 1))
	  {
	    //if (DEPU) cout<<"--TASK--)"<<i<<endl;	    
	    // todos as suas leituras estao disponiveis
	    if (FILE_IN[i]==0)
	      {
		if (DEPU) cout<<"TASK)"<<i<<endl;
		qtd_mv = 0;

		// inicializa estruturas que marcam qual 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
		for (int s = 0; s < data->num_site; s++)
		  {
		    SITE_MIN_MAQ[s].mks = INFINITY_COST;
		    SITE_MIN_MAQ[s].cst = INFINITY_COST;
		    SITE_MIN_MAQ[s].slw = INFINITY_COST;
		  }
		
		// para todas as maquinas que pode executar a tarefa
		for (int msite, m = 0; m < _m; m++ )
		  if (data->m_storage[m] == 1)
		  {

		    // +++++++++++++++++++++++++++++++++++++++ VERIFICA APENAS AS MELHORES MAQUINAS POR SITE +++++++++++++++++++++++
		    //if (DEPU) {cout<<"--------------------- SITE_MIN_MAQ = "; for (int s = 0; s < data->num_site; s++) {  cout<<"("<<SITE_MIN_MAQ[s].mks<<", "<<SITE_MIN_MAQ[s].cst<<", "<<SITE_MIN_MAQ[s].slw<<"), ";  }cout<<endl; }
		    // testa se a maquina tem algo melhor (mks,custo,slow) do que a melhor maquina do site que ja foi avaliada previamente. Se não tiver, pula essa maquina
		    msite = data->m_site[m];
		    if ((MS_M[m] >= SITE_MIN_MAQ[msite].mks) and (data->m_cost[m] >= SITE_MIN_MAQ[msite].cst) and (data->m_slow[m] >= SITE_MIN_MAQ[msite].slw))
		      continue;
		    else
		      {
			// se tem algo melhor vai verificar essa alocação tarefa/maquina, mas soh atualiza os melhores valores do site se os 3 valores (mks,custo,slow) forem melhores.
			if ((MS_M[m] <= SITE_MIN_MAQ[msite].mks) and (data->m_cost[m] <= SITE_MIN_MAQ[msite].cst) and (data->m_slow[m] <= SITE_MIN_MAQ[msite].slw))
			  {
			    SITE_MIN_MAQ[msite].mks = MS_M[m]; SITE_MIN_MAQ[msite].cst = data->m_cost[m]; SITE_MIN_MAQ[msite].slw = data->m_slow[m];
			  }
		      }
		    // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
		    
		    // === GUARDA 1  ===
		    MS_M_x  = MS_M[m];
		    for (int m2 = 0; m2 < _m; m2++ ) CAP_M_t1[m2] = CAP_M[m2];
		    // ================
      
		    // inicializa vetor das maquinas de leitura
		    ini_intvet_r(D_REEXC, D_TASK, data->max_in);
		    if (DEPU) cout<<"t)"<<i<<" m)"<<m<<" = "<<data->t_ij(i,m)<<" site)"<<data->m_site[m]<<endl;

		    // estabelece o tipo de enumeracao das re-execucoes (total ou reduzida)
		    if (data->t_in_tam[i] <= MaxTam_lei)
		      {
			tipo_enum_lei = 0;
			if (DEPU) cout<<"enumeracao de D_TASK TOTAL"<<endl;
		      }
		    else
		      {
			tipo_enum_lei = 1;
			if (DEPU) cout<<"enumeracao de D_TASK REDUZIDA"<<endl;
		      }
		    		      
		    fim_r=true;
		    while (fim_r)
		      {
			
			//if (DEPU) cout<<"------------------------------------ D_TASK = "; for(int d=0; d < data->t_in_tam[i]; d++) if (D_TASK[d]==1) { cout<<data->t_in[i][d]<<", "; } cout<<endl;
			//if (DEPU) cout<<"------------------------------------ D_TASK = "; for(int d=0; d < data->t_in_tam[i]; d++) { cout<<D_TASK[d]<<", "; } cout<<endl;
			//if (DEPU) cout<<"------------------------------------ D_REEXC = "; for(int d=0; d < data->d_in_tam[i]; d++) if (D_REEXC[d]==1) { cout<<data->d_in[i][d]<<", "; } cout<<endl;
 
			// ----- contabiliza as leituras/re-execucoes e reexecucao pela combinacao dada por D_REEXC -----
                        viavel_r = exec_read_reexc(data, i, m, false);
			// ---------------------------------------------------------------------------------
			
			// --------------------------- considera escrita ----------------------------
			if (viavel_r != false)
			  {
			    // === GUARDA 2 ===
			    MS_M_w = MS_M[m];
			    for (int m2 = 0; m2 < _m; m2++ ) CAP_M_t2[m2] = CAP_M[m2];
			    // ===============
			    			    
			    // inicializa vetor das maquinas de escrita
			    ini_intvet_w(D_WRITE, data->max_out, data);
			    
			    fim_w=true;
			    while (fim_w)
			      {
				//cout<<"@ SITE="<<SITE_WRITE<<" D_WRITE = "; for(int d2=0; d2 < data->d_out_tam[i]; d2++) { cout<<D_WRITE[d2]<<", "; } cout<<endl;

				// ----- contabiliza as escritas pela combinacao dada por D_WRITE -----
				viavel_w = write(data, i, m, false);
				// ---------------------------------------------------------------------------------
								
				if (viavel_w != false)
				  {
				    // checa movimento
				    fo = fobj(data, &mks, &cst, &mks_part, &cst_part);
				    if (DEPU) cout<<"               ++++++++ movimento => "<<"t)"<<i<<" m)"<<m<<" MKS = "<<mks<<" cst = "<<cst<<" fo = "<<fo<<"("<<mks_part<<" + "<<cst_part<<")"<<endl;
				    
				    // +++++++++++ guarda movimento na lista de candidatos ++++++++++
				    atualiza_LC(data, i, m, fo);
				    qtd_mv ++;
				    // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
				    
				  }// if (viavel_w != false) (se a atribuicao de escritas eh valida)
				
				// === RECUPERA 2 ===
				MS_M[m]  = MS_M_w;
				for (int m2 = 0; m2 < _m; m2++ ) CAP_M[m2] = CAP_M_t2[m2];
				// ==================
				
				// atualiza maquinas de escrita para proxima combinacao
				if (tipo_enum_esc == 0)
				  fim_w=inc_intvet_w(D_WRITE, 0, data->d_out_tam[i], _m-1);
				else
				  fim_w=inc_intvet_redux_w(D_WRITE, data->d_out_tam[i], _m-1, data);
								
			      }// while (fim_w)
			    
			  }// if (viavel_r != false) (se a atribuicao de leituras/reexecucoes eh valida)
			
			// === RECUPERA 1 ===
			MS_M[m]  = MS_M_x;
			for (int m2 = 0; m2 < _m; m2++ ) CAP_M[m2] = CAP_M_t1[m2];
			// ==================
			
			// atualiza leitura para proxima combinacao
			if (tipo_enum_lei == 0)
			  fim_r=inc_intvet_r(D_TASK, D_REEXC, 0, data->t_in_tam[i], data->d_in_tam[i], i, m, data);
			else
			  fim_r=inc_intvet_redux_r(D_TASK, D_REEXC, 0, data->t_in_tam[i], data->d_in_tam[i], i, m, data);

			//-------- Guloso Sem reexecucao ----------
			if (FLAG==0)
			  fim_r=false;
			
		      }//while (fim_r)

		  }// if (data->m_storage[m] == 1)
		
	      }//if (FILE_IN[i]==0)

	  }//if (TASK[i]==0)

      // se nenhum movimento valido foi encontrado então retorna que a construcao falhou em encontrar uma solucao valida pois
      // ultrapassou o limite maximo de tempo 2 x t_max
      if (tamLC==0)
	{
	  if (DEPU) cout<<"nenhum movimento valido foi encontrado"<<endl;
	  return false;
	}
     
      //************************************** REALIZA MOVIMENTO ***************************************

      if (DEPU) cout<<endl<<"== Realiza Movimento =="<<endl;

      //cout<<"NTASKS="<<NTASK<<" qtd_mv="<<qtd_mv<<endl;
      
      // ordena LC
      qsort(LC, tamLC, sizeof(bd_movimento), compLC);
      
      if (DEPU) { cout<<"%%%%%%%%%% LC ("<<tamLC<<") %%%%%%%%% ["<<c_minLC<<" , "<<c_maxLC<<"]"<<endl; for ( int i = 0; i < TMAX_LC; i++ ) cout<<i<<") "<<LC[i].c<<", "; cout<<endl; }

      // escolhe movimento
      if (alphaLC != 0)
	{
	  //  escolhe o movimento aleatoriamente nos melhores movimentos com fo ateh c_minLC + c_alpha*(c_maxLC - c_minLC)
	  fo_maxRLC = c_minLC + alphaLC*(c_maxLC - c_minLC);
	  tam_RLC   = 0;
	  for ( int i = 0; i < TMAX_LC; i++ )
	    if (LC[i].c <= fo_maxRLC)
	      tam_RLC++;
	  sorteio = (int)(rand() % tam_RLC);
	  if (DEPU) cout<<endl<<"fo_max_RLC = "<<fo_maxRLC<<" tam_RLC = "<<tam_RLC<<" SORTEIO = "<<sorteio<<endl;
	}
      else
	{
	  // alpha=0, faz guloso, pega o melhor
	  sorteio=0;
	  if (DEPU) cout<<" GULOSO -> SORTEIO = "<<sorteio<<endl;
	}
             
      // indice do melhor movimento na lista de candidatos
      b_ind = sorteio;
      b_t   = LC[b_ind].t;
      b_m   = LC[b_ind].m;
      if (DEPU) cout<<"==============BEST MOVE=========== executar "<<b_t<<" em "<<b_m<<endl;
      
      // conta o numero de tarefas diferentes obrigatorias executadas
      if ((TASK[b_t]==0) and (data->t_ob[b_t] == 1))
	NTASK++;
      TASK[b_t]++;

      // ---- recupera D_TASK, D_REEXC e D_WRITE para fazer a leitura/re-execucao, execucao e escrita do movimento ----
      for(int d=0; d < data->d_in_tam[b_t]; d++) D_REEXC[d]=0;
      for(int d=0; d < data->t_in_tam[b_t]; d++)
	{
	  D_TASK[d] = LC[b_ind].r[d];
	  if (D_TASK[d] == 1)
	    atualiza_dados_gerados(data, D_REEXC, b_t, d, b_m);
	}
      for(int d=0; d < data->d_out_tam[b_t]; d++)
	D_WRITE[d] = LC[b_ind].w[d];

      // ------------------------------------------------------------------------------
      if (DEPU) {cout<<"------------------------------------- Tarefas a serem re-executadas (D_TASK) diretamente = "; for(int d=0; d < data->t_in_tam[b_t]; d++) if (D_TASK[d]==1) { cout<<data->t_in[b_t][d]<<", "; } cout<<endl;}			
      if (DEPU) {cout<<"------------------------------------- Dados gerados por reexecucao (D_REEXC) diretamente = "; for(int d=0; d < data->d_in_tam[b_t]; d++) if (D_REEXC[d]==1) { cout<<data->d_in[b_t][d]<<", "; } cout<<endl;}
      if (DEPU) {cout<<"------------------------------------- Maquinas em que dados foram escritos (D_WRITE)  = "; for(int d=0; d < data->d_out_tam[b_t]; d++) { cout<<D_WRITE[d]<<", "; } cout<<endl;}
       
      // ---------- realiza leitura/re-execucao e execucao do movimento
      exec_read_reexc(data, b_t, b_m, true);
	       
      // ------------------------------------ escrita
      write(data, b_t, b_m, true);

      // atualiza TASK_MAQ
      TASK_MAQ[b_t][b_m]=1;
      for(int d=0; d < data->t_in_tam[b_t]; d++)
	if (D_TASK[d]==1)
	  TASK_MAQ[data->t_in[b_t][d]][b_m] = 1;
      
      // funcao objetivo
      FO = fobj(data, &MS, &CST, &MS_PART, &CST_PART);

      //imprime solucao parcial 
      if (DEPU)
      	{
      	  imprime_estruturas(data);
      	  imprime_sol(data);
      	}
            
    }//while (number_task < data->n)

 // uma solucao valida foi encontrada
 return true;
}


// imprime estruturas
bool BDHeuri::imprime_estruturas(Data* data)
{

  cout<<"Matriz de Tarefa executada por Maquina (TASK_MAQ)"<<endl;
  for ( int i = 0; i < _n; i++ )
    {
      for ( int m = 0; m < _m; m++ )
	cout<<TASK_MAQ[i][m]<<", ";
      cout<<endl;
    }
  cout<<endl;

  cout<<"periodo em que o dado apareceu no workflow DADO_T =";
  for ( int i = 0; i < _d; i++ )
    cout<<i<<") "<<DADO_T[i]<<", ";
  cout<<endl;
  
  cout<<"quantas vezes exec cada tarefa TASK =";
  for ( int i = 0; i < _n; i++ )
    cout<<i<<") "<<TASK[i]<<", ";
  cout<<endl;

  cout<<"tempo de inicio minimo de cada tarefa (depende dos dados de entrada) = ";
  for ( int i = 0; i < _n; i++ )
    cout<<i<<") "<<TASK_T_MIN[i]<<", ";
  cout<<endl;
  
  cout<<"Tarefas liberadas pelo FILE_IN =";
  for ( int i = 0; i < _n; i++ )
    if (FILE_IN[i]==0)
      cout<<i<<", ";
  cout<<endl;

  cout<<"B_READ";cout<<endl;
  for ( int m = 0; m < _m; m++ )
    {
      for ( int d = 0; d < _d; d++ )
	cout<<get_B_READ(m,d)<<", ";
      cout<<endl;
    }
  cout<<endl;

  cout<<"B_WRITE";cout<<endl;
  for ( int m = 0; m < _m; m++ )
    {
      for ( int d = 0; d < _d; d++ )
	cout<<get_B_WRITE(m,d)<<", ";
      cout<<endl;
    }
  cout<<endl;

  cout<<"FILE_MD";cout<<endl;
  for ( int m = 0; m < _m; m++ )
    {
      for ( int d = 0; d < _d; d++ )
	cout<<get_FILE_MD(m,d)<<", ";
      cout<<endl;
    }
  cout<<endl;

  cout<<endl<<"NTASK = "<<NTASK<<endl;

  return true;
}




// imprime solucao
bool BDHeuri::imprime_sol(Data* data)
{
  bool continua;
  bool continua2;
  int  t;

  cout<<"**********************************************************************************************************"<<endl;
  cout<<"**********************************************************************************************************"<<endl;
  cout<<endl<<"---------------- MS = "<<MS<<" CST = "<<CST<<" FO = "<<FO<<") --------------"<<endl;
  for(int j=0; j < _m; j++) {cout<<left<<setw(tcol)<<" "<<setw(tcol)<<"mks="+to_string(MS_M[j]);} cout<<endl;
  for(int j=0; j < _m; j++) {cout<<left<<setw(tcol)<<" "<<setw(tcol)<<"cap="+to_string(CAP_M[j]);} cout<<endl; 
  for(int j=0; j < _m; j++) {cout<<left<<setw(tcol)<<"t)"<<setw(tcol)<<"(M"+to_string(j)+")";} cout<<endl; cout<<endl;

  continua = true;
  t        = 0;
  while (continua)
    {
      continua = false;
      for(int m=0; m < _m; m++)
	{
	  if (t >= QTD_M[m])
	    {
	      cout<<left<<setw(tcol)<<" "<<setw(tcol)<<" ";
	      continue;
	    }
	  else
	    {
	      continua  = true;
	      
	      // leitura
	      if (TL[t][m].tp == 1)
		{
		  cout<<left<<setw(tcol)<<TL[t][m].ti;
		  cout<<left<<setw(tcol)<<"r"+to_string(TL[t][m].tk)+"("+to_string(TL[t][m].dt)+")"+to_string(TL[t][m].vm);
		}
	  
	      // execucao
	      if (TL[t][m].tp == 0)
		{
		  cout<<left<<setw(tcol)<<TL[t][m].ti;
		  cout<<left<<setw(tcol)<<"x"+to_string(TL[t][m].tk);
		}
	  
	      // escrita
	      if (TL[t][m].tp == 2)
		{
		  cout<<left<<setw(tcol)<<TL[t][m].ti;
		  cout<<left<<setw(tcol)<<"w"+to_string(TL[t][m].tk)+"("+to_string(TL[t][m].dt)+")"+to_string(TL[t][m].vm);
		}
	  
	      // leitura de re-execucao
	      if (TL[t][m].tp == 4)
		{
		  cout<<left<<setw(tcol)<<TL[t][m].ti;
		  cout<<left<<setw(tcol)<<"r*"+to_string(TL[t][m].tk)+"("+to_string(TL[t][m].dt)+")"+to_string(TL[t][m].vm);
		}
	  
	      // execucao de re-execucao
	      if (TL[t][m].tp == 3)
		{
		  cout<<left<<setw(tcol)<<TL[t][m].ti;
		  cout<<left<<setw(tcol)<<"x*"+to_string(TL[t][m].tk);
		}
	      
	      // escrita de re-execucao
	      if (TL[t][m].tp == 5)
		{
		  cout<<left<<setw(tcol)<<TL[t][m].ti;
		  cout<<left<<setw(tcol)<<"w*"+to_string(TL[t][m].tk)+"("+to_string(TL[t][m].dt)+")"+to_string(TL[t][m].vm);
		}

	    }// else
	  
	}// for(m=0; m < _m; m++)

      cout<<endl;
      t++;
    }// while (continua)

  cout<<"**********************************************************************************************************"<<endl;
  cout<<"**********************************************************************************************************"<<endl;		  
  return true;
}



// salva melhor solucao em arquivo
bool BDHeuri::salva_best(Data* data, char * instance, double alfaMKS, double alfaCST)
{
  bool continua;
  bool continua2;
  int  t;

  ofstream filesol;
  filesol.open ("bestsol.txt");

  filesol<<"**********************************************************************************************************"<<endl;
  filesol<<"**********************************************************************************************************"<<endl;
  filesol<<endl<<"@@@ inst = "<<instance<<"\t alphaMKS = "<<alfaMKS<<"\t alphaCST = "<<alfaCST<<endl;
  filesol<<"@@@ --------------- MS = "<<MS<<" CST = "<<CST<<" FO = "<<FO<<") --------------"<<endl;
  for(int j=0; j < _m; j++) {filesol<<left<<setw(tcol)<<" "<<setw(tcol)<<"mks="+to_string(MS_M[j]);} filesol<<endl;
  for(int j=0; j < _m; j++) {filesol<<left<<setw(tcol)<<" "<<setw(tcol)<<"cap="+to_string(CAP_M[j]);} filesol<<endl; 
  for(int j=0; j < _m; j++) {filesol<<left<<setw(tcol)<<"t)"<<setw(tcol)<<"(M"+to_string(j)+")";} filesol<<endl; filesol<<endl;

  continua = true;
  t        = 0;
  while (continua)
    {
      continua = false;
      for(int m=0; m < _m; m++)
	{
	  if (t >= QTD_M[m])
	    {
	      filesol<<left<<setw(tcol)<<" "<<setw(tcol)<<" ";
	      continue;
	    }
	  else
	    {
	      continua  = true;
	      
	      // leitura
	      if (TL[t][m].tp == 1)
		{
		  filesol<<left<<setw(tcol)<<TL[t][m].ti;
		  filesol<<left<<setw(tcol)<<"r"+to_string(TL[t][m].tk)+"("+to_string(TL[t][m].dt)+")"+to_string(TL[t][m].vm);
		}
	  
	      // execucao
	      if (TL[t][m].tp == 0)
		{
		  filesol<<left<<setw(tcol)<<TL[t][m].ti;
		  filesol<<left<<setw(tcol)<<"x"+to_string(TL[t][m].tk);
		}
	  
	      // escrita
	      if (TL[t][m].tp == 2)
		{
		  filesol<<left<<setw(tcol)<<TL[t][m].ti;
		  filesol<<left<<setw(tcol)<<"w"+to_string(TL[t][m].tk)+"("+to_string(TL[t][m].dt)+")"+to_string(TL[t][m].vm);
		}
	  
	      // leitura de re-execucao
	      if (TL[t][m].tp == 4)
		{
		  filesol<<left<<setw(tcol)<<TL[t][m].ti;
		  filesol<<left<<setw(tcol)<<"r*"+to_string(TL[t][m].tk)+"("+to_string(TL[t][m].dt)+")"+to_string(TL[t][m].vm);
		}
	  
	      // execucao de re-execucao
	      if (TL[t][m].tp == 3)
		{
		  filesol<<left<<setw(tcol)<<TL[t][m].ti;
		  filesol<<left<<setw(tcol)<<"x*"+to_string(TL[t][m].tk);
		}
	      
	      // escrita de re-execucao
	      if (TL[t][m].tp == 5)
		{
		  filesol<<left<<setw(tcol)<<TL[t][m].ti;
		  filesol<<left<<setw(tcol)<<"w*"+to_string(TL[t][m].tk)+"("+to_string(TL[t][m].dt)+")"+to_string(TL[t][m].vm);
		}

	    }// else
	  
	}// for(m=0; m < _m; m++)

      filesol<<endl;
      t++;
    }// while (continua)

  filesol<<"**********************************************************************************************************"<<endl;
  filesol<<"**********************************************************************************************************"<<endl;

  filesol.close();
  return true;
}




// imprime melhor solucao que esta em arquivo
bool BDHeuri::imprime_best()
{

  ifstream ifs;

  cout<<endl<<"*******************************************************************************"<<endl;
  cout<<"******************************** MELHOR SOLUCAO  ******************************"<<endl;
  ifs.open ("bestsol.txt", std::ifstream::in);

  char cc = ifs.get();

  while (ifs.good()) {
    cout << cc;
    cc = ifs.get();
  }

  ifs.close();

  return true;
}







// metodo heuristico
// FLAG = 2  GRASP
// FLAG = 1  multistart guloso-aleatorio
// FLAG = 0  guloso (sem reexecucao)
// FLAG = -1 guloso (com reexecucao)
void BDHeuri::heuristica(Data* data, int MaxIt, int Maxtime, int mDEPU, char * instance)
{
  double BB_FO, B_FO, FO1, FO2;                        // melhor funcao objetivo
  int    BB_MS, B_MS, MS1, MS2;                        // melhor makespam
  double BB_MS_PART, B_MS_PART, MS_PART1, MS_PART2;    // melhor parcela na f.o. referente ao makespam
  double BB_CST, B_CST, CST1, CST2;                    // melhor custo financeiro
  double BB_CST_PART, B_CST_PART, CST_PART1, CST_PART2;// melhor parcela na f.o. referente ao custo financeiro

  /* **PARAMETROS** */
  int    ini_TMAX_LC = 100;                // tamanho inicial da lista de candidatos (para método guloso basta colocar tamanho 1)
  int    inc_TMAX_LC = 100000;            // incremento do tamanho da lista de candidatos
  
  double ini_alphaLC = 0.0;               // valor inicial do alpha da lista de candidatos (alpha = 0 é o guloso)
  double inc_alphaLC = 0.1;               // incremento do alpha da lista de candidatos
  double max_alpha   = 0.7;               // maximo valor de alpha
  
  MaxTam_D           = 10000;  // maximo tamanho de D_TASK, D_REEXC e D_WRITE para nao explodir a enumeracao (NAO LIMITAR, PODE DEIXAR TAREFAS DE FORA)
  MaxTam_lei         = 5;      // 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)
  tipo_enum_esc      = 1;      // 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 (COMPLETAMENTE INVIAVEL FAZER A ENUMERACAO TOTAL NA ESCRITA)
  /* *********** */

  /* variavel global */
  MAX_LV_BK          = 5;     // nivel maximo do backtracking para realizar as reexecuções (tarefa reexec tarefa que reexec tarefa que ...)
  
  // Combinacao (Pesada e Forte)
  //ini_TMAX_LC        = 100;
  //
  // Combinacao (Leve e Fraca)
  //ini_TMAX_LC        = 10;
  
  bool   valida;               // solucao valida foi encontrada ?
  bool   stop;                 // para o metodo ?

  // numero de iteracoes por alfa
  int    alfa_iter;
  int    ini_alfa_iter      = floor(MaxIt / 5);
  int    inc_alfa_iter      = 0; //floor(MaxIt / 100);
  int    inc_inc_alfa_iter  = 0; //floor(MaxIt / 100); 
  
  // depuracao
  DEPU = mDEPU;
  
  cout<<"----- multistart -----"<<endl;
  cout<<"  -- PARAMETROS"<<endl;
  cout<<"  -- MaxIt         = "<<MaxIt<<endl;
  cout<<"  -- Maxtime       = "<<Maxtime<<endl;
  cout<<"  -- MaxTam_lei    = "<<MaxTam_lei<<endl;
  cout<<"  -- MAX_LV_BK     = "<<MAX_LV_BK<<endl;
  cout<<"  -- ini_TMAX_LC   = "<<ini_TMAX_LC<<endl;
  cout<<"  -- inc_TMAX_LC   = "<<inc_TMAX_LC<<endl;
  cout<<"  -- max_sizeLC    = "<<max_sizeLC<<endl<<endl;
  cout<<"  -- ini_alphaLC   = "<<ini_alphaLC<<endl;
  cout<<"  -- inc_alphaLC   = "<<inc_alphaLC<<endl;
  cout<<"  -- max_sizealpha = "<<1<<endl<<endl;
  
    
  // tempo inicial
  start_h = clock();

  alphaLC = ini_alphaLC;               // parametro de aceitacao da lista RESTRITA de candidatos
  BB_FO   = INFINITY_COST;             // Melhor dos melhores (Best of the Best)

  alfa_iter = ini_alfa_iter;           // numero de iterações inicial para o valor inicial de alfa

  // --------- Guloso --------- 
  if ((FLAG==0) || (FLAG==-1))
    {
      ini_TMAX_LC = 1;
      MaxIt       = 1;
    }
  
  stop = false;
  while ((alphaLC <= max_alpha) and (!stop))
    {
      cout<<"alphaLC = "<<alphaLC;
      TMAX_LC = ini_TMAX_LC;    // tamanho da lista de candidatos

      while ((TMAX_LC < max_sizeLC)  and (!stop))
	{
	  B_FO    = INFINITY_COST;
	  cout<<"   TMAX_LC = "<<TMAX_LC<<"     ITER = "<<MaxIt /*alfa_iter*/<<endl;
	  
	  for(int it=0; it < MaxIt /*alfa_iter*/ and (!stop); it++)
	    {
	      // parada por tempo
	      if (((double)clock() - (double)start_h) / CLOCKS_PER_SEC >  Maxtime)
		{
		  cout<<"** limite de tempo ** "<<endl;
		  stop = true;
		  break;
		}
	      cout<<"       it) "<<it<<" "<<endl;

	      // ---- construtivo ----
	      valida = construtivo(data);

	      if (valida)
		{
		  FO1 = fobj(data, &MS1, &CST1, &MS_PART1, &CST_PART1);
		  FO1 = corrige_inconsistencia_com_struct_bl(data, instance, &MS1, &CST1, &MS_PART1, &CST_PART1);
		  if ((alphaLC == 0) and ((FLAG==0) || (FLAG==-1)))
		    {
		      //cout<<"         GULOSO ms="<<MS1<<" cst="<<CST1<<endl;
		      cout<<"@@GU "<<instance<<"\t"<<FO1<<"\t"<<MS1<<"\t"<<CST1<<"\t"<<(((double)clock() - (double)start_h) / CLOCKS_PER_SEC)<<endl;
		    }
		  else
		    cout<<"         CONST  ms="<<MS1<<" cst="<<CST1<<endl;
		  //imprime_sol(data);

		  
		  /***** Busca Local *******/
		  if (FLAG == 2)
		    FO1 = bl(data, &MS1, &CST1, &MS_PART1, &CST_PART1, Maxtime);
		  /*************************/
		  cout<<"         BL     ms="<<MS1<<" cst="<<CST1<<endl;
		  //imprime_sol(data);

		  
		  if (FO1 + data->PRECISAO < B_FO)
		    {
		      B_FO   = FO1;
		      B_MS   = MS1;
		      B_CST  = CST1;
		      B_MS_PART   = MS_PART1;
		      B_CST_PART  = CST_PART1;
		      
		      //cout<<"      @@@ it) "<<it<<" fo = "<<B_FO<<" ("<<B_MS_PART<<"+"<<B_CST_PART<<") \t(ms="<<B_MS<<" cst="<<B_CST<<")\t alphaLC = "<<alphaLC<<"\t tamLC = "<<TMAX_LC<<"\tt =   : "<<((double)clock() - (double)start_h) / CLOCKS_PER_SEC<<endl;
		      //imprime_estruturas(data);

		         
		      // Best of the Best
		      if (FO1 + data->PRECISAO < BB_FO)
			{
			  BB_FO   = FO1;
			  BB_MS   = MS1;
			  BB_CST  = CST1;
			  BB_MS_PART   = MS_PART1;
			  BB_CST_PART  = CST_PART1;
			  
			  //cout<<"################## ALFA = "<<alphaLC<<" TMAX_LC = "<<TMAX_LC<<" #################"<<endl;
			  cout<<"               ##BEST## it)"<<it<<" fo = "<<BB_FO<<" ("<<BB_MS_PART<<"+"<<BB_CST_PART<<") \t(ms="<<B_MS<<" cst="<<B_CST<<")\t alphaLC = "<<alphaLC<<"******************* \t tamLC = "<<TMAX_LC<<"\tt =   : "<<((double)clock() - (double)start_h) / CLOCKS_PER_SEC<<" ************************"<<endl;
			  //imprime_estruturas(data);
			  //imprime_sol(data);
			  salva_best(data,instance, data->alfa_t, data->alfa_b);

			  // Atualizou melhor solução, vamos reiniciar as iterações dessa configuração
			  it = 0;

			  // --------- Guloso -------------
			  if ((FLAG==0) || (FLAG==-1))
			    	{
				  stop = true;
				  break;
				}

			}// if (FO1 + data->PRECISAO < BB_FO)
		      else
			{
			  // encontrou solucao tao boa quanto a melhor
			  //if (DEPU){
			  if (fabs(FO1 - BB_FO) <= data->PRECISAO)
			    cout<<"            ##TÃO_BÃO_QUANTO it)"<<it<<" fo = "<<BB_FO<<" ("<<BB_MS_PART<<"+"<<BB_CST_PART<<") \t(ms="<<B_MS<<" cst="<<B_CST<<")\t alphaLC = "<<alphaLC<<"\t tamLC = "<<TMAX_LC<<"\tt =   : "<<((double)clock() - (double)start_h) / CLOCKS_PER_SEC<<" "<<endl; 
			  //else cout<<"#it "<<it<<") fo = "<<FO1<<"\t(ms="<<MS1<<" cst="<<CST1<<")\t alphaLC = "<<alphaLC<<"\t tamLC = "<<TMAX_LC<<"\tt =   : "<<((double)clock() - (double)start_h) / CLOCKS_PER_SEC<<endl;
			  //}
			}
		    		    	     		      
		    }//if (FO1 + data->PRECISAO < B_FO)
		  else
		    {
		      // encontrou solucao tao boa quanto a melhor
		      if (DEPU){
		      if (fabs(FO1 - BB_FO) <= data->PRECISAO)
			cout<<"   ##TÃO_BÃO_QUANTO it)"<<it<<" fo = "<<BB_FO<<" ("<<BB_MS_PART<<"+"<<BB_CST_PART<<") \t(ms="<<B_MS<<" cst="<<B_CST<<")\t alphaLC = "<<alphaLC<<"\t tamLC = "<<TMAX_LC<<"\tt =   : "<<((double)clock() - (double)start_h) / CLOCKS_PER_SEC<<" "<<endl;
		      else cout<<"#it "<<it<<") fo = "<<FO1<<"\t(ms="<<MS1<<" cst="<<CST1<<")\t alphaLC = "<<alphaLC<<"\t tamLC = "<<TMAX_LC<<"\tt =   : "<<((double)clock() - (double)start_h) / CLOCKS_PER_SEC<<endl;}
		    }
		  
		}// if (valida)
	      else
		{
		  cout<<"#it "<<it<<"--------------------------------- nao valida! ----------------------------------"<<endl;

		  // --------- Guloso -------------
		  if ((FLAG==0) || (FLAG==-1))
		    {
		      stop = true;
		      break;
		    }
		}

	      // soh executa uma iteração com alpha=0 (guloso)
	      if (alphaLC == 0)
		{
		  alphaLC = 0.1;
		  break;
		}
	      
	    }// for(int it=0; it < MaxIt; it++)
	  
	  //if (data->DEPU) cout<<"it )"<<it<<" fo = "<<B_FO<<"\t(ms="<<B_MS<<" cst="<<B_CST<<")\t alphaLC = "<<alphaLC<<"\t tamLC = "<<TMAX_LC<<"\tt =   : "<<((double)clock() - (double)start_h) / CLOCKS_PER_SEC<<endl;
	  
	  // incremento
	  TMAX_LC = TMAX_LC + inc_TMAX_LC;
	  
	}//while(TMAX_LC < max_sizeLC)
  
      alphaLC   = alphaLC   + inc_alphaLC;

      alfa_iter     = alfa_iter + inc_alfa_iter;
      inc_alfa_iter = inc_alfa_iter + inc_inc_alfa_iter;
      
    }//while (alphaLC <= 1)


  cout<<"MELHOR SOLUCAO ENCONTRADA"<<endl;
  imprime_best();

  if (FLAG==1)  cout<<"@@MS "<<instance<<"\t"<<BB_FO<<"\t"<<BB_MS<<"\t"<<BB_CST<<"\t"<<(((double)clock() - (double)start_h) / CLOCKS_PER_SEC)<<endl;
  if (FLAG==2)  cout<<"@@GR "<<instance<<"\t"<<BB_FO<<"\t"<<BB_MS<<"\t"<<BB_CST<<"\t"<<(((double)clock() - (double)start_h) / CLOCKS_PER_SEC)<<endl;
  
  cout<<endl<<endl<<"TEMPO TOTAL = "<<((double)clock() - (double)start_h) / CLOCKS_PER_SEC<<endl;
  cout<<"SOL         = "<<BB_FO<<endl;
  cout<<"   MSK      = "<<BB_MS<<endl;
  cout<<"   CUSTO    = "<<BB_CST<<endl;
  cout<<endl<<"bk_lv_max  = "<<bk_lv_max+1<<endl;
}




/*****************************************************************************************/
/************************************ BUSCA LOCAL ****************************************/
/*****************************************************************************************/


// carrega estruturas da busca local a partir da estruturas do construtivo
bool BDHeuri::TL_struct_bl(Data* data)
{
  int  min_t, m_t, pred, suc;
  bool para, para2, achou;
  int  aDepu=0;

  if (aDepu) cout<<endl<<"--- TL_struct_bl -----"<<endl;

  /* numero de elementos em ELE */
  num_ELE = 0;

  /* numero de tarefas na ordem */
  num_ORDER_T = 0;

  /*vetor TASK_RXC (uso temporario) ira armazenar quantas vezes a tarefa i foi executada (+1) */
  for ( int i = 0; i < _n; i++ )
    TASK_RXC[i] = 0;

  for ( int d = 0; d < _d; d++ )
    {
      /*vetor FILE_RXC (uso temporario) ira armazenar quantas vezes o dado d foi gerado/escrito (+1) */
      FILE_RXC[d] = 0;
    }

  
      
  /* inicializa vetor de elementos  */
  for (int i = 0; i < max_elem_bl; i++)
    {
      ELE[i].ty  =-1; ELE[i].id  =-1; ELE[i].cp  =-1; ELE[i].vm  =-1; ELE[i].elet = -1;
      ELE[i].tes =0;  ELE[i].tle =0;  ELE[i].tles=0;  ELE[i].tpred=0; ELE[i].tsuc = 0;
    }

  /* inicializa vetor de ordem */
  for (int i = 0; i < max_order_bl; i++)
    {
      ORDER_T[i].id   =-1; ORDER_T[i].cp   =-1;  ORDER_T[i].ele  =-1;  ORDER_T[i].TL_t =-1; ORDER_T[i].TL_m =-1;
    }

  /* vetores (uso temporario) com os candidatos iniciais para entrarem na ordem */
  for(int m=0; m < _m; m++)
    {
      CAP_M[m]    = -1; /* vetor (uso temporario) de tarefas candidatas a entrar na ordem (por maquina) */
      CAP_M_t1[m] = -1; /* vetor (uso temporario) dos tempos finais (lei+exec+esc) das tarefas candidatas a entrar na ordem (por maquina) */
      CAP_M_t2[m] = -1; /* vetor (uso temporario) do indice em TL da ultima escrita da tarefa candidata a entrar na ordem (por maquina) */

      /* guarda se a maquina m tem dado ESTATICO d */
      for ( int d = 0; d < _d; d++ )
	FILE_MD[m][d] = -1;
    }

  /* inicializacao dos vetores com os candidatos iniciais para entrarem na ordem */
  for(int m=0; m < _m; m++)
    {
      /*procurar pela primeira tarefa a ser executada na maquina */
      para=false;
      for(int t=0; (t < QTD_M[m]) && !para; t++)
	if ((TL[t][m].tp == 0) || (TL[t][m].tp == 3))
	  {
	    CAP_M[m] = TL[t][m].tk;

	    /* procura agora o tempo final da ultima escrita desta tarefa */
	    for(int t2=t; (t2 < QTD_M[m]) && !para; t2++)
	      /* a acao deve ser uma escrita e a depois dela nao pode ser uma escrita (pois eh a ultima escrita da tarefa) */
	      if (((TL[t2][m].tp == 2) || (TL[t2][m].tp == 5)) && ((TL[t2+1][m].tp != 2) && (TL[t2+1][m].tp != 5)))
		{
		  CAP_M_t1[m] = TL[t2][m].ti + TL[t2][m].tm;
		  CAP_M_t2[m] = t2;
		  para        = true;
		}
	    if (CAP_M_t1[m]==-1) { cout<<"**ERRO ERRO ERRO** tarefa "<<CAP_M[m]<<" na maquina "<<m<<" nao achamos ultima escrita"<<endl; abort();}
	  }
    }

  /* --------- Primeiro as tarefas ------------ */
  // enquanto houver tarefa para colocar na ordem
  para = false;
  while (!para)
    {
      /* escolhe proxima tarefa a ser inserida em Elementos e na ordem */
      min_t = data->INFINT; //_t_max;
      m_t   = -1;
      for(int m=0; m < _m; m++)
	if (CAP_M[m] != -1)
	  {
	    if (CAP_M_t1[m] <= min_t)
	      {
		min_t = CAP_M_t1[m];
		m_t   = m;
	      }
	  }// for(int el_t, m=0; m < _m; m++)  if (CAP_M[m] != -1)

      if (m_t != -1)
	{
	  /* insere tarefa em Elementos e na ordem */
	  ELE[num_ELE].ty  = 0;
	  ELE[num_ELE].id  = CAP_M[m_t];
	  ELE[num_ELE].cp  = TASK_RXC[(int) CAP_M[m_t]];
	  ELE[num_ELE].vm  = m_t;
	  ELE[num_ELE].ord = num_ORDER_T;

	  ORDER_T[num_ORDER_T].id      = CAP_M[m_t];
	  ORDER_T[num_ORDER_T].cp      = TASK_RXC[(int) CAP_M[m_t]];
	  ORDER_T[num_ORDER_T].ele     = num_ELE;
	  ORDER_T[num_ORDER_T].TL_t    = CAP_M_t2[m_t];
	  ORDER_T[num_ORDER_T].TL_m    = m_t;
	  if (aDepu) cout<<endl<<"   insere t"<<(int) CAP_M[m_t]<<"("<<TASK_RXC[(int) CAP_M[m_t]]<<") em m"<<m_t<<" <ele="<<num_ELE<<"> na com ultima escrita em TL["<<ORDER_T[num_ORDER_T].TL_t<<"]["<<ORDER_T[num_ORDER_T].TL_m<<"]"<<endl;
	  
	  TASK_RXC[(int) CAP_M[m_t]]++;
	  num_ELE     = num_ELE + 1;
	  num_ORDER_T = num_ORDER_T + 1;

	  /* atualiza a proxima tarefa candidata da maquina m_t */
	  para2      = false;
	  CAP_M[m_t] = -1;
	  for(int t=(int) CAP_M_t2[m_t]; (t < QTD_M[m_t]) && !para2; t++)
	    if ((TL[t][m_t].tp == 0) || (TL[t][m_t].tp == 3))
	      {
		CAP_M[m_t] = TL[t][m_t].tk;

		/* procura agora o tempo final da ultima escrita desta tarefa */
		for(int t2=t; (t2 < QTD_M[m_t]) && !para2; t2++)
		  /* a acao deve ser uma escrita e a depois dela nao pode ser uma escrita (pois eh a ultima escrita da tarefa) */
		  if (((TL[t2][m_t].tp == 2) || (TL[t2][m_t].tp == 5)) && ((TL[t2+1][m_t].tp != 2) && (TL[t2+1][m_t].tp != 5))) 
		    {
		      CAP_M_t1[m_t] = TL[t2][m_t].ti + TL[t2][m_t].tm;
		      CAP_M_t2[m_t] = t2;
		      para2        = true;
		    }
		if (CAP_M_t1[m_t]==-1) { cout<<"**ERRO ERRO ERRO** (tarefa) "<<CAP_M[m_t]<<" na maquina "<<m_t<<" nao achamos ultima escrita"<<endl; abort();}
		
	      }// for(int t=(int) CAP_M_t2[m_t]; (t < QTD_M[m_t]) && !para2; t++)  if ((TL[t][m_t].tp == 0) || (TL[t][m_t].tp == 3))
	  
	}// if (m_t != -1)

      // nao encontrou mais nenhuma tarefa no scheduling para ser inserida (ja foi tudo, pode parar)
      else
	para = true;
      	    
    }// while (!para)
  
  /* --------- Depois escrita dos dados ------------ */
  for(int el_t,id_t, cp_t,t,t2,m,ord=0; ord < num_ORDER_T; ord++)
    {
      /* tarefa,copia e indice do elemento da tarefa da ordem, TL[t][m] indica a ultima escrita da tarefa na time line TL */
      id_t = ORDER_T[ord].id;
      cp_t = ORDER_T[ord].cp;
      el_t = ORDER_T[ord].ele;
      t    = ORDER_T[ord].TL_t;
      m    = ORDER_T[ord].TL_m;

      /* para cada escrita da tarefa, gerar elemento. Para achar as escritas anda para cima na TL */
      for (int t2=t; t2>=0; t2--)
	if ((TL[t2][m].tp == 2) || (TL[t2][m].tp == 5))
	  {
	    ELE[num_ELE].ty   = 1;
	    ELE[num_ELE].id   = TL[t2][m].dt;
	    ELE[num_ELE].cp   = FILE_RXC[TL[t2][m].dt];
	    ELE[num_ELE].vm   = TL[t2][m].vm;
	    ELE[num_ELE].elet = el_t;
	    
	    /* tarefa que escreveu o dado */
	    ELE[el_t].es[ELE[el_t].tes] = num_ELE;
	    ELE[el_t].tes++;

	    FILE_RXC[TL[t2][m].dt]++;
	    num_ELE = num_ELE + 1;
	    
	  }//for (int t2=t; t2>=0; t2--)  if ((TL[t2][m].tp == 2) || (TL[t2][m].tp == 5))
	else
	  break;
      
    }//for(int el_t,id_t, cp_t,t,t2,m,ord=0; ord < num_ORDER_T; ord++)

  /* --------- Depois leitura dos dados ------------ */
  /*para cada maquina */
 for(int el_t, el_t2, el_d, m=0; m < _m; m++)
    /*para cada operacao (exec, leit, escri) na maquina */
    for(int t=0; t < QTD_M[m]; t++)
      {
	/* leitura da execucao */ /* leitura da re-execucao */
	if ((TL[t][m].tp == 1) || (TL[t][m].tp == 4))
	  {
	    /* indice do elemento da tarefa que leu o dado */
	    el_t=-1;
	    for (int i=0; i<num_ELE; i++)
	      if ((ELE[i].ty == 0) && (ELE[i].id == TL[t][m].tk) && (ELE[i].vm == TL[t][m].vmo))
	    	{
	    	  el_t = i;
	    	  break;
	    	}
	    if (el_t==-1) { cout<<"**ERRO ERRO ERRO** dado "<<ELE[num_ELE].id<<" copia "<<ELE[num_ELE].cp<<" nao achamos a tarefa "<<TL[t][m].tk<<" que a escreveu nos Elementos"<<endl; abort();}
	    	    
	    /* indice do elemento dado que foi lido */
	    el_d=-1;
	    for (int i=0; i<num_ELE; i++)
	      if ((ELE[i].ty == 1) && (ELE[i].id == TL[t][m].dt) && (ELE[i].vm == TL[t][m].vm))
		{
		  el_d = i;
		  break;
		}
	    
	    /* dado não encontrado nos Elementos, ele é estatico */
	    if (el_d==-1)
	      {
		ELE[el_t].les[ELE[el_t].tles] = TL[t][m].dt;
		ELE[el_t].vms[ELE[el_t].tles] = TL[t][m].vm;
		ELE[el_t].tles++;

		/* guarda os dados/maquinas estaticos na solução */
		FILE_MD[TL[t][m].vm][TL[t][m].dt] = 1;
	      }
	    /* dinamico, esta na lista de elementos */
	    else
	      {
		ELE[el_t].le[ELE[el_t].tle] = el_d;
		ELE[el_t].tle++;

		/* indice do elemento da tarefa que escreveu o dado */
		el_t2=ELE[el_d].elet;

		/********** PREDECESSOR ***********/
		/* checa se o predecessor ja foi inserido na lista */
		for (achou=false, pred=0; pred < ELE[el_t].tpred; pred++)
		  if (ELE[el_t].pred[pred] == el_t2)
		    {
		      achou=true;
		      break;
		    }
		/* atualiza lista de predecessores da tarefa que leu o dado */
		if (!achou)
		  {
		    ELE[el_t].pred[ELE[el_t].tpred] = el_t2;
		    ELE[el_t].tpred++;
		  }

		/********** SUCESSOR ***********/
		/* checa se o sucessor ja foi inserido na lista */
		for (achou=false, suc=0; suc < ELE[el_t2].tsuc; suc++)
		  if (ELE[el_t2].suc[suc] == el_t)
		    {
		      achou=true;
		      break;
		    }
		/* atualiza lista de sucessores da tarefa que leu o dado */
		if (!achou)
		  {
		    ELE[el_t2].suc[ELE[el_t2].tsuc] = el_t;
		    ELE[el_t2].tsuc++;
		  }
		
	      }
	       
	  }// if ((TL[t][m].tp == 1) || (TL[t][m].tp == 4))
	
      }// for(int el_t, m=0; m < _m; m++)  for(int t=0; t < QTD_M[m]; t++)
  
  return true;
}



// imprime estrutura de representacao da solucao da busca local
bool BDHeuri::imprime_struct_bl(Data* data)
{
  cout<<endl<<"------ Estruturas da solução do bl --------"<<endl;

  cout<<"-- Elementos --"<<endl;
  cout<<"index)\tid(cp)\t<vm> "<<endl;
  for(int el=0; el < num_ELE; el++)
    {
      if (ELE[el].ty == 0)
	{
	  cout<<el<<")\t"<<"t"<<ELE[el].id<<"("<<ELE[el].cp<<")\t<"<<ELE[el].vm<<">";
	  cout<<"\t esc=(";
	  for(int i=0; i < ELE[el].tes; i++) cout<<ELE[el].es[i]<<",";
	  cout<<")\t le_d=(";
	  for(int i=0; i < ELE[el].tle; i++) cout<<ELE[el].le[i]<<",";
	  cout<<")\t le_s=<";
	  for(int i=0; i < ELE[el].tles; i++) cout<<ELE[el].les[i]<<"("<<ELE[el].vms[i]<<"),";
	  cout<<">\t PRED=(";
	  for(int i=0; i < ELE[el].tpred; i++) cout<<ELE[el].pred[i]<<",";
	  cout<<")\t SUC=(";
	  for(int i=0; i < ELE[el].tsuc; i++) cout<<ELE[el].suc[i]<<",";
	  cout<<")"<<endl;
	}

      if (ELE[el].ty == 1)
	cout<<el<<")\t"<<"d"<<ELE[el].id<<"("<<ELE[el].cp<<")\t<"<<ELE[el].vm<<">\t t_esc=("<<ELE[el].elet<<")"<<endl;
    }

  cout<<endl<<"-- Ordem Tarefas --"<<endl;
  cout<<"index)\tid(cp)\t<ele>"<<endl;
  for(int ord=0; ord < num_ORDER_T; ord++)
    cout<<ord<<")\t"<<"t"<<ORDER_T[ord].id<<"("<<ORDER_T[ord].cp<<")\t<"<<ORDER_T[ord].ele<<">"<<endl;
								       
  cout<<endl<<"----------------------------------------"<<endl;

  return true;
}


// calcula funcao objetivo na busca local
// flag=0, calcula f.o. apenas
// flag=1, calcula f.o e carrega estrutura da time line TL
double BDHeuri::fobj_bl(Data* data, int* makespam, double* custof, double* ms_part, double* cs_part, int flag)
{
  int    maxi, start, finish, execucao, leitura_d, leitura_s, escrita;
  double obj;
  int    aDepu=0;
  
  if (aDepu) cout<<endl<<"--- fobj_bl -----"<<endl;

  /* inicializa estruturas da TL */
  if (flag == 1)
    {
      for ( int m = 0; m < _m; m++ ) { MS_M[m]  = 0; CAP_M[m] = 0; QTD_M[m] = 0; }

      /* dados estaticos */
      for ( int d = 0; d < _d; d++ )
	for (int ind=0; ind < data->d_st_or_tam[d]; ind++)
	  CAP_M[data->d_st_or[d][ind]]     +=  data->d_size[d];
      
      for ( int t = 0; t < _a_max; t++ )
	for ( int m = 0; m < _m; m++ )
	  TL[t][m].vmo = TL[t][m].tp = TL[t][m].tk = TL[t][m].dt = TL[t][m].vm = TL[t][m].tm = TL[t][m].ti = -1 ;
    }
    
  // tempos de termino de (leitura+execucao+escrita) de elementos tarefas
  for (int i = 0; i < max_elem_bl; i++)
    ELE[i].tfim = 0;

   for ( int m = 0; m < _m; m++ )
    {
      // vetor (uso temporario) de tempos de termino de execucao de cada maquina 
      CAP_M_t1[m] = 0;
      // vetor (uso temporario) de capacidade das maquinas
      CAP_M_t2[m] = 0;
    }

   /* dados estaticos */
   for ( int d = 0; d < _d; d++ )
     for (int ind=0; ind < data->d_st_or_tam[d]; ind++)
       CAP_M_t2[data->d_st_or[d][ind]]  +=  data->d_size[d];
  
  for(int el_t, id_t, cp_t, m_t,ord=0; ord < num_ORDER_T; ord++)
    {
      /* id e copia da tarefa */
      id_t = ORDER_T[ord].id;
      cp_t = ORDER_T[ord].cp;
      el_t = ORDER_T[ord].ele;
      if (aDepu) cout<<"t"<<id_t<<"("<<cp_t<<") vm="<<ELE[el_t].vm<<endl;
      
      /* onde a tarefa vai ser executada */
      m_t = ELE[ORDER_T[ord].ele].vm;

      /* o maior tempo de termino dentre as tarefas predecessoras */
      maxi = 0;
      for (int el_pred, pred=0; pred < ELE[el_t].tpred; pred++)
	{
	  el_pred = ELE[el_t].pred[pred];
	  if (ELE[el_pred].tfim > maxi)
	    maxi = ELE[el_pred].tfim;
	}
      if (aDepu) cout<<"   maxipred="<<maxi<<endl;
      if (aDepu) cout<<"   mks_maq ="<<CAP_M_t1[m_t]<<endl;
      
      /* tempo de inicio da tarefa eh o maximo entre o max. dos predecessores e tempo de uso da maquina */
      if (maxi >= CAP_M_t1[m_t]) start = maxi;
      else                       start = CAP_M_t1[m_t];
      if (aDepu) cout<<"   start="<<start<<endl;

      /* carrega TL */
      if (flag == 1)
	MS_M[m_t] = start;
      
      /* ---tempo de leitura da tarefa--- */

      /* leitura dinamica */
      leitura_d = 0;
      for(int m_dl, d_dl, el_dl, dl=0; dl < ELE[ORDER_T[ord].ele].tle; dl++)
	{
	  /* elemento do dado a ser lido pela tarefa */
	  el_dl = ELE[ORDER_T[ord].ele].le[dl];

	  /* dado a ser lido */
	  d_dl = ELE[el_dl].id;

	  /* maquina a ser lido o dado */
	  m_dl = ELE[el_dl].vm;
  
	  leitura_d += data->t_djp(d_dl, m_t, m_dl);

	  /* carrega TL */
	  if (flag == 1)
	    {
	      TL[QTD_M[m_t]][m_t].vmo = m_t; 
	      TL[QTD_M[m_t]][m_t].tp  = 1;
	      TL[QTD_M[m_t]][m_t].tk  = id_t;
	      TL[QTD_M[m_t]][m_t].dt  = d_dl;
	      TL[QTD_M[m_t]][m_t].vm  = m_dl;
	      TL[QTD_M[m_t]][m_t].tm  = data->t_djp(d_dl, m_t, m_dl);
	      TL[QTD_M[m_t]][m_t].ti  = MS_M[m_t];
	      
	      QTD_M[m_t]++;
	      if (QTD_M[m_t] >= _a_max) {cout<<"ERRO tamanho de TL passou _a_max.  "<<_a_max << endl; exit(0);}
	      MS_M[m_t] += data->t_djp(d_dl, m_t, m_dl);
	    }
	  
	}//for(int m_dl, d_dl, el_dl, dl=0; dl < ELE[ORDER_T[ord].ele].tle; dl++)
      if (aDepu) cout<<"   leitura dinamica="<<leitura_d<<endl;

      /* leitura estatica */
      leitura_s = 0;
      for(int m_dl, d_dl, el_dl, dl=0; dl < ELE[ORDER_T[ord].ele].tles; dl++)
	{
	  /* dado a ser lido */
	  d_dl = ELE[ORDER_T[ord].ele].les[dl];

	  /* maquina a ser lido o dado */
	  m_dl = ELE[ORDER_T[ord].ele].vms[dl];;
  
	  leitura_s += data->t_djp(d_dl, m_t, m_dl);

	  /* carrega TL */
	  if (flag == 1)
	    {
	      TL[QTD_M[m_t]][m_t].vmo = m_t; 
	      TL[QTD_M[m_t]][m_t].tp  = 1;
	      TL[QTD_M[m_t]][m_t].tk  = id_t;
	      TL[QTD_M[m_t]][m_t].dt  = d_dl;
	      TL[QTD_M[m_t]][m_t].vm  = m_dl;
	      TL[QTD_M[m_t]][m_t].tm  = data->t_djp(d_dl, m_t, m_dl);
	      TL[QTD_M[m_t]][m_t].ti  = MS_M[m_t];
	      
	      QTD_M[m_t]++;
	      if (QTD_M[m_t] >= _a_max) {cout<<"ERRO tamanho de TL passou _a_max.  "<<_a_max << endl; exit(0);}
	      MS_M[m_t] += data->t_djp(d_dl, m_t, m_dl);
	    }
	}
      if (aDepu) cout<<"   leitura estatica="<<leitura_s<<endl;

      /* ---tempo de execucao--- */
      execucao = data->t_ij(id_t, m_t);
      if (aDepu) cout<<"   exec="<<execucao<<endl;

      /* carrega TL */
      if (flag == 1)
	{
	  TL[QTD_M[m_t]][m_t].vmo = m_t; 
	  TL[QTD_M[m_t]][m_t].tp  = 0; 
	  TL[QTD_M[m_t]][m_t].tk  = id_t;
	  TL[QTD_M[m_t]][m_t].tm  = data->t_ij(id_t, m_t);
	  TL[QTD_M[m_t]][m_t].ti  = MS_M[m_t];
	      
	  QTD_M[m_t]++;
	  if (QTD_M[m_t] >= _a_max) {cout<<"ERRO tamanho de TL passou _a_max.  "<<_a_max << endl; exit(0);}
	  MS_M[m_t] += data->t_ij(id_t, m_t);
	}
      
      /* ---tempo de escrita da tarefa--- */
      escrita = 0;
      for(int m_de, d_de, el_de, de=0; de < ELE[ORDER_T[ord].ele].tes; de++)
	{
	  /* elemento do dado a ser escrito pela tarefa */
	  el_de = ELE[ORDER_T[ord].ele].es[de];

	  /* dado a ser escrito */
	  d_de = ELE[el_de].id;

	  /* maquina a ser escrito o dado */
	  m_de = ELE[el_de].vm;
  
	  escrita += data->t_djp(d_de, m_t, m_de);

	  /* carrega TL */
	  if (flag == 1)
	    {
	      TL[QTD_M[m_t]][m_t].vmo = m_t; 
	      TL[QTD_M[m_t]][m_t].tp  = 2;
	      TL[QTD_M[m_t]][m_t].tk  = id_t;
	      TL[QTD_M[m_t]][m_t].dt  = d_de;
	      TL[QTD_M[m_t]][m_t].vm  = m_de;
	      TL[QTD_M[m_t]][m_t].tm  = data->t_djp(d_de, m_t, m_de);
	      TL[QTD_M[m_t]][m_t].ti  = MS_M[m_t];
	      
	      QTD_M[m_t]++;
	      if (QTD_M[m_t] >= _a_max) {cout<<"ERRO tamanho de TL passou _a_max.  "<<_a_max << endl; exit(0);}
	      MS_M[m_t]   += data->t_djp(d_de, m_t, m_de);
	      CAP_M[m_de] += data->d_size[d_de]; 
	    }

	  CAP_M_t2[m_de] += data->d_size[d_de];
	}
      if (aDepu) cout<<"   escrita="<<escrita<<endl;
      
      // atualiza vetores de tempos da maquina e da tarefa
      CAP_M_t1[m_t]  = start + leitura_d + leitura_s + execucao + escrita;
      ELE[el_t].tfim = start + leitura_d + leitura_s + execucao + escrita;
      if (aDepu) cout<<"   M_msk["<<m_t<<"]="<<CAP_M_t1[m_t]<<endl;
      if (aDepu) cout<<"   T_msk["<<id_t<<"]="<<ELE[el_t].tfim<<endl;
	
    }// for(int id_t,m_t,ord=0; ord < num_ORDER_T; ord++)

  // Makespam e Custo financeiro
  * makespam=0; * custof = 0;
  for ( int m = 0; m < _m; m++ )
    {
      if (CAP_M_t1[m] > * makespam)
	* makespam = CAP_M_t1[m];

      * custof += CAP_M_t1[m] * data->m_cost[m];
    }

  //f.o.
  * ms_part  = ((data->alfa_t * (* makespam))/ data->max_time_wkf /*data->t*/);
  * cs_part  = ((data->alfa_b * (* custof)) / data->max_cost_wkf /*data->c_max*/);
  obj        =  (* ms_part) + (* cs_part);
  if (flag == 1) { MS = * makespam; MS_PART = * ms_part; CST_PART = * cs_part; CST = * custof; FO = obj; }
      
  if (aDepu) cout<<endl<<"MKS="<<* makespam<<" CSTF="<<* custof<<" FO="<<obj<<endl;

  return obj;
}


/* vizinhanca que tenta mudar a maquina de uma tarefa */
bool BDHeuri::move_t_m_bl(Data* data, double f_obj, int* makespam, double* custof, double* ms_part, double* cs_part, int Depu)
{
  int      vm_el, tam_tasks;
  int      _makespam;
  double   _obj, _custof, _ms_part, _cs_part;

  if (Depu) cout<<"---------------------- move_t_m_bl --------------------------"<<endl;

  // TASK_T_MIN ira conter os indices dos elementos tarefas que seram considerados para movimento
  tam_tasks = 0;
  for (int el=0; el<num_ELE; el++)
    if (ELE[el].ty == 0)
      {
	TASK_T_MIN[tam_tasks] = el;
	tam_tasks++;
      }
  if (Depu) { cout<<"TASK = "; for(int ii = 0; ii <tam_tasks; ii++) { cout<<TASK_T_MIN[ii]<<", ";} cout<<endl;} 

  // Embaralha aleatoreamente os indices das tarefas a serem analisadas
  for(int temp_id, jj, ii = tam_tasks-1; ii > 0; ii--)
    {
        jj             = rand() % (ii+1);
	temp_id        = TASK_T_MIN[ii];
	TASK_T_MIN[ii] = TASK_T_MIN[jj];
	TASK_T_MIN[jj] = temp_id;
    }
  if (Depu) { cout<<"Suffle = "; for(int ii = 0; ii <tam_tasks; ii++) { cout<<TASK_T_MIN[ii]<<", ";} cout<<endl; }

  // chama a função objetvo uma vez para carregar o vetor CAP_M_t1 que guarda os mks das maquinas na solução 
  _obj = fobj_bl(data, &_makespam, &_custof, &_ms_part, &_cs_part, 0);

  // guarda os mks (pois a cada chamada de fobj_bl modifica CAP_M_t1)
  for ( int m = 0; m < _m; m++ )
    MS_M_t1[m] = CAP_M_t1[m];
  
  //for (int msite, el=0; el<num_ELE; el++)
  // if (ELE[el].ty == 0)
  for (int msite, el, i_task=0; i_task<tam_tasks; i_task++)
    {
      /* indice da tarefa da vez */
      el = TASK_T_MIN[i_task];
      
      /* VM do elemento */
      vm_el = ELE[el].vm;
      
      // inicializa estruturas que marcam qual lista de maquinas (uma por site) que contem a maquina com menor (mks,custo,slow) que ja foi considerada para realizar um movimento
      for (int s = 0; s < data->num_site; s++)
	{
	  SITE_MIN_MAQ[s].mks = INFINITY_COST;
	  SITE_MIN_MAQ[s].cst = INFINITY_COST;
	  SITE_MIN_MAQ[s].slw = INFINITY_COST;
	}
      
      for ( int m = 0; m < _m; m++ )
	if (m != vm_el)
	  /* se for tarefa nao pode ir para maquina cache */
	  if (data->m_storage[m] == 1)
	    {
	      // +++++++++++++++++++++++++++++++++++++++ VERIFICA MOVIMENTO DE TAREFAS APENAS PARA AS MELHORES MAQUINAS POR SITE +++++++++++++++++++++++
	      //if (Depu) {cout<<"      SITE_MIN_MAQ = "; for (int s = 0; s < data->num_site; s++) {  cout<<"("<<SITE_MIN_MAQ[s].mks<<", "<<SITE_MIN_MAQ[s].cst<<", "<<SITE_MIN_MAQ[s].slw<<"), ";  }cout<<endl; }
	      
	      msite = data->m_site[m];
	      if ((MS_M_t1[m] >= SITE_MIN_MAQ[msite].mks) and (data->m_cost[m] >= SITE_MIN_MAQ[msite].cst) and (data->m_slow[m] >= SITE_MIN_MAQ[msite].slw))
		continue;
	      else
		{
		  // se tem um possivel movimento melhor vai verificar, mas soh atualiza os melhores valores do site se os 3 valores (mks,custo,slow) forem melhores.
		  if ((MS_M_t1[m] <= SITE_MIN_MAQ[msite].mks) and (data->m_cost[m] <= SITE_MIN_MAQ[msite].cst) and (data->m_slow[m] <= SITE_MIN_MAQ[msite].slw))
		    {
		      SITE_MIN_MAQ[msite].mks = MS_M_t1[m]; SITE_MIN_MAQ[msite].cst = data->m_cost[m]; SITE_MIN_MAQ[msite].slw = data->m_slow[m];
		    }
		}
	      // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	      
	      // ->
	      ELE[el].vm = m;
	      
	      // calcula custo do movimento
	      _obj = fobj_bl(data, &_makespam, &_custof, &_ms_part, &_cs_part, 0);
	      if (Depu) cout<<"       testa t"<<ELE[el].id<<" m"<<vm_el<<" -> m"<<m<<"\t ("<<_obj<<")"<<endl;
	      
	      // teste de inviabilidade de tempo (o vetor CAP_M_t1 que guarda os mks das maquinas na solução da chamada de fobj_bl)
	      if (CAP_M_t1[m] > _t_max)
		{
		  if (Depu) cout<<"   !!! passou tempo maximo !!!"<<endl;
		}
	      else
		{
		  // achou movimento de melhora, pode retornar
		  if (_obj + data->PRECISAO < f_obj)
		    {
		      * makespam = _makespam;
		      * custof   = _custof;
		      * ms_part  = _ms_part;
		      * cs_part  = _cs_part;
		      
		      if (Depu) cout<<"   move_t_m) t"<<ELE[el].id<<" m"<<vm_el<<" -> m"<<m<<"\t MKS=" <<_makespam<<"\t CST="<<_custof<<"\t ("<<_obj<<")"<<endl;
		      //if (Depu) imprime_sol(data);
		      
		      return true;
		    }
		}// else
	      
	      // <-
	      ELE[el].vm = vm_el;
	      
	    }// if (data->m_storage[m] == 1)
      
    }//for (int i=0; i<num_ELE; i++)
  
  return false;
}




/* realiza uma sequencia de movimentos de custo 0, para ter diversidade na solução */
bool BDHeuri::zero_cost_move(Data* data, double f_obj, int* makespam, double* custof, double* ms_part, double* cs_part, int Depu)
{
  int      vm_el, tam_tasks, tam_dados, tam_maqs;
  int      _makespam;
  double   _obj, _custof, _ms_part, _cs_part;
  bool     continua;
  bool     zero_task  = true;
  bool     zero_dado  = true;
  
  if (Depu) cout<<"---------------------- zero_cost_move --------------------------"<<endl;

  // ********************** TAREFAS ************************** 

  if (zero_task)
    {
      if (Depu) cout<<"---------------------- TASKzero_cost_move --------------------------"<<endl;

      // TASK_T_MIN ira conter os indices dos elementos tarefas que seram considerados para movimento
      tam_tasks = 0;
      for (int el=0; el<num_ELE; el++)
	if (ELE[el].ty == 0)
	  {
	    TASK_T_MIN[tam_tasks] = el;
	    tam_tasks++;
	  }
      //if (Depu) { cout<<"TASK = "; for(int ii = 0; ii <tam_tasks; ii++) { cout<<TASK_T_MIN[ii]<<", ";} cout<<endl;} 
      
      // Embaralha aleatoreamente os indices das tarefas a serem analisadas
      for(int temp_id, jj, ii = tam_tasks-1; ii > 0; ii--)
	{
	  jj             = rand() % (ii+1);
	  temp_id        = TASK_T_MIN[ii];
	  TASK_T_MIN[ii] = TASK_T_MIN[jj];
	  TASK_T_MIN[jj] = temp_id;
	}
      //if (Depu) { cout<<"Suffle = "; for(int ii = 0; ii <tam_tasks; ii++) { cout<<TASK_T_MIN[ii]<<", ";} cout<<endl; }
      
      // chama a função objetvo uma vez para carregar o vetor CAP_M_t1 que guarda os mks das maquinas na solução 
      _obj = fobj_bl(data, &_makespam, &_custof, &_ms_part, &_cs_part, 0);
      
      // guarda os mks (pois a cada chamada de fobj_bl modifica CAP_M_t1)
      for ( int m = 0; m < _m; m++ )
	MS_M_t1[m] = CAP_M_t1[m];
      
      //for (int msite, el=0; el<num_ELE; el++)
      // if (ELE[el].ty == 0)
      for (int msite, el, i_task=0; i_task<tam_tasks; i_task++)
	{
	  /* indice da tarefa da vez */
	  el = TASK_T_MIN[i_task];
	  
	  /* VM do elemento */
	  vm_el = ELE[el].vm;
	  
	  // inicializa estruturas que marcam qual lista de maquinas (uma por site) que contem a maquina com menor (mks,custo,slow) que ja foi considerada para realizar um movimento
	  for (int s = 0; s < data->num_site; s++)
	    {
	      SITE_MIN_MAQ[s].mks = INFINITY_COST;
	      SITE_MIN_MAQ[s].cst = INFINITY_COST;
	      SITE_MIN_MAQ[s].slw = INFINITY_COST;
	    }
	  
	  // MS_M_t2 ira conter os indices das maquinas que seram considerados para movimento
	  tam_maqs = 0;
	  for ( int m = 0; m < _m; m++ )
	    if ((m != vm_el) and (data->m_storage[m] == 1))
	      {
		MS_M_t2[tam_maqs] = m;
		tam_maqs++;
	      }
	  
	  // Embaralha aleatoreamente os indices das maquinas a serem analisadas
	  for(int temp_id, jj, ii = tam_maqs-1; ii > 0; ii--)
	    {
	      jj             = rand() % (ii+1);
	      temp_id        = MS_M_t2[ii];
	      MS_M_t2[ii]    = MS_M_t2[jj];
	      MS_M_t2[jj]    = temp_id;
	    }
	  
	  //for ( int m = 0; m < _m; m++ )
	  //if (m != vm_el)
	  /* se for tarefa nao pode ir para maquina cache */
	  // if (data->m_storage[m] == 1)
	  continua = true;
	  for (int m, i_maq=0; i_maq<tam_maqs and continua; i_maq++)
	    {
	      /* indice da maquina da vez */
	      m = MS_M_t2[i_maq];
	      
	      // +++++++++++++++++++++++++++++++++++++++ VERIFICA MOVIMENTO DE TAREFAS APENAS PARA AS MELHORES MAQUINAS POR SITE +++++++++++++++++++++++
	      //if (Depu) {cout<<"      SITE_MIN_MAQ = "; for (int s = 0; s < data->num_site; s++) {  cout<<"("<<SITE_MIN_MAQ[s].mks<<", "<<SITE_MIN_MAQ[s].cst<<", "<<SITE_MIN_MAQ[s].slw<<"), ";  }cout<<endl; }
	      
	      msite = data->m_site[m];
	      if ((MS_M_t1[m] >= SITE_MIN_MAQ[msite].mks) and (data->m_cost[m] >= SITE_MIN_MAQ[msite].cst) and (data->m_slow[m] >= SITE_MIN_MAQ[msite].slw))
		continue;
	      else
		{
		  // se tem um possivel movimento melhor vai verificar, mas soh atualiza os melhores valores do site se os 3 valores (mks,custo,slow) forem melhores.
		  if ((MS_M_t1[m] <= SITE_MIN_MAQ[msite].mks) and (data->m_cost[m] <= SITE_MIN_MAQ[msite].cst) and (data->m_slow[m] <= SITE_MIN_MAQ[msite].slw))
		    {
		      SITE_MIN_MAQ[msite].mks = MS_M_t1[m]; SITE_MIN_MAQ[msite].cst = data->m_cost[m]; SITE_MIN_MAQ[msite].slw = data->m_slow[m];
		    }
		}
	      // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	      
	      // ->
	      ELE[el].vm = m;
	      
	      // calcula custo do movimento
	      _obj = fobj_bl(data, &_makespam, &_custof, &_ms_part, &_cs_part, 0);
	      if (Depu) cout<<"       testa t"<<ELE[el].id<<" m"<<vm_el<<" -> m"<<m<<"\t ("<<_obj<<")"<<endl;
	      
	      // achou movimento de custo 0
	      if (abs(_obj  - f_obj) <= data->PRECISAO)
		{
		  * makespam = _makespam;
		  * custof   = _custof;
		  * ms_part  = _ms_part;
		  * cs_part  = _cs_part;
		  
		  if (Depu) cout<<"           --- move_t_m) t"<<ELE[el].id<<" m"<<vm_el<<" -> m"<<m<<"\t MKS=" <<_makespam<<"\t CST="<<_custof<<"\t ("<<_obj<<")"<<endl;
		  //if (Depu) imprime_sol(data);
		  
		  continua = false;
		  continue;
		}
	      
	      // <-
	      ELE[el].vm = vm_el;
	      
	    }// for (int m, i_maq=0; i_maq<tam_maqs; i_maq++)
	  
	}//for (int msite, el, i_task=0; i_task<tam_tasks; i_task++)

    }// if (zero_task)





  // ********************** DADOS ************************** 

  if (zero_dado)
    {
      if (Depu) cout<<"---------------------- DADOzero_cost_move --------------------------"<<endl;

      // TASK_T_MIN ira conter os indices dos elementos dados que seram considerados para movimento
      tam_dados = 0;
      for (int el=0; el<num_ELE; el++)
	if (ELE[el].ty == 1)
	  {
	    TASK_T_MIN[tam_dados] = el;
	    tam_dados++;
	  }
      //if (Depu) { cout<<"DADOS = "; for(int ii = 0; ii <tam_tasks; ii++) { cout<<TASK_T_MIN[ii]<<", ";} cout<<endl;} 
      
      // Embaralha aleatoreamente os indices dos dados a serem analisadas
      for(int temp_id, jj, ii = tam_dados-1; ii > 0; ii--)
	{
	  jj             = rand() % (ii+1);
	  temp_id        = TASK_T_MIN[ii];
	  TASK_T_MIN[ii] = TASK_T_MIN[jj];
	  TASK_T_MIN[jj] = temp_id;
	}
      //if (Depu) { cout<<"Suffle = "; for(int ii = 0; ii <tam_tasks; ii++) { cout<<TASK_T_MIN[ii]<<", ";} cout<<endl; }
      
      // chama a função objetvo uma vez para carregar o vetor CAP_M_t1 que guarda os mks das maquinas na solução 
      _obj = fobj_bl(data, &_makespam, &_custof, &_ms_part, &_cs_part, 0);
      
      // guarda os mks (pois a cada chamada de fobj_bl modifica CAP_M_t1)
      for ( int m = 0; m < _m; m++ )
	MS_M_t1[m] = CAP_M_t1[m];
      
      //for (int msite, el=0; el<num_ELE; el++)
      // if (ELE[el].ty == 0)
      for (int msite, el, i_dado=0; i_dado<tam_dados; i_dado++)
	{
	  /* indice do dado da vez */
	  el = TASK_T_MIN[i_dado];
	  
	  /* VM do elemento */
	  vm_el = ELE[el].vm;
	  
	  // MS_M_t2 ira conter os indices das maquinas que seram considerados para movimento
	  tam_maqs = 0;
	  for ( int m = 0; m < _m; m++ )
	    if ((m != vm_el) and (data->m_storage[m] == 0))
	      {
		MS_M_t2[tam_maqs] = m;
		tam_maqs++;
	      }
	  
	  // Embaralha aleatoreamente os indices das maquinas a serem analisadas
	  for(int temp_id, jj, ii = tam_maqs-1; ii > 0; ii--)
	    {
	      jj             = rand() % (ii+1);
	      temp_id        = MS_M_t2[ii];
	      MS_M_t2[ii]    = MS_M_t2[jj];
	      MS_M_t2[jj]    = temp_id;
	    }
	  
	  //for ( int m = 0; m < _m; m++ )
	  //if (m != vm_el)
	  /* se for tarefa nao pode ir para maquina cache */
	  // if (data->m_storage[m] == 1)
	  continua = true;
	  for (int m, i_maq=0; i_maq<tam_maqs and continua; i_maq++)
	    {
	      /* indice da maquina da vez */
	      m = MS_M_t2[i_maq];
	      	      
	      // ->
	      ELE[el].vm = m;
	      
	      // calcula custo do movimento
	      _obj = fobj_bl(data, &_makespam, &_custof, &_ms_part, &_cs_part, 0);
	      if (Depu) cout<<"       testa d"<<ELE[el].id<<" m"<<vm_el<<" -> m"<<m<<"\t ("<<_obj<<")"<<endl;
	      
	      // achou movimento de custo 0
	      if (abs(_obj  - f_obj) <= data->PRECISAO)
		{
		  * makespam = _makespam;
		  * custof   = _custof;
		  * ms_part  = _ms_part;
		  * cs_part  = _cs_part;
		  
		  if (Depu) cout<<"           --- move_d_m) d"<<ELE[el].id<<" m"<<vm_el<<" -> m"<<m<<"\t MKS=" <<_makespam<<"\t CST="<<_custof<<"\t ("<<_obj<<")"<<endl;
		  //if (Depu) imprime_sol(data);
		  
		  continua = false;
		  continue;
		}
	      
	      // <-
	      ELE[el].vm = vm_el;
	      
	    }// for (int m, i_maq=0; i_maq<tam_maqs; i_maq++)
	  
	}//for (int msite, el, i_task=0; i_task<tam_tasks; i_task++)

    }// if (zero_dado)

  return true;
}










/* vizinhanca que tenta mudar a maquina de duas tarefas que estão na mesma maquina */
bool BDHeuri::move_2t_m_bl(Data* data, double f_obj, int* makespam, double* custof, double* ms_part, double* cs_part, int Depu)
{
  int      vm_el;
  int      _makespam;
  double   _obj, _custof, _ms_part, _cs_part;

  if (Depu) cout<<"---------------------- move_2t_m_bl --------------------------"<<endl;

  // chama a função objetvo uma vez para carregar o vetor CAP_M_t1 que guarda os mks das maquinas na solução 
  _obj = fobj_bl(data, &_makespam, &_custof, &_ms_part, &_cs_part, 0);

  // guarda os mks (pois a cada chamada de fobj_bl modifica CAP_M_t1)
  for ( int m = 0; m < _m; m++ )
    MS_M_t1[m] = CAP_M_t1[m];
  
  for (int msite, id_el, vm_el, el=0; el<num_ELE; el++)
    if (ELE[el].ty == 0)
      {
	id_el = ELE[el].id;
	vm_el = ELE[el].vm;
		
	for (int id_el2, vm_el2, el2=el+1; el2<num_ELE; el2++)
	  if (ELE[el2].ty == 0)
	    {
	      id_el2 = ELE[el2].id;
	      vm_el2 = ELE[el2].vm;

	      if (vm_el == vm_el2)
		{
		  if (Depu) cout<<"t"<<id_el<<" e t"<<id_el2<<" em m"<<vm_el<<endl;
		  // inicializa estruturas que marcam qual lista de maquinas (uma por site) que contem a maquina com menor (mks,custo,slow) que ja foi considerada para realizar um movimento
		  for (int s = 0; s < data->num_site; s++)
		    {SITE_MIN_MAQ[s].mks  = INFINITY_COST; SITE_MIN_MAQ[s].cst  = INFINITY_COST; SITE_MIN_MAQ[s].slw  = INFINITY_COST;}

		  for ( int msite, m = 0; m < _m; m++ )
		    if (m != vm_el)
		      /* se for tarefa nao pode ir para maquina cache */
		      if (data->m_storage[m] == 1)
			{
			  // +++++++++++++++++++++++++++++++++++++++ VERIFICA MOVIMENTO DE TAREFAS APENAS PARA AS MELHORES MAQUINAS POR SITE DA MAQUINA 1 +++++++++++++++++++++++
			  //if (Depu) {cout<<"   SITE_MIN_MAQ = "; for (int s = 0; s < data->num_site; s++) {  cout<<"("<<SITE_MIN_MAQ[s].mks<<", "<<SITE_MIN_MAQ[s].cst<<", "<<SITE_MIN_MAQ[s].slw<<"), ";  }cout<<endl; }
			  
			  msite  = data->m_site[m];
			  if ((MS_M_t1[m] >= SITE_MIN_MAQ[msite].mks) and (data->m_cost[m] >= SITE_MIN_MAQ[msite].cst) and (data->m_slow[m] >= SITE_MIN_MAQ[msite].slw))
			    continue;
			  else
			    {
			      // se tem um possivel movimento melhor vai verificar, mas soh atualiza os melhores valores do site se os 3 valores (mks,custo,slow) forem melhores.
			      if ((MS_M_t1[m] <= SITE_MIN_MAQ[msite].mks) and (data->m_cost[m] <= SITE_MIN_MAQ[msite].cst) and (data->m_slow[m] <= SITE_MIN_MAQ[msite].slw))
				{
				  SITE_MIN_MAQ[msite].mks = MS_M_t1[m]; SITE_MIN_MAQ[msite].cst = data->m_cost[m]; SITE_MIN_MAQ[msite].slw = data->m_slow[m];
				}
			    }
			  // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
			  if (Depu) cout<<"   m"<<m<<endl;

			  // inicializa estruturas que marcam qual lista de maquinas (uma por site) que contem a maquina com menor (mks,custo,slow) que ja foi considerada para realizar um movimento
			  for (int s = 0; s < data->num_site; s++)
			    {SITE_MIN_MAQ2[s].mks = INFINITY_COST; SITE_MIN_MAQ2[s].cst = INFINITY_COST; SITE_MIN_MAQ2[s].slw = INFINITY_COST;}
		  
			  for ( int msite2, m2 = 0; m2 < _m; m2++ )
			    if (m2 != vm_el)
			      /* se for tarefa nao pode ir para maquina cache */
			      if (data->m_storage[m2] == 1)
				{
				  // +++++++++++++++++++++++++++++++++++++++ VERIFICA MOVIMENTO DE TAREFAS APENAS PARA AS MELHORES MAQUINAS POR SITE DA MAQUINA 2 +++++++++++++++++++++++
				  //if (Depu) {cout<<"      SITE_MIN_MAQ2 = "; for (int s = 0; s < data->num_site; s++) {  cout<<"("<<SITE_MIN_MAQ2[s].mks<<", "<<SITE_MIN_MAQ2[s].cst<<", "<<SITE_MIN_MAQ2[s].slw<<"), ";  }cout<<endl; }
				  
				  msite2 = data->m_site[m2];
				  if ((MS_M_t1[m2] >= SITE_MIN_MAQ2[msite2].mks) and (data->m_cost[m2] >= SITE_MIN_MAQ2[msite2].cst) and (data->m_slow[m2] >= SITE_MIN_MAQ2[msite2].slw))
				    {
				      continue;
				    }
				  else
				    {
				      // se tem um possivel movimento melhor vai verificar, mas soh atualiza os melhores valores do site se os 3 valores (mks,custo,slow) forem melhores.
				      if ((MS_M_t1[m2] <= SITE_MIN_MAQ2[msite2].mks) and (data->m_cost[m2] <= SITE_MIN_MAQ2[msite2].cst) and (data->m_slow[m2] <= SITE_MIN_MAQ2[msite2].slw))
					{
					  SITE_MIN_MAQ2[msite2].mks = MS_M_t1[m2]; SITE_MIN_MAQ2[msite2].cst = data->m_cost[m2]; SITE_MIN_MAQ2[msite2].slw = data->m_slow[m2];
					}
				    }
				  // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
				  if (Depu) cout<<"      m"<<m2<<endl;

				  // ->
				  ELE[el].vm  = m;
				  ELE[el2].vm = m2;
	      
				  // calcula custo do movimento
				  _obj = fobj_bl(data, &_makespam, &_custof, &_ms_part, &_cs_part, 0);
				  if (Depu) cout<<"          testa t"<<ELE[el].id<<" m"<<vm_el<<" -> m"<<m<<" & t"<<ELE[el2].id<<" m"<<vm_el2<<" -> m"<<m2<<"\t ("<<_obj<<")"<<endl;
				  
				  // teste de inviabilidade de tempo (o vetor CAP_M_t1 que guarda os mks das maquinas na solução da chamada de fobj_bl)
				  if ((CAP_M_t1[m] > _t_max) or (CAP_M_t1[m2] > _t_max))
				    {
				      if (Depu) cout<<"   !!! passou tempo maximo !!!"<<endl;
				    }
				  else
				    {
				      // achou movimento de melhora, pode retornar
				      if (_obj + data->PRECISAO < f_obj)
					{
					  * makespam = _makespam;
					  * custof   = _custof;
					  * ms_part  = _ms_part;
					  * cs_part  = _cs_part;
					  if (Depu) cout<<"          ********* MOVE t"<<ELE[el].id<<" m"<<vm_el<<" -> m"<<m<<" & t"<<ELE[el2].id<<" m"<<vm_el2<<" -> m"<<m2<<"\t ("<<_obj<<") ***************"<<endl;
					 
					  //if (Depu) imprime_sol(data);
					  
					  return true;
					}
				    }// else
		
				  // <-
				  ELE[el].vm  = vm_el;
				  ELE[el2].vm = vm_el2;
				  
				}//if (data->m_storage[m2] == 1)

			}//if (data->m_storage[m] == 1)

		}// if (vm_el == vm_el2)

	    }//if (ELE[el2].ty == 0)

      }//if (ELE[el].ty == 0)
      
  return false;
}









/* vizinhanca que tenta mudar a maquina de um dado */
bool BDHeuri::move_d_m_bl(Data* data, double f_obj, int* makespam, double* custof, double* ms_part, double* cs_part, int Depu)
{
  int      vm_el, inviavel;
  int      _makespam;
  double   _obj, _custof, _ms_part, _cs_part;

  //Depu = 1;
  if (Depu) cout<<"---------------------- move_d_m_bl --------------------------"<<endl;

  /****************** FASE 1 *************/
  /* tenta mover dados para outros sites */
  /***************************************/
  
  for (int msite, el=0; el<num_ELE; el++)
    if (ELE[el].ty == 1)
      {
	/* VM do elemento */
	vm_el = ELE[el].vm;

	for ( int m = 0; m < _m; m++ )
	  if (m != vm_el)
	    /* nao pode ir para maquina sem ser cache */
	    if (data->m_storage[m] == 0)
	      {
		// ->
		ELE[el].vm = m;
	      
		// calcula custo do movimento
		_obj = fobj_bl(data, &_makespam, &_custof, &_ms_part, &_cs_part, 0);
		if (Depu) cout<<"       testa d"<<ELE[el].id<<" m"<<vm_el<<" -> m"<<m<<"\t ("<<_obj<<")"<<endl;

		// teste de inviabilidade 
		inviavel = 0;							  
		for ( int ii = 0; ii < _m; ii++ )
		  {
		    // teste de inviabilidade de tempo (o vetor CAP_M_t1 que guarda os mks das maquinas na solução da chamada de fobj_bl)
		    if (CAP_M_t1[ii] > _t_max)
		      {
			inviavel = 1;
			if (Depu) cout<<"   !!! passou tempo maximo !!! na maq "<<ii<<endl;
			break; 
		      }
		    // teste de inviabilidade de capacidade da maquina (o vetor CAP_M_t2 que guarda o quantidade de dados das maquinas na solução da chamada de fobj_bl)
		    if (CAP_M_t2[m] > data->m_cap[m])
		      {
			inviavel = 1;
			if (Depu) cout<<"   !!! passou capacidade da maquina !!! na maq "<<ii<<endl;
			break; 
		      }
		  }// for ( int ii = 0; ii < _m; ii++ )

		if (inviavel == 0)
		  {
		    // achou movimento de melhora, pode retornar
		    if (_obj + data->PRECISAO < f_obj)
		      {
			* makespam = _makespam;
			* custof   = _custof;
			* ms_part  = _ms_part;
			* cs_part  = _cs_part;
			
			if (Depu) cout<<"   move_m) d"<<ELE[el].id<<" m"<<vm_el<<" -> m"<<m<<"\t MKS=" <<_makespam<<"\t CST="<<_custof<<"\t ("<<_obj<<")"<<endl;
			//if (Depu) imprime_sol(data);
			
			return true;
		      }
		  }// if (inviavel == 0)
	       	      
		// <-
		ELE[el].vm = vm_el;
	      
	      }// if (data->m_storage[m] == 0)
      
      }//for (int i=0; i<num_ELE; i++)

  /************************************************************************* FASE 2 **************************************************************/
  /* para cada tarefa, verifica se a leitura pode ser feita localmente por um dado no seu proprio site (podendo ser uma copia do dado existente) */
  /***********************************************************************************************************************************************/

  //Depu = 1;
  // if (Depu) cout<<"FASE 2"<<endl;
  // for (int vm_t, site_t, id_t, el=0; el<num_ELE; el++)
  //   if (ELE[el].ty == 0)
  //     {
  // 	id_t    = ELE[el].id;
  // 	vm_t    = ELE[el].vm;
  // 	site_t  = data->m_site[vm_t];
  // 	if (Depu) cout<<"T"<<id_t<<" (site "<<site_t<<")"<<endl;
	
  // 	/*********************************** leitura dinamica ******************************/
  // 	if (ELE[el].tle > 0)
  // 	  {
  // 	    for(int dl_el, id_dl, vm_dl, site_dl, ii=0; ii < ELE[el].tle; ii++)
  // 	      {
  // 		dl_el         = ELE[el].le[ii];
  // 		id_dl         = ELE[dl_el].id;
  // 		vm_dl         = ELE[dl_el].vm;
  // 		site_dl       = data->m_site[vm_dl];
  // 		if (Depu) cout<<"   Le dinamico D"<<id_dl<<" em M"<<vm_dl<<" (site "<<site_dl<<")"<<endl;

  // 		// o dado de leitura nao esta no mesmo site
  // 		if (site_t != site_dl)
  // 		  {
  // 		    // ---- procura copia local dinamica 
  // 		    for (int vm_cp, site_cp, id_cp, el2=0; el2<num_ELE; el2++)
  // 		      if ((ELE[el2].ty == 1) and (ELE[el2].id == id_dl) and (el2 != dl_el))
  // 			{
  // 			  id_cp   = ELE[el2].id;
  // 			  vm_cp   = ELE[el2].vm;
  // 			  site_cp = data->m_site[vm_cp];
  // 			  if (Depu) cout<<"      Tem D"<<id_cp<<" dinamico em M"<<vm_cp<<endl;

  // 			  if (site_cp != site_dl)
  // 			    {
  // 			      // ->
  // 			      ELE[el].le[ii] = el2;
  // 			      if (Depu) cout<<"         Achou copia em outro site, YEABA"<<endl;
	      
  // 			      // calcula custo do movimento
  // 			      _obj = fobj_bl(data, &_makespam, &_custof, &_ms_part, &_cs_part, 0);
  // 			      if (Depu) cout<<"         --- testa t"<<id_t<<" que lia d"<<id_dl<<"("<<ELE[dl_el].cp<<") em m"<<vm_dl<<" e vai ler d"<<id_cp<<"("<<ELE[el2].cp<<") em m"<<vm_cp<<" "<<_obj<<"->"<<f_obj<<endl;

  // 			      // achou movimento de melhora, pode retornar
  // 			      if (_obj + data->PRECISAO < f_obj)
  // 				{
  // 				  * makespam = _makespam;
  // 				  * custof   = _custof;
  // 				  * ms_part  = _ms_part;
  // 				  * cs_part  = _cs_part;
  // 				  /*if (Depu)*/ cout<<"            *** move t"<<id_t<<" que lia d"<<id_dl<<"("<<ELE[dl_el].cp<<") em m"<<vm_dl<<" e vai ler d"<<id_cp<<"("<<ELE[el2].cp<<") em m"<<vm_cp<<endl;
  // 				   //if (Depu) imprime_sol(data);
			
  // 				  return true;
  // 				}

  // 			      //<--
  // 			      ELE[el].le[ii] = dl_el;
			      
  // 			    }//  if (site_cp == site_t)
			  
  // 			}//if ((ELE[el2].ty == 0) and (ELE[el2].id == id_dl))

  // 		    // ---- procura copia local estatica
  // 		    if (FILE_MD[data->vm_st_site[site_t]][id_dl] == 1)
  // 		      {
  // 			int vm_cpe = data->vm_st_site[site_t];
  // 			int id_cpe = id_dl;
  // 			if (Depu) cout<<"      Tem D"<<id_cpe<<" estatico em M"<<vm_cpe<<endl;

  // 			//-> coloca no estatico
  // 			ELE[el].les[ELE[el].tles] = id_cpe;
  // 			ELE[el].vms[ELE[el].tles] = vm_cpe;
  // 			ELE[el].tles++;

  // 			//-> tira do dinamico
  // 			for(int jj=ii; jj < ELE[el].tle-1; jj++)
  // 			  ELE[el].le[jj] = ELE[el].le[jj+1];
  // 			ELE[el].tle--;
			  
  // 			// calcula custo do movimento
  // 			_obj = fobj_bl(data, &_makespam, &_custof, &_ms_part, &_cs_part, 0);
  // 			if (Depu) cout<<"         --- testa t"<<id_t<<" que lia d"<<id_dl<<"("<<ELE[dl_el].cp<<") em m"<<vm_dl<<" e vai ler d"<<id_cpe<<"(estatico) em m"<<vm_cpe<<endl;
 
  // 			// achou movimento de melhora, pode retornar
  // 			if (_obj + data->PRECISAO < f_obj)
  // 			  {
  // 			    /*if (Depu)*/ cout<<"         ****** move t"<<id_t<<" que lia d"<<id_dl<<"("<<ELE[dl_el].cp<<") em m"<<vm_dl<<" e vai ler d"<<id_cpe<<"(estatico) em m"<<vm_cpe<<endl;
  // 			    // Estatico local eh sempre uma melhora, nao tem como piorar, vindo de uma leitura dinamica em outro site
  // 			    * makespam = _makespam;
  // 			    * custof   = _custof;
  // 			    * ms_part  = _ms_part;
  // 			    * cs_part  = _cs_part;
			    
  // 			    return true;
  // 			  }
			
  // 			//-> tira no estatico
  // 			ELE[el].tles--;

  // 			//-> coloca no dinamico
  // 			int davez = dl_el;
  // 			for(int temp, jj=ii; jj < ELE[el].tle; jj++)
  // 			  {
  // 			    temp           = ELE[el].le[jj];
  // 			    ELE[el].le[jj] = davez;
  // 			    davez          = temp;
  // 			  }
  // 			ELE[el].le[ELE[el].tle] = davez;
  // 			ELE[el].tle++;
			
  // 		      }//if (FILE_MD[data->vm_st_site[site_t]][id_dl] == 1)
		    
  // 		  }//if (site_t != site_de)
	       
  // 	      }//for(int de_el, vm_de, ii=0; ii < ELE[el].tle; ii++)

  // 	  }//if (ELE[el].tle > 0)

  // 	/*********************************** leitura estatica ******************************/
  // 	if (ELE[el].tles > 0)
  // 	  {
  // 	    for(int id_dls, vm_dls, site_dls, ii=0; ii < ELE[el].tles; ii++)
  // 	      {
  // 		id_dls      = ELE[el].les[ii];
  // 		vm_dls      = ELE[el].vms[ii];
  // 		site_dls    = data->m_site[vm_dls];
  // 		if (Depu) cout<<"   Le estatico D"<<id_dls<<" em M"<<vm_dls<<" (site "<<site_dls<<")"<<endl;

  // 		// o dado de leitura nao esta no mesmo site
  // 		if (site_t != site_dls)
  // 		  {
  // 		    // ---- procura copia local dinamica 
  // 		    for (int vm_cp, site_cp, id_cp, el2=0; el2<num_ELE; el2++)
  // 		      if ((ELE[el2].ty == 1) and (ELE[el2].id == id_dls))
  // 			{
  // 			  id_cp   = ELE[el2].id;
  // 			  vm_cp   = ELE[el2].vm;
  // 			  site_cp = data->m_site[vm_cp];
  // 			  if (Depu) cout<<"      Tem D"<<id_cp<<" dinamico em M"<<vm_cp<<endl;

  // 			   if (site_cp != site_dls)
  // 			    {
  // 			      // ->tira do estatico
  // 			      for(int jj=ii; jj < ELE[el].tles-1; jj++)
  // 				{
  // 				  ELE[el].les[jj] = ELE[el].les[jj+1];
  // 				  ELE[el].vms[jj] = ELE[el].vms[jj+1];
  // 				}
  // 			      ELE[el].tles--;
			      
  // 			      // ->coloca no dinamico
  // 			      ELE[el].le[ELE[el].tle] = el2;
  // 			      ELE[el].tle++;
  // 			      if (Depu) cout<<"         Achou copia em outro site, YEABA"<<endl;
	      
  // 			      // calcula custo do movimento
  // 			      _obj = fobj_bl(data, &_makespam, &_custof, &_ms_part, &_cs_part, 0);
  // 			      if (Depu) cout<<"         --- testa t"<<id_t<<" que lia d"<<id_dls<<"(estatico) em m"<<vm_dls<<" e vai ler d"<<id_cp<<"("<<ELE[el2].cp<<") em m"<<vm_cp<<" "<<_obj<<"->"<<f_obj<<endl;

  // 			      // achou movimento de melhora, pode retornar
  // 			      if (_obj + data->PRECISAO < f_obj)
  // 				{
  // 				  * makespam = _makespam;
  // 				  * custof   = _custof;
  // 				  * ms_part  = _ms_part;
  // 				  * cs_part  = _cs_part;
  // 				  /*if (Depu) */ cout<<"         *** move t"<<id_t<<" que lia d"<<id_dls<<"(estatico) em m"<<vm_dls<<" e vai ler d"<<id_cp<<"("<<ELE[el2].cp<<") em m"<<vm_cp<<" "<<_obj<<"->"<<f_obj<<endl;
  // 				   //if (Depu) imprime_sol(data);
			
  // 				  return true;
  // 				}

  // 			      // coloca no estatico
  // 			      int davez1 = id_dls;
  // 			      int davez2 = vm_dls;
  // 			      for(int temp, jj=ii; jj < ELE[el].tles; jj++)
  // 				{
  // 				  temp             = ELE[el].les[jj];
  // 				  ELE[el].les[jj]  = davez1;
  // 				  davez1           = temp;

  // 				  temp             = ELE[el].vms[jj];
  // 				  ELE[el].vms[jj]  = davez2;
  // 				  davez2           = temp;
  // 				}
  // 			      ELE[el].les[ELE[el].tles] = davez1;
  // 			      ELE[el].vms[ELE[el].tles] = davez2;
  // 			      ELE[el].tles++;
			      
  // 			      //<- tira do dinamico
  // 			      ELE[el].tle--;
			      
  // 			    }//  if (site_cp == site_t)
			  
  // 			}//if ((ELE[el2].ty == 0) and (ELE[el2].id == id_dl))

  // 		  }//if (site_cp != site_dls)
		
  // 	      }//for(int id_dls, vm_dls, site_dls, ii=0; ii < ELE[el].tles; ii++)
	    
  // 	  }//if (ELE[el].tles > 0)
	
  //     }// if (ELE[el].ty == 1)
	
  return false;
}









/* vizinhanca que tenta mudar o site de uma execução/escrita */
bool BDHeuri::move_exec_esc_site_bl(Data* data, double f_obj, int* makespam, double* custof, double* ms_part, double* cs_part, int Depu)
{
  int      vm_el;
  int      _makespam, inviavel;
  double   _obj, _custof, _ms_part, _cs_part;

  // chama a função objetvo uma vez para carregar o vetor CAP_M_t1 que guarda os mks das maquinas na solução 
  _obj = fobj_bl(data, &_makespam, &_custof, &_ms_part, &_cs_part, 0);

  if (Depu) cout<<"---------------------- move_exec_esc_site_bl --------------------------obj = "<<_obj<<endl;
  
  // guarda os mks (pois a cada chamada de fobj_bl modifica CAP_M_t1)
  for ( int m = 0; m < _m; m++ )
    MS_M_t1[m] = CAP_M_t1[m];
  
  for (int site_el, msite, el=0; el<num_ELE; el++)
    if (ELE[el].ty == 0)
      {
	/* VM do elemento (tarefa) */
	vm_el   = ELE[el].vm;
	site_el = data->m_site[vm_el];
	  
	// inicializa estruturas que marcam qual lista de maquinas (uma por site) que contem a maquina com menor (mks,custo,slow) que ja foi considerada para realizar um movimento
	for (int s = 0; s < data->num_site; s++)
	  {
	    SITE_MIN_MAQ[s].mks = INFINITY_COST;
	    SITE_MIN_MAQ[s].cst = INFINITY_COST;
	    SITE_MIN_MAQ[s].slw = INFINITY_COST;
	  }
	      
	for ( int m = 0; m < _m; m++ )
	  /* move para outro site */
	  if (site_el != data->m_site[m])
	    {
	      /* nao pode ir para maquina cache */
	      if (data->m_storage[m] == 1)
		{
		  // +++++++++++++++++++++++++++++++++++++++ VERIFICA MOVIMENTO DE TAREFAS APENAS PARA AS MELHORES MAQUINAS POR SITE +++++++++++++++++++++++
		  //if (Depu) {cout<<"      SITE_MIN_MAQ = "; for (int s = 0; s < data->num_site; s++) {  cout<<"("<<SITE_MIN_MAQ[s].mks<<", "<<SITE_MIN_MAQ[s].cst<<", "<<SITE_MIN_MAQ[s].slw<<"), ";  }cout<<endl; }
		  
		  msite = data->m_site[m];
		  if ((MS_M_t1[m] >= SITE_MIN_MAQ[msite].mks) and (data->m_cost[m] >= SITE_MIN_MAQ[msite].cst) and (data->m_slow[m] >= SITE_MIN_MAQ[msite].slw))
		    continue;
		  else
		    {
		      // se tem um possivel movimento melhor vai verificar, mas soh atualiza os melhores valores do site se os 3 valores (mks,custo,slow) forem melhores.
		      if ((MS_M_t1[m] <= SITE_MIN_MAQ[msite].mks) and (data->m_cost[m] <= SITE_MIN_MAQ[msite].cst) and (data->m_slow[m] <= SITE_MIN_MAQ[msite].slw))
			{
			  SITE_MIN_MAQ[msite].mks = MS_M_t1[m]; SITE_MIN_MAQ[msite].cst = data->m_cost[m]; SITE_MIN_MAQ[msite].slw = data->m_slow[m];
			}
		    }
		  // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

		  /*cout<<"TASK) "<<ELE[el].id<<endl;
		    cout<<"A) ELE[de_el].vm = ";		  
		    for(int de_el, ii=0; ii < ELE[el].tes; ii++)
		    cout<<"d"<<ELE[ELE[el].es[ii]].id<<"->m"<<ELE[ELE[el].es[ii]].vm<<", ";
		    cout<<endl;*/

		  // **************************************  TENTATIVA 1 ******************************* //
		  // ******************************* Move a tarefa e suas escritas ********************* //
		  
		  // ->
		  ELE[el].vm = m;
		  for(int de_el, ii=0; ii < ELE[el].tes; ii++)
		    {
		      de_el         = ELE[el].es[ii];
		      D_WRITE[ii]   = ELE[de_el].vm;
		      ELE[de_el].vm = data->vm_st_site[msite];
		    }
		  		  
		  // calcula custo do movimento
		  _obj = fobj_bl(data, &_makespam, &_custof, &_ms_part, &_cs_part, 0);
		  
		  if (Depu)
		    {
		      cout<<"       T1 testa t"<<ELE[el].id<<" m"<<vm_el<<" -> m"<<m<<" ESC[";
		      for(int de_el, ii=0; ii < ELE[el].tes; ii++)
			cout<<"d"<<ELE[ELE[el].es[ii]].id<<", ";
		      cout<<"] em m"<<data->vm_st_site[msite]<<"\t ("<<_obj<<")"<<endl;
		    }
		  
		  // teste de inviabilidade 
		  inviavel = 0;							  
		  for ( int ii = 0; ii < _m; ii++ )
		    {
		      // teste de inviabilidade de tempo (o vetor CAP_M_t1 que guarda os mks das maquinas na solução da chamada de fobj_bl)
		      if (CAP_M_t1[ii] > _t_max)
			{
			  inviavel = 1;
			  if (Depu) cout<<"   !!! passou tempo maximo !!! na maq "<<ii<<endl;
			  break; 
			}
		      // teste de inviabilidade de capacidade da maquina (o vetor CAP_M_t2 que guarda o quantidade de dados das maquinas na solução da chamada de fobj_bl)
		      if (CAP_M_t2[m] > data->m_cap[m])
			{
			  inviavel = 1;
			  if (Depu) cout<<"   !!! passou capacidade da maquina !!! na maq "<<ii<<endl;
			  break; 
			}
		    }// for ( int ii = 0; ii < _m; ii++ )

		  if (inviavel == 0)
		    {
		      // achou movimento de melhora, pode retornar
		      if (_obj + data->PRECISAO < f_obj)
			{
			  * makespam = _makespam;
			  * custof   = _custof;
			  * ms_part  = _ms_part;
			  * cs_part  = _cs_part;

			  Depu = 1;
			  if (Depu) cout<<"   T1 move_site) t"<<ELE[el].id<<" m"<<vm_el<<" -> m"<<m<<"\t MKS=" <<_makespam<<"\t CST="<<_custof<<"\t ("<<_obj<<")"<<endl;
			  //if (Depu) imprime_sol(data);
			  return true;
			}
		    }
		  		  
		  // <-
		  ELE[el].vm = vm_el;
		  for(int de_el, ii=0; ii < ELE[el].tes; ii++)
		    {
		      de_el         = ELE[el].es[ii];
		      ELE[de_el].vm = D_WRITE[ii];
		    }
		  
		  /*cout<<"D) ELE[de_el].vm = ";		  
		    for(int de_el, ii=0; ii < ELE[el].tes; ii++)
		    cout<<"d"<<ELE[ELE[el].es[ii]].id<<"->m"<<ELE[ELE[el].es[ii]].vm<<", ";
		    cout<<endl; */


		  if (ELE[el].tle > 0)
		    {
		      // **************************************  TENTATIVA 2 ******************************* //
		      // ******************************* Move a tarefa e suas leituras dinamicas *********** //
		      
		      // ->
		      ELE[el].vm = m;
		      for(int de_el, ii=0; ii < ELE[el].tle; ii++)
		  	{
		  	  de_el         = ELE[el].le[ii];
		  	  D_REEXC[ii]   = ELE[de_el].vm;
		  	  ELE[de_el].vm = data->vm_st_site[msite];
		  	}
		      
		      // calcula custo do movimento
		      _obj = fobj_bl(data, &_makespam, &_custof, &_ms_part, &_cs_part, 0);
		      
		      if (Depu)
		  	{
		  	  cout<<"       T2 testa t"<<ELE[el].id<<" m"<<vm_el<<" -> m"<<m<<" LEI[";
		  	  for(int de_el, ii=0; ii < ELE[el].tle; ii++)
		  	    cout<<"d"<<ELE[ELE[el].le[ii]].id<<", ";
		  	  cout<<"] em m"<<data->vm_st_site[msite]<<"\t ("<<_obj<<")"<<endl;
		  	}
		      
		      // teste de inviabilidade 
		      inviavel = 0;							  
		      for ( int ii = 0; ii < _m; ii++ )
		  	{
		  	  // teste de inviabilidade de tempo (o vetor CAP_M_t1 que guarda os mks das maquinas na solução da chamada de fobj_bl)
		  	  if (CAP_M_t1[ii] > _t_max)
		  	    {
		  	      inviavel = 1;
		  	      if (Depu) cout<<"   !!! passou tempo maximo !!! na maq "<<ii<<endl;
		  	      break; 
		  	    }
		  	  // teste de inviabilidade de capacidade da maquina (o vetor CAP_M_t2 que guarda o quantidade de dados das maquinas na solução da chamada de fobj_bl)
		  	  if (CAP_M_t2[m] > data->m_cap[m])
		  	    {
		  	      inviavel = 1;
		  	      if (Depu) cout<<"   !!! passou capacidade da maquina !!! na maq "<<ii<<endl;
		  	      break; 
		  	    }
		  	}// for ( int ii = 0; ii < _m; ii++ )
		      
		      if (inviavel == 0)
		  	{
		  	  // achou movimento de melhora, pode retornar
		  	  if (_obj + data->PRECISAO < f_obj)
		  	    {
		  	      * makespam = _makespam;
		  	      * custof   = _custof;
		  	      * ms_part  = _ms_part;
		  	      * cs_part  = _cs_part;

		  	      Depu = 1;
		  	      if (Depu) cout<<"   T2 move_site) t"<<ELE[el].id<<" m"<<vm_el<<" -> m"<<m<<"\t MKS=" <<_makespam<<"\t CST="<<_custof<<"\t ("<<_obj<<")"<<endl;
		  	      //if (Depu) imprime_sol(data);
		  	      return true;
		  	    }
		  	}
		      
		      // <-
		      ELE[el].vm = vm_el;
		      for(int de_el, ii=0; ii < ELE[el].tle; ii++)
		  	{
		  	  de_el         = ELE[el].le[ii];
		  	  ELE[de_el].vm = D_REEXC[ii];
		  	}
		      
		      /*cout<<"D) ELE[de_el].vm = ";		  
		  	for(int de_el, ii=0; ii < ELE[el].tes; ii++)
		  	cout<<"d"<<ELE[ELE[el].es[ii]].id<<"->m"<<ELE[ELE[el].es[ii]].vm<<", ";
		  	cout<<endl; */ 

		    }//  if (ELE[el].tle > 0)

		  
		   if (ELE[el].tle > 0)
		     {
		       // **************************************  TENTATIVA 3 ******************************* //
		       // ******************************* Move a tarefa e suas escritas/leituras dinamicas ** //
		       
		       // ->
		       ELE[el].vm = m;
		       for(int de_el, ii=0; ii < ELE[el].tes; ii++)
		  	 {
		  	   de_el         = ELE[el].es[ii];
		  	   D_WRITE[ii]   = ELE[de_el].vm;
		  	   ELE[de_el].vm = data->vm_st_site[msite];
		  	 }
		       for(int de_el, ii=0; ii < ELE[el].tle; ii++)
		  	 {
		  	   de_el         = ELE[el].le[ii];
		  	   D_REEXC[ii]   = ELE[de_el].vm;
		  	   ELE[de_el].vm = data->vm_st_site[msite];
		  	 }
		       
		       // calcula custo do movimento
		       _obj = fobj_bl(data, &_makespam, &_custof, &_ms_part, &_cs_part, 0);
		       
		       if (Depu)
		  	 {
		  	   cout<<"       T3 testa t"<<ELE[el].id<<" m"<<vm_el<<" -> m"<<m<<" ESC[";
		  	   for(int de_el, ii=0; ii < ELE[el].tes; ii++)
		  	     cout<<"d"<<ELE[ELE[el].es[ii]].id<<", ";
		  	   cout<<"] & LEI[";
		  	   for(int de_el, ii=0; ii < ELE[el].tle; ii++)
		  	     cout<<"d"<<ELE[ELE[el].le[ii]].id<<", ";
		  	   cout<<"] em m"<<data->vm_st_site[msite]<<"\t ("<<_obj<<")"<<endl;
		  	 }
		       
		       // teste de inviabilidade 
		       inviavel = 0;							  
		       for ( int ii = 0; ii < _m; ii++ )
		  	 {
		  	   // teste de inviabilidade de tempo (o vetor CAP_M_t1 que guarda os mks das maquinas na solução da chamada de fobj_bl)
		  	   if (CAP_M_t1[ii] > _t_max)
		  	     {
		  	       inviavel = 1;
		  	       if (Depu) cout<<"   !!! passou tempo maximo !!! na maq "<<ii<<endl;
		  	       break; 
		  	     }
		  	   // teste de inviabilidade de capacidade da maquina (o vetor CAP_M_t2 que guarda o quantidade de dados das maquinas na solução da chamada de fobj_bl)
		  	   if (CAP_M_t2[m] > data->m_cap[m])
		  	     {
		  	       inviavel = 1;
		  	       if (Depu) cout<<"   !!! passou capacidade da maquina !!! na maq "<<ii<<endl;
		  	       break; 
		  	     }
		  	 }// for ( int ii = 0; ii < _m; ii++ )
		       
		       if (inviavel == 0)
		  	 {
		  	   // achou movimento de melhora, pode retornar
		  	   if (_obj + data->PRECISAO < f_obj)
		  	     {
		  	       * makespam = _makespam;
		  	       * custof   = _custof;
		  	       * ms_part  = _ms_part;
		  	       * cs_part  = _cs_part;

		  	       Depu = 1;
		  	       if (Depu) cout<<"   T3 move_site) t"<<ELE[el].id<<" m"<<vm_el<<" -> m"<<m<<"\t MKS=" <<_makespam<<"\t CST="<<_custof<<"\t ("<<_obj<<")"<<endl;
		  	       //if (Depu) imprime_sol(data);
		  	       return true;
		  	     }
		  	 }
		       
		       // <-
		       ELE[el].vm = vm_el;
		       for(int de_el, ii=0; ii < ELE[el].tes; ii++)
		  	 {
		  	   de_el         = ELE[el].es[ii];
		  	   ELE[de_el].vm = D_WRITE[ii];
		  	 }
		       for(int de_el, ii=0; ii < ELE[el].tle; ii++)
		  	 {
		  	   de_el         = ELE[el].le[ii];
		  	   ELE[de_el].vm = D_REEXC[ii];
		  	 }
		       
		       /*cout<<"D) ELE[de_el].vm = ";		  
		  	 for(int de_el, ii=0; ii < ELE[el].tes; ii++)
		  	 cout<<"d"<<ELE[ELE[el].es[ii]].id<<"->m"<<ELE[ELE[el].es[ii]].vm<<", ";
		  	 cout<<endl; */

		     }//  if (ELE[el].tle > 0)


		   //   ======================== ESTA ALTERANDO A SOLUÇÃO ========================== ERRO ERRO ERRO 
		  //   if (ELE[el].tle > 0)
		  //    {
		  //      // **************************************  TENTATIVA 4 ******************************* //
		  //      // ******************************* Move a tarefa, suas leituras dinamicas e as tarefas que as geraram ** //
		       
		  //      // ->
		  //      ELE[el].vm = m;
		  //      for(int tpai_el, de_el, ii=0; ii < ELE[el].tle; ii++)
		  // 	 {
		  // 	   // dado de leitura dinamico 
		  // 	   de_el         = ELE[el].le[ii];
		  // 	   D_REEXC[ii]   = ELE[de_el].vm;
		  // 	   ELE[de_el].vm = data->vm_st_site[msite];

		  // 	   // quem gerou o dado
		  // 	   tpai_el         = ELE[de_el].elet;
		  // 	   D_TASK[ii]      = ELE[tpai_el].vm;
		  // 	   ELE[tpai_el].vm = m;
		  // 	 }

		       		       
		  //      // calcula custo do movimento
		  //      _obj = fobj_bl(data, &_makespam, &_custof, &_ms_part, &_cs_part, 0);

		  //      if (Depu)
		  // 	 {
		  // 	   cout<<"       T4 testa t"<<ELE[el].id<<" m"<<vm_el<<" -> m"<<m<<" TASKS[";
		  // 	   for(int de_el, ii=0; ii < ELE[el].tle; ii++)
		  // 	     cout<<"t"<<ELE[ELE[ELE[el].le[ii]].elet].id<<", ";
		  // 	   cout<<"] em m"<<m<<" & LEI[";
		  // 	   for(int de_el, ii=0; ii < ELE[el].tle; ii++)
		  // 	     cout<<"d"<<ELE[ELE[el].le[ii]].id<<", ";
		  // 	   cout<<"] em m"<<data->vm_st_site[msite]<<"\t ("<<_obj<<")"<<endl;
		  // 	 }
		       
		  //      // teste de inviabilidade 
		  //      inviavel = 0;							  
		  //      for ( int ii = 0; ii < _m; ii++ )
		  // 	 {
		  // 	   // teste de inviabilidade de tempo (o vetor CAP_M_t1 que guarda os mks das maquinas na solução da chamada de fobj_bl)
		  // 	   if (CAP_M_t1[ii] > _t_max)
		  // 	     {
		  // 	       inviavel = 1;
		  // 	       if (Depu) cout<<"   !!! passou tempo maximo !!! na maq "<<ii<<endl;
		  // 	       break; 
		  // 	     }
		  // 	   // teste de inviabilidade de capacidade da maquina (o vetor CAP_M_t2 que guarda o quantidade de dados das maquinas na solução da chamada de fobj_bl)
		  // 	   if (CAP_M_t2[m] > data->m_cap[m])
		  // 	     {
		  // 	       inviavel = 1;
		  // 	       if (Depu) cout<<"   !!! passou capacidade da maquina !!! na maq "<<ii<<endl;
		  // 	       break; 
		  // 	     }
		  // 	 }// for ( int ii = 0; ii < _m; ii++ )
		       
		  //      if (inviavel == 0)
		  // 	 {
		  // 	   // achou movimento de melhora, pode retornar
		  // 	   if (_obj + data->PRECISAO < f_obj)
		  // 	     {
		  // 	       * makespam = _makespam;
		  // 	       * custof   = _custof;
		  // 	       * ms_part  = _ms_part;
		  // 	       * cs_part  = _cs_part;

		  // 	       Depu = 1;
		  // 	       if (Depu) cout<<"   T4 move_site) t"<<ELE[el].id<<" m"<<vm_el<<" -> m"<<m<<"\t MKS=" <<_makespam<<"\t CST="<<_custof<<"\t ("<<_obj<<")"<<endl;
		  // 	       //if (Depu) imprime_sol(data);
		  // 	       return true;
		  // 	     }
		  // 	 }
		       
		  //      // <-
		  //      ELE[el].vm = vm_el;
		  //      for(int tpai_el, de_el, ii=0; ii < ELE[el].tle; ii++)
		  // 	 {
		  // 	   //dado 
		  // 	   de_el         = ELE[el].le[ii];
		  // 	   ELE[de_el].vm = D_REEXC[ii];

		  // 	   // tarefa pai
		  // 	   tpai_el         = ELE[de_el].elet;
		  // 	   ELE[tpai_el].vm = D_TASK[ii];
		  // 	 }
		       
		  //      /*cout<<"D) ELE[de_el].vm = ";		  
		  // 	 for(int de_el, ii=0; ii < ELE[el].tes; ii++)
		  // 	 cout<<"d"<<ELE[ELE[el].es[ii]].id<<"->m"<<ELE[ELE[el].es[ii]].vm<<", ";
		  // 	 cout<<endl; */

		  //    }//  if (ELE[el].tle > 0)
		  
		   
		}//if (data->m_storage[m] == 1)
	      
	    }// if (site_el != data->m_site[m])
	
      }//for (int i=0; i<num_ELE; i++)
  
  return false;
}









/* vizinhanca que tenta trocar a maquina de 2 elementos (dado ou tarefa) */
bool BDHeuri::switch_m_bl(Data* data, double f_obj, int* makespam, double* custof, double* ms_part, double* cs_part, int Depu)
{
  int      vm_el1, vm_el2;
  int      _makespam;
  double   _obj, _custof, _ms_part, _cs_part;

  if (Depu) cout<<"---------------------- switch_m_bl --------------------------"<<endl;
  
  for (int el1=0; el1<num_ELE-1; el1++)
    for (int el2=el1+1; el2<num_ELE; el2++)
      {
	/* VM do elemento 1 e 2 */
	vm_el1 = ELE[el1].vm;
	vm_el2 = ELE[el2].vm;

	/* configurações invalidas */
	if (  ((ELE[el1].ty == 0) and (data->m_storage[vm_el2] == 0))   or
	      ((ELE[el2].ty == 0) and (data->m_storage[vm_el1] == 0))   or
	      ((ELE[el1].ty == 1) and (data->m_storage[vm_el2] == 1))   or
	      ((ELE[el2].ty == 1) and (data->m_storage[vm_el1] == 1))   )
	  continue;

	//cout<<"ele1: t)"<<ELE[el1].ty<<" str) "<<data->m_storage[vm_el1]<<" ele2: t)"<<ELE[el2].ty<<" str) "<<data->m_storage[vm_el2]<<endl;
	
	if (vm_el1 != vm_el2)
	  {
	    // ->
	    ELE[el1].vm = vm_el2;
	    ELE[el2].vm = vm_el1;
		
	    // calcula custo do movimento
	    _obj = fobj_bl(data, &_makespam, &_custof, &_ms_part, &_cs_part, 0);
		
	    if ((ELE[el1].ty == 0) and (ELE[el2].ty == 0)) {if (Depu) cout<<"troca vm de t"<<ELE[el1].id<<"(m"<<vm_el1<<") e t"<<ELE[el2].id<<"(m"<<vm_el2<<") -> ("<<_obj<<")"<<endl;}
	    else if ((ELE[el1].ty == 0) and (ELE[el2].ty == 1)) {if (Depu) cout<<"troca vm de t"<<ELE[el1].id<<"(m"<<vm_el1<<") e d"<<ELE[el2].id<<"(m"<<vm_el2<<") -> ("<<_obj<<")"<<endl;}
	    else if ((ELE[el1].ty == 1) and (ELE[el2].ty == 0)) {if (Depu) cout<<"troca vm de d"<<ELE[el1].id<<"(m"<<vm_el1<<") e t"<<ELE[el2].id<<"(m"<<vm_el2<<") -> ("<<_obj<<")"<<endl;}
	    else if ((ELE[el1].ty == 1) and (ELE[el2].ty == 1)) {if (Depu) cout<<"troca vm de d"<<ELE[el1].id<<"(m"<<vm_el1<<") e d"<<ELE[el2].id<<"(m"<<vm_el2<<") -> ("<<_obj<<")"<<endl;}

	    // teste de inviabilidade de tempo (o vetor CAP_M_t1 que guarda os mks das maquinas na solução da chamada de fobj_bl)
	    if ((CAP_M_t1[vm_el1] > _t_max) or ((CAP_M_t1[vm_el2] > _t_max)))
		{
		  if (Depu) cout<<"   !!! passou tempo maximo !!!"<<endl;
		}
	      else
		{
		  // teste de inviabilidade de capacidade da maquina (o vetor CAP_M_t2 que guarda o quantidade de dados das maquinas na solução da chamada de fobj_bl)
		  if ((CAP_M_t2[vm_el1] > data->m_cap[vm_el1]) or (CAP_M_t2[vm_el2] > data->m_cap[vm_el2]))
		    {
		      if (Depu) cout<<"   !!! passou capacidade da maquina !!!"<<endl;
		    }
		  else
		    {
		      // achou movimento de melhora, pode retornar
		      if (_obj + data->PRECISAO < f_obj)
			{
			  * makespam = _makespam;
			  * custof   = _custof;
			  * ms_part  = _ms_part;
			  * cs_part  = _cs_part;

			  Depu=1;
			  if ((ELE[el1].ty == 0) and (ELE[el2].ty == 0)) {if (Depu) cout<<"   switch_m)  t"<<ELE[el1].id<<"(m"<<vm_el1<<") e t"<<ELE[el2].id<<"(m"<<vm_el2<<")\t MKS="<<_makespam<<"\t CST="<<_custof<<"\t ("<<_obj<<")"<<endl;}
			  else if ((ELE[el1].ty == 0) and (ELE[el2].ty == 1)) {if (Depu) cout<<"   switch_m)  t"<<ELE[el1].id<<"(m"<<vm_el1<<") e d"<<ELE[el2].id<<"(m"<<vm_el2<<")\t MKS="<<_makespam<<"\t CST="<<_custof<<"\t ("<<_obj<<")"<<endl;}
			  else if ((ELE[el1].ty == 1) and (ELE[el2].ty == 0)) {if (Depu) cout<<"   switch_m)  d"<<ELE[el1].id<<"(m"<<vm_el1<<") e t"<<ELE[el2].id<<"(m"<<vm_el2<<")\t MKS="<<_makespam<<"\t CST="<<_custof<<"\t ("<<_obj<<")"<<endl;}
			  else if ((ELE[el1].ty == 1) and (ELE[el2].ty == 1)) {if (Depu) cout<<"   switch_m)  d"<<ELE[el1].id<<"(m"<<vm_el1<<") e d"<<ELE[el2].id<<"(m"<<vm_el2<<")\t MKS="<<_makespam<<"\t CST="<<_custof<<"\t ("<<_obj<<")"<<endl;}
			  //if (Depu) imprime_sol(data);
		    
			  return true;
			}

		    }//else
		}//else
		
	    // <-
	    ELE[el1].vm = vm_el1;
	    ELE[el2].vm = vm_el2;
	    
	  }// if (((ELE[el1].ty == 1) || (data->m_storage[vm_el2] == 1)) && ((ELE[el2].ty == 1) || (data->m_storage[vm_el1] == 1)) && (vm_el1 != vm_el2))
	
      }// for (int el1=0; el1<num_ELE-1; el1++) for (int el2=el+1; el2<num_ELE; el2++)
  
  return false;
}





/* vizinhanca que tenta trocar a ordem das tarefas que podem ser executadas em paralelo  */
bool BDHeuri::switch_t_bl(Data* data, double f_obj, int* makespam, double* custof, double* ms_part, double* cs_part, int Depu)
{
  int      _makespam;
  double   _obj, _custof, _ms_part, _cs_part;
  bool     eh_pred;

  if (Depu) cout<<"---------------------- switch_t_bl --------------------------"<<endl;
  
  for(int el_t, id_t, cp_t, ord=0; ord < num_ORDER_T-1; ord++)
    {
      /* id e copia da tarefa */
      id_t = ORDER_T[ord].id;
      cp_t = ORDER_T[ord].cp;
      el_t = ORDER_T[ord].ele;
      //if (Depu) cout<<"t"<<id_t<<"("<<cp_t<<") vm="<<ELE[el_t].vm<<endl;

      for(int el_t2, id_t2, cp_t2, ord2=ord+1; ord2 < num_ORDER_T; ord2++)
	{
	  /* id e copia da tarefa */
	  id_t2 = ORDER_T[ord2].id;
	  cp_t2 = ORDER_T[ord2].cp;
	  el_t2 = ORDER_T[ord2].ele;
	  //if (Depu) cout<<"   t"<<id_t2<<"("<<cp_t2<<") vm="<<ELE[el_t2].vm<<endl;
	  
	  if (data-> SUCESS[id_t][id_t2] == 1)
	    {
	      //if (Depu) cout<<"   "<<id_t2<<" É SUCESSORA DE "<<id_t<<", PAROU"<<endl;
	      break;
	    }

	  eh_pred = false;
	  for(int el_t3, id_t3, cp_t3, ord3=ord2-1; ord3 > ord; ord3--)
	    {
	      /* id e copia da tarefa */
	      id_t3 = ORDER_T[ord3].id;
	      cp_t3 = ORDER_T[ord3].cp;
	      el_t3 = ORDER_T[ord3].ele;
	      //if (Depu) cout<<"      t"<<id_t3<<"("<<cp_t3<<") vm="<<ELE[el_t3].vm<<endl;
	      
	      if (data-> PREDEC[id_t2][id_t3] == 1)
		{
		  eh_pred = true;
		  //if (Depu) cout<<"      "<<id_t3<<" É PREDECESSORA DE "<<id_t2<<", PAROU"<<endl;
		  break;
		}
	      
	    }//for(int el_t3, id_t3, cp_t3, ord3=ord2-1; ord3 > ord; ord3--)

	  if (!eh_pred)
	    {
	      // ->
	      ORDER_T[ord].id    = id_t2; ORDER_T[ord].cp    = cp_t2; ORDER_T[ord].ele   = el_t2;
	      ORDER_T[ord2].id   = id_t;  ORDER_T[ord2].cp   = cp_t;  ORDER_T[ord2].ele  = el_t;

	      // calcula custo do movimento
	      _obj = fobj_bl(data, &_makespam, &_custof, &_ms_part, &_cs_part, Depu);
	      if (Depu) cout<<"--- tenta trocar t"<<id_t<<"("<<cp_t<<") <-> t"<<id_t2<<"(" <<cp_t2<<")\t MKS ="<<_makespam<<"\t CST ="<<_custof<<"\t ("<<_obj<<")"<<endl;
	      
	       // achou movimento de melhora, pode retornar
	      if (_obj + data->PRECISAO < f_obj)
		{
		  * makespam = _makespam;
		  * custof   = _custof;
		  * ms_part  = _ms_part;
		  * cs_part  = _cs_part;
		  if (Depu) cout<<"   switch_t) t"<<id_t<<"("<<cp_t<<") <-> t"<<id_t2<<"(" <<cp_t2<<")\t MKS ="<<_makespam<<"\t CST ="<<_custof<<"\t ("<<_obj<<")"<<endl;

		  return true;
		}
	      
	      // <-
	      ORDER_T[ord].id    = id_t;  ORDER_T[ord].cp    = cp_t;  ORDER_T[ord].ele   = el_t;
	      ORDER_T[ord2].id   = id_t2; ORDER_T[ord2].cp   = cp_t2; ORDER_T[ord2].ele  = el_t2;
	      
	    }//if (!eh_pred)

	}//for(int el_t2, id_t2, cp_t2, ord2=ord+1; ord2 < num_ORDER_T; ord2++)

    }//for(int el_t, id_t, cp_t, ord=0; ord < num_ORDER_T-1; ord++)

  return false;
}



/* busca local */
double BDHeuri::bl(Data* data, int* makespam, double* custof, double* ms_part, double* cs_part, int Maxtime)
{
  int      _makespam;
  double   _custof, _ms_part, _cs_part, f_obj;
  bool     para;
  int      aDepu=data->DEPU;

  // Parametros
  int      ini_num_zero = 3;
  int      num_zero;

  /* vizinhancas */
  bool     move_t_m  = false;   // move tarefa para maquina diferente
  bool     move_d_m  = false;   // move o dado para uma maquina diferente
  bool     switch_m  = false;  // troca a maquina de dois elementos (tarefa ou dado)
  bool     switch_t  = false;  // troca a ordem de tarefas na execucao 
  bool     move_2t_m = false;  // move 2 tarefas da mesma maquina para maquinas diferentes
  bool     move_s    = false;  // move o conjunto (dado leit, tarefa, dado esc) para outra maquina em outro site

  // quais vizinhanças estão ativas (maiores que 50 tasks, drop the swicth)
  if (data->n <= 50)
    {
      move_t_m  = true;   
      move_d_m  = true;
      switch_m  = true;
      switch_t  = true;
      //move_2t_m = true;
      //move_s    = true;
    }
  else
    {
      move_t_m  = true;   
      move_d_m  = true;
    }

  // solucao do construtivo
  //imprime_sol(data);

  // carrega solucao na estrutura da busca local 
  TL_struct_bl(data);

  // imprime estrutura da busca local 
  if (aDepu) imprime_struct_bl(data);

  // f.o.
  f_obj = fobj_bl(data, &_makespam, &_custof, &_ms_part, &_cs_part, aDepu);
  * makespam = _makespam; * custof   = _custof; * ms_part  = _ms_part; * cs_part  = _cs_part;
  if (aDepu) cout<<"constr)  MKS="<<_makespam<<"\t CST="<<_custof<<"\t ("<<f_obj<<")"<<endl;
  //if (aDepu) imprime_sol(data);
  
  // solucao da busca local
  //imprime_sol(data);

  if (aDepu) cout<<"*********** BUSCA LOCAL **********"<<endl;
  para     = false;
  num_zero = ini_num_zero;
  while (!para)
    {
      // parada por tempo
      if (((double)clock() - (double)start_h) / CLOCKS_PER_SEC >  Maxtime)
	{
	  cout<<"** limite de tempo ** "<<endl;
	  para = true;
	  continue;
	}
	      
      if (move_t_m)
	//move o elemento para uma VM diferente
	if (move_t_m_bl(data, f_obj,  &_makespam, &_custof, &_ms_part, &_cs_part, aDepu))
	  {
	    f_obj = _ms_part + _cs_part;
	    
	    * makespam = _makespam; * custof   = _custof; * ms_part  = _ms_part; * cs_part  = _cs_part;
	    cout<<"             move_T_m    ms="<<_makespam<<" cst="<<_custof<<endl;
	    num_zero   = ini_num_zero;
	    continue;
	  }

      if (move_d_m)
	//move o elemento para uma VM diferente
	if (move_d_m_bl(data, f_obj,  &_makespam, &_custof, &_ms_part, &_cs_part, aDepu))
	  {
	    f_obj = _ms_part + _cs_part;
	    
	    * makespam = _makespam; * custof   = _custof; * ms_part  = _ms_part; * cs_part  = _cs_part;
	    cout<<"             move_D_m    ms="<<_makespam<<" cst="<<_custof<<endl; 
	    num_zero   = ini_num_zero;
	    continue;
	  }

      if (move_s)
	//move par tarefa/escrita para site diferente
	if (move_exec_esc_site_bl(data, f_obj,  &_makespam, &_custof, &_ms_part, &_cs_part, aDepu))
	  {
	    f_obj = _ms_part + _cs_part;
	    
	    * makespam = _makespam; * custof   = _custof; * ms_part  = _ms_part; * cs_part  = _cs_part;
	    cout<<"             move_s    ms="<<_makespam<<" cst="<<_custof<<endl;
	    num_zero   = ini_num_zero;
	    continue;
	  }
          
      if (switch_m)
	//troca as VMs de dois elementos diferentes
	if (switch_m_bl(data, f_obj,  &_makespam, &_custof, &_ms_part, &_cs_part, aDepu))
	  {
	    f_obj = _ms_part + _cs_part;
	    
	    * makespam = _makespam; * custof   = _custof; * ms_part  = _ms_part; * cs_part  = _cs_part;
	    cout<<"             swim_m    ms="<<_makespam<<" cst="<<_custof<<endl;
	    num_zero   = ini_num_zero;
	    continue;
	  }

      if (switch_t)
	//troca a ordem de duas tarefas que podem ser executadas em paralelo
	if (switch_t_bl(data, f_obj,  &_makespam, &_custof, &_ms_part, &_cs_part, aDepu))
	  {
	    f_obj = _ms_part + _cs_part;
	    //if (aDepu) imprime_struct_bl(data);
	    //if (aDepu) imprime_sol(data);
	    
	    * makespam = _makespam; * custof   = _custof; * ms_part  = _ms_part; * cs_part  = _cs_part;
	    cout<<"            SWITCH_T    ms="<<_makespam<<" cst="<<_custof<<endl;
	    num_zero   = ini_num_zero;
	    continue;
	  }

      if (move_2t_m)
	//move o elemento para uma VM diferente
	if (move_2t_m_bl(data, f_obj,  &_makespam, &_custof, &_ms_part, &_cs_part, aDepu))
	  {
	    f_obj = _ms_part + _cs_part;
	    
	    * makespam = _makespam; * custof   = _custof; * ms_part  = _ms_part; * cs_part  = _cs_part;
	    cout<<"             MOVE_2T_m    ms="<<_makespam<<" cst="<<_custof<<endl;
	    num_zero   = ini_num_zero;
	    continue;
	  }

      //movimentos de custo zero
      if (num_zero > 0)
	{
	  zero_cost_move(data, f_obj,  &_makespam, &_custof, &_ms_part, &_cs_part, aDepu);
	  cout<<"                ZERO_m("<<num_zero<<")"<<endl;
	      
	  num_zero--;
	  continue;
	}

      // condicao de parada
      para = true;
	
    }// while (para)

  // chama mais uma vez a f.o. para carregar as estruturas da time line TL e poder salvar/imprimir
  f_obj = fobj_bl(data, &_makespam, &_custof, &_ms_part, &_cs_part, 1);

 return (* ms_part + * cs_part);
}


// ao carregar a solução do construtivo na estrutura da busca local (explicada no trabalho do Luan)
// pequenas inconsistencias sao corrigidas
double BDHeuri::corrige_inconsistencia_com_struct_bl(Data* data, char * instance, int* makespam, double* custof, double* ms_part, double* cs_part)
{
  int      _makespam;
  double   _custof, _ms_part, _cs_part;
  
  // carrega estruturas da busca local a partir da estruturas do construtivo

  // solucao do construtivo
  //imprime_sol(data);

  // carrega solucao na estrutura da busca local 
  TL_struct_bl(data);

  // imprime estrutura da busca local 
  //imprime_struct_bl(data);

  // f.o.
  fobj_bl(data, &_makespam, &_custof, &_ms_part, &_cs_part, 1);

  //if ((* makespam != _makespam) || (* custof != _custof)) { cout<<instance<<" **ERRO ERRO *CORRI_INC*  ERRO** MS "<<* makespam<<" != "<<_makespam<<" e CST "<<* custof<<" != "<<_custof<<endl; abort();}

  // solucao da busca local
  //imprime_sol(data);

  //abort();

  * makespam = _makespam;
  * custof   = _custof;
  * ms_part  = _ms_part;
  * cs_part  = _cs_part;

  return (* ms_part + * cs_part);
}


/********************************************************************************************/
/**** funcoes para calculo da altura da tarefa (paper do Luan), mas não estou usando ********/
/*******************************************************************************************/


// calcula a altura inicial das tarefas na ordem de tarefas
void BDHeuri::calcula_altura_i_tarefas_ordem(Data* data, int ord)
{
  int   ord_pred, el_pred, el_t, id_t, max_alt_pred, pred_alt;
  bool  tem_pred;

  // id da tarefa 
  id_t = ORDER_T[ord].id;
  el_t = ORDER_T[ord].ele;
 
  // percorre tarefas predecessores
  max_alt_pred = 0; tem_pred=false;
  for (int i=0; i<ELE[el_t].tpred; i++)
    {
      // tem predecessor na ordem
      tem_pred=true;
      
      el_pred  = ELE[el_t].pred[i];
      ord_pred = ELE[el_pred].ord;

      // altura inicial do predecessor ainda nao foi calculada
      if (altura_i_order[ord_pred] == -1)
	calcula_altura_i_tarefas_ordem(data, ord_pred);

      // altura inicial do predecessor (ja calculada)
      pred_alt = altura_i_order[ord_pred];
	      
      if (max_alt_pred < pred_alt)
	max_alt_pred = pred_alt;
    }

  // determina altura inicial
  if (tem_pred)
    altura_i_order[ord] = max_alt_pred + 1;
  else
    altura_i_order[ord] = 0;
}



// calcula a altura final das tarefas na ordem de tarefas
void BDHeuri::calcula_altura_f_tarefas_ordem(Data* data, int ord)
{
  int   ord_suc, el_suc, id_t, el_t, min_alt_suc, suc_alt, sorteio;
  bool  tem_suc;

  // id da tarefa 
  id_t = ORDER_T[ord].id;
  el_t = ORDER_T[ord].ele;
  //cout<<"      t"<<id_t<<"("<<ORDER_T[ord].cp<<")"<<endl;

  // percorre sucessores
  min_alt_suc = (_n*_m)+1; tem_suc=false;
  //cout<<"     min_alt_suc  = "<< min_alt_suc<<endl;

  for (int i=0; i<ELE[el_t].tsuc; i++)
    {
      // tem predecessor na ordem
      tem_suc=true;

      el_suc  = ELE[el_t].suc[i];
      ord_suc = ELE[el_suc].ord;
      	      
      // altura do sucessor  ainda nao foi calculada
      if (altura_order[ord_suc] == -1)
	calcula_altura_f_tarefas_ordem(data, ord_suc);

      // altura do sucessor (ja calculada)
      suc_alt = altura_order[ord_suc];
      //cout<<"         suc"<<ORDER_T[suc_ord].id<<"("<<ORDER_T[suc_ord].cp<<") altura = "<<suc_alt<<endl;
	      
      if (min_alt_suc > suc_alt)
	min_alt_suc = suc_alt;
    }
  //cout<<"      t"<<id_t<<"("<<ORDER_T[ord].cp<<") min_alt_suc = "<<min_alt_suc<<endl;

  // determina altura 
  if (tem_suc)
    {
      sorteio            = (int) (rand() % ((min_alt_suc-1) - altura_i_order[ord] + 1)) + altura_i_order[ord]; 
      altura_order[ord]  = sorteio;
      cout<<"t"<<id_t<<"("<<ORDER_T[ord].cp<<")\t h=["<<altura_i_order[ord]<<","<<(min_alt_suc-1)<<"]\t escolheu="<<sorteio<<endl;
    }
  else
    {
      altura_order[ord] = altura_i_order[ord];
      cout<<"t"<<id_t<<"("<<ORDER_T[ord].cp<<")\t h="<<altura_i_order[ord]<<endl;
    }
}


// calcula a altura inicial das tarefas na ordem de tarefas
void BDHeuri::calcula_altura_ordem(Data* data, int Depu)
{
  // inicializa
  for(int ord=0; ord < num_ORDER_T; ord++)
    {
      altura_i_order[ord] = -1;
      altura_order[ord]   = -1;
    }

  // calcula altura inicial
  for(int ord=0; ord < num_ORDER_T; ord++)
    if (altura_i_order[ord] == -1)
      calcula_altura_i_tarefas_ordem(data, ord);

  if (Depu) {cout<<"altura_i = "; for(int i=0; i < num_ORDER_T; i++) {cout<<"t"<<ORDER_T[i].id<<"("<<ORDER_T[i].cp<<")="<<altura_i_order[i]<<", ";} cout<<endl;}

  // calcula altura final
  for(int ord=0; ord < num_ORDER_T; ord++)
    if (altura_order[ord] == -1)
      calcula_altura_f_tarefas_ordem(data, ord);

  if (Depu) {cout<<"altura = "; for(int i=0; i < num_ORDER_T; i++) {cout<<"t"<<ORDER_T[i].id<<"("<<ORDER_T[i].cp<<")="<<altura_order[i]<<", ";} cout<<endl;}
  
}