NEH algorithm with acceleration, C++ implementation.
The program has 3 functions: data reading, data writting and NEH algorithm solving problem function based on read data file. The program displays time. Compilation: Microsoft Visual C++ 2010 Express.
////////////////////////////////////////////////////////////////////////// // program posiada 3 funkcje: // wczytywania danych, zapisywania danych, rozwiazywania problemu // przeplywowego algorytmem NEH z akceleracja // posiada rowniez funkcje pomocnicze oraz odpowiednie struktury danych // program wyswietla czas dzialania algorytmu, zmienna cmax nie wyswietlana // dla kolejnych instancji przechowuje cmax // kompilacja: Microsoft Visual Studio 2010 #include<iostream> #include<fstream> #include<vector> #include<list> #include<stdio.h> #include<algorithm> #include<cstdlib> #include<Windows.h> #define INSTANCE_AMOUT 120 #pragma warning(disable: 4996) using namespace std; struct JobsData { int no; int time; }; struct AllData { int **Tab_Job; int jobs; //liczba zadan int machines; //liczba maszyn list<JobsData> Jobs_List; //lista zadan posiada nr zadania i calkowity czas potrzebny do spedzenia na maszynach vector<int>solution; // tablica uszeregowan czasow zadan }; bool compare(const JobsData& _jd1, const JobsData& _jd2) { return _jd1.time > _jd2.time; } int clear_matrix(int **Tab,int x, int y); void print_matrix(int **Tab, int x, int y); ///////////////////////////////////////////////// // zamien vector'y void swap_V(int &x,int &y); // ///////////////////////////////////////////////// ///////////////////////////////////////////////// // funkcja wczytuje dane z odpowiedniego pliku // bench_fs.txt // PRE: AllData - wskaznik na strukture danych // z elementami niezbednymido wykonania // algorytmu, // pFile - wskaznik na otwarty plil // POST: brak // void GetData(AllData *D, FILE *pFile); // ///////////////////////////////////////////////// ///////////////////////////////////////////////// // funkcja wczytuje dane z odpowiedniego pliku // bench_fs.txt // PRE: AllData - wskaznik na strukture danych // z tablica wynikowa solution // pFileOut - wskaznik na plik do zapisu // POST: brak // void ToFile(AllData *W, FILE *pFileOut); // ///////////////////////////////////////////////// //////////////////////////////////////////////// // funkcja implementujaca algorytm NEH // z akceleracja // PRE: AllData - wskaznik na strukture danych // z elementami niezbednymi do wykonania // algorytmu NEH // POST: brak void DoNEH_acc(AllData *N); // //////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////// // main int main() { __int64 start, stop, freq; AllData *ins = new AllData[INSTANCE_AMOUT]; FILE *pFile; pFile=fopen("bench_fs.txt","r"); for(int instance = 0; instance < INSTANCE_AMOUT; instance++) // for dla kolejnych instancji { GetData(ins,pFile); //wczytaj dane z pliku ins++; } fclose(pFile); ins=ins-INSTANCE_AMOUT; QueryPerformanceCounter((LARGE_INTEGER*)&start); for(int instance = 0; instance < INSTANCE_AMOUT; instance++) { DoNEH_acc(ins); //uszereguj je NEH'em ins++; } QueryPerformanceCounter((LARGE_INTEGER*)&stop); QueryPerformanceFrequency((LARGE_INTEGER*)&freq); cout<<" "<<endl; cout<<"time: " << ((double)(stop-start))/freq << "s" << endl; ins=ins-INSTANCE_AMOUT; FILE *pFileOut; pFileOut=fopen("data_out.txt","w"); for(int instance = 0; instance < INSTANCE_AMOUT; instance++) { ToFile(ins,pFileOut); //zapisz dane do pliku ins++; } fclose(pFileOut); getchar(); return 0; } // koniec main ////////////////////////////////////////////////////////////////////////// ///////////////////////////////////////////////// // GetData void GetData(AllData *D, FILE *pFile) { int E_time;//suma czasow jednego zadania na wszystkich maszynach int time; //czas zadania na maszynie int nvm;//pomijana char iname[6];//nazwa instancji w pliku JobsData Job; //dane zadania if(pFile == NULL){fprintf(stderr,"Blad: Nie podano uchwytu do pliku\n");exit(-1);} fscanf(pFile,"%s",iname); fscanf(pFile,"%d",&D->jobs); fscanf(pFile,"%d",&D->machines); D->Tab_Job = new int * [D->machines]; // i-zadan na j-maszynach for (int j = 0; j < D->machines; j++){ D->Tab_Job[j] = new int[D->jobs]; } for(int i = 0; i < D->jobs; i++) { E_time = 0; for(int j = 0; j < D->machines; j++) { fscanf(pFile,"%d",&nvm); fscanf(pFile,"%d",&time); E_time = E_time + time; D->Tab_Job[j][i] = time; } Job.no = i+1; Job.time = E_time; D->Jobs_List.push_back(Job); } } // koniec funkcji GetData ///////////////////////////////////////////////// ///////////////////////////////////////////////// // ToFile void ToFile(AllData *W, FILE *pFileOut) { for(int i = 0; i < W->jobs; i++) { fprintf(pFileOut,"%d ", W->solution[i]); } fprintf(pFileOut,"\n"); } // koniec ToFile ///////////////////////////////////////////////// ///////////////////////////////////////////////////////////////////// // NEH z akceleracja void DoNEH_acc(AllData *N) { int max, min; int _dict = 0; int new_job; int cmax; int tmp_job; vector<int>max_vect; N->solution.clear(); N->Jobs_List.sort(compare); //mam uszeregowane zadania ze zgledu na czas N->solution.push_back(N->Jobs_List.front().no);// dodaje do tablicy 1 element posortowanej listy zadan N->Jobs_List.pop_front(); // sciagam ten element z listy, na liscie o jedno zadanie mniej int **E = new int*[N->machines+1]; //tworze macierz E for (int i = 0; i < N->machines+1; i++) { E[i] = new int[N->jobs]; } int **Q= new int*[N->machines+1]; //tworze macierz Q for (int i = 0; i < N->machines+1; i++) { Q[i] = new int[N->jobs]; } int **F= new int*[N->machines+1]; //tworze macierz F for (int i = 0; i < N->machines+1; i++) { F[i] = new int[N->jobs]; } int **F_Q= new int*[N->machines+1]; //tworze macierz F for (int i = 0; i < N->machines+1; i++) { F_Q[i] = new int[N->jobs]; } clear_matrix(E,N->machines+1,N->jobs); // clear_matrix(Q,N->machines+1,N->jobs); // wypelniam je zerami clear_matrix(F,N->machines+1,N->jobs); // clear_matrix(F_Q,N->machines+1,N->jobs); /////////////////////////////////////////////////////////////////////// // poczatek petli dla kazdego zadania while(N->Jobs_List.size() != 0) { max_vect.clear(); for(int i=0; i < (int)N->solution.size(); i++) ////////////////////////////////////////////////////////////////////////////////// matrix E { for(int j=0; j < N->machines; j++)// w pierwszej kolumnie { E[j+1][i+1] = max(E[j][i+1],E[j+1][i]) + N->Tab_Job[j][N->solution[i]-1]; } } for(int i = (int)N->solution.size()-1; i >= 0; i--) ////////////////////////////////////////////////////////////////////////////////// matrix Q { for(int j = N->machines-1; j >= 0; j--)// w pierwszej kolumnie { Q[j][i] = max(Q[j+1][i],Q[j][i+1]) + N->Tab_Job[j][N->solution[i]-1]; } } new_job = N->Jobs_List.front().no; // sciagam nowe zadanie N->Jobs_List.pop_front(); // for(int i=0; i < (int)N->solution.size()+1; i++) ////////////////////////////////////////////////////////////////////////////////// matrix F { for(int j=0; j < N->machines; j++)// w pierwszej kolumnie { F[j+1][i] = max(E[j+1][i],F[j][i]) + N->Tab_Job[j][new_job-1]; } } for(int i=0; i < (int)N->solution.size()+1; i++) ////////////////////////////////////////////////////////////////////////////////// matrix F_Q { for(int j=0; j < N->machines; j++)// w pierwszej kolumnie { F_Q[j][i] = Q[j][i]+F[j+1][i]; } } for(int i=0; i < (int)N->solution.size()+1; i++) // znajduje maxa poszczegolnych kolumn w macierzy F+Q { max = 0; for(int j=0; j < N->machines; j++) { if(F_Q[j][i] > max) {max = F_Q[j][i];} } max_vect.push_back(max); } min=999999; for(int i=0; i < (int)max_vect.size(); i++) { if(max_vect[i]<min){ min = max_vect[i]; _dict = i;} // _slownik_it zeby znac indeks na ktory mam wstawic to zadanie } cmax = min; N->solution.push_back(0); for(int i = _dict; i < (int)N->solution.size(); i++) { swap_V(N->solution[i],tmp_job); } N->solution[_dict] = new_job; } //koniec while } // koniec funkcji // ///////////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////////////// // funkcje dodatkowe void swap_V(int &x,int &y) //swap4vector { int temp; temp=x; x=y; y=temp; } int clear_matrix(int **Tab,int x, int y) { for(int i = 0; i < x; i++) for(int j = 0; j < y; j++) Tab[i][j]=0; return 0; } void print_matrix(int **Tab, int x, int y) { for(int i = 0; i < x; i++){ for(int j = 0; j < y; j++) {cout<<Tab[i][j];} cout<<" "<<endl;} } // /////////////////////////////////////////////////////////////////////
No comments:
Post a Comment