/*-------------------------------------------------------------------------------
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.
void Johnson_alg(T_JOB* job, int N, int M, int* sch, int x, int y);


F3|perm|max(Ci) feladatra a Johnson-algoritmus kiterjeszthető!
Bizonyos feltételek teljesülése esetén a megoldás optimális, egyébként az optimalitás nem garantálható!
int Johnson_alg_3gepre(T_JOB* job, int N, int M, int* sch, int x);

Továbbfejlesztett modell:
F|permut|max(Ci)  Utemezesi fedadat:
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.


Dannenbring-algoritmus:
Az eredeti M-gépes problémából egy mesterséges kétgépes problémát generál úgy,
hogy a műveleti idők súlyozott lineáris kombinációjával állítja elő
a virtuális kétgépes probléma időadatait.
A kétgépes feladat megoldható a Johnson-algoritmussal és ez adja az eredeti probléma megoldását. .
-------------------------------------------------------------------------------*/


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

typedef struct{
                int id;
                long *ProcT, /*vektorban tarolhato az operaciok ideje*/
                     *StartT,
                     *EndT;
                long T,  /* tardiness, csuszas */
                     d;  /* due date, hatariido */
              }T_JOB;

typedef struct{
               long Cmax;  /*Cmax Completion Time*/
              }T_OBJF;



void Simulation_FS(T_JOB* job, int N, int M, int* sch, long t);
void Evaluation(T_JOB* job, int N, int M, T_OBJF* obj);
void print_Machine_Gantt_FS(T_JOB* job, int N, int M, int* sch);
void print_Job_Gantt_FS(T_JOB* job, int N, int M, int* sch);
void Johnson_alg(T_JOB* job, int N, int M, int* sch, int x, int y);
int Johnson_alg_3gepre(T_JOB* job, int N, int M, int* sch, int x);
void Dannenbring_alg(T_JOB* job, int N, int M, int* sch);
void copy_sch(int* s1, int* s2, int N);

int main(int argc, char* argv[])
{
 int par;  //kiterjeszthetoseg feltetelenek vizsgalata

 T_JOB* job;  //munkak adatai
 int M; //gepek szama
 int m; //gepek indexe
 int* sch;
 T_OBJF obj;
 T_OBJF obj_best;

 int N; //munkak szama
 int i; //munkak indexe

 printf("\n Kerem a munkak szamat:");
 scanf("%d", &N);
 printf("\n Kerem a gepek szamat:");
 scanf("%d", &M);


 randomize();
 job = (T_JOB*) calloc( N, sizeof(T_JOB));
 for (i=0; i<N; i++)
 {
    job[i].id = i;
    job[i].ProcT = (long*) calloc(M, sizeof(long));
    for (m=0; m<M; m++)
      job[i].ProcT[m] = 1 + random(20);
    job[i].StartT = (long*) calloc(M, sizeof(long));
    job[i].EndT = (long*) calloc(M, sizeof(long));

    job[i].d = 1 + random(10) * random(5) * N;
 }

 sch = (int*) calloc(N, sizeof(int));

 //Ad-hoc
 for (i=0; i<N; i++)
 {
  sch[i]=i; //elore
  //sch[i]=N-1-i;  //vissza
 }

 Simulation_FS(job, N, M, sch, 0);
 Evaluation(job, N, M, &obj);
 printf("\n Ad-hoc sorrend eseten Cmax=%ld", obj.Cmax);
 //print_Machine_Gantt_FS(job, N, M, sch);
 printf("\n");
 //print_Job_Gantt_FS(job, N, M, sch);
 getch();

/*
 //Johnson-algoritmus
 Johnson_alg(job, N, M, sch, 0, 1);
 Simulation_FS(job, N, M, sch, 0);
 Evaluation(job, N, M, &obj);
 printf("\n Johnson sorrend eseten Cmax=%ld", obj.Cmax);
 print_Machine_Gantt_FS(job, N, M, sch);
 printf("\n");
 print_Job_Gantt_FS(job, N, M, sch);
 getch();

 //Johnson-algoritmus 3 gepre
  par = Johnson_alg_3gepre(job, N, M, sch, 0);
  if ( par == -1 )
   {
   printf("\n Keves gep!");
   getch();
   }
  else
  {
  Simulation_FS(job, N, M, sch, 0);
  Evaluation(job, N, M, &obj);
  printf("\n Johnson sorrend 3 gep eseten Cmax=%ld", obj.Cmax);
  print_Machine_Gantt_FS(job, N, M, sch);
  printf("\n");
  print_Job_Gantt_FS(job, N, M, sch);
  if (par == 1)
   printf("\n Kiterjesztes feltetele teljesul!");
  else
   printf("\n Kiterjesztes feltetele nem teljesul!");

  getch();
  }
 */
 //CDS algoritmus
 {
   int* sch_best; //legjobb megoldas
   sch_best = (int*) calloc(N, sizeof(int));

   //m a gepek futoindexe
   for (m=0; m<M-1; m++)
   {
     //a virtualis elso gep indexe: m
     //a virtualis masodik gep: m+1
    Johnson_alg(job, N, 2, sch, m, m + 1);
    Simulation_FS(job, N, M, sch, 0);
    Evaluation(job, N, M, &obj);
    printf("\n Johnson sorrend a %d. ketgepes esetben Cmax=%ld", m, obj.Cmax);

    if ( m==0 )
     {
       copy_sch(sch, sch_best, N);  //utemterv
       obj_best = obj;              //celfuggveny
     }
    else
     {
      if ( obj_best.Cmax > obj.Cmax )
        {
          copy_sch(sch, sch_best, N);  //utemterv
          obj_best = obj;              //celfuggveny
        }
     }

   }
   printf("\n CDS sorrend eseten Cmax=%ld", obj_best.Cmax);
   //printf("\n CDS sorrend: ");

   //Eredmenyek reszletes kiirasa
   //Simulation_FS(job, N, M, sch_best, 0);
   //print_Machine_Gantt_FS(job, N, M, sch_best);
   //print_Job_Gantt_FS(job, N, M, sch_best);

  getch();
  free( sch_best );
 }

  //Dannenbring algoritmus

  Dannenbring_alg(job, N, M, sch);
  Simulation_FS(job, N, M, sch, 0);
  Evaluation(job, N, M, &obj);
  printf("\n Dannenbring sorrend eseten Cmax=%ld", obj.Cmax);
  getch();


 for( i=0; i<N; i++)
    {
     free( job[i].ProcT);
     free( job[i].StartT);
     free( job[i].EndT);
    }
 free (job);

 free (sch);

 return 0;
}

void Simulation_FS(T_JOB* job, int N, int M, int* sch, long t)
{
  int i; //munka futoindexe a vegrehajtas szerint
  int m; //gep futoindexe

  for( i=0; i<N; i++ )
    for ( m=0; m<M; m++ )
    {
      if ( i==0 ) //kezdo munka
      {
        if ( m==0 ) //kezdo gep
        {
          job[ sch[i] ].StartT[m] = t;  //eleje
        }
        else //nem az elso gep
        {
         //elozo geprol mikor erkezik
         job[ sch[i] ].StartT[m] = job[ sch[i] ].EndT[m-1];
        }
      }
      else //nem elso munka
      {
        if ( m==0 ) //kezdo gep
        {
         //elozo munka mikor fejezodik be
         job[ sch[i] ].StartT[m] = job[ sch[i-1] ].EndT[m];
        }
        else //nem az elso gep
        {
        //elozo geprol mikor erkezik, a gep elozo munkaja mikor fejezodik be
        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] ].ProcT[m];
    }

}

void print_Machine_Gantt_FS(T_JOB* job, int N, int M, int* sch)
{
 int i, m;

  for(m=0; m<M; m++)
  {

    printf("\n %d gep \n n: \t job \tStartT\t ProcT \t EndT", m);
    for (i=0; i<N; i++)
       printf("\n %d \t %d \t %ld \t %ld \t %ld",
              i,
              sch[i],
              job[sch[i]].StartT[m],
              job[sch[i]].ProcT[m],
              job[sch[i]].EndT[m]
              );
  }
}

void print_Job_Gantt_FS(T_JOB* job, int N, int M, int* sch)
{
 int i, m;

  for (i=0; i<N; i++)
  {
  printf("\n %d munka \n n: \t gep \tStartT\t ProcT \t EndT", i);
  for(m=0; m<M; m++)
       printf("\n %d \t %d \t %ld \t %ld \t %ld",
              i,
              m,
              job[i].StartT[m],
              job[i].ProcT[m],
              job[i].EndT[m]
              );
  }
}

void Evaluation(T_JOB* job, int N, int M, T_OBJF* obj)
{
  int i;
  obj->Cmax = job[0].EndT[M-1];
  for (i=1; i<N; i++)
     if ( job[i].EndT[M-1] > obj->Cmax )
         obj->Cmax = job[i].EndT[M-1];
}

void Johnson_alg(T_JOB* job, int N, int M, int* sch, int x, int y)
{
  int i, j;
  int temp;
  int * r;
  int f, l;

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

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

  f = 0; /* first */
  l = N-1; /* last */

  for(i=0; i<N; i++)
     if ( job[ r[i] ].ProcT[x] < job[ r[i] ].ProcT[y] )
      {
        //elejere a mar beutemezettek moge
        sch[ f ] = r[ i ];
        f++;
      }
     else
      {
         //a vegere a mar beutemezettek ele
         sch[ l ] = r[ i ];
         l--;
      }

  free(r);

}

int Johnson_alg_3gepre(T_JOB* job, int N, int M, int* sch, int x)
{
 int i;
 long min_0, max_1, min_2;
 T_JOB* job_V;

 if ( M < 3 )
 {
 for (i=0; i<N; i++)
  sch[i] = i;
 return -1;
 }

 job_V = (T_JOB*) calloc( N, sizeof(T_JOB));

 for (i=0; i<N; i++)
 {
    job_V[i].id = i;
    job_V[i].ProcT = (long*) calloc(2, sizeof(long));
    job_V[i].ProcT[0] = job[i].ProcT[x] + job[i].ProcT[x+1];
    job_V[i].ProcT[1] = job[i].ProcT[x+1] + job[i].ProcT[x+2];
 }

 Johnson_alg(job_V, N, 2, sch, 0, 1);

 for (i=0; i<N; i++)
    free( job_V[i].ProcT );

 free(job_V);


   /* optimalitas vizsgalata */
  for (i=0; i<N; i++)
    {
      if ( i==0 )
       {
        min_0 = job[i].ProcT[x];
        max_1 = job[i].ProcT[x+1];
        min_2 = job[i].ProcT[x+2];
       }
       else
       {
        if ( min_0 > job[i].ProcT[x])
             min_0 = job[i].ProcT[x];

        if ( max_1 > job[i].ProcT[x+1])
             max_1 = job[i].ProcT[x+1];

        if ( min_2 > job[i].ProcT[x+2])
             min_2 = job[i].ProcT[x+2];
       }

    }


  if ( min_0 >= max_1 || min_2 >= max_1 )
  return 1;
  else
  return 0;

}


void copy_sch(int* s1, int* s2, int N)
{
 int i;
 for (i=0; i<N; i++)
   s2[i] = s1[i];
}


void Dannenbring_alg(T_JOB* job, int N, int M, int* sch)
{
 int i;  //munkak futoindexe
 int j; //gepek futoindexe
 T_JOB* job_V;
 job_V = (T_JOB*) calloc( N, sizeof(T_JOB));

 for (i=0; i<N; i++)
 {
    job_V[i].id = i;
    job_V[i].ProcT = (long*) calloc(2, sizeof(long));

    job_V[i].ProcT[0] = 0;
    job_V[i].ProcT[1] = 0;

    for (j=0; j<M; j++)
       {
        job_V[i].ProcT[0] += (M-j+1)*job[i].ProcT[j];
        job_V[i].ProcT[1] += j*job[i].ProcT[j];
       }
 }

 Johnson_alg(job_V, N, 2, sch, 0, 1);

 for (i=0; i<N; i++)
    free( job_V[i].ProcT );

 free(job_V);
}