/*
  F|perm|Cmax ütemezési feladat heurisztikus megoldasa.
  Egyutas előzésnélküli, többoperációs termelésütemezési feladat.
  Szimuláció.
    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.

  Speciális eset:
  F2|perm|Cmax Ütemezési fedadat megoldása Johnson-algoritmussal.
  A Johnson_alg fv optimális megoldást eredményez (két gép esetében).
*/

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

#define NObjF 1

typedef struct {
                int id;       //azonosito
                long* ProcT;  //muveleti idok
                long* StartT; //muvelet inditas
                long* EndT;   //muvelet befejezese

               } T_JOB; //type of job

void Simulation_FS(T_JOB* job, int NJ, int NM, int* s, long t_ref);
void Print_Job_Gantt(T_JOB* job, int NJ, int NM, int* s);
void Evaluation(T_JOB* job, int NJ, int NM, int* s, double* ObjF);
void Print_ObjF(double* ObjF);
void Johnson_alg(T_JOB* job, int NJ, int NM, int* s, int m1, int m2);

int main(int argc, char* argv[])
{
  int NJ;     //number of jobs, munkak szama
  int NM;     //number of machine, gepek szama
  int i, m;   //futoindex
  T_JOB* job;  //munkak adatai
  int* sch;    //schedule, utemterv
  long t_ref;  //folyamat inditasanak idopontja
  double* ObjF; //objective function, celfuggveny

  ObjF = (double*) calloc(NObjF, sizeof(double) ); //vektor

  printf("\n F|perm|Cmax utemezesi feladat demo!");
  printf("\n Munkak szama:");
  scanf("%d", &NJ);

  printf("\n Gepek szama:");
  scanf("%d", &NM);

  printf("\n Inditas idopontja: (pl. 5)");
  scanf("%ld", &t_ref);


  //Modellepeites
  job = (T_JOB*) calloc(NJ, sizeof(T_JOB) ); //strukturavektor

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

      //CAPP-bol lekerdezett idoadatok
      for( m=0; m<NM; m++)
        job[i].ProcT[m] = 1 + rand()%20;  //muveleti ido erteke indoegysegben
   }


  sch = (int*) calloc(NJ, sizeof(int) ); //vektor
  //ad-hoc sorrenddel inicializalva
  for( i=0; i<NJ; i++)
      sch[i] = i;

  printf("\n Ad-hoc sorrend:");
  //szimulacio
  Simulation_FS(job, NJ, NM, sch, t_ref);
  //Print_Job_Gantt(job, NJ, NM, sch);

  //kiertekeles
  Evaluation(job, NJ, NM, sch, ObjF);
  Print_ObjF(ObjF);


 if ( NM >= 2 )
  {
   printf("\n Johnson sorrend a 0. es 1. gepre alapozva:");
   Johnson_alg(job, NJ, NM, sch, 0, 1);
   Simulation_FS(job, NJ, NM, sch, t_ref);
   //Print_Job_Gantt(job, NJ, NM, sch);
   Evaluation(job, NJ, NM, sch, ObjF);
   Print_ObjF(ObjF);
  }

  getch();


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

  return 0;
}
//---------------------------------------------------------------------------

void Simulation_FS(T_JOB* job, int NJ, int NM, int* s, long t_ref)
{
  //a szimulacio vegrehajtas-vezerelt modon valosul meg,
  //nem valos esemeny-vezerelt logika szerint

  int i, m; //i: inditas sorszama

  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;
           else  //nem kezdo gep, kozbenso
              job[ s[i] ].StartT[ m ] = job[ s[i] ].EndT[ m-1 ];
              //anyagmozgatas ideje elhanyagolhato, ha nem + TravlT

        }
      else
        {  //nem kezdo, kozbenso
           if ( m==0 )  //kezdo gep
              job[ s[i] ].StartT[ m ] = job[ s[i-1] ].EndT[ m ];
              //setup ido elhanyagolhato, vagy benne van a ProcT-ben
              //ha nem + SetupT
           else  //nem kezdo gep, kozbenso
              job[ s[i] ].StartT[ m ] = max( job[ s[i] ].EndT[m-1],  //elozo geprol mikor erkezik
                                             job[ s[i-1]].EndT[m] );  //a gep mikor szabadul fel

        }

       job[ s[i] ].EndT[ m ] =   job[ s[i] ].StartT[ m ]  //inditas
                               + job[ s[i] ].ProcT[ m ]; //muvleti ido

    }


}

void Print_Job_Gantt(T_JOB* job, int NJ, int NM, int* s)
{
   int i, m;
   printf("\n Munkak vegrehajtasi idoadatai:");
   for( i=0; i<NJ; i++ )
    {
      printf("\n %d. munka", s[i]);
      printf("\n gep \t Kezd \t Muv. \t Bef.");
      for( m=0; m<NM; m++)
      {
        printf("\n %d \t %ld \t %ld \t %ld"
              ,m
              ,job[ s[i] ].StartT[m]
              ,job[ s[i] ].ProcT[m]
              ,job[ s[i] ].EndT[m]);
      }
    }

}

void Evaluation(T_JOB* job, int NJ, int NM, int* s, double* ObjF)
{
  int f; //futoindex
  for ( f=0; f<NObjF; f++)
      ObjF[f] = 0.0;

  //0 rekesze legyeb a Cmax
  ObjF[0] = job[ s[NJ-1] ].EndT[ NM-1 ];
  //tovabbi celfv-k szamitasa...
}

void Print_ObjF(double* ObjF)
{
  int f; //futoindex
  for ( f=0; f<NObjF; f++)
      printf("\n %d. celfv: %lf", f, ObjF[f]);

}

void Johnson_alg(T_JOB* job, int NJ, int NM, int* s, int m1, int m2)
{
  int* r; //segedvektor
  int i, j, temp;
  int first, last; //firrst, last

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

  //1. fazis elorendezes
  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;
      }

  //utemezes
   first = 0;
   last = NJ-1;
   for( i=0; i<NJ; i++)
    {
      if ( job[ r[i] ].ProcT[m1] <= job[ r[i] ].ProcT[m2] )
        {
           s[first] = r[i];
           first++;
        }
     else
        {
           s[last] = r[i];
           last--;
        }
    }


  free(r);

}