docs/notebooks/13-scheduling.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "6nOTljC_mTMn",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Scheduling\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "t8dCcpf7mivV",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Setup\n",
    "\n",
    "We start by downloading the unified planning library."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-07-07T08:26:03.277967428Z",
     "start_time": "2023-07-07T08:26:01.671820250Z"
    },
    "id": "BoqALxJWdfl8",
    "scrolled": true,
    "tags": [
     "remove_from_CI"
    ]
   },
   "outputs": [],
   "source": [
    "%pip install unified-planning[aries]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## A *scheduling* primer\n",
    "\n",
    "`unified-planning` provides support for modeling *scheduling problems*. It heavily relies on all the building blocks of planning problems and in particular:\n",
    "\n",
    " - reuse state definition (`Type`, `Fluent`, initial state, (timed) goals, ...)\n",
    " - replace `Action` with `Activity`\n",
    " - add syntactic sugar for common patterns in scheduling problems (resources, ...)\n",
    " \n",
    " \n",
    " \n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "problem name = factory\n",
       "\n",
       "fluents = [\n",
       "]\n",
       "\n",
       "initial fluents default = [\n",
       "]\n",
       "\n",
       "initial values = [\n",
       "]\n",
       "\n",
       "\n",
       "BASE: {\n",
       "  }\n",
       "\n",
       "Activities:\n",
       "  "
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from unified_planning.shortcuts import *\n",
    "from unified_planning.model.scheduling import SchedulingProblem\n",
    "\n",
    "# Create an empty problem called factory\n",
    "problem = SchedulingProblem(\"factory\")\n",
    "problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Resources as numeric fluents\n",
    "\n",
    "A `SchedulingProblem` allows boolean, symbolic and numeric fluents to state representation, just like a regular planning problem.\n",
    "\n",
    "In addition, it exposes an [`add_resource`](https://unified-planning.readthedocs.io/en/latest/api/model/scheduling/SchedulingProblem.html#unified_planning.model.scheduling.SchedulingProblem.add_resource) method that eases the definition of reusable resources:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "problem name = factory\n",
      "\n",
      "fluents = [\n",
      "  integer[0, 1] machine1\n",
      "  integer[0, 1] machine2\n",
      "  integer[0, 4] operators\n",
      "]\n",
      "\n",
      "initial fluents default = [\n",
      "  integer[0, 1] machine1 := 1\n",
      "  integer[0, 1] machine2 := 1\n",
      "  integer[0, 4] operators := 4\n",
      "]\n",
      "\n",
      "initial values = [\n",
      "]\n",
      "\n",
      "\n",
      "BASE: {\n",
      "  }\n",
      "\n",
      "Activities:\n",
      "  \n"
     ]
    }
   ],
   "source": [
    "# Create two unary resources, one for each machine\n",
    "machine1 = problem.add_resource(\"machine1\", capacity=1)\n",
    "machine2 = problem.add_resource(\"machine2\", capacity=1)\n",
    "# Create a resource with capacity 4 representing the available operators\n",
    "operators = problem.add_resource(\"operators\", capacity=4)\n",
    "\n",
    "print(problem)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Activities\n",
    "\n",
    "An [`Activity`](https://unified-planning.readthedocs.io/en/latest/api/model/scheduling/Activity.html) is essentially a **durative action** that appears **exactly once** in the solution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a1 {\n",
      "    duration = [3, 3]\n",
      "    effects = [\n",
      "      start(a1):\n",
      "        machine1 -= 1:\n",
      "      end(a1):\n",
      "        machine1 += 1:\n",
      "    ]\n",
      "  }\n"
     ]
    }
   ],
   "source": [
    "# Create an activity a1 that has a duration of 3 time units that uses the machine 1\n",
    "a1 = problem.add_activity(\"a1\", duration=3)\n",
    "a1.uses(machine1, amount=1)\n",
    "\n",
    "print(a1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a1 {\n",
      "    duration = [3, 3]\n",
      "    effects = [\n",
      "      start(a1):\n",
      "        machine1 -= 1:\n",
      "        operators -= 2:\n",
      "      end(a1):\n",
      "        machine1 += 1:\n",
      "        operators += 2:\n",
      "    ]\n",
      "  }\n"
     ]
    }
   ],
   "source": [
    "# Specify that activity a1 requires 2 operators to be executed\n",
    "a1.uses(operators, amount=2)\n",
    "print(a1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "a2 {\n",
       "    duration = [6, 6]\n",
       "    constraints = [\n",
       "      (end(a2) <= 14)\n",
       "    ]\n",
       "    effects = [\n",
       "      start(a2):\n",
       "        operators -= 1:\n",
       "        machine2 -= 1:\n",
       "      end(a2):\n",
       "        operators += 1:\n",
       "        machine2 += 1:\n",
       "    ]\n",
       "  }"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Create a new activity a2 that lasts 6 time units and require machine2 and 1 operator\n",
    "a2 = problem.add_activity(\"a2\", duration=6)\n",
    "a2.uses(operators)  # default usage is 1\n",
    "a2.uses(machine2)\n",
    "\n",
    "# Require that activity be finished by time unit 14\n",
    "a2.add_deadline(14)\n",
    "a2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "problem name = factory\n",
       "\n",
       "fluents = [\n",
       "  integer[0, 1] machine1\n",
       "  integer[0, 1] machine2\n",
       "  integer[0, 4] operators\n",
       "]\n",
       "\n",
       "initial fluents default = [\n",
       "  integer[0, 1] machine1 := 1\n",
       "  integer[0, 1] machine2 := 1\n",
       "  integer[0, 4] operators := 4\n",
       "]\n",
       "\n",
       "initial values = [\n",
       "  machine1 := 1\n",
       "  machine2 := 1\n",
       "  operators := 4\n",
       "]\n",
       "\n",
       "quality metrics = [\n",
       "  minimize makespan\n",
       "]\n",
       "\n",
       "BASE: {\n",
       "    constraints = [\n",
       "      (end(a2) < start(a1))\n",
       "    ]\n",
       "    effects = [\n",
       "      start + 17:\n",
       "        operators -= 1:\n",
       "        operators -= 1:\n",
       "      start + 25:\n",
       "        operators += 1:\n",
       "        operators += 1:\n",
       "    ]\n",
       "  }\n",
       "\n",
       "Activities:\n",
       "  a1 {\n",
       "    duration = [3, 3]\n",
       "    effects = [\n",
       "      start(a1):\n",
       "        machine1 -= 1:\n",
       "        operators -= 2:\n",
       "      end(a1):\n",
       "        machine1 += 1:\n",
       "        operators += 2:\n",
       "    ]\n",
       "  }\n",
       "  a2 {\n",
       "    duration = [6, 6]\n",
       "    constraints = [\n",
       "      (end(a2) <= 14)\n",
       "    ]\n",
       "    effects = [\n",
       "      start(a2):\n",
       "        operators -= 1:\n",
       "        machine2 -= 1:\n",
       "      end(a2):\n",
       "        operators += 1:\n",
       "        machine2 += 1:\n",
       "    ]\n",
       "  }\n",
       "  "
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# finish a2 strictly before starting a1\n",
    "problem.add_constraint(LT(a2.end, a1.start))\n",
    "\n",
    "# One worker is unavailable over [17, 25)\n",
    "problem.add_decrease_effect(17, operators, 1)\n",
    "problem.add_increase_effect(25, operators, 1)\n",
    "problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As a last step, lets just specify that we want the makespan to be minimized."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "problem.add_quality_metric(MinimizeMakespan())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Solving scheduling problems\n",
    "\n",
    "Like all problems in the UP, we can access the `kind` field that is automatically computed to reflect the features in the problem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "PROBLEM_CLASS: ['SCHEDULING']\n",
      "PROBLEM_TYPE: ['SIMPLE_NUMERIC_PLANNING']\n",
      "TIME: ['TIMED_EFFECTS', 'DISCRETE_TIME']\n",
      "EXPRESSION_DURATION: ['INT_TYPE_DURATIONS']\n",
      "NUMBERS: ['BOUNDED_TYPES']\n",
      "EFFECTS_KIND: ['DECREASE_EFFECTS', 'INCREASE_EFFECTS']\n",
      "FLUENTS_TYPE: ['INT_FLUENTS']\n",
      "QUALITY_METRICS: ['MAKESPAN']\n"
     ]
    }
   ],
   "source": [
    "print(problem.kind)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    " Currently, the only solver supporting scheduling problems is [aries](https://github.com/plaans/aries/tree/master/planning/unified/plugin).\n",
    " When asking for a oneshot solver, it would automatically be selected to solve the problem.\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "status: SOLVED_OPTIMALLY\n",
      "engine: aries\n",
      "plan: Schedule:\n",
      "    [0, 6] a2\n",
      "    [7, 10] a1\n",
      "\n"
     ]
    }
   ],
   "source": [
    "with OneshotPlanner(problem_kind=problem.kind) as planner:\n",
    "    res = planner.solve(problem)\n",
    "    print(res)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can see, all activities are present in the solution, with `a2` finishing strictly before starting `a1` as imposed in the problem's constraints."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Going Further\n",
    "\n",
    "Reference: [Complete parser for jobshop (with operators) problems](https://github.com/aiplan4eu/unified-planning/blob/master/unified_planning/test/examples/scheduling/jobshop.py)"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "colab": {
   "collapsed_sections": [],
   "name": "UP Hierarchical Planning",
   "provenance": []
  },
  "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.12"
  },
  "vscode": {
   "interpreter": {
    "hash": "e7370f93d1d0cde622a1f8e1c04877d8463912d04d973331ad4851f04de6915a"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}