/*-------------------------------------------------------------------------------
F|perm|max(Ci)  Ütemezési fedadat szimulációja.
Egyutas előzésnélküli többoperációs termelésütemezési feladat.
A Simulation_FS 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.

F2|perm|max(Ci) Ütemezési fedadat megoldása Johnson-algoritmussal. 

Az algoritmus optimális megoldást eredményez.
-------------------------------------------------------------------------------*/


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

typedef struct {
                 int id;
                 long* ProcT; //vektor
                 long* StartT; //vektor
                 long* EndT;   //vektor
               }T_JOB;

void Simulation_FS( T_JOB* job, int NJ, int NM, int* s, long t_ref );
long Evaluation_FS( T_JOB* job, int NJ, int NM, int* s);
void Print_Machine_Gantt( T_JOB* job, int NJ, int NM, int* s);

void Johnson_Alg( T_JOB* job, int NJ, int* s, int m1, int m2 );


int main(int argc, char* argv[])
{
  int i, NJ; //number of jobs
  int m, NM; //number of machines

  T_JOB* job;  //jobs
  int* s;      //schedule
  long Cmax;   //befejezesi idopont

  printf("\n Flow Shop feladat szimulacioja");
  printf("\n Munkak szama: ");
  scanf("%d", &NJ);
  printf("\n Gepek szama: ");
  scanf("%d", &NM);

  //munkak
  job = (T_JOB*) calloc( NJ, sizeof(T_JOB));
  for ( i=0; i<NJ; i++)
    {
       job[i].id = i;  //azonosito
       job[i].ProcT  = (long*) calloc( NM, sizeof(long) );
       job[i].StartT = (long*) calloc( NM, sizeof(long) );
       job[i].EndT   = (long*) calloc( NM, sizeof(long) );

       //technologiai terv definialja
       for ( m=0; m<=NM; m++ )
          job[i].ProcT[m] = 1 + rand()%10;

    }

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

  printf("\n Ad-hoc ");
  Simulation_FS( job, NJ, NM, s, 0 );
  Cmax = Evaluation_FS( job, NJ, NM, s );
  Print_Machine_Gantt( job, NJ, NM, s);
  printf("\n Cmax = %ld", Cmax);

  printf("\n Johnson sorrend");
  Johnson_Alg( job, NJ, s, 0, 1 ); //ket kezdo gep: m1=0; m2=1;
  Simulation_FS( job, NJ, NM, s, 0 );
  Cmax = Evaluation_FS( job, NJ, NM, s );
  Print_Machine_Gantt( job, NJ, NM, s);
  printf("\n Cmax = %ld", Cmax);

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


  getch();
  return 0;
}
//---------------------------------------------------------------------------

void Simulation_FS( T_JOB* job, int NJ, int NM, int* s, long t_ref )
{
  int i, m;

  for ( i=0; i<NJ; i++)
    {
      for( m=0; m<NM; m++)
        {
          if ( i == 0 )
            { //kezdo munka
             if ( m == 0 ) //kezdo gep
                job[s[i]].StartT[m] = t_ref; //referencia idopont
             else          //kozbenso gep
                //elozo muvelet befejezodott
                job[s[i]].StartT[m] = job[s[i]].EndT[m-1];
            }
           else
            { //kozbenso munka
             if ( m == 0 )
                //elozo munka befejezodott
                job[s[i]].StartT[m] = job[s[i-1]].EndT[m];
             else
                //elozo muvelet befejezodott
                //elozo munka befejezodott
                job[s[i]].StartT[m] = max ( job[s[i]].EndT[m-1],
                                            job[s[i-1]].EndT[m] );
            }

          job[s[i]].EndT[m] = job[s[i]].StartT[m] +
                              job[s[i]].ProcT[m];
        }
    }

}

long Evaluation_FS( T_JOB* job, int NJ, int NM, int* s)
{ //az utolso munka befejezesi idopontja az utolso gepen
  return job[ s[NJ-1] ].EndT[NM-1];
}

void Print_Machine_Gantt( T_JOB* job, int NJ, int NM, int* s)
{
  int i, m;
  printf("\n Eroforras-orientalt Gantt diagram");
  for ( m=0; m<NM; m++)
    {
       printf("\n %d. gep:");
       printf("\n \t sz \t munka \t indul \t muv. \t bef.");
       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[m],
                    job[s[i]].ProcT[m],
                    job[s[i]].EndT[m]);
    }

}

void Johnson_Alg( T_JOB* job, int NJ, int* s, int m1, int m2 )
{
 int i, j;  //munkak futoindexe
 int f, l;  //first eleje, last vege
 int* r;    //elozetes rendezes
 int temp;  //cserehez

 //memoria foglalas
 r = (int*)  calloc(NJ, sizeof(NJ));
 //inicializalas
 for (i=0; i<NJ; i++)
   r[i] = i;
 //rendezes idoadatok szerint nemcsokkeno sorrendbe
 for (i=0; i<NJ-1; i++)
   for(j=i+1; j<NJ; j++)
     if ( min( job[ r[i] ].ProcT[m1], job[ r[i] ].ProcT[m2])
          >
          min( job[ r[j] ].ProcT[m1], job[ r[j] ].ProcT[m2])
        )
        { //csere
          temp = r[i];
          r[i] = r[j];
          r[j] = temp;
        }

  //utemterv
  f = 0;
  l = NJ-1;

  for(i=0; i<NJ; i++)
   {
     if ( job[ r[i] ].ProcT[m1]
          <=
          job[ r[i] ].ProcT[m2]
        )
        { //elore a mar beutamezettek moge
          s[ f ] = r[i];
          f++;  //kovetkezo szabad pozicio
        }
     else
        { //hatre a mar beutemezettek ele
          s[ l ] = r[i];
          l--;  //szabad pozicio
        }
   }

 free(r);
}