/*-------------------------------------------------------------------------------
A termelésinformatikai alapjai c. tantrárgy GEIAK150-B
Miskolci Egyetem, Alkalmazott Informatikai Intézeti Tanszék
Dr. Kulcsár Gyula, egyetemi docens

TIA gyakorlat 06
Flow Shop modell
Sorba kapcsolódó munkahelyek szimulációja.
Egyutas előzésnélküli többoperációs ütemezési feladat.
1. rész:
Modellépítés és szimuláció.
A Simulation_FS függvény 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 gyakorlat 07
F2|perm|Cmax utemezesi feladat
megoldasa Johnson-algoritmussal.
Az algoritmus optimális megoldást eredményez (két gép esetén).

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

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

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

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 generate_job_data( T_JOB* job, int NJ, int NR);
void creat_adhoc_schedule(int* s, int NJ);
void Simulation_FS( T_JOB* job, int NJ, int NR, int* s, long* t0);
void Johnson_alg(T_JOB* job, int NJ, int r, int* s);
void print_Res_Gantt(T_JOB* job, int NJ, int NR, int* s);
void print_Job_Gantt(T_JOB* job, int NJ, int NR, int* s);
long Evaluate_FS(T_JOB* job, int NJ, int NR, int* s);





int main(int argc, char* argv[])
{
  int i;     //munka indexe
  int NJ;    //munkak szama
  int r;     //eroforrasok indexe
  int NR;    //eroforrasok (munkahelyek) szama
  T_JOB* job; //munkakra mutato pointer
  int* s;     //utemezesi vektor
  long Cmax;



  printf("\n Flow Shop modell");

  printf("\n Munkak szama = ");
  scanf("%d", &NJ);

  printf("\n Munkahelyek szama = ");
  scanf("%d", &NR);

  //feltelezzuk, hogy a munkahelyek azonositoja
  //a technologiai sorrend szerint van kiosztva

  job = (T_JOB*) calloc(NJ, sizeof(T_JOB) );
  for( i=0; i<NJ; i++ )
   {
      job[i].ProcT = (long*) calloc(NR, sizeof(long));  //tomb
      job[i].StartT = (long*) calloc(NR, sizeof(long));  //tomb
      job[i].EndT = (long*) calloc(NR, sizeof(long));  //tomb
   }

   //utemterv: dontesi valtozo
   s = (int*) calloc(NJ, sizeof(int));
   creat_adhoc_schedule(s, NJ);

   //muv. idok
   generate_job_data( job, NJ, NR);

   printf("\n Ad-hoc sorrend eseten:");
   Simulation_FS( job, NJ, NR, s, 0);
   Cmax = Evaluate_FS(job, NJ, NR, s);
   printf( "\n\n Cmax = %ld", Cmax);


   //F2 eseten
   if (NR == 2)
    {
       printf("\n\n Johnson-algoritmus");
       Johnson_alg(job, NJ, 0, s);
       Simulation_FS( job, NJ, NR, s, 0);
       print_Res_Gantt(job, NJ, NR, s);
       print_Job_Gantt(job, NJ, NR, s);
       Cmax = Evaluate_FS(job, NJ, NR, s);
       printf( "\n\n Cmax = %ld", Cmax);



    }

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

  free( s );


  printf("\n Vege! \n Bill. nyomasra kilep.");
  getch();
  
  return 0;
}
//---------------------------------------------------------------------------

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

  for (i=0; i<NJ; i++)
   {
     job[i].id = i;

     for( r=0; r<NR; r++)
       job[i].ProcT[r] = 1 + rand()%100;  //muv. idok


   }

}

void creat_adhoc_schedule(int* s, int NJ)
{
  int i;

  for (i=0; i<NJ; i++)
     s[i] = i;

}

void Simulation_FS( T_JOB* job, int NJ, int NR, int* s, long* t0)
{
   int i, r;

   for( i=0; i<NJ; i++ )
   { //i az inditasi sorrend indexe
     for( r=0; r<NR; r++ )
      {
        if ( i==0 )
         {  //kezdo munka
           if ( r==0 )
            {  //kezdo munkahely
               job[ s[i] ].StartT[r] = t0; //ref. idoben indul
            }
            else
            {  //nem kezdo munkahely
               job[ s[i] ].StartT[r] = job[ s[i] ].EndT[r-1]; //elozo munkahelyen a bef.

            }

         }
        else
         { //nem kezdo munka
           if ( r==0 )
            {  //kezdo munkahely
               job[ s[i] ].StartT[r] = job[ s[i-1] ].EndT[r]; //elozo munka bef.

            }
            else
            {  //nem kezdo munkahely
               job[ s[i] ].StartT[r] = max_l( job[ s[i] ].EndT[r-1], //elozo munkahlyen a bef.
                                            job[ s[i-1] ]. EndT[r] ); //elozo munka bef.

            }


         }
         //bef. idopont = kezd. idopont + muveleti ido
         job[ s[i] ].EndT[r] = job[ s[i] ].StartT[r]
                               + job[ s[i] ].ProcT[r]; 
      }

   }
}

void Johnson_alg(T_JOB* job, int NJ, int r, int* s)
{
   //Johnson-algoritmus F2|perm|Cmax feladatra
   int i; //job index
   int index; //kijelolt pozicio
   int j; //job index
   int* v;  //elorendezeshez
   long value, value_at_j;
   int temp;

   int first, last;

   v = (int*) calloc(NJ, sizeof(int));
   for( i=0; i<NJ; i++)
      v[i] = i;

  //1. fazis: elorendezes
  //Milyen sorrendben dontunk a munkakrol
   for( i=0; i<NJ-1; i++)
    {
       index = i; //ebbe a pozicioba keresem az elemet
       value = min_l( job[ v[index]  ].ProcT[r],
                      job[ v[index]  ].ProcT[r+1] );

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

          if ( value_at_j < value )
            { //jelolt
              index = j;
              value = value_at_j;
            }
        }

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

        }
    }


  //2. fazis: utemezes
  //Hova tegyuk a munkat
  first = 0;
  last = NJ-1;

  for ( i=0; i<NJ; i++)
   {
      if ( job[ v[i] ].ProcT[r] < job[ v[i] ].ProcT[r+1] )
        {  //az s vektor elejere a mar beutemezettek moge
          s[ first ] = v[i];  //beutemezem
          first++;
        }
      else
        {  //az s vektor vegere a mar beutemezettek ele
           s[ last ] = v[i];
           last--;
        }
   }


   free( v );


}

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

   printf("\n Eroforras-orientalt Gantt adatok:");
   for (r=0; r<NR; r++)
     {
       printf("\n %d. munkahely", r);
       printf("\n # \t munka \t kezd. \t muv. \t bef.");
       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]);

         }

     }
}

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

   printf("\n Munka-orientalt Gantt adatok:");
   for (i=0; i<NJ; i++)
     {
       printf("\n %d. munka", i);
       printf("\n # \t gep \t kezd. \t muv. \t bef.");
       for ( r=0; r<NR; r++ )
         {
           printf("\n %d \t %d \t %ld \t %ld \t %ld",
                   r,
                   r,
                   job[ i ].StartT[r],
                   job[ i ].ProcT[r],
                   job[ i ].EndT[r]);

         }

     }
}

long Evaluate_FS(T_JOB* job, int NJ, int NR, int* s)
{  //Flow Shop miatt a Cmax kozvetlenul lekerdezheto
   return job[ s[NJ-1] ].EndT[ NR-1 ];
}