notebooks/Cooking_Times_and_Dynamic_Programming_chapter.ipynb

{"nbformat": 4, "nbformat_minor": 0, "metadata": {"colab": {"name": "Cooking_Times_and_Dynamic_Programming_chapter.ipynb", "provenance": [], "collapsed_sections": []}, "kernelspec": {"name": "python3", "display_name": "Python 3"}}, "cells": [{"cell_type": "markdown", "metadata": {"id": "HfiFcAD_BDLs"}, "source": ["# Cooking Times and Dynamic Programming\n", "\n", "Copyright Luca de Alfaro, 2019. \n", "License: [CC-BY-NC-ND](https://creativecommons.org/licenses/by-nc-nd/4.0/)."]}, {"cell_type": "markdown", "metadata": {"id": "66851e8c4e4c2adb", "colab_type": "text"}, "source": "\nPrepared on: Tue Nov 16 12:32:56 2021\n\nThis is a book chapter; it is not a homework assignment.  \nDo not submit it as a solution to a homework assignment; you would receive no credit.\n"}, {"cell_type": "markdown", "metadata": {"id": "phBpLWvWfC7_"}, "source": ["In the previous chapter, on a particular run of the scheduler for pasta carbonara, I got:\n", "\n", "```\n", "['dice pancetta',\n", " 'fill pot with water',\n", " 'put eggs in bowl',\n", " 'put pancetta in pan',\n", " 'dice onions',\n", " 'put oil and butter in pan',\n", " 'bring pot of water to a boil',\n", " 'add salt to water',\n", " 'put pasta in water',\n", " 'beat eggs',\n", " 'put onions in pan',\n", " 'colander pasta',\n", " 'cook pancetta',\n", " 'serve']\n", "```\n", "\n", "This not only makes little sense; it violates the first axiom of making pasta, which states that pasta must be served as soon as fully cooked.  Above, we take our sweet time to cook pancetta _after_ the pasta has been colandered! \n", "Indeed, one of the challenges of true cooking is to ensure that things are ready at exactly the right times.  The pancetta has to be done cooking exactly when the pasta is colandered, so that all is united when it's just hot and right. \n", "The difficulty is that it's hard to decide precisely when do we need to start slicing onions, or heating water, to achieve this synchronicity.  \n", "We will help by designing a _timed scheduler._\n", "\n", "\n", " "]}, {"cell_type": "markdown", "metadata": {"id": "9JTLyqOOhe3n"}, "source": ["The idea behind the timed scheduler is to endow each task with an _execution time_.  We specify then that the whole schedule has to be done at time 0, and we then go back and compute when we need to start the various tasks, or rather, when is the last possible moment to start the individual tasks, to be done at time 0. \n", "\n", "The times at which we start tasks will be negative; if you find it strange to use negative time, you might want to think at it as a countdouwn, where we finish with -3, -2, -1, and at 0, not quite liftoff, but a call that dinner is ready; more prosaic perhaps, but also more commestible. "]}, {"cell_type": "markdown", "metadata": {"id": "iCwpQi5djMF_"}, "source": ["### Computing start times for the tasks\n", "\n", "How do we annotate each task with its starting time? \n", "\n", "The idea is as follows.  For a task $x$, denote by $t(x)$ its start time, denote by $d(x)$ its duration, and denote by $s(x)$ its set of successors, that is, the set of tasks that depend on $x$ directly. \n", "\n", "First, consider a task with no successors.  The task can be done last, and so we simply need to set $t(x) = -d(x)$ to ensure we finish at time 0.\n", "\n", "Second, consider a task $x$ with successors $s(x) = \\{y_1, y_2, \\ldots, y_n\\}$. \n", "In order to finish $x$ on time for the start of $y_i$, for $1 \\leq i \\leq n$, it must be $t(x) + d(x) \\leq t(y_i)$. \n", "As we wish to start $x$ as late as possible, to be done \"just in time\", $t(x)$ must be the _largest_ value such that $t(x) \\leq t(y_i) - d(x)$, for all $1 \\leq i \\leq n$. \n", "Thus, it is easy to see that we must choose\n", "\n", "$$\n", "t(x) = - d(x) + \\min_{y \\in s(x)} t(y) \\; .\n", "$$"]}, {"cell_type": "markdown", "metadata": {"id": "pRRKo0-akFTr"}, "source": ["###An abstract algorithm for starting times\n", "\n", "All we need to do is to ensure that the constraint \n", "\n", "$$t(x) = - d(x) + \\min_{y \\in s(x)} t(y)$$\n", "\n", "holds for all tasks (with the convention that $\\min \\emptyset = 0$). \n", "How can we do this? \n", "\n", "We can solve this following an approach known as _dynamic programming._  If you have a set of elements (in our case, tasks), along with a constraint on the elements (such as our formula for $t(x)$ for a task $x$), you can sometimes treat the constraint as an update rule, rather than an equality. To do so, we start by  setting the start times to be as late as possible, that is, to $-d(x)$. \n", "We then consider all task $x$ in turn, and we _update_ the start time of $x$ via:\n", "\n", "$$t(x) := -d(x)  + \\min_{y \\in s(x)} t(y) \\; .$$\n", "\n", "Once we cannot perform any update, the constraint will hold for all tasks.\n", "\n", "Our algorithm can thus be expressed as follows: \n", "\n", "1.   Set $t(x) = -d(x)$ for all tasks $x$. \n", "2.   Repeat:\n", ">  For all tasks $x$, do:\n", "$\n", "t(x) := -d(x)  + \\min_{y \\in s(x)} t(y)\n", "$\n", "* until no change occurs (that is, until $t(x)$ is unchanged for all tasks $x$). \n", "\n", "The \"until no change occurs\" above means that we have reached a _fixed point_ of the update rule: the update rule, when applied, causes no change in the values.\n", "\n", "Informally, the algorithm works because initially we set $t(x) = 0$ for every task, thus setting the start time to be as late as possible; we then anticipate the start time only if we have a good reason to do so, to leave enough time for a dependent task to also execute before time 0. "]}, {"cell_type": "markdown", "metadata": {"id": "hnZxF_4jTYDe"}, "source": ["### Correctness of the algorithm\n", "\n", "This section is optional, and can be skipped at a first reading.  "]}, {"cell_type": "markdown", "metadata": {"id": "B8bEwSnOnim1"}, "source": ["\n", "\n", "How can we prove precisely that the algorithm works? \n", "Denote by $t^*(x)$ the _true_ latest starting time for $x$.  \n", "The proof proceeds in the following steps.\n", "\n", "1.  **Termination:** first, we will prove that the algorithm terminates. \n", "2.  **Overapproximation:** Second, we will prove that throughout the algorithm, $t(x)$ is always later than the latest starting time, or $t(x) \\geq t^*(x)$.\n", "3.  **Underapproximation:** Then, we show that if the relation $t(x) = - d(x) + \\min_{y \\in s(x)} t(y)$ holds, then we have enough time to do all tasks, that is, $t(x) \\leq t^*(x)$. \n", "4.  From 2 and 3 above, we conclude that at the fixpoint we have $t(x) = t^*(x)$, QED.\n", "\n", "We prove 1, 2, 3  in the following.  Let $D(x)$ be the set of tasks that depend on $x$; of course, $s(x) \\subseteq D(x)$, but $D(x)$ also contains the tasks that depend on $x$ via intermediate tasks.\n"]}, {"cell_type": "markdown", "metadata": {"id": "6vl8fv44yM0E"}, "source": ["#### Termination\n", "\n", "The one difficult step consists in proving termination, because, well, the algorithm may actually _not_ terminate! \n", "\n", "If there are cycles in the dependency graph, the algorithm never terminates.  Consider tasks $a$, $b$, $c$, with $a$ dependent on $b$, $b$ on $c$, and $c$ on $a$; assume that all tasks take 1 second.  If we set $t(a) = 0$, we update then $t(c) = -1$, then $t(b) = -2$, then $t(a) = -3$, and so on and so forth. \n", "\n", "If there are no cycles in the dependency graph, then every path in the graph is of finite length (finite number of edges), because no node can be repeated along the path.  Let $n(x)$ be the length of the longest dependency path ending at $x$, so that $n(x) = 0$ if no task depends on $x$. We prove by induction that the value of $t(x)$ is determined after at most $n(x)$ iterations of step 2 above. \n", "This shows that the algorithm terminates in at most as many iterations of step 2 as there are tasks. \n", "\n", "Precisely, the inductive assertion is that $t(x)$ does not change after $n(x)$ iterations of the algorithm; the induction is over $n(x)$. \n", "\n", "For the base case, consider tasks $x$ with no dependents, so with $n(x) = 0$. \n", "Initially, we set $t(x) = -d(x)$, and as the set $D(x)$ of successor of $x$ is empty, the update reduces to $t(x) := -d(x)$, which leaves $t(x)$ unchanged. \n", "\n", "For the induction step, consider a task $x$ with $n(x) = k$.  Obviously, $n(y) < k$ for all $y \\in D(x)$, and by induction hypothesis, the values $t(y)$ of $y \\in D(x)$ are determined after $k-1$ iterations.  At iteration $k$, we set $t(x) := -d(x) + \\min_{y \\in s(x)} t(y)$; from then on, as there will not be any change in the right hand side of the update rule, the value of $t(x)$ will also not change."]}, {"cell_type": "markdown", "metadata": {"id": "-TM8LjX3ySTu"}, "source": ["#### Overapproximation\n", "\n", "We want to show that for all tasks $x$, we have $t(x) \\geq t^*(x)$. \n", "This is proved by induction on the number of iterations of the repeat (step 2) of the algorithm. \n", "\n", "The base case, for zero iterations, follows because initially we have $t(x) = 0$ and $t^*(x) \\leq 0$. \n", "\n", "In every subsequent iteration of the algorithm, denote with $t(x)$ the start time of $x$ before the iteration (at the end of the previous iteration), and with $t'(x)$ the start time of $x$ at the end of the iteration.  \n", "If $t'(x) \\geq t(x)$, the results follows immediately by induction. \n", "\n", "Assume that $t'(x) < t(x)$.  Then, there is a task $y \\in s(x)$ such that $t'(x) = -d(x) + t(y)$. \n", "By induction hypothesis, we have $t(y) \\geq t^*(y)$, and so \n", "\n", "$$t'(x) \\geq -d(x) + t^*(y)$$\n", "\n", "We have $t^*(x) \\leq -d(x) + t^*(y)$, to give enough time for task $x$ to run. \n", "This leads to $t'(x) \\geq t^*(x)$, completing the induction case. "]}, {"cell_type": "markdown", "metadata": {"id": "m_DshIlO-HHI"}, "source": ["#### Underapproximation\n", "\n", "For the proof of the under-approximation, it helps to define an _update operator_ $A$. \n", "Let $\\vec{t}$ be the vector consisting of all starting times.  Then, our rule $t(x) := -d(x) + \\min_{y \\in s(x)} t(y)$ can be written as $\\vec{t} = A(\\vec{t})$, where $A$ is an update operator operating on the vector of start times. \n", "\n", "The operator $A$ is monotonic, that is, $\\vec{t} \\leq \\vec{u}$ implies $A(\\vec{t}) \\leq A(\\vec{u})$, where the inequalities are interpreted in pointwise fashion.  This is simply because the functions $\\min$ and $+$ are monotonic.\n", "\n", "Furthermore, let $\\vec{t}_0$ be defined by $t_0(x) = -d(x)$, and let $\\vec{t}_1$ be defined by $t(x) = -d(x) + \\min{y \\in s(x)} t_0(y)$; in other words, let $\\vec{t}_0$ be the initial vector, and $\\vec{t}_1 = A(\\vec{t}_0)$ be the first iterate.  \n", "In general, let $\\vec{t}_{n+1} = A(\\vec{t}_n)$ for $n \\geq 0$.\n", "Since $\\min{y \\in s(x)} t_0(y) \\leq 0$, we have $\\vec{t}_1 \\leq \\vec{t}_0$,  and thus, $A(\\vec{t}_1) \\leq A(\\vec{t}_0)$, or $\\vec{t}_2 \\leq \\vec{t}_1$. \n", "This in turn, again by monotoninicy of $A$, leads to $\\vec{t}_3 \\leq \\vec{t}_2$, so that the sequence $\\vec{t}_0, \\vec{t}_1, \\vec{t}_2, \\ldots$, is monotonically decreasing. \n", "In particular, we have that $t_n(x) \\leq - d(x)$ for all $n \\geq 0$. \n", "\n", "If $t(x) = - d(x) + \\min_{y \\in s(x)} t(y)$ holds for all tasks $x$ at the end of the iterations, then also $t(x) + d(x) \\leq t(y)$ holds for all tasks x and their dependent tasks $y$. \n", "Thus, if we started every task $x$ at $t(x)$, we would be able to complete every task $x$ by $t(x) + d(x)$. \n", "Since $t(x) + d(x) \\leq 0$, $t(\\cdot)$ is a feasible schedule, and it must be earlier or equal to the latest feasible schedule, so that $t(x) \\leq t^*(x)$ for every task $x$."]}, {"cell_type": "markdown", "metadata": {"id": "SacXTaqvMTDF"}, "source": ["### A naive implementation\n", "\n", "A naive implementation of the algorithm is as follows."]}, {"cell_type": "code", "metadata": {"id": "imwpMFJseRYP"}, "source": ["class Task(object):\n", "    \"\"\"We represent a task, with a name, duration, and start time.\"\"\"\n", "\n", "    def __init__(self, name=None, duration=0.):\n", "        assert duration > 0, \"The task duration needs to be positive.\"\n", "        self.name = name\n", "        self.duration = duration\n", "        self.start_time = None # Not known initially.\n", "\n", "    def __repr__(self):\n", "        \"\"\"This is used by our functions before to print tasks.\"\"\"\n", "        return \"%s[%f][s=%r]\" % (self.name, self.duration, self.start_time)\n", "\n", "    def __hash__(self):\n", "        \"\"\"We need to define this, so that tasks can be used as keys\n", "        to dictionaries.\"\"\"\n", "        return hash(self.name)\n", "\n", "    def __eq__(self, other):\n", "        \"\"\"Used for comparisons.\"\"\"\n", "        return (self.name == other.name and self.duration == other.duration\n", "                and self.start_time == other.start_time)\n"], "execution_count": null, "outputs": []}, {"cell_type": "code", "metadata": {"id": "CPkbhrGNjzp_"}, "source": ["from collections import defaultdict\n", "\n", "class TimedScheduler(object):\n", "\n", "    def __init__(self):\n", "        # Once the tasks are scheduled, they will appear in this list in\n", "        # order of increasing start time.\n", "        self.tasks = set()\n", "        self.predecessors = defaultdict(set) # Not really needed.\n", "        self.successors = defaultdict(set)\n", "        self.sorted_tasks = None\n", "\n", "    def add_task(self, t, dependencies):\n", "        \"\"\"Adds a task t with given dependencies.\"\"\"\n", "        # Makes sure we know about all tasks mentioned.\n", "        self.tasks.add(t)\n", "        self.tasks.update(dependencies)\n", "        # Adds to the predecessors of t the tasks in the dependencies.\n", "        self.predecessors[t] = self.predecessors[t] | set(dependencies)\n", "        for u in dependencies:\n", "            self.successors[u].add(t)\n", "\n", "    def compute_schedule(self):\n", "        \"\"\"Computes a schedule\"\"\"\n", "        # Initialization step.\n", "        for t in self.tasks:\n", "            t.start_time = - t.duration\n", "        # Iterations.\n", "        # If the graph is acyclic, we can do at most n-1 updates, as n-1 is\n", "        # the length of the longest path.  So we try to do n updates, and\n", "        # if the n-th update still shows change, we stop with an error,\n", "        # reporting that the graph contains a cycle.\n", "        for num_iteration in range(len(self.tasks)):\n", "            changed = False\n", "            for x in self.tasks:\n", "                new_time = - x.duration + min([0.] + [y.start_time\n", "                                               for y in self.successors[x]])\n", "                changed = changed or new_time != x.start_time\n", "                x.start_time = new_time\n", "            if not changed:\n", "                break\n", "        assert not changed, \"The graph contains a cycle.\"\n", "        self.sorted_tasks = list(self.tasks)\n", "        self.sorted_tasks.sort(key = lambda t : t.start_time)\n", "\n", "    def get_schedule(self):\n", "        return self.sorted_tasks\n"], "execution_count": null, "outputs": []}, {"cell_type": "markdown", "metadata": {"id": "JmVYsRxeR6si"}, "source": ["We have now reached the apex of our intellectual achievement: we can finally know when to start the various tasks involved in making pasta carbonara.  Such effort, but such reward, also!"]}, {"cell_type": "code", "metadata": {"id": "kQUMRJI_fWio"}, "source": ["tcarbonara = TimedScheduler()\n", "\n", "# Let's define the tasks first.\n", "t_onions = Task('dice onions', 2.)\n", "t_pancetta = Task('dice pancetta', 10.)\n", "t_oilbutter = Task('put oil and butter in pan', 1.)\n", "t_pan = Task('cook pancetta', 35.)\n", "\n", "t_fill = Task('fill pot with water', 1.)\n", "t_boil = Task('bring water to a boil', 10.)\n", "t_salt = Task('add salt to water', 1.)\n", "t_pasta = Task('cook pasta', 13.)\n", "\n", "t_eggs = Task('put eggs in bown', 2.)\n", "t_beat = Task('beat eggs', 1.)\n", "\n", "t_serve = Task('serve pasta', 2.)\n", "\n", "# First, the part about cooking the pancetta.\n", "tcarbonara.add_task(t_onions, [])\n", "tcarbonara.add_task(t_pancetta, [])\n", "tcarbonara.add_task(t_oilbutter, [])\n", "tcarbonara.add_task(t_pan, [t_onions, t_pancetta, t_oilbutter])\n", "\n", "tcarbonara.add_task(t_fill, [])\n", "tcarbonara.add_task(t_boil, [t_fill])\n", "tcarbonara.add_task(t_salt, [t_boil])\n", "tcarbonara.add_task(t_pasta, [t_salt])\n", "\n", "tcarbonara.add_task(t_eggs, [])\n", "tcarbonara.add_task(t_beat, [t_eggs])\n", "\n", "tcarbonara.add_task(t_serve, [t_beat, t_pasta, t_pan])\n"], "execution_count": null, "outputs": []}, {"cell_type": "code", "metadata": {"id": "vjw5fzJfSMsX"}, "source": ["tcarbonara.compute_schedule()\n"], "execution_count": null, "outputs": []}, {"cell_type": "code", "metadata": {"id": "-TMcmvDiS5Fd"}, "source": ["for t in tcarbonara.get_schedule():\n", "    print(t.name, \":\", t.start_time)\n"], "execution_count": null, "outputs": [{"output_type": "stream", "text": ["dice pancetta : -47.0\n", "dice onions : -39.0\n", "put oil and butter in pan : -38.0\n", "cook pancetta : -37.0\n", "fill pot with water : -27.0\n", "bring water to a boil : -26.0\n", "add salt to water : -16.0\n", "cook pasta : -15.0\n", "put eggs in bown : -5.0\n", "beat eggs : -3.0\n", "serve pasta : -2.0\n"], "name": "stdout"}]}, {"cell_type": "markdown", "metadata": {"id": "KZ-adUnmTxos"}, "source": ["Let us check that this will not run forever in case of loops. "]}, {"cell_type": "code", "metadata": {"id": "5oFeJ4nWTK-W"}, "source": ["ta = Task('a', 1.)\n", "tb = Task('b', 1.)\n", "tc = Task('c', 2.)\n", "s = TimedScheduler()\n", "s.add_task(ta, [tb])\n", "s.add_task(tb, [tc])\n", "s.add_task(tc, [ta])\n", "try:\n", "    s.compute_schedule()\n", "except AssertionError:\n", "    print(\"Detected a loop\")\n"], "execution_count": null, "outputs": [{"output_type": "stream", "text": ["Detected a loop\n"], "name": "stdout"}]}, {"cell_type": "markdown", "metadata": {"id": "3rKmZB3IkXko"}, "source": ["### An efficient implementation of the algorithm\n", "\n", "Let us consider again the scheduling method of our TimedScheduler class."]}, {"cell_type": "code", "metadata": {"id": "0xG7d0VMkili"}, "source": ["def compute_schedule(self):\n", "    \"\"\"Computes a schedule\"\"\"\n", "    # Initialization step.\n", "    for t in self.tasks:\n", "        t.start_time = - t.duration\n", "    # Iterations.\n", "    # If the graph is acyclic, we can do at most n-1 updates, as n-1 is\n", "    # the length of the longest path.  So we try to do n updates, and\n", "    # if the n-th update still shows change, we stop with an error,\n", "    # reporting that the graph contains a cycle.\n", "    for num_iteration in range(len(self.tasks)):\n", "        changed = False\n", "        for x in self.tasks:\n", "            new_time = - x.duration + min([0.] + [y.start_time\n", "                                           for y in self.successors[x]])\n", "            changed = changed or new_time != x.start_time\n", "            x.start_time = new_time\n", "        if not changed:\n", "            break\n", "    assert not changed, \"The graph contains a cycle.\"\n", "    self.sorted_tasks = list(self.tasks)\n", "    self.sorted_tasks.sort(key = lambda t : t.start_time)\n"], "execution_count": null, "outputs": []}, {"cell_type": "markdown", "metadata": {"id": "r48lIowqkqKV"}, "source": ["This implementation is correct, but it does waste quite a bit of unnecessary work.  For a task $x$, we note that the start time $t(x)$ of $x$ changes only when the start time of some successor of $x$ has changed. \n", "Thus, we can obtain amore efficient algorithm by propagating change, updating the starting time of a task only when the starting time of some of its successors changed.\n", "\n", "To this end, we maintain a _changed_ set, which keeps track of the tasks whose starting times have changed. \n", "Let $L$ be the set of tasks that have no successors; these are the tasks that can be done last. \n", "Initially, we set $t(x) = -d(x)$ for $x \\in L$, and $t(x) = 0$ otherwise; \n", "we also set _changed_ to $L$. \n", "Then, we iteratively pick a task $x$ in _changed_, and for all its predecessors $y$, we set $t(y) = min\\{t(y), -d(y) + t(x)\\}$; if this update changes the value of $t(y)$, we put $y$ in _changed_. \n", "The process continues until there is no task in _changed_, so that all changes have been propagated. \n", "\n", "The algorithm can be written as follows. "]}, {"cell_type": "code", "metadata": {"id": "2gzripRxqEzG"}, "source": ["def fast_compute_schedule(self):\n", "    \"\"\"Computes a schedule for a timed scheduler.\"\"\"\n", "    # Initialization step.\n", "    for t in self.tasks:\n", "        t.start_time = - t.duration\n", "    changed = {x for x in self.tasks if len(self.successors[x]) == 0}\n", "    while len(changed) > 0:\n", "        x = changed.pop()\n", "        for y in self.predecessors[x]:\n", "            new_start_time = min(y.start_time, -y.duration + x.start_time)\n", "            if new_start_time < y.start_time:\n", "                changed.add(y)\n", "                y.start_time = new_start_time\n", "    self.sorted_tasks = list(self.tasks)\n", "    self.sorted_tasks.sort(key = lambda t : t.start_time)\n", "\n", "TimedScheduler.fast_compute_schedule = fast_compute_schedule\n"], "execution_count": null, "outputs": []}, {"cell_type": "code", "metadata": {"id": "hjbM8w6isMl5"}, "source": ["tcarbonara.fast_compute_schedule()\n", "for t in tcarbonara.get_schedule():\n", "    print(t.name, \":\", t.start_time)\n"], "execution_count": null, "outputs": [{"output_type": "stream", "text": ["dice pancetta : -47.0\n", "dice onions : -39.0\n", "put oil and butter in pan : -38.0\n", "cook pancetta : -37.0\n", "fill pot with water : -27.0\n", "bring water to a boil : -26.0\n", "add salt to water : -16.0\n", "cook pasta : -15.0\n", "put eggs in bown : -5.0\n", "beat eggs : -3.0\n", "serve pasta : -2.0\n"], "name": "stdout"}]}, {"cell_type": "markdown", "metadata": {"id": "lY8qUcFSs6PK"}, "source": ["Let us check that the two schedules computed are indeed the same. "]}, {"cell_type": "code", "metadata": {"id": "bDAWgAPws_6e"}, "source": ["tcarbonara.compute_schedule()\n", "# We need to produce a static dictionary: the schedule is formed\n", "# by tasks with a .start_time defined, and if we call the scheduler\n", "# one more time, these .start_time will be modified.\n", "d1 = {t.name: t.start_time for t in tcarbonara.get_schedule()}\n", "tcarbonara.fast_compute_schedule()\n", "d2 = {t.name: t.start_time for t in tcarbonara.get_schedule()}\n", "d1 == d2\n"], "execution_count": null, "outputs": [{"output_type": "execute_result", "data": {"text/plain": ["True"]}, "metadata": {"tags": []}, "execution_count": 15}]}, {"cell_type": "markdown", "metadata": {"id": "VXZ3N8ch4nqq"}, "source": ["Writing two implementations of the same algorithm, one simple, the other efficient, and testing them by checking that they give the same results, is a useful and common testing technique. "]}, {"cell_type": "markdown", "metadata": {"id": "UnDUNMXl4E5W"}, "source": ["**Exercise:** the fast_compute_schedule method does not check for loops.  Modify it so that it terminates with an assertion error if the dependency graph contains a loop.  There are various ways in which this can be done, but one of the simplest is as follows.  This is a rough idea; you will need to take care of some corner cases (the tests will help). \n", "\n", "If there is a loop, the algorithm will keep updating the starting times of the tasks in the loop, so that the starting times will become smaller and smaller. \n", "If $X$ is the set of all tasks, clearly the worst case for a task $x$ is that all others have to be done before it, in which case $t(x) = - \\sum_{x \\in X} d(x)$.  So if you ever assign a starting time to a task that is _smaller than_  $- \\sum_{x \\in X} d(x)$, there must be a loop.\n", "\n", "Note that this relies on the assumption that all tasks have strictly positive durations."]}, {"cell_type": "code", "metadata": {"id": "EBqEjJNVgcn3", "cellView": "form"}, "source": ["#@title Importing nose\n", "\n", "# Let us ensure that nose is installed.\n", "try:\n", "    from nose.tools import assert_equal, assert_true\n", "    from nose.tools import assert_false, assert_almost_equal\n", "except:\n", "    !pip install nose\n", "    from nose.tools import assert_equal, assert_true\n", "    from nose.tools import assert_false, assert_almost_equal\n"], "execution_count": null, "outputs": [{"output_type": "stream", "text": ["Collecting nose\n", "\u001b[?25l  Downloading https://files.pythonhosted.org/packages/15/d8/dd071918c040f50fa1cf80da16423af51ff8ce4a0f2399b7bf8de45ac3d9/nose-1.3.7-py3-none-any.whl (154kB)\n", "\r\u001b[K     |\u2588\u2588\u258f                             | 10kB 14.7MB/s eta 0:00:01\r\u001b[K     |\u2588\u2588\u2588\u2588\u258e                           | 20kB 19.3MB/s eta 0:00:01\r\u001b[K     |\u2588\u2588\u2588\u2588\u2588\u2588\u258d                         | 30kB 18.1MB/s eta 0:00:01\r\u001b[K     |\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u258c                       | 40kB 12.8MB/s eta 0:00:01\r\u001b[K     |\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u258b                     | 51kB 9.8MB/s eta 0:00:01\r\u001b[K     |\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u258a                   | 61kB 8.5MB/s eta 0:00:01\r\u001b[K     |\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2589                 | 71kB 9.4MB/s eta 0:00:01\r\u001b[K     |\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588               | 81kB 10.3MB/s eta 0:00:01\r\u001b[K     |\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588             | 92kB 9.8MB/s eta 0:00:01\r\u001b[K     |\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u258f          | 102kB 9.5MB/s eta 0:00:01\r\u001b[K     |\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u258e        | 112kB 9.5MB/s eta 0:00:01\r\u001b[K     |\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u258d      | 122kB 9.5MB/s eta 0:00:01\r\u001b[K     |\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u258c    | 133kB 9.5MB/s eta 0:00:01\r\u001b[K     |\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u258b  | 143kB 9.5MB/s eta 0:00:01\r\u001b[K     |\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u258a| 153kB 9.5MB/s eta 0:00:01\r\u001b[K     |\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588| 163kB 9.5MB/s \n", "\u001b[?25hInstalling collected packages: nose\n", "Successfully installed nose-1.3.7\n"], "name": "stdout"}]}, {"cell_type": "code", "metadata": {"id": "qRh5yGI_QB32"}, "source": ["### Definition of `fast_compute_schedule` that checks for loops\n", "\n", "class DependencyLoop(Exception):\n", "    pass\n", "\n", "def safe_fast_compute_schedule(self):\n", "    \"\"\"Computes a schedule for the TimedScheduler.  Raises DependencyLoop\n", "    if the dependency graph contains a loop.\"\"\"\n", "    ### BEGIN SOLUTION\n", "    raise NotImplementedError()\n", "    ### END SOLUTION\n", "\n", "TimedScheduler.fast_compute_schedule = safe_fast_compute_schedule\n"], "execution_count": null, "outputs": []}, {"cell_type": "markdown", "metadata": {"id": "4Kijmo7Kf-Dv"}, "source": ["As usual, let us test this."]}, {"cell_type": "code", "metadata": {"id": "44CyvXM-gAna"}, "source": ["### Tests with loop\n", "\n", "# First, a graph consisting only of a loop.\n", "ta = Task('a', 1.)\n", "tb = Task('b', 1.)\n", "tc = Task('c', 2.)\n", "s = TimedScheduler()\n", "s.add_task(ta, [tb])\n", "s.add_task(tb, [tc])\n", "s.add_task(tc, [ta])\n", "loop = False\n", "try:\n", "    s.fast_compute_schedule()\n", "except DependencyLoop:\n", "    loop = True\n", "assert_true(loop)\n", "\n"], "execution_count": null, "outputs": []}, {"cell_type": "code", "metadata": {"id": "CzQBEb6RiC4M"}, "source": ["### More tests with loop\n", "\n", "# Then, a more complex example with a loop.\n", "ta = Task('a', 1.)\n", "tb = Task('b', 1.)\n", "tc = Task('c', 2.)\n", "td = Task('d', 4.)\n", "te = Task('e', 3.)\n", "s = TimedScheduler()\n", "s.add_task(ta, [tb, td])\n", "s.add_task(tb, [tc])\n", "s.add_task(tc, [ta])\n", "s.add_task(td, [])\n", "s.add_task(te, [tb])\n", "loop = False\n", "try:\n", "    s.fast_compute_schedule()\n", "except DependencyLoop:\n", "    loop = True\n", "assert_true(loop)\n", "\n"], "execution_count": null, "outputs": []}, {"cell_type": "code", "metadata": {"id": "RC34dUiRkxAo"}, "source": ["### Tests without loop\n", "\n", "# An example without a loop.\n", "ta = Task('a', 1.)\n", "tb = Task('b', 1.)\n", "tc = Task('c', 2.)\n", "td = Task('d', 4.)\n", "te = Task('e', 3.)\n", "s = TimedScheduler()\n", "s.add_task(ta, [tb, td])\n", "s.add_task(tb, [tc])\n", "s.add_task(tc, [td])\n", "s.add_task(td, [])\n", "s.add_task(te, [tb])\n", "loop = False\n", "try:\n", "    s.fast_compute_schedule()\n", "except DependencyLoop:\n", "    loop = True\n", "assert_false(loop)\n", "\n"], "execution_count": null, "outputs": []}, {"cell_type": "markdown", "metadata": {"id": "Ya4rAU0XXKpH"}, "source": ["## Epilogue\n", "\n", "Scheduling is a complex problem, with many variants.  Consider for instance our timed scheduling problem: it models only partially how one can cook.  For instance, people generally cannot slice two things at once: if there's only one person, some tasks, such as slicing, become mutually exclusive.  One may also have limitations on how many things can be cooked at the same time.  These are known, in general, as resource constraints on a schedule.  Schedules can have other types of constraints too: particular tasks may be able to be started only after predetermined times, and so forth. \n", "For the two problems we have seen, scheduling with dependencies, and with duration constraints, efficient optimal solutions are known. \n", "For complex scheduling problems, it is often the case that such efficient solutions are not available, and one must write algorithms that search for a solution, often with the help of heuristics. "]}]}