{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Resource Constraint Project Scheduling Problem\n",
"\n",
"## 問題設定\n",
"\n",
"本章ではジョブショップスケジューリング問題 (JSSP) を一般化した、資源制約付きプロジェクトスケジューリング問題の定式化について扱います。\n",
"英語の頭文字をとり RCPSP と呼ぶことにします。\n",
"\n",
"RCPSP は JSSP の Machine の概念を一般し、 Resource という概念を導入します。\n",
"Job は複数種類の Resource を適当な個数使用することで処理されます。\n",
"RCPSP は以下のように定義されます。\n",
"\n",
"1. m種類の Resource $R_1, R_2, \\dots, R_m$ にはそれぞれ、使用可能個数 $A_1, A_2, \\dots, A_m$ (Availabily) が定まっている。\n",
"1. n種類の Job $J_1, J_2, \\dots\\ J_n$ にはそれぞれ、処理時間 $D_1, \\dots, D_n$ と要求する資源の個数 (Request) が定まっている。\n",
" * Job $J_i$ は Resource $R_j$ を $N_{i, j}$ 個要求する。\n",
"1. (順序制約) Job には順序関係 (Precedence relations) が定まっている。\n",
" * Job $J_i$ は Job $J_{p_i(1)}, J_{p_i(2)}, \\dots, J_{p_i(n_i)}$ の処理が完了してからしか処理を開始できない。\n",
"1. (資源制約) 同時に処理する Job の要求する資源の個数はその資源の使用可能個数以下でなければならない。\n",
"1. このとき、与えられた評価尺度を最適にするような Job の開始時刻を求める。\n",
" * 全ての Job が完了する時刻の最小化問題を解くことが多い。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## amplify_sched を用いた実装\n",
"\n",
"amplify_sched で RCPSP を解きます。\n",
"PSPLIB から RCPSP の問題をダウンロードします。\n",
"\n",
"PSPLIB: https://www.om-db.wi.tum.de/psplib/main.html"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"%%bash\n",
"# Download rcpsp j30 data from PSPLIB.\n",
"wget -q https://www.om-db.wi.tum.de/psplib/files/j30.sm.zip\n",
"mkdir -p rcpsp/j30\n",
"unzip -q -n j30.sm.zip -d rcpsp/j30"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"PSPLIB のパーサを実装します。パーサの実装は定式化とあまり関係がありませんので、スキップしても問題ありません。"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"from collections import namedtuple\n",
"from dataclasses import dataclass\n",
"\n",
"\n",
"@dataclass\n",
"class RCPSP:\n",
" Pred = namedtuple(\"Pred\", [\"jobnr\", \"num_modes\", \"num_successors\", \"successors\"])\n",
" ReqDur = namedtuple(\"ReqDur\", [\"jobnr\", \"mode\", \"duration\", \"request\"])\n",
" Job = namedtuple(\"Job\", [\"num_modes\", \"successors\", \"duration\", \"request\"])\n",
"\n",
" # Base data\n",
" base_data: str\n",
" initial_value_random_generator: int\n",
" # Overview\n",
" projects: int\n",
" jobs: int\n",
" horizon: int\n",
" renewable: int\n",
" nonrenewable: int\n",
" doubly_constrained: int\n",
" # Project information\n",
" pronr: int\n",
" num_jobs: int\n",
" rel_date: int\n",
" due_date: int\n",
" tard_cost: int\n",
" mpm_time: int\n",
" # Precedence relations\n",
" pred_list: list\n",
" # Request/Durations\n",
" req_dur_list: list\n",
" # Resource availabilities\n",
" avail_list: list\n",
"\n",
" def get_job(self, jobnr: int) -> Job:\n",
" for pred in self.pred_list:\n",
" if pred.jobnr == jobnr:\n",
" num_modes = pred.num_modes\n",
" successors = pred.successors\n",
" break\n",
" duration = dict()\n",
" request = dict()\n",
" for req_dur in self.req_dur_list:\n",
" if req_dur.jobnr == jobnr:\n",
" # Ignore mode\n",
" duration = req_dur.duration\n",
" request = req_dur.request\n",
" break\n",
" return RCPSP.Job(num_modes, successors, duration, request)\n",
"\n",
" def get_jobs(self) -> dict:\n",
" ret = dict()\n",
" for i in range(1, 1 + self.jobs):\n",
" ret[i] = self.get_job(i)\n",
" return ret\n",
"\n",
"\n",
"def parse_rcpsp_file(file_path) -> RCPSP:\n",
" with open(file_path) as f:\n",
" d = f.readlines()\n",
" for i, line in enumerate(d):\n",
" if line.startswith(\"file with basedata : \"):\n",
" base_data = line[32:]\n",
" if line.startswith(\"initial value random generator: \"):\n",
" initial_value_random_generator = int(line[32:])\n",
" if line.startswith(\"projects : \"):\n",
" projects = int(line[32:])\n",
" if line.startswith(\"jobs (incl. supersource/sink ): \"):\n",
" jobs = int(line[32:])\n",
" if line.startswith(\"horizon : \"):\n",
" horizon = int(line[32:])\n",
" if line.startswith(\" - renewable : \"):\n",
" renewable = int(line[32:].split()[0])\n",
" if line.startswith(\" - nonrenewable : \"):\n",
" nonrenewable = int(line[32:].split()[0])\n",
" if line.startswith(\" - doubly constrained : \"):\n",
" doubly_constrained = int(line[32:].split()[0])\n",
" if line.startswith(\"PROJECT INFORMATION:\"):\n",
" pronr, num_jobs, rel_date, due_date, tard_cost, mpm_time = [int(x) for x in d[i + 2].split()]\n",
" if line.startswith(\"PRECEDENCE RELATIONS:\"):\n",
" pred_list = list()\n",
" sum_modes = 0\n",
" for j in range(i + 2, i + 2 + jobs):\n",
" tmp = d[j].split()\n",
" jobnr = int(tmp[0])\n",
" num_modes = int(tmp[1])\n",
" sum_modes += num_modes\n",
" num_successors = int(tmp[2])\n",
" successors = list()\n",
" if num_successors > 0:\n",
" successors = [int(x) for x in tmp[3:]]\n",
" pred_list.append(RCPSP.Pred(jobnr, num_modes, num_successors, successors))\n",
" if line.startswith(\"REQUESTS/DURATIONS:\"):\n",
" req_dur_list = list()\n",
" for j in range(i + 3, i + 3 + sum_modes):\n",
" tmp = d[j][:9].split()\n",
" if len(tmp) > 0:\n",
" jobnr = int(tmp[0])\n",
" tmp = d[j][9:].split()\n",
" mode = int(tmp[0])\n",
" duration = int(tmp[1])\n",
" request = [int(x) for x in tmp[2:]]\n",
" req_dur_list.append(RCPSP.ReqDur(jobnr, mode, duration, request))\n",
" if line.startswith(\"RESOURCEAVAILABILITIES:\"):\n",
" avail_list = [int(x) for x in d[i + 2].split()]\n",
" return RCPSP(\n",
" base_data,\n",
" initial_value_random_generator,\n",
" projects,\n",
" jobs,\n",
" horizon,\n",
" renewable,\n",
" nonrenewable,\n",
" doubly_constrained,\n",
" pronr,\n",
" num_jobs,\n",
" rel_date,\n",
" due_date,\n",
" tard_cost,\n",
" mpm_time,\n",
" pred_list,\n",
" req_dur_list,\n",
" avail_list,\n",
" )"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [],
"source": [
"# Parse file\n",
"file_path = \"rcpsp/j30/j3010_1.sm\"\n",
"problem = parse_rcpsp_file(file_path)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"amplify_sched で RCPSP を定式化します。\n",
"\n",
"amplify_sched は Job を何らかの Machine で実行することを前提としています。\n",
"RCPSP には Machine という概念はありませんので、仮想的に Jobの数だけ Machine を用意し、各 Job は対応した Machine で処理されることとします。\n",
"Machine は対応する一つの Job だけ処理します。\n",
"\n",
"amplify_sched を用いると資源制約は capacity/required_resources 制約として、順序制約は dependent_jobs 制約として実装できます。"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [],
"source": [
"from amplify_sched import *\n",
"\n",
"num_jobs = problem.jobs\n",
"num_machines = num_jobs\n",
"num_resources = problem.renewable\n",
"avail_list = problem.avail_list\n",
"jobs = problem.get_jobs()\n",
"\n",
"model = amplify_sched.Model()\n",
"# Machine を仮想的に Job の数だけ追加する\n",
"for i in range(num_machines):\n",
" model.machines.add(str(i + 1))\n",
"# Job を追加し、処理時間を設定する\n",
"for i in range(num_jobs):\n",
" job_id = str(i + 1)\n",
" machine_id = job_id\n",
" model.jobs.add(job_id)\n",
" model.jobs[job_id].append()\n",
" model.jobs[job_id][0].processing_times[machine_id] = jobs[int(job_id)].duration\n",
"# Resource を追加し、使用可能個数を設定する\n",
"for i in range(num_resources):\n",
" model.resources.add(str(i + 1))\n",
" model.resources[str(i + 1)].capacity = avail_list[i]\n",
"# 資源制約\n",
"for job_id, job in jobs.items():\n",
" for i, request in enumerate(job.request):\n",
" # Resource を request 回追加する\n",
" resource_id = str(i + 1)\n",
" for _ in range(request):\n",
" model.jobs[str(job_id)][0].required_resources.append(resource_id)\n",
"# 順序制約\n",
"for job_id, job in jobs.items():\n",
" for successor in job.successors:\n",
" model.jobs[str(successor)].add_dependent_jobs(str(job_id))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"上で定式化モデルをエンジンで解くと、1秒で最適解に到達することを確認できます。"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'OPTIMAL'"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"token = \"xxxxxxxxxxxxxxxxxxxxxxxxx\"\n",
"gantt = model.solve(token=token, timeout=1)\n",
"gantt.status"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"ガントチャートを表示すると、各 Machine が一つの Job を処理していることを確認できます。"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
" \n",
" "
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"application/vnd.plotly.v1+json": {
"config": {
"plotlyServerURL": "https://plot.ly"
},
"data": [
{
"alignmentgroup": "True",
"base": [
0
],
"customdata": [
[
"1",
0
]
],
"hovertemplate": "Job=%{customdata[0]}
Start=%{base}
Finish=%{x}
Machine=%{y}
Process=%{customdata[1]}
Start=%{base}
Finish=%{x}
Machine=%{y}
Process=%{customdata[1]}
Start=%{base}
Finish=%{x}
Machine=%{y}
Process=%{customdata[1]}
Start=%{base}
Finish=%{x}
Machine=%{y}
Process=%{customdata[1]}
Start=%{base}
Finish=%{x}
Machine=%{y}
Process=%{customdata[1]}
Start=%{base}
Finish=%{x}
Machine=%{y}
Process=%{customdata[1]}
Start=%{base}
Finish=%{x}
Machine=%{y}
Process=%{customdata[1]}
Start=%{base}
Finish=%{x}
Machine=%{y}
Process=%{customdata[1]}
Start=%{base}
Finish=%{x}
Machine=%{y}
Process=%{customdata[1]}
Start=%{base}
Finish=%{x}
Machine=%{y}
Process=%{customdata[1]}
Start=%{base}
Finish=%{x}
Machine=%{y}
Process=%{customdata[1]}
Start=%{base}
Finish=%{x}
Machine=%{y}
Process=%{customdata[1]}
Start=%{base}
Finish=%{x}
Machine=%{y}
Process=%{customdata[1]}
Start=%{base}
Finish=%{x}
Machine=%{y}
Process=%{customdata[1]}
Start=%{base}
Finish=%{x}
Machine=%{y}
Process=%{customdata[1]}
Start=%{base}
Finish=%{x}
Machine=%{y}
Process=%{customdata[1]}
Start=%{base}
Finish=%{x}
Machine=%{y}
Process=%{customdata[1]}
Start=%{base}
Finish=%{x}
Machine=%{y}
Process=%{customdata[1]}
Start=%{base}
Finish=%{x}
Machine=%{y}
Process=%{customdata[1]}
Start=%{base}
Finish=%{x}
Machine=%{y}
Process=%{customdata[1]}
Start=%{base}
Finish=%{x}
Machine=%{y}
Process=%{customdata[1]}
Start=%{base}
Finish=%{x}
Machine=%{y}
Process=%{customdata[1]}
Start=%{base}
Finish=%{x}
Machine=%{y}
Process=%{customdata[1]}
Start=%{base}
Finish=%{x}
Machine=%{y}
Process=%{customdata[1]}
Start=%{base}
Finish=%{x}
Machine=%{y}
Process=%{customdata[1]}
Start=%{base}
Finish=%{x}
Machine=%{y}
Process=%{customdata[1]}
Start=%{base}
Finish=%{x}
Machine=%{y}
Process=%{customdata[1]}
Start=%{base}
Finish=%{x}
Machine=%{y}
Process=%{customdata[1]}
Start=%{base}
Finish=%{x}
Machine=%{y}
Process=%{customdata[1]}
Start=%{base}
Finish=%{x}
Machine=%{y}
Process=%{customdata[1]}
Start=%{base}
Finish=%{x}
Machine=%{y}
Process=%{customdata[1]}
Start=%{base}
Finish=%{x}
Machine=%{y}
Process=%{customdata[1]}