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



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


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


}