Reinforcement Learning on RCPSP.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# This is a sandbox for some tests with RCPSPs#"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "import re # regex\n",
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "path = 'path_to_j12060_9.sm'\n",
    "with open(path, \"r\") as f:\n",
    "    file = f.readlines()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's parse the file! It has some unique structure so we will hard-code the different parts. We start with some general data about the project"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>value</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>projects</th>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>jobs (incl. supersource/sink )</th>\n",
       "      <td>122</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>horizon</th>\n",
       "      <td>682</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>pronr.</th>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>#jobs</th>\n",
       "      <td>120</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>rel.date</th>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>duedate</th>\n",
       "      <td>101</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>tardcost</th>\n",
       "      <td>89</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>MPM-Time</th>\n",
       "      <td>101</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                               value\n",
       "projects                           1\n",
       "jobs (incl. supersource/sink )   122\n",
       "horizon                          682\n",
       "pronr.                             1\n",
       "#jobs                            120\n",
       "rel.date                           0\n",
       "duedate                          101\n",
       "tardcost                          89\n",
       "MPM-Time                         101"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "general = {}\n",
    "for line in file[1:3]:\n",
    "    l = list(map(str.strip, line.split(sep = ':')))\n",
    "    general[l[0]] = l[1]\n",
    "\n",
    "project = {}\n",
    "for line in file[4:7]:\n",
    "    l = list(map(str.strip, line.split(sep = ':')))\n",
    "    project[l[0]] = l[1]\n",
    "\n",
    "info = (list(map(str.split, file[13:15])))\n",
    "for i in range(len(info[0])):\n",
    "    project[info[0][i]] = info[1][i]\n",
    "\n",
    "general_df = pd.DataFrame.from_dict(general, orient='index', columns=['value'])\n",
    "project_df = pd.DataFrame.from_dict(project, orient='index', columns=['value'])\n",
    "project_df"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These are the __resources__: The number of renewable resources is usually four but this approach will be able to deal with different numbers of resources as well."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>value</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>renewable</th>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>nonrenewable</th>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>doubly constrained</th>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>R 1</th>\n",
       "      <td>59</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>R 2</th>\n",
       "      <td>58</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>R 3</th>\n",
       "      <td>53</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>R 4</th>\n",
       "      <td>56</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                   value\n",
       "renewable              4\n",
       "nonrenewable           0\n",
       "doubly constrained     0\n",
       "R 1                   59\n",
       "R 2                   58\n",
       "R 3                   53\n",
       "R 4                   56"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "res_sep = re.compile('[RND][ \\d]{2}|[\\d]+') # regex pattern to extract the resources\n",
    "resources = {}\n",
    "for line in file[8:11]:\n",
    "    l = list(map(str.strip, line.replace('-', '').split(sep = ':')))\n",
    "    resources[l[0]] = l[1][0]\n",
    "res = [re.findall(res_sep, file[-3]), re.findall(res_sep, file[-2])]\n",
    "for i, r in enumerate(res[0]):\n",
    "    resources[r] = res[1][i]\n",
    "resources_df = pd.DataFrame.from_dict(resources, orient='index', columns=['value'])\n",
    "resources_df"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, all the __relations__ and __durations__ of the tasks."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "sep = re.compile('[*]+') # regex pattern to find the end of a block; blocks are seperated by a row of ****\n",
    "dur_sep = re.compile('[RND][ \\d]{2}|[\\w.]+')\n",
    "\n",
    "relations = []\n",
    "idx = 17 # start index to find the precedence relations\n",
    "while not re.findall(sep, file[idx]):\n",
    "    relations.append(file[idx])\n",
    "    idx += 1\n",
    "\n",
    "durations = []\n",
    "idx = idx + 4 # start index to find the task's durations. They start four lines after the relations block.\n",
    "header = re.findall(dur_sep, file[idx - 2])\n",
    "while not re.findall(sep, file[idx]):\n",
    "    durations.append(file[idx].strip().split())\n",
    "    idx += 1\n",
    "durations_df = pd.DataFrame(durations, columns=header)\n",
    "\n",
    "relations_df = pd.DataFrame(columns=relations[0].split())\n",
    "for i, rel in enumerate(map(str.split, relations[1:])):\n",
    "    relations_df.loc[i] = [rel[0], rel[1], rel[2], list(map(int, rel[3:]))]\n",
    "\n",
    "# now merge/join both DataFrames and set the columns types to numeric (when possible)\n",
    "df = relations_df.merge(durations_df, how='right', on='jobnr.')\n",
    "df.set_index('jobnr.', inplace=True)\n",
    "df = df.apply(pd.to_numeric, errors='ignore')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "#modes          int64\n",
      "#successors     int64\n",
      "successors     object\n",
      "mode            int64\n",
      "duration        int64\n",
      "R 1             int64\n",
      "R 2             int64\n",
      "R 3             int64\n",
      "R 4             int64\n",
      "dtype: object\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>#modes</th>\n",
       "      <th>#successors</th>\n",
       "      <th>successors</th>\n",
       "      <th>mode</th>\n",
       "      <th>duration</th>\n",
       "      <th>R 1</th>\n",
       "      <th>R 2</th>\n",
       "      <th>R 3</th>\n",
       "      <th>R 4</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>jobnr.</th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>[2, 3, 4]</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>[6, 15, 45]</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>3</td>\n",
       "      <td>8</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>[5, 8, 17]</td>\n",
       "      <td>1</td>\n",
       "      <td>9</td>\n",
       "      <td>6</td>\n",
       "      <td>7</td>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>[7, 9, 11]</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>6</td>\n",
       "      <td>2</td>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>[18, 48, 52]</td>\n",
       "      <td>1</td>\n",
       "      <td>9</td>\n",
       "      <td>9</td>\n",
       "      <td>8</td>\n",
       "      <td>8</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "        #modes  #successors    successors  mode  duration  R 1  R 2  R 3  R 4\n",
       "jobnr.                                                                       \n",
       "1            1            3     [2, 3, 4]     1         0    0    0    0    0\n",
       "2            1            3   [6, 15, 45]     1         1    2    3    8    1\n",
       "3            1            3    [5, 8, 17]     1         9    6    7    1    3\n",
       "4            1            3    [7, 9, 11]     1         2    6    2    3    1\n",
       "5            1            3  [18, 48, 52]     1         9    9    8    8    4"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print(df.dtypes)\n",
    "df.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Basic Random Walk ##\n",
    "Let's go on a walk - a random walk actually. We will start at the first node and randomly choose the next node to visit. We will also add up the time it takes to pass the nodes. We will not consider the resources for now."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "starting with job 1\n",
      "successors: [2, 3, 4] -> next job: 2\n",
      "successors: [6, 15, 45] -> next job: 45\n",
      "successors: [81] -> next job: 81\n",
      "successors: [95] -> next job: 95\n",
      "successors: [106] -> next job: 106\n",
      "successors: [108, 109] -> next job: 108\n",
      "successors: [114] -> next job: 114\n",
      "successors: [115] -> next job: 115\n",
      "successors: [120] -> next job: 120\n",
      "successors: [122] -> next job: 122\n",
      "total duration: 44\n"
     ]
    }
   ],
   "source": [
    "node = df.loc[str(1)]\n",
    "successors = node.successors\n",
    "duration = 0\n",
    "print('starting with job', node.name)\n",
    "\n",
    "while len(successors) > 0:\n",
    "    node = df.loc[str(random.choice(successors))]\n",
    "    print('successors:', successors, '-> next job:', node.name)\n",
    "    successors = node.successors\n",
    "    duration += node.duration\n",
    "\n",
    "print('total duration:', duration)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's have a look at the resource use. We copy the random walk from above and add the constraints: we have only limited resources available (the number of available units is listed in _resource_df_ for each resource) and jobs block those resources for different amounts of time. When no free resources are available to start the next tast we have to wait until a preceding task is completed. We are first going to try a greedy approach and just pick as many tasks as possible to start at each moment."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>limits</th>\n",
       "      <th>available</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>R 1</th>\n",
       "      <td>59</td>\n",
       "      <td>59</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>R 2</th>\n",
       "      <td>58</td>\n",
       "      <td>58</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>R 3</th>\n",
       "      <td>53</td>\n",
       "      <td>53</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>R 4</th>\n",
       "      <td>56</td>\n",
       "      <td>56</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "     limits  available\n",
       "R 1      59         59\n",
       "R 2      58         58\n",
       "R 3      53         53\n",
       "R 4      56         56"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "limits = pd.concat([resources_df.iloc[3:], resources_df.iloc[3:]], axis = 1)\n",
    "limits.columns = ['limits', 'available']\n",
    "limits = limits.apply(pd.to_numeric)\n",
    "limits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "finished: {2: 1, 4: 2, 15: 3, 39: 4, 45: 8, 16: 8, 3: 9, 106: 9, 48: 9, 9: 10, 6: 11, 11: 11, 44: 11, 7: 12, 17: 12, 64: 13, 84: 17, 72: 17, 81: 19, 24: 19, 28: 19, 108: 19, 8: 19, 5: 20, 109: 20, 33: 24, 63: 24, 78: 25, 32: 25, 20: 25, 23: 26, 12: 27, 91: 27, 49: 28, 30: 29, 93: 29, 105: 30, 115: 30, 96: 30, 27: 30, 21: 31, 114: 31, 118: 31, 46: 33, 29: 33, 104: 33, 95: 36, 112: 37, 94: 37, 119: 37, 56: 37, 18: 38, 122: 38}\n"
     ]
    }
   ],
   "source": [
    "successors = list(df.loc[str(1)].successors)\n",
    "duration = 0\n",
    "running_jobs = {}\n",
    "finished_jobs = {}\n",
    "\n",
    "while len(successors) > 0:\n",
    "    # add all jobs to running_jobs as long as the resources are not depleted\n",
    "    for s in successors:\n",
    "        if not s in running_jobs and min(limits.available - df.loc[str(s)][5:]) >= 0:\n",
    "            running_jobs[s] = df.loc[str(s)].duration\n",
    "            limits.available -= df.loc[str(s)][5:]\n",
    "\n",
    "    # move on to the next timestep\n",
    "    duration += 1\n",
    "    for key in list(running_jobs):\n",
    "        running_jobs[key] -= 1\n",
    "\n",
    "        # let's see if a job is finished\n",
    "        if running_jobs[key] <= 0:\n",
    "            if not key in finished_jobs:\n",
    "                finished_jobs[key] = duration\n",
    "            running_jobs.pop(key)\n",
    "            limits.available += df.loc[str(key)][5:]\n",
    "            successors.remove(key)\n",
    "            if len(df.loc[str(key)].successors) > 0:\n",
    "                successors.extend(df.loc[str(key)].successors)\n",
    "            else:\n",
    "                successors = []\n",
    "\n",
    "print('finished:', finished_jobs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is a deterministic solution. It starts at job 1 (which is just a dummy node) and starts all its successors (jobs 2, 3, 4). These jobs finish after different time periods: job 1 is finished at time step 1, job 4 at time step 2 and job 3 at time step 9. The successors of job 2 (jobs 6, 15 and 45) can therefore be started in time step 1 whereas the successors of job 3 (jobs 5, 8, 17) can only be started after job 3 is finished at time step 9.\n",
    "\n",
    "so the path through the network is:\n",
    "- __1 finished in 0 -> 2, 3, 4__\n",
    "- __2 finished in 1 -> 6, 15, 45__\n",
    "- 3 finished in 9 -> 5, 8, 17\n",
    "- 4 finished in 2 -> 7, 9, 11\n",
    "- 5 finished in 20 -> 18\n",
    "- 6 finished in 11 -> 23, 33, 63\n",
    "- 7 finished in 12 -> 12, 27, 29\n",
    "- 8 finished in 19 ->\n",
    "- 9 finished in 10 -> 30, 32, 49\n",
    "- 11 finished in 11 -> 20, 21, 46\n",
    "- 12 finished in 27 ->\n",
    "- __15 finished in 3 -> 16, 39, 44__\n",
    "- 16 finished in 8 -> 24, 28, 64\n",
    "- 17 finished in 12 -> 33\n",
    "- 18 finished in 38 ->\n",
    "- 20 finished in 25 ->\n",
    "- 21 finished in 31 ->\n",
    "- 23 finished in 26 ->\n",
    "- 24 finished in 19 -> 32, 56\n",
    "- 27 finished in 30 ->\n",
    "- 28 finished in 19 ->\n",
    "- 29 finished in 33 ->\n",
    "- 30 finished in 29 ->\n",
    "- 32 finished in 25 ->\n",
    "- 33 finished in 24 ->\n",
    "- __39 finished in 4 -> 48, 106__\n",
    "- 44 finished in 11 -> 105, 109, 115\n",
    "- 45 finished in 8 -> 81\n",
    "- 46 finished in 33 ->\n",
    "- __48 finished in 9 -> 72, 78, 84__\n",
    "- 49 finished in 28 ->\n",
    "- 56 finished in 37 ->\n",
    "- 63 finished in 24 ->\n",
    "- 64 finished in 13 -> 104, 112\n",
    "- 72 finished in 17 -> 91, 94, 96\n",
    "- 78 finished in 25 -> 94\n",
    "- 81 finished in 19 -> 95\n",
    "- __84 finished in 17 -> 93, 118__\n",
    "- 91 finished in 27 ->\n",
    "- 93 finished in 29 ->\n",
    "- 94 finished in 37 ->\n",
    "- 95 finished in 36 ->\n",
    "- 104 finished in 33 ->\n",
    "- 105 finished in 30 -> 112\n",
    "- 106 finished in 9 -> 108, 109\n",
    "- 108 finished in 19 -> 114\n",
    "- 109 finished in 20 ->\n",
    "- 112 finished in 37 ->\n",
    "- 114 finished in 31 ->\n",
    "- 115 finished in 30 ->\n",
    "- __118 finished in 31 -> 119__\n",
    "- __119 finished in 37 -> 122__\n",
    "\n",
    "Going this path takes the algorithm 37 time steps whereas the time steps for the path from the start node 1 to the sink node 122 (1-2-15-39-48-84-118-119-122) would only take 14 time steps. That's far from optimal!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "summed up durations: 14\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>#modes</th>\n",
       "      <th>#successors</th>\n",
       "      <th>successors</th>\n",
       "      <th>mode</th>\n",
       "      <th>duration</th>\n",
       "      <th>R 1</th>\n",
       "      <th>R 2</th>\n",
       "      <th>R 3</th>\n",
       "      <th>R 4</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>jobnr.</th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>[2, 3, 4]</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>[6, 15, 45]</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>3</td>\n",
       "      <td>8</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>15</th>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>[16, 39, 44]</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>6</td>\n",
       "      <td>4</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>39</th>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>[48, 106]</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>6</td>\n",
       "      <td>5</td>\n",
       "      <td>5</td>\n",
       "      <td>6</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>48</th>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>[72, 78, 84]</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>6</td>\n",
       "      <td>6</td>\n",
       "      <td>8</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>84</th>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>[93, 118]</td>\n",
       "      <td>1</td>\n",
       "      <td>5</td>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>6</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>118</th>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>[119]</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>5</td>\n",
       "      <td>9</td>\n",
       "      <td>5</td>\n",
       "      <td>5</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>119</th>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>[122]</td>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>4</td>\n",
       "      <td>1</td>\n",
       "      <td>9</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>122</th>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>[]</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "        #modes  #successors    successors  mode  duration  R 1  R 2  R 3  R 4\n",
       "jobnr.                                                                       \n",
       "1            1            3     [2, 3, 4]     1         0    0    0    0    0\n",
       "2            1            3   [6, 15, 45]     1         1    2    3    8    1\n",
       "15           1            3  [16, 39, 44]     1         2    6    4    2    2\n",
       "39           1            2     [48, 106]     1         1    6    5    5    6\n",
       "48           1            3  [72, 78, 84]     1         1    6    6    8    1\n",
       "84           1            2     [93, 118]     1         5    3    1    3    6\n",
       "118          1            1         [119]     1         1    5    9    5    5\n",
       "119          1            1         [122]     1         3    4    1    9    1\n",
       "122          1            0            []     1         0    0    0    0    0"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "network_path = df.loc[list(map(str, [1, 2, 15, 39, 48, 84, 118, 119, 122]))]\n",
    "print('summed up durations:', sum(network_path.duration))\n",
    "network_path"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Monte Carlo Implementation ##\n",
    "Based on Johannes Meyl's thesis and his pseudo-code description on page 40. There are three phases during the running time of the algorithm:\n",
    "1. Exploration phase - short term (**n_s cycles**)\n",
    "2. Learning phase - mid term (**n_m cycles**)\n",
    "3. Convergence phase (**n_max - n_m - n_s cycles**)\n",
    "\n",
    "There is also a parameter **n_noCha** [1, n_max] that defines the number of cycles during which we must not change the size of the Q-matrix."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "n_s, n_m, n_max, n_noCha = 0, 0, 0, 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Meyl uses different greediness parameters ε during theses phases. We define the function to determine the parameter:\n",
    "\n",
    "$$\\epsilon(n)=\\left\\{\\begin{array}{ll} \\varepsilon_s, & 0 \\leq n \\leq n_s \\\\\n",
    "              \\frac{\\varepsilon_f - \\varepsilon_s}{n_m}(n - n_s) + \\varepsilon_s & n_s < n \\leq n_s + n_m \\text{, with } f_\\varepsilon = 0 \\\\\n",
    "              \\varepsilon_m & n_s < n \\leq n_s + n_m \\text{, with } f_\\varepsilon = 1 \\\\\n",
    "              0 & n_s + n_m < n \\leq n_{max} \\end{array}\\right.$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def epsilon(n, function_type=0, eps_m=0):\n",
    "    '''\n",
    "    Returns the value of the greediness parameter epsilon that depends on the phase\n",
    "    (exploration, learning, convergence) of the algorithm.\n",
    "    function_type -> choose 0 for a for a constant decay and 1 for a constant value eps_m\n",
    "    '''\n",
    "    if 0 <= n <= n_s:\n",
    "        return eps_s\n",
    "    elif n_s < n <= (n_s + n_m):\n",
    "        if function_type:\n",
    "            return eps_m\n",
    "        else:\n",
    "            return (((eps_f - eps_s) / n_m) * (n - n_s) + eps_s)\n",
    "    elif (n_s + n_m) < n <= n_max:\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The reward function can use known project durations *t_min* and *t_max* to encourage the algorithm to improve good solutions even more.\n",
    "\n",
    "$$r(t)=\\left\\{\\begin{array}{ll} 1 - \\left(\\frac{t - t_{min}}{t_{max}}\\right)^{0,4} & f_r = 0 \\\\\n",
    "              \\frac{t - t_{max}}{t_{min} - t_{max}} & f_r = 1 \\end{array}\\right.$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def reward(t, function_type=0):\n",
    "    '''\n",
    "    function_type -> if the times t_min and t_max are unknown choose type 1\n",
    "                     and calculate the times manually.\n",
    "    '''\n",
    "    if function_type:\n",
    "        return (t - t_max) / (t_min - t_max)\n",
    "    else:\n",
    "        return 1 - ((t - t_min) / t_max)**0.4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Meyl implements two different types of learning rates: one uses a constant value around 0.01 and one uses a learning rate that decays linearly during the convergence phase (during (*n_s + n_m*) and *n_max*)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def learning_rate(n, function_type=0, alpha_f=0):\n",
    "    '''\n",
    "    Returns the learning rate alpha that is either a constant value alpha_b\n",
    "    or can be chosen to decay during the convergence phase (for n > n_m + n_s).\n",
    "    function_type -> choose 0 for a function that linearly decays from alpha_b\n",
    "                     to a final value alpha_f during the convergence phase or\n",
    "                     choose 1 for the constant value alpha_b.\n",
    "    '''\n",
    "    if 0 <= n <= (n_s + n_m):\n",
    "        return alpha_b\n",
    "    elif (n_s + n_m) < n <= n_max:\n",
    "        if function_type:\n",
    "            return (((alhpha_b - alpha_f) / (n_m + n_s - n_max)) * (n - n_max)) + alpha_f\n",
    "        else:\n",
    "            return alpha_b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These are the parameters Meyl used in his test run to compare his Monte Carlo Approach with a Q-Learning Algorithm. He runs the algorithm three times for n_max in [1000, 2500, 5000]. He uses:\n",
    "* *function_type 1* for the epsilon function (linear decreasing epsilon during learning phase)\n",
    "* *function_type 1* for the reward function (specified *t_min* and *t_max*)\n",
    "* *function_type 0* for the learning rate (constant learning rate *alpha_b*)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "eps_s, eps_f = 1, 0.05 # function_type 1 -> constant value eps_m\n",
    "alhpha_b = 0.1 # function_type = 0 -> constant value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Meyl uses an object state with with a unique ID and two lists for idle tokens (jobs) that can be started when resources are available and busy tokens for running jobs. We will just use a DataFrame with two columns for easy access to replicate this object as Meyl does not define any other functions for this object."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>idle</th>\n",
       "      <th>busy</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "Empty DataFrame\n",
       "Columns: [idle, busy]\n",
       "Index: []"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "states = pd.DataFrame(columns=['idle', 'busy'])\n",
    "# adding states: states.loc[3] = [[1, 2, 3], [5, 6, 7]]\n",
    "states"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Likewise he defines an action object that is linked to the state object. The action object is linked to a state and has an ID that identifies it uniquely together with the state ID (as we cann usually start different jobs (i.e. start different actions) in each state). The object also keeps a list of all executed jobs. A DataFrame is suitable to replicate the object for now."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>StateID</th>\n",
       "      <th>ActionID</th>\n",
       "      <th>executedJobs</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "Empty DataFrame\n",
       "Columns: [StateID, ActionID, executedJobs]\n",
       "Index: []"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "actions = pd.DataFrame(columns = ['StateID', 'ActionID', 'executedJobs'])\n",
    "# actions.loc[len(actions)] = ['s_1', 'a_1,0', [1, 2, 3]]\n",
    "actions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Meyl's Q-table - that lists states as rows and actions as columns - has a peculiar structure: it has a lot of empty cell values (not zero but empty). This is a Q-table with two states and two actions for state 0, one action for state 1 and two actions for state 2:\n",
    "\n",
    "$$Q(s,a)=\\begin{array}{c c} &\n",
    "\\begin{array}{c c c c c} a_{0,0} & a_{0,1} & a_{1,0} & a_{2,0} & a_{2,1} \\end{array} \n",
    "\\\\\n",
    "\\begin{array}{c c c} s_0 \\\\ s_1 \\\\ s_2 \\end{array} \n",
    "&\n",
    "\\left[\n",
    "\\begin{array}{c c c c c}\n",
    "q_{0,0} & q_{0,1} & & &\\\\\n",
    " & & q_{1,0} & &\\\\\n",
    " & & & q_{2,0} & q_{2,1}\n",
    "\\end{array}\n",
    "\\right]\n",
    "\\end{array}$$\n",
    "\n",
    "We will still implement the Q-table as an actual table. We will stick to the indices of the RCPSP and start with state 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>s_1</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "Empty DataFrame\n",
       "Columns: [s_1]\n",
       "Index: []"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "qtable = pd.DataFrame(columns=['s_1'])\n",
    "# qtable.loc['a_0,0', 's_0'] = 42 # to add action a_0,0\n",
    "# qtable['s_1'] = None\n",
    "qtable"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lese Zustand s_t aus;<br>\n",
    "Speichere st auf Zustandsliste;<br>\n",
    "**if** s_t *ist neu* **then**<br>\n",
    "&emsp; Speichere s_t;<br>\n",
    "**else**<br>\n",
    "&emsp; Finde s_t in Menge aller Zustände S;<br>\n",
    "**end**<br>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = df.loc[str(1)]\n",
    "if not ('s_'+ s.name) in states.index:\n",
    "    states.loc['s_' + s.name] = [[], []]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finde Aktionen a_(t,i) für s_t;<br>\n",
    "**if** eps < Random-Wert zwischen 0 und 1 **then**<br>\n",
    "&emsp; Generiere Entscheidungsliste zufällig;<br>\n",
    "**else**<br>\n",
    "&emsp; **if** s_t *ist neu* **then**<br>\n",
    "&emsp; &emsp; Generiere Entscheidungsliste zufällig;<br>\n",
    "&emsp; **else**<br>\n",
    "&emsp; &emsp; Lese Q-Values Q(s_t, a_(t,i)) jeder a_(t,i) aus;<br>\n",
    "&emsp; &emsp; Finde a_(t,i) mit max_a Q(s_t;a_(t,i));<br>\n",
    "&emsp; &emsp; Lese IDs der auszuführenden Missionen von a_(t,max) aus;<br>\n",
    "&emsp; &emsp; Füge IDs auf Entscheidungsliste hinzu;<br>\n",
    "&emsp; **end**<br>\n",
    "**end**\n",
    "\n",
    "We will need to define some values for n_s, n_m and n_max in order to run the *epsilon*-function we defined above. Meyl does not provide values for n_s and n_m, though. Let's also restructure the code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "n_s, n_m, n_max = 200, 800, 1000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Generiere Entscheidungsliste zufällig\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "if not ('s_' + s.name) in states.index:\n",
    "    states.loc[s.name] = [[], []]\n",
    "    print('Generiere Entscheidungsliste zufällig, weil neuer State')\n",
    "    print(random.choice(df.loc[s.name].successors))\n",
    "elif epsilon(n=1000) < random.random():\n",
    "    print('Generiere Entscheidungsliste zufällig')\n",
    "    print(random.choice(df.loc[s.name].successors))\n",
    "else:\n",
    "    print('Get Q-Values of all actions')\n",
    "    print(actions[actions.StateID == 's_' + s.name])\n",
    "    # ToDo read Q-values and find the best action"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Führe a_(t,max) aus;<br>\n",
    "Speichere a_(t,max) auf Aktionsliste;<br>\n",
    "Lese s_(t+1) aus;<br>\n",
    "**if** s_t = finaler Zustand **then**<br>\n",
    "&emsp; Berechne Belohnung r_(t+1);<br>\n",
    "&emsp; **for** j = 0 to Zustandslistenlänge **do**<br>\n",
    "&emsp; &emsp; Q(s_(t−j); a_(t−j,max)) ← Q(s_(t−j, a_(t−j,max)) + α[r_(t+1) − Q(s_(t−j, a_(t−j,max))];<br>\n",
    "&emsp; **end**<br>\n",
    "**else**<br>\n",
    "**end**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}