ECF 1.5
SchedulingEvalOp.cpp
1#include <cmath>
2#include <ecf/ECF.h>
3#include "SchedulingEvalOp.h"
4
5#include "readpar.h"
6#include "matrice.h"
7
8
9// prilagodba za ECF
10// trenutno radi:
11// single:
12// staticki
13// setup
14// constraints (?)
15
16
17
18// makroi za uvjetnu provjeru
19#define CHECKMSG(condition, text) \
20if(!(condition)) {fprintf(stderr,"file: " __FILE__ "\nline: %d\nmsg: " text "\n",__LINE__); exit(1);}
21#define CHECK(condition) \
22if(!(condition)) {fprintf(stderr,"Nesto ne valja!\nfile: " __FILE__ "\nline: %d\n" ,__LINE__); exit(1);}
23// fja max{x,0}
24#define POS(x) (x>0 ? x : 0)
25#define MIN(x,y) (x<y ? x : y)
26#define MAX(x,y) (x>y ? x : y)
27
28// fitness_types
29const int Twt = 0;
30const int Nwt = 1;
31const int FTwt = 2;
32const int ETwt = 3;
33const int Fwt = 4;
34const int Cmax = 5;
35const int FUNCTIONS = 6;
36
37
38void SchedulingEvalOp::registerParameters(StateP state)
39{
40 state->getRegistry()->registerEntry("test_cases", (voidP) (new std::string), ECF::STRING);
41 state->getRegistry()->registerEntry("normalized", (voidP) (new uint(1)), ECF::UINT);
42}
43
44
45bool SchedulingEvalOp::initialize(StateP state)
46{
47 std::string configFile;
48
49 // check if the parameters are defined in the conf. file
50 if(!state->getRegistry()->isModified("test_cases"))
51 return false;
52
53 voidP sptr = state->getRegistry()->getEntry("test_cases"); // get parameter value
54 configFile = *((std::string*) sptr.get()); // convert from voidP to user defined type
55
56 sptr = state->getRegistry()->getEntry("normalized"); // get parameter value
57 m_Normalized = (bool) *((uint*) sptr.get()); // convert from voidP to user defined type
58
59// originalni dio iz BEAGLE implementacije:
60 std::string input,sp,duration,deadline,weightT,weightF,weightE,weightN,term,ready,cons,speed;
61 char pom[256];
62 ReadPar p;
63 unsigned int i,j;
64 double d_niz[2][1000];
65
66 // inicijalizacija default vrijednosti
67 input = configFile; // glavni ulazni fajl, mora ga biti
68
69 // ucitavanje parametara
70 p.OpenFile(input.c_str());
71 if(p.ReadParameter("single",ReadPar::INTEGER,&i))
72 m_Environment = SINGLE;
73 else if(p.ReadParameter("uniform",ReadPar::INTEGER,&i))
74 m_Environment = UNIFORM;
75 else if(p.ReadParameter("unrelated",ReadPar::INTEGER,&i))
76 m_Environment = UNRELATED;
77 else if(p.ReadParameter("jobshop",ReadPar::INTEGER,&i))
78 m_Environment = JOBSHOP;
79 p.ReadParameter("sets",ReadPar::INTEGER,&sets);
80 p.ReadParameter("max_jobs",ReadPar::INTEGER,&max_jobs);
81 if(!p.ReadParameter("max_machines",ReadPar::INTEGER,&max_machines))
82 max_machines = 1;
83 p.ReadParameter("max_length",ReadPar::INTEGER,&max_length);
84 p.ReadParameter("duration",ReadPar::STRING,pom); duration = pom;
85 p.ReadParameter("deadline",ReadPar::STRING,pom); deadline = pom;
86 p.ReadParameter("weight_T",ReadPar::STRING,pom); weightT = pom;
87 p.ReadParameter("weight_F",ReadPar::STRING,pom); weightF = pom;
88 p.ReadParameter("weight_E",ReadPar::STRING,pom); weightE = pom;
89 p.ReadParameter("weight_N",ReadPar::STRING,pom); weightN = pom;
90 p.ReadParameter("SP",ReadPar::STRING,pom); sp = pom;
91 p.ReadParameter("machine_file",ReadPar::STRING,pom); speed = pom;
92 // dinamicki dolasci poslova
93 if(p.ReadParameter("ready",ReadPar::STRING,pom))
94 { ready = pom;
95 m_dynamic = true;
96 }
97 else
98 m_dynamic = false;
99 // limited error fitness izracunavanje
100 if(p.ReadParameter("LEF",ReadPar::INTEGER,&i))
101 { if(i==1)
102 { m_LEF = true;
103 if(!p.ReadParameter("LEF_value",ReadPar::DOUBLE,&m_LEFVal))
104 CHECKMSG(0,"LEF vrijednost nije zadana!");
105 }
106 else
107 m_LEF = false;
108 }
109 // evaluacija - ispis rjesenja za svaku jedinku
110 if(p.ReadParameter("evaluation",ReadPar::INTEGER,&i))
111 if(i==1) m_Evaluation = true;
112 else m_Evaluation = false;
113 // fitness - mora biti definiran
114 if(p.ReadParameter("fitness",ReadPar::STRING,pom))
115 { input = pom;
116 if(input == "Twt")
117 m_fitness = Twt;
118 else if(input == "Nwt")
119 m_fitness = Nwt;
120 else if(input == "FTwt")
121 m_fitness = FTwt;
122 else if(input == "ETwt")
123 m_fitness = ETwt;
124 else if(input == "Cmax")
125 m_fitness = Cmax;
126 else if(input == "Fwt")
127 m_fitness = Fwt;
128 else
129 CHECKMSG(0,"Nepoznata fitnes funkcija!");
130 }
131 else CHECKMSG(0,"Nije definirana fitnes funkcija!");
132 // editiranje jedinke
133 if(p.ReadParameter("editing",ReadPar::INTEGER,&i))
134 if(i==1) m_editing = true;
135 // stochastic sampling, koliko
136 if(p.ReadParameter("stsampling",ReadPar::DOUBLE,&m_sampling))
137 m_stsampling = true;
138 else
139 m_stsampling = false;
140 // ogranicenja u rasporedu
141 if(p.ReadParameter("constraints",ReadPar::STRING,pom))
142 { cons = pom;
143 m_constrained = true;
144 }
145 else
146 m_constrained = false;
147 // trajanja postavljanja
148 if(p.ReadParameter("setup",ReadPar::DOUBLE,&m_setup_faktor))
149 m_setup = true;
150 else
151 m_setup = false;
152
153 if(p.ReadParameter("idleness",ReadPar::INTEGER, &i))
154 if(i == 1) m_Idleness = true;
155
156 //duration = path + duration;
157 //deadline = path + deadline;
158 //sp = path + sp;
159 //weightT = path + weightT;
160 //weightF = path + weightF;
161 //weightE = path + weightE;
162 //weightN = path + weightN;
163 //ready = path + ready;
164 N.Init(sets);
165 SP.Init(sets);
166 SD.Init(sets);
167 Machines.Init(sets);
168 MachineReady.Init(max_machines);
169 Speed.Init(sets,max_jobs);
170 Duration.Init(sets,max_jobs);
171 Deadline.Init(sets,max_jobs);
172 Durations.Init(max_jobs, max_machines);
173 MachineIndex.Init(max_jobs, max_machines);
174 WeightT.Init(sets,max_jobs);
175 WeightF.Init(sets,max_jobs);
176 WeightE.Init(sets,max_jobs);
177 WeightN.Init(sets,max_jobs);
178 Fitness.Init(sets+1,FUNCTIONS);
179 Values.Init(max_machines,max_jobs);
180 Precedence.Reset(max_jobs,max_jobs); // prazna matrica znaci da nema ogranicenja!
181 Setup.Init(max_jobs+1,max_jobs);
182 if(m_Environment == JOBSHOP)
183 { Schedule.Init(sets, max_machines*max_jobs);
184 PTimeAvg.Reset(sets, max_machines);
185 }
186 else
187 { Schedule.Init(sets,max_jobs);
188 PTimeAvg.Init(sets,max_jobs);
189 PTimeMinMachine.Init(sets,max_jobs);
190 }
191 SortedReady.Init(sets,max_jobs);
192
193 pVrijednosti = new double[max_jobs];
194 pRasporedjen = new bool[max_jobs];
195 pIndex = new unsigned int[max_jobs];
196 pUsed = new unsigned int[max_jobs];
197 pArray = new double[max_jobs];
198 pSlack = new double[max_jobs];
199 pSlackSpeed = new double[max_jobs];
200 pArrival = new double[max_jobs];
201 pLevel = new double[max_jobs];
202 pSetupAvg = new double[max_jobs + 1];
203 pSamples = new bool[sets];
204 pLastJob = new unsigned int[max_machines];
205 pMachineScheduled = new unsigned int[max_machines];
206 pOperationReady = new double[max_machines];
207 pJobReady = new double[max_jobs];
208 pOperationsScheduled = new unsigned int[max_jobs];
209 pTotalWorkRemaining = new double[max_jobs];
210 pTotalWorkDone = new double[max_jobs];
211 pTotalMachineWork = new double[max_machines];
212 pOperationsWaiting = new unsigned int[max_machines];
213 pMachineWorkRemaining = new double[max_machines];
214 pMachineValues = new double[max_machines];
215 p.ReadParameter("jobs",ReadPar::DOUBLE,&d_niz[0][0],sets);
216 p.ReadParameter("machines",ReadPar::DOUBLE,&d_niz[1][0],sets);
217 total_jobs = 0;
218 for(i=0; i<sets; i++)
219 { N[i][0] = d_niz[0][i];
220 total_jobs += (int) d_niz[0][i];
221 Machines[i][0] = d_niz[1][i];
222 }
223 Duration.Load(duration.c_str());
224 Deadline.Load(deadline.c_str());
225 if(m_Environment==UNIFORM)
226 { Speed.Load(speed.c_str());
227 }
228 WeightT.Load(weightT.c_str());
229 WeightF.Load(weightF.c_str());
230 WeightE.Load(weightE.c_str());
231 WeightN.Load(weightN.c_str());
232 SP.Load(sp.c_str());
233 if(m_dynamic) Ready.Load(ready.c_str());
234 else Ready.Reset(sets,max_jobs);
235 if(m_constrained) Constraints.Load(cons.c_str());
236 // racunamo sumu deadline-a
237 Level.Init(sets,max_jobs);
238 for(i=0; i<sets; i++)
239 { SD.Set(i,0);
240 for(j=0; j<(unsigned int)N.Get(i); j++)
241 { SD.data[i][0] += Deadline.data[i][j];
242 Level[i][j] = -1; // oznacimo da je neizracunato
243 }
244 }
245 // racunamo level cvorova u grafu ovisnosti
246 for(i=0; i<sets; i++)
247 { if(m_constrained)
248 ReadConstraints(Constraints,i,(unsigned int)N.Get(i),Precedence);
249 for(j=0; j<(unsigned int)N.Get(i); j++)
250 Level[i][j] = NodeLevel(i,j);
251 }
252 // racunamo prosjek i minimalno trajanje izvodjenja za UNRELATED
253 if(m_Environment == UNRELATED)
254 { for(uint set=0; set<sets; set++)
255 { uint jobs = (uint) N[set][0];
256 uint machines = (uint) Machines[set][0];
257 for(j=0; j<jobs; j++)
258 { PTimeAvg[set][j] = 0;
259 uint min_machine = 0;
260 for(uint machine=0; machine<machines; machine++)
261 { PTimeAvg[set][j] += Duration[set][j*machines + machine];
262 if(Duration[set][j*machines + machine] < Duration[set][j*machines + min_machine])
263 min_machine = machine;
264 }
265 PTimeAvg[set][j] /= machines;
266 PTimeMinMachine[set][j] = min_machine;
267 }
268 }
269 }
270 if(m_Environment == JOBSHOP) // prosjek trajanja operacija po strojevima
271 { for(uint set=0; set<sets; set++)
272 { uint jobs = (uint) N[set][0];
273 uint machines = (uint) Machines[set][0];
274 for(j=0; j<jobs; j++)
275 { uint operations = machines;
276 for(uint op=0; op<operations; op++)
277 { double dur = Duration[set][j*operations + op];
278 uint machine = (uint) dur / 1000;
279 dur = (int)dur % 1000; // dobijemo trajanje
280 PTimeAvg[set][machine] += dur;
281 }
282 }
283 for(uint m=0; m<machines; m++)
284 PTimeAvg[set][m] /= jobs;
285 }
286 }
287
288 // sortiramo indekse poslova po dolascima - treba za ubrzano izracunavanje
289 //for(i=0; i<sets; i++)
290 //{ ::pVal = Ready[i];
291 // uint jobs = (uint) N[i][0];
292 // for(j=0; j<jobs; j++)
293 // pIndex[j] = j;
294 // qsort(pIndex,jobs,sizeof(unsigned int),::Before);
295 // for(j=0; j<jobs; j++)
296 // SortedReady[i][j] = pIndex[j];
297 //}
298
299 p.CloseFile();
300
301 return true;
302}
303
304
305// rekurzivno racunanje 'level' vrijednosti svakog posla
306// ima smisla samo u problemima s ogranicenjima
307// promjena 27.07: level cvora ukljucuje i trajanje cvora
308double SchedulingEvalOp::NodeLevel(int set, int node)
309{ double value,level;
310 int succ,i,next;
311 if(Level[set][node] > -1) // ako je vec izracunato
312 return Level[set][node];
313 if(Precedence[node][1] == 0) // ako nema sljedbenika
314 return Duration[set][node];
315 succ = (int)Precedence[node][1]; // koliko sljedbenika
316 next = (int)Precedence[node][2]; // prvi sljedbenik
317 level = NodeLevel(set,next) + Duration[set][node]; // level zbog prvog sljedbenika
318 for(i=1; i<succ; i++)
319 { next = (int)Precedence[node][i+2];
320 value = NodeLevel(set,next) + Duration[set][node];
321 if(value > level)
322 level = value;
323 }
324 return level;
325}
326
327
328
329
330SchedulingEvalOp::~SchedulingEvalOp()
331{
332 delete [] pRasporedjen;
333 delete [] pVrijednosti;
334 delete [] pIndex;
335 delete [] pUsed;
336 delete [] pArray;
337 delete [] pSlack;
338 delete [] pSlackSpeed;
339 delete [] pSamples;
340 delete [] pArrival;
341 delete [] pLevel;
342 delete [] pSetupAvg;
343 delete [] pLastJob;
344 delete [] pMachineScheduled;
345 delete [] pOperationReady;
346 delete [] pJobReady;
347 delete [] pOperationsScheduled;
348 delete [] pTotalWorkRemaining;
349 delete [] pTotalWorkDone;
350 delete [] pTotalMachineWork;
351 delete [] pMachineWorkRemaining;
352 delete [] pOperationsWaiting;
353 delete [] pMachineValues;
354}
355
356
357// dekodira matricu Constraints i definira matricu Precedence
358void SchedulingEvalOp::ReadConstraints(Matrica &Constraints, int set, int jobs, Matrica &Precedence)
359{
360 int i,j,prethodnika,prethodnik,pom;
361 unsigned int podatak;
362 //Precedence.Init(jobs,jobs);
363 // prvo ocistimo prva dva stupca! gdje su brojevi prethodnika i sljedbenika
364 for(i=0; i<jobs; i++)
365 for(j=0; j<2; j++)
366 Precedence[i][j] = 0;
367 for(i=0; i<jobs; i++)
368 { podatak = (unsigned int) Constraints[set][i];
369 prethodnik = 1; // koji po redu posao iza mene
370 prethodnika = 0;
371 while(podatak != 0)
372 { if(podatak%2 != 0)
373 { prethodnika++; // povecam broj svojih prethodnika
374 pom = (int) Precedence[i-prethodnik][1] + 1;
375 Precedence[i-prethodnik][pom+1] = i;
376 Precedence[i-prethodnik][1] = pom; // i broj sljedbenika od moga prethodnika
377 }
378 prethodnik++;
379 podatak /= 2;
380 }
381 Precedence[i][0] = prethodnika;
382 }
383}
384
385
386// generira matricu sequence dependant setup trajanja
387// i polje prosjecnih trajanja postavljanja za svaki posao prema ostalima
388void SchedulingEvalOp::MakeSetup(Matrica &Duration, int set, int jobs, double faktor, Matrica &Setup)
389{
390 int i,j;
391 pSetupAvg[jobs] = 0;
392 if(m_Environment == JOBSHOP)
393 { srand(set);
394 for(i=0; i<jobs; i++)
395 { Setup[jobs][i] = (int) ((rand()%max_length+1) * faktor); // polazno trajanje postavljanja
396 pSetupAvg[jobs] += Setup[jobs][i];
397 for(j=0; j<=i; j++)
398 { Setup[i][j] = (int) ((rand()%max_length+1) * faktor);
399 Setup[j][i] = (int) ((rand()%max_length+1) * faktor);
400 pSetupAvg[i] += Setup[i][j];
401 pSetupAvg[j] += Setup[j][i];
402 }
403 }
404 }
405 else
406 for(i=0; i<jobs; i++)
407 { pSetupAvg[i] = 0;
408 Setup[jobs][i] = Duration[set][(i+1) % jobs]; // polazno trajanje postavljanja
409 pSetupAvg[jobs] += Setup[jobs][i];
410 for(j=0; j<=i; j++)
411 { Setup[i][j] = ceil( fabs( Duration[set][i] - Duration[set][j] ) * faktor);
412 Setup[j][i] = ceil( fabs( Duration[set][(i+1) % jobs] - Duration[set][(j+1) % jobs] ) * faktor);
413 pSetupAvg[i] += Setup[i][j];
414 pSetupAvg[j] += Setup[j][i];
415 }
416 }
417 pSetupAvg[jobs] /= jobs;
418 for(i=0; i<jobs; i++)
419 pSetupAvg[i] /= (jobs-1);
420}
421
422
423FitnessP SchedulingEvalOp::evaluate(IndividualP individual)
424{
425 // stvaranje zeljenog Fintess objekta:
426 FitnessP fitness = static_cast<FitnessP> (new FitnessMin);
427
428 // dohvat genotipa jedinke
429 TreeP tree = boost::dynamic_pointer_cast<Tree::Tree> (individual->getGenotype());
430
431// oroginalni kod iz BEAGLE implementacije
432 unsigned int i;
433 double dRawFitness, dFitness;
434
435 // stochastic sampling?
436 if(m_stsampling)
437 { int koliko = (int) (m_sampling*sets);
438 int razmak = sets / koliko;
439 int pocetni = rand()%razmak;
440 for(i=0; i<sets; i++)
441 pSamples[i] = false;
442 for(i=pocetni; i<sets; i+=razmak)
443 pSamples[i] = true;
444 }
445
446 switch(m_Environment)
447 { case SINGLE:
448 dRawFitness = EvaluateSingle(tree);
449 break;
450 //case UNIFORM:
451 // EvaluateUniform(dRawFitness);
452 //break;
453 //case UNRELATED:
454 // EvaluateUnrelated(dRawFitness);
455 //break;
456 //case JOBSHOP:
457 // EvaluateJobShop(dRawFitness);
458 //break;
459 }
460
461 //dFitness = dRawFitness /= nJobS*SETS; // prosjek
462 //double lRMSE = sqrt(sqrt(dRawFitness)); // irelevantno za turnir selekciju
463 //dFitness = (1.0 / (lRMSE + 1.0));
464 //dFitness = -dRawFitness; // obrnemo kriterij (trazimo minimum)
465 dFitness = dRawFitness;
466
467 //if(m_Evaluation) // samo za usporedbu heuristika! pise rezultate svih skupova u fajl
468 //{ Fitness.Save("rezultat_GP.txt");
469 // std::ostream *file = new std::ofstream("rezultat_GP.txt", std::ios_base::app);
470 // Evaluator.write();
471 // *file << std::endl << "-- infix: " << Evaluator.m_output << " --" << std::endl;
472 // *file << "Editirano: " << edited << ", ukupno: " << total << std::endl;
473 // *file << std::flush;
474 // delete file;
475 // Schedule.Save("raspored_GP.txt");
476 //}
477
478 fitness->setValue(dFitness);
479
480 return fitness;
481}
482
483
484// obrada za SINGLE okruzenje
485double SchedulingEvalOp::EvaluateSingle(TreeP tree)
486{
487 double dClock, dRez, dSetFitness, dAvgWeights, dAvgDuration, dAvgDueDate;
488 double dLateness, dTotalLateness=0, dTardiness, dTotalTardiness=0;
489 double dNwt, dTotalNwt=0, dBest, dSPr, dSDr;
490 unsigned int nPoslova,nNiz,nJob,i,j,index,nLateJobs,nTotalLateJobs=0,nNr;
491 unsigned int nLastJob,nOdabrani;
492
493 double dRawFitness=0;
494
495// vrtimo sve skupove
496 for(nNiz = 0; nNiz < sets; nNiz++)
497 { nNr = nPoslova = (int) N.Get(nNiz);
498 // preliminarna ispitivanja
499 // radimo li stochastic sampling
500 if(m_stsampling)
501 if(pSamples[nNiz] == false)
502 continue; // jednostavno preskocimo taj test case
503 // gleda li se limited error fitness
504 if(m_LEF)
505 { if(dRawFitness > m_LEFVal)
506 break; // prekid ispitivanja
507 }
508 if(m_constrained) // ima li ogranicenja
509 ReadConstraints(Constraints,nNiz,nPoslova,Precedence);
510 if(m_setup) // trajanja postavljanja
511 MakeSetup(Duration,nNiz,nPoslova,m_setup_faktor,Setup);
512
513 // postavljanje pocetnih vrijednosti za pojedini skup
514 nLateJobs = 0;
515 dLateness = 0;
516 dTardiness = 0;
517 dNwt = 0;
518 dClock = 0; dSetFitness = 0;
519 nLastJob = nPoslova;
520 dAvgDueDate = 0;
521 for(i=0; i<nPoslova; i++)
522 { dAvgDueDate += Deadline[nNiz][i];
523 pRasporedjen[i] = false; // svi nerasporedjeni
524 pIndex[i] = i; // inicijalni poredak
525 }
526 dAvgDueDate /= nPoslova;
527 dSPr = SP.Get(nNiz);
528 dSDr = SD.Get(nNiz);
529
530 // postavljanje pocetnih vrijednosti terminala - nepromjenjivi terminali
531/* Evaluator.m_pTermValues[T_N] = N.Get(nNiz);
532 Evaluator.SetTermArraySize(nPoslova); // koliko poslova u skupu - za vektorsku evaluaciju
533 Evaluator.pIndex = pIndex; // polje indeksa poslova
534 Evaluator.m_iOffset = 0; // indeks prvog nerasporedjenog
535 for(i=0; i<nPoslova; i++)
536 { Evaluator.m_dTermValuesArray[T_N][i] = N.data[nNiz][0];
537 Evaluator.m_dTermValuesArray[T_SP][i] = SP.data[nNiz][0];
538 Evaluator.m_dTermValuesArray[T_SD][i] = SD.data[nNiz][0];
539 Evaluator.m_dTermValuesArray[T_SC][i] = Precedence[i][1]; // broj sljedbenika
540 Evaluator.m_dTermValuesArray[T_TF][i] = 1 - dAvgDueDate / SP[nNiz][0];
541 }
542 memcpy(Evaluator.m_dTermValuesArray[T_pt], Duration.data[nNiz], nPoslova*sizeof(double));
543 memcpy(Evaluator.m_dTermValuesArray[T_dd], Deadline.data[nNiz], nPoslova*sizeof(double));
544 memcpy(Evaluator.m_dTermValuesArray[T_w], WeightT.data[nNiz], nPoslova*sizeof(double));
545 memcpy(Evaluator.m_dTermValuesArray[T_LVL], Level[nNiz], nPoslova*sizeof(double));
546*/
547
549// ako u terminalima ima vremenski ovisnih, moramo raditi posao po posao
550 for(nJob=0; nJob<nPoslova; nJob++) // rasporedjujemo svaki posao unutar skupa jedan po jedan
551 {
552 // terminali neovisni o poslu (ali ovisni o rasporedjenim poslovima!)
553 tree->setTerminalValue("SPr", &dSPr); // suma trajanja preostalih
554 tree->setTerminalValue("Nr", &nNr); // broj preostalih
555
556 // dinamicka okolina; + uzeta u obzir eventualna ogranicenja
557 if(m_dynamic)
558 { unsigned int raspolozivi = nJob, prvi = nJob;
559 unsigned int najkraci; // najkraci raspolozivi
560 // trebamo pronaci prvog raspolozivog bez nezavrsenih prethodnika
561 for(; Precedence[pIndex[raspolozivi]][0] > 0; raspolozivi++) NULL;
562 double kada = Ready[nNiz][pIndex[raspolozivi]]; // pocetno vrijeme
563 double najdulje = 0, najkrace = 0;
564 for( ; raspolozivi < nPoslova; raspolozivi++) // koji je 'najstariji'?
565 { int job = pIndex[raspolozivi];
566 if(Ready.data[nNiz][job] < kada && Precedence[job][0] == 0) // gledamo najblize vrijeme dolaska
567 { kada = Ready.data[nNiz][job];
568 prvi = raspolozivi;
569 }
570 }
571 if(kada > dClock) // ako nema raspolozivih
572 { dClock = kada; // sat postavimo na najblize vrijeme dolaska
573 }
574 // pronadjimo najduljeg i najkraceg raspolozivog
575 najdulje = najkrace = Duration[nNiz][pIndex[prvi]];
576 najkraci = prvi;
577 for(i = nJob; i < nPoslova; i++)
578 { int job = pIndex[i];
579 if(dClock < Ready[nNiz][job] || Precedence[job][0] > 0)
580 continue;
581 if(Duration[nNiz][job] < najkrace) // najkrace
582 { najkrace = Duration[nNiz][job];
583 najkraci = i;
584 }
585 }
586 // sad pogledamo najduljega koji pocinje <= zavrsetka najkraceg raspolozivog
587 for(i = nJob; i < nPoslova; i++)
588 { int job = pIndex[i];
589 if(Precedence[job][0] > 0)
590 continue;
591 if(Duration[nNiz][job] > najdulje && Ready[nNiz][job] <= (dClock+najkrace)) // gledamo najdulje trajanje
592 najdulje = Duration[nNiz][job];
593 }
594 // sada je (dClock + najkrace + najdulje) limit za gledanje u buducnost!
595
596 // trebamo izracunati nove vrijednosti vremenski ovisnih terminala!
597 double dCurrent;
598 for(i = nJob; i<nPoslova; i++)
599 { j = pIndex[i];
600 // terminali ovisni o poslu
601 pSlack[j] = POS(Deadline[nNiz][j] - (dClock + Duration[nNiz][j]));
602 tree->setTerminalValue("SL", &pSlack[j]);
603 tree->setTerminalValue("pt", &Duration[nNiz][j]);
604 tree->setTerminalValue("w", &WeightT[nNiz][j]);
605 tree->setTerminalValue("dd", &Deadline[nNiz][j]);
606
607 // terminali za trajanja postavljanja
608 if(m_setup) {
609 tree->setTerminalValue("STP", &Setup[nLastJob][j]); // trajanje postavljanja
610 tree->setTerminalValue("Sav", &pSetupAvg[nLastJob]); // prosjecno t.p.
611 }
612
613 // terminali za ogranicenja u redoslijedu
614 if(m_constrained) {
615 tree->setTerminalValue("SC", &Precedence[j][1]); // broj sljedbenika
616 tree->setTerminalValue("LVL", &Level[nNiz][j]); // razina posla (level)
617 }
618
619 tree->execute(&dCurrent);
620 pVrijednosti[j] = dCurrent;
621 }
622
623 // druga verzija (jednostavnija)
624 // samo gledamo najboljega koji moze poceti prije zavrsetka najkraceg raspolozivog
625 dBest = pVrijednosti[pIndex[najkraci]]; // poc. vrijednost za usporedbu
626 nOdabrani = najkraci;
627 for(i=nJob; i<nPoslova; i++) // trazimo najbolju vrijednost unutar < (dClock + najkrace)
628 { if((pVrijednosti[pIndex[i]] < dBest) && (Ready[nNiz][pIndex[i]] < dClock + najkrace) \
629 && Precedence[pIndex[i]][0] == 0)
630 { dBest = pVrijednosti[pIndex[i]];
631 nOdabrani = i;
632 }
633 }
634 kada = Ready[nNiz][pIndex[nOdabrani]] - dClock; // za koliko pocinje odabrani?
635
636 // redovni nastavak (iza 1. i 2. verzije)
637 if(kada > 0) // odabrali smo cekati
638 dClock += kada; // ili: dClock = Ready[nNiz][pIndex[nOdabrani]];
639 } // endif - m_dynamic
640
641 // staticki
642 else
643 { //CalcTimedTerminals(nNiz,nPoslova,nJob,dClock);
644
645 double dCurrent;
646
647 // ocijeni sve nerasporedjene poslove
648 for(i = nJob; i<nPoslova; i++)
649 { j = pIndex[i];
650 // terminali ovisni o poslu
651 pSlack[j] = POS(Deadline[nNiz][j] - (dClock + Duration[nNiz][j]));
652 tree->setTerminalValue("SL", &pSlack[j]);
653 tree->setTerminalValue("pt", &Duration[nNiz][j]);
654 tree->setTerminalValue("w", &WeightT[nNiz][j]);
655 tree->setTerminalValue("dd", &Deadline[nNiz][j]);
656
657 // terminali za trajanja postavljanja
658 if(m_setup) {
659 tree->setTerminalValue("STP", &Setup[nLastJob][j]); // trajanje postavljanja
660 tree->setTerminalValue("Sav", &pSetupAvg[nLastJob]); // prosjecno t.p.
661 }
662
663 // terminali za ogranicenja u redoslijedu
664 if(m_constrained) {
665 tree->setTerminalValue("SC", &Precedence[j][1]); // broj sljedbenika
666 tree->setTerminalValue("LVL", &Level[nNiz][j]); // razina posla (level)
667 }
668
669 tree->execute(&dCurrent);
670
671 pVrijednosti[j] = dCurrent;
672 }
673
674 dBest = pVrijednosti[pIndex[nJob]]; // pretpostavimo da je neki najbolji
675 nOdabrani = nJob;
676
677 if(m_constrained) // trazimo prvi bez prethodnika
678 for(; Precedence[pIndex[nOdabrani]][0] > 0; nOdabrani++) NULL;
679
680 for(i = nJob; i<nPoslova; i++) // pa pogledamo ostale
681 { // trazimo najmanju vrijednost
682 int index = pIndex[i];
683 if(pVrijednosti[index] < dBest && Precedence[index][0] == 0) // je li to najbolja vrijednost?
684 { dBest = pVrijednosti[index];
685 nOdabrani = i;
686 }
687 }
688 }
689
690 // vrijednost pIndex[nOdabrani] je indeks posla koji ide sljedeci
691 // gledamo nOdabrani kao rezultat; zamijenimo nJob-ti i odabrani u polju indeksa
692 i = pIndex[nJob];
693 pIndex[nJob] = pIndex[nOdabrani];
694 pIndex[nOdabrani] = i;
695 pRasporedjen[pIndex[nJob]] = true;
696
697 // azuriramo vrijednosti promjenjivih terminala
698 dClock += Duration[nNiz][pIndex[nJob]]; // update vremena
699 dSPr -= Duration[nNiz][pIndex[nJob]]; // update trajanja preostalih
700 dSDr -= Deadline[nNiz][pIndex[nJob]]; // update deadlinea
701 nNr--; // update broja preostalih
702 if(m_constrained) // smanjimo broj prethodnika svim sljedbenicima odabranog posla
703 for(i=0; i<Precedence[pIndex[nJob]][1]; i++)
704 { j = (int) Precedence[pIndex[nJob]][i+2];
705 Precedence[j][0] -= 1;
706 }
707 if(m_setup) // trajanje postavljanja
708 { dClock += Setup[nLastJob][pIndex[nJob]];
709 nLastJob = pIndex[nJob]; // sljedeci prethodni posao
710 }
711 Schedule[nNiz][nJob] = pIndex[nJob]; // zapisemo posao u raspored
712 } // kraj petlje koja vrti poslove u skupu
713
714
715 // racunanje raznih kriterija za trenutni skup
716 { if(m_Evaluation)
717 { for(nJob=nPoslova ; nJob < this->max_jobs; nJob++)
718 Schedule[nNiz][nJob] = 0; // ostalo nule
719 }
720 // odredimo fitnes kriterij - sve moguce funkcije
721 dClock = 0; nLastJob = nPoslova; dAvgWeights = dAvgDuration = 0;
722 for(nJob = 0; nJob<nPoslova; nJob++)
723 { index = pIndex[nJob];
724 dAvgWeights += WeightT[nNiz][index];
725 dAvgDuration += Duration[nNiz][index];
726 if(m_dynamic && dClock < Ready[nNiz][index]) // ako jos nije raspoloziv
727 dClock = Ready[nNiz][index];
728 if(m_setup)
729 dClock += Setup[nLastJob][index];
730 nLastJob = index;
731 dClock += Duration.data[nNiz][index]; // update vremena
732 dRez = dClock - Deadline.Get(nNiz,index); // kasnjenje
733 dLateness += dRez*WeightT.data[nNiz][index]; // tezinsko kasnjenje
734 if(dRez > 0) dTardiness += dRez*WeightT.data[nNiz][index]; // tezinska zakasnjelost
735 if(dRez > 0) nLateJobs ++; // kao broj zakasnjelih poslova
736 if(dRez > 0) dNwt += WeightN.data[nNiz][index]; // tezinski broj zakasnjelih
737 }
738 // normiranje fitnesa ovisno o broju poslova - dodano 27.07.
739 // promijenjeno (valjda konacno) 04.09.
740 if(m_Normalized) {
741 dAvgWeights /= nPoslova; // prosjecni tezinski faktor skupa
742 dAvgDuration /= nPoslova;
743 dTardiness /= (nPoslova * dAvgWeights * dAvgDuration);
744 dNwt /= (nPoslova * dAvgWeights);
745 }
746 switch(m_fitness) // sto uzimamo kao fitnes?
747 { case Twt: dRawFitness += dTardiness; break;
748 case Nwt: dRawFitness += dNwt; break;
749 default: exit(1);
750 }
751 nTotalLateJobs += nLateJobs;
752 dTotalNwt += dNwt;
753 dTotalLateness += dLateness;
754 dTotalTardiness += dTardiness;
755 Fitness[nNiz][Twt] = dTardiness;
756 Fitness[nNiz][Nwt] = dNwt;
757 Fitness[nNiz][FTwt] = 0; // zasada
758 Fitness[nNiz][ETwt] = 0;
759 }
760 }
761// kraj petlje koja vrti skupove poslova
762
763 Fitness[sets][Twt] = dTotalTardiness;
764 Fitness[sets][Nwt] = dTotalNwt;
765
766 return dRawFitness;
767}
Fitness
Fitness base class.
Definition: Fitness.h:16
FitnessMin
Fitness for minimization problems.
Definition: FitnessMin.h:12
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
_node
Definition: nodes.h:92
Generated on Wed Aug 3 2022 17:50:42 for ECF by doxygen 1.9.4