{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# 10-Solving Job Sequencing Problem with PyQUBO\n", "この節では、[Ising formulations of many NP problems](https://arxiv.org/pdf/1302.5843v3.pdf) から6.3. Job Eequencing with Integer LengthsをPyQUBOを用いて解きます。" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "view-in-github" }, "source": [ "[![Open in Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/github/OpenJij/OpenJijTutorial/blob/master/source/ja/010-JobSequencingPyqubo.ipynb)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 整数長ジョブスケジューリング問題\n", "整数長ジョブスケジューリング問題は以下のような状況の最適解を求める問題であり、NP困難な問題の一つです。まずは具体的な問から考えてみましょう。" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 具体例\n", "分かりやすくするために具体的に以下のような問を考えます。\n", "> 10個の仕事と3個のコンピュータがあります。10個の仕事の長さは$1,2,\\cdots,10$です。\n", "> どのようにコンピュータに仕事を割り振れば仕事にかかる時間の最大値$\\max M_\\alpha$を最小化できるか考えます。\n", "> 例えば、$V_1=\\{9,10\\},V_2=\\{1,2,7,8\\},V_3=\\{3,4,5,6\\}$とすると$\\max(M_1,M_2,M_3)=19$となって問の最適解となります。" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "