/*--------------------------------------------------------------------------------
P||Cmax  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<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 LPT
  int** l; //hozzarendeles es sorrend
  int * db; //gepek terhelese
  long * C; //a gepek felszabadulasanak idopontja
  int Mmax = 0;

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



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

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

   //befejezesi idopontok
   C = (int*) calloc(M, sizeof(int));
   for ( m=0; m<M; m++)
     C[m] = 0;

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

  //1.lepes: rendezes LPT longest processing time
  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++)
      {
        //gepkivalasztas
        int Mmin = 0;
        for (m=1; m<M; m++)
              if ( C[Mmin] > C[m] )
                Mmin = m;
       //terheles
       db[Mmin]++;
       l[Mmin][db[Mmin]] = r[i];
       C[Mmin]+= job[ r[i] ].pt;
      }




   //
   //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;
       }
   //gep-orientealt Gantt diagram
   for (m=0; m<M; m++) //gepenken
   {
     printf("\n Gep: %d, munkak szama: %d \n", m, db[m]);
     for (j=0; j<db[m]; j++)
     {
      printf("\n\t %d. munka: %d", j, l[m][j]);
      printf("\t st: %ld \t et: %ld", job[l[m][j]].st, job[l[m][j]].et );
     }
   }

   //celfuggveny kiertekelese
        for (m=1; m<M; m++)
              if ( C[Mmax] < C[m] )
                Mmax = m;


       printf("\n Cmax = %ld", C[Mmax]);


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

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

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