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

typedef struct {
                int id;
                long int SetT,
                         ProcT,
                         OpT,
                         StartT,
                         EndT,
                         D,
                         L;
                }T_JOB;

typedef struct {
                int id;
                int l; /*load*/
                long int C; /*completion time*/
               }T_MACHINE;

typedef struct {
               long Cmax,  /*utolso job bef. idopontja*/
                    Csum; /* bef. idok osszege*/
               }T_OBJF;    /*celfuggvenyek*/

void MSPT_rule(T_JOB* job, int** sch, int NJ, T_MACHINE* machine, int NM);
void LPT_LIST_rule(T_JOB* job, int** sch, int NJ, T_MACHINE* machine, int NM);
void simulation(T_JOB* job, int** sch, int NJ, T_MACHINE* machine, int NM, long t);
void evaluation(T_JOB* job, int NJ, T_OBJF* objf);
void print_objf(T_OBJF* objf);
void print_Gantt(T_JOB* job, int** sch, int NJ, T_MACHINE* machine, int NM);
void SPT_rule(T_JOB* job, int* r, int NJ);
void EDD_rule(T_JOB* job, int* r, int NJ);
void LPT_rule(T_JOB* job, int* r, int NJ);


int main(int argc, char* argv[])
{
  int NJ; /* munkak szama*/
  int NM; /* gepek szama*/
  T_MACHINE * mach;
  int i, j;
  T_JOB* job; /* munkak strvektre mutato*/
  int** sch; /* utemterv */
  T_OBJF objf;
  /* modellepites, utemezes, szimulacio, ertekeles*/

  /*modellepites*/
  printf("\n Kerem a munkak aktualis szamat:");
  scanf("%d", &NJ);

  printf("\n Kerem a gepek aktualis szamat:");
  scanf("%d", &NM);

  job = calloc(sizeof(T_JOB), NJ);
  randomize();
  for (i=0; i<NJ; i++)
   {
    job[i].id = i;
    job[i].SetT = 1 + random(10);
    job[i].ProcT = 1 + random(100);
    job[i].OpT = job[i].SetT + job[i].ProcT;
    job[i].D = 1 + random(50) + job[i].OpT*random(5);
   }

  /*utemezes*/
  sch = calloc(sizeof(int*), NM);
  for (i=0; i<NM; i++)
     sch[i] = calloc(sizeof(int), NJ);

  /* gepek */
  mach = (T_MACHINE*) calloc(NM, sizeof(T_MACHINE));

  /*Ad-hoc*/
  //printf("\n AD-HOC sorrend: \n");
  /*utemezes MSPT-vel*/
  printf("\n MSPT \n");
  MSPT_rule(job, sch, NJ, mach, NM);
  /*szimulacio*/
  simulation(job, sch, NJ, mach, NM, 0);
  /*ertekeles*/
  evaluation(job, NJ, &objf);
  //print_Gantt(job, sch, NJ);
  print_objf(&objf);

  printf("\n LPT+LIST \n");
  LPT_LIST_rule(job, sch, NJ, mach, NM);
  /*szimulacio*/
  simulation(job, sch, NJ, mach, NM, 0);
  /*ertekeles*/
  evaluation(job, NJ, &objf);
  //print_Gantt(job, sch, NJ);
  print_objf(&objf);

  getch();

  for(i=0; i<NM; i++)
     free(sch[i]);
  free(sch);
  free(job);
  free(mach);

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

void simulation(T_JOB* job, int** sch, int NJ, T_MACHINE* machine, int NM, long t)
{
  int i;
  int m;
  for (m=0; m<NM; m++)
  {
  i=0;
  job[ sch[m][i] ].StartT = t;
  job[ sch[m][i] ].EndT = job[ sch[m][i] ].StartT + job[ sch[m][i] ].OpT;

  for (i=1; i<machine[m].l; i++)
  {
    job[ sch[m][i] ].StartT = job[ sch[m][i-1] ].EndT;
    job[ sch[m][i] ].EndT = job[ sch[m][i] ].StartT + job[ sch[m][i] ].OpT;
  }

  }
}

void evaluation(T_JOB* job, int NJ, T_OBJF* objf)
{
 int i;
 objf->Csum = 0;
 objf->Cmax = 0;

 for (i=0; i<NJ; i++ )
 {
  objf->Csum += job[i].EndT;

  job[i].L = job[i].EndT - job[i].D; /*keses*/

  if (i==0) objf->Cmax = job[i].EndT;
  else if ( objf->Cmax < job[i].EndT ) objf->Cmax = job[i].EndT;

 }
}

void print_objf(T_OBJF* objf)
{
 printf("\n Csum= %ld", objf->Csum);
 printf("\n Cmax= %ld", objf->Cmax);
}

void print_Gantt(T_JOB* job, int** sch, int NJ, T_MACHINE* machine, int NM)
{
 int i;
 int m;
 for (m=0; m<NM; m++)
 {

 printf("\n machine_%d \n", m);
 printf("\n n: job_id \t StarT \t OpT \t EndT \t D \t L");

 for ( i=0; i<machine[m].l; i++)
 {
  printf("\n %d: job_%d \t %ld \t %ld \t %ld \t %ld \t %ld",
  i,
  sch[m][i],
  job[ sch[m][i]].StartT,
  job[ sch[m][i]].OpT,
  job[ sch[m][i]].EndT,
  job[ sch[m][i]].D,
  job[ sch[m][i]].L);

 }

 }//m
}

void LPT_rule(T_JOB* job, int* r, int NJ)
{
 int i, j, temp;
 for (i=0; i<NJ-1; i++)
  for (j=i+1; j<NJ; j++)
   {
     if ( job[ r[i] ].OpT < job[ r[j] ].OpT )
       {
        temp = r[j];
        r[j] = r[i];
        r[i] = temp;
       }
   }

}


void SPT_rule(T_JOB* job, int* r, int NJ)
{
 int i, j, temp;
 for (i=0; i<NJ-1; i++)
  for (j=i+1; j<NJ; j++)
   {
     if ( job[ r[i] ].OpT > job[ r[j] ].OpT )
       {
        temp = r[j];
        r[j] = r[i];
        r[i] = temp;
       }
   }

}


void EDD_rule(T_JOB* job, int* r, int NJ)
{
 int i, j, temp;
 for (i=0; i<NJ-1; i++)
  for (j=i+1; j<NJ; j++)
   {
     if ( job[ r[i] ].D > job[ r[j] ].D )
       {
        temp = r[j];
        r[j] = r[i];
        r[i] = temp;
       }
   }

}


void LPT_LIST_rule(T_JOB* job, int** sch, int NJ, T_MACHINE* machine, int NM)
{
 int* r;
 int i; /*job index*/
 int m; /*machine index*/
 int am; /*gepek futoindexe*/
 r = (int *) calloc(NJ, sizeof(int));
 for (i=0; i<NJ; i++) r[i]=i;

 /* elokeszites LPT rendezes*/
   LPT_rule(job, r, NJ);

  /*jobok szetosztasa a gepek kozott LIST-algoritmussal*/

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

  for (i=0; i<NJ; i++)
  {
   m = 0; /* melyik gep kapja meg */
   for (am = 1; am<NM; am++)
     if ( machine[am].C < machine[m].C )
         m = am;

   //printf("\n i=%d m=%d, l=%d ", i, m, machine[m].l );
   sch[m][ machine[m].l ] = r[i];
   machine[m].l++;
   machine[m].C += job[ r[i] ].OpT;
  }

 free(r);
}


void MSPT_rule(T_JOB* job, int** sch, int NJ, T_MACHINE* machine, int NM)
{
 int* r;
 int i; /*job index*/
 int x; /* fiktiv munkak szama*/
 int m; /*machine index*/

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

 /* elokeszites SPT rendezes*/
   SPT_rule(job, r, NJ);

  /*jobok szetosztasa a gepek kozott MSPT-vel*/
  if ( NJ%NM == 0 ) x = 0;
  else x = NM - NJ%NM;

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



  for (i=0; i<NJ; i++)
  {
   m = (x + i) % NM; /* gep azonositoja*/
   //printf("\n i=%d m=%d, l=%d ", i, m, machine[m].l );
   sch[m][ machine[m].l ] = r[i];
   machine[m].l++;
  }

 free(r);
}