/*------------------------------------------------------------------------------
TIA 6. gyakorlat
F|perm|Cmax
Egyutas előzésnélküli többoperációs ütemezési feladat.
Cél: A befejezési időpont minimalizálása.
1. rész:
Modellépítés és szimuláció.
A Simulation_F 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.

TIA 7. gyakorlat
F2|perm|Cmax ütemezési fedadat megoldása Johnson-algoritmussal.
Az algoritmus optimális megoldást eredményez.

TIA 8. gyakorlat
F3|perm|Cmax ütemezési fedadat megoldása
kiterjesztett Johnson-algoritmussal.
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ó!


Továbbfejlesztett modell:

F|permut|Cmax
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 munkacsoport á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 NM-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;       //azonosito
                long* ProcT;  //muveleti idok, vector of processing times
                long* StartT; //keydesi idok, vector of starting times
                long* EndT;   //befejezesi idok, vector of finishing (end) times
               } T_JOB;
 /*CodeBlocks
 long max( long a, long b)
   {
     return a > b ? a : b; //felteteles operator
     //if (a > b) return a;
     //else return b;
   }

 long min( long a, long b)
   {
     return a < b ? a : b; //felteteles operator
   }

 */
void Simulation_F( T_JOB* job, int NJ, int NM, int* s, long t_ref);
void Print_Job_Gantt( T_JOB* job, int NJ, int NM);
void Print_Machine_Gantt( T_JOB* job, int NJ, int NM, int* s);
long Evaluate( T_JOB* job, int NJ, int NM, int* s);
void Johnson_alg( T_JOB* job, int NJ, int m1, int m2, int* s);
void Johnson_alg_extension( T_JOB* job, int NJ, int* s);
void copy_vector( int* v1, int* v2, int NJ);
void CDS_alg( T_JOB* job, int NJ, int NM, int* s);


int main(int argc, char* argv[])
{
  int i; //munka indexe, job
  int NJ; //munkak szama, number of jobs
  int m; //gep indexe, muvelet sorszama
  int NM; //gepek szam, number of machines
  int* s; //utemterv, schedule
  T_JOB* job;   //jobok listaja, vector of jobs
  long Cmax;   //utolso munka bef. idopontja, maximal completion time

  printf("\n Flow Shop utemezesi feladat demo.");
  printf("\n Munkak szama:");
  scanf("%d", &NJ);
  printf("\n Gepek szama:");
  scanf("%d", &NM);

  //Modellepites, Model Building
  srand( 0 ); //inicializalja a veletlenszam generatort
  job = (T_JOB*) calloc( NJ, sizeof(T_JOB) ); //mem. foglalas
  for (i=0; i<NJ; i++)
   {
      job[i].id = i;
      job[i].ProcT  = (long*) calloc( NM, sizeof(long) );
      job[i].StartT = (long*) calloc( NM, sizeof(long) );
      job[i].EndT   = (long*) calloc( NM, sizeof(long) );

      //a technologiai terv definialja a muveleti idoket
      for (m=0; m<NM; m++)
          job[i].ProcT[m] = 1 + rand()%200;  //kvazi-veletlenszam
   }

   s = (int*) calloc( NJ, sizeof(int) );  //utemterv
   //egy megoldas
   for ( i=0; i<NJ; i++)
      s[i] = i;   //Ad-hoc sorrend

  //Szimulacio
  printf("Ad-hoc sorrend szerint utemezve");
  Simulation_F( job, NJ, NM, s, 0); //0 idopontban indul a folyamat
  //Print_Job_Gantt( job, NJ, NM);
  //Print_Machine_Gantt( job, NJ, NM, s);
  Cmax = Evaluate( job, NJ, NM, s);
  printf("\n Cmax = %ld", Cmax);

  if ( NM == 2)
  {
  //Johnson-algoritmus
  printf("\n \n Johnson-algoritmus szerint utemezve");
  Johnson_alg( job, NJ, 0, 1, s);
  Simulation_F( job, NJ, NM, s, 0); //0 idopontban indul a folyamat
  //Print_Job_Gantt( job, NJ, NM);
  //Print_Machine_Gantt( job, NJ, NM, s);
  Cmax = Evaluate( job, NJ, NM, s);
  printf("\n Cmax = %ld", Cmax);
  }

  if ( NM == 3)
  {
  //Johnson-algoritmus kiterjesztett valtozata
  printf("\n \n Johnson-algoritmus (kit. v.) szerint utemezve");
  Johnson_alg_extension( job, NJ, s);
  Simulation_F( job, NJ, NM, s, 0); //0 idopontban indul a folyamat
  //Print_Job_Gantt( job, NJ, NM);
  //Print_Machine_Gantt( job, NJ, NM, s);
  Cmax = Evaluate( job, NJ, NM, s);
  printf("\n Cmax = %ld", Cmax);
  }

  //CDS-alg
  printf("\n \n CDS-algoritmus szerint utemezve");
  CDS_alg( job, NJ, NM, s);
  Simulation_F( job, NJ, NM, s, 0); //0 idopontban indul a folyamat
  //Print_Job_Gantt( job, NJ, NM);
  //Print_Machine_Gantt( job, NJ, NM, s);
  Cmax = Evaluate( job, NJ, NM, s);
  printf("\n Cmax = %ld", Cmax);



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

  getch();
  return 0;
}

 void Simulation_F( T_JOB* job, int NJ, int NM, int* s, long t_ref)
 {
   //a tablara felirt logikai kovetkeztetes eredmenye alapjan
   //a szimulacio elvegezheto "executiin-driven" elv hasznalataval
   int i;  //munka index
   int m;  //gep index

   for (i=0; i<NJ; i++)  //i az inditas szerinti sorszam
    {  //a munka azonositoja s[i]
      for(m=0; m<NM; m++)
       {
          if ( i==0 )
          {  //kezdo munka
             if ( m==0 )
               { //kezdo gep
                 job[ s[i] ].StartT[ m ] = t_ref;
                 //nincs elotte mas munka
               }
             else
               { //kozbenso gep
                 job[ s[i] ].StartT[ m ] = job[ s[i] ].EndT[ m-1 ];
                 //a gep biztosan szabad
               }

          }
          else
          {  //kozbenso munka
             if ( m==0 )
               { //kezdo gep
                 //Figyelem> Bug: StartT helyett EndT
                 job[ s[i] ].StartT[ m ] = job[ s[i-1] ].EndT[ m ];
                 //az elozo munka befejezodott a gepen
               }
             else
               { //kozbenso gep
                 job[ s[i] ].StartT[ m ] = max( job[ s[i-1] ].EndT[ m ]
                                               ,job[ s[i] ].EndT[ m-1 ] );
                                          // elozo munka az adott genen mikor fejezodik be
                                          // a munka elozo operacioja mikor fejezodik be
               }
          }

          job[ s[i] ].EndT[ m ] = job[ s[i] ].StartT[ m ] +
                                  job[ s[i] ].ProcT[ m ];
          //bef. idoponto = kezdesi idopont + muveleti ido

       }
    }

 }



void Print_Job_Gantt( T_JOB* job, int NJ, int NM)
{
  int i; //job
  int m; //gep

  printf("\n Munka-orinetalt Gantt-diagram:\n");
  for( i=0; i<NJ; i++)
   {
     printf("\nMunka: %d", i);
     printf("\n gep \t start \t proc \t bef.");
     for ( m=0; m<NM; m++)
      {
        printf("\n %d \t %ld \t %ld \t %ld",
                m,
                job[i].StartT[m],
                job[i].ProcT[m],
                job[i].EndT[m] );
      }
   }
}

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

  printf("\n Gep-orinetalt Gantt-diagram:\n");
  for( m=0; m<NM; m++)
   {
     printf("\n Gep: %d", m);
     printf("\n sor. \t munka \t start \t proc \t bef.");
     for ( i=0; i<NJ; i++)
      {
        printf("\n %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] );
      }
   }
}

long Evaluate( T_JOB* job, int NJ, int NM, int* s)
{
 return job[ s[NJ-1] ].EndT[NM-1];
}

void Johnson_alg( T_JOB* job, int NJ, int m1, int m2, int* s)
{
  int i, j, temp; //munka
  int min_index;      //rendezeshez
  long min, act_min;
  int* v;

  int first_pos;
  int last_pos;

  //vektor
  v = (int*) calloc(NJ, sizeof(int) );

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

  //rendezes muveleti ido szerint nemcsokkeno sorrendbe
  for ( i=0; i<NJ-1; i++)
    {
       min_index = i;
       min = min( job[ min_index].ProcT[m1], job[min_index].ProcT[m2]);
       for ( j=i+1; j<NJ; j++)
          {
            act_min = min( job[j].ProcT[m1], job[j].ProcT[m2]);
            if (  act_min < min )
                  {
                   min_index = j;
                   min = act_min;
                  }
          }

       if ( min_index != i )
         { //csere
            temp = v[i];
            v[i] = v[min_index];
            v[min_index] = temp;

         }
    }

  //utemezes
  first_pos = 0;
  last_pos = NJ-1;

  for (i=0; i<NJ; i++)
   {
     if ( job[ v[i] ].ProcT[m1] <= job[ v[i] ].ProcT[m2] )
       {  //elso gepen kisebb a muv. ido, ezert az elejere syurjuk be a mar beutemezettek moge
          s[ first_pos ] = v[i];
          first_pos++;
       }
     else
       { //vegere a mar beutemezettek ele
         s[ last_pos ] = v[i];
         last_pos--;
       }
   }


  free( v );
}

void Johnson_alg_extension( T_JOB* job, int NJ, int* s)
{
  int i, m;
  T_JOB* job_V2; //virtualis ketges feladat

  job_V2 = (T_JOB*) calloc ( NJ, sizeof(T_JOB));
  for (i=0; i<NJ; i++)
   {
     job_V2[i].ProcT = (long*) calloc( 2, sizeof(long));
     //idoadatok szarmaztatasa
     job_V2[i].ProcT[0] = job[i].ProcT[0] + job[i].ProcT[1];
     job_V2[i].ProcT[1] = job[i].ProcT[1] + job[i].ProcT[2];

   }

  //alkalmazzuk a virtualis rendszerre a Johnhson-alg.-ot
    Johnson_alg( job_V2, NJ, 0, 1, s);


  for (i=0; i<NJ; i++)
      free( job_V2[i].ProcT);
  free( job_V2 );
}

void CDS_alg( T_JOB* job, int NJ, int NM, int* s)
{
  int i, m;
  int* s_best; //legjobb megoldas
  int* s_act;  //vizsgalt megoldas
  long Cmax_best; //celfv.
  long Cmax_act;  //celfv.

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


  for ( m=0; m<NM-1; m++ ) //m-1 darab ketgepes eset
     {
       Johnson_alg( job, NJ, m, m+1, s_act);
       Simulation_F( job, NJ, NM, s_act, 0); //0 idopontban indul a folyamat
       Cmax_act = Evaluate( job, NJ, NM, s_act);

       if ( m==0 ) //elso vizsgalt eset
         {  //az elsot feltetel nelkul elfogadjuk
            Cmax_best = Cmax_act;
            copy_vector( s_act, s_best, NJ);
         }
       else
         {
           if ( Cmax_act < Cmax_best ) //jobb az uj
            {
               Cmax_best = Cmax_act;
               copy_vector( s_act, s_best, NJ);
            }
         }
     }

   //a vizsgalt megoldasok kozul a legjobb
    copy_vector( s_best, s, NJ);


   free( s_best );
   free( s_act );

}

void copy_vector( int* v1, int* v2, int NJ)
 {
   int i;
   for ( i=0; i<NJ; i++ )
       v2[i] = v1[i];
 }