/*------------------------------------------------------------------------------
TIA 6. gyakorlat
F|perm|Cmax
Egyutas előzésnélküli többoperációs ütemezési feladat.
Cél: A befejezési időpont minimalizálása.
1. rész:
Modellépítés és szimuláció.
A Simulation_F 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.

TIA 7. gyakorlat
F2|perm|Cmax ütemezési fedadat megoldása Johnson-algoritmussal.
Az algoritmus optimális megoldást eredményez (két gép esetén).

TIA 9. gyakorlat
F3|perm|Cmax ütemezési fedadat megoldása
kiterjesztett Johnson-algoritmussal.
A három gépes feladatot két virtuális gépre vezetjük vissza úgy.
hogy minden munka esetében az első és a második operáció műveleti idejét összeadjuk,
és a második és harmadik operáció műveleti idejét szintén összeadjuk.
Az így előállított virtuális kétgépes feladatra alkalmazzuk a Johnson-algoritmust.
Ha az első gép legkisebb időadata nagyobb mint a középső gép legnagyobb időadata,
vagy a harmadik gép legkisebb időadata nagyobb mint a középső gép legnagyobb időadata
akkor a megoldás optimális, egyébként az optimalitás nem garantálható!


Továbbfejlesztett modell:

F|permut|Cmax
Dannenbring-módszer lényege az, hogy a tetszőleges számú sorba kapcsolódó gépeket
egy virtuális kétgépes modellre vezetjük vissza egy alkalmasan megválasztott súlyozási szisztéma segítségével.
Az így előállított virtuális kétgépes feladatra alkalmazzuk a Johnson-algoritmust.

TIA 10. gyakorlat
F|perm|Cmax Utemezesi fedadat megoldasa kereső algoritmus alkalmazásával.
Lokális szomszédsági kereső algoritmus implementálása (egy továbbfejleszthető alap kereső algoritmsu váz).
Futási eredmények: A keresési módszer lassabban működik, de jobb eredményt ad mint a korábban vizsgált heurisztikus algoritmusok.


-------------------------------------------------------------------------------*/

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

typedef struct {
                int id;  //azonosito
                long* ProcT;   //pointer mutat a muveleti idok vektorara
                long* StartT;  //pointer mutat a kezdesi idok vektorara
                long* EndT;    //pointer mutat a befejezesi idok vektorara
               } T_JOB;

void Simulation_F( T_JOB* job, int NJ, int NR, int* s, long t0);
long Evaluate_F( T_JOB* job, int NJ, int NR, int* s);
void Print_Res_Gantt( T_JOB* job, int NJ, int NR, int* s);
void Johnson_alg( T_JOB* job, int NJ, int r, int* s);
void Johnson_alg_ext_F3( T_JOB* job, int NJ, int r, int* s);
void Dannenbring( T_JOB* job, int NJ, int NR, int* s);
void copy_sch( int* s1, int* s2, int NJ);
void CDS_alg( T_JOB* job, int NJ, int NR, int* s);
void Search_alg( T_JOB* job, int NJ, int NR, int* s, int STEP, int LOOP);
void Neighbour( int* s_0, int* s_act, int NJ);


/*CodeBlocks eseten definialjuk a max fuggvenyt
long max(long a, long b)
{
 return a>=b ? a : b;
}

long min(long a, long b)
{
 return a<=b ? a : b;
}
*/

int main()
{
 T_JOB* job; //mutat a strukturavektorra
 int NJ;     //munkak szama
 int NR;     //eroforrasok (munkahelyek) szama
 time_t t;
 int i;      //munka index
 int r;      //eroforras index
 int* s;     //utemtervre mutat
 long Cmax;

 srand( time(&t)); //inic.

 printf("\n Flow Shop demo.");
 printf("\n Munkak szama:");
 scanf("%d", &NJ); //ellenorzes nincs
 printf("\n Eroforrasok szama:");
 scanf("%d", &NR); //ellenorzes nincs


 //Valosagban a technologiai tervbol kiolvashatok a muveleti idok
 job = (T_JOB*) calloc(NJ, sizeof(T_JOB)); //strukturavektor
 s = (int*) calloc(NJ, sizeof(int));       //utemterv

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

     for ( r=0; r<NR; r++ )
        job[i].ProcT[r] = 1 + rand()%20;  //muveleti idok

     s[i] = i; //Ad-hoc
  }

  //szimulacio
  printf("\n Flow Shop modell.");
  printf("\n Ad-hoc sorrend:");
  Simulation_F( job, NJ, NR, s, 0);
  //Print_Res_Gantt( job, NJ, NR, s);
  Cmax = Evaluate_F( job, NJ, NR, s);
  printf("\n Cmax = %ld", Cmax);

  if ( NR == 2 )
  {
   printf("\n Johnson sorrend:");
   Johnson_alg( job, NJ, 0, s); //r=0
   Simulation_F( job, NJ, NR, s, 0);
   //Print_Res_Gantt( job, NJ, NR, s);
   Cmax = Evaluate_F( job, NJ, NR, s);
   printf("\n Cmax = %ld", Cmax);
  }

  if ( NR == 3 )
  {
   printf("\n Johnson sorrend F3-ra:");
   Johnson_alg_ext_F3( job, NJ, 0, s);
   Simulation_F( job, NJ, NR, s, 0);
   //Print_Res_Gantt( job, NJ, NR, s);
   Cmax = Evaluate_F( job, NJ, NR, s);
   printf("\n Cmax = %ld", Cmax);
  }

   printf("\n Dannenbring sorrend:");
   Dannenbring( job, NJ, NR, s);
   Simulation_F( job, NJ, NR, s, 0);
   //Print_Res_Gantt( job, NJ, NR, s);
   Cmax = Evaluate_F( job, NJ, NR, s);
   printf("\n Cmax = %ld", Cmax);

   printf("\n CDS sorrend:");
   CDS_alg( job, NJ, NR, s);
   Simulation_F( job, NJ, NR, s, 0);
   //Print_Res_Gantt( job, NJ, NR, s);
   Cmax = Evaluate_F( job, NJ, NR, s);
   printf("\n Cmax = %ld", Cmax);

 {
   int STEP, LOOP;
   printf("\n Random kereses:");

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

   Search_alg( job, NJ, NR, s, STEP, LOOP);
   Simulation_F( job, NJ, NR, s, 0);
   //Print_Res_Gantt( job, NJ, NR, s);
   Cmax = Evaluate_F( job, NJ, NR, s);
   printf("\n Cmax = %ld", Cmax);
 }

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


 getch();
 
 return 1;
}

void Simulation_F( T_JOB* job, int NJ, int NR, int* s, long t0)
{
 //Elozes nelkuli Flow Shop modell szimulacioja
 int i, r;

 for ( i=0; i<NJ; i++ )
  for ( r=0; r<NR; r++ )
  {
      if ( i == 0 )
        {
          if ( r==0 )
            { //kezdo munka kezdo gepen
              job[ s[i] ].StartT[r] = t0;  //ref. idoben indul
            }
          else
            { //kezdo munka nem kezdo gepen
              job[ s[i] ].StartT[r] = job[ s[i] ].EndT[r-1];  //elozo gepen mikor vegez
            }
        }
      else
        {
          if ( r==0 )
            {
              job[ s[i] ].StartT[r] = job[ s[i-1] ].EndT[r]; //elozo munka mikor vegzett
            }
          else
            { //nem kezdo munka nem kezdo gepen
              //elozo geprol a munka mikor erkezik
              //elozo munka ezen a gepen mikor vegez
              job[ s[i] ].StartT[r] = max( job[ s[i] ].EndT[r-1],
                                           job[ s[i-1] ].EndT[r] );
            }
        }

      //kesz         =   indul          +   muveleti ido
      //BUG javitva i helyett s[i]
      job[ s[i] ].EndT[r] = job[ s[i] ].StartT[r] + job[ s[i] ].ProcT[r];



  }

}

void Print_Res_Gantt( T_JOB* job, int NJ, int NR, int* s)
{
  int i, r;

  printf("\n\n Eroforras-orientalt Gantt diagramm");
  for ( r=0; r<NR; r++)
   {
     printf("\n R_%d", r);
     printf("\n sor. \t munka \t indul \t muv. \t kesz");
     for ( i=0; i<NJ; i++)
       printf("\n %d. \t %d \t %ld \t %ld \t %ld",
                i,
                s[i],
                job[ s[i] ].StartT[r],
                job[ s[i] ].ProcT[r],
                job[ s[i] ].EndT[r] );

   }

}

long Evaluate_F( T_JOB* job, int NJ, int NR, int* s)
{
  //F modell alapjan adott, hogy az utolsokent inditott munka utolso gepre vonatkoyo befejezesi idopontja a Cmax
  return job[ s[ NJ-1 ] ].EndT[ NR-1 ];
}

void Johnson_alg( T_JOB* job, int NJ, int r, int* s)
{  //Johnson-algoritmus F2|perc|Cmax feladatra

  int i,j;  //segedvaltozok a rendezeshez
  int* v;   //vektorra mutato pointer
  int min_index;   //a legkisebb muveleti idejeu munka pozicioja a v vektorban
  long min_val;    //a kulcsertek ami szerint rendezunk
  long act_val;    //a kulcsertek ami szerint rendezunk
  int temp;
  int first, last; //s vektor epitesekor hasznalt szamlalok

  v = (int*) calloc(NJ, sizeof(int) );

  //elokeszites: munkak elorendezese muveleti idok alapjan
  for ( i=0; i<NJ; i++)
       v[i] = i;

   //rendezes
   for ( i=0; i<NJ-1; i++ )
   {
      min_index = i;
      min_val   = min( job[ v[min_index] ].ProcT[r] ,
                        job[ v[min_index] ].ProcT[r+1]  );

      for ( j=i+1; j<NJ; j++ )
       {
        act_val   = min( job[ v[j] ].ProcT[r] ,
                         job[ v[j] ].ProcT[r+1]  );

        if ( min_val > act_val )
          {
            min_index = j;   //jelolt megjegyzese
            min_val = act_val;
          }

       }

     if ( min_index != i )
       { //csere
          temp = v[ i ];
          v[ i ] = v[ min_index ];
          v[ min_index ] = temp;
       }
   }
   //elokeszites kesz

   //utmezes
   first = 0;
   last = NJ-1;

   for ( i=0; i<NJ; i++)
    {
       //mindig a v[i] munkat utemezzuk be
       if ( job[ v[i] ].ProcT[r] <= job[ v[i] ].ProcT[r+1]  )
         {  //elso gepen kisebb a muveleti ido
            //beszurjuk a vektor elejere a mar beutemezettek moge
            s[ first ] = v[ i ];
            first++;
         }
       else
         {  //masodik gep ideje kisebb
            //beszurjuk a vektor vegere a mar beutemzettek ele
            s[ last ] = v[ i ];
            last--;
         }
    }

  free( v );

}

void Johnson_alg_ext_F3( T_JOB* job, int NJ, int r, int* s)
{
  int i;  //munka
  T_JOB* V2_job;

  //virtualis ket gep
  V2_job = (T_JOB*) calloc(NJ, sizeof(T_JOB));
  for( i=0; i<NJ; i++)
   {
     V2_job[i].ProcT = (long*) calloc(2, sizeof(long));

     V2_job[i].ProcT[0] = job[i].ProcT[0] + job[i].ProcT[1];
     V2_job[i].ProcT[1] = job[i].ProcT[1] + job[i].ProcT[2];

   }

  //Johnson-algoritmus futtatasa a virtualis ket gepen
  Johnson_alg( V2_job, NJ, 0, s);


   //mem. felszabaditas
  for( i=0; i<NJ; i++)
     free( V2_job[i].ProcT );

   free( V2_job );


}

void Dannenbring( T_JOB* job, int NJ, int NR, int* s)
{
  int i;  //munka
  int j;  //gep
  T_JOB* V2_job;

  //virtualis ket gep
  V2_job = (T_JOB*) calloc(NJ, sizeof(T_JOB));
  for( i=0; i<NJ; i++)
   {
     V2_job[i].ProcT = (long*) calloc(2, sizeof(long));

     V2_job[i].ProcT[0] = 0;
     for ( j=0; j<NR; j++)
        V2_job[i].ProcT[0] += (NR - (j+1) + 1)*job[i].ProcT[j];
                                   // j a modellben 1, 2, .., m
     V2_job[i].ProcT[1] = 0;
     for ( j=0; j<NR; j++)
        V2_job[i].ProcT[0] += (j+1)*job[i].ProcT[j];
                             // j a modellben 1, 2, .., m

   }

  //Johnson-algoritmus futtatasa a virtualis ket gepen
  Johnson_alg( V2_job, NJ, 0, s);


   //mem. felszabaditas
  for( i=0; i<NJ; i++)
     free( V2_job[i].ProcT );

   free( V2_job );


}

void CDS_alg( T_JOB* job, int NJ, int NR, int* s)
{
  int r; //eroforras index
  int* s_act;   //aktualisan vizsgalt megoldas
  int* s_best;  //a vizsgalt legjobb megoldas

  long Cmax_act; //az aktualisan vizsgalt megoldas celfuggveny-erteke
  long Cmax_best; //a legjobb vizsgalt megoldas celfuggveny-erteke

  s_act  = (int*) calloc( NJ, sizeof(int) );
  s_best = (int*) calloc( NJ, sizeof(int) );

  for( r=0; r<NR-1; r++)
   { //virtualis ket gepet vizsgal: r es r+1 a ket gep
     Johnson_alg( job, NJ, r, s_act);
     Simulation_F( job, NJ, NR, s_act, 0); //teljes probleman futtatjuk a szimulaciot
     Cmax_act = Evaluate_F( job, NJ, NR, s_act);

     if ( r==0 )
       { //az elso jelolt
         copy_sch( s_act, s_best, NJ );
         Cmax_best = Cmax_act;
       }
     else
       {
        if ( Cmax_best > Cmax_act )
           {
             copy_sch( s_act, s_best, NJ );
             Cmax_best = Cmax_act;
           }
       }
   }

    //eredmeny
    copy_sch( s_best, s, NJ );

  free( s_act );
  free( s_best );
}

void copy_sch( int* s1, int* s2, int NJ)
{
  int i;
  for( i=0; i<NJ; i++)
    s2[i] = s1[i];
}

void Search_alg( T_JOB* job, int NJ, int NR, int* s, int STEP, int LOOP)
{
  int step, loop; //keresesi segedvaltozok

  int* s_0;     //bazis megoldas
  int* s_act;   //aktualisan vizsgalt megoldas
  int* s_ext;   //a kiterjesztes (szomszedsag) legjobb megoldas
  int* s_best;  //a vizsgalt legjobb megoldas

  long Cmax_act; //az aktualisan vizsgalt megoldas celfuggveny-erteke
  long Cmax_ext; //legjobb szomszedos megoldas celfuggveny-erteke
  long Cmax_best; //a legjobb vizsgalt megoldas celfuggveny-erteke

  s_0  = (int*) calloc( NJ, sizeof(int) );
  s_act  = (int*) calloc( NJ, sizeof(int) );
  s_ext  = (int*) calloc( NJ, sizeof(int) );
  s_best = (int*) calloc( NJ, sizeof(int) );

  //bazis generalas: a bemeneten megkapott s adja a bazist
  copy_sch( s, s_0, NJ);
  copy_sch( s, s_best, NJ);
  Simulation_F( job, NJ, NR, s_best, 0); //teljes probleman futtatjuk a szimulaciot
  Cmax_best = Evaluate_F( job, NJ, NR, s_best);

  for( step=1; step<=STEP; step++ )
  {
   for( loop=1; loop<=LOOP; loop++) //szomszedok keszitese a bazisbol kiindulva
   {
     Neighbour( s_0, s_act, NJ); //szomszedsagi operator
     Simulation_F( job, NJ, NR, s_act, 0); //teljes probleman futtatjuk a szimulaciot
     Cmax_act = Evaluate_F( job, NJ, NR, s_act);

     if ( loop==1 )
       { //az elso jelolt
         copy_sch( s_act, s_ext, NJ );
         Cmax_ext = Cmax_act;
       }
     else
       {
        if ( Cmax_ext > Cmax_act )
           {
             copy_sch( s_act, s_ext, NJ );
             Cmax_ext = Cmax_act;
           }
       }
   } //loop

   //bazis kivalasztasa
   //mindig a legjobb szomszed lesz az uj bazis
   copy_sch( s_ext, s_0, NJ);

   if ( Cmax_best > Cmax_ext )
    {
       copy_sch( s_ext, s_best, NJ);
       Cmax_best = Cmax_ext;
    }
  } //step

  //eredmeny
  copy_sch( s_best, s, NJ );

  free( s_0 );
  free( s_act );
  free( s_ext );
  free( s_best );
}

void Neighbour( int* s_0, int* s_act, int NJ)
{ //szomszedsagi operator
  //veletlenszeruen valasztott cella tartalmat felcsereli az elotte levo cella tartalmazal

  int x;

  copy_sch( s_0, s_act, NJ); //masolat
  x = rand()%NJ; //veletlenszeru valasztas

  if ( x == 0 )
   { //gyuruve alakitjuk a vektort es a 0. baloldalan megjelenik az utolso elem
     s_act[x] = s_0[NJ-1];
     s_act[NJ-1] = s_0[x];
   }
  else
   {
     s_act[x] = s_0[x-1];
     s_act[x-1] = s_0[x];
   }
}