/* A termelésinformatikai alapjai c. tantrárgy GEIAK150-B Miskolci Egyetem, Alkalmazott Informatikai Intézeti Tanszék Dr. Kulcsár Gyula, egyetemi docens TIA gyakorlat 06 Flow Shop modell Sorba kapcsolódó munkahelyek szimulációja. Egyutas előzésnélküli többoperációs ütemezési feladat. 1. rész: Modellépítés és szimuláció. A Simulation_FS függvény 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 gyakorlat 08 F2|perm|Cmax ütemezési feladat megoldása Johnson-algoritmussal. Az algoritmus optimális megoldást eredményez (két gép esetén). TIA gyakorlat 09 F3|perm|Cmax ütemezési feladat 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ó! TIA gyakorlat 10 Fm|perm|Cmax ütemezési feladat megoldása Palmer-módszer: prioritási indexek számítása és rendezés Dannenbring-módszer: vurtuális kétgépes feladatra transzformálás TIA gyakorlat 11 Fm|perm|Cmax ütemezési feladat megoldása CDS algoritmus Kereső eljárás ----------------------- DTFSZTIR gyakorlat 02 Anyagmozgatási idők és átállási idők modellezése DTFSZTIR gyakorlat 03 Időben korlátozottan rendelkezésre álló erőforrások modellezése A munkák nem szakítható meg. Cél: Az ütetemzés megvalósítása a rendelkezésre állási időintervallumok figyelembe vételével ------------------------------------------------------------------------------- */ #include #include //--------------------------------------------------------------------------- typedef struct { int id; //azonosito long* ProcT; //muveleti idok listajara mutato pointer long* StartT; //inditasi idopont --||-- long* EndT; //befejezesi idopont --||-- }T_JOB; typedef struct { long ST; long ET; }T_TIMEWINDOW; typedef struct { int id; //azonosito long* TransT; //anyagmozgatasi ido long** SetT; //atallasi idok int NCal; //intervallumok sama T_TIMEWINDOW* Cal; //rendelkezesre allasi idointervallumok }T_RES; long max_l(long a, long b) { return a>=b ? a : b; } long min_l(long a, long b) { return a<=b ? a : b; } void Simulation_FS( T_JOB* job, int NJ, T_RES* res, int NR, int* s, long t0); void print_Res_Gantt( T_JOB* job, int NJ, int NR, int* s); void print_Job_Gantt( T_JOB* job, int NJ, int NR, int* s); void Johnson_alg(T_JOB* job, int NJ, int r, int* s); long Evaluate(T_JOB* job, int NJ, int NR, int* s); int F3_Johnson_alg_ext(T_JOB* job, int NJ, int r, int* s); int Fm_Palmer_alg(T_JOB* job, int NJ, int NR, int* s); void Fm_Dannenbring_alg(T_JOB* job, int NJ, int NR, int* s); void copy_sch( int* s1, int* s2, int NJ ); void Fm_CDS_alg(T_JOB* job, int NJ, T_RES* res, int NR, int* s); void Neighbour(int* s_0, int* s_act, int NJ); void Fm_Search_alg(T_JOB* job, int NJ, T_RES* res, int NR, int* s, int STEP, int LOOP); void Print_Res_Cal(T_RES* res, int NR); int Load_STET_to_Cal(long* st, long* et, T_RES* res, int r); int main(int argc, char* argv[]) { int NJ; //munkak szama int i, j; //munka indexe int NR; //munkahelyek (eroforrasok) szama int r, k; //munkahely indexe T_JOB* job; T_RES* res; int* s; //kozos utemterv minden gepre, mert a munkak nem elozheti meg egymast int r_value; int c; //idointervallum index printf(" \n Flow shop modell"); printf("\n Munkak szama="); scanf("%d", &NJ); printf("\n Munkahelyek szama="); scanf("%d", &NR); res = (T_RES*) calloc(NR, sizeof(T_RES) ); //eroforrasok for( r=0; r job[i].ProcT[0] ) min_pi0 = job[i].ProcT[0]; if ( max_pi1 < job[i].ProcT[1] ) max_pi1 = job[i].ProcT[1]; if ( min_pi2 > job[i].ProcT[2] ) min_pi2 = job[i].ProcT[2]; } //mem. felszabaditas for( i=0; i I[ s[index] ] ) index = k; if ( index != i ) { //csere temp = s[index]; s[index] = s[i]; s[i] = temp; } } free( I ); } void Fm_Dannenbring_alg(T_JOB* job, int NJ, int NR, int* s) { int i; //job index int j; //gep es operacio index T_JOB* virt_job; //virtualis F2 rendszer virt_job = (T_JOB*) calloc(NJ, sizeof(T_JOB)); for ( i=0; i C_act ) { C_best = C_act; copy_sch( s_best, s_act, NJ); } } } copy_sch( s, s_best, NJ); free( s_act ); free( s_best ); } void copy_sch( int* s1, int* s2, int NJ ) { int i; for ( i=0; i C_act ) { C_ext = C_act; copy_sch( s_ext, s_act, NJ); } } }//loop //uj bazist ad a legjobb szomszed copy_sch( s_0, s_ext, NJ); if ( C_best > C_ext ) { C_best = C_ext; copy_sch( s_best, s_ext, NJ); } }//step copy_sch( s, s_best, NJ); free( s_act ); free( s_best ); free( s_0 ); free( s_ext ); } void Neighbour(int* s_0, int* s_act, int NJ) { //pelda szomszedsagi operatorra int x; //teljes masolat copy_sch(s_act, s_0, NJ); //modositas x = rand()%NJ; //veletlenszeruen valasztott pozicio if ( x == 0 ) { s_act[x] = s_0[NJ-1]; s_act[NJ-1] = s_0[x]; } else { s_act[x] = s_0[x-1]; s_act[x-1] = s_0[x]; } } void Print_Res_Cal(T_RES* res, int NR) { int r; int c; printf("\n\n Eroforrasok rendelkezesre allasi idointervallumai"); for (r=0; r= res[r].NCal ) { new_st = res[r].Cal[c-1].ET; new_et = new_st + size; break; } continue; } } c++; } *st = new_st; *et = new_et; return found; }