notebooks/RCPSP tutorials/RCPSP-1 Introduction.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Introduction to RCPSP\n",
    "\n",
    "What is RCPSP ? (Resource Constrained Project Scheduling Problem)\n",
    "\n",
    "- $M$ activities or tasks in a project (instance)\n",
    "- Precedence constraints: \n",
    "\n",
    "    > If activity $j\\in[1,M]$ is a successor of activity $i\\in[1,M]$, then activity $i$ must be completed before activity $j$ can be started\n",
    "\n",
    "- Resource constraints: \n",
    "\n",
    "    > Each project is assigned a set of K renewable resources where each resource $k$ is available in $R_{k}$ units for the entire duration of the project. Each activity may require one or more of these resources to be completed. While scheduling the activities, the daily resource usage for resource $k$ can not exceed $R_{k}$ units. \n",
    "    \n",
    "- Each activity $j$ takes $d_{j}$ time units to complete.\n",
    "\n",
    "- The overall goal of the problem is usually to minimize the makespan.\n",
    "\n",
    "Here we focus on *single mode RCPSP with renewable resources*, but there exists also variants of the problem\n",
    "- multi-mode: a task can be performed in several ways (modes), with specific duration and resources needs. The choice of the mode is in this case part of the solution.\n",
    "- mix of renewable and non-renewable resources.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Prerequisites\n",
    "\n",
    "\n",
    "Concerning the python kernel to use for this notebook:\n",
    "- If running locally, be sure to use an environment with discrete-optimization and minizinc.\n",
    "- If running on colab, the next cell does it for you.\n",
    "- If running on binder, the environment should be ready.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# On Colab: install the library\n",
    "on_colab = \"google.colab\" in str(get_ipython())\n",
    "if on_colab:\n",
    "    import importlib\n",
    "    import os\n",
    "    import sys  # noqa: avoid having this import removed by pycln\n",
    "\n",
    "    !{sys.executable} -m pip install -U pip\n",
    "\n",
    "    # uninstall google protobuf conflicting with ray and sb3\n",
    "    ! pip uninstall -y protobuf\n",
    "\n",
    "    # install dev version for dev doc, or release version for release doc\n",
    "    !{sys.executable} -m pip install git+https://github.com/airbus/discrete-optimization@master#egg=discrete-optimization\n",
    "\n",
    "    # be sure to load the proper cffi (downgraded compared to the one initially on colab)\n",
    "    import cffi\n",
    "\n",
    "    importlib.reload(cffi)\n",
    "\n",
    "    # install and configure minizinc\n",
    "    !curl -o minizinc.AppImage -L https://github.com/MiniZinc/MiniZincIDE/releases/download/2.6.3/MiniZincIDE-2.6.3-x86_64.AppImage\n",
    "    !chmod +x minizinc.AppImage\n",
    "    !./minizinc.AppImage --appimage-extract\n",
    "    os.environ[\"PATH\"] = f\"{os.getcwd()}/squashfs-root/usr/bin/:{os.environ['PATH']}\"\n",
    "    os.environ[\"LD_LIBRARY_PATH\"] = (\n",
    "        f\"{os.getcwd()}/squashfs-root/usr/lib/:{os.environ['LD_LIBRARY_PATH']}\"\n",
    "    )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Imports"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import logging\n",
    "import random\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "import nest_asyncio\n",
    "import networkx as nx\n",
    "import numpy as np\n",
    "\n",
    "from discrete_optimization.datasets import fetch_data_from_psplib\n",
    "\n",
    "# Main module for RCPSP Model\n",
    "from discrete_optimization.rcpsp.rcpsp_model import RCPSPSolution\n",
    "from discrete_optimization.rcpsp.rcpsp_parser import get_data_available, parse_file\n",
    "from discrete_optimization.rcpsp.rcpsp_utils import (\n",
    "    Graph,\n",
    "    compute_graph_rcpsp,\n",
    "    plot_ressource_view,\n",
    "    plot_task_gantt,\n",
    ")\n",
    "\n",
    "# patch asyncio so that applications using async functions can run in jupyter\n",
    "nest_asyncio.apply()\n",
    "\n",
    "# set logging level\n",
    "logging.basicConfig(level=logging.INFO)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Download datasets\n",
    "\n",
    "If not yet available, we import the datasets from [psplib](https://www.om-db.wi.tum.de/psplib/data.html)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "needed_datasets = [\"j301_1.sm\"]\n",
    "download_needed = False\n",
    "try:\n",
    "    files_available_paths = get_data_available()\n",
    "    for dataset in needed_datasets:\n",
    "        if len([f for f in files_available_paths if dataset in f]) == 0:\n",
    "            download_needed = True\n",
    "            break\n",
    "except:\n",
    "    download_needed = True\n",
    "\n",
    "if download_needed:\n",
    "    fetch_data_from_psplib()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Set random seed (for reproducible results in this notebook)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def set_random_seed(seed=42):\n",
    "    random.seed(seed)\n",
    "    np.random.seed(seed)\n",
    "\n",
    "\n",
    "set_random_seed()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## View input data\n",
    "\n",
    "We use here the instance of an RCPSP described in the file `j301_1.sm`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### File structure\n",
    "Let us have a look of that file."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "filepath = [f for f in get_data_available() if \"j301_1.sm\" in f][0]\n",
    "with open(filepath, \"rt\") as f:\n",
    "    print(f.read())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are 32 jobs, including the source task (1) and the sink task (32). \n",
    "\n",
    "- The first part of the file describe the precedence constraints : \n",
    "  > Task $1$ should finish before task $2$, $3$, $4$ start.\n",
    "  \n",
    "- The second part of the file details the duration and resource usage per task : \n",
    "  > Task $3$ lasts 4 units of times and requires 10 units of $R_1$\n",
    "  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Parsing file\n",
    "We parse the file to get a RCPSP model object in discrete-optimization library."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "filepath = [f for f in get_data_available() if \"j301_1.sm\" in f][0]\n",
    "rcpsp_model = parse_file(filepath)\n",
    "print(type(rcpsp_model))\n",
    "print(rcpsp_model)\n",
    "print(\"Nb jobs : \", rcpsp_model.n_jobs)\n",
    "print(\"Precedences : \", rcpsp_model.successors)\n",
    "print(\"Resources Availability : \", rcpsp_model.resources)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Precedence graph\n",
    "We can have a visual version of the precedence graph :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# compute graph\n",
    "graph: Graph = compute_graph_rcpsp(rcpsp_model)\n",
    "graph_nx = graph.to_networkx()\n",
    "# compute positions\n",
    "dfs = nx.dfs_tree(G=graph_nx, source=1, depth_limit=10)\n",
    "shortest_path_length = nx.shortest_path_length(dfs, 1)\n",
    "length_to_nodes = {}\n",
    "position = {}\n",
    "for node in sorted(shortest_path_length, key=lambda x: shortest_path_length[x]):\n",
    "    length = shortest_path_length[node]\n",
    "    while not (length not in length_to_nodes or len(length_to_nodes[length]) <= 5):\n",
    "        length += 1\n",
    "    if length not in length_to_nodes:\n",
    "        length_to_nodes[length] = []\n",
    "    length_to_nodes[length] += [node]\n",
    "    position[node] = (length, len(length_to_nodes[length]))\n",
    "\n",
    "# different color for source and sink task\n",
    "sink_source_color = \"#FFB000\"\n",
    "normal_task_color = \"#648FFF\"\n",
    "node_color = len(graph_nx) * [normal_task_color]\n",
    "node_color[0] = sink_source_color\n",
    "node_color[-1] = sink_source_color\n",
    "\n",
    "# plot\n",
    "nx.draw_networkx(graph_nx, pos=position, node_color=node_color)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Critical path \n",
    "We can compute the largest path possible from source to sink task, which gives a lower bound on the makespan. This method is usually called critical path. \n",
    "When we computed the graph in previous cell, each edges store the minimum duration of a task, we also store the opposite of this number in ```minus_min_duration``` attribute of an edge."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(graph.edges[5])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This means to fulfill the (2, 15) precedence you have to accomplish the task 2, which takes minimum 8 unit times to do. Let's compute the critical path. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "path = nx.astar_path(\n",
    "    G=graph_nx,\n",
    "    source=1,\n",
    "    target=rcpsp_model.n_jobs,\n",
    "    heuristic=lambda x, y: -100 if x != rcpsp_model.n_jobs else 0,\n",
    "    weight=\"minus_min_duration\",\n",
    ")\n",
    "edges = [(n1, n2) for n1, n2 in zip(path[:-1], path[1:])]\n",
    "duration = sum(graph_nx[n[0]][n[1]][\"min_duration\"] for n in edges)\n",
    "print(\"Duration of critical path : \", duration)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We know that our makespan will be at minimum 38 then because we necessarly have to accomplish the task found in the critical path sequentially, and the sum of their duration is 38. We can visualize this path in the precedence graph : "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fig, ax = plt.subplots(1)\n",
    "nx.draw_networkx(graph_nx, pos=position, node_color=node_color, ax=ax)\n",
    "nx.draw_networkx_edges(graph_nx, pos=position, edgelist=edges, edge_color=\"r\", ax=ax)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Other procedure to compute critical path or minimum project duration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The critical path can be computed by a graph procedure described in https://www.youtube.com/watch?v=4oDLMs11Exs. It is a quite simple : forward and backward graph exploration. In the end it provides earliest start date, earliest finish date, and their counterpart (for a optimal schedule ignoring the resource requirements) : latest start date, latest finish date."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from discrete_optimization.rcpsp.solver.cpm import CPM\n",
    "\n",
    "solver = CPM(problem=rcpsp_model)\n",
    "critical_path = solver.run_classic_cpm()\n",
    "edges = [(pi, pi1) for pi, pi1 in zip(critical_path[:-1], critical_path[1:])]\n",
    "print(solver.map_node[rcpsp_model.sink_task])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The critical path can be identified as nodes where all the values are equals."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fig, ax = plt.subplots(1)\n",
    "nx.draw_networkx(graph_nx, pos=position, node_color=node_color, ax=ax)\n",
    "nx.draw_networkx_edges(graph_nx, pos=position, edgelist=edges, edge_color=\"r\", ax=ax)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We find the same result as previously.\n",
    "The CPM object is giving us more information on the problem than the pure longest path computation, let's look : "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for task in rcpsp_model.tasks_list:\n",
    "    print(f\"CPM output for task {task} : {solver.map_node[task]}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We access to all the labels that the critical path forward and backward pass computed. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Compute a \"Dummy\" solution for RCPSP\n",
    "A solution can be defined as a permutation of jobs which is then transformed into a feasible schedule if possible using the SGS routine, which stands for serial schedule generation scheme. It consists at scheduling an activity as soon as it is available following the permutation order if possible.\n",
    "The following algorithm is the following."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![image](img/sgs.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Compute a schedule from a given jobs permutation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "permutation = list(range(rcpsp_model.n_jobs_non_dummy))\n",
    "# We just pick a random permutation of [0, n]\n",
    "random.shuffle(permutation)\n",
    "print(f\"priority list given to sgs : {permutation}\")\n",
    "mode_list = [1 for i in range(rcpsp_model.n_jobs)]\n",
    "rcpsp_sol = RCPSPSolution(\n",
    "    problem=rcpsp_model, rcpsp_permutation=permutation, rcpsp_modes=mode_list\n",
    ")\n",
    "print(\"schedule feasible: \", rcpsp_sol.rcpsp_schedule_feasible)\n",
    "print(\"schedule: \", rcpsp_sol.rcpsp_schedule)\n",
    "print(\"rcpsp_modes:\", rcpsp_sol.rcpsp_modes)\n",
    "fitnesses = rcpsp_model.evaluate(rcpsp_sol)\n",
    "print(\"fitnesses: \", fitnesses)\n",
    "resource_consumption = rcpsp_model.compute_resource_consumption(rcpsp_sol)\n",
    "print(\"resource_consumption: \", resource_consumption)\n",
    "print(\"mean_resource_reserve:\", rcpsp_sol.compute_mean_resource_reserve())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Plotting the solution\n",
    "\n",
    "#### Resource consumption over time : "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fig_resource_view = plot_ressource_view(\n",
    "    rcpsp_model=rcpsp_model, rcpsp_sol=rcpsp_sol, title_figure=\"Dummy solution\"\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Task view\n",
    "We can plot the schedule from a task point of view too, each line of the plot show where the task should be accomplished."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fig_gantt = plot_task_gantt(rcpsp_model=rcpsp_model, rcpsp_sol=rcpsp_sol)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conclusion\n",
    "\n",
    "In this notebook you've been introduced to the definition of RCPSP problem which is a classical scheduling problem, with precedence constraint and resource consumption constraint.\n",
    "We have illustrated the precedence graph and ways of computing longest path that gives us a lower bound of the total duration of the schedule.\n",
    "Finally we introduced a method called *SGS* that computes a feasible schedule from a priority list of task to schedule.\n",
    "\n",
    "In following notebooks, you'll be introduced to scheduling solvers providing good quality schedules with different paradigm : \n",
    "- [greedy heuristics](RCPSP%20%232%20Heuristics%20Solving.ipynb)\n",
    "- [Metaheuristics and genetic algorithm](RCPSP%20%233%20Local%20search.ipynb)\n",
    "- [Linear programming](RCPSP%20%234%20Linear%20programming.ipynb)\n",
    "- [Constraint programming](RCPSP%20%235%20Constraint%20Programming.ipynb)\n",
    "- [Large Neighborhood search](RCPSP%20%236%20Large%20Neighbourhood%20Search%20.ipynb)\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.18"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": true,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "512px"
   },
   "toc_section_display": true,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}