Untitled

 avatar
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