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

TIA gyakorlat 08
Oktatási szünet

TIA gyakorlat 09
F3|perm|Cmax ütemezési feladat 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ó!

TIA gyakorlat 10
Fm|perm|Cmax ütemezési feladat megoldása
Palmer-algoritmus
Dannenbring-algoritmus

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

#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 F3_Johnson_alg_ext(T_JOB* job, int NJ, int r, int* s);
void Fm_Palmer_alg(T_JOB* job, int NJ, int NR, int* s);
void Fm_Dannenbring_alg(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;
  int r_value;



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



    }

   //F3 eseten
   if (NR == 3)
    {
       printf("\n\n F3 esetre a Johnson-algoritmus");
       r_value = F3_Johnson_alg_ext(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);


       if ( r_value == 1 )
          printf("\n A megoldas optimalis.");
       else
          printf("\n Az optimalis megoldas elerese nem garantalt.");

    }

       printf("\n\n Fm esetre a Palmer-algoritmus");
       Fm_Palmer_alg(job, NJ, NR, 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);


       printf("\n\n Fm esetre a Dannenbring-algoritmus");
       Fm_Dannenbring_alg(job, NJ, NR, 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 ];
}

int F3_Johnson_alg_ext(T_JOB* job, int NJ, int r, int* s)
{
  T_JOB* V2_job;  //virtualis ketgepes kornyezet
  int i;          //job index

  long min_pi0, min_pi2, max_pi1;


  //Transzformacio virtualis ketgepes rendszerre
  V2_job = (T_JOB*) calloc(NJ, sizeof(T_JOB));
    for( i=0; i<NJ; i++ )
   {
      V2_job[i].ProcT = (long*) calloc(2, sizeof(long));  //tomb

       V2_job[i].ProcT[0] = job[i].ProcT[r] + job[i].ProcT[r+1];
       V2_job[i].ProcT[1] = job[i].ProcT[r+1] + job[i].ProcT[r+2];
   }

   //Johnson-algoritmus
   Johnson_alg(V2_job, NJ, 0, s);

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

    free( V2_job );


   min_pi0 = job[0].ProcT[0];
   min_pi2 = job[0].ProcT[2];
   max_pi1 = job[0].ProcT[1];

   for ( i=1; i<NJ; i++ )
    {
      if ( min_pi0 > job[i].ProcT[0] )
          min_pi0 = job[i].ProcT[0];

      if ( min_pi2 > job[i].ProcT[2] )
          min_pi2 = job[i].ProcT[2];

      if ( max_pi1 < job[i].ProcT[1] )
          max_pi1 = job[i].ProcT[1];
    }


    if ( min_pi0 >= max_pi1 || min_pi2 >= max_pi1 )
       return 1;  //optimalis a megoldas
    else
       return 0;  //nem garantalhato az optimum elerese

}

void Fm_Palmer_alg(T_JOB* job, int NJ, int NR, int* s)
{
   int i,k;    //munka index
   int j;      //operacio (egyben a gep) index
   int index;  //rendezes segedvaltozoja
   int temp;   //csere segedvaltozoja

   double* I;  //Pa;mer-index

   //mkem. foglalas
   I = (double*) calloc(NJ, sizeof(double) );   //tomb

   //1. fazis: Pa;mer-indexek szamitasa
   for (i=0; i<NJ; i++)
    {
      I[i]=0.0;

      for (j=0; j<NR; j++)
          I[i] -= job[i].ProcT[j] * (NR - (2*(j+1) - 1))/2.0;
    }

    
   //2. fezis: rendezes
   for (i=0; i<NJ; i++)
      s[i] = i;            //inicializalas

   for (i=0; i<NJ-1; i++)     // i az s tomb indexe
   {
     index = i;
     for ( k=i+1; k<NJ; k++)
        if ( I[ s[i] ] < I[ s[k] ] )
            index = k;

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

       }
   }

   //mem. felszabaditas
   free(I);
}

void Fm_Dannenbring_alg(T_JOB* job, int NJ, int NR, int* s)
{
  T_JOB* V2_job;  //virtualis ketgepes kornyezet
  int i;          //job index
  int j;          //muvelet (es a gep) indexe

 //Transzformacio virtualis ketgepes rendszerre
  V2_job = (T_JOB*) calloc(NJ, sizeof(T_JOB));
  for( i=0; i<NJ; i++ )
   {
      V2_job[i].ProcT = (long*) calloc(2, sizeof(long));  //tomb

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

       V2_job[i].ProcT[1] = 0;
       for( j=0; j<NR; j++ )
          V2_job[i]. ProcT[1] += (j+1)*job[i].ProcT[j];
   }

   //Johnson-algoritmus
   Johnson_alg(V2_job, NJ, 0, s);

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

    free( V2_job );

}