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


/*------------------------------------------------------------------------------
1||Tmax  Utemezesi fedadat megoldasa EDD ütemezési szabály alkalmazásával.
Egygépes termelésiütemezési feladat.
Az ütemezés célja a legnagyobb csúszá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 (M) 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<conio.h>
#include<stdlib.h>
#include<alloc.h>

typedef struct {
                int id;
                long ProcT,
                     StartT,
                     EndT,
                     T, /*Tardiness, csuszas*/
                     d; /*Due Date, hatarido*/
                } T_JOB;

typedef struct {
                long Csum,
                     Tmax,
                     Cmax;
                } T_OBJ;

typedef struct {
                int id,
                    l; /* a hozzarendelt munkak szama*/
                long C; /* felszabadulas idopontja*/
                } T_MACHINE;

void Simulation(T_JOB* job, int N, int* sch, long t);
void Simulation_P(T_JOB* job, int N, T_MACHINE * machine, int M, int** s, long t);
void Evaluation(T_JOB* job, int N, T_OBJ* obj);
void SPT_rule(T_JOB* job, int N, int* sch);
void LPT_rule(T_JOB* job, int N, int* sch);
void EDD_rule(T_JOB* job, int N, int* sch);
void Print_Gantt(T_JOB* job, int N, int* sch);
void Print_Mach_Gantt(T_JOB* job, int N, T_MACHINE * machine, int M, int** s);
void MSPT_rule(T_JOB* job, int N, T_MACHINE * machine, int M, int** s);
void LPT_List_rule(T_JOB* job, int N, T_MACHINE * machine, int M, int** s);

int main(int argc, char* argv[])
{
 T_JOB* job;
 T_OBJ obj;
 int* sch;
 int** s; //ketdimenzios tomb
 T_MACHINE* machine;
 int N; //job-ok szama
 int M; //gepek szama
 int i, m;
 long Csum;

 printf("Kerem a munkak szamat:");
 scanf("%d", &N);

 printf("\n Kerem a gepek szamat:");
 scanf("%d", &M);
 /* egygepes feladatban az utemtervet leiro dontesi valtozo egy vektor*/
 sch = (int*) calloc(N, sizeof(int));
 /* parhuzamosgepes feladatban az utemtervet leiro dontesi valtozo egy matrix*/
 s = (int**) calloc(M, sizeof(int*));
 for (m=0; m<M; m++)
   {
   s[m] = (int*) calloc(N, sizeof(int));
   for (i=0; i<N; i++)
      s[m][i] = 0;
   }

 machine = (T_MACHINE*) calloc(M, sizeof(T_MACHINE));
 for (m=0; m<M; m++)
    machine[m].l = 0;

 job = (T_JOB*) calloc(N, sizeof(T_JOB));
 randomize();
 for (i=0; i<N; i++)
 {
   job[i].id = i;
   job[i].ProcT = 1 + random(200);
   job[i].d = 1 + random(50) * random(5) * N;
   sch[i]=job[i].id;
   /* Figyelem! gyakorlaton ez okozta az exception-t:
   s[0]=job[i].id;
   */
   /* az elso gepre terheljuk az osszes munkat */
   s[0][i]= job[i].id;
   /* Figyelem */
   //printf("\n ProcT = %ld \n", job[i].ProcT );
 }
 machine[0].l = N;  /*az elso gepen az osszes munka */

 /*
 //Ad-hoc sorrend
 Simulation(job, N, sch, 0);
 Evaluation(job, N, &obj);
 printf("\n Ad-hoc sorrend eseten Csum = %ld", obj.Csum);
 printf("\n Ad-hoc sorrend eseten Tmax = %ld", obj.Tmax);
 Print_Gantt(job, N, sch);
 getch();
 */

 /*LPT+List sorrend*/
 LPT_List_rule(job, N, machine, M, s);
 Simulation_P(job, N, machine, M, s, 0);
 Evaluation(job, N, &obj);
 printf("\n LPT+List sorrend eseten Csum = %ld", obj.Csum);
 printf("\n LPT+List sorrend eseten Tmax = %ld", obj.Tmax);
 printf("\n LPT+List sorrend eseten Cmax = %ld", obj.Cmax);
 //Print_Gantt(job, N, sch);
 Print_Mach_Gantt(job, N, machine, M, s);

 getch();


 /*MSPT sorrend*/
 MSPT_rule(job, N, machine, M, s);
 Simulation_P(job, N, machine, M, s, 0);
 Evaluation(job, N, &obj);
 printf("\n MSPT sorrend eseten Csum = %ld", obj.Csum);
 printf("\n MSPT sorrend eseten Tmax = %ld", obj.Tmax);
 printf("\n MSPT sorrend eseten Cmax = %ld", obj.Cmax);
 //Print_Gantt(job, N, sch);
 Print_Mach_Gantt(job, N, machine, M, s);
 getch();
/*
 //SPT sorrend
 SPT_rule(job, N, sch);
 Simulation(job, N, sch, 0);
 Evaluation(job, N, &obj);
 printf("\n SPT sorrend eseten Csum = %ld", obj.Csum);
 printf("\n SPT sorrend eseten Tmax = %ld", obj.Tmax);
 Print_Gantt(job, N, sch);
 getch();

 //EDD sorrend
 EDD_rule(job, N, sch);
 Simulation(job, N, sch, 0);
 Evaluation(job, N, &obj);
 printf("\n EDD sorrend eseten Csum = %ld", obj.Csum);
 printf("\n EDD sorrend eseten Tmax = %ld", obj.Tmax);
 Print_Gantt(job, N, sch);
 */
 free (job);
 free (sch);
 for (m=0; m<M; m++)
    if (s[m]!=NULL) free(s[m]);
 free(s);
 free(machine);

 getch();

 return 0;
}
//---------------------------------------------------------------------------
void Simulation(T_JOB* job, int N, int* sch, long t)
{
  int i;
  job[ sch[0] ].StartT = t;
  job[ sch[0] ].EndT = job[ sch[0] ].StartT + job[ sch[0] ].ProcT;
  for (i=1; i<N; i++)
  {
    job[ sch[i] ].StartT = job[ sch[i-1] ].EndT;
    job[ sch[i] ].EndT = job[ sch[i] ].StartT + job[ sch[i] ].ProcT;

  }
}

void Simulation_P(T_JOB* job, int N, T_MACHINE * machine, int M, int** s, long t)
{
 int m;

 for (m=0; m<M; m++)
    /* figyelem hibas:
    if (machine[m].l < 1 ) Simulation(job, machine[m].l, s[m], t);
    helyesen:
    */
    if (machine[m].l > 0 ) Simulation(job, machine[m].l, s[m], t);
    /* ha nincs a gephez munka hozzarendelve nem kell szamolni*/
}

void Evaluation(T_JOB* job, int N, T_OBJ* obj)
{
  int i;
  obj->Csum = 0;
  obj->Tmax = 0;
  obj->Cmax = 0;

  for (i=0; i<N; i++)
    {
      obj->Csum += job[i].EndT;
      job[i].T = max( 0, job[i].EndT - job[i].d);
      if ( i==0 )
          {
          obj->Tmax = job[i].T;
          obj->Cmax = job[i].EndT;
          }
      else {
           if ( obj->Tmax < job[i].T )
              obj->Tmax = job[i].T;

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

}

void SPT_rule(T_JOB* job, int N, int* sch)
{
  int i, j;
  int temp;
  /* Shortest Processing Time */
  for (i=0; i<N-1; i++)
    for (j=i+1; j<N; j++)
      if ( job[ sch[i] ].ProcT > job[ sch[j] ].ProcT )
         {
           temp = sch[i];
           sch[i] = sch[j];
           sch[j] = temp;
         }

}

void LPT_rule(T_JOB* job, int N, int* sch)
{
  int i, j;
  int temp;
  /* Longest Processing Time */
  for (i=0; i<N-1; i++)
    for (j=i+1; j<N; j++)
      if ( job[ sch[i] ].ProcT < job[ sch[j] ].ProcT )
         {
           temp = sch[i];
           sch[i] = sch[j];
           sch[j] = temp;
         }

}


void EDD_rule(T_JOB* job, int N, int* sch)
{
  int i, j;
  int temp;
  /* Earliaes Due Date */
  for (i=0; i<N-1; i++)
    for (j=i+1; j<N; j++)
      if ( job[ sch[i] ].d > job[ sch[j] ].d )
         {
           temp = sch[i];
           sch[i] = sch[j];
           sch[j] = temp;
         }

}

void Print_Gantt(T_JOB* job, int N, int* sch)
{
  int i;

  printf("\n sorsz \t job \t ST \t PT \t ET \t d \t T");
  for (i=0; i<N; i++)
  {
    printf("\n %d \t %d \t %ld \t %ld \t %ld \t %ld \t %ld",
    i,
    sch[i],
    job[ sch[i] ].StartT,
    job[ sch[i] ].ProcT,
    job[ sch[i] ].EndT,
    job[ sch[i] ].d,
    job[ sch[i] ].T );
  }
}

void Print_Mach_Gantt(T_JOB* job, int N, T_MACHINE * machine, int M, int** s)
{
  int m;

  for (m=0; m<M; m++)
  {
     printf("\n %d. gep [ %d ]",m, machine[m].l );
     Print_Gantt(job, machine[m].l, s[m]);

  }


}


void LPT_List_rule(T_JOB* job, int N, T_MACHINE * machine, int M, int** s)
{
 int* r;
 int i;  //job  index
 int sel_mach;  //kivalasztott gep indexe
 int m; //gepek futoindexe
 int pos; //kovetkezo szabad rekesz sorszama

 r = (int*) calloc(N, sizeof(int));
 /* rendezes elott inicializalas */
 for (i=0; i<N; i++)
      r[i] = i;

 LPT_rule(job, N, r);

 for (m=0; m<M; m++)
   {
    machine[m].l = 0;
    machine[m].C = 0;
    }

 for (i=0; i<N; i++)
  {
   //i a sorszam
   //r[i] a betemezendo munka azonositoja
   //a legkorabban felszabadulo gep kivalasztasa
   sel_mach = 0;
   for (m=1; m<M; m++)
     if ( machine[sel_mach].C > machine[m].C ) sel_mach = m;
   //az i.-edik munka beutemezese a kivalasztott gepre
   //a terhelesi lista vegere kerul
   pos = machine[sel_mach].l;
   s[ sel_mach ][ pos ] = r[i];
   machine[sel_mach].l++;
   machine[sel_mach].C += job[r[i]].ProcT;
  }

 free(r);
}


void MSPT_rule(T_JOB* job, int N, T_MACHINE * machine, int M, int** s)
{
 int* r;
 int i;  //job  index
 int m;  //gep index
 int pos; //kovetkezo szabad rekesz sorszama

 r = (int*) calloc(N, sizeof(int));
 /* rendezes elott inicializalas */
 for (i=0; i<N; i++)
      r[i] = i;

 SPT_rule(job, N, r);

 for (m=0; m<M; m++)
   machine[m].l = 0;

 for (i=0; i<N; i++)
  {
   m = i % M;
   pos = machine[m].l;
   //printf("\n m = %d \t pos = %d", m, pos);
   //getch();
   s[ m ][ pos ] = r[i];
   machine[m].l++;
  }

 free(r);
}