Preemptive Resource-Constrained Project Scheduling Problem (PRCPSP)

import hexaly.optimizer
import sys


# The input files follow the "Patterson" format
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])

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

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

    # Resource weight of resource r required for task i
    weight = [[] for i in range(nb_tasks)]

    # Number of successors
    nb_successors = [0 for i in range(nb_tasks)]

    # Successors of each task i
    successors = [[] for i in range(nb_tasks)]

    for i in range(nb_tasks):
        line = lines[i + 2].split()
        duration[i] = int(line[0])
        weight[i] = [int(line[r + 1]) for r in range(nb_resources)]
        nb_successors[i] = int(line[nb_resources + 1])
        successors[i] = [int(line[nb_resources + 2 + s]) - 1 for s in range(nb_successors[i])]

    # Trivial upper bound for the start times of the tasks
    horizon = sum(duration[i] for i in range(nb_tasks))

    # Number of intervals authorized for each task (pseudo preemption)
    max_nb_preemptions = 4 

    return (nb_tasks, nb_resources, capacity, duration, weight, nb_successors, successors, horizon, max_nb_preemptions)


def main(instance_file, output_file, time_limit):
    nb_tasks, nb_resources, capacity, duration, weight, nb_successors, successors, horizon, max_nb_preemptions = read_instance(
        instance_file)

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

        # Interval decisions: time range of each task
        # Each task can be split into max_nb_preemtptions subtasks
        tasks = [[model.interval(0, horizon) for t in range(max_nb_preemptions)] 
                 for i in range(nb_tasks)]

        for i in range(nb_tasks):
            # Task duration constraints
            model.constraint(
                    model.sum(model.length(tasks[i][t]) for t in range(max_nb_preemptions)) == duration[i])
            
            # Precedence constraints between each task's subtasks
            for t in range(max_nb_preemptions - 1):
                model.constraint(tasks[i][t] < tasks[i][t + 1])
           
        # Precedence constraints between the tasks
        for i in range(nb_tasks):
            for s in range(nb_successors[i]):
                model.constraint(tasks[i][max_nb_preemptions - 1] < tasks[successors[i][s]][0])

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

        # Cumulative resource constraints
        for r in range(nb_resources):
            capacity_respected = model.lambda_function(
                lambda t: model.sum(weight[i][r] * model.contains(tasks[i][k], t)
                                    for i in range(nb_tasks) for k in range(max_nb_preemptions))
                <= capacity[r])
            model.constraint(model.and_(model.range(makespan), capacity_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
        # - for each task, the task id, the start and end times of each subtask
        #
        if output_file != None:
            with open(output_file, "w") as f:
                print("Solution written in file", output_file)
                f.write(str(makespan.value) + "\n")
                for i in range(nb_tasks):
                    start_time = tasks[i][0].value.start()
                    f.write(str(i + 1))
                    for k in range(max_nb_preemptions):
                        if tasks[i][k].value.end() != start_time :
                            f.write(" (" + str(start_time) + " " + str(tasks[i][k].value.end()) + ")")
                            if k < max_nb_preemptions - 1 :
                                start_time = tasks[i][k + 1].value.start()
                    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 Prcpsp {
private:
    // Number of tasks
    int nbTasks;
    // Number of resources
    int nbResources;
    // Maximum capacity of each resource
    std::vector<int> capacity;
    // Duration of each task
    std::vector<int> duration;
    // Resource weight of resource r required for task i
    std::vector<std::vector<int>> weight;
    // Number of successors
    std::vector<int> nbSuccessors;
    // Successors for each task i
    std::vector<std::vector<int>> successors;
    // Trivial upper bound for the start times of the tasks
    int horizon = 0;
    // Number of intervals authorized for each task (pseudo preemption)
    int maxNbPreemptions = 4;

    // Hexaly Optimizer
    HexalyOptimizer optimizer;
    // Decision variables: time range of each task
    std::vector<std::vector<HxExpression>> tasks;
    // Objective = minimize the makespan: end of the last task of the last job
    HxExpression makespan;

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

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

        infile >> nbTasks;
        infile >> nbResources;

        // The maximum capacity of each resource
        capacity.resize(nbResources);
        for (int r = 0; r < nbResources; ++r) {
            infile >> capacity[r];
        }

        duration.resize(nbTasks);
        weight.resize(nbTasks);
        nbSuccessors.resize(nbTasks);
        successors.resize(nbTasks);

        for (int i = 0; i < nbTasks; ++i) {
            infile >> duration[i];
            weight[i].resize(nbResources);
            for (int r = 0; r < nbResources; ++r) {
                infile >> weight[i][r];
            }
            infile >> nbSuccessors[i];
            successors[i].resize(nbSuccessors[i]);
            for (int s = 0; s < nbSuccessors[i]; ++s) {
                int x;
                infile >> x;
                successors[i][s] = x - 1;
            }
            horizon += duration[i];
        }

        infile.close();
    }

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

        // Interval decisions: time range of each task
        // Each task can be split into maxNbPreemptions subtasks
        tasks.resize(nbTasks);
        for (int i = 0; i < nbTasks; ++i) {

            tasks[i].resize(maxNbPreemptions);

            for (int t = 0; t < maxNbPreemptions; t++){
                tasks[i][t] = model.intervalVar(0, horizon);
            }
            
            // Task duration constraints
            HxExpression taskDuration = model.sum();
            for (int t = 0; t < maxNbPreemptions; t++) {
                taskDuration.addOperand(model.length(tasks[i][t]));
            }
            model.constraint(taskDuration == duration[i]);

            // Precedence constraints between each task's subtasks
            for (int t = 0; t < maxNbPreemptions - 1; t++){
                model.constraint(tasks[i][t] < tasks[i][t + 1]);
            }
        }
        
        // Precedence constraints between the tasks
        for (int i = 0; i < nbTasks; ++i) {
            for (int s = 0; s < nbSuccessors[i]; ++s) {
                model.constraint(tasks[i][maxNbPreemptions - 1] < tasks[successors[i][s]][0]);
            }
        }
        
        // Makespan: end of the last task
        makespan = model.max();
        for (int i = 0; i < nbTasks; ++i) {
            makespan.addOperand(model.end(tasks[i][maxNbPreemptions - 1]));
        }
        
        // Cumulative resource constraints
        for (int r = 0; r < nbResources; ++r) {
            HxExpression capacityRespected = model.createLambdaFunction([&](HxExpression t) {
                HxExpression totalWeight = model.sum();
                for (int i = 0; i < nbTasks; ++i) {
                    for (int k = 0; k < maxNbPreemptions; k++){
                        HxExpression taskWeight = weight[i][r] * model.contains(tasks[i][k], t);
                        totalWeight.addOperand(taskWeight);
                    }
                }
                return model.leq(totalWeight, capacity[r]);
            });
            model.constraint(model.and_(model.range(0, makespan), capacityRespected));
        }
        
        // 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
     *  - for each task, the task id, the start and end times of each subtask */
    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() << std::endl;
        for (int i = 0; i < nbTasks; ++i) {
            hxint startTime = (tasks[i][0]).getIntervalValue().getStart();
            outfile << i + 1;
            for (int k = 0; k < maxNbPreemptions; k++){
                if ((tasks[i][k]).getIntervalValue().getEnd() != startTime){
                outfile << " (" << startTime << " "
                                    << (tasks[i][k]).getIntervalValue().getEnd() << ")";
                    if (k < maxNbPreemptions - 1){
                        startTime = (tasks[i][k + 1]).getIntervalValue().getStart();
                    }
                }
            }
            outfile << std::endl;
        }
        outfile.close();
    }
};

int main(int argc, char** argv) {
    if (argc < 2) {
        std::cout << "Usage: Prcpsp 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";

    Prcpsp 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 Prcpsp : IDisposable
{
    // Number of tasks
    private int nbTasks;

    // Number of resources
    private int nbResources;

    // Maximum capacity of each resource
    private int[] capacity;

    // Duration of each task
    private int[] duration;

    // Resource weight of resource r required for task i
    private int[,] weight;

    // Number of successors
    private int[] nbSuccessors;

    // Successors for each task i
    private int[][] successors;

    // Trivial upper bound for the start times of the tasks
    private int horizon = 0;

    // Number of intervals authorized for each task (pseudo preemption)
    private int maxNbPreemptions = 4;

    // Hexaly Optimizer
    private HexalyOptimizer optimizer;

    // Decision variables: time range of each task
    private HxExpression[,] tasks;

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

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

    string[] SplitInput(StreamReader input)
    {
        string line = input.ReadLine();
        if (line == null)
            return new string[0];
        return line.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
    }

    // The input files follow the "Patterson" format
    private void ReadInstance(string fileName)
    {
        using (StreamReader input = new StreamReader(fileName))
        {
            string[] splitted = SplitInput(input);
            if (splitted.Length == 0)
                splitted = SplitInput(input);
            nbTasks = int.Parse(splitted[0]);
            nbResources = int.Parse(splitted[1]);

            // The maximum capacity of each resource
            capacity = new int[nbResources];
            splitted = SplitInput(input);
            for (int r = 0; r < nbResources; ++r)
                capacity[r] = int.Parse(splitted[r]);

            duration = new int[nbTasks];
            weight = new int[nbTasks, nbResources];
            nbSuccessors = new int[nbTasks];
            successors = new int[nbTasks][];

            for (int i = 0; i < nbTasks; ++i)
            {
                splitted = SplitInput(input);
                if (splitted.Length == 0)
                    splitted = SplitInput(input);
                duration[i] = int.Parse(splitted[0]);
                for (int r = 0; r < nbResources; ++r)
                    weight[i, r] = int.Parse(splitted[r + 1]);
                nbSuccessors[i] = int.Parse(splitted[nbResources + 1]);
                successors[i] = new int[nbSuccessors[i]];
                for (int s = 0; s < nbSuccessors[i]; ++s)
                    successors[i][s] = int.Parse(splitted[s + nbResources + 2]) - 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
        // Each task can be split into maxNbPreemptions subtasks
        tasks = new HxExpression[nbTasks, maxNbPreemptions];
        for (int i = 0; i < nbTasks; ++i)
        {
            for (int t = 0; t < maxNbPreemptions; ++t){
                tasks[i, t] = model.Interval(0, horizon);
            }

            // Task duration constraints
            HxExpression  taskDuration = model.Sum();
            for (int t = 0; t < maxNbPreemptions; ++t){
                taskDuration.AddOperand(model.Length(tasks[i, t]));
            }
            model.Constraint(taskDuration == duration[i]);

            // Precedence constraints between each task's subtasks
            for (int t = 0; t < maxNbPreemptions - 1; ++t){
                model.Constraint(tasks[i, t] < tasks[i, t + 1]);
            }
        }

        // Precedence constraints between the tasks
        for (int i = 0; i < nbTasks; ++i)
        {
            for (int s = 0; s < nbSuccessors[i]; ++s)
            {
                model.Constraint(tasks[i, maxNbPreemptions - 1] < tasks[successors[i][s], 0]);
            }
        }

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

        // Cumulative resource constraints
        for (int r = 0; r < nbResources; ++r)
        {
            HxExpression capacityRespected = model.LambdaFunction(t =>
                {
                    HxExpression totalWeight = model.Sum();
                    for (int i = 0; i < nbTasks; ++i)
                    {
                        for (int k = 0; k < maxNbPreemptions; ++k){
                            totalWeight.AddOperand(weight[i, r] * model.Contains(tasks[i, k], t));
                        }
                    }
                    return totalWeight <= capacity[r];
                }
            );
            model.Constraint(model.And(model.Range(0, makespan), capacityRespected));
        }

        // 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
     *  - for each task, the task id, the start and end times of each subtask */
    public void WriteSolution(string fileName)
    {
        using (StreamWriter output = new StreamWriter(fileName))
        {
            Console.WriteLine("Solution written in file " + fileName);
            output.WriteLine(makespan.GetValue());
            for (int i = 0; i < nbTasks; ++i)
            {
                long startTime = tasks[i, 0].GetIntervalValue().Start();
                output.Write((i + 1));
                for (int k = 0; k < maxNbPreemptions; ++k){
                    if (tasks[i, k].GetIntervalValue().End() != startTime){
                        output.Write(" (" + startTime + " " + tasks[i, k].GetIntervalValue().End() + ")");
                        if (k < maxNbPreemptions - 1){
                            startTime = tasks[i, k + 1].GetIntervalValue().Start();
                        }
                    }   
                } 
                output.WriteLine();
            }
        }
    }

    public static void Main(string[] args)
    {
        if (args.Length < 1)
        {
            Console.WriteLine("Usage: Prcpsp 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 (Prcpsp model = new Prcpsp(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 Prcpsp {
    // Number of tasks
    private int nbTasks;
    // Number of resources
    private int nbResources;
    // Maximum capacity of each resource
    private int[] capacity;
    // Duration of each task
    private int[] duration;
    // Resource weight of resource r required for task i
    private int[][] weight;
    // Number of successors
    private int[] nbSuccessors;
    // Successors for each task i
    private int[][] successors;
    // Trivial upper bound for the start times of the tasks
    private int horizon = 0;
    // Number of intervals authorized for each task (pseudo preemption)
    private int maxNbPreemptions = 4;

    // Hexaly Optimizer
    final HexalyOptimizer optimizer;
    // Decision variables: time range of each task
    private HxExpression[][] tasks;
    // Objective = minimize the makespan: end of the last task of the last job
    private HxExpression makespan;

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

    // The input files follow the "Patterson" format
    private void readInstance(String fileName) throws IOException {
        try (Scanner input = new Scanner(new File(fileName))) {
            nbTasks = input.nextInt();
            nbResources = input.nextInt();

            // The maximum capacity of each resource
            capacity = new int[nbResources];
            for (int r = 0; r < nbResources; ++r) {
                capacity[r] = input.nextInt();
            }

            duration = new int[nbTasks];
            weight = new int[nbTasks][nbResources];
            nbSuccessors = new int[nbTasks];
            successors = new int[nbTasks][];
            for (int i = 0; i < nbTasks; ++i) {
                duration[i] = input.nextInt();
                for (int r = 0; r < nbResources; ++r) {
                    weight[i][r] = input.nextInt();
                }
                nbSuccessors[i] = input.nextInt();
                successors[i] = new int[nbSuccessors[i]];
                for (int s = 0; s < nbSuccessors[i]; ++s) {
                    successors[i][s] = input.nextInt() - 1;
                }
                horizon += duration[i];
            }
        }
    }

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

        // Interval decisions: time range of each task
        // Each task can be split into maxNbPreemptions subtasks
        tasks = new HxExpression[nbTasks][maxNbPreemptions];
        for (int i = 0; i < nbTasks; ++i){

            for (int t = 0; t < maxNbPreemptions; ++t) {
                tasks[i][t] = model.intervalVar(0, horizon);
            }
            
            // Task duration constraints
            HxExpression taskDuration = model.sum();
            for (int t = 0; t < maxNbPreemptions; ++t) {
                taskDuration.addOperand(model.length(tasks[i][t]));
            }
            model.constraint(model.eq(taskDuration, duration[i]));

            // Precedence constraints between each task's subtasks
            for (int t = 0; t < maxNbPreemptions - 1; ++t){
                model.constraint(model.lt(tasks[i][t], tasks[i][t + 1]));
            }
        }

        // Precedence constraints between the tasks
        for (int i = 0; i < nbTasks; ++i) {
            for (int s = 0; s < nbSuccessors[i]; ++s) {
                model.constraint(model.lt(tasks[i][maxNbPreemptions - 1], tasks[successors[i][s]][0]));
            }
        }

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

        // Cumulative resource constraints
        for (int r = 0; r < nbResources; ++r) {
            final int rL = r;
            HxExpression capacityRespected = model.lambdaFunction(t -> {
                HxExpression totalWeight = model.sum();
                for (int i = 0; i < nbTasks; ++i) {
                    for (int k = 0; k < maxNbPreemptions; ++k){
                        totalWeight.addOperand(model.prod(
                            weight[i][rL],
                            model.contains(tasks[i][k], t)));
                    }
                }
                return model.leq(totalWeight, capacity[rL]);
            });
            model.constraint(model.and(model.range(0, makespan), capacityRespected));
        }

        // 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
     * - for each task, the task id, the start and end times of each subtask
     */
    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());

            for (int i = 0; i < nbTasks; ++i) {
                long start_time = tasks[i][0].getIntervalValue().getStart();
                output.print(i + 1);
                for (int k = 0; k < maxNbPreemptions; ++k){
                    if (tasks[i][k].getIntervalValue().getEnd() != start_time){
                        output.print(" (" + start_time + " "
                            + tasks[i][k].getIntervalValue().getEnd() + ")");
                        if (k < maxNbPreemptions - 1){
                            start_time = tasks[i][k + 1].getIntervalValue().getStart();
                        }
                    }
                }
                output.println();
            }
        }
    }

    public static void main(String[] args) {
        if (args.length < 1) {
            System.out.println("Usage: java Prcpsp 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()) {
            Prcpsp model = new Prcpsp(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);
        }
    }
}