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

#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 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;
 //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
 //STP elv alkalmazasa
 r = (int*) calloc(n, sizeof(int));
 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+x)/m, sizeof(int));

  l = (int*) calloc(m, sizeof(int)); //load

 //2. MSPT
  //kezdo allapot
  for (j=0; j<m; j++)
   l[j]=0;
  //feladatok szetosztasa
  for (i=0; i<n; i++)
  {
   //az r vektor i. munkaja a gep gepre kerul
   gep = (x+i)%m;
   //terheles az r[i] munkat a gep azon. gep l[gep] poziciojaba
   Sch[gep][ l[gep] ]=r[i];
   l[gep]++;  //terhelesek szama
  }
  //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);
  }

 //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);

  //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 );

        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;
}

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;
}