{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problème d'ordonnancement\n",
    "\n",
    "Un [problème d'ordonnancement](https://fr.wikipedia.org/wiki/Th%C3%A9orie_de_l%27ordonnancement) est un problème dans lequel il faut déterminer le meilleur moment de démarrer un travail, une tâche alors que celles-ci ont des durées bien précises et dépendent les unes des autres."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Enoncé\n",
    "\n",
    "On définit un problème d'ordonnancement un peu plus simple dans lequel toutes les tâches ont la même durée qu'on représente par une matrice d'adjacence non symétrique."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "\n",
       "    <script src=\"https://sdpython.github.io/js/viz-lite.js\"></script>\n",
       "    <div id=\"8bbaca87-572c-4a98-959c-3c0c9c4c923c\"></div>\n",
       "    <script>\n",
       "    var svgGraph = Viz(\"digraph{ \\n  rankdir=\\\"LR\\\";\\n  size=\\\"4,4\\\";\\n  0;\\n  1;\\n  2;\\n  3;\\n  4;\\n  0 -> 1;\\n  0 -> 2;\\n  0 -> 3;\\n  1 -> 2;\\n  1 -> 4;\\n  2 -> 4;\\n  3 -> 4;\\n}\");\n",
       "    document.getElementById('8bbaca87-572c-4a98-959c-3c0c9c4c923c').innerHTML = svgGraph;\n",
       "    </script>\n",
       "    "
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import uuid\n",
    "import numpy\n",
    "import matplotlib.pyplot as plt\n",
    "from IPython.display import HTML\n",
    "\n",
    "\n",
    "def plot_network(mat):\n",
    "    # Dessine un graph à l'aide du language DOT\n",
    "    # https://graphviz.org/doc/info/lang.html\n",
    "    rows = [\"digraph{ \", '  rankdir=\"LR\";', '  size=\"4,4\";']\n",
    "    for i in range(max(mat.shape)):\n",
    "        rows.append(\"  %d;\" % i)\n",
    "    for i in range(mat.shape[0]):\n",
    "        for j in range(mat.shape[1]):\n",
    "            if mat[i, j] > 0:\n",
    "                rows.append(\"  %d -> %d;\" % (i, j))\n",
    "    rows.append(\"}\")\n",
    "    dot = \"\\n\".join(rows)\n",
    "    # print(dot)  # décommenter cette ligne pour voir le résultat\n",
    "    hdot = dot.replace(\"\\n\", \"\\\\n\").replace('\"', '\\\\\"')\n",
    "    uid = uuid.uuid4()\n",
    "    text = f\"\"\"\n",
    "    <script src=\"https://sdpython.github.io/js/viz-lite.js\"></script>\n",
    "    <div id=\"{uid}\"></div>\n",
    "    <script>\n",
    "    var svgGraph = Viz(\"{hdot}\");\n",
    "    document.getElementById('{uid}').innerHTML = svgGraph;\n",
    "    </script>\n",
    "    \"\"\"\n",
    "    return HTML(text)\n",
    "\n",
    "\n",
    "mat = numpy.array(\n",
    "    [\n",
    "        [0, 1, 1, 1, 0],\n",
    "        [0, 0, 1, 0, 1],\n",
    "        [0, 0, 0, 0, 1],\n",
    "        [0, 0, 0, 0, 1],\n",
    "        [0, 0, 0, 0, 0],\n",
    "    ]\n",
    ")\n",
    "\n",
    "plot_network(mat)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le graphe se lit comme suit : *pour faire la tâche 2, il faut faire la tâche 0 et 1 d'abord.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q1 : écrire un algorithme qui détermine dans quel ordre on peut exécuter les tâches.\n",
    "\n",
    "Il peut y avoir plusieurs tâches en parallèle. Quelle forme pourrait prendre le résultat ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q2 : Et si les tâches n'ont plus la même durée ?\n",
    "\n",
    "Ne pourrait-on pas réutiliser ce qu'on a fait avec une petite astuce..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Réponses"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q1\n",
    "\n",
    "Comment représenter le résultat ? Une idée consiste à créer un tableau fin $F_{i}$ où *i* est la tâche. $F_{i}=t$ signifie qu'au temps *t*, la tâche *i* est finie."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 1, 3]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def order_same_weight(mat):\n",
    "    # matrice la fin de chaque tâche\n",
    "    # au début, on suppose qu'elles se terminent toutes à l'origine des temps\n",
    "    fin = [-1 for i in range(mat.shape[0])]\n",
    "\n",
    "    for j in range(mat.shape[1]):\n",
    "        if mat[:, j].sum() == 0:\n",
    "            # si la tâche j ne dépend d'aucune autre tâche\n",
    "            # alors on peut commencer en 0\n",
    "            fin[j] = 0\n",
    "\n",
    "    update = True\n",
    "    while update:\n",
    "        update = False\n",
    "        for i in range(mat.shape[0]):\n",
    "            for j in range(mat.shape[1]):\n",
    "                if mat[i, j] == 0 or fin[i] == -1:\n",
    "                    continue\n",
    "                # indique la j dépend de la tâche i\n",
    "                if fin[j] < fin[i] + 1:\n",
    "                    update = True\n",
    "                    fin[j] = fin[i] + 1\n",
    "                    # fin[j] = max(fin[j], fin[i] + 1)\n",
    "\n",
    "    return fin\n",
    "\n",
    "\n",
    "order_same_weight(mat)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On vérifie sur un graphe plus compliqué."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "\n",
       "    <script src=\"https://sdpython.github.io/js/viz-lite.js\"></script>\n",
       "    <div id=\"b25e6056-a381-48b2-bd1c-6ca87449123c\"></div>\n",
       "    <script>\n",
       "    var svgGraph = Viz(\"digraph{ \\n  rankdir=\\\"LR\\\";\\n  size=\\\"4,4\\\";\\n  0;\\n  1;\\n  2;\\n  3;\\n  4;\\n  5;\\n  0 -> 1;\\n  0 -> 2;\\n  0 -> 3;\\n  1 -> 2;\\n  1 -> 4;\\n  2 -> 4;\\n  3 -> 4;\\n  5 -> 0;\\n}\");\n",
       "    document.getElementById('b25e6056-a381-48b2-bd1c-6ca87449123c').innerHTML = svgGraph;\n",
       "    </script>\n",
       "    "
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mat2 = numpy.array(\n",
    "    [\n",
    "        [0, 1, 1, 1, 0, 0],\n",
    "        [0, 0, 1, 0, 1, 0],\n",
    "        [0, 0, 0, 0, 1, 0],\n",
    "        [0, 0, 0, 0, 1, 0],\n",
    "        [0, 0, 0, 0, 0, 0],\n",
    "        [1, 0, 0, 0, 0, 0],\n",
    "    ]\n",
    ")\n",
    "plot_network(mat2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 2, 4, 0]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "order_same_weight(mat2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q2 \n",
    "\n",
    "Une astuce... Une tâche deux fois plus longue, c'est comme si on avait deux tâches, la seconde dépend uniquement de la première ou alors simple tenir compte de la durée lorsqu'on calcule le maximum. Voir la ligne ``########### ligne changée``."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 1, 3]"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def order_any_weight(mat, durations):\n",
    "    # mat est la matrice précédente\n",
    "    # duractions est la durée de chaque tâche (les durées sont entières)\n",
    "    # matrice la fin de chaque tâche\n",
    "    # au début, on suppose qu'elles se terminent toutes à l'origine des temps\n",
    "    fin = [-1 for i in range(mat.shape[0])]\n",
    "\n",
    "    for j in range(mat.shape[1]):\n",
    "        if mat[:, j].sum() == 0:\n",
    "            # si la tâche j ne dépend d'aucune autre tâche\n",
    "            # alors on peut commencer en 0\n",
    "            fin[j] = 0\n",
    "\n",
    "    update = True\n",
    "    while update:\n",
    "        update = False\n",
    "        for i in range(mat.shape[0]):\n",
    "            for j in range(mat.shape[1]):\n",
    "                if mat[i, j] == 0 or fin[i] == -1:\n",
    "                    continue\n",
    "                # indique la j dépend de la tâche i\n",
    "                new_end = fin[i] + durations[i]  ########### ligne changée\n",
    "                if fin[j] < new_end:\n",
    "                    update = True\n",
    "                    fin[j] = new_end\n",
    "                    # fin[j] = max(fin[j], fin[i] + 1)\n",
    "\n",
    "    return fin\n",
    "\n",
    "\n",
    "order_any_weight(mat, durations=[1, 1, 1, 1, 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 3, 1, 4]"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "order_any_weight(mat, durations=[1, 2, 1, 1, 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.10.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}