/*------------------------------------------------------------------------------
1||Szum(Ci)  Utemezesi fedadat megoldasa SPT ütemezési szabály alkalmazásával.
Egygépes termelésiütemezési feladat.
Az ütemezés célja a befejezési idők összegének minimalizálása, 
ezáltal az átlagos készletszint minimalizálása.
SPT Shortest Processing Time (műveleti idő szerint nemcsökkenő munkasorrend)
A megoldás optimális ütemtervet eredményez.

Bővítés:
1|di|Lmax
Egygépes termelésiütemezési feladat.
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.
-------------------------------------------------------------------------------*/

/*-------------------------------------------------------------------------------
P||Szum(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. 
-------------------------------------------------------------------------------*/

/*-------------------------------------------------------------------------------
P||max(Ci)  Utemezesi fedadat megoldasa 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. 
-------------------------------------------------------------------------------*/




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

typedef struct{
               int id;      //azonsito
               long ProcT;  //muveleti ido
               long StartT; //kezdesi ido
               long EndT;   //befejezesi ido
               long d;      //hatarido
               long L;      //keses
               }T_JOB;      //Munka (Job)

typedef struct{
               long Csum;  //befejezesi idopontok osszege
               double ASL; //atlagos keszletszint
               long Lmax;  //legnagyobb keses
               long Cmax;  //utolso munka befejezesi idopontja
               }T_OBJF;    //celfuggveny, objective function

typedef struct{
               int id;
               int l;      //load, terheles (elvegzendo munkak szama)
               long Cmax;   //completion time on the resource, felszabadulas ideje
              }T_RES;      //resource

void Simulation(T_JOB* job, int* sch, int NJ, int t_ref);
void Simulation_P(T_JOB* job, int** s, int NJ, int NM, T_RES* res, int t_ref);

//void Evaluate(T_JOB* job, int* sch, int NJ, T_OBJF* obj);
void Evaluate(T_JOB* job, int NJ, T_OBJF* obj);

void Print_Job_Gantt(T_JOB* job, int* sch, int NJ); //idotabla megjelenitese
void Print_Res_Gantt(T_JOB* job, int** s, int NJ, int NM, T_RES* res);

void SPT_rule(T_JOB* job, int* sch, int NJ);
void EDD_rule(T_JOB* job, int* sch, int NJ);
void MSPT_rule(T_JOB* job, int** s, int NJ, int NM, T_RES* res);
void Print_ObjF(T_OBJF* obj);
void LPT_rule(T_JOB* job, int* sch, int NJ);
void LPT_List_rule(T_JOB* job, int** s, int NJ, int NM, T_RES* res);








int main(int argc, char* argv[])
{
  int i;  //futoindex a munkakhoz
  int NJ; //munkak szama
  int m;  //gepek (eroforrasok) futoindexe
  int NM; //gepek eroforrasok) szama
  T_RES* res; //eroforrasok listaja
  T_JOB* job; //strukturavektorra mutato pointer
  //int* sch;  //utemterv vektorara mutato pointer
  int** s;   //utemterv a parhuzamos gepek szamara
  long t_ref = 0; //referencia idopont
  T_OBJF obj;

  printf("\n Parhuzamos gepeket uzemelteto gyartorendszer utemezese.");
  printf("\n Munkak szama:");
  scanf("%d", &NJ);   //betoltes bill.-rol

  printf("\n Gepek szama:");
  scanf("%d", &NM);   //betoltes bill.-rol

  //memoriafoglalas
  res = (T_RES*) calloc( NM, sizeof(T_RES) );
  for( m=0; m<NM; m++)
    {
      res[m].id = m;
      res[m].l = 0;
    }

  job = (T_JOB*) calloc( NJ, sizeof(T_JOB) );
  //parhuzamos gepek eseten a dontesi valtozo egy matrix
  //sch = (int*) calloc( NJ, sizeof(int) );
  s = (int**) calloc(NM, sizeof(int*) );
  for ( m=0; m<NM; m++)
       s[m] = (int*) calloc(NJ, sizeof(int) );

  //input adatok generalasa
  for (i=0; i<NJ; i++)
    {
      job[i].id = i;
      job[i].ProcT = 1 + rand()%20;
      job[i].d = 1 + (1 + rand()%8) * (1+rand()%5) * NJ;
      //sch[i] = i;  //azonosito szerinti sorrend
      s[0][i] = i;   //egy gephez rendeltuk az osszes munkat
    }
    res[0].l = NJ;

  //muveletek
  //Ad-hoc
  Simulation_P(job, s, NJ, NM, res, t_ref);
  Evaluate(job, NJ, &obj);
  printf("\n Ad-hoc sorrend");
  //Print_Job_Gantt(job, sch, NJ);
  Print_Res_Gantt(job, s, NJ, NM, res);
  Print_ObjF(&obj);

  //MSPT szabaly alkalmazasa
  MSPT_rule(job, s, NJ, NM, res); //rendezes nemcsokkeno sorrendbe, es szetosztas
  Simulation_P(job, s, NJ, NM, res, t_ref);
  Evaluate(job, NJ, &obj);
  printf("\n MSPT sorrend");
  //Print_Job_Gantt(job, sch, NJ);
  Print_Res_Gantt(job, s, NJ, NM, res);
  Print_ObjF(&obj);

  //LPT+List szabaly alkalmazasa
  LPT_List_rule(job, s, NJ, NM, res); //rendezes nemcsokkeno sorrendbe, es szetosztas
  Simulation_P(job, s, NJ, NM, res, t_ref);
  Evaluate(job, NJ, &obj);
  printf("\n LPT+List sorrend");
  //Print_Job_Gantt(job, sch, NJ);
  Print_Res_Gantt(job, s, NJ, NM, res);
  Print_ObjF(&obj);


  /*
  //EDD
  EDD_rule(job, sch, NJ); //rendezes nemcsokkeno sorrendbe
  Simulation(job, sch, NJ, t_ref);
  Evaluate(job, sch, NJ, &obj);
  printf("\n EDD sorrend");
  Print_Job_Gantt(job, sch, NJ);
  printf("\n Csum = %ld \n ASL = %lf \n Lmax = %ld",
       obj.Csum,
       obj.ASL,
       obj.Lmax );
  */

  //momoriafelszabaditas
  free( job );
  free( res );

  //matrix lebontasa
  for( m=0; m<NM; m++ )
     free( s[m] );
  free(s);

  getch(); //bill. lenyomasara var
  return 0;
}
//---------------------------------------------------------------------------

void Simulation(T_JOB* job, int* sch, int NJ, int t_ref)
{
  int i;

  job[ sch[0] ].StartT = t_ref; //elso munka a ref idopontban indul
  job[ sch[0] ].EndT = job[ sch[0] ].StartT + job[ sch[0] ].ProcT;
  job[ sch[0] ].L = job[ sch[0] ].EndT - job[ sch[0] ].d;

  for(i=1; i<NJ; i++) //i az utemterv altal eloirt sorszam
    {
       job[ sch[i] ].StartT = job[ sch[i-1] ].EndT;
       job[ sch[i] ].EndT = job[ sch[i] ].StartT + job[ sch[i] ].ProcT;
       job[ sch[i] ].L = job[ sch[i] ].EndT - job[ sch[i] ].d;
    }
}

//void Evaluate(T_JOB* job, int* sch, int NJ, T_OBJF* obj)
void Evaluate(T_JOB* job, int NJ, T_OBJF* obj)
{
  long Csum = 0;
  int i;
  long Lmax = job[ 0 ].L;
  long Cmax = job[ 0 ].EndT;

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

    if ( Cmax < job[ i ].EndT )
         Cmax = job[ i ].EndT;
   }

  obj->Csum = Csum;
  //obj->ASL = (double) Csum / job[ sch[NJ-1] ].EndT;
  obj->ASL = (double) Csum / Cmax;
  obj->Lmax = Lmax;
  obj->Cmax = Cmax;

}

void Print_Job_Gantt(T_JOB* job, int* sch, int NJ)
{
  int i;

  printf("\n Sorszam \t Munka \t Indit \t Befejez \t Hatarido \t Keses");
  for (i=0; i<NJ; i++)
    printf("\n %d \t\t %d \t %ld \t %ld \t\t %ld \t\t %ld",
            i,
            sch[i],
            job[ sch[i] ].StartT,
            job[ sch[i] ].EndT,
            job[ sch[i] ].d,
            job[ sch[i] ].L);
}

void Print_Res_Gantt(T_JOB* job, int** s, int NJ, int NM, T_RES* res)
{
  int m;
  for( m=0; m<NM; m++)
     {
       printf("\n %d eroforras <%d> \n", m, res[m].l );
       Print_Job_Gantt(job, s[m], res[m].l);  //egy gep

     }
}


void SPT_rule(T_JOB* job, int* sch, int NJ)
{
  //SPT szerinti rendezes
  int i, j;
  int temp;

  for ( i=0; i < NJ-1; i++)
    for  ( j=i+1; j <= NJ-1; j++ )
       if ( job[ sch[i] ].ProcT > job[ sch[j] ].ProcT )
         { //csere
           temp = sch[i];
           sch[i] = sch[j];
           sch[j] = temp;
         }
}

void EDD_rule(T_JOB* job, int* sch, int NJ)
{
  //EDD szerinti rendezes
  int i, j;
  int temp;

  for ( i=0; i < NJ-1; i++)
    for  ( j=i+1; j <= NJ-1; j++ )
       if ( job[ sch[i] ].d > job[ sch[j] ].d )
         { //csere
           temp = sch[i];
           sch[i] = sch[j];
           sch[j] = temp;
         }
}

void Simulation_P(T_JOB* job, int** s, int NJ, int NM, T_RES* res, int t_ref)
{
  int m;

  for( m=0; m<NM; m++) //minden gepet kulon-kulon szimulalunk
    Simulation(job, s[m], res[m].l, t_ref);

}

void MSPT_rule(T_JOB* job, int** s, int NJ, int NM, T_RES* res)
{
  //fiktiv munkak nelkul is ugyanaz a celfuggveny ertek
  int i;
  int m;
  int* r;
  r = (int*) calloc(NJ, sizeof(int) );
  for( i=0; i<NJ; i++)
     r[i] = i;

  //SPT
  SPT_rule(job, r, NJ);

  for(m=0; m<NM; m++)
    res[m].l = 0;    //kezdetben nincs munka hozzarendelve

  for( i=0; i<NJ; i++)
   {
     m = i % NM;//kivalssztott gep
     s[ m ][ res[m].l ] = r[i]; //szetosztas
     //fontos
     res[ m ].l++;
   }

  free(r);
}

void Print_ObjF(T_OBJF* obj)
{
  printf("\n Csum = %ld \
          \n ASL = %lf \
          \n Lmax = %ld \
          \n Cmax = %ld",
       obj->Csum,
       obj->ASL,
       obj->Lmax,
       obj->Cmax );

}

void LPT_List_rule(T_JOB* job, int** s, int NJ, int NM, T_RES* res)
{
  //heurisztikus megoldas
  int i;
  int m;
  int tm; //target machine
  int* r;
  r = (int*) calloc(NJ, sizeof(int) );
  for( i=0; i<NJ; i++)
     r[i] = i;

  //LPT
  LPT_rule(job, r, NJ);

  //terheles inicializalasa
  for(m=0; m<NM; m++)
    {
    res[m].l = 0;    //kezdetben nincs munka hozzarendelve
    res[m].Cmax = 0; //az eroforras felszabudalasi idopontja
    }

  for( i=0; i<NJ; i++)
   {
     //eroforras kivalasztasa
     tm = 0;
     for ( m=1; m<NM; m++ )
        if ( res[tm].Cmax > res[m].Cmax )
             tm = m;   //kivalasztas

     //terheles
     s[ tm ][ res[tm].l ] = r[i]; //munka a gep soranak soronkovetkezo rekeszebe
     res[tm].l++;  //munkak szama a gepen
     res[tm].Cmax += job[ r[i] ].ProcT;  //felszabadulas idopontja

   }

  free(r);
}

void LPT_rule(T_JOB* job, int* sch, int NJ)
{
  //LPT szerinti rendezes
  int i, j;
  int temp;

  for ( i=0; i < NJ-1; i++)
    for  ( j=i+1; j <= NJ-1; j++ )
       if ( job[ sch[i] ].ProcT < job[ sch[j] ].ProcT )
         { //csere
           temp = sch[i];
           sch[i] = sch[j];
           sch[j] = temp;
         }
}