MH-Builder Tutorial

/***************************************************************************************
*                 MH-Builder,   a framework for designing adaptive metaheuristics    *
*                               for single and multi-objective optimization.           *
*                    (c) 2019 University of Lille, CNRS                                *
*                                                                                      *
* This program is free software; you can redistribute it and/or modify it              *
* under the terms of the GNU General Public License as published by                    *
* the Free Software Foundation; either version 3 of the License, or (at                *
* your option) any later version.                                                      *
*                                                                                      *
* This program is distributed in the hope that it will be useful, but WITHOUT          *
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or                *
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License                 *
* for more details.                                                                    *
*                                                                                      *
* You should have received a copy of the GNU General Public License                    *
* along with this program. If not, see <http://www.gnu.org/licenses/>.                 *
****************************************************************************************
         Authors: Asuncion Gomez and additional contributors (see Authors)
****************************************************************************************/

#ifndef MH_BUILDER_FSP_H
#define MH_BUILDER_FSP_H

#include "representation/permutation/PermutationSolution.h"
#include <fstream>

namespace representation::permutation::problems::fsp {
    /*! Define type for a FSP solution */
    template<typename FIT>
    class FSPSol : public representation::permutation::PermutationSolution<FIT> {
    public:
        /**
         * Construct a fsp solution of size n
         * @param n size of permutation (number of jobs)
         */
        explicit FSPSol(unsigned long long int n = 0) : representation::permutation::PermutationSolution<FIT>(n) {}
    };

    /**
     * Class representing a FSP (Flowshop Problem) instance
     */
    class FSP {
    public:
        /**
         * Load a FSP instance
         * @param instanceFile a data files
         */
        explicit FSP(const std::string &instanceFile) {
            readInstance(instanceFile);
        }

        /**
         * Read an instance file
         * @param instanceFile a data files
         */
        void readInstance(const std::string &instanceFile) {
            std::string line, tmp;

            std::ifstream input(instanceFile);
            if (!input)
                throw std::runtime_error("Error: unable to open benchmark file");

            input >> N >> M >> seed;
            due_date.resize(N);
            processing_time.resize(M);
            for (unsigned long long int i = 0; i < M; i++) {
                processing_time[i].resize(N);
            }


            total_job_processing_time.resize(N);
            std::fill(total_job_processing_time.begin(), total_job_processing_time.end(), 0);
            int num_job;
            total_processing_time = 0;
            for (unsigned long long int i = 0; i < N; i++) {
                input >> num_job >> due_date[i];
                for (unsigned long long int j = 0; j < M; j++) {
                    input >> processing_time[j][i];
                    total_processing_time += processing_time[j][i];
                    total_job_processing_time[i] += processing_time[j][i];
                }
            }

            input.close();
        }

        /**
         * Get the number of jobs
         *  @return the number of jobs
         */
        unsigned long long int getN() {
            return N;
        }

        /**
         * Get the number of machines
         *  @return the number of machines
         */
        unsigned long long int getM() {
            return M;
        }

        /**
         * Get the initial seed
         *  @return the initial seed
         */
        unsigned long long int getSeed() {
            return seed;
        }

        /**
         * Get the processing time matrix
         * @return the matrix of the the processing time
         */
        std::vector<std::vector<unsigned long long int>> getProcessingTimeMatrix() {
            return processing_time;
        }

        /**
         * Get the total processing time
         * @return the total processing time
         */
        unsigned long long int getTotalProcessingTime() const {
            return total_processing_time;
        }

        /**
         * Get the total processing time for job i
         * @return the total processing time for job i
         */
        unsigned long long int getTotalProcessingTime(unsigned long long int i) const {
            return total_job_processing_time[i];
        }

        /**
         * Get the due date of the job i
         *  @return the due date of the job i
         */
        double getDueDate(unsigned long long int i) const {
            return due_date[i];
        }

        /**
         * Get the task time of the job j at the machine i
         *  @return the task time of the job j at the machine i
         */
        unsigned long long int getProcessingTime(unsigned long long int i, unsigned long long int j) {
            return processing_time[i][j];
        }

    protected:
        /*! Number of jobs */
        unsigned long long int N;
        /*! Number of machines */
        unsigned long long int M;
        /*! Seed */
        unsigned long long int seed;
        /*! Due date vector*/
        std::vector<unsigned long long int> due_date;
        /*! Processing time matrix */
        std::vector<std::vector<unsigned long long int> > processing_time;
        /*! Total job processing time */
        std::vector<unsigned long long int> total_job_processing_time;
        /*! Total processing time */
        unsigned long long int total_processing_time;
    };
}
#endif //MH_BUILDER_FSP_H

/***************************************************************************************
*                 MH-Builder,   a framework for designing adaptive metaheuristics    *
*                               for single and multi-objective optimization.           *
*                    (c) 2019 University of Lille, CNRS                                *
*                                                                                      *
* This program is free software; you can redistribute it and/or modify it              *
* under the terms of the GNU General Public License as published by                    *
* the Free Software Foundation; either version 3 of the License, or (at                *
* your option) any later version.                                                      *
*                                                                                      *
* This program is distributed in the hope that it will be useful, but WITHOUT          *
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or                *
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License                 *
* for more details.                                                                    *
*                                                                                      *
* You should have received a copy of the GNU General Public License                    *
* along with this program. If not, see <http://www.gnu.org/licenses/>.                 *
****************************************************************************************
         Authors: Olivier Caron and additional contributors (see Authors)
****************************************************************************************/

#ifndef MH_BUILDER_NOWAITFSP_H
#define MH_BUILDER_NOWAITFSP_H


namespace representation::permutation::problems::fsp {

#include "representation/permutation/problems/fsp/FSP.h"
#include <algorithm>

    /**
        * Class representing a No-Wait FlowShop Problem) instance
    */
class NoWaitFSP : public representation::permutation::problems::fsp::FSP {
    public:
        explicit NoWaitFSP(const std::string &instanceFile) : FSP(instanceFile) {
            this->initDelay();
        }

        /**
         * initialize the delay matrix d (Bertolissi 2000)
         * d[i][j] corresponds to the delay between the start of job i and the start of following job j
         * on the same first machine
         */
        void initDelay() {
            d.resize(this->N);
            for (unsigned long long int i = 0; i < this->N; i++) {
                d[i].resize(this->N);
                for (unsigned long long int j = 0; j < this->N; j++) {
                    if (i != j) {
                        this->d[i][j] = this->processing_time[0][i];
                        int maxi = 0;
                        for (unsigned long long int r = 0; r < this->M; r++) {
                            int nb = 0;
                            for (unsigned long long int h = 1; h <= r; h++)
                                nb = nb + this->processing_time[h][i];
                            for (unsigned long long int h = 0; h < r; h++)
                                nb = nb - this->processing_time[h][j];
                            maxi = std::max(maxi, nb);
                        }
                        this->d[i][j] += maxi;
                    }
                }
            }
        }

        /**
         *
         * @param i job i
         * @param j job j following i
         * @return the delay between the start of job i and the start of following job j on the first machine
         */
        unsigned long long int
        delay(const unsigned long long int i, const unsigned long long int j) const {
            return this->d[i][j];
        }

    protected:
        /*! delay matrix d (Bertolissi 2000)
         * d[i][j] corresponds to the delay between the start of job i and the start of following job j
         * on the same first machine*/
        std::vector<std::vector<unsigned long long int>> d;
    };
}
#endif //MH_BUILDER_NOWAITFSP_H

/***************************************************************************************
*                 MH-Builder,   a framework for designing adaptive metaheuristics    *
*                               for single and multi-objective optimization.           *
*                    (c) 2019 University of Lille, CNRS                                *
*                                                                                      *
* This program is free software; you can redistribute it and/or modify it              *
* under the terms of the GNU General Public License as published by                    *
* the Free Software Foundation; either version 3 of the License, or (at                *
* your option) any later version.                                                      *
*                                                                                      *
* This program is distributed in the hope that it will be useful, but WITHOUT          *
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or                *
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License                 *
* for more details.                                                                    *
*                                                                                      *
* You should have received a copy of the GNU General Public License                    *
* along with this program. If not, see <http://www.gnu.org/licenses/>.                 *
****************************************************************************************
         Authors: Olivier Caron and additional contributors (see Authors)
****************************************************************************************/

#ifndef MH_BUILDER_NOWAITFSPEVAL_H
#define MH_BUILDER_NOWAITFSPEVAL_H

#include "core/Eval.h"
#include "NoWaitFSP.h"

namespace representation::permutation::problems::fsp {
    /**
     * Class representing an evaluator for Flowshop problem
     */
    template<typename FSPSol>
    class NoWaitFSPEval : public core::Eval<FSPSol> {
    public:

        /**
        ** Constructor of the evaluation
        ** @param _fsp data for evaluator
        */
        explicit NoWaitFSPEval(NoWaitFSP &_fsp) : fsp(_fsp) {
        }

        /**
         * Evaluate a NWFSP solution
         * @param sol a solution
         */
        void operator()(FSPSol &sol) override {
            /*! fitness solution */
            auto &fit = sol.fitness();
            auto objv = fit.objectives();

            /** single objective : makespan **/
            objv.resize(1);
            objv[0] = makespan(sol);
            fit.objectives(objv);
            this->eval_counter++;
        }

        virtual unsigned long long int makespan(const FSPSol &_fs) const {
            return completionTime(_fs.size() - 1, _fs);
        }

    protected:
        /*! FSP data */
        NoWaitFSP fsp;


        virtual unsigned long long int completionTime(const unsigned long long int pos, const FSPSol &_fs) const {
            if (pos == 0) return fsp.getTotalProcessingTime(_fs[0]);
            else {
                int time = 0;
                for (unsigned long long int k = 1; k <= pos; k++) time += fsp.delay(_fs[k - 1], _fs[k]);
                return time + fsp.getTotalProcessingTime(_fs[pos]);
            }
        }

    };
}
#endif //MH_BUILDER_NOWAITFSPEVAL_H