00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #include <ecf/ECF.h>
00020 #include "fitnes.hpp"
00021 #include <cmath>
00022
00023
00024 node Nodes[TOTAL_NODES];
00025
00026
00027 #define CHECKMSG(condition, text) \
00028 if(!(condition)) {fprintf(stderr,"file: " __FILE__ "\nline: %d\nmsg: " text "\n",__LINE__); exit(1);}
00029 #define CHECK(condition) \
00030 if(!(condition)) {fprintf(stderr,"Nesto ne valja!\nfile: " __FILE__ "\nline: %d\n" ,__LINE__); exit(1);}
00031
00032 #define POS(x) (x>0 ? x : 0)
00033 #define MIN(x,y) (x<y ? x : y)
00034 #define MAX(x,y) (x>y ? x : y)
00035
00036
00037
00038 double *pVal;
00039 int Before(const void *arg1, const void *arg2)
00040 {
00041 if(pVal[*(uint*)arg1] < pVal[*(uint*)arg2])
00042 return -1;
00043 else if(pVal[*(uint*)arg1] > pVal[*(uint*)arg2])
00044 return 1;
00045 return 0;
00046 }
00047
00048
00049
00050 SchedulingEvalOp::SchedulingEvalOp()
00051 {
00052 for(int i=0; i<TERMINALS+OFFSET; i++)
00053 { Nodes[i].active = false;
00054 }
00055 for(int i=TERMINALS+OFFSET; i<TOTAL_NODES; i++)
00056 { Nodes[i].active = true;
00057 }
00058
00059 Nodes[NUL].name = "0";
00060 Nodes[NUL].value = 0;
00061 Nodes[ONE].name = "1";
00062 Nodes[ONE].value = 1;
00063 Nodes[T_N].name = "N";
00064 Nodes[T_SP].name = "SP";
00065 Nodes[T_SD].name = "SD";
00066 Nodes[T_pt].name = "pt";
00067 Nodes[T_dd].name = "dd";
00068 Nodes[T_w].name = "w";
00069 Nodes[T_Nr].name = "Nr";
00070 Nodes[T_SPr].name = "SPr";
00071 Nodes[T_SL].name = "SL";
00072 Nodes[T_AR].name = "AR";
00073 Nodes[T_SC].name = "SC";
00074 Nodes[T_LVL].name = "LVL";
00075 Nodes[T_STP].name = "STP";
00076 Nodes[T_Sav].name = "Sav";
00077 Nodes[T_SLs].name = "SLs";
00078 Nodes[T_SPD].name = "SPD";
00079 Nodes[T_Msm].name = "Msm";
00080 Nodes[T_pmin].name = "pmin";
00081 Nodes[T_pavg].name = "pavg";
00082 Nodes[T_PAT].name = "PAT";
00083 Nodes[T_MR].name = "MR";
00084 Nodes[T_age].name = "age";
00085 Nodes[T_L].name = "L";
00086 Nodes[T_SLr].name = "SLr";
00087 Nodes[T_CLK].name = "CLK";
00088 Nodes[T_NOPr].name = "NOPr";
00089 Nodes[T_TWK].name = "TWK";
00090 Nodes[T_TWKr].name = "TWKR";
00091 Nodes[T_PTav].name = "PTav";
00092 Nodes[T_HTR].name = "HTR";
00093 Nodes[T_TF].name = "TF";
00094
00095 Nodes[T_MNOPr].name = "MNOPr";
00096 Nodes[T_MNOPw].name = "MNOPw";
00097 Nodes[T_MTWK].name = "MTWK";
00098 Nodes[T_MTWKr].name = "MTWKr";
00099 Nodes[T_MTWKav].name = "MTWKav";
00100 Nodes[T_MUTL].name = "MUTL";
00101
00102 Nodes[ADD].name = "+";
00103 Nodes[SUB].name = "-";
00104 Nodes[MUL].name = "*";
00105 Nodes[DIV].name = "/";
00106 Nodes[POS].name = "pos";
00107 Nodes[SQR].name = "sqr";
00108 Nodes[IFGT].name = "ifgt";
00109
00110 m_Idleness = false;
00111 m_TermUsage = false;
00112 m_BestSubset = 100;
00113 m_LEF = 0;
00114 m_editing = false;
00115 m_Evaluation = false;
00116 Evaluator.SetExprSize(2000);
00117 edited = 0;
00118 total = 0;
00119 }
00120
00121
00122 SchedulingEvalOp::~SchedulingEvalOp()
00123 {
00124 delete [] pRasporedjen;
00125 delete [] pVrijednosti;
00126 delete [] pIndex;
00127 delete [] pUsed;
00128 delete [] pArray;
00129 delete [] pSlack;
00130 delete [] pSlackSpeed;
00131 delete [] pSamples;
00132 delete [] pArrival;
00133 delete [] pLevel;
00134 delete [] pSetupAvg;
00135 delete [] pLastJob;
00136 delete [] pMachineScheduled;
00137 delete [] pOperationReady;
00138 delete [] pJobReady;
00139 delete [] pOperationsScheduled;
00140 delete [] pTotalWorkRemaining;
00141 delete [] pTotalWorkDone;
00142 delete [] pTotalMachineWork;
00143 delete [] pMachineWorkRemaining;
00144 delete [] pOperationsWaiting;
00145 delete [] pMachineValues;
00146 }
00147
00148
00149 void SchedulingEvalOp::registerParameters(StateP state)
00150 {
00151 state->getRegistry()->registerEntry("test_cases", (voidP) (new std::string), ECF::STRING);
00152 state->getRegistry()->registerEntry("normalized", (voidP) (new uint(1)), ECF::UINT);
00153 state->getRegistry()->registerEntry("genotip", (voidP) (new uint(1)), ECF::UINT);
00154 state->getRegistry()->registerEntry("primjer", (voidP) (new uint(0)), ECF::UINT);
00155 }
00156
00157
00158
00159
00160 bool SchedulingEvalOp::initialize(StateP state)
00161 {
00162 state_ = state;
00163
00164 std::string configFile;
00165
00166
00167 if(!state->getRegistry()->isModified("test_cases"))
00168 return false;
00169
00170 voidP sptr = state->getRegistry()->getEntry("test_cases");
00171 configFile = *((std::string*) sptr.get());
00172 in_file = configFile;
00173
00174 sptr = state->getRegistry()->getEntry("normalized");
00175 m_Normalized = (bool) *((uint*) sptr.get());
00176
00177 sptr = state->getRegistry()->getEntry("genotip");
00178 m_genotip = (uint) *((uint*) sptr.get());
00179
00180 sptr = state->getRegistry()->getEntry("primjer");
00181 m_primjer = (uint) *((uint*) sptr.get());
00182
00183 if(m_primjer > 60) {
00184 m_primjer = *((uint*) state->getContext()->environment);
00185 }
00186
00187 if(m_genotip == 1)
00188
00189 ReadTerminals(state);
00190
00191
00192 std::string input,sp,duration,deadline,weightT,weightF,weightE,weightN,term,ready,cons,speed;
00193 char pom[256];
00194 ReadPar p;
00195 unsigned int i,j;
00196 double d_niz[2][1000];
00197
00200
00201
00202
00203
00204
00205
00208
00209
00210
00211 input = configFile;
00212
00213
00214 p.OpenFile(input.c_str());
00215 if(p.ReadParameter("single",ReadPar::INTEGER,&i))
00216 m_Environment = SINGLE;
00217 else if(p.ReadParameter("uniform",ReadPar::INTEGER,&i))
00218 m_Environment = UNIFORM;
00219 else if(p.ReadParameter("unrelated",ReadPar::INTEGER,&i))
00220 m_Environment = UNRELATED;
00221 else if(p.ReadParameter("jobshop",ReadPar::INTEGER,&i))
00222 m_Environment = JOBSHOP;
00223 p.ReadParameter("sets",ReadPar::INTEGER,&sets);
00224 p.ReadParameter("max_jobs",ReadPar::INTEGER,&max_jobs);
00225 if(!p.ReadParameter("max_machines",ReadPar::INTEGER,&max_machines))
00226 max_machines = 1;
00227 p.ReadParameter("max_length",ReadPar::INTEGER,&max_length);
00228 p.ReadParameter("duration",ReadPar::STRING,pom); duration = pom;
00229 p.ReadParameter("deadline",ReadPar::STRING,pom); deadline = pom;
00230 p.ReadParameter("weight_T",ReadPar::STRING,pom); weightT = pom;
00231 p.ReadParameter("weight_F",ReadPar::STRING,pom); weightF = pom;
00232 p.ReadParameter("weight_E",ReadPar::STRING,pom); weightE = pom;
00233 p.ReadParameter("weight_N",ReadPar::STRING,pom); weightN = pom;
00234 p.ReadParameter("SP",ReadPar::STRING,pom); sp = pom;
00235 p.ReadParameter("machine_file",ReadPar::STRING,pom); speed = pom;
00236
00237 if(p.ReadParameter("ready",ReadPar::STRING,pom))
00238 { ready = pom;
00239 m_dynamic = true;
00240 }
00241 else
00242 m_dynamic = false;
00243
00244 if(p.ReadParameter("LEF",ReadPar::INTEGER,&i))
00245 { if(i==1)
00246 { m_LEF = true;
00247 if(!p.ReadParameter("LEF_value",ReadPar::DOUBLE,&m_LEFVal))
00248 CHECKMSG(0,"LEF vrijednost nije zadana!");
00249 }
00250 }
00251
00252 if(p.ReadParameter("evaluation",ReadPar::INTEGER,&i))
00253 if(i==1) m_Evaluation = true;
00254
00255 if(p.ReadParameter("fitness",ReadPar::STRING,pom))
00256 { input = pom;
00257 if(input == "Twt")
00258 m_fitness = Twt;
00259 else if(input == "Nwt")
00260 m_fitness = Nwt;
00261 else if(input == "FTwt")
00262 m_fitness = FTwt;
00263 else if(input == "ETwt")
00264 m_fitness = ETwt;
00265 else if(input == "Cmax")
00266 m_fitness = Cmax;
00267 else if(input == "Fwt")
00268 m_fitness = Fwt;
00269 else if(input == "TwtCmax")
00270 m_fitness = TwtCmax;
00271 else if(input == "NwtCmax")
00272 m_fitness = NwtCmax;
00273 else
00274 CHECKMSG(0,"Nepoznata fitnes funkcija!");
00275 }
00276 else CHECKMSG(0,"Nije definirana fitnes funkcija!");
00277
00278 if(p.ReadParameter("editing",ReadPar::INTEGER,&i))
00279 if(i==1) m_editing = true;
00280
00281 if(p.ReadParameter("stsampling",ReadPar::DOUBLE,&m_sampling))
00282 m_stsampling = true;
00283 else
00284 m_stsampling = false;
00285
00286 if(p.ReadParameter("constraints",ReadPar::STRING,pom))
00287 { cons = pom;
00288 m_constrained = true;
00289 }
00290 else
00291 m_constrained = false;
00292
00293 if(p.ReadParameter("setup",ReadPar::DOUBLE,&m_setup_faktor))
00294 m_setup = true;
00295 else
00296 m_setup = false;
00297
00298 p.ReadParameter("bestsubset",ReadPar::INTEGER,&m_BestSubset);
00299 if(p.ReadParameter("idleness",ReadPar::INTEGER, &i))
00300 if(i == 1) m_Idleness = true;
00301
00302 N.Init(sets);
00303 SP.Init(sets);
00304 SD.Init(sets);
00305 Machines.Init(sets);
00306 MachineReady.Init(max_machines);
00307 Speed.Init(sets,max_jobs);
00308 Duration.Init(sets,max_jobs);
00309 Deadline.Init(sets,max_jobs);
00310 Durations.Init(max_jobs, max_machines);
00311 MachineIndex.Init(max_jobs, max_machines);
00312 WeightT.Init(sets,max_jobs);
00313 WeightF.Init(sets,max_jobs);
00314 WeightE.Init(sets,max_jobs);
00315 WeightN.Init(sets,max_jobs);
00316 Fitness.Init(sets+1,FUNCTIONS);
00317 Values.Init(max_machines,max_jobs);
00318 Precedence.Reset(max_jobs,max_jobs);
00319 Setup.Init(max_jobs+1,max_jobs);
00320 if(m_Environment == JOBSHOP)
00321 { Schedule.Init(sets, max_machines*max_jobs);
00322 PTimeAvg.Reset(sets, max_machines);
00323 }
00324 else
00325 { Schedule.Init(sets,max_jobs);
00326 PTimeAvg.Init(sets,max_jobs);
00327 PTimeMinMachine.Init(sets,max_jobs);
00328 }
00329 SortedReady.Init(sets,max_jobs);
00330
00331 pVrijednosti = new double[max_jobs];
00332 pRasporedjen = new bool[max_jobs];
00333 pIndex = new unsigned int[max_jobs];
00334 pUsed = new unsigned int[max_jobs];
00335 pArray = new double[max_jobs];
00336 pSlack = new double[max_jobs];
00337 pSlackSpeed = new double[max_jobs];
00338 pArrival = new double[max_jobs];
00339 pLevel = new double[max_jobs];
00340 pSetupAvg = new double[max_jobs + 1];
00341 pSamples = new bool[sets];
00342 pLastJob = new unsigned int[max_machines];
00343 pMachineScheduled = new unsigned int[max_machines];
00344 pOperationReady = new double[max_machines];
00345 pJobReady = new double[max_jobs];
00346 pOperationsScheduled = new unsigned int[max_jobs];
00347 pTotalWorkRemaining = new double[max_jobs];
00348 pTotalWorkDone = new double[max_jobs];
00349 pTotalMachineWork = new double[max_machines];
00350 pOperationsWaiting = new unsigned int[max_machines];
00351 pMachineWorkRemaining = new double[max_machines];
00352 pMachineValues = new double[max_machines];
00353 p.ReadParameter("jobs",ReadPar::DOUBLE,&d_niz[0][0],sets);
00354 p.ReadParameter("machines",ReadPar::DOUBLE,&d_niz[1][0],sets);
00355 total_jobs = 0;
00356 for(i=0; i<sets; i++)
00357 { N[i][0] = d_niz[0][i];
00358 total_jobs += (int) d_niz[0][i];
00359 Machines[i][0] = d_niz[1][i];
00360 }
00361 Duration.Load(duration.c_str());
00362 Deadline.Load(deadline.c_str());
00363 if(m_Environment==UNIFORM)
00364 { Speed.Load(speed.c_str());
00365 }
00366 WeightT.Load(weightT.c_str());
00367 WeightF.Load(weightF.c_str());
00368 WeightE.Load(weightE.c_str());
00369 WeightN.Load(weightN.c_str());
00370 SP.Load(sp.c_str());
00371 if(m_dynamic) Ready.Load(ready.c_str());
00372 else Ready.Reset(sets,max_jobs);
00373 if(m_constrained) Constraints.Load(cons.c_str());
00374
00375 Level.Init(sets,max_jobs);
00376 for(i=0; i<sets; i++)
00377 { SD.Set(i,0);
00378 for(j=0; j<(unsigned int)N.Get(i); j++)
00379 { SD.data[i][0] += Deadline.data[i][j];
00380 Level[i][j] = -1;
00381 }
00382 }
00383
00384 for(i=0; i<sets; i++)
00385 { if(m_constrained)
00386 ReadConstraints(Constraints,i,(unsigned int)N.Get(i),Precedence);
00387 for(j=0; j<(unsigned int)N.Get(i); j++)
00388 Level[i][j] = NodeLevel(i,j);
00389 }
00390
00391 if(m_Environment == UNRELATED)
00392 { for(uint set=0; set<sets; set++)
00393 { uint jobs = (uint) N[set][0];
00394 uint machines = (uint) Machines[set][0];
00395 for(j=0; j<jobs; j++)
00396 { PTimeAvg[set][j] = 0;
00397 uint min_machine = 0;
00398 for(uint machine=0; machine<machines; machine++)
00399 { PTimeAvg[set][j] += Duration[set][j*machines + machine];
00400 if(Duration[set][j*machines + machine] < Duration[set][j*machines + min_machine])
00401 min_machine = machine;
00402 }
00403 PTimeAvg[set][j] /= machines;
00404 PTimeMinMachine[set][j] = min_machine;
00405 }
00406 }
00407 }
00408 if(m_Environment == JOBSHOP)
00409 { for(uint set=0; set<sets; set++)
00410 { uint jobs = (uint) N[set][0];
00411 uint machines = (uint) Machines[set][0];
00412 for(j=0; j<jobs; j++)
00413 { uint operations = machines;
00414 for(uint op=0; op<operations; op++)
00415 { double dur = Duration[set][j*operations + op];
00416 uint machine = (uint) dur / 1000;
00417 dur = (int)dur % 1000;
00418 PTimeAvg[set][machine] += dur;
00419 }
00420 }
00421 for(uint m=0; m<machines; m++)
00422 PTimeAvg[set][m] /= jobs;
00423 }
00424 }
00425
00426
00427 for(i=0; i<sets; i++)
00428 { ::pVal = Ready[i];
00429 uint jobs = (uint) N[i][0];
00430 for(j=0; j<jobs; j++)
00431 pIndex[j] = j;
00432 qsort(pIndex,jobs,sizeof(unsigned int),::Before);
00433 for(j=0; j<jobs; j++)
00434 SortedReady[i][j] = pIndex[j];
00435 }
00436
00437 p.CloseFile();
00438
00439 return true;
00440 }
00441
00442
00443
00444
00445 void SchedulingEvalOp::DefineNodeNames(void)
00446 {
00447 }
00448
00449
00450
00451
00452
00453 void SchedulingEvalOp::ReadTerminals(TreeP tree)
00454 {
00455 int i,dummy;
00456 ReadPar p;
00457 std::string term;
00458 p.OpenFile(in_file.c_str());
00459
00460
00461 for(i = OFFSET; i < TERMINALS + OFFSET; i++)
00462 { term = "T_" + Nodes[i].name;
00463 if(p.ReadParameter(term.c_str(),ReadPar::INTEGER,&dummy))
00464 { Nodes[i].active = true;
00465
00466
00467 Tree::PrimitiveP newTerm = (Tree::PrimitiveP) new Tree::Primitives::Terminal;
00468 newTerm->setName(Nodes[i].name);
00469 tree->addTerminal(newTerm);
00470 }
00471 }
00472 p.CloseFile();
00473 }
00474
00475
00476
00477
00478 void SchedulingEvalOp::ReadTerminals(StateP state)
00479 {
00480 int i;
00481 std::string term;
00482
00483 GenotypeP gen = (GenotypeP) (state->getGenotypes()[0]);
00484 TreeP tree = boost::dynamic_pointer_cast<Tree::Tree> (gen);
00485 voidP val = tree->getParameterValue(state, "terminalset");
00486 std::string terminals = *((std::string*) val.get());
00487 terminals = " " + terminals + " ";
00488
00489
00490 for(i = OFFSET; i < TERMINALS + OFFSET; i++)
00491 { if(terminals.find(" " + Nodes[i].name + " ") != string::npos)
00492 { Nodes[i].active = true;
00493 }
00494 }
00495 }
00496
00497
00498
00499
00500
00501 vector<IndividualP> jedinke;
00502
00503 bool provjeriDuplikate(IndividualP individual, StateP state_)
00504 {
00505 static uint gen = 0;
00506 static uint jednakih = 0;
00507
00508 bool jednaka = false;
00509
00510
00511 if(state_->getGenerationNo() != gen) {
00512 gen = state_->getGenerationNo();
00513
00514 ECF_LOG(state_, 1, "jednakih: " + uint2str(jednakih) + ", " + uint2str(100*jednakih/jedinke.size()));
00515
00516 jedinke.clear();
00517 jednakih = 0;
00518 }
00519
00520
00521 uint broj = (uint) jedinke.size();
00522 Tree::Tree* nova = (Tree::Tree*) individual->getGenotype().get();
00523 for(uint i = 0; i < broj; i++) {
00524 Tree::Tree* stara = (Tree::Tree*) jedinke[i]->getGenotype().get();
00525 if(nova->size() != stara->size())
00526 continue;
00527 uint n, size = (uint) nova->size();
00528 Tree::NodeP cvor1, cvor2;
00529 for(n = 0; n < size; n++) {
00530 cvor1 = (*nova)[n];
00531 cvor2 = (*stara)[n];
00532 if(cvor1->primitive_ != cvor2->primitive_)
00533 break;
00534 }
00535
00536 if(n == size) {
00537 jednakih++;
00538 individual->fitness = (FitnessP) jedinke[i]->fitness->copy();
00539 jednaka = true;
00540 break;
00541 }
00542 }
00543
00544 return jednaka;
00545 }
00546
00547
00548
00549 FitnessP SchedulingEvalOp::evaluate(IndividualP individual)
00550 {
00551
00552
00553
00554
00555
00556
00557
00558
00559
00560
00561
00562
00563
00564
00565
00566 FitnessP fitness = static_cast<FitnessP> (new FitnessMin);
00567
00568 if(m_genotip == 0) {
00569
00570 FloatingPointP fp = boost::dynamic_pointer_cast<FloatingPoint::FloatingPoint> (individual->getGenotype());
00571 double dFitness;
00572
00573 EvaluateUnrelatedFP(fp, dFitness);
00574
00575 fitness->setValue(dFitness);
00576
00577 return fitness;
00578 }
00579
00580
00581
00582 TreeP tree = boost::dynamic_pointer_cast<Tree::Tree> (individual->getGenotype());
00583
00584
00585 unsigned int i;
00586 double dRawFitness, dFitness;
00587 ReadIndividual(individual);
00588
00589
00590 if(m_stsampling)
00591 { int koliko = (int) (m_sampling*sets);
00592 int razmak = sets / koliko;
00593 int pocetni = rand()%razmak;
00594 for(i=0; i<sets; i++)
00595 pSamples[i] = false;
00596 for(i=pocetni; i<sets; i+=razmak)
00597 pSamples[i] = true;
00598 }
00599
00600 switch(m_Environment)
00601 { case SINGLE:
00602 EvaluateSingle(dRawFitness);
00603 break;
00604 case UNIFORM:
00605 EvaluateUniform(dRawFitness);
00606 break;
00607 case UNRELATED:
00608 EvaluateUnrelated(dRawFitness);
00609 break;
00610 case JOBSHOP:
00611 EvaluateJobShop(dRawFitness);
00612 break;
00613 }
00614
00615
00616
00617
00618 dFitness = dRawFitness;
00619
00620 if(m_Evaluation)
00621 { Fitness.Save("rezultat_GP.txt");
00622 std::ostream *file = new std::ofstream("rezultat_GP.txt", std::ios_base::app);
00623 Evaluator.write();
00624 *file << std::endl << "-- infix: " << Evaluator.m_output << " --" << std::endl;
00625 *file << "Editirano: " << edited << ", ukupno: " << total << std::endl;
00626 *file << std::flush;
00627 delete file;
00628 Schedule.Save("raspored_GP.txt");
00629 }
00630
00631
00632
00633
00634
00635 fitness->setValue(dFitness);
00636
00637
00638 individual->fitness = fitness;
00639 jedinke.push_back((IndividualP) individual->copy());
00640
00641 return fitness;
00642 }
00643
00644
00645 void SchedulingEvalOp::write(std::string &output)
00646 {
00647 }
00648
00649
00650
00651 void SchedulingEvalOp::ReadConstraints(Matrica &Constraints, int set, int jobs, Matrica &Precedence)
00652 {
00653 int i,j,prethodnika,prethodnik,pom;
00654 unsigned int podatak;
00655
00656
00657 for(i=0; i<jobs; i++)
00658 for(j=0; j<2; j++)
00659 Precedence[i][j] = 0;
00660 for(i=0; i<jobs; i++)
00661 { podatak = (unsigned int) Constraints[set][i];
00662 prethodnik = 1;
00663 prethodnika = 0;
00664 while(podatak != 0)
00665 { if(podatak%2 != 0)
00666 { prethodnika++;
00667 pom = (int) Precedence[i-prethodnik][1] + 1;
00668 Precedence[i-prethodnik][pom+1] = i;
00669 Precedence[i-prethodnik][1] = pom;
00670 }
00671 prethodnik++;
00672 podatak /= 2;
00673 }
00674 Precedence[i][0] = prethodnika;
00675 }
00676 }
00677
00678
00679
00680
00681 void SchedulingEvalOp::MakeSetup(Matrica &Duration, int set, int jobs, double faktor, Matrica &Setup)
00682 {
00683 int i,j;
00684 pSetupAvg[jobs] = 0;
00685 if(m_Environment == JOBSHOP)
00686 { srand(set);
00687 for(i=0; i<jobs; i++)
00688 { Setup[jobs][i] = (int) ((rand()%max_length+1) * faktor);
00689 pSetupAvg[jobs] += Setup[jobs][i];
00690 for(j=0; j<=i; j++)
00691 { Setup[i][j] = (int) ((rand()%max_length+1) * faktor);
00692 Setup[j][i] = (int) ((rand()%max_length+1) * faktor);
00693 pSetupAvg[i] += Setup[i][j];
00694 pSetupAvg[j] += Setup[j][i];
00695 }
00696 }
00697 }
00698 else
00699 for(i=0; i<jobs; i++)
00700 { pSetupAvg[i] = 0;
00701 Setup[jobs][i] = Duration[set][(i+1) % jobs];
00702 pSetupAvg[jobs] += Setup[jobs][i];
00703 for(j=0; j<=i; j++)
00704 { Setup[i][j] = ceil( fabs( Duration[set][i] - Duration[set][j] ) * faktor);
00705 Setup[j][i] = ceil( fabs( Duration[set][(i+1) % jobs] - Duration[set][(j+1) % jobs] ) * faktor);
00706 pSetupAvg[i] += Setup[i][j];
00707 pSetupAvg[j] += Setup[j][i];
00708 }
00709 }
00710 pSetupAvg[jobs] /= jobs;
00711 for(i=0; i<jobs; i++)
00712 pSetupAvg[i] /= (jobs-1);
00713 }
00714
00715
00716
00717 void SchedulingEvalOp::ReadIndividual(IndividualP individual)
00718 {
00719 TreeP tree = boost::dynamic_pointer_cast<Tree::Tree> (individual->getGenotype());
00720 static std::string strTerminal;
00721 unsigned int nTreeSize,i,j,nTree;
00722 uint nTrees = (uint) individual->size();
00723 for(nTree = 0; nTree<nTrees; nTree++)
00724 { TreeP pTree = boost::dynamic_pointer_cast<Tree::Tree> (individual->getGenotype(nTree));
00725 nTreeSize = (uint) pTree->size();
00726 if(nTreeSize > Evaluator.m_iExprSize)
00727 Evaluator.SetExprSize(nTreeSize);
00728
00729
00730 for(i=0; i<nTreeSize; i++)
00731 {
00732 strTerminal = (*pTree)[i]->primitive_->getName();
00733 for(j=OFFSET; j<TOTAL_NODES; j++)
00734 { if(!Nodes[j].active)
00735 continue;
00736 if(strTerminal == Nodes[j].name)
00737 { Evaluator.m_pExpression[nTree][i] = j;
00738 break;
00739 }
00740 }
00741 assert(j<TOTAL_NODES);
00742 }
00743
00744 if(m_editing)
00745 { Evaluator.m_nTree = nTree;
00746 Evaluator.m_iPosition = Evaluator.m_iEditedPos = -1;
00747 Evaluator.edit();
00748 Evaluator.copy();
00749 total += Evaluator.m_iPosition;
00750 edited += Evaluator.m_iPosition - Evaluator.m_iEditedPos;
00751 }
00752 }
00753
00754 }
00755
00756
00757
00758
00759
00760 double SchedulingEvalOp::NodeLevel(int set, int node)
00761 { double value,level;
00762 int succ,i,next;
00763 if(Level[set][node] > -1)
00764 return Level[set][node];
00765 if(Precedence[node][1] == 0)
00766 return Duration[set][node];
00767 succ = (int)Precedence[node][1];
00768 next = (int)Precedence[node][2];
00769 level = NodeLevel(set,next) + Duration[set][node];
00770 for(i=1; i<succ; i++)
00771 { next = (int)Precedence[node][i+2];
00772 value = NodeLevel(set,next) + Duration[set][node];
00773 if(value > level)
00774 level = value;
00775 }
00776 return level;
00777 }
00778
00779
00780
00781 void SchedulingEvalOp::CalcTimedTerminals(uint &nNiz, uint &nPoslova, uint &nJob, double &dClock, \
00782 uint nMachine, uint nMachines)
00783 { uint i,j;
00784 for(i=nJob; i<nPoslova; i++)
00785 { j = pIndex[i];
00786 if(m_Environment == UNIFORM)
00787 { Evaluator.m_dTermValuesArray[T_SPD][j] = Speed[nNiz][nMachine];
00788 pSlack[j] = Deadline[nNiz][j] - (dClock + Duration[nNiz][j]);
00789 pSlackSpeed[j] = Deadline[nNiz][j] - (dClock + Duration[nNiz][j] * Speed[nNiz][nMachine]);
00790 Evaluator.m_dTermValuesArray[T_L][j] = POS(dClock + Duration[nNiz][j]*Speed[nNiz][nMachine]- Deadline[nNiz][j]);
00791 }
00792 if(m_Environment == UNRELATED)
00793 { Evaluator.m_dTermValuesArray[T_PAT][j] = POS(MachineReady[(uint)PTimeMinMachine[nNiz][j]][0] - dClock);
00794 Evaluator.m_dTermValuesArray[T_MR][j] = POS(MachineReady[nMachine][0] - dClock);
00795 Evaluator.m_dTermValuesArray[T_pt][j] = Duration[nNiz][j*nMachines + nMachine];
00796 Evaluator.m_dTermValuesArray[T_age][j] = POS(dClock - Ready[nNiz][j]);
00797 pSlack[j] = Deadline[nNiz][j] - (dClock + Duration[nNiz][j*nMachines + nMachine]);
00798 Evaluator.m_dTermValuesArray[T_L][j] = POS(dClock + Duration[nNiz][j*nMachines + nMachine]- Deadline[nNiz][j]);
00799 }
00800 if(m_Environment == SINGLE)
00801 { pSlack[j] = Deadline[nNiz][j] - (dClock + Duration[nNiz][j]);
00802 Evaluator.m_dTermValuesArray[T_L][j] = POS(dClock + Duration[nNiz][j]- Deadline[nNiz][j]);
00803
00804 }
00805
00806
00807 Evaluator.m_dTermValuesArray[T_CLK][j] = dClock;
00808 pArrival[j] = POS(Ready[nNiz][j] - dClock);
00809 Evaluator.m_dTermValuesArray[T_AR][j] = pArrival[j];
00810 if(pSlack[j]<0) pSlack[j] = 0;
00811 if(pSlackSpeed[j]<0) pSlackSpeed[j] = 0;
00812
00813 Evaluator.m_dTermValuesArray[T_SL][j] = pSlack[j];
00814 Evaluator.m_dTermValuesArray[T_SLs][j] = pSlackSpeed[j];
00815
00816 if(m_Environment != SINGLE)
00817 {
00818 Evaluator.m_dTermValuesArray[T_STP][j] = Setup[pLastJob[nMachine]][j];
00819 Evaluator.m_dTermValuesArray[T_Sav][j] = pSetupAvg[pLastJob[nMachine]];
00820 }
00821 }
00822 }
00823
00824
00825
00826 void SchedulingEvalOp::EvaluateSingle(double &dRawFitness)
00827 {
00828 double dClock, dRez, dSetFitness, dAvgWeights, dAvgDuration, dAvgDueDate;
00829 double dLateness, dTotalLateness=0, dTardiness, dTotalTardiness=0;
00830 double dNwt, dTotalNwt=0, dBest, dSPr, dSDr;
00831 unsigned int nPoslova,nNiz,nJob,i,j,k,index,nLateJobs,nTotalLateJobs=0,nNr;
00832 unsigned int nLastJob,nOdabrani;
00833
00834 dRawFitness=0;
00835
00836
00837 for(nNiz=0; nNiz<sets; nNiz++)
00838 { nNr = nPoslova = (int) N.Get(nNiz);
00839
00840
00841 if(m_stsampling)
00842 if(pSamples[nNiz] == false)
00843 continue;
00844
00845 if(m_LEF)
00846 { if(dRawFitness > m_LEFVal)
00847 break;
00848 }
00849 if(m_constrained)
00850 ReadConstraints(Constraints,nNiz,nPoslova,Precedence);
00851 if(m_setup)
00852 MakeSetup(Duration,nNiz,nPoslova,m_setup_faktor,Setup);
00853
00854 nLateJobs = 0;
00855 dLateness = 0;
00856 dTardiness = 0;
00857 dNwt = 0;
00858 dClock = 0; dSetFitness = 0;
00859 nLastJob = nPoslova;
00860 dAvgDueDate = 0;
00861 for(i=0; i<nPoslova; i++)
00862 { dAvgDueDate += Deadline[nNiz][i];
00863 pRasporedjen[i] = false;
00864 pIndex[i] = i;
00865 }
00866 dAvgDueDate /= nPoslova;
00867
00868 Evaluator.m_pTermValues[T_N] = N.Get(nNiz);
00869 dSPr = Evaluator.m_pTermValues[T_SP] = SP.Get(nNiz);
00870 dSDr = Evaluator.m_pTermValues[T_SD] = SD.Get(nNiz);
00871 Evaluator.SetTermArraySize(nPoslova);
00872 Evaluator.pIndex = pIndex;
00873 Evaluator.m_iOffset = 0;
00874 for(i=0; i<nPoslova; i++)
00875 { Evaluator.m_dTermValuesArray[T_N][i] = N.data[nNiz][0];
00876 Evaluator.m_dTermValuesArray[T_SP][i] = SP.data[nNiz][0];
00877 Evaluator.m_dTermValuesArray[T_SD][i] = SD.data[nNiz][0];
00878 Evaluator.m_dTermValuesArray[T_SC][i] = Precedence[i][1];
00879 Evaluator.m_dTermValuesArray[T_TF][i] = 1 - dAvgDueDate / SP[nNiz][0];
00880 }
00881 memcpy(Evaluator.m_dTermValuesArray[T_pt], Duration.data[nNiz], nPoslova*sizeof(double));
00882 memcpy(Evaluator.m_dTermValuesArray[T_dd], Deadline.data[nNiz], nPoslova*sizeof(double));
00883 memcpy(Evaluator.m_dTermValuesArray[T_w], WeightT.data[nNiz], nPoslova*sizeof(double));
00884 memcpy(Evaluator.m_dTermValuesArray[T_LVL], Level[nNiz], nPoslova*sizeof(double));
00885
00887
00888
00889 for(nJob=0; nJob<nPoslova; nJob++)
00890 { for(i=nJob; i<nPoslova; i++)
00891 { j = pIndex[i];
00892 Evaluator.m_dTermValuesArray[T_SPr][j] = dSPr;
00893 Evaluator.m_dTermValuesArray[T_Nr][j] = nNr;
00894 Evaluator.m_dTermValuesArray[T_STP][j] = Setup[nLastJob][j];
00895 Evaluator.m_dTermValuesArray[T_Sav][j] = pSetupAvg[nLastJob];
00896
00897 }
00898 Evaluator.m_iPosition = -1;
00899 Evaluator.m_iOffset = nJob;
00900
00901 if(m_dynamic)
00902 { unsigned int raspolozivi = nJob, prvi = nJob;
00903 unsigned int najkraci;
00904
00905 for(; Precedence[pIndex[raspolozivi]][0] > 0; raspolozivi++) NULL;
00906 double kada = Ready[nNiz][pIndex[raspolozivi]];
00907 double najdulje = 0, najkrace = 0;
00908 for( ; raspolozivi < nPoslova; raspolozivi++)
00909 { k = pIndex[raspolozivi];
00910 if(Ready.data[nNiz][k] < kada && Precedence[k][0] == 0)
00911 { kada = Ready.data[nNiz][k];
00912 prvi = raspolozivi;
00913 }
00914 }
00915 if(kada > dClock)
00916 { dClock = kada;
00917 }
00918
00919 CalcTimedTerminals(nNiz,nPoslova,nJob,dClock);
00920
00921 najdulje = najkrace = Duration[nNiz][pIndex[prvi]];
00922 najkraci = prvi;
00923 for(i=nJob; i<nPoslova; i++)
00924 { k = pIndex[i];
00925 if(dClock < Ready[nNiz][k] || Precedence[k][0] > 0)
00926 continue;
00927 if(Duration[nNiz][k] < najkrace)
00928 { najkrace = Duration[nNiz][k];
00929 najkraci = i;
00930 }
00931 }
00932
00933 for(i=nJob; i<nPoslova; i++)
00934 { k = pIndex[i];
00935 if(Precedence[k][0] > 0)
00936 continue;
00937 if(Duration[nNiz][k] > najdulje && Ready[nNiz][k] <= (dClock+najkrace))
00938 najdulje = Duration[nNiz][k];
00939 }
00940
00941
00942 Evaluator.evaluate_array(pVrijednosti);
00943
00944
00945
00946
00947
00948
00949 kada = najkrace + najdulje;
00950 dBest = pVrijednosti[pIndex[najkraci]];
00951 nOdabrani = najkraci;
00952 for(i=nJob; i<nPoslova; i++)
00953 { k = pIndex[i];
00954 if(Precedence[k][0] == 0 && (pVrijednosti[k] < dBest) && (Ready[nNiz][k] < dClock + kada))
00955 { dBest = pVrijednosti[k];
00956 nOdabrani = i;
00957 }
00958 }
00959 kada = Ready[nNiz][pIndex[nOdabrani]] - dClock;
00960 if(kada >= najkrace)
00961 { dBest = pVrijednosti[pIndex[najkraci]];
00962 nOdabrani = najkraci;
00963 for(i=nJob; i<nPoslova; i++)
00964 { k = pIndex[i];
00965 if(Precedence[k][0] == 0 && (Ready[nNiz][k] + Duration[nNiz][k] <= dClock + kada) \
00966 && pVrijednosti[k] < dBest \
00967 && Ready[nNiz][k] - dClock < najkrace)
00968 { dBest = pVrijednosti[k];
00969 nOdabrani = i;
00970 }
00971 }
00972 kada = Ready[nNiz][pIndex[nOdabrani]] - dClock;
00973 }
00974
00975
00976
00977
00978
00979
00980
00981
00982
00983
00984
00985
00986
00987
00988
00989 if(kada > 0)
00990 dClock += kada;
00991 }
00992
00993 else
00994 { CalcTimedTerminals(nNiz,nPoslova,nJob,dClock);
00995 nOdabrani = nJob;
00996 if(m_constrained)
00997 for(; Precedence[pIndex[nOdabrani]][0] > 0; nOdabrani++) NULL;
00998 Evaluator.evaluate_array(pVrijednosti);
00999 dBest = pVrijednosti[pIndex[nOdabrani]];
01000 for(i=nJob; i<nPoslova; i++)
01001 {
01002 if(pVrijednosti[pIndex[i]] < dBest && Precedence[pIndex[i]][0] == 0)
01003 { dBest = pVrijednosti[pIndex[i]];
01004 nOdabrani = i;
01005 }
01006 }
01007 }
01008
01009
01010
01011 i = pIndex[nJob];
01012 pIndex[nJob] = pIndex[nOdabrani];
01013 pIndex[nOdabrani] = i;
01014 pRasporedjen[pIndex[nJob]] = true;
01015 dClock += Duration[nNiz][pIndex[nJob]];
01016 dSPr -= Duration[nNiz][pIndex[nJob]];
01017 dSDr -= Deadline[nNiz][pIndex[nJob]];
01018 nNr--;
01019 if(m_constrained)
01020 for(i=0; i<Precedence[pIndex[nJob]][1]; i++)
01021 { j = (int) Precedence[pIndex[nJob]][i+2];
01022 Precedence[j][0] -= 1;
01023 }
01024 if(m_setup)
01025 { dClock += Setup[nLastJob][pIndex[nJob]];
01026 nLastJob = pIndex[nJob];
01027 }
01028 Schedule[nNiz][nJob] = pIndex[nJob];
01029 }
01030
01031
01032 { if(m_Evaluation)
01033 { for(nJob=nPoslova ; nJob < this->max_jobs; nJob++)
01034 Schedule[nNiz][nJob] = 0;
01035 }
01036
01037 dClock = 0; nLastJob = nPoslova; dAvgWeights = dAvgDuration = 0;
01038 for(nJob = 0; nJob<nPoslova; nJob++)
01039 { index = pIndex[nJob];
01040 dAvgWeights += WeightT[nNiz][index];
01041 dAvgDuration += Duration[nNiz][index];
01042 if(m_dynamic && dClock < Ready[nNiz][index])
01043 dClock = Ready[nNiz][index];
01044 if(m_setup)
01045 dClock += Setup[nLastJob][index];
01046 nLastJob = index;
01047 dClock += Duration.data[nNiz][index];
01048 dRez = dClock - Deadline.Get(nNiz,index);
01049 dLateness += dRez*WeightT.data[nNiz][index];
01050 if(dRez > 0) dTardiness += dRez*WeightT.data[nNiz][index];
01051 if(dRez > 0) nLateJobs ++;
01052 if(dRez > 0) dNwt += WeightN.data[nNiz][index];
01053 }
01054
01055
01056 dAvgWeights /= nPoslova;
01057 dAvgDuration /= nPoslova;
01058 dTardiness /= (nPoslova * dAvgWeights * dAvgDuration);
01059 dNwt /= (nPoslova * dAvgWeights);
01060 double Cmax = dClock / (nPoslova * dAvgDuration);
01061 switch(m_fitness)
01062 { case Twt: dRawFitness += dTardiness; break;
01063 case Nwt: dRawFitness += dNwt; break;
01064 case TwtCmax: dRawFitness += dTardiness * Cmax; break;
01065 case NwtCmax: dRawFitness += dNwt * Cmax; break;
01066 default: exit(1);
01067 }
01068 nTotalLateJobs += nLateJobs;
01069 dTotalNwt += dNwt;
01070 dTotalLateness += dLateness;
01071 dTotalTardiness += dTardiness;
01072 Fitness[nNiz][Twt] = dTardiness;
01073 Fitness[nNiz][Nwt] = dNwt;
01074 Fitness[nNiz][FTwt] = 0;
01075 Fitness[nNiz][ETwt] = 0;
01076 }
01077 }
01078
01079 Fitness.data[sets][Twt] = dTotalTardiness;
01080 Fitness.data[sets][Nwt] = dTotalNwt;
01081 }
01082
01083
01084
01085
01086
01087 void SchedulingEvalOp::EvaluateUniform(double &dRawFitness)
01088 {
01089 double dClock, dRez, dSetFitness, dAvgWeights, dAvgDuration;
01090 double dLateness, dTotalLateness=0, dTardiness, dTotalTardiness=0, dTotalFwt=0;
01091 double dNwt, dTotalNwt=0, dBest, dSPr, dMsum, dSetupTime, dFwt, dCmax, dTotalCmax=0;
01092 unsigned int nPoslova,nNiz,nJob,i,j,k,index,nLateJobs,nTotalLateJobs=0,nNr;
01093 unsigned int nLastJob,nMachines,nOdabrani,nMachine;
01094
01095 dRawFitness=0;
01096
01097
01098 for(nNiz=0; nNiz<sets; nNiz++)
01099 { nNr = nPoslova = (int) N.Get(nNiz);
01100
01101
01102 if(m_stsampling)
01103 if(pSamples[nNiz] == false)
01104 continue;
01105
01106 if(m_LEF)
01107 { if(dRawFitness > m_LEFVal)
01108 break;
01109 }
01110 if(m_constrained)
01111 ReadConstraints(Constraints,nNiz,nPoslova,Precedence);
01112 if(m_setup)
01113 MakeSetup(Duration,nNiz,nPoslova,m_setup_faktor,Setup);
01114
01115 nLateJobs = 0;
01116 dLateness = 0;
01117 dTardiness = 0;
01118 dNwt = 0;
01119 dFwt = 0;
01120 dClock = 0; dSetFitness = 0;
01121 nLastJob = nPoslova;
01122 for(i=0; i<nPoslova; i++)
01123 { pRasporedjen[i] = false;
01124 pIndex[i] = i;
01125 }
01126 nMachines = (uint) Machines[nNiz][0];
01127 dMsum = 0;
01128 for(j=0; j<nMachines; j++)
01129 { MachineReady[j][0] = 0;
01130 dMsum += 1/Speed[nNiz][j];
01131 pLastJob[j] = nPoslova;
01132 }
01133
01134 Evaluator.m_pTermValues[T_N] = N.Get(nNiz);
01135 dSPr = Evaluator.m_pTermValues[T_SP] = SP.Get(nNiz);
01136 Evaluator.m_pTermValues[T_SD] = SD.Get(nNiz);
01137 Evaluator.SetTermArraySize(nPoslova);
01138 Evaluator.pIndex = pIndex;
01139 Evaluator.m_iOffset = 0;
01140 for(i=0; i<nPoslova; i++)
01141 { Evaluator.m_dTermValuesArray[T_N][i] = N.data[nNiz][0];
01142 Evaluator.m_dTermValuesArray[T_SP][i] = SP.data[nNiz][0];
01143 Evaluator.m_dTermValuesArray[T_SD][i] = SD.data[nNiz][0];
01144 Evaluator.m_dTermValuesArray[T_SC][i] = Precedence[i][1];
01145 }
01146 memcpy(Evaluator.m_dTermValuesArray[T_pt], Duration.data[nNiz], nPoslova*sizeof(double));
01147 memcpy(Evaluator.m_dTermValuesArray[T_dd], Deadline.data[nNiz], nPoslova*sizeof(double));
01148 memcpy(Evaluator.m_dTermValuesArray[T_w], WeightT.data[nNiz], nPoslova*sizeof(double));
01149 memcpy(Evaluator.m_dTermValuesArray[T_LVL], Level[nNiz], nPoslova*sizeof(double));
01150
01152
01153
01154 for(nJob=0; nJob<nPoslova; nJob++)
01155 { for(i=nJob; i<nPoslova; i++)
01156 { j = pIndex[i];
01157 Evaluator.m_dTermValuesArray[T_SPr][j] = dSPr;
01158 Evaluator.m_dTermValuesArray[T_Nr][j] = nNr;
01159 }
01160 Evaluator.m_iPosition = -1;
01161 Evaluator.m_iOffset = nJob;
01162
01163 if(m_dynamic)
01164 {
01165 unsigned int raspolozivi = nJob, prvi = nJob;
01166
01167 for(; Precedence[pIndex[raspolozivi]][0] > 0; raspolozivi++) NULL;
01168 double kada = Ready[nNiz][pIndex[raspolozivi]];
01169 for( ; raspolozivi < nPoslova; raspolozivi++)
01170 { k = pIndex[raspolozivi];
01171 if(Ready.data[nNiz][k] < kada && Precedence[k][0] == 0)
01172 { kada = Ready.data[nNiz][k];
01173 prvi = raspolozivi;
01174 }
01175 }
01176 nMachine = 0;
01177 for(i=0; i<nMachines; i++)
01178 if(MachineReady[i][0] < MachineReady[nMachine][0])
01179 nMachine = i;
01180
01181 if(kada < MachineReady[nMachine][0])
01182 kada = MachineReady[nMachine][0];
01183 if(kada > dClock)
01184 dClock = kada;
01185
01186 CalcTimedTerminals(nNiz,nPoslova,nJob,dClock,nMachine);
01187
01188 Evaluator.evaluate_array(pVrijednosti);
01189
01190 dBest = pVrijednosti[pIndex[prvi]];
01191 nOdabrani = prvi;
01192 for(i=nJob; i<nPoslova; i++)
01193 { if((pVrijednosti[pIndex[i]] < dBest) && Precedence[pIndex[i]][0] == 0 \
01194 && Ready[nNiz][pIndex[i]] <= dClock)
01195 { dBest = pVrijednosti[pIndex[i]];
01196 nOdabrani = i;
01197 }
01198 }
01199 }
01200 else
01201 {
01202 nMachine = 0;
01203 for(i=1; i<nMachines; i++)
01204 if(MachineReady[i][0] < MachineReady[nMachine][0])
01205 nMachine = i;
01206 dClock = MachineReady[nMachine][0];
01207 CalcTimedTerminals(nNiz,nPoslova,nJob,dClock,nMachine);
01208 nOdabrani = nJob;
01209 if(m_constrained)
01210 for(; Precedence[pIndex[nOdabrani]][0] > 0; nOdabrani++) NULL;
01211 Evaluator.evaluate_array(pVrijednosti);
01212 dBest = pVrijednosti[pIndex[nOdabrani]];
01213 for(i=nJob; i<nPoslova; i++)
01214 {
01215 if(pVrijednosti[pIndex[i]] < dBest && Precedence[pIndex[i]][0] == 0)
01216 { dBest = pVrijednosti[pIndex[i]];
01217 nOdabrani = i;
01218 }
01219 }
01220 }
01221
01222
01223
01224 i = pIndex[nJob];
01225 pIndex[nJob] = pIndex[nOdabrani];
01226 pIndex[nOdabrani] = i;
01227 pRasporedjen[pIndex[nJob]] = true;
01228
01229
01230 dSPr -= Duration.data[nNiz][pIndex[nJob]]*dMsum;
01231 nNr--;
01232 if(m_setup)
01233 { dSetupTime = Setup[pLastJob[nMachine]][pIndex[nJob]];
01234 pLastJob[nMachine] = pIndex[nJob];
01235 }
01236 else dSetupTime = 0;
01237 if(m_constrained)
01238 for(i=0; i<Precedence[pIndex[nJob]][1]; i++)
01239 { j = (int) Precedence[pIndex[nJob]][i+2];
01240 Precedence[j][0] -= 1;
01241 }
01242 MachineReady[nMachine][0] = dClock + dSetupTime + \
01243 Duration[nNiz][pIndex[nJob]] * Speed[nNiz][nMachine];
01244
01245 Schedule[nNiz][nJob] = pIndex[nJob] + nMachine * 1000;
01246 }
01247
01248 { if(m_Evaluation)
01249 { for(nJob=nPoslova ; nJob < this->max_jobs; nJob++)
01250 Schedule[nNiz][nJob] = 0;
01251 }
01252
01253 dClock = 0; nLastJob = nPoslova; dAvgWeights = 0;
01254 for(i=0; i<nMachines; i++)
01255 { MachineReady[i][0] = 0;
01256 pLastJob[i] = nPoslova;
01257 }
01258 for(nJob = 0; nJob<nPoslova; nJob++)
01259 { index = (int) Schedule[nNiz][nJob];
01260 nMachine = index / 1000;
01261 index = index % 1000;
01262 dAvgWeights += WeightT[nNiz][index];
01263 if(m_dynamic && MachineReady[nMachine][0] < Ready[nNiz][index])
01264 MachineReady[nMachine][0] = Ready[nNiz][index];
01265 MachineReady[nMachine][0] += Duration[nNiz][index] * Speed[nNiz][nMachine];
01266 if(m_setup)
01267 MachineReady[nMachine][0] += Setup[pLastJob[nMachine]][index];
01268 pLastJob[nMachine] = index;
01269 dRez = MachineReady[nMachine][0] - Deadline.Get(nNiz,index);
01270 dLateness += dRez*WeightT.data[nNiz][index];
01271 if(dRez > 0) dTardiness += dRez*WeightT.data[nNiz][index];
01272 if(dRez > 0) nLateJobs ++;
01273 if(dRez > 0) dNwt += WeightN.data[nNiz][index];
01274 dFwt = (MachineReady[nMachine][0] - Ready[nNiz][index]) * WeightT[nNiz][index];
01275 }
01276 dCmax = 0;
01277 for(i=0; i<nMachines; i++)
01278 if(MachineReady[i][0] > dCmax)
01279 dCmax = MachineReady[i][0];
01280
01281
01282 dAvgDuration = SP[nNiz][0] / nPoslova;
01283 dAvgWeights /= nPoslova;
01284 dTardiness /= (nPoslova * dAvgWeights * dAvgDuration);
01285 dNwt /= (nPoslova * dAvgWeights);
01286 dFwt /= (nPoslova * dAvgWeights * dAvgDuration);
01287 dCmax /= (nPoslova * dAvgDuration);
01288 switch(m_fitness)
01289 { case Twt: dRawFitness += dTardiness; break;
01290 case Nwt: dRawFitness += dNwt; break;
01291 case Fwt: dRawFitness += dFwt; break;
01292 case Cmax: dRawFitness += dCmax; break;
01293 default: throw;
01294 }
01295 nTotalLateJobs += nLateJobs;
01296 dTotalNwt += dNwt;
01297 dTotalFwt += dFwt;
01298 dTotalLateness += dLateness;
01299 dTotalTardiness += dTardiness;
01300 dTotalCmax += dCmax;
01301 Fitness[nNiz][Twt] = dTardiness;
01302 Fitness[nNiz][Nwt] = dNwt;
01303 Fitness[nNiz][FTwt] = 0;
01304 Fitness[nNiz][ETwt] = 0;
01305 Fitness[nNiz][Fwt] = dFwt;
01306 Fitness[nNiz][Cmax] = dCmax;
01307 }
01308
01309 }
01310 Fitness[sets][Twt] = dTotalTardiness;
01311 Fitness[sets][Nwt] = dTotalNwt;
01312 Fitness[sets][FTwt] = 0;
01313 Fitness[sets][ETwt] = 0;
01314 Fitness[sets][Fwt] = dTotalFwt;
01315 Fitness[sets][Cmax] = dTotalCmax;
01316 }
01317
01318
01319
01320
01321
01322
01323
01324 void SchedulingEvalOp::EvaluateUnrelated(double &dRawFitness)
01325 {
01326 double dClock, dRez, dSetFitness, dAvgWeights, dCmax, dTotalCmax=0;
01327 double dLateness, dTotalLateness=0, dTardiness, dTotalTardiness=0;
01328 double dNwt, dTotalNwt=0, dBest, dSPr, dSetupTime, dFwt, dTotalFwt=0;
01329 unsigned int nPoslova,nNiz,nJob,i,j,k,index,nLateJobs,nTotalLateJobs=0,nNr;
01330 unsigned int nLastJob,nMachines,nOdabrani,nMachine;
01331
01332 dRawFitness=0;
01333
01334
01335 for(nNiz=0; nNiz<sets; nNiz++)
01336 { nNr = nPoslova = (int) N.Get(nNiz);
01337
01338
01339 if(m_stsampling)
01340 if(pSamples[nNiz] == false)
01341 continue;
01342
01343 if(m_LEF)
01344 { if(dRawFitness > m_LEFVal)
01345 break;
01346 }
01347 if(m_constrained)
01348 ReadConstraints(Constraints,nNiz,nPoslova,Precedence);
01349 if(m_setup)
01350 MakeSetup(Duration,nNiz,nPoslova,m_setup_faktor,Setup);
01351
01352 nLateJobs = 0;
01353 dLateness = 0;
01354 dTardiness = 0;
01355 dNwt = 0;
01356 dFwt = 0;
01357 dClock = 0; dSetFitness = 0;
01358 nLastJob = nPoslova;
01359 for(i=0; i<nPoslova; i++)
01360 { pRasporedjen[i] = false;
01361
01362 pIndex[i] = (uint) SortedReady[nNiz][i];
01363 }
01364
01365 nMachines = (uint) Machines[nNiz][0];
01366 for(j=0; j<nMachines; j++)
01367 { MachineReady[j][0] = 0;
01368 pLastJob[j] = nPoslova;
01369 }
01370
01371
01372 dSPr = SP.Get(nNiz);
01373 Evaluator.SetTermArraySize(nPoslova);
01374 Evaluator.pIndex = pIndex;
01375 Evaluator.m_iOffset = 0;
01376 Evaluator.m_iEnd = 1;
01377 for(i=0; i<nPoslova; i++)
01378 { Evaluator.m_dTermValuesArray[T_N][i] = N.data[nNiz][0];
01379 Evaluator.m_dTermValuesArray[T_SP][i] = SP.data[nNiz][0];
01380 Evaluator.m_dTermValuesArray[T_SD][i] = SD.data[nNiz][0];
01381 Evaluator.m_dTermValuesArray[T_SC][i] = Precedence[i][1];
01382
01383 Evaluator.m_dTermValuesArray[T_pmin][i] = Duration[nNiz][i*nMachines + (uint)PTimeMinMachine[nNiz][i]];
01384 }
01385 memcpy(Evaluator.m_dTermValuesArray[T_dd], Deadline.data[nNiz], nPoslova*sizeof(double));
01386 memcpy(Evaluator.m_dTermValuesArray[T_w], WeightT.data[nNiz], nPoslova*sizeof(double));
01387 memcpy(Evaluator.m_dTermValuesArray[T_LVL], Level[nNiz], nPoslova*sizeof(double));
01388 memcpy(Evaluator.m_dTermValuesArray[T_pavg], PTimeAvg[nNiz], nPoslova*sizeof(double));
01389
01391
01392
01393 for(nJob=0; nJob<nPoslova; nJob++)
01394 { for(i=nJob; i<nPoslova; i++)
01395 { j = pIndex[i];
01396 Evaluator.m_dTermValuesArray[T_SPr][j] = dSPr;
01397 Evaluator.m_dTermValuesArray[T_Nr][j] = nNr;
01398 }
01399 Evaluator.m_iPosition = -1;
01400 Evaluator.m_iOffset = nJob;
01401
01402 if(m_dynamic)
01403
01404
01405
01406
01407
01408
01409
01410
01411
01412
01413 {
01414 unsigned int raspolozivi = nJob, prvi = nJob;
01415
01416 for(; Precedence[pIndex[raspolozivi]][0] > 0; raspolozivi++) NULL;
01417 double kada = Ready[nNiz][pIndex[raspolozivi]];
01418 for( ; raspolozivi < nPoslova; raspolozivi++)
01419 { k = pIndex[raspolozivi];
01420 if(Ready.data[nNiz][k] < kada && Precedence[k][0] == 0)
01421 { kada = Ready.data[nNiz][k];
01422 prvi = raspolozivi;
01423 }
01424 }
01425 nMachine = 0;
01426 for(i=0; i<nMachines; i++)
01427 if(MachineReady[i][0] < MachineReady[nMachine][0])
01428 nMachine = i;
01429
01430 if(kada < MachineReady[nMachine][0])
01431 kada = MachineReady[nMachine][0];
01432 dClock = kada;
01433
01434 for(i=Evaluator.m_iEnd; i<nPoslova && Ready[nNiz][pIndex[i]]<=dClock; i++) NULL;
01435 Evaluator.m_iEnd = i;
01436
01437
01438
01439 for(nMachine=0; nMachine<nMachines; nMachine++)
01440 {
01441
01442
01443 CalcTimedTerminals(nNiz,nPoslova,nJob,dClock,nMachine,nMachines);
01444 Evaluator.m_iPosition = -1;
01445 Evaluator.evaluate_array(pVrijednosti);
01446 memcpy(Values[nMachine],pVrijednosti,nPoslova*sizeof(double));
01447 }
01448 bool BestSet = false;
01449 uint nBestMachine, nBestJobMachine;
01450 for(i=nJob; i<nPoslova; i++)
01451 { if(Precedence[pIndex[i]][0] != 0 || Ready[nNiz][pIndex[i]] > dClock)
01452 continue;
01453
01454 nBestJobMachine = 0;
01455 for(nMachine=1; nMachine<nMachines; nMachine++)
01456 if(Values[nBestJobMachine][pIndex[i]] < Values[nMachine][pIndex[i]])
01457 nBestJobMachine = nMachine;
01458 if(MachineReady[nBestJobMachine][0] > dClock)
01459 continue;
01460 if(!BestSet)
01461 { nBestMachine = nBestJobMachine;
01462 dBest = Values[nBestMachine][pIndex[i]];
01463 nOdabrani = i;
01464 BestSet = true;
01465 }
01466 else
01467 { if(Values[nBestJobMachine][pIndex[i]] < dBest)
01468 { nBestMachine = nBestJobMachine;
01469 dBest = Values[nBestJobMachine][pIndex[i]];
01470 nOdabrani = i;
01471 }
01472 }
01473 }
01474
01475 if(!BestSet)
01476 { nJob--;
01477
01478
01479 for(i=0; i<nMachines && MachineReady[i][0] <= dClock; i++) NULL;
01480 nMachine = i;
01481 for( ; i<nMachines; i++)
01482 if(MachineReady[i][0] > dClock && MachineReady[i][0] < MachineReady[nMachine][0])
01483 nMachine = i;
01484
01485
01486 unsigned int raspolozivi = nJob, prvi = nJob;
01487
01488 for(; raspolozivi < nPoslova && (Precedence[pIndex[raspolozivi]][0] > 0 || Ready[nNiz][pIndex[raspolozivi]] <= dClock); raspolozivi++) NULL;
01489 double kada;
01490 if(raspolozivi < nPoslova)
01491 { kada = Ready[nNiz][pIndex[raspolozivi]];
01492 for( ; raspolozivi < nPoslova; raspolozivi++)
01493 { k = pIndex[raspolozivi];
01494 if(Ready[nNiz][k] < kada && Ready[nNiz][k] > dClock && Precedence[k][0] == 0)
01495 { kada = Ready[nNiz][k];
01496 prvi = raspolozivi;
01497 }
01498 }
01499 }
01500
01501
01502 dClock = MachineReady[nMachine][0];
01503 if(raspolozivi < nPoslova && kada < dClock)
01504 dClock = kada;
01505
01506
01507 for(i=0; i<nMachines; i++)
01508 if(MachineReady[i][0] < dClock)
01509 MachineReady[i][0] = dClock;
01510 continue;
01511 }
01512
01513 nMachine = nBestMachine;
01514 }
01515
01516 else
01517 {
01518 nMachine = 0;
01519 for(i=1; i<nMachines; i++)
01520 if(MachineReady[i][0] < MachineReady[nMachine][0])
01521 nMachine = i;
01522 dClock = MachineReady[nMachine][0];
01523 CalcTimedTerminals(nNiz,nPoslova,nJob,dClock,nMachine,nMachines);
01524 nOdabrani = nJob;
01525 if(m_constrained)
01526 for(; Precedence[pIndex[nOdabrani]][0] > 0; nOdabrani++) NULL;
01527 Evaluator.evaluate_array(pVrijednosti);
01528 dBest = pVrijednosti[pIndex[nOdabrani]];
01529 for(i=nJob; i<nPoslova; i++)
01530 {
01531 if(pVrijednosti[pIndex[i]] < dBest && Precedence[pIndex[i]][0] == 0)
01532 { dBest = pVrijednosti[pIndex[i]];
01533 nOdabrani = i;
01534 }
01535 }
01536 }
01537
01538
01539
01540 i = pIndex[nJob];
01541 pIndex[nJob] = pIndex[nOdabrani];
01542 pIndex[nOdabrani] = i;
01543 pRasporedjen[pIndex[nJob]] = true;
01544 nOdabrani = pIndex[nJob];
01545
01546
01547
01548 nNr--;
01549 if(m_setup)
01550 { dSetupTime = Setup[pLastJob[nMachine]][nOdabrani];
01551 pLastJob[nMachine] = nOdabrani;
01552 }
01553 else dSetupTime = 0;
01554 if(m_constrained)
01555 for(i=0; i<Precedence[nOdabrani][1]; i++)
01556 { j = (int) Precedence[nOdabrani][i+2];
01557 Precedence[j][0] -= 1;
01558 }
01559 MachineReady[nMachine][0] = dClock + dSetupTime + \
01560 Duration[nNiz][nOdabrani*nMachines + nMachine];
01561
01562 Schedule[nNiz][nJob] = nOdabrani + nMachine * 1000;
01563 }
01564
01565
01566 { if(m_Evaluation)
01567 { for(nJob=nPoslova ; nJob < this->max_jobs; nJob++)
01568 Schedule[nNiz][nJob] = 0;
01569 }
01570
01571 dClock = 0; nLastJob = nPoslova; dAvgWeights = 0; dCmax = 0;
01572 for(i=0; i<nMachines; i++)
01573 { MachineReady[i][0] = 0;
01574 pLastJob[i] = nPoslova;
01575 }
01576 for(nJob = 0; nJob<nPoslova; nJob++)
01577 { index = (int) Schedule[nNiz][nJob];
01578 nMachine = index / 1000;
01579 index = index % 1000;
01580 dAvgWeights += WeightT[nNiz][index];
01581 if(m_dynamic && MachineReady[nMachine][0] < Ready[nNiz][index])
01582 MachineReady[nMachine][0] = Ready[nNiz][index];
01583 MachineReady[nMachine][0] += Duration[nNiz][index*nMachines + nMachine];
01584 if(m_setup)
01585 MachineReady[nMachine][0] += Setup[pLastJob[nMachine]][index];
01586 pLastJob[nMachine] = index;
01587 dRez = MachineReady[nMachine][0] - Deadline.Get(nNiz,index);
01588 dLateness += dRez*WeightT.data[nNiz][index];
01589 if(dRez > 0) dTardiness += dRez*WeightT.data[nNiz][index];
01590 if(dRez > 0) nLateJobs ++;
01591 if(dRez > 0) dNwt += WeightN.data[nNiz][index];
01592 if(m_dynamic)
01593 dFwt += MachineReady[nMachine][0] - Ready[nNiz][index];
01594 else
01595 dFwt += MachineReady[nMachine][0];
01596 }
01597 for(i=0; i<nMachines; i++)
01598 if(MachineReady[i][0] > dCmax)
01599 dCmax = MachineReady[i][0];
01600
01601 dAvgWeights /= nPoslova;
01602
01603
01604
01605 double dAvgDuration = SP[nNiz][0] / nPoslova;
01606 dTardiness /= (nPoslova * dAvgWeights * dAvgDuration);
01607
01608 dNwt /= (nPoslova * dAvgWeights);
01609 dFwt /= nPoslova;
01610 dCmax /= nPoslova;
01611 switch(m_fitness)
01612 { case Twt: dRawFitness += dTardiness; break;
01613 case Nwt: dRawFitness += dNwt; break;
01614 case Fwt: dRawFitness += dFwt; break;
01615 case Cmax: dRawFitness += dCmax; break;
01616 default: CHECK(0);
01617 }
01618 nTotalLateJobs += nLateJobs;
01619 dTotalNwt += dNwt;
01620 dTotalFwt += dFwt;
01621 dTotalLateness += dLateness;
01622 dTotalTardiness += dTardiness;
01623 dTotalCmax += dCmax;
01624 Fitness[nNiz][Twt] = dTardiness;
01625 Fitness[nNiz][Nwt] = dNwt;
01626 Fitness[nNiz][FTwt] = 0;
01627 Fitness[nNiz][ETwt] = 0;
01628 Fitness[nNiz][Fwt] = dFwt;
01629 Fitness[nNiz][Cmax] = dCmax;
01630 }
01631
01632 }
01633 Fitness[sets][Twt] = dTotalTardiness;
01634 Fitness[sets][Nwt] = dTotalNwt;
01635 Fitness[sets][Fwt] = dTotalFwt;
01636 Fitness[sets][Cmax] = dTotalCmax;
01637 }
01638
01639
01640
01641
01642
01643
01644
01645 void SchedulingEvalOp::EvaluateUnrelatedFP(FloatingPointP fp, double &dRawFitness)
01646 {
01647 double dClock, dRez, dSetFitness, dAvgWeights, dCmax, dTotalCmax=0;
01648 double dLateness, dTotalLateness=0, dTardiness, dTotalTardiness=0;
01649 double dNwt, dTotalNwt=0, dBest, dSPr, dSetupTime, dFwt, dTotalFwt=0;
01650 unsigned int nPoslova,nNiz,nJob,i,j,k,index,nLateJobs,nTotalLateJobs=0,nNr;
01651 unsigned int nLastJob,nMachines,nOdabrani,nMachine;
01652
01653 dRawFitness = 0;
01654
01655
01656
01657
01658 nNiz = m_primjer;
01659 {
01660
01661 nNr = nPoslova = (int) N.Get(nNiz);
01662
01663 if(m_constrained)
01664 ReadConstraints(Constraints,nNiz,nPoslova,Precedence);
01665 if(m_setup)
01666 MakeSetup(Duration,nNiz,nPoslova,m_setup_faktor,Setup);
01667
01668
01669 nLateJobs = 0;
01670 dLateness = 0;
01671 dTardiness = 0;
01672 dNwt = 0;
01673 dFwt = 0;
01674 dClock = 0; dSetFitness = 0;
01675 nLastJob = nPoslova;
01676 for(i=0; i<nPoslova; i++)
01677 { pRasporedjen[i] = false;
01678
01679 pIndex[i] = (uint) SortedReady[nNiz][i];
01680 }
01681 nMachines = (uint) Machines[nNiz][0];
01682
01683
01684 nJob = 0;
01685
01686
01687 std::vector<double> machineBounds;
01688 machineBounds.resize(nMachines + 1);
01689 for(uint m = 0; m <= nMachines; m++)
01690 machineBounds[m] = (m) * 1. / nMachines;
01691
01692 std::vector<double> jobValues(nPoslova);
01693 std::vector<uint> jobIndexes(nPoslova);
01694
01695
01696 for(uint m = 0; m < nMachines; m++) {
01697 uint nJobs = 0;
01698
01699
01700 for(uint job = 0; job < nPoslova; job++)
01701 if(fp->realValue[job] >= machineBounds[m] && fp->realValue[job] < machineBounds[m + 1]) {
01702 jobValues[nJobs] = fp->realValue[job];
01703 jobIndexes[nJobs] = job;
01704 nJobs++;
01705 }
01706
01707
01708 if(nJobs == 0)
01709 continue;
01710
01711
01712 double pd;
01713 uint pi;
01714 for(uint i = 0; i < nJobs - 1; i++)
01715 for(uint j = i + 1; j < nJobs; j++)
01716 if(jobValues[i] > jobValues[j]) {
01717 pd = jobValues[i];
01718 jobValues[i] = jobValues[j];
01719 jobValues[j] = pd;
01720 pi = jobIndexes[i];
01721 jobIndexes[i] = jobIndexes[j];
01722 jobIndexes[j] = pi;
01723 }
01724
01725
01726 for(uint job = 0; job < nJobs; job++) {
01727 Schedule[nNiz][nJob] = jobIndexes[job] + m * 1000;
01728 nJob++;
01729 }
01730
01731 }
01732
01733
01734
01735
01736
01737
01738
01739 { if(m_Evaluation)
01740 { for(nJob=nPoslova ; nJob < this->max_jobs; nJob++)
01741 Schedule[nNiz][nJob] = 0;
01742 }
01743
01744 dClock = 0; nLastJob = nPoslova; dAvgWeights = 0; dCmax = 0;
01745 for(i=0; i<nMachines; i++)
01746 { MachineReady[i][0] = 0;
01747 pLastJob[i] = nPoslova;
01748 }
01749 for(nJob = 0; nJob<nPoslova; nJob++)
01750 { index = (int) Schedule[nNiz][nJob];
01751 nMachine = index / 1000;
01752 index = index % 1000;
01753 dAvgWeights += WeightT[nNiz][index];
01754 if(m_dynamic && MachineReady[nMachine][0] < Ready[nNiz][index])
01755 MachineReady[nMachine][0] = Ready[nNiz][index];
01756 MachineReady[nMachine][0] += Duration[nNiz][index*nMachines + nMachine];
01757 if(m_setup)
01758 MachineReady[nMachine][0] += Setup[pLastJob[nMachine]][index];
01759 pLastJob[nMachine] = index;
01760 dRez = MachineReady[nMachine][0] - Deadline.Get(nNiz,index);
01761 dLateness += dRez*WeightT.data[nNiz][index];
01762 if(dRez > 0) dTardiness += dRez*WeightT.data[nNiz][index];
01763 if(dRez > 0) nLateJobs ++;
01764 if(dRez > 0) dNwt += WeightN.data[nNiz][index];
01765 if(m_dynamic)
01766 dFwt += MachineReady[nMachine][0] - Ready[nNiz][index];
01767 else
01768 dFwt += MachineReady[nMachine][0];
01769 }
01770 for(i=0; i<nMachines; i++)
01771 if(MachineReady[i][0] > dCmax)
01772 dCmax = MachineReady[i][0];
01773
01774 double dAvgDuration = SP[nNiz][0] / nPoslova;
01775 dAvgWeights /= nPoslova;
01776 dTardiness /= (nPoslova * dAvgWeights * dAvgDuration);
01777 dNwt /= (nPoslova * dAvgWeights);
01778 dFwt /= (nPoslova * dAvgWeights * dAvgDuration);
01779 dCmax /= (nPoslova * dAvgDuration);
01780 switch(m_fitness)
01781 { case Twt: dRawFitness += dTardiness; break;
01782 case Nwt: dRawFitness += dNwt; break;
01783 case Fwt: dRawFitness += dFwt; break;
01784 case Cmax: dRawFitness += dCmax; break;
01785 default: CHECK(0);
01786 }
01787 nTotalLateJobs += nLateJobs;
01788 dTotalNwt += dNwt;
01789 dTotalFwt += dFwt;
01790 dTotalLateness += dLateness;
01791 dTotalTardiness += dTardiness;
01792 dTotalCmax += dCmax;
01793 Fitness[nNiz][Twt] = dTardiness;
01794 Fitness[nNiz][Nwt] = dNwt;
01795 Fitness[nNiz][FTwt] = 0;
01796 Fitness[nNiz][ETwt] = 0;
01797 Fitness[nNiz][Fwt] = dFwt;
01798 Fitness[nNiz][Cmax] = dCmax;
01799 }
01800
01801 }
01802 Fitness[sets][Twt] = dTotalTardiness;
01803 Fitness[sets][Nwt] = dTotalNwt;
01804 Fitness[sets][Fwt] = dTotalFwt;
01805 Fitness[sets][Cmax] = dTotalCmax;
01806 }
01807
01808
01809
01810
01811
01812 void SchedulingEvalOp::EvaluateJobShop(double &dRawFitness)
01813 {
01814 double dL, dT, dTwt, dF, dFwt, dN, dNwt, dCmax;
01815 double dTotalT, dTotalTwt, dTotalF, dTotalFwt, dTotalN, dTotalNwt, dTotalCmax;
01816 double dClock, dAvgWeights, dTotalAvgLoad, dBestMachineValue, dAvgDuration;
01817 double dBest, dSetupTime, m1, m2, dNajkrace, dBegin;
01818 unsigned int nPoslova, nNiz, nJob, i, j, k, nNr, nOperations, nOperation, nNextOperation;
01819 unsigned int nMachines, nMachine, nSchedule, nMachineIndex, nJobsToEval, nBestJob, nNextMachine;
01820 unsigned int nBottleneck;
01821
01822 dRawFitness=0;
01823 dTotalT = dTotalTwt = dTotalF = dTotalFwt = dTotalN = dTotalNwt = dTotalCmax = 0;
01824
01825
01826 for(nNiz=0; nNiz<sets; nNiz++)
01827 { nNr = nPoslova = (int) N.Get(nNiz);
01828
01829
01830 if(m_stsampling)
01831 if(pSamples[nNiz] == false)
01832 continue;
01833
01834 if(m_LEF)
01835 { if(dRawFitness > m_LEFVal)
01836 break;
01837 }
01838 if(m_setup)
01839 MakeSetup(Duration,nNiz,nPoslova,m_setup_faktor,Setup);
01840
01841 dClock = 0;
01842 dTotalAvgLoad = 0;
01843 nOperations = nMachines = (uint) Machines[nNiz][0];
01844 dBestMachineValue = 0;
01845 nBottleneck = nMachines;
01846 for(j=0; j<nMachines; j++)
01847 { MachineReady[j][0] = 0;
01848 pLastJob[j] = nPoslova;
01849 pMachineScheduled[j] = 0;
01850 pOperationReady[j] = -1;
01851 pTotalMachineWork[j] = 0;
01852 pOperationsWaiting[j] = 0;
01853 pMachineValues[j] = 0;
01854 }
01855 for(i=0; i<nPoslova; i++)
01856 { pTotalWorkRemaining[i] = 0;
01857 pTotalWorkDone[i] = 0;
01858 pIndex[i] = i;
01859 pJobReady[i] = Ready[nNiz][i];
01860 pOperationsScheduled[i] = 0;
01861 for(j=0; j<nOperations; j++)
01862 { k = (int) Duration[nNiz][i*nOperations + j];
01863 nMachine = k / 1000;
01864 if(j == 0)
01865 pOperationsWaiting[nMachine]++;
01866 k = k % 1000;
01867 pTotalWorkRemaining[i] += k;
01868 Durations[i][j] = k;
01869 dTotalAvgLoad += k;
01870 MachineIndex[i][j] = nMachine;
01871 pTotalMachineWork[nMachine] += k;
01872 }
01873
01874 nMachine = (int) MachineIndex[i][0];
01875 pOperationReady[nMachine] = pJobReady[i];
01876
01877 }
01878 dAvgDuration = dTotalAvgLoad / nPoslova;
01879 dTotalAvgLoad /= nMachines;
01880 Evaluator.SetTermArraySize(nPoslova);
01881 Evaluator.pIndex = pIndex;
01882 Evaluator.m_iOffset = 0;
01883
01884
01885 memcpy(Evaluator.m_dTermValuesArray[T_dd], Deadline.data[nNiz], nPoslova*sizeof(double));
01886 memcpy(Evaluator.m_dTermValuesArray[T_w], WeightT.data[nNiz], nPoslova*sizeof(double));
01887 memcpy(Evaluator.m_dTermValuesArray[T_TWK], pTotalWorkRemaining, nPoslova*sizeof(double));
01888
01889 for(i=0; i<nMachines; i++)
01890 { Evaluator.m_dTermValuesArray[T_MTWKav][i] = dTotalAvgLoad;
01891 Evaluator.m_dTermValuesArray[T_MTWK][i] = pTotalMachineWork[i];
01892 pMachineWorkRemaining[i] = pTotalMachineWork[i];
01893 }
01894 memcpy(Evaluator.m_dTermValuesArray[T_MTWK], pTotalMachineWork, nMachines*sizeof(double));
01895
01896 for(nSchedule = 0; nSchedule < nPoslova*nMachines; nSchedule++)
01897 {
01898 for(nMachine = 0; nMachine<nMachines; nMachine++)
01899 if(pOperationReady[nMachine] >= 0)
01900 break;
01901 for(i = nMachine; i < nMachines; i++)
01902 { if(pOperationReady[i] < 0)
01903 continue;
01904 m1 = MAX(MachineReady[i][0],pOperationReady[i]);
01905 m2 = MAX(MachineReady[nMachine][0],pOperationReady[nMachine]);
01906 if(m1 < m2)
01907 nMachine = i;
01908 }
01909 dClock = MAX(MachineReady[nMachine][0], pOperationReady[nMachine]);
01910
01911 dNajkrace = -1;
01912 for(nJob=0; nJob<nPoslova; nJob++)
01913 { nOperation = pOperationsScheduled[nJob];
01914 if(nOperation == nMachines) continue;
01915 nMachineIndex = (int) MachineIndex[nJob][nOperation];
01916 if(nMachineIndex != nMachine) continue;
01917 if(dNajkrace < 0)
01918 dNajkrace = MAX(dClock, pJobReady[nJob]) + Durations[nJob][nOperation];
01919 else
01920 { dBegin = MAX(dClock, pJobReady[nJob]);
01921 if(dNajkrace > dBegin + Durations[nJob][nOperation])
01922 dNajkrace = dBegin + Durations[nJob][nOperation];
01923 }
01924 }
01925
01926
01927
01928 nJobsToEval = 0;
01929 for(nJob=0; nJob<nPoslova; nJob++)
01930 { nOperation = pOperationsScheduled[nJob];
01931 if(nOperation == nMachines) continue;
01932 nMachineIndex = (int) MachineIndex[nJob][nOperation];
01933 if(nMachineIndex != nMachine) continue;
01934
01935 if(!m_Idleness)
01936 if(pJobReady[nJob] > dClock) continue;
01937
01938 dBegin = MAX(pJobReady[nJob],dClock);
01939 if(dBegin > dNajkrace)
01940 continue;
01941
01942 pIndex[nJobsToEval] = nJob;
01943 nJobsToEval++;
01944 }
01945 #ifdef TREES
01946
01947 *
01948 MNOPr[nMachine] = nOperations - pMachineScheduled[nMachine]
01949 MTWKav = dTotalAvgLoad;
01950 MTWK[nMachine] = pTotalMachineWork[nMachine];
01951 MNOPw[nMachine] = pOperationsWaiting[nMachine];
01952 MTWKr[nMachine] = pMachineWorkRemaining[nMachine];
01953 MUTL[nMachine] = (pTotalMachineWork[nMachine] - pMachineWorkRemaining[nMachine]) / dClock;
01954 */
01955 Evaluator.m_nTree = 0;
01956
01957 Evaluator.m_dTermValuesArray[T_MNOPr][nMachine] = nOperations - pMachineScheduled[nMachine];
01958 Evaluator.m_dTermValuesArray[T_MNOPw][nMachine] = pOperationsWaiting[nMachine];
01959 Evaluator.m_dTermValuesArray[T_MTWKr][nMachine] = pMachineWorkRemaining[nMachine];
01960 if(dClock == 0)
01961 Evaluator.m_dTermValuesArray[T_MUTL][nMachine] = 1;
01962 else
01963 Evaluator.m_dTermValuesArray[T_MUTL][nMachine] = (pTotalMachineWork[nMachine] - pMachineWorkRemaining[nMachine]) / dClock;
01964
01965 Evaluator.m_iPosition = -1;
01966 nSavedIndex = pIndex[nMachine];
01967 pIndex[nMachine] = nMachine;
01968 Evaluator.m_iOffset = nMachine;
01969 Evaluator.m_iEnd = nMachine + 1;
01970 Evaluator.evaluate_array(pVrijednosti);
01971 pMachineValues[nMachine] = pVrijednosti[nMachine];
01972
01973 * dBestMachineValue = pMachineValues[0];
01974 nBottleneck = 0;
01975 for(i=0; i<nMachine; i++)
01976 if(pMachineValues[i] > dBestMachineValue)
01977 { dBestMachineValue = pMachineValues[i];
01978 nBottleneck = i;
01979 }
01980 */
01981
01982
01983 if(pMachineValues[nMachine] >= dBestMachineValue)
01984 { dBestMachineValue = pMachineValues[nMachine];
01985 nBottleneck = nMachine;
01986 }
01987
01988 if(nMachine == nBottleneck)
01989 Evaluator.m_nTree = 2;
01990 else
01991 Evaluator.m_nTree = 1;
01992 pIndex[nMachine] = nSavedIndex;
01993 #else // samo jedno stablo
01994 Evaluator.m_nTree = 0;
01995 #endif
01996
01997
01998 for(i=0; i<nJobsToEval; i++)
01999 { nJob = pIndex[i];
02000 nOperation = pOperationsScheduled[nJob];
02001 Evaluator.m_dTermValuesArray[T_pt][nJob] = Durations[nJob][nOperation];
02002 Evaluator.m_dTermValuesArray[T_CLK][nJob] = dClock;
02003 Evaluator.m_dTermValuesArray[T_AR][nJob] = POS(pJobReady[nJob] - dClock);
02004 Evaluator.m_dTermValuesArray[T_STP][nJob] = Setup[pLastJob[nMachine]][nJob];
02005 Evaluator.m_dTermValuesArray[T_Sav][nJob] = pSetupAvg[pLastJob[nMachine]];
02006 Evaluator.m_dTermValuesArray[T_age][nJob] = POS(dClock - Ready[nNiz][nJob]);
02007 Evaluator.m_dTermValuesArray[T_NOPr][nJob] = nOperations - pOperationsScheduled[nJob];
02008 Evaluator.m_dTermValuesArray[T_PTav][nJob] = PTimeAvg[nNiz][nMachine];
02009 Evaluator.m_dTermValuesArray[T_TWKr][nJob] = pTotalWorkRemaining[nJob];
02010 if(pTotalWorkDone[nJob] == 0)
02011 Evaluator.m_dTermValuesArray[T_HTR][nJob] = 1;
02012 else
02013 Evaluator.m_dTermValuesArray[T_HTR][nJob] = POS(dClock - Ready[nNiz][nJob]) / pTotalWorkDone[nJob];
02014 }
02015 Evaluator.m_iPosition = -1;
02016 Evaluator.m_iOffset = 0;
02017 Evaluator.m_iEnd = nJobsToEval;
02018 Evaluator.evaluate_array(pVrijednosti);
02019 dBest = pVrijednosti[pIndex[0]];
02020 nBestJob = pIndex[0];
02021 for(i=1; i<nJobsToEval; i++)
02022 { if(pVrijednosti[pIndex[i]] < dBest)
02023 { dBest = pVrijednosti[pIndex[i]];
02024 nBestJob = pIndex[i];
02025 }
02026 }
02027
02028
02029 nOperation = pOperationsScheduled[nBestJob];
02030 pOperationsScheduled[nBestJob] += 1;
02031 pTotalWorkRemaining[nBestJob] -= Durations[nBestJob][nOperation];
02032 pMachineWorkRemaining[nMachine] -= Durations[nBestJob][nOperation];
02033 pTotalWorkDone[nBestJob] += Durations[nBestJob][nOperation];
02034 if(m_setup)
02035 { dSetupTime = Setup[pLastJob[nMachine]][nBestJob];
02036 pLastJob[nMachine] = nBestJob;
02037 }
02038 else
02039 dSetupTime = 0;
02040 dClock = MAX(dClock, pJobReady[nBestJob]);
02041 MachineReady[nMachine][0] = dClock + dSetupTime + Durations[nBestJob][nOperation];
02042 pJobReady[nBestJob] = MachineReady[nMachine][0];
02043 if(nOperation < nOperations-1)
02044 { nNextMachine = (int) MachineIndex[nBestJob][pOperationsScheduled[nBestJob]];
02045 if(pOperationReady[nNextMachine] < 0)
02046 pOperationReady[nNextMachine] = pJobReady[nBestJob];
02047 else
02048 if(pOperationReady[nNextMachine] > pJobReady[nBestJob])
02049 pOperationReady[nNextMachine] = pJobReady[nBestJob];
02050 }
02051
02052 pOperationReady[nMachine] = -1;
02053 pOperationsWaiting[nMachine] = 0;
02054 for(j=0; j<nPoslova; j++)
02055 { nNextOperation = pOperationsScheduled[j];
02056 if(nNextOperation == nMachines) continue;
02057 nNextMachine = (int) MachineIndex[j][nNextOperation];
02058 if(nNextMachine != nMachine) continue;
02059 pOperationsWaiting[nMachine]++;
02060 if(pOperationReady[nMachine] < 0)
02061 pOperationReady[nMachine] = pJobReady[j];
02062 else
02063 if(pOperationReady[nMachine] > pJobReady[j])
02064 pOperationReady[nMachine] = pJobReady[j];
02065 }
02066 nOperation = (int) pMachineScheduled[nMachine];
02067 pMachineScheduled[nMachine] += 1;
02068 Schedule[nNiz][nMachine * nPoslova + nOperation] = nBestJob;
02069 }
02070
02071
02072 { if(m_Evaluation)
02073 { for(i=nPoslova*nMachines ; i < (uint)Schedule.GetCol(); i++)
02074 Schedule[nNiz][i] = 0;
02075 }
02076
02077 dAvgWeights = 0;
02078 dCmax = dF = dFwt = dT = dTwt = dN = dNwt = 0;
02079 for(j=0; j<nPoslova; j++)
02080 { dAvgWeights += WeightT[nNiz][j];
02081 if(dCmax < pJobReady[j])
02082 dCmax = pJobReady[j];
02083 dF += pJobReady[j] - Ready[nNiz][j];
02084 dFwt += (pJobReady[j] - Ready[nNiz][j]) * WeightT[nNiz][j];
02085 if(pJobReady[j] > Deadline[nNiz][j])
02086 { dN += 1;
02087 dNwt += WeightT[nNiz][j];
02088 dL = pJobReady[j] - Deadline[nNiz][j];
02089 dT += dL;
02090 dTwt += WeightT[nNiz][j] * dL;
02091 }
02092 }
02093 dAvgWeights /= nPoslova;
02094 dCmax /= nPoslova*dAvgDuration;
02095 dF /= nPoslova;
02096 dFwt /= nPoslova*dAvgWeights*dAvgDuration;
02097 dT /= nPoslova;
02098 dTwt /= nPoslova*dAvgWeights*dAvgDuration;
02099 dN /= nPoslova;
02100 dNwt /= nPoslova*dAvgWeights;
02101 dTotalCmax += dCmax;
02102 dTotalF += dF;
02103 dTotalFwt += dFwt;
02104 dTotalT += dT;
02105 dTotalTwt += dTwt;
02106 dTotalN += dN;
02107 dTotalNwt += dNwt;
02108
02109 switch(m_fitness)
02110 { case Twt: dRawFitness += dTwt; break;
02111 case Nwt: dRawFitness += dNwt; break;
02112 case Fwt: dRawFitness += dFwt; break;
02113 case Cmax: dRawFitness += dCmax; break;
02114 default: CHECK(0);
02115 }
02116 Fitness[nNiz][Twt] = dTwt;
02117 Fitness[nNiz][Nwt] = dNwt;
02118 Fitness[nNiz][FTwt] = 0;
02119 Fitness[nNiz][ETwt] = 0;
02120 Fitness[nNiz][Fwt] = dFwt;
02121 Fitness[nNiz][Cmax] = dCmax;
02122 }
02123
02124 }
02125 Fitness.data[sets][Twt] = dTotalTwt;
02126 Fitness.data[sets][Nwt] = dTotalNwt;
02127 }