/*------------------------------------------------------------------------------
TIA 8. gyakorlat
F|perm|Cmax ütemezési feladat modellezése.
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 9. 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 10. 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|perm|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.

========
DTFSZTIR 2. gyakorlat

F|perm|Cmax Utemezesi fedadat megoldasa
CDS algoritmus

Továbbfejlesztett modell:

F|perm|Cmax
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 munkacsoport átfutási idejének minimalizálása.

CDS-algoritmus:
A Campbell-Dudek-Smith algoritmus a többgépes feladatot kétgépes problémákra
vezeti vissza.
Az algoritmus az eredeti NR gépes feladatból NR-1 darab mesterséges kétgépes problémát generál
úgy, hogy az egymást követő gépek lesznek a kétgépes feladat gépei.
A kétgépes feladatok egyenként megoldhatók a Johnson-algoritmussal.
Kiválasztva közülük a teljes feladatra vonatkozó átfutási idő szempontjából
a legjobbat, az lesz az NR-gépes probléma megoldása.
A megodás nem optimális mert a feladat NP-hard, de jó közelítő ütemtervet eredményez.


Kereső algoritmus
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.


DTFSZTIR 5. gyakorlat

Munkasorrend-függő gépátállítások figyelembe vétele

Gépek közötti anyagmozgatási idők modellezése



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

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

typedef struct {
                int id;
                long* ProcT;  //pointer: muveleti idok vektorara mutat
                long* StartT; //pointer: inditasi idopontok vektorara mutat
                long* EndT; //pointer: befejezesi idopontok vektorara mutat
               }T_JOB; //munka

typedef struct {
                int id;
                long** SetupT;  //atallitasi idok matrixa
                long* TransT;  //anyagmozgatasi idok vektora
               }T_RES;  //eroforras

long max_l( long a, long b) { return a>b ? a : b; }
long min_l( long a, long b) { return a<b ? a : b; }

void Simulation_F( T_JOB* job, int NJ, int NR, T_RES* res, int* s, long t_ref);
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);
int  Johnson_alg_ext_F3( T_JOB* job, int NJ, int r, int* s);
void Dannenbring_F( T_JOB* job, int NJ, int NR, int* s);
long Evaluate(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, T_RES* res, int* s);
void Search_alg( T_JOB* job, int NJ, int NR, T_RES* res, int* s, int STEP, int LOOP);
void Neighbour(int* s_0, int* s_act, int NJ);







int main(int argc, char* argv[])
{
  int NJ;   //munkak szama
  int i, j;    //munka indexe
  int NR;   //eroforrasok (munkahelyek) szama
  int r, k;    //eroforras indexe
  T_RES* res;  //eroforrasok listajara mutat
  T_JOB* job; //job-tablara mutat
  //perm: a munkak nem elozheti meg egymast
  int* s;     //utemezes vektorara mutat
  long Cmax;  //celfuggvenz erteke
  int STEP, LOOP; //kereseshez parameter

  printf("\n Flow Shop utemezesi feladat szimulacioja.");
  printf("\n Munkak szama:");
  scanf("%d", &NJ);
  printf("\n Eroforrasok szama:");
  scanf("%d", &NR);

  //mem. fogalalas
  res = (T_RES*) calloc(NR, sizeof(T_RES));

  for ( r=0; r<NR; r++)
   {
     res[r].id = r;
     res[r].SetupT = (long**) calloc(NJ, sizeof(long*));
     for ( i=0; i<NJ; i++)
       {
         res[r].SetupT[i] = (long*) calloc(NJ, sizeof(long));
         for ( j=0; j<NJ; j++)
           if ( i == j )
              res[r].SetupT[i][j] = 0;  //azonos tipusok kozott
           else
              res[r].SetupT[i][j] = 20 + rand()%50; //kulonbozo tipusok kozott
       }

    res[r].TransT = (long*) calloc(NR, sizeof(long));
    for( k=0; k<NR; k++)
       if ( r == k )
          res[r].TransT[k] = 0; //azonos a forras es a celgep
       else
          res[r].TransT[k] = 10 + rand()%100;
   }

  job = (T_JOB*) calloc(NJ, sizeof(T_JOB));
  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));
      //alapadat generalasa
      for ( r=0; r<NR; r++ )
         job[i].ProcT[r] = 1+rand()%100;  //muveleti ido

      job[i].StartT = (long*) calloc(NR, sizeof(long));
      job[i].EndT = (long*) calloc(NR, sizeof(long));

      //AD-HOC: erkezesi sorrend
      s[i]=i;
      //LIFO
      //s[i]=NJ-1-i;
    }

  //teszt
  printf("\n AD-HOC sorrend:");
  Simulation_F( job, NJ, NR, res, s, 0);
  //Print_Res_Gantt( job, NJ, NR, s);
  Cmax = Evaluate(job, NJ, NR, s);
  printf("\n Cmax = %ld", Cmax);


  if ( NR == 2 )
    { //F2 ketgepes eset
     printf("\n Johnson sorrend:");
     Johnson_alg( job, NJ, 0, s); //0 es 1 a gep azonosito
     Simulation_F( job, NJ, NR, res, s, 0);
     Print_Res_Gantt( job, NJ, NR, s);
     Cmax = Evaluate(job, NJ, NR, s);
     printf("\n Cmax = %ld", Cmax);


    }

  if ( NR==3 )
    { //F3
     printf("\n Johnson sorrend F3-ra:");
     if ( Johnson_alg_ext_F3( job, NJ, 0, s) == 1 )
        printf("\n Optimalitas feltetele teljesul.");
     else
        printf("\n Optimalitas feltetele nem teljesul.");
     //az eredeti idoadatokkal futtatjuk a szimulaciot
     Simulation_F( job, NJ, NR, res, s, 0);
     Print_Res_Gantt( job, NJ, NR, s);
     Cmax = Evaluate(job, NJ, NR, s);
     printf("\n Cmax = %ld", Cmax);

    }
          //Dannenbring-alg. Fm-re
     printf("\n Dannenbring algoritmus Fm-re:");
     Dannenbring_F( job, NJ, NR, s);
     //az eredeti idoadatokkal futtatjuk a szimulaciot
     Simulation_F( job, NJ, NR, res, s, 0);
     //Print_Res_Gantt( job, NJ, NR, s);
     Cmax = Evaluate(job, NJ, NR, s);
     printf("\n Cmax = %ld", Cmax);

     //CDS alg. Fm-re
     printf("\n CDS algoritmus Fm-re:");
     CDS_alg( job, NJ, NR, res, s);
     //az eredeti idoadatokkal futtatjuk a szimulaciot
     Simulation_F( job, NJ, NR, res, s, 0);
     //Print_Res_Gantt( job, NJ, NR, s);
     Cmax = Evaluate(job, NJ, NR, s);
     printf("\n Cmax = %ld", Cmax);


     //Search alg. Fm-re
    printf("\n Kereso algoritmus demo Fm||Cmax feladatra");
    printf("\n Kereso lepesek szama=");
    scanf("%d", &STEP);
    printf("\n Szomszedos megoldasok vizsgalt szama=");
    scanf("%d", &LOOP);

     Search_alg( job, NJ, NR, res, s, STEP, LOOP);
     //az eredeti idoadatokkal futtatjuk a szimulaciot
     Simulation_F( job, NJ, NR, res, s, 0);
     //Print_Res_Gantt( job, NJ, NR, s);
     Cmax = Evaluate(job, NJ, NR, s);
     printf("\n Cmax = %ld", Cmax);

  //felszabaditas
  for ( r=0; r<NR; r++)
   {
     for ( i=0; i<NJ; i++)
       {
         free( res[r].SetupT[i] );
       }
     free( res[r].SetupT );
   }
 free( res );  

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

  getch();
  return 1;
}

void Simulation_F( T_JOB* job, int NJ, int NR, T_RES* res, int* s, long t_ref)
{
  int i; //vegrehajtasi sorrend indexe
  int r; //eroforras indexe

  for ( i=0; i<NJ; i++ ) //vegrehajtasi sorrend
   for ( r=0; r<NR; r++ )
   {
     if ( i==0 ) //kezdo munka
       {
          if ( r==0 ) //kezdo munkahely
             {
             //az inditas idopontja a mervado
             job[ s[i] ].StartT[r] = t_ref;  //referencia ido
                    //bef. ido = kezdet + muv. ido;
             job[ s[i] ].EndT[r] = job[ s[i] ].StartT[r]
                           + res[r].SetupT[ 0 ][s[i]]     //0. tipus az alapertelmezett
                           + job[ s[i] ].ProcT[r];

             }
          else  //nem kezdo munkahely
             {
             //elozo geprol mikor erkezik
             job[ s[i] ].StartT[r] = job[ s[i] ].EndT[r-1]
                                     + res[r].TransT[r-1];  //anyagmozgatasi ido
                    //bef. ido = kezdet + muv. ido;
             job[ s[i] ].EndT[r] = job[ s[i] ].StartT[r]
                           + res[r].SetupT[ 0 ][s[i]]     //atallitas
                           + job[ s[i] ].ProcT[r];

             }
       }
     else  //nem kezdo munka
       {
          if ( r==0 ) //kezdo munkahely
             {
             //elozo munka mikor fejezodik be
             job[ s[i] ].StartT[r] = job[ s[i-1] ].EndT[r];
                    //bef. ido = kezdet + muv. ido;
             job[ s[i] ].EndT[r] = job[ s[i] ].StartT[r]
                                   + res[r].SetupT[ s[i-1] ][s[i]]  //atallitas
                                   + job[ s[i] ].ProcT[r];

             }
          else  //nem kezdo munkahely
             {
             job[ s[i] ].StartT[r] = max_l( job[ s[i] ].EndT[r-1] + res[r].TransT[r-1], //elozo geprol mikor erkezik
                                            job[ s[i-1] ].EndT[r] ); //a gep mikor szabadul fel az elozo munka terhelese alol
                    //bef. ido = kezdet + muv. ido;
             job[ s[i] ].EndT[r] = job[ s[i] ].StartT[r]
                                 + res[r].SetupT[ s[ i-1 ] ][s[i]]   //atallitas
                                 + job[ s[i] ].ProcT[r];

             }
       }

   }
}

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

  printf("\n Resource Gantt Chart \n");
  for (r=0; r<NR; r++)
   {
     printf("\n R_%d", r);
     printf("\n\t sor\tmunka\tindul\tmuv.\tvegez");
     for (i=0; i<NJ; i++)
      printf("\n\t %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]);

   }
}

void Johnson_alg( T_JOB* job, int NJ, int r, int* s)
{
  int i, j; //job indexek a rendezeshez
  int* v;   //elorendezeshez szukseges vektorra mutato pointer
  int index, sel_index;
  long value, sel_value;
  int temp;
  int first, last;

  v = (int*) calloc(NJ, sizeof(int) );  //vektor az elorendezeshez
  //inicializalas
  for (i=0; i<NJ; i++)
     v[i] = i;

   //elorendezes muveleti idok alapjan
   for( i=0; i<NJ-1; i++ )
     {
       index = i;
       value = min_l( job[ v[index] ].ProcT[r],
                      job[ v[index] ].ProcT[r+1] );

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

       if ( value > sel_value )
          { //megjegyzem
            index = j;
            value = sel_value;
          }

       }

     if ( index != i )
       { //csere
         temp = v[ index ];
         v[ index ] = v[ i ];
         v[ i ] = temp;
       }
     }

   //beutemezes
   first = 0;
   last  = NJ-1;
   for( i=0; i<NJ; i++ )
     {
       if ( job[ v[i] ].ProcT[r] <=
            job[ v[i] ].ProcT[r+1] )
          { //elorol indulva a mar beutemezettek moge
            s[ first ] = v[i]; //beutemezes
            first++;
          }
       else
          { //hatulrol indulva a mar beutemezettek ele
            s[ last ] = v[i]; //beutemezes
            last--;
          }
     }

  free( v );
}

long Evaluate(T_JOB* job, int NJ, int NR, int* s)
{
   //Cmax: utolsokent elkeszulo munka befejezesi idopontja
   //F|perm|Cmax modell eseten az utolsokent inditott munka bef. ideje az utolso gepen
   return job[ s[NJ-1] ].EndT[NR-1];
}

int Johnson_alg_ext_F3( T_JOB* job, int NJ, int r, int* s)
{
  //Johnson-algoritmus alkalmazasa harom gepes esetre

  int i;   //munka indexe
  T_JOB* job_V2;  //virtualis ketgepes eset idoadataihoz szukseges
  long pi0_min, pi1_max, pi2_min;

  //transzformacio ket gepres esetre
  job_V2 = (T_JOB*) calloc( NJ, sizeof(T_JOB) ); //strukturavektor
  for ( i=0; i<NJ; i++ )
    {
       //csak a muveleti idoket hasznaljuk
       job_V2[i].ProcT = (long*) calloc(2, sizeof(long) ); //ket virtualis gep

       job_V2[i].ProcT[0] = job[i].ProcT[r] +
                            job[i].ProcT[r+1];

       job_V2[i].ProcT[1] = job[i].ProcT[r+1] +
                            job[i].ProcT[r+2];

    }

   //Johnson-alg hasznalata a virtualis ketgepes esetre
   Johnson_alg( job_V2, NJ, 0, s);

   //optimalitas ellenorzese
   pi0_min = job[0].ProcT[r];
   pi1_max = job[0].ProcT[r+1];
   pi2_min = job[0].ProcT[r+2];

   for ( i=1; i<NJ; i++ )
    {
      if ( pi0_min > job[i].ProcT[r] )
           pi0_min = job[i].ProcT[r];

      if ( pi1_max < job[i].ProcT[r+1] )
           pi1_max = job[i].ProcT[r+1];

      if ( pi2_min > job[i].ProcT[r+2] )
           pi2_min = job[i].ProcT[r+2];
    }

   for( i=0; i<NJ; i++ )
     free( job_V2[i].ProcT );
   free( job_V2 );

   if ( pi0_min >= pi1_max || pi2_min >= pi1_max )
      return 1;
   else
      return 0;
}

void Dannenbring_F( T_JOB* job, int NJ, int NR, int* s)
{
  //Dannenbring-algoritmus alkalmazasa
  int i;   //munka indexe
  int r;   //gep indexe
  T_JOB* job_V2;  //virtualis ketgepes eset idoadataihoz szukseges

  //transzformacio ket gepres esetre
  job_V2 = (T_JOB*) calloc( NJ, sizeof(T_JOB) ); //strukturavektor

  for ( i=0; i<NJ; i++ )
    {
       //csak a muveleti idoket hasznaljuk
       job_V2[i].ProcT = (long*) calloc(2, sizeof(long) ); //ket virtualis gep

       job_V2[i].ProcT[0] = 0;
       job_V2[i].ProcT[1] = 0;

       for ( r=0; r<NR; r++ )
       {
         job_V2[i].ProcT[0] += (NR-(r+1)+1) * job[i].ProcT[r];
         job_V2[i].ProcT[1] += (r+1) * job[i].ProcT[r];

       }
    }

   //Johnson-alg hasznalata a virtualis ketgepes esetre
   Johnson_alg( job_V2, NJ, 0, s);


   for( i=0; i<NJ; i++ )
     free( job_V2[i].ProcT );
   free( job_V2 );

}

void CDS_alg( T_JOB* job, int NJ, int NR, T_RES* res, int* s)
{
  int r; //futoindex a gepekhez

  int* s_act; //aktualisan vizsgalt utemezes
  int* s_best; //a legjobb megoldas

  long Cmax_act;  //celfuggveny
  long Cmax_best;

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

  for ( r=0; r < NJ-1; r++ )
   {
     Johnson_alg( job, NJ, r, s_act); //Johnson alg
     Simulation_F( job, NJ, NR, res, s_act, 0); //szimulacio a teljes rendszerre
     Cmax_act = Evaluate( job, NJ, NR, s_act); //Cmax

     if ( r==0 )
       {
         //elso vizsgalt megoldast menti
         copy_sch( s_act, s_best, NJ);
         Cmax_best = Cmax_act;

       }
     else
       if ( Cmax_act < Cmax_best )
        {
         //a jobb megoldast menti
         copy_sch( s_act, s_best, NJ);
         Cmax_best = Cmax_act;

        }

   }

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


  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, T_RES* res, int* s, int STEP, int LOOP)
{
  //STEP keresesi lepesek szama
  //LOOP adott lepesben vizsgalt szomszedok szama

  int step, loop; //futoindex

  int* s_0; //bazis utemezes
  int* s_act; //aktualisan vizsgalt utemezes
  int* s_ext; //a legjobb szomszedos megoldas
  int* s_best; //a legjobb megtalalt megoldas

  long Cmax_act;  //celfuggveny
  long Cmax_ext;
 long Cmax_best;

  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) );

  //inicializalas
  copy_sch(s, s_0, NJ);  //kezdo bazis a bemeneti megoldas
  copy_sch(s, s_best, NJ);  //kezdo bazis a legjobb megoldas
  Simulation_F( job, NJ, NR, res, s_best, 0); //szimulacio a teljes rendszerre
  Cmax_best = Evaluate( job, NJ, NR, s_best); //Cmax

  for ( step=1; step <= STEP; step++ ) //keresesi lepesek
  {

   for ( loop=1; loop <= LOOP; loop++ )
   {
     Neighbour(s_0, s_act, NJ); //modosito operator
     Simulation_F( job, NJ, NR, res, s_act, 0); //szimulacio a teljes rendszerre
     Cmax_act = Evaluate( job, NJ, NR, s_act); //Cmax

     if ( loop==1 )
       {
         //elso vizsgalt megoldast menti
         copy_sch( s_act, s_ext, NJ);
         Cmax_ext = Cmax_act;

       }
     else
       if ( Cmax_act < Cmax_ext )
        {
         //a jobb megoldast menti
         copy_sch( s_act, s_ext, NJ);
         Cmax_ext = Cmax_act;
        }
   } //loop

   //nem ragad le
   copy_sch( s_ext, s_0, NJ); //a legjobb szomszed lesz a kovetkeyo bazismegoldas

   if ( Cmax_ext < Cmax_best )
     {
        copy_sch( s_ext, s_best, NJ);
        Cmax_best = Cmax_ext;
     }

  } //step

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


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

void Neighbour(int* s_0, int* s_act, int NJ)
{ //pelda modosito operatorra
  //sokfele modszer implementalhato

  int i; //index
  int x; //kivalasztott cella

  copy_sch(s_0, s_act, NJ);

  x = rand()%NJ;

  if ( x==0 )
   {
     //kezdo elemet az utolsoval felcsereli
     s_act[x] = s_0[NJ-1];
     s_act[NJ-1] = s_0[x];
   }
  else
   {
     //kivalasztott es az elotte levo csereje
     s_act[x] = s_0[x-1];
     s_act[x-1] = s_0[x];
   }
}