ECF 1.5
fitnes.cpp
1/*
2Radi za:
3SINGLE okruzenje:
4- staticke i dinamicke dolaske poslova
5- sa i bez ogranicenja u rasporedu
6- trajanja postavljanja za staticki i dinamicki slucaj
7UNIFORM okruzenje:
8- staticke i dinamicke dolaske poslova
9- trajanja postavljanja za staticki i dinamicki slucaj
10treba napraviti:
11- promijeniti racunanje SPr ! (otkomentirati)
12UNRELATED okruzenje:
13- dinamicki uvjeti rada (simulacija online schedulinga)
14JOBSHOP okruzenje:
15- staticki dolasci poslova
16- sa ili bez idle time
17*/
18
19#include <ecf/ECF.h>
20#include "fitnes.hpp"
21#include <cmath>
22
23// globalna varijabla - koriste je svi zivi...
24node Nodes[TOTAL_NODES];
25
26// makroi za uvjetnu provjeru
27#define CHECKMSG(condition, text) \
28if(!(condition)) {fprintf(stderr,"file: " __FILE__ "\nline: %d\nmsg: " text "\n",__LINE__); exit(1);}
29#define CHECK(condition) \
30if(!(condition)) {fprintf(stderr,"Nesto ne valja!\nfile: " __FILE__ "\nline: %d\n" ,__LINE__); exit(1);}
31// fja max{x,0}
32#define POS(x) (x>0 ? x : 0)
33#define MIN(x,y) (x<y ? x : y)
34#define MAX(x,y) (x>y ? x : y)
35
36
37// fja za uporabu qsort-a
38double *pVal;
39int Before(const void *arg1, const void *arg2)
40{
41 if(pVal[*(uint*)arg1] < pVal[*(uint*)arg2])
42 return -1;
43 else if(pVal[*(uint*)arg1] > pVal[*(uint*)arg2])
44 return 1;
45 return 0;
46}
47
48
49// definira imena terminala i funkcija; takodjer postavlja aktivne funkcije
50SchedulingEvalOp::SchedulingEvalOp()
51{
52 for(int i=0; i<TERMINALS+OFFSET; i++)
53 { Nodes[i].active = false;
54 }
55 for(int i=TERMINALS+OFFSET; i<TOTAL_NODES; i++)
56 { Nodes[i].active = true;
57 }
58 // definiramo imena mogucih funkcija i terminala
59 Nodes[NUL].name = "0";
60 Nodes[NUL].value = 0;
61 Nodes[ONE].name = "1";
62 Nodes[ONE].value = 1;
63 Nodes[T_N].name = "N";
64 Nodes[T_SP].name = "SP";
65 Nodes[T_SD].name = "SD";
66 Nodes[T_pt].name = "pt";
67 Nodes[T_dd].name = "dd";
68 Nodes[T_w].name = "w";
69 Nodes[T_Nr].name = "Nr";
70 Nodes[T_SPr].name = "SPr";
71 Nodes[T_SL].name = "SL";
72 Nodes[T_AR].name = "AR";
73 Nodes[T_SC].name = "SC";
74 Nodes[T_LVL].name = "LVL";
75 Nodes[T_STP].name = "STP";
76 Nodes[T_Sav].name = "Sav";
77 Nodes[T_SLs].name = "SLs";
78 Nodes[T_SPD].name = "SPD";
79 Nodes[T_Msm].name = "Msm";
80 Nodes[T_pmin].name = "pmin";
81 Nodes[T_pavg].name = "pavg";
82 Nodes[T_PAT].name = "PAT";
83 Nodes[T_MR].name = "MR";
84 Nodes[T_age].name = "age";
85 Nodes[T_L].name = "L";
86 Nodes[T_SLr].name = "SLr";
87 Nodes[T_CLK].name = "CLK";
88 Nodes[T_NOPr].name = "NOPr";
89 Nodes[T_TWK].name = "TWK";
90 Nodes[T_TWKr].name = "TWKR";
91 Nodes[T_PTav].name = "PTav";
92 Nodes[T_HTR].name = "HTR";
93 Nodes[T_TF].name = "TF";
94 // terminali za strojeve
95 Nodes[T_MNOPr].name = "MNOPr";
96 Nodes[T_MNOPw].name = "MNOPw";
97 Nodes[T_MTWK].name = "MTWK";
98 Nodes[T_MTWKr].name = "MTWKr";
99 Nodes[T_MTWKav].name = "MTWKav";
100 Nodes[T_MUTL].name = "MUTL";
101
102
103 Nodes[T_wc].name="wc";
104 Nodes[T_we].name="we";
105
106 // funkcije
107 Nodes[ADD].name = "+";
108 Nodes[SUB].name = "-";
109 Nodes[MUL].name = "*";
110 Nodes[DIV].name = "/";
111 Nodes[POS].name = "pos";
112 Nodes[SQR].name = "sqr";
113 Nodes[IFGT].name = "ifgt";
114 // default parametri
115 m_Idleness = false; // po defaultu ne cekamo u job shop okruzenju
116 m_TermUsage = false; // iskljucena statistika koristenja terminala
117 m_BestSubset = 100; // po defaultu gledamo 100 najboljih
118 m_LEF = 0; // nema rezanja fitnesa po defaultu
119 m_editing = false; // niti editiranja
120 m_Evaluation = false; // pisanje detaljnih rezultata u fajl je iskljuceno
121 Evaluator.SetExprSize(2000); // postavimo max velicinu izraza... :)
122 edited = 0; // koliko cvorova je editirano
123 total = 0; // koliko cvorova je ukupno bilo
124}
125
126
127SchedulingEvalOp::~SchedulingEvalOp()
128{
129 delete [] pRasporedjen;
130 delete [] pVrijednosti;
131 delete [] pIndex;
132 delete [] pUsed;
133 delete [] pArray;
134 delete [] pSlack;
135 delete [] pSlackSpeed;
136 delete [] pSamples;
137 delete [] pArrival;
138 delete [] pLevel;
139 delete [] pSetupAvg;
140 delete [] pLastJob;
141 delete [] pMachineScheduled;
142 delete [] pOperationReady;
143 delete [] pJobReady;
144 delete [] pOperationsScheduled;
145 delete [] pTotalWorkRemaining;
146 delete [] pTotalWorkDone;
147 delete [] pTotalMachineWork;
148 delete [] pMachineWorkRemaining;
149 delete [] pOperationsWaiting;
150 delete [] pMachineValues;
151}
152
153
154void SchedulingEvalOp::registerParameters(StateP state)
155{
156 state->getRegistry()->registerEntry("test_cases", (voidP) (new std::string), ECF::STRING);
157 state->getRegistry()->registerEntry("normalized", (voidP) (new uint(1)), ECF::UINT);
158 state->getRegistry()->registerEntry("genotip", (voidP) (new std::string), ECF::STRING);
159 state->getRegistry()->registerEntry("primjer", (voidP) (new uint(0)), ECF::UINT);
160}
161
162
163// inicijalizacija
164// zove se nakon ucitavanja GP parametara, prije pocetka evolucije
165bool SchedulingEvalOp::initialize(StateP state)
166{
167 state_ = state;
168
169 std::string configFile;
170
171 // check if the parameters are defined in the conf. file
172 if(!state->getRegistry()->isModified("test_cases"))
173 return false;
174
175 voidP sptr = state->getRegistry()->getEntry("test_cases"); // get parameter value
176 configFile = *((std::string*) sptr.get()); // convert from voidP to user defined type
177 in_file = configFile;
178
179 sptr = state->getRegistry()->getEntry("normalized"); // get parameter value
180 m_Normalized = (bool) *((uint*) sptr.get()); // convert from voidP to user defined type
181
182 sptr = state->getRegistry()->getEntry("genotip"); // get parameter value
183 m_genotip = *((std::string*) sptr.get()); // convert from voidP to user defined type
184
185 sptr = state->getRegistry()->getEntry("primjer"); // get parameter value
186 m_primjer = (uint) *((uint*) sptr.get()); // convert from voidP to user defined type
187
188 if(m_primjer > 60) {
189 m_primjer = *((uint*) state->getContext()->environment);
190 }
191
192 if(m_genotip == "GP") // ako koristimo GP
193 // procitaj terminale iz registrija
194 ReadTerminals(state);
195 else{
196 m_primjer = *((uint*) state->getContext()->environment);
197 }
198// originalni dio iz BEAGLE implementacije:
199 std::string input,sp,duration,deadline,weightT,weightF,weightE,weightN, weightC,term,ready,cons,speed;
200 char pom[256];
201 ReadPar p;
202 unsigned int i,j;
203 double d_niz[2][1000];
204
207 //IntegerVector::Handle hPopSize;
208 //hPopSize = castHandleT<IntegerVector>(ioSystem.getRegister().getEntry("ec.pop.size"));
209 //unsigned int nDemes = (unsigned int) (*hPopSize).size();
210 //m_PopSize = 0;
211 //for(i=0; i<nDemes; i++)
212 // m_PopSize += (*hPopSize)[i];
215 //m_SubsetSize = (uint) (0.1 * (float)m_PopSize) + 1;
216
217 // inicijalizacija default vrijednosti
218 input = configFile; // glavni ulazni fajl, mora ga biti
219
220 // ucitavanje parametara
221 p.OpenFile(input.c_str());
222 if(p.ReadParameter("single",ReadPar::INTEGER,&i))
223 m_Environment = SINGLE;
224 else if(p.ReadParameter("uniform",ReadPar::INTEGER,&i))
225 m_Environment = UNIFORM;
226 else if(p.ReadParameter("unrelated",ReadPar::INTEGER,&i))
227 m_Environment = UNRELATED;
228 else if(p.ReadParameter("jobshop",ReadPar::INTEGER,&i))
229 m_Environment = JOBSHOP;
230 p.ReadParameter("sets",ReadPar::INTEGER,&sets);
231 p.ReadParameter("max_jobs",ReadPar::INTEGER,&max_jobs);
232 if(!p.ReadParameter("max_machines",ReadPar::INTEGER,&max_machines))
233 max_machines = 1;
234 p.ReadParameter("max_length",ReadPar::INTEGER,&max_length);
235 p.ReadParameter("duration",ReadPar::STRING,pom); duration = pom;
236 p.ReadParameter("deadline",ReadPar::STRING,pom); deadline = pom;
237 p.ReadParameter("weight_T",ReadPar::STRING,pom); weightT = pom;
238 p.ReadParameter("weight_F",ReadPar::STRING,pom); weightF = pom;
239 p.ReadParameter("weight_E",ReadPar::STRING,pom); weightE = pom;
240 p.ReadParameter("weight_N",ReadPar::STRING,pom); weightN = pom;
241 p.ReadParameter("weight_C",ReadPar::STRING,pom); weightC = pom;
242 p.ReadParameter("SP",ReadPar::STRING,pom); sp = pom;
243 p.ReadParameter("machine_file",ReadPar::STRING,pom); speed = pom;
244 // dinamicki dolasci poslova
245 if(p.ReadParameter("ready",ReadPar::STRING,pom))
246 { ready = pom;
247 m_dynamic = true;
248 }
249 else
250 m_dynamic = false;
251 // limited error fitness izracunavanje
252 if(p.ReadParameter("LEF",ReadPar::INTEGER,&i))
253 { if(i==1)
254 { m_LEF = true;
255 if(!p.ReadParameter("LEF_value",ReadPar::DOUBLE,&m_LEFVal))
256 CHECKMSG(0,"LEF vrijednost nije zadana!");
257 }
258 }
259 // evaluacija - ispis rjesenja za svaku jedinku
260 if(p.ReadParameter("evaluation",ReadPar::INTEGER,&i))
261 if(i==1) m_Evaluation = true;
262 // fitness - mora biti definiran
263 if(p.ReadParameter("fitness",ReadPar::STRING,pom))
264 { input = pom;
265 if(input == "Twt")
266 m_fitness = Twt;
267 else if(input == "Nwt")
268 m_fitness = Nwt;
269 else if(input == "FTwt")
270 m_fitness = FTwt;
271 else if(input == "ETwt")
272 m_fitness = ETwt;
273 else if(input == "Cmax")
274 m_fitness = Cmax;
275 else if(input == "Fwt")
276 m_fitness = Fwt;
277 else if(input == "TwtCmax")
278 m_fitness = TwtCmax;
279 else if(input == "NwtCmax")
280 m_fitness = NwtCmax;
281 else if(input == "Mus")
282 m_fitness = Mus;
283 else if(input == "Fmax")
284 m_fitness = Fmax;
285 else if(input=="Tmax")
286 m_fitness = Tmax;
287 else if(input == "Cw"){
288 m_fitness = Cw;
289 //cout<<"tralalal "<<m_fitness<<endl;
290 }
291 else
292 CHECKMSG(0,"Nepoznata fitnes funkcija!");
293 }
294 else CHECKMSG(0,"Nije definirana fitnes funkcija!");
295 // editiranje jedinke
296 if(p.ReadParameter("editing",ReadPar::INTEGER,&i))
297 if(i==1) m_editing = true;
298 // stochastic sampling, koliko
299 if(p.ReadParameter("stsampling",ReadPar::DOUBLE,&m_sampling))
300 m_stsampling = true;
301 else
302 m_stsampling = false;
303 // ogranicenja u rasporedu
304 if(p.ReadParameter("constraints",ReadPar::STRING,pom))
305 { cons = pom;
306 m_constrained = true;
307 }
308 else
309 m_constrained = false;
310 // trajanja postavljanja
311 if(p.ReadParameter("setup",ReadPar::DOUBLE,&m_setup_faktor))
312 m_setup = true;
313 else
314 m_setup = false;
315 // eventualno definiranje podskupa jedinki za brojanje terminala
316 p.ReadParameter("bestsubset",ReadPar::INTEGER,&m_BestSubset);
317 if(p.ReadParameter("idleness",ReadPar::INTEGER, &i))
318 if(i == 1) m_Idleness = true;
319
320 N.Init(sets);
321 SP.Init(sets);
322 SD.Init(sets);
323 Machines.Init(sets);
324 MachineReady.Init(max_machines);
325 Speed.Init(sets,max_jobs);
326 Duration.Init(sets,max_jobs);
327 Deadline.Init(sets,max_jobs);
328 Durations.Init(max_jobs, max_machines);
329 MachineIndex.Init(max_jobs, max_machines);
330 WeightT.Init(sets,max_jobs);
331 WeightF.Init(sets,max_jobs);
332 WeightE.Init(sets,max_jobs);
333 WeightN.Init(sets,max_jobs);
334 WeightC.Init(sets,max_jobs);
335 Fitness.Init(sets+1,FUNCTIONS);
336 Values.Init(max_machines,max_jobs);
337 Precedence.Reset(max_jobs,max_jobs); // prazna matrica znaci da nema ogranicenja!
338 Setup.Init(max_jobs+1,max_jobs);
339 if(m_Environment == JOBSHOP)
340 { Schedule.Init(sets, max_machines*max_jobs);
341 PTimeAvg.Reset(sets, max_machines);
342 }
343 else
344 { Schedule.Init(sets,max_jobs);
345 PTimeAvg.Init(sets,max_jobs);
346 PTimeMinMachine.Init(sets,max_jobs);
347 }
348 SortedReady.Init(sets,max_jobs);
349
350 pVrijednosti = new double[max_jobs];
351 pRasporedjen = new bool[max_jobs];
352 pIndex = new unsigned int[max_jobs];
353 pUsed = new unsigned int[max_jobs];
354 pArray = new double[max_jobs];
355 pSlack = new double[max_jobs];
356 pSlackSpeed = new double[max_jobs];
357 pArrival = new double[max_jobs];
358 pLevel = new double[max_jobs];
359 pSetupAvg = new double[max_jobs + 1];
360 pSamples = new bool[sets];
361 pLastJob = new unsigned int[max_machines];
362 pMachineScheduled = new unsigned int[max_machines];
363 pOperationReady = new double[max_machines];
364 pJobReady = new double[max_jobs];
365 pOperationsScheduled = new unsigned int[max_jobs];
366 pTotalWorkRemaining = new double[max_jobs];
367 pTotalWorkDone = new double[max_jobs];
368 pTotalMachineWork = new double[max_machines];
369 pOperationsWaiting = new unsigned int[max_machines];
370 pMachineWorkRemaining = new double[max_machines];
371 pMachineValues = new double[max_machines];
372 p.ReadParameter("jobs",ReadPar::DOUBLE,&d_niz[0][0],sets);
373 p.ReadParameter("machines",ReadPar::DOUBLE,&d_niz[1][0],sets);
374 total_jobs = 0;
375 for(i=0; i<sets; i++)
376 { N[i][0] = d_niz[0][i];
377 total_jobs += (int) d_niz[0][i];
378 Machines[i][0] = d_niz[1][i];
379 }
380 Duration.Load(duration.c_str());
381 Deadline.Load(deadline.c_str());
382 if(m_Environment==UNIFORM)
383 { Speed.Load(speed.c_str());
384 }
385 WeightT.Load(weightT.c_str());
386 WeightF.Load(weightF.c_str());
387 WeightE.Load(weightE.c_str());
388 WeightN.Load(weightN.c_str());
389
390 WeightC.Load(weightC.c_str());
391 SP.Load(sp.c_str());
392 if(m_dynamic) Ready.Load(ready.c_str());
393 else Ready.Reset(sets,max_jobs);
394 if(m_constrained) Constraints.Load(cons.c_str());
395 // racunamo sumu deadline-a
396 Level.Init(sets,max_jobs);
397 for(i=0; i<sets; i++)
398 { SD.Set(i,0);
399 for(j=0; j<(unsigned int)N.Get(i); j++)
400 { SD.data[i][0] += Deadline.data[i][j];
401 Level[i][j] = -1; // oznacimo da je neizracunato
402 }
403 }
404 // racunamo level cvorova u grafu ovisnosti
405 for(i=0; i<sets; i++)
406 { if(m_constrained)
407 ReadConstraints(Constraints,i,(unsigned int)N.Get(i),Precedence);
408 for(j=0; j<(unsigned int)N.Get(i); j++)
409 Level[i][j] = NodeLevel(i,j);
410 }
411 // racunamo prosjek i minimalno trajanje izvodjenja za UNRELATED
412 if(m_Environment == UNRELATED)
413 { for(uint set=0; set<sets; set++)
414 { uint jobs = (uint) N[set][0];
415 uint machines = (uint) Machines[set][0];
416 for(j=0; j<jobs; j++)
417 { PTimeAvg[set][j] = 0;
418 uint min_machine = 0;
419 for(uint machine=0; machine<machines; machine++)
420 { PTimeAvg[set][j] += Duration[set][j*machines + machine];
421 if(Duration[set][j*machines + machine] < Duration[set][j*machines + min_machine])
422 min_machine = machine;
423 }
424 PTimeAvg[set][j] /= machines;
425 PTimeMinMachine[set][j] = min_machine;
426 }
427 }
428 }
429 if(m_Environment == JOBSHOP) // prosjek trajanja operacija po strojevima
430 { for(uint set=0; set<sets; set++)
431 { uint jobs = (uint) N[set][0];
432 uint machines = (uint) Machines[set][0];
433 for(j=0; j<jobs; j++)
434 { uint operations = machines;
435 for(uint op=0; op<operations; op++)
436 { double dur = Duration[set][j*operations + op];
437 uint machine = (uint) dur / 1000;
438 dur = (int)dur % 1000; // dobijemo trajanje
439 PTimeAvg[set][machine] += dur;
440 }
441 }
442 for(uint m=0; m<machines; m++)
443 PTimeAvg[set][m] /= jobs;
444 }
445 }
446
447 // sortiramo indekse poslova po dolascima - treba za ubrzano izracunavanje
448 for(i=0; i<sets; i++)
449 { ::pVal = Ready[i];
450 uint jobs = (uint) N[i][0];
451 for(j=0; j<jobs; j++)
452 pIndex[j] = j;
453 qsort(pIndex,jobs,sizeof(unsigned int),::Before);
454 for(j=0; j<jobs; j++)
455 SortedReady[i][j] = pIndex[j];
456 }
457
458 p.CloseFile();
459
460 return true;
461}
462
463
464
465// zove se iz main() prije inicijalizacije populacije
466void SchedulingEvalOp::DefineNodeNames(void)
467{
468}
469
470
471// citanje terminala iz konf. datoteke
472// radi se prije inicijalizacije populacije; poziva se iz main()
473// DEPRECATED!
474void SchedulingEvalOp::ReadTerminals(TreeP tree)
475{
476 int i,dummy;
477 ReadPar p;
478 std::string term;
479 p.OpenFile(in_file.c_str());
480
481 // citanje aktivnih terminala
482 for(i = OFFSET; i < TERMINALS + OFFSET; i++)
483 { term = "T_" + Nodes[i].name;
484 if(p.ReadParameter(term.c_str(),ReadPar::INTEGER,&dummy))
485 { Nodes[i].active = true;
486
487 // zadavanje terminala ECF-u
488 Tree::PrimitiveP newTerm = (Tree::PrimitiveP) new Tree::Primitives::Terminal;
489 newTerm->setName(Nodes[i].name);
490 tree->addTerminal(newTerm);
491 }
492 }
493 p.CloseFile();
494}
495
496
497// citanje terminala iz ECF parametra 'tree.terminalset'
498// poziva se iz initialize()
499void SchedulingEvalOp::ReadTerminals(StateP state)
500{
501 int i;
502 std::string term;
503
504 GenotypeP gen = (GenotypeP) (state->getGenotypes()[0]);
505 TreeP tree = boost::dynamic_pointer_cast<Tree::Tree> (gen);
506 voidP val = tree->getParameterValue(state, "terminalset");
507 std::string terminals = *((std::string*) val.get());
508 terminals = " " + terminals + " ";
509
510 // citanje aktivnih terminala
511 //for(i = OFFSET; i < TERMINALS + OFFSET; i++)
512 for(i = 0; i < TERMINALS + OFFSET; i++)
513 { if(terminals.find(" " + Nodes[i].name + " ") != string::npos)
514 { Nodes[i].active = true;
515 }
516 }
517}
518
519
520//
521// dio za provjeru duplikata
522//
523vector<IndividualP> jedinke;
524
525bool provjeriDuplikate(IndividualP individual, StateP state_)
526{
527 static uint gen = 0;
528 static uint jednakih = 0;
529
530 bool jednaka = false;
531
532 // provjeri generaciju
533 if(state_->getGenerationNo() != gen) {
534 gen = state_->getGenerationNo();
535
536 ECF_LOG(state_, 1, "jednakih: " + uint2str(jednakih) + ", " + uint2str(100*jednakih/jedinke.size()));
537
538 jedinke.clear();
539 jednakih = 0;
540 }
541
542 // provjeri sadrzaj
543 uint broj = (uint) jedinke.size();
544 Tree::Tree* nova = (Tree::Tree*) individual->getGenotype().get();
545 for(uint i = 0; i < broj; i++) {
546 Tree::Tree* stara = (Tree::Tree*) jedinke[i]->getGenotype().get();
547 if(nova->size() != stara->size())
548 continue;
549 uint n, size = (uint) nova->size();
550 Tree::NodeP cvor1, cvor2;
551 for(n = 0; n < size; n++) {
552 cvor1 = (*nova)[n];
553 cvor2 = (*stara)[n];
554 if(cvor1->primitive_ != cvor2->primitive_)
555 break;
556 }
557 // ako smo nasli jednaku, dodijeli joj Fitness od stare
558 if(n == size) {
559 jednakih++;
560 individual->fitness = (FitnessP) jedinke[i]->fitness->copy();
561 jednaka = true;
562 break;
563 }
564 }
565
566 return jednaka;
567}
568
569
570
571FitnessP SchedulingEvalOp::evaluate(IndividualP individual)
572{
573/* double dClock, dRawFitness=0, dFitness, dRez, dSetFitness, dAvgWeights;
574 double dLateness, dTotalLateness=0, dTardiness, dTotalTardiness=0;
575 double dNwt, dTotalNwt=0, dBest, dSPr, dMsum, dSetupTime, dFwt;
576 Double DResult, DBest;
577 unsigned int nPoslova,nNiz,nJob,i,j,k,index,nLateJobs,nTotalLateJobs=0,nNr;
578 unsigned int nLastJob,nMachines,nOdabrani,nMachine;
579*/
580
581 // 7.5.2014: provjera duplikata
582 //if(provjeriDuplikate(individual, state_)) {
583 // FitnessP fitness = individual->fitness;
584 // return fitness;
585 //}
586
587 // stvaranje zeljenog Fintess objekta:
588 FitnessP fitness = static_cast<FitnessP> (new FitnessMin);
589
590 if(m_genotip == "FP") { // koristimo FP, zasada samo unrelated okruzenje
591
592 FloatingPointP fp = boost::dynamic_pointer_cast<FloatingPoint::FloatingPoint> (individual->getGenotype());
593 double dFitness;
594
595 EvaluateUnrelatedFP(fp, dFitness);
596
597 fitness->setValue(dFitness);
598
599 return fitness;
600 }
601 if(m_genotip == "PERM"){
602 double dFitness;
603
604 EvaluateUnrelatedPermutation(individual, dFitness);
605 fitness->setValue(dFitness);
606 return fitness;
607 }
608
609
610 // dohvat genotipa jedinke
611 TreeP tree = boost::dynamic_pointer_cast<Tree::Tree> (individual->getGenotype());
612
613
614 //
615 // tu pozvati simplifikaciju!
616 //
617
618// oroginalni kod iz BEAGLE implementacije
619 unsigned int i;
620 double dRawFitness, dFitness;
621 ReadIndividual(individual); // procitaj i zapisi jedinku
622
623 // stochastic sampling?
624 if(m_stsampling)
625 { int koliko = (int) (m_sampling*sets);
626 int razmak = sets / koliko;
627 int pocetni = rand()%razmak;
628 for(i=0; i<sets; i++)
629 pSamples[i] = false;
630 for(i=pocetni; i<sets; i+=razmak)
631 pSamples[i] = true;
632 }
633
634 switch(m_Environment)
635 { case SINGLE:
636 EvaluateSingle(dRawFitness);
637 break;
638 case UNIFORM:
639 EvaluateUniform(dRawFitness);
640 break;
641 case UNRELATED:
642 EvaluateUnrelated(dRawFitness);
643 break;
644 case JOBSHOP:
645 EvaluateJobShop(dRawFitness);
646 break;
647 }
648
649 //dFitness = dRawFitness /= nJobS*SETS; // prosjek
650 //double lRMSE = sqrt(sqrt(dRawFitness)); // irelevantno za turnir selekciju
651 //dFitness = (1.0 / (lRMSE + 1.0));
652 dFitness = dRawFitness; // (trazimo minimum)
653
654 if(m_Evaluation) // samo za usporedbu heuristika! pise rezultate svih skupova u fajl
655 { Fitness.Save("rezultat_GP.txt");
656 std::ostream *file = new std::ofstream("rezultat_GP.txt", std::ios_base::app);
657 Evaluator.write();
658 *file << std::endl << "-- infix: " << Evaluator.m_output << " --" << std::endl;
659 *file << "Editirano: " << edited << ", ukupno: " << total << std::endl;
660 *file << std::flush;
661 delete file;
662 Schedule.Save("raspored_GP.txt");
663 }
664
665 // pogledamo je li ukljuceno brojanje terminala
666// if(m_TermUsage)
667// UpdateTerminalStatistic(dFitness);
668
669 fitness->setValue(dFitness);
670
671 // provjera duplikata: ova je bila nova, zapisi fitnes i zapamti ovu jedinku:
672 individual->fitness = fitness;
673 jedinke.push_back((IndividualP) individual->copy());
674
675 return fitness;
676}
677
678
679void SchedulingEvalOp::write(std::string &output)
680{
681}
682
683
684// dekodira matricu Constraints i definira matricu Precedence
685void SchedulingEvalOp::ReadConstraints(Matrica &Constraints, int set, int jobs, Matrica &Precedence)
686{
687 int i,j,prethodnika,prethodnik,pom;
688 unsigned int podatak;
689 //Precedence.Init(jobs,jobs);
690 // prvo ocistimo prva dva stupca! gdje su brojevi prethodnika i sljedbenika
691 for(i=0; i<jobs; i++)
692 for(j=0; j<2; j++)
693 Precedence[i][j] = 0;
694 for(i=0; i<jobs; i++)
695 { podatak = (unsigned int) Constraints[set][i];
696 prethodnik = 1; // koji po redu posao iza mene
697 prethodnika = 0;
698 while(podatak != 0)
699 { if(podatak%2 != 0)
700 { prethodnika++; // povecam broj svojih prethodnika
701 pom = (int) Precedence[i-prethodnik][1] + 1;
702 Precedence[i-prethodnik][pom+1] = i;
703 Precedence[i-prethodnik][1] = pom; // i broj sljedbenika od moga prethodnika
704 }
705 prethodnik++;
706 podatak /= 2;
707 }
708 Precedence[i][0] = prethodnika;
709 }
710}
711
712
713// generira matricu sequence dependant setup trajanja
714// i polje prosjecnih trajanja postavljanja za svaki posao prema ostalima
715void SchedulingEvalOp::MakeSetup(Matrica &Duration, int set, int jobs, double faktor, Matrica &Setup)
716{
717 int i,j;
718 pSetupAvg[jobs] = 0;
719 if(m_Environment == JOBSHOP)
720 { srand(set);
721 for(i=0; i<jobs; i++)
722 { Setup[jobs][i] = (int) ((rand()%max_length+1) * faktor); // polazno trajanje postavljanja
723 pSetupAvg[jobs] += Setup[jobs][i];
724 for(j=0; j<=i; j++)
725 { Setup[i][j] = (int) ((rand()%max_length+1) * faktor);
726 Setup[j][i] = (int) ((rand()%max_length+1) * faktor);
727 pSetupAvg[i] += Setup[i][j];
728 pSetupAvg[j] += Setup[j][i];
729 }
730 }
731 }
732 else
733 for(i=0; i<jobs; i++)
734 { pSetupAvg[i] = 0;
735 Setup[jobs][i] = Duration[set][(i+1) % jobs]; // polazno trajanje postavljanja
736 pSetupAvg[jobs] += Setup[jobs][i];
737 for(j=0; j<=i; j++)
738 { Setup[i][j] = ceil( fabs( Duration[set][i] - Duration[set][j] ) * faktor);
739 Setup[j][i] = ceil( fabs( Duration[set][(i+1) % jobs] - Duration[set][(j+1) % jobs] ) * faktor);
740 pSetupAvg[i] += Setup[i][j];
741 pSetupAvg[j] += Setup[j][i];
742 }
743 }
744 pSetupAvg[jobs] /= jobs;
745 for(i=0; i<jobs; i++)
746 pSetupAvg[i] /= (jobs-1);
747}
748
749
750// procita jedinku i zapise u RPN; takodjer editira i prebroji terminale
751void SchedulingEvalOp::ReadIndividual(IndividualP individual)
752{
753 TreeP tree = boost::dynamic_pointer_cast<Tree::Tree> (individual->getGenotype());
754 static std::string strTerminal;
755 unsigned int nTreeSize,i,j,nTree;
756 uint nTrees = (uint) individual->size();
757 for(nTree = 0; nTree<nTrees; nTree++) // vrtimo kroz stabla
758 { TreeP pTree = boost::dynamic_pointer_cast<Tree::Tree> (individual->getGenotype(nTree)); // pokazivac na tree
759 nTreeSize = (uint) pTree->size();
760 if(nTreeSize > Evaluator.m_iExprSize) // jel imamo dovoljno mjesta za cvorove
761 Evaluator.SetExprSize(nTreeSize);
762
763 // procitamo cijelo stablo i zapisemo u rpn
764 for(i=0; i<nTreeSize; i++)
765 { //strTerminal = (*pTree)[i].mPrimitive->getName();
766 strTerminal = (*pTree)[i]->primitive_->getName();
767 for(j=0; j<TOTAL_NODES; j++)
768 { if(!Nodes[j].active)
769 continue;
770 if(strTerminal == Nodes[j].name)
771 { Evaluator.m_pExpression[nTree][i] = j;
772 break;
773 }
774 }
775 assert(j<TOTAL_NODES);
776 }
777 // editiranje?
778 if(m_editing)
779 { Evaluator.m_nTree = nTree; // zadamo na kojem se stablu radi
780 Evaluator.m_iPosition = Evaluator.m_iEditedPos = -1;
781 Evaluator.edit();
782 Evaluator.copy(); // automatski prebrojava terminale i funkcije
783 total += Evaluator.m_iPosition;
784 edited += Evaluator.m_iPosition - Evaluator.m_iEditedPos;
785 }
786 }
787
788}
789
790
791// rekurzivno racunanje 'level' vrijednosti svakog posla
792// ima smisla samo u problemima s ogranicenjima
793// promjena 27.07: level cvora ukljucuje i trajanje cvora
794double SchedulingEvalOp::NodeLevel(int set, int node)
795{ double value,level;
796 int succ,i,next;
797 if(Level[set][node] > -1) // ako je vec izracunato
798 return Level[set][node];
799 if(Precedence[node][1] == 0) // ako nema sljedbenika
800 return Duration[set][node];
801 succ = (int)Precedence[node][1]; // koliko sljedbenika
802 next = (int)Precedence[node][2]; // prvi sljedbenik
803 level = NodeLevel(set,next) + Duration[set][node]; // level zbog prvog sljedbenika
804 for(i=1; i<succ; i++)
805 { next = (int)Precedence[node][i+2];
806 value = NodeLevel(set,next) + Duration[set][node];
807 if(value > level)
808 level = value;
809 }
810 return level;
811}
812
813
814// racuna vremenski i drugacije ovisne terminale
815void SchedulingEvalOp::CalcTimedTerminals(uint &nNiz, uint &nPoslova, uint &nJob, double &dClock, \
816 uint nMachine, uint nMachines)
817{ uint i,j;
818 for(i=nJob; i<nPoslova; i++) // racunamo vrem. ovisne terminale, samo za nerasporedjene poslove
819 { j = pIndex[i]; // 'pravi' indeks posla
820 if(m_Environment == UNIFORM)
821 { Evaluator.m_dTermValuesArray[T_SPD][j] = Speed[nNiz][nMachine]; // brzina stroja (neovisna o poslu)
822 pSlack[j] = Deadline[nNiz][j] - (dClock + Duration[nNiz][j]);
823 pSlackSpeed[j] = Deadline[nNiz][j] - (dClock + Duration[nNiz][j] * Speed[nNiz][nMachine]);
824 Evaluator.m_dTermValuesArray[T_L][j] = POS(dClock + Duration[nNiz][j]*Speed[nNiz][nMachine]- Deadline[nNiz][j]); // kasnjenje
825 }
826 if(m_Environment == UNRELATED)
827 { Evaluator.m_dTermValuesArray[T_PAT][j] = POS(MachineReady[(uint)PTimeMinMachine[nNiz][j]][0] - dClock);
828 Evaluator.m_dTermValuesArray[T_MR][j] = POS(MachineReady[nMachine][0] - dClock);
829 Evaluator.m_dTermValuesArray[T_pt][j] = Duration[nNiz][j*nMachines + nMachine];
830 Evaluator.m_dTermValuesArray[T_age][j] = POS(dClock - Ready[nNiz][j]);
831 pSlack[j] = Deadline[nNiz][j] - (dClock + Duration[nNiz][j*nMachines + nMachine]);
832 Evaluator.m_dTermValuesArray[T_L][j] = POS(dClock + Duration[nNiz][j*nMachines + nMachine]- Deadline[nNiz][j]); // kasnjenje
833 }
834 if(m_Environment == SINGLE)
835 { pSlack[j] = Deadline[nNiz][j] - (dClock + Duration[nNiz][j]);
836 Evaluator.m_dTermValuesArray[T_L][j] = POS(dClock + Duration[nNiz][j]- Deadline[nNiz][j]); // kasnjenje
837 //Evaluator.m_dTermValuesArray[T_L][j] = POS(dClock - Deadline[nNiz][j]); // kasnjenje
838 }
839
840 // 'zajednicki' terminali
841 Evaluator.m_dTermValuesArray[T_CLK][j] = dClock;
842 pArrival[j] = POS(Ready[nNiz][j] - dClock); // pozitivna vrijednost dolaska
843 Evaluator.m_dTermValuesArray[T_AR][j] = pArrival[j]; // za koliko dolazi
844 if(pSlack[j]<0) pSlack[j] = 0; // uzimamo samo pozitivni slack?
845 if(pSlackSpeed[j]<0) pSlackSpeed[j] = 0; // uzimamo samo pozitivni slack?
846 // pokazalo se malo boljim!
847 Evaluator.m_dTermValuesArray[T_SL][j] = pSlack[j]; // slack
848 Evaluator.m_dTermValuesArray[T_SLs][j] = pSlackSpeed[j]; // slack sa brzinom
849
850 if(m_Environment != SINGLE) // za SINGLE se racunaju u glavnoj funkciji
851 { // trajanje postavljanja u odnosu na zadnji posao na zadanom stroju
852 Evaluator.m_dTermValuesArray[T_STP][j] = Setup[pLastJob[nMachine]][j];
853 Evaluator.m_dTermValuesArray[T_Sav][j] = pSetupAvg[pLastJob[nMachine]]; // prosjecno t.p.
854 }
855 }
856}
857
858
859// obrada za SINGLE okruzenje
860void SchedulingEvalOp::EvaluateSingle(double &dRawFitness)
861{
862 double dClock, dRez, dSetFitness, dAvgWeights, dAvgDuration, dAvgDueDate;
863 double dLateness, dTotalLateness=0, dTardiness, dTotalTardiness=0;
864 double dNwt, dTotalNwt=0, dBest, dSPr, dSDr;
865 unsigned int nPoslova,nNiz,nJob,i,j,k,index,nLateJobs,nTotalLateJobs=0,nNr;
866 unsigned int nLastJob,nOdabrani;
867
868 dRawFitness=0;
869
870// vrtimo sve skupove
871 for(nNiz=0; nNiz<sets; nNiz++)
872 {
873 // ili samo jedan primjer ako je zadan
874 if(m_primjer > 0 && m_primjer != (nNiz + 1))
875 continue;
876
877 nNr = nPoslova = (int) N.Get(nNiz);
878 // preliminarna ispitivanja
879 // radimo li stochastic sampling
880 if(m_stsampling)
881 if(pSamples[nNiz] == false)
882 continue; // jednostavno preskocimo taj test case
883 // gleda li se limited error fitness
884 if(m_LEF)
885 { if(dRawFitness > m_LEFVal)
886 break; // prekid ispitivanja
887 }
888 if(m_constrained) // ima li ogranicenja
889 ReadConstraints(Constraints,nNiz,nPoslova,Precedence);
890 if(m_setup) // trajanja postavljanja
891 MakeSetup(Duration,nNiz,nPoslova,m_setup_faktor,Setup);
892 // postavljanje pocetnih vrijednosti za pojedini skup
893 nLateJobs = 0;
894 dLateness = 0;
895 dTardiness = 0;
896 dNwt = 0;
897 dClock = 0; dSetFitness = 0;
898 nLastJob = nPoslova;
899 dAvgDueDate = 0;
900 for(i=0; i<nPoslova; i++)
901 { dAvgDueDate += Deadline[nNiz][i];
902 pRasporedjen[i] = false; // svi nerasporedjeni
903 pIndex[i] = i; // inicijalni poredak
904 }
905 dAvgDueDate /= nPoslova;
906 // postavljanje pocetnih vrijednosti terminala
907 Evaluator.m_pTermValues[T_N] = N.Get(nNiz);
908 dSPr = Evaluator.m_pTermValues[T_SP] = SP.Get(nNiz);
909 dSDr = Evaluator.m_pTermValues[T_SD] = SD.Get(nNiz);
910 Evaluator.SetTermArraySize(nPoslova); // koliko poslova u skupu - za vektorsku evaluaciju
911 Evaluator.pIndex = pIndex; // polje indeksa poslova
912 Evaluator.m_iOffset = 0; // indeks prvog nerasporedjenog
913 for(i=0; i<nPoslova; i++)
914 { Evaluator.m_dTermValuesArray[T_N][i] = N.data[nNiz][0];
915 Evaluator.m_dTermValuesArray[T_SP][i] = SP.data[nNiz][0];
916 Evaluator.m_dTermValuesArray[T_SD][i] = SD.data[nNiz][0];
917 Evaluator.m_dTermValuesArray[T_SC][i] = Precedence[i][1]; // broj sljedbenika
918 Evaluator.m_dTermValuesArray[T_TF][i] = 1 - dAvgDueDate / SP[nNiz][0];
919 }
920 memcpy(Evaluator.m_dTermValuesArray[T_pt], Duration.data[nNiz], nPoslova*sizeof(double));
921 memcpy(Evaluator.m_dTermValuesArray[T_dd], Deadline.data[nNiz], nPoslova*sizeof(double));
922 memcpy(Evaluator.m_dTermValuesArray[T_w], WeightT.data[nNiz], nPoslova*sizeof(double));
923 memcpy(Evaluator.m_dTermValuesArray[T_LVL], Level[nNiz], nPoslova*sizeof(double));
924
926// ako u terminalima ima vremenski ovisnih, moramo raditi posao po posao
927// vektorska evaluacija!
928 for(nJob=0; nJob<nPoslova; nJob++) // rasporedjujemo svaki posao unutar skupa
929 { for(i=nJob; i<nPoslova; i++) // racunamo vrem. ovisne terminale, samo za nerasporedjene poslove
930 { j = pIndex[i];
931 Evaluator.m_dTermValuesArray[T_SPr][j] = dSPr; // suma trajanja preostalih
932 Evaluator.m_dTermValuesArray[T_Nr][j] = nNr; // broj preostalih
933 Evaluator.m_dTermValuesArray[T_STP][j] = Setup[nLastJob][j]; // trajanje postavljanja
934 Evaluator.m_dTermValuesArray[T_Sav][j] = pSetupAvg[nLastJob]; // prosjecno t.p.
935 //Evaluator.m_dTermValuesArray[T_SD][j] = dSDr; // proba
936 }
937 Evaluator.m_iPosition = -1;
938 Evaluator.m_iOffset = nJob; // od kojeg posla pocinjemo - prethodni su vec rasporedjeni!
939
940 if(m_dynamic) // dinamicka okolina; + uzeta u obzir eventualna ogranicenja
941 { unsigned int raspolozivi = nJob, prvi = nJob;
942 unsigned int najkraci; // najkraci raspolozivi
943 // trebamo pronaci prvog raspolozivog bez nezavrsenih prethodnika
944 for(; Precedence[pIndex[raspolozivi]][0] > 0; raspolozivi++) NULL;
945 double kada = Ready[nNiz][pIndex[raspolozivi]]; // pocetno vrijeme
946 double najdulje = 0, najkrace = 0;
947 for( ; raspolozivi < nPoslova; raspolozivi++) // koji je 'najstariji'?
948 { k = pIndex[raspolozivi];
949 if(Ready.data[nNiz][k] < kada && Precedence[k][0] == 0) // gledamo najblize vrijeme dolaska
950 { kada = Ready.data[nNiz][k];
951 prvi = raspolozivi;
952 }
953 }
954 if(kada > dClock) // nema raspolozivih
955 { dClock = kada; // sat postavimo na najblize vrijeme dolaska
956 }
957 // trebamo izracunati nove vrijednosti vremenski ovisnih terminala!
958 CalcTimedTerminals(nNiz,nPoslova,nJob,dClock);
959 // pronadjimo najduljeg i najkraceg raspolozivog
960 najdulje = najkrace = Duration[nNiz][pIndex[prvi]];
961 najkraci = prvi;
962 for(i=nJob; i<nPoslova; i++)
963 { k = pIndex[i];
964 if(dClock < Ready[nNiz][k] || Precedence[k][0] > 0)
965 continue;
966 if(Duration[nNiz][k] < najkrace) // najkrace
967 { najkrace = Duration[nNiz][k];
968 najkraci = i;
969 }
970 }
971 // sad pogledamo najduljega koji pocinje <= zavrsetka najkraceg raspolozivog
972 for(i=nJob; i<nPoslova; i++)
973 { k = pIndex[i];
974 if(Precedence[k][0] > 0)
975 continue;
976 if(Duration[nNiz][k] > najdulje && Ready[nNiz][k] <= (dClock+najkrace)) // gledamo najdulje trajanje
977 najdulje = Duration[nNiz][k];
978 }
979 // sada je (dClock + najkrace + najdulje) limit za gledanje u buducnost!
980
981 Evaluator.evaluate_array(pVrijednosti); // ocijenimo sve
982 // prva verzija (kompliciranija)
983 // gledat cemo sve cije vrijeme dolaska je prije zavrsetka najduljeg trenutno raspolozivog
984 // MODIFIKACIJA (09.09.): gledamo sve koji mogu poceti prije zavrsetka najkraceg + trajanje do tada spremnog najduljeg!
985 // (pronadjemo najduljeg koji moze poceti prije zavrsetka najkraceg)
986 // tada: ako se prije odabranoga moze ugurati neki kraci, odaberemo najboljeg kraceg
987 //kada = najdulje + 1; // poc. vrijednost za dolazak trenutno odabranog
988 kada = najkrace + najdulje;
989 dBest = pVrijednosti[pIndex[najkraci]]; // poc. vrijednost za usporedbu
990 nOdabrani = najkraci;
991 for(i=nJob; i<nPoslova; i++) // trazimo najbolju vrijednost unutar < (dClock + kada)
992 { k = pIndex[i];
993 if(Precedence[k][0] == 0 && (pVrijednosti[k] < dBest) && (Ready[nNiz][k] < dClock + kada))
994 { dBest = pVrijednosti[k];
995 nOdabrani = i;
996 }
997 }
998 kada = Ready[nNiz][pIndex[nOdabrani]] - dClock; // za koliko pocinje odabrani?
999 if(kada >= najkrace) // ako stane jos barem jedan, odaberimo najbolji koji ce zavrsiti prije pocetka odabranog
1000 { dBest = pVrijednosti[pIndex[najkraci]]; // poc. vrijednost za usporedbu
1001 nOdabrani = najkraci;
1002 for(i=nJob; i<nPoslova; i++)
1003 { k = pIndex[i];
1004 if(Precedence[k][0] == 0 && (Ready[nNiz][k] + Duration[nNiz][k] <= dClock + kada) \
1005 && pVrijednosti[k] < dBest \
1006 && Ready[nNiz][k] - dClock < najkrace) // pocinje prije zavrsetka najkraceg!
1007 { dBest = pVrijednosti[k];
1008 nOdabrani = i;
1009 }
1010 }
1011 kada = Ready[nNiz][pIndex[nOdabrani]] - dClock; // novi odabrani
1012 }
1013
1014/* // druga verzija (jednostavnija)
1015 // samo gledamo najboljega koji moze poceti prije zavrsetka najkraceg raspolozivog
1016 dBest = pVrijednosti[pIndex[najkraci]]; // poc. vrijednost za usporedbu
1017 nOdabrani = najkraci;
1018 for(i=nJob; i<nPoslova; i++) // trazimo najbolju vrijednost unutar < (dClock + najkrace)
1019 { if((pVrijednosti[pIndex[i]] < dBest) && (Ready[nNiz][pIndex[i]] < dClock + najkrace) \
1020 && Precedence[pIndex[i]][0] == 0)
1021 { dBest = pVrijednosti[pIndex[i]];
1022 nOdabrani = i;
1023 }
1024 }
1025 kada = Ready[nNiz][pIndex[nOdabrani]] - dClock; // za koliko pocinje odabrani?
1026*/
1027 // redovni nastavak (iza 1. i 2. verzije)
1028 if(kada > 0) // odabrali smo cekati
1029 dClock += kada; // ili: dClock = Ready[nNiz][pIndex[nOdabrani]];
1030 } // endif - m_dynamic
1031
1032 else // staticki
1033 { CalcTimedTerminals(nNiz,nPoslova,nJob,dClock);
1034 nOdabrani = nJob;
1035 if(m_constrained) // trazimo prvi bez prethodnika
1036 for(; Precedence[pIndex[nOdabrani]][0] > 0; nOdabrani++) NULL;
1037 Evaluator.evaluate_array(pVrijednosti); // ocijenimo sve
1038 dBest = pVrijednosti[pIndex[nOdabrani]]; // pretpostavimo da je neki najbolji
1039 for(i=nJob; i<nPoslova; i++) // pa pogledamo ostale
1040 { // trazimo najmanju vrijednost
1041 if(pVrijednosti[pIndex[i]] < dBest && Precedence[pIndex[i]][0] == 0) // je li to najbolja vrijednost?
1042 { dBest = pVrijednosti[pIndex[i]];
1043 nOdabrani = i;
1044 }
1045 }
1046 }
1047
1048 // vrijednost pIndex[nOdabrani] je indeks posla koji ide sljedeci
1049 // gledamo nOdabrani kao rezultat; zamijenimo nJob-ti i odabrani u polju indeksa
1050 i = pIndex[nJob];
1051 pIndex[nJob] = pIndex[nOdabrani];
1052 pIndex[nOdabrani] = i;
1053 pRasporedjen[pIndex[nJob]] = true;
1054 dClock += Duration[nNiz][pIndex[nJob]]; // update vremena
1055 dSPr -= Duration[nNiz][pIndex[nJob]]; // update trajanja preostalih
1056 dSDr -= Deadline[nNiz][pIndex[nJob]]; // update deadlinea
1057 nNr--; // update broja preostalih
1058 if(m_constrained) // smanjimo broj prethodnika svim sljedbenicima odabranog posla
1059 for(i=0; i<Precedence[pIndex[nJob]][1]; i++)
1060 { j = (int) Precedence[pIndex[nJob]][i+2];
1061 Precedence[j][0] -= 1;
1062 }
1063 if(m_setup) // trajanje postavljanja
1064 { dClock += Setup[nLastJob][pIndex[nJob]];
1065 nLastJob = pIndex[nJob]; // sljedeci prethodni posao
1066 }
1067 Schedule[nNiz][nJob] = pIndex[nJob]; // zapisemo u raspored
1068 } // kraj petlje koja vrti poslove u skupu
1069
1070 // racunanje raznih kriterija za trenutni skup
1071 { if(m_Evaluation)
1072 { for(nJob=nPoslova ; nJob < this->max_jobs; nJob++)
1073 Schedule[nNiz][nJob] = 0; // ostalo nule
1074 }
1075 // odredimo fitnes kriterij - sve moguce funkcije
1076 dClock = 0; nLastJob = nPoslova; dAvgWeights = dAvgDuration = 0;
1077 for(nJob = 0; nJob<nPoslova; nJob++)
1078 { index = pIndex[nJob];
1079 dAvgWeights += WeightT[nNiz][index];
1080 dAvgDuration += Duration[nNiz][index];
1081 if(m_dynamic && dClock < Ready[nNiz][index]) // ako jos nije raspoloziv
1082 dClock = Ready[nNiz][index];
1083 if(m_setup)
1084 dClock += Setup[nLastJob][index];
1085 nLastJob = index;
1086 dClock += Duration.data[nNiz][index]; // update vremena
1087 dRez = dClock - Deadline.Get(nNiz,index); // kasnjenje
1088 dLateness += dRez*WeightT.data[nNiz][index]; // tezinsko kasnjenje
1089 if(dRez > 0) dTardiness += dRez*WeightT.data[nNiz][index]; // tezinska zakasnjelost
1090 if(dRez > 0) nLateJobs ++; // kao broj zakasnjelih poslova
1091 if(dRez > 0) dNwt += WeightN.data[nNiz][index]; // tezinski broj zakasnjelih
1092 }
1093 // normiranje fitnesa ovisno o broju poslova - dodano 27.07.
1094 // promijenjeno (valjda konacno) 04.09.
1095 dAvgWeights /= nPoslova; // prosjecni tezinski faktor skupa
1096 dAvgDuration /= nPoslova;
1097 dTardiness /= (nPoslova * dAvgWeights * dAvgDuration);
1098 dNwt /= (nPoslova * dAvgWeights);
1099 double Cmax = dClock / (nPoslova * dAvgDuration);
1100 switch(m_fitness) // sto uzimamo kao fitnes?
1101 { case Twt: dRawFitness += dTardiness; break;
1102 case Nwt: dRawFitness += dNwt; break;
1103 case TwtCmax: dRawFitness += dTardiness * Cmax; break;
1104 case NwtCmax: dRawFitness += dNwt * Cmax; break;
1105 default: exit(1);
1106 }
1107 nTotalLateJobs += nLateJobs;
1108 dTotalNwt += dNwt;
1109 dTotalLateness += dLateness;
1110 dTotalTardiness += dTardiness;
1111 Fitness[nNiz][Twt] = dTardiness;
1112 Fitness[nNiz][Nwt] = dNwt;
1113 Fitness[nNiz][FTwt] = 0; // zasada
1114 Fitness[nNiz][ETwt] = 0;
1115 }
1116 }
1117// kraj petlje koja vrti skupove poslova
1118 Fitness.data[sets][Twt] = dTotalTardiness;
1119 Fitness.data[sets][Nwt] = dTotalNwt;
1120}
1121
1122
1123
1124// obrada za UNIFORM okruzenje
1125// implementirani terminali: pt,w,dd,SPD,SL,Sls,Msm,STP,Sav,Nr,SP
1126void SchedulingEvalOp::EvaluateUniform(double &dRawFitness)
1127{
1128 double dClock, dRez, dSetFitness, dAvgWeights, dAvgDuration;
1129 double dLateness, dTotalLateness=0, dTardiness, dTotalTardiness=0, dTotalFwt=0;
1130 double dNwt, dTotalNwt=0, dBest, dSPr, dMsum, dSetupTime, dFwt, dCmax, dTotalCmax=0;
1131 unsigned int nPoslova,nNiz,nJob,i,j,k,index,nLateJobs,nTotalLateJobs=0,nNr;
1132 unsigned int nLastJob,nMachines,nOdabrani,nMachine;
1133
1134 dRawFitness=0;
1135
1136// vrtimo sve skupove
1137 for(nNiz=0; nNiz<sets; nNiz++)
1138 { nNr = nPoslova = (int) N.Get(nNiz);
1139 // preliminarna ispitivanja
1140 // radimo li stochastic sampling
1141 if(m_stsampling)
1142 if(pSamples[nNiz] == false)
1143 continue; // jednostavno preskocimo taj test case
1144 // gleda li se limited error fitness
1145 if(m_LEF)
1146 { if(dRawFitness > m_LEFVal)
1147 break; // prekid ispitivanja
1148 }
1149 if(m_constrained) // ima li ogranicenja
1150 ReadConstraints(Constraints,nNiz,nPoslova,Precedence);
1151 if(m_setup) // trajanja postavljanja
1152 MakeSetup(Duration,nNiz,nPoslova,m_setup_faktor,Setup);
1153 // postavljanje pocetnih vrijednosti za pojedini skup
1154 nLateJobs = 0;
1155 dLateness = 0;
1156 dTardiness = 0;
1157 dNwt = 0;
1158 dFwt = 0;
1159 dClock = 0; dSetFitness = 0;
1160 nLastJob = nPoslova;
1161 for(i=0; i<nPoslova; i++)
1162 { pRasporedjen[i] = false; // svi nerasporedjeni
1163 pIndex[i] = i; // inicijalni poredak
1164 }
1165 nMachines = (uint) Machines[nNiz][0];
1166 dMsum = 0;
1167 for(j=0; j<nMachines; j++)
1168 { MachineReady[j][0] = 0; // pocetno vrijeme raspolozivosti strojeva
1169 dMsum += 1/Speed[nNiz][j]; // suma brzina svih strojeva
1170 pLastJob[j] = nPoslova; // pocetni prethodni posao
1171 }
1172 // postavljanje pocetnih vrijednosti terminala
1173 Evaluator.m_pTermValues[T_N] = N.Get(nNiz);
1174 dSPr = Evaluator.m_pTermValues[T_SP] = SP.Get(nNiz);
1175 Evaluator.m_pTermValues[T_SD] = SD.Get(nNiz);
1176 Evaluator.SetTermArraySize(nPoslova); // koliko poslova u skupu - za vektorsku evaluaciju
1177 Evaluator.pIndex = pIndex; // polje indeksa poslova
1178 Evaluator.m_iOffset = 0; // indeks prvog nerasporedjenog
1179 for(i=0; i<nPoslova; i++)
1180 { Evaluator.m_dTermValuesArray[T_N][i] = N.data[nNiz][0];
1181 Evaluator.m_dTermValuesArray[T_SP][i] = SP.data[nNiz][0];
1182 Evaluator.m_dTermValuesArray[T_SD][i] = SD.data[nNiz][0];
1183 Evaluator.m_dTermValuesArray[T_SC][i] = Precedence[i][1]; // broj sljedbenika
1184 }
1185 memcpy(Evaluator.m_dTermValuesArray[T_pt], Duration.data[nNiz], nPoslova*sizeof(double));
1186 memcpy(Evaluator.m_dTermValuesArray[T_dd], Deadline.data[nNiz], nPoslova*sizeof(double));
1187 memcpy(Evaluator.m_dTermValuesArray[T_w], WeightT.data[nNiz], nPoslova*sizeof(double));
1188 memcpy(Evaluator.m_dTermValuesArray[T_LVL], Level[nNiz], nPoslova*sizeof(double));
1189
1191// ako u terminalima ima vremenski ovisnih, moramo raditi posao po posao
1192// vektorska evaluacija!
1193 for(nJob=0; nJob<nPoslova; nJob++) // rasporedjujemo svaki posao unutar skupa
1194 { for(i=nJob; i<nPoslova; i++) // racunamo nove terminale samo za nerasporedjene
1195 { j = pIndex[i];
1196 Evaluator.m_dTermValuesArray[T_SPr][j] = dSPr; // suma trajanja preostalih
1197 Evaluator.m_dTermValuesArray[T_Nr][j] = nNr; // broj preostalih
1198 }
1199 Evaluator.m_iPosition = -1;
1200 Evaluator.m_iOffset = nJob; // od kojeg posla pocinjemo - prethodni su vec rasporedjeni!
1201
1202 if(m_dynamic) // dinamicka okolina;
1203 { // trebamo naci prvi raspolozivi stroj i prvi raspolozivi posao
1204 unsigned int raspolozivi = nJob, prvi = nJob;
1205 // trebamo pronaci prvog raspolozivog bez nezavrsenih prethodnika
1206 for(; Precedence[pIndex[raspolozivi]][0] > 0; raspolozivi++) NULL;
1207 double kada = Ready[nNiz][pIndex[raspolozivi]]; // pocetno vrijeme
1208 for( ; raspolozivi < nPoslova; raspolozivi++) // koji je 'najstariji'?
1209 { k = pIndex[raspolozivi];
1210 if(Ready.data[nNiz][k] < kada && Precedence[k][0] == 0) // gledamo najblize vrijeme dolaska
1211 { kada = Ready.data[nNiz][k];
1212 prvi = raspolozivi;
1213 }
1214 } // sada je pIndex[prvi] prvi raspolozivi posao
1215 nMachine = 0;
1216 for(i=0; i<nMachines; i++)
1217 if(MachineReady[i][0] < MachineReady[nMachine][0])
1218 nMachine = i;
1219 // nMachine je prvi raspolozivi stroj
1220 if(kada < MachineReady[nMachine][0])
1221 kada = MachineReady[nMachine][0];
1222 if(kada > dClock) // prvo vrijeme kad imamo raspoloziv i stroj i posao
1223 dClock = kada; // sat postavimo na najblize vrijeme raspolozivosti
1224 // trebamo izracunati nove vrijednosti vremenski ovisnih terminala!
1225 CalcTimedTerminals(nNiz,nPoslova,nJob,dClock,nMachine);
1226
1227 Evaluator.evaluate_array(pVrijednosti); // ocijenimo sve
1228 // samo gledamo najboljega koji moze poceti
1229 dBest = pVrijednosti[pIndex[prvi]]; // poc. vrijednost za usporedbu
1230 nOdabrani = prvi;
1231 for(i=nJob; i<nPoslova; i++)
1232 { if((pVrijednosti[pIndex[i]] < dBest) && Precedence[pIndex[i]][0] == 0 \
1233 && Ready[nNiz][pIndex[i]] <= dClock)
1234 { dBest = pVrijednosti[pIndex[i]];
1235 nOdabrani = i;
1236 }
1237 }
1238 } // endif - m_dynamic
1239 else // staticki
1240 { // pronadjemo prvi raspolozivi stroj
1241 nMachine = 0;
1242 for(i=1; i<nMachines; i++)
1243 if(MachineReady[i][0] < MachineReady[nMachine][0])
1244 nMachine = i;
1245 dClock = MachineReady[nMachine][0]; // to je trenutno vrijeme
1246 CalcTimedTerminals(nNiz,nPoslova,nJob,dClock,nMachine);
1247 nOdabrani = nJob;
1248 if(m_constrained) // trazimo prvi bez prethodnika
1249 for(; Precedence[pIndex[nOdabrani]][0] > 0; nOdabrani++) NULL;
1250 Evaluator.evaluate_array(pVrijednosti); // ocijenimo sve
1251 dBest = pVrijednosti[pIndex[nOdabrani]]; // pretpostavimo da je neki najbolji
1252 for(i=nJob; i<nPoslova; i++) // pa pogledamo ostale
1253 { // trazimo najmanju vrijednost
1254 if(pVrijednosti[pIndex[i]] < dBest && Precedence[pIndex[i]][0] == 0) // je li to najbolja vrijednost?
1255 { dBest = pVrijednosti[pIndex[i]];
1256 nOdabrani = i;
1257 }
1258 }
1259 }
1260
1261 // vrijednost pIndex[nOdabrani] je indeks posla koji ide sljedeci, na stroju nMachine
1262 // gledamo nOdabrani kao rezultat; zamijenimo nJob-ti i odabrani u polju indeksa
1263 i = pIndex[nJob];
1264 pIndex[nJob] = pIndex[nOdabrani];
1265 pIndex[nOdabrani] = i;
1266 pRasporedjen[pIndex[nJob]] = true;
1267
1268 //dSPr -= Duration.data[nNiz][pIndex[nJob]]; // update trajanja preostalih
1269 dSPr -= Duration.data[nNiz][pIndex[nJob]]*dMsum; // zapravo bi trebalo ovako!
1270 nNr--; // update broja preostalih
1271 if(m_setup) // trajanje postavljanja
1272 { dSetupTime = Setup[pLastJob[nMachine]][pIndex[nJob]];
1273 pLastJob[nMachine] = pIndex[nJob]; // sljedeci prethodni posao
1274 }
1275 else dSetupTime = 0;
1276 if(m_constrained) // smanjimo broj prethodnika svim sljedbenicima odabranog posla
1277 for(i=0; i<Precedence[pIndex[nJob]][1]; i++)
1278 { j = (int) Precedence[pIndex[nJob]][i+2];
1279 Precedence[j][0] -= 1;
1280 }
1281 MachineReady[nMachine][0] = dClock + dSetupTime + \
1282 Duration[nNiz][pIndex[nJob]] * Speed[nNiz][nMachine];
1283 // odredimo sljedeci element u matrici rasporeda (indeks stroja je tisucica)
1284 Schedule[nNiz][nJob] = pIndex[nJob] + nMachine * 1000;
1285 } // kraj petlje koja vrti poslove u skupu
1286 // racunanje raznih kriterija za trenutni skup
1287 { if(m_Evaluation)
1288 { for(nJob=nPoslova ; nJob < this->max_jobs; nJob++)
1289 Schedule[nNiz][nJob] = 0; // ostalo nule
1290 }
1291 // odredimo fitnes kriterij - sve moguce funkcije
1292 dClock = 0; nLastJob = nPoslova; dAvgWeights = 0;
1293 for(i=0; i<nMachines; i++)
1294 { MachineReady[i][0] = 0;
1295 pLastJob[i] = nPoslova;
1296 }
1297 for(nJob = 0; nJob<nPoslova; nJob++)
1298 { index = (int) Schedule[nNiz][nJob];
1299 nMachine = index / 1000; // na kojem stroju
1300 index = index % 1000; // koji posao
1301 dAvgWeights += WeightT[nNiz][index];
1302 if(m_dynamic && MachineReady[nMachine][0] < Ready[nNiz][index]) // ako posao jos nije raspoloziv
1303 MachineReady[nMachine][0] = Ready[nNiz][index];
1304 MachineReady[nMachine][0] += Duration[nNiz][index] * Speed[nNiz][nMachine];
1305 if(m_setup)
1306 MachineReady[nMachine][0] += Setup[pLastJob[nMachine]][index];
1307 pLastJob[nMachine] = index;
1308 dRez = MachineReady[nMachine][0] - Deadline.Get(nNiz,index); // kasnjenje
1309 dLateness += dRez*WeightT.data[nNiz][index]; // tezinsko kasnjenje
1310 if(dRez > 0) dTardiness += dRez*WeightT.data[nNiz][index]; // tezinska zakasnjelost
1311 if(dRez > 0) nLateJobs ++; // kao broj zakasnjelih poslova
1312 if(dRez > 0) dNwt += WeightN.data[nNiz][index]; // tezinski broj zakasnjelih
1313 dFwt = (MachineReady[nMachine][0] - Ready[nNiz][index]) * WeightT[nNiz][index]; // tezinsko protjecanje
1314 }
1315 dCmax = 0; // odredjivanje Cmax
1316 for(i=0; i<nMachines; i++)
1317 if(MachineReady[i][0] > dCmax)
1318 dCmax = MachineReady[i][0];
1319 // normiranje fitnesa ovisno o broju poslova - dodano 27.07.
1320 // i o prosjecnom trajanju - dodano 15.09.
1321 dAvgDuration = SP[nNiz][0] / nPoslova; // prosjecno trajanje posla
1322 dAvgWeights /= nPoslova; // prosjecni tezinski faktor skupa
1323 dTardiness /= (nPoslova * dAvgWeights * dAvgDuration);
1324 dNwt /= (nPoslova * dAvgWeights);
1325 dFwt /= (nPoslova * dAvgWeights * dAvgDuration);
1326 dCmax /= (nPoslova * dAvgDuration);
1327 switch(m_fitness) // sto uzimamo kao fitnes?
1328 { case Twt: dRawFitness += dTardiness; break;
1329 case Nwt: dRawFitness += dNwt; break;
1330 case Fwt: dRawFitness += dFwt; break;
1331 case Cmax: dRawFitness += dCmax; break;
1332 default: throw;
1333 }
1334 nTotalLateJobs += nLateJobs;
1335 dTotalNwt += dNwt;
1336 dTotalFwt += dFwt;
1337 dTotalLateness += dLateness;
1338 dTotalTardiness += dTardiness;
1339 dTotalCmax += dCmax;
1340 Fitness[nNiz][Twt] = dTardiness;
1341 Fitness[nNiz][Nwt] = dNwt;
1342 Fitness[nNiz][FTwt] = 0; // zasada
1343 Fitness[nNiz][ETwt] = 0;
1344 Fitness[nNiz][Fwt] = dFwt;
1345 Fitness[nNiz][Cmax] = dCmax;
1346 }
1347
1348 } // kraj petlje koja vrti skupove poslova
1349 Fitness[sets][Twt] = dTotalTardiness;
1350 Fitness[sets][Nwt] = dTotalNwt;
1351 Fitness[sets][FTwt] = 0;
1352 Fitness[sets][ETwt] = 0;
1353 Fitness[sets][Fwt] = dTotalFwt;
1354 Fitness[sets][Cmax] = dTotalCmax;
1355}
1356
1357
1358
1359
1360// obrada za UNRELATED okruzenje
1361// implementirani terminali: w, dd, pt, SL, pmin, pavg, PAT, MR, age
1362// ne koristimo u dinamickom: N, Nr, SP, SPr, SD
1363void SchedulingEvalOp::EvaluateUnrelated(double &dRawFitness)
1364{
1365 double dClock, dRez, dSetFitness, dAvgWeights, dCmax, dTotalCmax=0;
1366 double dLateness, dTotalLateness=0, dTardiness, dTotalTardiness=0;
1367 double dEarliness, dTotalEarliness = 0;
1368 double dEarlinessTardiness, dTotalEarlinessTardiness = 0;
1369 double dTmax, dTotalTmax = 0;
1370 double dFmax, dTotalFmax = 0;
1371 double dMus, dTotalMus = 0;
1372 double dCw, dTotalCw =0;
1373 vector<double> machineUseage;
1374 double dNwt, dTotalNwt=0, dBest, dSPr, dSetupTime, dFwt, dTotalFwt=0;
1375 unsigned int nPoslova,nNiz,nJob,i,j,k,index,nLateJobs,nTotalLateJobs=0,nNr;
1376 unsigned int nLastJob,nMachines,nOdabrani,nMachine;
1377 double dAvgWeightsC;
1378 double dAvgWeightsE;
1379
1380
1381 dRawFitness=0;
1382
1383// vrtimo sve skupove
1384 for(nNiz=0; nNiz<sets; nNiz++)
1385 { nNr = nPoslova = (int) N.Get(nNiz);
1386 // preliminarna ispitivanja
1387 // radimo li stochastic sampling
1388 if(m_stsampling)
1389 if(pSamples[nNiz] == false)
1390 continue; // jednostavno preskocimo taj test case
1391 // gleda li se limited error fitness
1392 if(m_LEF)
1393 { if(dRawFitness > m_LEFVal)
1394 break; // prekid ispitivanja
1395 }
1396 if(m_constrained) // ima li ogranicenja
1397 ReadConstraints(Constraints,nNiz,nPoslova,Precedence);
1398 if(m_setup) // trajanja postavljanja
1399 MakeSetup(Duration,nNiz,nPoslova,m_setup_faktor,Setup);
1400 // postavljanje pocetnih vrijednosti za pojedini skup
1401 nLateJobs = 0;
1402 dLateness = 0;
1403 dTardiness = 0;
1404 dEarliness = 0;
1405 dMus = 0;
1406 dNwt = 0;
1407 dCw = 0;
1408 dFwt = 0;
1409 dFmax =0;
1410 dTmax =0;
1411 dClock = 0; dSetFitness = 0;
1412 dAvgWeightsC = 0;
1413 dAvgWeightsE = 0;
1414 nLastJob = nPoslova;
1415 for(i=0; i<nPoslova; i++)
1416 { pRasporedjen[i] = false; // svi nerasporedjeni
1417 // procitamo niz indeksa poslova sortiran po dolasku
1418 pIndex[i] = (uint) SortedReady[nNiz][i]; // inicijalni poredak
1419 }
1420
1421 nMachines = (uint) Machines[nNiz][0];
1422
1423 machineUseage.clear();
1424 for(int kk=0; kk<nMachines; kk++){
1425 machineUseage.push_back(0);
1426 }
1427
1428
1429 for(j=0; j<nMachines; j++)
1430 { MachineReady[j][0] = 0; // pocetno vrijeme raspolozivosti strojeva
1431 pLastJob[j] = nPoslova; // pocetni prethodni posao
1432 }
1433
1434 // postavljanje pocetnih vrijednosti terminala
1435 dSPr = SP.Get(nNiz);
1436 Evaluator.SetTermArraySize(nPoslova); // koliko poslova u skupu - za vektorsku evaluaciju
1437 Evaluator.pIndex = pIndex; // polje indeksa poslova
1438 Evaluator.m_iOffset = 0; // indeks prvog nerasporedjenog
1439 Evaluator.m_iEnd = 1; // pocetna vrijednost zadnjeg posla koji se uzima u o obzir
1440 for(i=0; i<nPoslova; i++)
1441 { Evaluator.m_dTermValuesArray[T_N][i] = N.data[nNiz][0];
1442 Evaluator.m_dTermValuesArray[T_SP][i] = SP.data[nNiz][0];
1443 Evaluator.m_dTermValuesArray[T_SD][i] = SD.data[nNiz][0];
1444 Evaluator.m_dTermValuesArray[T_SC][i] = Precedence[i][1]; // broj sljedbenika
1445 // najkrace trajanje izvodjenja posla
1446 Evaluator.m_dTermValuesArray[T_pmin][i] = Duration[nNiz][i*nMachines + (uint)PTimeMinMachine[nNiz][i]];
1447 }
1448 memcpy(Evaluator.m_dTermValuesArray[T_dd], Deadline.data[nNiz], nPoslova*sizeof(double));
1449 memcpy(Evaluator.m_dTermValuesArray[T_w], WeightT.data[nNiz], nPoslova*sizeof(double));
1450 memcpy(Evaluator.m_dTermValuesArray[T_LVL], Level[nNiz], nPoslova*sizeof(double));
1451 memcpy(Evaluator.m_dTermValuesArray[T_pavg], PTimeAvg[nNiz], nPoslova*sizeof(double));
1452
1454// ako u terminalima ima vremenski ovisnih, moramo raditi posao po posao
1455// vektorska evaluacija!
1456 for(nJob=0; nJob<nPoslova; nJob++) // rasporedjujemo svaki posao unutar skupa
1457 { for(i=nJob; i<nPoslova; i++) // racunamo nove terminale samo za nerasporedjene
1458 { j = pIndex[i];
1459 Evaluator.m_dTermValuesArray[T_SPr][j] = dSPr; // suma trajanja preostalih
1460 Evaluator.m_dTermValuesArray[T_Nr][j] = nNr; // broj preostalih
1461 }
1462 Evaluator.m_iPosition = -1;
1463 Evaluator.m_iOffset = nJob; // od kojeg posla pocinjemo - prethodni su vec rasporedjeni!
1464
1465 if(m_dynamic) // dinamicka okolina; zapravo simulacija online rasporedjivanja
1466//
1467// daklem ovako:
1468// - gledamo prvo vrijeme kad je raspoloziv i posao i stroj (barem jedan)
1469// - ocijenimo sve poslove za sve strojeve
1470// - gledamo najbolju vrijednost:
1471// - ako je za raspolozivi stroj, rasporedi
1472// - ako je za neraspolozivi stroj, gledaj sljedece vrijednosti (od drugih poslova)
1473// - ako svi poslovi imaju svoje najbolje vrijednosti za neraspolozive strojeve, NE RASPOREDI nego
1474// pomakni vrijeme na prvi sljedeci raspolozivi stroj ILI POSAO i ponovi ispocetka (za sve pristigle poslove!)
1475//
1476 { // trebamo naci prvi raspolozivi stroj i prvi raspolozivi posao
1477 unsigned int raspolozivi = nJob, prvi = nJob;
1478 // trebamo pronaci prvog raspolozivog bez nezavrsenih prethodnika
1479 for(; Precedence[pIndex[raspolozivi]][0] > 0; raspolozivi++) NULL;
1480 double kada = Ready[nNiz][pIndex[raspolozivi]]; // pocetno vrijeme
1481 for( ; raspolozivi < nPoslova; raspolozivi++) // koji je 'najstariji'?
1482 { k = pIndex[raspolozivi];
1483 if(Ready.data[nNiz][k] < kada && Precedence[k][0] == 0) // gledamo najblize vrijeme dolaska
1484 { kada = Ready.data[nNiz][k];
1485 prvi = raspolozivi;
1486 }
1487 } // sada je pIndex[prvi] prvi raspolozivi posao
1488 nMachine = 0;
1489 for(i=0; i<nMachines; i++)
1490 if(MachineReady[i][0] < MachineReady[nMachine][0])
1491 nMachine = i;
1492 // nMachine je prvi raspolozivi stroj
1493 if(kada < MachineReady[nMachine][0])
1494 kada = MachineReady[nMachine][0];
1495 dClock = kada; // sat postavimo na najblize vrijeme raspolozivosti
1496 // sad odredimo koji zadnji posao gledamo iz polja indeksa
1497 for(i=Evaluator.m_iEnd; i<nPoslova && Ready[nNiz][pIndex[i]]<=dClock; i++) NULL;
1498 Evaluator.m_iEnd = i;
1499
1500 // probajmo ovako: pronaci najbolju kombinaciju svih pristiglih poslova i raspolozivih strojeva
1501 // varijacija: gledamo sve strojeve (i one trenutno zauzete)
1502 for(nMachine=0; nMachine<nMachines; nMachine++)
1503 { //if(MachineReady[nMachine][0] > dClock) // varijanta samo sa slobodnim strojevima
1504 // continue;
1505 // trebamo izracunati nove vrijednosti vremenski ovisnih terminala!
1506 CalcTimedTerminals(nNiz,nPoslova,nJob,dClock,nMachine,nMachines);
1507 Evaluator.m_iPosition = -1;
1508 Evaluator.evaluate_array(pVrijednosti); // ocijenimo sve
1509 memcpy(Values[nMachine],pVrijednosti,nPoslova*sizeof(double)); // pohranimo vrijednosti za taj stroj
1510 }
1511 bool BestSet = false;
1512 uint nBestMachine, nBestJobMachine;
1513 for(i=nJob; i<nPoslova; i++)
1514 { if(Precedence[pIndex[i]][0] != 0 || Ready[nNiz][pIndex[i]] > dClock)
1515 continue;
1516 // je li posao odabrao neraspolozivi stroj?
1517 nBestJobMachine = 0;
1518 for(nMachine=1; nMachine<nMachines; nMachine++)
1519 if(Values[nBestJobMachine][pIndex[i]] < Values[nMachine][pIndex[i]])
1520 nBestJobMachine = nMachine;
1521 if(MachineReady[nBestJobMachine][0] > dClock)
1522 continue; // tebe necemo sada rasporediti...
1523 if(!BestSet) // ako je to prvi posao koji je odabrao raspolozivi stroj
1524 { nBestMachine = nBestJobMachine;
1525 dBest = Values[nBestMachine][pIndex[i]];
1526 nOdabrani = i;
1527 BestSet = true;
1528 }
1529 else // inace vidi kolika je vrijednost
1530 { if(Values[nBestJobMachine][pIndex[i]] < dBest)
1531 { nBestMachine = nBestJobMachine;
1532 dBest = Values[nBestJobMachine][pIndex[i]];
1533 nOdabrani = i;
1534 }
1535 }
1536 }
1537 // ako nijedan posao nije za raspolozivi stroj, prekidamo iteraciju petlje koja vrti poslove
1538 if(!BestSet)
1539 { nJob--; // azuriraj indeks for petlje (nismo rasporedili posao)
1540 // vremena svih raspolozivih strojeva prebaci na prvi sljedeci zavrsetak
1541 // prvo pronadji najblizi _sljedeci_ raspolozivi stroj (nMachine)
1542 for(i=0; i<nMachines && MachineReady[i][0] <= dClock; i++) NULL;
1543 nMachine = i;
1544 for( ; i<nMachines; i++)
1545 if(MachineReady[i][0] > dClock && MachineReady[i][0] < MachineReady[nMachine][0])
1546 nMachine = i;
1547
1548 // onda prvi _sljedeci_ raspolozivi posao
1549 unsigned int raspolozivi = nJob, prvi = nJob;
1550 // trebamo pronaci prvog sljedeceg raspolozivog bez nezavrsenih prethodnika
1551 for(; raspolozivi < nPoslova && (Precedence[pIndex[raspolozivi]][0] > 0 || Ready[nNiz][pIndex[raspolozivi]] <= dClock); raspolozivi++) NULL;
1552 double kada;
1553 if(raspolozivi < nPoslova) // ima li uopce novih?
1554 { kada = Ready[nNiz][pIndex[raspolozivi]]; // pocetno vrijeme
1555 for( ; raspolozivi < nPoslova; raspolozivi++) // koji je 'najstariji'?
1556 { k = pIndex[raspolozivi];
1557 if(Ready[nNiz][k] < kada && Ready[nNiz][k] > dClock && Precedence[k][0] == 0) // gledamo najblize vrijeme dolaska
1558 { kada = Ready[nNiz][k];
1559 prvi = raspolozivi;
1560 }
1561 } // sada je pIndex[prvi] prvi raspolozivi posao
1562 }
1563
1564 // a onda odredimo manje od ta dva vremena (raspolozivost stroja ili posla)
1565 dClock = MachineReady[nMachine][0];
1566 if(raspolozivi < nPoslova && kada < dClock)
1567 dClock = kada;
1568
1569 // azuriraj vremena raspolozivosti strojeva
1570 for(i=0; i<nMachines; i++)
1571 if(MachineReady[i][0] < dClock)
1572 MachineReady[i][0] = dClock;
1573 continue; // idi na pocetak petlje koja vrti poslove
1574 }
1575 // inace, rasporedi posao na raspolozivom stroju
1576 nMachine = nBestMachine;
1577 } // endif - m_dynamic
1578
1579 else // staticki
1580 { // pronadjemo prvi raspolozivi stroj
1581 nMachine = 0;
1582 for(i=1; i<nMachines; i++)
1583 if(MachineReady[i][0] < MachineReady[nMachine][0])
1584 nMachine = i;
1585 dClock = MachineReady[nMachine][0]; // to je trenutno vrijeme
1586 CalcTimedTerminals(nNiz,nPoslova,nJob,dClock,nMachine,nMachines);
1587 nOdabrani = nJob;
1588 if(m_constrained) // trazimo prvi bez prethodnika
1589 for(; Precedence[pIndex[nOdabrani]][0] > 0; nOdabrani++) NULL;
1590 Evaluator.evaluate_array(pVrijednosti); // ocijenimo sve
1591 dBest = pVrijednosti[pIndex[nOdabrani]]; // pretpostavimo da je neki najbolji
1592 for(i=nJob; i<nPoslova; i++) // pa pogledamo ostale
1593 { // trazimo najmanju vrijednost
1594 if(pVrijednosti[pIndex[i]] < dBest && Precedence[pIndex[i]][0] == 0) // je li to najbolja vrijednost?
1595 { dBest = pVrijednosti[pIndex[i]];
1596 nOdabrani = i;
1597 }
1598 }
1599 } // zavrsen odabir posla
1600
1601 // vrijednost pIndex[nOdabrani] je indeks posla koji ide sljedeci, na stroju nMachine
1602 // gledamo nOdabrani kao rezultat; zamijenimo nJob-ti i odabrani u polju indeksa
1603 i = pIndex[nJob];
1604 pIndex[nJob] = pIndex[nOdabrani];
1605 pIndex[nOdabrani] = i;
1606 pRasporedjen[pIndex[nJob]] = true;
1607 nOdabrani = pIndex[nJob]; // nOdabrani je pravi indeks posla
1608
1609 // update trajanja preostalih - jos treba definirati
1610 //dSPr -= Duration.data[nNiz][nOdabrani]*dMsum;
1611 nNr--; // update broja preostalih
1612 if(m_setup) // trajanje postavljanja
1613 { dSetupTime = Setup[pLastJob[nMachine]][nOdabrani];
1614 pLastJob[nMachine] = nOdabrani; // sljedeci prethodni posao
1615 }
1616 else dSetupTime = 0;
1617 if(m_constrained) // smanjimo broj prethodnika svim sljedbenicima odabranog posla
1618 for(i=0; i<Precedence[nOdabrani][1]; i++)
1619 { j = (int) Precedence[nOdabrani][i+2];
1620 Precedence[j][0] -= 1;
1621 }
1622 MachineReady[nMachine][0] = dClock + dSetupTime + \
1623 Duration[nNiz][nOdabrani*nMachines + nMachine];
1624 // odredimo sljedeci element u matrici rasporeda (indeks stroja je tisucica)
1625 Schedule[nNiz][nJob] = nOdabrani + nMachine * 1000;
1626 } // kraj petlje koja vrti poslove u skupu
1627
1628 // racunanje raznih kriterija za trenutni skup
1629 { if(m_Evaluation)
1630 { for(nJob=nPoslova ; nJob < this->max_jobs; nJob++)
1631 Schedule[nNiz][nJob] = 0; // ostalo nule
1632 }
1633 // odredimo fitnes kriterij - sve moguce funkcije
1634 dClock = 0; nLastJob = nPoslova; dAvgWeights = 0; dCmax = 0;
1635 for(i=0; i<nMachines; i++)
1636 { MachineReady[i][0] = 0;
1637 pLastJob[i] = nPoslova;
1638 }
1639 for(nJob = 0; nJob<nPoslova; nJob++)
1640 { index = (int) Schedule[nNiz][nJob];
1641 nMachine = index / 1000; // na kojem stroju
1642 index = index % 1000; // koji posao
1643 dAvgWeights += WeightT[nNiz][index];
1644 if(m_dynamic && MachineReady[nMachine][0] < Ready[nNiz][index]) // ako posao jos nije raspoloziv
1645 MachineReady[nMachine][0] = Ready[nNiz][index];
1646 MachineReady[nMachine][0] += Duration[nNiz][index*nMachines + nMachine];
1647 if(m_setup)
1648 MachineReady[nMachine][0] += Setup[pLastJob[nMachine]][index];
1649 pLastJob[nMachine] = index;
1650 dRez = MachineReady[nMachine][0] - Deadline.Get(nNiz,index); // kasnjenje
1651 dLateness += dRez*WeightT.data[nNiz][index]; // tezinsko kasnjenje
1652 dAvgWeightsC+= WeightC.data[nNiz][index];
1653 dAvgWeightsE+= WeightE.data[nNiz][index];
1654 machineUseage[nMachine] += Duration[nNiz][index*nMachines + nMachine];
1655 dCw += MachineReady[nMachine][0] * WeightC.data[nNiz][index];
1656
1657 if(dRez>0&&dTmax<(dRez*WeightT.data[nNiz][index])){
1658 dTmax = dRez*WeightT.data[nNiz][index];
1659 }
1660
1661 if(dFmax<(MachineReady[nMachine][0] - Ready[nNiz][index])){
1662 dFmax = MachineReady[nMachine][0] - Ready[nNiz][index];
1663 }
1664
1665 if(dRez > 0) dTardiness += dRez*WeightT.data[nNiz][index]; // tezinska zakasnjelost
1666 if(dRez > 0) nLateJobs ++; // kao broj zakasnjelih poslova
1667 if(dRez > 0) dNwt += WeightN.data[nNiz][index]; // tezinski broj zakasnjelih
1668 if(dRez < 0) dEarliness += WeightE.data[nNiz][index]*dRez;
1669 if(m_dynamic)
1670 dFwt += MachineReady[nMachine][0] - Ready[nNiz][index]; // protjecanje, NIJE TEZINSKO
1671 else
1672 dFwt += MachineReady[nMachine][0];
1673 }
1674 for(i=0; i<nMachines; i++)
1675 if(MachineReady[i][0] > dCmax)
1676 dCmax = MachineReady[i][0];
1677
1678 double max=machineUseage[0]/dCmax, min =machineUseage[0]/dCmax;
1679
1680
1681 for(i=0; i<nMachines; i++){
1682 machineUseage[i]/= dCmax;
1683 dMus+=machineUseage[i];
1684 if(max<machineUseage[i])
1685 max = machineUseage[i];
1686 if(min>machineUseage[i])
1687 min = machineUseage[i];
1688 }
1689
1690 //dMus = -dMus; // da postane minimizacijski problem
1691 // normiranje fitnesa ovisno o broju poslova - dodano 27.07.
1692 dAvgWeights /= nPoslova; // prosjecni tezinski faktor skupa
1693 dAvgWeightsC/= nPoslova;
1694 dAvgWeightsE/= nPoslova;
1695 double dAvgDuration = SP[nNiz][0] / nPoslova; // prosjecno trajanje posla
1696 dMus=(max - min)/(nPoslova * dAvgDuration);
1697 dTardiness /= (nPoslova * dAvgWeights * dAvgDuration);
1698 dEarliness /= (nPoslova * dAvgWeightsE * dAvgDuration);
1699 dNwt /= (nPoslova * dAvgWeights);
1700 dFwt /= dAvgDuration * nPoslova;
1701 dCmax /= nPoslova * dAvgDuration;
1702 dCw /=(nPoslova * dAvgWeightsC * dAvgDuration);
1703 dTmax /= (dAvgDuration*nPoslova);
1704 dFmax /= (dAvgDuration*nPoslova);
1705 switch(m_fitness) // sto uzimamo kao fitnes?
1706 { case Twt: dRawFitness += dTardiness; break;
1707 case Nwt: dRawFitness += dNwt; break;
1708 case Fwt: dRawFitness += dFwt; break;
1709 case Cmax: dRawFitness += dCmax; break;
1710 case Ewt: dRawFitness += dEarliness; break;
1711 case ETwt: dRawFitness += (-dEarliness+dTardiness); break;
1712 case Tmax: dRawFitness += dTmax; break;
1713 case Fmax: dRawFitness += dFmax; break;
1714 case Cw: dRawFitness += dCw; break;
1715 case Mus: dRawFitness += dMus; break;
1716 default: CHECKMSG(0, "NEsto poslo po zlu");
1717 }
1718 nTotalLateJobs += nLateJobs;
1719 dTotalNwt += dNwt;
1720 dTotalFwt += dFwt;
1721 dTotalLateness += dLateness;
1722 dTotalTardiness += dTardiness;
1723 dTotalCmax += dCmax;
1724 dTotalEarliness += dEarliness;
1725 dTotalEarlinessTardiness+=(-dEarliness+dTardiness);
1726 dTotalMus+=dMus;
1727 dTotalCw +=dCw;
1728 dTotalTmax +=dTmax;
1729 dTotalFmax += dFmax;
1730 Fitness[nNiz][Twt] = dTardiness;
1731 Fitness[nNiz][Nwt] = dNwt;
1732 Fitness[nNiz][FTwt] = 0; // zasada
1733 Fitness[nNiz][Ewt] = dEarliness;
1734 Fitness[nNiz][Fwt] = dFwt;
1735 Fitness[nNiz][Cmax] = dCmax;
1736 Fitness[nNiz][ETwt] = (-dEarliness)+dTardiness;
1737 Fitness[nNiz][Mus] = dMus;
1738 Fitness[nNiz][Cw] = dCw;
1739 Fitness[nNiz][Tmax] = dTmax;
1740 Fitness[nNiz][Fmax] = dFmax;
1741
1742 }
1743
1744 } // kraj petlje koja vrti skupove poslova
1745 Fitness[sets][Twt] = dTotalTardiness;
1746 Fitness[sets][Nwt] = dTotalNwt;
1747 Fitness[sets][Fwt] = dTotalFwt;
1748 Fitness[sets][Cmax] = dTotalCmax;
1749 Fitness[sets][ETwt] = dTotalEarlinessTardiness;
1750 Fitness[sets][Mus] = dTotalMus;
1751 Fitness[sets][Ewt] = dTotalEarliness;
1752 Fitness[sets][Cw] = dTotalCw;
1753 Fitness[sets][Tmax] = dTotalTmax;
1754 Fitness[sets][Fmax] = dTotalFmax;
1755}
1756
1757
1758void SchedulingEvalOp::EvaluateUnrelatedPermutation(IndividualP individual, double &dRawFitness)
1759{
1760 Permutation::Permutation *permutation = (Permutation::Permutation*)individual->getGenotype(0).get();
1761 IntGenotype::IntGenotype *intGenotype = (IntGenotype::IntGenotype*) individual->getGenotype(1).get();
1762
1763 double dClock, dRez, dSetFitness, dAvgWeights, dCmax, dTotalCmax=0;
1764 double dLateness, dTotalLateness=0, dTardiness, dTotalTardiness=0;
1765 double dEarliness, dTotalEarliness = 0;
1766 double dEarlinessTardiness, dTotalEarlinessTardiness = 0;
1767 double dTmax, dTotalTmax = 0;
1768 double dFmax, dTotalFmax = 0;
1769 double dMus, dTotalMus = 0;
1770 double dCw, dTotalCw =0;
1771 vector<double> machineUseage;
1772 double dNwt, dTotalNwt=0, dBest, dSPr, dSetupTime, dFwt, dTotalFwt=0;
1773 unsigned int nPoslova,nNiz,nJob,i,j,k,index,nLateJobs,nTotalLateJobs=0,nNr;
1774 unsigned int nLastJob,nMachines,nOdabrani,nMachine;
1775 double dAvgWeightsC;
1776 double dAvgWeightsE;
1777
1778 dRawFitness=0;
1779
1780 // optimiramo samo jedan ispitni primjer!
1781
1782 nNiz = m_primjer;
1783 {
1784
1785 nNr = nPoslova = (int) N.Get(nNiz);
1786 // preliminarna ispitivanja
1787 if(m_constrained) // ima li ogranicenja
1788 ReadConstraints(Constraints,nNiz,nPoslova,Precedence);
1789 if(m_setup) // trajanja postavljanja
1790 MakeSetup(Duration,nNiz,nPoslova,m_setup_faktor,Setup);
1791
1792 // postavljanje pocetnih vrijednosti za pojedini skup
1793 nLateJobs = 0;
1794 dLateness = 0;
1795 dTardiness = 0;
1796 dEarliness = 0;
1797 dEarlinessTardiness = 0;
1798 dMus = 0;
1799 dNwt = 0;
1800 dCw = 0;
1801 dFwt = 0;
1802 dFmax =0;
1803 dTmax =0;
1804 dClock = 0; dSetFitness = 0;
1805 dAvgWeightsC = 0;
1806 dAvgWeightsE = 0;
1807 dClock = 0; dSetFitness = 0;
1808 nLastJob = nPoslova;
1809 for(i=0; i<nPoslova; i++)
1810 { pRasporedjen[i] = false; // svi nerasporedjeni
1811 // procitamo niz indeksa poslova sortiran po dolasku
1812 pIndex[i] = (uint) SortedReady[nNiz][i]; // inicijalni poredak
1813 }
1814 nMachines = (uint) Machines[nNiz][0];
1815
1816 // redni broj rasporedjenog posla
1817 nJob = 0;
1818
1820 //std::vector<double> machineBounds;
1821 //machineBounds.resize(nMachines + 1);
1822 //for(uint m = 0; m <= nMachines; m++)
1823 // machineBounds[m] = (m) * 1. / nMachines;
1824 //
1825 //std::vector<double> jobValues(nPoslova);
1826 //std::vector<uint> jobIndexes(nPoslova);
1827
1829 //for(uint m = 0; m < nMachines; m++) {
1830 // uint nJobs = 0;
1831
1832 // // koji poslovi idu na ovaj stroj i koji su njihovi indeksi
1833 // for(uint job = 0; job < nPoslova; job++)
1834 // if(fp->realValue[job] >= machineBounds[m] && fp->realValue[job] < machineBounds[m + 1]) {
1835 // jobValues[nJobs] = fp->realValue[job];
1836 // jobIndexes[nJobs] = job;
1837 // nJobs++;
1838 // }
1839
1840 // // ako nema poslova za ovaj stroj, odi dalje
1841 // if(nJobs == 0)
1842 // continue;
1843
1844 // // sortiraj poslove na stroju po vrijednostima
1845 // double pd;
1846 // uint pi;
1847 // for(uint i = 0; i < nJobs - 1; i++)
1848 // for(uint j = i + 1; j < nJobs; j++)
1849 // if(jobValues[i] > jobValues[j]) {
1850 // pd = jobValues[i];
1851 // jobValues[i] = jobValues[j];
1852 // jobValues[j] = pd;
1853 // pi = jobIndexes[i];
1854 // jobIndexes[i] = jobIndexes[j];
1855 // jobIndexes[j] = pi;
1856 // }
1857
1858 // // zapisi u raspored
1859 // for(uint job = 0; job < nJobs; job++) {
1860 // Schedule[nNiz][nJob] = jobIndexes[job] + m * 1000;
1861 // nJob++;
1862 // }
1863
1864 for(uint i = 0; i < permutation->getSize(); i++) {
1865 Schedule[nNiz][i] = permutation->variables.at(i) + intGenotype->intValues.at(i) * 1000;
1866 }
1867
1868 for(int kk=0; kk<nMachines; kk++){
1869 machineUseage.push_back(0);
1870 }
1871
1872// Schedule[nNiz][nJob] = nOdabrani + nMachine * 1000;
1873
1874
1875 // racunanje raznih kriterija za trenutni skup
1876 { if(m_Evaluation)
1877 { for(nJob=nPoslova ; nJob < this->max_jobs; nJob++)
1878 Schedule[nNiz][nJob] = 0; // ostalo nule
1879 }
1880 // odredimo fitnes kriterij - sve moguce funkcije
1881 dClock = 0; nLastJob = nPoslova; dAvgWeights = 0; dCmax = 0;
1882 for(i=0; i<nMachines; i++)
1883 { MachineReady[i][0] = 0;
1884 pLastJob[i] = nPoslova;
1885 }
1886 for(nJob = 0; nJob<nPoslova; nJob++)
1887 { index = (int) Schedule[nNiz][nJob];
1888 nMachine = index / 1000; // na kojem stroju
1889 index = index % 1000; // koji posao
1890 dAvgWeights += WeightT[nNiz][index];
1891 if(m_dynamic && MachineReady[nMachine][0] < Ready[nNiz][index]) // ako posao jos nije raspoloziv
1892 MachineReady[nMachine][0] = Ready[nNiz][index];
1893 MachineReady[nMachine][0] += Duration[nNiz][index*nMachines + nMachine];
1894 if(m_setup)
1895 MachineReady[nMachine][0] += Setup[pLastJob[nMachine]][index];
1896 pLastJob[nMachine] = index;
1897 dRez = MachineReady[nMachine][0] - Deadline.Get(nNiz,index); // kasnjenje
1898 dLateness += dRez*WeightT.data[nNiz][index]; // tezinsko kasnjenje
1899 dAvgWeightsC+= WeightC.data[nNiz][index];
1900 dAvgWeightsE+= WeightE.data[nNiz][index];
1901 machineUseage[nMachine] += Duration[nNiz][index*nMachines + nMachine];
1902 dCw += MachineReady[nMachine][0] * WeightC.data[nNiz][index];
1903
1904 if(dRez>0&&dTmax<(dRez*WeightT.data[nNiz][index])){
1905 dTmax = dRez*WeightT.data[nNiz][index];
1906 }
1907
1908 if(dFmax<(MachineReady[nMachine][0] - Ready[nNiz][index])){
1909 dFmax = MachineReady[nMachine][0] - Ready[nNiz][index];
1910 }
1911
1912 if(dRez > 0) dTardiness += dRez*WeightT.data[nNiz][index]; // tezinska zakasnjelost
1913 if(dRez > 0) nLateJobs ++; // kao broj zakasnjelih poslova
1914 if(dRez > 0) dNwt += WeightN.data[nNiz][index]; // tezinski broj zakasnjelih
1915 if(dRez < 0) dEarliness += WeightE.data[nNiz][index]*dRez;
1916 if(m_dynamic)
1917 dFwt += MachineReady[nMachine][0] - Ready[nNiz][index]; // protjecanje, NIJE TEZINSKO
1918 else
1919 dFwt += MachineReady[nMachine][0];
1920 }
1921 for(i=0; i<nMachines; i++)
1922 if(MachineReady[i][0] > dCmax)
1923 dCmax = MachineReady[i][0];
1924
1925 double max=machineUseage[0]/dCmax, min =machineUseage[0]/dCmax;
1926
1927
1928 for(i=0; i<nMachines; i++){
1929 machineUseage[i]/= dCmax;
1930 dMus+=machineUseage[i];
1931 if(max<machineUseage[i])
1932 max = machineUseage[i];
1933 if(min>machineUseage[i])
1934 min = machineUseage[i];
1935 }
1936
1937 //dMus = -dMus; // da postane minimizacijski problem
1938 // normiranje fitnesa ovisno o broju poslova - dodano 27.07.
1939 dAvgWeights /= nPoslova; // prosjecni tezinski faktor skupa
1940 dAvgWeightsC/= nPoslova;
1941 dAvgWeightsE/= nPoslova;
1942 double dAvgDuration = SP[nNiz][0] / nPoslova; // prosjecno trajanje posla
1943 dMus=(max - min)/(nPoslova * dAvgDuration);
1944 dTardiness /= (nPoslova * dAvgWeights * dAvgDuration);
1945 dEarliness /= (nPoslova * dAvgWeightsE * dAvgDuration);
1946 dNwt /= (nPoslova * dAvgWeights);
1947 dFwt /= dAvgDuration * nPoslova;
1948 dCmax /= nPoslova * dAvgDuration;
1949 dCw /=(nPoslova * dAvgWeightsC * dAvgDuration);
1950 dTmax /= (dAvgDuration*nPoslova);
1951 dFmax /= (dAvgDuration*nPoslova);
1952 switch(m_fitness) // sto uzimamo kao fitnes?
1953 { case Twt: dRawFitness += dTardiness; break;
1954 case Nwt: dRawFitness += dNwt; break;
1955 case Fwt: dRawFitness += dFwt; break;
1956 case Cmax: dRawFitness += dCmax; break;
1957 case Ewt: dRawFitness += dEarliness; break;
1958 default: CHECK(0);
1959 }
1960 nTotalLateJobs += nLateJobs;
1961 dTotalNwt += dNwt;
1962 dTotalFwt += dFwt;
1963 dTotalLateness += dLateness;
1964 dTotalTardiness += dTardiness;
1965 dTotalCmax += dCmax;
1966 dTotalEarliness += dEarliness;
1967 dTotalEarlinessTardiness+=dEarliness+dTardiness;
1968 dTotalMus+=dMus;
1969 dTotalCw +=dCw;
1970 dTotalTmax +=dTmax;
1971 dTotalFmax += dFmax;
1972 Fitness[nNiz][Twt] = dTardiness;
1973 Fitness[nNiz][Nwt] = dNwt;
1974 Fitness[nNiz][FTwt] = 0; // zasada
1975 Fitness[nNiz][Ewt] = dEarliness;
1976 Fitness[nNiz][Fwt] = dFwt;
1977 Fitness[nNiz][Cmax] = dCmax;
1978 Fitness[nNiz][ETwt] = dEarliness+dTardiness;
1979 Fitness[nNiz][Mus] = dMus;
1980 Fitness[nNiz][Cw] = dCw;
1981 Fitness[nNiz][Tmax] = dTmax;
1982 Fitness[nNiz][Fmax] = dFmax;
1983
1984 }
1985
1986
1987 } // kraj petlje koja vrti skupove poslova
1988 Fitness[sets][Twt] = dTotalTardiness;
1989 Fitness[sets][Nwt] = dTotalNwt;
1990 Fitness[sets][Fwt] = dTotalFwt;
1991 Fitness[sets][Cmax] = dTotalCmax;
1992 Fitness[sets][ETwt] = dTotalEarlinessTardiness;
1993 Fitness[sets][Mus] = dTotalMus;
1994 Fitness[sets][Ewt] = dTotalEarliness;
1995 Fitness[sets][Cw] = dTotalCw;
1996 Fitness[sets][Tmax] = dTotalTmax;
1997 Fitness[sets][Fmax] = dTotalFmax;
1998
1999}
2000
2001//
2002// UNRELATED okruzenje, ali uz pomoc floating point prikaza
2003//
2004void SchedulingEvalOp::EvaluateUnrelatedFP(FloatingPointP fp, double &dRawFitness)
2005{
2006 double dClock, dRez, dSetFitness, dAvgWeights, dCmax, dTotalCmax=0;
2007 double dLateness, dTotalLateness=0, dTardiness, dTotalTardiness=0;
2008 double dNwt, dTotalNwt=0, dBest, dSPr, dSetupTime, dFwt, dTotalFwt=0;
2009 unsigned int nPoslova,nNiz,nJob,i,j,k,index,nLateJobs,nTotalLateJobs=0,nNr;
2010 unsigned int nLastJob,nMachines,nOdabrani,nMachine;
2011
2012 dRawFitness = 0;
2013
2014 // optimiramo samo jedan ispitni primjer!
2015
2016 nNiz = m_primjer;
2017 {
2018
2019 nNr = nPoslova = (int) N.Get(nNiz);
2020 // preliminarna ispitivanja
2021 if(m_constrained) // ima li ogranicenja
2022 ReadConstraints(Constraints,nNiz,nPoslova,Precedence);
2023 if(m_setup) // trajanja postavljanja
2024 MakeSetup(Duration,nNiz,nPoslova,m_setup_faktor,Setup);
2025
2026 // postavljanje pocetnih vrijednosti za pojedini skup
2027 nLateJobs = 0;
2028 dLateness = 0;
2029 dTardiness = 0;
2030 dNwt = 0;
2031 dFwt = 0;
2032 dClock = 0; dSetFitness = 0;
2033 nLastJob = nPoslova;
2034 for(i=0; i<nPoslova; i++)
2035 { pRasporedjen[i] = false; // svi nerasporedjeni
2036 // procitamo niz indeksa poslova sortiran po dolasku
2037 pIndex[i] = (uint) SortedReady[nNiz][i]; // inicijalni poredak
2038 }
2039 nMachines = (uint) Machines[nNiz][0];
2040
2041 // redni broj rasporedjenog posla
2042 nJob = 0;
2043
2044 // odredi granice FP vrijednosti za svaki stroj
2045 std::vector<double> machineBounds;
2046 machineBounds.resize(nMachines + 1);
2047 for(uint m = 0; m <= nMachines; m++)
2048 machineBounds[m] = (m) * 1. / nMachines;
2049 machineBounds[nMachines] = 1.000000001;
2050 std::vector<double> jobValues(nPoslova);
2051 std::vector<uint> jobIndexes(nPoslova);
2052
2053 // odredimo poslove za svaki stroj posebno
2054 for(uint m = 0; m < nMachines; m++) {
2055 uint nJobs = 0;
2056
2057 // koji poslovi idu na ovaj stroj i koji su njihovi indeksi
2058 for(uint job = 0; job < nPoslova; job++)
2059 if(fp->realValue[job] >= machineBounds[m] && fp->realValue[job] < machineBounds[m + 1]) {
2060 jobValues[nJobs] = fp->realValue[job];
2061 jobIndexes[nJobs] = job;
2062 nJobs++;
2063 }
2064
2065 // ako nema poslova za ovaj stroj, odi dalje
2066 if(nJobs == 0)
2067 continue;
2068
2069 // sortiraj poslove na stroju po vrijednostima
2070 double pd;
2071 uint pi;
2072 for(uint i = 0; i < nJobs - 1; i++)
2073 for(uint j = i + 1; j < nJobs; j++)
2074 if(jobValues[i] > jobValues[j]) {
2075 pd = jobValues[i];
2076 jobValues[i] = jobValues[j];
2077 jobValues[j] = pd;
2078 pi = jobIndexes[i];
2079 jobIndexes[i] = jobIndexes[j];
2080 jobIndexes[j] = pi;
2081 }
2082
2083 // zapisi u raspored
2084 for(uint job = 0; job < nJobs; job++) {
2085 Schedule[nNiz][nJob] = jobIndexes[job] + m * 1000;
2086 nJob++;
2087 }
2088
2089 }
2090
2091
2092
2093// Schedule[nNiz][nJob] = nOdabrani + nMachine * 1000;
2094
2095
2096 // racunanje raznih kriterija za trenutni skup
2097 { if(m_Evaluation)
2098 { for(nJob=nPoslova ; nJob < this->max_jobs; nJob++)
2099 Schedule[nNiz][nJob] = 0; // ostalo nule
2100 }
2101 // odredimo fitnes kriterij - sve moguce funkcije
2102 dClock = 0; nLastJob = nPoslova; dAvgWeights = 0; dCmax = 0;
2103 for(i=0; i<nMachines; i++)
2104 { MachineReady[i][0] = 0;
2105 pLastJob[i] = nPoslova;
2106 }
2107 for(nJob = 0; nJob<nPoslova; nJob++)
2108 { index = (int) Schedule[nNiz][nJob];
2109 nMachine = index / 1000; // na kojem stroju
2110 index = index % 1000; // koji posao
2111 dAvgWeights += WeightT[nNiz][index];
2112 if(m_dynamic && MachineReady[nMachine][0] < Ready[nNiz][index]) // ako posao jos nije raspoloziv
2113 MachineReady[nMachine][0] = Ready[nNiz][index];
2114 MachineReady[nMachine][0] += Duration[nNiz][index*nMachines + nMachine];
2115 if(m_setup)
2116 MachineReady[nMachine][0] += Setup[pLastJob[nMachine]][index];
2117 pLastJob[nMachine] = index;
2118 dRez = MachineReady[nMachine][0] - Deadline.Get(nNiz,index); // kasnjenje
2119 dLateness += dRez*WeightT.data[nNiz][index]; // tezinsko kasnjenje
2120 if(dRez > 0) dTardiness += dRez*WeightT.data[nNiz][index]; // tezinska zakasnjelost
2121 if(dRez > 0) nLateJobs ++; // kao broj zakasnjelih poslova
2122 if(dRez > 0) dNwt += WeightN.data[nNiz][index]; // tezinski broj zakasnjelih
2123 if(m_dynamic)
2124 dFwt += MachineReady[nMachine][0] - Ready[nNiz][index]; // protjecanje, NIJE TEZINSKO
2125 else
2126 dFwt += MachineReady[nMachine][0];
2127 }
2128 for(i=0; i<nMachines; i++)
2129 if(MachineReady[i][0] > dCmax)
2130 dCmax = MachineReady[i][0];
2131 // normiranje fitnesa ovisno o broju poslova
2132 double dAvgDuration = SP[nNiz][0] / nPoslova; // prosjecno trajanje posla
2133 dAvgWeights /= nPoslova; // prosjecni tezinski faktor skupa
2134 dTardiness /= (nPoslova * dAvgWeights * dAvgDuration);
2135 dNwt /= (nPoslova * dAvgWeights);
2136 dFwt /= dAvgDuration * nPoslova;
2137 dCmax /= (nPoslova * dAvgDuration);
2138 switch(m_fitness) // sto uzimamo kao fitnes?
2139 { case Twt: dRawFitness += dTardiness; break;
2140 case Nwt: dRawFitness += dNwt; break;
2141 case Fwt: dRawFitness += dFwt; break;
2142 case Cmax: dRawFitness += dCmax; break;
2143 default: CHECK(0);
2144 }
2145 nTotalLateJobs += nLateJobs;
2146 dTotalNwt += dNwt;
2147 dTotalFwt += dFwt;
2148 dTotalLateness += dLateness;
2149 dTotalTardiness += dTardiness;
2150 dTotalCmax += dCmax;
2151 Fitness[nNiz][Twt] = dTardiness;
2152 Fitness[nNiz][Nwt] = dNwt;
2153 Fitness[nNiz][FTwt] = 0; // zasada
2154 Fitness[nNiz][ETwt] = 0;
2155 Fitness[nNiz][Fwt] = dFwt;
2156 Fitness[nNiz][Cmax] = dCmax;
2157 }
2158
2159 } // kraj petlje koja vrti skupove poslova
2160 Fitness[sets][Twt] = dTotalTardiness;
2161 Fitness[sets][Nwt] = dTotalNwt;
2162 Fitness[sets][Fwt] = dTotalFwt;
2163 Fitness[sets][Cmax] = dTotalCmax;
2164}
2165
2166
2167
2168
2169
2170void SchedulingEvalOp::EvaluateJobShop(double &dRawFitness)
2171{
2172 double dL, dT, dTwt, dF, dFwt, dN, dNwt, dCmax;
2173 double dTotalT, dTotalTwt, dTotalF, dTotalFwt, dTotalN, dTotalNwt, dTotalCmax;
2174 double dClock, dAvgWeights, dTotalAvgLoad, dBestMachineValue, dAvgDuration;
2175 double dBest, dSetupTime, m1, m2, dNajkrace, dBegin;
2176 unsigned int nPoslova, nNiz, nJob, i, j, k, nNr, nOperations, nOperation, nNextOperation;
2177 unsigned int nMachines, nMachine, nSchedule, nMachineIndex, nJobsToEval, nBestJob, nNextMachine;
2178 unsigned int nBottleneck;
2179
2180 dRawFitness=0;
2181 dTotalT = dTotalTwt = dTotalF = dTotalFwt = dTotalN = dTotalNwt = dTotalCmax = 0;
2182
2183// vrtimo sve skupove
2184 for(nNiz=0; nNiz<sets; nNiz++)
2185 { nNr = nPoslova = (int) N.Get(nNiz);
2186 // preliminarna ispitivanja
2187 // radimo li stochastic sampling
2188 if(m_stsampling)
2189 if(pSamples[nNiz] == false)
2190 continue; // jednostavno preskocimo taj test case
2191 // gleda li se limited error fitness
2192 if(m_LEF)
2193 { if(dRawFitness > m_LEFVal)
2194 break; // prekid ispitivanja
2195 }
2196 if(m_setup) // trajanja postavljanja
2197 MakeSetup(Duration,nNiz,nPoslova,m_setup_faktor,Setup);
2198 // postavljanje pocetnih vrijednosti za pojedini skup
2199 dClock = 0;
2200 dTotalAvgLoad = 0; // prosjecno opterecenje svih strojeva
2201 nOperations = nMachines = (uint) Machines[nNiz][0];
2202 dBestMachineValue = 0;
2203 nBottleneck = nMachines; // nijedan nije bottleneck na pocetku
2204 for(j=0; j<nMachines; j++)
2205 { MachineReady[j][0] = 0; // pocetno vrijeme raspolozivosti strojeva
2206 pLastJob[j] = nPoslova; // pocetni prethodni posao
2207 pMachineScheduled[j] = 0; // broj rasporedjenih operacija na stroju
2208 pOperationReady[j] = -1; // raspolozivost operacija za strojeve tek treba odrediti
2209 pTotalMachineWork[j] = 0; // ukupno opterecenje stroja
2210 pOperationsWaiting[j] = 0; // broj operacija na cekanju
2211 pMachineValues[j] = 0; // vrijednosti strojeva - racunaju se stablom odluke
2212 }
2213 for(i=0; i<nPoslova; i++)
2214 { pTotalWorkRemaining[i] = 0;
2215 pTotalWorkDone[i] = 0;
2216 pIndex[i] = i; // inicijalni poredak
2217 pJobReady[i] = Ready[nNiz][i]; // Ready su nule u statickom slucaju
2218 pOperationsScheduled[i] = 0; // broj rasporedjenih operacija posla
2219 for(j=0; j<nOperations; j++)
2220 { k = (int) Duration[nNiz][i*nOperations + j];
2221 nMachine = k / 1000; // indeks stroja
2222 if(j == 0) // za prvu operaciju
2223 pOperationsWaiting[nMachine]++;
2224 k = k % 1000; // trajanje operacije
2225 pTotalWorkRemaining[i] += k;
2226 Durations[i][j] = k;
2227 dTotalAvgLoad += k;
2228 MachineIndex[i][j] = nMachine;
2229 pTotalMachineWork[nMachine] += k;
2230 }
2231 // pogledamo na kojem je stroju prva operacija posla
2232 nMachine = (int) MachineIndex[i][0];
2233 pOperationReady[nMachine] = pJobReady[i];
2234 // znaci taj stroj je trazen u trenutku dolaska posla (0 u statickom slucaju)
2235 }
2236 dAvgDuration = dTotalAvgLoad / nPoslova; // prosjecno trajanje poslova
2237 dTotalAvgLoad /= nMachines;
2238 Evaluator.SetTermArraySize(nPoslova); // koliko poslova u skupu - za vektorsku evaluaciju
2239 Evaluator.pIndex = pIndex; // polje indeksa poslova
2240 Evaluator.m_iOffset = 0; // indeks prvog nerasporedjenog
2241 //Evaluator.m_iEnd = 1; // pocetna vrijednost zadnjeg posla koji se uzima u o obzir
2242 // postavljanje pocetnih vrijednosti terminala - nepromjenjivi
2243 memcpy(Evaluator.m_dTermValuesArray[T_dd], Deadline.data[nNiz], nPoslova*sizeof(double));
2244 memcpy(Evaluator.m_dTermValuesArray[T_w], WeightT.data[nNiz], nPoslova*sizeof(double));
2245 memcpy(Evaluator.m_dTermValuesArray[T_TWK], pTotalWorkRemaining, nPoslova*sizeof(double));
2246 // nepromjenjivi terminali za strojeve
2247 for(i=0; i<nMachines; i++)
2248 { Evaluator.m_dTermValuesArray[T_MTWKav][i] = dTotalAvgLoad;
2249 Evaluator.m_dTermValuesArray[T_MTWK][i] = pTotalMachineWork[i];
2250 pMachineWorkRemaining[i] = pTotalMachineWork[i];
2251 }
2252 memcpy(Evaluator.m_dTermValuesArray[T_MTWK], pTotalMachineWork, nMachines*sizeof(double));
2253
2254 for(nSchedule = 0; nSchedule < nPoslova*nMachines; nSchedule++)
2255 { // treba pronaci stroj koji ima najranije vrijeme raspolozivosti i sebe i operacije za njega
2256 for(nMachine = 0; nMachine<nMachines; nMachine++)
2257 if(pOperationReady[nMachine] >= 0) // je li stroj uopce trazen
2258 break;
2259 for(i = nMachine; i < nMachines; i++)
2260 { if(pOperationReady[i] < 0) // jos se nije pojavila potreba za tim strojem
2261 continue;
2262 m1 = MAX(MachineReady[i][0],pOperationReady[i]);
2263 m2 = MAX(MachineReady[nMachine][0],pOperationReady[nMachine]);
2264 if(m1 < m2) // ima neki stroj koji je prije raspoloziv za rasporediti
2265 nMachine = i;
2266 }
2267 dClock = MAX(MachineReady[nMachine][0], pOperationReady[nMachine]);
2268 // pronadjemo kada bilo koja operacija moze najprije zavrsiti
2269 dNajkrace = -1;
2270 for(nJob=0; nJob<nPoslova; nJob++)
2271 { nOperation = pOperationsScheduled[nJob];
2272 if(nOperation == nMachines) continue; // ovaj posao je zavrsio
2273 nMachineIndex = (int) MachineIndex[nJob][nOperation];
2274 if(nMachineIndex != nMachine) continue; // ovaj posao ne ceka na taj stroj
2275 if(dNajkrace < 0)
2276 dNajkrace = MAX(dClock, pJobReady[nJob]) + Durations[nJob][nOperation];
2277 else
2278 { dBegin = MAX(dClock, pJobReady[nJob]);
2279 if(dNajkrace > dBegin + Durations[nJob][nOperation])
2280 dNajkrace = dBegin + Durations[nJob][nOperation];
2281 }
2282 }
2283 // sada treba pronaci operaciju najveceg prioriteta koja ceka na taj stroj
2284 // radimo tako da poslove cije operacije treba ocijeniti stavimo na pocetak pIndex
2285 // prije evaluacije odredimo koliko ih ima (kao m_iEnd u Evaluatoru)
2286 nJobsToEval = 0;
2287 for(nJob=0; nJob<nPoslova; nJob++)
2288 { nOperation = pOperationsScheduled[nJob];
2289 if(nOperation == nMachines) continue; // ovaj posao je zavrsio
2290 nMachineIndex = (int) MachineIndex[nJob][nOperation];
2291 if(nMachineIndex != nMachine) continue; // ovaj posao ne ceka na taj stroj
2292 // mozemo uzeti u obzir samo one koji su vec spremni:
2293 if(!m_Idleness)
2294 if(pJobReady[nJob] > dClock) continue; // jos nije zavrsila prethodna operacija
2295 // ili mozemo uzeti u obzir i one koji ce tek zavrsiti, ali ne kasnije od moguceg zavrsetka najkrace spremne operacije
2296 dBegin = MAX(pJobReady[nJob],dClock);
2297 if(dBegin > dNajkrace) // nema smisla gledati ako pocinje iza najkraceg zavrsetka
2298 continue;
2299 // ako smo dosli ovdje, uzet cemo u obzir operaciju nOper. posla nJob na stroju nMachine
2300 pIndex[nJobsToEval] = nJob;
2301 nJobsToEval++;
2302 }
2303#ifdef TREES
2304 // pomocu prvog stabla odlucimo koja od dva preostala koristimo za prioritete
2305*
2306MNOPr[nMachine] = nOperations - pMachineScheduled[nMachine]
2307MTWKav = dTotalAvgLoad;
2308MTWK[nMachine] = pTotalMachineWork[nMachine];
2309MNOPw[nMachine] = pOperationsWaiting[nMachine];
2310MTWKr[nMachine] = pMachineWorkRemaining[nMachine];
2311MUTL[nMachine] = (pTotalMachineWork[nMachine] - pMachineWorkRemaining[nMachine]) / dClock;
2312*/
2313 Evaluator.m_nTree = 0;
2314 // prvo stablo racunamo samo za nMachine - pa za taj stroj racunamo terminale
2315 Evaluator.m_dTermValuesArray[T_MNOPr][nMachine] = nOperations - pMachineScheduled[nMachine];
2316 Evaluator.m_dTermValuesArray[T_MNOPw][nMachine] = pOperationsWaiting[nMachine];
2317 Evaluator.m_dTermValuesArray[T_MTWKr][nMachine] = pMachineWorkRemaining[nMachine];
2318 if(dClock == 0)
2319 Evaluator.m_dTermValuesArray[T_MUTL][nMachine] = 1;
2320 else
2321 Evaluator.m_dTermValuesArray[T_MUTL][nMachine] = (pTotalMachineWork[nMachine] - pMachineWorkRemaining[nMachine]) / dClock;
2322
2323 Evaluator.m_iPosition = -1;
2324 nSavedIndex = pIndex[nMachine]; // pohranimo indeks posla koji se tu nalazi
2325 pIndex[nMachine] = nMachine;
2326 Evaluator.m_iOffset = nMachine;
2327 Evaluator.m_iEnd = nMachine + 1;
2328 Evaluator.evaluate_array(pVrijednosti); // ocijenimo stroj u stablu odluke
2329 pMachineValues[nMachine] = pVrijednosti[nMachine];
2330 // MODIFIKACIJA 15.09.: uvijek pronadjemo novi dBestMachineValue kao Bottleneck
2331* dBestMachineValue = pMachineValues[0];
2332 nBottleneck = 0;
2333 for(i=0; i<nMachine; i++)
2334 if(pMachineValues[i] > dBestMachineValue)
2335 { dBestMachineValue = pMachineValues[i];
2336 nBottleneck = i;
2337 }
2338*/
2339 // MODIFIKACIJA 13.09.: uvijek pamtimo stroj koji je postigao najvecu vrijednost
2340 // (dok se ne postigne veca)
2341 if(pMachineValues[nMachine] >= dBestMachineValue) // je li nova najveca vrijednost?
2342 { dBestMachineValue = pMachineValues[nMachine];
2343 nBottleneck = nMachine;
2344 }
2345
2346 if(nMachine == nBottleneck) // jesam li ja bottleneck?
2347 Evaluator.m_nTree = 2; // za najoptereceniji stroj
2348 else
2349 Evaluator.m_nTree = 1; // za sve ostale
2350 pIndex[nMachine] = nSavedIndex; // vratimo indeks posla
2351#else // samo jedno stablo
2352 Evaluator.m_nTree = 0; // vratimo na obicno stablo
2353#endif
2354 // vektorska evaluacija!
2355 // trebamo definirati vrijednosti terminala za trenutne operacije odabranih poslova
2356 for(i=0; i<nJobsToEval; i++)
2357 { nJob = pIndex[i];
2358 nOperation = pOperationsScheduled[nJob];
2359 Evaluator.m_dTermValuesArray[T_pt][nJob] = Durations[nJob][nOperation];
2360 Evaluator.m_dTermValuesArray[T_CLK][nJob] = dClock;
2361 Evaluator.m_dTermValuesArray[T_AR][nJob] = POS(pJobReady[nJob] - dClock);
2362 Evaluator.m_dTermValuesArray[T_STP][nJob] = Setup[pLastJob[nMachine]][nJob];
2363 Evaluator.m_dTermValuesArray[T_Sav][nJob] = pSetupAvg[pLastJob[nMachine]];
2364 Evaluator.m_dTermValuesArray[T_age][nJob] = POS(dClock - Ready[nNiz][nJob]);
2365 Evaluator.m_dTermValuesArray[T_NOPr][nJob] = nOperations - pOperationsScheduled[nJob];
2366 Evaluator.m_dTermValuesArray[T_PTav][nJob] = PTimeAvg[nNiz][nMachine];
2367 Evaluator.m_dTermValuesArray[T_TWKr][nJob] = pTotalWorkRemaining[nJob];
2368 if(pTotalWorkDone[nJob] == 0)
2369 Evaluator.m_dTermValuesArray[T_HTR][nJob] = 1;
2370 else
2371 Evaluator.m_dTermValuesArray[T_HTR][nJob] = POS(dClock - Ready[nNiz][nJob]) / pTotalWorkDone[nJob];
2372 }
2373 Evaluator.m_iPosition = -1;
2374 Evaluator.m_iOffset = 0;
2375 Evaluator.m_iEnd = nJobsToEval; // toliko ih ima za ocijeniti
2376 Evaluator.evaluate_array(pVrijednosti); // ocijenimo sve u odabranom stablu
2377 dBest = pVrijednosti[pIndex[0]]; // poc. vrijednost za usporedbu
2378 nBestJob = pIndex[0];
2379 for(i=1; i<nJobsToEval; i++)
2380 { if(pVrijednosti[pIndex[i]] < dBest)
2381 { dBest = pVrijednosti[pIndex[i]];
2382 nBestJob = pIndex[i];
2383 }
2384 }
2385
2386 // nBestJob na nMachine
2387 nOperation = pOperationsScheduled[nBestJob]; // sadasnja operacija (koja ce se izvesti)
2388 pOperationsScheduled[nBestJob] += 1; // novi broj rasporedjenih operacija posla
2389 pTotalWorkRemaining[nBestJob] -= Durations[nBestJob][nOperation];
2390 pMachineWorkRemaining[nMachine] -= Durations[nBestJob][nOperation];
2391 pTotalWorkDone[nBestJob] += Durations[nBestJob][nOperation];
2392 if(m_setup)
2393 { dSetupTime = Setup[pLastJob[nMachine]][nBestJob];
2394 pLastJob[nMachine] = nBestJob;
2395 }
2396 else
2397 dSetupTime = 0;
2398 dClock = MAX(dClock, pJobReady[nBestJob]); // ako smo odlucili pricekati
2399 MachineReady[nMachine][0] = dClock + dSetupTime + Durations[nBestJob][nOperation];
2400 pJobReady[nBestJob] = MachineReady[nMachine][0]; // kada ce sljedeca operacija biti raspoloziva
2401 if(nOperation < nOperations-1) // ako posao ima jos operacija
2402 { nNextMachine = (int) MachineIndex[nBestJob][pOperationsScheduled[nBestJob]];
2403 if(pOperationReady[nNextMachine] < 0) // ako stroj trenutno nije trazen...
2404 pOperationReady[nNextMachine] = pJobReady[nBestJob]; // ... bit ce tada
2405 else // provjeri dolazi li moja sljedeca operacija prije trenutno najblize za taj stroj
2406 if(pOperationReady[nNextMachine] > pJobReady[nBestJob])
2407 pOperationReady[nNextMachine] = pJobReady[nBestJob];
2408 }
2409 // kada cu ja (stroj) opet biti trazen?
2410 pOperationReady[nMachine] = -1;
2411 pOperationsWaiting[nMachine] = 0;
2412 for(j=0; j<nPoslova; j++)
2413 { nNextOperation = pOperationsScheduled[j];
2414 if(nNextOperation == nMachines) continue; // ovaj nema vise operacija
2415 nNextMachine = (int) MachineIndex[j][nNextOperation];
2416 if(nNextMachine != nMachine) continue;
2417 pOperationsWaiting[nMachine]++;
2418 if(pOperationReady[nMachine] < 0)
2419 pOperationReady[nMachine] = pJobReady[j];
2420 else
2421 if(pOperationReady[nMachine] > pJobReady[j])
2422 pOperationReady[nMachine] = pJobReady[j];
2423 }
2424 nOperation = (int) pMachineScheduled[nMachine];
2425 pMachineScheduled[nMachine] += 1;
2426 Schedule[nNiz][nMachine * nPoslova + nOperation] = nBestJob;
2427 } // kraj rasporedjivanja skupa
2428
2429 // racunanje raznih kriterija za trenutni skup
2430 { if(m_Evaluation)
2431 { for(i=nPoslova*nMachines ; i < (uint)Schedule.GetCol(); i++)
2432 Schedule[nNiz][i] = 0; // ostalo nule
2433 }
2434 // odredimo fitnes kriterij - sve moguce funkcije
2435 dAvgWeights = 0;
2436 dCmax = dF = dFwt = dT = dTwt = dN = dNwt = 0;
2437 for(j=0; j<nPoslova; j++)
2438 { dAvgWeights += WeightT[nNiz][j];
2439 if(dCmax < pJobReady[j])
2440 dCmax = pJobReady[j];
2441 dF += pJobReady[j] - Ready[nNiz][j];
2442 dFwt += (pJobReady[j] - Ready[nNiz][j]) * WeightT[nNiz][j];
2443 if(pJobReady[j] > Deadline[nNiz][j])
2444 { dN += 1;
2445 dNwt += WeightT[nNiz][j];
2446 dL = pJobReady[j] - Deadline[nNiz][j];
2447 dT += dL;
2448 dTwt += WeightT[nNiz][j] * dL;
2449 }
2450 }
2451 dAvgWeights /= nPoslova;
2452 dCmax /= nPoslova*dAvgDuration;
2453 dF /= nPoslova;
2454 dFwt /= nPoslova*dAvgWeights*dAvgDuration;
2455 dT /= nPoslova;
2456 dTwt /= nPoslova*dAvgWeights*dAvgDuration;
2457 dN /= nPoslova;
2458 dNwt /= nPoslova*dAvgWeights;
2459 dTotalCmax += dCmax;
2460 dTotalF += dF;
2461 dTotalFwt += dFwt;
2462 dTotalT += dT;
2463 dTotalTwt += dTwt;
2464 dTotalN += dN;
2465 dTotalNwt += dNwt;
2466
2467 switch(m_fitness) // sto uzimamo kao fitnes?
2468 { case Twt: dRawFitness += dTwt; break;
2469 case Nwt: dRawFitness += dNwt; break;
2470 case Fwt: dRawFitness += dFwt; break;
2471 case Cmax: dRawFitness += dCmax; break;
2472 default: CHECK(0);
2473 }
2474 Fitness[nNiz][Twt] = dTwt;
2475 Fitness[nNiz][Nwt] = dNwt;
2476 Fitness[nNiz][FTwt] = 0; // zasada
2477 Fitness[nNiz][ETwt] = 0;
2478 Fitness[nNiz][Fwt] = dFwt;
2479 Fitness[nNiz][Cmax] = dCmax;
2480 }
2481
2482 } // kraj petlje koja vrti skupove poslova
2483 Fitness.data[sets][Twt] = dTotalTwt;
2484 Fitness.data[sets][Nwt] = dTotalNwt;
2485}
Fitness
Fitness base class.
Definition: Fitness.h:16
FitnessMin
Fitness for minimization problems.
Definition: FitnessMin.h:12
Permutation::Permutation
Permutation class - implements genotype as a vector of indices 0..(n-1) (permutation of indices)
Definition: Permutation.h:37
SchedulingEvalOp::initialize
bool initialize(StateP)
Initialize the evaluator. Called before first evaluation occurs.
Definition: fitnes.cpp:165
SchedulingEvalOp::evaluate
FitnessP evaluate(IndividualP individual)
Evaluate a single individual. Method must create and return a Fitness object.
Definition: fitnes.cpp:571
SchedulingEvalOp::registerParameters
void registerParameters(StateP)
Register evaluator parameters. Called before EvaluateOp::initialize method.
Definition: fitnes.cpp:154
Tree::Primitives::Primitive::setName
void setName(std::string name)
Set primitive's name.
Definition: Primitive.cpp:100
Tree::Primitives::TerminalT
Terminal tree node class (Tree genotype).
Definition: Terminal.h:16
Tree::Tree
Tree class - implements genotype as a tree.
Definition: Tree_c.h:29
Tree::Tree::copy
Tree * copy()
Create an identical copy of the genotype object.
Definition: Tree.cpp:37
_node
Definition: nodes.h:92
Generated on Wed Aug 3 2022 17:50:42 for ECF by doxygen 1.9.4