/*------------------------------------------------------------------------------
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<alloc.h>
#include<stdlib.h>
#include<conio.h>

typedef struct{
                int id;
                long ProcT,
                     StartT,
                     EndT,
                     T,  /* tardiness, csuszas */
                     d;  /* due date, hatariido */
              }T_JOB;

typedef struct{
               long Csum,
                    Tmax;  /* Max Tardiness */
               long Cmax;  /*Cmax Completion Time*/
              }T_OBJF;

typedef struct{
                int id,
                    l;  /*load, teheles, hozzarendelt munkak szama*/
                long C; /*Completion, felszadulasi ido */
               }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_OBJF* obj);
void print_job(T_JOB* job, int N);
void print_Gantt(T_JOB* job, int N, int* sch);
void print_Gantt_P(T_JOB* job, int N, T_MACHINE* machine, int M, int** s);
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 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_MACHINE* machine;
 int M; //gepek szama
 int m; //gepek indexe
 int** s; //utemterv
 int* sch;
 T_OBJF obj;
 int N; //munkak szama
 int i; //munkak indexe

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

 machine = (T_MACHINE*) calloc(M, sizeof(T_MACHINE));

 randomize();
 job = (T_JOB*) calloc( N, sizeof(T_JOB));
 for (i=0; i<N; i++)
 {
    job[i].id = i;
    job[i].ProcT = 1 + random(20);
    job[i].d = 1 + random(10) * random(5) * N;
 }


 s = (int**) calloc(M, sizeof(int*));
 for (m=0; m<M; m++)
    s[m] = (int*) calloc(N, sizeof(int));

 sch = (int*) calloc(N, sizeof(int));

 /*MSPT a P modellre*/
 MSPT_rule(job, N, machine, M, s);
 Simulation_P(job, N, machine, M, s, 0);
 Evaluation(job, N, &obj);
 print_Gantt_P(job, N, machine, M, s);
 printf("\n MSPT utemterv eseten Csum=%ld", obj.Csum);
 printf("\n MSPT utemterv eseten Cmax=%ld", obj.Cmax);
 getch();

 /*LPT+List a P modellre*/
 LPT_List_rule(job, N, machine, M, s);
 Simulation_P(job, N, machine, M, s, 0);
 Evaluation(job, N, &obj);
 print_Gantt_P(job, N, machine, M, s);
 printf("\n LPT+List utemterv eseten Csum=%ld", obj.Csum);
 printf("\n LPT+List utemterv eseten Cmax=%ld", obj.Cmax);
 getch();

 /*
 //Ad-hoc
 for (i=0; i<N; i++)
 {
  sch[i]=i;
 }

 Simulation(job, N, sch, 0);
 Evaluation(job, N, &obj);
 //print_job(job, N);
 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();

 //SPT
 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
 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);
 getch();
 */
 getch();



 free (sch);
 free (job);
 free (machine);

 for (m=0; m<M; m++)
    free( s[m] );
 free (s);


 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++)
    Simulation(job, machine[m].l, s[m], t);

}


void Evaluation(T_JOB* job, int N, T_OBJF* 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); /*Tardiness*/
    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 print_job(T_JOB* job, int N)
{
 int i;
 printf("\n id \t StartT \t ProcT \t EndT");

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

void print_Gantt(T_JOB* job, int N, int* sch)
{
 int i;
 printf("\n sorsz \t id \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_Gantt_P(T_JOB* job, int N, T_MACHINE* machine, int M, int** s)
{
  int m;
  for (m=0; m<M; m++)
  {  printf("\n %d. gep terhelese %d munka", m, machine[m].l);
     print_Gantt(job, machine[m].l, s[m]);
   }
}



void SPT_rule(T_JOB* job, int N, int* sch)
{
  /* Shortest Processing Time*/
  int temp;
  int i, j;

  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)
{
  /* Longest Processing Time*/
  int temp;
  int i, j;

  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)
{
  /* Earliest Due Date */
  int temp;
  int i, j;

  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 MSPT_rule(T_JOB* job, int N, T_MACHINE* machine, int M, int** s)
{
 int i, m;
 int* r;

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

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

 SPT_rule(job, N, r);  //rendezes

 for (i=0; i<N; i++)
  {
    m = i % M;
    s[ m ][ machine[m].l ] = r[i];
    machine[m].l++;
  }


 free(r);
}

void LPT_List_rule(T_JOB* job, int N, T_MACHINE* machine, int M, int** s)
{
 int i; /* munkak futoindexe*/
 int m; /* gepek futoindexe*/
 int sel_mach; /* kivalasztott gep*/
 int* r; /* seged vektor rendezeshez*/

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

 for(m=0; m<M; m++)   /* uresek a gepek*/
    {
    machine[m].l = 0;
    machine[m].C = 0;
    }

 LPT_rule(job, N, r);  //rendezes muveleti ido szerint csokkeno sorrendbe

 for (i=0; i<N; i++)  /* List algoritmus*/
  {
    //ki kell valasztani a legkorabban felszabadulo gepet
    sel_mach = 0;
    for (m=1; m<M; m++)
       if ( machine[ sel_mach ].C > machine[ m ].C )
            sel_mach = m;

    /* a gep terhelesi soranak vegehez hozzaadjuk a munkat*/
    /* a beutemezendo munka sorszama i
                            azonositoja r[i] */
    s[ sel_mach ][ machine[sel_mach].l ] = r[i];
    machine[sel_mach].l++; /* noveljuk a terhelesek szamat*/
    machine[sel_mach].C += job[ r[i] ].ProcT; /*muveleti idovel noveljuk*/
  }

  /* az utemterv az s matrixban eloallt*/
 free(r);
}