/*------------------------------------------------------------------------------
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.

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

#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

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




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

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

  //mem. fogalalas
  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, 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, 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, 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, s, 0);
     Print_Res_Gantt( job, NJ, NR, s);
     Cmax = Evaluate(job, NJ, NR, s);
     printf("\n Cmax = %ld", Cmax);

  //felszabaditas
  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, 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
          else  //nem kezdo munkahely
             //elozo geprol mikor erkezik
             job[ s[i] ].StartT[r] = job[ s[i] ].EndT[r-1];
       }
     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];
          else  //nem kezdo munkahely
             job[ s[i] ].StartT[r] = max_l( job[ s[i] ].EndT[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]
                           + 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 );

}