Cos tam dziala - czyli genetyk w fazie produkcji

#include <stdio.h>
#include <conio.h>
#include <math.h>
#include <fstream>
#include <cstdlib>
#include <time.h>
#include <string.h>
#include <cstdlib>
#include <iostream>
#include <windows.h>


using namespace std;


//------------TASK-STRUCTURE-----------
struct Task{
    int start_time;
    int time_length;
    int real_number;
    bool isPause;
    Task *next;

    Task();
    void add(int start_time, int time_length, int real_number, bool isPause, Task * &head);
};

Task::Task() {}

void Task::add(int start_time, int time_length, int real_number, bool isPause, Task * &head) {
    Task *new_task = new Task;
    Task *temp;

    new_task->start_time = start_time;
    new_task->time_length = time_length;
    new_task->real_number = real_number;
    new_task->isPause = isPause;
    new_task->next = NULL;

    temp = head;
    if(temp) {
        while(temp->next) temp = temp->next;
        temp->next = new_task;
    } else head = new_task;
}


//------------SOLUTION-STRUCTURE---------------
struct Solution {
    Task *machine_1_sequence;
    Task *machine_2_sequence;
    int fitness_value;
    Solution *next;

    Solution();
    void add(Solution * &head);
};

Solution::Solution() {}

void Solution::add(Solution * &head) {
    Solution *new_solution = new Solution;
    Solution *temp;

    new_solution->machine_1_sequence = NULL;
    new_solution->machine_2_sequence = NULL;
    new_solution->fitness_value = 0;


    new_solution->next = NULL;

    temp = head;
    if(temp) {
        while(temp->next) temp = temp->next;
        temp->next = new_solution;
    } else head = new_solution;
}


//-----------POPULATION-STRUCTURE--------------
struct Population {
    Solution *solution;

    Population();
    void add_solution(Solution * &old_solution);
    int population_size();
};

Population::Population() {
    solution = NULL;
}

void Population::add_solution(Solution * &old_solution) {
    Task *machine1_task = old_solution->machine_1_sequence;
    Task *machine2_task = old_solution->machine_2_sequence;

    solution->add(solution);
    Solution *new_solution = solution;

    while(new_solution->next) new_solution = new_solution->next;

    while(machine1_task) {
        new_solution->machine_1_sequence->add(machine1_task->start_time, machine1_task->time_length, machine1_task->real_number, false, new_solution->machine_1_sequence);
        machine1_task = machine1_task->next;
    }

    while(machine2_task) {
        new_solution->machine_2_sequence->add(machine2_task->start_time, machine2_task->time_length, machine2_task->real_number, false, new_solution->machine_2_sequence);
        machine2_task = machine2_task->next;
    }
    new_solution->fitness_value = old_solution->fitness_value;
}

int Population::population_size() {
    Solution *temp_solution = solution;
    int population_size = 0;

    while(temp_solution) {
        population_size++;
        temp_solution = temp_solution->next;
    }

    return population_size;
}


//---------GLOBAL-VARIABLES----------------
Task *machine1_operations;
Task *machine2_operations;

Task *machine1_pauses;
Task *machine2_pauses;



void swapTasks(Task *sequence, Task *task1, Task *task2) {

    Task *temp_sequence = sequence;
    Task *task1_prev, *task2_prev;
    Task *temp_task;

//--ZAMIANA-GDY-ZADANIE-PIERWSZE-JEST-NA-PIERWSZYM-MIEJSCU-USZEREGOWANIA
    if(task1->real_number == temp_sequence->real_number) {

         if(task1->next == task2) {

            task1->next = task2->next;
            task2->next = task1;
            sequence = task2;

            int tempStartTime = task1->start_time;
            task1->start_time = task2->start_time;
            task2->start_time = tempStartTime;
            return;
        }

        while(temp_sequence) {
            if(temp_sequence->next->real_number == task2->real_number) {
                task2_prev = temp_sequence;
                    break;
            }
            temp_sequence = temp_sequence->next;
        }

        temp_task = task1->next;
        task1->next = task2->next;
        task2->next = temp_task;

        task2_prev = task1;
        sequence = task2;

        int tempStartTime = task1->start_time;
        task1->start_time = task2->start_time;
        task2->start_time = tempStartTime;
        return;
    }

//--ZAMIANA-GDY-ZADANIE-DRUGIE-JEST-NA-PIERWSZYM-MIEJSCU-USZEREGOWANIA
    if(task2->real_number == temp_sequence->real_number) {

        if(task2->next == task1) {

            task2->next = task1->next;
            task1->next = task2;
            sequence = task1;

            int tempStartTime = task1->start_time;
            task1->start_time = task2->start_time;
            task2->start_time = tempStartTime;
            return;
        }

        while(temp_sequence) {
                if(temp_sequence->next->real_number == task1->real_number) {
                    task1_prev = temp_sequence;
                    break;
                }
            temp_sequence = temp_sequence->next;
        }

        temp_task = task1->next;
        task1->next = task2->next;
        task2->next = temp_task;

        task1_prev = task2;
        sequence = task1;

        int tempStartTime = task1->start_time;
        task1->start_time = task2->start_time;
        task2->start_time = tempStartTime;
        return;
    }

//--ZAMIANA-GDY-ZADANIA-NASTEPUJA-JEDEN-PO-DRUGIM
    if(task1->next == task2) {
        while(temp_sequence) {
            if (temp_sequence->next->real_number == task1->real_number) {
                task1_prev = temp_sequence;
            }
            temp_sequence = temp_sequence->next;
        }
        task1_prev = task2;

        temp_task = task2->next;
        task2->next = task1;
        task1->next = temp_task;

        int tempStartTime = task1->start_time;
        task1->start_time = task2->start_time;
        task2->start_time = tempStartTime;
        return;
    }

    if(task2->next == task1) {
        while(temp_sequence) {
            if (temp_sequence->next->real_number == task2->real_number) {
                task2_prev = temp_sequence;
            }
            temp_sequence = temp_sequence->next;
        }
        task2_prev = task1;

        temp_task = task1->next;
        task1->next = task2;
        task2->next = temp_task;

        int tempStartTime = task1->start_time;
        task1->start_time = task2->start_time;
        task2->start_time = tempStartTime;
        return;
    }

//--ZAMIANA-W-KAZDYM-INNYM-PRZYPADKU
    while(temp_sequence) {

        if(!temp_sequence->next) break;
        if(temp_sequence->next->real_number == task1->real_number) task1_prev = temp_sequence;
        if(temp_sequence->next->real_number == task2->real_number) task2_prev = temp_sequence;

        temp_sequence = temp_sequence->next;
    }

    task1_prev = task2;
    task2_prev = task1;

    temp_task = task1->next;
    task1->next = task2->next;
    task2->next = temp_task;

    int tempStartTime = task1->start_time;
    task1->start_time = task2->start_time;
    task2->start_time = tempStartTime;
}

Task *takeFromSequence(Task *sequence, Task *task2){

    Task *temp;
    Task *takenTask;
    temp = sequence;

    if(task2 == sequence){
        if(sequence){
            takenTask = sequence;
            sequence = sequence->next;
        }

    } else {

        while(temp->next != task2){
            temp = temp->next;
        }

        takenTask = temp->next;
        temp->next = task2->next;

    }
    return takenTask;
}


bool isCollideWithPause(Task *task, Task *pauses){

    Task *pause = pauses;

    while(pause){
        if( ( (task->start_time > pause->start_time) && (task->start_time < pause->start_time + pause->time_length) ) ||
        ( (task->start_time + task->time_length > pause->start_time) && (task->start_time + task->time_length < pause->start_time + pause->time_length) ) ){
            return true;
        }
        pause = pause->next;
    }

    return false;
}


int returnPossibleStartTime(Solution *solution, Task *task){

    Task *next_task = solution->machine_1_sequence;

    while (next_task->real_number != task->real_number) {
        next_task = next_task->next;
        if(!next_task) return 0;

    }
    return next_task->start_time + next_task->time_length;

}


void insertToSequence(Solution *solution, Task *task, int machine_number) {

    if(machine_number == 1) {

        int task_start_time = 0;
        int task_finish_time = task_start_time + task->time_length;
        bool checkEverythingAgain = true;

        while(checkEverythingAgain) {
            checkEverythingAgain = false;

            bool checkTasksAgain = true;
            while(checkTasksAgain) {
                Task *solution_task = solution->machine_1_sequence;
                while(solution_task) {
                    for(int i = task_start_time ; i <= task_finish_time ; i++) {
                        if(i >= solution_task->start_time && i <= solution_task->start_time + solution_task->time_length) {
                            task_start_time = solution_task->start_time + solution_task->time_length + 1;
                            task_finish_time = task_start_time + task->time_length;
                            checkTasksAgain = true;
                            checkEverythingAgain = true;
                            break;
                        }
                    }
                    checkTasksAgain = false;
                    solution_task = solution_task->next;
                }
            }

            bool checkPausesAgain = true;
            while(checkPausesAgain) {
                Task *pauseM1 = machine1_pauses;
                while(pauseM1) {
                    for(int i = task_start_time ; i <= task_finish_time ; i++) {
                        if(i >= pauseM1->start_time && i <= pauseM1->start_time + pauseM1->time_length) {
                            task_start_time = pauseM1->start_time + pauseM1->time_length + 1;
                            task_finish_time = task_start_time + task->time_length;
                            checkPausesAgain = true;
                            checkEverythingAgain = true;
                            break;
                        }
                    }
                    checkPausesAgain = false;
                    pauseM1 = pauseM1->next;
                }
            }
        }

        Task *solution_task = solution->machine_1_sequence;
        Task *new_task = new Task;
        new_task->start_time = task_start_time;
        new_task->real_number = task->real_number;
        new_task->isPause = false;
        new_task->time_length = task->time_length;
        new_task->next=NULL;

        if(task_start_time < solution_task->start_time) {

            new_task->next = solution_task;
            solution_task = new_task;

        } else {
            while(solution_task) {
                if(!solution_task->next) {
                    solution_task->next = new_task;
                    break;
                }

                if(solution_task->next->start_time > task_start_time) {

                    Task *temp_task = solution_task->next;
                    solution_task->next = new_task;
                    new_task->next = temp_task;
                    break;
                }
                solution_task = solution_task->next;
            }
        }
      //  cout << "left";
      //  cout << task->real_number << " : " << task_start_time << endl;
    } else if(machine_number == 2) {

        int task_start_time = returnPossibleStartTime(solution, task);
        int task_finish_time = task_start_time + task->time_length;
        bool checkEverythingAgain = true;

        while(checkEverythingAgain) {
            checkEverythingAgain = false;

            bool checkTasksAgain = true;
            while(checkTasksAgain) {
                Task *solution_task = solution->machine_2_sequence;
                while(solution_task) {
                    for(int i = task_start_time ; i <= task_finish_time ; i++) {
                        if(i >= solution_task->start_time && i <= solution_task->start_time + solution_task->time_length) {
                            task_start_time = solution_task->start_time + solution_task->time_length + 1;
                            task_finish_time = task_start_time + task->time_length;
                            checkTasksAgain = true;
                            checkEverythingAgain = true;
                            break;
                        }
                    }
                    checkTasksAgain = false;
                    solution_task = solution_task->next;
                }
            }

            bool checkPausesAgain = true;
            while(checkPausesAgain) {
                Task *pauseM2 = machine2_pauses;
                while(pauseM2) {
                    for(int i = task_start_time ; i <= task_finish_time ; i++) {
                        if(i >= pauseM2->start_time && i <= pauseM2->start_time + pauseM2->time_length) {
                            task_start_time = pauseM2->start_time + pauseM2->time_length + 1;
                            task_finish_time = task_start_time + task->time_length;
                            checkPausesAgain = true;
                            checkEverythingAgain = true;
                            break;
                        }
                    }
                    checkPausesAgain = false;
                    pauseM2 = pauseM2->next;
                }
            }
        }

        Task *solution_task = solution->machine_2_sequence;
        Task *new_task = new Task;
        new_task->start_time = task_start_time;
        new_task->real_number = task->real_number;
        new_task->isPause = false;
        new_task->time_length = task->time_length;
        new_task->next=NULL;


        if(task_start_time < solution_task->start_time) {

           new_task->next = solution_task;
            solution_task = new_task;

        } else {
            while(solution_task) {
                if(!solution_task->next) {
                    solution_task->next = new_task;
                    break;
                }

                if(solution_task->next->start_time > task_start_time) {

                    Task *temp_task = solution_task->next;
                    solution_task->next = new_task;
                    new_task->next = temp_task;
                    break;
                }
                solution_task = solution_task->next;
            }
        }
        //cout << task->real_number << " : " << task_start_time << endl;
        //cout << "left";
    }

}

void repair(Solution *solution, int numberOfTasks){

    Task *temp;
    Task *pom;
    Task *temp2;
    bool tasks[numberOfTasks];

//--USUWANIE-POWIELEN-NA-MASZYNIE-1
    for(int i = 0 ; i < numberOfTasks ; i++) tasks[i] = false;

    temp = solution->machine_1_sequence;
    while(temp) {
        if(tasks[temp->real_number]){
            pom = temp->next;
            delete takeFromSequence(solution->machine_1_sequence, temp);
            temp = pom;
        } else {
            tasks[temp->real_number] = true;
            temp = temp->next;
        }
    }

//--DOPISYWANIE-BRAKUJACYCH-ZADAN-DO-MASZYNY-1
    for(int i = 0 ; i < numberOfTasks ; i++){

        if(!tasks[i]){
            temp = machine1_operations;

            while(temp->real_number != i){
                temp = temp->next;
            }

            insertToSequence(solution, temp, 1);
        }
    }


//--USUWANIE-POWIELEN-NA-MASZYNIE-2
    for(int i = 0 ; i < numberOfTasks ; i++) tasks[i] = false;

    temp = solution->machine_2_sequence;
    while(temp) {
        if(tasks[temp->real_number]){
            pom = temp->next;
            delete takeFromSequence(solution->machine_2_sequence, temp);
            temp = pom;
        } else {
            tasks[temp->real_number] = true;
            temp = temp->next;
        }
    }

//--DOPISYWANIE-BRAKUJACYCH-ZADAN-NA-MASZYNIE-2
    for(int i = 0 ; i < numberOfTasks ; i++){

        if(!tasks[i]) {
            temp = machine2_operations;

            while(temp->real_number != i){
                temp = temp->next;
            }

            insertToSequence(solution, temp, 2);
        }
    }

//--PRZESTAWIANIE-NIEPASUJACYCH-ZADAN-NA-MASZYNIE-1
    temp = solution->machine_1_sequence;

    while(temp->next){

        if( (temp->start_time + temp->time_length > temp->next->start_time) || isCollideWithPause(temp, machine1_pauses) ){
            temp2 = temp->next;
            pom = takeFromSequence(solution->machine_1_sequence, temp);
            Task *global_task=machine1_operations;

            while(global_task->real_number != pom->real_number) global_task = global_task->next;

            insertToSequence(solution, global_task, 1);
            delete pom;
            temp = temp2;

        } else temp=temp->next;

    }

//--PRZESTAWIANIE-NIEPASUJACYCH-ZADAN-NA-MASZYNIE-2
    temp = solution->machine_2_sequence;
    while(temp->next){
        if( (temp->start_time + temp->time_length > temp->next->start_time) || isCollideWithPause(temp, machine2_pauses) || returnPossibleStartTime(solution, temp) < temp->start_time){
            temp2 = temp->next;
            pom = takeFromSequence(solution->machine_2_sequence, temp);
            Task *global_task=machine2_operations;
            while(global_task->real_number != pom->real_number) global_task = global_task->next;
            insertToSequence(solution, global_task, 2);
            delete pom;
            temp = temp2;
        } else temp = temp->next;
    }

}




void mutate(Solution *old_solution, int numberOfTasks, Population *population) {

    population->add_solution(old_solution);
    Solution *new_solution = population->solution;
    while(new_solution->next) new_solution = new_solution->next;


    Task *z1_op1 = new_solution->machine_1_sequence;                //---WSKAZNIK-NA-ZADANIE-1-NA-MASZYNIE-1
    Task *z2_op1 = new_solution->machine_1_sequence;                //---WSKAZNIK-NA-ZADANIE-2-NA-MASZYNIE-1
    Task *z1_op2 = new_solution->machine_2_sequence;                //---WSKAZNIK-NA-ZADANIE-1-NA-MASZYNIE-2
    Task *z2_op2 = new_solution->machine_2_sequence;                //---WSKAZNIK-NA-ZADANIE-2-NA-MASZYNIE-2

    int z1_rand = rand() % (numberOfTasks - 1);                           //---LOSOWANIE-NUMERU-ZADANIA-1-NA-MASZYNIE-1
    for(int i = 0 ; i < z1_rand ; i++) z1_op1 = z1_op1->next;             //---PRZESUNIECIE-WSKAZNIKA-DO-TEGO-ZADANIA


    int z2_rand = rand() % (numberOfTasks - 1);                               //---LOSOWANIE-NUMERU-ZADANIA-2-NA-MASZYNIE-1
    while (z1_rand == z2_rand) z2_rand = rand() % (numberOfTasks - 1);         //---SPRAWDZANIE-CZY-NIE-WYLOSOWANO-TEGO-SAMEGO-ZADANIA

    for(int i = 0 ; i < z2_rand ; i++) z2_op1 = z2_op1->next;             //---PRZESUNIECIE-WSKAZNIKA-DO-TEGO-ZADANIA

//--WYSZUKANIE-TYCH-ZADAN-NA-MASZYNIE-DRUGIEJ-I-USTAWIENIE-WSKAZNIKA
    while(z1_op2->real_number != z1_op1->real_number) z1_op2 = z1_op2->next;
    while(z2_op2->real_number != z2_op1->real_number) z2_op2 = z2_op2->next;

    swapTasks(new_solution->machine_1_sequence, z1_op1, z2_op1);            //---ZAMIANA-ZADAN-NA-MASZYNIE-1
    swapTasks(new_solution->machine_2_sequence, z1_op2, z2_op2);            //---ZAMIANA-ZADAN-NA-MASZYNIE-2

          Task * temp1 = new_solution->machine_1_sequence;
            Task * temp2 = new_solution->machine_2_sequence;
            int a = 0, b = 0;

            while(temp1) {
                a++;
                temp1 = temp1->next;
            }

            while(temp2) {
                b++;
                temp2 = temp2->next;
            }
            cout << "M1: " << a << " M2: " << b << endl;
            getch();

    repair(new_solution, numberOfTasks);               //---NAPRAWIENIE-EWENTUALNIE-POWSTALYCH-BLEDOW-USZEREGOWANIA
}





void crossover(Solution *old_solution1, Population *old_population, int numberOfTasks, Population *population) {

//--SZUKANIE-DRUGIEGO-,-INNEGO-ROZWIAZANIA-ZE-STAREJ-POPULACJI
    Solution *old_solution2;
    do {
        old_solution2 = old_population->solution;
        int rand_second_solution = rand() % (old_population->population_size() - 1);
        for(int i = 0 ; i < rand_second_solution ; i++) old_solution2 = old_solution2->next;
    } while (old_solution1->fitness_value == old_solution2->fitness_value);

//--DODANIE-PIERWSZEGO-STAREGO-ROZWIAZANIA-DO-NOWEJ-POPULLACJI-I-ZNALEZIENIE-GO
    population->add_solution(old_solution1);
    Solution *new_solution1 = population->solution;
    while(new_solution1->next) new_solution1 = new_solution1->next;

//--DODANIE-DRUGIEGO-STAREGO-ROZWIAZANIA-DO-NOWEJ-POPULACJI-I-ZNALEZIENIE-GO
    population->add_solution(old_solution2);
    Solution *new_solution2 = population->solution;
    while(new_solution2->next) new_solution2 = new_solution2->next;

/*KRZYZOWANIE-NA-MASZYNIE-1*/
    Task *start_task1 = new_solution1->machine_1_sequence;
    Task *over_task1 = new_solution1->machine_1_sequence;
    Task *start_task2 = new_solution2->machine_1_sequence;
    Task *over_task2 = new_solution2->machine_1_sequence;
    Task *before_start_task1 = new_solution1->machine_1_sequence;
    Task *before_start_task2 = new_solution2->machine_1_sequence;
    Task *after_over_task1;
    Task *after_over_task2;

    int task_start_time;
    int rand_start_range;
    int rand_over_range;

    do {
        rand_start_range = rand() % (numberOfTasks - 2) + 1;
        rand_over_range = rand() % (numberOfTasks - 2) + 1;
    } while(rand_start_range != rand_over_range || rand_start_range == rand_over_range + 1 || rand_start_range == rand_over_range - 1);

    if(rand_start_range > rand_over_range) {
        int temp = rand_start_range;
        rand_start_range = rand_over_range;
        rand_over_range = temp;
    }

//--PRZESUNIECIE-WSKAZNIKA-NA-POCZATEK-ZAKRESU
    for(int i = 0 ; i < rand_start_range ; i++){
        start_task1 = start_task1->next;
        start_task2 = start_task2->next;
    }

//--PRZESUNIECIE-WSKAZNIKA-NA-KONIEC-ZAKRESU
    for(int i = 0 ; i < rand_over_range ; i++){
        over_task1 = over_task1->next;
        over_task2 = over_task2->next;
    }

    while(before_start_task1->next != start_task1) before_start_task1 = before_start_task1->next;
    while(before_start_task2->next != start_task2) before_start_task2 = before_start_task2->next;

    after_over_task1 = over_task1->next;
    after_over_task2 = over_task2->next;

    task_start_time = start_task1->start_time;
    start_task1->start_time = start_task2->start_time;
    start_task2->start_time = task_start_time;

    before_start_task1->next = start_task2;
    before_start_task2->next = start_task1;
    over_task1->next = after_over_task2;
    over_task2->next = after_over_task1;

//--AKTUALIZACJA-CZASOW-ROZPOCZECIA
    before_start_task1 = start_task1;
    while(before_start_task1 != over_task1) {
       // cout << before_start_task1->next << endl;
        before_start_task1->next->start_time = before_start_task1->start_time + before_start_task1->time_length;
        before_start_task1 = before_start_task1->next;
    }

    before_start_task2 = start_task2;
    while(before_start_task2 != over_task2) {
        before_start_task2->next->start_time = before_start_task2->start_time + before_start_task2->time_length;
        before_start_task2 = before_start_task2->next;
    }

/*KRZYZOWANIE-NA-MASZYNIE-2*/
    start_task1 = new_solution1->machine_2_sequence;
    start_task2 = new_solution2->machine_2_sequence;
    before_start_task1 = new_solution1->machine_2_sequence;
    before_start_task2 = new_solution2->machine_2_sequence;
    over_task1=new_solution1->machine_2_sequence;
    over_task2=new_solution2->machine_2_sequence;
//--PRZESUNIECIE-WSKAZNIKA-NA-POCZATEK-ZAKRESU
    for(int i = 0 ; i < rand_start_range ; i++){
        start_task1 = start_task1->next;
        start_task2 = start_task2->next;
    }

//--PRZESUNIECIE-WSKAZNIKA-NA-KONIEC-ZAKRESU
    for(int i = 0 ; i < rand_over_range ; i++){
        over_task1 = over_task1->next;
        over_task2 = over_task2->next;
    }

    while(before_start_task1->next != start_task1) before_start_task1 = before_start_task1->next;
    while(before_start_task2->next != start_task2) before_start_task2=before_start_task2->next;

    after_over_task1 = over_task1->next;
    after_over_task2 = over_task2->next;

    task_start_time = start_task1->start_time;
    start_task1->start_time = start_task2->start_time;
    start_task2->start_time = task_start_time;

    over_task1->next = after_over_task2;
    over_task2->next = after_over_task1;
    before_start_task1->next = start_task2;
    before_start_task2->next = start_task1;

//--AKTUALIZACJA-CZASOW-ROZPOCZECIA
    before_start_task1 = start_task1;
    while(before_start_task1 != over_task1){
        before_start_task1->next->start_time = before_start_task1->start_time + before_start_task1->time_length;
        before_start_task1 = before_start_task1->next;
    }

    before_start_task2=start_task2;
    while(before_start_task2 != over_task2){
        before_start_task2->next->start_time = before_start_task2->start_time + before_start_task2->time_length;
        before_start_task2 = before_start_task2->next;
    }

            /*    Task * temp1 = solution1->machine_1_sequence;
            Task * temp2 = solution1->machine_2_sequence;
            int a = 0, b = 0;

            while(temp1) {
                a++;
                temp1 = temp1->next;
            }

            while(temp2) {
                b++;
                temp2 = temp2->next;
            }
            cout << "M1: " << a << " M2: " << b << endl;
            getch();

            temp1 = solution2->machine_1_sequence;
            temp2 = solution2->machine_2_sequence;
            a = 0, b = 0;

            while(temp1) {
                a++;
                temp1 = temp1->next;
            }

            while(temp2) {
                b++;
                temp2 = temp2->next;
            }
            cout << "M1: " << a << " M2: " << b << endl;
            getch();*/

    repair(new_solution1, numberOfTasks);
    repair(new_solution2, numberOfTasks);

}


//---------------------SELECTION-OPERATOR---------------------------
void calculate_fitness(Population *population) {
    Solution *solution = population->solution;                                      //---WSKAZNIK-NA-PIERWSZE-ROZWIAZANIE-W-POPULACJI
    int maxFitnessValue = 0;                                                        //---ZMIENNA-PRZECHOWUJACA-WARTOSC-NAJWIEKSZEJ-FUNKCJI

//--DLA-KAZDEGO-ROZWIAZANIA-WYLICZANA-JEST-WARTOSC-FUNKCJI-CELU-(IM-WIEKSZA-WARTOSC-TYM-LEPSZE-USZEREGOWANIE)
    while(solution) {
        Task *machine1_task = solution->machine_1_sequence;                         //---WSKAZNIK-NA-ZADANIE-DLA-DANEGO-ROZWIAZANIA-DLA-MASZYNY-1
        Task *machine2_task = solution->machine_2_sequence;                         //---WSKAZNIK-NA-ZADANIE-DLA-DANEGO-ROZWIAZANIA-DLA-MASZYNY-2
        int fitnessValue = 0;                               //---WARTOSC-FUNKCJI-CELU

//------SUMOWANIE-CZASOW-ZAKONCZENIA-OPERACJI-DLA-MASZYNY-1
        while(machine1_task) {
            fitnessValue += machine1_task->start_time + machine1_task->time_length;
            machine1_task = machine1_task->next;
        }

//------SUMOWANIE-CZASOW-ZAKONCZENIA-OPERACJI-DLA-MASZYNY-2
        while(machine2_task) {
            fitnessValue += machine2_task->start_time + machine2_task->time_length;
            machine2_task = machine2_task->next;
        }

//------SPRAWDZANIE-CZY-AKTUALNA-WARTOSC-FUNKCJI-CELU-JEST-NAJWIEKSZA
        if(fitnessValue > maxFitnessValue) {
            maxFitnessValue = fitnessValue + 1;
        }

        solution->fitness_value = fitnessValue;     //---ZAPISANIE-WARTOSCI-FUNKCJI-CELU-(TU-JESZCZE-WIEKSZA-WARTOSC-JEST-GORSZYM-USZEREGOWANIEM)
        solution = solution->next;
    }
    solution = population->solution;

//--ZAMIANA-WARTOSCI-FUNKCJI-CELU-(IM-WIEKSZA-TERAZ-JEST-LEPSZYM-USZEREGOWANIEM)
    while(solution) {
        solution->fitness_value = maxFitnessValue - solution->fitness_value;
        solution = solution->next;
    }
}

void roulette_selection(Population *population, int new_population_size) {
    int sumOfFitnessValues = 0;
    Solution *solution = population->solution;

    while(solution) {
        sumOfFitnessValues += solution->fitness_value;
        solution = solution->next;
    }

    for(int i = 0 ; i < new_population_size ; i++) {
        int rouletteMarble = rand();
    }

}

void tournament_selection(Population *population, Population *new_population, int new_population_size) {
    Solution *solution1;
    Solution *solution2;
    int population_size = population->population_size();
    int solution1_number;
    int solution2_number;

    int popArray[population_size];
    for(int i = 0 ; i < population_size ; i++) {
        popArray[i] = 0;
    }

    for(int i = 0 ; i < new_population_size ; i++) {

        solution1 = population->solution;
        solution2 = population->solution;

        while(true) {
            solution1_number = rand() % (population_size - 1);
            if(popArray[solution1_number] == 0) {
                popArray[solution1_number] = 1;
                break;
            }
        }

        while(true) {
            solution2_number = rand() % (population_size - 1);
            if(popArray[solution2_number] == 0) {
                popArray[solution2_number] = 1;
                break;
            }
        }

        for(int i = 0 ; i < solution1_number ; i++) solution1 = solution1->next;
        for(int i = 0 ; i < solution2_number ; i++) solution2 = solution2->next;

        if(solution1->fitness_value > solution2->fitness_value) {
            popArray[solution2_number] = 0;
            new_population->add_solution(solution1);
        } else {
            popArray[solution1_number] = 0;
            new_population->add_solution(solution2);
        }
    }
}

void selection(Population *population, Population* new_population, int new_population_size) {

    calculate_fitness(population);
    //roulette_selection(population, new_population_size);
    tournament_selection(population, new_population, new_population_size);
}

//-----------------------------------------------------------
int generate_population(int numberOfTasks, int sizeOfPopulation, Population * &population) {
    for(int i = 0 ; i < sizeOfPopulation ; i++) {

        population->solution->add(population->solution);            //---DODANIE-NOWEGO-ROZWIAZANIA-DO-LISTY-ROZWIAZAŃ
        Solution *solution = population->solution;
        for(int j = 0 ; j < i; j++) solution = solution->next;      //---PRZESUNIECIE-WSKAZNNIKA-DO-AKTUALNIE-GENEROWANEGO-ROZWIAZANIA

        int taskOrder[numberOfTasks], usedTasks[numberOfTasks];
        for(int j = 0 ; j < numberOfTasks ; j++) usedTasks[j] = 0;

//------GENEROWANIE-KOLEJNOŚCI-ZADAŃ-NA-PIERWSZEJ-MASZYNIE
        for(int j = 0 ; j < numberOfTasks ; j++) {
            while(true){
                int taskNumber =(int) (rand()% numberOfTasks);
                if(usedTasks[taskNumber] == 0) {
                    usedTasks[taskNumber] = 1;
                    taskOrder[j] = taskNumber;
                    break;
                }
            }
        }

//------DODAWANIE-TASKÓW-DO-AKTUALNIE-GENEROWANEGO-ROZWIAZANIA
        for(int j = 0 ; j < numberOfTasks ; j++) {



/*__________GENEROWANIE-USZEREGOWANIA-DLA-MASZYNY-1*/
            int taskNumber = taskOrder[j];                  //---RZECZYWISTY-NUMER-ZADANIA-KTORE-MA-ZOSTAC-DODANE-DO-ROZWIAZANIA
            int task_start_timeM1 = 0;                      //---MOMENT-CZASU-W-KTORYM-AKTUALNIE-DODAWANE-ZADANIE-MOZE-ROZPOCZAC-WYKONYWANIE
            Task *machine1Task, *sequenceM1;

            machine1Task = machine1_operations;             //---WSKAŹNIK-NA-ZADANIE-Z-LISTY-ZADAŃ-WCZYTANYCH-Z-PLIKU
            sequenceM1 = solution->machine_1_sequence;      //---WSKAŹNIK-POMOCNICZY-NA-AKTUALNIE-GENEROWANE-ROZWIAZANIE-DLA-MASZYNY-PIERWSZEJ

//----------PRZESUNIECIE-WSKAZNIKA-NA-POZYCJE-KTOREMU-ODPOWIADA-WCZESNIEJ-WYGENEROWANY-NUMER-ZADANIA
            for(int k = 0; k < taskNumber ; k++) {
                machine1Task = machine1Task->next;
            }

//----------ZNALEZIENIE-NAJBLIZSZEGO-MOZLIWEGO-CZASU-KIEDY-ZADANIE-MOZE-ROZPOCZAC-WYKONYWANIE
            while(sequenceM1) {
                task_start_timeM1 = sequenceM1->start_time + sequenceM1->time_length;
                sequenceM1 = sequenceM1->next;
            }

            Task *pauseM1;                                  //---WSKAZNIK-NA-LISTE-PRZERW-DLA-MASZYNY-1
            bool checkAgain = true;

//----------ZNAJDOWANIE-NOWEGO-MOZLIWEGO-CZASU-ROZPOCZECIA-WYKONYWANIA-ZADANIA-W-ZALEZNOSCI-OD-PRZERW
            while(checkAgain){
                pauseM1 = machine1_pauses;
                while(pauseM1) {
                    for(int k = task_start_timeM1 ; k <= task_start_timeM1 + machine1Task->time_length ; k++) {
                        if(k >= pauseM1->start_time && k <= pauseM1->start_time + pauseM1->time_length) {
                            task_start_timeM1 = pauseM1->start_time + pauseM1->time_length;
                            checkAgain = true;
                            break;
                        }
                    }
                    checkAgain = false;
                    pauseM1 = pauseM1->next;
                }
            }
            solution->machine_1_sequence->add(task_start_timeM1, machine1Task->time_length, machine1Task->real_number, false, solution->machine_1_sequence);



/*__________GENEROWANIE-USZEREGOWANIA-DLA-MASZYNY-2*/
            Task *machine2Task, *sequenceM2;
            int task_start_timeM2 = 0;                      //---MOMENT-CZASU-W-KTORYM-AKTUALNIE-DODAWANE-ZADANIE-MOZE-ROZPOCZAC-WYKONYWANIE

            machine2Task = machine2_operations;             //---WSKAZNIK-NA-ZADANIE-Z-LISTY-ZADAN-WCZYTANYCH-Z-PLIKU
            sequenceM2 = solution->machine_2_sequence;      //---WSKAZNIK-POMOCNICZY-NA-AKTUALNIE-GENEROWANE-ROZWIAZANIE-DLA-MASZYNY-DRUGIEJ

//---------PRZESUNIECIE-WSKAZNIKA-NA-POZYCJE-KTOREMU-ODPOWIADA-WCZESNIEJ-WYGENEROWANY-NUMER-ZADANIA
            for(int k = 0 ; k < taskNumber ; k++) {
                machine2Task = machine2Task->next;
            }

//---------ZNALEZIENIE-NAJBLIZSZEGO-MOZLIWEGO-CZASU-KIEDY-ZADANIE-MOZE-ROZPOCZAC-WYKONYWANIE
            while(sequenceM2) {
                task_start_timeM2 = sequenceM2->start_time + sequenceM2->time_length;
                sequenceM2 = sequenceM2->next;
            }

//----------SPRAWDZENIE-CZY-ZADANIE-NA-MASZYNIE-2-NIE-ZACZYNA-SIE-SZYBCIEJ-NIZ-KONCZY-SIE-ZADANIE-NA-MASZYNIE-1
            if(task_start_timeM2 <= task_start_timeM1 + machine1Task->time_length) {
                task_start_timeM2 = task_start_timeM1 + machine1Task->time_length;
            }

            Task *pauseM2;                      //---WSKAZNIK-NA-LISTE-PRZERW-DLA-MASZYNY-2
            checkAgain = true;

//----------ZNAJDOWANIE-NOWEGO-MOZLIWEGO-CZASU-ROZPOCZECIA-WYKONYWANIA-ZADANIA-W-ZALEZNOSCI-OD-PRZERW
            while(checkAgain){
                pauseM2 = machine2_pauses;
                while(pauseM2) {
                    for(int k = task_start_timeM2 ; k <= task_start_timeM2 + machine2Task->time_length ; k++) {
                        if(k >= pauseM2->start_time && k <= pauseM2->start_time + pauseM2->time_length) {
                            task_start_timeM2 = pauseM2->start_time + pauseM2->time_length + 1;
                            checkAgain = true;
                            break;
                        }
                    }
                    checkAgain = false;
                    pauseM2 = pauseM2->next;
                }
            }

            solution->machine_2_sequence->add(task_start_timeM2, machine2Task->time_length, machine2Task->real_number, false, solution->machine_2_sequence);
        }
    }
    return numberOfTasks;
}


int load_instance(char fileName[20]) {
    char buf[100];                  //---ZMIENNA-POMOCNICZA-PRZECHOWUJACA-DANE-NA-TEMAT-ZADAN-I-PRZERW
    int numberOfTasks;              //---ILOSC-ZDAN-KTORE-WYSTEPUJA-W-DANEJ-INSTANCJI-PROBLEMU
    fstream plik;

    plik.open(fileName, ios::in);

    if(plik.good()) {
        plik.getline(buf, 6);
        numberOfTasks = atoi(buf);  //---WCZYTANIE-ILOSCI-ZADAN-(PIERWSZY-WIERSZ-PLIKU)

//------WCZYTANIE-I-DODANIE-WSZYSTKICH-ZADAN-DO-LISTY-ZADAN
        for(int i = 0 ; i < numberOfTasks ; i++) {
            int machine1_task, machine2_task;

            plik.getline(buf, 10, ';');
            machine1_task = atoi(buf);
            plik.getline(buf, 10);
            machine2_task = atoi(buf);

            machine1_operations->add(0, machine1_task, i, false, machine1_operations);
            machine2_operations->add(0, machine2_task, i, false, machine2_operations);
        }

//------WCZYTANIE-I-DODANIE-PRZERW-DO-LISTY-PRZERW
        while(!plik.eof()) {
            int pauseNumber, machineNumber, timeForPause, whenPauseStart;

            plik.getline(buf, 10, ';');
            pauseNumber = atoi(buf);
            plik.getline(buf, 10, ';');
            machineNumber = atoi(buf);
            plik.getline(buf, 10, ';');
            timeForPause = atoi(buf);
            plik.getline(buf, 10);
            whenPauseStart = atoi(buf);

            if(timeForPause == 0 && machineNumber == 0 && whenPauseStart == 0) break;

            if(machineNumber == 0) machine1_pauses->add(whenPauseStart, timeForPause, pauseNumber, true, machine1_pauses);
            if(machineNumber == 1) machine2_pauses->add(whenPauseStart, timeForPause, pauseNumber, true, machine2_pauses);
        }

    } else cout << "Ups...Something went wrong.";

    plik.close();

    return numberOfTasks;
}

void save_results(Population *population, char fileName[20]) {
    char new_fileName[30] ="solution/";
    strncat(new_fileName, fileName, 20);
    calculate_fitness(population);

    Solution *best_solution = population->solution;
    Solution *solution = population->solution;

    while(solution) {
        if(solution->fitness_value > best_solution->fitness_value) {
            best_solution = solution;
        }
        solution = solution->next;
    }

    Task *machine1_seq = best_solution->machine_1_sequence;
    Task *machine2_seq = best_solution->machine_2_sequence;
    int fitness_value = 0;
    int maximum_time;

    while(machine1_seq) {
        fitness_value += machine1_seq->start_time + machine1_seq->time_length;
        machine1_seq = machine1_seq->next;
    }

    while(machine2_seq) {
        fitness_value += machine2_seq->start_time + machine2_seq->time_length;
        maximum_time = machine2_seq->start_time + machine2_seq->time_length;
        machine2_seq = machine2_seq->next;
    }

    machine1_seq = best_solution->machine_1_sequence;
    machine2_seq = best_solution->machine_2_sequence;
    fstream plik;
    plik.open(new_fileName, ios::out);

    plik << maximum_time << ";" << fitness_value << endl;

//-----------WPISYWANIE-USZEREGOWANIA-NA-MASZYNIE-1
    int actuallTimeMoment = 0;
    int pause_number_M1 = 1;
    int idle_pause_number_M1 = 1;
    int sum_pause_M1 = 0;
    int sum_idle_pause_M1 = 0;

    plik << "M1:";
    while(machine1_seq) {
        bool idle = true;

        if(machine1_seq->start_time == actuallTimeMoment) {
            plik << "o1_z" << machine1_seq->real_number << "," << machine1_seq->start_time << "," << machine1_seq->time_length << ";";
            actuallTimeMoment = machine1_seq->start_time + machine1_seq->time_length;
            machine1_seq = machine1_seq->next;
            idle = false;
        }

        Task *machine1_p = machine1_pauses;
        while(machine1_p) {
            if(machine1_p->start_time == actuallTimeMoment) {
                plik << "maint" << pause_number_M1 << "_M1," << machine1_p->start_time << "," << machine1_p->time_length << ";";
                pause_number_M1++;
                sum_pause_M1 += machine1_p->time_length;
                actuallTimeMoment = machine1_p->start_time + machine1_p->time_length;
                idle = false;
            }
            machine1_p = machine1_p->next;
        }
        if(idle) {
            machine1_p = machine1_pauses;
            int closest_Pause = MAXINTATOM;
            int closest_Task = MAXINTATOM;

            Task *temp_machine1_seq = best_solution->machine_1_sequence;
            while(temp_machine1_seq) {
                if(temp_machine1_seq->start_time >= actuallTimeMoment) {
                    closest_Task = temp_machine1_seq->start_time;
                    break;
                }
                temp_machine1_seq = temp_machine1_seq->next;
            }

            while(machine1_p) {
                if(machine1_p->start_time < closest_Pause && machine1_p->start_time >= actuallTimeMoment) closest_Pause = machine1_p->start_time;
                machine1_p = machine1_p->next;
            }

            if(closest_Task < closest_Pause) {
                plik << "idle" << idle_pause_number_M1 << "_M1," << actuallTimeMoment << "," << closest_Task - actuallTimeMoment << ";";
                idle_pause_number_M1++;
                sum_idle_pause_M1 += closest_Task - actuallTimeMoment;
                actuallTimeMoment = closest_Task;
            } else {
                plik << "idle" << idle_pause_number_M1 << "_M1," << actuallTimeMoment << "," << closest_Pause - actuallTimeMoment << ";";
                idle_pause_number_M1++;
                sum_idle_pause_M1 += closest_Pause - actuallTimeMoment;
                actuallTimeMoment = closest_Pause;
            }
        }
    }
    plik << endl;


//-----------WPISYWANIE-USZEREGOWANIA-NA-MASZYNIE-2
    actuallTimeMoment = 0;
    int pause_number_M2 = 1;
    int idle_pause_number_M2 = 1;
    int sum_pause_M2 = 0;
    int sum_idle_pause_M2 = 0;

    plik << "M2:";
    while(machine2_seq) {
        bool idle = true;

        if(machine2_seq->start_time == actuallTimeMoment) {
            plik << "o2_z" << machine2_seq->real_number << "," << machine2_seq->start_time << "," << machine2_seq->time_length << ";";
            actuallTimeMoment = machine2_seq->start_time + machine2_seq->time_length;
            machine2_seq = machine2_seq->next;
            idle = false;
        }

        Task *machine2_p = machine2_pauses;

        while(machine2_p) {
            if(machine2_p->start_time == actuallTimeMoment) {
                plik << "maint" << pause_number_M2 << "_M2," << machine2_p->start_time << "," << machine2_p->time_length << ";";
                pause_number_M2++;
                sum_pause_M2 += machine2_p->time_length;
                actuallTimeMoment = machine2_p->start_time + machine2_p->time_length;
                idle = false;
            }
            machine2_p = machine2_p->next;
        }
        if(idle) {
            machine2_p = machine2_pauses;
            int closest_Pause = MAXINTATOM;
            int closest_Task = MAXINTATOM;

            Task *temp_machine2_seq = best_solution->machine_2_sequence;
            while(temp_machine2_seq) {
                if(temp_machine2_seq->start_time >= actuallTimeMoment) {
                    closest_Task = temp_machine2_seq->start_time;
                    break;
                }
                temp_machine2_seq = temp_machine2_seq->next;
            }

            while(machine2_p) {
                if(machine2_p->start_time < closest_Pause && machine2_p->start_time >= actuallTimeMoment) closest_Pause = machine2_p->start_time;
                machine2_p = machine2_p->next;
            }

            if(closest_Task < closest_Pause) {
                plik << "idle" << idle_pause_number_M2 << "_M2," << actuallTimeMoment << "," << closest_Task - actuallTimeMoment << ";";
                idle_pause_number_M2++;
                sum_idle_pause_M2 += closest_Task - actuallTimeMoment;
                actuallTimeMoment = closest_Task;
            } else {
                plik << "idle" << idle_pause_number_M2 << "_M2," << actuallTimeMoment << "," << closest_Pause - actuallTimeMoment << ";";
                idle_pause_number_M2++;
                sum_idle_pause_M2 += closest_Task - actuallTimeMoment;
                actuallTimeMoment = closest_Pause;
            }
        }
    }
    plik << endl;
    plik << pause_number_M1 << "," << sum_pause_M1 << endl;
    plik << pause_number_M2 << "," << sum_pause_M2 << endl;
    plik << idle_pause_number_M1 << "," << sum_idle_pause_M1 << endl;
    plik << idle_pause_number_M2 << "," << sum_idle_pause_M2;
    plik.close();
}

double getTime() {
  long long f, t;
  QueryPerformanceFrequency( (PLARGE_INTEGER) & f );
  QueryPerformanceCounter( (PLARGE_INTEGER) & t);
  return (double)t / (double)f;
}

int main() {

    #define START_POPULATION_SIZE  50                    //---ROZMIAR-POPULACJI-STARTOWEJ
    #define MAIN_POPULATION_SIZE  30                     //---ROZMIAR-POPULACJI-DO-KTOREGO-ROZMIARU-OPERATOR-SELEKCJI-BEDZIE-ZMNIEJSZAC
    #define CROSSOVER_PROPABILITY 95                  //---PRAWDOPODOBIENSTWO-WYSTAPIENIA-KRZYZOWANIA
    #define MUTATION_PROPABILITY 55                     //---PRAWDOPODOBIENSTWO-WYSTAPIENIA-MUTACJI

    int numberOfFiles = 1;                  //---LICZBA-PLIKOW-ZAWIERAJACYCH-ROZNE-INSTANCJE-PROBLEMU
    char fileName[20];

    srand(time(NULL));

    for(int i = 1; i <= numberOfFiles; i++) {
        Population *population = new Population;        //---WSKAZNIK-NA-POPULACJE-STARTOWA

        itoa(i * 100, fileName, 10);
        strncat(fileName, "RANDOM.txt", 10);

        int numberOfTasks = generate_population(load_instance(fileName), START_POPULATION_SIZE, population);        //---GENEROWANIE-STARTOWEJ-POPULACJI
        double startTime = getTime();
        double currentTime;

//------PRZEZ-OKRESLONY-CZAS-WYKONYWANE-SA-OPERACJE-MUTACJI-KRZYZOWANIA-I-SELEKCJI
       // do {
            Population *new_population = new Population;                            //---UTWORZENIE-NOWEGO-MIEJSCA-W-PAMIECI-DLA-NOWEJ-POPULACJI
/* SEL */   selection(population, new_population, MAIN_POPULATION_SIZE);            //---SELEKCJA-STAREJ-POPULACJI-W-NOWA-POPULACJE
            delete population;
            population = new Population;

//----------WYKONWANIE-OPERACJI-MUTACJI-I-KRZYZOWANIA-DLA-KAZDEGO-ZADANIA
            Solution *solution = new_population->solution;

            while(solution) {

                int crossoverPropability = (rand() % 100) + 1;
/* CRO */       if(crossoverPropability <= CROSSOVER_PROPABILITY) crossover(solution, new_population, numberOfTasks, population);

                int mutationPropability = (rand() % 100) + 1;
/* MUT */       if(mutationPropability <= MUTATION_PROPABILITY) {mutate(solution, numberOfTasks, population); cout << "MUTATAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";}

                solution = solution->next;

            }
            delete new_population;

            currentTime = getTime();
        //    } while(currentTime - startTime < 10);

        save_results(population, fileName);         //---ZAPISANIE-WYNIKU-PRZEPROWADZENIA-ALGORYTMU-DO-PLIKU-TEKSTOWEGO

        Solution * temp;
        temp = population->solution;

            Task *temp1;
            temp1 = temp->machine_1_sequence;

        while(temp) {
            Task *temp1, *temp2;
            temp1 = temp->machine_1_sequence;
            temp2 = temp->machine_2_sequence;
            while(temp1) {
                cout << temp1->start_time << ":" << temp1->start_time + temp1->time_length <<"\t";
                temp1 = temp1->next;
            }
            cout << endl << endl << "_________________________________________________" << endl << endl;
            while(temp2) {
                cout << temp2->start_time << ":" << temp2->start_time + temp2->time_length << "\t";
                temp2 = temp2->next;
            }
            cout << endl << endl << endl << endl << temp->fitness_value << endl << endl << endl;
            temp = temp->next;
        }
    }

    return 0;
}