Open Shop Scheduling Problem¶

#include "localsolver.h"
#include <algorithm>
#include <fstream>
#include <iostream>
#include <limits>
#include <numeric>
#include <vector>

using namespace localsolver;

class Openshop {
private:
    // Number of jobs
    int nbJobs;
    // Number of machines
    int nbMachines;
    // Processing time on each machine for each job activity
    std::vector<std::vector<int>> processingTime;
    // Trivial upper bound for the start time of activities
    int maxStart;

    // Localsolver
    LocalSolver localsolver;
    // Decision variables : start time of each activity
    std::vector<std::vector<LSExpression>> start;
    // Decision variables : processing order of jobs for each machine
    std::vector<LSExpression> jobsOrder;
    // Decision variables : processing order of machines for each job
    std::vector<LSExpression> machinesOrder;
    // Objective = minimize the makespan: end of the last activity of the last job
    LSExpression makespan;

public:
    Openshop() : localsolver() {}

    // The input files follow the "Taillard" format
    void readInstance(const std::string& instanceFile) {
        std::ifstream infile;
        infile.exceptions(std::ifstream::failbit | std::ifstream::badbit);
        infile.open(instanceFile.c_str());

        infile.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
        infile >> nbJobs;
        infile >> nbMachines;
        infile.ignore(std::numeric_limits<std::streamsize>::max(), '\n');

        // Processing times for each job on each machine
        // (given in the activity order, the processing order is a decision variable)
        infile.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
        std::vector<std::vector<int>> processingTimesActivityOrder =
            std::vector<std::vector<int>>(nbJobs, std::vector<int>(nbMachines));
        for (int j = 0; j < nbJobs; ++j) {
            for (int m = 0; m < nbMachines; ++m) {
                infile >> processingTimesActivityOrder[j][m];
            }
        }
        infile.ignore(std::numeric_limits<std::streamsize>::max(), '\n');

        // Index of machines for each activity
        infile.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
        std::vector<std::vector<int>> machineIndex =
            std::vector<std::vector<int>>(nbJobs, std::vector<int>(nbMachines));
        for (int j = 0; j < nbJobs; ++j) {
            for (int m = 0; m < nbMachines; ++m) {
                int x;
                infile >> x;
                machineIndex[j][m] = x - 1;
            }
        }

        infile.close();

        // Reorder processing times: processingTime[j][m] is the processing time of the
        // activity of job j that is processed on machine m
        processingTime.resize(nbJobs);
        for (int j = 0; j < nbJobs; ++j) {
            processingTime[j].resize(nbMachines);
            for (int m = 0; m < nbMachines; ++m) {
                std::vector<int>::iterator findM = std::find(machineIndex[j].begin(), machineIndex[j].end(), m);
                int k = std::distance(machineIndex[j].begin(), findM);
                processingTime[j][m] = processingTimesActivityOrder[j][k];
            }
        }

        // Trivial upper bound for the start time of activities
        maxStart = 0;
        for (int j = 0; j < nbJobs; ++j) {
            maxStart += std::accumulate(processingTime[j].begin(), processingTime[j].end(), 0);
        }
    }

    void solve(int timeLimit) {
        // Declare the optimization model
        LSModel model = localsolver.getModel();

        // Integer decisions: start time of each activity
        // start[j][m] is the start time of the activity of job j
        // which is processed on machine m
        start.resize(nbJobs);
        std::vector<std::vector<LSExpression>> end(nbJobs);
        for (int j = 0; j < nbJobs; ++j) {
            start[j].resize(nbMachines);
            end[j].resize(nbMachines);
            for (int m = 0; m < nbMachines; ++m) {
                start[j][m] = model.intVar(0, maxStart);
                end[j][m] = start[j][m] + processingTime[j][m];
            }
        }
        LSExpression startArray = model.array();
        LSExpression endArray = model.array();
        for (int j = 0; j < nbJobs; ++j) {
            startArray.addOperand(model.array(start[j].begin(), start[j].end()));
            endArray.addOperand(model.array(end[j].begin(), end[j].end()));
        }

        // Sequence of activities on each machine
        jobsOrder.resize(nbMachines);
        for (int m = 0; m < nbMachines; ++m) {
            jobsOrder[m] = model.listVar(nbJobs);
            // Each job is scheduled on every machine
            model.constraint(model.eq(model.count(jobsOrder[m]), nbJobs));

            // Every machine executes a single activity at a time
            LSExpression sequenceLambda = model.createLambdaFunction([&](LSExpression i) {
                return model.geq(model.at(startArray, jobsOrder[m][i], m), model.at(endArray, jobsOrder[m][i - 1], m));
            });
            model.constraint(model.and_(model.range(1, nbJobs), sequenceLambda));
        }

        // Sequence of machines for each job
        machinesOrder.resize(nbJobs);
        for (int j = 0; j < nbJobs; ++j) {
            machinesOrder[j] = model.listVar(nbMachines);
            // Every activity is scheduled on its corresponding machine
            model.constraint(model.eq(model.count(machinesOrder[j]), nbMachines));

            // A job has a single activity at a time
            LSExpression sequenceLambda = model.createLambdaFunction([&](LSExpression k) {
                return model.geq(model.at(startArray, j, machinesOrder[j][k]),
                                 model.at(endArray, j, machinesOrder[j][k - 1]));
            });
            model.constraint(model.and_(model.range(1, nbMachines), sequenceLambda));
        }

        // Minimize the makespan : the end of the last activity
        makespan = model.max();
        for (int m = 0; m < nbMachines; ++m) {
            for (int j = 0; j < nbJobs; ++j) {
                makespan.addOperand(model.at(endArray, j, m));
            }
        }
        model.minimize(makespan);

        model.close();

        // Parametrize the solver
        localsolver.getParam().setTimeLimit(timeLimit);

        localsolver.solve();
    }

    /* Write the solution in a file with the following format:
     *  - for each machine, the job sequence */
    void writeSolution(const std::string& fileName) {
        std::ofstream outfile(fileName.c_str());
        if (!outfile.is_open()) {
            std::cerr << "File " << fileName << " cannot be opened." << std::endl;
            exit(1);
        }
        for (int m = 0; m < nbMachines; ++m) {
            LSCollection finalJobsOrder = jobsOrder[m].getCollectionValue();
            for (int j = 0; j < nbJobs; ++j) {
                outfile << finalJobsOrder.get(j) << " ";
            }
            outfile << std::endl;
        }
        outfile.close();
        std::cout << "Solution written in file " << fileName << std::endl;
    }
};

int main(int argc, char** argv) {
    if (argc < 2) {
        std::cout << "Usage: openshop instanceFile [outputFile] [timeLimit]" << std::endl;
        exit(1);
    }

    const char* instanceFile = argv[1];
    const char* outputFile = argc > 2 ? argv[2] : nullptr;
    const char* strTimeLimit = argc > 3 ? argv[3] : "60";

    Openshop model;
    try {
        model.readInstance(instanceFile);
        const int timeLimit = atoi(strTimeLimit);
        model.solve(timeLimit);
        if (outputFile != nullptr)
            model.writeSolution(outputFile);
        return 0;
    } catch (const std::exception& e) {
        std::cerr << "An error occured: " << e.what() << std::endl;
        return 1;
    }
}