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

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

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


    }

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