Untitled

mail@pastecode.io avatar
unknown
plain_text
19 days ago
6.7 kB
1
Indexable
Never
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <ctime>
#include <cstdlib>
#include <locale>

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, const vector<int>& _processingTimes) : id(_id), processingTimes(_processingTimes) {}
};

// 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) {
            int processingTime;
            file >> processingTime;
            processingTimes[i] = processingTime;
        }
        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] += task.processingTimes[processorIndex];
    }

    return schedule;
}

// Główna funkcja szeregowania zadań
vector<Task> scheduleTasks(const vector<Task>& tasks, int numGenerations, int populationSize, int numProcessors) {
    srand(time(nullptr));
    vector<Task> bestSchedule;
    int bestFitness = INT_MAX;

    for (int generation = 0; generation < numGenerations; ++generation) {
        // Algorytm zachłanny
        vector<Task> greedySchedule = greedyAlgorithm(tasks, numProcessors);

        // Ocena harmonogramu algorytmem zachłannym
        int greedyFitness = evaluateFitness(greedySchedule, numProcessors);

        // Jeśli nowy najlepszy harmonogram, zapamiętaj go
        if (greedyFitness < bestFitness) {
            bestFitness = greedyFitness;
            bestSchedule = greedySchedule;
        }

        // Mutacja
        mutate(bestSchedule);

        // Krzyżowanie
        int parent1Index = rand() % populationSize;
        int parent2Index = rand() % populationSize;
        vector<Task> child = crossover(bestSchedule, bestSchedule); // Krzyżuj najlepsze harmonogramy
        bestSchedule = child;
    }

    return bestSchedule;
}

// Funkcja pomocnicza do wyświetlania harmonogramu
void printSchedule(const vector<Task>& schedule) {
    cout << "Optimal schedule:" << endl;

    // Wektor do przechowywania przypisanych zadań dla każdego procesora
    vector<vector<int>> tasksAssigned(schedule[0].processingTimes.size());

    for (size_t i = 0; i < schedule.size(); ++i) {
        int processorIndex = i % schedule[i].processingTimes.size();
        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(schedule[0].processingTimes.size(), 0);

    // Obliczanie czasów zakończenia dla każdego procesora
    for (size_t i = 0; i < schedule.size(); ++i) {
        int processorIndex = i % schedule[i].processingTimes.size();
        processorCompletionTimes[processorIndex] += schedule[i].processingTimes[processorIndex];
    }

    // Znajdowanie najdłuższego czasu zakończenia procesora
    int maxCompletionTime = *max_element(processorCompletionTimes.begin(), processorCompletionTimes.end());
    cout << "Longest processor completion time: " << maxCompletionTime << " units" << endl;
}

int main() {
    // Ustawienie odpowiedniej lokalizacji dla wyjścia
    setlocale(LC_ALL, "");

    // Liczba procesorów i zadań
    int numProcessors, numTasks;

    // Wczytanie danych z pliku
    vector<Task> tasks = readDataFromFile("m25.txt", numProcessors, numTasks);

    // Parametry algorytmu genetycznego
    int numGenerations = 1000;
    int populationSize = numTasks;

    // Szeregowanie zadań
    vector<Task> optimalSchedule = scheduleTasks(tasks, numGenerations, populationSize, numProcessors);

    // Wyświetlenie optymalnego harmonogramu
    printSchedule(optimalSchedule);

    return 0;
}
Leave a Comment