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

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

typedef struct{
                int id;      //identifier of the job
                long* ProcT; //processing time of the operations
                long* StartT;
                long* EndT;
              } T_JOB;

void Simulation_FS( T_JOB* job, int NJ, int NM,
                 int* s, long t_ref);
void Print_Job_Gantt( T_JOB* job, int NJ, int NM, int* s);
void Print_Machine_Gantt( T_JOB* job, int NJ, int NM, int* s);
long Evaluation_FS( 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 copy_sch( int* s1, int* s2, int NJ);
void CDS( T_JOB* job, int NJ, int NM, int* s);


int main(int argc, char* argv[])
{
  int NJ; //number of jobs in the system
  int NM; //number of machines (people)
  int i;  //index of job
  int m;  //index of machine
  T_JOB* job;  //list of jobs
  int* s;      //schedule
  long Cmax;   //completion time


  //adatok betoltese
  printf("\n Egyutas, elozes nelkuli utemezesi feladat.");
  printf("\n Munkak szama:");
  scanf("%d", &NJ);
  printf("\n Gepek szama:");
  scanf("%d", &NM);

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

      //folyamattervezo adatai adottak a valosagban
      for ( m=0; m<NM; m++ )
        job[i].ProcT[m] = 1 + rand()%20;
    }

  //utemterv
  s = (int*) calloc(NJ, sizeof(int) );
  //ad-hoc sorrend
  for( i=0; i<NJ; i++)
      s[i] = i;
      //s[i] = NJ-1-i; //forditott sorrend

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

  //if ( NM == 2 )
  {
   //szimulacio
   Johnson_Alg( job, NJ, s, 0, 1); //m1 = 0; m2 = 1;
   Simulation_FS( job, NJ, NM, s, 0);
   printf("\n Johnson sorrend");
   //Print_Job_Gantt( job, NJ, NM, s);
   //Print_Machine_Gantt( job, NJ, NM, s);
   Cmax = Evaluation_FS( job, NJ, NM, s);
   printf("\n Cmax = %ld", Cmax );
  }

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

   CDS( job, NJ, NM, s);
   Simulation_FS( job, NJ, NM, s, 0);
   printf("\n CDS sorrend");
   //Print_Job_Gantt( job, NJ, NM, s);
   //Print_Machine_Gantt( job, NJ, NM, s);
   Cmax = Evaluation_FS( job, NJ, NM, s);
   printf("\n Cmax = %ld", Cmax );


  getch();

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

  free( s );

  return 0;
}
//---------------------------------------------------------------------------

void Simulation_FS( T_JOB* job, int NJ, int NM,
                 int* s, long t_ref)
{ //egyutas, elozes nelkuli (Flow Shop) feladat szimulacioja
  int i, m; //futoindex
            //i jelenti az inditas sorszamat
            //m elvegzendo operacio sorszama
            //s[i] az i-edik munka azonositoja

  for( i=0; i<NJ; i++ )
    {
      for( m=0; m<NM; m++ )
        {
           if ( i==0 ) //kezdo munka
             {
              if ( m==0 ) //kezdo operacio
                 //mikor inditjuk
                 job[ s[i] ].StartT[m] = t_ref;
              else //nem kezdo operacio
                 //az elozo operacioja mikor fejezodik be
                 job[ s[i] ].StartT[m] = job[ s[i] ].EndT[m-1];
             }
           else  //nem kezdo munka
             {
              if ( m==0 ) //kezdo operacio
                 //az elotte elvegzett operacio mikor fejezodik be
                 job[ s[i] ].StartT[m] = job[ s[i-1] ].EndT[m];
              else
                 //a munka mikor erkezik
                 //a gep mikor szabadul fel
                 job[ s[i] ].StartT[m] = max ( job[ s[i] ].EndT[m-1],
                                               job[ s[i-1] ].EndT[m] );
             }
           //befejezes = inditas + muveleti ido
           job[ s[i] ].EndT[m] =   job[ s[i] ].StartT[m]
                                 + job[ s[i] ].ProcT[m];
        }
    }

}

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

     }

}

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

     }

}


long Evaluation_FS( T_JOB* job, int NJ, int NM, int* s)
{
   //utolsokent inditott munka utolso operacioja
   return job[ s[NJ-1] ].EndT[ NM-1];
}

void Johnson_Alg( T_JOB* job, int NJ, int* s, int m1, int m2)
{
  int i, j; //munka index
  int* r;   //rendezett vektor
  int f, l; //first eleje, last vege
  int temp; //cserehez

  //memoriafoglalas
  r = (int*) calloc(NJ, sizeof(int) );
  //inicializalas
  for (i=0; i<NJ; i++)
     r[i] = i;

  //rendezes kivaltja a keresest
  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;
       }

  //beutemezes
  f = 0;      //first
  l = NJ - 1; //last
  for (i=0; i<NJ; i++)
    if ( job[ r[i] ].ProcT[m1]
         <
         job[ r[i] ].ProcT[m2]
       )
       { //elore a mar beutemezettek moge
         s[ f ] = r[i];
         f++;
       }
    else
       { //hatra a mar beutemezettek ele
         s[ l ] = r[i];
         l--;
       }


  free(r);
}

void Johnson_Alg_Ext_F3( T_JOB* job, int NJ, int* s)
{
  int i;
  T_JOB* virt_job;  //lekepzes ket gepre
  virt_job = (T_JOB*) calloc(NJ, sizeof(T_JOB) );
  for (i=0; i<NJ; i++)
    {
       virt_job[i].ProcT = calloc(2, sizeof(long) );
       virt_job[i].StartT = calloc(2, sizeof(long) );
       virt_job[i].EndT = calloc(2, sizeof(long) );

       //virtualis 2 gepes modell idoadatai
       virt_job[i].ProcT[0] = job[i].ProcT[0]
                            + job[i].ProcT[1];
       virt_job[i].ProcT[1] = job[i].ProcT[1]
                            + job[i].ProcT[2];
    }

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


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

}

void CDS( T_JOB* job, int NJ, int NM, int* s)
{
  int i;  //munka index
  int m;  //gep index

  int* s_best; //legjobb megoldas
  int* s_act;  //aktualis megoldas

  long Cmax_best; //legjobb megoldas celfv-je
  long Cmax_act;  //aktualis megoldas celfv-je

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

  //virtualis 2 gepes modellek
  //NM-1 darab paros
  for( m=0; m<NM-1; m++)
   {
     //m es az m+1 gep
      Johnson_Alg( job, NJ, s_act, m, m+1); //m1 = m; m2 = m+1;
      Simulation_FS( job, NJ, NM, s_act, 0);
      Cmax_act = Evaluation_FS( job, NJ, NM, s_act);

      if ( m == 0 ) //kezdo megoldas
        {
            copy_sch(s_act, s_best, NJ);
            Cmax_best = Cmax_act;
        }
      else
         if ( Cmax_best > Cmax_act )
           {
            copy_sch(s_act, s_best, NJ);
            Cmax_best = Cmax_act;
           }
   }

  //legjobb megoldas
  copy_sch(s_best, s, NJ);

  free(s_best);
  free(s_act);
}

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