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

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

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

typedef struct{
               int id;        //azonosito
               long* ProcT;   //muveleti idok vektora
               long* StartT;  //inditasi idopontok vektora
               long* EndT;    //befejezesi idopontok vektora
               } T_JOB;       //munka

/*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;
}

*/

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_alg(T_JOB* job, int NJ, int NR, int* s);




int main()
{
  time_t t;
  int NJ; //number of jobs
  int i;  //index of jobs
  int NR; //number of resources
  int r;  //index of resources

  T_JOB* job;  //jobs
  int* s;      //schedule
  long Cmax;   //celfv erteke

  //A termelesinformatikai integralt rendszerbol lekerdezheto
  printf("\n Flow Shop demo.");
  printf("\n Kerem a munkak szamat:");
  scanf("%d", &NJ);  //ellenorzes nincs
  printf("\n Kerem a gepek szamat:");
  scanf("%d", &NR);  //ellenorzes nincs

  srand( time(&t) ); //inic.
  s = (int*) calloc(NJ, sizeof(int)); //utemterv
  job = (T_JOB*) calloc(NJ, sizeof(T_JOB)); //strukturavektor
  for (i=0; i<NJ; i++)
    {
      job[i].id = i;
      job[i].ProcT  = (long*) calloc(NR, sizeof(long)); //helyfoglalas
      job[i].StartT = (long*) calloc(NR, sizeof(long)); //helyfoglalas
      job[i].EndT   = (long*) calloc(NR, sizeof(long)); //helyfoglalas

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

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

   //Ad-hoc sorrend
    printf("\n Ad-hoc F|perm|Cmax feladatra.");
    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-algoritmus F2|perm|Cmax feladatra.");
    Johnson_alg(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);


    }


   if ( NR == 3 )
    {
    printf("\n Johnson-algoritmus F3|perm|Cmax feladatra.");
    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 F|perm|Cmax feladatra.");
    Dannenbring_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);



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

  getch();
  return 1;
}

void Simulation_F(T_JOB* job, int NJ, int NR, int* s, long t0)
{
  int i; //job index
  int r; //resource index

  for ( i=0; i<NJ; i++)
   for ( r=0; r<NR; r++)
    {
      if ( i==0 )
        { //kezdo munka
          if ( r==0 )
            { //kezdo gep
              job[ s[i] ].StartT[ r ] = t0; //ref. idoben indul
            }
          else
            { //nem kezdo gep
              job[ s[i] ].StartT[ r ] = job[ s[i] ].EndT[ r-1 ]; //elozo gepen a befejezes idopontja hatarozza meg
            }
        }
      else
        { //nem kezdo munka
          if ( r==0 )
            { //kezdo gep
              job[ s[i] ].StartT[ r ] = job[ s[i-1] ].EndT[ r ];  //elozo munka befejezese hatarozza meg az inditast
            }
          else
            { //nem kezdo gep
              //max azt mutatja, hogy melyik eset a dominans
              job[ s[i] ].StartT[ r ] = max(  job[ s[i] ].EndT[ r-1 ],
                                               job[ s[i-1] ].EndT[ r ] );
            }

        }

      //kesz = indit + dolgozik
     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 diagram:");
  for ( r=0; r<NR; r++)
  {
    printf("\n R_%d", r);
    printf("\n sor \t job \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)
{
 //utolso munka befejezesi idopontja az utolso gepen
 return job[ s[NJ-1] ].EndT[NR-1];  //Cmax
}

void Johnson_alg(T_JOB* job, int NJ, int r, int* s)
{
  int i, j;  //munkak indexelese a rendezeshez
  int* v;    //elorendezeshez
  int min_index;   //legkisebb elem indexe a meg rendezetlenek kozul
  long min_val;    //legkisebb elem erteke a meg nem rendezetlenek kozul
  long act_val;
  int temp;
  int first, last;  //beszurashoz

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

  //elokeszito resz: elorendezes
  for ( i=0; i<NJ; i++) //inicializalas
    v[i] = i;

  //rendezes SPT szabaly
  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++)   //vizsgalja a jelolteket
     {
       act_val   = min ( job[ v[ j ] ].ProcT[ r ],
                         job[ v[ j ] ].ProcT[ r+1 ] );

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

     if ( min_index != i )
      { //csere szukseges
        temp   = v[ i ];
        v[ i ] = v[ min_index ];
        v[ min_index ] = temp;

      }
  } //rendezes kesz

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

   for ( i=0; i<NJ; i++ ) //v rendezett vektor szerint
    {
        if ( job[ v[i] ].ProcT[r] < job[ v[i] ].ProcT[r+1] )
          {  //az utemterv elejere a mar beutemyettek moge
             s[ first ] = v[ i ];  //beutemezes
             first++;
          }
          else
          {  //az utemterv vegere a mar beutemezettek ele
             s[ last ] = v[ i ]; //beutemezes
             last--;
          }
      //printf("\n %d", v[i]);
    }


  free( v ); //felszabaditas
}

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

  V2_job = (T_JOB*) calloc(NJ, sizeof(T_JOB) );
  for (i=0; i<NJ; i++)
   {
       //kizarolag a muveleti idoket hasznaljuk
       V2_job[i].ProcT = (long*) calloc(2, sizeof(long));
       //transzformacio
       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];
   }

   //virtualis gepekre alkalmazom a Johnson-algoritmust
   Johnson_alg(V2_job, NJ, 0, s);


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

  free( V2_job);
}

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

  V2_job = (T_JOB*) calloc(NJ, sizeof(T_JOB) );
  for (i=0; i<NJ; i++)
   {
       //kizarolag a muveleti idoket hasznaljuk
       V2_job[i].ProcT = (long*) calloc(2, sizeof(long));

       //transzformacio
       //virtualis elso gep
       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=0 miatt
       //virtualis masodik gep
       V2_job[i].ProcT[1] = 0;
       for ( j=0; j<NR; j++)
           V2_job[i].ProcT[1] += (j+1)*job[i].ProcT[j];

   }

   //virtualis gepekre alkalmazom a Johnson-algoritmust
   Johnson_alg(V2_job, NJ, 0, s);


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

  free( V2_job);
}