/*-------------------------------------------------------------------------------
F|permut|max(Ci)  Utemezesi fedadat megoldasa véletlenszerűen kereső algoritmus alkalmazásával.
Többgépes egyutas előzés nélküli termelésiütemezési feladat.
Az ütemezés célja a legkésőbbi befejezési időpont minimalizálása, 
ezáltal a teljes rendeléscsoport átfutási idejének minimalizálása.
Összehasonlítás a CDS-algoritmussal.
A keresési módszer lassabb de jobb közelítést ad.
-------------------------------------------------------------------------------*/

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>

typedef struct{
                long id,
                     * SetT,
                     * ProcT,
                     * OptT,
                     * StartT,
                     * EndT;
              }T_JOB;


long simulation(int* S, T_JOB* job, int n, int m, long ref_T);
void job_print(int* Sch, T_JOB* job, int n, int m);
void sim_data_print(int* Sch, T_JOB* job, int n, int m);
void Johnson_ald(int* Sch, T_JOB* job, int n, int x, int y );

void copy(int* s, int* d, int n);
void neigbour( int* S_inic, int* S, int n);
void random_search(int* S, T_JOB* job, int n, int m, int STEP, int LOOP);


int main(int argc, char* argv[])
{
 T_JOB* job;
 int n; //jobok darabszama
 int m; //gepek szama
 int i; //job futoindex
 int j; //gepek futoindex
 int * Sch; //utemterv
 int *r;  //rendezes Johnson alg. elott
 int x, y; //elso masodik Johnson
 long Cmax; //maximalis befejezesi ido
 long Cbest; //kereses soran legjobb celfv ertek
 int *Sch_best; //kereses soran talalt legjobb megoldas
 //virtualis adatbazis lekerdeze
 randomize();
 printf("\n Kerem a jobok szamat:");
 scanf("%d", &n); //n erteket kap bill-rol

 printf("\n Kerem a gepek szamat:");
 scanf("%d", &m); //m erteket kap bill-rol

 job = (T_JOB*) calloc(n, sizeof(T_JOB) );
 randomize();
 for (i=0; i<n; i++)
 {
  job[i].id = i;
  job[i].SetT = (long*) calloc(m, sizeof(long));
  job[i].ProcT = (long*) calloc(m, sizeof(long));
  job[i].OptT = (long*) calloc(m, sizeof(long));
  job[i].StartT = (long*) calloc(m, sizeof(long));
  job[i].EndT = (long*) calloc(m, sizeof(long));

  for (j=0; j<m; j++)
    {
     job[i].SetT[j] = random (10) + 10;
     job[i].ProcT[j] = random (100) + 10;
     job[i].OptT[j] = job[i].SetT[j] + job[i].ProcT[j];
     }
  }

  Sch = (int*) calloc(n, sizeof(int));
  for (i=0; i<n; i++)
    Sch[i]=i;

  Sch_best = (int*) calloc(n, sizeof(int));

  //CDS
  for (j=0; j<m-1; j++) //0-1  1-2 ...(m-1)-m
  {
   Johnson_ald(Sch, job, n, j, j+1 );
   Cmax = simulation(Sch, job, n, m, 0);
   //printf("\n %d. megoldas: \n \t Cmax=%ld",j, Cmax);

   if (j==0)
     {
      Cbest = Cmax;
       for(i=0; i<n; i++)
          Sch_best[i]=Sch[i];

     }
   else
     {
      if ( Cbest > Cmax )
       {
         Cbest = Cmax;
         for(i=0; i<n; i++)
            Sch_best[i]=Sch[i];

       }
     }
  }
  for(i=0; i<n; i++)
     Sch[i]=Sch_best[i];
  //kiindulasi adatok
  //job_print(Sch, job, n, m);
  //szimulacio
  Cmax = simulation(Sch, job, n, m, 0);
  printf("\n \n \t CDS heurisztika eredmenye: Cmax=%ld", Cmax);
  //eredmeny
  //sim_data_print(Sch, job, n, m);

    //random kereses
  random_search(Sch, job, n, m, 100, 500);
  Cmax = simulation(Sch, job, n, m, 0);
  printf("\n \n \t Kereses eredmenye: Cmax=%ld", Cmax);


 for (i=0; i<n; i++)
  {
   free( job[i].SetT );
   free( job[i].ProcT );
   free( job[i].OptT );
   free( job[i].StartT );
   free( job[i].EndT );
  }
  free( job );
  free( Sch );
  free( Sch_best );


 getch();
 return 1;
}

void random_search(int* S, T_JOB* job, int n, int m, int STEP, int LOOP)
{
 int step, loop;
 long g, g_best, g_n_best;
 int* S_best;
 int* S_n_best;
 int* S_inic;

 S_best = (int*) calloc(n, sizeof(int));
 S_n_best = (int*) calloc(n, sizeof(int));
 S_inic = (int*) calloc(n, sizeof(int));

 copy( S, S_inic, n); //kezdo
 g = simulation(S_inic, job, n, m, 0);
 copy( S_inic, S_best, n ); //legjobb
 g_best = g;

 for (step=0; step<STEP; step++)
 {
   for (loop=0; loop<LOOP; loop++)
   {
   //kepezzunk szomszedot
   neigbour( S_inic, S, n);
   g = simulation(S, job, n, m, 0);
   //printf("\n %d. megoldas: \n \t Cmax=%ld",j, Cmax);

   if (loop==0)
     {
      g_n_best = g;
      copy(S, S_n_best, n);
     }
   else
      if ( g_n_best > g )
       {
         g_n_best = g;
         copy(S, S_n_best, n);
       }
   }//loop
   copy( S_n_best, S_inic, n);

   if (g_best > g_n_best)
   {
    g_best = g_n_best;
    copy( S_n_best, S_best, n);
   }
  } //step

    copy(S_best, S, n);

 free( S_best);
 free( S_n_best);
 free( S_inic);
}

void neigbour( int* S_inic, int* S, int n)
{
 int d;
 int temp;
 copy(S_inic, S, n);
 d = random(n);
 if ( d==0 )
   {
     temp = S[n-1];
     S[n-1] = S[d];
     S[d] = temp;
   }
 else
   {
     temp = S[d-1];
     S[d-1] = S[d];
     S[d] = temp;

   }
}


void copy(int* s, int* d, int n)
{
  int i;
  for (i=0; i<n; i++)
    d[i]=s[i];
}


long simulation(int* S, T_JOB* job, int n, int m, long ref_T)
{ //n munka m gepen sch sorrendben
  int i, j;

  for ( i=0; i<n; i++ )
   for ( j= 0; j<m; j++ )
   {
    if ( i == 0 )
    {
      if ( j == 0 )
      {
       job[S[i]].StartT[j] = ref_T;
      }
      else
      { //kezdo munka nem kezdo gepen
        job[S[i]].StartT[j] = job[S[i]].EndT[j-1];
      }
    }
    else //nem kezdo munka
    {
      if (m==0)
      { //kezdo gep
         job[S[i]].StartT[j] = job[S[i-1]].EndT[j];
      }
      else
      { //nem kezdo gep               //elozo gepen          //elozo munka
         job[S[i]].StartT[j] = max( job[S[i]].EndT[j-1] , job[S[i-1]].EndT[j] );

      }
    }//if i
    job[S[i]].EndT[j] = job[S[i]].StartT[j]
                           + job[S[i]].OptT[j];

   }//for
  return job[S[n-1]].EndT[m-1];
}

void job_print(int* Sch, T_JOB* job, int n, int m)
{
 int i, j;
 printf("\n Idoadatok:\n");
 for (j=0; j<m; j++)
  {
   printf("\n %d_Operacio:", j);

   for (i=0; i<n; i++ )
   {
    printf("\n \t jobid=%d \t %ld", Sch[i], job[Sch[i]].OptT[j]);
   }
  }
}

void sim_data_print(int* Sch, T_JOB* job, int n, int m)
{
 int i, j;
 printf("\n Idoadatok:\n");
 for (j=0; j<m; j++)
  {
   printf("\n %d_Operacio:", j);

   for (i=0; i<n; i++ )
   {
    printf("\n \t %d \t %ld \t %ld \t %ld", Sch[i], job[Sch[i]].OptT[j], job[Sch[i]].StartT[j], job[Sch[i]].EndT[j]);
   }
  }
}

void Johnson_ald(int* Sch, T_JOB* job, int n, int x, int y )
{
 int i, j, temp;
 int b, l;
 long ti, tj;
 int *r = (int *) calloc(n, sizeof(int));
 for (i=0; i<n; i++)
   r[i] = Sch[i];

 for (i=0; i<n-1; i++)
   for (j=i+1; j<n; j++ )
   {
    ti = min( job[r[i]].OptT[x], job[r[i]].OptT[y] );
    tj = min( job[r[j]].OptT[x], job[r[j]].OptT[y] );
    if ( ti > tj)
     {
      temp = r[i];
      r[i] = r[j];
      r[j] = temp;
     }

   }

   b=0;
   l=n-1;  //korrekcio!!!!

   for(i=0; i<n; i++)
    if ( job[r[i]].OptT[x] < job[r[i]].OptT[y])
     {
      Sch[b]=r[i];
      b++;
     }
    else
    {
     Sch[l]=r[i];
     l--;
    }


 free(r);
}