/*------------------------------------------------------------------------------ TIA 6. gyakorlat F|perm|Cmax 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 7. 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 9. 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|permut|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. TIA 10. gyakorlat F|perm|Cmax Utemezesi fedadat megoldasa kereső algoritmus alkalmazásával. 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 2. gyakorlat Továbbfejlesztés: A gépek átállításának (set-up) modellezése. Anyagmozgatási (logisztikai) idők figyelembe vétele. A szimuláció bővítése. DTFSZTIR 3. gyakorlat Modell bővítése: 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 4. gyakorlat Szakaszosan rendelkezésre álló erőforrások terhelésére szolgáló algortimus: 2. módszer: A Load_STET_to_Cal_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. -------------------------------------------------------------------------------*/ #include #include #include typedef struct{ int id; //azonosito long* ProcT; //muveleti idok vektora long* StartT; //inditasi idopontok vektora long* EndT; //befejezesi idopontok vektora } T_JOB; typedef struct{ long st; //kezdet long et; //vege } T_TW; //timewindow typedef struct{ int id; //azonosito long** SetT; //atallasi ido, set-up long* TransT; //anyagmozgatasi ido, transportation time //az aktualis gepre erkezes egy masik geprol int NC; //number of calendar, az intervallumok szama T_TW* Cal; //calendar, id[intervallumok sorozata } T_RES; //eroforras /*CodeBlocks eseten definialjuk a max fuggvenyt long max(long a, long b) { return a>=b ? a : b; } long min(long a, long b) { return a<=b ? a : b; } */ void Simulation_F(T_JOB* job, int NJ, T_RES* res, int NR, int* s, long t0, int cut); long Evaluate_F(T_JOB* job, int NJ, int NR, int* s); void Print_Res_Gantt(T_JOB* job, int NJ, int NR, int* s); void Johnson_alg(T_JOB* job, int NJ, int r, int* s); void Johnson_alg_ext_F3(T_JOB* job, int NJ, int r, int* s); void Dannenbring_alg(T_JOB* job, int NJ, int NR, int* s); void copy_sch(int* s1, int* s2, int NJ); void CDS_alg(T_JOB* job, int NJ, T_RES* res, int NR, int* s, int cut); void Search_alg(T_JOB* job, int NJ, T_RES* res, int NR, int* s, int STEP, int LOOP, int cut); void Neighbour( int* s_0, int* s_act, int NJ); int Load_STET_to_Cal( long* st, long* et, T_RES* res, int r); int Load_STET_to_Cal_cut( long* st, long* et, T_RES* res, int r, int cut); void Print_Res_Cal(T_RES* res, int NR); int main() { time_t t; int NJ; //number of jobs int i, j; //index of jobs int NR; //number of resources int r, k; //index of resources int c; //index of timewindow int cut; //a munkak megszakithatosagat jelzi T_JOB* job; //jobs T_RES* res; //resources int* s; //schedule long Cmax; //celfv erteke //A termelesinformatikai integralt rendszerbol lekerdezheto printf("\n Flow Shop demo."); printf("\n Kerem a munkak szamat:"); scanf("%d", &NJ); //ellenorzes nincs printf("\n Kerem a eroforrasok szamat:"); scanf("%d", &NR); //ellenorzes nincs srand( time(&t) ); //inic. s = (int*) calloc(NJ, sizeof(int)); //utemterv job = (T_JOB*) calloc(NJ, sizeof(T_JOB)); //strukturavektor for (i=0; i act_val ) { //a jelolt megjegyzese min_index = j; min_val = act_val; } } if ( min_index != i ) { //csere szukseges temp = v[ i ]; v[ i ] = v[ min_index ]; v[ min_index ] = temp; } } //rendezes kesz //Utemezes first = 0; last = NJ-1; for ( i=0; i Cmax_act ) { Cmax_best = Cmax_act; //masolat copy_sch(s_act, s_best, NJ); //masolat } } } //eredmeny copy_sch(s_best, s, NJ); //masolat free( s_act ); free( s_best ); } void copy_sch(int* s1, int* s2, int NJ) { int i; for (i=0; i Cmax_act ) { Cmax_ext = Cmax_act; //masolat copy_sch(s_act, s_ext, NJ); //masolat } } }//loop //a legjobb szomszedot mindig elfogadja uj bazisnak copy_sch(s_ext, s_0, NJ); //masolat if ( Cmax_best > Cmax_ext ) { Cmax_best = Cmax_ext; //masolat copy_sch(s_ext, s_best, NJ); //masolat } }//step //eredmeny copy_sch(s_best, s, NJ); //masolat free( s_0 ); free( s_act ); free( s_ext ); free( s_best ); } void Neighbour( int* s_0, int* s_act, int NJ) { //szomszedsagi operator kepez uj megodast //veletlenszeruen valasztott elemet felcsereljuk az eggyel kisebb sorszamu elemmel int x; x = rand()%NJ; //veletlenszeruen valsztott cella copy_sch(s_0, s_act, NJ); //modositas if ( x==0 ) { //gyuruve alakitjuk a vektort s_act[0] = s_0[NJ-1]; s_act[NJ-1] = s_0[0]; } else { s_act[x] = s_0[x-1]; s_act[x-1] = s_0[x]; } } int Load_STET_to_Cal( long* st, long* et, T_RES* res, int r) { //a munka nem szakithato meg, egyben el kell fernie az idoablakban //operacio long nst; long net; long size; int found; //megtalalt intervallum sorszama int c; //intervallumok futoindexe found = -1; //nincs megfelelo size = *et - *st; //idotartam nst = *st; net = nst + size; c = 0; while ( c < res[r].NC ) { if ( nst < res[r].Cal[c].et ) { nst = max ( nst, res[r].Cal[c].st ); //mikor indulhat net = nst + size; if ( net <= res[r].Cal[c].et ) { found = c; break; } else { c++; if ( c >= res[r].NC ) //nincs tobb intervallum { //az utolso vegere igazitja a kezdest nst = res[r].Cal[c-1].et; net = nst + size; break; } continue; } } c++; } *st = nst; *et = net; return found; } int Load_STET_to_Cal_cut( long* st, long* et, T_RES* res, int r, int cut) { //a munka szakithato, tobb reszletre darabolva is elhelyezheto az idoablakokban //operacio long nst; long net; long size; long fps = -1; //first part start int found; //megtalalt intervallum sorszama int c; //intervallumok futoindexe if ( cut == 0 ) return Load_STET_to_Cal( st, et, res, r); found = -1; //nincs megfelelo size = *et - *st; //idotartam nst = *st; net = nst + size; c = 0; while ( c < res[r].NC ) { if ( nst < res[r].Cal[c].et ) { nst = max ( nst, res[r].Cal[c].st ); //mikor indulhat net = nst + size; if ( fps == -1 ) fps = nst; if ( net <= res[r].Cal[c].et ) { found = c; break; } else { c++; if ( c >= res[r].NC ) //nincs tobb intervallum { //az utolso intervallumbol "kilogatja" a veget ha nem fer el benne net = nst + size; break; } size = size - (res[r].Cal[c-1].et - nst); continue; } } c++; } if (fps == -1 ) *st = nst; else *st = fps; *et = net; return found; } void Print_Res_Cal(T_RES* res, int NR) { int r; int c; for ( r=0; r