{"cells": [{"cell_type": "markdown", "metadata": {}, "source": ["# Algo - Probl\u00e8me d'ordonnancement\n", "\n", "Un [probl\u00e8me d'ordonnancement](https://fr.wikipedia.org/wiki/Th%C3%A9orie_de_l%27ordonnancement) est un probl\u00e8me dans lequel il faut d\u00e9terminer le meilleur moment de d\u00e9marrer un travail, une t\u00e2che alors que celles-ci ont des dur\u00e9es bien pr\u00e9cises et d\u00e9pendent les unes des autres."]}, {"cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [{"data": {"text/html": ["\n", ""], "text/plain": [""]}, "execution_count": 2, "metadata": {}, "output_type": "execute_result"}], "source": ["from jyquickhelper import add_notebook_menu\n", "add_notebook_menu()"]}, {"cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": ["%matplotlib inline"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Enonc\u00e9\n", "\n", "On d\u00e9finit un probl\u00e8me d'ordonnancement un peu plus simple dans lequel toutes les t\u00e2ches ont la m\u00eame dur\u00e9e qu'on repr\u00e9sente par une matrice d'adjacence non sym\u00e9trique."]}, {"cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [{"data": {"text/html": ["\n", ""], "text/plain": [""]}, "execution_count": 4, "metadata": {}, "output_type": "execute_result"}], "source": ["import numpy\n", "import matplotlib.pyplot as plt\n", "from jyquickhelper import RenderJsDot\n", "\n", "\n", "def plot_network(mat):\n", " # Dessine un graph \u00e0 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\u00e9commenter cette ligne pour voir le r\u00e9sultat\n", " return RenderJsDot(dot)\n", "\n", "mat = numpy.array([[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", "plot_network(mat)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Le graphe se lit comme suit : *pour faire la t\u00e2che 2, il faut faire la t\u00e2che 0 et 1 d'abord.*"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Q1 : \u00e9crire un algorithme qui d\u00e9termine dans quel ordre on peut ex\u00e9cuter les t\u00e2ches.\n", "\n", "Il peut y avoir plusieurs t\u00e2ches en parall\u00e8le. Quelle forme pourrait prendre le r\u00e9sultat ?"]}, {"cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": []}, {"cell_type": "markdown", "metadata": {}, "source": ["### Q2 : Et si les t\u00e2ches n'ont plus la m\u00eame dur\u00e9e ?\n", "\n", "Ne pourrait-on pas r\u00e9utiliser ce qu'on a fait avec une petite astuce..."]}, {"cell_type": "markdown", "metadata": {}, "source": ["## R\u00e9ponses"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Q1\n", "\n", "Comment repr\u00e9senter le r\u00e9sultat ? Une id\u00e9e consiste \u00e0 cr\u00e9er un tableau fin $F_{i}$ o\u00f9 *i* est la t\u00e2che. $F_{i}=t$ signifie qu'au temps *t*, la t\u00e2che *i* est finie."]}, {"cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [{"data": {"text/plain": ["[0, 1, 2, 1, 3]"]}, "execution_count": 6, "metadata": {}, "output_type": "execute_result"}], "source": ["def order_same_weight(mat):\n", " # matrice la fin de chaque t\u00e2che\n", " # au d\u00e9but, on suppose qu'elles se terminent toutes \u00e0 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\u00e2che j ne d\u00e9pend d'aucune autre t\u00e2che\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\u00e9pend de la t\u00e2che 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", "order_same_weight(mat)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["On v\u00e9rifie sur un graphe plus compliqu\u00e9."]}, {"cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [{"data": {"text/html": ["\n", ""], "text/plain": [""]}, "execution_count": 7, "metadata": {}, "output_type": "execute_result"}], "source": ["mat2 = numpy.array([[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", "plot_network(mat2)"]}, {"cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [{"data": {"text/plain": ["[1, 2, 3, 2, 4, 0]"]}, "execution_count": 8, "metadata": {}, "output_type": "execute_result"}], "source": ["order_same_weight(mat2)"]}, {"cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [], "source": []}, {"cell_type": "markdown", "metadata": {}, "source": ["### Q2 \n", "\n", "Une astuce... Une t\u00e2che deux fois plus longue, c'est comme si on avait deux t\u00e2ches, la seconde d\u00e9pend uniquement de la premi\u00e8re ou alors simple tenir compte de la dur\u00e9e lorsqu'on calcule le maximum. Voir la ligne ``########### ligne chang\u00e9e``."]}, {"cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [{"data": {"text/plain": ["[0, 1, 2, 1, 3]"]}, "execution_count": 10, "metadata": {}, "output_type": "execute_result"}], "source": ["def order_any_weight(mat, durations):\n", " # mat est la matrice pr\u00e9c\u00e9dente\n", " # duractions est la dur\u00e9e de chaque t\u00e2che (les dur\u00e9es sont enti\u00e8res)\n", " # matrice la fin de chaque t\u00e2che\n", " # au d\u00e9but, on suppose qu'elles se terminent toutes \u00e0 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\u00e2che j ne d\u00e9pend d'aucune autre t\u00e2che\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\u00e9pend de la t\u00e2che i\n", " new_end = fin[i] + durations[i] ########### ligne chang\u00e9e\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", "order_any_weight(mat, durations=[1, 1, 1, 1, 1])"]}, {"cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [{"data": {"text/plain": ["[0, 1, 3, 1, 4]"]}, "execution_count": 11, "metadata": {}, "output_type": "execute_result"}], "source": ["order_any_weight(mat, durations=[1, 2, 1, 1, 1])"]}, {"cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [], "source": []}], "metadata": {"kernelspec": {"display_name": "Python 3", "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.7.2"}}, "nbformat": 4, "nbformat_minor": 2}