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

typedef struct{
        int id;
        long pt;
        long st;
        long et;
        }T_JOB;


int main(int argc, char* argv[])
{
  int M, N, i, j, m, temp;
  T_JOB* job;
  int* r;  //rendezett SPT
  int** l; //hozzarendeles es sorrend
  int * db; //gepek terhelese
  int x; //fiktiv munkak szama
  int k;
  long szumC;

  clrscr();
  printf("\n Egszeru pelda P utemezesi modellre Szum(Ci) celfuggveny eseten");
  printf("\n Kerem a munkak szamat:");
  scanf("%d", &N);
  printf("\n Kerem a gepek szamat:");
  scanf("%d", &M);

  job = (T_JOB*) calloc(N, sizeof(T_JOB));
  r = (int*) calloc(N, sizeof(int));
  x = M-N%M;
  k = (N+x)/M;

     //memter fogl. load-nak
   l = (int**) calloc(M, sizeof(int*));
   for (i=0; i<k; i++)
         l[i] = (int*) calloc(k, sizeof(int));

   //terheles
   db = (int*) calloc(M, sizeof(int));
   for ( m=0; m<M; m++)
     db[m] = 0;


  randomize();
  for (i=0; i<N; i++)
   {
      r[i]=job[i].id = i;
      job[i].pt = 1+random(30);
   }

  //1.lepes: rendezes SPT
  for (i=0; i<N-1; i++)
   for (j=i+1; j<N; j++)
     if (job[r[i]].pt > job[r[j]].pt )
      {
        temp=r[i];
        r[i]=r[j];
        r[j]=temp;
      }

    //2. lepes: szetosztas
    for (i=0; i<N; i++)
      {
         int act_m;
         act_m = (x+i)%M;
         l[ act_m ][ db[act_m] ] = r[i];
         db[act_m]++;
      }

    //szimulacio
    for (m=0; m<M; m++) //gepenken
     for (j=0; j<db[m]; j++)
       {
        if (j==0)
           job[ l[m][j] ].st = 0;
        else
           job[ l[m][j] ].st = job[ l[m][j-1] ].et;

        job[ l[m][j] ].et = job[ l[m][j] ].st + job[ l[m][j] ].pt;
       }

   //celfuggveny kiertekelese
      szumC = 0;

    for (i=0; i<N; i++)
      szumC += job[i].et;




   for (m=0; m<M; m++) //gepenken
   {
     printf("\n Gep: %d \n", m);
     for (j=0; j<db[m]; j++)
     {
      printf("\n %d. job: %d", j, l[m][j]);
      printf("\t st: %ld \t et: %ld", job[l[m][j]].st, job[l[m][j]].et );
     }
   }


   printf("\n szumC: %ld", szumC);

  //mem felszab
   for (i=0; i<k; i++)
         free (l[i]);
   free(l);

   free(r);
   free(db);
   free(job);

getch();
return 0;
}
//---------------------------------------------------------------------------