Untitled
unknown
plain_text
a year ago
7.6 kB
5
Indexable
#include <iostream> #include <vector> #include <algorithm> #include <fstream> #include <ctime> #include <cstdlib> #include <limits> using namespace std; // Struktura reprezentująca zadanie struct Task { int id; // Identyfikator zadania vector<int> processingTimes; // Czasy wykonania zadania na poszczególnych procesorach Task(int _id, vector<int> _processingTimes) : id(_id), processingTimes(_processingTimes) {} }; // Funkcja do wyświetlania liczby procesorów i zadań void printProblemParameters(int numProcessors, int numTasks) { cout << "Liczba procesorów: " << numProcessors << endl; cout << "Liczba zadań: " << numTasks << endl; } // Funkcja do wczytywania danych z pliku tekstowego vector<Task> readDataFromFile(const string& filename, int& numProcessors, int& numTasks) { ifstream file(filename); if (!file.is_open()) { cerr << "Error: Couldn't open the file." << endl; exit(1); } file >> numProcessors >> numTasks; vector<Task> tasks; for (int taskId = 1; taskId <= numTasks; ++taskId) { vector<int> processingTimes(numProcessors); for (int i = 0; i < numProcessors; ++i) { file >> processingTimes[i]; } tasks.emplace_back(taskId, processingTimes); } file.close(); return tasks; } // Funkcja obliczająca czas zakończenia ostatniego zadania na wszystkich procesorach int calculateCompletionTime(const vector<Task>& schedule, int numProcessors) { vector<int> completionTimes(numProcessors, 0); for (const Task& task : schedule) { for (int i = 0; i < numProcessors; ++i) { completionTimes[i] += task.processingTimes[i]; } } return *max_element(completionTimes.begin(), completionTimes.end()); } // Funkcja oceny (fitness) - oblicza czas zakończenia ostatniego zadania int evaluateFitness(const vector<Task>& schedule, int numProcessors) { return calculateCompletionTime(schedule, numProcessors); } // Funkcja krzyżowania - mieszanie genów dwóch rodziców vector<Task> crossover(const vector<Task>& parent1, const vector<Task>& parent2) { int crossoverPoint = rand() % parent1.size(); vector<Task> child(parent1.begin(), parent1.begin() + crossoverPoint); child.insert(child.end(), parent2.begin() + crossoverPoint, parent2.end()); return child; } // Funkcja mutacji - zamiana miejscami dwóch zadań void mutate(vector<Task>& schedule) { int index1 = rand() % schedule.size(); int index2 = rand() % schedule.size(); swap(schedule[index1], schedule[index2]); } // Funkcja zachłanna do przypisania zadań do procesorów vector<Task> greedyAlgorithm(const vector<Task>& tasks, int numProcessors) { vector<Task> schedule; vector<int> processorTimes(numProcessors, 0); // Przypisz zadania do procesorów w sposób zachłanny, wybierając procesor o najdłuższym czasie pracy for (const Task& task : tasks) { int maxProcessorTime = *max_element(processorTimes.begin(), processorTimes.end()); int processorIndex = find(processorTimes.begin(), processorTimes.end(), maxProcessorTime) - processorTimes.begin(); schedule.push_back(task); processorTimes[processorIndex] += *max_element(task.processingTimes.begin(), task.processingTimes.end()); } return schedule; } // Główna funkcja szeregowania zadań vector<vector<Task>> scheduleTasks(const vector<Task>& tasks, int numGenerations, int populationSize, int numProcessors) { srand(time(nullptr)); vector<vector<Task>> schedules(10); // Wektor przechowujący 10 harmonogramów // Generowanie harmonogramów for (int i = 0; i < 10; ++i) { schedules[i] = greedyAlgorithm(tasks, numProcessors); } // Krzyżowanie i mutacja for (int generation = 0; generation < numGenerations; ++generation) { // Krzyżowanie for (int i = 0; i < 10; i += 2) { vector<Task> child1 = crossover(schedules[i], schedules[i + 1]); vector<Task> child2 = crossover(schedules[i + 1], schedules[i]); schedules.push_back(child1); schedules.push_back(child2); } // Mutacja for (int i = 0; i < 10; ++i) { mutate(schedules[i]); } } // Sortowanie harmonogramów względem oceny (fitness) sort(schedules.begin(), schedules.end(), [&](const vector<Task>& a, const vector<Task>& b) { return evaluateFitness(a, numProcessors) < evaluateFitness(b, numProcessors); }); // Wybór najlepszych 8 harmonogramów vector<vector<Task>> bestSchedules(schedules.begin(), schedules.begin() + 8); // Wybór 2 losowych harmonogramów spośród pozostałych 12 random_shuffle(schedules.begin() + 8, schedules.end()); bestSchedules.insert(bestSchedules.end(), schedules.begin() + 8, schedules.begin() + 10); return bestSchedules; } // Funkcja pomocnicza do wyświetlania harmonogramu void printSchedule(const vector<Task>& schedule, int numProcessors) { cout << "Optimal schedule:" << endl; // Wektor do przechowywania przypisanych zadań dla każdego procesora vector<vector<int>> tasksAssigned(numProcessors); // Przypisz zadania do odpowiednich procesorów for (size_t i = 0; i < schedule.size(); ++i) { int processorIndex = i % numProcessors; tasksAssigned[processorIndex].push_back(schedule[i].id); } // Wyświetlanie przypisanych zadań dla każdego procesora for (size_t i = 0; i < tasksAssigned.size(); ++i) { cout << "Processor " << i + 1 << " - "; for (size_t j = 0; j < tasksAssigned[i].size(); ++j) { cout << "Task " << tasksAssigned[i][j]; if (j != tasksAssigned[i].size() - 1) { cout << ", "; } } cout << endl; } // Wektor do przechowywania czasów zakończenia dla każdego procesora vector<int> processorCompletionTimes(numProcessors, 0); // Obliczanie czasów zakończenia dla każdego procesora for (const Task& task : schedule) { for (int i = 0; i < numProcessors; ++i) { processorCompletionTimes[i] += task.processingTimes[i]; } } // Znajdź najdłuższy czas pracy procesora w bieżącym harmonogramie int longestProcessorWorkTime = *max_element(processorCompletionTimes.begin(), processorCompletionTimes.end()); // Wyświetlanie najdłuższego czasu pracy procesora w bieżącym harmonogramie cout << "Longest processor work time: " << longestProcessorWorkTime << endl; // Wyświetlanie czasów zakończenia dla każdego procesora for (int i = 0; i < numProcessors; ++i) { cout << "Processor " << i + 1 << " completion time: " << processorCompletionTimes[i] << endl; } } int main() { int numProcessors, numTasks; vector<Task> tasks = readDataFromFile("m25.txt", numProcessors, numTasks); printProblemParameters(numProcessors, numTasks); int numGenerations = 10; int populationSize = 30; vector<vector<Task>> bestSchedules = scheduleTasks(tasks, numGenerations, populationSize, numProcessors); // Wyświetlenie najlepszych harmonogramów cout << "Best schedules:" << endl; for (size_t i = 0; i < bestSchedules.size(); ++i) { cout << "Schedule " << i + 1 << ":" << endl; printSchedule(bestSchedules[i], numProcessors); cout << endl; } return 0; }
Editor is loading...
Leave a Comment