tutorial-ja/310_jobsequencing_ja.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "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.6.5"
    },
    "colab": {
      "name": "034_job_sequencing_with_integer_lengths",
      "provenance": []
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "4hlG7J_hkj6N",
        "colab_type": "text"
      },
      "source": [
        "# Job Sequencing with Integer Lengths問題\n",
        "各々サイズ$(L_i)$の決まったジョブが$N$個あり、それを$m$個のマシンに割り当てるときに、マシン$\\alpha$に割り当てられたジョブのサイズの合計$\\displaystyle M_\\alpha = \\sum_{i \\in alpha} L_i$の最大値$max(M_\\alpha)$が最小になるような割り当て方を求める問題をJob Sequencing with Integer Lengths問題といいます($L_i$は正整数とします)。0番目のマシンのジョブサイズが最大になるとして一般性を失わないので、以下では$max(M_\\alpha) = M_0$とします。また、その最大値をとる$M_0$と他の$M_\\alpha$との差$M_0 - M_\\alpha$を$n$とします。"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "hSBPwjZ-kj6O",
        "colab_type": "text"
      },
      "source": [
        "# ハミルトニアン\n",
        "次の論文を参考にすると、ハミルトニアンは以下のようになります。  \n",
        "https://arxiv.org/abs/1302.5843  \n",
        "$\\displaystyle H = H_A + H_B$  \n",
        "$\\displaystyle H_A = A \\sum_{i=1}^N \\left( 1 - \\sum_\\alpha x_{i,\\alpha} \\right)^2 + A\\sum_{\\alpha=1}^m \\left( \\sum_{n=1}^M ny_{n,\\alpha} + \\sum_i L_i \\left( x_{i,\\alpha} - x_{i,1}\\right) \\right)^2$  \n",
        "$\\displaystyle H_B = B \\sum_i L_ix_i$  \n",
        "$x_{i, \\alpha}$は求めたい解そのものです。各ジョブ$i$がマシン$\\alpha$に割り当てられるときこの値は1を取ります。$H_A$の第一項は$x_{i, \\alpha}$が各$i$についてひとつの$\\alpha$で1となることを保証する項です。$y_{n, \\alpha}$は補助変数です。各マシン$\\alpha$について、$M_0 - M_\\alpha = n$となるときこの値は1を取ります。$H_A$の第二項は各マシン$\\alpha$について割り当てられたジョブのサイズを$x_{i, \\alpha}$と$y_{n, \\alpha}$で表現したときにそれらが等しくなることを保証する項となります。  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "UuL76HRAkj6P",
        "colab_type": "text"
      },
      "source": [
        "# ハミルトニアンを少し工夫してみる\n",
        "上記のハミルトニアンのままで実装を行いましたが、良い解が得られないため、以下の通り改変を行ってみました。  \n",
        "①$H_A$の各項はスケールが違うので係数を$A_1,A_2$に分解し、それぞれ設定できるようにしました。  \n",
        "②$y_{n,\\alpha}$は各$\\alpha$についてひとつの$n$で1を取ると考えて$H_A$に$\\displaystyle A_1\\sum_{\\alpha}\\left( 1 - \\sum_n y_{n,\\alpha} \\right)^2$の項を加えました。  \n",
        "特に、①の変更を入れたことで解が安定しました。これらの変更を加えた$H_A$を以下のように変形しておきます。"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "skQZyskckj6Q",
        "colab_type": "text"
      },
      "source": [
        "$\\displaystyle H_A = A_1\\sum_i \\left( 1 - \\sum_\\alpha x_{i,\\alpha} \\right)^2 + A_1\\sum_{\\alpha}\\left( 1 - \\sum_n y_{n,\\alpha} \\right)^2 + A_2\\sum_\\alpha \\left( \\sum_n ny_{n,\\alpha} + \\sum_i L_i \\left( x_{i,\\alpha} - x_{i,1}\\right) \\right)^2$  \n",
        "$\\displaystyle = A_1\\sum_i \\left( -2 \\sum_\\alpha x_{i,\\alpha} + \\left( \\sum_\\alpha x_{i,\\alpha} \\right)^2 \\right) + A_1\\sum_\\alpha \\left( -2 \\sum_n y_{n,\\alpha} + \\left( \\sum_n y_{n,\\alpha} \\right)^2 \\right)$  \n",
        "$\\displaystyle + A_2\\sum_\\alpha \\left( \\left( \\sum_n ny_{n,\\alpha} \\right)^2 + 2\\left( \\sum_n ny_{n,\\alpha} \\right)\\left(\\sum_i L_i \\left( x_{i,\\alpha} - x_{i,1}\\right)\\right) +\\left(\\sum_i L_i \\left( x_{i,\\alpha} - x_{i,1}\\right)\\right)^2 \\right) + Const.$\n",
        "$\\displaystyle = A_1\\sum_i \\sum_\\alpha \\left( -x_{i,\\alpha}^2 + \\sum_{\\beta \\left( \\gt \\alpha \\right)} 2x_{i,\\alpha}x_{i, \\beta} \\right) + A_1\\sum_\\alpha \\sum_n \\left( -y_{n,\\alpha}^2 + \\sum_{m \\left( \\gt n \\right) } 2y_{n,\\alpha}y_{m, \\alpha} \\right)　+ A_2\\sum_\\alpha \\sum_n \\left( n^2y_{n, \\alpha}^2 + \\sum_{m \\left( \\gt n \\right) } 2nmy_{n,\\alpha}y_{m, \\alpha} \\right) $  \n",
        "$\\displaystyle + A_2\\sum_\\alpha \\sum_i \\left( \\left( \\sum_n 2nL_i y_{n,\\alpha} \\left( x_{i,\\alpha} - x_{i,1}\\right) \\right) + L_i^2 \\left( x_{i,\\alpha} - x_{i,1}\\right)^2 + \\sum_{j \\left( \\gt i \\right) } 2L_iL_j \\left( x_{i,\\alpha} - x_{i,1}\\right) \\left( x_{j,\\alpha} - x_{j,1}\\right) \\right) + Const.$  \n",
        "$\\displaystyle =\\sum_\\alpha \\sum_i \\left( - A_1x_{i,\\alpha}^2 +  A_2L_i^2 \\left( x_{i,\\alpha} - x_{i,1}\\right)^2 + \\sum_{\\beta \\left( \\gt \\alpha \\right) }  2A_1x_{i,\\alpha}x_{i, \\beta} + \\sum_{j \\left( \\gt i \\right) } 2A_2L_iL_j \\left( x_{i,\\alpha} - x_{i,1}\\right) \\left( x_{j,\\alpha} - x_{j,1}\\right)+ \\sum_n 2A_2nL_i y_{n,\\alpha} \\left( x_{i,\\alpha} - x_{i,1}\\right) \\right)$  \n",
        "$\\displaystyle + \\sum_\\alpha \\sum_n \\left( \\left( -A_1 + A_2n^2 \\right) y_{n, \\alpha}^2 + \\sum_{m \\left( \\gt n \\right) } 2\\left(A_1+ A_2nm \\right) y_{n,\\alpha}y_{m, \\alpha} \\right) + Const.$  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GNlmR69wkj6R",
        "colab_type": "text"
      },
      "source": [
        "# QUBOを計算して問題を解く\n",
        "QUBO行列を計算するクラスを作成します。"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "WJV08yw0lcRA",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 136
        },
        "outputId": "33943259-62fb-4198-825e-723d252f565d"
      },
      "source": [
        "!pip install blueqat"
      ],
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Collecting blueqat\n",
            "\u001b[?25l  Downloading https://files.pythonhosted.org/packages/bb/86/1b72a7cbe500b861d63e84cc6383fbf3730f08ae69fcd85146ae8e3b8873/blueqat-0.3.10-py3-none-any.whl (46kB)\n",
            "\r\u001b[K     |███████                         | 10kB 19.3MB/s eta 0:00:01\r\u001b[K     |██████████████                  | 20kB 1.7MB/s eta 0:00:01\r\u001b[K     |█████████████████████▏          | 30kB 2.6MB/s eta 0:00:01\r\u001b[K     |████████████████████████████▏   | 40kB 1.7MB/s eta 0:00:01\r\u001b[K     |████████████████████████████████| 51kB 1.6MB/s \n",
            "\u001b[?25hRequirement already satisfied: scipy>=1.1.0 in /usr/local/lib/python3.6/dist-packages (from blueqat) (1.3.3)\n",
            "Requirement already satisfied: numpy~=1.12 in /usr/local/lib/python3.6/dist-packages (from blueqat) (1.17.4)\n",
            "Installing collected packages: blueqat\n",
            "Successfully installed blueqat-0.3.10\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "fQ757CPUkj6S",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "import blueqat.opt as wq\n",
        "import numpy as np\n",
        "\n",
        "class Qubo():\n",
        "    def __init__(self, jobs, n_machine, max_delta, A1, A2, B):\n",
        "        self.__jobs = jobs\n",
        "        self.__n_jobs = len(jobs)\n",
        "        self.__n_machine = n_machine\n",
        "        self.__max_delta = max_delta\n",
        "        self.__A1 = A1\n",
        "        self.__A2 = A2\n",
        "        self.__B = B\n",
        "        self.__index_offset = self.__n_jobs * self.__n_machine\n",
        "\n",
        "    def __calc_sum_alpha_n_m(self, qubo, alpha, n):\n",
        "        A1 = self.__A1\n",
        "        A2 = self.__A2\n",
        "        for m in range(n + 1, self.__max_delta + 1):\n",
        "            v_n_alpha = self.__index_offset + alpha * self.__max_delta + n - 1\n",
        "            v_m_alpha = self.__index_offset + alpha * self.__max_delta + m - 1\n",
        "            qubo[v_n_alpha][v_m_alpha] += 2 * (A2 * n * m + A1)\n",
        "\n",
        "    def __calc_sum_alpha_n(self, qubo, alpha):\n",
        "        A1 = self.__A1\n",
        "        A2 = self.__A2\n",
        "        for n in range(1, self.__max_delta + 1):\n",
        "            v_n_alpha = self.__index_offset + alpha * self.__max_delta + n - 1\n",
        "            qubo[v_n_alpha][v_n_alpha] += (A2 * n ** 2 - A1)\n",
        "            \n",
        "            self.__calc_sum_alpha_n_m(qubo, alpha, n)\n",
        "\n",
        "    def __calc_sum_alpha_i_beta(self, qubo, alpha, i):\n",
        "        A1 = self.__A1\n",
        "        for beta in range(alpha + 1, self.__n_machine):\n",
        "            u_i_alpha = i * self.__n_machine + alpha\n",
        "            u_i_beta = i * self.__n_machine + beta\n",
        "            qubo[u_i_alpha][u_i_beta] += 2 * A1\n",
        "\n",
        "    def __calc_sum_alpha_i_j(self, qubo, alpha, i):\n",
        "        A2 = self.__A2\n",
        "        Li = self.__jobs[i]\n",
        "        for j in range(i + 1, self.__n_jobs):\n",
        "            Lj = self.__jobs[j]\n",
        "            u_i_alpha = i * self.__n_machine + alpha\n",
        "            u_j_alpha = j * self.__n_machine + alpha\n",
        "            u_i_0 = i * self.__n_machine \n",
        "            u_j_0 = j * self.__n_machine\n",
        "            qubo[u_i_alpha][u_j_alpha] += 2 * A2 * Li * Lj\n",
        "            qubo[u_i_alpha][u_j_0] += -2 * A2 * Li * Lj\n",
        "            qubo[u_i_0][u_j_alpha] += -2 * A2 * Li * Lj\n",
        "            qubo[u_i_0][u_j_0] += 2 * A2 * Li * Lj\n",
        "\n",
        "    def __calc_sum_alpha_i_n(self, qubo, alpha, i):\n",
        "        A2 = self.__A2\n",
        "        Li = self.__jobs[i]\n",
        "        u_i_alpha = i * self.__n_machine + alpha\n",
        "        u_i_0 = i * self.__n_machine\n",
        "        for n in range(1, self.__max_delta + 1):\n",
        "            v_n_alpha = self.__index_offset + alpha * self.__max_delta + n - 1\n",
        "            qubo[u_i_alpha][v_n_alpha] += 2 * A2 * n * Li\n",
        "            qubo[u_i_0][v_n_alpha] += -2 * A2 * n * Li\n",
        "\n",
        "    def __calc_sum_alpha_i(self,qubo, alpha):\n",
        "        A1 = self.__A1\n",
        "        A2 = self.__A2\n",
        "        for i in range(self.__n_jobs):\n",
        "            u_i_alpha = i * self.__n_machine + alpha\n",
        "            u_i_0 = i * self.__n_machine\n",
        "            Li = self.__jobs[i]\n",
        "            qubo[u_i_alpha][u_i_alpha] += -A1 + A2 * Li ** 2\n",
        "            qubo[u_i_0][u_i_0] += A2 * Li ** 2\n",
        "            qubo[u_i_0][u_i_alpha] += -2 * A2 * Li ** 2\n",
        "\n",
        "            self.__calc_sum_alpha_i_beta(qubo, alpha, i)\n",
        "            self.__calc_sum_alpha_i_j(qubo, alpha, i)\n",
        "            self.__calc_sum_alpha_i_n(qubo, alpha, i)\n",
        "\n",
        "    def __calc_constraint_func(self,qubo):\n",
        "        for alpha in range(self.__n_machine):\n",
        "            self.__calc_sum_alpha_i(qubo, alpha)\n",
        "            self.__calc_sum_alpha_n(qubo, alpha)\n",
        "\n",
        "    def __calc_objective_func(self,qubo):\n",
        "        B = self.__B\n",
        "        for i in range(self.__n_jobs):\n",
        "            u_i_0 = i * self.__n_machine\n",
        "            Li = self.__jobs[i]\n",
        "            qubo[u_i_0][u_i_0] += B * Li\n",
        "\n",
        "    def __calc_qubo(self, qubo):\n",
        "        self.__calc_constraint_func(qubo)\n",
        "        self.__calc_objective_func(qubo)\n",
        "\n",
        "    def get_qubo(self):\n",
        "        size = self.__n_machine * (self.__n_jobs + self.__max_delta)\n",
        "        qubo = np.zeros((size, size))\n",
        "        self.__calc_qubo(qubo)\n",
        "        return qubo\n",
        "\n",
        "    def show_answer(self, solution):\n",
        "        print(f\"Solution is {solution}\")\n",
        "        assigned_job_sizes = np.zeros(self.__n_machine, dtype=int)\n",
        "        for i in range(self.__n_jobs):\n",
        "            assigned = False\n",
        "            for alpha in range(self.__n_machine):\n",
        "                u_i_alpha = i * n_machine + alpha\n",
        "                if(solution[u_i_alpha] > 0):\n",
        "                    print(f\"Job{i} has been assigned to the machine{alpha}.\")\n",
        "                    assigned_job_sizes[alpha] += self.__jobs[i]\n",
        "                    assigned = True\n",
        "            if assigned == False:\n",
        "                    print(f\"Job{i} has not been assigned.\")\n",
        "        for alpha in range(self.__n_machine):\n",
        "            print(f\"Total size of jobs assigned to machine{alpha} is {assigned_job_sizes[alpha]}.\")\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Ho6diI3ckj6X",
        "colab_type": "text"
      },
      "source": [
        "問題を設定し、解きます。$A1, A2, B$のバランスは、それぞれの係数がかかっている項全体のスケールのバランスを考慮して決定しています。"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "nTJKjzjJkj6Y",
        "colab_type": "code",
        "outputId": "2244f78d-91a2-427c-c396-7322bd5c3ffd",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        }
      },
      "source": [
        "jobs = [1,1,2,2,5,5,7] # the numbers are lengths(Li) of jobs\n",
        "n_machine = 3\n",
        "max_delta = 7 # permissive maximum delta of M1 - Malpha. select by yourself.\n",
        "A1 = 1\n",
        "A2 = (A1 / max(jobs) ** 2) * 0.9\n",
        "B = (A1 / max(jobs)) * 0.5\n",
        "qubo = Qubo(jobs, n_machine, max_delta, A1, A2, B)\n",
        "annealer = wq.opt()\n",
        "annealer.qubo = qubo.get_qubo()\n",
        "for _ in range(10):\n",
        "    solution = annealer.sa()\n",
        "    qubo.show_answer(solution)\n",
        "    print()"
      ],
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Solution is [1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]\n",
            "Job0 has been assigned to the machine0.\n",
            "Job1 has been assigned to the machine2.\n",
            "Job2 has been assigned to the machine0.\n",
            "Job3 has been assigned to the machine2.\n",
            "Job4 has been assigned to the machine2.\n",
            "Job5 has been assigned to the machine0.\n",
            "Job6 has been assigned to the machine1.\n",
            "Total size of jobs assigned to machine0 is 8.\n",
            "Total size of jobs assigned to machine1 is 7.\n",
            "Total size of jobs assigned to machine2 is 8.\n",
            "\n",
            "Solution is [0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]\n",
            "Job0 has been assigned to the machine2.\n",
            "Job1 has been assigned to the machine1.\n",
            "Job2 has been assigned to the machine0.\n",
            "Job3 has been assigned to the machine2.\n",
            "Job4 has been assigned to the machine1.\n",
            "Job5 has been assigned to the machine2.\n",
            "Job6 has been assigned to the machine0.\n",
            "Total size of jobs assigned to machine0 is 9.\n",
            "Total size of jobs assigned to machine1 is 6.\n",
            "Total size of jobs assigned to machine2 is 8.\n",
            "\n",
            "Solution is [0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]\n",
            "Job0 has been assigned to the machine1.\n",
            "Job1 has been assigned to the machine1.\n",
            "Job2 has been assigned to the machine2.\n",
            "Job3 has been assigned to the machine0.\n",
            "Job4 has been assigned to the machine2.\n",
            "Job5 has been assigned to the machine1.\n",
            "Job6 has been assigned to the machine0.\n",
            "Total size of jobs assigned to machine0 is 9.\n",
            "Total size of jobs assigned to machine1 is 7.\n",
            "Total size of jobs assigned to machine2 is 7.\n",
            "\n",
            "Solution is [0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0]\n",
            "Job0 has been assigned to the machine1.\n",
            "Job1 has been assigned to the machine0.\n",
            "Job2 has been assigned to the machine0.\n",
            "Job3 has been assigned to the machine0.\n",
            "Job4 has been assigned to the machine1.\n",
            "Job5 has been assigned to the machine0.\n",
            "Job6 has been assigned to the machine2.\n",
            "Total size of jobs assigned to machine0 is 10.\n",
            "Total size of jobs assigned to machine1 is 6.\n",
            "Total size of jobs assigned to machine2 is 7.\n",
            "\n",
            "Solution is [0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0]\n",
            "Job0 has been assigned to the machine2.\n",
            "Job1 has been assigned to the machine0.\n",
            "Job2 has been assigned to the machine0.\n",
            "Job3 has been assigned to the machine1.\n",
            "Job4 has been assigned to the machine1.\n",
            "Job5 has been assigned to the machine0.\n",
            "Job6 has been assigned to the machine2.\n",
            "Total size of jobs assigned to machine0 is 8.\n",
            "Total size of jobs assigned to machine1 is 7.\n",
            "Total size of jobs assigned to machine2 is 8.\n",
            "\n",
            "Solution is [1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0]\n",
            "Job0 has been assigned to the machine0.\n",
            "Job1 has been assigned to the machine0.\n",
            "Job2 has been assigned to the machine1.\n",
            "Job3 has been assigned to the machine2.\n",
            "Job4 has been assigned to the machine2.\n",
            "Job5 has been assigned to the machine1.\n",
            "Job6 has been assigned to the machine0.\n",
            "Total size of jobs assigned to machine0 is 9.\n",
            "Total size of jobs assigned to machine1 is 7.\n",
            "Total size of jobs assigned to machine2 is 7.\n",
            "\n",
            "Solution is [0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0]\n",
            "Job0 has been assigned to the machine1.\n",
            "Job1 has been assigned to the machine1.\n",
            "Job2 has been assigned to the machine0.\n",
            "Job3 has been assigned to the machine1.\n",
            "Job4 has been assigned to the machine2.\n",
            "Job5 has been assigned to the machine1.\n",
            "Job6 has been assigned to the machine0.\n",
            "Total size of jobs assigned to machine0 is 9.\n",
            "Total size of jobs assigned to machine1 is 9.\n",
            "Total size of jobs assigned to machine2 is 5.\n",
            "\n",
            "Solution is [0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0]\n",
            "Job0 has been assigned to the machine1.\n",
            "Job1 has been assigned to the machine1.\n",
            "Job2 has been assigned to the machine2.\n",
            "Job3 has been assigned to the machine0.\n",
            "Job4 has been assigned to the machine2.\n",
            "Job5 has been assigned to the machine1.\n",
            "Job6 has been assigned to the machine0.\n",
            "Total size of jobs assigned to machine0 is 9.\n",
            "Total size of jobs assigned to machine1 is 7.\n",
            "Total size of jobs assigned to machine2 is 7.\n",
            "\n",
            "Solution is [0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0]\n",
            "Job0 has been assigned to the machine2.\n",
            "Job1 has been assigned to the machine1.\n",
            "Job2 has been assigned to the machine2.\n",
            "Job3 has been assigned to the machine0.\n",
            "Job4 has been assigned to the machine1.\n",
            "Job5 has been assigned to the machine2.\n",
            "Job6 has been assigned to the machine0.\n",
            "Total size of jobs assigned to machine0 is 9.\n",
            "Total size of jobs assigned to machine1 is 6.\n",
            "Total size of jobs assigned to machine2 is 8.\n",
            "\n",
            "Solution is [0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0]\n",
            "Job0 has been assigned to the machine2.\n",
            "Job1 has been assigned to the machine0.\n",
            "Job2 has been assigned to the machine1.\n",
            "Job3 has been assigned to the machine0.\n",
            "Job4 has been assigned to the machine0.\n",
            "Job5 has been assigned to the machine1.\n",
            "Job6 has been assigned to the machine2.\n",
            "Total size of jobs assigned to machine0 is 8.\n",
            "Total size of jobs assigned to machine1 is 7.\n",
            "Total size of jobs assigned to machine2 is 8.\n",
            "\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "dQ1_VOwNkj6d",
        "colab_type": "text"
      },
      "source": [
        "補助変数まで正確に答えを出すのは難しいですが、答えはそれなりに得られています。"
      ]
    }
  ]
}