/*--------------------------------------------------------------------------------
F|prmut|Cmax  Utemezesi fedadat megoldasa CDS-algoritmus alkalmazásával.
Többgépes egyutas előzés nélküli 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.
CDS-algoritmus:
A Campbell-Dudek-Smith algoritmus a többgépes feladatot kétgépes problémákra
vezeti vissza. 
Az algoritmus az eredeti m gépes feladatból m-1 darab mesterséges kétgépes problémát generál
úgy, hogy az egymást követő gépek lesznek a kétgépes feladat gépei.
A kétgépes feladatok egyenként megoldhatók a Johnson-algoritmussal.
Kiválasztva közülük a teljes feladatra vonatkozó átfutási idő szempontjából 
a legjobbat, az lesz az m-gépes probléma megoldása.
A megoldás nem optimális mert a feladat NP-hard, de jó közelítő ütemtervet eredményez.
--------------------------------------------------------------------------------*/


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

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

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


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;

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

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

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


   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
  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)
{
  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];
      }
     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];
      }
   }

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

}