/*
  F|perm|Cmax ütemezési feladat heurisztikus megoldasa.
  Egyutas előzésnélküli, többoperációs termelésütemezési feladat.
  Szimuláció.
    A Simulation_FS adott műveleti idők és adott indítási sorrend esetében
    kiszámítja az operációk indítási és befejezési időpontjait.

  Speciális eset:
  F2|perm|Cmax Ütemezési fedadat megoldása Johnson-algoritmussal.
  A Johnson_alg fv optimális megoldást eredményez (két gép esetében).

  Továbbfejlesztett modell:
  F|permut|max(Ci) Utemezesi fedadat megoldasa véletlenszerűen kereső algoritmus alkalmazásával.
  Lokális kereső algoritmus demo.
    
*/

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

#define NObjF 1

typedef struct {
                int id;       //azonosito
                long* ProcT;  //muveleti idok
                long* StartT; //muvelet inditas
                long* EndT;   //muvelet befejezese

               } T_JOB; //type of job

void Simulation_FS(T_JOB* job, int NJ, int NM, int* s, long t_ref);
void Print_Job_Gantt(T_JOB* job, int NJ, int NM, int* s);
void Evaluation(T_JOB* job, int NJ, int NM, int* s, double* ObjF);
void Print_ObjF(double* ObjF);
void Johnson_alg(T_JOB* job, int NJ, int NM, int* s, int m1, int m2);
int Search(T_JOB* job, int NJ, int NM, int* s, long t_ref,
            int LOOP, int STEP, int key
            );
void copy_sch(int* s, int* t, int NJ );
void Neighbour( int* s0, int* sk, int NJ );


int main(int argc, char* argv[])
{
  int NJ;     //number of jobs, munkak szama
  int NM;     //number of machine, gepek szama
  int i, m;   //futoindex
  T_JOB* job;  //munkak adatai
  int* sch;    //schedule, utemterv
  long t_ref;  //folyamat inditasanak idopontja
  double* ObjF; //objective function, celfuggveny
  int STEP, LOOP; //kereses parameterei
  int bs;

  ObjF = (double*) calloc(NObjF, sizeof(double) ); //vektor

  randomize();
  printf("\n F|perm|Cmax utemezesi feladat demo!");
  printf("\n Munkak szama:");
  scanf("%d", &NJ);

  printf("\n Gepek szama:");
  scanf("%d", &NM);

  printf("\n Inditas idopontja: (pl. 5)");
  scanf("%ld", &t_ref);


  //Modellepeites
  job = (T_JOB*) calloc(NJ, sizeof(T_JOB) ); //strukturavektor

  for( i=0; i<NJ; i++)
   {
      job[i].id = i;
      job[i].ProcT  = (long*) calloc(NM, sizeof(long) ); //vektor
      job[i].StartT = (long*) calloc(NM, sizeof(long) ); //vektor
      job[i].EndT   = (long*) calloc(NM, sizeof(long) ); //vektor

      //CAPP-bol lekerdezett idoadatok
      for( m=0; m<NM; m++)
        job[i].ProcT[m] = 1 + rand()%20;  //muveleti ido erteke indoegysegben
   }


  sch = (int*) calloc(NJ, sizeof(int) ); //vektor
  //ad-hoc sorrenddel inicializalva
  for( i=0; i<NJ; i++)
      sch[i] = i;

  printf("\n Ad-hoc sorrend:");
  //szimulacio
  Simulation_FS(job, NJ, NM, sch, t_ref);
  //Print_Job_Gantt(job, NJ, NM, sch);

  //kiertekeles
  Evaluation(job, NJ, NM, sch, ObjF);
  Print_ObjF(ObjF);


 /*
 if ( NM >= 2 )
  {
   printf("\n Johnson sorrend a 0. es 1. gepre alapozva:");
   Johnson_alg(job, NJ, NM, sch, 0, 1);
   Simulation_FS(job, NJ, NM, sch, t_ref);
   //Print_Job_Gantt(job, NJ, NM, sch);
   Evaluation(job, NJ, NM, sch, ObjF);
   Print_ObjF(ObjF);
  }
 */
  getch();

  printf("\n Kereso algoritmus demo");
  printf("\n STEP = ");
  scanf("%d", &STEP);

  printf("\n LOOP = ");
  scanf("%d", &LOOP);

  bs = Search( job, NJ, NM, sch, t_ref, LOOP, STEP, 0 );
  Simulation_FS(job, NJ, NM, sch, t_ref);
   //Print_Job_Gantt(job, NJ, NM, sch);
 Evaluation(job, NJ, NM, sch, ObjF);
 Print_ObjF(ObjF);
 printf("\n Legjobb lepes: %d", bs);

  getch();



  //memoria felszabaditas
  for( i=0; i<NJ; i++)
    {
      free( job[i].ProcT );
      free( job[i].StartT );
      free( job[i].EndT );
    }
  free( job );
  free( sch );
  free( ObjF );

  return 0;
}
//---------------------------------------------------------------------------

void Simulation_FS(T_JOB* job, int NJ, int NM, int* s, long t_ref)
{
  //a szimulacio vegrehajtas-vezerelt modon valosul meg,
  //nem valos esemeny-vezerelt logika szerint

  int i, m; //i: inditas sorszama

  for ( i=0; i<NJ; i++)
    for( m=0; m<NM; m++ )
    {
      if ( i == 0 )  //kezdo munka
        {
           if ( m == 0 )  //kezdo gep
              job[ s[i]  ].StartT[ m ] = t_ref;
           else  //nem kezdo gep, kozbenso
              job[ s[i] ].StartT[ m ] = job[ s[i] ].EndT[ m-1 ];
              //anyagmozgatas ideje elhanyagolhato, ha nem + TravlT

        }
      else
        {  //nem kezdo, kozbenso
           if ( m==0 )  //kezdo gep
              job[ s[i] ].StartT[ m ] = job[ s[i-1] ].EndT[ m ];
              //setup ido elhanyagolhato, vagy benne van a ProcT-ben
              //ha nem + SetupT
           else  //nem kezdo gep, kozbenso
              job[ s[i] ].StartT[ m ] = max( job[ s[i] ].EndT[m-1],  //elozo geprol mikor erkezik
                                             job[ s[i-1]].EndT[m] );  //a gep mikor szabadul fel

        }

       job[ s[i] ].EndT[ m ] =   job[ s[i] ].StartT[ m ]  //inditas
                               + job[ s[i] ].ProcT[ m ]; //muvleti ido

    }


}

void Print_Job_Gantt(T_JOB* job, int NJ, int NM, int* s)
{
   int i, m;
   printf("\n Munkak vegrehajtasi idoadatai:");
   for( i=0; i<NJ; i++ )
    {
      printf("\n %d. munka", s[i]);
      printf("\n gep \t Kezd \t Muv. \t Bef.");
      for( m=0; m<NM; m++)
      {
        printf("\n %d \t %ld \t %ld \t %ld"
              ,m
              ,job[ s[i] ].StartT[m]
              ,job[ s[i] ].ProcT[m]
              ,job[ s[i] ].EndT[m]);
      }
    }

}

void Evaluation(T_JOB* job, int NJ, int NM, int* s, double* ObjF)
{
  int f; //futoindex
  for ( f=0; f<NObjF; f++)
      ObjF[f] = 0.0;

  //0 rekesze legyeb a Cmax
  ObjF[0] = job[ s[NJ-1] ].EndT[ NM-1 ];
  //tovabbi celfv-k szamitasa...
}

void Print_ObjF(double* ObjF)
{
  int f; //futoindex
  for ( f=0; f<NObjF; f++)
      printf("\n %d. celfv: %lf", f, ObjF[f]);

}

void Johnson_alg(T_JOB* job, int NJ, int NM, int* s, int m1, int m2)
{
  int* r; //segedvektor
  int i, j, temp;
  int first, last; //firrst, last

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

  //1. fazis elorendezes
  for( i=0; i<NJ-1; i++)
    for( j=i+1; j<NJ; j++ )
      if (  min( job[ r[i] ].ProcT[m1], job[ r[i] ].ProcT[m2] )
            >
            min( job[ r[j] ].ProcT[m1], job[ r[j] ].ProcT[m2] )
         )
      {  //csere
         temp = r[i];
         r[i] = r[j];
         r[j] = temp;
      }

  //utemezes
   first = 0;
   last = NJ-1;
   for( i=0; i<NJ; i++)
    {
      if ( job[ r[i] ].ProcT[m1] <= job[ r[i] ].ProcT[m2] )
        {
           s[first] = r[i];
           first++;
        }
     else
        {
           s[last] = r[i];
           last--;
        }
    }


  free(r);

}

int Search(T_JOB* job, int NJ, int NM, int* s, long t_ref,
            int LOOP, int STEP, int key
            )
{
  int* s0;
  int* sk;
  int* s_ext;
  int* s_best;
  int loop, step;
  int Best_Step;

  double ObjF_sk;
  double ObjF_s_ext;
  double ObjF_s_best;
  double* ObjF;

  ObjF = (double*) calloc(NObjF, sizeof(double) );

  s0 = (int*) calloc(NJ, sizeof(int));
  sk = (int*) calloc(NJ, sizeof(int));
  s_ext = (int*) calloc(NJ, sizeof(int));
  s_best = (int*) calloc(NJ, sizeof(int));

  copy_sch(s, s_best, NJ);
  //fontos
  Simulation_FS(job, NJ, NM, s, t_ref);
  Evaluation(job, NJ, NM, s, ObjF);
  ObjF_s_best = ObjF[key];

  copy_sch(s, s0, NJ);
  Best_Step = 0;

  for( step = 1; step <= STEP; step++ )
  {
     for( loop=1; loop <= LOOP; loop++ )
        {
           Neighbour( s0, sk, NJ ); //szomszedsagi operator
           Simulation_FS(job, NJ, NM, sk, t_ref);
           Evaluation(job, NJ, NM, sk, ObjF);
           ObjF_sk = ObjF[key];

           if ( loop == 1 )  //legjobb szomszed kivalasztasa
             {
               copy_sch(sk, s_ext, NJ); //megoldas megjegyzese
               ObjF_s_ext = ObjF_sk;    //celfv megjegyzesa
             }
           else
              if ( ObjF_s_ext > ObjF_sk )
                { //jobb megoldas mint a legjobb szomszed
                  copy_sch(sk, s_ext, NJ); //megoldas megjegyzese
                  ObjF_s_ext = ObjF_sk;    //celfv megjegyzesa
                }
        }

     //bazismedolgas frissitese a kiterjesztes vegen
     copy_sch(s_ext, s0, NJ);

     if ( ObjF_s_best > ObjF_s_ext )
                { //jobb megoldas mint az eddiggi legjobb
                  copy_sch(s_ext, s_best, NJ); //megoldas megjegyzese
                  ObjF_s_best = ObjF_s_ext;    //celfv megjegyzesa
                  Best_Step = step;            //lepes sorszama
                }


  }

  //legjobb visszaadasa
  copy_sch( s_best, s, NJ);

  free( ObjF );
  free( s0 );
  free( sk );
  free( s_ext );
  free( s_best );

  return Best_Step;
}

void copy_sch(int* s, int* t, int NJ )
{
  int i;

  for( i=0; i<NJ; i++)
       t[i] = s[i];

}

void Neighbour( int* s0, int* sk, int NJ )
{
 //pelda
 //veletlenszeruen valsztott elemet a bal szomszedjaval felcserelem
 //kivetel a 0. elem, ot az utolso elemmel csereljuk fel
 int x;

 copy_sch( s0, sk, NJ );

 x = rand()%NJ;  //0..NJ-1

 if ( x == 0 )
   {
      sk[ 0 ] = s0 [ NJ-1 ];
      sk[ NJ-1 ] = s0 [ 0 ];
   }
 else
   {
      sk[ x ] = s0 [ x-1 ];
      sk[ x-1 ] = s0 [ x ];

   }

}