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



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

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;      //munka

typedef struct{
              long Csum;
              long Cmax;    //max. Completion Time
              double ASL;   //average stock level, atlagos keszletszint
              long Lmax;    //max. Lateness, legnagyobb keses
              }T_OBJF;      //objective function

typedef struct{
              int id;
              int l;        //load, terheles: vegrehajtando munkak szama
              }T_RES;       //resource, eroforras

void Simulation(T_JOB* job, int NJ, int* sch, long t_ref);
long Evaluate_Csum(T_JOB* job, int NJ);
void Evaluate(T_JOB* job, int NJ, T_OBJF* obj);
void print_gantt(T_JOB* job, int NJ, int* sch);
void SPT_rule(T_JOB* job, int NJ, int* sch);
void EDD_rule(T_JOB* job, int NJ, int* sch);
void print_obj(T_OBJF* obj);

void Simulation_P(T_JOB* job, int NJ, T_RES* res, int NM, int** s, long t_ref);
void MSPT_rule(T_JOB* job, int NJ, T_RES* res, int NM, int** s);
void print_gantt_P(T_JOB* job, int NJ, T_RES* res, int NM, int** s);



int main(int argc, char* argv[])
{
  int NJ;     //number of jobs, munkak szama
  T_JOB* job; //strukturavektorra mutato pointer
  int i;      //munka futoindexe
  int* sch;   //schedule utemterv
  long Csum;  //celfuggveny erteke
  T_OBJF obj; //celfuggvenyek

  int** s;    //parhuzamos gepek eseten a megoldast egy matrix irja le
  int NM;     //number of machine, gepek szama
  int m;      //gepek futoindexe
  T_RES* res; //eroforrasok

  //input generalas
  printf("\n Parhuzamos gepek termelesutemezesi feladata.");
  printf("\n Munkak szama: ");
  scanf("%d", &NJ);
  printf("\n Eroforrasok szama: ");
  scanf("%d", &NM);

  //memmoriafoglalas
  //eroforras
  res = (T_RES*) calloc( NM, sizeof(T_RES) );

  //matrix
  s = (int**) calloc( NM, sizeof(int*) );
  for( m=0; m<NM; m++ )
    {
      s[m] = (int*) calloc( NJ, sizeof(int) );
      res[m].id = m;    //azonosito
      res[m].l = 0;     //terheles
    }


  job = (T_JOB*) calloc( NJ, sizeof(T_JOB) ); //strukturavektor
  sch = (int*) calloc( NJ, sizeof(int) );     //vektor
  for ( i = 0; i<NJ; i++ )
    {
      job[i].id = i; //sorszam jelenti az azonositot
      job[i].ProcT = 1 + rand()%20;   //1 es 20 kozotti veletlenszam
      job[i].d = (1 + rand()%NJ) * (1 + rand()%30);
      sch[i] = i;   //ad-hoc sorrend

      s[0][i] = i;     //kezdeti megoldas
      res[0].l = NJ;   //osszes munka a 0. gephez tartozik

    }

  /*
  //Ad-hoc sorrend
  Simulation_P(job, NJ, res, NM, s, 0);
  Evaluate(job, NJ, &obj);

  printf("\n Ad-hoc sorrend ");
  print_gantt_P(job, NJ, res, NM, s);
  print_obj(&obj);
 */
 
  //MSPT, Modified Shortest Processing Time
  MSPT_rule(job, NJ, res, NM, s);
  Simulation_P(job, NJ, res, NM, s, 0);
  Evaluate(job, NJ, &obj);
  printf("\n MSPT sorrend");
  print_gantt_P(job, NJ, res, NM, s);
  print_obj(&obj);

 /*
  //EDD sorrend
  EDD_rule(job, NJ, sch);
  Simulation(job, NJ, sch, 0);
  print_gantt(job, NJ, sch);
  Evaluate(job, NJ, &obj);
  printf("\n EDD sorrend");
  print_obj(&obj);
 */

  getch();

  //memoria felszabaditas
  free( job );
  free( sch );

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

  //eroforras
  free ( res );


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

void Simulation(T_JOB* job, int NJ, int* sch, long t_ref)
{
  //egygepes gyartorendszer szimulacioja
  //bemenetkend adott utemterv szerint
  //szamoljuk a munkak kezdesi es befejezesi idopontjat

  int i; //munkak futoindexe

  job[ sch[0] ].StartT = t_ref;
  job[ sch[0] ].EndT = job[ sch[0] ].StartT + job[ sch[0] ].ProcT;
  //befejezes = inditas + muvelet
  job[ sch[0] ].L = job[ sch[0] ].EndT - job[ sch[0] ].d; //keses = befejezes idopontja - hatarido


  for (i=1; i<NJ; i++)
    {
      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; //keses = befejezes idopontja - hatarido

    }
}

void Simulation_P(T_JOB* job, int NJ, T_RES* res, int NM, int** s, long t_ref)
{
  //mivel a gepek egymastol fuggetlenul mukodnek
  //kulon-kulon szimulalhato a mukodes
  int m;
  for ( m = 0; m < NM; m++ )
    //az m. gep utemterve az s matrix m. sora
    //az m. gephez tertozo munkak szama res[m].l
    Simulation(job, res[m].l, s[m], t_ref);

}

long Evaluate_Csum(T_JOB* job, int NJ)
{
  long Csum = 0;
  int i;
  for(i=0; i<NJ; i++)
    Csum += job[i].EndT;
    //befejezesi idopontok osszege
    //egyenlo a keszletdiagram alatti terulet nagysagaval

  return Csum;
}

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

  int i;
  for(i=0; i<NJ; i++)
   {
    Csum += job[i].EndT;
    //befejezesi idopontok osszege
    //egyenlo a keszletdiagram alatti terulet nagysagaval
    if ( Cmax < job[i].EndT )
         Cmax = job[i].EndT;

    if ( Lmax < job[i].L )
         Lmax = job[i].L;

   }


    obj->Csum = Csum;
    obj->Cmax = Cmax;
    obj->ASL = (double) Csum / Cmax;
    obj->Lmax = Lmax;
}

void print_gantt(T_JOB* job, int NJ, int* sch)
{
  int i;
  printf("\n Munkak vegrehajtasanak idoadatai:");
  printf("\n Sorszam \t Munka \tIndul\t Befejezes \t Hatarido \t Keses");

  for ( i=0; i<NJ; i++ )
    printf("\n\t %d \t %d \t %ld \t %ld \t\t %ld \t\t %ld",
            i,
            job[ sch[i] ].id,
            job[ sch[i] ].StartT,
            job[ sch[i] ].EndT,
            job[ sch[i] ].d,
            job[ sch[i] ].L);

}

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

}

void SPT_rule(T_JOB* job, int NJ, int* sch)
{
  //Shortest Processing Time
  //muveleti ido szerint nemcsokkeno munkasorrend kialakitasa
  int i, j;
  int temp;

  for( i=0; i < NJ-1; i++ )
    for( j=i+1; j < NJ; 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 NJ, int* sch)
{
  //Earliast Due Date
  //hatarido szerint nemcsokkeno munkasorrend kialakitasa
  int i, j;
  int temp;

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


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

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

  int* r;
  r = (int*) calloc( NJ, sizeof(int) );
  for( i=0; i<NJ; i++ )
     r[i] = i;
  //1. lepes SPT rendezes
  SPT_rule(job, NJ, r);

  //for( i=0; i<NJ; i++ )
  //   printf("\n %d", r[i]);


  //2. lepes szetosztes
  //terheles nullazasa
  for( m=0; m<NM; m++)
     res[m].l = 0;
  //terheles szetosztasa
  for( i=0; i<NJ; i++ )
    {
      m = i % NM;    //kivalasztott gep
      s[ m ][ res[ m ].l ] = r[i];
      res[ m ].l++;  //noveli a gep terheleset
      //printf("\n m = %d l = %d r[i] = %d", m, res[m].l, r[i]);
    }

  free( r );

}