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

typedef struct{
                long id,
                     SetT,
                     ProcT,
                     OptT,
                     StartT,
                     EndT;
              }T_JOB;


int SPT(int* r, T_JOB* job, int n);
long simulation(int* Sch, T_JOB* job, int n, long ref_T);

int LPT(int* r, T_JOB* job, int n);

int main(int argc, char* argv[])
{
 T_JOB* job;
 int n; //jobok darabszama
 int m; //gepek szama
 int i; //job futoindex
 int j; //gepek futoindex
 int ** Sch; //utemterv
 int *r;  //rendezes SPT alapjan
 int *l; //jobok szama gepenkent (terheles load)
 int x; //fiktiv munkak szama
 int gep; //kivalasztott gep
 int munka; //kivalasztott munka
 long sum_EndT;
 //ket uj valt
 long max_EndT;
 long *C; //bef. ido

 //virtualis adatbazis lekerdeze
 randomize();
 printf("\n Kerem a jobok szamat:");
 scanf("%d", &n); //n erteket kap bill-rol
 job = (T_JOB*) calloc(n, sizeof(T_JOB) );
 for (i=0; i<n; i++)
 {
  job[i].id = i;
  job[i].SetT = random (10) + 10;
  job[i].ProcT = random (100) + 10;
  job[i].OptT = job[i].SetT + job[i].ProcT;

 }


 //1. pont
 r = (int*) calloc(n, sizeof(int));

 //1. pont
 LPT(r, job, n);

 //STP elv alkalmazasa
 //SPT(r, job, n);
 //ell
 printf("\n r: \n ");
 for (i=0; i<n; i++)
   printf("\n jobid = %d \t OptT: %ld", r[i], job[r[i]].OptT );

 printf("\n Kerem a gepek szamat:");
 scanf("%d", &m); //m erteket kap bill-rol
 if (n%m == 0) x = 0;
 else x = m - n%m;

 //utemterv mem. ter. lefoglal
  Sch = (int**) calloc(m, sizeof(int*));
  for (j=0; j<m; j++)
    Sch[j] =  (int*) calloc(n, sizeof(int));

  l = (int*) calloc(m, sizeof(int)); //load
  C = (long*) calloc(m, sizeof(long)); //bef idok

 //2. MSPT
  //kezdo allapot
  for (j=0; j<m; j++)
   { l[j]=0;
     C[j]=0;
   }
  //feladatok szetosztasa
  for (i=0; i<n; i++)
  {
   //az r vektor i. munkaja a gep gepre kerul
   gep = 0;
   for (j=1; j<m; j++)
     if ( C[gep] > C[j] ) gep = j;

   //terheles az r[i] munkat a gep azon. gep l[gep] poziciojaba
   Sch[gep][ l[gep] ]=r[i];
   l[gep]++;  //terhelesek szama
   //fontos
   C[gep]+=job[r[i]].OptT;
  }
  //utemterv kesz!!!
 //finomprogram generalas szimulacioval
 //szimulacio gepenkent egymastol fuggetlenul
 sum_EndT = 0;

 for (j=0; j<m; j++)
  {
  sum_EndT += simulation(Sch[j], job, l[j], 0);
  if (j == 0) max_EndT = C[j];
  else if ( C[j] > max_EndT )
       max_EndT = C[j];
  }

 //munkak Gantt diagramja
 printf("\n Fine Sch: \n ");
 for (i=0; i<n; i++)
   printf("\n jobid = %d \t StartT: %ld \t EndT: %ld", i, job[i].StartT, job[i].EndT );

 //printf("\n Bef. idop. osszege: %ld", sum_EndT);
 printf("\n Bef. idop. maximuma: %ld", max_EndT);

  //gepek Gantt diagramja
  for (j=0; j<m; j++)
  {
   printf("\n %d. gep: [%d]", j, l[j]);
   for (i=0; i<l[j]; i++)
    {
     munka = Sch[j][i];
     printf("\n \t %d. munka_%d \t %ld \t %ld ",i, munka , job[munka].StartT, job[ munka ].EndT);
    }
  }

 getch();
 free(r);
 free(job);
 //utemterv mem. ter. felszab
  for (j=0; j<m; j++)
    free ( Sch[j] );
  free( Sch );
  free( l );
  free( C );
  return 0;
}
//---------------------------------------------------------------------------

int SPT(int* r, T_JOB* job, int n)
{
 int i, j, temp;
 for (i=0; i<n; i++)
  r[i]=job[i].id;

 for (i=0; i<n-1; i++)
  for (j=i+1; j<n; j++)
   if (job[ r[i] ].OptT > job[ r[j] ].OptT)
   { //nem csokkeno OptT ertek szerint
     temp = r[i];
     r[i] = r[j];
     r[j] = temp;
   }
 return 1;
}

int LPT(int* r, T_JOB* job, int n)
{
 int i, j, temp;
 for (i=0; i<n; i++)
  r[i]=job[i].id;

 for (i=0; i<n-1; i++)
  for (j=i+1; j<n; j++)
   if (job[ r[i] ].OptT < job[ r[j] ].OptT)
   { //nem csokkeno OptT ertek szerint
     temp = r[i];
     r[i] = r[j];
     r[j] = temp;
   }
 return 1;
}


long simulation(int* Sch, T_JOB* job, int z, long ref_T)
{
 long sum_EndT = 0;
 int i;
 job[Sch[0]].StartT = ref_T; //kezdet
 job[Sch[0]].EndT = job[Sch[0]].StartT + job[Sch[0]].OptT;
 sum_EndT = job[Sch[0]].EndT;

 for (i=1; i<z; i++)
 {
  job[Sch[i]].StartT = job[Sch[i-1]].EndT;
  job[Sch[i]].EndT = job[Sch[i]].StartT + job[Sch[i]].OptT;
  sum_EndT += job[Sch[i]].EndT;
 }
 return sum_EndT;
}