/*------------------------------------------------------------------------------ TIA 8. gyakorlat F|perm|Cmax ütemezési feladat modellezése. Egyutas előzésnélküli többoperációs ütemezési feladat. Cél: A befejezési időpont minimalizálása. 1. rész: Modellépítés és szimuláció. A Simulation_F adott műveleti idők és adott indítási sorrend esetében kiszámítja az operációk indítási és befejezési időpontjait. TIA 9. gyakorlat F2|perm|Cmax ütemezési fedadat megoldása Johnson-algoritmussal. Az algoritmus optimális megoldást eredményez (két gép esetén). TIA 10. gyakorlat F3|perm|Cmax ütemezési fedadat megoldása kiterjesztett Johnson-algoritmussal. A három gépes feladatot két virtuális gépre vezetjük vissza úgy. hogy minden munka esetében az első és a második operáció műveleti idejét összeadjuk, és a második és harmadik operáció műveleti idejét szintén összeadjuk. Az így előállított virtuális kétgépes feladatra alkalmazzuk a Johnson-algoritmust. Ha az első gép legkisebb időadata nagyobb mint a középső gép legnagyobb időadata, vagy a harmadik gép legkisebb időadata nagyobb mint a középső gép legnagyobb időadata akkor a megoldás optimális, egyébként az optimalitás nem garantálható! Továbbfejlesztett modell: F|perm|Cmax Dannenbring-módszer lényege az, hogy a tetszőleges számú sorba kapcsolódó gépeket egy virtuális kétgépes modellre vezetjük vissza egy alkalmasan megválasztott súlyozási szisztéma segítségével. Az így előállított virtuális kétgépes feladatra alkalmazzuk a Johnson-algoritmust. ======== DTFSZTIR 2. gyakorlat F|perm|Cmax Utemezesi fedadat megoldasa CDS algoritmus Továbbfejlesztett modell: F|perm|Cmax Többgépes egyutas előzés nélküli termelésiütemezési feladat. Az ütemezés célja a legkésőbbi befejezési időpont minimalizálása, ezáltal a teljes munkacsoport átfutási idejének minimalizálása. CDS-algoritmus: A Campbell-Dudek-Smith algoritmus a többgépes feladatot kétgépes problémákra vezeti vissza. Az algoritmus az eredeti NR gépes feladatból NR-1 darab mesterséges kétgépes problémát generál úgy, hogy az egymást követő gépek lesznek a kétgépes feladat gépei. A kétgépes feladatok egyenként megoldhatók a Johnson-algoritmussal. Kiválasztva közülük a teljes feladatra vonatkozó átfutási idő szempontjából a legjobbat, az lesz az NR-gépes probléma megoldása. A megodás nem optimális mert a feladat NP-hard, de jó közelítő ütemtervet eredményez. Kereső algoritmus Lokális szomszédsági kereső algoritmus implementálása (egy továbbfejleszthető alap kereső algoritmsu váz). Futási eredmények: A keresési módszer lassabban működik, de jobb eredményt ad mint a korábban vizsgált heurisztikus algoritmusok. DTFSZTIR 5. gyakorlat Munkasorrend-függő gépátállítások figyelembe vétele Gépek közötti anyagmozgatási idők modellezése DTFSZTIR 6. gyakorlat Az eroforrások időben nem folyamatosan állnak rendelkezésre. Modell bővítése: Calm Erőforrások időben korlátozottan állnak rendelkezésre Az erőforrások szakaszosan állnak rendelkezésre (Cal: saját "műszakbeosztással" rendelkeznek). F, Calm |perm|max(Ci) Szakaszosan rendelkezésre álló erőforrások terhelésére szolgáló algortimus: 1. módszer: A Load_STET_to_Cal függvény a megadott terhelést [st, et] az adott gépre megszakitás nelkul helyezi el (a legkorábbi rendelkezésre állási intervallumra, amelyen egészben elfér). DTFSZTIR 7. gyakorlat 2. módszer: A Load_STET_to_Cal_with_cut függvény a cut paraméter értékétől függően a megadott terhelést [st, et] but==0 érték esetén: az adott gépre megszakitás nelkul helyezi el (a legkorábbi rendelkezésre állási intervallumra, amelyen egészben elfér). cut==1 érték esetén: megszakitásokkal akár több darabban helyezi el az adott gép rendelkezésre állási időintervallumaira. A függvény a szimulációban kerül meghívásra. DTFSZTIR 9. gyakorlat Többcélú optimalizálás: Több célfüggvény egyidejű figyelembevétele. Evaluate függvény bővítése (Cmax, Tmax, Tsum, Usum) A megoldások egymáshoz vizsonyított relatív minőségének számszerűsítésére alapozott matematikai modell. F függvény implementálása A korábban alkalmazott kereső algoritmus továbbfejlesztése többcélű optimalizálás érdekében. -------------------------------------------------------------------------------*/ #include #include #define NOBJF 4 typedef struct { int id; long* ProcT; //pointer: muveleti idok vektorara mutat long* StartT; //pointer: inditasi idopontok vektorara mutat long* EndT; //pointer: befejezesi idopontok vektorara mutat long d; //hatarido }T_JOB; //munka typedef struct { long ST; //kezdete long ET; //vege }T_TimeWin; //idoablak typedef struct { int id; long** SetupT; //atallitasi idok matrixa long* TransT; //anyagmozgatasi idok vektora int NCal; //intervallumok szama T_TimeWin* Cal; //rendelkezesre allasi idointervallumok }T_RES; //eroforras long max_l( long a, long b) { return a>b ? a : b; } long min_l( long a, long b) { return a sel_value ) { //megjegyzem index = j; value = sel_value; } } if ( index != i ) { //csere temp = v[ index ]; v[ index ] = v[ i ]; v[ i ] = temp; } } //beutemezes first = 0; last = NJ-1; for( i=0; i 0 ) Usum++; Tsum += Ti; } Cmax = job[ s[NJ-1] ].EndT[NR-1]; ObjF[0] = Cmax; ObjF[1] = Tmax; ObjF[2] = Tsum; ObjF[3] = Usum; return Cmax; } int Johnson_alg_ext_F3( T_JOB* job, int NJ, int r, int* s) { //Johnson-algoritmus alkalmazasa harom gepes esetre int i; //munka indexe T_JOB* job_V2; //virtualis ketgepes eset idoadataihoz szukseges long pi0_min, pi1_max, pi2_min; //transzformacio ket gepres esetre job_V2 = (T_JOB*) calloc( NJ, sizeof(T_JOB) ); //strukturavektor for ( i=0; i job[i].ProcT[r] ) pi0_min = job[i].ProcT[r]; if ( pi1_max < job[i].ProcT[r+1] ) pi1_max = job[i].ProcT[r+1]; if ( pi2_min > job[i].ProcT[r+2] ) pi2_min = job[i].ProcT[r+2]; } for( i=0; i= pi1_max || pi2_min >= pi1_max ) return 1; else return 0; } void Dannenbring_F( T_JOB* job, int NJ, int NR, int* s) { //Dannenbring-algoritmus alkalmazasa int i; //munka indexe int r; //gep indexe T_JOB* job_V2; //virtualis ketgepes eset idoadataihoz szukseges //transzformacio ket gepres esetre job_V2 = (T_JOB*) calloc( NJ, sizeof(T_JOB) ); //strukturavektor for ( i=0; i= new_st ) { new_st = max( new_st, res[r].Cal[c].ST ); //intervallum kezdetre allitja new_et = new_st + size; if ( new_et <= res[r].Cal[c].ET ) { //"belefer" found = c; break; } else { //"kilog" c++; if ( c >= res[r].NCal ) { //nincs tobb intervalllum new_st = res[r].Cal[c-1].ET; new_et = new_st + size; found = -1; break; } continue; } } c++; } *st = new_st; *et = new_et; return found; } int Load_STET_to_Cal_with_cut( long* st, long* et, T_RES* res, int r, int cut) { //kereso algoritmus, amely elhelyezi a munka idokeretet //az eroforras rendelkezesre allasi idointervallumait figyelembe veve //a munka megszakithato es kesobb folytathato //szekvencialis kerese long new_st; //modosiott kezdet long new_et; //modositott befejezes long fps = -1; //first part start, elso "resz" inditas long size; //muveleti ido int c; //intervallumok indexe int found = -1; //kivlasztott intervallum sorszamat if ( cut == 0 ) return Load_STET_to_Cal( st, et, res, r); new_st = *st; size = *et - *st; new_et = new_st + size; c = 0; while( c < res[r].NCal ) //van elem { if ( res[r].Cal[c].ET >= new_st ) { new_st = max( new_st, res[r].Cal[c].ST ); //intervallum kezdetre allitja new_et = new_st + size; if ( fps == -1 ) { fps = new_st; //elso resz inditasa } if ( new_et <= res[r].Cal[c].ET ) { //"belefer" found = c; break; } else { //"kilogo reszt" tovabb visszuk c++; if ( c >= res[r].NCal ) { //nincs tobb intervalllum new_et = new_st + size; found = -1; break; } //vagas "cut" //tovabbvitt utemezetlen resz size -= res[r].Cal[c-1].ET - new_st; //new_st = res[r].Cal[c].ST; //new_et = new_st + size; continue; } } c++; } if ( fps == -1 ) *st = new_st; //nincs darabolas, eleve "kilog" else *st = fps; //elso resz kezdete *et = new_et; return found; } void Print_ObjF(double* ObjF, int NObjF) { int k; printf("\n \n A celfuggveny-ertekek:"); for (k=0; k