/*------------------------------------------------------------------------------- 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 01 Egy eroforrást tartalmazó gyártócella működésének szimulációja. TIA gyakorlat 02 Egy eroforrást tartalmazó gyártócella ütemezése. Az ütemezés célja a befejezési idők összegének minimalizálása, ezáltal az átlagos készletszint minimalizálása. Az SPT (Shortest Processing Time) műveleti idő szerint nemcsökkenő munkasorrend optimális ütemtervet eredményez. TIA gyakorlat 03 Egygépes utemezési feladat modellezése, határidős munkák figyelembe vételével. Minden munkának saját határideje van. Az ütemezés célja a legnagyobb késés minimalizálása. EDD Earliest Due Date (határidő szerint nemcsökkenő munkasorrend) A megoldás optimális ütemtervet eredményez. TIA gyakorlat 04 Továbbfejlesztés: Párhuzamos gépes termelésütemezési feladat: P||Csum ütemezési feladat. Megoldás: MSPT algoritmus. Az ütemezés célja a munkák befejezési időpontjai összegének minimalizálása. MSPT Modified Shortest Processing Time módosított legrövidebb műveleti idejű munka előre: Alkalmazzuk az SPT szabályt a munkák sorbarendezésére (műveleti idők alapján nemcsökkenő sorrendbe), ezután képezzünk a gépek számának megfelelő hosszú csoportokat. Az első csoport munkái az elsők rendre az egyes gépeken, a második csoport munkái a másodikok rendre az egyes gépeken stb. A megoldás optimális ütemtervet eredményez. TIA gyakorlat 05 Továbbfejlesztés: P||Cmax ütemezési fedadat megoldása LPT+LIST ütemezési szabály alkalmazásával. Párhuzamosan működő gépek ütemezési feladata. Az ütemezés célja a legkésőbbi befejezési időpont minimalizálása, ezáltal a teljes rendeléscsoport átfutási idejének minimalizálása. LPT+LIST Alkalmazzuk az LPT szabályt a munkák sorbarendezésére (műveleti idők alapján nemnövekvő sorrendbe), ezután az így kapott sorrendben vesszük a munkákat és mindig a legkorábban felszabaduló gépre ütemezzük a már beütemezettek mögé, ha több gép egyidejűleg szabadul fel, akkor a legkisebb azonosítójút terheljük. Az algoritmus nem garantálja az optimális megoldás elérését, mert a feladat NP-hard, de jó közelítő ütemtervet eredményez. Bővítés: P|di|Lmax ütemezési fedadat megoldása EDD+LIST ütemezési szabály alkalmazásával. Párhuzamos gépes termelésiütemezési feladat. Az ütemezés célja a legnagyobb késés minimalizálása. EDD+LIST Alkalmazzuk az EDD szabályt a munkák sorbarendezésére (határidők alapján nemcsökkenő sorrendbe), ezután az így kapott sorrendben vesszük a munkákat és mindig a legkorábban felszabaduló gépre ütemezzük a már beütemezettek mögé, ha több gép egyidejűleg szabadul fel, akkor a legkisebb azonosítójút terheljük. Az algoritmus nem garantálja az optimális megoldás elérését, mert a feladat NP-hard, de jó közelítő ütemtervet eredményez. ------------------------------------------------------------------------------- */ #include #include typedef struct { int id; long ProcT; long StartT; long EndT; long d; //hatarido long L; //keses } T_JOB; typedef struct { int id; int l; //load, terheles: elvegzendo munkak szama long C; //completion time, befejezesi idopont = terheles vege } T_RES; // void generate_data( T_JOB* job, int NJ ); void create_schedule(int* s, int NJ); void simulation( T_JOB* job, int NJ, int* s, long t0); void print_execution_data( T_JOB* job, int NJ, int* s); void Evaluate( T_JOB* job, int NJ, double* obj_f ); void print_obj_f( double* obj_f ); void SPT_rule( T_JOB* job, int NJ, int* s); void LPT_rule( T_JOB* job, int NJ, int* s); void EDD_rule( T_JOB* job, int NJ, int* s); void MSPT( T_JOB* job, int NJ, T_RES* res, int NR, int** sch); void simulation_P( T_JOB* job, int NJ, T_RES* res, int NR, int** sch, long t0); void print_Res_Gantt_table( T_JOB* job, int NJ, T_RES* res, int NR, int** sch); void EDD_LPT_LIST_alg( T_JOB* job, int NJ, T_RES* res, int NR, int** sch, int mode); int main(int argc, char* argv[]) { int NJ; //number of jobs T_JOB* job; //strukturara mutato pointer int i; int* s; //utemtervre mutato pointer double obj_f[4]; //celfuggvenyek tombje int NR; //number of resources T_RES* res; //pointer int r; //gep futoindexe int* sch; //utemterv minden gepre kulon-kulon printf("\n Demo program egygepes gyartocella szimulaciojara"); printf("\n Munkak szama = "); scanf("%d", &NJ); printf("\n Gepek (eroforrasok) szama = "); scanf("%d", &NR); //mem. foglalas job = (T_JOB*) calloc(NJ, sizeof(T_JOB) ); //dinamikus tomb res = (T_RES*) calloc(NR, sizeof(T_RES) ); //dinamikus tomb s = (int*) calloc(NJ, sizeof(int) ); //dinamikus tomb sch = (int**) calloc(NR, sizeof(int*)); for ( r=0; r job[ s[j] ].ProcT ) index = j; if ( index != i ) { //csere temp = s[index]; s[index] = s[i]; s[i] = temp; } } } void LPT_rule( T_JOB* job, int NJ, int* s) { //Longest Processing Time //Muveleti ido szerint nemnovekvo sorrend int i, j, index, temp; for ( i=0; i job[ s[j] ].d ) //hatarido szerint nemcsokkeno sorrend index = j; if ( index != i ) { //csere temp = s[index]; s[index] = s[i]; s[i] = temp; } } } void MSPT( T_JOB* job, int NJ, T_RES* res, int NR, int** sch) { //1. fazis: elokeszites int* v; int i; int r; v = (int*) calloc(NJ, sizeof(int) ); for ( i=0; i res[ r ].C ) r_sel = r; //a kivalsztott munka melyik pozicioba kerul? sch[r_sel][ res[r_sel].l ] = v[i]; res[r_sel].l++; res[r_sel].C += job[ v[i] ].ProcT; } free(v); }