/*--------------------------------------------------------------------------------
F2|prmut|Cmax  Utemezesi fedadat megoldasa Johnson-algoritmus alkalmazásával.
Kétgé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.
A megoldás optimális ütemtervet eredményez.
--------------------------------------------------------------------------------*/




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


typedef struct {
                long st[2], //start time
                     et[2], //end time
                     pt[2]; //proc. time
                }T_JOB;

long kisebb(long a, long b)
{
 return a>b?b:a;
}

int main(int argc, char* argv[])
{
  T_JOB* job;
  int N;
  int M;
  int* s;
  int e, v;
  int i, j;
  int m;
  int* r;
  int temp;
  long x, y;

  clrscr();
  printf("\n Egszeru pelda Johnson-alg.-ra.");

  //ERP
  printf("\n Munkak szama: ");
  scanf("%d", &N);
  //CAPC
  M = 2;


  //CAPP
  randomize();
  job = (T_JOB*) calloc(N, sizeof(T_JOB));
  for (i=0; i<N; i++)
  { printf("\n %d_job:", i);
    for (m=0; m<M; m++)
     {
      job[i].pt[m] = 1+random(20);
      printf("\t %ld", job[i].pt[m]);
     }
    }


  //Johnson-alg.

  s = (int*) calloc(N, sizeof(int));
  r = (int*) calloc(N, sizeof(int));

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

  //rendezes nem csokkeno
  for( i=0; i<N-1; i++)
   for ( j=i+1; j<N; j++)
    { x = kisebb(job[r[i]].pt[0], job[r[i]].pt[1]);
      y = kisebb(job[r[j]].pt[0], job[r[j]].pt[1] );
     if (  x > y )
         {
          temp=r[i];
          r[i] = r[j];
          r[j] = temp;
         }
     }
  //rendezett
  printf("\n Rendezes utan: \n");
  for( i=0; i<N; i++)
    printf("\t %d", r[i]);

   //utemezes
     for( i=0, e = 0, v = N-1; i<N; i++)
      if ( job[r[i]].pt[0] > job[r[i]].pt[1] )
          {
          s[v] = r[i];
          v--;
          }
      else
          {
          s[e] = r[i];
          e++;
          }
  printf("\n J-alg utan: \n");
  for( i=0; i<N; i++)
    printf("\t %d", s[i]);


   //szimulacio

   for (m=0; m<M; m++)
   {
    for (i=0; i<N; i++)
     if (m==0)
      { //kezdo gep
         if (i == 0)
           job[s[i]].st[m] = 0;
         else
           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
         if (i == 0)
           job[s[i]].st[m] = job[s[i]].et[m-1];
         else
           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];
      }
   }

   //szimulacio eredmenye
   for (m=0; m<M; m++)
   { printf("\n %d_gep:", m);
     for (i=0; i<N; i++)
        printf("\n %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[N-1]].et[M-1]);

   free(job);
   free(s);
   free(r);
   getch();
   return 0;
}
//---------------------------------------------------------------------------