/* 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 DTFSZTIR gyakorlat 04 Időben korlátozott rendelkezésre állási időintervallumok kezelése A munkák megszakítható és később folytathatók ------------------------------------------------------------------------------- */ #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, int cut_mode); 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, int cut_mode); 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, int cut_mode); void Print_Res_Cal(T_RES* res, int NR); int Load_STET_to_Cal(long* st, long* et, T_RES* res, int r); int Load_STET_to_Cal_with_cut(long* st, long* et, T_RES* res, int r); int Load_STET_to_Cal_by_mode(long* st, long* et, T_RES* res, int r, int cut_mode); 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 int cut_mode; //operacio megszakithatosagat definialja //0 nem szakithato meg //1 megszakithato char respons; printf(" \n Flow shop modell"); printf("\n Munkak szama="); scanf("%d", &NJ); printf("\n Munkahelyek szama="); scanf("%d", &NR); printf("\n Az operaciok megszakithatok (i/n) ?"); respons = getch(); if ( respons == 'i' || respons == 'I' ) cut_mode = 1; else cut_mode = 0; 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; } int Load_STET_to_Cal_with_cut(long* st, long* et, T_RES* res, int r) { //az algoritmus megkeresi azt a legkorabbi rendelkezesre allasi //idointervallumot, amelyre megszakitas nelkul el tudja helyezni //a muveletet int c; //intervallum index long new_st; //modositott kezdet long new_et; //modositott befejezes long size; //muvelet vegrehajtasi ideje int found; //megtalalt alkalmas intervallum indexe long fps = -1; //first part start, elso resz kezdete new_st = *st; new_et = *et; size = *et - *st; found = -1; //nincs talalat c = 0; while( c < res[r].NCal ) { if ( new_st < res[r].Cal[c].ET ) //vizsgalhato { //hatarra illesztes ha szukseges new_st = max_l( new_st, res[r].Cal[c].ST); new_et = new_st + size; //vegenek az illesztese if ( fps == -1 ) fps = new_st; //elso darab inditasa if ( new_et <= res[r].Cal[c].ET ) { //belefer, kesz found = c; break; } else { //kilog c++; if ( c >= res[r].NCal ) { //nem kell az utolso intervallum vegere allitani a kilogo resz kezdetet //new_st = res[r].Cal[c-1].ET; new_et = new_st + size; break; } //csak a meg be nem helyezett reszt toljuk tovabb size -= res[r].Cal[c-1].ET - new_st; continue; } } c++; } if ( fps != -1 ) *st = fps; else *st = new_st; *et = new_et; return found; } int Load_STET_to_Cal_by_mode(long* st, long* et, T_RES* res, int r, int cut_mode) { int return_value; if ( cut_mode == 1 ) return_value = Load_STET_to_Cal_with_cut(st, et, res, r); else return_value = Load_STET_to_Cal( st, et, res, r); return return_value; }