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

Továbbfejlesztés:
F2|perm|max(Ci) Ütemezési fedadat megoldása Johnson-algoritmussal.
void Johnson_Alg( T_JOB* job, int NJ, int* s, int m1, int m2 );
Az algoritmus optimális megoldást eredményez.

F3|perm|max(Ci) feladatra a Johnson-algoritmus kiterjeszthető!
Ha az első gép legkisebb időadata nagyobb mint a középső gép legnagyobb időadata,
vagy a harmadik gép legkisebb időadata nagyobb mint a középső gép legnagyobb időadata
akkor a megoldás optimális, egyébként az optimalitás nem garantálható!
void Johnson_Alg_Ext_F3( T_JOB* job, int NJ, int* s );

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 NM gépes feladatból NM-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.

Továbbfejlesztett modell:
F|permut|max(Ci) Utemezesi fedadat megoldasa véletlenszerűen kereső algoritmus alkalmazásával.
Lokális kereső algoritmus demo.
A keresési módszer lassabban működik, de jobb közelítést ad mint a CDS algoritmus.

Továbbfejlesztés:
Több célfüggvény számítása, a felhasználó választhatja ki az aktuális célfüggvényt.
-------------------------------------------------------------------------------*/


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

#define NObjF 4

typedef struct {
                 int id;
                 long* ProcT; //vektor
                 long* StartT; //vektor
                 long* EndT;   //vektor
                 long d;       //hatarido, due date
               }T_JOB;

/*CodeBlocks esetén
long min( long a, long b)
 {
   return a < b ? a : b;
 }

long max( long a, long b)
 {
   return a > b ? a : b;
 }
*/

void Simulation_FS( T_JOB* job, int NJ, int NM, int* s, long t_ref );
//long Evaluation_FS( T_JOB* job, int NJ, int NM, int* s);
long Evaluation_FS( T_JOB* job, int NJ, int NM, int* s, double* ObjF);

void Print_Machine_Gantt( T_JOB* job, int NJ, int NM, int* s);

void Johnson_Alg( T_JOB* job, int NJ, int* s, int m1, int m2 );
void Johnson_Alg_Ext_F3( T_JOB* job, int NJ, int* s );
void CDS_Alg( T_JOB* job, int NJ, int NM, int* s );
void copy_sch(int* s1, int* s2, int NJ);
//void Search_Alg( T_JOB* job, int NJ, int NM, int* s, int STEP, int LOOP );
void Search_Alg( T_JOB* job, int NJ, int NM, int* s, int STEP, int LOOP, int objf_index );

void Neighbour( int* s0, int* s_act, int NJ); //szomszegos megoldas keszitese



int main(int argc, char* argv[])
{
  int i, NJ; //number of jobs
  int m, NM; //number of machines
  int objf_index; //kivalsztott celfv sorszama

  T_JOB* job;  //jobs
  int* s;      //schedule
  long Cmax;   //befejezesi idopont
  double ObjF[ NObjF ];  //celfv vektor
  printf("\n Flow Shop feladat szimulacioja");
  printf("\n Munkak szama: ");
  scanf("%d", &NJ);
  printf("\n Gepek szama: ");
  scanf("%d", &NM);
  printf("\n Celfv sorszam: ");
  //ellenorzes!!!
  scanf("%d", &objf_index);

  //munkak
  job = (T_JOB*) calloc( NJ, sizeof(T_JOB));
  for ( i=0; i<NJ; i++)
    {
       job[i].id = i;  //azonosito
       job[i].ProcT  = (long*) calloc( NM, sizeof(long) );
       job[i].StartT = (long*) calloc( NM, sizeof(long) );
       job[i].EndT   = (long*) calloc( NM, sizeof(long) );

       //technologiai terv definialja
       for ( m=0; m<NM; m++ )
          job[i].ProcT[m] = 1 + rand()%10;

       job[i].d = 1 + rand()%100;

    }

  //utemterv
  s = (int*) calloc( NJ, sizeof(int) );
  for( i=0; i<NJ; i++)
      s[i] = i;

  printf("\n\n Ad-hoc ");
  Simulation_FS( job, NJ, NM, s, 0 );
  Cmax = Evaluation_FS( job, NJ, NM, s, ObjF );
  //Print_Machine_Gantt( job, NJ, NM, s);
  printf("\n Cmax = %ld", Cmax);

  if ( NM == 2)
    {  //optimalis megoldas
     printf("\n\n Johnson sorrend");
     Johnson_Alg( job, NJ, s, 0, 1 ); //ket kezdo gep: m1=0; m2=1;
     Simulation_FS( job, NJ, NM, s, 0 );
     Cmax = Evaluation_FS( job, NJ, NM, s, ObjF );
     //Print_Machine_Gantt( job, NJ, NM, s);
     printf("\n Cmax = %ld", Cmax);
    }

  if ( NM == 3)
    {
     printf("\n\n Johnson sorrend 3 gepre");
     Johnson_Alg_Ext_F3( job, NJ, s);     //virtualis 2 gepen
     Simulation_FS( job, NJ, NM, s, 0 );  //valos 3 gepen
     Cmax = Evaluation_FS( job, NJ, NM, s, ObjF );
     //Print_Machine_Gantt( job, NJ, NM, s);
     printf("\n Cmax = %ld", Cmax);
    }

  if ( NM > 1)
    { //heurisztikus megoldas
     printf("\n\n CDS sorrend");
     CDS_Alg( job, NJ, NM, s );
     Simulation_FS( job, NJ, NM, s, 0 );  //valos 3 gepen
     Cmax = Evaluation_FS( job, NJ, NM, s, ObjF );
     //Print_Machine_Gantt( job, NJ, NM, s);
     printf("\n Cmax = %ld", Cmax);
    }

  if ( NM > 1)
    { //heurisztikus megoldas
     int STEP; //lepesek szama
     int LOOP; //kiterjesztesben vizsgalt szomszedok szama

     printf("\n\n Kereses ");

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

     Search_Alg( job, NJ, NM, s, STEP, LOOP, objf_index );
     Simulation_FS( job, NJ, NM, s, 0 );  //valos 3 gepen
     Evaluation_FS( job, NJ, NM, s, ObjF );
     //Print_Machine_Gantt( job, NJ, NM, s);
     printf("\n ObjF = %lf", ObjF[objf_index]);
    }

  //memeoria felszabaditas
  for( i=0; i<NJ; i++)
    {
    free( job[i].StartT );
    free( job[i].ProcT );
    free( job[i].EndT );
    }
 free( job );
 free( s );


  getch();
  return 0;
}
//---------------------------------------------------------------------------

void Simulation_FS( T_JOB* job, int NJ, int NM, int* s, long t_ref )
{
  int i, m;

  for ( i=0; i<NJ; i++)
    {
      for( m=0; m<NM; m++)
        {
          if ( i == 0 )
            { //kezdo munka
             if ( m == 0 ) //kezdo gep
                job[s[i]].StartT[m] = t_ref; //referencia idopont
             else          //kozbenso gep
                //elozo muvelet befejezodott
                job[s[i]].StartT[m] = job[s[i]].EndT[m-1];
            }
           else
            { //kozbenso munka
             if ( m == 0 )
                //elozo munka befejezodott
                job[s[i]].StartT[m] = job[s[i-1]].EndT[m];
             else
                //elozo muvelet befejezodott
                //elozo munka befejezodott
                job[s[i]].StartT[m] = max ( job[s[i]].EndT[m-1],
                                            job[s[i-1]].EndT[m] );
            }

          job[s[i]].EndT[m] = job[s[i]].StartT[m] +
                              job[s[i]].ProcT[m];
        }
    }

}

long Evaluation_FS( T_JOB* job, int NJ, int NM, int* s, double* ObjF)
{
  int i;
  long Ci;   //befejezesi idopont
  int Ui;    //egysegnyi buntetes
  long Ti;  //csuszas
  //az utolso munka befejezesi idopontja az utolso gepen
  //Cmax
  ObjF[0] = job[ s[NJ-1] ].EndT[NM-1];
  //SzumUi
  ObjF[1] = 0;
  //SzumTi
  ObjF[2] = 0;
  //maxTi
  ObjF[3] = 0;

  for( i=0; i<NJ; i++ )
   {
     Ci = job[ s[i] ].EndT[NM-1];
     Ui = Ci > job[ s[i]].d ? 1 : 0;

     ObjF[1] += Ui;  //keso munkak szamat
     Ti = max( 0, Ci - job[ s[i]].d ); //csuszas

     ObjF[2] += Ti;  //keso munkak szamat

     if ( Ti > ObjF[3] )
          ObjF[3] = Ti;

   }

  //korabbi hasznalathoz
  return job[ s[NJ-1] ].EndT[NM-1];
}

void Print_Machine_Gantt( T_JOB* job, int NJ, int NM, int* s)
{
  int i, m;
  printf("\n Eroforras-orientalt Gantt diagram");
  for ( m=0; m<NM; m++)
    {
       printf("\n %d. gep:");
       printf("\n \t sz \t munka \t indul \t muv. \t bef.");
       for ( i=0; i<NJ; i++)
           printf("\n \t %d \t %d \t %ld \t %ld \t %ld",
                    i,
                    s[i],
                    job[s[i]].StartT[m],
                    job[s[i]].ProcT[m],
                    job[s[i]].EndT[m]);
    }

}

void Johnson_Alg( T_JOB* job, int NJ, int* s, int m1, int m2 )
{
 int i, j;  //munkak futoindexe
 int f, l;  //first eleje, last vege
 int* r;    //elozetes rendezes
 int temp;  //cserehez

 //memoria foglalas
 r = (int*)  calloc(NJ, sizeof(NJ));
 //inicializalas
 for (i=0; i<NJ; i++)
   r[i] = i;
 //rendezes idoadatok szerint nemcsokkeno sorrendbe
 for (i=0; i<NJ-1; i++)
   for(j=i+1; j<NJ; j++)
     if ( min( job[ r[i] ].ProcT[m1], job[ r[i] ].ProcT[m2])
          >
          min( job[ r[j] ].ProcT[m1], job[ r[j] ].ProcT[m2])
        )
        { //csere
          temp = r[i];
          r[i] = r[j];
          r[j] = temp;
        }

  //utemterv
  f = 0;
  l = NJ-1;

  for(i=0; i<NJ; i++)
   {
     if ( job[ r[i] ].ProcT[m1]
          <=
          job[ r[i] ].ProcT[m2]
        )
        { //elore a mar beutamezettek moge
          s[ f ] = r[i];
          f++;  //kovetkezo szabad pozicio
        }
     else
        { //hatre a mar beutemezettek ele
          s[ l ] = r[i];
          l--;  //szabad pozicio
        }
   }

 free(r);
}

void Johnson_Alg_Ext_F3( T_JOB* job, int NJ, int* s )
{
  //ket virtualis gep letrehozasa
  T_JOB* job_ext;
  int i;

  job_ext = (T_JOB*) calloc(NJ, sizeof(T_JOB) );
  for(i=0; i<NJ; i++)
    {
      job_ext[i].id = i;
      job_ext[i].ProcT = (long*) calloc(2, sizeof(long) );  //2 virtualis muvelet
      job_ext[i].StartT = (long*) calloc(2, sizeof(long) );
      job_ext[i].EndT = (long*) calloc(2, sizeof(long) );

      //idoadatok a virtualis gepeken
      job_ext[i].ProcT[0] = job[i].ProcT[0]
                          + job[i].ProcT[1];

      job_ext[i].ProcT[1] = job[i].ProcT[1]
                          + job[i].ProcT[2];

    }

  Johnson_Alg( job_ext, NJ, s, 0, 1 );

  //mem. felszabaditas
  for(i=0; i<NJ; i++)
    {
      free( job_ext[i].ProcT );
      free( job_ext[i].StartT );
      free( job_ext[i].EndT );
    }
  free( job_ext );

}

void CDS_Alg( T_JOB* job, int NJ, int NM, int* s )
{
 int i; //job index
 int m; //machine index
 double ObjF[ NObjF ];
 int* s_act;  //aktualis
 int* s_best; //legjobb

 long Cmax_act;  //celfv
 long Cmax_best; //celfv

 s_act = (int*) calloc(NJ, sizeof(int));
 s_best = (int*) calloc(NJ, sizeof(int));

 for(m=0; m<NM-1; m++)
   {
     //m es az m+1 gepre alk. Johnson-alg
     Johnson_Alg( job, NJ, s_act, m, m+1 );
     Simulation_FS( job, NJ, NM, s_act, 0 );
     Cmax_act = Evaluation_FS( job, NJ, NM, s_act, ObjF );

     if ( m==0 )
       {
         copy_sch(s_act, s_best, NJ);
         Cmax_best = Cmax_act;
       }
     else
        if ( Cmax_act < Cmax_best )
          {
            copy_sch(s_act, s_best, NJ);
            Cmax_best = Cmax_act;
          }
   }

 copy_sch(s_best, s, NJ);

 free( s_act );
 free( s_best );
}

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

void Search_Alg( T_JOB* job, int NJ, int NM, int* s, int STEP, int LOOP, int objf_index )
{
  int step, loop;
 //long Cmax_act, Cmax_ext, Cmax_best; //celfv-ertekek
  double F_act, F_ext, F_best;
  double ObjF[ NObjF ];  //celfv vektor

  int* s0;      //kiindulasi bazismegoldas
  int* s_act;   //aktualis megoldas
  int* s_ext;   //a szomszedsag legjobb megoldasa
  int* s_best;  //a legjobb megtalalt megoldas

  s0 = (int*) calloc(NJ, sizeof(int) );
  s_act = (int*) calloc(NJ, sizeof(int) );
  s_ext = (int*) calloc(NJ, sizeof(int) );
  s_best = (int*) calloc(NJ, sizeof(int) );


  //inicializalas
  copy_sch(s, s0, NJ);
  copy_sch(s, s_best, NJ);
  Simulation_FS( job, NJ, NM, s_best, 0 );
  Evaluation_FS( job, NJ, NM, s_best, ObjF );
  F_best = ObjF[objf_index];


  //algoritmus
  for( step=1; step<=STEP; step++ )
   {
    for( loop=1; loop<=LOOP; loop++ )
      {
        Neighbour( s0, s_act, NJ); //szomszegos megoldas keszitese
        Simulation_FS( job, NJ, NM, s_act, 0 );
        Evaluation_FS( job, NJ, NM, s_act, ObjF );
        F_act = ObjF[objf_index];

        if ( loop == 1 )
          { //elso szomszed
            copy_sch( s_act, s_ext, NJ );
            F_ext = F_act;
          }
        else
          if ( F_act < F_ext )
          { //nem elso szomszed
            copy_sch( s_act, s_ext, NJ );
            F_ext = F_act;
          }
      }

    copy_sch( s_ext, s0, NJ );


    if ( F_ext < F_best ) //jobb mint a legjobb
       { //legjobb megjegyzese
         copy_sch( s_ext, s_best, NJ );
         F_best = F_ext;
       }
   }//step

   //eredmny visszaadasa
  copy_sch( s_best, s, NJ );

  free( s0 );
  free( s_act );
  free( s_ext );
  free( s_best );

}

void Neighbour( int* s0, int* s_act, int NJ) //szomszegos megoldas keszitese
{
  //veletlenszeru eloremozditas

  int i;
  int t; //kivalasztott pozicio
  t = rand()%NJ; //veletlenszru valasztas

  for( i=0; i<NJ; i++)
     s_act[i] = s0[i];

  if( t == 0 )
    { //vegere rak
      s_act[ NJ-1 ] = s0[ t ];
      s_act[ t ] = s0[ NJ-1 ];

    }
  else
    { //elore leptetes
      s_act[ t-1 ] = s0[ t ];
      s_act[ t ] = s0[ t-1 ];
    }

}