day3/swarm/pygmo_scheduling.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "pygmo-scheduling.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "authorship_tag": "ABX9TyOazy04R1p7wQMH4Tp3UX/m",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/lisaong/diec/blob/master/day3/swarm/pygmo_scheduling.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "B4ZCk_1zGSrE",
        "colab_type": "text"
      },
      "source": [
        "# The Job Shop Problem\n",
        "\n",
        "(Credits: https://developers.google.com/optimization/scheduling/job_shop)\n",
        "\n",
        "One common scheduling problem is the job shop, in which multiple jobs are processed on several machines. Each job consists of a sequence of tasks, which must be performed in a given order, and each task must be processed on a specific machine. For example, the job could be the manufacture of a single consumer item, such as an automobile. The problem is to schedule the tasks on the machines so as to minimize the length of the schedule—the time it takes for all the jobs to be completed.\n",
        "\n",
        "There are several constraints for the job shop problem:\n",
        "\n",
        "* No task for a job can be started until the previous task for that job is completed.\n",
        "* A machine can only work on one task at a time.\n",
        "* A task, once started, must run to completion.\n",
        "\n",
        "## How this applies to Edge Computing\n",
        "Scalable Edge Computing architectures involves multiple compute nodes, where each node may specialise in different functions. For example, an airport security system where video cameras are used to track passenger movement can be envisioned as a pipeline of Edge nodes:\n",
        "- Nodes attached to the video camera doing frame extraction and buffering\n",
        "- Nodes receiving the buffered video frames to perform feature extraction\n",
        "- Nodes running ML algorithms on the extracted video features to get the predicted passenger paths\n",
        "\n",
        "Note that the term \"nodes\" here may refer to physical nodes or logical (functional) nodes within an Edge compute system. The idea is still the same - a pipeline is split into stages (tasks assigned to nodes) so that we can parallelise the pipeline (run multiple jobs at the same time).\n",
        "\n",
        "The Job Shop problem is about how to schedule tasks in parallel to minimise overall latency."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "R7njheagcBaF",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "2NTRZ5QyJyHb",
        "colab_type": "text"
      },
      "source": [
        "## Example Problem\n",
        "\n",
        "Below is a simple example of a job shop problem, in which each task is labeled by a pair of numbers (m, p) where m is the number of the machine the task must be processed on and p is the processing time of the task — the amount of time it requires. (The numbering of jobs and machines starts at 0.)\n",
        "\n",
        "* job 0 = [(0, 3), (1, 2), (2, 2)]\n",
        "* job 1 = [(0, 2), (2, 1), (1, 4)]\n",
        "* job 2 = [(1, 4), (2, 3)]\n",
        "\n",
        "In the example, job 0 has three tasks. The first, (0, 3), must be processed on machine 0 in 3 units of time. The second, (1, 2), must be processed on machine 1 in 2 units of time, and so on. Altogether, there are eight tasks.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "M9bzJMaDKPsz",
        "colab_type": "text"
      },
      "source": [
        "### A solution for the problem\n",
        "A solution to the job shop problem is an assignment of a start time for each task, which meets the constraints given above. The diagram below shows one possible solution for the problem:\n",
        "\n",
        "![schedule](https://developers.google.com/optimization/images/scheduling/schedule1.png)\n",
        "\n",
        "You can check that the tasks for each job are scheduled at non-overlapping time intervals, in the order given by the problem.\n",
        "\n",
        "The length of this solution is 12, which is the first time when all three jobs are complete.\n",
        "\n",
        "(credits: https://developers.google.com/optimization/scheduling/job_shop)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "SpII2yimKztW",
        "colab_type": "text"
      },
      "source": [
        "### Variables and constraints for the problem\n",
        "\n",
        "This section describes how to set up the variables and constraints for the problem. First, let task(i, j) denote the jth task in the sequence for job i. For example, task(0, 2) denotes the second task for job 0, which corresponds to the pair (1, 2) in the problem description.\n",
        "\n",
        "Next, define $t_{i, j}$ to be the start time for task(i, j). The $t_{i, j}$ are the variables in the job shop problem. Finding a solution involves determining values for these variables that meet the requirement of the problem.\n",
        "\n",
        "There are two types of constraints for the job shop problem:\n",
        "\n",
        "* Precedence constraints — These arise from the condition that for any two consecutive tasks in the same job, the first must be completed before the second can be started. For example, task(0, 2) and task(0, 3) are consecutive tasks for job 0. Since the processing time for task(0, 2) is 2, the start time for task(0, 3) must be at least 2 units of time after the start time for task 2. (Perhaps task 2 is painting a door, and it takes two hours for the paint to dry.) As a result, you get the following constraint:\n",
        "\n",
        "    $t_{0, 2}   + 2  ≤  t_{0, 3}$\n",
        "\n",
        "* No overlap constraints — These arise from the restriction that a machine can't work on two tasks at the same time. For example, task(0, 2) and task(2, 1) are both processed on machine 1. Since their processing times are 2 and 4, respectively, one of the following constraints must hold:\n",
        "    $t_{0, 2}   + 2  ≤  t_{2, 1}$ (if task(0, 2) is scheduled before task(2, 1))\n",
        "\n",
        "    or\n",
        "\n",
        "    $t_{2, 1}   + 4  ≤  t_{0, 2}$ (if task(2, 1) is scheduled before task(0, 2)).\n",
        "\n",
        "### Objective for the problem\n",
        "The objective of the job shop problem is to minimize the makespan: the length of time from the earliest start time of the jobs to the latest end time"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tlEpH_HRJ_KZ",
        "colab_type": "text"
      },
      "source": [
        "### PyGMO\n",
        "\n",
        "The example from Google uses Google's or-tools CP-SAT solver  (https://developers.google.com/optimization/cp/cp_solver) to solve the scheduling problem.\n",
        "\n",
        "We will see how biologically inspired Global Optimisation Algorithms can solve this problem, using the PyGMO library. PyGMO is a Python wrapper for the PaGMO (Parallel Global Multi-objective Optimizer) C++ solver. Source: https://github.com/esa/pygmo2\n",
        "\n",
        "The Jobshop scheduling problem is known as a \"constrainted single-objective optimisation problem.\" It means that:\n",
        "* There is 1 objective (to minimise, or to maximise)\n",
        "* There are constraints that limit the solution space\n",
        "\n",
        "Not all algorithms perform constrained optimisation. Most algorithms in PyGMO support unconstrained optimisation.\n",
        "\n",
        "Libraries with Similar Approaches for solving Scheduling Problems:\n",
        "* https://pypi.org/project/pyschedule/0.2.6/\n",
        "* https://github.com/mcfadd/Job_Shop_Schedule_Problem\n",
        "* https://github.com/brandhaug/jssp-swarm (in Scala)\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "CQbCKhjGNyG6",
        "colab_type": "code",
        "outputId": "7f9d8575-62bf-4190-c9d8-61513574c239",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 167
        }
      },
      "source": [
        "!pip install pygmo"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Collecting pygmo\n",
            "\u001b[?25l  Downloading https://files.pythonhosted.org/packages/d4/6a/d3b889a50899f7ff7ace64467061f1392b870aa90b2bd55d370f19a99dfa/pygmo-2.13.0-cp36-cp36m-manylinux1_x86_64.whl (10.7MB)\n",
            "\u001b[K     |████████████████████████████████| 10.7MB 460kB/s \n",
            "\u001b[?25hRequirement already satisfied: cloudpickle in /usr/local/lib/python3.6/dist-packages (from pygmo) (1.2.2)\n",
            "Requirement already satisfied: numpy in /usr/local/lib/python3.6/dist-packages (from pygmo) (1.17.5)\n",
            "Installing collected packages: pygmo\n",
            "Successfully installed pygmo-2.13.0\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "iepiDqwWXVvF",
        "colab_type": "text"
      },
      "source": [
        "### A simple user-defined problem\n",
        "\n",
        "As an introduction to how to use PyGMO, we'll first cover a simple problem of finding the values of $(x_1, x_2)$ that will minimise $y = {x_1}^2 + {x_2}^2$.\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "OBPk7it8HsRj",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "import pygmo as pg\n",
        "\n",
        "# https://esa.github.io/pygmo2/tutorials/coding_udp_simple.html\n",
        "class example_function:\n",
        "  def __init__(self, dim):\n",
        "    self.dim = dim\n",
        "\n",
        "  def fitness(self, x):\n",
        "    \"\"\"The objective function to minimise\n",
        "    \"\"\"\n",
        "    return [sum(x*x)]\n",
        "  \n",
        "  def get_bounds(self):\n",
        "    \"\"\"The bounds of the vector (the answer)\n",
        "    \"\"\"\n",
        "    return ([-1] * self.dim,[1] * self.dim)\n",
        "\n",
        "  def get_extra_info(self):\n",
        "    \"\"\"Describes extra information of the problem\n",
        "    \"\"\"\n",
        "    return f'\\tDimensions: {self.dim}'\n",
        "  \n",
        "prob = pg.problem(example_function(dim=2))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "MR4eHwuUT38G",
        "colab_type": "code",
        "outputId": "cecb00e7-8dbc-434c-eb3c-d9ed50bc7154",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 425
        }
      },
      "source": [
        "print(prob)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Problem name: <class '__main__.example_function'>\n",
            "\tGlobal dimension:\t\t\t2\n",
            "\tInteger dimension:\t\t\t0\n",
            "\tFitness dimension:\t\t\t1\n",
            "\tNumber of objectives:\t\t\t1\n",
            "\tEquality constraints dimension:\t\t0\n",
            "\tInequality constraints dimension:\t0\n",
            "\tLower bounds: [-1, -1]\n",
            "\tUpper bounds: [1, 1]\n",
            "\tHas batch fitness evaluation: false\n",
            "\n",
            "\tHas gradient: false\n",
            "\tUser implemented gradient sparsity: false\n",
            "\tHas hessians: false\n",
            "\tUser implemented hessians sparsity: false\n",
            "\n",
            "\tFitness evaluations: 0\n",
            "\n",
            "\tThread safety: none\n",
            "\n",
            "Extra info:\n",
            "\tDimensions: 2\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Fa4C4YEAT4_E",
        "colab_type": "code",
        "outputId": "ac5cb3f3-6ada-427e-b872-4f8c50cf2190",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 36
        }
      },
      "source": [
        "algo = pg.algorithm(pg.bee_colony(gen = 20, limit = 20))\n",
        "pop = pg.population(prob,10)\n",
        "pop = algo.evolve(pop)\n",
        "print(f'solution: {pop.champion_x}, fitness value: {pop.champion_f}')"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "solution: [-0.00020625  0.00028443], fitness value: [1.23436773e-07]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "97KnWCZAWTQ7",
        "colab_type": "text"
      },
      "source": [
        "### Jobshop Problem Definition\n",
        "For the jobshop scheduling problem, we have 8 tasks.\n",
        "\n",
        "As the jobs_data is static, we can express the solution as a list of start times, one start time per job.\n",
        "\n",
        "Dimensions of our problem: 8\n",
        "\n",
        "Constraints: 2\n",
        "*   Precedence\n",
        "*   No-overlap"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "51jd9MHrWf8f",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Each job is a list of multiple tasks: (machine_id, processing_time)\n",
        "jobs_data = [\n",
        "  [(0, 3), (1, 2), (2, 2)],  # Job0\n",
        "  [(0, 2), (2, 1), (1, 4)],  # Job1\n",
        "  [(1, 4), (2, 3)]  # Job2\n",
        "]\n",
        "\n",
        "machines_count = 1 + max(task[0] for job in jobs_data for task in job)\n",
        "all_machines = range(machines_count)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "wc_NfmC7dvWt",
        "colab_type": "code",
        "outputId": "a6e4d03a-3ee1-4615-bee6-8a78b80e9896",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 166
        }
      },
      "source": [
        "# Flatten the jobs data by index by encoding the job_id into the tuple\n",
        "\n",
        "# the *task syntax will unpack a tuple\n",
        "jobs_list = [(i, *task) for i in range(len(jobs_data)) for task in jobs_data[i]]\n",
        "\n",
        "jobs_list # (job_id, machine_id, processing_time)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[(0, 0, 3),\n",
              " (0, 1, 2),\n",
              " (0, 2, 2),\n",
              " (1, 0, 2),\n",
              " (1, 2, 1),\n",
              " (1, 1, 4),\n",
              " (2, 1, 4),\n",
              " (2, 2, 3)]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 7
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "S9ByZLNSecAb",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# now we can define our problem\n",
        "import numpy as np\n",
        "\n",
        "# constants for accessing the tuples\n",
        "JOB = 0\n",
        "MACHINE = 1\n",
        "DURATION = 2\n",
        "\n",
        "class jobshop_function:\n",
        "  def __init__(self, jobs, max_schedule_time=20):\n",
        "    \"\"\" jobs: list of jobs (job_id, machine_id, duration)\n",
        "        max_schedule_time: maximum time allowed for the schedule\n",
        "    \"\"\"\n",
        "    self.jobs = jobs_list\n",
        "    self.dim = len(jobs_list)\n",
        "    self.t_max = max_schedule_time\n",
        "    self.t_min = 0\n",
        "\n",
        "    self.job_start_indices = []\n",
        "    for i in range(1, self.dim):\n",
        "      if self.jobs[i-1][JOB] != self.jobs[i][JOB]:\n",
        "        self.job_start_indices.append(i)    \n",
        "    self.machines_count = 1 + max(job[MACHINE] for job in jobs)\n",
        "\n",
        "  def fitness(self, x):\n",
        "    \"\"\"The fitness: the objective to minimize and any constraints\n",
        "    x: contains the start times\n",
        "    \"\"\"\n",
        "    # Compute the objective:\n",
        "    # the length of time from the earliest start time of the jobs to the\n",
        "    # latest end time\n",
        "    start_times = x # code readability\n",
        "    end_times = [job[DURATION]+s for job, s in zip(self.jobs, start_times)]\n",
        "    objective = max(end_times) - min(start_times)\n",
        "    assert(objective > 0)\n",
        "\n",
        "    # Compute the constraints:\n",
        "    # 1) Precedence: for any two consecutive tasks in the same job, the first must \n",
        "    # be completed before the second can be started\n",
        "    #\n",
        "    # Say we have 3 tasks with their start and end times:\n",
        "    #   (s1, e1), (s2, e2), (s3, e3)\n",
        "    # Check that:\n",
        "    #   s1 >= 0, s2 >= e1, s3 >= e2\n",
        "    # If any of these are FALSE, the constraint is not met\n",
        "\n",
        "    # Compute the prev task's end times, initializing end times to\n",
        "    # -1 for the first task of each job\n",
        "    # (-1 is used instead of 0 to allow for start times at 0)\n",
        "    prev_end_times = np.array([-1] + end_times[:-1])\n",
        "    prev_end_times[self.job_start_indices] = -1\n",
        "\n",
        "    # Count how many times the constraint is not met\n",
        "    # (i.e. when prev task's end time exceeds next task's start time\n",
        "    violate_precedence = float(sum((prev_end_times - start_times) > 0))\n",
        "    \n",
        "    # 2) No overlap: a machine can't work on two tasks at the same time.\n",
        "    # Say we have 2 tasks on the same machine with their start and end times,\n",
        "    # where the start times are sorted\n",
        "    #   (s1, e1), (s2, e2)\n",
        "    # Check that e1 <= s2. We can do this by sorting first by start times,\n",
        "    # then flattening the tuples out to make sure that the values are sorted\n",
        "    #\n",
        "    # Extract tasks assigned to each machine, their start and end times\n",
        "    tasks_by_machines = {machine:[] for machine in range(self.machines_count)}\n",
        "    for i in range(self.dim):\n",
        "      tasks_by_machines[self.jobs[i][MACHINE]].append(\n",
        "          (start_times[i], end_times[i]))\n",
        "\n",
        "    # sort by start time, then compute whether overlap happens\n",
        "    # none of the numbers should overlap\n",
        "    overlap = 0.\n",
        "    for machine in tasks_by_machines.keys():\n",
        "      tasks_by_machines[machine].sort(key=lambda t:t[0]) # inplace sort\n",
        "      flattened = np.array([t for ts in tasks_by_machines[machine] for t in ts])\n",
        "      # overlap means previous value exceeds the next value\n",
        "      overlap += float(sum(flattened[:-1] > flattened[1:]))\n",
        "\n",
        "    # subtract the earliest start time to get the makespan\n",
        "    return [objective, violate_precedence, overlap]\n",
        "\n",
        "  def get_bounds(self):\n",
        "    \"\"\"The bounds of the vector\n",
        "    \"\"\"\n",
        "    return ([self.t_min] * self.dim,[self.t_max] * self.dim)\n",
        "\n",
        "  def get_nix(self):\n",
        "    \"\"\"Returns the number of integer dimensions\"\"\"\n",
        "    return self.dim\n",
        "\n",
        "  def get_nec(self):\n",
        "    \"\"\"The number of equality constraints:\n",
        "    1 no-overlap constraint\n",
        "    1 precedence constraint\n",
        "    \"\"\"\n",
        "    return 2\n",
        "\n",
        "  def get_extra_info(self):\n",
        "    return f'\\tDimensions: {self.dim} \\\n",
        "      \\n\\tJobs: {self.jobs} \\\n",
        "      \\n\\tSchedule Limit: {self.t_max}'\n",
        "  \n",
        "jobshop_prob = pg.problem(jobshop_function(jobs=jobs_list))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "jVdGPTxvg9wB",
        "colab_type": "code",
        "outputId": "a3284c4d-202a-42f3-b6ba-086a7208cb84",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 481
        }
      },
      "source": [
        "print(jobshop_prob)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Problem name: <class '__main__.jobshop_function'>\n",
            "\tGlobal dimension:\t\t\t8\n",
            "\tInteger dimension:\t\t\t8\n",
            "\tFitness dimension:\t\t\t3\n",
            "\tNumber of objectives:\t\t\t1\n",
            "\tEquality constraints dimension:\t\t2\n",
            "\tInequality constraints dimension:\t0\n",
            "\tTolerances on constraints: [0, 0]\n",
            "\tLower bounds: [0, 0, 0, 0, 0, ... ]\n",
            "\tUpper bounds: [20, 20, 20, 20, 20, ... ]\n",
            "\tHas batch fitness evaluation: false\n",
            "\n",
            "\tHas gradient: false\n",
            "\tUser implemented gradient sparsity: false\n",
            "\tHas hessians: false\n",
            "\tUser implemented hessians sparsity: false\n",
            "\n",
            "\tFitness evaluations: 0\n",
            "\n",
            "\tThread safety: none\n",
            "\n",
            "Extra info:\n",
            "\tDimensions: 8       \n",
            "\tJobs: [(0, 0, 3), (0, 1, 2), (0, 2, 2), (1, 0, 2), (1, 2, 1), (1, 1, 4), (2, 1, 4), (2, 2, 3)]       \n",
            "\tSchedule Limit: 20\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "SX1aU32RkBA-",
        "colab_type": "code",
        "outputId": "a9137bd6-00f3-4158-a690-6903272167f8",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 36
        }
      },
      "source": [
        "# Unit testing\n",
        "jobshop_prob.fitness([1, 2, 3, 4, 5, 6, 7, 8])"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([10.,  4.,  1.])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 10
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "54WIHYwkV2aB",
        "colab_type": "text"
      },
      "source": [
        "## Run the Optimiser\n",
        "\n",
        "List of algorithms are here:\n",
        "https://esa.github.io/pygmo2/overview.html#list-of-algorithms\n",
        "\n",
        "GACO runs the Extended Ant Colony Optimization algorithm, which supports constrained optimisation:\n",
        "https://esa.github.io/pygmo2/algorithms.html#pygmo.gaco\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "b8ntF4EHF6fT",
        "colab_type": "code",
        "outputId": "3496ade1-b0bb-40d2-9ae9-dc737b939a9c",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 36
        }
      },
      "source": [
        "# Optimise\n",
        "population_size = 1000\n",
        "iterations = 100\n",
        "\n",
        "prob = pg.problem(jobshop_function(jobs=jobs_list, max_schedule_time=12))\n",
        "pop = pg.population(prob, size=population_size, seed=123)\n",
        "algo = pg.algorithm(pg.gaco(gen=iterations, ker=population_size, seed=123))\n",
        "algo.set_verbosity(1000)\n",
        "pop = algo.evolve(pop)\n",
        "\n",
        "print(f'solution: {pop.champion_x}, fitness value: {pop.champion_f}')"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "solution: [ 3.  6. 11.  1.  6.  9.  2.  7.], fitness value: [12.  0.  0.]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Pi29FXK_XVCc",
        "colab_type": "text"
      },
      "source": [
        "Original Problem:\n",
        "```\n",
        "(machine_id, duration)\n",
        "jobs_data = [\n",
        "  [(0, 3), (1, 2), (2, 2)],  # Job0\n",
        "  [(0, 2), (2, 1), (1, 4)],  # Job1\n",
        "  [(1, 4), (2, 3)]  # Job2\n",
        "]\n",
        "```\n",
        "\n",
        "Schedule:\n",
        "```\n",
        "start_times = [\n",
        "  [3, 6, 11], # Job0\n",
        "  [1, 6, 9], # Job1\n",
        "  [2, 7], # Job2\n",
        "]\n",
        "```\n",
        "\n",
        "Machine 0: \n",
        "* Job1 Task 0 at t=1-2\n",
        "* Job0 Task 0 at t=3-6\n",
        "\n",
        "Machine 1:\n",
        "* Job2 Task 0 at t=2-6\n",
        "* Job0 Task 1 at t=6-8\n",
        "* Job1 Task 2 at t=9-13\n",
        "\n",
        "Machine 2:\n",
        "* Job1 Task 1 at t=6-7\n",
        "* Job2 Task 1 at t=7-10\n",
        "* Job0 Task 2 at t=11-13\n",
        "\n",
        "The overall scheduled time is 12, which is similar to the example by Google's OR tools. The constraint logic can be fine-tuned further as it is authored by hand."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vuU2miVxcLIa",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    }
  ]
}