/*------------------------------------------------------------------------------ TIA 3. gyakorlat Egygépes termelésütemezési feladat modellezése és megoldása. 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 4. gyakorlat 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 6. gyakorlat Továbbfejlesztés: Bővítés: P||Sum(Ci) Utemezesi fedadat megoldasa MSPT ütemezési szabály alkalmazásával. 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. Feltétel, hogy a munkák és a gépek számának hányadosa (N/M) egész legyen, ezt teljesíthetjük, ha bizonyos számú 0 műveleti idejű fiktív munkát hozzáadunk a rendeléscsoporthoz. A megoldás optimális ütemtervet eredményez. TIA 7. gyakorlat Továbbfejlesztés: Bővítés: P||Cmax ütemezési fedadat megoldása LPT+LIST ütemezési szabály alkalmazásával. Párhuzamos gépes termelésiütemezési feladat. 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. A megoldás nem optimális 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. A megoldás nem optimális mert a feladat NP-hard, de jó közelítő ütemtervet eredményez. -------------------------------------------------------------------------------*/ #include #include typedef struct{ int id; //azonosito: 0,1, ... long ProcT; //muveleti ido long StartT; //kezdeti ido long EndT; //befejezesi ido long d; //hatarido long L; //keses } T_JOB; //munka typedef struct{ int id; //azonosito int l; //terheles, munkak szama long C; //mikor szabadul fel a terheles alol } T_RES; //eroforras void Simulation( T_JOB* job, int NJ, int* s, long t0); void Evaluate( T_JOB* job, int NJ, double* obj_val); void print_obj_val( double* obj_val); void print_job_Gantt(T_JOB* job, int NJ, int* s); 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_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 mode); void Simulation_P( T_JOB* job, T_RES* res, int NR, int** sch, long t0); void print_job_Gantt_P(T_JOB* job, T_RES* res, int NR, int** sch); int main(int argc, char* argv[]) { T_JOB* job; //munkak strukturavektora int NJ; //munkak szama T_RES* res; //eroforrasok stukturavektora int NR; //eroforrasok szama int i; //munka indexe int r; //eroforrasok indexe int* s; //utemterv, vektor int** sch; //utemterv, matrix double obj_val[4]; //celfuggvenyek printf("\n Parhuzamosan mukodo eroforrasok iranyitasa"); printf("\n Munkak szama="); scanf("%d", &NJ); //betolti az erteket printf("\n Eroforrasok szama="); scanf("%d", &NR); //betolti az erteket //ellenorzes nincs job = (T_JOB*) calloc(NJ, sizeof(T_JOB) ); //vektor res = (T_RES*) calloc(NR, sizeof(T_RES)); //vektor s = (int*) calloc(NJ, sizeof(int) ); //vektor 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 int i, j, index, temp; for( i=0; i job[ s[j] ].d ) //Earliest Due Date index = j; if ( index != i ) { //csere temp = s[ index ]; s[ index ] = s[i]; s[ i ] = temp; } } } void MSPT_rule(T_JOB* job, int NJ, T_RES* res, int NR, int** sch) { //elokeszites int* s; int i; int r; int sel_r, sel_poz; s = (int*) calloc(NJ, sizeof(int)); for (r=0; r