/* 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 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 ovábbfejlesztés: Határidős munkák utemezése a legnagyobb késés minimalizálása érdekében. Egygépes termelésiütemezési feladat. 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||Csum ütemezési feladat megoldása MSPT algoritmusal. Párhuzamos gépes termelésütemezési feladat. 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 //--------------------------------------------------------------------------- #define N_of_ObjF 4 //celfuggvenyek szama typedef struct { int id; //azonosito long ProcT; //muveleti ido long StartT; //inditasi idopont long EndT; //befejezesi idopont long L; //keses long d; //hatarido }T_JOB; typedef struct { int id; //azonosito int l; //terheles: utemezett munkak szama long C; //eroforras felszabadulasanak idopontja }T_RES; void Simulation( T_JOB* job, int NJ, int* s, long t0); void Evalute( 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 print_execution_details( T_JOB* job, int NJ, int* s); void Simulation_P( T_JOB* job, int NJ, T_RES* res, int NR, int** sch, long t0); void MSPT_rule( T_JOB* job, int NJ, T_RES* res, int NR, int** sch); void EDD_LPT_LIST_rule( T_JOB* job, int NJ, T_RES* res, int NR, int** sch, int mod); void print_Res_Gantt( T_JOB* job, int NJ, T_RES* res, int NR, int** sch); int main(int argc, char* argv[]) { int NJ; //munkak szama, number of jobs T_JOB* job; //munkak dinamikusan letrehozott tombje int* s; //utemterv int i; //munka indexe double obj_f[ N_of_ObjF ]; //N_of_ObjF darab celfuggveny T_RES* res; //eroforrasok: gepek int NR; //eroforrasok szama int r; //eroforras index int** sch; //utemterv printf("\n Utemezesi szabalyok demo"); printf("\n Munkak szama = "); scanf("%d", &NJ); //ellenorzes nincs printf("\n Eroforrasok szama = "); scanf("%d", &NR); //ellenorzes nincs //mem. foglalas job = (T_JOB*) calloc( NJ, sizeof( T_JOB ) ); //strukturatomb res = (T_RES*) calloc( NR, sizeof( T_RES ) ); s = (int*) calloc( NJ, sizeof( int ) ); //int tomb sch = (int**) calloc( NR, sizeof( int* ) ); //pointervektor for ( r=0; r job[ s[j] ].ProcT ) index = j; } if ( index != i ) { //i pozicioban levo elem es az index pozicioban levo elem csereje temp = s[ index ]; s[ index ] = s[ i ]; s[ i ] = temp; } } } void LPT_rule( T_JOB* job, int NJ, int* s) { //rendezes ProcT alapjan nemcsokkeno sorrendbe int i, j, index, temp; for ( i=0; i job[ s[j] ].d ) index = j; } if ( index != i ) { //i pozicioban levo elem es az index pozicioban levo elem csereje temp = s[ index ]; s[ index ] = s[ i ]; s[ i ] = temp; } } } void print_execution_details( T_JOB* job, int NJ, int* s) { //vegrahajtas adatainak megjelenitese int i; printf("\n\n Muveletek vegrahajtasa"); printf("\n \t # \t munka \t indul \t muv. \t bef. \t hatar \t keses"); for ( i=0; i