/*------------------------------------------------------------------------------ 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. -------------------------------------------------------------------------------*/ #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{ int id; //azonosito long** SetT; //atallasi ido, set-up long* TransT; //anyagmozgatasi ido, transportation time //az aktualis gepre erkezes egy masik geprol } 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); 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); void Search_alg(T_JOB* job, int NJ, T_RES* res, int NR, int* s, int STEP, int LOOP); void Neighbour( int* s_0, int* s_act, int NJ); 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 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]; } }