• Main Page
  • Modules
  • Classes
  • Files
  • File List

D:/Projekt/ECF_trunk/examples/iprojekt/SchedulingEvalOp.cpp

00001 #include <cmath>
00002 #include <ecf/ECF.h>
00003 #include "SchedulingEvalOp.h"
00004 
00005 #include "readpar.h"
00006 #include "matrice.h"
00007 
00008 
00009 // prilagodba za ECF
00010 // trenutno radi:
00011 //  single:
00012 //      staticki
00013 //          setup
00014 //          constraints (?)
00015 
00016 
00017 
00018 // makroi za uvjetnu provjeru
00019 #define CHECKMSG(condition, text) \
00020 if(!(condition)) {fprintf(stderr,"file: " __FILE__ "\nline: %d\nmsg:  " text "\n",__LINE__); exit(1);}
00021 #define CHECK(condition) \
00022 if(!(condition)) {fprintf(stderr,"Nesto ne valja!\nfile: " __FILE__ "\nline: %d\n" ,__LINE__); exit(1);}
00023 // fja max{x,0}
00024 #define POS(x)      (x>0 ? x : 0)
00025 #define MIN(x,y)    (x<y ? x : y)
00026 #define MAX(x,y)    (x>y ? x : y)
00027 
00028 // fitness_types
00029 const int Twt = 0;
00030 const int Nwt = 1;
00031 const int FTwt = 2;
00032 const int ETwt = 3;
00033 const int Fwt = 4;
00034 const int Cmax = 5;
00035 const int FUNCTIONS = 6;
00036 
00037 
00038 void SchedulingEvalOp::registerParameters(StateP state)
00039 {
00040     state->getRegistry()->registerEntry("test_cases", (voidP) (new std::string), ECF::STRING);
00041     state->getRegistry()->registerEntry("normalized", (voidP) (new uint(1)), ECF::UINT);
00042 }
00043 
00044 
00045 bool SchedulingEvalOp::initialize(StateP state)
00046 {
00047     std::string configFile;
00048 
00049     // check if the parameters are defined in the conf. file
00050     if(!state->getRegistry()->isModified("test_cases"))
00051         return false;
00052 
00053     voidP sptr = state->getRegistry()->getEntry("test_cases"); // get parameter value
00054     configFile = *((std::string*) sptr.get()); // convert from voidP to user defined type
00055 
00056     sptr = state->getRegistry()->getEntry("normalized"); // get parameter value
00057     m_Normalized = (bool) *((uint*) sptr.get()); // convert from voidP to user defined type
00058 
00059 // originalni dio iz BEAGLE implementacije:
00060     std::string input,sp,duration,deadline,weightT,weightF,weightE,weightN,term,ready,cons,speed;
00061     char pom[256];
00062     ReadPar p;
00063     unsigned int i,j;
00064     double d_niz[2][1000];
00065 
00066     // inicijalizacija default vrijednosti
00067     input = configFile; // glavni ulazni fajl, mora ga biti
00068 
00069     // ucitavanje parametara
00070     p.OpenFile(input.c_str());
00071     if(p.ReadParameter("single",ReadPar::INTEGER,&i))
00072         m_Environment = SINGLE;
00073     else if(p.ReadParameter("uniform",ReadPar::INTEGER,&i))
00074         m_Environment = UNIFORM;
00075     else if(p.ReadParameter("unrelated",ReadPar::INTEGER,&i))
00076         m_Environment = UNRELATED;
00077     else if(p.ReadParameter("jobshop",ReadPar::INTEGER,&i))
00078         m_Environment = JOBSHOP;
00079     p.ReadParameter("sets",ReadPar::INTEGER,&sets);
00080     p.ReadParameter("max_jobs",ReadPar::INTEGER,&max_jobs);
00081     if(!p.ReadParameter("max_machines",ReadPar::INTEGER,&max_machines))
00082         max_machines = 1;
00083     p.ReadParameter("max_length",ReadPar::INTEGER,&max_length);
00084     p.ReadParameter("duration",ReadPar::STRING,pom); duration = pom;
00085     p.ReadParameter("deadline",ReadPar::STRING,pom); deadline = pom;
00086     p.ReadParameter("weight_T",ReadPar::STRING,pom); weightT = pom;
00087     p.ReadParameter("weight_F",ReadPar::STRING,pom); weightF = pom;
00088     p.ReadParameter("weight_E",ReadPar::STRING,pom); weightE = pom;
00089     p.ReadParameter("weight_N",ReadPar::STRING,pom); weightN = pom;
00090     p.ReadParameter("SP",ReadPar::STRING,pom); sp = pom;
00091     p.ReadParameter("machine_file",ReadPar::STRING,pom); speed = pom;
00092     // dinamicki dolasci poslova
00093     if(p.ReadParameter("ready",ReadPar::STRING,pom))
00094     {   ready = pom;
00095         m_dynamic = true;
00096     }
00097     else
00098         m_dynamic = false;
00099     // limited error fitness izracunavanje
00100     if(p.ReadParameter("LEF",ReadPar::INTEGER,&i))
00101     {   if(i==1)
00102         {   m_LEF = true;
00103             if(!p.ReadParameter("LEF_value",ReadPar::DOUBLE,&m_LEFVal))
00104                 CHECKMSG(0,"LEF vrijednost nije zadana!");
00105         }
00106         else
00107             m_LEF = false;
00108     }
00109     // evaluacija - ispis rjesenja za svaku jedinku
00110     if(p.ReadParameter("evaluation",ReadPar::INTEGER,&i))
00111         if(i==1) m_Evaluation = true;
00112         else m_Evaluation = false;
00113     // fitness - mora biti definiran
00114     if(p.ReadParameter("fitness",ReadPar::STRING,pom))
00115     {   input = pom;
00116         if(input == "Twt")
00117             m_fitness = Twt;
00118         else if(input == "Nwt")
00119             m_fitness = Nwt;
00120         else if(input == "FTwt")
00121             m_fitness = FTwt;
00122         else if(input == "ETwt")
00123             m_fitness = ETwt;
00124         else if(input == "Cmax")
00125             m_fitness = Cmax;
00126         else if(input == "Fwt")
00127             m_fitness = Fwt;
00128         else
00129             CHECKMSG(0,"Nepoznata fitnes funkcija!");
00130     }
00131     else CHECKMSG(0,"Nije definirana fitnes funkcija!");
00132     // editiranje jedinke
00133     if(p.ReadParameter("editing",ReadPar::INTEGER,&i))
00134         if(i==1) m_editing = true;
00135     // stochastic sampling, koliko
00136     if(p.ReadParameter("stsampling",ReadPar::DOUBLE,&m_sampling))
00137         m_stsampling = true;
00138     else
00139         m_stsampling = false;
00140     // ogranicenja u rasporedu
00141     if(p.ReadParameter("constraints",ReadPar::STRING,pom))
00142     {   cons = pom;
00143         m_constrained = true;
00144     }
00145     else
00146         m_constrained = false;
00147     // trajanja postavljanja
00148     if(p.ReadParameter("setup",ReadPar::DOUBLE,&m_setup_faktor))
00149         m_setup = true;
00150     else
00151         m_setup = false;
00152 
00153     if(p.ReadParameter("idleness",ReadPar::INTEGER, &i))
00154         if(i == 1)  m_Idleness = true;
00155 
00156     //duration = path + duration;
00157     //deadline = path + deadline;
00158     //sp = path + sp;
00159     //weightT = path + weightT;
00160     //weightF = path + weightF;
00161     //weightE = path + weightE;
00162     //weightN = path + weightN;
00163     //ready = path + ready;
00164     N.Init(sets);
00165     SP.Init(sets);
00166     SD.Init(sets);
00167     Machines.Init(sets);
00168     MachineReady.Init(max_machines);
00169     Speed.Init(sets,max_jobs);
00170     Duration.Init(sets,max_jobs);
00171     Deadline.Init(sets,max_jobs);
00172     Durations.Init(max_jobs, max_machines);
00173     MachineIndex.Init(max_jobs, max_machines);
00174     WeightT.Init(sets,max_jobs);
00175     WeightF.Init(sets,max_jobs);
00176     WeightE.Init(sets,max_jobs);
00177     WeightN.Init(sets,max_jobs);
00178     Fitness.Init(sets+1,FUNCTIONS);
00179     Values.Init(max_machines,max_jobs);
00180     Precedence.Reset(max_jobs,max_jobs);    // prazna matrica znaci da nema ogranicenja!
00181     Setup.Init(max_jobs+1,max_jobs);
00182     if(m_Environment == JOBSHOP)
00183     {   Schedule.Init(sets, max_machines*max_jobs);
00184         PTimeAvg.Reset(sets, max_machines);
00185     }
00186     else
00187     {   Schedule.Init(sets,max_jobs);
00188         PTimeAvg.Init(sets,max_jobs);
00189         PTimeMinMachine.Init(sets,max_jobs);
00190     }
00191     SortedReady.Init(sets,max_jobs);
00192 
00193     pVrijednosti = new double[max_jobs];
00194     pRasporedjen = new bool[max_jobs];
00195     pIndex = new unsigned int[max_jobs];
00196     pUsed = new unsigned int[max_jobs];
00197     pArray = new double[max_jobs];
00198     pSlack = new double[max_jobs];
00199     pSlackSpeed = new double[max_jobs];
00200     pArrival = new double[max_jobs];
00201     pLevel = new double[max_jobs];
00202     pSetupAvg = new double[max_jobs + 1];
00203     pSamples = new bool[sets];
00204     pLastJob = new unsigned int[max_machines];
00205     pMachineScheduled = new unsigned int[max_machines];
00206     pOperationReady = new double[max_machines];
00207     pJobReady = new double[max_jobs];
00208     pOperationsScheduled = new unsigned int[max_jobs];
00209     pTotalWorkRemaining = new double[max_jobs];
00210     pTotalWorkDone = new double[max_jobs];
00211     pTotalMachineWork = new double[max_machines];
00212     pOperationsWaiting = new unsigned int[max_machines];
00213     pMachineWorkRemaining = new double[max_machines];
00214     pMachineValues = new double[max_machines];
00215     p.ReadParameter("jobs",ReadPar::DOUBLE,&d_niz[0][0],sets);
00216     p.ReadParameter("machines",ReadPar::DOUBLE,&d_niz[1][0],sets);
00217     total_jobs = 0;
00218     for(i=0; i<sets; i++)
00219     {   N[i][0] = d_niz[0][i];
00220         total_jobs += (int) d_niz[0][i];
00221         Machines[i][0] = d_niz[1][i];
00222     }
00223     Duration.Load(duration.c_str());
00224     Deadline.Load(deadline.c_str());
00225     if(m_Environment==UNIFORM)
00226     {   Speed.Load(speed.c_str());
00227     }
00228     WeightT.Load(weightT.c_str());
00229     WeightF.Load(weightF.c_str());
00230     WeightE.Load(weightE.c_str());
00231     WeightN.Load(weightN.c_str());
00232     SP.Load(sp.c_str());
00233     if(m_dynamic) Ready.Load(ready.c_str());
00234     else Ready.Reset(sets,max_jobs);
00235     if(m_constrained) Constraints.Load(cons.c_str());
00236     // racunamo sumu deadline-a
00237     Level.Init(sets,max_jobs);
00238     for(i=0; i<sets; i++)
00239     {   SD.Set(i,0);
00240         for(j=0; j<(unsigned int)N.Get(i); j++)
00241         {   SD.data[i][0] += Deadline.data[i][j];
00242             Level[i][j] = -1;   // oznacimo da je neizracunato
00243         }
00244     }
00245     // racunamo level cvorova u grafu ovisnosti
00246     for(i=0; i<sets; i++)
00247     {   if(m_constrained)
00248             ReadConstraints(Constraints,i,(unsigned int)N.Get(i),Precedence);
00249         for(j=0; j<(unsigned int)N.Get(i); j++)
00250             Level[i][j] = NodeLevel(i,j);
00251     }
00252     // racunamo prosjek i minimalno trajanje izvodjenja za UNRELATED
00253     if(m_Environment == UNRELATED)
00254     {   for(uint set=0; set<sets; set++)
00255         {   uint jobs = (uint) N[set][0];
00256             uint machines = (uint) Machines[set][0];
00257             for(j=0; j<jobs; j++)
00258             {   PTimeAvg[set][j] = 0;
00259                 uint min_machine = 0;
00260                 for(uint machine=0; machine<machines; machine++)
00261                 {   PTimeAvg[set][j] += Duration[set][j*machines + machine];
00262                     if(Duration[set][j*machines + machine] < Duration[set][j*machines + min_machine])
00263                         min_machine = machine;
00264                 }
00265                 PTimeAvg[set][j] /= machines;
00266                 PTimeMinMachine[set][j] = min_machine;
00267             }
00268         }
00269     }
00270     if(m_Environment == JOBSHOP)    // prosjek trajanja operacija po strojevima
00271     {   for(uint set=0; set<sets; set++)
00272         {   uint jobs = (uint) N[set][0];
00273             uint machines = (uint) Machines[set][0];
00274             for(j=0; j<jobs; j++)
00275             {   uint operations = machines;
00276                 for(uint op=0; op<operations; op++)
00277                 {   double dur = Duration[set][j*operations + op];
00278                     uint machine = (uint) dur / 1000;
00279                     dur = (int)dur % 1000;  // dobijemo trajanje
00280                     PTimeAvg[set][machine] += dur;
00281                 }
00282             }
00283             for(uint m=0; m<machines; m++)
00284                 PTimeAvg[set][m] /= jobs;
00285         }
00286     }
00287 
00288     // sortiramo indekse poslova po dolascima - treba za ubrzano izracunavanje
00289     //for(i=0; i<sets; i++)
00290     //{ ::pVal = Ready[i];
00291     //  uint jobs = (uint) N[i][0];
00292     //  for(j=0; j<jobs; j++)
00293     //      pIndex[j] = j;
00294     //  qsort(pIndex,jobs,sizeof(unsigned int),::Before);
00295     //  for(j=0; j<jobs; j++)
00296     //      SortedReady[i][j] = pIndex[j];
00297     //}
00298                 
00299     p.CloseFile();
00300 
00301     return true;
00302 }
00303 
00304 
00305 // rekurzivno racunanje 'level' vrijednosti svakog posla
00306 // ima smisla samo u problemima s ogranicenjima
00307 // promjena 27.07: level cvora ukljucuje i trajanje cvora
00308 double SchedulingEvalOp::NodeLevel(int set, int node)
00309 {   double value,level;
00310     int succ,i,next;
00311     if(Level[set][node] > -1)   // ako je vec izracunato
00312         return Level[set][node];
00313     if(Precedence[node][1] == 0)    // ako nema sljedbenika
00314         return Duration[set][node];
00315     succ = (int)Precedence[node][1];    // koliko sljedbenika
00316     next = (int)Precedence[node][2];    // prvi sljedbenik
00317     level = NodeLevel(set,next) + Duration[set][node];  // level zbog prvog sljedbenika
00318     for(i=1; i<succ; i++)
00319     {   next = (int)Precedence[node][i+2];
00320         value = NodeLevel(set,next) + Duration[set][node];
00321         if(value > level)
00322             level = value;
00323     }
00324     return level;
00325 }
00326 
00327 
00328 
00329 
00330 SchedulingEvalOp::~SchedulingEvalOp()
00331 {
00332     delete [] pRasporedjen;
00333     delete [] pVrijednosti;
00334     delete [] pIndex;
00335     delete [] pUsed;
00336     delete [] pArray;
00337     delete [] pSlack;
00338     delete [] pSlackSpeed;
00339     delete [] pSamples;
00340     delete [] pArrival;
00341     delete [] pLevel;
00342     delete [] pSetupAvg;
00343     delete [] pLastJob;
00344     delete [] pMachineScheduled;
00345     delete [] pOperationReady;
00346     delete [] pJobReady;
00347     delete [] pOperationsScheduled;
00348     delete [] pTotalWorkRemaining;
00349     delete [] pTotalWorkDone;
00350     delete [] pTotalMachineWork;
00351     delete [] pMachineWorkRemaining;
00352     delete [] pOperationsWaiting;
00353     delete [] pMachineValues;
00354 }
00355 
00356 
00357 // dekodira matricu Constraints i definira matricu Precedence
00358 void SchedulingEvalOp::ReadConstraints(Matrica &Constraints, int set, int jobs, Matrica &Precedence)
00359 {
00360     int i,j,prethodnika,prethodnik,pom;
00361     unsigned int podatak;
00362     //Precedence.Init(jobs,jobs);
00363     // prvo ocistimo prva dva stupca! gdje su brojevi prethodnika i sljedbenika
00364     for(i=0; i<jobs; i++)
00365         for(j=0; j<2; j++)
00366             Precedence[i][j] = 0;
00367     for(i=0; i<jobs; i++)
00368     {   podatak = (unsigned int) Constraints[set][i];
00369         prethodnik = 1; // koji po redu posao iza mene
00370         prethodnika = 0;
00371         while(podatak != 0)
00372         {   if(podatak%2 != 0)
00373             {   prethodnika++;  // povecam broj svojih prethodnika
00374                 pom = (int) Precedence[i-prethodnik][1] + 1;
00375                 Precedence[i-prethodnik][pom+1] = i;
00376                 Precedence[i-prethodnik][1] = pom;  // i broj sljedbenika od moga prethodnika
00377             }
00378             prethodnik++;
00379             podatak /= 2;
00380         }
00381         Precedence[i][0] = prethodnika;
00382     }
00383 }
00384 
00385 
00386 // generira matricu sequence dependant setup trajanja
00387 // i polje prosjecnih trajanja postavljanja za svaki posao prema ostalima
00388 void SchedulingEvalOp::MakeSetup(Matrica &Duration, int set, int jobs, double faktor, Matrica &Setup)
00389 {
00390     int i,j;
00391     pSetupAvg[jobs] = 0;
00392     if(m_Environment == JOBSHOP)
00393     {   srand(set);
00394         for(i=0; i<jobs; i++)
00395         {   Setup[jobs][i] = (int) ((rand()%max_length+1) * faktor);    // polazno trajanje postavljanja
00396             pSetupAvg[jobs] += Setup[jobs][i];
00397             for(j=0; j<=i; j++)
00398             {   Setup[i][j] = (int) ((rand()%max_length+1) * faktor);
00399                 Setup[j][i] = (int) ((rand()%max_length+1) * faktor);
00400                 pSetupAvg[i] += Setup[i][j];
00401                 pSetupAvg[j] += Setup[j][i];
00402             }
00403         }
00404     }
00405     else
00406         for(i=0; i<jobs; i++)
00407         {   pSetupAvg[i] = 0;
00408             Setup[jobs][i] = Duration[set][(i+1) % jobs];   // polazno trajanje postavljanja
00409             pSetupAvg[jobs] += Setup[jobs][i];
00410             for(j=0; j<=i; j++)
00411             {   Setup[i][j] = ceil( fabs( Duration[set][i] - Duration[set][j] ) * faktor);
00412                 Setup[j][i] = ceil( fabs( Duration[set][(i+1) % jobs] - Duration[set][(j+1) % jobs] ) * faktor);
00413                 pSetupAvg[i] += Setup[i][j];
00414                 pSetupAvg[j] += Setup[j][i];
00415             }
00416         }
00417     pSetupAvg[jobs] /= jobs;
00418     for(i=0; i<jobs; i++)
00419         pSetupAvg[i] /= (jobs-1);
00420 }
00421 
00422 
00423 FitnessP SchedulingEvalOp::evaluate(IndividualP individual)
00424 {
00425     // stvaranje zeljenog Fintess objekta:
00426     FitnessP fitness = static_cast<FitnessP> (new FitnessMin);
00427 
00428     // dohvat genotipa jedinke
00429     TreeP tree = boost::dynamic_pointer_cast<Tree::Tree> (individual->getGenotype());
00430 
00431 // oroginalni kod iz BEAGLE implementacije
00432     unsigned int i;
00433     double dRawFitness, dFitness;
00434 
00435     // stochastic sampling?
00436     if(m_stsampling)
00437     {   int koliko = (int) (m_sampling*sets);
00438         int razmak = sets / koliko;
00439         int pocetni = rand()%razmak;
00440         for(i=0; i<sets; i++)
00441             pSamples[i] = false;
00442         for(i=pocetni; i<sets; i+=razmak)
00443             pSamples[i] = true;
00444     }
00445 
00446     switch(m_Environment)
00447     {   case SINGLE:
00448             dRawFitness = EvaluateSingle(tree);
00449         break;
00450         //case UNIFORM:
00451         //  EvaluateUniform(dRawFitness);
00452         //break;
00453         //case UNRELATED:
00454         //  EvaluateUnrelated(dRawFitness);
00455         //break;
00456         //case JOBSHOP:
00457         //  EvaluateJobShop(dRawFitness);
00458         //break;
00459     }
00460 
00461     //dFitness = dRawFitness /= nJobS*SETS; // prosjek
00462     //double lRMSE = sqrt(sqrt(dRawFitness));       // irelevantno za turnir selekciju
00463     //dFitness = (1.0 / (lRMSE + 1.0)); 
00464     //dFitness = -dRawFitness;  // obrnemo kriterij (trazimo minimum)
00465     dFitness = dRawFitness;
00466 
00467     //if(m_Evaluation)  // samo za usporedbu heuristika! pise rezultate svih skupova u fajl
00468     //{ Fitness.Save("rezultat_GP.txt");
00469     //  std::ostream *file = new std::ofstream("rezultat_GP.txt", std::ios_base::app);
00470     //  Evaluator.write();
00471     //  *file << std::endl << "-- infix: " << Evaluator.m_output << " --" << std::endl;
00472     //  *file << "Editirano: " << edited << ", ukupno: " << total << std::endl;
00473     //  *file << std::flush;
00474     //  delete file;
00475     //  Schedule.Save("raspored_GP.txt");
00476     //}
00477 
00478     fitness->setValue(dFitness);
00479 
00480     return fitness;
00481 }
00482 
00483 
00484 // obrada za SINGLE okruzenje
00485 double SchedulingEvalOp::EvaluateSingle(TreeP tree)
00486 {
00487     double dClock, dRez, dSetFitness, dAvgWeights, dAvgDuration, dAvgDueDate;
00488     double dLateness, dTotalLateness=0, dTardiness, dTotalTardiness=0;
00489     double dNwt, dTotalNwt=0, dBest, dSPr, dSDr;
00490     unsigned int nPoslova,nNiz,nJob,i,j,index,nLateJobs,nTotalLateJobs=0,nNr;
00491     unsigned int nLastJob,nOdabrani;
00492 
00493     double dRawFitness=0;
00494 
00495 // vrtimo sve skupove
00496     for(nNiz = 0; nNiz < sets; nNiz++)
00497     {   nNr = nPoslova = (int) N.Get(nNiz);
00498     // preliminarna ispitivanja
00499         // radimo li stochastic sampling
00500         if(m_stsampling)
00501             if(pSamples[nNiz] == false)
00502                 continue;   // jednostavno preskocimo taj test case
00503         // gleda li se limited error fitness
00504         if(m_LEF)
00505         {   if(dRawFitness > m_LEFVal)
00506                 break;  // prekid ispitivanja
00507         }
00508         if(m_constrained)   // ima li ogranicenja
00509             ReadConstraints(Constraints,nNiz,nPoslova,Precedence);
00510         if(m_setup) // trajanja postavljanja
00511             MakeSetup(Duration,nNiz,nPoslova,m_setup_faktor,Setup);
00512 
00513         // postavljanje pocetnih vrijednosti za pojedini skup
00514         nLateJobs = 0;
00515         dLateness = 0;
00516         dTardiness = 0;
00517         dNwt = 0;
00518         dClock = 0; dSetFitness = 0;
00519         nLastJob = nPoslova;
00520         dAvgDueDate = 0;
00521         for(i=0; i<nPoslova; i++)
00522         {   dAvgDueDate += Deadline[nNiz][i];
00523             pRasporedjen[i] = false;    // svi nerasporedjeni
00524             pIndex[i] = i;  // inicijalni poredak
00525         }
00526         dAvgDueDate /= nPoslova;
00527         dSPr = SP.Get(nNiz);
00528         dSDr = SD.Get(nNiz);
00529 
00530     // postavljanje pocetnih vrijednosti terminala - nepromjenjivi terminali
00531 /*      Evaluator.m_pTermValues[T_N] = N.Get(nNiz);
00532         Evaluator.SetTermArraySize(nPoslova);   // koliko poslova u skupu - za vektorsku evaluaciju
00533         Evaluator.pIndex = pIndex;  // polje indeksa poslova
00534         Evaluator.m_iOffset = 0;        // indeks prvog nerasporedjenog
00535         for(i=0; i<nPoslova; i++)
00536         {   Evaluator.m_dTermValuesArray[T_N][i] = N.data[nNiz][0];
00537             Evaluator.m_dTermValuesArray[T_SP][i] = SP.data[nNiz][0];
00538             Evaluator.m_dTermValuesArray[T_SD][i] = SD.data[nNiz][0];
00539             Evaluator.m_dTermValuesArray[T_SC][i] = Precedence[i][1];   // broj sljedbenika
00540             Evaluator.m_dTermValuesArray[T_TF][i] = 1 - dAvgDueDate / SP[nNiz][0];
00541         }
00542         memcpy(Evaluator.m_dTermValuesArray[T_pt], Duration.data[nNiz], nPoslova*sizeof(double));
00543         memcpy(Evaluator.m_dTermValuesArray[T_dd], Deadline.data[nNiz], nPoslova*sizeof(double));
00544         memcpy(Evaluator.m_dTermValuesArray[T_w],  WeightT.data[nNiz], nPoslova*sizeof(double));
00545         memcpy(Evaluator.m_dTermValuesArray[T_LVL], Level[nNiz], nPoslova*sizeof(double));
00546 */
00547 
00549 // ako u terminalima ima vremenski ovisnih, moramo raditi posao po posao
00550         for(nJob=0; nJob<nPoslova; nJob++)  // rasporedjujemo svaki posao unutar skupa jedan po jedan
00551         {   
00552             // terminali neovisni o poslu (ali ovisni o rasporedjenim poslovima!)
00553             tree->setTerminalValue("SPr", &dSPr);    // suma trajanja preostalih
00554             tree->setTerminalValue("Nr", &nNr);      // broj preostalih
00555 
00556             // dinamicka okolina; + uzeta u obzir eventualna ogranicenja
00557             if(m_dynamic)
00558             {   unsigned int raspolozivi = nJob, prvi = nJob;
00559                 unsigned int najkraci;  // najkraci raspolozivi
00560                 // trebamo pronaci prvog raspolozivog bez nezavrsenih prethodnika
00561                 for(; Precedence[pIndex[raspolozivi]][0] > 0; raspolozivi++)    NULL;
00562                 double kada = Ready[nNiz][pIndex[raspolozivi]]; // pocetno vrijeme
00563                 double najdulje = 0, najkrace = 0;
00564                 for( ; raspolozivi < nPoslova; raspolozivi++)   // koji je 'najstariji'?
00565                 {   int job = pIndex[raspolozivi];
00566                     if(Ready.data[nNiz][job] < kada && Precedence[job][0] == 0) // gledamo najblize vrijeme dolaska
00567                     {   kada = Ready.data[nNiz][job];
00568                         prvi = raspolozivi;
00569                     }
00570                 }
00571                 if(kada > dClock)   // ako nema raspolozivih 
00572                 {   dClock = kada;  // sat postavimo na najblize vrijeme dolaska
00573                 }
00574                 // pronadjimo najduljeg i najkraceg raspolozivog
00575                 najdulje = najkrace = Duration[nNiz][pIndex[prvi]];
00576                 najkraci = prvi;
00577                 for(i = nJob; i < nPoslova; i++)
00578                 {   int job = pIndex[i];
00579                     if(dClock < Ready[nNiz][job] || Precedence[job][0] > 0)
00580                         continue;
00581                     if(Duration[nNiz][job] < najkrace)  // najkrace
00582                     {   najkrace = Duration[nNiz][job];
00583                         najkraci = i;
00584                     }
00585                 }
00586                 // sad pogledamo najduljega koji pocinje <= zavrsetka najkraceg raspolozivog
00587                 for(i = nJob; i < nPoslova; i++)
00588                 {   int job = pIndex[i];
00589                     if(Precedence[job][0] > 0)
00590                         continue;
00591                     if(Duration[nNiz][job] > najdulje && Ready[nNiz][job] <= (dClock+najkrace)) // gledamo najdulje trajanje
00592                         najdulje = Duration[nNiz][job];
00593                 }
00594                 // sada je (dClock + najkrace + najdulje) limit za gledanje u buducnost!
00595 
00596                 // trebamo izracunati nove vrijednosti vremenski ovisnih terminala!
00597                 double dCurrent;
00598                 for(i = nJob; i<nPoslova; i++)
00599                 {   j = pIndex[i];
00600                     // terminali ovisni o poslu
00601                     pSlack[j] = POS(Deadline[nNiz][j] - (dClock + Duration[nNiz][j]));
00602                     tree->setTerminalValue("SL", &pSlack[j]);
00603                     tree->setTerminalValue("pt", &Duration[nNiz][j]);
00604                     tree->setTerminalValue("w", &WeightT[nNiz][j]);
00605                     tree->setTerminalValue("dd", &Deadline[nNiz][j]);
00606 
00607                     // terminali za trajanja postavljanja
00608                     if(m_setup) {
00609                         tree->setTerminalValue("STP", &Setup[nLastJob][j]);   // trajanje postavljanja
00610                         tree->setTerminalValue("Sav", &pSetupAvg[nLastJob]);  // prosjecno t.p.
00611                     }
00612 
00613                     // terminali za ogranicenja u redoslijedu
00614                     if(m_constrained) {
00615                         tree->setTerminalValue("SC", &Precedence[j][1]);      // broj sljedbenika
00616                         tree->setTerminalValue("LVL", &Level[nNiz][j]);       // razina posla (level)
00617                     }
00618 
00619                     tree->execute(&dCurrent);
00620                     pVrijednosti[j] = dCurrent;
00621                 }
00622 
00623                 // druga verzija (jednostavnija)
00624                 // samo gledamo najboljega koji moze poceti prije zavrsetka najkraceg raspolozivog
00625                 dBest = pVrijednosti[pIndex[najkraci]]; // poc. vrijednost za usporedbu
00626                 nOdabrani = najkraci;
00627                 for(i=nJob; i<nPoslova; i++)    // trazimo najbolju vrijednost unutar < (dClock + najkrace)
00628                 {   if((pVrijednosti[pIndex[i]] < dBest) && (Ready[nNiz][pIndex[i]] < dClock + najkrace) \
00629                         && Precedence[pIndex[i]][0] == 0)
00630                     {   dBest = pVrijednosti[pIndex[i]];
00631                         nOdabrani = i;
00632                     }
00633                 }
00634                 kada = Ready[nNiz][pIndex[nOdabrani]] - dClock; // za koliko pocinje odabrani?
00635 
00636                 // redovni nastavak (iza 1. i 2. verzije)
00637                 if(kada > 0)    // odabrali smo cekati
00638                     dClock += kada; // ili: dClock = Ready[nNiz][pIndex[nOdabrani]];
00639             }   // endif - m_dynamic
00640 
00641             // staticki
00642             else
00643             {   //CalcTimedTerminals(nNiz,nPoslova,nJob,dClock);
00644                 
00645                 double dCurrent;
00646 
00647                 // ocijeni sve nerasporedjene poslove
00648                 for(i = nJob; i<nPoslova; i++)
00649                 {   j = pIndex[i];
00650                     // terminali ovisni o poslu
00651                     pSlack[j] = POS(Deadline[nNiz][j] - (dClock + Duration[nNiz][j]));
00652                     tree->setTerminalValue("SL", &pSlack[j]);
00653                     tree->setTerminalValue("pt", &Duration[nNiz][j]);
00654                     tree->setTerminalValue("w", &WeightT[nNiz][j]);
00655                     tree->setTerminalValue("dd", &Deadline[nNiz][j]);
00656 
00657                     // terminali za trajanja postavljanja
00658                     if(m_setup) {
00659                         tree->setTerminalValue("STP", &Setup[nLastJob][j]);   // trajanje postavljanja
00660                         tree->setTerminalValue("Sav", &pSetupAvg[nLastJob]);  // prosjecno t.p.
00661                     }
00662 
00663                     // terminali za ogranicenja u redoslijedu
00664                     if(m_constrained) {
00665                         tree->setTerminalValue("SC", &Precedence[j][1]);      // broj sljedbenika
00666                         tree->setTerminalValue("LVL", &Level[nNiz][j]);       // razina posla (level)
00667                     }
00668 
00669                     tree->execute(&dCurrent);
00670 
00671                     pVrijednosti[j] = dCurrent;
00672                 }
00673 
00674                 dBest = pVrijednosti[pIndex[nJob]]; // pretpostavimo da je neki najbolji
00675                 nOdabrani = nJob;
00676 
00677                 if(m_constrained)   // trazimo prvi bez prethodnika
00678                     for(; Precedence[pIndex[nOdabrani]][0] > 0; nOdabrani++)    NULL;
00679 
00680                 for(i = nJob; i<nPoslova; i++)  // pa pogledamo ostale
00681                 {   // trazimo najmanju vrijednost
00682                     int index = pIndex[i];
00683                     if(pVrijednosti[index] < dBest && Precedence[index][0] == 0)    // je li to najbolja vrijednost?
00684                     {   dBest = pVrijednosti[index];
00685                         nOdabrani = i;
00686                     }
00687                 }
00688             }
00689 
00690             // vrijednost pIndex[nOdabrani] je indeks posla koji ide sljedeci
00691             // gledamo nOdabrani kao rezultat; zamijenimo nJob-ti i odabrani u polju indeksa
00692             i = pIndex[nJob];
00693             pIndex[nJob] = pIndex[nOdabrani];
00694             pIndex[nOdabrani] = i;
00695             pRasporedjen[pIndex[nJob]] = true;
00696 
00697             // azuriramo vrijednosti promjenjivih terminala
00698             dClock += Duration[nNiz][pIndex[nJob]];   // update vremena
00699             dSPr -= Duration[nNiz][pIndex[nJob]];     // update trajanja preostalih
00700             dSDr -= Deadline[nNiz][pIndex[nJob]];     // update deadlinea
00701             nNr--;                                    // update broja preostalih
00702             if(m_constrained)   // smanjimo broj prethodnika svim sljedbenicima odabranog posla
00703                 for(i=0; i<Precedence[pIndex[nJob]][1]; i++)
00704                 {   j = (int) Precedence[pIndex[nJob]][i+2];
00705                     Precedence[j][0] -= 1;
00706                 }
00707             if(m_setup) // trajanje postavljanja
00708             {   dClock += Setup[nLastJob][pIndex[nJob]];
00709                 nLastJob = pIndex[nJob];    // sljedeci prethodni posao
00710             }
00711             Schedule[nNiz][nJob] = pIndex[nJob];    // zapisemo posao u raspored
00712         } // kraj petlje koja vrti poslove u skupu
00713 
00714 
00715         // racunanje raznih kriterija za trenutni skup
00716         {   if(m_Evaluation)
00717             {   for(nJob=nPoslova ; nJob < this->max_jobs; nJob++)
00718                     Schedule[nNiz][nJob] = 0;                   // ostalo nule
00719             }
00720             // odredimo fitnes kriterij - sve moguce funkcije
00721             dClock = 0; nLastJob = nPoslova; dAvgWeights = dAvgDuration = 0;
00722             for(nJob = 0; nJob<nPoslova; nJob++)
00723             {   index = pIndex[nJob];
00724                 dAvgWeights += WeightT[nNiz][index];
00725                 dAvgDuration += Duration[nNiz][index];
00726                 if(m_dynamic && dClock < Ready[nNiz][index])    // ako jos nije raspoloziv
00727                     dClock = Ready[nNiz][index];
00728                 if(m_setup)
00729                     dClock += Setup[nLastJob][index];
00730                 nLastJob = index;
00731                 dClock += Duration.data[nNiz][index];   // update vremena
00732                 dRez = dClock - Deadline.Get(nNiz,index);   // kasnjenje
00733                 dLateness += dRez*WeightT.data[nNiz][index];    // tezinsko kasnjenje
00734                 if(dRez > 0) dTardiness += dRez*WeightT.data[nNiz][index];  // tezinska zakasnjelost
00735                 if(dRez > 0) nLateJobs ++;  // kao broj zakasnjelih poslova
00736                 if(dRez > 0) dNwt += WeightN.data[nNiz][index]; // tezinski broj zakasnjelih
00737             }
00738             // normiranje fitnesa ovisno o broju poslova - dodano 27.07.
00739             // promijenjeno (valjda konacno) 04.09.
00740             if(m_Normalized) {
00741                 dAvgWeights /= nPoslova;    // prosjecni tezinski faktor skupa
00742                 dAvgDuration /= nPoslova;
00743                 dTardiness /= (nPoslova * dAvgWeights * dAvgDuration);
00744                 dNwt /= (nPoslova * dAvgWeights);
00745             }
00746             switch(m_fitness)   // sto uzimamo kao fitnes?
00747             {   case Twt: dRawFitness += dTardiness; break;
00748                 case Nwt: dRawFitness += dNwt; break;
00749                 default: exit(1);
00750             }
00751             nTotalLateJobs += nLateJobs;
00752             dTotalNwt += dNwt;
00753             dTotalLateness += dLateness;
00754             dTotalTardiness += dTardiness;
00755             Fitness[nNiz][Twt] = dTardiness;
00756             Fitness[nNiz][Nwt] = dNwt;
00757             Fitness[nNiz][FTwt] = 0;    // zasada
00758             Fitness[nNiz][ETwt] = 0;
00759         }
00760     }
00761 // kraj petlje koja vrti skupove poslova
00762 
00763     Fitness[sets][Twt] = dTotalTardiness;
00764     Fitness[sets][Nwt] = dTotalNwt;
00765 
00766     return dRawFitness;
00767 }

Generated on Wed Sep 21 2011 13:46:53 for ECF by  doxygen 1.7.1