Flexible Resource-Constrained Project Scheduling Problem with States (FRCPSPS)

import hexaly.optimizer
import sys

def read_instance(filename):
    with open(filename) as f:
        lines = f.readlines()

    first_line = lines[0].split()

    # Number of tasks
    nb_tasks = int(first_line[0])

    # Number of resources
    nb_resources = int(first_line[1])

    # Number of states
    nb_states = int(first_line[2])

    # Maximum capacity of each resource
    capacity = [int(lines[1].split()[r]) for r in range(nb_resources)]

    #Delay after change of state
    delay_state = [[] for i in range(nb_states)]
    for i in range(nb_states):
        delay_state[i] = [int(lines[2+i].split()[j]) for j in range(nb_states)]

    # Duration of each task
    duration = [0 for i in range(nb_tasks)]

    # State of each task
    state = [0 for i in range(nb_tasks)]

    for i in range(nb_tasks):
        task_line = lines[i + 2 + nb_states].split()
        duration[i] = int(task_line[0])
        state[i] = int(task_line[1])
    
    # Trivial upper bound for the end times of the tasks
    horizon = sum(duration[i] for i in range(nb_tasks))

    return (nb_tasks, nb_resources, nb_states, capacity, delay_state, duration, state , horizon)


def main(instance_file, output_file, time_limit):
    nb_tasks, nb_resources, nb_states, capacity, delay_state, duration, state , horizon = read_instance(instance_file)

    with hexaly.optimizer.HexalyOptimizer() as optimizer:
        # Declare the optimization model
        model = optimizer.model

        # Interval decisions: time range of each task
        tasks = [model.interval(0, horizon) for i in range(nb_tasks)]

        # Task duration constraints
        for i in range(nb_tasks):
            model.constraint(model.length(tasks[i]) == duration[i])

        # Set of tasks done by each resource
        resources_tasks = [model.set(nb_tasks) for r in range(nb_resources)]
        resources = model.array(resources_tasks)

        # All tasks must be sheduled on a resource
        model.constraint(model.partition(resources))

        # Creates Hexaly arrays to allow access through "at" operator
        tasks_array = model.array(tasks)
        state_array = model.array(state)
        delay_array = model.array(delay_state)

        # Makespan: end of the last task
        makespan = model.max([model.end(tasks[i]) for i in range(nb_tasks)])

        # Resource constraints
        for r in range(nb_resources):
            capacity_respected = model.lambda_function(
                lambda t: model.sum(resources[r], model.lambda_function(
                    lambda i: model.contains(tasks_array[i], t)))
                <= capacity[r])
            model.constraint(model.and_(model.range(makespan), capacity_respected))

        # State incompatibility constraints
        for r in range(nb_resources):
            state_respected = model.lambda_function(
                lambda i: model.and_(resources_tasks[r], model.lambda_function(
                    lambda j: model.or_(state_array[i]==state_array[j],
                                        (model.end(tasks_array[i]) + delay_array[state_array[i]][state_array[j]]) <=model.start(tasks_array[j]),
                                        (model.end(tasks_array[j]) + delay_array[state_array[j]][state_array[i]]) <=model.start(tasks_array[i])))))
            model.constraint(model.and_(resources_tasks[r], state_respected))

        # Minimize the makespan
        model.minimize(makespan)

        model.close()

        # Parameterize the optimizer
        optimizer.param.time_limit = time_limit

        optimizer.solve()        

        # Write the solution in a file with the following format:
        #  - total makespan, number of Tasks
        #  - for each task, the task id, the start, the end times and the ressource of the task*/
        #
        if output_file != None:
            task_resources = [0 for i in range(nb_tasks)]

            for r in range(nb_resources):
                for task in resources_tasks[r].value:
                    task_resources[task]= r

            with open(output_file, "w") as f:
                print("Solution written in file", output_file)
                f.write(str(makespan.value) + " " + str(nb_tasks) + "\n")
                for i in range(nb_tasks):
                    f.write(str(i + 1) + " " + str(tasks[i].value.start()) + " " + str(tasks[i].value.end()) + " " + str(task_resources[i]))
                    f.write("\n")


if __name__ == '__main__':
    if len(sys.argv) < 2:
        print("Usage: python rcpsp.py instance_file [output_file] [time_limit]")
        sys.exit(1)

    instance_file = sys.argv[1]
    output_file = sys.argv[2] if len(sys.argv) >= 3 else None
    time_limit = int(sys.argv[3]) if len(sys.argv) >= 4 else 60
    main(instance_file, output_file, time_limit)

#include "optimizer/hexalyoptimizer.h"
#include <algorithm>
#include <fstream>
#include <iostream>
#include <limits>
#include <numeric>
#include <vector>


using namespace hexaly;

class Frcpsps {
private:
    // Number of tasks
    int nbTasks;
    // Number of resources
    int nbResources;
    // Number of states
    int nbStates;
    // Maximum capacity of each resource
    std::vector<int> capacity;
    // Delay after change of state
    std::vector<std::vector<int>> delayState;
    // Duration of each task
    std::vector<int> duration;
    // state of each task
    std::vector<int> state;
    // Trivial upper bound for the end times of the tasks
    int horizon = 0;

    // Hexaly Optimizer
    HexalyOptimizer optimizer;
    
    // Decision variables: time range of each task
    std::vector<HxExpression> tasks;

    // Decision variables: set of tasks done by each resource
    std::vector<HxExpression> resourceTasks;

    // For each task, the selected resource
    std::vector<HxExpression> taskResource;
    
    // Objective = minimize the makespan: end of the last task
    HxExpression makespan;


public:
    Frcpsps(const std::string& fileName) : optimizer() {}

    void readInstance(const std::string& fileName) {
        std::ifstream infile;
        infile.exceptions(std::ifstream::failbit | std::ifstream::badbit);
        infile.open(fileName.c_str());

        infile >> nbTasks >> nbResources >> nbStates;

        capacity.resize(nbResources);
        for (int r = 0; r < nbResources; ++r) {
            infile >> capacity[r];
        }

        delayState.resize(nbStates);
        for (int s = 0; s < nbStates; ++s) {
            delayState[s].resize(nbStates);
        }

        for (int i = 0; i < nbStates; ++i) {
            for (int j = 0; j < nbStates; ++j) {
                infile >> delayState[i][j];
            }
        }

        duration.resize(nbTasks);
        state.resize(nbTasks);
        for (int i = 0; i < nbTasks; ++i) {
            infile >> duration[i] >> state[i];
        }

        // Trivial upper bound for the end times of the tasks
        horizon = std::accumulate(duration.begin(), duration.end(), 0);

        infile.close();
    }

    void solve(int TimeLimit) {
        // Declare the optimization model
        HxModel model = optimizer.getModel();

        // Interval decisions: time range of each task
        tasks.resize(nbTasks);
        for (int i = 0; i < nbTasks; ++i) {
            tasks[i] = model.intervalVar(0, horizon);
            // Task duration constraints
            model.constraint(model.length(tasks[i]) == duration[i]);
        }

        // Set of tasks done by each resource
        resourceTasks.resize(nbResources);
        HxExpression resources = model.array();
        for (int r = 0; r < nbResources; ++r) {
            resourceTasks[r] = model.setVar(nbTasks);
            resources.addOperand(resourceTasks[r]);
        }
        
        // All tasks must be sheduled on a resource
        model.constraint(model.partition(resources));

        // Makespan: end of the last task
        makespan = model.max();
        for (int i = 0; i < nbTasks; ++i) {
            makespan.addOperand(model.end(tasks[i]));
        }

        // For each task, the selected resource
        taskResource.resize(nbTasks);
        for (int i = 0; i < nbTasks; ++i) {
            taskResource[i] = model.find(resources, i);
        }

        // Creates Hexaly arrays to allow access through "at" operator
        HxExpression tasksArray = model.array();
        for (int i = 0; i < nbTasks; ++i) {
            tasksArray.addOperand(tasks[i]);
        }
        HxExpression stateArray = model.array();
        for (int i = 0; i < nbTasks; ++i) {
            stateArray.addOperand(state[i]);
        }
        HxExpression delayArray = model.array();
        for (int s = 0; s < nbStates; ++s) {
            delayArray.addOperand(model.array(delayState[s].begin(), delayState[s].end()));
        }

        // Resource constraints
        for (int r = 0; r < nbResources; ++r) {
            HxExpression capacityRespected = model.createLambdaFunction([&](HxExpression t) {
                HxExpression total = model.createLambdaFunction([&](HxExpression i) {
                    return model.contains(tasksArray[i], t);
                });
                HxExpression totalTasks = model.sum(resourceTasks[r], total);
                return model.leq(totalTasks, capacity[r]);
            });
            model.constraint(model.and_(model.range(0, makespan), capacityRespected));
        }

        // State incompatibility constraints
        for (int r = 0; r < nbResources; ++r) {
            HxExpression stateRespected = model.createLambdaFunction([&](HxExpression j) {
                HxExpression total = model.createLambdaFunction([&](HxExpression i) {
                    return model.or_(stateArray[i]==stateArray[j],
                                        model.end(tasksArray[i]) + delayArray[stateArray[i]][stateArray[j]] <= model.start(tasksArray[j]),
                                        model.end(tasksArray[j]) + delayArray[stateArray[j]][stateArray[i]] <= model.start(tasksArray[i]));
                });
                HxExpression totalstates = model.and_(resourceTasks[r], total);
                return  totalstates;
            });
            model.constraint(model.and_(resourceTasks[r], stateRespected));
        }

        // Minimize the makespan
        model.minimize(makespan);

        model.close();

        // Parameterize the optimizer
        optimizer.getParam().setTimeLimit(TimeLimit);

        optimizer.solve();        
    }

    /* Write the solution in a file with the following format:
    *  - total makespan, number of Tasks
    *  - for each task, the task id, the start, the end times and the ressource of the task*/
    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);
        }
        std::cout << "Solution written in file " << fileName << std::endl;

        outfile << makespan.getValue() << " " << nbTasks << std::endl;
        for (int i = 0; i < nbTasks; ++i) {
            outfile << i + 1 << " " << tasks[i].getIntervalValue().getStart() << " "
                    << tasks[i].getIntervalValue().getEnd() << " "
                    << taskResource[i].getValue()
                    << std::endl;
        }
        outfile.close();
    }
};

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

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

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

using System;
using System.IO;
using Hexaly.Optimizer;

public class Frcpsps : IDisposable
{
    // Number of tasks
    private int nbTasks;
    // Number of resources
    private int nbResources;
    // Number of states
    private int nbStates;
    // Maximum capacity of each resource
    private int[] capacity;
    // Delay after change of state
    private int[][] delayState;
    // Duration of each task
    private int[] duration;
    // state of each task
    private int[] state;

    // Trivial upper bound for the end times of the tasks
    private int horizon = 0;
    // Hexaly Optimizer
    private HexalyOptimizer optimizer;
    // Decision variables: time range of each task
    private HxExpression[] tasks;
    // Decision variables: set of tasks done by each resource
    private HxExpression[] resourceTasks;
    // For each task, the selected resource
    private HxExpression[] taskResource;    

    // Objective = minimize the makespan: end of the last task of the last job
    private HxExpression makespan;

    public Frcpsps(string fileName)
    {
        optimizer = new HexalyOptimizer();
    }

    private static string[] ReadNextLine(StreamReader input) {
        return input.ReadLine().Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
    }


    private void ReadInstance(string fileName)
    {
        using (StreamReader input = new StreamReader(fileName))
        {
            string[] splitted = ReadNextLine(input);
            if (splitted.Length == 0)
                splitted = ReadNextLine(input);
            nbTasks = int.Parse(splitted[0]);
            nbResources = int.Parse(splitted[1]);
            nbStates = int.Parse(splitted[2]);


            capacity = new int[nbResources];
            splitted = ReadNextLine(input);
            for (int r = 0; r < nbResources; ++r)
                capacity[r] = int.Parse(splitted[r]);

            delayState = new int[nbStates][];
            for (int i = 0; i < nbStates; ++i)
            {
                splitted = ReadNextLine(input);
                delayState[i] = new int[nbStates];
                for (int j = 0; j < nbStates; ++j)
                    delayState[i][j] = int.Parse(splitted[j]);
            }

            duration = new int[nbTasks];
            state = new int[nbTasks];

            for (int i = 0; i < nbTasks; ++i)
            {
                splitted = ReadNextLine(input);
                if (splitted.Length == 0)
                    splitted = ReadNextLine(input);
                duration[i] = int.Parse(splitted[0]);
                state[i] = int.Parse(splitted[1]);
                horizon += duration[i];
            }
        }
    }

    public void Dispose()
    {
        optimizer.Dispose();
    }

    public void Solve(int timeLimit)
    {
        // Declare the optimization model
        HxModel model = optimizer.GetModel();

        // Interval decisions: time range of each task
        tasks = new HxExpression[nbTasks];
        for (int i = 0; i < nbTasks; ++i)
        {
            tasks[i] = model.Interval(0, horizon);

        // Task duration constraints
            model.Constraint(model.Length(tasks[i]) == duration[i]);
        }

        // Set of tasks done by each resource
        resourceTasks = new HxExpression[nbResources];
        for (int r = 0; r < nbResources; ++r)
            resourceTasks[r] = model.Set(nbTasks);

        // Creates Hexaly arrays to allow access through "at" operator
        HxExpression resources = model.Array(resourceTasks);
        HxExpression delayArray = model.Array(delayState);
        HxExpression tasksArray = model.Array(tasks);
        HxExpression stateArray = model.Array(state);

        // All tasks must be sheduled on a resource
        model.Constraint(model.Partition(resources));

        // For each task, the selected resource
        taskResource = new HxExpression[nbTasks];
        for (int i = 0; i < nbTasks; ++i)
        {
            taskResource[i] = model.Find(resources, i);
        }

        // Makespan: end of the last task
        makespan = model.Max();
        for (int i = 0; i < nbTasks; ++i)
            makespan.AddOperand(model.End(tasks[i]));

        // Resource constraints
        for (int r = 0; r < nbResources; ++r)
        {
            HxExpression capacityRespected = model.LambdaFunction(t =>
                {
                    HxExpression total = model.LambdaFunction(i =>
                    {
                        HxExpression rExpr = model.CreateConstant(r);
                        return model.Contains(tasksArray[i], t);
                    });
                    HxExpression totalTasks = model.Sum(resourceTasks[r], total);
                    return totalTasks <= capacity[r];
                });
            model.Constraint(model.And(model.Range(0, makespan), capacityRespected));
        }

        // State incompatibility constraints
        for (int r = 0; r < nbResources; ++r)
        {
            HxExpression stateRespected = model.LambdaFunction(j =>
                {
                    HxExpression total = model.LambdaFunction(i =>
                    {
                        HxExpression rExpr = model.CreateConstant(r);
                        return model.Or(stateArray[i]==stateArray[j],
                                        (model.End(tasksArray[i]) + delayArray[stateArray[i]][stateArray[j]]) <= model.Start(tasksArray[j]),
                                        (model.End(tasksArray[j]) + delayArray[stateArray[j]][stateArray[i]]) <= model.Start(tasksArray[i]));
                    });
                    HxExpression TotalExpr = model.And(resourceTasks[r], total);
                    return TotalExpr;                                                    
                });
            model.Constraint(model.And(resourceTasks[r], stateRespected));
        }

        // Minimize the makespan
        model.Minimize(makespan);

        model.Close();

        // Parameterize the optimizer
        optimizer.GetParam().SetTimeLimit(timeLimit);

        optimizer.Solve();
    }

    /* Write the solution in a file with the following format:
    *  - total makespan, number of Tasks
    *  - for each task, the task id, the start, the end times and the ressource of the task*/
    public void WriteSolution(string fileName)
    {
        using (StreamWriter output = new StreamWriter(fileName))
        {
            Console.WriteLine("Solution written in file " + fileName);
            output.WriteLine(makespan.GetValue()+ " " + nbTasks);
            for (int i = 0; i < nbTasks; ++i)
            {
                output.Write((i + 1) + " " + tasks[i].GetIntervalValue().Start() + " " + tasks[i].GetIntervalValue().End() + " " + taskResource[i].GetValue());
                output.WriteLine();
            }
        }
    }

    public static void Main(string[] args)
    {
        if (args.Length < 1)
        {
            Console.WriteLine("Usage: Frcpsps instanceFile [outputFile] [timeLimit]");
            System.Environment.Exit(1);
        }

        string instanceFile = args[0];
        string outputFile = args.Length > 1 ? args[1] : null;
        string strTimeLimit = args.Length > 2 ? args[2] : "60";

        using (Frcpsps model = new Frcpsps(instanceFile))
        {
            model.ReadInstance(instanceFile);
            model.Solve(int.Parse(strTimeLimit));
            if (outputFile != null)
                model.WriteSolution(outputFile);
        }
    }
}

import java.util.*;
import java.io.*;
import com.hexaly.optimizer.*;

public class Frcpsps {    
    // Number of tasks
    private int nbTasks;
    // Number of resources
    private int nbResources;
    // Number of states
    private int nbStates;
    // Maximum capacity of each resource
    private int[] capacity;
    // Delay after change of state
    private int[][] delayState;
    // Duration of each task
    private int[] duration;
    // state of each task
    private int[] state;
    // Trivial upper bound for the end times of the tasks
    private int horizon = 0;

    // Hexaly Optimizer
    final HexalyOptimizer optimizer;
    // Decision variables: time range of each task
    private HxExpression[] tasks;
    // Decision variables: set of tasks done by each resource
    private HxExpression[] resourceTasks;
    // For each task, the selected resource
    private HxExpression[] taskResource;
    // Objective = minimize the makespan: end of the last task of the last job
    private HxExpression makespan;

    public Frcpsps(HexalyOptimizer optimizer, String fileName) throws IOException {
        this.optimizer = optimizer;
    }

    private void readInstance(String fileName) throws IOException {
        try (Scanner input = new Scanner(new File(fileName))) {
            input.useLocale(Locale.ROOT);
            nbTasks = input.nextInt();
            nbResources = input.nextInt();
            nbStates = input.nextInt();


            capacity = new int[nbResources];
            for (int r = 0; r < nbResources; ++r) {
                capacity[r] = input.nextInt();
            }

            delayState = new int[nbStates][nbStates];
            for (int i = 0; i < nbStates; ++i)  {
                for (int j = 0; j < nbStates; ++j)  {
                delayState[i][j] = input.nextInt();
                }
            }

            duration = new int[nbTasks];
            state = new int[nbTasks];
            
            for (int i = 0; i < nbTasks; ++i) {
                duration[i] = input.nextInt();
                state[i] = input.nextInt();
                horizon += duration[i];
            }
        }
    }

    public void solve(int timeLimit) {
        // Declare the optimization model
        HxModel model = optimizer.getModel();

        // Interval decisions: time range of each task
        tasks = new HxExpression[nbTasks];
        for (int i = 0; i < nbTasks; ++i) {
            tasks[i] = model.intervalVar(0, horizon);

        // Task duration constraints
            model.constraint(model.eq(model.length(tasks[i]), duration[i]));
        }

        // Set of tasks done by each resource
        resourceTasks = new HxExpression[nbResources];

        for (int r = 0; r < nbResources; ++r) {
            resourceTasks[r] = model.setVar(nbTasks);
        }

        // Creates Hexaly arrays to allow access through "at" operator
        HxExpression resources = model.array(resourceTasks);
        HxExpression delayArray = model.array(delayState);
        HxExpression tasksArray = model.array(tasks);
        HxExpression stateArray = model.array(state);

        // For each task, the selected resource
        taskResource = new HxExpression[nbTasks];
        for (int i = 0; i < nbTasks; ++i) {
            taskResource[i] = model.find(resources, i);
        }
        
        // All tasks must be sheduled on a resource
        model.constraint(model.partition(resources));        

        // Makespan: end of the last task
        makespan = model.max();
        for (int i = 0; i < nbTasks; ++i) {
            makespan.addOperand(model.end(tasks[i]));
        }

        // Resource constraints
        for (int r = 0; r < nbResources; ++r) {
            final int rL = r;
            HxExpression capacityRespected = model.lambdaFunction(t -> {
                HxExpression total = model.lambdaFunction(i -> {
                    HxExpression rExpr = model.createConstant(rL);
                    return model.contains(model.at(tasksArray, i), t);
                });
                HxExpression totalTasks = model.sum(resourceTasks[rL], total);
                return model.leq(totalTasks, capacity[rL]);
            });
            model.constraint(model.and(model.range(0, makespan), capacityRespected));
        }

        // State incompatibility constraints
        for (int r = 0; r < nbResources; ++r) {
            final int rL = r;
            HxExpression stateRespected = model.lambdaFunction(j -> {
                    HxExpression total = model.lambdaFunction(i ->
                    {
                        HxExpression rExpr = model.createConstant(rL);
                        return model.or(
                            model.eq(model.at(stateArray, i), model.at(stateArray, j)), 
                            model.leq(
                                model.sum(model.end(model.at(tasksArray, j)), model.at(delayArray, model.at(stateArray, j), model.at(stateArray, i))), 
                                model.start(model.at(tasksArray, i))),
                            model.leq(
                                model.sum(model.end(model.at(tasksArray, i)), model.at(delayArray, model.at(stateArray, i), model.at(stateArray, j))), 
                                model.start(model.at(tasksArray, j)))
                            );
                                        
                    });
                    HxExpression TotalExpr = model.and(resourceTasks[rL], total);
                    return TotalExpr;
                                                    
                });
            model.constraint(model.and(resourceTasks[rL], stateRespected));
        }

        // Minimize the makespan
        model.minimize(makespan);

        model.close();

        // Parameterize the optimizer
        optimizer.getParam().setTimeLimit(timeLimit);

        optimizer.solve();
    }

    /* Write the solution in a file with the following format:
    *  - total makespan, number of Tasks
    *  - for each task, the task id, the start, the end times and the ressource of the task*/
    public void writeSolution(String fileName) throws IOException {
        try (PrintWriter output = new PrintWriter(fileName)) {
            System.out.println("Solution written in file " + fileName);

            output.println(makespan.getValue()+ " " + nbTasks);

            for (int i = 0; i < nbTasks; ++i) {
                output.println((i + 1) + " " + tasks[i].getIntervalValue().getStart() + " "
                        + tasks[i].getIntervalValue().getEnd() + " "
                        + taskResource[i].getValue()   
                        );
            }
        }
    }

    public static void main(String[] args) {
        if (args.length < 1) {
            System.out.println("Usage: java project_schedulingg instanceFile [outputFile] [timeLimit]");
            System.exit(1);
        }

        String instanceFile = args[0];
        String outputFile = args.length > 1 ? args[1] : null;
        String strTimeLimit = args.length > 2 ? args[2] : "60";
        try (HexalyOptimizer optimizer = new HexalyOptimizer()) {
            Frcpsps model = new Frcpsps(optimizer, instanceFile);
            model.readInstance(instanceFile);
            model.solve(Integer.parseInt(strTimeLimit));
            if (outputFile != null) {
                model.writeSolution(outputFile);
            }
        } catch (Exception ex) {
            System.err.println(ex);
            ex.printStackTrace();
            System.exit(1);
        }
    }
}