/*-------------------------------------------------------------------------------
1.
F2|permut|max(Ci)  Utemezesi fedadat megoldasa Johnson-algoritmus alkalmazásával.
Kétgépes egyutas előzés nélküli termelésiütemezési feladat.
Az ütemezés célja a legkésőbbi befejezési időpont minimalizálása, 
ezáltal a teljes rendeléscsoport átfutási idejének minimalizálása.
A megoldás optimális ütemtervet eredményez.
2.
F|permut|max(Ci)  Utemezesi fedadat megoldasa CDS-algoritmus alkalmazásával.
Többgépes egyutas előzés nélküli termelésiütemezési feladat.
Az ütemezés célja a legkésőbbi befejezési időpont minimalizálása, 
ezáltal a teljes rendeléscsoport átfutási idejének minimalizálása.
CDS-algoritmus:
A Campbell-Dudek-Smith algoritmus a többgépes feladatot kétgépes problémákra
vezeti vissza. 
Az algoritmus az eredeti m gépes feladatból m-1 darab mesterséges kétgépes problémát generál
úgy, hogy az egymást követő gépek lesznek a kétgépes feladat gépei.
A kétgépes feladatok egyenként megoldhatók a Johnson-algoritmussal.
Kiválasztva közülük a teljes feladatra vonatkozó átfutási idő szempontjából 
a legjobbat, az lesz az m-gépes probléma megoldása.
A megoldás nem optimális mert a feladat NP-hard, de jó közelítő ütemtervet eredményez.
-------------------------------------------------------------------------------*/

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

typedef struct{
                long id,
                     * SetT,
                     * ProcT,
                     * OptT,
                     * StartT,
                     * EndT;
              }T_JOB;


long simulation(int* S, T_JOB* job, int n, int m, long ref_T);
void job_print(int* Sch, T_JOB* job, int n, int m);
void sim_data_print(int* Sch, T_JOB* job, int n, int m);
void Johnson_ald(int* Sch, T_JOB* job, int n, int x, int y );

int main(int argc, char* argv[])
{
 T_JOB* job;
 int n; //jobok darabszama
 int m; //gepek szama
 int i; //job futoindex
 int j; //gepek futoindex
 int * Sch; //utemterv
 int *r;  //rendezes Johnson alg. elott
 int x, y; //elso masodik Johnson
 long Cmax; //maximalis befejezesi ido
 long Cbest; //kereses soran legjobb celfv ertek
 int *Sch_best; //kereses soran talalt legjobb megoldas
 //virtualis adatbazis lekerdeze
 randomize();
 printf("\n Kerem a jobok szamat:");
 scanf("%d", &n); //n erteket kap bill-rol

 printf("\n Kerem a gepek szamat:");
 scanf("%d", &m); //m erteket kap bill-rol

 job = (T_JOB*) calloc(n, sizeof(T_JOB) );
 randomize();
 for (i=0; i<n; i++)
 {
  job[i].id = i;
  job[i].SetT = (long*) calloc(m, sizeof(long));
  job[i].ProcT = (long*) calloc(m, sizeof(long));
  job[i].OptT = (long*) calloc(m, sizeof(long));
  job[i].StartT = (long*) calloc(m, sizeof(long));
  job[i].EndT = (long*) calloc(m, sizeof(long));

  for (j=0; j<m; j++)
    {
     job[i].SetT[j] = random (10) + 10;
     job[i].ProcT[j] = random (100) + 10;
     job[i].OptT[j] = job[i].SetT[j] + job[i].ProcT[j];
     }
  }

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

  Sch_best = (int*) calloc(n, sizeof(int));

  //CDS
  for (j=0; j<m-1; j++) //0-1  1-2 ...(m-1)-m
  {
   Johnson_ald(Sch, job, n, j, j+1 );
   Cmax = simulation(Sch, job, n, m, 0);
   printf("\n %d. megoldas: \n \t Cmax=%ld",j, Cmax);

   if (j==0)
     {
      Cbest = Cmax;
       for(i=0; i<n; i++)
          Sch_best[i]=Sch[i];

     }
   else
     {
      if ( Cbest > Cmax )
       {
         Cbest = Cmax;
         for(i=0; i<n; i++)
            Sch_best[i]=Sch[i];

       }
     }
  }

  for(i=0; i<n; i++)
     Sch[i]=Sch_best[i];


  //kiindulasi adatok
  job_print(Sch, job, n, m);


  //megoldas

  //szimulacio
  Cmax = simulation(Sch, job, n, m, 0);
  printf("\n \n \t Cmax=%ld", Cmax);

  //eredmeny
  sim_data_print(Sch, job, n, m);

 for (i=0; i<n; i++)
  {
   free( job[i].SetT );
   free( job[i].ProcT );
   free( job[i].OptT );
   free( job[i].StartT );
   free( job[i].EndT );
  }
  free( job );
  free( Sch );
  free( Sch_best );


 getch();
 return 1;
}

long simulation(int* S, T_JOB* job, int n, int m, long ref_T)
{ //n munka m gepen sch sorrendben
  int i, j;

  for ( i=0; i<n; i++ )
   for ( j= 0; j<m; j++ )
   {
    if ( i == 0 )
    {
      if ( j == 0 )
      {
       job[S[i]].StartT[j] = ref_T;
      }
      else
      { //kezdo munka nem kezdo gepen
        job[S[i]].StartT[j] = job[S[i]].EndT[j-1];
      }
    }
    else //nem kezdo munka
    {
      if (m==0)
      { //kezdo gep
         job[S[i]].StartT[j] = job[S[i-1]].EndT[j];
      }
      else
      { //nem kezdo gep               //elozo gepen          //elozo munka
         job[S[i]].StartT[j] = max( job[S[i]].EndT[j-1] , job[S[i-1]].EndT[j] );

      }
    }//if i
    job[S[i]].EndT[j] = job[S[i]].StartT[j]
                           + job[S[i]].OptT[j];

   }//for
  return job[S[n-1]].EndT[m-1];
}

void job_print(int* Sch, T_JOB* job, int n, int m)
{
 int i, j;
 printf("\n Idoadatok:\n");
 for (j=0; j<m; j++)
  {
   printf("\n %d_Operacio:", j);

   for (i=0; i<n; i++ )
   {
    printf("\n \t jobid=%d \t %ld", Sch[i], job[Sch[i]].OptT[j]);
   }
  }
}

void sim_data_print(int* Sch, T_JOB* job, int n, int m)
{
 int i, j;
 printf("\n Idoadatok:\n");
 for (j=0; j<m; j++)
  {
   printf("\n %d_Operacio:", j);

   for (i=0; i<n; i++ )
   {
    printf("\n \t %d \t %ld \t %ld \t %ld", Sch[i], job[Sch[i]].OptT[j], job[Sch[i]].StartT[j], job[Sch[i]].EndT[j]);
   }
  }
}

void Johnson_ald(int* Sch, T_JOB* job, int n, int x, int y )
{
 int i, j, temp;
 int b, l;
 long ti, tj;
 int *r = (int *) calloc(n, sizeof(int));
 for (i=0; i<n; i++)
   r[i] = Sch[i];

 for (i=0; i<n-1; i++)
   for (j=i+1; j<n; j++ )
   {
    ti = min( job[r[i]].OptT[x], job[r[i]].OptT[y] );
    tj = min( job[r[j]].OptT[x], job[r[j]].OptT[y] );
    if ( ti > tj)
     {
      temp = r[i];
      r[i] = r[j];
      r[j] = temp;
     }

   }

   b=0;
   l=n-1;

   for(i=0; i<n; i++)
    if ( job[r[i]].OptT[x] < job[r[i]].OptT[y])
     {
      Sch[b]=r[i];
      b++;
     }
    else
    {
     Sch[l]=r[i];
     l--;
    }


 free(r);
}