# Multi-Mode Resource Constrained Project Scheduling Problem (MRCPSP)¶

The Resource Constrained Project Scheduling Problem (RCPSP) consists in determining the start time of each task of a project, these tasks being subject to precedence and resources constraints. The precedence constraints are defined by the impossibility to start processing a task while the processing of at least one of its predecessor is not finished. Each task consumes a certain amount of resources, all of which are renewable. This means that all the consumptions of tasks are restored to the resource once the task’s processing is finished. In the RCPSP, the tasks’ duration is fixed. For the Multi-Mode version (MRCPSP), both the duration and the consumptions of tasks depend on the mode assigned to the task.

## Model formulation¶

To express a mathematical model for the MRCPSP suited for Artelys Kalis, we will use Tasks, which are objects that rely on integer variables as their start time, duration time and end time. We note the number of tasks to schedule and for each task its start time is an integer variable , its duration is an integer variable and its end time is an integer variable .

As said, the MRCPSP is different from the RCPSP by the fact that the durations and resource consumptions of tasks depend on their mode. For a task , its mode is an integer variable , the set of potential durations and is the set of potential consumption on each resource . For each task and each resource , is an integer variable representing the consumption of task on resource .

For each resource , its capacity (or availability) is noted , and the number of renewable resources is noted , while the number of non-renewable resources is noted .

Finally, we note the set of precedence, with meaning that task precedes task .

We therefore have the following model for the MRCPSP:

Let note that the last two sets of constraints of our model are implemented using element constraints.

## Implementation¶

In this section, we will see how to implement the mathematical model formulated above using the different interfaces of Artelys Kalis. Most especially, we will benefit from the API dedicated to scheduling problems.

#include <iostream>
#include <sstream>

// Including "kalis.h" to access the library
#include "Kalis.h"

// ********************************************************************
// * Main Program                                                     *
// ********************************************************************

int min(int a[], int size) {
int min = a[0];
for(int i = 1; i < size; i++) {
if(min > a[i]) {
min = a[i];
}
}
return min;
}

int max(int a[], int size) {
int max = a[0];
for(int i = 1; i < size; i++) {
if(max < a[i]) {
max = a[i];
}
}
return max;
}

template <size_t x, size_t y, size_t z>
int * retrieveConsumptions(int nbModes[], int (&consumptions)[x][y][z], int task, int res) {
for(int i = 0; i < nbModes[task]; i++) {
}
return c;
}

int main(void) {
// *** Description of datas

// *** Number of tasks in the project

// *** Number of resources
int const nbResources = 4;

// *** Number of renewable resources
int const nbResRen = 2;

// *** Horizon
int const horizon = 61;

// *** Number of modes of each task
int nbModes[10] = {3, 3, 3, 3, 1, 3, 3, 3, 3, 3};

// *** Set of successors of eack task
int nbSuccessors[10] = {2, 2, 1, 2, 2, 2, 1, 1, 0, 0};
{2, 3},
{3, 4},
{5},
{5, 6},
{6, 7},
{8, 9},
{9},
{9},
{},
{}
};

// *** Duration of eack task depending on their mode
{3, 5, 7},
{1, 4, 8},
{2, 3, 4},
{4, 5, 5},
{3},
{2, 4, 8},
{4, 5, 9},
{2, 3, 5},
{2, 4, 5},
{1, 4, 7}
};

// *** Consumption of resources by tasks depending on their mode: consumptions[idTask][idMode][idResource]
{{4, 2, 4, 5}, {2, 2, 3, 4}, {2, 1, 2, 1}},
{{5, 4, 4, 5}, {3, 3, 0, 3}, {2, 2, 0, 0}},
{{3, 3, 2, 0}, {2, 3, 2, 0}, {2, 2, 1, 0}},
{{3, 3, 4, 5}, {3, 3, 2, 0}, {3, 3, 0, 2}},
{{5, 5, 0, 0}},
{{4, 4, 4, 7}, {3, 3, 2, 5}, {2, 2, 0, 4}},
{{3, 2, 7, 3}, {3, 2, 3, 5}, {3, 2, 0, 0}},
{{2, 2, 5, 6}, {2, 4, 3, 3}, {2, 2, 0, 1}},
{{3, 3, 6, 4}, {4, 3, 4, 4}, {2, 2, 2, 2}},
{{4, 4, 6, 9}, {3, 3, 3, 5}, {4, 3, 2, 4}}
};

// *** Resource capacities
int resourceAvailabilities[nbResources] = {8, 7, 20, 25};

try {

// *** Creation of the Session
KSession session;

// *** Modeling of the problem
// *** Creation of the problem "MRCPSP" in this Session
KProblem problem(session, const_cast<char *>("MRCPSP"));

// Creation of the schedule
KSchedule schedule(problem, "Schedule", 0, horizon);

for(int i = 0; i < nbTasks; i++) {
std::stringstream sout("");
sout << "task(" << i << ")";
}

// Precedence
for(int i = 0; i < nbTasks; i++) {
for(int j = 0; j < nbSuccessors[i]; j++) {
}
}

// Resources
// renewable resources
KResource *resources = new KResource[nbResources];
for(int j = 0; j < nbResources; j++) {
std::stringstream sout("");
sout << "res(" << j << ")";
resources[j] = KDiscreteResource(schedule, sout.str().c_str(), resourceAvailabilities[j]);
for(int i = 0; i < nbTasks; i++) {
int *c = retrieveConsumptions(nbModes, consumptions, i, j);
if(j < nbResRen) {
resourceConsumptions[i*nbResources + j] = * tasks[i].getRequiresVar(&resources[j]);
} else {
resourceConsumptions[i*nbResources + j] = * tasks[i].getConsumesVar(&resources[j]);
}
delete [] c;
}
}

// Manage modes
KIntVarArray modes;
for(int i = 0; i < nbTasks; i++) {
std::stringstream sout("");
sout << "mode(" << i << ")";
modes += KIntVar(problem, sout.str().c_str(), 0, nbModes[i] - 1);

KIntArray durationsValues;
for(int k = 0; k < nbModes[i]; k++) {
durationsValues += durations[i][k];
}
KEltTerm kelt(durationsValues, *(modes.getElt(i)));
for(int j = 0; j < nbResources; j++) {
KIntArray consumptionsValues;
for(int k = 0; k < nbModes[i]; k++) {
consumptionsValues += consumptions[i][k][j];
}
KEltTerm keltConsumptions(consumptionsValues, *(modes.getElt(i)));
problem.post(new KElement(keltConsumptions, resourceConsumptions[i*nbResources + j]));
}
}

schedule.close();

KBranchingSchemeArray myBranchingSchemeArray;
KIntVarArray intvarArray;
for(int i = 0; i < nbTasks; i++) {
intvarArray += *(modes.getElt(i));
}
myBranchingSchemeArray += KAssignVar(KInputOrder(),KMinToMax(), intvarArray);

// problem.print();

// propagating problem
if (problem.propagate()) {
std::cout << "Problem is infeasible" << std::endl;
exit(1);
}

// *** Creation of the solver using our tree search controls for this problem
KSolver solver(problem, myBranchingSchemeArray);

solver.optimize();

// *** Get the last ( therefore the best ) solution and store it in a Solution object
KSolution solution = problem.getSolution();

// *** Print variables values for this solution
std::cout << "Best solution :" << std::endl;
solution.print();

// *** Print the objective value
std::cout << "Objective Value = " << solution.getObjectiveValue() << std::endl;

delete [] resourceConsumptions;
delete [] resources;

} catch (ArtelysException &artelysException) {
// *** An error occured
std::cout << "Exception " << artelysException.getCode() << " raised : " << artelysException.getMessage() << std::endl;
}

return 0;
}


## Results¶

The minimum makespan of the schedule is 20, with the following start times and modes for the tasks:

 Task 0 1 2 3 4 5 6 7 8 9 Start Time 0 0 7 7 4 12 12 9 16 16 Mode 2 1 0 2 0 1 0 2 1 1