/*------------------------------------------------------------------------------
1||Szum(Ci)  Utemezesi fedadat megoldasa SPT ütemezési szabály alkalmazásával.
Egygépes termelésiütemezési feladat.
Az ütemezés célja a befejezési idők összegének minimalizálása, 
ezáltal az átlagos készletszint minimalizálása.
SPT Shortest Processing Time (műveleti idő szerint nemcsökkenő munkasorrend)
A megoldás optimális ütemtervet eredményez.

Bővítés:
1|di|Lmax
Egygépes termelésiütemezési feladat.
Az ütemezés célja a legnagyobb késés minimalizálása.
EDD Earliest Due Date (határidő szerint nemcsökkenő munkasorrend)
A megoldás optimális ütemtervet eredményez.
-------------------------------------------------------------------------------*/


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

typedef struct{
               int id;      //azonsito
               long ProcT;  //muveleti ido
               long StartT; //kezdesi ido
               long EndT;   //befejezesi ido
               long d;      //hatarido
               long L;      //keses
               }T_JOB;      //Munka (Job)

typedef struct{
               long Csum;  //befejezesi idopontok osszege
               double ASL; //atlagos keszletszint
               long Lmax;  //legnagyobb keses
               }T_OBJF;    //celfuggveny, objective function

void Simulation(T_JOB* job, int* sch, int NJ, int t_ref);
void Evaluate(T_JOB* job, int* sch, int NJ, T_OBJF* obj);
void Print_Job_Gantt(T_JOB* job, int* sch, int NJ); //idotabla megjelenitese
void SPT_rule(T_JOB* job, int* sch, int NJ);
void EDD_rule(T_JOB* job, int* sch, int NJ);




int main(int argc, char* argv[])
{
  int i;  //futoindex a munkakhoz
  int NJ; //munkak szama
  T_JOB* job; //strukturavektorra mutato pointer
  int* sch; //utemterv vektorara mutato pointer
  long t_ref = 0; //referencia idopont
  T_OBJF obj;

  printf("\n Egygepes gyartorendszer utemezese.");
  printf("\n Munkak szama:");
  scanf("%d", &NJ);   //betoltes bill.-rol

  //memoriafoglalas
  job = (T_JOB*) calloc( NJ, sizeof(T_JOB) );
  sch = (int*) calloc( NJ, sizeof(int) );

  //input adatok generalasa
  for (i=0; i<NJ; i++)
    {
      job[i].id = i;
      job[i].ProcT = 1 + rand()%20;
      job[i].d = 1 + (1 + rand()%8) * (1+rand()%5) * NJ;
      sch[i] = i;  //azonosito szerinti sorrend
    }

  //muveletek
  //Ad-hoc
  Simulation(job, sch, NJ, t_ref);
  Evaluate(job, sch, NJ, &obj);
  printf("\n Ad-hoc sorrend");
  Print_Job_Gantt(job, sch, NJ);
  printf("\n Csum = %ld \n ASL = %lf \n Lmax = %ld",
       obj.Csum,
       obj.ASL,
       obj.Lmax );

  //SPT
  SPT_rule(job, sch, NJ); //rendezes nemcsokkeno sorrendbe
  Simulation(job, sch, NJ, t_ref);
  Evaluate(job, sch, NJ, &obj);
  printf("\n SPT sorrend");
  Print_Job_Gantt(job, sch, NJ);
  printf("\n Csum = %ld \n ASL = %lf \n Lmax = %ld",
       obj.Csum,
       obj.ASL,
       obj.Lmax );

  //EDD
  EDD_rule(job, sch, NJ); //rendezes nemcsokkeno sorrendbe
  Simulation(job, sch, NJ, t_ref);
  Evaluate(job, sch, NJ, &obj);
  printf("\n EDD sorrend");
  Print_Job_Gantt(job, sch, NJ);
  printf("\n Csum = %ld \n ASL = %lf \n Lmax = %ld",
       obj.Csum,
       obj.ASL,
       obj.Lmax );


  //momoriafelszabaditas
  free( job );
  free( sch );

  getch(); //bill. lenyomasara var
  return 0;
}
//---------------------------------------------------------------------------

void Simulation(T_JOB* job, int* sch, int NJ, int t_ref)
{
  int i;

  job[ sch[0] ].StartT = t_ref; //elso munka a ref idopontban indul
  job[ sch[0] ].EndT = job[ sch[0] ].StartT + job[ sch[0] ].ProcT;
  job[ sch[0] ].L = job[ sch[0] ].EndT - job[ sch[0] ].d;

  for(i=1; i<NJ; i++) //i az utemterv altal eloirt sorszam
    {
       job[ sch[i] ].StartT = job[ sch[i-1] ].EndT;
       job[ sch[i] ].EndT = job[ sch[i] ].StartT + job[ sch[i] ].ProcT;
       job[ sch[i] ].L = job[ sch[i] ].EndT - job[ sch[i] ].d;
    }
}

void Evaluate(T_JOB* job, int* sch, int NJ, T_OBJF* obj)
{
  long Csum = 0;
  int i;
  long Lmax = job[ 0 ].L;

  for (i=0; i<NJ; i++)
   {
    Csum += job[ sch[i] ].EndT;
    if ( Lmax < job[ i ].L )
         Lmax = job[ i ].L;
   }

  obj->Csum = Csum;
  obj->ASL = (double) Csum / job[ sch[NJ-1] ].EndT;
  obj->Lmax = Lmax;

}

void Print_Job_Gantt(T_JOB* job, int* sch, int NJ)
{
  int i;

  printf("\n Sorszam \t Munka \t Indit \t Befejez \t Hatarido \t Keses");
  for (i=0; i<NJ; i++)
    printf("\n %d \t\t %d \t %ld \t %ld \t\t %ld \t\t %ld",
            i,
            sch[i],
            job[ sch[i] ].StartT,
            job[ sch[i] ].EndT,
            job[ sch[i] ].d,
            job[ sch[i] ].L);

}

void SPT_rule(T_JOB* job, int* sch, int NJ)
{
  //SPT szerinti rendezes
  int i, j;
  int temp;

  for ( i=0; i < NJ-1; i++)
    for  ( j=i+1; j <= NJ-1; j++ )
       if ( job[ sch[i] ].ProcT > job[ sch[j] ].ProcT )
         { //csere
           temp = sch[i];
           sch[i] = sch[j];
           sch[j] = temp;
         }
}

void EDD_rule(T_JOB* job, int* sch, int NJ)
{
  //EDD szerinti rendezes
  int i, j;
  int temp;

  for ( i=0; i < NJ-1; i++)
    for  ( j=i+1; j <= NJ-1; j++ )
       if ( job[ sch[i] ].d > job[ sch[j] ].d )
         { //csere
           temp = sch[i];
           sch[i] = sch[j];
           sch[j] = temp;
         }
}