/*-------------------------------------------------------------------------------
TIA

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. .

DTFSZTIR

Továbbfejlesztett modell:

F|perm|max(Ci) Utemezesi fedadat megoldasa véletlenszerűen kereső algoritmus alkalmazásával.

Lokális kereső algoritmus demo (kész).

Továbbfejlesztés:
F|perm|max(Ci) szakaszosan rendelkezésre álló erőforrások figyelembevételével.

Továbbfejlesztett modell:

Szakaszosan rendelkezésre álló erőforrások terhelésére szolgáló algortimus.

A Load_STET_to_Cal függvény a megadott terhelést [st, et] 
az adott gépre megszakitás nelkul helyezi el 
(a legkorábbi rendelkezésre állási intervallumra, amelyen egészben elfér). 


-------------------------------------------------------------------------------*/


#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;

typedef struct{
               long ST;     //Start Time
               long ET;     //End Time
               }T_TW;       //Time Window

typedef struct{
               int id;
               int NCal;    //Number of Calendar elements
               T_TW* Cal;   //Calendar
              }T_RES;       //Resource: gep, ember stb.



//void Simulation_FS(T_JOB* job, int N, int M, int* sch, long t);
void Simulation_FS(T_JOB* job, int N, int M, int* sch, long t, T_RES* res);

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);
//DTFSZTIR
//int Search( T_JOB* job, int N, int M, int* sch, int STEP, int LOOP);
int Search( T_JOB* job, int N, int M, int* sch, int STEP, int LOOP, T_RES* res);
void Neighbour(int* s0, int* s, int N);
//res
void print_Cal( T_RES* res, int M);
int Load_STET_to_Cal( long* ST, long* ET, long last, T_RES* res, int m );



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 c; //intervallumok futoindexe
 int* sch;
 T_OBJF obj;
 T_OBJF obj_best;
 T_RES* res;       //eroforrasok adatai
 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();
 res = (T_RES*) calloc( M, sizeof(T_RES));
 for (m=0; m<M; m++)
   {
     res[m].id = m;
     res[m].NCal = 1 + rand()%10;  //szakaszok darabszama
     res[m].Cal = (T_TW*) calloc( res[m].NCal, sizeof(T_TW) ); //lista
     for ( c=0; c<res[m].NCal; c++)
        {  //intervallumok konkretizalasa
           if ( c==0 )
                res[m].Cal[c].ST = rand()%20;
           else
                res[m].Cal[c].ST = res[m].Cal[c-1].ET + 1 + rand()%20;

           res[m].Cal[c].ET = res[m].Cal[c].ST + 1 + rand()%50;
        }

   }

 print_Cal( res, M);

 printf(" \n Kezi teszt.");
 do
 {
  int found;
  long ST, ET, last;
  int mach;

  printf("\n mach = ");
  scanf("%d", &mach);
  printf("\n ST = ");
  scanf("%ld", &ST);
  printf("\n ET = ");
  scanf("%ld", &ET);
  printf("\n last = ");
  scanf("%ld", &last);

  found = Load_STET_to_Cal( &ST, &ET, last, res, mach );
  printf("\n newST = %ld", ST);
  printf("\n newET = %ld", ET);
  printf("\n found = %d", found);
  printf("\n Folytatja a tesztelest: (i/n)?");
 }
 while(  getch() == 'i');

 getch();

 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 + rand()%20;
      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 + rand()%10 * rand()%5 * N;
    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, res);
 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();

 //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, res);
    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, res);
  Evaluation(job, N, M, &obj);
  printf("\n Dannenbring sorrend eseten Cmax=%ld", obj.Cmax);
  getch();

 {
 int STEP, LOOP;
 int best_step;
 printf("\n A kereso alg. lepesszama:");
 scanf("%d", &STEP);
 printf("\n A kereso alg.-ban hasznalt szomszedok szama:");
 scanf("%d", &LOOP);

 //DTFSZTIR tovabbfejlesztes
 best_step = Search( job, N, M, sch, STEP, LOOP, res);
 Simulation_FS(job, N, M, sch, 0, res);
 Evaluation(job, N, M, &obj);
 printf("Dannenbring megoldassal inditva.");
 printf("\n A kereses eredmenye Cmax=%ld", obj.Cmax);
 printf("\n Legjobb lepes sorszama: %d", best_step);

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

 best_step = Search( job, N, M, sch, STEP, LOOP, res);
 Simulation_FS(job, N, M, sch, 0, res);
 Evaluation(job, N, M, &obj);
 printf("\n Ad-hoc megoldassal inditva.");
 printf("\n A kereses eredmenye Cmax=%ld", obj.Cmax);
 printf("\n Legjobb lepes sorszama: %d", best_step);

 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)
void Simulation_FS(T_JOB* job, int N, int M, int* sch, long t, T_RES* res)
{
  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];
      /* FONTOS modositas */
      Load_STET_to_Cal( &job[ sch[i] ].StartT[m],
                        &job[ sch[i] ].EndT[m],
                        0, res, 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);
}

 //DTFSZTIR tovabbfejlesztes
 int Search( T_JOB* job, int N, int M, int* sch, int STEP, int LOOP, T_RES* res)
 {
  int step, loop; //ciklusvaltozok
  int best_step = 0;  //legjobb megoldast eredmenyezo lepes sorszama

  int* s0; //kiindulo megoldas
  int* s;  //szomszedos megoldas
  int* s_best; //legjobb megoldas
  int* s_ext; //legjobb szomszed
  T_OBJF obj; // s-hez tartozo celfuggveny
  T_OBJF obj_best;
  T_OBJF obj_ext;

  //memoria foglalas
  s0 = (int*) calloc(N, sizeof(int)); //N elemu int vektor
  s = (int*) calloc(N, sizeof(int)); //N elemu int vektor
  s_best = (int*) calloc(N, sizeof(int)); //N elemu int vektor
  s_ext = (int*) calloc(N, sizeof(int)); //N elemu int vektor

  //inicializalas
  copy_sch( sch, s_best, N);
  Simulation_FS(job, N, M, s_best, 0, res);
  Evaluation(job, N, M, &obj_best);

  copy_sch( sch, s0, N);

  for ( step = 1; step <= STEP; step++)
   {
     for( loop = 1; loop <= LOOP; loop++)
      {
        Neighbour(s0, s, N);  //szomszedos megoldas keszitese
        Simulation_FS(job, N, M, s, 0, res);
        Evaluation(job, N, M, &obj);

        if ( loop == 1 ) //elso generalt szomszed
          {
            copy_sch(s, s_ext, N); //kiterjesztes legjobb megoldasa
            obj_ext = obj;
          }
         else
           if ( obj.Cmax < obj_ext.Cmax )
             {
               copy_sch(s, s_ext, N); //kiterjesztes legjobb megoldasa
               obj_ext = obj;
             }
      }//loop

      copy_sch(s_ext, s0, N);  //uj bazismegoldas

      if ( obj_ext.Cmax < obj_best.Cmax )
        {
         copy_sch(s_ext, s_best, N); //kereses legjobb megoldasa
         obj_best = obj_ext;
         best_step = step;
        }

   }//step

  //eredmeny
  copy_sch(s_best, sch, N);

  //memoria felszabaditas
  free( s0 );
  free( s );
  free( s_best );
  free( s_ext );

  return best_step;
 }

void Neighbour(int* s0, int* s, int N)
{
 //szomszedos megoldas keszitese
 //veletlenszeruen kivalasztott elemet a beloldali szomszedjaval megcsereli
 //0. elemet az utolsoval

 int i;
 int x; //kivalasztott elem sorszama

 x = rand()%N;
 for ( i = 0; i < N; i++ )
   s[i] = s0[i];

 if ( x == 0 )
   {  //utolsot az elsovel csereli
      s[x] = s0[N-1];
      s[N-1] = s0[x];
   }
  else
   {  //kivalasztott es a bal szomszed csereje
      s[x] = s0[x-1];
      s[x-1] = s0[x];
   }

}

void print_Cal( T_RES* res, int M)
{
  int c;
  int m;

  printf("\n Eroforrasok rendelkezesre allasa:");
  for( m=0; m<M; m++)
   {
      printf("\n %d. eroforras <%d>", res[m].id, res[m].NCal);
      for( c=0; c<res[m].NCal; c++)
        printf("\n \t %d: \t %ld \t %ld",
               c,
               res[m].Cal[c].ST,
               res[m].Cal[c].ET );
   }

}

int Load_STET_to_Cal( long* ST, long* ET, long last, T_RES* res, int m )
{

 long newST; //elhelyezett munka kezdete
 long newET; //elhelyezett munka vege
 long size;  //munka merete
 int c;      //intervallumok futoindexe
 int found;  //talalat

 size = *ET - *ST;
 newST = max( *ST, last);
 newET = newST + size;

 c = 0;
 found = -1;

 while( c < res[m].NCal )
  {
     if ( newST < res[m].Cal[c].ET )
      {
         newST = max( newST, res[m].Cal[c].ST );  //elejere igazit
         newET = newST + size;

         if ( newET <= res[m].Cal[c].ET ) //benne van a vege is
            {
              found = c;
              break;
            }
         else
           {
            c++;
            if ( c >= res[m].NCal )
              break;

            continue;
           }
      }
     c++;
  }

  *ST = newST;
  *ET = newET;
  
  return found; //megtalalt intervallum azonositoja
}