/*-------------------------------------------------------------------------------
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á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). 

Folytatás:
     Az új módszer alkalmazása a szimulációban FS-re.

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


#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;    //idointervallum eleje
               long ET;    //idointervallum vege
              }T_TW;       //Time Window, idointervallum

typedef struct{
               int id;     //eroforras azonosito
               int NCal;   //number of calendar elements,
               T_TW* Cal;  //Calendar
              }T_RES;      //resurce, eroforras



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 CDS_alg(T_JOB* job, int N, int M, int* sch);
void copy_sch(int* s1, int* s2, int N);
void Dannenbring_alg(T_JOB* job, int N, int M, int* sch);

//DTFSZTIR
int Search(T_JOB* job, int N, int M, int* sch, int STEP, int LOOP, int mode);
void Neighbour(int* s0, int* s, int N);
void Neighbour_v2(int* s0, int* s, int N);
int Load_STET_to_Cal( long* ST, long* ET, long last, T_RES* res, int m);
void print_Res_Cal(T_RES* res,  int M );


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

 T_JOB* job;  //munkak adatai
 T_RES* res;  //gepek
 int M; //gepek szama
 int m; //gepek indexe
 int c; //idointervallumok futoindexe
 int* sch;
 T_OBJF obj;
 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
 res = (T_RES*) calloc( M, sizeof(T_RES));
 for(m=0; m<M; m++)
   {
     res[m].id = m;
     res[m].NCal = 1 + rand()%10;
     res[m].Cal = (T_TW*) calloc( res[m].NCal , sizeof(T_TW) );
     for ( c=0; c<res[m].NCal; c++)
        { //az intervallumok nem lapolodhatnak at
          if (c==0)
               res[m].Cal[c].ST = rand()%20;
          else
               res[m].Cal[c].ST = res[m].Cal[c-1].ET + rand()%20;
          res[m].Cal[c].ET = res[m].Cal[c].ST + 1 + rand()%50;
        }
   }

  //teszt
  print_Res_Cal(res, M );
  do
  {
    long st, et, last;
    int found, m;

    printf("\n gep=");
    scanf("%ld", &m);
    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, m);
   printf("\n ST= %ld, ET= %ld, intervallum = %d", st, et, found);
   printf("\n Uj teszt (i/n)?");
  } while( getch()== 'i' );

 //job
 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].ProcT[m] = 1 + rand()%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;
    job[i].d = 1 + rand()%10 * rand()%5 * N;
 }

 //utemterv
 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();


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


 //Dannenbring alg
 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();

 {
 //DTFSZTIR
 //Kereso algoritmus
 int STEP; //Lepesek max. szama
 int LOOP; //egy lepesben vizsgalhato szomszedos megoldasok mex. szama
 int best_step;

 printf("\n Lepesek szama STEP=");
 scanf("%d", &STEP);

 printf("\n Szomszedok szama LOOP=");
 scanf("%d", &LOOP);

 printf("\n Dannenbring eredmenyevel inditva es N1 operator alkalmazasaval:");
 best_step = Search(job, N, M, sch, STEP, LOOP, 1);
 Simulation_FS(job, N, M, sch, 0);
 Evaluation(job, N, M, &obj);
 printf("\n Kereso algoritmus eseten Cmax=%ld", obj.Cmax);
 printf("\n Legjobb lepes: %d", best_step);

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

 printf("\n Ad-hoc sorrenddel inditva, N1 operator alkalmazasaval:");
 best_step = Search(job, N, M, sch, STEP, LOOP, 1);
 Simulation_FS(job, N, M, sch, 0);
 Evaluation(job, N, M, &obj);
 printf("\n Kereso algoritmus eseten Cmax=%ld", obj.Cmax);
 printf("\n Legjobb lepes: %d", best_step);

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

 printf("\n Ad-hoc sorrenddel inditva, N2 operator alkalmazasaval:");
 best_step = Search(job, N, M, sch, STEP, LOOP, 2);
 Simulation_FS(job, N, M, sch, 0);
 Evaluation(job, N, M, &obj);
 printf("\n Kereso algoritmus eseten Cmax=%ld", obj.Cmax);
 printf("\n Legjobb lepes: %d", best_step);

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

 printf("\n Ad-hoc sorrenddel inditva, N1 es N2 operator alkalmazasaval:");
 best_step = Search(job, N, M, sch, STEP, LOOP, 3);
 Simulation_FS(job, N, M, sch, 0);
 Evaluation(job, N, M, &obj);
 printf("\n Kereso algoritmus eseten Cmax=%ld", obj.Cmax);
 printf("\n Legjobb lepes: %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)
{
  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 CDS_alg(T_JOB* job, int N, int M, int* sch)
{
 int m; //gepek futoindexe
 int i; //munkak futoindexe
 T_OBJF obj; //celfuggveny
 T_OBJF obj_best; //legjobb megoldashoz tartozo celfuggveny
 int* sch_best; //legjobb utemterv (megoldas)

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

 for (m=0; m<M; m++)
 {
    //virtualis elso gep: m
    //virtualis masodk 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 %d. virtualis gep eseteben Cmax = %ld", m, obj.Cmax);

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

 copy_sch(sch_best, sch, N);

 free(sch_best);
}

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 m; //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( m=0; m<M; m++)
    { //ez a lenyeg!!!
     job_V[i].ProcT[0] += (M-m+1) * job[i].ProcT[m];
     job_V[i].ProcT[1] += m * job[i].ProcT[m];
     }

 }

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

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

 free(job_V);

}

int Search(T_JOB* job, int N, int M, int* sch, int STEP, int LOOP, int mode)
{
 int step, loop;
 int best_step = 0; //legjobb lepes sorszama

 int* s0; //kiindulo megoldas
 int* s;  //aktualis megoldas
 int* s_ext; //kiterjesztes legjobb megoldasa
 int* s_best; //legjobb megoldas

 T_OBJF obj_s;
 T_OBJF obj_s_ext;
 T_OBJF obj_s_best;

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

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

 //lokalis kereses
 for(step = 1; step <= STEP; step++ )
  {
    for (loop = 1; loop <= LOOP; loop++ )
      {
       switch( mode )
       {
        case 1: Neighbour(s0, s, N);
                break;
        case 2: Neighbour_v2(s0, s, N);
                break;
        case 3: //mindket szomszedsagi operatort alkalmazza
                if ( rand()%2 )
                   Neighbour(s0, s, N);
                else
                   Neighbour_v2(s0, s, N);
                break;
       }
       Simulation_FS(job, N, M, s, 0);
       Evaluation(job, N, M, &obj_s);

       if ( loop == 1 )
         { //kiterjesztes legjobbjanak megjegyzese
           copy_sch(s, s_ext, N);  //utemterv
           obj_s_ext = obj_s;      //celfuggveny
         }
       else
         if ( obj_s_ext.Cmax > obj_s.Cmax  )
         { //kiterjesztes legjobbjanak megjegyzese
           copy_sch(s, s_ext, N);  //utemterv
           obj_s_ext = obj_s;      //celfuggveny
         }

      }//loop

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

      if ( obj_s_best.Cmax > obj_s_ext.Cmax )
        { //legjobb megoldas megjegyzese
          copy_sch( s_ext, s_best, N);
          obj_s_best = obj_s_ext;
          best_step = step;
        }

  }//step

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

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

 return best_step; //legjobb lepes sorszama
}

void Neighbour(int* s0, int* s, int N)
{
  //szomszedsag definicioja
  //pelda: veletlenszeruen valasztott sorszamu elemet a tole balra levo elemmel felcsereljuk

  int i;
  //cel kivalasztasa
  int x = rand()%N;

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

  if ( x == 0 )
    {
       s[x] = s0[N-1];
       s[N-1] = s0[x];
    }
  else
    {
       s[x] = s0[x-1];
       s[x-1] = s0[x];

    }

}

void Neighbour_v2(int* s0, int* s, int N)
{
  //szomszedsag definicioja
  //pelda: ket veletlenszeruen valasztott sorszamu elemet felcsereljuk

  int i;
  //cel kivalasztasa
  int x = rand()%N;
  int y = rand()%N;

  if ( x == y ) y++;
  if ( y == N ) y = 0; //ne legyen azonos x es y

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

  s[x] = s0[y];
  s[y] = s0[x];

}

int Load_STET_to_Cal( long* ST, long* ET, long last, T_RES* res, int m)
{
 long newST; //uj inditasi idopont
 long newET; //uj bef. idopont
 long size;  //muvelet hossza
 int c;      //intervallumok futoindexe
 int found = -1;  //alkalmas intervallum sorszama

 size = *ET - *ST;
 newST = max( *ST, last );
 newET = newST + size;
 c = 0;
 while ( c < res[m].NCal )
  {
    if (  newST < res[m].Cal[c].ET )
      {
        newST = max( newST, res[m].Cal[c].ST ); //kezdethez igaxitjuk
        newET = newST + size;

        if ( newET <= res[m].Cal[c].ET  )
           {
             found = c;  //talalat
             break;
           }
        else
           {
           //Ha az utolso szakaszba sem illesztheto be
           //akkor az utolso utan inditja
           c++;
           if ( c >= res[m].NCal )
              {
                newST = res[m].Cal[c-1].ET;
                newET = newST + size;
                break;
              }
           continue;
          }
      }
    c++;

  }

  *ST = newST;   //erdmeny felulirja a kezdoerteket
  *ET = newET;

  return found;  //megtalalt intervallum sorszama
}

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

  for(m=0; m<M; m++)
  {
    printf("\n %d gep <%d>", m, res[m].NCal );
    printf("\n\tsorszam\t eleje \t vege");
    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 );
  }
}