/*--------------------------------------------------------------------------------
F|prmut|Cmax  Utemezesi fedadat megoldasa CDS-algoritmus alkalmazásával.
Az előző gyakorlaton megírt program bővítése 
szakaszosan rendelkezésre álló gépek terhelésére szolgáló algortimussal.

A load_stet_to_cal függvény a megadott terhelést [st, et] 
az adott gép azon rendelkezésre állási intervallumára
helyezi, amelyiken megszakitás nelkul elfér.
Ha egyik intervallumra sem fér rá, akkor az utolsó intervallum befejezési időpontjához
igazítottan helyezi el. 
--------------------------------------------------------------------------------*/






#include<stdlib.h>
#include<stdio.h>
#include<conio.h>

typedef struct{
                int jobid; //azonosito
                long * pt;  //muveleti ido, processing time
                long * st;  //kezdesi idopont, start time
                long * et;  //befejezesi idopont, end time
                } T_JOB;

typedef struct{
                long ST;
                long ET;
               } T_CAL;

typedef struct{
                int id;
                int nc; //intervallumok szamat
                T_CAL* cal;
               }T_MACH;

//elozes nelkuli egyutas modell (permutacios flow shop)
//NJ jobok szama, NM gepek szama, s utemterv=jobok sorrendje, job idoadatok
int FS_simulation(int NJ, int NM, int* s, T_JOB* job, T_MACH* mach);

//Johnson algoritmus 2 gepre A-->B sorrendben
//x az "A" gep, y a "B" gep sorszama, NJ jobok szama, NM gepek szama, s utemterv=jobok sorrendje, job idoadatok
void Johnson_algorithm( int x, int y, int NJ, int NM, int *s, T_JOB* job );


//szakaszosan rendelkezesre allo gepek terhelesere szolgalo algortimus
int load_stet_to_cal(T_MACH* mach, int m, long *st, long *et, long last);


int main(int argc, char* argv[])
{

  T_JOB * job;
  int NJ = 4;
  int NM = 5;
  int* s;       //utemterv
  int* s_best;  //lejobb utemterv
  int i,m,k;
  long Cmax, Cbest;
  //-----
  T_MACH* mach;
   long st;
   long et;
   long last;
   int found;
  //-----

  clrscr();
  printf("\n Demo program a CDS Campbell-Dudek-Scmith algoritmus bemutattasara");
  printf("\n amely jo kozelito megoldas ad az egyutas elozes nelkuli utemezesi feladatra");
  randomize();


  //intervallumok generalasa
  mach = (T_MACH*) calloc(NM, sizeof(T_MACH));
  for (m=0; m<NM; m++)
  {
   printf("\n %d. gep:", m);
   mach[m].id = m;
   mach[m].nc = 3+random(10);
   printf("\t nc=%d", mach[m].nc);

   mach[m].cal = (T_CAL*) calloc(mach[m].nc, sizeof(T_CAL));
   for (k=0; k<mach[m].nc; k++)
    {
      if (k==0)
        mach[m].cal[k].ST = random(10);
      else
        mach[m].cal[k].ST = mach[m].cal[k-1].ET + random(10);

        mach[m].cal[k].ET = mach[m].cal[k].ST + 10 + random(40);
        printf("\n \t\t %ld - %ld ", mach[m].cal[k].ST, mach[m].cal[k].ET);
    }
  }

  //test
  /*
   printf("\n st= ");
   scanf("%ld", &st);
   printf("\n et= ");
   scanf("%ld", &et);
   printf("\n last= ");
   scanf("%ld", &last);
   found = load_stet_to_cal(mach, NM-1, &st, &et, last);
   printf("\n st= %ld, et = %ld, found= %d", st, et, found);

   getch();
   */


  s = (int*) calloc(NJ, sizeof(int));
  s_best = (int*) calloc(NJ, sizeof(int));


  //strukturavektor az idoatatok tarolasara
  job = (T_JOB*) calloc(NJ, sizeof(T_JOB));
  for (i=0; i<NJ; i++)
    {
     job[i].pt = (long*) calloc(NM, sizeof(long));
     job[i].st = (long*) calloc(NM, sizeof(long));
     job[i].et = (long*) calloc(NM, sizeof(long));
    }

    //muveleti idok tablazatanak fejlece
    printf("\n\n Muveleti idok");
    printf("\n job");
     for(m=0; m<NM; m++)
       printf("\t %d.gep ", m);

  /*CAPP*/
  //muveleti idok generalasa
  for(i=0; i<NJ; i++)
   {
   job[i].jobid = i;
   s[i]=i;
   printf("\n %d", job[i].jobid);
     for(m=0; m<NM; m++)
       {
        job[i].pt[m] = 1+random(20);
        printf("\t %ld ", job[i].pt[m]);
       }
   }


   //NM-1 darab ketgepes feladatra bontjuk az eredeti NM gepes feladatot
   //egymast koveto ket gepre alkalmazzuk a Johnson algoritmust
   //a kapott utemtervet kiertekeljuk az NM gepes teljes feladatra
   //kivalasztjuk a legjobb megoldast
   printf("\n\n Dekomponalas %d darab ketgepes feladatra", NM-1);
   for (k=0; k<NM-1; k++)
   {
    Johnson_algorithm( k, k+1, NJ, NM, s, job);   //meghatarozzuk s-t ketgepre A=k, B=k+1
    Cmax = FS_simulation(NJ, NM, s, job, mach);         //kiertekeljuk s-t a teljes feladatra
    printf("\n %d iteracio (A=%d B=%d): Cmax=%ld", k, k, k+1, Cmax);  //kiirjuk a celfuggveny erteket

    if ( k==0)                                   //megorizzuk a legjobb megoldast es annak celfuggvenyerteket
     {
      Cbest = Cmax;
      for (i=0; i<NJ; i++)
        s_best[i]=s[i];
     }
     else
     {
       if ( Cbest > Cmax )
        {
          Cbest = Cmax;
          for (i=0; i<NJ; i++)
             s_best[i]=s[i];

        }
     }
   }


     //visszatoltjuk a megjegyyett legjobb megoldast
    for (i=0; i<NJ; i++)
     s[i]=s_best[i];

     //ujraszamitjuk a legjobb megoldashoz tartozo idoadatokat
     Cmax = FS_simulation(NJ, NM, s, job, mach);


   printf("\n CDS sorrend");
  for(i=0; i<NJ; i++)
   printf("\n %d ", job[s[i]].jobid);


    printf("\n\n CDS sorrendnek megfelelo idoadatok");
  //szimulacio eredmenye
   printf("\n\t\t st \t et");
   for (m=0; m<NM; m++)
   { printf("\n %d_gep:", m);
     for (i=0; i<NJ; i++)
        printf("\n\t %d_job: %ld \t %ld", s[i], job[s[i]].st[m], job[s[i]].et[m]);
   }
   printf("\n A sorozat bef. idopontja: %ld", job[s[NJ-1]].et[NM-1]);



  //memoriateruletek felszabaditasa
  for (m=0; m<NM; m++)
   free(mach[m].cal);
  free (mach);



  free(s);
  free(s_best);


    for (i=0; i<NJ; i++)
    {
     free(job[i].pt);
     free(job[i].st);
     free(job[i].et);
     }

  free(job);
  getch();

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

int FS_simulation(int NJ, int NM, int* s, T_JOB* job, T_MACH* mach)
{
  int t = 0;
  int i,m;

  for (m=0; m<NM; m++)      //gepek
   {
    for (i=0; i<NJ; i++)    //jobok (munkak)
     if (m==0)
      { //kezdo gep
         if (i == 0)     //kezdo job
           job[s[i]].st[m] = 0;
         else            //nem kezdo, kozbenso job
           job[s[i]].st[m] = job[s[i-1]].et[m];

         job[s[i]].et[m] = job[s[i]].st[m] + job[s[i]].pt[m];
         load_stet_to_cal(mach, m, &job[s[i]].st[m], &job[s[i]].et[m], 0);

      }
     else
      { //nem kezdo, kozbenso gep
         if (i == 0)     //kezdo job
           job[s[i]].st[m] = job[s[i]].et[m-1];
         else            //nem kezdo, kozbenso job
           job[s[i]].st[m] = max( job[s[i]].et[m-1], job[s[i-1]].et[m]);

         job[s[i]].et[m] = job[s[i]].st[m] + job[s[i]].pt[m];
         load_stet_to_cal(mach, m, &job[s[i]].st[m], &job[s[i]].et[m], 0);

      }
   }

   return job[s[NJ-1]].et[NM-1];
}

void Johnson_algorithm( int x, int y, int NJ, int NM, int *s, T_JOB* job )
{
int i,j, temp, e, v;
  int* r;
  r = (int*) calloc(NJ, sizeof(int));

 for(i=0; i<NJ; i++)
    r[i] = s[i];

for(i=0; i<NJ-1; i++)
   for(j=i+1; j<NJ; j++)
    {
      if ( min( job[r[i]].pt[x], job[r[i]].pt[y]) >
           min( job[r[j]].pt[x], job[r[j]].pt[y]) )
         {
          temp = r[i];
          r[i] = r[j];
          r[j] = temp;
         }
    }

  e = 0;
  v = NJ-1;
  for(i=0; i<NJ; i++)
   {
    if (job[r[i]].pt[x] < job[r[i]].pt[y] )
     {
       s[e] = r[i];
       e++;
     }
     else
     {
       s[v] = r[i];
       v--;
     }
   }
  free(r);

}

//a megadott terhelest [st, et] arra a rendelkezesre allasi intervallumra
//helyezi amelyiken megszakitas nelkul elfer
//ha egyikre sem fer ra, akkor az utolso intervallum befejezesi idopontjahoz igazitottan
//helyezi el 
int load_stet_to_cal(T_MACH* mach, int m, long *st, long *et, long last)
{
 int found = -1;
 int c;
 long size;
 long act_st;
 long act_et;

 act_st = *st;
 act_et = *et;

 size = act_et - act_st;
 act_st = max( act_st, last);
 act_et = act_st + size;

 c=0;
 while ( c < mach[m].nc )
  {
    //if ( mach[m].cal[c].ST <= act_st)
    if ( mach[m].cal[c].ET > act_st) //mod
    {
     act_st = max(act_st, mach[m].cal[c].ST); //mod
     act_et = act_st + size;                  //mod

     if ( mach[m].cal[c].ET >= act_et )
       {
        found = c;
        break;
       }
      else
       {
         c++;
         if (c>=mach[m].nc)
         {
          act_st = mach[m].cal[c-1].ET;
          act_et = act_st + size;
          found = c;
          break;
         }
         else
         {
          act_st = mach[m].cal[c].ST;
          act_et = act_st + size;
         }
         continue;
       }
    }
    else
     c++;
  }

 *st = act_st;
 *et = act_et;

 return found;
 }