/*
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 08
F2|perm|Cmax ütemezési feladat megoldása Johnson-algoritmussal.
Az algoritmus optimális megoldást eredményez (két gép esetén).

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ó!

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

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

//---------------------------------------------------------------------------

typedef struct {
                int id;  //azonosito
                long* ProcT; //muveleti idok listajara mutato pointer
                long* StartT; //inditasi idopont --||--
                long* EndT;   //befejezesi idopont --||--
               }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 Simulation_FS( T_JOB* job, int NJ, int NR, int* s, long t0);
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);
void Johnson_alg(T_JOB* job, int NJ, int r, int* s);
long Evaluate(T_JOB* job, int NJ, int NR, int* s);
int F3_Johnson_alg_ext(T_JOB* job, int NJ, int r, int* s);




int main(int argc, char* argv[])
{
  int NJ; //munkak szama
  int i;  //munka indexe
  int NR; //munkahelyek (eroforrasok) szama
  int r;  //munkahely indexe
  T_JOB* job;
  int* s; //kozos utemterv minden gepre, mert a munkak nem elozheti meg egymast
  int r_value;

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

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

  s = (int*) calloc(NJ, sizeof(int) ); //utemterv
  job = (T_JOB*) calloc(NJ, sizeof(T_JOB) );
  for( i=0; i<NJ; i++)
   {
     job[i].id = i;
     job[i].ProcT = (long*) calloc(NR, sizeof(long));  //muveleti idok gepenkent
     for (r=0; r<NR; r++)
        job[i].ProcT[r] = 1 + rand()%100;

     job[i].StartT = (long*) calloc(NR, sizeof(long));  //inditasi idopontok gepenkent
     job[i].EndT = (long*) calloc(NR, sizeof(long));  //befejezesi idopontok gepenkent

    //i] = i; //ad-hoc sorrend
    s[i] = NJ-i-1; //forditott ad-hoc sorrend
   }

   //ad-hoc sorrend szimulacioja
   printf("\n Ad-hoc sorrend");
   Simulation_FS( job, NJ, NR, s, 0);
   //print_Res_Gantt( job, NJ, NR, s);
   //print_Job_Gantt( job, NJ, NR, s);
   printf("\n Cmax = %ld", Evaluate(job, NJ, NR, s) );

   if ( NR == 2 )
    { //F2|perm|Cmax
      printf("\n Jonhson sorrend");
      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);
      printf("\n Cmax = %ld", Evaluate(job, NJ, NR, s) );

    }

   if ( NR == 3 )
   {  //F3|perm|Cmax
      printf("\n Kiterjesztett Jonhson sorrend");
      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);
      printf("\n Cmax = %ld", Evaluate(job, NJ, NR, s) );
      if ( r_value == 1 ) printf("\n A megoldás optimális!");
      else printf("\n Nem garantalhato az optimum elerese.");
   }

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

  getch();
  return 0;
}

void Simulation_FS( T_JOB* job, int NJ, int NR, int* s, long t0)
{
  int i; //az inditas sorrendjenek indexe
  int r; //munkahely indexe, technologiai sorrendet koveti a gepek azonositoja

  for( i=0; i<NJ; i++ )
    for( r=0; r<NR; r++ )
      {
         if ( i==0 )
            { //kezdo munka
              if ( r==0 )
                { //kezdo gepen
                  job[s[i]].StartT[r] = t0;
                }
              else
                { //nem kezdo gepen
                  job[s[i]].StartT[r] = job[s[i]].EndT[r-1];
                }
            }
         else
            { //nem kezdo munka
              if ( r==0 )
                { //kezdo gepen
                  job[s[i]].StartT[r] = job[s[i-1]].EndT[r];
                }
              else
                { //nem kezdo gepen
                  job[s[i]].StartT[r] = max_l( job[s[i]].EndT[r-1],  //elozo geprol mikor erkezik
                                               job[s[i-1]].EndT[r] ); //elozo munka mikor fejezodik be
                }
            }

         //bef = indul + 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;
  int r;

  printf("\n Eroforras-orientalt Gantt adatok:");

  for ( r=0; r<NR; r++ )
  {
    printf("\n %d. munkahely:", r);
    printf("\n # \t munka \t indul \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;
  int r;

  printf("\n\n Munka-orientalt Gantt adatok:");

  for ( i=0; i<NJ; i++ )
  {
    printf("\n %d. munka vegrehajtasa:", s[i] );
    printf("\n # \t gep \t indul \t muv.\t bef.");
    for ( r=0; r<NR; r++ )
      printf("\n %d\t%d\t%ld\t%ld\t%ld",
                 r,
                 r,
                 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;
  int index, temp;
  long value, val_of_j;
  int* v;      //elorendezes
  int first, last;  //szabad helyek indexe

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

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

  //elorendezes
  for(i=0; i<NJ-1; i++)
  {
    index = i;
    value = min_l( job[ v[i] ].ProcT[r], job[ v[i] ].ProcT[r+1]);
    for(j=i+1; j<NJ; j++)
     {
       val_of_j = min_l( job[ v[j] ].ProcT[r], job[ v[j] ].ProcT[r+1]);

      if ( val_of_j < value )
         {
           index = j;
           value = val_of_j;
         }
     }

    if ( index != i ) //van jobb jelolt
      {  //csere
         temp = v[ index ];
         v[ index ] = v[ i ];
         v[ i ] = temp;
      }
  }

  //utemezes
  first = 0;    //eleje
  last = NJ-1;  //vege

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

     }

  }

  free( v );
}

long Evaluate(T_JOB* job, int NJ, int NR, int* s)
{
   //kihasznalva az F|perm|Cmax modell jellemzoit
   //Cmax = utolsokent inditott munka bef. ideje az utolso gepen
   return job[ s[NJ-1]].EndT[NR-1];
}

int F3_Johnson_alg_ext(T_JOB* job, int NJ, int r, int* s)
{

  int i;  //job index
  T_JOB* virt_job;
  long min_pi0, max_pi1, min_pi2;
  //virtualis F2 rendszer
  virt_job = (T_JOB*) calloc(NJ, sizeof(T_JOB));
  for ( i=0; i<NJ; i++ )
   {
      virt_job[i].ProcT = (long*) calloc(2, sizeof(long));

      //idoadatok transzformacioja
      virt_job[i].ProcT[0] = job[i].ProcT[r] +
                             job[i].ProcT[r+1];

      virt_job[i].ProcT[1] = job[i].ProcT[r+1] +
                             job[i].ProcT[r+2];

   }

   //Johnson algoritmus alkalmazása a virtuális környezetben
   Johnson_alg(virt_job, NJ, 0, s);

   //optimalitás feltétel vizsgálata
   min_pi0 = job[0].ProcT[0];
   max_pi1 = job[0].ProcT[1];
   min_pi2 = job[0].ProcT[2];

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

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

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

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

   free( virt_job );

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