/*-------------------------------------------------------------------------------
F|perm|max(Ci)  Ütemezési fedadat szimulációja.
Egyutas többoperációs termelésütemezési feladat.
F2|perm|max(Ci)  Ütemezési fedadat megoldása Johnson-algoritmussal.
Az algoritmus optimális megoldást eredményez.
(Táblára felírt módszer: F3|perm|max(Ci) feladatra a Johnson-algoritmus kiterjeszthető!)
-------------------------------------------------------------------------------*/

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

typedef struct {
                int id;
                long int* SetT,  /*beallitasi idok, setup times*/
                        * ProcT, /*muveleti idok, processing times*/
                        * OpT,   /*operaciok teljes ideje, operation times*/
                        * StartT,/*kezdesi idopontok, starting times*/
                        * EndT;  /*befejezesi idopontok, ending times */
                 long   D,       /*hatarido*/
                        L;       /*keses*/
                }T_JOB;

typedef struct {
                int id;
                int l;      /*gephez rendelt munkak szama, load*/
                long int C; /*a gep utolso munkajanak befejezesi idopontja, completion time*/
               }T_MACHINE;

typedef struct {
               long Cmax, /*utolso munka bef. idopontja*/
                    Csum; /*bef. idok osszege*/
               double MUav; /*atlagos gepkihasznaltsag*/
               }T_OBJF;    /*celfuggvenyek*/

long simulation_FS(T_JOB* job, int* sch, int NJ, int NM, long t);
void print_objf(T_OBJF* objf);
void Johnson_alg(T_JOB* job, int* sch, int NJ, int x, int y);
void print_Gantt(T_JOB* job, int* sch, int NJ, int NM);


int main(int argc, char* argv[])
{
  long Cmax;
  int NJ; /* munkak szama*/
  int NM; /* gepek szama*/
  T_MACHINE * mach;
  int i, j;
  T_JOB* job; /* strukturavektorra mutato*/
  int* sch; /* utemterv */
  T_OBJF objf;
  /* modellepites, utemezes, szimulacio, ertekeles*/

  /*modellepites*/
  printf("\n Kerem a munkak aktualis szamat:");
  scanf("%d", &NJ);

  printf("\n Kerem a gepek aktualis szamat:");
  scanf("%d", &NM);

  job = (T_JOB*) calloc(NJ, sizeof(T_JOB));
  randomize();
  for (i=0; i<NJ; i++)
   {
    job[i].id = i;

    job[i].SetT = (long*) calloc(NM, sizeof(long int));
    job[i].ProcT = (long*) calloc(NM, sizeof(long int));
    job[i].OpT = (long*) calloc(NM, sizeof(long int));
    job[i].StartT = (long*) calloc(NM, sizeof(long int));
    job[i].EndT = (long*) calloc(NM, sizeof(long int));

    for (j=0; j<NM; j++)
    {
    job[i].SetT[j] = 1 + random(10);
    job[i].ProcT[j] = 1 + random(100);
    job[i].OpT[j] = job[i].SetT[j] + job[i].ProcT[j];
   }
    job[i].D = 1 + random(50) + NM * job[i].OpT[0]*random(5);
  }

  /*utemezes*/
     sch = (int*) calloc(NJ, sizeof(int));

  /* gepek */
  mach = (T_MACHINE*) calloc(NM, sizeof(T_MACHINE));

  /*Ad-hoc sorrend*/
  for(i=0; i<NJ; i++)
   sch[i]=i;

  Cmax = simulation_FS(job, sch, NJ, NM, 0);
  print_Gantt(job, sch, NJ, NM);
  printf("\n AD-HOC sorrend: Cmax=%ld \n", Cmax);
  /*print_Gantt(job, sch, NJ, NM);*/

  Johnson_alg(job, sch, NJ, 0, 1);
  Cmax = simulation_FS(job, sch, NJ, NM, 0);
  print_Gantt(job, sch, NJ, NM);
  printf("\n JOHNSON sorrend: Cmax=%ld \n", Cmax);


  printf("\n Vege!");
  getch();

  free(sch);

  for (i=0; i<NJ; i++)
   {
    free( job[i].ProcT);
    free( job[i].OpT);
    free( job[i].SetT);
    free( job[i].StartT);
    free( job[i].EndT);
    }
 free(job);
 free(mach);

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

long simulation_FS(T_JOB* job, int* sch, int NJ, int NM, long t)
{
 int i, /*job futoindex*/
     m; /*gep futoindex*/

 for (i=0; i<NJ; i++)
  for (m=0; m<NM; m++)
  {
   if ( i==0 ) /*kezdo munka*/
   {
     if ( m==0 ) /*kezdo gep*/
     {
       job[sch[i]].StartT[m] = t; /*kezdes a referencia idopontban*/
     }
     else /*nem kezdo gep*/
     {
       job[sch[i]].StartT[m] =  job[sch[i]].EndT[ m-1 ]; /* elozo geprol erkezik*/
     }
   }
   else /*nem kezdo munka*/
   {
     if (m==0) /*kezdo gep*/
     {
       job[sch[i]].StartT[m] = job[sch[i-1]].EndT[m];   /* kezdo gep nem varakozik*/
     }
     else /*nem kezdo gep*/
     {
      job[sch[i]].StartT[m] = max( job[sch[i]].EndT[m-1], job[sch[i-1]].EndT[m]);
     }
   }
  job[sch[i]].EndT[m] = job[sch[i]].StartT[m] + job[sch[i]].OpT[m]; /*befejezes idopont*/
  }
return job[sch[NJ-1]].EndT[NM-1];
}



void print_objf(T_OBJF* objf)
{
 printf("\n Csum= %ld", objf->Csum);
 printf("\n Cmax= %ld", objf->Cmax);
}

void Johnson_alg(T_JOB* job, int* sch, int NJ, int x, int y)
{
  int* r;
  int i, j, temp;
  int e, v;
  r = (int*) calloc(NJ, sizeof(int));
  for(i=0; i<NJ; i++)
    r[i]=i;

    /*rendezes*/
    for(i=0; i<NJ-1; i++)
     for(j=i+1; j<NJ; j++)
       if ( min(job[r[i]].OpT[x], job[r[i]].OpT[y])
            >
            min( job[r[j]].OpT[x], job[r[j]].OpT[y] )  )
        {  /*csere*/
         temp = r[i];
         r[i] = r[j];
         r[j] = temp;
        }
     e=0; v=NJ-1;
     for(i=0; i<NJ; i++)
     {
       if ( job[r[i]].OpT[x] < job[r[i]].OpT[y] )
          { sch[e]=r[i];
            e++;
          }
        else
          {
           sch[v]=r[i];
           v--;
          }
     }
  free(r);
}

void print_Gantt(T_JOB* job, int* sch, int NJ, int NM)
{
 int i;
 int m;
 for (m=0; m<NM; m++)
 {

 printf("\n machine_%d \n", m);
 printf("\n n: job_id \t StarT \t OpT \t EndT \n ");

 for ( i=0; i<NJ; i++)
 {
  printf("\n %d: job_%d \t %ld \t %ld \t %ld",
  i,
  sch[i],
  job[ sch[i]].StartT[m],
  job[ sch[i]].OpT[m],
  job[ sch[i]].EndT[m]);

 }

 }//m
}