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

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.

Tovabbfejlesztes:
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. 


-------------------------------------------------------------------------------*/

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

#define N_OBJF 4

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

typedef struct {
                int id;
                int l;   //load, terheles (a gephez rendelt munkak szama)
               } T_RES;

void Simulate( T_JOB* job, int NJ, int* s, long t_ref);
void Simulate_P( T_JOB* job, int NJ, T_RES* res, int NR,
                 int** sch, long t_ref);
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 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 Print_s( 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()
{
 int NJ; //munkak szama
 T_JOB* job; //munkak adatait
 int i;
 int* s;  //utemterv
 double objf[N_OBJF];
 time_t t;
 int NR; //eroforrasok szama
 T_RES* res; //eroforrasok
 int** sch;   //utemezes matrixa
 int r;       //eroforras index

 srand( time(&t) ); //veletlenszam generator inic.

 printf("\n Kerem a munkak szamat:");
 scanf("%d", &NJ); //vedelem nincs
 printf("\n Eroforrasok szama:");
 scanf("%d", &NR); //ellenorzes nincs

 job = (T_JOB*) calloc(NJ, sizeof(T_JOB) ); //strukturavektor
 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) ); //matrix

 //input adatok generalasa
 //valos rendszbol ezek lekerdezhetok
 for ( i=0; i<NJ; i++)
  {
   job[i].id = i;
   job[i].ProcT = 1 + rand()%20;
   job[i].d = job[i].ProcT + (NJ-i)*rand()%100;

   s[i] = i; //inic. utemterv AD-HOC sorrend
   sch[0][i] = i; //egyetlen gepre az osszes munka
  }
  res[0].l = NJ; //inic.

 //Ad-hoc sorrendet
  printf("\n Ad-hoc sorrend szerinti vegrehajtas:");
  Simulate( job, NJ, s, 0); //referencia ido 0
  Evalute( job, NJ, objf);
  Print_objf(objf);

 //SPT sorrendet
  printf("\n SPT sorrend szerinti vegrehajtas:");
  SPT_rule( job, NJ, s);
  Simulate( job, NJ, s, 0); //referencia ido 0
  Evalute( job, NJ, objf);
  Print_objf(objf);

 //EDD sorrendet
  printf("\n EDD sorrend szerinti vegrehajtas:");
  EDD_rule( job, NJ, s);
  Simulate( job, NJ, s, 0); //referencia ido 0
  Evalute( job, NJ, objf);
  Print_objf(objf);

  //P modell
  printf("\n P modell MSPT-vel utemezve:\n");
  MSPT_rule( job, NJ, res, NR, sch);
  Simulate_P( job, NJ, res, NR, sch, 0);
  Evalute( job, NJ, objf);
  Print_objf(objf);
  Print_sch_P( job, NJ, res, NR, sch);



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

 getch();
 return 1;
}

void Simulate( T_JOB* job, int NJ, int* s, long t_ref)
{
  int i;

  job[ s[0] ].StartT = t_ref;
  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;  //Work in process, atlagos keszletszint
 double Lmax;

 Csum = 0;
 Cmax = job[0]. EndT;
 job[0].L = job[0].EndT - job[0].d;
 Lmax = job[0].L;

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

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

  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, temp, index;

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

  for ( i=0; i<NJ-1; i++)
   {
     index = i;
     for (j=i+1; j<NJ; j++)
        if ( job[ s[j] ].ProcT < job[ s[index] ].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, temp, index;

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

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

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

}

void Simulate_P( T_JOB* job, int NJ, T_RES* res, int NR,
                 int** sch, long t_ref)
{
 //a parhuzamosan mukodo eroforrasok szimulaciojat szekvencialisan valositjuk meg
 int r;

 for (r=0; r<NR; r++)
   Simulate( job, res[r].l, sch[r], t_ref);
             //  sajat terheles es sajat utemezesvektor
}

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

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

  //MSPT elso fazisa
  SPT_rule( job, NJ, v);

  for (r=0; r<NR; r++)
     res[r].l = 0;      //ures utemterv, nincs terheles

  //MSPT masodik fazisa
  for (i=0; i<NJ; i++)
   {
     //munka v[i]
     //melyik gepre?
     sel_r = i % NR;  //osztasi maradek

     //melyik pozicioba?
     sel_pos = res[sel_r].l;

     //gep terheles?
     sch[sel_r][sel_pos] = v[i]; //utemterv vegere
     res[sel_r].l++;             //noveljuk a szamlalot
    }

  free( v );
}

void Print_s( T_JOB* job, int NJ, int* s)
{
  int i;
  printf("\n sor \t job \t start \t proc. \t end \t d \t L");
  for ( i=0; i<NJ; i++)
     printf("\n %d \t %d \t %ld \t %ld \t %ld \t %ld \t %ld",
             i,
             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 Utemezesi matrix:");
  for ( r=0; r<NR; r++)
    {
     printf("\n %d eroforras:", r);
     Print_s( job, res[r].l, sch[r]);
    }

}