/*------------------------------------------------------------------------------
TIA 2. gyakorlat
Egygépes termelésütemezési feladat modellezése és megoldása.
Az ütemezés célja a befejezési idők összegének minimalizálása,
ezáltal az átlagos készletszint minimalizálása.
Az SPT (Shortest Processing Time) műveleti idő szerint nemcsökkenő munkasorrend
optimális ütemtervet eredményez.

TIA 3. gyakorlat
Továbbfejlesztés: Határidős munkák utemezése a legnagyobb késés minimalizálása érdekében.
Egygépes termelésiütemezési feladat.
Minden munkának saját határideje van.
Az ütemezés célja a legnagyobb késés minimalizálása.
EDD Earliest Due Date (határidő szerint nemcsökkenő munkasorrend)
A megoldás optimális ütemtervet eredményez.

TIA 4. gyakorlat
Továbbfejlesztés:
Bővítés:
P||Sum(Ci)  Utemezesi fedadat megoldasa MSPT ütemezési szabály alkalmazásával.
Párhuzamos gépes termelésütemezési feladat.
Az ütemezés célja a munkák befejezési időpontjai összegének minimalizálása,
ezáltal az átlagos készletszint minimalizálása.
MSPT Modified Shortest Processing Time
módosított legrövidebb műveleti idejű munka előre:
Alkalmazzuk az SPT szabályt a munkák sorbarendezésére (műveleti idők alapján nemcsökkenő sorrendbe),
ezután képezzünk a gépek számának megfelelő hosszú csoportokat.
Az első csoport munkái az elsők rendre az egyes gépeken,
a második csoport munkái a másodikok rendre az egyes gépeken stb.
Feltétel, hogy a munkák és a gépek számának hányadosa (N/M) egész legyen,
ezt teljesíthetjük, ha bizonyos számú 0 műveleti idejű fiktív munkát hozzáadunk a rendeléscsoporthoz.
A megoldás optimális ütemtervet eredményez.

TIA 5. gyakorlat
Továbbfejlesztés:
P||Cmax ütemezési fedadat megoldása LPT+LIST ütemezési szabály alkalmazásával.
Párhuzamos gépes 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.
LPT+LIST
Alkalmazzuk az LPT szabályt a munkák sorbarendezésére (műveleti idők alapján nemnövekvő sorrendbe),
ezután az így kapott sorrendben vesszük a munkákat
és mindig a legkorábban felszabaduló gépre ütemezzük a már beütemezettek mögé,
ha több gép egyidejűleg szabadul fel, akkor a legkisebb azonosítójút terheljük.
A megoldás nem optimális mert a feladat NP-hard, de jó közelítő ütemtervet eredményez.

Bővítés:
P|di|Lmax ütemezési fedadat megoldása EDD+LIST ütemezési szabály alkalmazásával.
Párhuzamos gépes termelésiütemezési feladat.
Az ütemezés célja a legnagyobb késés minimalizálása.
EDD+LIST
Alkalmazzuk az EDD szabályt a munkák sorbarendezésére (határidők alapján nemcsökkenő sorrendbe),
ezután az így kapott sorrendben vesszük a munkákat
és mindig a legkorábban felszabaduló gépre ütemezzük a már beütemezettek mögé,
ha több gép egyidejűleg szabadul fel, akkor a legkisebb azonosítójút terheljük.
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>
#include<time.h>


#define N_OBJF 4

typedef struct {
                int id; //azonosito
                long ProcT; //muveleti ido
                long StartT; //inditasi idopont
                long EndT; //befejezesi idopont
                long d;    //hatarido
                long L;    //keses
                } T_JOB;

 typedef struct {
                 int id;  //eroforras azonosito
                 int l;   //load: terheles (gephez rendelt munkak szama)
                 long C;  //Completion time (mikor szabadul fel a terheles alol)
                } T_RES;

void Simulation( T_JOB* job, int NJ, int* s, long ref_time);
void Simulation_P( T_JOB* job, int NJ, T_RES* res, int NR,
                 int** sch, long ref_time);
void Evalute( T_JOB* job, int NJ, double* objf);
void Print_objf( double* objf);
void SPT_rule( T_JOB* job, int NJ, int* s);
void LPT_rule( T_JOB* job, int NJ, int* s);
void EDD_rule( T_JOB* job, int NJ, int* s);
void MSPT_rule( T_JOB* job, int NJ, T_RES* res, int NR, int** sch);
void EDD_LPT_LIST_alg( T_JOB* job, int NJ, T_RES* res, int NR, int** sch, int rule);
void Print_Sch( T_JOB* job, int NJ, int* s);
void Print_Sch_P( T_JOB* job, int NJ, T_RES* res, int NR, int** sch);


int main ( )
{
  time_t t;
  int NJ; //number of jobs
  int i;  //job index
  int* s;  //utemterv
  double objf[N_OBJF]; //statikus
  int NR; //number of resources

  T_JOB* job;
  T_RES* res;
  int** sch; //utemterv matrix
  int r;     //index az eroforrashoz

  srand( (unsigned) time(&t) );
  printf("\n Demo utemeyes egy eroforrasra Csum celfv-vel");
  printf("\n Kerem a munkak szamat:");
  scanf("%d", &NJ); //nincs ellenorzes
  printf("\n Eroforrasok (gep) szama:");
  scanf("%d", &NR); //nincs ellenorzes


  job = (T_JOB*) calloc(NJ, sizeof(T_JOB) ); //strukturatomb
  s = (int*) calloc(NJ, sizeof(int) );
  res = (T_RES*) calloc(NR, sizeof(T_RES) ); //strukturavektor
  sch = (int**) calloc(NR, sizeof(int*) );    //pointervektor
  for ( r=0; r<NR; r++)
      sch[r] = (int*) calloc(NJ, sizeof(int) );  //job-ok azonositoit tertalmazza

  //input generalasa
  for ( i=0; i<NJ; i++)
   { //Termelesinformatikai rendszerbol lekerdezheto a valosagban
     job[i].id = i;
     job[i].ProcT = 1 + rand() % 20;
     job[i].d = job[i].ProcT + (NJ - i)*rand()%100; //tesztelheto mas semaval
     s[i] = i; //as-hoc sorrend
     sch[0][i] = i; //ac-hoc sorrendben minden munka a 0. gepre kerul
   }
   res[0].l = NJ; //0. gepet terheli az osszes munka

   //ad-hoc
   Simulation( job, NJ, s, 0);
   Evalute( job, NJ, objf);
   printf("\n Ad-hoc sorrend eseten:");
   Print_objf( objf);

     //SPT-rule
   SPT_rule( job, NJ, s);
   Simulation( job, NJ, s, 0);
   Evalute( job, NJ, objf);
   printf("\n SPT sorrend eseten:");
   Print_objf( objf);

   EDD_rule( job, NJ, s);
   Simulation( job, NJ, s, 0);
   Evalute( job, NJ, objf);
   printf("\n EDD sorrend eseten:");
   Print_Sch( job, NJ, s);
   Print_objf( objf);

   //parhuzamos gepek
   printf("\n\n P modell");
   MSPT_rule( job, NJ, res, NR, sch);
   Simulation_P( job, NJ, res, NR, sch, 0);
   Evalute( job, NJ, objf);
   Print_Sch_P( job, NJ, res, NR, sch);
   Print_objf( objf);

   //parhuzamos gepek
   printf("\n\n P modell Cmax celfuggvennyel:");
   EDD_LPT_LIST_alg( job, NJ, res, NR, sch, 0); //LPT+LIST
   Simulation_P( job, NJ, res, NR, sch, 0);
   Evalute( job, NJ, objf);
   Print_Sch_P( job, NJ, res, NR, sch);
   Print_objf( objf);

   //parhuzamos gepek
   printf("\n\n P modell Lmax celfuggvennyel:");
   EDD_LPT_LIST_alg( job, NJ, res, NR, sch, 1); //EDD+LIST
   Simulation_P( job, NJ, res, NR, sch, 0);
   Evalute( job, NJ, objf);
   Print_Sch_P( job, NJ, res, NR, sch);
   Print_objf( objf);

  //mem. felszabaditas
  free( job );
  free( s );
  free( res );
  for( r=0; r<NR; r++)
     free( sch[r] );
  free( sch );

  getch();

  return 1;
}

void Simulation( T_JOB* job, int NJ, int* s, long ref_time)
{
  int i;

  job[ s[0] ].StartT = ref_time;
  job[ s[0] ].EndT = job[ s[0] ].StartT + job[ s[0] ].ProcT;

  for ( i=1; i<NJ; i++ )
   {
      job[ s[i] ].StartT = job[ s[i-1] ].EndT;
      job[ s[i] ].EndT = job[ s[i] ].StartT + job[ s[i] ].ProcT;

   }
}

void Evalute( T_JOB* job, int NJ, double* objf)
{
 int i;
 double Cmax;
 double Csum;
 double WIP;
 double Lmax;

 Csum = 0;
 Cmax = job[0].EndT;

 job[0].L = job[0].EndT - job[0].d; //keses
 Lmax = job[0].L;

 for ( i=0; i<NJ; i++)
  {
    if ( Cmax < job[i].EndT )
        Cmax = job[i].EndT;

    Csum += job[i].EndT;

    job[i].L = job[i].EndT - job[i].d; //keses
    if ( Lmax < job[i].L )
         Lmax = job[i].L;
  }

  WIP = Csum / Cmax;

  objf[0] = Cmax;
  objf[1] = Csum;
  objf[2] = WIP;
  objf[3] = Lmax;
}

void Print_objf( double* objf)
{
  printf("\n Cmax=%lf", objf[0]);
  printf("\n Csum=%lf", objf[1]);
  printf("\n WIP=%lf", objf[2]);
  printf("\n Lmax=%lf", objf[3]);

}

void SPT_rule( T_JOB* job, int NJ, int* s)
{
  int i,j, index, temp;

  //inic.
  for ( i=0; i<NJ; i++)
    s[i]=i;

  for ( i=0; i<NJ-1; i++)
   {
    index = i;
     for ( j=i+1; j<NJ; j++)
       if ( job[ s[index] ].ProcT > job[ s[j] ].ProcT )
         index = j;

     if ( index != i )
       { //csere
         temp = s[index];
         s[index] = s[i];
         s[i] = temp;
       }
    }
}

void LPT_rule( T_JOB* job, int NJ, int* s)
{
  int i,j, index, temp;

  //inic.
  for ( i=0; i<NJ; i++)
    s[i]=i;

  for ( i=0; i<NJ-1; i++)
   {
    index = i;
     for ( j=i+1; j<NJ; j++)
       if ( job[ s[index] ].ProcT < job[ s[j] ].ProcT )
         index = j;

     if ( index != i )
       { //csere
         temp = s[index];
         s[index] = s[i];
         s[i] = temp;
       }
    }
}

void EDD_rule( T_JOB* job, int NJ, int* s)
{
  int i,j, index, temp;

  //inic.
  for ( i=0; i<NJ; i++)
    s[i]=i;

  for ( i=0; i<NJ-1; i++)
   {
    index = i;
     for ( j=i+1; j<NJ; j++)
       if ( job[ s[index] ].d > job[ s[j] ].d )
         index = j;

     if ( index != i )
       { //csere
         temp = s[index];
         s[index] = s[i];
         s[i] = temp;
       }
    }
}

void Print_Sch( T_JOB* job, int NJ, int* s)
{
  int i;
  printf("\n id \t Start \t ProcT \t End \t d \t L");
  for ( i=0; i<NJ; i++)
     printf("\n %d \t %ld \t %ld \t %ld \t %ld \t %ld",
                s[i],
                job[s[i]].StartT,
                job[s[i]].ProcT,
                job[s[i]].EndT,
                job[s[i]].d,
                job[s[i]].L );

}

void Print_Sch_P( T_JOB* job, int NJ, T_RES* res, int NR, int** sch)
{
 int r;
 printf("\n\n Utemezes:");
 for ( r=0; r<NR; r++)
  {
    printf("\n %d. eroforras: \n" );
    Print_Sch(job, res[r].l, sch[r]);
   }

}

void Simulation_P( T_JOB* job, int NJ, T_RES* res, int NR,
                 int** sch, long ref_time)
{
  //A szabalyok lehetove teszik a virtualis parhuzamositast a
  //szimulacio megvalositasakor
  int r;

  for (r=0; r<NR; r++)
   Simulation( job, res[r].l, sch[r], ref_time);

}

void MSPT_rule( T_JOB* job, int NJ, T_RES* res, int NR, int** sch)
{
 int i;
 int r;
 int* v;
 int sel_r; //kijelolt gep
 int sel_pos; //kijelolt pozicio

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

 //1. elokeszites
  SPT_rule( job, NJ, v); //rendezes
  for (r=0; r<NR; r++)
     res[r].l = 0;       //nincs terheles a gepeken

 //2. munkak szetosztasa
 for ( i=0; i<NJ; i++)
  {
    //melyik gepre?
    sel_r = i % NR;
    sel_pos = res[ sel_r ].l; //pozicio
    sch[ sel_r ][ sel_pos ] = v[i];   //beutemezve
    res[ sel_r ].l++;   //terheles novelese
  }

 free( v );
}

void EDD_LPT_LIST_alg( T_JOB* job, int NJ, T_RES* res, int NR, int** sch, int rule)
{
 //Nem garantalhato a legjobb megoldas elerese
 //Kozelito jo megoldas erheto el.
 int i;
 int r;
 int* v;
 int sel_r; //kijelolt gep
 int sel_pos; //kijelolt pozicio
 int k;

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

 //1. elokeszites
  if ( rule == 0 )
     LPT_rule( job, NJ, v); //rendezes
  else
     EDD_rule( job, NJ, v); //rendezes

  for (r=0; r<NR; r++)
    {
     res[r].l = 0;       //nincs terheles a gepeken
     res[r].C = 0;       //terheles nelkul elerheto
     }

 //2. munkak szetosztasa List algoritmussal
 //a legkorabban felszabadulo gepet terheljuk
 for ( i=0; i<NJ; i++)
  {
    //melyik gepre?
    sel_r = 0;
    for ( k=1; k<NR; k++ )
       if ( res[ k ].C < res[ sel_r ].C )
            sel_r = k;

    sel_pos = res[ sel_r ].l; //pozicio
    sch[ sel_r ][ sel_pos ] = v[i];   //beutemezve
    res[ sel_r ].l++;   //terheles novelese
    res[ sel_r ].C += job[ v[i] ].ProcT;  //a gep bef. idopontja no az uj muvelet proc. idejevel
  }

 free( v );
}